Historische Entwicklung relationaler DBMS

Historische Entwicklung relationaler DBMSTed Codd: A Relational Model of Data for Large Shared Data Banks, Comm. ACM, Juni 1970, S. 377–387

Grundlagen des relationalen ModellsSeien D1, D2, ..., Dn Domänen (~Wertebereiche) Relation: R D1 x ... x Dn

Bsp.: Telefonbuch string x string x integer

Tupel: t RBsp.: t = („Mickey Mouse“, „Main Street“, 4711)

Schema: legt die Struktur der gespeicherten Daten festBsp.:

Telefonbuch: {[Name: string, Adresse: string, Telefon#:integer]}

Teilmenge des Kreuzprodukts

Name X Adresse X Telefon#

TelefonbuchName Straße Telefon#

Mickey Mouse Main Street 4711Minnie Mouse Broadway 94725Donald Duck Broadway 95672

... ... ...

• Ausprägung: der aktuelle Zustand der Datenbasis• Schlüssel: minimale Menge von Attributen, deren

Werte ein Tupel eindeutig identifizieren• Primärschlüssel: wird unterstrichen

• Einer der Schlüsselkandidaten wird als Primärschlüssel ausgewählt

• Hat eine besondere Bedeutung bei der Referenzierung von Tupeln

Studenten

Assistenten

MatrNr

PersNr

Semester

Name

Name

Fachgebiet

Note

hören

prüfen

arbeitenFür Professoren

Vorlesungen

lesen

voraussetzen

SWS

VorlNr

Titel

Raum

Rang

PersNr

Nach-folgerVorgänger

Name

Uni-Schema

1

N

1

1

N N

N

M

MMN

Relationale Darstellung von EntitytypenStudenten: {[MatrNr:integer, Name: string, Semester:

integer]}

Vorlesungen: {[VorlNr:integer, Titel: string, SWS: integer]}

Professoren: {[PersNr:integer, Name: string, Rang: string, Raum: integer]}

Assistenten: {[PersNr:integer, Name: string, Fachgebiet: string]}

Relationale Darstellung von Beziehungen

A11 E1

R

... AR1

EnE2 An1

A21

... ...

...

...

11kA

R

RkA

nnkA22kA

R von Attribute

1

E von Schlüssel

1

E von Schlüssel

221

E von Schlüssel

111 ,...,,,...,,...,,...,,,....,

n2

2

1

1

Rk

Rnknkk Rn

AAAAAAAAR:{[ ]}

Beziehungen unseres Beispiel-Schemas

hören : {[MatrNr: integer, VorlNr: integer]}

lesen : {[PersNr: integer, VorlNr: integer]}

arbeitenFür : {[AssistentenPersNr: integer, ProfPersNr: integer]}

voraussetzen : {[Vorgänger: integer, Nachfolger:

integer]}

prüfen : {[MatrNr: integer, VorlNr: integer, PersNr:

integer, Note: decimal]}

Studenten

MatrNr

Semester

Name hören Vorlesungen SWS

VorlNr

Titel

MN

Beziehungen unseres Beispiel-Schemas





integer]}



Schlüssel der Relationen





integer]}



Ausprägung der Beziehung hörenStudenten

MatrNr ...26120 ...27550 ...

... ...

hörenMatrNr VorlNr26120 500127550 500127550 405228106 504128106 505228106 521628106 525929120 500129120 504129120 504929555 502225403 502229555 5001

VorlesungenVorlNr ...5001 ...4052 ...

... ...

Studentenhören

VorlesungenMN

MatrNr VorlNr

Verfeinerung des relationalen Schemas

1:N-Beziehung Initial-Entwurf

Vorlesungen : {[VorlNr, Titel, SWS]}

Professoren : {[PersNr, Name, Rang, Raum]}

lesen: {[VorlNr, PersNr]}

Professoren Vorlesungenlesen1 N

Verfeinerung des relationalen Schemas

1:N-Beziehung Initial-Entwurf

Vorlesungen : {[VorlNr, Titel, SWS]}Professoren : {[PersNr, Name, Rang, Raum]}lesen: {[VorlNr, PersNr]}

Verfeinerung durch ZusammenfassungVorlesungen : {[VorlNr, Titel, SWS,

gelesenVon]}Professoren : {[PersNr, Name, Rang, Raum]}

RegelRelationen mit gleichem Schlüssel kann man

zusammenfassenaber nur diese und keine anderen!


Ausprägung von Professoren und Vorlesung

ProfessorenPersN

rName Ran

gRaum

