How do I set up a table to do recursive queries in Sqlite?

Question

I apologize if this is a basic question, but I'm a database novice. I'm using sqlite to manage a list of command-line options for some tools. A simple version of this is:

sqlite> CREATE TABLE option_set (set_id INTEGER, idx INTEGER, value TEXT );
sqlite> INSERT INTO option_set VALUES( 1, 1, 'a' );
sqlite> INSERT INTO option_set VALUES( 1, 2, 'b' );
sqlite> INSERT INTO option_set VALUES( 1, 3, 'c' );
sqlite> SELECT value FROM option_set WHERE set_id=1 ORDER BY idx;
a
b
c

This all works fine. I want to add an enhancement, however, where I allow one option_set to contain another. For instance, if I specified option_set=2 as { 'd', 'e', [option_set=1], 'f' }, I would like that to mean the options { 'd', 'e', 'a', 'b', 'c', 'f' }. The question is how to express this in the database. I was thinking of something along the lines of:

sqlite> CREATE TABLE option_set (set_id INTEGER, idx INTEGER, contained_set_id INTEGER, value TEXT );
sqlite> INSERT INTO option_set VALUES( 1, 1, NULL, 'a' );
sqlite> INSERT INTO option_set VALUES( 1, 2, NULL, 'b' );
sqlite> INSERT INTO option_set VALUES( 1, 3, NULL, 'c' );
sqlite> INSERT INTO option_set VALUES( 2, 1, NULL, 'd' );
sqlite> INSERT INTO option_set VALUES( 2, 2, NULL, 'e' );
sqlite> INSERT INTO option_set VALUES( 2, 3, 1, NULL );
sqlite> INSERT INTO option_set VALUES( 2, 4, NULL, 'f' );

The idea is that in each row of the table, I'd either have a value or another set_id that should be expanded. The problem is that I don't know how to query such a table - how could I produce the list of options short of recursively doing selects? I'm not crazy about the structure where the contained and value column are never both valid, but not sure how to get around that. Would a different table design work better?

Thanks.

CL. CL. · Accepted Answer · 2014-02-07T09:49:29

To do a recursive query, you need a recursive common table expression:

WITH RECURSIVE
  contained_sets(level, idx, contained_set_id, value)
  AS (SELECT 0, idx, contained_set_id, value
      FROM option_set
      WHERE set_id = 2
      UNION ALL
      SELECT level + 1,
             option_set.idx,
             option_set.contained_set_id,
             option_set.value
      FROM option_set
      JOIN contained_sets ON option_set.set_id = contained_sets.contained_set_id
      ORDER BY 1 DESC, 2)
SELECT value
FROM contained_sets
WHERE contained_set_id IS NULL;

value
----------
d
e
a
b
c
f

(This is supported in SQLite 3.8.3 or later.)

How do I set up a table to do recursive queries in Sqlite?

1 Answers