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

Você precisa estar logado para dar um feedback. Clique aqui para efetuar o login
Para efetuar o download você precisa estar logado. Clique aqui para efetuar o login
Confirmar voto
0
 (2)  (0)

Estruturas de dados hierárquicos são aquelas que costumam ser visualizadas na forma de árvore, com ligações entre nós pai e seus respectivos nós filhos. Existem formas bastante interessantes de tratar hierarquias. Como não poderia deixar de ser, cada abordagem tem seus custos e benefícios, e esses são os aspectos que serão discutidos neste artigo.

De que se trata o artigo

Estruturas de dados hierárquicos são aquelas que costumam ser visualizadas na forma de árvore, com ligações entre nós pai e seus respectivos nós filhos. Existem formas bastante interessantes de tratar hierarquias. Como não poderia deixar de ser, cada abordagem tem seus custos e benefícios, e esses são os aspectos que serão discutidos neste artigo.

Em que situação o tema útil

Estruturas de dados hierárquicas são bastante comuns em sistemas de informação, e muitas vezes a equipe de desenvolvimento acaba adotando uma das soluções convencionais de modelagem sem analisar o impacto dessa decisão. Este artigo tem por objetivo orientar os projetistas do banco de dados para que uma solução adequada seja escolhida.

Resumo DevMan

O artigo trata da modelagem de estruturas de dados hierárquicas em bancos de dados relacionais. Diversas possibilidades de solução são apresentadas, desde aquelas baseadas apenas em artifícios de modelagem até aquelas que utilizem recursos específicos de SGBDs. Para cada alternativa é feita uma análise do custo e benefício.

Autores: Sérgio Luis Sardi Mergen e Holisson Soares da Cunha

É 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.

Figura 1. Árvore de relacionamentos de subordinação

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.

Funcionário

Id

Nome

idChefe

1

Roger

Null

2

Felipe

1

3

Alfredo

1

4

Joao

2

5

Ricardo

4

6

Souza

4

7

Marcos

6

8

Julio

6

9

Tiago

Tabela 1. Relacionamentos de subordinação descritos de acordo com o modelo adjacente

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.

Listagem 1. Resolvendo as consultas “Sobe” e “Desce” usando junções pré-definidas

  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.

Nivel 1

"

A exibição deste artigo foi interrompida :(
Este post está disponível para assinantes MVP

 
Você precisa estar logado para dar um feedback. Clique aqui para efetuar o login
Receba nossas novidades
Ficou com alguma dúvida?