2125 Sokrates C4 2262126 Russel C4 2322127 Kopernikus C3 3102133 Popper C3 522134 Augustinus C3 3092136 Curie C4 362137 Kant C4 7

VorlesungenVorlNr Titel SWS Gelesen

Von5001 Grundzüge 4 21375041 Ethik 4 21255043 Erkenntnistheorie 3 21265049 Mäeutik 2 21254052 Logik 4 21255052 Wissenschaftstheo

rie3 2126

5216 Bioethik 2 21265259 Der Wiener Kreis 2 21335022 Glaube und

Wissen2 2134

4630 Die 3 Kritiken 4 2137Professoren Vorlesungenlesen

1 N

Vorsicht: So geht es NICHT

ProfessorenPersN

rName Ran

gRaum liest

2125 Sokrates C4 226 50412125 Sokrates C4 226 50492125 Sokrates C4 226 4052

... ... ... ... ...2134 Augustinus C3 309 50222136 Curie C4 36 ??

VorlesungenVorlNr Titel SWS5001 Grundzüge 45041 Ethik 45043 Erkenntnistheorie 35049 Mäeutik 24052 Logik 45052 Wissenschaftstheo

rie3

5216 Bioethik 25259 Der Wiener Kreis 25022 Glaube und

Wissen2

4630 Die 3 Kritiken 4


Vorsicht: So geht es NICHT:FolgenAnomalien

Update-Anomalie: Was passiert wenn Sokrates umzieht Lösch-Anomalie: Was passiert wenn „Glaube und

Wissen“ wegfällt Einfügeanomalie: Curie ist neu und liest noch keine

Vorlesungen

ProfessorenPersN

rName Ran

gRaum liest

2125 Sokrates C4 226 50412125 Sokrates C4 226 50492125 Sokrates C4 226 4052

... ... ... ... ...2134 Augustinus C3 309 50222136 Curie C4 36 ??

VorlesungenVorlNr Titel SWS5001 Grundzüge 45041 Ethik 45043 Erkenntnistheorie 35049 Mäeutik 24052 Logik 45052 Wissenschaftstheo

rie3

5216 Bioethik 25259 Der Wiener Kreis 25022 Glaube und

Wissen2

4630 Die 3 Kritiken 4

Vermeidung von Null-Werten

Menschen Bundesländer

MP

Wohnsitz

MdL

Nr

Name

Name

EW

1

N

1

1

1N


MP

Wohnsitz

MdL

Nr

Name

Name

EW

1

N

1

1

1N


MP

Wohnsitz

MdL

Nr

Name

Name

EW


MP

Wohnsitz

MdL

Nr

Name

Name

EW

Relationale Modellierung der Generalisierung

Fachgebiet

Assistenten

Professoren

Raum Rang

is_a Angestellte

PersNr Name

Angestellte: {[PersNr, Name]}Professoren: {[PersNr, Rang, Raum]}Assistenten: {[PersNr, Fachgebiet]}

Relationale Modellierung schwacher Entitytypen

Studenten ablegen Prüfungen1 N Note

PrüfTeil

MatrNr

Vorlesungen

umfassen

VorlNr

abhalten

Professoren

PersNr

N N

M M

Prüfungen: {[MatrNr: integer, PrüfTeil: string, Note: integer]}

umfassen: {[MatrNr: integer, PrüfTeil: string, VorlNr: integer]}

abhalten: {[MatrNr: integer, PrüfTeil: string, PersNr: integer]}

Man beachte, dass in diesem Fall der (global eindeutige) Schlüssel der Relation Prüfung nämlich MatrNr und PrüfTeil als Fremdschlüssel in die Relationen umfassen und abhalten übernommen werden muß.

Fremdschlüssel auf ein schwaches Entity

Die relationale Uni-DBProfessoren

PersNr Name Rang Raum2125 Sokrates C4 2262126 Russel C4 2322127 Kopernikus C3 3102133 Popper C3 522134 Augustinus C3 3092136 Curie C4 362137 Kant C4 7

StudentenMatrNr Name Semester24002 Xenokrates 1825403 Jonas 1226120 Fichte 1026830 Aristoxenos 827550 Schopenhau

er6

28106 Carnap 329120 Theophrasto

s2

29555 Feuerbach 2

VorlesungenVorlNr Titel SWS gelesen

von5001 Grundzüge 4 21375041 Ethik 4 21255043 Erkenntnistheorie 3 21265049 Mäeutik 2 21254052 Logik 4 21255052 Wissenschaftstheor

ie3 2126

5216 Bioethik 2 21265259 Der Wiener Kreis 2 21335022 Glaube und Wissen 2 21344630 Die 3 Kritiken 4 2137

