Baumstruktur mit Zugriffsrechten?

Baumstruktur mit Zugriffsrechten?

am 23.12.2007 17:18:36 von Sebastian Suchanek

Hallo NG!

Derzeit mache ich mir Gedanken zur Datenstruktur eines
Projektes. Eines der essentiellen Bestandteile dieses Projekts
ist eine Baumstruktur - etwas, das man meines Wissens nach wohl
am effizientesten als "Nested Set" in MySQL abbildet.
Beispiel:

[root]
|
+-- [A]
|
'-- [B]
|
'-- [C]

In der DB, nennen wir die Tabelle mal "baum":

id | name | links | rechts
---+------+-------+-------
1 | root | 1 | 8
2 | A | 2 | 3
3 | B | 4 | 7
4 | C | 5 | 6

So weit, so gut - bis hierher gibt's ja auch jede Menge
Tutorials im Web dazu.

Jetzt möchte ich allerdings in Kombination mit einer
Userverwaltung auch Rechte innerhalb des o.g. Baumes vergeben
können, also z.B. festlegen können, wer den Inhalt welches
Baumknoten ansehen oder verändern darf.
Dazu könnte ich mir folgende Tabelle "rechte" vorstellen[1]:

id | knoten | user | recht
---+--------+------+----------
1 | 2 | Lisa | Lesen
2 | 3 | Bart | Schreiben

(Lisa soll in Knoten "A" lesen und Bart in Knoten "B" schreiben
können.) Jetzt möchte ich aber gerne, daß sich das Schreibrecht
von Bart nicht nur auf Knoten "B" bezieht, sondern automatisch
rekursiv auch auf alle Kindknoten von "B".
OK, wenn ich auf Anwendungsebene zufällig Knoten "B" schon
"in der Hand" habe, lassen sich alle Kindknoten relativ einfach
bestimmen - aber was ist, wenn ich einfach nur wissen will, ob
Bart in Knoten "C" irgendetwas tun darf?
Was wären performante/elegante Möglichkeiten, dies
herauszufinden? Mit anderen Worten: Wie könnte eine Abfrage
aussehen, die als Ergebnis (alle) Rechte liefert, die Bart in
Knoten "C" hat?
Gibt es davon abgesehen weitere Anmerkungen, Vorschläge oder
Tips zu diesem Vorhaben bzw. zum Datenmodell?


TIA,

Sebastian

_____
Anmerkungen:
[1] Die Felder "user" und "recht" würden natürlich noch passend
normalisiert - diese Darstellung habe ich nur der besseren
Lesbarkeit wegen gewählt.

--
http://www.baumaschinen-modelle.net
http://www.schwerlast-rhein-main.de

Re: Baumstruktur mit Zugriffsrechten?

am 23.12.2007 17:47:52 von Bastian Blank

Sebastian Suchanek wrote:
> Derzeit mache ich mir Gedanken zur Datenstruktur eines
> Projektes. Eines der essentiellen Bestandteile dieses Projekts
> ist eine Baumstruktur - etwas, das man meines Wissens nach wohl
> am effizientesten als "Nested Set" in MySQL abbildet.

Du suchst ein Directory (wie LDAP), keine Datenbank. Aber du solltest
erst mal erzählen, was für ein Problem du überhaupt lösen willst.

> In der DB, nennen wir die Tabelle mal "baum":
> id | name | links | rechts
> ---+------+-------+-------
> 1 | root | 1 | 8
> 2 | A | 2 | 3
> 3 | B | 4 | 7
> 4 | C | 5 | 6

Auch noch binär der Baum...

Bastian

Re: Baumstruktur mit Zugriffsrechten?

am 23.12.2007 20:11:50 von Claus Reibenstein

Bastian Blank schrieb:

> Sebastian Suchanek wrote:
>
>> am effizientesten als "Nested Set" in MySQL abbildet.
¯¯¯¯¯¯¯¯¯¯

>> id | name | links | rechts
>> ---+------+-------+-------
>> 1 | root | 1 | 8
>> 2 | A | 2 | 3
>> 3 | B | 4 | 7
>> 4 | C | 5 | 6
>
> Auch noch binär der Baum...

