Armazenando relacionamentos hierárquicos em bancos de dados relacionais - Revista SQL Magazine 104

É bastante comum se deparar com a necessidade de armazenar dados hierárquicos em um sistema de informação. Esses dados são aqueles que costumam ser visualizados na forma de árvore, com ligações entre nós pai e seus respectivos nós filhos. Alguns exemplos típicos incluem composição de produtos (Bill of Materials – BOM) e relações entre chefe/subordinado. Às vezes, até mesmo a principal entidade de um modelo segue esta estrutura, como é o caso dos sistemas de fóruns com suas mensagens aninhadas.

Quem já precisou usar bancos de dados relacionais para atender a este tipo de situação sabe que a modelagem pode ser intrincada e exigir um certo grau de raciocínio na definição da melhor solução. Afinal, trata-se de informações dispostas em uma hierarquia, com um número muitas vezes indeterminado de níveis. Dependendo da solução adotada, alguns tipos de consulta podem exigir processamento recursivo, e outras podem até mesmo ser difíceis de formular.

O que muitos não sabem é que existem formas bastante interessantes de tratar hierarquias, usando modelos de dados dos mais diversos. Como não poderia deixar de ser, cada abordagem tem seus custos e benefícios, e esses são precisamente os aspectos discutidos neste artigo. Divirta-se avançando de seção em seção, ou como bom projetista de árvore, pulando de galho em galho.

Aplicação de exemplo

Para usar um exemplo bem genérico e conhecido por todos, escolhemos o problema de modelagem das relações de subordinação. Afinal, dentro de uma corporação, infelizmente quase todos têm um chefe.

A Figura 1 mostra as relações de chefia em uma empresa fictícia. Para começar, vamos analisar os componentes representados nesta árvore. Quando se fala sobre estruturas hierárquicas, costuma-se utilizar uma nomenclatura própria. Por exemplo, os elementos da árvore são chamados de nós, ou vértices, e as ligações entre elementos são chamadas de arcos.

As relações (grau de parentesco) entre os nós também recebem nomes. Nó pai (parent) é aquele que aparece acima de algum outro nó, enquanto um nó filho (child) aparece abaixo, tanto direta quanto indiretamente. Como já se pode imaginar, nó irmão (sibling) é o que possui o mesmo pai direto. Uma árvore também é composta por níveis que indicam a altura dos nós. Por exemplo, Roger, o Diretor Executivo, está no primeiro nível, enquanto seus subordinados diretos estão no segundo.

Outro conceito importante que vale a pena destacar é o de caminhamento em árvores. O caminhamento se refere à ordem em que os nós são acessados. Em árvores, existem dois tipos básicos, chamados de caminhamento em largura e em profundidade.

No primeiro deles (em largura), os nós são acessados da esquerda para a direita, dando prioridade para os nós de nível mais alto. Na Figura 1, essa ordem é denotada pelos números destacados em verde. Já no segundo tipo (em profundidade), a prioridade é dada para os nós filhos. Na Figura 1, essa ordem é denotada pelos números destacados em vermelho. Essa, na verdade, é a forma mais corriqueira de se acessar nós quando o interesse é o de geração de relatórios.

Vários tipos de consulta podem ser formulados em modelos hierárquicos. Neste artigo, analisaremos dois tipos apenas, que chamaremos de consulta “Desce” e consulta “Sobe”. Na consulta “Desce”, o objetivo é encontrar todas as relações de subordinação existentes a partir de um certo nó da árvore. Por exemplo, supondo que queiramos saber quem são os subordinados do João, a resposta esperada é a parte tracejada na Figura 1. Já na consulta “Sobe”, o objetivo é descobrir os nomes de todos os chefes de alguém (diretos e indiretos). No caso do João, a resposta seria o conjunto composto por Roger->Felipe->João (o próprio objeto de consulta faz parte da resposta, e os registros são exibidos do chefe menos direto para o mais direto).

No decorrer do artigo, mostraremos como estas duas consultas podem ser respondidas usando formas alternativas de modelagem. Vale destacar que os questionamentos que serão suscitados para estes casos são genéricos, e as respostas encontradas poderão servir como guia geral para a solução de diversos outros tipos de consulta hierárquica.

Junções de tabela pré-definidas (Hardcoded Joins)

O primeiro modelo que estudaremos é o descrito na Tabela 1. O esquema, que possui dados de funcionários, é um dos mais comuns quando se trata de modelos hierárquicos, e recebe o nome de modelo adjacente. O nome deve-se ao fato de que a informação do chefe (idChefe) é armazenada juntamente com outros dados do funcionário. Perceba a existência de um autorrelacionamento entre idChefe e id.

Quando se trata do modelo adjacente, uma das formas de resolver consultas é fixando (hardcoding) os critérios de junção SQL. A Listagem 1 mostra como ficariam os comandos SQL necessários para responder às consultas “Sobe” e “Desce”. O parâmetro “:ID” corresponde ao funcionário a partir de onde deve ser montada a resposta, que chamaremos de funcionário base. O mesmo parâmetro aparecerá nos demais exemplos descritos neste artigo para referenciar o funcionário base.

  Consulta 1 – Subordinados (Consulta Desce)
       SELECT base.id, base.nome, sub.id, sub.nome
       FROM funcionario base LEFT JOIN funcionario sub
       ON sub.idChefe = base.id
       WHERE b.idChefe = :ID
       ORDER BY base.id, sub.id
   
  Consulta 1 – Chefes (Consulta Sobe)
       SELECT chefe1.id, chefe1.nome, chefe2.id, chefe2.nome
       FROM funcionario base, funcionario chefe1, funcionario      
       chefe2
       WHERE base.id = :ID AND base.idChefe = chefe1.id 
  AND chefe1.idChefe = chefe2.id
       ORDER BY chefe1.id, chefe2.id 