voraussetzenVorgänger Nachfolger

5001 50415001 50435001 50495041 52165043 50525041 50525052 5259

hörenMatrNr VorlNr26120 500127550 500127550 405228106 504128106 505228106 521628106 525929120 500129120 504129120 504929555 502225403 5022

AssistentenPerslN

rName Fachgebiet Boss

3002 Platon Ideenlehre 21253003 Aristoteles Syllogistik 21253004 Wittgenstein Sprachtheorie 21263005 Rhetikus Planetenbewegun

g2127

3006 Newton Keplersche Gesetze

2127

3007 Spinoza Gott und Natur 2126

prüfenMatrNr VorlNr PersNr Note28106 5001 2126 125403 5041 2125 227550 4630 2137 2

ProfessorenPersN

rName Rang Rau

m2125 Sokrates C4 2262126 Russel C4 2322127 Koperniku

sC3 310

2133 Popper C3 522134 Augustinu

sC3 309

2136 Curie C4 362137 Kant C4 7

StudentenMatrN

rName Semeste

r24002 Xenokrates 1825403 Jonas 1226120 Fichte 1026830 Aristoxenos 827550 Schopenhau

er6

28106 Carnap 329120 Theophrasto

s2

29555 Feuerbach 2

VorlesungenVorlNr Titel SWSgelesen


rie3 2126


Wissen2 2134

4630 Die 3 Kritiken 4 2137

voraussetzenVorgänge

rNachfolger

5001 50415001 50435001 50495041 52165043 50525041 50525052 5259


AssistentenPerslN

rName Fachgebiet Boss

3002 Platon Ideenlehre 21253003 Aristoteles Syllogistik 21253004 Wittgenstei

nSprachtheorie 2126

3005 Rhetikus Planetenbewegung 21273006 Newton Keplersche Gesetze 21273007 Spinoza Gott und Natur 2126

prüfenMatrN

rVorlNr PersN

rNote

28106 5001 2126 125403 5041 2125 227550 4630 2137 2

Die relationale Algebra Selektion Pojektion x Kreuzprodukt A Join (Verbund) Umbenennung Mengendifferenz Division Vereinigung Mengendurchschnitt N Semi-Join (linkes Argument wird gefiltert) Q Semi-Join (rechtes Argument wird gefiltert) C linker äußerer Join D rechter äußerer Join K (voller) äußerer Join

Die relationalen Algebra-Operatoren

Semester > 10 (Studenten)MatrNr Name Semester24002 Xenokrate

s18

25403 Jonas 12

Semester > 10 (Studenten)Selektion

Rang(Professoren)

RangC4C3

Rang(Professoren)Projektion

Die relationalen Algebra-Operatoren

Professoren hörenPersNr Name Rang Raum MatrNr VorlNr2125 Sokrates C4 226 26120 5001

... ... ... ... ... ...2125 Sokrates C4 226 29555 5001

... ... ... ... ... ...2137 Kant C4 7 29555 5001

Kartesisches Produkt Professoren x hören

• Problem: riesige Zwischenergebnisse• Beispiel: (Professoren x hören)• "bessere" Operation: Join (siehe unten)

Die relationalen Algebra-OperatorenUmbenennung

Umbenennung von Relationen Beispiel: Ermittlung indirekter Vorgänger 2. Stufe der

Vorlesung 5216

V1. Vorgänger(V2. Nachfolger=5216 V1.Nachfolger = V2.Vorgänger(V1 (voraussetzen) x V2

(voraussetzen)))

Umbennung von Attributen Voraussetzung Vorgänger (voraussetzen)

Formale Definition der AlgebraBasisausdrücke Relation der Datenbank oder konstante Relationen

Operationen Selektion: p (E1) Projektion: S (E1) Kartesisches Produkt: E1 x E2

Umbenennung: V (E1), A B (E1) Vereinigung: E1 E2 Differenz: E1- E2

Der natürliche Verbund (Join)Gegeben seien:

• R(A1,..., Am, B1,..., Bk)

• S(B1,..., Bk, C1,..., Cn)

R A S = A1,..., Am, R.B1,..., R.Bk, C1,..., Cn(R.B1=S. B1 ... R.Bk = S.Bk(RxS))

R A SR S R S S R

A1 A2 ... Am B1 B2 ... Bk C1 C2 ... Cn

Drei-Wege-Join

(Studenten A hören) A Vorlesungen

(Studenten A hören) A Vorlesungen

MatrNr Name Semester VorlNr Titel SWS gelesenVon

26120 Fichte 10 5001 Grundzüge 4 213727550 Jonas 12 5022 Glaube und

