Is it possible to query a tree structure table in MySQL in a single query, to any depth?

Question

I'm thinking the answer is no, but I'd love it it anybody had any insight into how to crawl a tree structure to any depth in SQL (MySQL), but with a single query

More specifically, given a tree structured table (id, data, data, parent_id), and one row in the table, is it possible to get all descendants (child/grandchild/etc), or for that matter all ancestors (parent/grandparent/etc) without knowing how far down or up it will go, using a single query?

Or is using some kind of recursion require, where I keep querying deeper until there are no new results?

Specifically, I'm using Ruby and Rails, but I'm guessing that's not very relevant.

Thanks in advance for any advice!!

Answer 1

You're almost definitely going to want to employ some recursion for that. And if you're doing that, then it would be trivial (in fact easier) to get the entire tree rather than bits of it to a fixed depth.

In really rough pseudo-code you'll want something along these lines:

getChildren(parent){
    children = query(SELECT * FROM table WHERE parent_id = parent.id)
    return children
}

printTree(root){
    print root
    children = getChildren(root)
    for child in children {
        printTree(child)
    }
}

Although in practice you'd rarely want to do something like this. It will be rather inefficient since it's making one request for every row in the table, so it'll only be sensible for either small tables, or trees that aren't nested too deeply. To be honest, in either case you probably want to limit the depth.

However, given the popularity of these kinds of data structure, there may very well be some MySQL stuff to help you with this, specifically to cut down on the numbers of queries you need to make.

Edit: Having thought about it, it makes very little sense to make all these queries. If you're reading the entire table anyway, then you can just slurp the whole thing into RAM - assuming it's small enough!

Answer 2

Here are several resources:

http://forums.mysql.com/read.php?10,32818,32818#msg-32818

http://dev.mysql.com/tech-resources/articles/hierarchical-data.html

http://lists.mysql.com/mysql/201896

Basically, you'll need to do some sort of cursor in a sproc or query or build an adjacency table. I'd avoid recursion outside of the db, depending on how deep your tree is that could get really slow/sketchy.

Answer 3

SQL isn't a Turing Complete language, which means you're not going to be able to perform this sort of looping. You can do some very clever things with SQL and tree structures, but I can't think of a way to describe a row which has a certain id "in its hierarchy" for a hierarchy of arbitrary depth.

Your best bet is something along the lines of what @Dan suggested, which is to just work your way through the tree in some other, more capable language. You can actually generate a query string in a general-purpose language using a loop, where the query is just some convoluted series of joins (or sub-queries) which reflects the depth of the hierarchy you are looking for. That would be more efficient than looping and multiple queries.

Answer 4

I came across this problem before and had one wacky idea. You could store a field in each record that is concatenated string of it's direct ancestors' ids all the way back to the root.

Imagine you had records like this (indentation implies heirarchy and the numbers are id, ancestors.

• 1, "1"
  • 2, "2,1"
    • 5, "5,2,1"
    • 6, "6,2,1"
      • 7, "7,6,2,1"
      • 11, "11,6,2,1"
  • 3, "3,1"
    • 8, "8,3,1"
    • 9, "9,3,1"
    • 10, "10,3,1"

Then to select the descendents of id:6, just do this

SELECT FROM table WHERE ancestors LIKE "%6,2,1"

Keeping the ancestors column up to date might be more trouble than it's worth to you, but it's feasible solution in any DB.

Answer 5

Yes, this is possible, it's a called a Modified Preorder Tree Traversal, as best described here

Joe Celko's Trees and Hierarchies in SQL for Smarties

A working example (in PHP) is provided here

http://www.sitepoint.com/article/hierarchical-data-database/2/

Answer 6

Celko's technique (nested sets) is pretty good. I also have used an adjacency table with fields "ancestor" and "descendant" and "distance" (e.g. direct children/parents have a distance of 1, grandchildren/grandparents have a distance of 2, etc).

This needs to be maintained, but is fairly easy to do for inserts: you use a transaction, then put the direct link (parent, child, distance=1) into the table, then INSERT IGNORE a SELECTion of existing parent&children by adding distances (I can pull up the SQL when I have a chance), which wants an index on each of the 3 fields for performance. Where this approach gets ugly is for deletions... you basically have to mark all the items that have been affected and then rebuild them. But an advantage of this is that it can handle arbitrary acyclic graphs, whereas the nested set model can only do straight hierarchies (e.g. each item except the root has one and only one parent).

Answer 7

I found this site to be a useful resource in learning how to create a similar query:

http://www.webinade.com/web-development/creating-recursive-sql-calls-for-tables-with-parent-child-relationships

Answer 8

am on a similar project myself and this is how am storing data;

----------------+----------------
| Child | Parent |
----------------+----------------
|MemberID | ParentID |
----------------+----------------

now each of this Ids has about 9 characters.

am able to get the children with no stress using Select * from table where Parent=MemberID it works perfect

now my problem is how to get the descendants and ancestors.

I cnt use daniel bearsely's code of duplicating ids in all parent rows cos what if during the insertion of new data there is a break in sql and I need to delete the data already stored. this is just gonna complicate my work and obviously am not take a lot of data cos each member here has up to 32, 000 and even more desendants. imagine the data going in and out.

What I need is a logic of how to easily get the descendants especially then I can put it into code.

thanks in advance.