basic recursive query on sqlite3?

Question

I have a simple sqlite3 table that looks like this:

Table: Part
Part    SuperPart
wk0Z    wk00
wk06    wk02
wk07    wk02
eZ01    eZ00
eZ02    eZ00
eZ03    eZ01
eZ04    eZ01

I need to run a recursive query to find all the pairs of a given SuperPart with all of its subParts. So let's say that I have eZ00. eZ00 is a superpart of eZ01 and eZ01 is a superpart of eZ03. The result must include not only the pairs (eZ00, eZ01) and (eZ01 and eZ03) but must also include the pair (eZ00, eZ03).

I know there are other ways of defining the table, but I have no choice here. I know i can use several unions if I know the depth of my tree, but I won't allways know how depth I want to go. It'd help to have something like WITH RECURSIVE or even just WITH (,,) AS x but for what I've searched, that's not possible in sqlite, right?

Is there a way to do this recursive query in sqlite3?

UPDATE:

When this question was made, SQLite didn't support recursive queries, but as stated by @lunicon, SQLite now supports recursive CTE since 3.8.3 sqlite.org/lang_with.html

Answer 1

Based on the samples found in sqlite with documentation, the query

DROP TABLE IF EXISTS parts;
CREATE TABLE parts (part, superpart);
INSERT INTO parts VALUES("wk0Z", "wk00");
INSERT INTO parts VALUES("wk06", "wk02");
INSERT INTO parts VALUES("wk07", "wk02");
INSERT INTO parts VALUES("eZ01", "eZ00");
INSERT INTO parts VALUES("eZ02", "eZ00");
INSERT INTO parts VALUES("eZ03", "eZ01");
INSERT INTO parts VALUES("eZ04", "eZ01");

WITH RECURSIVE
  under_part(parent,part,level) AS (
     VALUES('?', 'eZ00', 0)
     UNION ALL
     SELECT parts.superpart, parts.part, under_part.level+1 
        FROM parts, under_part
     WHERE parts.superpart=under_part.part
  )
  SELECT SUBSTR('..........',1,level*3) || "(" || parent || ", " || part || ")" FROM under_part
  ;

would output

  (?, eZ00)
  ...(eZ00, eZ01)
  ...(eZ00, eZ02)
  ......(eZ01, eZ03)
  ......(eZ01, eZ04)

as "it should be" expected

the initial record of the recursive table can be replaced with

VALUES ((SELECT superpart FROM parts WHERE part='eZ00'), 'eZ00', 0)

in order to get also the parent of the initial superpart, although in this case there is no parent at all.

Answer 2

If you're lucky enough to be using SQLite 3.8.3 or higher then you do have access to recursive and non-recursive CTEs using WITH:

Thanks to lunicon for letting us know about this SQLite update.

---

In versions prior to 3.8.3, SQLite didn't support recursive CTEs (or CTEs at all for that matter) so there was no WITH in SQLite. Since you don't know how deep it goes, you can't use the standard JOIN trick to fake the recursive CTE. You have to do it the hard way and implement the recursion in your client code:

• Grab the initial row and the sub-part IDs.
• Grab the rows and sub-part IDs for the sub-parts.
• Repeat until nothing comes back.

Answer 3

This is the most basic query that I could think of, it generates a series where we start with 1,2 and keep adding 1 till we hit 20. not much useful but playing around a bit with this will help you build more complex recursive ones

The most basic series

WITH b(x,y) AS 
(
    SELECT 1,2 
    UNION ALL 
    SELECT x+ 1, y + 1 
    FROM b 
    WHERE x < 20
) SELECT * FROM b;

Prints

1|2
2|3
3|4
4|5
5|6
6|7
7|8
8|9
9|10
10|11
11|12
12|13
13|14
14|15
15|16
16|17
17|18
18|19
19|20
20|21

Here is another simple example that generates Fibonacci numbers we start with a = 0, b = 1 and then go a = b, b = a + b just like you would do in any programming language

Fibonacci Series

WITH b(x,y) AS 
(
    SELECT 0,1 
    UNION ALL 
    SELECT y, x + y 
    FROM b 
    WHERE x < 10000
) select * FROM b;

Prints

0|1
1|1
1|2
2|3
3|5
5|8
8|13
13|21
21|34
34|55
55|89
89|144
144|233
233|377
377|610
610|987
987|1597
1597|2584
2584|4181
4181|6765
6765|10946
10946|17711

Answer 4

there's a hack http://dje.me/2011/03/26/sqlite-data-trees.html

-- A method for storing and retrieving hierarchical data in sqlite3
-- by using a trigger and a temporary table.
-- I needed this but had trouble finding information on it.

-- This is for sqlite3, it mostly won't work on anything else, however 
-- most databases have better ways to do this anyway.

PRAGMA recursive_triggers = TRUE; -- This is not possible before 3.6.18

-- When creating the Node table either use a primary key or some other 
-- identifier which the child node can reference.

CREATE TABLE Node (id INTEGER PRIMARY KEY, parent INTEGER, 
    label VARCHAR(16));

INSERT INTO Node (parent, label) VALUES(NULL, "root");
INSERT INTO Node (parent, label) VALUES(1, "a");
INSERT INTO Node (parent, label) VALUES(2, "b");
INSERT INTO Node (parent, label) VALUES(3, "c1");
INSERT INTO Node (parent, label) VALUES(3, "c2");

-- Create the temp table, note that node is not a primary key
-- which insures the order of the results when Node records are
-- inserted out of order

CREATE TEMP TABLE Path (node INTEGER, parent INTEGER, 
    label VARCHAR(16));

CREATE TRIGGER find_path AFTER INSERT ON Path BEGIN
    INSERT INTO Path SELECT Node.* FROM Node WHERE 
        Node.id = new.parent;
END;


-- The flaw here is that label must be unique, so when creating
-- the table there must be a unique reference for selection
-- This insert sets off the trigger find_path

INSERT INTO Path SELECT * FROM Node WHERE label = "c2";

-- Return the hierarchy in order from "root" to "c2"
SELECT * FROM Path ORDER BY node ASC;

DROP TABLE Path; -- Important if you are staying connected


-- To test this run:
-- sqlite3 -init tree.sql tree.db

Answer 5

In this SQLite Release 3.8.3 On 2014-02-03 has been added support for CTEs. Here is documentation WITH clause Example:

WITH RECURSIVE
cnt(x) AS (
 SELECT 1
 UNION ALL
 SELECT x+1 FROM cnt
  LIMIT 1000000
)
SELECT x FROM cnt;