Wissen2 2134

28106 Carnap 3 4052 Wissenschftstheorie

3 2126

... ... ... ... ... ... ...

Allgemeiner Join (Theta-Join) Gegeben seien folgende Relationen(-Schemata)

R(A1, ..., An) und S(B1, ..., Bm)

R A SR S

A1 A2 ... An B1 B2 ... Bm

R A SR A S = (R x S)

Andere Join-Arten• natürlicher Join

LA B Ca1 b1 c1

a2 b2 c2

RC D Ec1 d1 e1

c3 d2 e2

A =

ResultatA B C D Ea1 b1 c1 d1 e1

LA B Ca1 b1 c1

a2 b2 c2

C =

• linker äußerer Join

RC D Ec1 d1 e1

c3 d2 e2


a2 b2 c2 - -

LA B Ca1 b1 c1

a2 b2 c2

D =

• rechter äußerer Join

RC D Ec1 d1 e1

c3 d2 e2


- - c3 d2 e2

Andere Join-Arten

LA B Ca1 b1 c1

a2 b2 c2

K =

• äußerer Join

LA B Ca1 b1 c1

a2 b2 c2

RC D Ec1 d1 e1

c3 d2 e2

N =

• Semi-Join von L mit R

RC D Ec1 d1 e1

c3 d2 e2


a2 b2 c2 - -

- - c3 d2 e2

ResultatA B Ca1 b1 c1

Andere Join-Arten (Forts.)

LA B Ca1 b1 c1

a2 b2 c2

RC D Ec1 d1 e1

c3 d2 e2

ResultatC D E c1 d1 e1

Q =

• Semi-Join von R mit L

Andere Join-Arten (Forts.)

LA B Ca1 b1 c1

a2 b2 c2

RC D Ec1 d1 e1

c3 d2 e2

ResultatA B C a2 b2 c2

=

• Anti-Semi-Join von L mit R

Die relationale DivisionBsp.: Finde MatrNr der Studenten, die alle vierstündigen Vorlesungen hören

L := VorlNr(SWS=4(Vorlesungen))

hören VorlNr(SWS=4(Vorlesungen))

L

t R S, falls für jedes ts S ein tr R existiert, so dass gilt: tr.S = ts.S tr.(R-S) = t

Die Division R S kann auch durch Differenz, Kreuzprodukt und Projektion ausgedrückt werden.

RM Vm1 v1

m1 v2

m1 v3

m2 v2

m2 v3

SVv1

v2

=

R S = (R S)(R) (R S)(( (R S)(R) x S) R)

R SMm1

Definition der Division

Mengendurchschnitt

Mengendurchschnitt nur auf zwei Argumentrelationen mit gleichem Schema anwendbar

Deshalb ist die Umbenennung des Attribute gelesenVon in PersNr in der Relation Vorlesungen notwendig

Der Mengendurchschnitt zweier Relationen R S kann durch die Mengendifferenz wie folgt ausgedrückt weden:

R S = R (R S)

Als Beispielanwendung für den Mengendurchschnitt (Operatorsymbol ) betrachten wir folgende Anfrage: Finde die PersNr aller C4-Professoren, die mindestens eine Vorlesung halten.

PersNr(PersNrgelesenVon(Vorlesungen)) PersNr(Rang=C4(Professoren))

Gruppierung und Aggregation(geht über die klassische Algebra hinaus – mehr als syntaktischer Zucker)

Aggregation & Gruppierung

Der RelationenkalkülEine Anfrage im Relationenkalkül hat die Form

{t P(t)}mit P(t) Formel.

Beispiele:C4-Professoren

{p p Professoren p.Rang = 'C4'}

Studenten mit mindestens einer Vorlesung von Curie

{s s Studenten h hören(s.MatrNr=h.MatrNr v Vorlesungen(h.VorlNr=v.VorlNr p Professoren(p.

PersNr=v.gelesenVon p.Name = 'Curie')))}

