SQL – Como armazenar e navegar em hierarquias?
-
09-06-2019 - |
Pergunta
Quais são as maneiras usadas para modelar e recuperar informações hierárquicas em um banco de dados?
Solução
Os artigos definitivos sobre esse assunto foram escritos por Joe Celko, e ele trabalhou vários deles em um livro chamado Joe Celko's Trees and Hierarchies in SQL for Smarties.
Ele prefere uma técnica chamada gráficos direcionados.Uma introdução ao seu trabalho sobre este assunto pode ser encontrada aqui
Outras dicas
Gosto do algoritmo de passagem de árvore de pré-encomenda modificado.Essa técnica facilita muito a consulta da árvore.
Mas aqui está uma lista de links sobre o tópico que copiei da página de contribuidores do Zend Framework (PHP) (postada lá por Postado por Laurent Melmoux em 05 de junho de 2007 às 15:52).
Muitos dos links são independentes de idioma:
Existem 2 representações e algoritmos principais para representar estruturas hierárquicas com bancos de dados:
- conjunto aninhado também conhecido como algoritmo de passagem de árvore de pré-ordem modificado
- modelo de lista de adjacências
Está bem explicado aqui:
- http://www.sitepoint.com/article/hierarchical-data-database
- Gerenciando dados hierárquicos no MySQL
- http://www.evolt.org/article/Four_ways_to_work_with_hierarchical_data/17/4047/index.html
Aqui estão mais alguns links que coletei:
- http://en.wikipedia.org/wiki/Tree_%28data_structure%29
- http://en.wikipedia.org/wiki/Category:Trees_%28structure%29
modelo de lista de adjacências
conjunto aninhado
- http://www.sqlsummit.com/AdjacencyList.htm
- http://www.edutech.ch/contribution/nstrees/index.php
- http://www.phpriot.com/d/articles/php/application-design/nested-trees-1/
- http://www.dbmsmag.com/9604d06.html
- http://en.wikipedia.org/wiki/Tree_traversal
- http://www.cosc.canterbury.ac.nz/mukundan/dsal/BTree.html (applet java que monta o funcionamento)
Gráficos
Aulas :
Conjuntos aninhados DB Tree Adodb
Modelo de Visitação ADOdb
PEAR::DB_NestedSet
- http://pear.php.net/package/DB_NestedSet
- utilização: https://www.entwickler.com/itr/kolumnen/psecom,id,26,nodeid,207.html
PERA::Árvore
- http://pear.php.net/package/Tree/download/0.3.0/
- http://www.phpkitchen.com/index.php?/archives/337-PEARTree-Tutorial.html
nstrees
Qual é a melhor maneira de representar uma hierarquia em um banco de dados SQL?Uma técnica genérica e portátil?
Vamos supor que a hierarquia seja principalmente lida, mas não completamente estática.Digamos que seja uma árvore genealógica.
Veja como não fazer isso:
create table person (
person_id integer autoincrement primary key,
name varchar(255) not null,
dob date,
mother integer,
father integer
);
E inserindo dados como este:
person_id name dob mother father
1 Pops 1900/1/1 null null
2 Grandma 1903/2/4 null null
3 Dad 1925/4/2 2 1
4 Uncle Kev 1927/3/3 2 1
5 Cuz Dave 1953/7/8 null 4
6 Billy 1954/8/1 null 3
Em vez disso, divida seus nós e relacionamentos em duas tabelas.
create table person (
person_id integer autoincrement primary key,
name varchar(255) not null,
dob date
);
create table ancestor (
ancestor_id integer,
descendant_id integer,
distance integer
);
Os dados são criados assim:
person_id name dob
1 Pops 1900/1/1
2 Grandma 1903/2/4
3 Dad 1925/4/2
4 Uncle Kev 1927/3/3
5 Cuz Dave 1953/7/8
6 Billy 1954/8/1
ancestor_id descendant_id distance
1 1 0
2 2 0
3 3 0
4 4 0
5 5 0
6 6 0
1 3 1
2 3 1
1 4 1
2 4 1
1 5 2
2 5 2
4 5 1
1 6 2
2 6 2
3 6 1
agora você pode executar consultas arbitrárias que não envolvem juntar a tabela novamente, o que aconteceria se você tivesse o relacionamento de hierarquia na mesma linha do nó.
Quem tem avós?
select * from person where person_id in
(select descendant_id from ancestor where distance=2);
Todos os seus descendentes:
select * from person where person_id in
(select descendant_id from ancestor
where ancestor_id=1 and distance>0);
Quem são os tios?
select decendant_id uncle from ancestor
where distance=1 and ancestor_id in
(select ancestor_id from ancestor
where distance=2 and not exists
(select ancestor_id from ancestor
where distance=1 and ancestor_id=uncle)
)
Você evita todos os problemas de unir uma tabela a si mesma por meio de subconsultas, uma limitação comum são 16 subsuqeries.
O problema é que manter a tabela ancestral é meio difícil - melhor feito com um procedimento armazenado.
Tenho que discordar de Josh.O que acontece se você estiver usando uma estrutura hierárquica enorme, como a organização de uma empresa.As pessoas podem ingressar/sair da empresa, alterar linhas hierárquicas, etc...Manter a “distância” seria um grande problema e você teria que manter duas tabelas de dados.
Esta consulta (SQL Server 2005 e superior) permite ver a linha completa de qualquer pessoa E calcula sua posição na hierarquia e requer apenas uma única tabela de informações do usuário.Ele pode ser modificado para encontrar qualquer relacionamento filho.
--Create table of dummy data
create table #person (
personID integer IDENTITY(1,1) NOT NULL,
name varchar(255) not null,
dob date,
father integer
);
INSERT INTO #person(name,dob,father)Values('Pops','1900/1/1',NULL);
INSERT INTO #person(name,dob,father)Values('Grandma','1903/2/4',null);
INSERT INTO #person(name,dob,father)Values('Dad','1925/4/2',1);
INSERT INTO #person(name,dob,father)Values('Uncle Kev','1927/3/3',1);
INSERT INTO #person(name,dob,father)Values('Cuz Dave','1953/7/8',4);
INSERT INTO #person(name,dob,father)Values('Billy','1954/8/1',3);
DECLARE @OldestPerson INT;
SET @OldestPerson = 1; -- Set this value to the ID of the oldest person in the family
WITH PersonHierarchy (personID,Name,dob,father, HierarchyLevel) AS
(
SELECT
personID
,Name
,dob
,father,
1 as HierarchyLevel
FROM #person
WHERE personID = @OldestPerson
UNION ALL
SELECT
e.personID,
e.Name,
e.dob,
e.father,
eh.HierarchyLevel + 1 AS HierarchyLevel
FROM #person e
INNER JOIN PersonHierarchy eh ON
e.father = eh.personID
)
SELECT *
FROM PersonHierarchy
ORDER BY HierarchyLevel, father;
DROP TABLE #person;
PARA SUA INFORMAÇÃO:O SQL Server 2008 apresenta um novo ID da hierarquia tipo de dados para esse tipo de situação.Dá a você controle sobre onde sua linha fica na "árvore", tanto horizontal quanto verticalmente.
Oráculo:SELECIONE...COMEÇAR COM ...CONECTAR POR
A Oracle possui uma extensão para SELECT que permite fácil recuperação baseada em árvore.Talvez o SQL Server tenha alguma extensão semelhante?
Esta consulta percorrerá uma tabela onde o relacionamento de aninhamento está armazenado em pai e criança colunas.
select * from my_table
start with parent = :TOP
connect by prior child = parent;
Prefiro uma mistura das técnicas usadas por Josh e Mark Harrison:
Duas tabelas, uma com os dados da Pessoa e outra com as informações hierárquicas (person_id, parent_id [, mother_id]) se o PK desta tabela for person_id, você tem uma árvore simples com apenas um pai por nó (o que faz sentido em neste caso, mas não em outros casos, como contas contábeis)
Esta tabela de hierarquia pode ser atravessada por procedimentos recursivos ou se seu banco de dados suportar por sentenças como SELECT...POR PRIOR (Oráculo).
Outra possibilidade é se você souber a profundidade máxima dos dados da hierarquia que deseja manter, usar uma única tabela com um conjunto de colunas por nível de hierarquia
Tivemos o mesmo problema quando implementamos um componente de árvore para [fleXive] e usou a abordagem do modelo de árvore de conjunto aninhado mencionada por Tharkun no MySQL documentos.
Além de acelerar (dramaticamente) as coisas, usamos um espalhado abordagem que significa simplesmente que usamos o valor Long máximo para os limites direitos de nível superior, o que nos permite inserir e mover nós sem recalcular todos os valores esquerdo e direito.Os valores para esquerda e direita são calculados dividindo o intervalo de um nó por 3 e usando o interno terceiro como limites para o novo nó.
Um exemplo de código java pode ser visto aqui.
Se você estiver usando o SQL Server 2005, então esse link explica como recuperar dados hierárquicos.
Expressões de tabela comuns (CTEs) podem ser suas amigas assim que você se sentir confortável em usá-las.