O problema com esta abordagem se torna evidente ao analisarmos a cláusula WHERE. As junções usadas conseguem atingir até dois níveis hierárquicos: no caso da consulta “Desce”, dois níveis abaixo, e na consulta “Sobe”, dois níveis acima. No entanto, como costuma ocorrer com casos reais, não existem limites para os níveis de largura e profundidade da árvore. Assim sendo, se novos níveis fossem acrescidos, essas relações extras de subordinação não seriam capturadas pelas consultas. Isso implicaria em manutenção de código para que as consultas fossem adaptadas.

Supondo que o número de níveis seja constante, ainda assim o método descrito merece algumas ressalvas. Em primeiro lugar destacamos o número de junções necessárias, equivalente ao número de níveis existentes entre o funcionário base e a raiz (para a consulta “Sobe”) ou entre o funcionário base e o último nível (para a consulta “Desce”). Dependendo da altura da árvore, o tempo necessário para o processamento dessas junções pode se tornar proibitivo.

Outro fator que deve ser considerado é a redundância de dados, como demonstrado na Tabela 2. A tabela exibe o resultado de uma consulta “Desce” adaptada que traz todos subordinados de Roger. As células pintadas representam informações que já foram capturadas em algum registro anterior. Como se pode ver, a redundância nesse caso chega a quase 50% dos resultados.

Funções recursivas em linguagens de programação

Uma forma de evitar a préfixação dos critérios de junção é através do uso de funções recursivas, explorando as facilidades existentes nas linguagens de programação. A Listagem 2 mostra um pseudocódigo que atende às consultas “Sobe” e “Desce”.

  Consulta 1 – Subordinados (Consulta Desce)
  FUNÇÃO ExibeSubordinados(id, edentação) 
       //camada de BD
       SELECT id, nome
       FROM funcionario WHERE idChefe = :id
     
       //camada de software
       FAÇA ENQUANTO houver registros de funcionario
           Realiza a endentação
           imprime funcionario.nome
           //chamada recursiva
           ExibeSubordinados(funcionario.id, edentação+1)
  FIM DA FUNÇÃO
  //para imprimir os subordinados de João (id = 4)
  ExibeSubordinados(4,1);
   
  Consulta 1 – Chefes (Consulta Sobe)
  FUNÇÃO EncontraChefes(id) //Consulta Sobe
       //camada de BD
       SELECT chefe.id, chefe.nome
       FROM funcionario base, funcionario chefe
       WHERE base.id = :ID AND base.idChefe = chefe.id 
     
       //camada de software
       SE for encontrado algum registro
           imprime chefe.nome
            //chamada recursiva
           EncontraChefes(chefe.id)
  FIM DA FUNÇÃO
  //Encontrar chefes do João (id = 4)
  EncontraChefes(4); 

Quanto à consulta “Desce”, o código recursivo vai sucessivamente obtendo/imprimindo os subordinados de cada funcionário, empregando o caminhamento em profundidade. A função é genérica e permite que a impressão comece em qualquer nível da árvore através do fornecimento do identificador correto. Se o valor fornecido for nulo, a árvore inteira é impressa. O código também descreve em linhas gerais como o controle de endentação pode ser feito para garantir que a disposição hierárquica dos funcionários no relatório possa ser visualmente compreendida.

O código referente à consulta “Sobe” segue a mesma linha do anterior. Em uma iteração do algoritmo, é descoberto quem é o chefe do funcionário passado como parâmetro. Além de serem impressos, os dados do chefe são repassados para a função para que a iteração seguinte descubra quem está no nível superior, e assim sucessivamente até atingir o nível máximo.

Conta a favor desta abordagem a sua simplicidade. O código demonstrado é bastante intuitivo e poderia ser facilmente aplicado para resolver os problemas propostos neste artigo. No entanto, se trata de uma saída custosa, pois cada nó visitado gera uma consulta extra. Por exemplo, considerando a árvore da Figura 1, e supondo que se deseje imprimir a árvore inteira, nove consultas teriam que ser submetidas ao banco. Parece um número razoável, mas não se esqueça que estamos trabalhando com uma árvore bastante pequena. Em uma corporação com muitos funcionários, o ônus de comunicação com o banco tornaria esta solução extremamente inviável.

Carga total para a memória

Ainda considerando linguagens de programação, pode-se reduzir os custos de comunicação com o banco de dados através de um processo inicial de carga total para a memória. Nesse processo, todos os registros de funcionários são carregados para a memória onde ficam residentes em uma estrutura de árvore.

A consulta SQL de carga é simples, como mostra a Listagem 3. O trabalho maior fica a cargo da linguagem de programação, que deverá criar os objetos relativos aos funcionários e associá-los aos seus chefes. Com todos os dados em memória, consultas são respondidas através do caminhamento da árvore.

  //Obtém todos os dados
       SELECT f.id, f.nome, f.idChefe
       FROM funcionario f 

Como benefício desta abordagem, têm-se todos os recursos da linguagem de programação à disposição para a realização das consultas, o que assegura um poder de expressão muito maior do que o de uma linguagem declarativa como a SQL. Outra vantagem em relação ao método anterior está no número reduzido de acessos ao banco (necessários apenas no momento de carga inicial).

