Artikel-Struktur in DB: Pro, Contra, Umsetzung

[patrick c]

Guten Spätnachmittag,

ich habe eine Frage zur Abbildung von einer Artikel-Struktur in einer DB-Tabelle (falls es relevant ist: MySql).
Die Struktur erfordert eine eindeutige Reihenfolge für jede Ebene.
Es gibt n-Ebenen.
Jeder Artikel hat einen Namen und die Ebene ist bekannt, Namen können mehrmals auftauchen (ein Artikel über Klima kann unter verschiedenen Länderkategorien vorhanden sein).
Das ganze soll möglichst effizient sein.
Auch zu beachten folgende Anforderung:
Zum Aufbau der Menüführung müssen leicht alle Ebenen geöffnet bis zum Aktuellen Artikel und dessen direkte Unterkategorie "ausgeklappt" ermittelbar sein.

Bisjetzt habe ich folgende 3 Möglichkeiten, mit ihren Vor- und Nachteilen:

• NestedSets: schneller lesender Zugriff, eindeutige Reihenfolge, komplizierter manipulierender Zugriff
      Wie die erforderten Einträge zur menüführung einfach herausfinden?
      Über Ebene und Name des Aktuellen "Pfades" und den Weg dorthin z.B. Kontinent -> Land -> Wetter kann ich nicht wirklich schön überprüfen, ob der Pfad existiert.
• Pfad speichern z.B. 1.3.4.5.2: Reihenfolge nur schwerlich festzulegen, da komplette Tabelle geändert werden müsste, begrenzte Möglichkeiten.
      Für Abfrage der Menüführung recht komfortabel.
      Pfad kann auch recht einfach überprüft werden.
      Geschwindigkeitsproblem?
• id/parent-id: rekursive mehrfache Abfragen notwendig, zusätzliche Spalte für Reihenfolge
      Abfragen relativ simpel.
      Pfad kann relativ unkompliziert validiert werden.

Also spricht wohl alles für Pfad oder id/parent-id. Doch für große Strukturen kommen diese wohl nicht in Frage. Kann mir jemand für meine Entscheidung Erfahrungen, Tips, Meinungen geben? Oder kann gar für meine Probleme mit NestedSets mir weiterhelfen, da mir NestedSets für sowas eigentlich immer im Kopf vorschwebten.

Ich bin gespannt auf Meinungen oder andere/neue Konzepte, mir fällt die Entscheidung schwer, da ich für meinen Einsatz teilweise Umsetzungsprobleme sehe.

Grüße
pc

[Frank (no reg)]

Hallo,

ich habe eine Frage zur Abbildung von einer Artikel-Struktur in einer DB-Tabelle (falls es relevant ist: MySql).

Im späteren sicherlich.

Die Struktur erfordert eine eindeutige Reihenfolge für jede Ebene.
Es gibt n-Ebenen.
Jeder Artikel hat einen Namen und die Ebene ist bekannt, Namen können mehrmals auftauchen (ein Artikel über Klima kann unter verschiedenen Länderkategorien vorhanden sein).

Du willst also von mehreren Stellen auf dasselbe Objekt verweisen?

• von unterschiedlichen Ebenen und Zweigen
• gleiche Ebene aber verschiedene Zweige

Das ganze soll möglichst effizient sein.

Das ist relativ und kann nicht pauschal beantwortet werden.

Auch zu beachten folgende Anforderung:
Zum Aufbau der Menüführung müssen leicht alle Ebenen geöffnet bis zum Aktuellen Artikel und dessen direkte Unterkategorie "ausgeklappt" ermittelbar sein.

Eine Datenbank kennt kein "ausklappen". Das ist Frontend-Logik (Bereich View vom MVC).

Bisjetzt habe ich folgende 3 Möglichkeiten, mit ihren Vor- und Nachteilen:

• NestedSets: schneller lesender Zugriff, eindeutige Reihenfolge, komplizierter manipulierender Zugriff

