Faça-o em SQL: Travessia da árvore SQL Recursiva

No artigo anterior, descrevi como usar as Expressões de Tabela Comum para encontrar o caminho mais curto em um gráfico dirigido. Esse exemplo pode ser difícil de seguir, admito. Vamos fazer algo muito mais comum, algo que é implementado em quase todos os sites - um menu. Em vez de escrever o código, vamos aproveitar a estrutura em árvore SQL escrevendo apenas uma consulta. Vamos usar CTEs para PostgreSQL e a cláusula de consulta hierárquica para Oracle. Se você quiser aprender a escrever CTEs por conta própria, eu recomendo nosso curso interativo Consultas Recursivas.

Então, vamos ver como é um menu simples:

O que temos aqui? Há um menu principal e um menu suspenso que aparece depois que clicamos no botão do menu principal. É claro, pode haver mais submenus anexados a outro botão do menu principal. Além disso, poderia haver também um submenu, que apareceria após clicarmos em um dos botões de um submenu.

Em geral, poderia haver um número ilimitado de níveis de menu. A disposição dos dados de tal menu é uma estrutura em árvore SQL:

Como você pode ver, é uma estrutura de árvore SQL típica. Há nós de menu que são anexados aos nós pai. O único nó sem um nó pai é o nó raiz.

É assim que armazenamos tal estrutura de árvore SQL no banco de dados:

Na estrutura de árvore SQL, cada nó tem sua própria e única identificação. Ele tem uma referência ao nó pai. Para cada nó de um submenu, precisamos de seu número seqüencial para fins de ordenação. A coluna name é apenas uma etiqueta que será mostrada no site. A coluna url_path pode exigir um pouco mais de explicação. Cada nó armazena uma parte do caminho URL completo do recurso. Todo seu caminho é uma concatenação do url_path de todos os nós desde a raiz até aquele nó.

Por exemplo, para os seguintes dados:

> select * from menu_node;
 id | parent_node_id | seq |        name        | url_path  
----+----------------+-----+--------------------+----------- 
  1 |                |   1 | root               | 
  2 |              1 |   1 | Diagram            | diagram 
  3 |              1 |   2 | My models          | my_models 
  4 |              1 |   3 | Share requests     | share 
  5 |              1 |   4 | My account         | account 
  6 |              1 |   5 | Invite people      | invite 
  7 |              1 |   6 | Help               | help 
  8 |              7 |   1 | Documentation      | doc 
  9 |              7 |   2 | FAQ                | faq 
 10 |              7 |   3 | Ask a question     | ask 
 11 |              7 |   4 | Request a feature  | feature 
 12 |              7 |   5 | Report a problem   | problem 
 13 |              7 |   6 | Keyboard shortcuts | shortcuts 
 14 |              8 |   1 | Section 1          | section1 
 15 |              8 |   2 | Section 2          | section2 
 16 |              8 |   3 | Section 3          | section3 
(16 rows) 

o caminho completo do nó "Seção 1" é: /help/doc/section1.

Tendo tal estrutura, queremos renderizar o menu na página. Se não utilizássemos uma consulta SQL para obter níveis hierárquicos em árvore, teríamos que executar múltiplas consultas (para cada nó obter seus filhos) ou recuperar todos os dados e construir a estrutura no código. Não estou dizendo que é uma má abordagem, mas pode ser feita de uma maneira mais fácil e inteligente.

PostgreSQL - cláusula recursiva COM

A fim de renderizar tal menu, precisamos saber o caminho URL completo de cada botão, informações sobre o nível do nó (para dar um estilo apropriado no CSS) e onde anexá-lo (é o ID do pai, é claro). Portanto, vamos começar a construir nossa consulta seleta com o CTE:

