Materialized Path + Nested Sets

I Have found four methods used to encode tree structures in relational databases:

1. Adjacency List
2. Materialized Paths
3. Nested Sets
4. 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:

Account catalog:

There is an account catalog with a code, name and type(M=Internal node, D=Leaf node) fileds.

The problem:

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.

The schema:

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.

Sample data:

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 ‘1.1.2.10′

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:

• schema.sql
• sample-data.sql
• sample-quieries.sql