#1
  1. No Profile Picture
    Registered User
    Devshed Newbie (0 - 499 posts)

    Join Date
    May 2011
    Posts
    11
    Rep 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!
  2. #2
  3. No Profile Picture
    Contributing User
    Devshed Intermediate (1500 - 1999 posts)

    Join Date
    Mar 2008
    Posts
    1,928
    Rep Power
    378
    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.
  4. #3
  5. No Profile Picture
    Registered User
    Devshed Newbie (0 - 499 posts)

    Join Date
    May 2011
    Posts
    11
    Rep Power
    0
    I am not sure, but I dont think it will be anymore than 10-15 long.
  6. #4
  7. No Profile Picture
    Contributing User
    Devshed Intermediate (1500 - 1999 posts)

    Join Date
    Mar 2008
    Posts
    1,928
    Rep Power
    378
    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 |
    +------+--------+---------+
  8. #5
  9. No Profile Picture
    Registered User
    Devshed Newbie (0 - 499 posts)

    Join Date
    May 2011
    Posts
    11
    Rep Power
    0
    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);
    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 |
    +------+--------+---------+
    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?
  10. #6
  11. No Profile Picture
    Contributing User
    Devshed Intermediate (1500 - 1999 posts)

    Join Date
    Mar 2008
    Posts
    1,928
    Rep Power
    378
    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....'

IMN logo majestic logo threadwatch logo seochat tools logo