SQL tree traversal

Question

I am not totally sure I am naming this right, but please bear with me.

I am wondering if is possible to do something like this in SQL(MySQL specifically): Let's say we have tree-like data that is persisted in the database in the following table:

  mysql> desc data_table;
  +------------------------+---------------------+------+-----+---------+----------------+
  | Field                  | Type                | Null | Key | Default | Extra          |
  +------------------------+---------------------+------+-----+---------+----------------+
  | id                     | int(10) unsigned    | NO   | PRI | NULL    | auto_increment |
  | parent_id              | int(10) unsigned    | YES  | MUL | NULL    |                |
  | value                  | text                | YES  |     | NULL    |                |

So each row has a parent, except for the 'root' row and each row has children except for leaf rows.

Is it possible to find all descendants of any given row utilizing solely SQL?

Answer 1

It's possible to fetch all descendants utilizing solely SQL, but not in a single query. But I'm sure you figured that out; I assume you mean you want to do it in a single query.

You might be interested in reading about some alternative designs to store tree structures, that do enable you to fetch all descendants using a single SQL query. See my presentation Models for Hierarchical Data with SQL and PHP.

You can also use recursive SQL queries with other brands of database (e.g. PostgreSQL), but MySQL does not currently support this feature.

Answer 2

You're probably better of with the nested set model instead (see http://dev.mysql.com/tech-resources/articles/hierarchical-data.html - further down). Its far more efficient for selects and you can get the complete path to each node with a simple self join. However, in practice it is a good idea to pre-cache path and depth if you want to do things like " where depth = 3" or want to show the complete path for multiple nodes if you have more than 1000 records in your table.