Algebra relacji

Definicja 1 (Relacja matematyczna). Relacją R między elementami zbioru D

1

× D

2

× · · · × D

n

, gdzie

przypomnijmy

D

1

× D

2

× · · · × D

n

= {(d

1

, d

2

, . . . , d

n

) : d

i

∈ D

i

, i = 1, 2, . . . , n} ,

nazywamy każdy podzbiór iloczynu karteziańskiego D

1

× D

2

× · · · × D

n

.

Definicja 2 (Relacja w sensie Codd’a). Niech U = {A

1

, A

2

, A

3

, . . . } będzie zbiorem złożonym z atrybutów

A

1

, A

2

, A

2

, . . . . Dla każdego atrybutu A ∈ U zbiór jego wartości (prostych) nazywamy dziedziną i oznaczamy

dom (A). Zakładamy, że dla każdego A ∈ U zachodzi inkluzja NULL ∈ dom (A).

Dla zbioru atrybutów U = {B

1

, B

2

, . . . , B

n

}, gdzie B

1

, B

2

, . . . , B

n

∈ U, definiujemy:

• krotkę t typu U (z ang. tuple) jako zbiór par uporządkowanych

t = {(B

1

, b

1

) , (B

2

, b

2

) , . . . , (B

n

, b

n

)}

ozn.

= [B

1

: b

1

, B

2

: b

2

, . . . , B

n

: b

n

]

gdzie b

i

∈ D

i

= dom (B

i

) dla i = 1, 2, . . . , n.

• relację typu U jako dowolny, skończony podzbiór zbioru wszystkich krotek typu U .

Uwaga 1. Każdy zbiór par t = [A

1

: a

1

, A

2

: a

2

, . . . , A

n

: a

n

], przy oznaczeniach z powyższej definicji, jest

pewną funkcją ze zbioru atrybutów U = {A

1

, A

2

, . . . , A

n

} w zbiór wartości V = D

1

∪ D

2

∪ · · · ∪ D

n

, gdzie

D

i

= dom (A

i

) dla i = 1, 2, . . . , n, a zatem t : U → V jest funkcją taką, że dla każdego A ∈ U, t (A) ∈

dom (A).

Oznaczenia:

• KROTKA(U ) — zbiór wszystkich krotek typu U ,

• KROTKA(∅) = {} — zbiór zawiera jedną krotkę, krotkę pustą  typu ∅ o długości zero,

• null(U ) – krotka null-owa typu U , dla każdego atrybutu A ∈ U , null (A) = NULL,

• REL(U ) – zbiór wszystkich relacji typu U (Ile jest takich relacji jeśli |KROTKA (U )| = k?),

• REL(∅) = {∅, {}}, gdzie ∅ to pusta relacja typu ∅, nie zawierająca żadnej krotki,

• U, X, Y, V, W — zbiory atrybutów (typy relacji),

• R (U ) , S (X) , . . . — relacje odpowiednio typu U, X, . . . ; gdy typ wynika z kontekstu piszemy

R, S, . . . ,

• t (U ) , r (X) , . . . — krotki typu U, X, . . . ; gdy typ wynika z kontekstu piszemy t, r, . . . ,

• zamiast pisać r = [A

1

: a1, A

2

: a

2

, . . . , A

n

: a

n

] piszemy w skrócie r = (a

1

, a

2

, . . . , a

n

) — domyśl-

ne przyjmujemy uporządkowanie wartości w krotce takie jak uporządkowanie atrybutów w typie

relacji,

• zamiast pisać R ({A, B}) piszemy w skrócie R (A, B),

• zamiast pisać R (X ∪ Y ) piszemy w skrócie R (X, Y ).

Operacje na relacjach (algebra relacji)

1. Operacje mnogościowe na relacjach

Operandy: R (U ) , S (U ) — relacje typu U

Wynik: T (U ) — relacja typu U

Suma mnogościowa (ang. union)

T = R ∪ S {t : t ∈ R ∨ t ∈ S}

Różnica mnogościowa (ang. difference)

T = R \ S = {t : t ∈ R ∧ t /

∈ S}

Przekrój mnogościowy (ang. intersection)

T = R ∩ S = {t : t ∈ R ∨ t ∈ S)

Dopełnienie mnogościowe (ang. complement) T = R

c

= KROTKA (X) \ R (X)