Ja, wäge doch mal ab, was öfter vorkommt. Wieviel manipulierende Operationen hast du? Was vielleicht ein Schwachpunkt ist, es muss immer den gesamten Baum updaten. Bei 100'000 Datensätzen könnte das dann schon was ausmachen. Von wieviel Datensätzen reden wir?

In NestedSets würde ich die Payload-Daten, also die echten Nutzdaten so gering wie möglich halten, z.b. nur eine ID, welche den "Artikel" eindeutig identifiziert. Dies hält das Datenvolumen klein.

• Pfad speichern z.B. 1.3.4.5.2: Reihenfolge nur schwerlich festzulegen

Was machst du bei 1.3.4.5.3.2.5? Ist die 3 an 2. Stelle dieselbe 3 wie an 5. Stelle?

Für Abfrage der Menüführung recht komfortabel.

Ah ... ja?

Geschwindigkeitsproblem?

Was verleitet dich zu dieser Annahme?

• id/parent-id: rekursive mehrfache Abfragen notwendig, zusätzliche Spalte für Reihenfolge

Sicherlich eine gangbare Alternative.

Abfragen relativ simpel.

Woher stammt deine Ansicht? Was für Abfragen? Was ist mit "Gib alles was auf Ebene 5 ist"? ... Ebene 5 ist eine Element was auf ein Elternelement, welches auf ein Elternelement, welches auf ein Elternelement, welches auf ein Elternelement ohne Elternelement verweist. Wie willst du das in einer einzigen Abfrage machen?

Gruss, Frank

[patrick c]

Abend,

danke für die Antwort.

Die Struktur erfordert eine eindeutige Reihenfolge für jede Ebene.
Es gibt n-Ebenen.
Jeder Artikel hat einen Namen und die Ebene ist bekannt, Namen können mehrmals auftauchen (ein Artikel über Klima kann unter verschiedenen Länderkategorien vorhanden sein).

Du willst also von mehreren Stellen auf dasselbe Objekt verweisen?

• von unterschiedlichen Ebenen und Zweigen
• gleiche Ebene aber verschiedene Zweige

Nein nicht dasselbe Objekt, aber ein Artikel, der womöglich den gleichen Namen wie ein anderes Objekt in einem beliebigen anderen Zweig und einer beliebig anderen Ebene hat.

Auch zu beachten folgende Anforderung:
Zum Aufbau der Menüführung müssen leicht alle Ebenen geöffnet bis zum Aktuellen Artikel und dessen direkte Unterkategorie "ausgeklappt" ermittelbar sein.

Eine Datenbank kennt kein "ausklappen". Das ist Frontend-Logik (Bereich View vom MVC).