Caso não seja possível manter os dados em sessão, a saída é recriar a árvore a cada requisição ao servidor. Aqui é importante ter cuidado. Caso a tabela possua muitos registros, a consulta pode ser muito custosa. Na verdade, se o número de registros for muito elevado, até mesmo manter a árvore em memória é perigoso. Se este for o caso, talvez seja melhor escolher outra alternativa.

Stored Procedures

Nas duas seções anteriores, vimos como os problemas propostos são resolvidos quando se delega a complexidade para a camada de software. Nesta seção, o enfoque é oposto. Boa parte do processamento é realizada dentro de uma stored procedure (SP), deixando para a camada de software o simples trabalho de impressão dos resultados obtidos.

A Listagem 4 mostra stored procedures em MySQL usadas para encontrar as respostas. Como se pode ver, as SPs são bastante parecidas. Os dois algoritmos utilizam uma tabela auxiliar, usada para armazenar resultados parciais. Basicamente, no decorrer do processamento são realizadas buscas em largura, jogando para a tabela auxiliar os registros que forem sendo encontrados.

Para a consulta “Desce”, a cada iteração são buscados os registros cujos chefes já estiverem na tabela de resposta. Para a consulta “Sobe”, a cada iteração são buscados os registros cujos subordinados já estiverem na tabela de resposta. A clausula IGNORE é própria do MySQL e garante que não ocorrerá erro ao se tentar inserir registros que já existirem na tabela.

  Consulta 1 – Subordinados (Consulta Desce)
          DROP PROCEDURE IF EXISTS calculaArvore;
          DELIMITER go
          CREATE PROCEDURE calculaArvore(raiz INT )
          BEGIN
          DROP TABLE IF EXISTS arvore;
          CREATE TABLE arvore
          SELECT id, idChefe, 0 AS nivel
          FROM funcionario
          WHERE idChefe = raiz;
          ALTER TABLE arvore ADD PRIMARY KEY(id);
          REPEAT
          INSERT IGNORE INTO arvore
          SELECT f.id, f.idChefe, arv.nivel+1
          FROM funcionario f
          JOIN arvore arv ON f.idChefe = arv.id;
          UNTIL Row_Count() = 0 END REPEAT;
          END;
          go
 
 Consulta 2 – Chefes (Consulta Sobe)
          DROP PROCEDURE IF EXISTS calculaArvore;
          DELIMITER go
          CREATE PROCEDURE calculaArvore(raiz INT )
          BEGIN
          DROP TABLE IF EXISTS arvore;
          CREATE TABLE arvore
          SELECT id, idChefe, 0 AS nivel
          FROM funcionario
          WHERE id = raiz;
          ALTER TABLE arvore ADD PRIMARY KEY(id);
          REPEAT
          INSERT IGNORE INTO arvore
          SELECT f.id, f.idChefe, arv.nivel+1
          FROM funcionario f
          JOIN arvore arv ON arv.idChefe = f.id;
          UNTIL Row_Count() = 0 END REPEAT;
          END;
          go 

A computação começa a ficar mais densa à medida que a tabela auxiliar aumenta, pois a cada iteração os dados dessa tabela são cruzados com os dados da tabela “Funcionario”. Outro efeito desagradável é o desperdício de processamento na geração de registros redundantes, pois o conjunto de dados usado em uma interação para encontrar resultados é um subconjunto dos dados usados na interação seguinte. Ou seja, mesmo reduzindo os custos de comunicação com o SGBD, os custos internos de processamento podem se tornar expressivos. Dependendo da política de segurança configurada pelo DBA, é bem possível que consultas demoradas sejam interrompidas por timeout.

Se for esse o caso, não se preocupe, existem diversos tipos de SP que podem ser usadas. A que foi mostrada acima usa particularidades do MySQL, e consegue fugir do processamento recursivo, tão temido por alguns. Outros tipos de SP são mais genéricos (não ficam restritos a algum SGBD específico) e usam estratégias diferentes para buscar os dados de interesse. Por exemplo, uma abordagem genérica bastante comum emprega tabelas auxiliares que tem por objetivo empilhar informações. Em um momento posterior, estas informações são desempilhadas e tratadas já na ordem correta de caminhamento.

Observe que, para a consulta “Desce”, os registros são disponibilizados na ordem de caminhamento em largura. É necessário levar isso em consideração na hora de elaborar o algoritmo que consumirá esses dados, principalmente se o objetivo for a geração de relatórios de subordinação. No caminhamento em largura, muitos dos nós lidos só serão impressos mais adiante. Assim, é preciso mantê-los em memória até o momento em que eles forem processados. Antes de adotar uma solução baseada no caminhamento em largura, verifique se essa sobrecarga é aceitável. Já no caminhamento em profundidade os nós são lidos na ordem em que devem ser impressos. A princípio isso parece evitar o uso desnecessário de recursos computacionais. No entanto, dependendo de como a solução foi desenvolvida, parte das vantagens dessa forma de caminhamento são perdidas. Por exemplo, caso a solução seja baseada em recursividade, é possível que alguns recursos precisem ser alocados, seja na forma de registros em memória ou conexões extras com o banco de dados.

Recursos específicos de SGBDs