Uwaga 2. W przypadku dopełnienia istotnym jest, aby zbiór KROTKA (X) był skończony (Dlaczego?),

co powoduje, że w praktyce dopełnienie nie jest stosowane.

Sumy zewnętrzne (otwarte, ang. outer union)

Niech Z = X ∪ Y i R (X) będzie relacją typu X, a S (Y ) typu Y . Tworzymy relację R

0

(Z) typu Z poprzez

uzupełnienie krotek relacji R (X) o argumenty z Z \X „wypełniając” ich wartości NULL-ami, dokładniej:

R

0

(Z) = {t

0

∈ KROTKA (Z) : (t

0

(A) = t (A) dla A ∈ X) ∧ (t

0

(A) = null (A) dla A ∈ Z \ X)} .

W analogiczny sposób tworzymy relację S

0

(Z) typu Z, to znaczy

S

0

(Z) = {r

0

∈ KROTKA (Z) : (r

0

(B) = r (B) dla B ∈ Y ) ∧ (r

0

(B) = null (B) dla B ∈ Z \ Y )} .

Definiujemy sumę zewnętrzną R (X) OUTER UNION S (Y ) relacji R (X) i S (Y ) jako

R (X) OUTER UNION S (Y ) = R

0

(Z) ∪ S

0

(Z) .

2. Operacje na krotkach

2.1. Ograniczenie krotki

Niech r (U ) będzie krotką typu U i niech X ⊆ U . Krotkę r [X] typu X nazywamy ograniczeniem

krotki r (U ) do zbioru atrybutów X, wtedy i tylko wtedy, gdy

t (A) = r (A)

dla każdego A ∈ X.

2.2. Złączenie krotek

Krotkę r

1 s typu X ∪ Y nazywamy złączeniem naturalnym (ang. natural join) krotek r (X) i

s (Y ), wtedy i tylko wtedy, gdy t [X] = r i t [Y ] = s.

3. Operacje relacyjne

3.1. Projekcja, rzut (ang. projection) relacji

Niech R (U ) będzie relacją typu U i niech X ⊆ U . Relację R [X] (lub π

X

(R)) typu X nazywamy

projekcją relacji R na X, wtedy i tylko wtedy, gdy

R [X] = π

X

(R) = {t ∈ KROTKA (X) : ∃

r∈R

t = r [X]} ,

w szczególności

R [∅] = π

∅

(R) =















∅

gdy R = ∅,

{}

w p.p.

3.2. Selekcja (ang. selection)

Niech A, A

0

∈ U, ν ∈

S

A∈U

dom (A) , θ ∈ {=, 6=, <, ¬, >, ­, like, . . . }.

• Atomowymi warunkami selekcji są: A θ ν oraz A θ A

0

.

• Każdy atomowy warunek selekcji jest warunkiem selekcji.

• Jeśli E i E

0

są warunkami selekcji, to są nimi również: (E) , ¬E, E ∨ E

0

, E ∧ E

0

.

Relację σ

E

(R) typu U nazywamy selekcją relacji R (U ) względem warunku selekcji E, wtedy

i tylko wtedy, gdy

σ

E

(R) = {t ∈ R : E (t) = TRUE} .

Sposoby obliczania warunków selekcji:

a) (A θ ν) (t) = t (A) θ ν,

b) (A θ A

0

) (t) = t (A) θ t (A

0

),

c) (¬E) (t) = ¬ (E (t)),

d ) (E ∨ E

0

) (t) = E (t) ∨ E

0

(t),

e) (E ∧ E

0

) (t) = E (t) ∧ E

0

(t).

Ponieważ języki relacyjnych baz danych, np. SQL, opierają się na logice trójwartościowej o warto-

ściach: TRUE, FALSE i UNKNOWN („nieznana”), to dodatkowo mamy:

f ) t (A) θ NULL = UNKNOWN,

g) NULL θ ν = UNKNOWN dla każdego ν, również równego NULL.

3.3. Przemianowanie (ang. renaming)

Niech R (U ) będzie relacją typu U , a A i B niech będą atrybutami, przy czym A ∈ U i B /

∈ U .

Niech W = U \ {A} ∪ {B}. Relację δ

A→B

(R) typu W nazywamy przemianowaniem w relacji

R atrybutu A na atrybut B, wtedy i tylko wtedy, gdy

δ

A→B

(R) =

n

