Wie kann ein gerichteter Graph mit mehreren Eltern dargestellt werden?

8

http://dirtsimple.org/2010/11/simplest-way-to-do-tree-based-queries.html bietet einen Algorithmus zum Einfügen und Löschen aus einer Closure Table.

Ich möchte eine ähnliche Datenstruktur modellieren, außer dass Knoten mehrere Eltern haben können.

Gegeben:

Grafik Nr. 1

Wenn wir entfernen, [B, C]erwarte ich am Ende:

Grafik 2

und wenn wir den Knoten entfernen, Berwarte ich am Ende Folgendes:

Grafik 3

Wenn Sie jedoch den Algorithmus des Autors zum Entfernen von Links oder Knoten verwenden, werden Sie feststellen, dass er [D, C, 1]zum Löschen markiert wird, was unerwünscht ist.

Was ich bisher versucht habe

Ich habe versucht, die ursprüngliche Datenstruktur anzupassen, indem ich eine referencesSpalte hinzugefügt habe , die angibt, wie viele Möglichkeiten es gibt, zwischen zwei Knoten zu reisen. In dem obigen Beispiel können Sie von Reisen Anach Centweder durch Boder durch D. Die Idee wäre gewesen, dass beim BEntfernen der Pfad von Azu Cbeibehalten wird und die Referenzanzahl von 2 auf 1 abnimmt. Theoretisch war das nett, aber ich konnte nicht herausfinden, wie die Implementierung funktioniert, und jetzt frage ich mich, ob Es ist überhaupt möglich (die Datenstruktur enthält möglicherweise nicht genügend Informationen, um herauszufinden, welche Zeilen entfernt werden sollen).

Was ich frage

Wie würden Sie Closure Tables anpassen, um mehrere Eltern zu unterstützen? Welche alternativen Datenstrukturen würden Sie empfehlen? https://stackoverflow.com/q/4048151/14731 enthält eine exaustive Liste solcher Datenstrukturen, aber es ist nicht klar, welche mehrere Eltern unterstützen (oder für welche am besten geeignet sind).

Gili
quelle
Also, was hast du versucht? Und was ist die referencesSpalte?
Ypercubeᵀᴹ
Ich glaube nicht, dass man in Ihrem Szenario Verschlusstabellen anpassen würde . Verschlusstabellen eignen sich für viele baumbasierte Anwendungen, aber diese Frage spielt auf einen viel weniger restriktiven Typ von DAG (Directed Acyclic Graph) an. Dies ist ein Thema, das für eine Masterarbeit geeignet sein könnte. Wie so viele andere Dinge in Bezug auf Datenbanken hängt eine optimale Lösung stark von Ihrem genauen, spezifischen Anwendungsfall ab. Dies oder das könnte Ihnen den Einstieg erleichtern.
Avarkx
Welche Datenbank-Software?
Neil McGuigan
@NeilMcGuigan, H2 und PostgreSQL, obwohl ich natürlich eine DB-agnostische Lösung bevorzuge.
Gili

Antworten:

3

Erstellen Sie normalerweise eine Knotentabelle und eine Beziehungstabelle. Gerichtete Diagramme sind nicht wirklich hierarchisch und können Schleifen aufweisen, was das Abfragen erschwert. Wenn Sie sich eine DAG jedoch als einen verallgemeinerten Baum vorstellen (dh einen Baum, der mehrere Eltern zulässt, aber dennoch streng hierarchisch ist) und einen gerichteten Graphen als eine verallgemeinerte DAG (dh wie eine DAG, aber nicht streng hierarchisch), wird es einfacher.

Für eine sehr einfache PostgreSQL-Lösung könnten wir also Folgendes tun:

CREATE TABLE node (
    id serial primary key,
    payload jsonb not null
);

CREATE TABLE relationship (
    id serial primary key,
    relationship_type text not null,
    from_node int references node(id) not null,
    to_node int references node(id) not null,
    payload jsonb not null
);

Dann können Sie so etwas abfragen:

with recursive dg as (
    select n.id as node_id, null::Int as parent, array[n.id] as path
      from node n
    union all
    select to_node, from_node, path || to_node
      FROM relationship
      JOIN dg on dg.node_id = from_node AND NOT from_node = ANY(path)
)
select * from dg;
Chris Travers
quelle