SQL: come archiviare e navigare nelle gerarchie?

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

Domanda

Quali sono i modi che utilizzi per modellare e recuperare informazioni gerarchiche in un database?

È stato utile?

Soluzione

Gli articoli definitivi su questo argomento sono stati scritti da Joe Celko, che ne ha inseriti alcuni in un libro intitolato Joe Celko's Trees and Hierarchies in SQL for Smarties.

Preferisce una tecnica chiamata grafici diretti.È possibile trovare un'introduzione al suo lavoro su questo argomento Qui

Altri suggerimenti

Mi piace l'algoritmo di attraversamento dell'albero di preordine modificato.Questa tecnica rende molto semplice interrogare l'albero.

Ma ecco un elenco di collegamenti sull'argomento che ho copiato dalla pagina Web dei contributori di Zend Framework (PHP) (pubblicato lì da Inserito da Laurent Melmoux il 5 giugno 2007 15:52).

Molti dei collegamenti sono indipendenti dalla lingua:

Esistono 2 rappresentazioni e algoritmi principali per rappresentare le strutture gerarchiche con i database:

  • insieme nidificato noto anche come algoritmo di attraversamento dell'albero di preordine modificato
  • modello di lista di adiacenza

E' spiegato bene qui:

Ecco alcuni altri link che ho raccolto:

modello di lista di adiacenza

insieme nidificato

Grafici

Classi :

Insiemi nidificati Albero DB Adodb

Modello di visita ADOdb

PEAR::DB_NestedSet

Pero

nstrees

Qual è il modo migliore per rappresentare una gerarchia in un database SQL?Una tecnica generica e portatile?

Supponiamo che la gerarchia sia per lo più letta, ma non completamente statica.Diciamo che è un albero genealogico.

Ecco come non farlo:

create table person (
person_id integer autoincrement primary key,
name      varchar(255) not null,
dob       date,
mother    integer,
father    integer
);

E inserendo i dati in questo modo: 

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

Invece, dividi i tuoi nodi e le tue relazioni in due tabelle.

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
);

I dati vengono creati in questo modo:

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

ora puoi eseguire query arbitrarie che non implicano il ricongiungimento della tabella su se stessa, cosa che accadrebbe se avessi la relazione ereditaria nella stessa riga del nodo.

Chi ha i nonni?

select * from person where person_id in 
    (select descendant_id from ancestor where distance=2);

Tutti i tuoi discendenti:

select * from person where person_id in 
    (select descendant_id from ancestor 
    where ancestor_id=1 and distance>0);

Chi sono gli zii? 

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)
    )

Eviti tutti i problemi legati all'unione di una tabella a se stessa tramite sottoquery, una limitazione comune è di 16 sottoquery.

Il problema è che mantenere la tabella degli antenati è piuttosto difficile, è meglio farlo con una procedura memorizzata.

Non sono d'accordo con Josh.Cosa succede se utilizzi un'enorme struttura gerarchica come un'organizzazione aziendale.Le persone possono entrare/lasciare l'azienda, cambiare le linee di riporto, ecc...Mantenere la "distanza" sarebbe un grosso problema e dovresti mantenere due tabelle di dati.

Questa query (SQL Server 2005 e versioni successive) ti consentirà di vedere la riga completa di qualsiasi persona E di calcolare la sua posizione nella gerarchia e richiede solo una singola tabella di informazioni sull'utente.Può essere modificato per trovare qualsiasi relazione figlio.

--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;

PER TUA INFORMAZIONE:SQL Server 2008 introduce una nuova ID gerarchia tipo di dati per questo tipo di situazione.Ti dà il controllo su dove si trova la tua fila nell'"albero", sia orizzontalmente che verticalmente.

Oracolo:SELEZIONARE ...INIZIARE CON ...CONNETTITI DA

Oracle ha un'estensione a SELECT che consente un facile recupero basato su albero.Forse SQL Server ha un'estensione simile?

Questa query attraverserà una tabella in cui è archiviata la relazione di nidificazione genitore E bambino colonne.

select * from my_table
    start with parent = :TOP
    connect by prior child = parent;

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

Preferisco un mix delle tecniche usate da Josh e Mark Harrison:

Due tabelle, una con i dati della Persona e l'altra con le informazioni gerarchiche (person_id, parent_id [, mother_id]) se il PK di questa tabella è person_id, hai un albero semplice con un solo genitore per nodo (che ha senso in questo caso, ma non in altri casi come la contabilità)

Questa tabella gerarchica può essere attraversata da procedure ricorsive o se il tuo DB la supporta da frasi come SELECT...DA PRIOR (Oracolo).

Un'altra possibilità è che se conosci la profondità massima dei dati della gerarchia che vuoi mantenere è utilizzare una singola tabella con un set di colonne per livello di gerarchia

Abbiamo riscontrato lo stesso problema quando abbiamo implementato un componente ad albero per [fleXive] e ha utilizzato l'approccio del modello ad albero di insiemi nidificati menzionato da Tharkun da MySQL documenti.

Oltre a velocizzare le cose (drasticamente) abbiamo usato a diffuso approccio che significa semplicemente che abbiamo utilizzato il valore Long massimo per i limiti destri di livello superiore che ci consente di inserire e spostare i nodi senza ricalcolare tutti i valori sinistro e destro.I valori per sinistra e destra vengono calcolati dividendo l'intervallo di un nodo per 3 e utilizzando il interno terzo come limiti per il nuovo nodo.

È possibile vedere un esempio di codice Java Qui.

Se stai utilizzando SQL Server 2005 allora questo link spiega come recuperare i dati gerarchici.

Le espressioni di tabella comuni (CTE) possono diventare tue amiche una volta che ti senti a tuo agio nell'usarle.

Autorizzato sotto: CC-BY-SA insieme a attribuzione
Non affiliato a StackOverflow
scroll top