Recursive Query in MYSQL?

Question

I think my problem is solved with a 'recursive query', but since MySQL doesn't support recursive queries I was trying to use the adjacent list model. This should not be a problem since I know how deep I want to go.

Here's an example of what I need to do: Table Classes:

dept    classNum    prereqDept  prereqClassNum
BIO     465         BIO         335
EE      405         EE          325
EE      325         EE          120
BIO     465         EE          120
BIO     335         BIO         225
BIO     225         CHEM        110
BIO     225         BIO         105

What I need is all the classes of a certain level (let's say 400) with all their prerequisites up to 3 levels deep. So I'd get something like

dept    classNum    prereqDept  prereqClassNum
BIO     465         BIO         335
BIO     465         BIO         225
BIO     465         CHEM        110
BIO     465         BIO         105
EE      405         EE          325
EE      405         EE          120
....

I know I need to use 3-LEFT JOINs if I want to go 3 levels deep, but I can't figure out how to set up these joins to get what I need. Any ideas? I'll appreacite your help!

P.S. I can't change the table structure at all.

Answer 1

Hmm. Try this:

SELECT * FROM
(
    (
        SELECT t1.dept, t1.classNum, t1.prereqDept, t1.prereqClassNum
        FROM class AS t1
        WHERE t1.classNum >= 400
    )
    UNION
    (
        SELECT t1.dept, t1.classNum, t2.prereqDept, t2.prereqClassNum
        FROM class AS t1
        JOIN class AS t2 ON (t1.prereqDept = t2.dept AND t1.prereqClassNum = t2.classNum)
        WHERE t1.classNum >= 400
    )
    UNION
    (
        SELECT t1.dept, t1.classNum, t3.prereqDept, t3.prereqClassNum
        FROM class AS t1
        JOIN class AS t2 ON (t1.prereqDept = t2.dept AND t1.prereqClassNum = t2.classNum)
        JOIN class AS t3 ON (t2.prereqDept = t3.dept AND t2.prereqClassNum = t3.classNum)
        WHERE t1.classNum >= 400
    )
) AS t4
ORDER BY dept, classNum, prereqDept, prereqClassNum

Answer 2

I've run this and it gets all classes with (in this sample) up to 3 pre-requisites, but could be expanded to 4, 5, 6 just by copying the pairs based on "IDSeq = ?".

The critical element here is to get a number assigned to each record based on the common Dept + ClassNum each time starting with 1 at the beginning of each time the group changes. To do this, I've applied SQL Variables to FIRST Make sure that each group is sequenced 1, 2, 3... 1, 2, ... 1, ... 1, 2, 3, 4, 5... etc...

Result of Inner Query

Once this is done, we can do a simple group by with no other complex joining, joining, unioning, etc... Just apply a max() of an IF() based on the known sequence. As you can see the pattern, I'm getting whatever the row has for its prerequisite Dept and ClassNum provided that is the "1"st record, then again on the "2"nd, and "3"rd, but could be applied for the "4"th, "5"th, etc.

By using the max( if() ), every class will always have a 1 sequence, but only sometimes will have a 2, let alone a 3, 4 or 5. So, if there is NOT a value, it at least gets filled with blank spaces so it won't show null. Then, if/when there IS a value, the MAX() will supercede the blank spaces when it hits...

The final query is amazing and probably JUST what you need.

select
      NewSet.Dept,
      NewSet.ClassNum,
      max( if( NewSet.IDSeq = 1, NewSet.PreReqDept, '    ' )) FirstDept,
      max( if( NewSet.IDSeq = 1, NewSet.PreReqClassNum, '    ' )) FirstClassNum,
      max( if( NewSet.IDSeq = 2, NewSet.PreReqDept, '    ' )) SecondDept,
      max( if( NewSet.IDSeq = 2, NewSet.PreReqClassNum, '    ' )) SecondClassNum,
      max( if( NewSet.IDSeq = 3, NewSet.PreReqDept, '    ' )) ThirdDept,
      max( if( NewSet.IDSeq = 3, NewSet.PreReqClassNum, '    ' )) ThirdClassNum
   from 
      ( select 
             @orig := @orig +1 as OrigSeq,
             @seq := if( concat(P.Dept, P.ClassNum ) = @LastGrp, @seq +1, 1 ) as IDSeq,
             @LastGrp := concat( P.Dept,  P.ClassNum ) NextGrp,
             P.Dept,
             P.ClassNum,
             P.PreReqDept,
             P.PreReqClassNum
          from 
             PreReqs P,
             ( select @orig := 0, @seq := 0, @LastGrp := '' ) x
          order by 
             Dept,
             ClassNum ) NewSet
   group by
      NewSet.Dept,
      NewSet.ClassNum
   order by 
      NewSet.Dept,
      NewSet.ClassNum

Answer 3

The way I would do it (not sure if there is anything easier). First get dependencies at one level (easy):

SELECT * FROM table;

Then two level down:

SELECT t.dept AS dept, t.classNum AS classNum, t2.prereqDept AS prereqDept, t2.prereqClassNum AS prereqClassNum FROM table AS t
 LEFT JOIN table AS t2 WHERE t2.classNum = t.prereqClassNum;

Reuse that to go three level down:

SELECT t3.dept AS dept, t3.classNum AS classNum, t4.prereqDept AS prereqDept, t4.prereqClassNum AS prereqClassNum 
FROM (
    SELECT t.dept AS dept, t.classNum AS classNum, t2.prereqDept AS prereqDept, t2.prereqClassNum AS prereqClassNum FROM table AS t
    LEFT JOIN table AS t2 WHERE t2.classNum = t.prereqClassNum
) AS t3
LEFT JOIN table AS t4 WHERE t4.classNum = t3.prereqClassNum;

Finally, you can just do a UNION of all those three queries.

(SELECT * FROM table)
UNION
(SELECT t.dept AS dept, t.classNum AS classNum, t2.prereqDept AS prereqDept, t2.prereqClassNum AS prereqClassNum FROM table AS t
LEFT JOIN table AS t2 WHERE t2.classNum = t.prereqClassNum)
UNION
(SELECT t3.dept AS dept, t3.classNum AS classNum, t4.prereqDept AS prereqDept, t4.prereqClassNum AS prereqClassNum 
FROM (
    SELECT t.dept AS dept, t.classNum AS classNum, t2.prereqDept AS prereqDept, t2.prereqClassNum AS prereqClassNum FROM table AS t
    LEFT JOIN table AS t2 WHERE t2.classNum = t.prereqClassNum
) AS t3
LEFT JOIN table AS t4 WHERE t4.classNum = t3.prereqClassNum);

I did not check it works... but something like that should work...