t ∈ KROTKA (W ) : ∃

r∈R

t = π

U \{A}

(r)

1 [B : r (A)]

o

.

3.4. Iloczyn kartezjański (ang. cross join, Cartesian product)

Niech R (X) i S (Y ) będą relacjami typu odpowiednio X i Y , gdzie X = {A

1

, A

2

, . . . , A

n

}, Y =

{B

1

, B

2

, . . . , B

m

}. Określmy prefiksowanie atrybutów relacji R i S w następujący sposób R.X =

{R.A

1

, R.A

2

, . . . , R.A

n

} , S.Y = {S.B

1

, S.B

2

, . . . , S.B

m

}. Iloczynem kartezjańskim relacji R

i S nazywamy relację R × S typu R.X ∪ S.Y , wtedy i tylko wtedy, gdy

R × S = {t ∈ KROTKA (R.X ∪ S.Y ) : π

R.X

(t) = R ∧ π

S.Y

(t) = S} .

3.5. Złączenie (ang. join)

Relację R

1 S typu X ∪ Y nazywamy złączeniem naturalnym (ang. natural join) relacji R (X)

i S (Y ), wtedy i tylko wtedy, gdy

R

1 S = {t ∈ KROTKA (X ∪ Y ) : π

X

(t) = R ∧ π

Y

(t) = S} ,

albo równoważnie

R

1 S = (t ∈ KROTKA (X ∪ Y ) : ∃

r∈R

∃

s∈S

t = r

1 s) .

Jeżeli R i S są relacjami odpowiednio typu X i Y oraz X = Y , to R

1 S = R ∩ S, z kolei jeżeli

X ∩ Y = ∅, to R

1 S = R × S.

Właściwości

1 dla relacji R, S, T typu U:

a) R

1 {} = R,

b) R

1 ∅ = ∅,

c) R

1 π

X

{R} = R, gdzie X ⊆ U ,

d ) R ⊆ π

X

(R)

1 π

Y

(R), gdzie X ∪ Y = U ,

e) R

1 S = S 1 R

f ) R

1 (S 1 T ) = (R 1 S) 1 T .

3.6. θ-złączenie, theta-złączenie (θ-join)

Niech R (X) , S (Y ) będą relacjami odpowiednio typu X i Y , gdzie X = {A

1

, A

2

, . . . , A

n

} , Y =

{B

1

, B

2

, . . . B

m

} i niech θ ∈ {=, 6=, <, ¬, >, ­, like, . . . }.

Relację R

1

F

S typu X × Y nazywamy θ-złączeniem relacji R i S względem warunku

złączenia F (analogicznie jak warunek selekcji), wtedy i tylko wtedy, gdy

R

1

F

S = {t ∈ R × S : F (t) = TRUE} .

θ-złączenie jest więc selekcją z iloczynu kartezjańskiego, a zatem

R

1

F

S = σ

F

(R × S) .

3.7. Złączenia zewnętrzne (ang. outer join)

(a) Złączenie zewnętrzne lewostronne (ang. left outer join)

Relację R+

1

F

S typu X ∪ Y nazywamy złączeniem zewnętrznym lewostronnym relacji

R (X) i S (Y ), wtedy i tylko wtedy, gdy

R+

1

F

S = {t ∈ R × S : F (t) = TRUE} ∪

∪ {π

X

(t) × null (Y \ X) : t ∈ R × S ∧ F (t) 6= TRUE} ,

czyli do wyniku należą wszystkie krotki relacji R (lewy operand) połączone albo z dopasowaną

krotką z relacji S, albo uzupełniona wartościami NULL, gdy brak dopasowanej krotki (krotka

s jest dopasowana do r, jeśli F (r

1 s) = TRUE).

(b) Złączenie zewnętrzne prawostronne (ang. right outer join)

Relację R

1 +

F

S typu X ∪ Y nazywamy złączeniem zewnętrznym prawostronnym

relacji R (X) i S (Y ), wtedy i tylko wtedy, gdy

R

1 +

F

S = {t ∈ R × S : F (t) = TRUE} ∪

∪ {π

Y

(t) × null (X \ Y ) : t ∈ R × S ∧ F (t) 6= TRUE} ,

czyli do wyniku należą wszystkie krotki relacji S (prawy operand) połączone albo z dopasowaną

krotką z relacji R, albo uzupełniona wartościami NULL, gdy brak dopasowanej krotki.

