Relationale Algebra: Unterschied zwischen den Versionen

aus GlossarWiki, der Glossar-Datenbank der Fachhochschule Augsburg
Keine Bearbeitungszusammenfassung
Keine Bearbeitungszusammenfassung
(37 dazwischenliegende Versionen desselben Benutzers werden nicht angezeigt)
Zeile 1: Zeile 1:
{{Qualität
[[Kategorie:Lehrveranstaltung]]
|correctness        = 2
|extent              = 1
|numberOfReferences  = 3
|qualityOfReferences = 5
|conformance        = 5
}}
 
==Definition ([[Wolfgang Kowarschick|Kowarschick]] (2018))==
 
Eine [[Algebraische Struktur|Algebra]] <math>\mathcal{R} = (R, id, \pi, \sigma, \times, \div, \cup, \cap, \setminus)</math> heißt [[Relationale Algebra]] wenn die Trägermenge oder -klasse <math>R</math> eine [[Menge (Mengenlehre)|Menge]] bzw. [[Klasse (Mengenlehre)|Klasse]] von [[Relation|Relationen]] mit benannten Attributen ist.
 
* <math>id: R \rightarrow R</math> ist die so genannte Identitätsfunktion: Es gilt stets <math>id(r) = r</math>
* <math>\pi_{f_1  \,\text{as}\, a_1, \,\ldots, \,f_n \,\text{as}\, a_n}: R \rightharpoonup  R</math> sind die so genannten Projektionsfunktionen, die mit Hilfe der Funktionen $f_i$ für jedes Tupel $n$ neue Attribute berechnen. Die neuen Attribute haben die Namen $a_i$.
* <math>\sigma_b: R \rightharpoonup R</math> sind die so genannte Selektionsfunktionen: Mit ihrer Hilfe werden aus einer Relation diejenigen Tupel selektiert, die die Bedingung $b$ erfüllen.
* <math>\times: R, R \rightharpoonup R</math> ist das kartesische Produkt, das zwei Relationen zu einer Relation verknüpft. Für jede mögliche Kombination von zwei Tupeln der Urbildrelationen ist die [[Konkatenation]] der  beiden Tupel Element der Bildrelation.
* <math>\div: R, R \rightharpoonup R</math> ist die Division. Im Prinzip ist dies die Umkehrfunktion des kartesischen Produktes.
* <math>\cup: R, R \rightharpoonup R</math> ermittelt die Vereinigung zweier (strukturgleicher) Relationen.
* <math>\cap: R, R \rightharpoonup R</math> ermittelt den Durchschnitt zweier (strukturgleicher) Relationen.
* <math>\setminus: R, R \rightharpoonup R</math> ermittelt die Differenz zweier (strukturgleicher) Relationen.
 
==Geschichte==
 
1969/1970 schlägt [[Edgar Frank Codd]] vor, Relationen zu verwenden, um große Datenbanken (“large data banks”)
zu verwalten<ref name="Codd 1969">{{Quelle|Codd (1969)}}</ref><ref name="Codd 1970">{{Quelle|Codd (1970)}}</ref>.
Er definiert dazu insbesondere die beiden relationalen Operationen „Projektion“ und „Join“.
Im ersten Satz des Abstract seines internen Reports „Derivability, Redundancy and Consistency of Relations Stored in Large Data Banks“
von 1969 macht Codd eine geradezu prophetische Aussage:
 
{{Quote|The large, integrated data banks of the future will
contain many relations of various degrees in stored form. (Codd (1969)<ref name="Codd 1969"/>)
}}
 
Übersetzung (von Kowarschick):<br/>
{{Quote|Die großen, integrierten Datenbanken der Zukunft werden
viele Relationen unterschiedlichsten Grades in gespeicherter Form enthalten.
}}
 
Ende 1970, {{dh}} im selben Jahr, in dem Codds Arbeit publik wurde, stellen [[Rudolf Bayer]] und [[Ed McCreight]] den [[B-Baum]] 
vor, eine [[Datenstruktur]], die es ermöglicht, Relationen mit einer großen Anzahl von Tupel so auf einer Festplatte zu speichern,
dass der lesende Zugriff auf Tupel sowie die Modifikation von Tupeln hocheffizient erfolgen
kann.<ref name="Bayer 1970">{{Quelle|Bayer, McCreight (1970)}}</ref><ref name="Bayer 1972">{{Quelle|Bayer, McCreight (1972)}}</ref>
 
In den 70er Jahren begann auf Basis dieser beiden Arbeiten die Erfolgsgeschichte der [[Relationale Datenbank|Relationalen Datenbanken]]
einschließlich der zugehörigen Sprache [[SQL]].
 
