Re: Netzwerkstrukturen im relationalen Modell

vortex25(at)gmx(dot)de writes:

> On Wed, 13 Apr 2005 02:45:35 +0200
> Andreas Seltenreich <seltenreich(at)gmx(dot)de> wrote:
>
>> vortex25(at)gmx(dot)de writes:
>>
>> > Es sollen Beziehungen zwischen Objekten der gleichen Menge
>> > hergestellt werden. Dabei darf es eine Verbindung zwischen
>> > zwei Objekten nur einmal geben. Es kann aber ein Objekt
>> > mit beliebig vielen anderen Objekten verbunden werden.
>>
>> Ist die Relation auf der Menge tatsächlich antisymmetrisch, oder ist
>> sie symmetrisch, und du willst dir die zweite Richtung wegen der
>> Redundanz sparen? D.h. nur die obere Hälfte einer symmetrischen
>> Adjazenzmatrix pflegen?
>
> Also mit meinen Worten würde ich sagen: "in der Realität ist
> die Relation symmetrisch". Antisymmetrisch würde ja sicher
> bedeuten, daß die Verbindung auch real Eigenschaften
> wie z.B. eine "Richtung" aufweist und damit die
> Art der Speicherung festliegt?

Genau. In der Graphenwelt würde man auch von "gerichtet" bzw.
"ungerichtet" sprechen.

> Du meinst also, es wäre auch kein Fehler die Verbindung
> auch in der Datenbank "zweimal" zu speichern und so die
> reale Symmetrie nachzubilden?

Das hängt davon ab, wie man Fehler definiert. Gutes Datenbankdesign
ist es jedoch bestimmt nicht, da man sich Redundanz ja soweit wie
möglich entledigen soll.

> Ich habe darüber auch schon nachgedacht, diese Möglichkeit aber eben
> wegen der Redundanz und auch wegen der daraus resultierenden Gefahr
> von Inkonsistenzen verworfen (was passiert, wenn aus irgendwelchen
> Gründen mal nur eine hälfte der Symmetrischen Verbindung eingetragen
> wird?).

Genau, deshalb würde ich den Weg auch nicht gehen wollen.

> Über den Begriff der Adjazenzmatrix grübel ich ja nun schon eine
> ganze Weile. Ich kenne düster aus dem Mathematikunterricht
> alle möglichen "junktionen". Ist disjunkt und adjunkt
> das gleiche? Ist es so, daß man die Mengen der zu
> verknüpfenden Elemente quasi als Vektor auffasst
> (was ja dann eigentlich keine Menge mehr ist?) und diese
> mittels der Matrix aufeinander abbildet?
> Die Adjunkte einer Matrix hat doch dann sicher was mit
> der Adjazenzmatrix zu tun? Oder klingt das nur so ähnlich?

Nein, viel einfacher: Da ein Rechner üblicherweise keine Lineare
Algebra oder Graphen-Bildchen versteht, muß man die Relation auf einer
Menge eben durch etwas repräsentieren, mit dem der Rechner umgehen
kann: Listen und Matrizen (im Falle von postgresql sind es ja Listen
(Tabellen), aber zur Veranschaulichung der Symmetrie hab' ich auch von
Matrizen gesprochen).

Als Einführung vielleicht:
http://de.wikipedia.org/wiki/Repr%C3%A4sentation_von_Graphen_im_Computer

> Ich hätte also z.B. die Menge S={1,2,3} und stelle
> eine Verbindung zwischen den Elementen "2" und "3"
> her. Sähe das dann so aus: ?
> ( 0 0 0 ) (1)
> ( 0 0 1 ) * (2) = (1 2 3)
> ( 0 1 0 ) (3)
>
> Da ist aber doch jetzt die "Redundanz" quasi schon drin.
> Obwohl die Zeilen der Matrix nicht geradzahlig sind?
> ACH! Du meinst mit "oberer Hälfte" die "rechte obere Hälfte"?
> Ja, klar! logisch! *freu* :-) Ich glaub' jetzt hab ich's
> verstanden :-).

