Rescue all nodes from an Sqlite database tree

Question

I have a serialized tree in my database in the table arvore. Like any good tree, every node can have at most a 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 (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 (this node’s ID is provided in the search). How to proceed?

I am using Sqlite, but if you have a solution in pure SQL will be even better.

Answer 1

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

Note that the Sqlite documentation itself informs that Ctes are part of the SQL:1999 specification, so this solution is standard.

Spoiler: for Sqlserver, recursive queries are made only with WITH, without the reserved word RECURSIVE.

Mysql 8 supports recursive query, according to those references; Mariadb already supports since version 10.2.2.

A CTE is part of a basic set and then added to it a recursive/induced set. It is a thought contrary to mathematical induction, from which 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 who is in the same tree has the same id_raiz. The result of the above consultation 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 take all data from a tree from a single node, we can make an auto-merge of CTE into it, since it is the same problem solved in that reply.

The idea here is to identify from a node what its 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>