[VTV] Rekursive Knotenabfrage

[Igotcha]

Hallo zusammen,

ich arbeite viel mit dem VirtualTreeView, doch stehe momentan ziemlich auf dem Schlauch.

Für eine hierarchische Berechtigungsstruktur benötige ich auf jeder Knotenebene die Information darüber, welche Knoten (mit ihren IDs) darunter liegen, um diese in einer DB zu speichern.

Beispiel:

Delphi-Quellcode:

ID NAME                                           RIGHTS
01 Root_1                                         02, 03, 04, 05, 06
02   +------ Child_1                              03, 04, 05
03              +----- Child_11      
04              +----- Child_12                   05
05                        +-------Child_121
06   +------ Child_2

Im Programm soll das Einfügen von neuen Ebenen direkt im VTV möglich sein. Füge ich z.B. am Child_11 eine zusätzliche Ebene ein, ändern sich alle "RIGHTS" des Baums über diesem Knoten. Ein einfaches "Previous Node" geht aber nicht, da ja auch alle Nodes unter Child_1 und zwar dann wieder in Vorwärtsrichtung benötigt werden (in dem Fall 04 und 05).

Delphi-Quellcode:

ID NAME                                           RIGHTS
01 Root_1                                         02, 03, 04, 05, 06, 07
02   +------ Child_1                              03, 04, 05, 07
03              +----- Child_11                   07
07                        +-------Child_111
04              +----- Child_12                   05
05                        +-------Child_121
06   +------ Child_2

Hat da jemand evtl. einen Ansatz?

Danke und Grüße
Igotcha

[marabu]

Hallo,

wenn du die Knoten deiner TreeView direkt auf eine DB-Tabelle (ID, PARENT_ID, NAME, ...) abbildest, dann finden sich die Knoten-IDs, welche du unter RIGHTS aufgeführt hast, über eine rekursive Auswertung der PARENT_ID wieder - ohne dass du irgendetwas zusätzlich speichern musst.

Grüße vom marabu

[generic]

suche mal nach nested sets bzw. schau dir mal das hier an:
http://www.falafel.com/Blogs/tabid/1...6/Default.aspx

[Igotcha]

Zitat von marabu:

Hallo,

wenn du die Knoten deiner TreeView direkt auf eine DB-Tabelle (ID, PARENT_ID, NAME, ...) abbildest, dann finden sich die Knoten-IDs, welche du unter RIGHTS aufgeführt hast, über eine rekursive Auswertung der PARENT_ID wieder - ohne dass du irgendetwas zusätzlich speichern musst.

Grüße vom marabu

Nein, gerade das brauche ich ja nicht. Ich brauche nicht die Info, welcher Node, welchen Parent hat, sondern ich benötige die Information "Welche Kinder haben die Nodes über dem gerade eingefügten Node, bis hin zum Root-Node".

Wie gesagt, ich brauche das zur Abbildung einer Berechtigungsstruktur. Wenn ich also irgendwo einen Knoten einfüge (und genau zu diesem Zeitpunkt sollen die "RIGHTS" des eingefügten Knotens ermittelt und in die DB geschrieben werden), dann haben alle Nodes - ausgehend nach oben vom gerade eingefügten - natürlich auch die entsprechende Berechtigungen für die Knoten, die im gleichen Ast darunter liegen.

Und die Speicherung der Parent-ID pro Node bringt auch nichts, da dies eine 1:1-Beziehung ist. Aus diesem Grund habe ich das Beispiel oben gebildet: Beim Einfügen des Child_111 muss man eben nicht nur nach oben zu Root_1, sondern auch bei Child_12 nach unten gehen, um alle relevanten IDs zu ermitteln.

Gruß Igotcha

[marabu]

Hallo,

noch bin ich mir sicher, dass ich dein Problem verstanden habe. Die von mir angegebene Abbildung ist eine Standardlösung zur relationalen Speicherung rekursiver Strukturen, speziell von Bäumen. Es muss tatsächlich nur der PARENT_ID gespeichert werden um alle gewünschten Auswertungen zu ermöglichen. Insbesondere die von dir benötigten Schlüssel aller Knoten in einem beliebigen Teilbaum (ADG convex hull) lassen sich ermitteln. Manche RDBMS bieten SQL-Erweiterungen an, die solche Anfragen vereinfachen - bei anderen kann man mit Stored Procedures arbeiten. In Folge einer expliziten Speicherung der RIGHTS aus deinem Beispiel erhältst du eine sogenannte Update-Anomalie. Ich mag garnicht glauben, dass ich dein Problem falsch verstanden habe.

