Is it possible to write a SQLite query which recursively gets all items that are child items of a root node

Question

I have 2 tables. items and itemItems

itemItems describes a many to many relationship between items. I.e. a member of items could have many children and they could have many children which in turn could have many children etc..

item:

itemID |  more stuff ......
1         ...    
2         ...
3         ...
4         ...

itemItems:

parentItemID |  childItemID  
1               2 
1               3
2               4

I want to write a query that would recursively get all of the children under one root node.

I believe this is possible with something called a recursive join but I find the concept very confusing.... (similar to this question, but with sqlite not sql server and many to many not one to many)

I can get the first level (i.e. all children under one item) by doing the following

SELECT * 
FROM items 
INNER JOIN itemItems
ON items.itemID = itemItems.childItemID
WHERE itemItems.parentItemID = 1

How could I extend this to recursively get all the children's children etc...?

Answer 1

I just got a similar query to work using the with recursive syntax. The general form is:

with recursive tc( i )
  as ( select [... initial-query ...]
        union [... recursive-part (include tc) ...]
     )
 select * from tc;

The key in my case was to make sure that tc was listed in the recursive part. Also, this final select is just to show the full content of the transitive closure, the real one should select the rows that you need.

I think that this recipe would apply to your case as the following. I haven't tested this, I'm just copy/pasting from my query and replacing with your table names. It does work for me, but I might have translated this incorrectly. I'm also not really sure about efficiency, etc., it is just something that I got to work.

with recursive tc( i )
  as ( select childItemID from itemItems where parentItemID = 1
        union select childItemID from itemItems, tc
               where itemItems.parentItemID = tc.i
     )
  select * from item where itemID in tc;

NOTE: This worked for me on version 3.8.3.1 but not on 3.7.2.

Answer 2

The recursive version above requires ANSI SQL:1999 which is supported by the common DBMS in those days, but there also is an ANSI SQL-92 method to achieve bounded recursion. This approach can be extended arbitrarily.

The below example supports up to 7 levels. If you want more, add more.

SELECT DISTINCT
    I.*
FROM
    item I INNER JOIN (
        SELECT 
            I1.itemID as Level1,
            I2.itemID as Level2,
            I3.itemID as Level3,
            I4.itemID as Level4,
            I5.itemID as Level5,
            I6.itemID as Level6,
            I7.itemID as Level7
        FROM 
            item I1 LEFT JOIN 
            item I2 ON EXISTS (SELECT NULL FROM itemItems II1 WHERE II1.parentItemID = I1.itemID AND I2.itemID = II1.childItemID) LEFT JOIN
            item I3 ON EXISTS (SELECT NULL FROM itemItems II2 WHERE II2.parentItemID = I2.itemID AND I3.itemID = II2.childItemID) LEFT JOIN
            item I4 ON EXISTS (SELECT NULL FROM itemItems II3 WHERE II3.parentItemID = I3.itemID AND I4.itemID = II3.childItemID) LEFT JOIN
            item I5 ON EXISTS (SELECT NULL FROM itemItems II4 WHERE II4.parentItemID = I4.itemID AND I5.itemID = II4.childItemID) LEFT JOIN
            item I6 ON EXISTS (SELECT NULL FROM itemItems II5 WHERE II5.parentItemID = I5.itemID AND I6.itemID = II5.childItemID) LEFT JOIN
            item I7 ON EXISTS (SELECT NULL FROM itemItems II6 WHERE II6.parentItemID = I6.itemID AND I7.itemID = II6.childItemID)
        WHERE
            I1.itemID = 1    -- root node condition
    ) D ON I.itemID = D.Level1 OR I.itemID = D.Level2 OR I.itemID = D.Level3 OR I.itemID = D.Level4 OR I.itemID = D.Level5 OR I.itemID = D.Level6 Or I.itemID = D.Level7