Wo siehst Du hier einen binären Baum? Sebastian beschreibt oben, was
diese Struktur darstellen soll, und so weit ich das überblicke, tut sie
auch genau das.

Wer lesen kann ...

Gruß. Claus

Re: Baumstruktur mit Zugriffsrechten?

am 24.12.2007 11:14:07 von Sebastian Suchanek

Sebastian Suchanek macht die Ingrid:

> [...]
> Mit anderen Worten: Wie könnte eine Abfrage
> aussehen, die als Ergebnis (alle) Rechte liefert, die Bart
> in Knoten "C" hat?
> [...]

Inzwischen ist mir selbst eine Lösung eingefallen:

SELECT
recht
FROM rechte r
LEFT JOIN baum b
ON b.id = r.knoten
WHERE
user = $user
AND
$knoten_id BETWEEN b.links AND b.rechts

Das liefert alle Rechte, die $user im Knoten $knoten_id hat.
("$user" und "$knoten_id" müssen natürlich passend von der
Applikation gesetzt werden.)


Tschüs,

Sebastian

--
http://www.baumaschinen-modelle.net
http://www.schwerlast-rhein-main.de

Re: Baumstruktur mit Zugriffsrechten?

am 24.12.2007 11:27:15 von Christian Kirsch

Sebastian Suchanek schrieb:
> Hallo NG!
>
> Derzeit mache ich mir Gedanken zur Datenstruktur eines
> Projektes. Eines der essentiellen Bestandteile dieses Projekts
> ist eine Baumstruktur - etwas, das man meines Wissens nach wohl
> am effizientesten als "Nested Set" in MySQL abbildet.

Wenn man nur einen Hammer kennt, sieht alles wie ein Nagel aus?
Sicherlich *kann* man Bäume in relationalen Datenbanken abbilden - aber
*will* man?

> Beispiel:
>
> [root]
> |
> +-- [A]
> |
> '-- [B]
> |
> '-- [C]
>
> In der DB, nennen wir die Tabelle mal "baum":
>
> id | name | links | rechts
> ---+------+-------+-------
> 1 | root | 1 | 8
> 2 | A | 2 | 3
> 3 | B | 4 | 7
> 4 | C | 5 | 6
>
> So weit, so gut - bis hierher gibt's ja auch jede Menge
> Tutorials im Web dazu.
>
> Jetzt möchte ich allerdings in Kombination mit einer
> Userverwaltung auch Rechte innerhalb des o.g. Baumes vergeben
> können, also z.B. festlegen können, wer den Inhalt welches
> Baumknoten ansehen oder verändern darf.

Es gibt LDAP. Es gibt auch z.B. Subversion. Vielleicht guckst Du mal von
der Seite des Problems aus?


> Gibt es davon abgesehen weitere Anmerkungen, Vorschläge oder
> Tips zu diesem Vorhaben bzw. zum Datenmodell?

S.o.: Beschreib doch erstmal in dürren Worten, was Deine Aufgabe ist.
Danach kann man darüber diskutieren, welches Werkzeug sich dafür am
besten eignet und wie man dieses Werkzeug am besten einsetzt.

Re: Baumstruktur mit Zugriffsrechten?

am 24.12.2007 16:07:04 von Sebastian Suchanek

Thus spoke Christian Kirsch:
> Sebastian Suchanek schrieb:
>> Hallo NG!
>>
>> Derzeit mache ich mir Gedanken zur Datenstruktur eines
>> Projektes. Eines der essentiellen Bestandteile dieses
>> Projekts ist eine Baumstruktur - etwas, das man meines
>> Wissens nach wohl am effizientesten als "Nested Set" in
>> MySQL abbildet.
>
> Wenn man nur einen Hammer kennt, sieht alles wie ein Nagel
> aus? Sicherlich *kann* man Bäume in relationalen
> Datenbanken abbilden - aber *will* man?

Ich denke schon - siehe unten. :-)

