Baumstruktur mit Rechten

[Mr_G]

Hallo zusammen,
ich glaube ich brauche mal ein par Anregungen. Es geht um folgendes: Ich bastel an einem PHP-Projekt mit einer Benutzerverwaltung, in dem ich eine Baumstruktur habe (in meinem Fall ein Menü), die in einer MySQL-Datenbank liegt. Nun soll aber nicht jeder Benutzer Zugriff auf die ganze Struktur haben. Dazu wollte ich einfach eine Relation einführen, die einen Knoten ggf. mit einem Benutzer in Verbindung bringt, wenn dieser bestimmte Zugriffsrechte hat (hierbei würde ich gerne auch eine mögliche Vererbung einbauen).
Nun stellt sich mir die Frage wie ich das ganze Heckmeck in die Datenbank bekomme. Für eine menüartige Baumstruktur würden sich ja Nested Sets anbieten aber die Farge ist, ob das Sinn macht, wenn ich die Struktur via "Rechteauslese" zerschnibbel. Eine andere Idee wäre einfach eine Tabelle zu nehemen und für jeden Knoten einen evtl. Vater anzugeben. Das zurechtschnibbeln könnte ich dann in PHP machen.
Ich bin für jeden Vorschlag dankbar...

[mkinzler]

Ich würde die Rechte in eine eigene Relation auslagern.

[Mr_G]

Zitat:

Zitat von Mr_G

...Dazu wollte ich einfach eine Relation einführen, die einen Knoten ggf. mit einem Benutzer in Verbindung bringt, wenn dieser bestimmte Zugriffsrechte hat...

Zitat:

Zitat von mkinzler

Ich würde die Rechte in eine eigene Relation auslagern.

Könntest du das noch etwas präzisieren, damit ich weiß ob sich das mit meiner Idee deckt?
Ich dachte eben an eine Tabelle mit KnotenID, BenuterID und Recht (+ evtl. Vererbung?)...

[mkinzler]

So hatte ich es auch gemeint. Wie meinst du die Vererbung auf Nutzer- oder Astebene?

[Mr_G]

Ich dachte an die Äste... also Knoten A hat für Benutzer X ein Recht, welches auf die Unterbäume weitervererbt wird.

[mkinzler]

Je nach implementierung der Baumanzeige ( Rekursion) ergibt sich das ja automatisch.

[Mr_G]

Das mag sein... die Frage ist wie macht man es am Besten?
Wenn man mit Nested Sets arbeitet und man die "Auslese" via SQL gestaltet wird man wohl für jeden Zweig mit Vererbung ein extra Query machen müssen. Das ist eher nicht so elegant oder? Also besser alles holen und mittels PHP verarbeiten? Dann wäre ja die Lösung ohne Nested Sets und mit VaterID angebracht...?

[mjustin]

Zitat:

Zitat von Mr_G

Ich dachte an die Äste... also Knoten A hat für Benutzer X ein Recht, welches auf die Unterbäume weitervererbt wird.

Ist das immer so? Falls ja, ok - was aber, wenn die Regeln komplizierter werden, zum Beispiel Rechte auf bestimmte Unterpunkte einzelnen Benutzern entzogen werden sollen ...

Rechteverwaltung ist ein sehr schönes Kapitel in der Unternehmenssoftwareentwicklung, die Delphi-Komponenten die ich bisher gesehen habe, waren alle recht einfach gestrickt (und daher mussten wir uns etwas eigenes bauen, das halbwegs funktioniert).


Falls ich es neu progrommieren würde: RBAC mit Rollenmappings fällt mir da als Ansatz ein, also Rollen die bestimmten Funktionen zugeordnet sind, und innerhalb der Benutzerverwaltung können die Benutzer einer oder mehreren Gruppen zugeordnet werden. Als Sahnehäubchen dient das Rollenmapping dazu, die Namen der Rollen im Programm mit den Rollennamen in der Benutzerverwaltung zu mappen.

Also User1 -> GruppeA -> Rolle1 -> Rechte

Konkret: 'Maier' in Gruppe 'Personalsachbearbeitung', diese Gruppe wird auf die Rolle 'Human Resources' gemappt, und dieser Rolle werden die Rechte zugeordnet.

[Mr_G]

