Relationale Algebra
Dieser Artikel erfüllt die GlossarWiki-Qualitätsanforderungen nur teilweise:
| Korrektheit: 2 (teilweise überprüft) |
Umfang: 1 (zu gering) |
Quellenangaben: 3 (wichtige Quellen vorhanden) |
Quellenarten: 5 (ausgezeichnet) |
Konformität: 5 (ausgezeichnet) |
Definition (Kowarschick (2018))
Eine Algebra $ \mathcal{R} = (R, id, \pi, \sigma, \times, \div, \cup, \cap, \setminus) $ heißt Relationale Algebra wenn die Trägermenge oder -klasse $ R $ eine Menge bzw. Klasse von Relationen mit benannten Attributen ist.
- $ id: R \rightarrow R $ ist die so genannte Identitätsfunktion: Es gilt stets $ id(r) = r $
- $ \pi_{f_1 \,\text{as}\, a_1, \,\ldots, \,f_n \,\text{as}\, a_n}: R \rightharpoonup R $ 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$.
- $ \sigma_b: R \rightharpoonup R $ sind die so genannte Selektionsfunktionen: Mit ihrer Hilfe werden aus einer Relation diejenigen Tupel selektiert, die die Bedingung $b$ erfüllen.
- $ \times: R, R \rightharpoonup R $ 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.
- $ \div: R, R \rightharpoonup R $ ist die Division. Im Prinzip ist dies die Umkehrfunktion des kartesischen Produktes.
- $ \cup: R, R \rightharpoonup R $ ermittelt die Vereinigung zweier (strukturgleicher) Relationen.
- $ \cap: R, R \rightharpoonup R $ ermittelt den Durchschnitt zweier (strukturgleicher) Relationen.
- $ \setminus: R, R \rightharpoonup R $ ermittelt die Differenz zweier (strukturgleicher) Relationen.
SQL
Die Relationale Algebra ist Grundlage der Datenbank-Sprache SQL. In SQL werden allerdings Tabellen an Stelle von Relationen eingesetzt.
Unterschiede
| Relation | Tabelle |
|---|---|
| duplikatfrei: Relationen sind Mengen, daher kommt kein Tupel zweimal vor. | Duplikate: Tabellen sind Listen, daher können Tupel mehrfach vorkommen. Allerdings gilt dies in SQL nur bei berechneten Tabellen, nicht aber bei gespeicherten Tabellen. |
| ungeordnet: Relationen sind Mengen, daher sind die darin enthaltenen Tupel nicht geordnet. In einer Relationalen Algebra kann es keine Operation zum Sortieren von Relationen geben. |
geordnet: Tabellen sind (geordnete) Listen, daher ist die Reihenfolge der Tupel festgelegt. 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. |
Anmerkung
1969/1970 schlägt Edgar Frank Codd vor, Relationen zu verwenden, um große Datenbanken (“large data banks”) zu verwalten[1][2]. 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:
The large, integrated data banks of the future will contain many relations of various degrees in stored form. (Codd (1969)[1])
Übersetzung (von Kowarschick):
Die großen, integrierten Datenbanken der Zukunft werden viele Relationen unterschiedlichsten Grades in gespeicherter Form enthalten.
Ende 1970, d. h. 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.[3][4]
In den 70er Jahren begann auf Basis dieser beiden Arbeiten die Erfolgsgeschichte der Relationalen Datenbanken einschließlich der zugehörigen Sprache SQL.
Relationale Operationen
Identität
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[5]
wurde zu diesem Zweck der Befehl table 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[6]).
So ist es kein Wunder, dass diese Identitätsfunktion in SQL 99[7] 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
| R | → | $id$(R) | ||||||||||||||||||||||||||||||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
|
→ |
|
Projektion
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.[1][2]
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.
Beispiele
| R | → | $\pi_{a4, a1}$(R) | ||||||||||||||||||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
|
→ |
|
Attribute können auch berechnet und (um-)benannt werden. Duplikate, wie z. B. (a, g, 24), werden (in der Relationalen Algebra, nicht in SQL!) automatisch entfernt.
| R | → | $\pi_{a1, a3, a4+a5 \rm{\,as\,} b1}$(R) | |||||||||||||||||||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
|
→ |
|
Selektion
Quellen
- ↑ 1,0 1,1 1,2 Codd (1969): Edgar Frank Codd; Derivability, Redundancy and Consistency of Relations Stored in Large Data Banks; in: ACM SIGMOD Record; Band: 38; Nummer: 1; Seite(n): 17–36; Verlag: Association for Computing Machinery; Adresse: New York; Web-Link; 2009; Quellengüte: 5 (Artikel)
- ↑ 2,0 2,1 Codd (1970): Edgar Frank Codd; A Relational Model of Data for Large Shared Data Banks; in: Communications of the ACM; Band: 13; Nummer: 6; Seite(n): 377-387; Verlag: Association for Computing Machinery; Adresse: New York; Web-Link; 1970; Quellengüte: 5 (Artikel)
- ↑
- ↑ Bayer, McCreight (1972): Rudolf Bayer und Edward M. McCreight; Organization and Maintenance of Large Ordered Indexes; in: Acta Informatica; Band: 1; Nummer: 3; Seite(n): 173-189; Verlag: Springer-Verlag; Web-Link; 1972; Quellengüte: 5 (Artikel)
- ↑ Date, Darwen (1993): Christopher J. Date und Hugh Darwen; A Guide to the SQL Standard – A user's guid to the standard relational language SQL; Auflage: 3; Verlag: Addison-Wesley; Adresse: Reading, Massachusetts, USA; 1993; Quellengüte: 5 (Buch)
- ↑ [https://www.postgresql.org/docs/current/static/sql-select.html PostgreSQL: Select
- ↑ Gulutzan, Pelzer (1999): Peter Gulutzan und Trudy Pelzer; SQL-99 complete, Really – An Example-Based Reference Manual of the New Standard; Verlag: R&D Books; ISBN: 0-87930-568-1; 1999; Quellengüte: 5 (Buch)
- Ullman (1988): Jeffrey D. Ullman; Principles of Database and Knowledge-Base Systems – Volume I: Classical Database Systems; Verlag: Computer Science Press; Adresse: New York, Oxford; ISBN: 0-7167-8158-1; Web-Link; 1988; Quellengüte: 5 (Buch)
- Ullman (1989): Jeffrey D. Ullman; Principles of Database and Knowledge-Base Systems – Volume II: The New Technologies; Verlag: Computer Science Press; Adresse: New York, Oxford; ISBN: 0-7167-8069-O, 0-7167-8182-X; Web-Link; 1989; Quellengüte: 5 (Buch)
- Garcia-Molina, Ullman, Widom (2002): Hector Garcia-Molina, Jeffrey D. Ullman und Jennifer Widom; Database Systems: The Complete Book; Verlag: Prentice Hall; Adresse: New Jersey, Upper Saddle River; ISBN: 0-13-031995-3; Web-Link; 2002; Quellengüte: 5 (Buch)
- Elmasri, Navathe (2011): Ramez Elmasri und Shamkant B. Navathe; Fundamentals of Database Systems; Auflage: 3; Verlag: Pearson Studium; ISBN: 978-0-136-08620-8; 2011; Quellengüte: 5 (Buch)
TO BE DONE
- $⨝$, $ ⟕ $, $ ⟖ $, $ ⟗ $, $\triangle$