> [...]
>> Gibt es davon abgesehen weitere Anmerkungen, Vorschläge
>> oder Tips zu diesem Vorhaben bzw. zum Datenmodell?
>
> S.o.: Beschreib doch erstmal in dürren Worten, was Deine
> Aufgabe ist. Danach kann man darüber diskutieren, welches
> Werkzeug sich dafür am besten eignet und wie man dieses
> Werkzeug am besten einsetzt.

OK, Du hast es so gewollt. :-)
Ich fange mal ganz von vorne an: Auf meinem "Desktop-PC"
befinden sich meine gesammelten Digitalfotos und auch Dia-
/Negativ-Scans in nicht ganz unerheblicher Anzahl. Diese möchte
ich - zusätzlich zum bereits durchgeführten LTO-Backup - als
Sicherungsmaßnahme auf meinen Heimserver spiegeln. Da dieser
Heimserver aber dank DynDNS und DSL-Flatrate einerseits ohnehin
(quasi) dauerhaft aus dem Internet erreichbar ist und ich
andererseits auch gerne eine Möglichkeit hätte, Freunden und
Bekannten einzelne Bilder oder auch größere Bildergruppen
zugänglich zu machen, habe ich über eine Art Web-Frontend zu
dieser Spiegelung nachgedacht.
Dabei möchte ich dann individuell festlegen können, welcher User
welche(s) Bild(er) wie zu sehen bekommt: Also ob - auf Wunsch -
in voller Auflösung von x Megapixeln oder nur in reduzierter
Auflösung von z.B. 800*600 Pixeln (das Herunterrechnen soll dann
- incl. Caching, siehe unten - auch gleich das Frontend
übernehmen) oder ob der User das Bild z.B. nur mit einer
Copyright-Einblendung zu sehen bekommt.

Zusätzlich soll - natürlich ;-) - auch die Möglichkeit bestehen,
z.B. nach Stichwörtern zu suchen. Und hier kommt jetzt langsam
die Datenbank ins Spiel: Die Bilddateien selbst werden zwar mit
IPTC-Daten verschlagwortet werden und auch technische Details
zur Aufnahme sind zumindest bei den Digitalfotos via EXIF-Header
ohnehin in den Bildern enthalten, allerdings ist mein Heimserver
zwecks Energiesparen bewußt schmalbrüstig ausgelegt (Via C3
733MHz, entsprechend auch kein /wirklich/ schnelles Bussystem),
weswegen direktes Suchen im Dateisystem hierzu de facto
wegfällt. (Und auch mit dickerer Hardware in >70GB nicht
wirklich Spaß machen würde.)
Deswegen möchte ich ein Abbild der Verzeichnisstruktur (=>
Baum!) in eine Datenbank hieven auch ausgewählte Metadaten
der darin abgelegten Bilder wie z.B. die IPTC-Stichwörter oder
eine handvoll EXIF-Daten zu jedem Bild mit in der Datenbank
ablegen, um halbwegs performant darin suchen zu können.

Daß ich an der Verzeichnis- bzw. Baumstruktur auch innerhalb der
Datenbank festhalten möchte, liegt daran, daß die existierende
Verzeichnisstruktur bereits eine grobe Kategorisierung der
Bildinhalte widerspiegelt und entsprechend voraussichtlich als
Haupt-Navigationsweg im Frontend auftauchen wird. Entsprechend
erscheint es mir sinnvoll, diese Informationen in einer
Datenbank vorzuhalten, da ich ein DBMS hierfür im Vergleich
z.B. zu Disk-IO für vergleichsweise "billig" im Hinblick auf
CPU-, RAM- und IO-Last halte und da diese Informationen
vermutlich relativ oft gelesen werden müssen, um das Webfrontend
aufzubauen. Entsprechend logisch ist es außerdem auch, Usern mit
"einem einzelnen Mausklick" Zugriffsrechte für ganze Teil-
Verzeichnisstrukturen geben zu wollen bzw. zu können. (Womit wir
bei meiner ursprünglichen Frage wären.)
Außerdem grübele ich darüber nach, ob es möglicherweise sinnvoll
und/oder durchführbar ist, in einer späteren Ausbaustufe auch
die Stichwörter in einem weiteren Baum hierarchisch zu
strukturieren, um ihnen einen logischen Kontext zueinander geben
zu können.

