Modelagem de banco de dados: estrutura de dados em árvore relacional
3 de junho de 2019
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.
Leia também:
SEO – Google lança nova atualização em 2019 de seu algoritmo
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:
CURSOS QUE ESTAMOS RECOMENDANDO:
- Plano de Assinatura Danki.Code: Diversos cursos completos e atualizados para se tornar um Dev FullStack.
- Mercado em Alta de Desenvolvedor Node.JS e React, recomendamos este treinamento.
LIVROS QUE INDICAMOS
- Livros para análistas e cientistas de dados que recomendamos
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 emarvoresprofundas, 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
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
Leia também:
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:
- 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 WITHeCONNECT BY) que podem simplificar a tarefa, mas não são portáveis, o que foge do escopo da pergunta. - 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 comids 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) - 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 talvezprofundidade). 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… - 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.
E para terminar
VOCÊ ESTÁ NA SEÇÃO: Banco de Dados
