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