Relationsalgebra

Dieser Artikel behandelt den Begriff aus der Theorie der Booleschen Algebren. Zum ähnlich lautenden Begriff aus der Theorie der Datenbanken siehe Relationale Algebra.

In der Mathematik und abstrakten Algebra ist eine Relationsalgebra (englisch: relation algebra) eine residuierte Boolesche Algebra,^[1] die um eine Involution (als einstellige Operation), genannt Konverse, erweitert wurde. Das für diese Begriffsbildung maßgebliche Beispiel einer Relationsalgebra ist die Algebra ${\displaystyle 2^{A^{2}}={\mathcal {P}}(A\times A)}$ aller zweistelligen Relationen auf einer Menge ${\displaystyle A}$ (d. h. auf den Teilmengen des kartesischen Produkts ${\displaystyle A\times A=A^{2}}$), zusammen mit der Verkettung von Relationen und der Umkehrrelation (konversen Relation).

Definition

Die folgenden Axiome sind angelehnt an Givant (2006, Seite 283) und wurden zuerst 1948 von Alfred Tarski aufgestellt.^[2]

Eine Relationsalgebra ist ein 9-Tupel ${\displaystyle (L,\land ,\lor ,\neg ,0,1,\circ ,\mathrm {I} ,{}^{\smile })}$, für das gilt:

• ${\displaystyle (L,\land ,\lor ,\neg ,0,1)}$ ist eine Boolesche Algebra mit Konjunktion ${\displaystyle \land }$, Disjunktion ${\displaystyle \lor }$ und Negation ${\displaystyle \neg }$ sowie Nullelement ${\displaystyle 0}$ und Einselement ${\displaystyle 1}$:
• ${\displaystyle (L,\circ ,\mathrm {I} )}$ ist ein Monoid mit einem eigenen Einselement ${\displaystyle \mathrm {I} }$,
• ${\displaystyle {}^{\smile }}$ ist eine Involution, genannt Konverse,
• ${\displaystyle \forall a,b\in {L}:(a\circ b)^{\smile }=b^{\smile }\circ a^{\smile }}$, d. h. die Konverse ist gegenüber der Verknüpfung ${\displaystyle \circ }$ treu,
• ${\displaystyle \forall a,b\in {L}:(a\lor b)^{\smile }=a^{\smile }\lor b^{\smile }}$,
• ${\displaystyle \forall a,b,c\in {L}:(a\lor b)\circ {c}=(a\circ {c})\lor (b\circ {c})}$ (Distributivität) und
• ${\displaystyle \forall a,b\in {L}:(a^{\smile }\circ \neg (a\circ {b}))\lor \neg {b}=\neg {b}}$, was nichts anderes bedeutet als ${\displaystyle a\circ {b}\leq \neg {c}\Leftrightarrow a^{\smile }\circ c\leq \neg {b}\Leftrightarrow c\circ b^{\smile }\leq \neg {a}}$ (Peircesches Gesetz).^[3]

  

  Veranschaulichung zum Peirceschen Gesetz, hier mit u, v, w statt a, b, c

Beispiel

Die homogenen zweistelligen Relationen ${\displaystyle R\subseteq A\times A}$ bilden die Relationsalgebra

${\displaystyle {\mathfrak {Re}}(A)=(2^{A^{2}},\cap ,\cup ,{}^{^{-}},\emptyset ,A^{2},\circ ,\mathrm {I} _{A},{}^{\smile })}$ ^[4]

unter Verwendung der Notationen ${\displaystyle A^{2}=A\times A,\ \;\ 2^{A^{2}}={\mathcal {P}}(A\times A)}$.^[5]

Peirce-Algebra

• Eine Weiterentwicklung davon ist die (heterogene) Peirce-Algebra, benannt nach Charles Sanders Peirce – eine abstrakte Beschreibung der Relationsalgebra ${\displaystyle {\mathfrak {Re}}(A)}$ der homogenen zweistelligen Relationen zusammen mit Vor-/Nachbeschränkungen auf Mengen.

Siehe auch

• Boolesche Algebra
• Heyting-Algebra