A seção anterior mostrou como problemas de consultas hierárquicas podem ser resolvidos usando Stored Procedures. Apesar desse recurso estar presente em praticamente todos SGBDs comerciais, a sintaxe para criação das SPs é própria de cada fornecedor. Isso dificulta processos de migração de bancos de dados, pois todas SPs precisariam ser convertidas para o novo formato. Caso você esteja muito satisfeito com seu banco, e não se preocupa com o uso de recursos específicos, siga lendo esta seção.

O que apresentaremos se chama Common table Expressions (CTE). Esse recurso permite gerar resultados intermediários, que são complementados através de chamadas recursivas que usam os mesmos resultados intermediários. A capacidade de chamar a si próprio possibilita que estruturas hierárquicas sejam processadas de forma simples.

A Listagem 5 mostra como responder as consultas “Sobe” e “Desce” utilizando CTE. O código usa a sintaxe própria do PostGres, mas com poucas adaptações ele pode ser traduzido para sintaxes de outros bancos, como DB2 e SQL Server.

  Consulta 1 – Subordinados (Consulta Desce)
  WITH RECURSIVE chefe AS
  (
      SELECT id, nome, idChefe, 0 AS nivel 
      FROM funcionario WHERE id= :ID 
      
      UNION ALL
      
      -- chamada recursiva
      SELECT sub.id, sub.nome, sub.idChefe, nivel+1
      FROM funcionario sub
      JOIN chefe ON (sub.idChefe = chefe.id)
  )
  SELECT * FROM chefe ORDER BY nivel;
   
   
  Consulta 2 – Chefes (Consulta Sobe)
  WITH RECURSIVE sub AS
  (
      SELECT id, name, idChefe, 0 AS nivel 
      FROM funcionario WHERE id= :ID 
      
      UNION ALL
      
      -- chamada recursiva
      SELECT chefe.id, chefe.name, chefe.idChefe, nivel+1
      FROM funcionario chefe
      JOIN sub ON (sub.idChefe = chefe.id)
  )
  SELECT * FROM sub ORDER BY nivel DESC; 

Para a consulta “Desce”, o resultado intermediário pode ser gerado inicialmente com um registro base, correspondente ao chefe de interesse. Uma chamada recursiva seria usada para encontrar os subordinados desse chefe. Para esses subordinados, uma nova chamada recursiva seria usada para encontrar seus respectivos subordinados, e assim por diante. No final, todos os registros encontrados são unidos. O efeito é parecido a SP demonstrada na seção anterior, com os registros finais gerados na ordem de caminhamento em largura. No entanto, o mecanismo empregado para a geração da resposta é mais eficiente, não calculando registros redundantes e usando conjuntos de dados mais enxutos durante a computação. Já a consulta “Sobe” se assemelha tanto com a consulta “Desce” que dispensa muita explicação. A única diferença é que a recursão é usada para buscar os chefes, e com isso o critério de junção (chefe=idChefe) precisa ser invertido. Vale ressaltar que esse artifício não está presente em todos SGBDs. Por exemplo, o MySQL não possui suporte a esse tipo de chamada recursiva. Para tratar dados hierárquicos no MySQL, ou usa-se algum método baseado em SQL ANSI ou usa-se stored procedures como as descritas na seção anterior. Já outros SGBDs não apenas suportam CTE, mas oferecem outras possibilidades para fins parecidos. Por exemplo, o CONNECT BY da Oracle resolve consultas hierárquicas de uma maneira relativamente simples.

Outro ponto que merece destaque é um que já foi mencionado antes. O grande inconveniente das soluções comentadas nessa seção, seja CTE, SPs ou CONNECT BY, é o fato de que elas usam linguagens proprietárias. Se porventura surgir a necessidade de migrar para outro fornecedor de banco de dados, todo código proprietário precisará ser convertido. Em alguns casos a conversão pode ser intuitiva, mas de qualquer forma, será algo a mais com o que se preocupar.

Modelo Plano

A Tabela 3 mostra como ficam os dados de exemplo depois da adição destes atributos. Opcionalmente, a tabela poderia ser dividida verticalmente em duas, deixando a tabela original com informações próprias do funcionário (ex. “Id”, “nome”) e a tabela derivada com informações de controle de hierarquia (“rank”, “nível”, “idChefe”). A divisão torna o modelo mais modular, uma vez que ele ajuda a definir o papel de cada tabela do modelo. Por outro lado, as consultas hierárquicas passam a conter junções extras para associar os registros divididos. Para fins didáticos, neste artigo optamos pela solução mais simples, e mantivemos tudo em uma única tabela. Em aplicações reais, caberá ao projetista escolher a opção que julgar mais conveniente.

Com base nas informações da Tabela 3, pode-se usar o SQL da Listagem 6 para imprimir toda a árvore de funcionários.

  //Obtém todos os dados
  SELECT nome, nivel
       FROM funcionario 
       ORDER BY rank 

Observe o uso do atributo rank. Ao ordenar a consulta por esse atributo, se garante que os registros sejam lidos na ordem com que devem ser inseridos na árvore (leitura em profundidade). No entanto, sua utilidade se restringe a poucos casos. Por exemplo, o atributo é útil se for necessário imprimir um relatório com todos os níveis de profundidade (o que é um subcaso da consulta “Desce”). Na maioria dos outros casos, seria necessário usar algumas das soluções mostradas anteriormente.

Já o atributo nível ajuda no controle da endentação. Com base no valor desse atributo sabe-se qual a tabulação que deve ser empregada na impressão. Esse atributo representa uma forma de evitar que a endentação tenha que ser calculada via linguagem de programação, como foi demonstrado nas primeiras seções do artigo. O problema passa a ser atualizar os valores do atributo quando os dados de hierarquia sofrerem modificações.