WITH RECURSIVE menu_tree 
  (id, name, url, level, parent_node_id, seq) AS (

No início, precisamos obter o nó raiz:

  SELECT 
    id, 
    name, 
    '' || url_path, 
    0, 
    parent_node_id, 
    1 
  FROM menu_node 
  WHERE parent_node_id is NULL

Depois, recursivamente, vamos mais fundo com nossa consulta SQL, concatenando o caminho e incrementando o nível:

  UNION ALL 
  SELECT 
    mn.id, 
    mn.name, 
    mt.url || '/' || mn.url_path, 
    mt.level + 1, 
    mt.id, 
    mn.seq 
  FROM menu_node mn, menu_tree mt 
  WHERE mn.parent_node_id = mt.id

E no final, precisamos obter todas as linhas, exceto o nó raiz (não precisamos mais dele) na ordem correta. Primeiro, elas devem ser ordenadas por nível, depois "agrupadas" por pai, e finalmente seguindo a ordem seq. Assim, a consulta terá este aspecto:

SELECT * FROM menu_tree 
WHERE level > 0 
ORDER BY level, parent_node_id, seq; 

A consulta final:

WITH RECURSIVE menu_tree 
  (id, name, url, level, parent_node_id, seq) 
AS ( 
  SELECT 
    id, 
    name, 
    '' || url_path, 
    0, 
    parent_node_id, 
    1 
  FROM menu_node 
  WHERE parent_node_id is NULL 

  UNION ALL 
  SELECT 
    mn.id, 
    mn.name, 
    mt.url || '/' || mn.url_path, 
    mt.level + 1, 
    mt.id, 
    mn.seq 
  FROM menu_node mn, menu_tree mt 
  WHERE mn.parent_node_id = mt.id 
) 
SELECT * FROM menu_tree 
WHERE level > 0 
ORDER BY level, parent_node_id, seq;

Parece bem fácil, não é mesmo? Como resultado, obtemos os dados:

 id |        name        |        url         | level | parent_node_id | seq 
----+--------------------+--------------------+-------+----------------+----- 
  2 | Diagram            | /diagram           |     1 |              1 |   1 
  3 | My models          | /my_models         |     1 |              1 |   2 
  4 | Share requests     | /share             |     1 |              1 |   3 
  5 | My account         | /account           |     1 |              1 |   4 
  6 | Invite people      | /invite            |     1 |              1 |   5 
  7 | Help               | /help              |     1 |              1 |   6 
  8 | Documentation      | /help/doc          |     2 |              7 |   1 
  9 | FAQ                | /help/faq          |     2 |              7 |   2 
 10 | Ask a question     | /help/ask          |     2 |              7 |   3 
 11 | Request a feature  | /help/feature      |     2 |              7 |   4 
 12 | Report a problem   | /help/problem      |     2 |              7 |   5 
 13 | Keyboard shortcuts | /help/shortcuts    |     2 |              7 |   6 
 14 | Section 1          | /help/doc/section1 |     3 |              8 |   1 
 15 | Section 2          | /help/doc/section2 |     3 |              8 |   2 
 16 | Section 3          | /help/doc/section3 |     3 |              8 |   3 
(15 rows)

Com esta consulta única, você pode obter todos os dados necessários para fazer um simples menu de vários níveis. Graças à estrutura em árvore SQL, seus dados são representados de uma forma clara e facilmente digerível.

Para praticar a escrita de perguntas hierárquicas como esta, eu recomendo nosso curso interativo Consultas Recursivas.

Oracle - consultas hierárquicas

No Oracle você pode usar tanto a cláusula de consulta hierárquica (também conhecida como "CONNECT BY query") ou o fator de subconsulta recursiva (introduzido na versão 11g versão 2).

A estrutura da segunda é quase a mesma que na consulta para o PostgreSQL. As únicas diferenças são:

• falta da palavra-chave RECURSIVE
• "nível" é uma palavra reservada, por isso devemos mudá-la

O restante permanece inalterado e a consulta funciona bem.

Com relação à cláusula de consulta hierárquica, sua sintaxe é totalmente diferente. A consulta tem este aspecto:

SELECT 
  id, 
  name,
  SYS_CONNECT_BY_PATH(url_path, '/') AS url, 
  LEVEL, 
  parent_node_id, 
  seq 
FROM menu_node 
START WITH id IN 
  (SELECT id FROM menu_node WHERE parent_node_id IS NULL) 
CONNECT BY PRIOR id = parent_node_id;

Uma coisa digna de nota é que esta consulta será verdadeiramente recorrente, isto é - em uma ordem de profundidade-primeira. A cláusula "recursiva" com o PostgreSQL e (por padrão) no Oracle atravessa a estrutura em uma ordem ampla-primeira.

Como você pode ver, compreender o conceito da estrutura em árvore SQL pode economizar algum de nosso precioso tempo (e algumas linhas de código). A escolha é sua se você usa ou não consultas recursivas de travessia, mas vale definitivamente a pena conhecer a alternativa.

Para aprender a escrever consultas recursivas em SQL, eu recomendo nosso curso interativo Consultas Recursivas. Ele contém 114 exercícios práticos de codificação que lhe permitem praticar Expressões de Tabelas Comuns e consultas recursivas como as mostradas neste artigo.