Stammbaum mit 2 Eltern abbilden

[cell]

Hallo Leute,

Wie der Titel schon verrät, versuche ich einen Stammbaum mit 2 Eltern in der Datenbank abzubilden.

Ich habe dies bereits mit dem "Vaterzeiger" realisiert, wobei zu jeden element die ID des Faters und der Mutter gespeichert wird.

Zu jeden Element gibt es eine Vielzahl von Eigenschaften (25 - 40 ca. - die meisten sind decimal oder string). Derzeit habe ich ca 20000 Testeinträge.

Dazu gibt es eine Suche. Funktioniert alles wunderbar^^.

Probleme macht aber die Suche wenn ich nach Werten Suche die erst (rekursiv) berechnet werden müssen.

Da meine Skripte und Datenbank schon etwas komplexer sind werde ich es euch an einem vereinfachten Beispiel erklären:

- zu allen Elementen gibt es eine Eigenschaft Farbe und Größe

- Kind (rot, 10)<- Vater (rot, 15), Mutter (blau, 6) <-Opa1 (gelb, 9), Oma1 (rot, 11), Opa2 (rot, 12), Oma2 (blau, 8)

- bei "such mir alle, die mit einen Farbanteil von > 20% und Größe < 12,5"

- die Werte sind fiktiv und bei der Berechnung wird immer 50% von Mutter und 50% vom Vater genommen

=> in diesn Fall hat das Kind die Werte (rot 50%, blau 25%, gelb 25%)

Nun rechnt und rechnet und rechnet der Webserver umher und es dauert bis man ergebnisse bekommt, da er ja die Berechnung für jeden Eintrag machen muss.

Meine Ideen zur Verbesserung:

-----------------------------

Nested Sets -> klappt nicht

Ich habe schon überlegt ob ich irgendwie Nested Sets anwenden kann. Leider hab ich da keine Möglichkeit gefunden, da es bei mir die Zuordnungen mehrdeutig sind (1 oder 2 Eltern zu jeden Element und jedes Element kann mehrere Kinder haben - wie bein Mensch).

Speicherung der berechneten Werte:

-----------------------------------

Einmal zu jeden Element alle prozentualen Werte anhand der Vorfahren berechnen und zu dem Element abspeichern. Dadurch würde die Suche bestimmt um einiges schneller laufen, aber die Werte müssen immer für einen kompletten Baum neu berechnet werden sobald ein Element geändert wird. Außerdem stell ich es mir fehleranfällig vor.

Habt ihr vielleicht einen besseren Lösungsvorschlag oder eine Idee wie ich die Suche etwas verbessern kann?

Ich danke schonmal im vorraus für eure Hilfe.

[flashpixx]

Wenn ich das jetzt richtig verstehe hast Du einen Baum der noch zusätzliche Attribute enthält. Also ich würde die Datenstruktur von dem Baum getrennt von den Attributmengen speichern.

Die Berechnung sehe ich nicht so an, als dass Du immer den kompletten Baum neu generieren musst. Auch hier wieder nach meinem Verständnis hast Du die Kanten im Baum mit Werten belegt. Wenn sich jetzt nun der Wert an einem Knoten ändert, dann musst Du nur den Teilbaum unterhalb des Knoten bzw. bis zur Wurzel neu generieren, d.h. nur die Knoten die auf dem Pfad liegen, müssen verändert werden.

Für die Suche würde man die Daten, in denen man sucht, außerhalb des Baumes speichern und eben nur bei Änderung des Baumes anhand des Pfades neu berechnen, d.h. die Suche würde erst auf auf der Attributmenge einschränken. und da jeder Eintrag genau ein Element im Baum hat, musst Du dann nur von den eingeschränkten Knoten den Baum aufbauen.

Man kann die Struktur schon als Nested Setz Speichern, wobei man dann eben 2 Bäume vorhält. Und zwischen den Mengen dann entsprechende Kanten zieht, wie sie korrespondieren. Halte ich aber für weniger sinnvoll.

Bearbeitet 14. März 2011 von flashpixx

[cell]

Den Stammbaum getrennt von den restspeichern bringt schon was. Hab ich auch gemacht.

Als Nested Sets speichern klappt aber nicht, da es eine m zu n Beziehujng (0 bis max 2 Eltern zu jeden Element, welches n Kinder haben kann) ist. Mit genau einem Kind würd es vielleicht klappen, aber nicht mit mehr.

[flashpixx]

Als Nested Sets speichern klappt aber nicht, da es eine m zu n Beziehujng (0 bis max 2 Eltern zu jeden Element, welches n Kinder haben kann) ist. Mit genau einem Kind würd es vielleicht klappen, aber nicht mit mehr.

Die Beziehung ist nicht m:n sondern 1:n. Ein Elternelement kann n Kindelemente haben und das lässt sich mit einem Nested Set abbilden. In Deinem Fall hast Du eben zwei Nested Sets, einmal für die Väter und einmal für die Mutter, wobei dann die Kindeinträge immer auf das gleiche Element verweisen. Weiterhin wäre es auch sinnvoll gar nicht die Unterscheidung zwischen Mutter / Vater zu machen, sondern einfach einen Elterneintrag zu generieren, der wieder auf Einträge in der Personenentity verweist. Somit hat dann ein Kind, genau einen Vaterknoten, was sich exakt als Nested Set modellieren lässt