Nested Set Model

Na seção anterior foi mostrado um modelo onde um atributo (rank) armazena a posição do elemento dentro da árvore, com base no caminhamento por profundidade. Nesta seção, veremos um modelo que segue esta mesma linha, mas que pode ser empregado em um número maior de problemas.

Em vez de um atributo, teremos dois atributos cujo propósito é armazenar o posicionamento do elemento. Vamos chamá-los de dir (direita) e esq (esquerda).

A Figura 2 mostra a árvore já preenchida com esta nova informação posicional. O preenchimento ocorre da seguinte forma: um valor é incrementado conforme se caminha pela árvore em profundidade. Quando se passa por um elemento na descida, o valor da esquerda é atualizado com o próximo incremento. Quando se passa por um elemento na subida, o valor da direita é atualizado.

A Tabela 4 mostra como ficaria o novo esquema de acordo com este modelo. Observe que o atributo “idChefe” foi removido, uma vez que é possível obter esta informação através dos atributos “esq” e “dir”.

Você deve estar se perguntando como calcular os valores no momento de alterações nesta tabela. Neste artigo não mostraremos como isso é feito, mas fique tranquilo. Existem scripts que atualizam corretamente estes atributos, quando um funcionário for incluído, removido ou remanejado.

Observando a árvore da Figura 2, podemos perceber uma característica importante. Se compararmos algum nó filho com qualquer um de seus nós pai, veremos que o atributo “esq” do nó filho é sempre maior do que o atributo “esq” do pai, e menor do que o atributo “dir” do pai. Essa propriedade é garantida pela forma como os atributos são calculados, e se mostra particularmente útil para responder consultas nesse modelo.

Um exemplo de sua serventia fica evidente na Listagem 7. Para encontrar os subordinados de algum chefe, primeiro criamos duas instâncias da tabela “Funcionario”, uma para representar o chefe e outra para buscar seus subordinados. O próximo passo é comparar os atributos “esq” e “dir” do chefe escolhido com o atributo “esq” de cada um dos funcionários existentes. Já para buscar os chefes de algum funcionário, basta fazer a correlação contrária, definindo o subordinado escolhido e comparando os atributos “esq” e “dir” usando a lógica inversa.

Como já demonstrado em outro exemplo, o atributo “nivel” é usado para controlar a altura na árvore. Esse atributo é útil para a endentação dos resultados na consulta “Desce”, pois ajuda a determinar quem é o chefe direto dos funcionários retornados. Na verdade, essa informação é desnecessária. Existe uma correlação entre os atributos “esq” e “dir” que responde essa pergunta. Deixaremos para você a missão de analisar os dados e resolver esse dilema.

  Consulta 1 – Subordinados (Consulta Desce)
 SELECT sub.id, sub.nome, sub.nivel 
 FROM funcionario base, funcionario sub 
 WHERE sub.esq <= base.dir  AND sub.esq >= base.esq 
  AND base.id = :ID 
 ORDER BY sub.esq
  
 Consulta 2 – Chefes (Consulta Sobe)
  SELECT chefe.id, chefe.nome 
 FROM funcionario chefe, funcionario base 
 WHERE base.esq <= chefe.dir AND base.esq >= chefe.esq  
  AND base.id = :ID 
 ORDER BY chefe.esq 

As consultas da Listagem 7 obtém um ótimo desempenho se comparadas com as abordagens anteriores. Com apenas uma junção é possível descobrir todos subordinados ou todos os chefes de alguém. No entanto, nem todas as tarefas possuem a mesma simplicidade. Na verdade, tarefas que deveriam ser simples exigem a adoção de scripts complexos. Por exemplo, a exclusão de algum funcionário pode requerer que boa parte dos demais funcionários tenham seus atributos “esq” e “dir” atualizados. Uma forma de minimizar esse problema envolve o uso de valores mais “espalhados” para os atributos “esq” e “dir”. A escolha correta de valores para esses atributos pode evitar que alterações em algum nó da árvore tenham que ser propagados para nós vizinhos.

As operações de consulta também podem exigir uma boa dose de processamento em alguns casos específicos. Por exemplo, para descobrir o subordinado (ou o chefe) imediato de algum funcionário, são necessários três autorrelacionamentos e uma subconsulta, sendo que o modelo adjacente puro resolve o problema com apenas um autorrelacionamento.

Para casos como esse, não existe fórmula mágica que torne a consulta mais enxuta. Caso você decida que o Nested Set Model é ideal para as suas necessidades, o que pode ser feito é identificar subconsultas que são disparadas com muita frequência e transformá-las em visões. Isso não elimina a necessidade de subconsultas, mas agiliza seu processamento. No final das contas, seja qual for o modelo que você escolher, um bom tuning sempre terá o seu valor.

Modelos de Enumeração de Caminho

Nesta seção mostraremos soluções baseadas em modelos de enumeração de caminho. Esses modelos se caracterizam pelo uso de um atributo especial, cuja função é armazenar o caminho hierárquico dos elementos. Dois submodelos se destacam: Enumeração de Vértice (Node Enumeration) e Enumeração de Arco (Edge Enumeration), sendo que a denominação depende do conteúdo que é armazenado no atributo.