Freundliche Grüße

[Phoenix]

Zitat von Igotcha:

Und die Speicherung der Parent-ID pro Node bringt auch nichts, da dies eine 1:1-Beziehung ist. Aus diesem Grund habe ich das Beispiel oben gebildet: Beim Einfügen des Child_111 muss man eben nicht nur nach oben zu Root_1, sondern auch bei Child_12 nach unten gehen, um alle relevanten IDs zu ermitteln.

Also wenn man das so liest sagst Du eigentlich: "Egal wo ich was mache, es betrifft immer alle Knoten". Denn spätestens beim Rootnode sind die zugehörigen Childs nämlich alle.

Aber gehen wir mal davon aus, dass es so ist, wie Du Es im Beispiel gezeichnet hast: Hier wird die neue Berechtigung (07) nur auf dem Pfad hoch zum Rootnode gesetzt. Dir reicht also ParentNode vollkommen aus.

Sollte (obwohl es nicht eingezeichnet ist!) die Berechtigung 07 auch auf 12 und 121 gesetzt werden müssen, so kannst Du doch einfach für jeden Node den auf dem 'Hochweg' erwischst einfach alle Childnodes auch noch modifizieren. Das sind genau die Knoten, die den entsprechenden Node (in dem Fall 12) als Parent eingetragen haben (wie es bei 121 der Fall ist). Somit reicht Dir wieder ausschliesslich die Angabe des Parents.

Kurz gesagt: Über die Angabe des Parents bei jedem Node kannst Du jederzeit, von jeder Position aus, vollkommen frei durch den Baum navigieren und kannst immer jeden anderen Node im Baum erreichen.

[Igotcha]

Ich glaube das Problem ist noch nicht ganz klar geworden

Also mal im Ablauf:

Ein neuer Knoten wird im Programm im VTV eingefügt (hier der Child_111)

Daraufhin müssen folgende Dabenbankoperationen stattfinden:

a) Child_111 wird per INSERT eingefügt (und natürlich seine Parent_ID = 03 gesetzt - das passiert ja schon heute). Child_111 erhält vom DB die ID = 07

b) bei allen Nodes über Child_111 muss jetzt das Feld RIGHTS (und der entsprechende Record-Eintrag im VTV) upgedated werden

Node_ID 03 -> RIGHTS -> 07
Node_ID 02 -> RIGHTS -> 03, 04, 05, 07
Node_ID 01 -> RIGHTS -> 02, 03, 04, 05, 06, 07

c) das gleiche soll natürlich passieren, wenn man einen Node löscht.

Mein Problem ist jetzt: Wie bekomme ich bei b) die IDs 04, 05, 06 in die Nodes mit der ID 01 und 02, da ich ja nicht nur stur von Child_111 nach oben gehen kann, sondern pro Parent ja wieder abfragen muss, welche Kinder dieser hat, um die IDs nach oben "zu reichen".

Hintergrund: An die Nodes (IDs) werden relational Adressdaten gebunden. Die Berechtigungsabfrage erfolgt dann in der Form "SELECT * FROM adressen WHERE adress_right IN (hier steht der entsprechende Ausdruck aus 'RIGHTS')" so dass ich bei Auswahl eines Nodes im VTV alle zugeordneten Adressen aller Unterknoten erhalte.

Viele Grüße
Igotcha

[DGL-luke]

Hmm... warum trägst du nicht diese baumstruktur per einfachem nach oben verkettetem Baum (sagen wir einfach mal binary tree) in die DB ein (so wies jetzt schon ist, über ID und Parent_Id) und liest die Rechte dann dynamisch aus? Es muss ja bestimmte Abfrageszenarien geben, z.B. "alle Rechte bei Knoten x".