Vielen Dank für die ausführliche Antwort!
Role Based Access Control hört sich ganz gut an, aber was mich noch interessieren würde ist wie das ganze in der Baumstruktur verankert wird?
Wichtig wäre mir auch noch ein Rat zum Thema Speicherung: In welcher Form lege ich den Baum am besten in der Datenbank ab und wo verarbeite ich das ganze am besten?
Momentan tendiere ich dazu einfach die ganze Struktur aus der Datenbank zu lesen und mittels PHP die Rechte darauf anzuwenden. Nur weiß ich nicht wie ich das mit der Vererbung hinbekommen soll.

[mkinzler]

Zitat:

Role Based Access Control hört sich ganz gut an

Das wäre die andere Variante der Vererbung

Zitat:

In welcher Form lege ich den Baum am besten in der Datenbank ab und wo verarbeite ich das ganze am besten?

Ich kenne mich mit MySQL nicht so aus (NestedSets). In FireBird würde ich das durch eine rekursive SP oder eine rekursiven CTE erledigen

Zitat:

Momentan tendiere ich dazu einfach die ganze Struktur aus der Datenbank zu lesen und mittels PHP die Rechte darauf anzuwenden

Kann man auch durch Joins in einem Aufwasch erledigen

[Mr_G]

Zitat:

Zitat von mkinzler

...Das wäre die andere Variante der Vererbung

Wie gesagt... ich habe noch nicht ganz verstanden wie dieses Konzept in (m)eine Baumstruktur integriert werden muss. Vielleicht kann mir das jemand nochmal verdeutlichen oder einen Link mit einem kleinen Beispiel geben.

Zitat:

Zitat von mkinzler

Ich kenne mich mit MySQL nicht so aus (NestedSets). In FireBird würde ich das durch eine rekursive SP oder eine rekursiven CTE erledigen

CTEs gibt es leider nicht. Eine SP wäre eine Möglichkeit... zu den Nested Sets: Es handelt sich eigentlich nur um ein Prinzip zum ablegen von Bäumen in relationalen Datenbanken (siehe hier und hier).

[mkinzler]

Eine Rechtvergabe per Rolle bedeutet nur, dass nicht eine Benutzer sondern eine Benutzergruppe das Recht zugeordnet bekommt.
Um das Prinzip um Rechte zu erweitern bedraf es einen Join auf die Rechtetabelle, dann fliegen die Äste ohne Recht raus

[omata]

Zitat:

Zitat von Mr_G

...
Wichtig wäre mir auch noch ein Rat zum Thema Speicherung: In welcher Form lege ich den Baum am besten in der Datenbank ab und wo verarbeite ich das ganze am besten?

klick

[Mr_G]

Danke für die weiteren Antworten...
Ich glaube ich leg mal los und bastel mir einen Entwurf. Den können wir ja dann immernoch diskutieren.
@omata: Deine SP ist mir zu monströs: Zwei Temporary Tables und wenn ich mich nicht irre zwei Verfahren die den Nested Sets "eher unterlegen" sind kombiniert... trozdem danke für den Link! *need input* :-D

[omata]

Zitat:

Zitat von Mr_G

Deine SP ist mir zu monströs: Zwei Temporary Tables und wenn ich mich nicht irre zwei Verfahren die den Nested Sets "eher ... unterlegen" sind kombiniert...

Ja, das hier alergisch auf Temporäre Tabellen reagiert wird kenne ich ja. In Wirklichkeit haben ich damit schon oft gigantische Geschindigkeitsoptimierungen erzeugen können.
Schade, das hier immer der interresante Gedanke, der sich hinter dieser Thematik und Vorgehensweise verbirgt nicht erkannt wird. Das hier zwei Temporäre Tabellen zum Einsatz kommen, liegt leider an der primitiven Art, wie MySQL mit INSERT-Statements argieren kann.
Der von dir angegebene Links stellt leider nur eine minimalistische Sicht der Dinge dar, wenn dir das reicht und du das erziehlen kannst, was du benötigst, ist das ja ausreichend.
Viel Erfolg bei der Umsetzung.

[Mr_G]

Zitat:

Zitat von omata

Der von dir angegebene Links stellt leider nur eine minimalistische Sicht der Dinge dar, wenn dir das reicht und du das erziehlen kannst, was du benötigst, ist das ja ausreichend.