A Tabela 5 mostra um exemplo de Enumeração de Vértice. O caminho até um funcionário está indicado no atributo “caminho”. Esse atributo armazena o identificador do próprio funcionário concatenado com os identificadores de seus chefes. Usamos a barra (/) para separar os identificadores. Contudo, qualquer caractere pode ser usado, desde que se possa garantir que ele não irá aparecer como parte de algum identificador. Assim como no modelo plano, o atributo nível é usado unicamente para controle de endentação. Quem achar melhor removê-lo, poderá fazer a endentação via linguagem de programação, inferindo o nível pelo número de barras (/) presentes no atributo “caminho”.

A Listagem 8 mostra as consultas que resolvem os problemas “Sobe” e “Desce”. Para encontrar os subordinados, a ideia é procurar por registros cujo caminho contenha o caminho do registro base, o que no MySQL pode ser obtido através do operador POSITION. O operador POSITION também é utilizado para encontrar os chefes, porém de forma oposta. Desta vez a ideia é procurar por registros cuja sequência esteja contida na sequência do registro base. É importante ressaltar que as duas consultas demonstradas recorrem a funções de string para chegar até um resultado. Por esse motivo, para agilizar a busca, é interessante que seja criado algum índice sobre o atributo “caminho”.

  Consulta 1 – Subordinados (Consulta Desce)
 SELECT sub.nome, sub.id, sub.nivel 
 FROM funcionario base, funcionario sub 
 WHERE POSITION(base.caminho IN sub.caminho)
  AND base.id = :ID 
  ORDER BY sub.caminho;
   
  Consulta 2 – Chefes (Consulta Sobe)
  SELECT chefe.nome, chefe.id 
 FROM funcionario base, funcionario chefe 
 WHERE POSITION(chefe.caminho IN base.caminho) 
  AND base.id = :ID 
 ORDER BY chefe.caminho; 

Na enumeração de arco, o atributo “caminho” recebe um conteúdo diferente. Em vez do identificador do próprio registro, usa-se um número de sequência próprio que identifica a posição de um elemento embaixo do seu pai. A Tabela 6 mostra como ficariam os dados se o caminho fosse gerado dessa forma.

Os mesmos algoritmos usados na Enumeração de Vértice podem ser usados na Enumeração de Arco, sendo que os resultados são bastante parecidos. A diferença pode ocorrer na ordem com que os elementos irmãos são exibidos. A ordem é definida pelo atributo caminho. Na Enumeração de Vértice, este atributo possui identificadores dos registros, o que torna difícil controlar a sequência em que os registros irmãos são retornados.

Já com a Enumeração de Arco, o caminho é composto por um número sequencial, cujo valor é determinado pela lógica de inserção que o projetista elaborou. Assim, caso se deseje preservar uma determinada ordem entre irmãos, a Enumeração de Arco é mais adequada. Apenas esteja ciente de que será necessário um trabalho extra para que os números sequenciais sejam gerados de acordo.

Também é importante observar que existe um limite para o número de níveis que esses modelos suportam, e esse limite está relacionado com o tamanho do atributo “Caminho”. Por exemplo, suponha que esse atributo seja um char de 255 posições, e que os identificadores possam ter no máximo cinco dígitos cada (máximo 99999). Nessas circunstâncias, são suportados até 51 níveis, sem que o tamanho do atributo estoure. Dependendo dos requisitos do projeto, tal quantidade de níveis pode variar entre adequada, razoável e até mesmo arriscada. Antes de tomar uma decisão, verifique quais são as reais necessidades, tanto imediatas quanto de longo prazo. Afinal, ainda que se possa adaptar o modelo para suprir níveis excedentes (por exemplo, através da adição de um novo atributo de caminho), este trabalho acaba gerando um estresse que poderia ser evitado.

Método Chandler

De certa forma, a abordagem apresentada nesta seção também se baseia na informação de caminho. A diferença fundamental é que, em vez de um único atributo, múltiplos atributos são necessários, um para cada nível da árvore.

A Tabela 7 mostra os atributos necessários para a nossa árvore de exemplo, juntamente com os valores que foram atribuídos para eles. Se compararmos estas informações com o caminho armazenado na Tabela 6, veremos que a lógica deste modelo se aproxima bastante da lógica empregada na Enumeração de Arco.

O número de níveis preenchidos (diferentes de zero) mostra a altura do funcionário dentro da hierarquia. Por exemplo, o Diretor Executivo (grau máximo na instituição) está no topo, pois apenas um nível está preenchido. Os subordinados recebem os mesmos valores atribuídos para seus respectivos chefes, com exceção do atributo que indica o seu próprio nível. Este recebe um número sequencial, que indica a ordem do subordinado embaixo do seu chefe.

A Listagem 9 mostra os comandos usados para responder as duas consultas propostas. Para popular espaço, usamos apelidos curtos para os funcionários base (b), chefe (c) e subordinado (s).

O comando SQL usado para encontrar os subordinados é bastante simples. A relação entre o funcionário base e seus subordinados é alcançada através de uma comparação dos seus níveis. É importante observar que a comparação precisa ser feita pelo atributo correto, que é aquele que indica a altura do funcionário base. No caso da João, trata-se do atributo “nivel3”.

Para que a impressão do relatório respeite o caminhamento em profundidade, é preciso ordenar os registros pelos níveis, conforme indicado no comando SQL. Os níveis também podem ser usados para controle de endentação. Quanto mais níveis diferentes de zero, maior será a tabulação dada na impressão.