select s.*from Studenten swhere exists ( select h.* from hören h where h.MatrNr = s.MatrNr and exists ( select * from Vorlesungen v where v.VorlNr = h.VorlNr and exists ( select * from Professoren p where p.Name =‚Curie' and p.PersNr= v.gelesenVon )))

Dieselbe Anfrage in SQL … … belegt die Verwandtschaft

Allquantor Wer hat alle vierstündigen Vorlesungen gehört

{s s Studenten v Vorlesungen (v.SWS=4 h hören(h.VorlNr=v.VorlNr h.MatrNr= s.MatrNr))}

Definition des TupelkalkülsAtome

s R, mit s Tupelvariable und R Relationenname s.At.B, mit s und t Tupelvariablen, A und B Attributnamen und

Vergleichsperator (, , , ...) s. A c mit c Konstante

Formeln Alle Atome sind Formeln Ist P Formel, so auch P und (P) Sind P1 und P2 Formeln, so auch P1 P2 , P1 P2 und P1 P2 Ist P(t) Formel mit freier Variable t, so auch

t R(P(t)) und t R(P(t))

Sicherheit Einschränkung auf Anfragen mit endlichem Ergebnis. Die folgende Beispielanfrage

{n (n Professoren)}ist nicht sicher.

Das Ergebnis ist unendlich. Bedingung: Ergebnis des Ausdrucks muss Teilmenge

der Domäne der Formel sein. Die Domäne einer Formel enthält

- alle in der Formel vorkommenden Konstanten- alle Attributwerte von Relationen, die in der Formel

referenziert werden

Der DomänenkalkülEin Ausdruck des Domänenkalküls hat die Form

{[v1, v2 , ..., vn]P (v1 ,..., vn)}mit v1 ,..., vn Domänenvariablen und P Formel.

Beispiel: MatrNr und Namen der Prüflinge von Curie

{[m, n] s ([m, n, s] Studenten v, p, g ([m, v, p,g] prüfen a,r, b([p, a, r , b] Professoren a = 'Curie')))}

Prolog ~ Domänenkalkül

Sicherheit des Domänenkalküls Sicherheit ist analog zum Tupelkakkül zum Beispiel ist

{[p,n,r,o] ([p,n,r,o] Professoren) }nicht sicher.

Ein Ausdruck {[x1, x2, ..., xn] P(x1, x2, ..., xn)}

ist sicher, falls folgende drei Bedingungen gelten:

1. Falls Tupel [c1, c2, ..., cn ] mit Konstante ci im Ergebnis enthalten ist, so muss jedes ci (1 i n) in der Domäne von P enthalten sein.

2. Für jede existenz-quantifizierte Teilformel x(P1(x)) muss gelten, dass P1 nur für Elemente aus der Domäne von P1 erfüllbar sein kann - oder evtl. für gar keine. Mit anderen Worten, wenn für eine Konstante c das Prädikat P1(c) erfüllt ist, so muss c in der Domäne von P1 enthalten sein.

3. Für jede universal-quantifizierte Teilformel x(P1(x)) muss gelten, dass sie dann und nur dann erfüllt ist, wenn P1(x) für alle Werte der Domäne von P1 erfüllt ist- Mit anderen Worten, P1(d) muss für alle d, die nicht in der Domäne von P1 enthalten sind, auf jeden Fall erfüllt sein.

AusdruckskraftDie drei Sprachen1. relationale Algebra,2. relationaler Tupelkalkül, eingeschränkt auf sichere

Ausdrücke und3. relationaler Domänenkalkül, eingeschränkt auf sichere

Ausdrücke sind gleich mächtig

ProfessorenPersNr Name Rang Rau

mFakName

2125 Sokrates C4 226 Philosophie2126 Russel C4 232 Philosophie2127 Kopernik

usC3 310 Physik

2133 Popper C3 52 Philosophie2134 Augustin

usC3 309 Theologie

2136 Curie C4 36 Physik2137 Kant C4 7 Philosophie

StudentenMatrNr Name Semest

erFakName

24002 Xenokrates 18 Philosophie25403 Jonas 12 Theologie26120 Fichte 10 Philosophie26830 Aristoxenos 8 Philosophie27550 Schopenhauer 6 Philosophie28106 Carnap 3 Physik29120 Theophrastos 2 Physik29555 Feuerbach 2 Theologie

VorlesungenVorlNr Titel SWSgelesen


rie3 2126


Wissen2 2134

4630 Die 3 Kritiken 4 2137


ProfessorenPersNr Name Rang Rau

mFakName

2125 Sokrates C4 226 Philosophie2126 Russel C4 232 Philosophie2127 Kopernik

usC3 310 Physik

2133 Popper C3 52 Philosophie2134 Augustin

usC3 309 Theologie

2136 Curie C4 36 Physik2137 Kant C4 7 Philosophie

StudentenMatrNr Name Semester Geschlec

htFakName

24002 Xenokrates 18 M Philosophie25403 Jonas 12 W Theologie26120 Fichte 10 W Philosophie26830 Aristoxenos 8 M Philosophie27550 Schopenhauer 6 M Philosophie28106 Carnap 3 W Physik29120 Theophrastos 2 M Physik29555 Feuerbach 2 W Theologie

Documents

Historische Entwicklung relationaler DBMS