SQL: come archiviare e navigare nelle gerarchie?
-
09-06-2019 - |
Domanda
Quali sono i modi che utilizzi per modellare e recuperare informazioni gerarchiche in un database?
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:
- http://www.sitepoint.com/article/hierarchical-data-database
- Gestione dei dati gerarchici in MySQL
- http://www.evolt.org/article/Four_ways_to_work_with_hierarchical_data/17/4047/index.html
Ecco alcuni altri link che ho raccolto:
- http://en.wikipedia.org/wiki/Tree_%28data_structure%29
- http://en.wikipedia.org/wiki/Category:Trees_%28structure%29
modello di lista di adiacenza
insieme nidificato
- http://www.sqlsummit.com/AdjacencyList.htm
- http://www.edutech.ch/contribution/ntrees/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 che monta il funzionamento)
Grafici
Classi :
Insiemi nidificati Albero DB Adodb
Modello di visita ADOdb
PEAR::DB_NestedSet
- http://pear.php.net/package/DB_NestedSet
- utilizzo: https://www.entwickler.com/itr/kolumnen/psecom,id,26,nodeid,207.html
Pero
- http://pear.php.net/package/Tree/download/0.3.0/
- http://www.phpkitchen.com/index.php?/archives/337-PEARTree-Tutorial.html
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;
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.