sql - von - relationale datenbank vorteile




Welche Möglichkeiten gibt es, um hierarchische Daten in einer relationalen Datenbank zu speichern? (5)

Adjazenzmodell + geschachtelte Mengenmodell

Ich ging dafür, weil ich neue Elemente leicht in den Baum einfügen konnte (Sie brauchen nur die ID eines Zweigs, um ein neues Element einzufügen) und es auch ziemlich schnell abzufragen.

+-------------+----------------------+--------+-----+-----+
| 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 |
+-------------+----------------------+--------+-----+-----+
  • Jedes Mal, wenn Sie alle untergeordneten Elemente eines übergeordneten Elements benötigen, fragen Sie einfach die parent Spalte ab.
  • Wenn Sie alle Nachkommen eines Elternteils benötigen, rgt Sie nach Artikeln, die zwischen lft und rgt des Elternteils liegen.
  • Wenn Sie alle Eltern eines beliebigen Knotens bis zur Wurzel des Baums rgt Sie nach Elementen, die lft niedriger als die rgt und rgt des Knotens größer als das rgt des Knotens sind, und sortieren Sie nach parent .

Ich musste den Zugriff auf den Baum beschleunigen und den Baum schneller durchsuchen als Inserts, deshalb habe ich das gewählt

Das einzige Problem besteht darin, die left und right Spalten beim Einfügen neuer Elemente zu korrigieren. Nun, ich habe eine gespeicherte Prozedur dafür erstellt und sie jedes Mal aufgerufen, wenn ich ein neues Element eingefügt habe, was in meinem Fall selten war, aber es ist wirklich schnell. Ich habe die Idee aus dem Buch von Joe Celko, und die gespeicherte Prozedur und wie ich dazu gekommen bin, wird hier in DBA SE erklärt https://dba.stackexchange.com/q/89051/41481

Gute Übersichten

In der Regel entscheiden Sie zwischen schnellen Lesezeiten (z. B. verschachtelte Menge) oder schnellen Schreibzeiten (Adjazenzliste). In der Regel erhalten Sie eine Kombination der unten aufgeführten Optionen, die am besten zu Ihren Bedürfnissen passen. Im Folgenden finden Sie einige detaillierte Informationen:

Optionen

