DB-Abfrage bei Rechteverwaltung

[gow]

Hallo,

Ich hab mir für meine Webseite folgendes Rechtesystem einfallen lassen:

• Es gibt Rollen und untergeordnetet Rollen (so wie bei Drupal)

• Jedem Benutzer sind keine, eine oder mehrere Rollen zugeteilt

• Es gibt Kategorien und Unterkategorien für Dokumente, etc.

• Jeder Benutzer darf in einer Kategorie das tun, was in seinen
    zugeordneten Rollen und übergeordneten Rollen erlaubt ist und
    zwar in der erlaubten Kategorie und Unterkategorien.

All diese Daten sind in eine MySQL-DB gespeichert.

Nun mein Problem: Wie kann ich möglichst performant abfragen, ob der Benutzer eine bestimmte Aktion in einer Kategorie tun darf?

lg gow

[dedlfix]

Hi!

Ich hab mir für meine Webseite folgendes Rechtesystem einfallen lassen:

• Es gibt Rollen und untergeordnetet Rollen (so wie bei Drupal)
• Jedem Benutzer sind keine, eine oder mehrere Rollen zugeteilt
• Es gibt Kategorien und Unterkategorien für Dokumente, etc.
• Jeder Benutzer darf in einer Kategorie das tun, was in seinen
    zugeordneten Rollen und übergeordneten Rollen erlaubt ist und
    zwar in der erlaubten Kategorie und Unterkategorien.

Wenn man dazu mal einen kleinen Ausflug in die Grammatik macht, hast du gerade Subjekte und Objekte beschrieben, aber die Prädikate fehlen. Es kann aber auch sein, dass du diese implizit mit der Rolle verbunden hast, also die Rollen nicht Gast, Benutzer und Moderator heißen sondern Leser, Schreiber und Löscher. Mit Prädikaten ergäbe sich eine feinere Gliederung.

Subjekt                   Prädikat          [Objekt]
Welche Person(engruppe)   darf was machen   [an welchem/n Objekt(en)]?

So bildet man ja einfache Sätze und so kann man auch ein Berechtigungssystem aufbauen. Das Objekt steht in [Klammern], weil es optional ist. Es würde die Tätigkeiten eines Subjektes auf bestimmte Objekte einschränken. Beispielsweise darf ein Moderator dann nicht mehr alles löschen sondern nur die Beiträge in ausgewählten Foren/Themenbereichen/wasauchimmer.

All diese Daten sind in eine MySQL-DB gespeichert.
Nun mein Problem: Wie kann ich möglichst performant abfragen, ob der Benutzer eine bestimmte Aktion in einer Kategorie tun darf?

Das hängt ja nicht zuletzt davon ab, wie du deine Prosa von oben in eine konkrete Struktur umgesetzt hast. Oder ging es dir auch darum, eine brauchbare Struktur zu finden? Dann gib bitte ein paar konkrete Beispiele an.

Lo!

[gow]

Hallo,

Ich versuche es einmal mit Beispieldaten:

Tabelle group (Gruppe/Rollen)
+----+---------------+-----------+
| id | name          | parent_id |
+----+---------------+-----------+
| 0  | Alle          | 0         |   (Alle Benutzer)
+----+---------------+-----------+
| 1  | Redakteur     | 0         |
+----+---------------+-----------+
| 2  | Chefredakteur | 1         |
+----+---------------+-----------+
| 3  | Eventposter   | 0         |
+----+---------------+-----------+
| ...                            |
+----+---------------+-----------+

Ergiebt:
Alle
 Redakteur
  Chefredakteur
 abc

Tabelle category (Kategorien)
+----+--------------+-----------+
| id | name         | parent_id |
+----+--------------+-----------+
| 0  | (Alles)      | 0         |
+----+--------------+-----------+
| 1  | Nachrichten  | 0         |
+----+--------------+-----------+
| 2  | Welt         | 1         |
+----+--------------+-----------+
| 3  | Lokales      | 1         |
+----+--------------+-----------+
| 4  | Events       | 0         |
+----+--------------+-----------+

Ergiebt:
(Alles)
 Nachrichten
  Welt
  Lokales
 Events

