imported>Bauder24 am 5. Dezember 2022 um 14:15 Uhr

2022-12-05T14:15:59Z

Neue Seite

Der Begriff '''Nested Sets''' (verschachtelte Mengen) bezeichnet ein Modell zur Abbildung eines [[Baum (Graphentheorie)|Baumes]] mit Hilfe von [[Menge (Mathematik)|Mengen]], die ineinander verschachtelt sind. Dabei wird die "ist-Kind-von"-Beziehung auf eine "ist-Teilmenge-von"-Beziehung abgebildet. Das Modell wurde ursprünglich im Buch ''SQL for Smarties'' von [[Joe Celko]] vorgestellt. Es wird hauptsächlich im Rahmen von Datenbankanwendungen eingesetzt. Diese Technik ist auch unter dem Namen '''Modified Preorder Tree Traversal''' (MPTT) bekannt. Mit Hilfe von Nested Sets erkauft man sich die Möglichkeit, Teilbäume oder den Pfad zur Wurzel mit konstantem Aufwand auslesen zu können zum Preis, beim Ändern des Baumes mit komplexeren Operationen arbeiten zu müssen.

== Klassische Baumstruktur ==
Der klassische Ansatz zur Implementierung einer Baumstruktur in einer Datenbank ist das ''[[Adjazenzliste|Adjazenzlisten-Modell]]''. Hierbei wird zu jedem Knoten eine Referenz auf dessen Elternknoten abgelegt. Die Wurzel hat dabei keinen Verweis zu einem Elternknoten (das Feld ist mit NULL belegt); ein Blatt ist ein Knoten, zu dem kein anderer Knoten verweist.

== Baumstruktur als verschachtelte Mengen ==
Beim ''Nested-Sets-Modell'' wird die Baumstruktur in ineinander verschachtelte Mengen transformiert. Jeder Knoten entspricht einer Teilmenge; jede Teilmenge ist eine Teilmenge aller ihrer Eltern-Mengen. In einer Datenbank können diese verschachtelten Mengen repräsentiert werden, indem für jede Teilmenge zwei Werte bestimmt werden, die die Grenzen dieser Teilmenge bestimmen. Diese Werte werden oft mit ''links'' und ''rechts'' bezeichnet. Der Wert ''links'' ist immer kleiner als ''rechts''. Beide Werte einer Teilmenge sind größer als der Wert ''links'' ihrer Elternmenge und kleiner als deren Wert ''rechts''. Die folgende Grafik zeigt einen Baum, der in verschachtelte Mengen transformiert wurde. Die grünen Zahlen an den Rändern einer Menge sind die oben beschriebenen Werte ''links'' an der linken Kante und ''rechts'' an der rechten Kante.
=== Beispiel ===
[[Datei:Nestedsets.svg]]

== Operationen ==
=== Knoten einfügen ===
Die Teilmenge für den ersten Knoten erhält die Werte 1 für ''links'' und 2 für ''rechts''. Wird eine weitere Teilmenge für einen neuen Knoten unterhalb eines bestehenden Knotens eingefügt, wird ''rechts'' für die frischgebackene Elternmenge um 2 erhöht. Damit dies möglich ist, muss vorher im gesamten Baum jeder Wert ''links'' oder ''rechts'', der größer als der ursprüngliche Wert ''rechts'' der neuen Elternmenge ist, ebenfalls um 2 erhöht werden. Die Werte ''rechts'' minus 2 und ''rechts'' minus 1 der Elternmenge werden dann der neu eingefügten Teilmenge als ''links'' und ''rechts'' zugeordnet. Zu beachten ist hierbei, dass, anders als beim herkömmlichen Adjazenzlisten-Modell, die Reihenfolge der Kinder eines Knotens erhalten bleibt. Die soeben beschriebe Vorgehensweise ist äquivalent dazu, neue Knoten immer ans Ende der Liste der Kinder des Elternknotens anzuhängen. Genauso ist es denkbar, eine neue Teilmenge an beliebiger Stelle zwischen den anderen Teilmengen der Elternmenge einzufügen. Dabei müssen dann die Werte ''links'' und ''rechts'' der auf die neu eingefügte Teilmenge folgenden Kinder ebenfalls erhöht werden.

