Relationenalgebra
Mit binären Relationen läßt sich ein algebraischer
Kalkül aufbauen:
-
die Nullrelation 0:
dabei bestehen gar keine Beziehungen,
alle Elemente der Inzidenzmatrix sind 0 (FALSE)
-
die Allrelation 1:
jedes Element steht zu jedem in Beziehung
(auch zu sich selbst!),
alle Elemente der Inzidenzmatrix sind 1 (TRUE)
-
zu jeder Relation R gibt es das Komplement
R:
es besteht eine Beziehung genau dann, wenn in R keine besteht,
alle Elemente der Inzidenzmatrix werden invertiert
-
zu zwei Relationen R und S gibt es die
Konjunktion R
S:
die Elemente der Inzidenzmatrizen werden mit verknüpft
-
zu zwei Relationen R und S gibt es die
Disjunktion R
S:
die Elemente der Inzidenzmatrizen werden mit verknüpft
Damit haben wir bereits eine Boolesche Algebra erhalten;
wir nehmen weitere Elemente und Operationen hinzu:
-
die Identität Id:
jedes Element steht nur zu sich selbst in Beziehung,
die Inzidenzmatrix ist die Einheitsmatrix
-
zu zwei Relationen R und S gibt es das
Relationenprodukt
R.S:
aR.Sb 
c: aRc cSb
Die Inzidenzmatrizen werden nach den Regeln der Matrixalgebra multipliziert;
dabei wird aber + durch und 
durch ersetzt.
Wenn man die Matrixelemente 0 und 1 verwendet, kann man auch
in der Matrixalgebra rechnen und dann das Resultat "stutzen",
also Werte >1 auf 1 reduzieren.
Den gleichen Kunstgriff kann man auch bei der Disjunktion verwenden;
die Konjunktion kommt schon richtig heraus.
-
Für das Relationenprodukt ist die Relation Id das
Einselement, die Nullrelation 0 das Nullelement; mit der
Disjunktion anstelle einer Addition ergibt sich eine Ringstruktur.
Die so erhaltene Relationenalgebra kann man noch erweitern
auf Relationen zwischen verschiedenen Grundmengen,
und um mehrstellige Relationen; der erhaltene Formalismus ist wichtig
als Grundlage der Theorie der Datenbanken.
zurück |
Inhalt | Index |
vor |
Vorlesung
Klaus Lagally, 22. Februar 2000, 19:36