Tabelle permission
+----------+-------------+-----------------+
| group_id | category_id | what            |
+----------+-------------+-----------------+
| 0        | 0           | readpublished   |  (Jeder darf alle veröffentlichte Dinge lesen)
+----------+-------------+-----------------+
| 1        | 1           | add             |  (Redakteure dürfen Artikel in Kategorie "Nachrichten" hinzufügen)
+----------+-------------+-----------------+
| 1        | 1           | read            |  (Redakteure dürfen alles Lesen)
+----------+-------------+-----------------+
| 2        | 1           | publish         |  (Chefredakteure dürfen Artikel in Kategorie "Nachrichten" veröffentlichen)
+----------+-------------+-----------------+
| 3        | 4           | add             |  (Eventposter dürfen Artikel in Kategorie "Events" hinzufügen)
+----------+-------------+-----------------+
| 3        | 4           | publish         |  (Eventposter dürfen Artikel in Kategorie "Events" veröffentlichen)
+----------+-------------+-----------------+

Außerdem dürfen Benutzer der Gruppe Chefredakteur Artikel in Kategorie "Nachtrichten" hinzufügen.

Die Tabellen müssen nicht so aufgebaut sein, wenn eine andere Strukturierung besser wäre, bitte sagen.

Ist mein Problem jetzt verständlich?

lg gow

[dedlfix]

Hi!

Tabelle group (Gruppe/Rollen) [...]
Tabelle category (Kategorien) [...]
Tabelle permission [...]
Ist mein Problem jetzt verständlich?

Ja, so wie du das nun beschreibst, ist es das Subjekt-Prädikat-Objekt-Prinzip (Wer-darf-[was]). Als erstes müsstest du vom vorgegebenen Nutzer dessen Gruppenzugehörigkeiten ermitteln. Das ergibt zum Beispiel für ein Eventposter-Mitglied also Eventposter und Alle sowie für den ChefRed Chefredakteur, Redakteur und Alle beziehungsweise die jeweiligen IDs. Dann hast du ja ein Objekt oder auch nicht. Für dieses musst du die Kategorie-Zugehörigkeiten auf gleiche Weise ermitteln. Die Details dazu lass ich mal weg, denn zum Thema rekursives DBMS-Befragen dürftest du genügend Meinungen und Antworten finden.

Nun hast du also eine Liste der Gruppenzugehörigkeiten und eventuell eine für die Kategorien. Jetzt musst du zum gegebenen Prädikat (die auszuführende Tätigkeit) ermitteln, ob deren group_id und category_id in den beiden Listen enthalten ist.

Die Tabellen müssen nicht so aufgebaut sein, wenn eine andere Strukturierung besser wäre, bitte sagen.

Problematisch ist bei einem solchen Aufbau immer die Beziehung über den Parent-Zeiger, denn um alle Vorfahren zu ermitteln, benötigst du in der Regel mehrere Abfragen, was einen ziemlichen Overhead an Query- und Resultverarbeitung mit sich bringt. Aus Nested Sets lassen sich üblicherweise mit einem einzigen Statement die gewünschten Informationen abfragen, bedeuten aber einen erhöhten Aufwand beim Datenändern und beim Tabellenaufbau.

Des Weiteren ist der Wert 0 für eine ID eher ungebräuchlich, weil sie recht einfach mit NULL verwechselt oder NULL nach 0 getypecastet werden kann. Und zumindest für die Objekte/Kategorien benötigst du einen Wert, der ausdrückt, dass selbige keine Rolle spielen (z.B. für Admins und andere Götter). Hierfür könnte NULL (bevorzugt) oder 0 ein geeigneter Kandidat sein.

Lo!

[gow]

Hallo,

Ich hab mir auch schon überlegt Nested Sets zu verwenden, allerdings hab ich zuvor noch nie Nested Sets verwendet.
Wie hoch ist der Änderungsaufwand bei Nested Sets (auch bei sehr vielen Tabelleneinträgen)?

Bei welchen Datenumfang sollte welches Verfahren verwendet werden?

lg gow

[dedlfix]

Hi!

Ich hab mir auch schon überlegt Nested Sets zu verwenden, allerdings hab ich zuvor noch nie Nested Sets verwendet.
Wie hoch ist der Änderungsaufwand bei Nested Sets (auch bei sehr vielen Tabelleneinträgen)?

Wenn du das Prinzip mit dem L-R-Feldern verstanden hast, wirst du sicher bemerken, dass jedes Mal, wenn ein Element eingefügt oder entfernt wird, die L-R-Einträge mit größeren Nummern neu nummeriert werden müssen. Und damit das nicht zu Unfällen führt, muss man dafür sorgen, dass in der Zeit kein anderer Prozess auf den Datenbestand zugreifen kann.

Bei welchen Datenumfang sollte welches Verfahren verwendet werden?

