Sequential Recursive Query

Dev Shed Forums Sponsor:

October 5th, 2012, 10:13 AM

YoungL

Registered User

Join Date: May 2011

Posts: 11

Time spent in forums: 2 h 15 m 42 sec
Reputation Power: 0

Sequential Recursive Query

Im trying to store a daisy chain link in a MySQL database. Each link will have a start value and an end value. The end value from one row will equal the from value on another row. These may or may not be in order.

For example:

ConnectionTbl
--------------

FromVal | ToVal
---------------
1 | 2
---------------
2 | 3
---------------
5 | 1
---------------
7 | 8
---------------
4 | 7

I need to write a query which will take a point in the from column and give a list of related rows... EG:

5 -> 1 -> 2 -> 3

Given the value of 2 in the from table.

The idea is that you will be able to go to any point and figure the start and end point.

The data can be manipulated in php afterwards, for the time being we just need the full list of data associated with that given value.

ToVal is effectively a ForeignKey to the PrimaryKey FromVal

Thanks for your help in advance!

October 5th, 2012, 10:32 AM

cafelatte

Contributing User

Dev Shed Intermediate (1500 - 1999 posts)

Join Date: Mar 2008

Posts: 1,923

Time spent in forums: 1 Month 5 Days 16 h 21 m 8 sec
Reputation Power: 377

How long is the longest conceivable path?

(I'm not entirely sure that knowing the answer to this will lead me to a solution!)

Last edited by cafelatte : October 5th, 2012 at 10:58 AM.

October 5th, 2012, 11:37 AM

YoungL

Registered User

Join Date: May 2011

Posts: 11

Time spent in forums: 2 h 15 m 42 sec
Reputation Power: 0

I am not sure, but I dont think it will be anymore than 10-15 long.

October 5th, 2012, 12:11 PM

cafelatte

Contributing User

Join Date: Mar 2008

Posts: 1,923

Time spent in forums: 1 Month 5 Days 16 h 21 m 8 sec
Reputation Power: 377

Are we allowed to re-conceptualise the problem?

Every node in the path has a parent node. So 3's parent is 2. 2's parent is 1, etc.

The root node then is simply the node who's parent is NULL:

Code:

CREATE TABLE connections
(node INT NOT NULL PRIMARY KEY,parent INT NULL);

INSERT INTO connections
VALUES
(2,1),
(3,2),
(1,5),
(8,7),
(7,4),
(4,NULL),
(5,NULL);

From there, we're back to a more conventional kind of query, although if the paths really are as long as you say you may want to consider some form of stored procedure, or handling the recursion with some application level code:

Code:

SELECT * 
  FROM connections x 
  JOIN 
     ( SELECT CONCAT_WS(',',
              t1.node
            , t2.node
            , t3.node
            , t4.node) path  FROM connections t1 
         LEFT 
         JOIN connections t2 
           ON t2.parent = t1.node 
         LEFT 
         JOIN connections t3 
           ON t3.parent = t2.node 
         LEFT 
         JOIN connections t4
           ON t4.parent = t3.node 
        WHERE t1.parent IS NULL
     ) y 
    ON FIND_IN_SET(x.node,y.path) > 0 
   AND x.node = 2;
 
+------+--------+---------+
| node | parent | path    |
+------+--------+---------+
|    2 |      1 | 5,1,2,3 |
+------+--------+---------+

October 5th, 2012, 01:01 PM

YoungL

Registered User

Join Date: May 2011

Posts: 11

Time spent in forums: 2 h 15 m 42 sec
Reputation Power: 0

Quote:

Originally Posted by cafelatte

Are we allowed to re-conceptualise the problem?

Every node in the path has a parent node. So 3's parent is 2. 2's parent is 1, etc.

The root node then is simply the node who's parent is NULL:

Code:

CREATE TABLE connections
(node INT NOT NULL PRIMARY KEY,parent INT NULL);

INSERT INTO connections
VALUES
(2,1),
(3,2),
(1,5),
(8,7),
(7,4),
(4,NULL),
(5,NULL);

Code:

SELECT * 
  FROM connections x 
  JOIN 
     ( SELECT CONCAT_WS(',',
              t1.node
            , t2.node
            , t3.node
            , t4.node) path  FROM connections t1 
         LEFT 
         JOIN connections t2 
           ON t2.parent = t1.node 
         LEFT 
         JOIN connections t3 
           ON t3.parent = t2.node 
         LEFT 
         JOIN connections t4
           ON t4.parent = t3.node 
        WHERE t1.parent IS NULL
     ) y 
    ON FIND_IN_SET(x.node,y.path) > 0 
   AND x.node = 2;
 
+------+--------+---------+
| node | parent | path    |
+------+--------+---------+
|    2 |      1 | 5,1,2,3 |
+------+--------+---------+

That works really well, its exactly what I am after but is it possible to do it for a higher degree than 4, obviously I can manually increase the query. but is there a way to have it dynamically do so. So that the query continues until it reaches null?

October 5th, 2012, 05:07 PM

cafelatte

Contributing User

Join Date: Mar 2008

Posts: 1,923

Time spent in forums: 1 Month 5 Days 16 h 21 m 8 sec
Reputation Power: 377

Methods include those stated above, although I don't actually know how to construct said Stored Procedure!

Additionally, you might consider switching to a nested set model, which, once you get the hang of it, makes this kind of recursion easier.

As you imply, our idea of joining the table to itself as many times as could possibly be required is obviously clumsy, but hey 'if it works....'

Sequential Recursive Query

Developer Shed Advertisers and Affiliates