check if a child is a descendant using a single mysql query

Question

Suppose I have this table

parent | child 
   1       2        
   1       3        
   2       4        
   4       5        
   5       6

and I want to check if 6 is a descendant of 1 (which it is)....can I accomplish this within one single query, or will I have to inevitably get all data and process them with PHP?

score 1 · Answer 1 · edited May 23 '17 at 12:29

That's a tree (or a graph if one node could have more than one parent)... Every node of the tree knows only is parent, you can't parse the tree structure backwards with a single "hop".

Or better, you could, but only if you save the full path from the node to the root of the tree into the node db line, like this...

parent | child | path
   1       3      3,1
   3       2      2,3,1

And so on...

You could also read this: O(1) algorithm to determine if node is descendant of another node in a multiway tree?

score 1 · Answer 2 · answered Jun 18 '12 at 21:26

1

To do this in a single query requires recursive syntax, which mysql does not support. Oracle uses with ... connect by prior and SqlServer uses CTE (Common Table Expressions) for recursing.

Essentially, you will have to query and parse using PHP or create a temporary table using a stored procedure to do the recursion programmatically.

answered Jun 18 '12 at 21:26

Joe

214
1
5

.. and PostgreSQL doet it with `WITH RECURSIVE` – Wrikken Jun 18 '12 at 21:29

score 1 · Accepted Answer · edited May 23 '17 at 12:12

You can walk the tree using recursion in MySQL without processing the data in PHP. MySQL doesn't support true recursion though, so you'd have to settle for some recursive-ish techniques:

One method is described in this SO question, but would involve changing your tables.

Another method would be by using a stored function, which will loop through the table until the job is done (which is recursive in a way). This would probably work with your current table, but is more complex to achieve.

I have an example right here that walks a TYPO3 pages table, finding all page ID's for a given rootline (comparable to what you're trying to achieve):

BEGIN
        DECLARE _id INT;
        DECLARE _parent INT;
        DECLARE _next INT;
        DECLARE CONTINUE HANDLER FOR NOT FOUND SET @id = NULL;

        SET _parent = @id;
        SET _id = -1;

        IF @id IS NULL THEN
                RETURN NULL;
        END IF;

        LOOP
                SELECT  MIN(uid)
                INTO    @id
                FROM    pages
                WHERE   pid = _parent
                AND uid > _id
                AND deleted = 0
                AND hidden =0;                
                IF @id IS NOT NULL OR _parent = @start_with THEN
                        SET @level = @level + 1;
                        RETURN @id;
                END IF;
                SET @level := @level - 1;
                SELECT  uid, pid
                INTO    _id, _parent
                FROM    pages
                WHERE   uid = _parent
                AND     deleted = 0
                AND     hidden = 0;
        END LOOP;
END

Excuse me for not having the time right now to tailor this example to your needs, making this an incomplete answer, but I'm hoping this can get you on the right track nonetheless.

Well, I imagine there are more efficient solutions possible with different data models. Within TYPO3 we don't have the option to change one of the primary tables though, so we have to settle for this. And it actually works quite well; We use it regularly on large installations (multiple thousands of pages in the table) and the function delivers instant results there. Load increase is neglectable compared to the cycles the rest of the software pulls. — Rem.co, Jun 19 '12 at 13:47

check if a child is a descendant using a single mysql query

3 Answers3