Relationale Algebra: Unterschied zwischen den Versionen

aus GlossarWiki, der Glossar-Datenbank der Fachhochschule Augsburg
Keine Bearbeitungszusammenfassung
Keine Bearbeitungszusammenfassung
Zeile 7: Zeile 7:
}}
}}


==Definition ([[Wolfgang kowarschick|Kowarschick]] (2018))==
==Definition ([[Wolfgang Kowarschick|Kowarschick]] (2018))==


Eine [[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.
Eine [[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.
Zeile 20: Zeile 20:
* <math>\cap: R, R \rightharpoonup R</math> ermittelt die Differenz zweier (strukturgleicher) Relationen.
* <math>\cap: R, R \rightharpoonup R</math> ermittelt die Differenz zweier (strukturgleicher) Relationen.


==Amkerkung==
==Anmerkung==


Die Relationale Algebra wurde 1969 von [[Edgar Frank Codd]] eingeführt, um große Datenbanken (“large data banks”)
Die ersten Elemente der Relationale Algebra (Projektion und Join) wurde 1969/1970 von [[Edgar Frank Codd]] eingeführt, um große Datenbanken (“large data banks”)
zu verwalten:
zu verwalten<ref name="Codd 1969">{{Quelle|Codd (1969)}}</ref><ref name="Codd 1970">{{Quelle|Codd (1970)}}</ref>. Im ersten Satz
des Abstract seines internen Reports „Derivability, Redundancy and Consistency of Relations Stored in Large Data Banks“
mach Codd eine geradezu prophetische Aussage:


{{Quote|The large, integrated data banks of the future will
{{Quote|The large, integrated data banks of the future will
contain many relations of various degrees in stored form. It
contain many relations of various degrees in stored form. (Codd (1969)<ref name="Codd 1969"/>)
will not be unusual for this set of stored relations to be
redundant. Two types of redundancy are defined and discussed.
One type may be employed to improve accessibility of certain
kinds of information which happen to be in great demand. When
either type of redundancy exists, those responsible for control
of the data bank should know about it and have some means of
detecting any “logical” inconsistencies in the total set of
stored relations. Consistency checking might be helpful in
tracking down unauthorized (and possibly fraudulent) changes
in the data bank contents.
}}  
}}  
Ü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,
das 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]].


==Relationale Operationen==
==Relationale Operationen==


===Identität===
===Identität===
[[Datei:Tabelle.png | 150px | rechts |]]
[[Datei:Tabelle.png | mini|150px | 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.
 
In [[SQL]] wird eine derartige Funktion benötigt, um den gesamten Inhalt einer Relation zu erfragen, da in jeder
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, ohne ihn allerdings in der Dokumentation zu erwähnen).
 
So ist es kein Wunder, 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'''
'''Beispiel'''
Zeile 60: Zeile 79:
   | c || f || g
   | c || f || g
   |}
   |}
|  
| →
|
|
   {| class="wikitable"
   {| class="wikitable"
Zeile 73: Zeile 92:
|}
|}
==Quellen==
==Quellen==
*{{Quelle|Codd (1969)}}
 
*{{Quelle|Codd (1970)}}
*
*
*
*
<references/>
<references/>
<ol>
<ol>
<li value="3">{{Quelle|Ullman (1988)}}</li>
<li value="7">{{Quelle|Ullman (1988)}}</li>
<li value="3">{{Quelle|Ullman (1989)}}</li>
<li>{{Quelle|Ullman (1989)}}</li>
<li value="3">{{Quelle|Garcia-Molina, Ullman, Widom (2002)}}</li>
<li>{{Quelle|Garcia-Molina, Ullman, Widom (2002)}}</li>
<li value="3">{{Quelle|Elmasri, Navathe (2011)}}</li>
<li>{{Quelle|Elmasri, Navathe (2011)}}</li>
</ol>
</ol>
{{TBD|$⨝$, <math>⟕</math>, <math>⟖</math>, <math>⟗</math>, $\triangle$}}
{{TBD|$⨝$, <math>⟕</math>, <math>⟖</math>, <math>⟗</math>, $\triangle$}}

Version vom 16. Mai 2018, 13:45 Uhr

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 \rm{as} a_1, \ldots, f_n \rm{as} a_n}: R \rightharpoonup R $ sind die so genannten Projektionsfunktionen, die mit Hilfe von Projektionsfunktionen $f_i$ für jedes Tupel $n$ 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.
  • $ \cap: R, R \rightharpoonup R $ ermittelt die Differenz zweier (strukturgleicher) Relationen.

Anmerkung

Die ersten Elemente der Relationale Algebra (Projektion und Join) wurde 1969/1970 von Edgar Frank Codd eingeführt, um große Datenbanken (“large data banks”) zu verwalten[1][2]. Im ersten Satz des Abstract seines internen Reports „Derivability, Redundancy and Consistency of Relations Stored in Large Data Banks“ mach 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, das 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 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.

In SQL wird eine derartige Funktion benötigt, um den gesamten Inhalt einer Relation zu erfragen, da in jeder 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, ohne ihn allerdings in der Dokumentation zu erwähnen).

So ist es kein Wunder, diese Identitätsfunktion in SQL 99[6] 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)
a1 a2 a3
a b c
a d b
c f g
→
a1 a2 a3
a b c
a d b
c f g

Quellen

  1. ↑ 1,0 1,1 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. ↑ 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)
  3. ↑
  4. ↑ 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)
  5. ↑ 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)
  6. ↑ 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)
  1. 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)
  2. 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)
  3. 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)
  4. 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$
Abgerufen von „https://glossar.hs-augsburg.de/w/index.php?title=Relationale_Algebra&oldid=44619“