Dazu kann ich mich nicht festlegen. Das hängt auch von der Tiefe der Verschachtelungen ab. Wenn du nur maximal ein oder zwei Vorfahren hast, dann kannst du auch mit Self-Joins oder Subquerys um die Runden kommen.

Lo!

[gow]

Hallo,

Und damit das nicht zu Unfällen führt, muss man dafür sorgen, dass in der Zeit kein anderer Prozess auf den Datenbestand zugreifen kann.

Und was ist, wenn das Script (aus welchen Grund auch immer) abgebrochen wird?
Ich müsste dann ja eine InnoDB verwenden, ist die nicht langsamer?

Dazu kann ich mich nicht festlegen. Das hängt auch von der Tiefe der Verschachtelungen ab.

Theoretisch könnten auch 15 Kategorien ineinander verschachtelt werden.
Allerdings gibt es aber ab einer gewissen Tiefe keinen sind mehr, also könnte ich das einschränken, falls das was bringt.

lg gow

[Tom]

Hello,

Und was ist, wenn das Script (aus welchen Grund auch immer) abgebrochen wird?
Ich müsste dann ja eine InnoDB verwenden, ist die nicht langsamer?

Das datenverändernde Script darf nicht abgebrochen werden, bevor es alle Änderungen vorgenommen hat.
Das kannst bzw. musst Du mittels ignore_user_abort() http://de3.php.net/manual/en/function.ignore-user-abort.php und connection_aborted() http://de3.php.net/manual/en/function.connection-aborted.php steuern.

Liebe Grüße aus dem schönen Oberharz

Tom vom Berg

[dedlfix]

Hi!

Und damit das nicht zu Unfällen führt, muss man dafür sorgen, dass in der Zeit kein anderer Prozess auf den Datenbestand zugreifen kann.
Und was ist, wenn das Script (aus welchen Grund auch immer) abgebrochen wird?

In welcher Hinsicht genau? Statements können natürlich nur soweit abgearbeitet werden, wie das Programm kommt. Eine gesperrte Tabelle bleibt aber nicht zurück, denn noch bestehende Sperren werden am Ende der Verbindung aufgehoben, und die Verbindung stirbt auf jeden Fall am Scriptende. Transaktionen sind hier auf alle Fälle sehr zu empfehlen.

Ich müsste dann ja eine InnoDB verwenden, ist die nicht langsamer?

Die Geschwindigkeitsunterschiede werden sicher nicht großartig über das Grundrauschen kommen. Ansonsten gibt es dazu sicher irgendwo im Netz einen Vergleich.

Dazu kann ich mich nicht festlegen. Das hängt auch von der Tiefe der Verschachtelungen ab.
Theoretisch könnten auch 15 Kategorien ineinander verschachtelt werden.
Allerdings gibt es aber ab einer gewissen Tiefe keinen sind mehr, also könnte ich das einschränken, falls das was bringt.

Jedes Level musst du extra mit der Information aus der vorigen Abfrage befragen. Diese Rekursion bleibt beim Parent-Ansatz immer erhalten. Du kannst lediglich bei sehr begrenzter Tiefe die Rekursion in einem Schritt vornehmen, indem du pro Level mindestens eine zusätzliche Subquery oder Self-Join einbaust. Das wird schnell unübersichtlich, weswegen es sich empfiehlt, das nicht weiter als bis 3 Verschachtlungen zu treiben. Rein technisch könnte man das bis zu den Limits von MySQL und PHP treiben.

Lo!

[gow]

Hallo,

Transaktionen sind hier auf alle Fälle sehr zu empfehlen.
[...]
Die Geschwindigkeitsunterschiede werden sicher nicht großartig über das Grundrauschen kommen.

Also würdest du InnoDB für die Tabelle category und group empfehlen?

lg gow

[gow]

Hallo,

Ich hab da eine Lösung für Nested Sets um nicht immer die ganze Tabelle modifizieren zu müssen.
Nun möchte ich wissen, was ihr davon haltet:

Es gibt ja, z.B. bei einer Kategorie-Hierarchie immer eine oberste Kategorie, die keine übergeordnete mehr hat. Man speichere also einfach pro Kategorie noch die Root-Kategorie und ändere nur mehr die lft und rgt-Werte der Kategorien mit derselben Root-Kategorie. Das System kann auch bei Gruppen-Hirachien angewendet werden.

lg gow

[dedlfix]

Hi!

Ich hab da eine Lösung für Nested Sets um nicht immer die ganze Tabelle modifizieren zu müssen.
Nun möchte ich wissen, was ihr davon haltet:

