Comment puis-je prendre un arbre dans un sqlite db et transformer un noeud en un chemin allant de lui à la racine?

Question

J'ai une base de données SQLite avec une table qui représente un arbre. Chaque ligne de la table représente une relation entre deux nœuds sauf le premier nœud qui se lie à lui-même.

Fondamentalement donné ce tableau

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; 

sortie ce tableau

+------+------------------------------------------------------+ 
| 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         | 
... 

Je lis à propos WITH et WITH RECURSIVE, mais je ne peux pas obtenir ma tête la façon dont ils travaillent.

Answer 1

Cette solution construit le chemin de la feuille à la racine:

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; 

S'il vous plaît lire la documentation ici: http://www.sqlite.org/lang_with.html

La toutes les clés ajoute initiale de sélection dans la file d'attente comme feuille et la tête et le chemin. Feuille est coulé à l'entier de la clause ORDER BY plus tard, la tête est la tête de courant et le chemin sera pas prolongé par l'étape:

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

Pour chaque élément de file d'attente de la base de données est interrogée pour étendre le chemin à la tête vers la racine de l'arbre. La tête de l'élément de file d'attente doit donc correspondre à une clé, qui n'est pas la racine de l'arborescence.

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

Le chemin combiné des deux est prolongée par un tiret et ajouté à la file d'attente:

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 

Le résultat contient tous les chemins de feuille en racines, y compris tous les résultats intermédiaires. Par conséquent, nous ne sélectionner que ceux, qui a pris fin au nœud racine avec la tête/valeur de clé 1.

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

Sinon, vous pouvez aussi il suffit de sélectionner ceux qui ont le plus long chemin.

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;