Re: Netzwerkstrukturen im relationalen Modell

vortex25(at)gmx(dot)de writes:

> On Wed, 13 Apr 2005 15:15:33 +0200
> Andreas Seltenreich <seltenreich(at)gmx(dot)de> wrote:
>
>> Genau. In der Graphenwelt würde man auch von "gerichtet" bzw.
>> "ungerichtet" sprechen.
>
> Aaah... wieder ein Licht aufgegangen :-).
>
>> 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).
> Hmmm, ob dann die Matrix nur eine andere Darstellungsform der Liste
> ist?

Ack. Alle nach der Graphentheorie wohldefinierten Graphen lassen sich
sowohl durch Listen, als auch durch Matrizen darstellen. Die Matrizen
haben den Vorteil, daß sich die Speicheradresse des Ergebnisses, ob
zwei Elemente in Relation zu einander stehen, direkt aus den Elementen
ergibt. Bei dünn besetzten Matrizen (Speicherverschwendung) - oder
wenn man gerade eine relationale Datenbank 'rumliegen hat - sind
Listen die Erste Wahl.

> In meinem Fall drängt sich die Darstellung als Matrix ja
> förmlich auf. Irgendwie eine besondere Matrix ist es auch immer,
> denn es steht ja nur entweder 0 oder 1 drin.

Wenn es sich um Relationen aus der Linearen Algebra handelt, steckt in
der Matrix tatsächlich nur der Wahrheitswert. Mit der Graphentheorie
können aber auch Mehrfachbindungen existieren; z.B. beim modellieren
von Elektronenbindungen in Molekülen.

> Oder meinst Du damit, daß man das garnicht so mathematisch auffassen
> darf, Du verwendest nur die entsprechenden Begriffe, weil's eben wie
> eine Matrix aussieht?

Das wollte ich damit sagen. Ich wüßte z.B. nicht, daß man aus der
Betrachtung der Matrix als lineare Abbildung (wie du es in der zweiten
Mail mal dargestellt hast), der Determinante, der Eigenwerte, etc
irgendwas sinnvolles über den Graphen aussagen könnte.

> Genaugenommen gibt es (noch) gar kein richtiges Projekt. Ich mach' das nur
> so aus Spaß :). Mit einem realen Problem hat es aber schon zu tun.
> Mal ganz abstrakt gesprochen geht es um ein Netz von
> gleichberechtigten Datenfunkstellen, die sich miteinander
> unterhalten. Aber es kann nicht jeder mit jedem sprechen.

Dann sind Graphen zum Modellieren ja genau das richtige.

>> 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...
> Wenn ich mir das nun so recht überlege, geht es doch eigentlich
> nur darum, eine Abbildung zu finden, die immer den gleichen
> eindeutigen Wert liefert, egal auf welcher Seite der
> Symmetrie der Adjazenzmatrix man sich befindet.

Ack.

>
> Wie wäre es denn dann damit:
> create UNIQUE INDEX relation_idx_antisymmetrie
> ON relation (a*b,a+b)
>
> Mal so aus dem Bauch raus müsste das doch eindeutig sein, oder?

Hmm, sollte mit Integers auch klappen.

Für die Lösung mit max() und min() hab' ich mich entschieden, da diese
relativ unabhängig vom Datentyp ist, weil der >-Operator - im
Gegensatz zur Multiplikation und Addition - auf fast alle Datentypen
definiert ist, die Postgres kennt.

scratch=> \do >
Liste der Operatoren
Schema | Name | Linker Typ | Rechter Typ
------------+------+-----------------------------+---------------------
pg_catalog | > | "char" | "char"
pg_catalog | > | "path" | "path"
[...]
pg_catalog | > | inet | inet
[...]

Falls deine "Datenfunkstellen" IP-Adressen haben, könntest du die mit
dem min()/max()-Ansatz z.B. direkt verwenden:

scratch=> select '192.168.0.1'::inet > '172.64.0.1'::inet;
?column?
----------
t
(1 Zeile)

Gruß
Andreas