MPTT (Modified Preorder Tree Traversal) oder wie speichere ich hierarchische Daten?

[Arne Buchwald]

Hallo,

ich habe gestern von Matthias (rm) den folgenden Link http://www.sitepoint.com/print/hierarchical-data-database bekommen und habe mir das ganze eben soweit durchgelesen.

Das MPTT-Model macht auf den ersten Blick einen fantastischen Eindruck, jedoch habe ich zwei Bedenken, die das Modell für meinen Anwendungszweck leider unbrauchbar machen könnten.

1) Im Modell wird angesprochen, wie leicht es ist, vom Ende (im dortigen Beispiel: eine Frucht) den Pfad zum root-node zu erhalten. In meinem Einsatzzweck benötige ich jedoch eine Möglichkeit, über einen weiteren Join die Anzahl aller Datensätze zu ermitteln, die unterhalb eines beliebigen Nodes liegen.

2) Einfüge/Lösch-Anomalien
Auch wenn der Begriff aus der Normalisierung kommt und nicht exakt passt, gehen meine Bedenken trotzdem in diese Richtung. In meiner Anwendung habe ich große Datenmengen, wobei diese immer mit einem Node aus der hierarchischen Anordnung verknüpft sind. Wenn jetzt irgendwo ein Node gelöscht oder eingefügt wird, müssen alle Verknüpfungstabellen geupdatet werden, das nicht unerheblich Last erzeugt. Je nachdem, wo eine Änderung in der hierarchischen Anordnung stattfindet, kann dieses nach dem Modell auch die ganze Datenbank betreffen.

Wie seht ihr dieses Modell? Teilt ihr meine Bedenken oder kennt ihr eine bessere Möglichkeit?


Ich hatte in anderne Scripten gesehen, dass folgende Konstruktion zum Einsatz kommt:

ResellerID, parentID, parentList, title
----------------------------------------------------------
     1        ,             ,              , Admin
     2        ,   1        ,      1      , Reseller 1
     3        ,   1        ,      1      , Reseller 2
     4        ,   2        ,      (1,2)  , Reseller 1 des Resellers 1
     5        ,   4        ,      (1,2,4)  , Reseller 1 (No. 5) des Reseller 1 (No. 4) des Resellers 1 (No. 2)

und dann eine Abfrage von Node X bis zum Endnote mit einem SQL-Statement

WHERE 2 IN (parentList)

durchgeführt wird. Leider wird "IN (parentlist)" bei mir dann wohl als String behandelt, so dass keine Abfrage "Ist 2 ein Element in der Parentlist" durchgeführt wird.

 

[hpvw]

Re: MPTT (Modified Preorder Tree Traversal) oder wie speichere ich hierarchische Date

Hallo Arne,
das Modell, welches Du in Deinem Beispiel darstellst, habe ich noch nicht gesehen.
Mein erster Kritikpunkt an dem Modell ist, dass bereits die erste Normalform verletzt wird. Die parentList ist nicht atomar.
Im Gegensatz zum ursprünglichen Datentyp (int) muss sie darüber hinaus als char gespeichert werden. Das ist Dir bei Deinem Query ja auch bereits aufgefallen.
Wenn Du die Struktur (mit allen Vorgängern) in einer einzigen Tabelle abbilden willst, würde ich die parentList anders aufbauen, und zwar ausschließlich als, durch Kommata getrennte, Liste mit einem Komma am Ende. Beispiel für Dein Element mit der ID 5: 1,2,4,
Dadurch könntest Du wenigstens mit Zeichenketten-Funktionen sicher arbeiten:

... WHERE LOCATE(CONCAT(2,','),parentList)>0

Alternativ wäre auch möglich, ohne das Komma am Ende mit FIND_IN_SET zu arbeiten. LOACATE und CONCAT sollte es in vergleichbarer Form in jedem DBMS geben, bei FIND_IN_SET wäre ich mir nicht so sicher.

Ich würde jedoch eine andere Modellierung vorschlagen und die parentList in eine zweite Tabelle auslagern:

Reseller
ResellerID, parentID, title
----------------------------------------------------------
     1         null   Admin
     2           1    Reseller 1
     3           1    Reseller 2
     4           2    Reseller 1 des Resellers 1
     5           4    Reseller 1 (No. 5) des Reseller 1 (No. 4) des Resellers 1 (No. 2)

AllRessellerParent
ResellerID, parentID
----------------------------------------------------------
     2         1
     3         1
     4         1
     4         2
     5         1
     5         2
     5         4

Um nun alle übergeordneten Reseller eines Datensatzes (im Beispiel ResellerID 2) zu erhalten kannst Du mit einem Subquery oder einem entsprechenden Workaround arbeiten:

SELECT title AS aParentReseller 
FROM Reseller
WHERE ResellerID IN (
  SELECT parentID
  FROM AllRessellerParent
  WHERE ResellerID = 2
)

oder

SELECT title AS aParentReseller 
FROM Reseller
JOIN AllRessellerParent
  ON Reseller.ResellerID = AllRessellerParent.parentID
WHERE AllRessellerParent.ResellerID = 2

Die passende Datenbankversion vorausgesetzt, kannst Du die von Dir dargestellte Tabelle auch jederzeit mit GROUP_CONCAT als Ergebnistabelle erzeugen.

Nun zum MPTT
Dein erstes Problem ist, wenn ich es richtig verstanden habe, bereits in dem Artikel gelöst. Mit einem Subquery ist es kein Problem das Retrieve-the-Tree-Query in die Projektion des The-Path-to-a-Node-Query aufzunehmen. Wenn Dein DBMS das nicht unterstützt, müßte man sich einen Workaround mit JOIN überlegen.

Am Beispiel aus dem Artikel (die Tabelle heißt bei mir mptt und nicht tree) für die Kirsche mit Subquery:

