What are the Options for Storing Hierarchical Data in a Relational Database?

Question

Good Overviews

• One more Nested Intervals vs. Adjacency List comparison: the best comparison of Adjacency List, Materialized Path, Nested Set and Nested Interval I've found.
• Models for hierarchical data: slides with good explanations of tradeoffs and example usage
• Representing hierarchies in MySQL: very good overview of Nested Set in particular
• Hierarchical data in RDBMSs: most comprehensive and well organized set of links I've seen, but not much in the way on explanation

Options

Ones I am aware of and general features:

1. Adjacency List:
   • Columns: ID, ParentID
   • Easy to implement.
   • Cheap node moves, inserts, and deletes.
   • Expensive to find level (can store as a computed column), ancestry & descendants (Bridge Hierarchy combined with level column can solve), path (Lineage Column can solve).
   • Use Common Table Expressions in those databases that support them to traverse.
2. Nested Set (a.k.a Modified Preorder Tree Traversal)
   • First described by Joe Celko - covered in depth in his book Trees and Hierarchies in SQL for Smarties
   • Columns: Left, Right
   • Cheap level, ancestry, descendants
   • Compared to Adjacency List, moves, inserts, deletes more expensive.
   • Requires a specific sort order (e.g. created). So sorting all descendants in a different order requires additional work.
3. Nested Intervals
   • Combination of Nested Sets and Materialized Path where left/right columns are floating point decimals instead of integers and encode the path information.
4. Bridge Table (a.k.a. Closure Table)
   • Columns: ancestor, descendant
   • Stands apart from table it describes.
   • Can include some nodes in more than one hierarchy.
   • Cheap ancestry and descendants (albeit not in what order)
   • For complete knowledge of a hierarchy needs to be combined with another option.
5. Flat Table
   • A modification of the Adjacency List that adds a Level and Rank (e.g. ordering) column to each record.
   • Expensive move and delete
   • Cheap ancestry and descendants
   • Good Use: threaded discussion - forums / blog comments
6. Lineage Column (a.k.a. Materialized Path)
   • Column: lineage (e.g. /parent/child/grandchild/etc...)
   • Limit to how deep the hierarchy can be.

Database Specific Notes

MySQL

• Use session variables for Adjacency List

Oracle

• Use CONNECT BY to traverse Adjacency Lists

PostgreSQL

• ltree datatype for Materialized Path

SQL Server

• General summary
• 2008 offers HierarchyId data type appears to help with Lineage Column approach and expand the depth that can be represented.

Answer 1

This is a very partial answer to your question, but I hope still useful.

Microsoft SQL Server 2008 implements two features that are extremely useful for managing hierarchical data:

• the HierarchyId data type.
• common table expressions, using the with keyword.

Have a look at this article for starts. See also my own question here.

Answer 2

Joe Celko wrote the book on SQL Trees & Hiearichies

Answer 3

Some articles from my blog on the subject:

• Adjacency list vs. nested sets: MySQL
• Adjacency list vs. nested sets: PostgreSQL
• Adjacency list vs. nested sets: Oracle

• Adjacency list vs. nested sets: SQL Server

• Hierarchical queries in MySQL (querying adjacency lists in MySQL)

Answer 4

This is kind of a question that is still interesting even after all big 3 vendors implemented Recursive WITH clause. I'd suggest that different readers would be pleased with different answers.

1. Comprehensive list of references by Troels Arvin (although it seems to be missing many recent fine articles mentioned in similar stackoverflow threads).
2. For the lack of competition, introductory textbook by Joe Celko "Trees and Hierarchies in SQL for Smarties" can indeed be considered a classics.
3. For mathematical sophistry and connections between various methods look up Tropashko publications.