Hierarchien speichern - und das versioniert

[syntor]

Hallo

Ich möchte eine hierarchische Datenstruktur versioniert speichern.
Dabei ist es wichtig, dass der Baum sortiert ist, und dass die Reihenfolge für jede Version gespeichert wird. Des Weiteren möchte ich in der Lage sein, eine Art "pointer" zu haben, mit welchem ich einen Teilbaum als Kind eines Knoten einblenden kann. Das letzte was mir noch in den Sinn kommt ist, dass die Laufzeit linear sein soll. Ich möchte also nicht für n Knoten mit Grad X n-mal Kindsknoten abrufen müssen. Dasselbe soll auch für beliebig tiefe Verschachtelungen durch Pointer möchglich sein.

Operationen wie das Verschieben ganzer Teilbäume, umsortieren oder einfügen neuer Knoten soll "billig" sein, auch beim erstellen eines Snapshots soll nicht der ganze Baum dupliziert werden müssen.

Ich habe bereits eine Implementation in PHP von all dem, die ziemlich zuverlässig funktioniert. Nun möchte ich diese nach Python portieren und habe mir gedacht, ich frage hier mal nach, was es denn für Verbesserungsvorschläge gibt. Alle Daten werden in einem RDBMS gespeichert. Dazumals habe ich lange im Internet gesucht, hatte aber kein vergleichbares Projekt gefunden, das versionierte Baumstrukturen in einer Datenbank ablegen kann, mit den Kriterien die ich mir gesetzt hatte.

Hier eine kurze Skizze meines Datenbankmodells:
Knoten
Diese Tabelle beinhaltet alle Knoten. Das einzig wirklich notwendige Feld hier ist eine ID, die dann als Fremdschlüssel referenziert werden kann.
Versionen
Die verschiedenen Versionen werden durchnummeriert.
Beziehungen
Es wird vermerkt, von welchem Knoten zu welchem eine Beziehung besteht, die Distanz/Tiefe wird auch gespeichert. (ancestor, descendant, depth) Für jeden Knoten existiert immer zumindest eine Beziehung zu sich selbst (Tiefe 0) und je eine Beziehung zu jedem Nachfahren (lies: Nachfahre, nicht Kind). Da ich jeweils alle Beziehungen zu Nachfahren speichere, kann ich einfach einen ganzen Teilbaum auf einmal auslesen. Für jede Beziehung werden ausserdem zwei Versionsnummern gespeichert: Die Nummber, ab welcher diese Beziehung Gültigkeit erhält, und eine "Verfallsnummer". null heisst, dass sie auch in der neusten Version noch gültig ist.
Sortierung
Zuordnung: Knoten Id -> Position, die Versionierung ist gleich aufgebaut wie bei den Beziehungen.
Pointer
Dies ist genau gleich aufgebaut wie die Beziehungen. Es ist eine Art Dependency-Tree zwischen den Verschiedenen Bäumen, der komplett aufgelöst wird.

Mit diesem Modell kann ich einen neuen Snapshot machen, indem ich einfach bei allen neuen Änderungen, eine neue Versionsnummer setze. Verschieben und einfügen geschieht relativ einfach (vergleiche mit nested sets).
Ich hoffe ich habe meinen Ansatz schon detailliert genug beschrieben, damit man etwa sehen kann, wie es funktioniert.
Ich denke, dass es sinnvoll ist, das einmal so zu posten, und auf Feedback zu warten, um zu sehen, wie das Verständnis für das bis jetzt geschriebene ist. Vielleicht habt ihr ja auch so einen tollen Ansatz, ohne sich auf meinen zu beziehen.

Etwas das mir am jetzigen Ansatz gar nicht gefällt ist, dass die Versionierung "linear" ist, es werden keine Branches unterstützt.

[noisefloor]

Hallo,

was mir spontan dazu einfüllt sind drei Sachen:

a) Graph Datenbank
b) Key-Value Store mit "geschickter" Wahl der Namen des Keys
c) XML

Abgesehen davon: Dein Projekt steht und fällt ja mit der Struktur der DB. Die Programmiersprache ist IMHO zweitrangig. Daher sollte der Port von PHP auf Python eigentlich ohne weitere möglich sein.

Gruß, noisefloor

[sparrow]

Hallo,

da hier noisefloor das Thema Graph-Datenbanken und nosql angesprochen hat zwei Links zu Podcasts die ich in letzter Zeit sehr interessant fand:


http://blog.radiotux.de/2011/01/09/bina ... r-1-nosql/
http://blog.radiotux.de/2010/12/13/sendung-graphdb/


Vielleicht hast du ja Zeit die Sendungen zu hören, sie sind auf jeden Fall recht informell.


Gruß
Sparrow

[syntor]

@nosiefloor:
a) ist sehr interessant, aber ich möchte, dass es ohne spezielle Zusatzsoftware läuft.
b) Ich verstehe nicht, wie ich das auf mein Problem anwenden soll.
c) Du denkst, eine XML Datei pro Baum? Und eine pro Version? Wie würde ich die Pointer effizient realisieren, wenn nicht über eine zusätzliche Datenbank-artige Struktur?

@sparrow: Vielen Dank, die werde ich mir sicher einmal anhören. Nur ist halt hier auch dasselbe Problem wie bei a) - Ich möchte eben, dass ich solche Bäume auch bei kleinen Websites einsetzen kann.

Was die Programmiersprache betrifft: Die Portierung an und für sich ist nicht das Problem, aber da ich sowieso alles neu schreiben muss, dachte ich, dass ich ja ein paar Dinge verbessern - oder gar einen ganz anderen Ansatz wählen könnte.

[lunar]

Vielleicht hast du ja Zeit die Sendungen zu hören, sie sind auf jeden Fall recht informell.

Na, hoffentlich sind sie auch informativ

[noisefloor]

Hallo,

Ich verstehe nicht, wie ich das auf mein Problem anwenden soll.

Ein ziemlich gutes Beispiel ist in der [url="http://redis.io]Redis[/url] Doku: Klick. Interessant ist der Teil aber "Data Layout". Wichtig dabei: Wirf alles, was du im Kopf über RDBMS hast, beim Lesen über Bord. Ein KV-Store braucht einen anderen Ansatz beim DB-Layout.

Du denkst, eine XML Datei pro Baum? Und eine pro Version?

Na ja, bei Baumstruktur ist hier halt XML eingefallen. Über das _wie_ habe ich mir keine weiteren Gedanken gemacht.

Gruß, noisefloor

[syntor]

So, die Podcasts habe ich mir angehört, ist ja wirklich sehr interessant, auch Redis kam darin vor. Über Graphdatenbanken habe ich mir im Rahmen meiner Maturaarbeit Gedanken gemacht, das ist ja wirklich cool!
Ich denke, ich werde zuerst mal meine Bäume und Graphen nur für in-memory Gebrauch implementieren, also ohne Persistenz.