gerichteter Graph in ne DB speichern?

[Shade Of Mine]

Hallo Leute.

Eine normale Baumstruktur kann man ja ganz gut in eine Tabelle reinquetschen ( http://dev.mysql.com/tech-resources/articles/hierarchical-data.html ). Doch wie sieht es mit einem zyklischen gerichteten Graphen aus?

Geht das vernünftig? Worum es mir besonders geht sind schnelle Lookups auf die Pfade zu den einzelnen Knoten.

Mir fehlen leider die Begriffe um vernünftig Googlen zu können ausserdem scheint das n sehr spezielles thema zu sein -> ich finde zB ganz wenig über Baumstrukturen aber über Graphen garnichts

[HabsNieVerwendet]

Graphentheorie matrix

[TheTester]

Machs doch ganz "billig". Erstelle zwei Tabellen eine für die Knoten mit Knoten ID und Beschreibung und eine für die Kanten mit Kanten ID, Startknoten, Endknoten und Gewicht.

tt

[Shade Of Mine]

TheTester schrieb:

Machs doch ganz "billig". Erstelle zwei Tabellen eine für die Knoten mit Knoten ID und Beschreibung und eine für die Kanten mit Kanten ID, Startknoten, Endknoten und Gewicht.

hab ich mir schon ueberlegt, aber wie mache ich da effiziente lookups?
ich brauche sau schnelle lookups auf die pfade die es zu einem knoten gibt - das ich 99% der zeit nix anderes mache als solche lookups...

@HabsNieVerwendet:
das problem ist, dass der Graph dynamisch waechst.

die allgemeine struktur bleibt gleich, da tut sie quasi nie was - aber es kommen viele neue leaf knoten dazu (das ganze ist eine ACL implementation: und ein neuer User der sich registriert ist eben ein kind von Users - und das kommt oft vor, da kann ich nicht jedesmal die matrix neu aufbauen)

[TheTester]

Vielleicht ist ein Graph der falsche Ansatz für eine ACL ( ich nehme an Access Control List )

tt

[Shade Of Mine]

TheTester schrieb:

Vielleicht ist ein Graph der falsche Ansatz für eine ACL ( ich nehme an Access Control List )

Durchaus moeglich.

Mein Problem ist folgendes:

Users
  Joe
  Bill
  Moderators
    Frank
    Ted
    Admins
      Eric

das waere der ARO baum.
das laeuft problemlos so.

nun soll ein neuer punkt dazu kommen:

Users
  Joe
  Bill
  Moderators
    Frank
    Ted
    Admins
      Eric
Reviewers
  Joe
  Moderators

bei sowas habe ich zuerst eben an einen graphen gedacht...
bin aber auch dabei mir diverse acl implementierungen anzusehen um vielleicht einen anderen ansatz zu finden...