Man denkt bei einem Baum direkt an Dinge wie z.B. das Dateisystem: Ein Verzeichnis kann mehrere Unterverzeichnisse und diverse Dateien beinhalten. Diese Parent/Child-Beziehung (von den Verzeichnissen) kann man am einfachsten in der relationalen Datenbank folgendermaßen abbilden:
Tabelle: FOLDER
+----+-------------+-----------+
| ID | NAME | PARENT_ID |
+----+-------------+-----------+
| 1 | Parent1 | NULL |
| 2 | Child1 | 1 |
| 3 | Child2 | 1 |
| 4 | Parent2 | NULL |
| 6 | Child2 | 4 |
| 7 | ChildChild1 | 6 |
| 8 | Child1New | 4 |
+----+-------------+-----------+
Die in einem Verzeichnis enthaltenen Dateien müssen natürlich mit einer Relations-Tabelle realisiert werden. z.B.:
Tabelle: FOLDER_FILES
+-----------+-------------+
| FOLDER_ID | FILE_ID |
+-----------+-------------+
| 1 | 2 |
| 2 | 3 |
+-----------+-------------+
Jetzt kommt der Kunde und möchte z.B. nur noch die Verzeichnisse sehen die Dateien beinhalten. Das hört sich erstmal sehr einfach an - nur haben wir das Problem, dass ein Verzeichnis keine Dateien beinhaltet aber in einem Unterverzeichnis Dateien zu finden sein könnten. Wir müssten also Teilmengen selektieren können. Genau zu diesem Zweck kann das "Nested Set"-Modell verwendet werden.
Ein einfacheres Modell ist "Materialzed path" (Pfad-Modell) - hier wird zu jedem Knoten (in diesem Beispiel Verzeichnis) der komplette Pfad in eine zusätzliche Spalte gespeichert:
Tabelle: FOLDER
+----+-------------+---------+-----------+
| ID | NAME | PATH | PARENT_ID |
+----+-------------+---------+-----------+
| 1 | Parent1 | .1. | NULL |
| 2 | Child1 | .1.2. | 1 |
| 3 | Child2 | .1.3. | 1 |
| 4 | Parent2 | .4. | NULL |
| 6 | Child2 | .4.6. | 4 |
| 7 | ChildChild1 | .4.6.7. | 6 |
| 8 | Child1New | .4.8. | 4 |
+----+-------------+---------+-----------+
Nun kann man einen kompletten Teilbaum mit folgender SQL-Abfrage erhalten:
SELECT * FROM FOLDER WHERE PATH LIKE '.4.%'Hier selektiert man das Verzeichnis "Parent2" inklusive aller Kinder.
Dieses Pattern ist mit Hibernate relativ einfach zu realisieren. Einfach eine zusätzliche Property/Spalte "PATH" hinzufügen und einen Interceptor schreiben, der vor dem Schreiben in die RDBMS den "Path" pro Element ermittelt.
Leider gibt es beim Modell "Materialized path" einige Restriktionen - u.a. die Länge der PATH-Spalte restriktiert die Verzeichnisbaumtiefe, die Performance auf eine Text-Spalte mit LIKE ist nicht optimal u.v.m
Das führt uns zum Modell "Nested Set". In diesem Blogbeitrag wurde das Prinzip sehr einfach und verständlich erklärt - deshalb werde ich mich hierzu nicht weiter auslassen (DRY-Prinzip). Ich werde mich hier auf die Implementierung in Spring und Hibernate konzentrieren.
Das Resultat in der Datenbank sieht dann wie folgt aus:
Tabelle: FOLDER
+----+-------------+-----------+-----------+---------+----------+
| ID | NAME | PARENT_ID | NS_THREAD | NS_LEFT | NS_RIGHT |
+----+-------------+-----------+-----------+---------+----------+
| 1 | Parent1 | NULL | 1 | 1 | 6 |
| 2 | Child1 | 1 | 1 | 2 | 3 |
| 3 | Child2 | 1 | 1 | 4 | 5 |
| 4 | Parent2 | NULL | 4 | 1 | 8 |
| 6 | Child2 | 4 | 4 | 2 | 5 |
| 7 | ChildChild1 | 6 | 4 | 3 | 4 |
| 8 | Child1New | 4 | 4 | 6 | 7 |
+----+-------------+-----------+-----------+---------+----------+
Hier handelt es sich um eine spezielle "Nested set"-Implementierung ist. Es gibt neben den Spalten "NS_LEFT" und "NS_RIGHT" noch die Spalte "NS_THREAD".
Um hier einen Teilbaum zu erhalten genügt folgende SQL-Abfrage:
SELECT * FROM FOLDER WHERE NS_THREAD = 4 AND NS_LEFT BETWEEN 1 AND 8
Die Implementierung des Interceptors, des Modells sowie die Hibernate-Konfiguration könnt Ihr hier begutachten.
Was man also von einem "Einzeiler" aus Rails, CakePHP und anderen Frameworks kennt ist bei Hibernate wirklich ziemlich komplex zu implementieren. Hier stellt sich die Frage ob Hibernate das nicht etwas einfacher für den Benutzer (Programmierer) machen sollte.
Weitere Links zum Thema:
Posts
Ich stehe momentan genau vor diesem Problem. Ich habe eine Tabelle Component, mit einer parent_id auf sich selbst. Vereinfacht gesagt: Komponenenten können Komponenten beinhalten.
AntwortenLöschenJetzt habe ich festgestellt, dass wenn Hibernate eine Wurzelkomponente inklusive aller Unterkomponenten lädt, für jede Komponente ein Query an die Datenbank abfeuert. Da dies in der Anwendung die absolut am häufigsten gebrauchte Operation ist, brauche ich hierfür eine Alternative, um die Skalierbarkeit zu gewährleisten. Dabei bin ich auf deinen Blog-Eintrag gestoßen und er hat mir zum Verständnis des eigentlichen Problems sehr weiter geholfen. Vielen Dank dafür.
Werde mich nun an die Umsetzung machen und hoffe, dass das von dir verlinkte Beispiel weiterhilft. Ist dieser Code von dir?