Und deswegen denke ich, daß eine Datenbank die eleganteste
Lösung für meine Wünsche ist. :-)

Daß das ganze auch ein paar Probleme mit sich bringt, ist auch
klar: Zum Beispiel besteht die prinzipielle Gefahr, daß
Dateisystem und Datenbankinhalte divergieren - das hoffe ich
aber mit "Dateisystem-Triggern" und nötigenfalls
Eigenverantwortung im Umgang mit den System in den Griff zu
bekommen.

Ach ja, und komm mir jetzt keiner mit den üblichen Webgalerien -
die leisten typischerweise nicht das, was ich hier beschrieben
habe. :-)


Tschüs,

Sebastian

--
http://www.baumaschinen-modelle.net
http://www.schwerlast-rhein-main.de

Re: Baumstruktur mit Zugriffsrechten?

am 24.12.2007 16:29:45 von Claus Reibenstein

Christian Kirsch schrieb:

> Sebastian Suchanek schrieb:
>
>> Derzeit mache ich mir Gedanken zur Datenstruktur eines
>> Projektes. Eines der essentiellen Bestandteile dieses Projekts
>> ist eine Baumstruktur - etwas, das man meines Wissens nach wohl
>> am effizientesten als "Nested Set" in MySQL abbildet.
>
> Wenn man nur einen Hammer kennt, sieht alles wie ein Nagel aus?

Der Sinn dieses Spruchs erschießt sich mir nicht. Bitte erläutere ihn
mir und zeige mir den Zusammenhang zum oberen Zitat auf.

> Sicherlich *kann* man Bäume in relationalen Datenbanken abbilden - aber
> *will* man?

Warum sollte man _nicht_ wollen?

> Es gibt LDAP. Es gibt auch z.B. Subversion.

Dass es auch andere Möglichkeiten gibt, ist noch lange kein
ausreichendes Argument. Warum sollte man diese vorziehen? Wo liegen ihre
Vorteile gegenüber einer Datenbank?

Gruß. Claus

Re: Baumstruktur mit Zugriffsrechten?

am 25.12.2007 10:30:28 von Stefan Dreyer

Claus Reibenstein wrote:
> Christian Kirsch schrieb:
> [...]
>=20
> Warum sollte man _nicht_ wollen?
>=20
>=20
>>Es gibt LDAP. Es gibt auch z.B. Subversion.
>=20
>=20
> Dass es auch andere Möglichkeiten gibt, ist noch lange kein
> ausreichendes Argument.=20

Vor allem da die genannten Dinge nichts mit einer Baumstruktur zu tun=20
haben. LDAP ist nur ein Zugriffsprotokoll für eine meistens=20
hierarchische Datenbank und wie man damit Bäume abbilden möchte und d=
ann=20
noch effizient darin suchen möchte, ist mir ein Rätsel.

> Warum sollte man diese vorziehen? Wo liegen ihre
> Vorteile gegenüber einer Datenbank?

Für den gewünschten fall gibt es keine Vorteile. Gut, ich würde mic=
h=20
jetzt nicht als ausgewiesenen LDAP-Crack bezeichnen, aber ich habe schon =

einiges damit realisiert. Es eignet sich gut um hierarchische Strukturen =

abzubilden, aber das war es dann auch schon. Dazu kommt noch, dass die=20
real existierenden OS-Implemenationen auch noch ein unzureichendes=20
Backend besitzen.

Re: Baumstruktur mit Zugriffsrechten?

am 08.01.2008 08:14:29 von Harald Stowasser

Christian Kirsch schrieb:

> Wenn man nur einen Hammer kennt, sieht alles wie ein Nagel aus?
> Sicherlich *kann* man Bäume in relationalen Datenbanken abbilden - aber
> *will* man?

Ja.