Relationale Algebra

8.1InformationssystemeJ. Biskup Relationale Operationen 04.11.96

Relationale Operationen

natürlicher Verbund

Selektion

Projektion

Vergleich

Vereinigung

Komplement

Differenz

Division


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


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 || )


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.


σ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


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


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)


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 || )


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


π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 =


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


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).


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) =


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).


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)... ).


Komplement

γ (d,r) := {µ | µ : dom r → d} \ r

A B

fgf

eef

rd := {e, f, g} A B

eegefg

effggg

γ(d, r)


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


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.


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 :=


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).

Documents

Relationale Algebra