Recursion in a single MySQL query?

Question

I have set up a network/tree and now, starting at one node, I'm trying to select all nodes that lie between this one and another node – all in one query.

Assume two tables, one for storing objects with attributes and one for storing their (direct) relationships. Let's keep the example simple.

CREATE TABLE objects (id varchar(64) PRIMARY KEY);
INSERT INTO objects VALUES ('seat'), ('chair'), ('furniture'), ('barstool'), ('stool');

CREATE TABLE parentships ( parent varchar(64) NOT NULL, child varchar(64) NOT NULL, PRIMARY KEY (parent, child), CONSTRAINT fk_child FOREIGN KEY (child) REFERENCES objects (id), CONSTRAINT fk_parent FOREIGN KEY (parent) REFERENCES objects (id) );
INSERT INTO parentships VALUES ('furniture', 'seat'), ('seat', 'chair'), ('seat', 'stool'), ('stool', 'barstool');

Furniture is the root/end node. Let me try to visualize this small network/tree.

furniture --- seat -+- chair
                    |
                    +- stool --- barstool

I assume that I need to create a recursion with SUBSELECT, LOOP and procedures but I've never used LOOP nor self-made procedures before. Maybe you can help me explain things while I'll continue to search/try on my own.

{magic query (parameter 'barstool')}

+-----------+
| parent    |
+-----------+   <--- This is what I want.
| stool     |
| chair     |
| seat      |
| furniture |
+-----------+

I've already figured out a way to manually do the first two steps of iterations.

SET @p = '';
SET @p = ( SELECT parent FROM parentships WHERE child IN ('barstool', @p) );

SELECT parent FROM parentships WHERE child IN ('barstool', @p);

But the documentation for loops is confusing me. This is my attempt but I'm getting error messages:

CREATE PROCEDURE find_all_ancestors(node varchar)
BEGIN
  SET @p = '';
  label1: LOOP
    SET @p = ( SELECT parent FROM parentships WHERE child IN (node, @p) );
    IF @p != 'furniture' THEN
      ITERATE label1
    END IF
    LEAVE label1
  END LOOP label1
  SET @x = @p
END

But I'm getting several error messages, starting with this one:

ERROR 1064 (42000): You have an error in your SQL syntax; check the manual that corresponds to your MySQL server version for the right syntax to use near 'label1: LOOP
    SET @p = ( SELECT parent FROM parentships WHERE child ' at line 4

Also, I would need to add the iterated @p to an array of intermediate results anyway and MySQL doesn't allow arrays. So maybe I'm using the wrong approach altogether.

Cheers.

Answer 1

Try below version - this is your code just slightly modified. After executing it returns comma delimited list with respective values.

I have placed also some comments into the code.

DELIMITER // /* It enables the ; delimiter used in the procedure body to be passed through to the server rather than being interpreted by mysql itself*/

DROP PROCEDURE IF EXISTS find_all_ancestors // 

CREATE PROCEDURE find_all_ancestors(node varchar(100)) # /*Need to define number of characters for varchar */

BEGIN

  SET @p = node;
  SET @s = '';
  SET @pc = '';
  SET @c = 0;

  label1: LOOP

    IF @p != 'furniture' AND @p IN (@s) = 0 THEN

        SET @c = @c + 1;

        SET @p = ( SELECT parent FROM parentships WHERE child IN (@p) LIMIT 1 );

        SET @s = CONCAT(@s,',',@p);

        IF @c = 2 AND @p IN (@s) = 0 THEN

            SET @pc = ( SELECT child FROM parentships WHERE parent IN (@p) LIMIT 1 );

            SET @s = CONCAT(@s,',',@pc);

        END IF;

        ITERATE label1;

    END IF;

    LEAVE label1;

  END LOOP label1;

    SELECT SUBSTRING(@s,2,100) AS RESULT FROM DUAL; 

END //

DELIMITER ;

Once you create the procedure you can run it:

CALL find_all_ancestors('barstool');

Also look for some stuff about hierarchical retrieval - https://www.google.com/search?q=hierarchical+retrieval+in+mysql. It could be helpful for you.

There are many others ways of doing this kind of things. Depending on you needs.