==SQL==
 
Die Relationale Algebra ist Grundlage der [[Datenbankmanagement|Datenbank]]-Sprache [[SQL]]. In SQL
werden allerdings [[Tabelle]]n an Stelle von [[Relation]]en eingesetzt.
 
'''Unterschiede'''
{| class = "wikitable" style = "table-layout: fixed; max-width: 48em;"
! style="width: 50%;" | Relation
! style="width: 50%;" | Tabelle
|-
| style="vertical-align:top;" | '''duplikatfrei''': Relationen sind {{Menge}}n, daher kommt kein [[Tupel]] zweimal vor.
| style="vertical-align:top;" | '''Duplikate''': Tabellen sind [[Liste]]n, daher können gleiche Tupel mehrfach vorkommen.<br/>
Allerdings gilt dies in SQL nur bei berechneten Tabellen, nicht aber bei gespeicherten Tabellen.
|-
| style="vertical-align:top;" | '''ungeordnet''': Relationen sind Mengen, daher sind die darin enthaltenen Tupel nicht geordnet.<br/>
In einer Relationalen Algebra kann es keine Operation zum Sortieren von Relationen geben.
| style="vertical-align:top;" | '''geordnet''':  Tabellen sind (geordnete) Listen, daher ist die Reihenfolge der Tupel festgelegt.<br/>
Allerdings kann man sich bei SQL-Befehlen nicht darauf verlassen, dass das Ergebnis in einer bestimmten Reihenfolge ausgegeben wird. In SQL gibt es daher eine spezielle [[ORDER-BY-Klausel]], um eine bestimmte Reihenfolge zu erzwingen.
|}
 
Außerdem werden in SQL (tabellen-)Zeilen (Rows) an Stelle von Tupeln verwendet. In Tabellenzeilen sind die einzelnen Spalten benannt und haben überdies eine Position.
 
Die klassische Tupel-Definition unterscheidet die verschiedenen Attribute anhand ihrer Position. Allerdings ist es nicht unüblich, diesen Positionen Namen zu geben. So wird bei einer Raumkoordinate die erste Position {{iAllg}} mit $x$ bezeichnet, die zweite mit $y$ und die dritte mit $z$.
 
In Programmiersprachen heißen Tupel, deren Elemente über die Position bestimmt werden, [[Array]]s oder [[Liste]]n: <code>[35, true, 'Hallo']</code>.
Tupel deren Elemente mittels Identifikatoren unterschieden werden, heißen [[Record]]s, [[Hashmap]]s/[[Hasharray]]s oder auch – {{zB}} in [[JavaScript]] – [[Objekt]]e: <code>{a: 35, b: true, c: 'Hallo'}</code>
 
==Relationale Operationen==
 
===Identität===
[[Datei:Tabelle.png | mini|200px | rechts |gerahmt|Die Identitätsfunktion verändert eine Tabelle nicht.]]
 
Die Identiätsfunktion liefert als Ergebnis stets die Urbildrelation zurück. Das heißt, sie verändert eine Relation nicht.
 
Die Identitätsfunktion ist die einzige [[totale Funktion]] der Relationalen Algebra. Das heißt, sie kann auf jede beliebige Relation angewendet werden.
 
In [[SQL]] wird eine derartige Funktion benötigt, um den gesamten Inhalt einer Relation zu erfragen, da in jeder
SQL-Anweisung zum Lesen von Dateninhalten mindestens eine relationale Operation enthalten sein muss.
 
