5

Eu tenho uma árvore serializada no meu banco de dados na tabela arvore. Como toda boa árvore, todo nó pode ter, no máximo, um único nó pai. Seus dados são nesse formato:

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'

A tabela acima é a serialização da floresta abaixo (apenas coloquei os ids nos nós):

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

Estou precisando selecionar apenas uma dessas árvores, dado apenas um único nó (é fornecido o ID desse nó na pesquisa). Como proceder?

Estou usando SQLite, mas se tiver uma solução em SQL pura será melhor ainda.

1

1 Resposta 1

6

Para resolver isso, precisamos fazer uma consulta recursiva. Para fazer uma consulta recursiva, usamos a Expressão Comum de Tabela (CTE).

Note que a própria documentação do SQLite informa que CTEs fazem parte da especificação SQL:1999, portanto essa solução é padrão.

Spoiler: para SQLServer, consultas recursivas se fazem somente com WITH, sem a palavra reservada RECURSIVE.

MySQL 8 suporta consulta recursiva, de acordo com essas referências; MariaDB já suporta desde a versão 10.2.2.

Uma CTE parte de um conjunto básico e, então, se acrescenta a ele um conjunto recursivo/induzido. É um pensamento contrário da indução matemática, de onde o elemento básico é o último obtido. No nosso caso, o elemento básico é a raiz: 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

Assim, podemos dizer que todos que estejam na mesma árvore possuem o mesmo id_raiz. O resultado da consulta acima é:

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

Para pegar todos os dados de uma árvore a partir de um único nó, podemos fazer uma auto junção da CTE nela mesma, já que é o mesmo problema resolvido nessa resposta.

A ideia aqui é identificar a partir de um nó qual sua árvore e, então, selecionar todos os elementos dessa árvore:

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>
3
  • 1
    Bacana demais @Jefferson, deixo meu mais 1. Obrigado
    – Marconi
    Commented 27/06/2017 às 17:24
  • 1
    @Marconi, vamos aumentando o conhecimento do mundo =D Commented 27/06/2017 às 20:39
  • 1
    Concerteza Jefferson!
    – Marconi
    Commented 27/06/2017 às 20:50

Você deve fazer log-in para responder a esta pergunta.

Esta não é a resposta que você está procurando? Pesquise outras perguntas com a tag .