8.1InformationssystemeJ. Biskup Relationale Operationen 04.11.96
Relationale Operationen
natürlicher Verbund
Selektion
Projektion
Vergleich
Vereinigung
Komplement
Differenz
Division
8.2InformationssystemeJ. Biskup Relationale Operationen 04.11.96
natürlicher Verbund
1. r s := {µ | µ : dom r ∪ dom s → C,
− und µ dom r ∈ r und µ dom s ∈ s},
2. i=1,...,k ri := {µ | µ : ∪i=1,...,k dom ri → C,
und µ dom ri ∈ ri für i = 1,...,k}
dom r ∪ dom s = ABC
dom r ∩ dom s = B
r A B
a b
e b
f g
s B C
b c
r s A B C
a b c
e b c
8.3InformationssystemeJ. Biskup Relationale Operationen 04.11.96
Grundlegende Eigenschaften des natürlichenVerbundes:r s = {µ | es gibt α ∈ r, β ∈ s :
α(A) = β(A) für alle A ∈ dom r ∩ dom s, µ = α ∪ β}
liefert einen einfachen Algorithmus:
PROCEDURE NestedLoopJoin(r, s : Relation) :
Relation;VAR ergebnis : Relation;
α, β : Tupel;
BEGINergebnis := Ø;FOR ALL α ∈ r DO
FOR ALL β ∈ s DOIF Passend( α, β)
(* liefert TRUE gdw α(A) = β(A) für alle A ∈ dom r ∩ dom s *)
THEN ergebnis := ergebnis ∪ { α ∪ β} END
ENDEND;RETURN ergebnis
END NestedLoopJoin;
Laufzeit: O ( || r || * || s || )
8.4InformationssystemeJ. Biskup Relationale Operationen 04.11.96
Falls dom r ∩ dom s = ∅, so r s = r × s(kartesischen Produkt ).
Falls dom r = dom s, so r s = r ∩ s(Durchschnitt ).
Der natürliche Verbund ist also doppelgesichtig:
er kann aggregierend wirken und damit (quadratisch)
vergrößerte Ergebnisse liefern;
er kann aussondernd wirken und damit verkleinerte
Ergebnisse liefern;
beide Wirkungen können sich auch überlagern.
8.5InformationssystemeJ. Biskup Relationale Operationen 04.11.96
σA=c (r) := r
A
c für A ∈ dom r
heißt A=c-Selektion (A=c-selection).
algebraische Eigenschaften:
r s = s r kommutativ
(r s) t = r (s t) assoziativ
r ⊂ s ⇒ r t ⊂ s t monoton
r ⊂ s ⇒ r s = r absorbtiv
r r = r idempotent
r ∅ = ∅ Nullelement ∅
σA=c (r s) ={ σA=c (r)
σA=c (r)
s
(s)σA=c
falls A ∈ dom r
falls A ∈ dom s∩dom r
8.6InformationssystemeJ. Biskup Relationale Operationen 04.11.96
Projektion1. Sei X ∩ dom r ≠ ∅. Dann heißt πX(r) := {νX | ν ∈ r} Projektion (projection) der Relation r auf X.2. Sei q : X → Y, Y ⊂ dom r, X ≠ ∅. Dann heißt πq(r) := {µ | µ : X → C, es gibt ν ∈ r mit µ = ν ° q}
q-Projektion der Relation r vermöge q.
q(C) = A
q(D) = A
q(E) = B
R A B
a b
e b
F g
πB(r) = B
b
g
πq(r) = C D E
a a b
e e b
f f g
8.7InformationssystemeJ. Biskup Relationale Operationen 04.11.96
Sei q : X → X,
q(A) := A für A ∈ X ⊂ dom r.
Dann gilt:
πq(r) = {µ | µ : X → C, es gibt ν ∈ r mit µ = ν ° q}
= {µ | µ : X → C, es gibt ν ∈ r mit µ = ν X}
= {ν X | ν ∈ r}
= πX(r)
8.8InformationssystemeJ. Biskup Relationale Operationen 04.11.96
Grundlegende Eigenschaften der Projektion:
einfacher Algorithmus:
PROCEDURE SequentialProject (q : Attributfunktion; r : Relation) :
Relation;VAR ergebnis : Relation;
ν : Tupel;
BEGINergebnis := ∅;FOR ALL ν ∈ r DO
ergebnis := ergebnis ∪ { ν ° q}
(* Falls das Tupel ν ° q noch nicht in der Relation
ergebnis enthalten ist, so füge es ein; dieseElementtest-Und-Einfüge-Operation kann durch
geeignete Datenstrukturen für die Relation ergebnis, z.B. sortierte Liste oder B*-Baum, unterstützt werden. *)
END;RETURN ergebnis
END SequentialProject;
Laufzeit: O ( || r || ⋅log || r || )
8.9InformationssystemeJ. Biskup Relationale Operationen 04.11.96
Sei ∪i=1,...,k Xi = dom r.
Dann gilt: r ⊂ i=1,...,k πXi(r).
Eine verlustbehaftete Zerlegung:
....
πA,B(r) = A B
ab
aa
π B,C (r) = B C
aa
ab
π A,B (r) π B,C (r) = A B C
aabb
aaaa
abab
r = A B C
ab
aa
ab
8.10InformationssystemeJ. Biskup Relationale Operationen 04.11.96
πdom rj ( i=1,...,k ri) ⊂ rj.
A B
ab
aa
r = B C
ab
aa
s =
A B C
aa
aa
ab
A B
aa
πA,B (r s) =r s =
8.11InformationssystemeJ. Biskup Relationale Operationen 04.11.96
Teilverbund (semijoin)
r s := πdom r (r s)
= r πdom r ∩ dom s (s)
A B
ab
aa
r = B C
ab
aa
s =
πB
(s) = B
a
r (s) = A B
a a
πB
8.12InformationssystemeJ. Biskup Relationale Operationen 04.11.96
Falls dom r ∩ dom s ⊂ X,
so gilt πX (r s) = πX (r) πX (s).
Falls A ∈ X ∩ dom r,
so gilt πX ( σA=c (r) ) = σA=c ( πX (r) ).
Sei X ∩ Y ∩ dom r ≠ ∅.
Dann gilt:
πX(πY(r)) = πX∩Y(r);
speziell für X ⊂ Y folgt:
πX(πY(r)) = πX(r).
8.13InformationssystemeJ. Biskup Relationale Operationen 04.11.96
Vereinigung
+ (d,r,s) := {µ | µ : dom r ∪ dom s → d,
und (µ dom r ∈ r oder µ dom s ∈ s)}
A B
f g f
e e f
r :=d := {e, f, g}
A C
fe
s :=
A B C
e e e e e e f f f e
f f f g g g f f f e
e f g e f g e f g f
+ (d, r, s) =
8.14InformationssystemeJ. Biskup Relationale Operationen 04.11.96
Grundlegende Eigenschaften derVereinigung:
1. Falls dom r = dom s,
d.h. r und s sind vereinigungsverträglich,
so gilt + (d,r,s) = r ∪ s.
2. + (d,r,s) = + (d,s,r).
3. (r ∪ s) t = (r t) ∪ (s t),
σA=c (r ∪ s) = σA=c (r) ∪ σA=c (s).
4. πX (+ (d, r, s) ) = + (d, πX (r), πX (s)),
speziell für dom r = dom s:
πX (r ∪ s) = πX (r) ∪ πX (s).
8.15InformationssystemeJ. Biskup Relationale Operationen 04.11.96
A=B-Vergleich, A ≠B-Vergleich
σA=B(r) := {µ | µ ∈ r, und µ(A) = µ(B)}
σA≠B(r) := {µ | µ ∈ r, und µ(A) ≠ µ(B)}
Grundlegende Eigenschaften des Vergleiches:
1. σA=B(r) ∪ σA≠B(r) = r.
2. σA=B(r) ∩ σA≠B(r) = ∅.
3. Sei X = {A1,...,Ak}, Y = {B 1,...,Bk}, wobei die Reihenfolge
der Aufzählung bekannt sei,
und X ∩ Y = ∅, X ∪ Y ⊂ dom r.
Dann sei
σX=Y(r) := σA1=B1 (σA2=B2 (... σAk=Bk(r)... ).
8.16InformationssystemeJ. Biskup Relationale Operationen 04.11.96
Komplement
γ (d,r) := {µ | µ : dom r → d} \ r
A B
fgf
eef
rd := {e, f, g} A B
eegefg
effggg
γ(d, r)
8.17InformationssystemeJ. Biskup Relationale Operationen 04.11.96
Differenz
Sei dom r ∩ dom s ≠ ∅.– (d,r,s) := {µ | µ ∈ r,
und µ dom r ∩ dom s ∉ πdom r ∩ dom s(s)}
= r γ (d, πdom r ∩ dom s(s))
A B
fgf
eef
r :=d := { e, f, g} A C
fe
s :=
Differenz der Relationen r und sa) direkt ermittelt:
π (s) =A A
e
– (d, r, s) = A B
f f
b) mit Hilfe der Umschreibung ermittelt:
r γ (d, πdom r ∩ dom s (s)) =
A B
fgf
eef
A
e
γ ( d, ) = A B
fgf
eef
A
fg
= A B
ff
8.18InformationssystemeJ. Biskup Relationale Operationen 04.11.96
Grundlegende Eigenschaften der Differenz:
1. Falls dom r = dom s, so –(d,r,s) = r \ s.
2. Falls dom r ∩ dom s ⊂ X, so
πX (– (d, r, s)) = – (d, πX (r), πX (s));
σA=c
(– (d, r, s)) ={– (d,σA=c(r), s) falls A ∈
– (d,σA=c(r), σA=c
(s)) falls A ∈ ∩
dom r
dom r dom s
3.
8.19InformationssystemeJ. Biskup Relationale Operationen 04.11.96
Division
Sei ∅ ≠ dom r ∩ dom s ≠ dom r, s ≠ ∅.
r / s := {µ | µ : dom r \ dom s → C, und für alle ν :
wenn ν ∈ πdom r ∩ dom s (s), dann µ ∪ ν ∈ r} = {µ | µ ∈ πdom r \ dom s (r) und {µ} πdom r ∩ dom s (s) ⊂ r}
Argumente:
man erhält folgende Projektionen:
π (s) =A A
a1a2
π (r) =B B
bd
Für µ1 := ( )B gilt πA(s) = A B
bb
a1a2
⊂ r.µ1
Für µ2 := ( )B gilt πA (s) = A B
dd
a1a2
r.µ2 ⊄
Also folgt r / s = B
b
.
d
b{ }
{ }
A B
b b d
a1 a2 a1
r := A C
c c
a1 a2
s :=
8.20InformationssystemeJ. Biskup Relationale Operationen 04.11.96
Grundlegende Eigenschaften der Division:
1. Falls dom r ∩ dom s = ∅ und s ≠ ∅, so gilt:
(r s) / s = r.
2. r /s = πdom r \ dom s(r) \
πdom r \ dom s((πdom r \ dom s(r) πdom r ∩ dom s(s)) \ r).