In [[SQL 92]]<ref>{{Quelle|Date, Darwen (1993)}}</ref>
wurde zu diesem Zweck der Befehl <code>table</code> eingeführt, dessen einzige Aufgabe es war, die ihm übergebene
Tabelle (Relation) vollständig auszugeben. Dieser Befehl hat sich jedoch nicht durchgesetzt
(auch wenn [[PostgreSQL]] ihn unterstützt<ref>https://www.postgresql.org/docs/current/static/sql-select.html PostgreSQL: Select</ref>).
 
So ist es kein Wunder, dass diese Identitätsfunktion in  [[SQL 99]]<ref>{{Quelle|Gulutzan, Pelzer (1999)}}</ref>
nicht mehr enthalten ist. Das ist auch nicht notwendig, da eine Projektion, die alle Attribute einer Relation unverändert zurück gibt,
ebenfalls als Identitätsfunktion verwendet werden kann (siehe nachfolgenden Abschnitt).
 
'''Beispiel'''
{|
! style="text-align:center;" | $r$
! style="text-align:center;" | →
! style="text-align:center;" | $id(r)$
!                                        | &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
! style="text-align:left; padding: 0.2em" | SQL
|-
|
  {| class="wikitable" style="margin: 0.5em 0 0 0"
  ! $a_1$ || $a_2$ || $a_3$ || $a_4$ || $a_5$
  |-
  | a || b || c || 5 || 13
  |-
  | a || d || b || 7 || 17
  |-
  | c || f || g ||  3 || 21
  |}
| →
|
  {| class="wikitable" style="margin: 0.5em 0 0 0"
  !  $a_1$ || $a_2$ || $a_3$ || $a_4$ || $a_5$
  |-
  | a || b || c || 5 || 13
  |-
  | a || d || b || 7 || 17
  |-
  | c || f || g ||  3 || 21
  |}
|
| style="vertical-align:top;" | <code>TABLE r</code>
|}
===Projektion===
[[Datei:Projektion.png | mini|200px | rechts |gerahmt|Eine Projektionsfunktion entfernt Spalten aus einer Tabelle und sortiert sie gegebenenfalls um.]]
[[Datei:ProjektionBerechnung.png | mini|200px | rechts |gerahmt|Genauer: Eine Projektionsfunktion berechnet neue Spalteninhalte aus den alten Spalteninhalten. Dabei entstehende Duplikattupel  werden ebenfalls entfernt.]]
 
Die Projektionsfunktion $\pi$ wurde von Codd eingeführt, um Attribute einer Relation entfernen können. Außerdem führte  Codd noch eine Permutationsfunktion ein, um die Reihenfolge der Attribute zu ändern.<ref name="Codd 1969">{{Quelle|Codd (1969)}}</ref><ref name="Codd 1970">{{Quelle|Codd (1970)}}</ref>
 
In der Zwischenzeit wird die Projektionsfunktion allgemeiner definiert. Sie berechnet für jedes Tupel einer Relation aus dessen Attributwerten ein neues Tupel.
Für die Benennung der neuen Attributwerte ist ebenfalls die Projektionsfunktion zuständig. Insbesondere ist die Permutationsfunktion damit überflüssig geworden. Deren
Aufgabe wird von der Projektionsfunktion ebenfalls wahrgenommen.
 
Man beachte, dass nur für Tupel mit Positionsattributen der Begriff [[Permutation]] sinnvoll ist (<code>[10,30]</code> und <code>[30,10]</code>bezeichnen zwei
verschiedene Punkte in einer Ebene). Für Tupel mit Attributnamen benötigt man dagegen keine Funktion, die Attribute vertauscht, da benannte Attribute keine Positionen besitzen (<code>{x: 10, y: 30}</code> und <code>{y: 30, x: 10}</code>bezeichnen denselben Punkt in einer Ebene). Hier muss eine Permutationsfunktion Attributnamen
umbenennen können (mittels der $as$-Operation).
 
Beachten Sie bitte: Die folgenden Beispiele funktionieren sowohl für Positionsattribute als auch für benannte Attribute als auch für Rows, bei denen Attribute sowohl eine Position als auch einen Namen haben.
 
'''Beispiele'''
{|
! style="text-align:center;" | $r$
! style="text-align:center;" | →
! style="text-align:center;" | $\pi_{a_4, \,a_1}(r)$
!                                        | &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
! style="text-align:left; padding: 0.2em" | SQL
|-
|
  {| class="wikitable" style="margin: 0.5em 0 0 0"
  !  $a_1$ || $a_2$ || $a_3$ || $a_4$ || $a_5$
  |-
  | c || b || c || 5 || 13
  |-
  | a || d || g || 7 || 17
  |-
  | a || f || g ||  3 || 21
  |}
| →
|
  {| class="wikitable" style="margin: 0.5em 0 0 0"
  ! $a_4$ || $a_1$
  |-
  | 5 || c
  |-
  | 7 || a
  |-
  | 3 || a
  |}
|
| style="vertical-align:top;" | <code>SELECT a4, a1 FROM r</code>
|}
 
'''Anmerkung''': $\pi_{a_4, \,a_1}(r)$ ist eine Abkürzung für $\pi_{a_4 \rm{\,as\,} a_4, \,a_1 \rm{\,as\,} a_1}(r)$.
 
Attribute können auch berechnet und (um-)benannt werden. Duplikate, wie {{zB}} (a, g, 24), werden (in der Relationalen Algebra, nicht in SQL!) automatisch entfernt.
{|
! style="text-align:center;" | $r$
! style="text-align:center;" | →
! style="text-align:center;" | $\pi_{a_1, \,a_3, \,a_4+a_5 \rm{\,as\,} b_1}(r)$
!                                        | &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
! style="text-align:left; padding: 0.2em" | SQL
|-
| style="vertical-align:top;" |
  {| class="wikitable" style="margin: 0.5em 0 0 0"
  !  $a_1$ || $a_2$ || $a_3$ || $a_4$ || $a_5$
  |-
  | c || b || c || 5 || 13
  |-
  | a || d || g || 7 || 17
  |-
  | a || f || g ||  3 || 21
  |}
| →
| style="vertical-align:top;" |
  {| class="wikitable" style="margin: 0.5em 0 0 0"
  ! $a_1$ || $a_3$ || $b_1$
  |-
  | c || a || 18
  |-
  | a || g || 24
  |}
|
| style="vertical-align:top;" | <code>SELECT a4, a3, a4+a5 AS b1<br/>FROM r</code>
|}
 
Die Identitätsfunktion kann – wie es bereits weiter oben angesprochen wurde – mit Hilfe der Projektionsfunktion nachgebildet werden. Allerdings benötigt man für jede
Relation eine spezielle Projektionsfunktion. In der Projektiosnliste müssen alle Attribute der zugehörigen Funktion genau einmal aufgeführt werden:
 
{|
! style="text-align:center;" | $r$
! style="text-align:center;" | →
! style="text-align:center;" | $\pi_{a_1, \,a_2, \,a_3, \,a_4, \,a_5}(r)$
!                                        | &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
!! style="text-align:left; padding: 0.2em" | SQL
|-
| style="vertical-align:top;" |
  {| class="wikitable" style="margin: 0.5em 0 0 0"
  !  $a_1$ || $a_2$ || $a_3$ || $a_4$ || $a_5$
  |-
  | c || b || c || 5 || 13
  |-
  | a || d || g || 7 || 17
  |-
  | a || f || g ||  3 || 21
  |}
| →
| style="vertical-align:top;" |
  {| class="wikitable" style="margin: 0.5em 0 0 0"
  !  $a_1$ || $a_2$ || $a_3$ || $a_4$ || $a_5$
  |-
  | c || b || c || 5 || 13
  |-
  | a || d || g || 7 || 17
  |-
  | a || f || g ||  3 || 21
  |}
|
| style="vertical-align:top;" | <code>SELECT a1, a2, a3, a4, a5 FROM r;</code>
<!--                                  --><code>SELECT r.* &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;FROM r;</code>
 
<!--                                  --><code>SELECT *&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;FROM r;</code>
|}
 
In SQL kann man abkürzend den Stern „<code>*</code>“ verwenden. Dieser bezeichnet alle Attribute der aktuellen Relation.
Mit <code>r.*</code> werden in SQL alle Attribute der Relation <code>r</code>  bezeichnet. Für das obige Beispiel kann man in der
Relationalen Algebra analog folgenden Abkürzungen definieren:
 
$ r = \pi_{a_1, \,a_2, \,a_3, \,a_4, \,a_5}(r) =  \pi_{r.*}(r) =  \pi_{*}(r) = id(r)$
 
Mit dem Stern-Operator man also eine alternative Definition der Identitätsfunktion mit Hilfe des Projektionsoperators angeben, die ohne die Attributnamen der jeweiligen Relation  auskommt. (In SQL ist die Verwendung des Sternoperator allerdings verpönt, da sich die Attribute einer Tabelle im Laufe der Zeit ändern können ([[Schemaevolution]]) und sich damit die Bedeutung des Sterns ändert. Das heißt, Anfragen, die einen <code>*</code> enthalten, können plötzlich weniger, mehr oder andere Spalten im Ergebnis liefern.)
 
===Selektion===
[[Datei:Selektion.png | mini|200px | rechts |gerahmt|Eine Selektionsfunktion entfernt Zeilen (= [[Tupel]]) aus einer Tabelle.]]
 
{|
! style="text-align:center;" | $r$
! style="text-align:center;" | →
! style="text-align:center;" | $\sigma_{a_1= \tt{'a'}}(r)$
!                                        | &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
!! style="text-align:left; padding: 0.2em" | SQL
|-
| style="vertical-align:top;" |
  {| class="wikitable" style="margin: 0.5em 0 0 0"
  !  $a_1$ || $a_2$ || $a_3$ || $a_4$ || $a_5$
  |-
  | c || b || c || 5 || 13
  |-
  | a || d || g || 7 || 17
  |-
  | a || f || g ||  3 || 21
  |}
| →
| style="vertical-align:top;" |
  {| class="wikitable" style="margin: 0.5em 0 0 0"
  !  $a_1$ || $a_2$ || $a_3$ || $a_4$ || $a_5$
  |-
  | a || d || g || 7 || 17
  |-
  | a || f || g ||  3 || 21
  |}
|
| style="vertical-align:top;" | <code>SELECT *<br/>FROM r<br/>WHERE a2 = 'a';</code>
|}
 
{|
! style="text-align:center;" | $r$
! style="text-align:center;" | →
! style="text-align:center;" | $\sigma_{a_1 = \tt{'a'} \,\wedge\, a_5<21}(r)$
!                                        | &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
!! style="text-align:left; padding: 0.2em" | SQL
|-
| style="vertical-align:top;" |
  {| class="wikitable" style="margin: 0.5em 0 0 0"
  !  $a_1$ || $a_2$ || $a_3$ || $a_4$ || $a_5$
  |-
  | c || b || c || 5 || 13
  |-
  | a || d || g || 7 || 17
  |-
  | a || f || g ||  3 || 21
  |}
| →
| style="vertical-align:top;" |
  {| class="wikitable" style="margin: 0.5em 0 0 0"
  !  $a_1$ || $a_2$ || $a_3$ || $a_4$ || $a_5$
  |-
  | a || d || g || 7 || 17
  |}
|
| style="vertical-align:top;" | <code>SELECT *<br/>FROM r<br/>WHERE a1 = 'a' AND a5 < 20;</code>
|}
 
===Kartesisches Produkt===
[[Datei:KartesischesProdukt.png | mini|440px | rechts |gerahmt|Das Kartesische Produkt verknüpft alle möglichen Tupelpaare zu jeweils einem Tupel, das alle Attribute beider Tupel enthält.]]
 
{|
! style="text-align:center;" | $r$
! style="text-align:center;" | $\times$
! style="text-align:center;" | $s$
! style="text-align:center;" | →
! style="text-align:center;" | $r $
!                                        | &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
!! style="text-align:left; padding: 0.2em" | SQL
|-
| style="vertical-align:top;" |
  {| class="wikitable" style="margin: 0.5em 0 0 0"
  !  $a_1$ || $a_2$ || $a_3$ || $a_4$ || $a_5$
  |-
  | c || b || c || 5 || 13
  |-
  | a || d || g || 7 || 17
  |-
  | a || f || g ||  3 || 21
  |}
| $\times$
| style="vertical-align:top;" |
  {| class="wikitable" style="margin: 0.5em 0 0 0"
  !  $a_1$ || $a_2$ || $a_3$ || $a_4$ || $a_5$
  |-
  | c || b || c || 5 || 13
  |-
  | a || d || g || 7 || 17
  |-
  | a || f || g ||  3 || 21
  |}
| →
| style="vertical-align:top;" |
  {| class="wikitable" style="margin: 0.5em 0 0 0"
  !  $a_1$ || $a_2$ || $a_3$ || $a_4$ || $a_5$
  |-
  | a || d || g || 7 || 17
  |-
  | a || f || g ||  3 || 21
  |}
|
| style="vertical-align:top;" | <code>SELECT *<br/>FROM r<br/>WHERE a2 = 'a';</code>
|}
 
===Join===
Ein Join ist formal nichts weiter, als ein Kartesisches Produkt gefolgt von einer Selektion.
<!--
===Mengen-Operationen: Vereinigung, Durchschnitt, Differenz, Symmetrische Differenz===
<div>
<span style="float: right;"> [[Datei:SymmetrischeDifferenzTabellen.png | mini|200px|gerahmt|Symmetrische Differenz]] </span>
<span style="float: right;"> [[Datei:DifferenzTabellen.png | mini|200px|gerahmt|Differenz]] </span>
<span style="float: right;"> [[Datei:DurchschnittTabellen.png | mini|200px|gerahmt|Durchschnitt]] </span>
<span style="float: right;"> [[Datei:VereinigungTabellen.png | mini|200px|gerahmt|Vereinigung]] </span>
</div>
-->
==Quellen==
 
<references/>
<ol>
<li value="7">{{Quelle|Ullman (1988)}}</li>
<li>{{Quelle|Ullman (1989)}}</li>
<li>{{Quelle|Garcia-Molina, Ullman, Widom (2002)}}</li>
<li>{{Quelle|Elmasri, Navathe (2011)}}</li>
</ol>
{{TBD|$⨝$, <math>⟕</math>, <math>⟖</math>, <math>⟗</math>, $\triangle$}}
 
[[Kategorie:Algebraische Struktur]]
[[Kategorie:Mathematische Definition]]
[[Kategorie:Datenmanagement]]
[[Kategorie:Glossar]]

Version vom 25. April 2019, 16:11 Uhr