Ich meinte hiermit, dass ich auch nur diesen Teil des "ausgeklappten" Baumes gerne möglichst einfach aus der Tabellenstruktur aubfragen können möchte, ohne den kompletten Baum abfragen zu müssen. (z.B. bei NestedSets wüsste ich nicht, wie das möglich ist.

• NestedSets: schneller lesender Zugriff, eindeutige Reihenfolge, komplizierter manipulierender Zugriff

Ja, wäge doch mal ab, was öfter vorkommt. Wieviel manipulierende Operationen hast du? Was vielleicht ein Schwachpunkt ist, es muss immer den gesamten Baum updaten. Bei 100'000 Datensätzen könnte das dann schon was ausmachen. Von wieviel Datensätzen reden wir?

Wir reden zwischen 3 und 4 stelliger Anzahl an Datensätzen.
Abgewägt ist schon: lesender Zugriff ist wesentlich häufiger und paar tausend Datensätze wird man schon aktualisieren können.
Jedoch scheinen mir die Abfragen für meine Anforderungen recht umständlich. Oben erwähnte Menustruktur wüsste ich nicht, wie ich Abfragen soll.

• Pfad speichern z.B. 1.3.4.5.2: Reihenfolge nur schwerlich festzulegen

Was machst du bei 1.3.4.5.3.2.5? Ist die 3 an 2. Stelle dieselbe 3 wie an 5. Stelle?

Es sind nicht dieselben.
Hierbei würde jeweils die n-te mit Punkt abgetrennte Zahl das Zahlte Element in der n-ten Ebene darstellen.

Abfragen relativ simpel.

Woher stammt deine Ansicht? Was für Abfragen? Was ist mit "Gib alles was auf Ebene 5 ist"? ... Ebene 5 ist eine Element was auf ein Elternelement, welches auf ein Elternelement, welches auf ein Elternelement, welches auf ein Elternelement ohne Elternelement verweist. Wie willst du das in einer einzigen Abfrage machen?

Garnicht. Ist aber in meinen täglichen Anforderungen auch nicht enthalten. ben genannte Menüstruktur wäre hier aber komfortabel Abzufragen.

Bin immer dankbar für neue Ideen, gerade im Bereich NestedSets, was mich einerseits überzeugt, scheitere ich einfach an so "täglichen" Aufgaben, wie den Pfad zu validieren oder oben erwähnten Teilbaum abzufragen.

Gruß
pc

[Vinzenz Mai]

Hallo,

Bin immer dankbar für neue Ideen, gerade im Bereich NestedSets, was mich einerseits überzeugt, scheitere ich einfach an so "täglichen" Aufgaben, wie den Pfad zu validieren oder oben erwähnten Teilbaum abzufragen.

schreibe eine Funktion

bool is_valid_path(partial_path)

und wende diese anschließend an.

Freundliche Grüße

Vinzenz

[patrick c]

Abend,

und was soll diese genau tun?

Erst den ganzen Baum Abfragen und in dann Namen für Name und Ebene für Ebene durchgehen und überprüfen, ob die Ebene jeweils eins Höher und die left und right jeweils innerhalb der übergeordneten liegen?

Ich meine, dass ich eine Funktion schreiben kann, die das erledigt, ist mir schon klar. Ich frage mich eher, wie ich einen NestedSets Pfad schon überprüfen kann.

Auch wie ich den Teilbaum, so wie ich ihn für das Menü möchte, aus NestedSets bekomme wüsste ich nicht. Ich bekomme das nicht aus einer Abfrage.

Gruß
pc

[Vinzenz Mai]

Hallo Patrick,

Auch wie ich den Teilbaum, so wie ich ihn für das Menü möchte, aus NestedSets bekomme wüsste ich nicht. Ich bekomme das nicht aus einer Abfrage.

dann machst Du etwas falsch, siehe z.B. http://www.klempert.de/nested_sets/#kap6

Ich sehe da weder ein Problem bei der Pfadüberprüfung mit einer einzigen SQL-Anweisung noch ein Problem, den Teilbaum zu bekommen. Und Performance sollte erst recht kein Problem sein.

Freundliche Grüße

Vinzenz

[patrick c]

Hallo,

also den Teilbaum mit Geschwister auf aktueller Ebene und Kinder eine Ebene tiefer, habe ich jetzt hinbekommen. (Link war echt hilfreich - Ebene mitspeichern erleichtert einiges)

Doch wie sollte eine einzige Abfreg für die Pfadüberprüfung aussehen?
Bsp.
Bekomme Daten für
Ebene 1 / Ebene 2 / Ebene 3
Jeweils ein Name ist Bekannt.
Europa / Deutschland / Berlin
Nun möchte ich also alle Elemente Abfragen, die Europa, Deutschland oder Berlin heißen und in Ebene 1, 2 und 3 liegen. Gleichzeitig müsste ich mich auf die jeweils vorherigen left und right Werte beziehen?

Gruß
pc

[Vinzenz Mai]

Hallo,

also den Teilbaum mit Geschwister auf aktueller Ebene und Kinder eine Ebene tiefer, habe ich jetzt hinbekommen. (Link war echt hilfreich - Ebene mitspeichern erleichtert einiges)

Doch wie sollte eine einzige Abfreg für die Pfadüberprüfung aussehen?
Ebene 1 / Ebene 2 / Ebene 3
Jeweils ein Name ist Bekannt.

was bedeutet das?

Europa / Deutschland / Berlin
Nun möchte ich also alle Elemente Abfragen, die Europa, Deutschland oder Berlin heißen und in Ebene 1, 2 und 3 liegen. Gleichzeitig müsste ich mich auf die jeweils vorherigen left und right Werte beziehen?

Nein. Du willst wissen, ob dies ein gültiger Pfad ist. Das ist etwas *ganz anderes*: Frage doch - wie auf der verlinkten Seite den Pfad von Berlin zur Wurzel ab und prüfe, ob Dein Pfad im Suchergebnis enthalten ist. 'ne einfache WHERE-Klausel, wo ist das Problem?

Freundliche Grüße

Vinzenz

[patrick c]

Morgen,

Doch wie sollte eine einzige Abfreg für die Pfadüberprüfung aussehen?
Ebene 1 / Ebene 2 / Ebene 3
Jeweils ein Name ist Bekannt.

was bedeutet das?

Es sind Namen bekannt, die durch alle Ebenen zum aktuellen Knoten/Blatt führen. Also ich weiß z.B. dass ich mich in der ersten Ebene innerhalb von Europa und unter Europa innerhalb von Deutschland und dort unter Berlin befinde.

Europa / Deutschland / Berlin
Nun möchte ich also alle Elemente Abfragen, die Europa, Deutschland oder Berlin heißen und in Ebene 1, 2 und 3 liegen. Gleichzeitig müsste ich mich auf die jeweils vorherigen left und right Werte beziehen?

Nein. Du willst wissen, ob dies ein gültiger Pfad ist. Das ist etwas *ganz anderes*: Frage doch - wie auf der verlinkten Seite den Pfad von Berlin zur Wurzel ab und prüfe, ob Dein Pfad im Suchergebnis enthalten ist. 'ne einfache WHERE-Klausel, wo ist das Problem?

Das geht nur so, wenn ich ausschließen kann, dass es in Ebene 3 mehr als ein Element mit dem Namen Berlin gibt. Das ist aber wie gesagt nicht der Fall, also muss ich die Validierung von "unten" her durchgehen und daran scheitere ich.

Gruß

[Vinzenz Mai]

Hallo Patrick,

Europa / Deutschland / Berlin

Das geht nur so, wenn ich ausschließen kann, dass es in Ebene 3 mehr als ein Element mit dem Namen Berlin gibt.

Nein, das ist nicht erforderlich. Es geht um den Pfad. Nicht nur um das Element in Ebene 3. Und Du kennst den Pfad.

Das ist aber wie gesagt nicht der Fall, also muss ich die Validierung von "unten" her durchgehen und daran scheitere ich.

Weil Du viel zu kompliziert denkst. Es ist doch ganz einfach:

• Gib mir alle Pfade, die in der dritten Ebene Berlin haben,
    wobei der Pfad wie angegeben aussehen soll

Ist die Ergebnismenge nicht leer, ist alles in Butter.
  Ist die Ergebnismenge leer, dann war es ein ungültiger Pfad.

Wo bitte, ist das Problem?
Warum löst diese einfache WHERE-Klausel nicht Dein Problem?

Beispiel: die Pfade

Asien / China / Berlin
    Europa / Österreich / Berlin
    Mars / Utopia / Berlin

erfüllen nicht die WHERE-Klausel.

Amerika / USA / Berlin

könnte sie erfüllen. Dann wäre es aber auch ein legaler Pfad.

Freundliche Grüße

Vinzenz

[Frank (no reg)]

Hi,

na wozu hast du die Left und Right Werte? Nimm die in der höchsten Ebene (wo Left und Right unterschiedlicher als unterschiedlich sind) und selektiere alle Knoten deren Left und Right innerhalb dieser Spanne liegt. Oder was willst du?

Dieser Zusammenhang:

Jeweils ein Name ist Bekannt.
Europa / Deutschland / Berlin
Nun möchte ich also alle Elemente Abfragen, die Europa, Deutschland oder Berlin heißen und in Ebene 1, 2 und 3 liegen.

will sich mir nicht so recht erschliessen.

Ein Name pro Ebene?

Die Elternknoten desselbigen haben Left und Right Werte, welche alle beide grösser sind als die Left und Right Werte des aktuellen Knotens. Das kann man auch umkehren, nur so als Tipp.

Nur um dich zu verwirren: Und wenn du das ganze als XML speicherst? XML hat gewissen Vorteile für hierarchische Daten gegenüber relationalen Datenbanken.

Ciao, Frank

[patrick c]

Morgen

na wozu hast du die Left und Right Werte? Nimm die in der höchsten Ebene (wo Left und Right unterschiedlicher als unterschiedlich sind) und selektiere alle Knoten deren Left und Right innerhalb dieser Spanne liegt. Oder was willst du?

Ich möchte ja nicht alle Kindknoten.

Dieser Zusammenhang:

Jeweils ein Name ist Bekannt.
Europa / Deutschland / Berlin
Nun möchte ich also alle Elemente Abfragen, die Europa, Deutschland oder Berlin heißen und in Ebene 1, 2 und 3 liegen.
will sich mir nicht so recht erschliessen.

Ein Name pro Ebene?

Jeder Knoten/jedes Blatt hat einen Namen, der zusätzlich zu left, right und ebene in der Tabelle zu finden ist. Ich erhalte jetzt einen "Pfad" in Form von Namen, die mich durch die Knoten zu dem aktuellen Knoten/Blatt führen sollen.
Beispielsweise wird durch Europa/Deutschland/Berlin gesagt, dass ich in der ersten Ebene innerhalb des Knotens Europa nach Deutschland suchen muss und von dessen Kindern nach Berlin.

Die Elternknoten desselbigen haben Left und Right Werte, welche alle beide grösser sind als die Left und Right Werte des aktuellen Knotens. Das kann man auch umkehren, nur so als Tipp.

right Wert muss größer sein, aber left Wert doch kleiner.

Nur um dich zu verwirren: Und wenn du das ganze als XML speicherst? XML hat gewissen Vorteile für hierarchische Daten gegenüber relationalen Datenbanken.

Das hatte ich auch schon überlegt. Jedoch habe ich für meinen Anwendungsfall auch keine Vereinfachung oder Vorteile gesehen und Angst um die Performance bei bis zu paar tausend Einträgen.
Außerdem wüsste ich auch keine geeignete XML-Struktur.

Gruß
pc

[Frank (no reg)]

Hallo,

den Pfad solltest du mit einem simplen GROUP_CONCAT hinbekommen.

Nehmen wir einfach mal den Zweig Welt, Europa, Deutschland, Berlin

Left, Right, Payload
------------------------------
[ 1] [14] Welt
 [ 2] [ 7] Europa
  [ 3] [ 6] Deutschland
   [ 4] [ 5] Berlin
 [ 8] [13] Amerika
  [ 9] [12] USA
   [10] [11] San Diego

Bei "Welt" sind Left und Right am unterschiedlichsten, also ist das der Wurzel Knoten. Bei "San Diego" und "Berlin" sind Left und Right nur 1 auseinander, das ist nur bei Endknoten so.

Wenn du jetzt abfragst: gib mir alles in Europa, fragst du technisch gib mir alles, wo Left und Right innerhalb von Left=2 und Right=7 liegen. 3,6 und 4,5 liegen beide vollständig darin. Das selbe Spiel kannst du mit Welt oder Amorika machen.

Alles was du dann noch für den Pfad brauchst, ist eine Aggregationsfunktion wie GROUP_CONCAT.

Bevor du dir Sorgen über Performance machst, solltest du dir Sorgen machen, deine Anforderungen überhaupt umsetzen zu können.

Cheers, Frank