SQL - Wie zum speichern und navigieren Hierarchien?

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

Frage

Was sind die Möglichkeiten, die Sie verwenden, zu modellieren und rufen Sie hierarchische Informationen in einer Datenbank?

War es hilfreich?

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:

Hier sind einige weitere links, die ich gesammelt habe:

Nähe Liste Modell

geschachtelte Satz

Graphes

Klassen :

Nested Sets DB Baum Adodb

Heimsuchung-Modell ADOdb

PEAR::DB_NestedSet

PEAR::Baum

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;

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

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.

Lizenziert unter: CC-BY-SA mit Zuschreibung
Nicht verbunden mit StackOverflow
scroll top