Verschachteltes Set-Modell - Nested set model

Das Nested-Set-Modell ist eine Technik zur Darstellung verschachtelter Sets (auch bekannt als Bäume oder Hierarchien ) in relationalen Datenbanken .

Motivation

Die standardmäßige relationale Algebra und die relationale Berechnung sowie die darauf basierenden SQL- Operationen sind nicht in der Lage, alle wünschenswerten Operationen auf Hierarchien direkt auszudrücken. Das Nested-Set-Modell ist eine Lösung für dieses Problem.

Eine alternative Lösung ist der Ausdruck der Hierarchie als Eltern-Kind-Beziehung. Celko nannte dies das Adjazenzlistenmodell . Wenn die Hierarchie eine beliebige Tiefe haben kann, erlaubt das Adjazenzlistenmodell nicht den Ausdruck von Operationen wie das Vergleichen des Inhalts von Hierarchien von zwei Elementen oder das Bestimmen, ob sich ein Element irgendwo in der Unterhierarchie eines anderen Elements befindet. Wenn die Hierarchie eine feste oder begrenzte Tiefe hat, sind die Operationen möglich, aber teuer, da eine relationale Verknüpfung pro Ebene erforderlich ist . Dies wird oft als Stücklistenproblem bezeichnet.

Hierarchien können einfach ausgedrückt werden, indem zu einer Graphdatenbank gewechselt wird . Alternativ gibt es für das relationale Modell mehrere Auflösungen, die in einigen relationalen Datenbankverwaltungssystemen als Workaround verfügbar sind :

• Unterstützung für einen dedizierten Hierarchiedatentyp , wie beispielsweise in der hierarchischen Abfrageeinrichtung von SQL ;
• Erweiterung der relationalen Sprache mit Hierarchiemanipulationen, wie beispielsweise in der verschachtelten relationalen Algebra .
• Erweitern der relationalen Sprache mit transitivem Abschluss , wie beispielsweise der CONNECT-Anweisung von SQL; dies ermöglicht die Verwendung einer Eltern-Kind-Beziehung, aber die Ausführung bleibt teuer;
• die Abfragen können in einer Sprache ausgedrückt werden, die Iteration unterstützt und die relationalen Operationen umschließt , wie PL/SQL , T-SQL oder eine allgemeine Programmiersprache

Wenn diese Lösungen nicht verfügbar oder nicht durchführbar sind, muss ein anderer Ansatz gewählt werden.

Technik

Das Modell der verschachtelten Menge besteht darin, die Knoten gemäß einer Baumdurchquerung zu nummerieren , die jeden Knoten zweimal besucht, wobei Nummern in der Reihenfolge des Besuchs und bei beiden Besuchen zugewiesen werden. Dadurch bleiben für jeden Knoten zwei Nummern übrig, die als zwei Attribute gespeichert werden. Abfragen werden kostengünstig: Die Hierarchiezugehörigkeit kann durch Vergleich dieser Zahlen getestet werden. Die Aktualisierung erfordert eine Neunummerierung und ist daher teuer. Verfeinerungen, die rationale Zahlen anstelle von ganzen Zahlen verwenden, können eine Neunummerierung vermeiden und sind daher schneller zu aktualisieren, wenn auch viel komplizierter.

Beispiel

In einem Bekleidungsgeschäftskatalog kann die Kleidung nach der links angegebenen Hierarchie kategorisiert werden:

Eine Hierarchie: Arten von Kleidung

Die durch die Baumdurchquerung zugewiesene Nummerierung

Die Kategorie „Bekleidung“ mit der höchsten Position in der Hierarchie umfasst alle untergeordneten Kategorien. Es werden daher linke und rechte Domänenwerte von 1 und 22 gegeben, wobei letzterer Wert das Doppelte der Gesamtzahl der repräsentierten Knoten ist. Die nächste hierarchische Ebene enthält "Männer" und "Frauen", beide enthalten Ebenen in sich, die berücksichtigt werden müssen. Dem Datenknoten jeder Ebene werden linke und rechte Domänenwerte entsprechend der Anzahl der darin enthaltenen Unterebenen zugewiesen, wie in den Tabellendaten gezeigt.

Leistung

Es ist zu erwarten, dass Abfragen, die verschachtelte Mengen verwenden, schneller sind als Abfragen, die eine gespeicherte Prozedur verwenden , um eine Adjazenzliste zu durchlaufen, und daher die schnellere Option für Datenbanken, die keine nativen rekursiven Abfragekonstrukte wie MySQL 5.x haben. Es ist jedoch zu erwarten, dass rekursive SQL-Abfragen bei Abfragen zum Suchen von unmittelbaren Nachkommen vergleichbar und bei anderen Tiefensuchabfragen viel schneller ausgeführt werden, ebenso wie die schnellere Option für Datenbanken, die sie bereitstellen, wie PostgreSQL , Oracle und Microsoft SQL Server . MySQL hatte früher keine rekursiven Abfragekonstrukte, fügte jedoch solche Funktionen in Version 8 hinzu.

Nachteile

Der Anwendungsfall für eine dynamische endlose Datenbankbaumhierarchie ist selten. Das Nested Set-Modell ist geeignet, wenn das Baumelement und ein oder zwei Attribute die einzigen Daten sind, ist jedoch eine schlechte Wahl, wenn komplexere relationale Daten für die Elemente im Baum vorhanden sind. Bei einer willkürlichen Starttiefe für eine Kategorie von 'Fahrzeuge' und ein Kind von 'Autos' mit einem Kind von 'Mercedes' muss eine Fremdschlüssel-Tabellenbeziehung hergestellt werden, es sei denn, die Baumtabelle ist nativ nicht normalisiert. Attribute eines neu erstellten Baumelements teilen möglicherweise nicht alle Attribute mit einem Elternteil, Kind oder sogar einem Geschwister. Wenn eine Fremdschlüsseltabelle für eine Tabelle mit 'Plants'-Attributen erstellt wird, wird den Kindattributdaten von 'Trees' und seinem Kind 'Oak' keine Integrität verliehen. Daher muss in jedem Fall eines in den Baum eingefügten Elements für alle außer den trivialsten Anwendungsfällen eine Fremdschlüsseltabelle der Attribute des Elements erstellt werden.

