J2EE, JEE, PHP
Frank D. Martínez's Blog
Software & Fun
Welcome to my technical blog. Here you can find my opinions and proposals over many software development things, mainly on open source projects.
Materialized Path + Nested Sets
I Have found four methods used to encode tree structures in relational databases:
- Adjacency List
- Materialized Paths
- Nested Sets
- Nested intervals
Please read this good article first: http://www.dbazine.com/oracle/or-articles/tropashko4
Each one has its advantages and disadvantages, and I have used Adjacency Lists and Materialized paths many times in different kinds of applications.
Now I will try a mixed approach: Materialized Path + Nested Sets.
The basic idea is to use Materialized paths and at the same time use the path as a boundary of nested sets (children). This method is not suitable for all problems but it is enough in many cases. You can Insert and Delete Tree elements with a simple SQL sentence and extract hierarchic information and aggregated values with simple queries.
Lets do it with an example:
There is an account catalog with a code, name and type(M=Internal node, D=Leaf node) fileds.
We want to store account balances of the leaf nodes and then make a query that retrieves the all tree with all aggregated balances calculated by the fly.
First we want to redesign the database and separate the account’s data from the tree structure:
Now we can encode the tree structure using a mixed form of materilized path and nested sets in the account_struct table and store balances and account data in the account table.
Now insert some data to play with:
The Idea is simple: left_ is the materialized path and right_ is the materialized path with an endign ‘Z’ character. So we can make queries using left_ between ‘1.1’ and ‘1.1Z’ instead of left_ like ‘1.1%’
It is all. Now we can make some interesting queries:
1. All ancestors of ‘18.104.22.168’
2. All children of ‘1.2’
3. General Balance sheet
4. Balance sheet of ‘1.1’
5. Balance of ‘1.2.1.05’ and its ancestors
I will play with this method in a small accounting (book keeping) application. I will publish any issue if I found any.
Download the SQL sample code:
This site contains personal opinions about many things and does not intend to be normative in any aspect.
Java, J2EE, J2SE, JEE, Are trademarks of Sun Microsystems Inc.