Es gibt ja, z.B. bei einer Kategorie-Hierarchie immer eine oberste Kategorie, die keine übergeordnete mehr hat. Man speichere also einfach pro Kategorie noch die Root-Kategorie und ändere nur mehr die lft und rgt-Werte der Kategorien mit derselben Root-Kategorie. Das System kann auch bei Gruppen-Hirachien angewendet werden.

Du willst also mehrere eigenständige Bäume aufbauen. Das kann man machen. Aber der Aufwand einer Änderung wird für dich als Programmierer nicht weniger, sondern sogar noch geringfügig höher, weil du nun auch noch die Root-Kategorie berücksichtigen musst. Lediglich das DBMS hat vielleicht ein bisschen weniger zu tun, weil es weniger Datensätze ändern muss. Dafür muss es jedoch eine weitere Bedingung beim Auswählen der Datensätze prüfen.

Ich erwarte nicht, dass das bei der anzunehmenderweise sehr geringen Anzahl an Kategorien insgesamt ins Gewicht fällt.

Lo!

[gow]

Hallo,

Ich erwarte nicht, dass das bei der anzunehmenderweise sehr geringen Anzahl an Kategorien insgesamt ins Gewicht fällt.

Und wie ist es bei einer großen Anzahl?
Es kann leicht sein dass ein paar hundert Kategorie-Bäume zusammenkommen, die selbst aber nicht so groß sind.
Wäre es geschwindigkeitssteigernd die root_cat_id zu einer Index-Spalte zu machen ?

lg gow

[dedlfix]

Hi!

Ich erwarte nicht, dass das bei der anzunehmenderweise sehr geringen Anzahl an Kategorien insgesamt ins Gewicht fällt.
Und wie ist es bei einer großen Anzahl?

Vermutlich nicht der Rede Wert. Ich nehme an, dass du die Kategorien nur selten änderst, also in deutlich größeren Abständen als minütlich.

Es kann leicht sein dass ein paar hundert Kategorie-Bäume zusammenkommen, die selbst aber nicht so groß sind.

Hört sich noch nicht nach einem Problem für ein DBMS an.

Wäre es geschwindigkeitssteigernd die root_cat_id zu einer Index-Spalte zu machen ?

Das sagt dir ein EXPLAIN bei je einem Versuch mit ohne Index. Üblicherweise bringt ein Index, der beim Abfragen verwendet werden kann, Punkte. Andererseits kostet seine Aktualisierung auch etwas beim Ändern von Daten. Dürfte aber erst bei großen Datenmengen und -änderungen auffallen.

Lo!

[gow]

Hallo,

Ich hab jetzt die SQL-Abfrage erstellt.

Info: Tabelle group_members verbindet Gruppe mit User (Spalte user_id und group_id).
Die andere Tabellen sind wie bereits gesagt, aber Tabelle groups und category zusätzlich mit Spalte lft und rgt für Nested Sets.

SELECT permission.category_id, permission.what  
FROM category cat INNER JOIN category parent_cat ON (parent_cat.lft <= cat.lft AND parent_cat.rgt >= cat.rgt)  
 INNER JOIN permission ON(permission.category_id=parent_cat.cat_id)  
 INNER JOIN groups ON(permission.group_id=groups.group_id)  
 INNER JOIN group_members ON(group_members.group_id=groups.group_id)  
WHERE cat.cat_id IN ($categorys) AND group_members.user_id=$user_id

$categorys: Liste der Kategorie-IDs (mit Komma getrennt), von der die Rechtezuordung abgefragt werden soll
$user_id: ID des Benutzers

Gibt diese Abfrage das richtige zurück? Das wäre sehr wichtig, immerhin geht es um die Sicherheit.

lg gow

[dedlfix]

Hi!

Gibt diese Abfrage das richtige zurück? Das wäre sehr wichtig, immerhin geht es um die Sicherheit.

Erstell dir ein paar Tests mit Beispielen möglichst aller vorkommenden Varianten. Wenn du noch an den Abfragen Änderungen vornehmen musst, weil die eine oder andere Kombination vielleicht nicht das gewünschte Ergebnis bringt, kannst du diese Tests anschließend wieder durchlaufen lassen, um zu sehen, ob sich ungewollte Änderungen ergeben haben. Gestaltet die Test möglichst so, dass sie auch automatisch ermitteln, ob ihr Ergebnis stimmte oder nicht. Es ist einfacher, die roten unter den grünen Lampen zu finden, als konzentriert immer wieder die Richtigkeit der Ergebnisse festzustellen.

Lo!

[dedlfix]

Hi!