Wenn nicht erwartet wird, dass sich der Baum häufig ändert, kann beim anfänglichen Entwurf eines Systems eine ordnungsgemäß normalisierte Hierarchie von Attributtabellen erstellt werden, was zu einfacheren, portableren SQL-Anweisungen führt; insbesondere solche, die nicht eine beliebige Anzahl von Laufzeit-, programmgesteuert erstellten oder gelöschten Tabellen für Änderungen am Baum erfordern. Bei komplexeren Systemen kann die Hierarchie durch relationale Modelle anstelle einer impliziten numerischen Baumstruktur entwickelt werden. Die Tiefe eines Elements ist einfach ein weiteres Attribut und nicht die Grundlage für eine gesamte DB-Architektur. Wie in SQL Antipatterns angegeben :

Nested Sets ist eine clevere Lösung – vielleicht zu clever. Es unterstützt auch nicht die referentielle Integrität. Sie wird am besten verwendet, wenn Sie einen Baum häufiger abfragen als ihn ändern müssen.

Das Modell lässt nicht mehrere übergeordnete Kategorien zu. Zum Beispiel könnte eine 'Eiche' ein Kind von 'Baum-Typ', aber auch 'Holz-Typ' sein. Um dies zu berücksichtigen, muss ein zusätzliches Tagging oder eine Taxonomie erstellt werden, was wiederum zu einem komplexeren Design führt als ein einfaches festes Modell.

Verschachtelte Mengen sind für Einfügungen sehr langsam, da die linken und rechten Domänenwerte für alle Datensätze in der Tabelle nach der Einfügung aktualisiert werden müssen. Dies kann zu einer großen Belastung der Datenbank führen, da viele Zeilen neu geschrieben und Indizes neu erstellt werden. Wenn es jedoch möglich ist, anstelle eines einzelnen großen Baums einen Wald aus kleinen Bäumen in einer Tabelle zu speichern, kann der Overhead erheblich reduziert werden, da nur ein kleiner Baum aktualisiert werden muss.

Das Nested-Intervall-Modell leidet nicht unter diesem Problem, ist jedoch komplexer zu implementieren und nicht so bekannt. Es leidet immer noch unter dem relationalen Fremdschlüsseltabellenproblem. Das verschachtelte Intervallmodell speichert die Position der Knoten als rationale Zahlen, ausgedrückt als Quotienten (n/d). [1]

Variationen

Die Verwendung des Modells der verschachtelten Menge wie oben beschrieben hat einige Leistungseinschränkungen während bestimmter Baumdurchquerungsoperationen. Wenn Sie beispielsweise versuchen, die unmittelbar untergeordneten Knoten eines übergeordneten Knotens zu finden, müssen Sie den Teilbaum auf eine bestimmte Ebene beschneiden, wie im folgenden SQL- Codebeispiel:

SELECT Child.Node, Child.Left, Child.Right
FROM Tree as Parent, Tree as Child
WHERE
	Child.Left BETWEEN Parent.Left AND Parent.Right
	AND NOT EXISTS (    -- No Middle Node
		SELECT *
		FROM Tree as Mid
		WHERE Mid.Left BETWEEN Parent.Left AND Parent.Right
     			AND Child.Left BETWEEN Mid.Left AND Mid.Right
			AND Mid.Node NOT IN (Parent.Node, Child.Node)
	)
	AND Parent.Left = 1  -- Given Parent Node Left Index

Oder gleichwertig:

SELECT DISTINCT Child.Node, Child.Left, Child.Right
FROM Tree as Child, Tree as Parent 
WHERE Parent.Left < Child.Left AND Parent.Right > Child.Right  -- associate Child Nodes with ancestors
GROUP BY Child.Node, Child.Left, Child.Right
HAVING max(Parent.Left) = 1  -- Subset for those with the given Parent Node as the nearest ancestor

Die Abfrage wird komplizierter, wenn nach Kindern mit einer Tiefe von mehr als einer Ebene gesucht wird. Um diese Einschränkung zu überwinden und die Baumdurchquerung zu vereinfachen , wird dem Modell eine zusätzliche Spalte hinzugefügt, um die Tiefe eines Knotens innerhalb eines Baums beizubehalten.

In diesem Modell kann das Auffinden der unmittelbaren Kinder eines übergeordneten Knotens mit dem folgenden SQL- Code erreicht werden:

SELECT Child.Node, Child.Left, Child.Right
FROM Tree as Child, Tree as Parent
WHERE
	Child.Depth = Parent.Depth + 1
	AND Child.Left > Parent.Left
	AND Child.Right < Parent.Right
	AND Parent.Depth = 1  -- Given Parent Node Left Index

Siehe auch

• Baumdurchquerung
• Baum (Datenstruktur)
• Nachbarschaftsliste

Verweise

Externe Links

• Troels' Links zu hierarchischen Daten in RDBMSs
• Hierarchische Daten in relationalen Datenbanken verwalten
• PHP PEAR-Implementierung für verschachtelte Sets – von Daniel Khan
• Transformieren Sie jede Adjazenzliste in verschachtelte Mengen mithilfe von MySQL Stored Procedures
• PHP Doctrine DBAL-Implementierung für Nested Sets – von PreviousNext
• R Nested Set – Beispiel für ein verschachteltes Set in R