Para encontrar os chefes de um funcionário, aplica-se a lógica inversa da usada para encontrar os subordinados, como em outros casos mostrados no artigo. Para orientar a comparação de níveis, verifica-se o atributo “nivel” do funcionário “chefe” em vez do atributo “nivel” do funcionário “base”.

Como se pode ver, o atributo “nivel” tem um papel importantíssimo. Com ele, é possível criar consultas genéricas compostas por critérios condicionais (CASE-WHEN). Sem ele, os critérios de comparação teriam que ser ajustados dependendo da altura do funcionário que se deseja pesquisar, o que tornaria a consulta engessada. A solução que apresentamos aqui é na verdade uma adaptação do modelo Chandler, visto que o modelo original não faz menção ao uso desse atributo.

  Consulta 1 – Subordinados (Consulta Desce)
 SELECT s.id, s.nome, s.nivel
  FROM  funcionario b, funcionario s 
  WHERE b.id = :ID AND 
  CASE 
  WHEN b.nivel= 1 THEN b.nivel1 = s.nivel1 
  WHEN b.nivel= 2 THEN b.nivel2 = s.nivel2 
  WHEN b.nivel= 3 THEN b.nivel3 = s.nivel3 
  WHEN b.nivel= 4 THEN b.nivel4 = s.nivel4 
  WHEN b.nivel= 5 THEN b.nivel5 = s.nivel5 
  END  
  ORDER BY c.nivel1, c.nivel2, c.nivel3, c.nivel4, c.nivel5; 
   
  Consulta 2 – Chefes (Consulta Sobe)
 SELECT c.id, c.nome, c.nivel 
 FROM  funcionario b, funcionario c 
 WHERE b.id = :ID AND 
  CASE 
 WHEN c.nivel = 1 THEN b.nivel1 = c.nivel1 
 WHEN c.nivel = 2 THEN b.nivel2 = c.nivel2
 WHEN c.nivel = 3 THEN b.nivel3 = c.nivel3
 WHEN c.nivel = 4 THEN b.nivel4 = c.nivel4
 WHEN c.nivel = 5 THEN b.nivel5 = c.nivel5 
  END
 ORDER BY c.nivel1, c.nivel2, c.nivel3, c.nivel4, c.nivel5; 

Já vimos que o Método Chandler se aproxima bastante do modelo de Enumeração de Arco, ao menos conceitualmente. Isso nos leva à conclusão lógica de que esse método pode também ser aplicado nos moldes da Enumeração por Vértice. A Tabela 8 mostra o Modelo de Chandler adaptado (mais uma vez), usando identificadores dos registros como os valores dos níveis, em vez de números sequenciais.

Para imprimir uma subárvore, ou listar os chefes, o processo é exatamente igual ao usado na Listagem 9. Nenhuma linha precisaria ser modificada. O benefício desse novo padrão de representação de níveis se torna aparente em outros tipos de consulta. Por exemplo, o chefe direto de alguém pode ser descoberto com uma consulta simples. Outro exemplo bacana envolve descobrir o chefe que está a uma certa altura de alguém, sendo a altura definida por um critério de seleção. A resolução desse problema fica como exercício para você.

Para quem estiver se perguntando, o nome deste método é dedicado a pessoa que garantiu os direitos de propriedade intelectual da ideia. Chega a surpreender o fato de alguém ter conseguido patentear o modelo, pois se trata de uma solução que sempre foi de conhecimento público (ou pelo menos aparentava ser). De qualquer forma, o Método Chandler foi concebido como uma forma de evitar as operações com strings necessárias com os modelos de Enumeração de Caminho. No entanto, ele usualmente requer o uso de consultas pouco intuitivas, como acabamos de ver nos exemplos. Além disso, trata-se de uma solução um tanto amarrada. Afinal, além da dificuldade em montar consultas genéricas (que conseguimos vencer com o uso de um atributo extra), é preciso saber de antemão quantos níveis devem ser suportados. Se a árvore crescer além do esperado, novos atributos precisariam ser adicionados, e estas mudanças de esquema quase nunca são vistas com bons olhos.

Dados hierárquicos e os paradigmas de programação

De certo modo, linguagens de programação são mais propícias para realizar determinadas operações, especialmente sobre modelos hierárquicos. Isso ocorre porque as linguagens normalmente usadas são procedurais. Isto é, cabe ao desenvolvedor especificar exatamente o que deve ser feito, usando pequenos blocos de construção. Isso lhe dá uma flexibilidade tremenda, e abre a possibilidade para que algoritmos dos mais complexos possam ser implementados.

Com SQL é diferente. Trata-se de uma linguagem declarativa, onde o desenvolvedor especifica o que deve ser feito, e não como. Linguagens declarativas são naturalmente mais limitadas, servindo para um tipo específico de operação. No caso do SQL, as operações ocorrem sobre relações. Esse é o seu forte. É por isso que, ao modelar hierarquias como relações é esperado encontrar dificuldades em especificar alguns tipos de consulta.

Uma possibilidade ainda não mencionada envolve utilizar linguagens de consulta voltadas a dados hierárquicos, como XPath/XQuery. Xquery é uma linguagem declarativa, assim como SQL. A diferença é que ela foi projetada para modelos hierárquicos, sendo baseada em caminhos de acesso e uma série de recursos com os quais já estamos acostumados, como caracteres coringa e filtros. Ou seja, para consultas hierárquicas, essa linguagem se torna naturalmente mais expressiva do que a linguagem SQL.

