CODEWITHSUNDEEP
sqlsqlitetreehierarchy
AquaCash5
AquaCash5

Reputation: 45

How do I take a tree in a sqlite db and turn a node into a path going from it to the root?

I have a SQLite database with a table that represents a tree. Each row in the table represents a relationship between two nodes except the first node which links to itself.

Basically given this table

BEGIN TRANSACTION;
CREATE TABLE "unnamed" (key TEXT PRIMARY KEY, value TEXT);
INSERT INTO `unnamed` (key,value) VALUES ('1','1');
INSERT INTO `unnamed` (key,value) VALUES ('2','1');
INSERT INTO `unnamed` (key,value) VALUES ('3','10');
INSERT INTO `unnamed` (key,value) VALUES ('10','5');
INSERT INTO `unnamed` (key,value) VALUES ('5','16');
INSERT INTO `unnamed` (key,value) VALUES ('16','8');
INSERT INTO `unnamed` (key,value) VALUES ('8','4');
INSERT INTO `unnamed` (key,value) VALUES ('4','2');
INSERT INTO `unnamed` (key,value) VALUES ('6','3');
INSERT INTO `unnamed` (key,value) VALUES ('7','22');
INSERT INTO `unnamed` (key,value) VALUES ('22','11');
INSERT INTO `unnamed` (key,value) VALUES ('11','34');
INSERT INTO `unnamed` (key,value) VALUES ('34','17');
INSERT INTO `unnamed` (key,value) VALUES ('17','52');
INSERT INTO `unnamed` (key,value) VALUES ('52','26');
INSERT INTO `unnamed` (key,value) VALUES ('26','13');
INSERT INTO `unnamed` (key,value) VALUES ('13','40');
INSERT INTO `unnamed` (key,value) VALUES ('40','20');
INSERT INTO `unnamed` (key,value) VALUES ('20','10');
INSERT INTO `unnamed` (key,value) VALUES ('9','28');
INSERT INTO `unnamed` (key,value) VALUES ('28','14');
INSERT INTO `unnamed` (key,value) VALUES ('14','7');
COMMIT;

Output this table

+------+------------------------------------------------------+
| Node | Path                                                 |
+------+------------------------------------------------------+
|    1 | 1                                                    |
|    2 | 2-1                                                  |
|    3 | 3-10-5-16-8-4-2-1                                    |
|    4 | 4-2-1                                                |
|    5 | 5-16-8-4-2-1                                         |
|    6 | 6-3-10-5-16-8-4-2-1                                  |
|    7 | 7-22-11-34-17-52-26-13-40-20-10-5-16-8-4-2-1         |
|    8 | 8-4-2-1                                              |
|    9 | 9-28-14-7-22-11-34-17-52-26-13-40-20-10-5-16-8-4-2-1 |
|   10 | 10-5-16-8-4-2-1                                      |
|   11 | 11-34-17-52-26-13-40-20-10-5-16-8-4-2-1              |
|   13 | 13-40-20-10-5-16-8-4-2-1                             |
|   14 | 14-7-22-11-34-17-52-26-13-40-20-10-5-16-8-4-2-1      |
|   16 | 16-8-4-2-1                                           |
|   17 | 17-52-26-13-40-20-10-5-16-8-4-2-1                    |
|   20 | 20-10-5-16-8-4-2-1                                   |
...

I have been reading about WITH and WITH RECURSIVE, but I cannot get my head around how they work.

Upvotes: 0

Views: 374

Answers (1)

hogi
hogi

Reputation: 896

This solution constructs the path from leaf to root:

WITH RECURSIVE
  queue(leaf,head,path) AS (
    SELECT CAST(key AS INTEGER) AS leaf, key AS head, key AS path
      FROM unnamed
    UNION
    SELECT queue.leaf AS leaf, unnamed.value AS head, (queue.path||'-'||unnamed.value) AS path
      FROM unnamed, queue
      WHERE unnamed.value != queue.head AND unnamed.key = queue.head
  )
SELECT leaf AS node, path AS path
  FROM queue
  WHERE head = 1
  -- WHERE length(path) = (SELECT MAX(LENGTH(path)) FROM queue AS q WHERE q.leaf = queue.leaf)
  ORDER BY leaf;

Please read the documentation here: http://www.sqlite.org/lang_with.html

The initial-select adds all keys into the queue as leaf and head and path. Leaf is cast to integer for the ORDER BY later on, head is the current head and path will be extended step by step:

SELECT CAST(key AS INTEGER) AS leaf, key AS head, key AS path
    FROM unnamed

For each queue item the database is queried to extend the path at the head towards the root of the tree. So the head of the queue item has to match a key, which is not the root of the tree.

WHERE unnamed.value != queue.head AND unnamed.key = queue.head

The combined path of the two is extended with a dash and added to the queue:

SELECT queue.leaf AS leaf, unnamed.value AS head, (queue.path||'-'||unnamed.value) AS path
    FROM unnamed, queue
    WHERE unnamed.value != queue.head AND unnamed.key = queue.head

The result contains all paths from leaf to root including all intermediate results. Therefore we only select those, which ended at the root node with head/key value 1.

SELECT leaf AS node, path AS path
    FROM queue
    WHERE head = 1
    ORDER BY leaf;

Alternatively you can also just select those with the longest path.

SELECT leaf AS node, path AS path
    FROM queue
    WHERE length(path) = (SELECT MAX(LENGTH(path)) FROM queue AS q WHERE q.leaf = queue.leaf)
    ORDER BY leaf;

Upvotes: 1

Related Questions