Powered by Rock Convert

MODELAGEM DE BANCO DE DADOS: Como modelar estrutura de dados em árvore com banco de dados relacional

Bom, é sempre preferível utilizar um SGDB que trate dados em árvore de forma natural, melhor ainda quando ele for especialmente desenhado para tal fim, como por exemplo, o Neo4j.

Porém existem algumas formas de se trabalhar em SGDB’s relacionais, vou enumerar 4 delas:

1. Lista Adjacente

Solução mais comunmente utilizada, cada entrada (registro) conhece somente seu nó superior, veja um exemplo de estrutura comumente utilizado:

Exemplo: Comentários em um Blog

Nesse exemplo, existe uma tabela que armazena comentários de um blog, existem os comentários principais, que não tem nós superiores (são a “raiz”), e existem os comentários que são respostas a outro comentário, e assim suscetivamente, em uma tabela do SGBD, teríamos a seguinte situação:

Tabela: comentarios

id          parent_id        usuario_id        comentario
----------------------------------------------------------------
1           NULL             33                Gostei do seu...
2           1                34                seu comentario foi exc...
3           1                99                Gostei Também...
4           3                34                Que bom que gostou...
5           NULL             80                Que Post Bacana ...

Renderizando, teríamos algo como:

Usuario 33 Comentou: Gostei do seu ...
      Usuário 34 Comentou: Seu comentario foi exc...
      Usuario 99 Comentou: Gostei Também...
            Usuário 34 Comentou: Que bom que gostou...
Usuario 80 Comentou: Que Post Bacana ...

Os comentários tem a mesa estrutura de dados, porem são aninhados dessa forma, é necessário percorrer recursivamente todos os dados a partir de um determinado ID.

Pontos POSITIVOS: Fácil de Implementar 
Pontos NEGATIVOS: Difícil de manusear em arvores profundas, funciona bem quando são poucos níveis

2. Caminho Enumerado

Basicamente a mesma estrutura do exemplo acima, porem a tabela contem o caminho desde o nó raiz até o ele próprio, veja o exemplo:

Tabela comentarios

Powered by Rock Convert

id          path_to_comment  usuario_id        comentario
----------------------------------------------------------------
1           /                33                Gostei do seu...
2           /1/2             34                seu comentario foi exc...
3           /1/3             99                Gostei Também...
4           /1/3/4           34                Que bom que gostou...
5           /                80                Que Post Bacana ...

Dessa forma poderíamos pegar os cometários abaixo do comentário de ID 3 fazendo algo como:

SELECT * from comentarios WHERE path_to_comment LIKE '/1/3/%';

Pontos POSITIVOS: Fácil de Implementar, consulta mais rápida e eficiente que o método de Lista Adjacente 
Pontos NEGATIVOS: É relativamente difícil refazer o caminho quando realocamos um elemento

3. Conjuntos Aninhados

É um método um pouco mais complexo, vou dar uma visão geral, pois uma resposta completa iria prolongar muito um resposta que é um visão geral sobre os métodos, então vamos lá:

Consistem em armazenar com cada nó, dois número (um para a esquerda e outro para a direita), o da esquerda armazena um número menor que o menor ID dos seus descendentes, e o número da direita, armazena um número maior, que o maior ID dos seus descendentes, então a fazer uma query, teríamos um escopo de busca, que em termos de performance seria bem mais eficiente que os outros métodos, veja uma imagem que ilustra isso:

Pontos POSITIVOS: Performance muito maior, facilidade de atravessar. 
Pontos NEGATIVOS: Bem mais difícil para implementar do que os outros métodos; performance não é tão maior em SGDB que não tem suporte a queries recursivas (exemplo: MySQL)

Te recomendo fazer um pergunta aqui no StackOverflow sobre essa técnica, daí eu ou outro usuário podemos te demonstrar melhorar tal técnica

4. Tabela de Relacionamento

Basicamente uma tabela “Muito-para-muitos” que armazena todas as ligações de um nó com seus descendentes, semelhante com a técnica do caminho enumerado, porém um pouco mais flexível e com mais performance que tal.

Conclusão

Para determinar a melhor estrutura para representar sua árvore, faça as seguintes perguntas:

1. A profundidade máxima é garantidamente muito pequena? (i.e. no máximo uns 3)Se a resposta for sim, uma solução mais simples pode ser a ideal (as souções mais complexas “se pagam” quando a escala do problema é grande). A “Lista de Adjacências” (Adjacency List) – onde cada nó possui uma chave estrangeira para o seu pai – é uma solução simples e direta. Entretanto, há autores que a consideram uma “solução ingênua” (naïve) – aplicável sim em casos simples, mas em geral a ser evitada.Note que pode ser necessário escrever mais de uma query dependendo da profundidade do nó (ex.: uma pra profundidade 1, uma pra 2, uma pra 3), por isso o requisito da árvore ser garantidamente rasa. Alguns SGBDs suportam “queries recursivas” (ex.: WITH, START WITH e CONNECT BY) que podem simplificar a tarefa, mas não são portáveis, o que foge do escopo da pergunta.
2. A profundidade máxima prevista é pequena?Outra técnica simples, mas sem os problemas da lista de adjacências é a “Enumeração de Caminhos” (Path Enumeration), onde cada nó possui uma coluna texual onde está representada a lista de ids desde a raiz até aquele nó. É simples tanto inserir/remover/modificar nós quanto percorrê-los (seja a sub-ávore, seja seus filhos diretos), bastando uma operação no campo textual – em geral envolvendo prefixos.É bom notar que essa tabela estaria desnormalizada (não está na primeira forma normal) e não possui integridade referencial (a coluna aceitaria listas com ids inexistentes), além do quê os caminhos podem se tornar muito longos em árvores profundas. (o requisito de espaço de um nó é proporcional à sua profundidade)
3. A profundidade máxima prevista é muito grande? Existem nós que são ancestrais da maioria dos outros nós?Se a resposta for não, considere utilizar uma Closure Table (que o @hernandes chamou de “Tabela de Relacionamento”, mas também poderia ser chamada “Tabela de Fechamento“) – uma tabela separada onde cada linha representa uma relação ancestral -> descendente (e talvez profundidade). Essa tabela proporciona rapidez no acesso em troca de maior espaço de armazenamento, e é eficiente para praticamente todo tipo de operação.Uma desvantagem (se estiver usando SQL puro) é a necessidade de manter atualizadas duas tabelas, e queries relativamente complexas (porém eficientes). E se a profundidade for muito grande, os nós folha terão um número elevado de ancestrais, cada um ocupando uma linha no fechamento. (o requisito de espaço de um nó também é proporcional à profundidade, mas o overhead é maior – uma linha para cada ancestral) Uma técnica alternativa pode ser interessante, a menos que…
4. A sua árvore é modificada com frequência? Sua tabela representa mais de uma árvore? (e é factível que duas árvores venham a ser “mescladas” em algum momento?)Caso a resposta seja não, o uso de “Conjuntos Aninhados” pode oferecer uma boa performance com baixo consumo de espaço. Nele cada nó define um intervalo (dois números: limite inferior/esquerdo e limite superior/direito) e considera-se “descendente” todo nó cujo intervalo esteja contido (aninhado) no intervalo de um outro nó. Em geral, as queries de consulta são simples e eficientes, e o requisito de espaço é pequeno e fixo para cada nó (dois inteiros).Entretanto, embora a remoção de um nó seja barata, a inserção ou locomoção de um nó pode ser bem cara, pois é preciso atualizar todos os seus ancestrais, seus irmãos (da direita tradicionalmente, mas uma variação seria escolher o lado com menos irmãos) e os irmãos de todos os seus ancestrais (mesmo lado). Se o nó não for folha, também os seus descendentes. Se o tempo for mais importante que o espaço, é preferível adotar a Closure Table nessa situação.Nota: se a sua tabela representa mais de uma árvore, há uma complicação adicional: a menos que cada nó identifique a qual árvore pertence, os conjuntos de uma ávore poderiam interferir nos conjuntos da outra. Isso faria com que alterações em um nó afetasse inclusive nós de outras árvores! E se a mesclagem de árvores for possível, todo o conjunto de uma delas pelo menos teria de ser refeito.

VOCÊ ESTÁ NA SEÇÃO:  Banco de Dados

• Sobre
• Últimos Posts

Ramos de Souza Janones

Janones, é um empreendedor brasileiro apaixonado por empreendedorismo e tecnologia. Ao longo dos anos trabalhando com o desenvolvimento de softwares desktop desde a linguagem Clipper, passando pelo Delphi e atualmente com Java.

Optou pela formação de Publicidade e Marketing por sua segunda empresa de tecnologia ter participado do "boom" da internet nos anos 90 e na procura de melhorar seus conhecimentos em negócios.

Em razão da principal formação e profundos conhecimentos em programação e banco de dados, é capaz de realizar o desenvolvimento de aplicativos web, desktop e mobile com maior criatividade e inovação que profissionais de desenvolvimento com uma formação única e mais especifica, dedicada somente ao desenvolvimento de softwares.

Com toda sua experiência com empresas de software, sua formação e paixão por negócios escreveu o livro "Marketing para Empresas e Profissionais de Software", publicado pela editora carioca Ciência Moderna em 2012. Além de outros livros sobre programação.

Últimos posts por Ramos de Souza Janones (exibir todos)

• Entenda o que é normalização no JavaScript - 7 de setembro de 2019
• TypeScript 3.5: Os novos recursos do TypeScript - 7 de setembro de 2019
• Resenha do livro: Como meu jogo alcançou 3 Milhões de Downloads? - 2 de setembro de 2019

Sumário

Nome do artigo

Como modelar estrutura de dados em árvore com banco de dados relacional

Descrição

MODELAGEM DE BANCO DE DADOS: Como modelar uma estrutura de dados em árvore com banco de dados relacional SGDB.

Autor

Ramos da Informática

Nome

Ramos da Informática

Logo