Ja, da war ich etwas nachlässig. Der korrekte Begriff wäre wohl obere
bzw. untere Dreiecksmatrix gewesen.

> Hm, heißt die Ajazenzmatrix dann vielleicht deswegen so,
> weil eine normale Matrix ja nicht unbedingt nur aus
> "1" und "0" bestehen muß? Wenn Adjunktion und
> Disjunktin das gleiche ist (bitte nicht schlagen, ich glaube
> mich da düster an sowas erinnern zu können), vielleicht
> heißt sie dann so, weil die Elemente entweder 1 ODER 0
> sind? Na, ich glaube jetzt wird es etwas ZU phantasievoll :-).

Ich denke, der Begriff stammt aus der Graphentheorie. Man legt
"benachbarte" (engl. adjacent) Knoten eben in einer solchen Matrix
bzw. Liste ab.

> Na, jedenfalls wäre die Speicherung der zweiten Hälfte
> der Ajazenzmatrix vielleicht wirklich nicht so dumm,
> denn beim Auswerten der Daten muß ich diese bislang immer
> künstlich wieder erzeugen (mittels UNION). Und ob das mal
> so effizient ist, wenn wirklich viele Daten drin sind?

Das kann ich nicht sagen, dazu hast du noch zu wenig von deinem
eigentlichen Projekt erzählt.

>> Wenn du die Antisymmetrie wegen der Redundanz willst, würde sich
>> anbieten, der Relation eine Ordnung aufzuzwingen:
>>
>> create table relation (a int, b int,
>> CONSTRAINT antisymmetrie CHECK (a<b), UNIQUE(a, b));
> Hm, das stimmt. Das ist eigentlich die beste Lösung, die mir
> bislang vorgeschlagen wurde. Das bedeutet zwar, daß ich das auch
> beim Speichern berücksichtigen muß, aber zumindest ist dann
> zu jeder Zeit die Konsistenz in der Datenbank gewährleistet.

Ja, aber da du ja noch in der Design-Phase bist, könnte man diesen Weg
ja noch in Betracht ziehen.

> Außerdem wäre damit gleich der Fall erschlagen, daß ein Objekt
> mit sich selbst verbunden wird!

Wobei das eher unproblematisch ist, da man, um das festzustellen, ja
keinerlei Datenbankzugriffe braucht.

>> Wenn die Relation tatsächlich antisymmetrisch ist, könnte man einen
>> UNIQUE-index auf eine passende Funktion definieren:

>> create table relation (a int, b int);
>>
>> create function min(integer, integer) returns integer as
>> 'select CASE WHEN $1 > $2 THEN $2 ELSE $1 END' language 'SQL'
>> IMMUTABLE;
>>
>> create function max(integer, integer) returns integer as
>> 'select CASE WHEN $1 > $2 THEN $1 ELSE $2 END' language 'SQL'
>> IMMUTABLE;

> Hm, macht min() und max() sowas nicht von Haus aus? Nur müssten
> es halt rows sein. Ich hätte erwartet, daß sowas in der Art:
> min(generate_series($1,$2,$2-$1)) funktioniert. Aber
> generate_series() scheint andere Spalten zu generieren, als
> die aus einer "richtigen" Tabelle :-).

Durr, kann gut sein, daß ich irgendwo eine eingebaute Funktion
übersehen habe. Auf die Schnelle hab' ich nur die Aggregatfunktionen
gefunden, und die sind Einstellig. Vielleicht schreibt ja noch jemand
anderes was dazu...

>> create UNIQUE INDEX relation_idx_antisymmetrie
>> ON relation (min(a,b),max(a,b));
> Aber hier wäre der Fall daß ein Objekt mit sich selbst
> verbunden wird, nicht automatisch ausgeschlossen, oder?
> --> CHECK a != b ?

Wie oben schon geschrieben: Aus Kostensicht ist der zusätzliche
Vergleich ja unproblematisch, da dazu keinerlei Datenbankzugriffe
notwendig sind.

Gruß
Andreas