Transaktionen sind hier auf alle Fälle sehr zu empfehlen.
Die Geschwindigkeitsunterschiede werden sicher nicht großartig über das Grundrauschen kommen.
Also würdest du InnoDB für die Tabelle category und group empfehlen?

Naja, wenn du Transaktionen verwenden willst, führt dein Weg wohl kaum an InnoDB vorbei.

Lo!

[Tom]

Hello,

sinnvoll ist eine Trennung in mindestens drei Stämme:

• aktive Objekte:  User, Programme
• passive Objekte: Daten, Geräte, Schnittstellen
• Zugehörigkeit: Jedes Objekt, egal ob aktiv oder passiv wird einer
    oder mehrerer "Abteilung" zugeorndet

Ein User erhält z.B. Rechte auf einen Datenstamnm, und das Recht, neue User anzulegen. Diesen neuen Usern kann er wiederum Rechte auf (Teile seines) Datenstammes vergeben. Er könnte ihnen auch das Recht ertielen, Rechte zu erteilen, wenn... Und hier wird es spannend.

Das Problem bei dieser Art Rechtevergabe ist immer: Wie will man Rechte auf etwas noch nicht vorhandenes erteilen? Man könnte also nun dem User A das Recht geben, für die Abteilungen, denen er angehört, seinerseits User anzulegen. Einem dieser User erteilt er dann z.B. noch das Recht, in der Abteilung GRAFIK wiederum User anzulegen.

Und dann solltest Du Rechte-Vererbung, Vererbungsfilter und diskrete Rechtevergabe noch berücksichtigen.

Liebe Grüße aus dem schönen Oberharz

Tom vom Berg

[dedlfix]

Hi!

Wie will man Rechte auf etwas noch nicht vorhandenes erteilen?

Das löst mein Subjekt-Prädikat-Objekt-Ansatz, indem er das Objekt optional lässt. Wenn das Objekt leer ist, darf das Subjekt eine Tätigkeit ausführen, egal welches Objekt betroffen ist.

Und dann solltest Du Rechte-Vererbung, Vererbungsfilter und diskrete Rechtevergabe noch berücksichtigen.

Wenn du diese Begriffe (zumindest die letzten beiden) bitte noch etwas erklären würdest, könnte ich mir vielleicht auch etwas darunter vorstellen.

Lo!

[Tom]

Hello,

Wie will man Rechte auf etwas noch nicht vorhandenes erteilen?

Das löst mein Subjekt-Prädikat-Objekt-Ansatz, indem er das Objekt optional lässt. Wenn das Objekt leer ist, darf das Subjekt eine Tätigkeit ausführen, egal welches Objekt betroffen ist.

Die Frage war auch eher als Anregung zu verstehen, weil nämlich genau diese Problemstellung in den meisten Rechteverwaltungen einfach ignoriert wird.

Und dann solltest Du Rechte-Vererbung, Vererbungsfilter und diskrete Rechtevergabe noch berücksichtigen.

Wenn du diese Begriffe (zumindest die letzten beiden) bitte noch etwas erklären würdest, könnte ich mir vielleicht auch etwas darunter vorstellen.

In einer Hierarchichen Rechtesatruktur können die Objekte die Rechte/Eigenschaften ihrer Oberordnung erben. Das wäre normal, so angewendet z.B. auch in in der Linux-Dateiverwaltung.

Wenn man nun Vererbungsfilter einsetzt, kann man bestimmen, dass bestimmte Rechte nicht weiter nach unten vererbt werden, auch wenn sie später in der Oberordnung erteilt werden.

Die diskrete Rechtevergabe setzt sich nun über die Vererbung und die Filter hinweg und vergibt einem Objekt, egal wo es in der Vererbungsstruktur/Hierarchie steht, gezielt betimmte Eigenschaften/Rechte. Diese werden dann üblicherweise auch nicht weitervererbt.

So kann man dann, um auf eine Redaktionsumgebung einzugehen, einem Redakteur für ein bestimmtes Thema oder Dokument Sonderrechte einräumen, die er aber nicht auf weitere davon abgeleitete Dokumente im selben Arbeitsbereich übertragen kann. Er müsste die Ableitung in seinen Arbeitsbereich verlegen, wenn er dazu berechtigt ist. Dort kann er dann selber wieder Rechte auf das Dokument erteilen.

Sowas lässt sich allerdigns nicht verallgemeinern, weil es von den Möglichkeiten der verwendeten Systemumgebung abhängig ist. Serverapplikationen contra Clientapplikation usw.

Liebe Grüße aus dem schönen Oberharz

Tom vom Berg