Ich bin mir bewusst und allgemeine Merkmale:

  1. Adjazenzliste :
    • Spalten: ID, ParentID
    • Einfach zu implementieren.
    • Günstiger Knoten wird verschoben, eingefügt und gelöscht.
    • Teuer, um die Ebene zu finden (kann als berechnete Spalte gespeichert werden), Abstammung und Nachkommen (Bridge-Tabelle kombiniert mit Level-Spalte kann lösen), Pfad (Lineage-Spalte kann lösen).
    • Verwenden Sie allgemeine Tabellenausdrücke in den Datenbanken, die sie durchqueren.
  2. Verschachtelter Satz (aka Modified Preorder Tree Traversal)
    • Popularisiert von Joe Celko in zahlreichen Artikeln und seinem Buch Bäume und Hierarchien in SQL für Smarties
    • Spalten: Links, Rechts
    • Billiges Niveau, Abstammung, Nachkommen
    • Volatile encoding - verschiebt, fügt ein, löscht teurer.
    • Erfordert eine bestimmte Sortierreihenfolge (z. B. erstellt). Um alle Nachkommen in einer anderen Reihenfolge zu sortieren, sind zusätzliche Arbeiten erforderlich.
  3. Verschachtelte Intervalle
    • Wie verschachtelte Menge, aber mit Real / Float / Dezimal, so dass die Codierung nicht flüchtig ist (kostengünstig move / insert / delete)
    • Es muss sich um echte / float / dezimale Darstellungsprobleme handeln
    • Eine komplexere Matrixcodierungsvariante fügt den Vorteil der Vorfahrencodierung hinzu, wie den materialisierten Pfad für "frei"
  4. Bridge-Tabelle (auch bekannt als Closure-Tabelle : einige gute Ideen zur Verwendung von Triggern für die Aufrechterhaltung dieses Ansatzes)
    • Spalten: Vorfahre, Nachfahre
    • Steht abseits von der Tabelle, die es beschreibt.
    • Kann einige Knoten in mehr als einer Hierarchie enthalten.
    • Billige Vorfahren und Nachkommen (wenn auch nicht in welcher Reihenfolge)
    • Für die vollständige Kenntnis einer Hierarchie muss mit einer anderen Option kombiniert werden.
  5. Flacher Tisch
    • Eine Änderung der Adjazenzliste, die jedem Datensatz eine Spalte "Level und Rang" (z. B. Reihenfolge) hinzufügt.
    • Teure Umzug und Löschen
    • Billige Abstammung und Nachkommen
    • Gute Verwendung: Threaded Diskussion - Foren / Blog-Kommentare
  6. Abstammungsspalte (aka Materialized Path , Path Enumeration)
    • Spalte: Abstammung (zB / Eltern / Kind / Enkel / etc ...)
    • Beschränken Sie, wie tief die Hierarchie sein kann.
    • Nachkommen billig (zB LEFT(lineage, #) = '/enumerated/path' )
    • Ancestry tricky (datenbankspezifische Abfragen)
  7. Mehrere Abstammungsspalten
    • Spalten: eine für jede Abstammungsstufe, bezieht sich auf alle Eltern bis zur Wurzel, Ebenen unterhalb der Stufe der Gegenstände werden auf NULL gesetzt
    • Beschränken Sie, wie tief die Hierarchie sein kann
    • Günstige Vorfahren, Nachkommen, Ebene
    • Billig einfügen, löschen, bewegen der Blätter
    • Teuer einfügen, löschen, verschieben der internen Knoten

Datenbankspezifische Hinweise

MySQL

Orakel

  • Verwenden Sie CONNECT BY , um Adjazenzlisten zu durchlaufen

PostgreSQL

SQL Server


Dies ist eine sehr unvollständige Antwort auf Ihre Frage, aber ich hoffe immer noch nützlich.

Microsoft SQL Server 2008 implementiert zwei Funktionen, die für die Verwaltung hierarchischer Daten äußerst nützlich sind:

  • der HierarchyId Datentyp.
  • allgemeine Tabellenausdrücke mit dem Schlüsselwort with .

Werfen Sie einen Blick auf "Modellieren Sie Ihre Datenhierarchien mit SQL Server 2008" von Kent Tegels auf MSDN für Starts. Siehe auch meine eigene Frage: Rekursive Abfrage der gleichen Tabelle in SQL Server 2008


Dieser Entwurf wurde noch nicht erwähnt:

Mehrere Abstammungsspalten

Obwohl es Einschränkungen gibt, wenn Sie sie ertragen können, ist es sehr einfach und sehr effizient. Eigenschaften:

  • Spalten: eine für jede Abstammungsstufe, bezieht sich auf alle Eltern bis zur Wurzel, Ebenen unterhalb der Ebene der aktuellen Gegenstände sind auf NULL gesetzt
  • Beschränken Sie, wie tief die Hierarchie sein kann
  • Günstige Vorfahren, Nachkommen, Ebene
  • Billig einfügen, löschen, bewegen der Blätter
  • Teuer einfügen, löschen, verschieben der internen Knoten

Hier folgt ein Beispiel - taxonomischer Baum der Vögel, also ist die Hierarchie Klasse / Ordnung / Familie / Gattung / Art - Spezies ist die unterste Ebene, 1 Reihe = 1 Taxon (was den Arten im Fall der Blattknoten entspricht):

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

und das Beispiel der Daten:

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

Das ist großartig, weil Sie auf diese Weise alle erforderlichen Operationen auf sehr einfache Weise ausführen können, solange die internen Kategorien ihre Ebene in der Struktur nicht ändern.


Ich verwende PostgreSQL mit Verschlusstabellen für meine Hierarchien. Ich habe eine universelle gespeicherte Prozedur für die gesamte Datenbank:

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;
$_$;

Dann erstelle ich für jede Tabelle, in der ich eine Hierarchie habe, einen Trigger

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

Zum Füllen einer Verschlusstabelle aus einer vorhandenen Hierarchie verwende ich diese gespeicherte Prozedur:

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

Closure-Tabellen sind mit 3 Spalten definiert - ANCESTOR_ID, DESCENDANT_ID, DEPTH. Es ist möglich (und ich rate sogar), Datensätze mit demselben Wert für ANCESTOR und DESCENDANT zu speichern und einen Wert von 0 für DEPTH. Dies vereinfacht die Abfragen zum Abrufen der Hierarchie. Und sie sind wirklich sehr einfach:

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

Wenn Ihre Datenbank Arrays unterstützt, können Sie auch eine Herkunftsspalte oder einen materialisierten Pfad als Array mit übergeordneten IDs implementieren.

Speziell mit Postgres können Sie dann die Mengenoperatoren verwenden, um die Hierarchie abzufragen und eine ausgezeichnete Leistung mit GIN-Indizes zu erzielen. Dies macht das Auffinden von Eltern, Kindern und der Tiefe in einer einzigen Abfrage ziemlich trivial. Updates sind auch ziemlich überschaubar.

Ich habe eine vollständige Beschreibung der Verwendung von Arrays für materialisierte Pfade, wenn Sie neugierig sind.





hierarchical-data