Die Rechte bei Knoten x ergeben sich ja aus den Werten bei sämtlichen leafs. das heißt, du gehst erkursiv durch deine Datenbank und suchst dir erst mal alle Knoten, deren Parent_Id x ist.
Dann gehst du diese Knoten durch und fragst "Ist dieser Knoten eni leaf"? Falls ja, liest du seinen Wert aus und fügst in in die ergebnismenge ein. falls nein, fängst du von vorne an: du suchst wieder alle Knoten, deren Parent_Id die Id dieses Knotens ist.

Das ist natürlich nicht besonders perfromant. Ich würde das deswegen in zwei Tabellen aufteilen, eine Tabelle mit leafs und eine tabelle, in die du einen binärbaum schreibst. dann kannst du dich zügig von Knoten x zu allen seinen childs durchhangeln.

Und einfügen in die db sollte auch nicht schwierig sein:

du suchst dir erst den knoten, an dem du einfügen willst(sei x). sind bereits beide Äste besetzt, erstellst du einen neuen Datensatz(sei y), dessen Parent_ID setzt du auf x. Das A-Feld von x setzt du auf y. Ans A-Feld von y hängst du nun einen neuen Datensatz, der nicht mehr weiter verzweigt sondern auf ein leaf verweist. Als B-Feld setzt du nun das, was gerade in der Luft hängt, nämlich das alte A-Feld von x.

Soweit verständlich?

Nochmal kurz:

BINARY_TREE ( INT id auto_increment, INT Parent, INT A, INT B, INT leaf)
LEAFS (INT id auto_increment, INT value)

Das kann man natürlich noch weiter optimieren, indem man das leaf-feld durch ein falg ersetzt, bei dessen gesetztheit A und B nicht mehr weiterverzweigen sondern leafs sind. die leafs-tabelle fällt dann weg und du musst beim durchrekursieren nur schauen, ob das flag gesetzt ist, falls nein, gehts weiter, falls ja, schreibst du die werte in deine ergebnismenge.

Alle Klarheiten beseitigt?

[Igotcha]

Zitat von DGL-luke:

Die Rechte bei Knoten x ergeben sich ja aus den Werten bei sämtlichen leafs. das heißt, du gehst erkursiv durch deine Datenbank und suchst dir erst mal alle Knoten, deren Parent_Id x ist.
Dann gehst du diese Knoten durch und fragst "Ist dieser Knoten eni leaf"? Falls ja, liest du seinen Wert aus und fügst in in die ergebnismenge ein. falls nein, fängst du von vorne an: du suchst wieder alle Knoten, deren Parent_Id die Id dieses Knotens ist.

Genau das ist mein Problemszenario

Eure Lösungen hier gehen aber von der Datenbank-Ebene aus. Meine gesuchte Lösung muss aber von der Userschnittstelle ausgehen und das Ergebnis wird in die Datenbank geschrieben.

Genau Deine beschriebene Vorgehensweise benötige ich technisch im VTV, da der Anstoß (Einfügen / Löschen eines Nodes) im Programm erfolgt (also die Aktion). Ich möchte nicht zuerst etwas in der Datenbank operieren, sondern den VTV (bzw. die einzelnen Nodes) entsprechend updaten und dann die Änderungen (zu genau diesem Node) in der DB updaten (die Reaktion).

Gruß Igotcha

[DGL-luke]

ok, alles klar. was genau hast du im vtv nicht, was du in der db brauchst? Schreibst du in eine column deines vtv alle berechtigungen rein?

Dann willst du wohl nicht von oben nach unten durchgehen, sondern von unten nach oben. ich mach mal ne zeichnung, zum selber durchüberlegen:

Code:

1 -       Berechtigungen A,B,C
 1.1 -     Berechtigungen A,B
  1.1.1 - Berechtigung A
  1.1.2 - Berechtigung B
 1.2 -     Berechtigungen C
  1.2.1 - Berechtigung C
2

Wenn sich dein modell so darstellen lässt, dann würde ich so vorgehen:

Angenommen: Insert der Berechtigung "D" als node 1.2.2 - Pseudocode:

Delphi-Quellcode:

1. CurrNode := AddNode(Parent=1.2,Value="D");
2. CurrNode := CurrNode.Parent;
3. if assigned(currnode) then CurrNode.AddRight("D") else break;
4. goto 2;

Damit hast du dann beim Node 1.2 die berechtigungen C,D und bei Node 1 A,B,C,D.