SELECT 
  m.title,
  (SELECT COUNT(*) - 1 
   FROM mptt i
   WHERE i.lft BETWEEN m.lft AND m.rgt) AS SubNodes
FROM mptt m 
WHERE m.lft < 4 AND m.rgt > 5 
ORDER BY m.lft ASC

Als Workaround mit JOIN:

SELECT 
  m.title,
  (COUNT(i.title) - 1) AS SubNodes
FROM mptt m 
LEFT JOIN mptt i 
  ON i.lft BETWEEN m.lft AND m.rgt
WHERE m.lft < 4 AND m.rgt > 5 
GROUP BY m.title
ORDER BY m.lft ASC

Da ich mich jetzt schon wieder ans ausprobieren gemacht habe, bevor ich den Artikel zuende gelesen habe, lasse ich das obere mal stehen und schreibe das ganze in "einfach" noch mal:

SELECT 
  title,
  ((rgt-lft-1)/2) AS SubNodes
FROM mptt 
WHERE lft < 4 AND rgt > 5 
ORDER BY lft ASC

Zu Deiner zweiten Sorge:
Man kann grundsätzliche Aussagen zu Performance und Problemen treffen, die allerdings im Einzelfall zu prüfen sind.

Wenn Du wenig Ebenen hast und dazu sogar noch wenige Nodes in der obersten Ebene, sollte klar sein, dass das Adjacent-List-Model zu bevorzugen ist. Das rekursive Auslesen fällt dann wenig ins Gewicht. Falsche Umsetzung der Nutzereingaben sind kaum vorstellbar, da das Modell sehr einfach ist. Anomalien sind verhältnismäßig einfach zu erkennen und zu korrigieren.

Da dies bei Dir nicht der Fall ist, ist abzuwägen.

Aus Performance-Sicht ist das Adjacent-List-Model vorzuziehen, wenn überwiegend Änderungen am Datenbestand vorgenommen werden und vollständiges Auslesen oder auslesen über mehrere Ebenen eher selten ist.

Nun vermute ich mal, dass Änderungen an Deinem Datenbestand eher selten sind oder sich mit den Auslese-Vorgängen wenigstens die Wage halten. Du sprichst außerdem von einem großen Datenbestand und Operationen, die bis zum Root-Node reichen.

Damit kommt das MPTT natürlich eher in Frage. Wenn nun aber allgemein wenig Vorgänge (lesend und schreibend) am Datenbestand passieren, da es z.B. wenige Nutzer gibt, würde ich das Adjacent-List-Model bevorzugen, weil das MPTT doch ein gutes Stück komplizierter ist, mehr Entwicklungszeit und mehr Tests benötigt und nicht unbedingt jeder Entwickler, der jetzt oder später an dem Projekt mitwirkt, versteht, was dort passiert.

Vermutlich trifft auch diese Vorraussetzung nicht nicht zu. Damit ist es allein aus Performancegründen geboten, das MPTT zu verwenden. Der entscheidende Nachteil ist, dass Fehler im Datenbestand schwer zu finden und korrigieren sind. Das heißt, Du musst sehr sorgfältig arbeiten und viele Tests durchführen. Ein Vorschlag wäre, dass Du schreibende Zugriffe auf die Tree-Tabelle ausschließlich von einer einzigen Klasse durchführen lässt, die Du entsprechend sorgfältig schreibst. Dann zwingst Du Dich, dass in anderen Bereichen der Anwendung keine schreibenden Queries auf diese Tabelle ausgeführt werden (das programmtechnisch zu verhindern ist nahezu unmöglich). In Deiner MPTT-Klasse implementierst Du Methoden zum Einfügen, Verschieben und Löschen, denen Du Parameter im Sinne des Adjacent-List-Modell übergibst und entsprechend umsetzt. Diese drei Methoden sind ohne große Gehirnakrobat aus anderen Teilen der Anwendung ansprechbar. Sie sind nur einmal zu schreiben und ausführlich zu testen und reduzieren damit die Fehleranfälligkeit Deines Baumes.

Vielleicht konnte ich Dir ja ein Paar Anregungen oder Entscheidungshilfen bieten.

Gruß hpvw

 

[Mik3e]

Hi Arne,

Sieht aus, als wäre hier im Forum die Nested Sets Hysterie ausgebrochen )
Genau dieses Thema haben wir (HP und ich) vor ca. 2 Wochen intesiv durchgekaut...
Wahrscheinlich findest Du hier die eine oder andere Interessante Antwort.
http://www.tutorials.de/tutorials225685.html

Meine ersten Erfahrungen bisher:
Performance: Römisch 1. Das Auslesen ist einfach genial und flutscht nur so... Ich habe mal einen Baum mit mehren tausend Nodes zu Testzwecken erzeugt, und ein Aufruf benötigt genau keine Rechenleistung (weder auf der DBMS- noch auf der PHP Maschine).

Nachteil (wie HP schon erwähnt hat): Update-Funktionen sind äußerst komplex und performancehungrig (wenn auch machbar). Ich muss gestehen, dass ich kein mathematisches Genie bin. Für meine Klasse die mir alle MPTT Methoden so anbietet, wie ich sie benötige, habe ich ca. eine Woche gebraucht. Dafür ist das Teil nun aber auch wirklich genial )

An dieser Stelle: DANKE HP Ohne seine Unterstützung hätt ichs wahrscheinlich nicht so rasch hinbekommen.

Wenn Du möchtest, kann ich Dir gerne Auszüge aus der Klasse posten.

WICHTIG: Für das Speichern des Baums unbedingt eine Transaktionssicher DB (Tabelle) verwenden, sonst hast Du beim Update rasch Probleme und ein echtes Chaos.

Ciao,
Mike