=== Transformieren einer Baumstruktur in verschachtelten Mengen ===
Eine bereits existierende Baumstruktur kann in verschachtelte Mengen überführt werden, in dem sie [[Tiefensuche|der Tiefe nach durchlaufen]] wird. Dabei werden, beginnend bei 1, die Kanten gezählt. Jedes Mal, wenn ein Knoten betreten wird, wird diesem der Wert des Zählers als ''links'' zugeordnet und der Zähler erhöht. Wenn der Knoten verlassen wird, nachdem alle seine Kinder bearbeitet wurden, wird ihm der Wert des Zählers als ''rechts'' zugeordnet und der Zähler abermals erhöht.

=== Teilbaum entfernen ===
Um einen vollständigen Teilbaum zu entfernen, werden zunächst die Werte ''links'' und ''rechts'' der Wurzel des Teilbaumes bestimmt. Danach kann dieser mitsamt seinen Teilmengen gelöscht werden, indem alle Knoten gelöscht werden, deren Werte für ''links'' und ''rechts'' innerhalb dieser Werte liegen oder mit ihnen übereinstimmen. Abschließend müssen noch alle ''links''-Werte sowie alle ''rechts''-Werte um die Breite des Teilbaumes verringert werden, die größer als der ''rechts''-Wert des zu entfernenden Knotens sind; die Breite ist hierbei die Differenz zwischen ''rechts'' und ''links'' dessen Wurzel plus 1.

== Auswertung ==
=== Anzahl aller Knoten eines Teilbaums ===
Die Hälfte der Breite eines Teilbaums entspricht der Anzahl der Knoten in diesem Teilbaum inklusive der Wurzel. Somit kann die Anzahl der Knoten im gesamten Baum ermittelt werden, indem der Wert ''rechts'' minus dem Wert ''links'' der Wurzel durch zwei geteilt und (auf-)gerundet wird.

=== Pfad zu einem Knoten ===
Im Gegensatz zum Adjazenzlistenmodell muss beim Nested-Sets-Modell der Pfad zu einem Knoten nicht rekursiv ermittelt werden. Es genügt, alle Teilmengen zu selektieren, deren ''links''-Werte kleiner sind und deren ''rechts''-Werte gleichzeitig größer sind als die des betrachteten Knotens. Werden diese Teilmengen nach ihrem ''links''-Wert sortiert, entspricht ihre Reihenfolge dem Weg von der Wurzel zum betrachteten Knoten.

=== Alle Knoten eines Teilbaumes ===
Alle Knoten unterhalb eines gegebenen Knotens können ermittelt werden, indem alle Teilmengen selektiert werden, deren Werte ''links'' und ''rechts'' sich innerhalb der Werte ''links'' und ''rechts'' des bearbeiteten Knotens befinden. Beim Adjanzenzlistenmodell müsste hier ebenfalls rekursiv vorgegangen werden.

=== Alle Blätter eines Teilbaumes ===
Die Abfrage nach einem kompletten Teilbaum kann leicht so modifiziert werden, dass nur Blätter, also Knoten ohne eigene Kinder, selektiert werden. Hierzu wird bei der Selektion als zusätzliches Kriterium ''rechts'' = ''links'' + 1 verwendet.

=== Tiefensuche ===
Um alle Knoten des Baumes gemäß einer [[Tiefensuche]] zu enumerieren, reicht bereits ein einfaches SELECT mit Sortierung aus. Und das in beiden Varianten ''preorder'' (Eltern- vor Kind-) sowie ''postorder'' (Kind- vor Elternknoten). Ebenso ist die durchlaufene Reihenfolge der Kindknoten aufgrund der symmetrischen Bedeutung von ''links'' und ''rechts'' durch eine leichte Variation der Sortierbedingung einfach umkehrbar.
<syntaxhighlight lang="sql">
SELECT * FROM tree ORDER BY r; /* DFS, postorder */
SELECT * FROM tree ORDER BY l; /* DFS, preorder */
SELECT * FROM tree ORDER BY l DESC; /* DFS, reverse postorder (smallest child last) */
SELECT * FROM tree ORDER BY r DESC; /* DFS, reverse preorder (smallest child last) */
</syntaxhighlight>

