Redeem all nodes in a SQLite database tree

Question

Redeem all nodes in a SQLite database tree

Navigation

#1 by (4 votes)

4

I have a serialized tree in my database in the arvore table. Like every good tree, every node can have at most one single parent node. Your data is in this format:

id | id_pai | valor
---+--------+------
1  |        | 'pai de todos'
2  | 1      | 'um nó intermediário'
3  | 1      | 'irmão do outro'
4  | 2      | 'uma folha'
5  | 1      | 'outra folha'
6  |        | 'outra árvore'
7  | 6      | 'filho 1'
8  | 6      | 'filho 2'

The above table is the serialization of the forest below (I just put the ids on the nodes):

   1       6
   |       |
+--+--+    +--+
|  |  |    |  |
2  3  5    7  8
|
4

I need to select only one of these trees, given only a single node (the ID of that node is provided in the search). How to proceed?

I'm using SQLite, but if you have a pure SQL solution it will be even better.

sql sqlite

asked by anonymous 22.06.2017 / 13:29

1 answer

How to check if a file is an image? Use IN or multiple ORs? Which one has the best performance?

score 4 · Accepted Answer

To solve this, we need to do a recursive query. For a recursive query, we use the Common Expression Table (CTE) .

Note that the SQLite documentation itself states that CTEs are part of the SQL: 1999 specification, so this solution is standard.

Spoiler: For SQLServer, recursive queries are done only with WITH , without the reserved word RECURSIVE .

MySQL 8 supports recursive query, according to referrals ; MariaDB already supports since version 10.2.2 .

A CTE starts from a basic set and then adds to it a recursive / induced set. It is a contrary thought of mathematical induction, from where the basic element is the last obtained. In our case, the basic element is the root: id_pai IS NULL .

WITH RECURSIVE arvore_recursiva AS (
    /* conjunto base da recursão */
    SELECT
        id,
        id AS id_raiz,
        valor,
        0 AS profundidade
   FROM
        arvore
   WHERE
        id_pai IS NULL

   /* parte recursiva */
   UNION ALL
   SELECT
        this.id as id,
        ancestral.id_raiz as id_raiz,
        this.valor as valor,
        ancestral.profundidade + 1 AS profundidade
   FROM
       arvore this
       INNER JOIN arvore_recursiva ancestral
           ON (this.id_pai = ancestral.id)
)
SELECT
    *
FROM
    arvore_recursiva

So we can say that everyone in the same tree has the same id_raiz . The result of the above query is:

id | id_raiz | valor                 | profundidade
---+---------+-----------------------+-------------
1  | 1       | 'pai de todos'        | 0
2  | 1       | 'um nó intermediário' | 1
3  | 1       | 'irmão do outro'      | 1
4  | 1       | 'uma folha'           | 2
5  | 1       | 'outra folha'         | 1
6  | 6       | 'outra árvore'        | 0
7  | 6       | 'filho 1'             | 1
8  | 6       | 'filho 2'             | 1

To get all the data in a tree from a single node, we can do a self join of the CTE on it, since it is the same problem solved in that response .

The idea here is to identify from a node what your tree is and then select all the elements of that tree:

WITH RECURSIVE arvore_recursiva AS (
    /* conjunto base da recursão */
    SELECT
        id,
        id AS id_raiz,
        valor,
        0 AS profundidade
   FROM
        arvore
   WHERE
        id_pai IS NULL

   /* parte recursiva */
   UNION ALL
   SELECT
        this.id as id,
        ancestral.id_raiz as id_raiz,
        this.valor as valor,
        ancestral.profundidade + 1 AS profundidade
   FROM
       arvore this
       INNER JOIN arvore_recursiva ancestral
           ON (this.id_pai = ancestral.id)
)
SELECT
    resto_arvore.*
FROM
    arvore_recursiva no_conhecido
    INNER JOIN arvore_recursiva resto_arvore
        ON (no_conhecido.id_raiz = resto_arvore.id_raiz)
WHERE
    no_conhecido.id = <ID DO NÓ CONHECIDO>