SQL - jak przechowywać i nawigować po hierarchiach?

Podoba mi się Zmodyfikowany algorytm Preorder Tree Traversal. Ta technika sprawia, że bardzo łatwo jest odpytywać drzewo.

Ale oto lista linków na ten temat, które skopiowałem ze strony współpracowników Zend Framework (PHP) (dodane przez: Laurent Melmoux at Jun 05, 2007 15: 52).

Wiele linków jest agnostykami językowymi:

Istnieją 2 główne reprezentacje i algorytmy do reprezentacji struktur hierarchicznych z bazami danych:

• zagnieżdżony zestaw znany również jako zmodyfikowany algorytm trawersowania drzewa preorder
• adjacency list model

Jest to dobrze wyjaśnione tutaj:

• http://www.sitepoint.com/article/hierarchical-data-database
• zarządzanie danymi hierarchicznymi w MySQL
• http://www.evolt.org/article/Four_ways_to_work_with_hierarchical_data/17/4047/index.html

Oto jeszcze kilka linków, które mam pobrano:

• http://en.wikipedia.org/wiki/Tree_%28data_structure%29
• http://en.wikipedia.org/wiki/Category:Trees_%28structure%29

Adjacency list model

• http://www.sqlteam.com/item.asp?ItemID=8866

Zagnieżdżone set

• 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 (aplet java )

Grafy

• http://www.artfulsoftware.com/mysqlbook/sampler/mysqled1ch20.html

Klasy:

Zagnieżdżone Zestawy DB Tree Adodb

• http://www.phpclasses.org/browse/package/2547.html

Model Odwiedzin ADOdb

• http://www.phpclasses.org/browse/package/2919.html

PEAR:: DB_NestedSet

• http://pear.php.net/package/DB_NestedSet
• utylizacja : https://www.entwickler.com/itr/kolumnen/psecom, id, 26, nodeid,207.html

Gruszka:: Drzewo

• http://pear.php.net/package/Tree/download/0.3.0/
• http://www.phpkitchen.com/index.php?/archives/337-PEARTree-Tutorial.html

Nstrees

• http://www.edutech.ch/contribution/nstrees/index.php

Jaki jest najlepszy sposób na reprezentowanie hierachy w bazie danych SQL? Ogólna, przenośna technika?

Załóżmy, że hierachy są w większości czytane, ale nie są całkowicie statyczne. Powiedzmy, że to drzewo genealogiczne.

Oto jak tego nie robić:

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

I wstawianie danych w ten sposób:

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

Zamiast tego podziel węzły i relacje na dwie tabele.

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

Dane są tworzone w następujący sposób:

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

Możesz teraz uruchamiać zapytania, które nie wiąże się z dołączeniem tabeli z powrotem na siebie, co się stanie, jeśli masz relacji heirachy w tym samym rzędzie co węzeł.

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

Wszyscy twoi potomkowie:

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

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

Unikasz wszystkich problemów związanych z połączeniem tabeli do siebie za pomocą zapytań podrzędnych, powszechnym ograniczeniem jest 16 zapytań podrzędnych.

Problem w tym, że utrzymanie tabeli przodków jest dość trudne-najlepiej zrobić to za pomocą procedury składowanej.

Muszę się nie zgodzić z Joshem. Co się stanie, jeśli używasz ogromnej struktury hierarchicznej, takiej jak organizacja firmy. Ludzie mogą dołączyć/opuścić firmę, zmienić linie raportowania itp... Utrzymanie "odległości" byłoby dużym problemem i trzeba byłoby zachować dwie tabele danych.

To zapytanie (SQL Server 2005 i nowsze) pozwoli Ci zobaczyć pełną linię każdej osoby i obliczy jej miejsce w hierarchii i wymaga tylko jednej tabeli informacji o użytkowniku. Można go zmodyfikować, aby znaleźć dowolny związek z dzieckiem.

--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 wprowadza nowy typ danych HierarchyID dla tego rodzaju sytuacji. Daje Ci kontrolę nad tym, gdzie w" drzewie " znajduje się twój wiersz, zarówno w poziomie, jak i w pionie.

Oracle: wybierz ... ZACZNIJ OD ... CONNECT BY

Oracle posiada rozszerzenie do SELECT, które umożliwia łatwe wyszukiwanie oparte na drzewie. Może SQL Server ma jakieś podobne rozszerzenie?

To zapytanie przemierzy tabelę, w której relacja zagnieżdżania jest przechowywana w kolumnach parent i child .

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

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

Wolę mix technik użytych przez Josha i Marka Harrisonów:

Dwie tabele, jedna z danymi osoby i druga z hierarchicznymi informacjami (person_id, parent_id [, mother_id]) jeśli PK tej tabeli jest person_id, masz proste drzewo z tylko jednym rodzicem przez węzeł (co ma sens w tym przypadku, ale nie w innych przypadkach, takich jak konta księgowe)

Ta tabela hiarchialna może być przekreślona procedurami rekurencyjnymi lub jeśli twój DB wspiera ją zdaniami takimi jak Wybierz... Przez przeora (Wyrocznia).

Inną możliwością jest, jeśli wiesz, że maksymalna głębokość danych hierarchii, którą chcesz mantain, to użycie pojedynczej tabeli z zestawem kolumn na poziom hierarchii

Mieliśmy ten sam problem, gdy zaimplementowaliśmy komponent drzewa dla [fleXive] i użyliśmy zagnieżdżonego modelu drzewa zbiorów, o którym wspomniał tharkun z MySQL docs.

Oprócz przyspieszenia rzeczy (dramatycznie) w górę użyliśmy spreaded podejście, które po prostu oznacza, że użyliśmy maksymalnej długiej wartości dla górnego poziomu prawej granicy, która pozwala nam wstawiać i przesuwać węzły bez przeliczania wszystkich wartości lewej i prawej. Wartości dla lewej i prawej są obliczane przez dzieląc zakres dla węzła przez 3 i używaj trzeciej wewnętrznej jako granic dla nowego węzła.

Przykład kodu java można zobaczyć tutaj.

Jeśli używasz SQL Server 2005 to ten link wyjaśnia, jak odzyskać dane hierarchiczne.

Common Table Expressions (CTE) mogą być twoimi przyjaciółmi, gdy poczujesz się z nich komfortowo.