Die zusätzliche Bestimmung der Knotentiefe beim Durchlauf ist mit Hilfe eines Self-Joins möglich. Hierbei werden alle Tupel aus zwei Knoten selektiert, bei denen die Werte ''links'' und ''rechts'' des ersten Knotens zwischen den Werten ''links'' und ''rechts'' des zweiten Knotens liegen. Dabei kann die Tiefe jedes Knotens ermittelt werden, in dem gezählt wird, wie oft ein Tupel mit diesem Knoten als erstem Knoten auftritt. Das Ergebnis wird nach dem Wert ''links'' der enthaltenen Knoten sortiert. Diese Abfrage könnte in [[SQL]] beispielsweise so aussehen:
<syntaxhighlight lang="sql">
SELECT (COUNT(parent.id)-1) AS depth, node.id
FROM tree AS node, tree AS parent
WHERE node.l BETWEEN parent.l and parent.r
GROUP BY node.id ORDER BY node.l;
</syntaxhighlight>

Bei großen ''Nested Sets'' wäre ein solcher Self-Join nur durch das Anlegen zusätzlicher Indizes auf ''links'' und ''rechts'' laufzeittechnisch überhaupt realisierbar.
Daher wird in der Praxis häufig ein gemischtes Modell von Adjazenzlisten und ''Nested Sets'' verwendet, zu jedem Knoten also noch zusätzlich der Verweis auf den Elternknoten und die Knotentiefe mit abgelegt. Durch diesen vernachlässigbaren Mehraufwand beim Schreiben erreicht man so effiziente Auswertungsmöglichkeiten für viele vergleichbare Fragestellungen.

== Vor- und Nachteile ==
* Die Komplexität beim Lesen ist in den meisten Fällen konstant. Beim Adjazenzlistenmodell ist der Aufwand linear abhängig von der Tiefe des bearbeiteten Knotens. Im Tausch ist eine Änderung des Baumes beim Nested-Sets-Modell wesentlich aufwändiger als beim Adjazenzlistenmodell. Somit eignet es sich besser für Strukturen, die nicht häufig modifiziert, aber sehr oft gelesen werden.
* Die Darstellung als Mengen passt besser in die mengenorientierte Welt der Datenbanken. Mit der Abfragesprache [[SQL]] kann auf Mengen besser operiert werden als auf hierarchischen Strukturen.
* Das Abfragen der direkten Kinder eines Knotens ist schwierig.
* Die Reihenfolge der Kinder eines Knotens bleibt erhalten.

== Weblinks ==
* [http://www.klempert.de/nested_sets/ ''Jede Menge Bäume – Nested Sets''] von Arne Klempert
* [http://ffm.junetz.de/members/reeg/DSP/node11.html#SECTION04340000000000000000 ''Bäume in SQL''] von Christoph Reeg
* [https://www.php-resource.de/de/php-tutorials/Das-Nested-Sets-Modell---Baeume-mit-SQL_14117 ''Das-Nested-Sets-Modell – Baeume mit SQL''] von php-resource.de
* [http://explainextended.com/2009/09/24/adjacency-list-vs-nested-sets-postgresql ''Adjecency List vs. Nested Set: Postgresql''] von Explain Extended (englisch)
* [http://explainextended.com/2009/09/25/adjacency-list-vs-nested-sets-sql-server ''Adjecency List vs. Nested Set: SQL-Server''] von Explain Extended (englisch)
* [http://explainextended.com/2009/09/28/adjacency-list-vs-nested-sets-oracle ''Adjecency List vs. Nested Set: ORACLE''] von Explain Extended (englisch)
* [http://explainextended.com/2009/09/29/adjacency-list-vs-nested-sets-mysql ''Adjecency List vs. Nested Set: MySQL''] von Explain Extended (englisch)

[[Kategorie:Datenstruktur]]
[[Kategorie:Graphentheorie]]

Nested Sets - Versionsgeschichte

imported>Bauder24 am 5. Dezember 2022 um 14:15 Uhr