SQL – Como armazenar e navegar em hierarquias?

StackOverflow https://stackoverflow.com/questions/38801

Pergunta

Quais são as maneiras usadas para modelar e recuperar informações hierárquicas em um banco de dados?

Foi útil?

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:

Aqui estão mais alguns links que coletei:

modelo de lista de adjacências

conjunto aninhado

Gráficos

Aulas :

Conjuntos aninhados DB Tree Adodb

Modelo de Visitação ADOdb

PEAR::DB_NestedSet

PERA::Árvore

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;

http://www.adp-gmbh.ch/ora/sql/connect_by.html

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.

Licenciado em: CC-BY-SA com atribuição
Não afiliado a StackOverflow
scroll top