Jakie są opcje przechowywania danych hierarchicznych w relacyjnej bazie danych? [Zamknięte]

1333

Dobry przegląd

Mówiąc ogólnie, podejmujesz decyzję pomiędzy szybkim czasem odczytu (na przykład zestawem zagnieżdżonym) lub szybkim czasem zapisu (lista sąsiadów). Zwykle kończy się kombinacją poniższych opcji, które najlepiej pasują do twoich potrzeb. Poniżej przedstawiono dogłębną lekturę:

Opcje

Te, które znam i ogólne cechy:

  1. Lista adiakencji :
    • Kolumny: ID, ParentID
    • Łatwy do wdrożenia.
    • Tanie przesuwanie, wstawianie i usuwanie węzłów.
    • Drogie, aby znaleźć poziom, pochodzenie i potomkowie, ścieżkę
    • Unikaj N + 1 poprzez wspólne wyrażenia tabel w bazach danych, które je obsługują
  2. Zestaw zagnieżdżony (znany również jako zmodyfikowane przemierzanie drzewa w przedsprzedaży )
    • Kolumny: lewy, prawy
    • Tanie pochodzenie, potomkowie
    • Bardzo drogie O(n/2)ruchy, wstawianie, usuwanie z powodu niestabilnego kodowania
  3. Stolik pomostowy (inaczej zwany stołem zamknięcia / wyzwalaczami )
    • Używa oddzielnej tabeli łączenia z: przodkiem, potomkiem, głębokością (opcjonalnie)
    • Tanie pochodzenie i potomkowie
    • Zapisuje koszty O(log n)(wielkość poddrzewa) dla wstawiania, aktualizacji, usuwania
    • Znormalizowane kodowanie: dobre dla statystyk RDBMS i planowania zapytań w złączeniach
    • Wymaga wielu wierszy na węzeł
  4. Kolumna linii (aka zmaterializowana ścieżka , wyliczenie ścieżki)
    • Kolumna: rodowód (np. / Rodzic / dziecko / wnuk / etc ...)
    • Tanie potomkowie poprzez zapytanie o prefiks (np. LEFT(lineage, #) = '/enumerated/path')
    • Zapisuje koszty O(log n)(wielkość poddrzewa) dla wstawiania, aktualizacji, usuwania
    • Nierelacyjny: opiera się na typie danych macierzy lub formacie ciągu szeregowego
  5. Zagnieżdżone interwały
    • Jak zestaw zagnieżdżony, ale z rzeczywistym / zmiennoprzecinkowym / dziesiętnym, dzięki czemu kodowanie nie jest ulotne (niedrogi ruch / wstaw / usuń)
    • Ma problemy z rzeczywistą / zmienną / dziesiętną reprezentacją / precyzją
    • Wariant kodowania matrycowego dodaje kodowanie przodka (zmaterializowaną ścieżkę) dla „wolnego”, ale z dodatkową trudnością algebry liniowej.
  6. Płaski stół
    • Zmodyfikowana lista Adjacency, która dodaje kolumnę Poziom i Pozycja (np. Kolejność) do każdego rekordu.
    • Tanie iteracja / paginacja
    • Drogie przenoszenie i usuwanie
    • Dobre wykorzystanie: dyskusja w wątkach - komentarze na forach / blogach
  7. Wiele kolumn linii
    • Kolumny: jedna dla każdego poziomu linii, odnosi się do wszystkich rodziców aż do katalogu głównego, poziomy w dół od poziomu elementu są ustawione na NULL
    • Tanie przodkowie, potomkowie, poziom
    • Tanie wstawianie, usuwanie, przenoszenie liści
    • Drogie wstawianie, usuwanie, przenoszenie wewnętrznych węzłów
    • Twardy limit głębokości hierarchii

Uwagi dotyczące bazy danych

MySQL

Wyrocznia

PostgreSQL

SQL Server

  • Ogólne podsumowanie
  • Oferty z 2008 r. Typ danych HierarchyId wydaje się pomagać w podejściu do kolumny linii i zwiększać głębokość, którą można przedstawić.
orangepips
źródło
5
Według slideshare.net/billkarwin/sql-antipatterns-strike-back stronie 77, Closure Tablessą lepsze Adjacency List, Path Enumerationa Nested Setspod względem łatwości użycia (i zgaduję wydajności, jak również).
Gili
Brakuje mi tutaj bardzo prostej wersji: zwykłej BLOBY. Jeśli w Twojej hierarchii jest tylko kilkadziesiąt pozycji, najlepszym wyborem może być serializowane drzewo identyfikatorów.
Lothar,
@Lothar: question to wiki społeczności, więc możesz je mieć. Myślę w tym względzie, że zrobiłbym to tylko z tymi bazami danych, które obsługują pewnego rodzaju struktury obiektów blob, takie jak XML ze stabilnym językiem zapytań, takim jak XPATH. W przeciwnym razie nie widzę dobrego sposobu odpytywania oprócz pobierania, deserializacji i munge w kodzie, a nie SQL. A jeśli naprawdę masz problem, w którym potrzebujesz wielu dowolnych elementów, lepiej byłoby użyć bazy danych Node, takiej jak Neo4J, z której korzystałem i którą lubiłem, ale nigdy nie przeszedłem do produkcji.
orangepips
2
Ten link MSDN do „Podsumowania ogólnego” nie wyświetla już artykułu. Było to w wydaniu MSDN Magazine z września 2008 r., Które można pobrać jako plik CHM lub zobaczyć w archiwum internetowym pod adresem: web.archive.org/web/20080913041559/http://msdn.microsoft.com:80/ …
kͩeͣmͮpͥ ͩ

Odpowiedzi:

66

Moją ulubioną odpowiedzią jest to, co sugeruje pierwsze zdanie w tym wątku. Użyj listy Adjacency, aby utrzymać hierarchię, a za pomocą zestawów zagnieżdżonych zapytaj hierarchię.

Do tej pory problem polegał na tym, że metoda krycia z listy Adjacecy do zestawów zagnieżdżonych była strasznie powolna, ponieważ większość osób korzysta z ekstremalnej metody RBAR znanej jako „Push Stack” do konwersji i uważana jest za zbyt kosztowną aby osiągnąć nirwanę prostoty konserwacji dzięki liście Adjacency i niesamowitej wydajności zestawów zagnieżdżonych. W rezultacie większość ludzi ostatecznie musi zadowolić się jednym lub drugim, szczególnie jeśli jest ich więcej niż, powiedzmy, kiepskie 100 000 węzłów. Korzystanie z metody wypychania stosu może zająć cały dzień, aby wykonać konwersję według tego, co MLM uważają za hierarchię milionów węzłów.

Pomyślałem, że dałbym Celko trochę konkurencji, wymyślając metodę konwersji Listy Adjacencji na zestawy zagnieżdżone z prędkościami, które po prostu wydają się niemożliwe. Oto wydajność metody wypychania stosu na moim laptopie i5.

Duration for     1,000 Nodes = 00:00:00:870 
Duration for    10,000 Nodes = 00:01:01:783 (70 times slower instead of just 10)
Duration for   100,000 Nodes = 00:49:59:730 (3,446 times slower instead of just 100) 
Duration for 1,000,000 Nodes = 'Didn't even try this'

Oto czas trwania nowej metody (z metodą wypychania stosu w nawiasach).

Duration for     1,000 Nodes = 00:00:00:053 (compared to 00:00:00:870)
Duration for    10,000 Nodes = 00:00:00:323 (compared to 00:01:01:783)
Duration for   100,000 Nodes = 00:00:03:867 (compared to 00:49:59:730)
Duration for 1,000,000 Nodes = 00:00:54:283 (compared to something like 2 days!!!)

Tak, to jest poprawne. 1 milion węzłów przekonwertowanych w mniej niż minutę i 100 000 węzłów w mniej niż 4 sekundy.

Możesz przeczytać o nowej metodzie i uzyskać kopię kodu pod następującym adresem URL. http://www.sqlservercentral.com/articles/Hierarchy/94040/

Opracowałem również „wstępnie zagregowaną” hierarchię przy użyciu podobnych metod. MLM i osoby sporządzające zestawienia materiałowe będą szczególnie zainteresowane tym artykułem. http://www.sqlservercentral.com/articles/T-SQL/94570/

Jeśli zajrzysz do jednego z artykułów, przejdź do linku „Dołącz do dyskusji” i daj mi znać, co myślisz.

Jeff Moden
źródło
Co to jest MLMer?
David Mann,
MLM = „Marketing wielopoziomowy”. Amway, Shaklee, ACN itp. Itp.
Jeff Moden
31

To jest bardzo częściowa odpowiedź na twoje pytanie, ale mam nadzieję, że nadal będzie przydatna.

Microsoft SQL Server 2008 implementuje dwie funkcje, które są niezwykle przydatne do zarządzania danymi hierarchicznymi:

  • hierarchyid typ danych.
  • typowe wyrażenia tabelowe przy użyciu słowa kluczowego with .

Na początek spójrz na „Modeluj swoje hierarchie danych za pomocą SQL Server 2008” autorstwa Kent Tegels na MSDN. Zobacz także moje własne pytanie: zapytanie rekursywne w tej samej tabeli w SQL Server 2008

CesarGon
źródło
2
Ciekawe, HierarchyId, nie wiedział o tym: msdn.microsoft.com/en-us/library/bb677290.aspx
orangepips
1
W rzeczy samej. Pracuję z wieloma rekurencyjnie hierarchicznymi danymi i uważam, że wspólne wyrażenia tabelowe są niezwykle przydatne. Zobacz msdn.microsoft.com/en-us/library/ms186243.aspx za intro.
CesarGon
28

Ten projekt nie został jeszcze wspomniany:

Wiele kolumn linii

Chociaż ma ograniczenia, jeśli możesz je znieść, jest bardzo prosty i bardzo wydajny. Funkcje:

  • Kolumny: jedna dla każdego poziomu linii, odnosi się do wszystkich rodziców aż do katalogu głównego, poziomy poniżej poziomu bieżących elementów są ustawione na 0 (lub NULL)
  • Istnieje stała granica głębokości hierarchii
  • Tanie przodkowie, potomkowie, poziom
  • Tanie wstawianie, usuwanie, przenoszenie liści
  • Drogie wstawianie, usuwanie, przenoszenie wewnętrznych węzłów

Oto przykład - taksonomiczne drzewo ptaków, więc hierarchia to Klasa / Porządek / Rodzina / Rodzaj / Gatunek - gatunek jest najniższym poziomem, 1 wiersz = 1 takson (co odpowiada gatunkowi w przypadku węzłów liści):

CREATE TABLE `taxons` (
  `TaxonId` smallint(6) NOT NULL default '0',
  `ClassId` smallint(6) default NULL,
  `OrderId` smallint(6) default NULL,
  `FamilyId` smallint(6) default NULL,
  `GenusId` smallint(6) default NULL,
  `Name` varchar(150) NOT NULL default ''
);

i przykład danych:

+---------+---------+---------+----------+---------+-------------------------------+
| TaxonId | ClassId | OrderId | FamilyId | GenusId | Name                          |
+---------+---------+---------+----------+---------+-------------------------------+
|     254 |       0 |       0 |        0 |       0 | Aves                          |
|     255 |     254 |       0 |        0 |       0 | Gaviiformes                   |
|     256 |     254 |     255 |        0 |       0 | Gaviidae                      |
|     257 |     254 |     255 |      256 |       0 | Gavia                         |
|     258 |     254 |     255 |      256 |     257 | Gavia stellata                |
|     259 |     254 |     255 |      256 |     257 | Gavia arctica                 |
|     260 |     254 |     255 |      256 |     257 | Gavia immer                   |
|     261 |     254 |     255 |      256 |     257 | Gavia adamsii                 |
|     262 |     254 |       0 |        0 |       0 | Podicipediformes              |
|     263 |     254 |     262 |        0 |       0 | Podicipedidae                 |
|     264 |     254 |     262 |      263 |       0 | Tachybaptus                   |

Jest to świetne, ponieważ w ten sposób wykonujesz wszystkie potrzebne operacje w bardzo łatwy sposób, o ile kategorie wewnętrzne nie zmieniają swojego poziomu w drzewie.

TMS
źródło
22

Model adiacyencji + model zestawów zagnieżdżonych

Poszedłem za tym, ponieważ mogłem łatwo wstawiać nowe elementy do drzewa (wystarczy identyfikator gałęzi, aby wstawić do niego nowy element), a także dość szybko odpytywać.

+-------------+----------------------+--------+-----+-----+
| category_id | name                 | parent | lft | rgt |
+-------------+----------------------+--------+-----+-----+
|           1 | ELECTRONICS          |   NULL |   1 |  20 |
|           2 | TELEVISIONS          |      1 |   2 |   9 |
|           3 | TUBE                 |      2 |   3 |   4 |
|           4 | LCD                  |      2 |   5 |   6 |
|           5 | PLASMA               |      2 |   7 |   8 |
|           6 | PORTABLE ELECTRONICS |      1 |  10 |  19 |
|           7 | MP3 PLAYERS          |      6 |  11 |  14 |
|           8 | FLASH                |      7 |  12 |  13 |
|           9 | CD PLAYERS           |      6 |  15 |  16 |
|          10 | 2 WAY RADIOS         |      6 |  17 |  18 |
+-------------+----------------------+--------+-----+-----+
  • Za każdym razem, gdy potrzebujesz wszystkich dzieci dowolnego rodzica, po prostu przeszukaj parentkolumnę.
  • Jeśli potrzebujesz wszystkich potomków któregoś z rodziców, zapytaj o przedmioty, które mają lftmiędzy nimi lfta rgtrodzicem.
  • Jeśli potrzebujesz wszystkich rodziców dowolnego węzła aż do korzenia drzewa, wyszukujesz elementy o wartości lftniższej niż węzeł lfti rgtwiększej niż węzeł rgti sortujesz według parent.

Musiałem sprawić, aby dostęp do drzewa i zapytania do niego były szybsze niż wstawki, dlatego właśnie to wybrałem

Jedynym problemem jest naprawa kolumn lefti rightpodczas wstawiania nowych elementów. Cóż, stworzyłem dla niego procedurę składowaną i wywoływałem ją za każdym razem, gdy wstawiałem nowy element, co w moim przypadku było rzadkie, ale jest naprawdę szybkie. Pomysł zaczerpnąłem z książki Joe Celko, a procedura składowana i sposób, w jaki ją wymyśliłem, wyjaśniono tutaj w DBA SE https://dba.stackexchange.com/q/89051/41481

azerafati
źródło
3
+1 to jest uzasadnione podejście. Z własnego doświadczenia wynika, że ​​klucz decyduje, czy nie masz nic przeciwko nieczytelnym odczytom, gdy występują duże operacje aktualizacji. Jeśli nie, staje się to problemem lub uniemożliwia ludziom bezpośrednie wyszukiwanie w tabelach i zawsze przechodzenie przez interfejs API - sproki / funkcje DB lub kod.
orangepips
1
To ciekawe rozwiązanie; nie jestem jednak pewien, czy zapytanie kolumny nadrzędnej naprawdę oferuje jakąkolwiek znaczącą przewagę przy poszukiwaniu dzieci - dlatego właśnie mamy kolumny lewą i prawą.
Thomas
2
@Thomas, istnieje różnica między childreni descendants. lefti rightsłużą do znajdowania potomków.
Azerafati,
14

Jeśli baza danych obsługuje tablice, możesz także zaimplementować kolumnę linii lub zmaterializowaną ścieżkę jako tablicę identyfikatorów nadrzędnych.

W szczególności za pomocą Postgresa można następnie użyć operatorów zestawów do przeszukiwania hierarchii i uzyskania doskonałej wydajności dzięki indeksom GIN. To sprawia, że ​​znalezienie rodziców, dzieci i głębokości jest bardzo proste w jednym zapytaniu. Aktualizacje są również łatwe do zarządzania.

Mam pełny opis używania tablic dla zmaterializowanych ścieżek, jeśli jesteście ciekawi.

Adam Sanderson
źródło
9

To jest naprawdę kwadratowy kołek, pytanie z okrągłymi otworami.

Jeśli relacyjne bazy danych i SQL są jedynymi młotami, które masz lub chcesz użyć, to odpowiedzi, które zostały opublikowane do tej pory, są odpowiednie. Dlaczego jednak nie skorzystać z narzędzia zaprojektowanego do obsługi danych hierarchicznych? Baza danych wykresów jest idealna dla złożonych danych hierarchicznych.

Nieefektywność modelu relacyjnego wraz ze złożonością dowolnego rozwiązania kodu / zapytania w celu odwzorowania modelu graficznego / hierarchicznego na model relacyjny nie jest po prostu warta wysiłku w porównaniu z łatwością, z jaką rozwiązanie bazy danych wykresów może rozwiązać ten sam problem.

Rozważ listę materiałów jako wspólną hierarchiczną strukturę danych.

class Component extends Vertex {
    long assetId;
    long partNumber;
    long material;
    long amount;
};

class PartOf extends Edge {
};

class AdjacentTo extends Edge {
};

Najkrótsza ścieżka między dwoma podzespołami : Prosty algorytm przechodzenia przez wykres. Dopuszczalne ścieżki można zakwalifikować na podstawie kryteriów.

Podobieństwo : Jaki jest stopień podobieństwa między dwoma zespołami? Wykonaj przemieszczenie obu pod-drzew, obliczając przecięcie i połączenie dwóch pod-drzew. Procent podobny to przecięcie podzielone przez związek.

Przejściowe zamknięcie : przejdź się do sub-drzewa i zsumuj interesujące pola, np. „Ile aluminium jest w podzespole?”

Tak, możesz rozwiązać problem za pomocą SQL i relacyjnej bazy danych. Istnieją jednak znacznie lepsze podejścia, jeśli chcesz użyć odpowiedniego narzędzia do pracy.

djhallx
źródło
5
Ta odpowiedź byłaby o wiele bardziej przydatna, gdyby przypadki użycia pokazały lub lepiej kontrastowały, jak na przykład zapytać bazę danych wykresów za pomocą SPARQL zamiast SQL w RDBMS.
orangepips
1
SPARQL dotyczy baz danych RDF, które są podklasą większej domeny baz grafowych. Pracuję z InfiniteGraph, który nie jest bazą danych RDF i obecnie nie obsługuje SPARQL. InfiniteGraph obsługuje kilka różnych mechanizmów zapytań: (1) interfejs API do nawigacji po wykresach do konfigurowania widoków, filtrów, kwalifikatorów ścieżek i procedur obsługi wyników, (2) złożony język dopasowywania wzorców ścieżek wykresów oraz (3) Gremlin.
djhallx
6

Używam PostgreSQL z tabelami zamknięcia dla moich hierarchii. Mam jedną uniwersalną procedurę składowaną dla całej bazy danych:

CREATE FUNCTION nomen_tree() RETURNS trigger
    LANGUAGE plpgsql
    AS $_$
DECLARE
  old_parent INTEGER;
  new_parent INTEGER;
  id_nom INTEGER;
  txt_name TEXT;
BEGIN
-- TG_ARGV[0] = name of table with entities with PARENT-CHILD relationships (TBL_ORIG)
-- TG_ARGV[1] = name of helper table with ANCESTOR, CHILD, DEPTH information (TBL_TREE)
-- TG_ARGV[2] = name of the field in TBL_ORIG which is used for the PARENT-CHILD relationship (FLD_PARENT)
    IF TG_OP = 'INSERT' THEN
    EXECUTE 'INSERT INTO ' || TG_ARGV[1] || ' (child_id,ancestor_id,depth) 
        SELECT $1.id,$1.id,0 UNION ALL
      SELECT $1.id,ancestor_id,depth+1 FROM ' || TG_ARGV[1] || ' WHERE child_id=$1.' || TG_ARGV[2] USING NEW;
    ELSE                                                           
    -- EXECUTE does not support conditional statements inside
    EXECUTE 'SELECT $1.' || TG_ARGV[2] || ',$2.' || TG_ARGV[2] INTO old_parent,new_parent USING OLD,NEW;
    IF COALESCE(old_parent,0) <> COALESCE(new_parent,0) THEN
      EXECUTE '
      -- prevent cycles in the tree
      UPDATE ' || TG_ARGV[0] || ' SET ' || TG_ARGV[2] || ' = $1.' || TG_ARGV[2]
        || ' WHERE id=$2.' || TG_ARGV[2] || ' AND EXISTS(SELECT 1 FROM '
        || TG_ARGV[1] || ' WHERE child_id=$2.' || TG_ARGV[2] || ' AND ancestor_id=$2.id);
      -- first remove edges between all old parents of node and its descendants
      DELETE FROM ' || TG_ARGV[1] || ' WHERE child_id IN
        (SELECT child_id FROM ' || TG_ARGV[1] || ' WHERE ancestor_id = $1.id)
        AND ancestor_id IN
        (SELECT ancestor_id FROM ' || TG_ARGV[1] || ' WHERE child_id = $1.id AND ancestor_id <> $1.id);
      -- then add edges for all new parents ...
      INSERT INTO ' || TG_ARGV[1] || ' (child_id,ancestor_id,depth) 
        SELECT child_id,ancestor_id,d_c+d_a FROM
        (SELECT child_id,depth AS d_c FROM ' || TG_ARGV[1] || ' WHERE ancestor_id=$2.id) AS child
        CROSS JOIN
        (SELECT ancestor_id,depth+1 AS d_a FROM ' || TG_ARGV[1] || ' WHERE child_id=$2.' 
        || TG_ARGV[2] || ') AS parent;' USING OLD, NEW;
    END IF;
  END IF;
  RETURN NULL;
END;
$_$;

Następnie dla każdej tabeli, w której mam hierarchię, tworzę wyzwalacz

CREATE TRIGGER nomenclature_tree_tr AFTER INSERT OR UPDATE ON nomenclature FOR EACH ROW EXECUTE PROCEDURE nomen_tree('my_db.nomenclature', 'my_db.nom_helper', 'parent_id');

Do zapełniania tabeli zamknięcia z istniejącej hierarchii używam tej procedury składowanej:

CREATE FUNCTION rebuild_tree(tbl_base text, tbl_closure text, fld_parent text) RETURNS void
    LANGUAGE plpgsql
    AS $$
BEGIN
    EXECUTE 'TRUNCATE ' || tbl_closure || ';
    INSERT INTO ' || tbl_closure || ' (child_id,ancestor_id,depth) 
        WITH RECURSIVE tree AS
      (
        SELECT id AS child_id,id AS ancestor_id,0 AS depth FROM ' || tbl_base || '
        UNION ALL 
        SELECT t.id,ancestor_id,depth+1 FROM ' || tbl_base || ' AS t
        JOIN tree ON child_id = ' || fld_parent || '
      )
      SELECT * FROM tree;';
END;
$$;

Tabele zamknięcia są zdefiniowane za pomocą 3 kolumn - ANCESTOR_ID, DESCENDANT_ID, DEPTH. Możliwe jest (a nawet doradzam) przechowywanie rekordów o tej samej wartości dla ANCESTOR i DESCENDANT oraz o wartości zero dla DEPTH. Uprości to zapytania dotyczące pobierania hierarchii. I są naprawdę bardzo proste:

-- get all descendants
SELECT tbl_orig.*,depth FROM tbl_closure LEFT JOIN tbl_orig ON descendant_id = tbl_orig.id WHERE ancestor_id = XXX AND depth <> 0;
-- get only direct descendants
SELECT tbl_orig.* FROM tbl_closure LEFT JOIN tbl_orig ON descendant_id = tbl_orig.id WHERE ancestor_id = XXX AND depth = 1;
-- get all ancestors
SELECT tbl_orig.* FROM tbl_closure LEFT JOIN tbl_orig ON ancestor_id = tbl_orig.id WHERE descendant_id = XXX AND depth <> 0;
-- find the deepest level of children
SELECT MAX(depth) FROM tbl_closure WHERE ancestor_id = XXX;
IVO GELOV
źródło