Traversing tree-like data in a relational database using SQL

Question

Is there a way to traverse tree data in SQL? I know about connect by in Oracle, but is there another way to do this in other SQL implementations? I'm asking because using connect by is easier than writing a loop or recursive function to run the query for each result.

Since some people seem to be confused by the phrase "tree data" I will explain further: What I mean is with regards to tables which have a parent_id or similar field which contains a primary key from another row in the same table.

The question comes from an experience where I was working with data stored in this way in an Oracle database and knew that the connect by isn't implemented in other DBMSs. If one were to use standard SQL, one would have to create a new table alias for each parent one would want to go up. This could easily get out of hand.

Answer 1

Celko's book is a good resource - if a bit overly "academic" at times.

I also have really found this method, known as 'closure tables' to work fairly well.

If you're using a database that allows recursive CTEs (such as PostgreSQL 8.4 or newer, or SQL Server 2005 or newer), they're really the best way to go. If you're on Oracle, there's always the venerable "connect by".

It is my experience that it's far more common to be handed a set of tables in a "naive tree" schema, and have to figure out how to extract the correct tree from that storage, than it is to have an opportunity to create the cleaner "closure tables" structure.

Answer 2

A recursive CTE is going to be your easiest solution. SQL Server 2005 and current versions of PostgreSQL support CTEs. If you're using SQL Server 2008 or newer, you could use the HIERARCHYID data type. You can find a good example of this at HierarchyID: Model Your Data Hierarchies with SQL Server 2008

Additional resources:

• SQL Server 2008 – HierarchyID – Part I
• SQL Server 2008 – HierarchyID – Part II
• SQL Server 2008 Hierarchies and HierarchyID
• The HierarchyID Datatype in SQL Server 2008

Answer 3

In SQL Server (2005 and later editions) you can use Common Table Expressions for reading hierarchies, see Microsoft SQL Server 2005 - CTE Example of a simple hierarchy for a couple of examples.

I have been recommended a book on the subject more generally which is "Trees and Hierarchies in SQL for Smarties" by Joe Celko - though I've not actually looked at the book myself yet.

Answer 4

The standard SQL method is a “Recursive query” which is provided by the Recursive CTE and designated as WITH [ RECURSIVE ] in the query. The implementation isn't specified in the spec, only the methods made available to query structures that are recursive. In the simplest case implementation of the data structure only requires an ID and Parent ID on a row.

There are also a lot of RDBMS-specific solutions: for instance, PostgreSQL supports Recursive CTEs, but it also provides ltree which provides a different set of advantages and disadvantages in the implementation.

You can find more information on this site by searching through the hierarchy tag.