(c) Złączenie zewnętrzne pełne (ang. full outer join)

Relację R+

1 +

F

S typu X ∪Y nazywamy złączeniem zewnętrznym pełnym relacji R (X)

i S (Y ), wtedy i tylko wtedy, gdy

R+

1 +

F

S = (R+

1

F

S) ∪ (R

1 +

F

S) .

3.8. Podzielenie (ang. division)

Niech X ⊆ U . Relację R ÷ S typu U \ X nazywamy podzieleniem relacji R (U ) przez S (X),

wtedy i tylko wtedy, gdy

R ÷ S =

n

t ∈ π

U \X

(R) : ∀

s∈S

t

1 s ∈ R

o

.

Własności podzielenia:

a) R ÷ S =

n

t ∈ π

U \X

(R) : S = R [t, X]

o

, gdzie R [t, X] = {s ∈ π

X

(R) : t

1 s ∈ R}.

b) Jeśli przyjmiemy, że n = count (S) , m = count (R [t, X]), gdzie t ∈ R [U \ X] i m = n, to

t ∈ R ÷ S.

Zadania

Zadanie 1. Niech

dom (IM IE) = {

0

Adam

0

,

0

Ewa

0

,

0

Karol

0

,

0

Zof ia

0

},

dom (N AZW ISKO) = {

0

Kowalska

0

,

0

Kowalski

0

,

0

N owak

0

},

dom (P RZEDM IOT ) = {

0

AN A

0

,

0

BAD

0

,

0

M AD

0

,

0

SIK

0

},

dom (OCEN A) = {2, 3, 4, 5},

dom (P U N KT Y ) = {0, 1, 2, . . . , 220}

dom (IN DEKS) = {111111, 222222, 333333, 444444, 555555, 666666}

R

1

IN DEKS

IM IE

N AZW ISKO

222222

Ewa

Kowalska

333333

Zof ia

Kowalska

555555

Ewa

N owak

R

2

IN DEKS

IM IE

N AZW ISKO

111111

Adam

Kowalski

444444

Karol

N owak

R

3

IM IE

N AZW ISKO P U N KT Y

Karol

Kowalski

170

Ewa

N owak

219

Zof ia

N owak

165

R

4

IN DEKS

P RZEDM IOT

OCEN A

111111

AN A

4

222222

AN A

5

444444

AN A

2

555555

AN A

4

111111

BAD

3

444444

BAD

4

111111

M AD

3

222222

M AD

4

444444

M AD

5

666666

M AD

2

222222

SIK

2

444444

SIK

4

Dla podanych niżej operacji algebry relacji obliczyć wynik wykonania operacji o ile jest to możliwe

(podać postać relacji wynikowej i zinterpretować wynik):

a) S

1

= R

1

∪ R

2

, R

1

∪ R

3

,

b) S

2

= π

{P RZEDM IOT }

(R

4

),

c) ¬S

1

, ¬S

2

,

d) R

2

∩ R

3

,

e)



π

{IM IE}

(S

1

) × π

{N AZW ISKO}

(S

1

)



\ π

{IM IE, N AZW ISKO}

(R

3

),

f ) σ

P U N KT Y >170

(R

3

),

g) σ

(P RZEDM IOT =

0

AN A

0

∨ P RZEDM IOT =

0

BAD

0

) ∧ OCEN A>2

(R

4

) , (podać kolejne kroki wartościowania),

h) R

4

÷ S

2

,

i) S

1

1

S

1

.IN DEKS=R

4

.IN DEKS

R

4

,

j) S

1

+

1

S

1

.IN DEKS=R

4

.IN DEKS

R

4

,

k) S

1

1 +

S

1

.IN DEKS=R

4

.IN DEKS

R

4

,

l) S

1

+

1 +

S

1

.IN DEKS=R

4

.IN DEKS

R

4

.

Zadanie 2. Udowodnij następujące własności operatora selekcji:

a) σ

E

(R ∪ S) = σ

E

(R) ∪ σ

E

(S),

b) σ

E

1

∧E

2

(R) = σ

E

1

(σ

E

2

(R)) = σ

E

2

(σ

E

1

(R)) = σ

E

1

(R) ∩ σ

E

2

(R),

c) σ

E

1

∨E

2

(R) = σ

E

1

(R) ∪ σ

E

2

(R).