Deixamos a Listagem 10 como exemplo de consulta que pode ser criada por meio desse paradigma. A consulta lê um documento XML contendo dados de funcionários e retorna um documento XML contendo a árvore de subordinação desses funcionários.

  Consulta 1 – Subordinados (Desce)
 declare function acme:exibeSub($func) { 
  <Func nome="{$func/nome}"> 
  <Subordinados> 
  {
  for $f in //Funcionario[idChefe = $func/id] 
  return acme:exibeSub($f) 
  } 
  </Subordinados>
   </Func> 
  };
  //exibe os subordinados do diretor executivo 
  acme:exibeSub (//Funcionario[empty(idChefe/text())])

Como mencionado, a consulta XQuery da Listagem 10 requer um documento XML como entrada. Se estamos trabalhando com uma base relacional, isso significa que teríamos que primeiro converter os dados para um formato compatível com XQuery. Por exemplo, poderíamos carregar os dados para uma árvore DOM e processar os relacionamentos de subordinação a partir daí. Essa solução lembra a que foi explicada na seção “Carga Total para a Memória”, só que nesse caso usamos SQL para carregar os dados e XQuery para navegar por eles.

Em vez dessa solução híbrida, onde duas linguagens de consulta são necessárias, também se poderiam utilizar bancos de dados XML nativos. Nesses bancos de dados, toda informação é modelada em formato XML. Naturalmente, a linguagem de consulta oficial é baseada em XPath e XQuery. No entanto, tais bancos de dados não são muito populares, e seu uso é mais voltado para certos tipos específicos de aplicação. Por exemplo, quando a finalidade mais comum dos dados é o transporte para outros sistemas, e esse transporte é realizado via XML, talvez seja mais indicado que esses dados já estejam armazenados em XML. Quando a finalidade mais comum é o consumo direto por aplicações, o apelo deste tipo de banco diminui bastante.

Isso vale para os bancos de dados orientados a objetos, ou objeto-relacionais. Seu uso é mais aconselhado para a manipulação de dados complexos, como aqueles envolvidos em aplicações de biologia molecular e manipulação de objetos espaciais. Além do mais, o processamento de consultas hierárquicas não é exatamente o forte desse paradigma. Por um lado, o acesso navegacional através de ponteiros simplifica e agiliza o processamento de muitos tipos de consulta. No entanto, a capacidade de navegar pelos objetos acaba não ajudando muito quando os dados estão dispostos em uma hierarquia de muitos níveis. Nesses casos, um banco de dados relacional apoiado por uma boa modelagem pode ser a melhor saída.

Outra possibilidade envolve abandonar de vez os bancos relacionais e partir para SGBDs hierárquicos, como o IMS da IBM (ler Nota do DevMan 1). Pelo nome, podemos supor que bancos hierárquicos são a melhor pedida para processar consultas hierárquicas. Será? É importante não fazer julgamentos precipitados. Bancos hierárquicos são conhecidos pela rapidez com que os dados são acessados. No entanto, seu uso é um tanto complexo, principalmente para os mais jovens, acostumados com as linguagens de programação de quarta geração.

Para exemplificar, no caso do IMS, o acesso aos dados poderia ocorrer através de uma aplicação escrita em COBOL que realizasse chamadas ao IMS via DL/I. Isso significa criar um programa altamente estruturado onde o acesso aos dados é realizado através de áreas mapeadas chamadas de blocos de controle. Depois disso tudo, talvez ainda seja necessário encapsular a aplicação COBOL em um adaptador que aceite comandos SQL, para que uma aplicação escrita em Java consiga acessar os dados. Isso sem falar que o IMS deve ser executado em plataformas do tipo mainframe.

Ou seja, trata-se de uma solução complexa e acima de tudo cara, tanto para a aquisição dos produtos/plataformas necessários quanto para a criação e manutenção das aplicações. Além do mais, cabe ressaltar que os SGBDs hierárquicos são ótimos para consultas simples. Já consultas complexas, como aquelas em que é necessário realizar o cruzamento entre diversos tipos de dados, são muitas vezes mais bem atendidas por bancos de dados relacionais.

Conclusões

Neste artigo descrevemos diversos métodos que podem ser usados para o armazenamento e consulta de dados hierárquicos. Para exemplificar, apresentamos soluções para duas consultas bastante comuns, uma que descobre os chefes de algum funcionário e outro que descobre quem são os seus subordinados. O material apresentado tem a intenção de servir de base para a criação de soluções que necessitem de dados hierárquicos. Deixaremos para você o trabalho de descobrir como os métodos podem ser usados para responder outros tipos de consulta, e o que deve ser feito para facilitar o armazenamento das informações.

Com um cardápio tão variado de opções, a pergunta que deve ser respondida é qual a melhor solução para o processamento de consultas hierárquicas. Para respondê-la, é imperativo que outras perguntas sejam respondidas antes: Que tipos de consulta hierárquica são necessários? Qual a frequência com que as consultas serão disparadas? Qual o volume de dados que será acessado? Quantas transações simultâneas deverão ser suportadas? E por último, mas não menos importante, quanto sua empresa está disposta a pagar por isso?

Pense bem antes de tomar a decisão. Afinal, escolhas bem embasadas são fundamentais na carreira de alguém. É importante lembrar que, além dos métodos demonstrados, pessoas também caminham pelo organograma da empresa. Por isso faça as escolhas certas, e o próximo relatório hierárquico poderá estar de cara nova. Vai que seu nome apareça alguns níveis acima?