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

Sartain

If anyone is looking for something to use with Android, WITH is only available from API Level 20 (Android L) using 3.8.4.3; if you want compatibility with lower APIs you'll have to go with johndpope's answer which is supported from API Level 8 (2.2) using 3.6.22. – Urushiol

Answer 1

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.

Formula

It makes sense, I was wondering if I could do it with pure sql. – Sartain

@Eric: Sorry, not with SQLite. You could (of course) if WITH RECURSIVE was available and you could if SQLite had a procedure language. You might be able to define your own SQL functions in whatever language you're using outside SQLite. – Formula

$muistooshort I take it you meant to say " you can't use the standard JOIN trick" – Sartain

@Eric: Right, thank you fellow Eric, I feeling like I'm talking to myself about fixing my own typo :) – Formula

Since 3.8.3 SQLite support recursive CTE! see examples sqlite.org/lang_with.html – Redeeming

@lunicon: Do you want to turn the comment into an answer? I'd certainly upvote it and maybe we could get Eric to come back and switch the accept. – Formula

Answer 2

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;

Morelock

@Sartain I haven't down voted your question, a was seeking for solution and when I have found it have decided to add answer. – Morelock

All the examples shown work, but when I try to roll my own I get "no such column" errors. – Scatter

The example adds nothing as an answer to the original question. – Mcdevitt

@Mcdevitt When I was answering there was nothing about CTE in the question. So can you explain what you mean "adds nothing" – Morelock

The example code provided is an excerpt from the docs about the query optimizer. It does not provide an example of how one would query the hierarchy of parent-child records. It simply points out that recursion is now supported in SQLite, which the OP had already figured out. – Mcdevitt

Answer 3

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.

Morrow

if that isnt the worst example for beginners – Industrial

I don't get your point about it ... the example is exactly the one given by the posted question – Morrow

Found a variant of this answer that also sorts the results and prints them as a tree structure. – Resolution

both examples (mine and "the variant") are taken from official sqlite documentation as noted at the beginning of the answer. Specifically in chapter "3.4. Controlling Depth-First Versus Breadth-First Search Of a Tree Using ORDER BY", take a look "SELECT SUBSTR('... etc" comes from there – Morrow

Answer 4

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

Industrial

Answer 5

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

Valle