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

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ę:

• Jeszcze jedno porównanie przedziałów zagnieżdżonych a porównanie listy adiakencji : najlepsze porównanie , jakie znalazłem, listy adiakencji, zmaterializowanej ścieżki, zestawu zagnieżdżonego i przedziału zagnieżdżonego.
• Modele danych hierarchicznych : slajdy z dobrymi objaśnieniami dotyczącymi kompromisów i przykładowego użycia
• Reprezentowanie hierarchii w MySQL : szczególnie bardzo dobry przegląd zestawu zagnieżdżonego
• Hierarchiczne dane w RDBMS : najbardziej kompleksowy i dobrze zorganizowany zestaw linków, jaki widziałem, ale niewiele w wyjaśnieniu

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

• Użyj zmiennych sesji dla listy Adjacency

Wyrocznia

• Użyj CONNECT BY, aby przeglądać listy Adjacency

PostgreSQL

• Typ danych dla ścieżki zmaterializowanej

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ć.

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.

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

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.

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

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.

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.

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;