SQL finding ancestors/decendants in a self-referencing table

Question

I have a table which references itself, like this:

CREATE TABLE Foo (
id INT NOT NULL AUTO_INCREMENT PRIMARY KEY,
parent INT NULL,
name VARCHAR (30) NOT NULL,
FOREIGN KEY (parent) REFERENCES Foo(id) ON DELETE CASCADE);

Sample data:

id   parent name
1    NULL   a
2    NULL   b
3    1      a1
4    1      a2
5    3      a1x
6    3      a2x

I want to write queries which will list the ancestors and decenders of a given row, e.g.

CALL find_ancestors('a1x')

Will return

id name
3  a1
1  a

and

CALL find_descendants('a')

Will return

id name
3  a1
5  a1x

How can I write these stored procedures for MySQL 5? Thanks

Bonus question for bounty: also select the distance of the returned row from the source and pass a maximum-distance parameter to the procedure, e.g.

CALL find_ancestors('a1x')

Will return

id name distance
3  a1   1
1  a    2

and

CALL find_ancestors_bounded('a1x',1)

Will return

id name distance
3  a1   1

I've considered reading "Joe Celko's Trees and Hierarchies in SQL for Smarties", which covers these kinds of problems. It's fascinating theoretical stuff, but I've always wondered for sql trees, what do people actually use them for in practice? — Mike Ryan, Feb 15 '12 at 14:54
Ahh. Thanks. It feels inadequate to say "Read this book" as my answer, so I'm not putting this in as an answer. But Celko's book above is pretty much the bible. For another explanation of it, see [StackOverflow: Is it possible to query a tree structure table in MySQL in a single query, to any depth?](http://stackoverflow.com/questions/169817/is-it-possible-to-query-a-tree-structure-table-in-mysql-in-a-single-query-to-an) — Mike Ryan, Feb 15 '12 at 15:58
The above seems to be dealing with binary trees, or at least the linked example does. And, not having the book to hand, I'd love to award points to n-ary example code. — spraff, Feb 15 '12 at 16:09
Though the example given in the answer is a binary tree, I don't think there's anything in the technique that limits it to a binary tree. (Note that the Modified Preorder Tree Traversal technique pretty much requires that your data be fixed -- with large dynamic trees, your db would be hosed by constantly reordering the tree.) Iterative solutions by stored proc would allow you to keep your structure unchanged though. — Mike Ryan, Feb 15 '12 at 16:22
@Mike Ryan - I most commonly see this where people are constructing a menu on a web site. The menu choices are hierarchical, stored in the database, and constructed on the fly. This sort of thing allows changing menu options or items without having to change lots of page code. At least, that is what I think they are doing. — mikeY, Apr 18 '13 at 14:26
I found your question looking for answers, I didn't come up with the solution but seeing so little answers for this question I thought I would take the time to come to SO a link people to the solution, so others can solve this faster, kudos to Rolando, He is my personal DBA Hero for this clever solution. http://dba.stackexchange.com/questions/7147/find-highest-level-of-a-hierarchical-field-with-vs-without-ctes — Gabriel Acosta, Apr 18 '13 at 13:54

Gabriel Acosta · Answer 1 · 2013-05-26T14:45:42.220

Lets say we have a table with four elements, id, item, class and parent_id. We want to have the complete Ancestors of any given Item, what we need to do is a custom mysql function that will actually loop through every record looking for a match for our item parent_id, once it founds a match, if the matched item has a parent_id, it will start looping again, and so forth. Every time our function finds a match, it will store it in a comma separated string that will be returned in the end (ex: 1,2,3,4)

Our function would look something like this:

DELIMITER $$
DROP FUNCTION IF EXISTS `junk`.`GetAncestry` $$
CREATE FUNCTION `junk`.`GetAncestry` (GivenID INT) RETURNS VARCHAR(1024)
DETERMINISTIC
BEGIN
    DECLARE rv VARCHAR(1024);
    DECLARE cm CHAR(1);
    DECLARE ch INT;

    SET rv = '';
    SET cm = '';
    SET ch = GivenID;
    WHILE ch > 0 DO
        SELECT IFNULL(parent_id,-1) INTO ch FROM
        (SELECT parent_id FROM pctable WHERE id = ch) A;
        IF ch > 0 THEN
            SET rv = CONCAT(rv,cm,ch);
            SET cm = ',';
        END IF;
    END WHILE;
    RETURN rv;
END $$
DELIMITER ;

This code is authored by RolandoMySQLDBA

SQL finding ancestors/decendants in a self-referencing table

1 Answers1