Pure Performance Inc

SQL databases are not designed for hierarchical data since the data is stored in flat relational tables with no built in parent-child relationship methods (Oracle does have the connect_by function to help).  XML databases on the other hand are built for hierarchical data.

So with SQL databases we have a problem that requires a solution.  Thanks to the SQL gurus out there we have three models to resolve this issue.  In this post I will point you to these resources.

What is hierarchical data?  The best example of a hierarchical model is a company organizational chart; other examples are product categories, forum categories and site maps.  With a hierarchical model you have a tree like structure that needs to be traversed to get to the node you’re looking for.

The Adjacency list model

This is the simplest method to implement, but it’s the slowest due to recursion.  So if you know the table will be large, use one of the other models. For a small table this would be the answer.

You simply add a parent column that links to the parent entry.  The root entry will be NULL because it does not link to any other node.

Traversing the table

SELECT t1.name AS lev1, t2.name as lev2, t3.name as lev3, t4.name as lev4

FROM category t1

LEFT JOIN category  t2 ON t2.cat_parent = t1.cat_id

LEFT JOIN category  t3 ON t3.cat_parent = t2.cat_id

LEFT JOIN category  t4 ON t4.cat_parent = t3.cat_id

WHERE t1.name = ‘Home’;

Resources

Trees in Oracle (using connect by)

Adjacency list defined

Adjacency list model (Joe Celko )

Materialized Path model

The idea with the Materialized path model is to link each node in the hierarchy with its position in the tree.  This is done with a concatenated list of all the nodes ancestors.  This list is usually stored in a delimited string.  Note the “Linage” field below.

Traversing the table

Select lpad(‘-’,length(t1.lineage))||t1.name listing

From category t1, category t2

Where t1.lineage like t2.lineage ||’%’

And t2.name = ‘Home’;

Order by t1.lineage;

Resources

More Trees & Hierarchies in SQL

Trees in SQL

Using Materialized Path to create a paths table

The Nested Set Model

This is the best model for selecting information out of a relational database but slow in adding and deleting. So if you have a static structure this would be your choice.

This model has been championed by Joe Celko and is detailed in his articles and book “Trees and Hierarchies in SQL for Smarties
“.

Nested Set Model

Traversing the table

(t2 is the parent)

SELECT  lpad(‘-’,COUNT(t2.name)-1)||t1.name,t1.left_node

FROM category t1,category t2

WHERE t1.left_node BETWEEN t2.left_node AND t2.right_node

GROUP BY t1.left_node,t1.name

order by t1.left_node;

Resources

Storing Hierarchical Data in a Database (using PHP)

Managing Hierarchical data in MySql

Sql for Smarities article (Joe Celko)

Nested Set Model defined

Definitions

Node – Abstract basic unit used to build linked data structures. Each node contains data and possibly links to other nodes.

Root – Node with no parents.

Leaf – Node with no children

Child – direct subordinate node.

Sibling – Node that shares the same parent.

Ancestors – Parent or other superior node.

Descendants – all subordinate nodes

Be Sociable, Share!

•