SQL - Wie zum speichern und navigieren Hierarchien?
-
09-06-2019 - |
Frage
Was sind die Möglichkeiten, die Sie verwenden, zu modellieren und rufen Sie hierarchische Informationen in einer Datenbank?
Lösung
Die endgültige Stück zu diesem Thema haben, wurden geschrieben von Joe Celko, und er arbeitete eine Reihe von Ihnen in einem Buch mit dem Titel Joe Celko ' s Bäume und Hierarchien in SQL für Smarties.
Er begünstigt eine Technik namens gerichtete Graphen.Eine Einführung in seine Arbeit zu diesem Thema gefunden werden kann hier
Andere Tipps
Ich mag die Modified Preorder Tree Traversal-Algorithmus.Diese Technik macht es sehr einfach zu Abfrage der Baum.
Aber hier ist eine Liste mit links zum Thema, die ich kopiert aus dem Zend Framework (PHP -) Mitwirkende Webseite (geschrieben von Geschrieben von Laurent Melmoux am Jun 05, 2007 15:52).
Viele der links sind sprachneutral:
Es gibt 2 Haupt-Darstellungen und algorithmen zum darstellen von hierarchischen Strukturen mit Datenbanken :
- geschachtelte Satz auch bekannt als modified preorder tree traversal-Algorithmus
- Nähe Liste Modell
Es ist sehr gut erklärt hier:
- http://www.sitepoint.com/article/hierarchical-data-database
- Verwaltung von Hierarchischen Daten in MySQL
- http://www.evolt.org/article/Four_ways_to_work_with_hierarchical_data/17/4047/index.html
Hier sind einige weitere links, die ich gesammelt habe:
- http://en.wikipedia.org/wiki/Tree_%28data_structure%29
- http://en.wikipedia.org/wiki/Category:Trees_%28structure%29
Nähe Liste Modell
geschachtelte Satz
- 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 (java-applet montrant le fonctionnement )
Graphes
Klassen :
Nested Sets DB Baum Adodb
Heimsuchung-Modell ADOdb
PEAR::DB_NestedSet
- http://pear.php.net/package/DB_NestedSet
- Nutzung : https://www.entwickler.com/itr/kolumnen/psecom,id,26,nodeid,207.html
PEAR::Baum
- http://pear.php.net/package/Tree/download/0.3.0/
- http://www.phpkitchen.com/index.php?/archives/337-PEARTree-Tutorial.html
nstrees
Was ist der beste Weg darstellen, eine Hierarchie in einer SQL-Datenbank?Eine generische, tragbare Technik?
Nehmen wir an, die Hierarchie ist meist zu Lesen, aber es ist nicht völlig statisch.Lassen Sie uns sagen, dass es einen Stammbaum.
Hier ist, wie man es nicht machen:
create table person (
person_id integer autoincrement primary key,
name varchar(255) not null,
dob date,
mother integer,
father integer
);
Und einfügen von Daten wie diese:
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
Stattdessen teilen Sie Ihre Knoten und Ihre Beziehungen in zwei Tabellen.
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
);
Die Daten wird wie folgt erstellt:
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
Sie können jetzt beliebigen Abfragen, die nicht mit in der Tabelle auf sich selbst zurück, was passieren würde, wenn Sie die heirachy Beziehung in der gleichen Zeile wie der Knoten.
Wer hat Großeltern?
select * from person where person_id in
(select descendant_id from ancestor where distance=2);
Alle Ihre Nachkommen:
select * from person where person_id in
(select descendant_id from ancestor
where ancestor_id=1 and distance>0);
Wer sind Onkel?
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)
)
Vermeiden Sie alle Probleme, die der Beitritt zu einem Tisch, um sich über Unterabfragen, eine häufige Einschränkung ist 16 subsuqeries.
Das Problem ist, die Aufrechterhaltung der Vorfahren Tabelle ist die Art von hart - am besten mit einer gespeicherten Prozedur.
Ich bin nicht einverstanden mit Josh.Was passiert, wenn Sie mit einer riesigen hierarchische Struktur, wie ein Unternehmens-Organisation.Die Leute können beitreten/verlassen der Firma, änderung reporting lines, etc...Die Aufrechterhaltung der "Abstand" das wäre ein großes problem, und Sie müssten warten zwei Tabellen von Daten.
Diese Abfrage (SQL Server 2005 und höher) würden Sie sehen, die komplette Linie von einer person, UND berechnet deren Position in der Hierarchie, und es erfordert nur eine einzelne Tabelle von Benutzer-Informationen.Es kann geändert werden, um jede-Kind-Beziehung.
--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;
FYI:SQL Server 2008 führt eine neue HierarchyID Daten-Typ für diese Art von situation.Gibt Ihnen Kontrolle darüber, wo der "Baum" Ihrer Reihe sitzt, sowohl vertikal als auch horizontal.
Oracle:WÄHLEN Sie ...BEGINNEN SIE MIT ...VERBINDUNG
Oracle hat eine Verlängerung zu WÄHLEN, die eine einfache Baum-based retrieval.Vielleicht SQL Server hat einige ähnliche Erweiterung?
Diese Abfrage Durchlaufen eine Tabelle, wo die nesting-Verhältnis ist gespeichert in Eltern und Kind Spalten.
select * from my_table
start with parent = :TOP
connect by prior child = parent;
Ich bevorzuge eine Mischung aus techinques verwendet, die von Josh und Mark Harrison:
Zwei Tabellen, eine mit den Daten der Person und andere mit der hierarchichal info (person_id, parent_id [, mother_id]), wenn der PK der Tabelle ist person_id, haben Sie eine einfache Struktur mit nur einem Elternteil, die von Knoten (was Sinn macht, in diesem Fall, nicht aber in anderen Fällen, wie dem Rechnungswesen-Konten)
Diese hiarchy Tabelle werden können transversed by rekursive Prozeduren oder wenn Sie Ihre DB-unterstützt durch Sätze wie WÄHLEN Sie...DURCH die VORHERIGE (Oracle).
Andere Möglichkeit ist, wenn Sie wissen, die max Tiefe der Hierarchie Daten, die Sie will mantain ist, verwenden Sie eine einzelne Tabelle mit einer Reihe von Spalten pro level der Hierarchie
Wir hatten das gleiche Problem, wenn wir implementieren einen Baum Komponente für [fleXive] und verwendet den geschachtelten Satz tree-model-Ansatz erwähnt tharkun aus der MySQL docs.
Zusätzlich zu der Geschwindigkeit der Dinge (dramatisch) wir verwendet eine Verbreitung Ansatz und das bedeutet, dass wir die maximale Long-Wert für die top-level-Recht Schranken, die es uns ermöglicht, einfügen und verschieben von Knoten, ohne die Neuberechnung aller Links und rechts.Werte für Links und rechts sind berechnet durch die Aufteilung der Bereich für einen Knoten mit 3 und mit der innere Dritten, wie Grenzen für den neuen Knoten.
Ein java-Codebeispiel gesehen werden kann hier.
Wenn Sie SQL Server 2005 verwenden, dann diesen link erklärt, wie das abrufen von hierarchischen Daten.
Common Table Expressions (CTEs) können Ihre Freunde sein, sobald Sie es sich bequem, Sie zu verwenden.