Ich lasse mich immer gerne eines besseren belehren. Also immer her mit den Ideen.
Nach den Weihnachtstagen werde ich mal meinen Ansatz posten.
Bis dahin... und Frohe Weihnachten! :xmas:

[Mr_G]

So...
Ich hab mir nochmal ein par Gedanken gemacht aber ich bin immer noch nicht zu einer zufriedenstellenden Lösung gekommen. Ich habe daher mal meine Idee in ein Bild gefasst (siehe Anhang).
Nun zu meinem Ansatz: Die Knoten landen alle in einer Tabelle, wobei zu jedem Knoten der Parent gespeichert wird. Zum Ausgeben kann ich dann einfach alle Knoten aus der DB lesen und nach ihrem Parent sotiert in Arrays packen und ausgeben. Die Zugriffssteuerung (hier geht es um einen seperaten Verwaltungsbereich indem der Zugriff eingeschränkt werden soll) wollte ich mit einer Entity Rechte lösen, die die Ensprechenden Rechte-Attribute besitzt sowie ein Attribut ob das Recht vererbt werden soll. Um diese Rechte nun mit den Knoten zu verbinden dachte ich an eine Relation die zusätlich eine Information enthält von welchem Knoten aus das Recht ggf. geerbt wurde. Die Rechte werden dann über den vorgeschlagenen Zwischenschritt der "Rolle" einem Benutzer zugeordnet.
Das ganze soll das so funktionieren: Jedem Knoten können verschiedene Rechtedatensätze zugewiesen werden, die ggf. kombiniert werden. Füge ich einen Knoten ein, wird vorher beim Parent geprüft welche vererbten Rechte dieser besitzt und die Rechte werden direkt auch mit dem neuen Knoten verknüpft. Wird die Vererbung aufgehoben, werden anhand des Quell-Attributs der Relation einfach die vererbten Verknüpfungen aufgehoben. Einzig das aktivieren der Vererbung bei vorhandenen Unterknoten ist Problematisch. Meine Idee: Entweder das Neted-Set-Modell anwenden, sodass alle Unterknoten mit einer Abfrage ermittelt werden können, oder eine rekursive Stored Procedure.
Nun stellt sich mir natürlich die Frage ob dieser Ansatz überhaupt brauchbar ist? Ich habe so etwas noch nie gemacht und denke mir fehlt da etwas der Durchblick. Ich bin für jeden Rat dankbar!

[Mr_G]

Keiner einen Kommentar? *push* :duck:

P.S.: So wie es ausshieht ist eine rekursive SP unter MySQL gar nicht möglich... :(

[alcaeus]

Moin,

ich verwende momentan ein aehnliches System in meinen Applikationen und habe es so geloest:
Es gibt eine Tabelle, in der das Nested Set definiert ist - das kennst du ja bereits.
Es gibt nun eine weitere Tabelle, welche auf Gruppenbasis (auch Benutzer sind Gruppen) Rechte zuweist. Dabei gilt: wenn nichts da ist, darf der Benutzer gar nichts.

Ich lese nun als erstes mit einem Query alle IDs aus, die der Benutzer sehen darf (natuerlich in Abhaengigkeit seiner kompletten Benutzergruppen, das ist ein etwas haessliches Dingen). Anschliessend speichere ich es folgendermassen im Array:

Code:

while ($row = $db->fetchrow($result)) {
  $allowedNodes[$row['id']] = true;
}

Diese Loesung hat schonmal den Vorteil, dass du nicht mit in_array() pruefen musst sondern mit isset(), was natuerlich schneller funktioniert.

Anschliessend hol ich mir das Nested Set raus:

Code:

$sql = 'SELECT * FROM nested_set ORDER BY left_id ASC';
$result = $db->query($sql);

Hier verwende ich nicht eine Beschraenkung auf die ID, denn ein Benutzer soll ein Child nicht sehen, wenn er den Parent nicht sehen kann - egal wie die Zugriffsrechte aufs Child sind.

In einer Schleife pruefe ich dann die ganze Sache:

Code:

$treeNodes = array();
while ($row = $db->fetchrow($result) {
  if (isset($rightID)) {
    if ($row['right_id'] < $rightID) {
      continue;
    }
    else {
      unset($rightID);
    }
  }
  
  if (!isset($alloowedNodes[$row['id']])) {
    $rightID = $row['right_id'];
    continue;
  }

  // Restliche Verarbeitung
  $treeNodes[] = $row;
}

Wenn ich nun auf einen Node stosse, welchen der Benutzer nicht sehen darf, speichere ich mir die Right-ID und ueberspringe saemtliche Nodes, deren Right-ID kleiner ist als die gespeicherte (die also unter diesem "unsichtbaren" Node liegen). Sobald ich auf den folgenden Node treffe, loesche ich die gespeicherte Right-ID wieder und arbeite normal weiter.

Mein Tipp: lass die Finger von rekursiven Dingen bei solchen Strukturen. Sobald der Baum groesser wird wirds richtig haesslich, und selbst bei kleinen Baeumen bombardierst du den Server mit Queries, fuer die er bei MyISAM erstmal die ganze Tabelle sperrt. Da kanns dann ganz schoen heiss hergehn ;)

Greetz
alcaeus

[Mr_G]

Vielen Dank für die ausführliche Antwort!
Deine elegante Lösung hat mich überzeugt: Ich werde Nested Sets verwenden...
Nun würde ich meine Rechte noch gerne vererben. Es gäbe ja die Möglichkeit den "Rechte-Datensatz" nur einemal mit einem Knoten zu verknüpfen und dann bei der Verarbeitung des Baumes sich die Rechte zu "merken" und auf die Unterknoten anzuwenden, oder das vererbte Recht direkt mit allen Unterknoten zu verknüpfen, wie ich es bis dato in etwa angedacht hatte (siehe #17).
Ich sehe die Vor- und Nachteile beim Zugriff: Werden oft einzelne Knoten nachgfragt sollte die direkte Verknüpfung besser sein (man muss nicht den ganzen Baum verarbeiten) - werden aber oft neune Knoten eingefügt und wird die Struktur oft verändert (ergo viele seperate Verknüpfungen müssten verändert werden) sollte das anwenden der Rechte bei der Verarbeitung besser geeignet sein, oder?

[alcaeus]

Moin,

du muesstest in dem Fall den Pfad zu einem Knoten einfach speichern und im Falle von nicht vorhandenen Rechten einfach diesen Pfad hochgehn bis du Rechte findest :)

Greetz
alcaeus

[Mr_G]

Hmm... den ganzen Pfad mag ich eigentlich nicht im Knoten speichern.
Wenn ich den ganzen Baum da hätte (also in PHP) könnte ich natürlich einfach "hochwandern" ... Der Vorteil bei den "zusätlichen Verknüpfungen" wäre vielleicht, dass ich dann einfach mit einer Abfrage sofort die Knoten bekomme zu denen die entsprechenden Rechte existieren.
Achje... immer diese Grundsatzentscheidungen :roll:

[alcaeus]

Moin,

du speicherst den Pfad natuerlich nicht in der Datenbank, sondern fuehrst ihn als Stack mit sobald du die ganzen Elemente im Baum durchgehst. Gleich am Anfang draufpushen, am Ende runterpoppen. Du musst allerdings irgendwie erkennen, wann du mehrere Elemente ausm Stack rausnehmen musst weil du mehrere Ebenen nach oben gehst ;)

Irgendwo hatte ich glaubich mal was dafuer liegen, aber ich bin momentan zu sehr in Urlaubs- und Wochenendsstimmung als dass ich mir darueber viele Gedanken machen will :angel:

Greetz
alcaeus

[Mr_G]

Kein Ding...
Ich schreib mir nun noch mal genau auf was ich (wie) erreichen möchte. Dann wäge ich ab. Mal sehen was dann bei rauskommt. :mrgreen:

P.S.: Schönes Wochende wünsch ich :dancer:

[Mr_G]

So... ich tendiere momentan zu einer Lösung, bei der die Verarbeitung via PHP laufen würde und ich mir also den gesamten Baum hole.
Der Vorteil: Ich erspare mir evtl. Komplikationen bei den vielen Verknüpfungen.
Der Nachteil: Ich muss immer den ganzen Baum holen.
Ich kann mich immernoch nicht 100% durchringen so loszucoden. Wie wird das denn in bestehenden Systemen gelöst?