Algebra relacji
Definicja 1 (Relacja matematyczna). RelacjÄ… R miÄ™dzy elementami zbioru D1 × D2 × · · · × Dn, gdzie
przypomnijmy
D1 × D2 × · · · × Dn = {(d1, d2, . . . , dn) : di " Di, i = 1, 2, . . . , n} ,
nazywamy każdy podzbiór iloczynu karteziaÅ„skiego D1 × D2 × · · · × Dn.
Definicja 2 (Relacja w sensie Codd a). Niech U = {A1, A2, A3, . . . } będzie zbiorem złożonym z atrybutów
A1, A2, A2, . . . . 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 = {B1, B2, . . . , Bn}, gdzie B1, B2, . . . , Bn " U, definiujemy:
" krotkę t typu U (z ang. tuple) jako zbiór par uporządkowanych
ozn.
t = {(B1, b1) , (B2, b2) , . . . , (Bn, bn)} = [B1 : b1, B2 : b2, . . . , Bn : bn]
gdzie bi " Di = dom (Bi) 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 = [A1 : a1, A2 : a2, . . . , An : an], przy oznaczeniach z powyższej definicji, jest
pewnÄ… funkcjÄ… ze zbioru atrybutów U = {A1, A2, . . . , An} w zbiór wartoÅ›ci V = D1 *" D2 *" · · · *" Dn, gdzie
Di = dom (Ai) 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 = [A1 : a1, A2 : a2, . . . , An : an] piszemy w skrócie r = (a1, a2, . . . , an)  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 = Rc = 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 (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 (Z) = {t " KROTKA (Z) : (t (A) = t (A) dla A " X) '" (t (A) = null (A) dla A " Z \ X)} .
W analogiczny sposób tworzymy relację S (Z) typu Z, to znaczy
S (Z) = {r " KROTKA (Z) : (r (B) = r (B) dla B " Y ) '" (r (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 (Z) *" S (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 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
Å„Å‚
ôÅ‚
ôÅ‚
òÅ‚
" gdy R = ",
R ["] = Ä„" (R) =
ôÅ‚
ôÅ‚
ół
{ } w p.p.
3.2. Selekcja (ang. selection)

Niech A, A " U, ½ " dom (A) , ¸ " {=, =, <, , >, , like, . . . }.

A"U
" Atomowymi warunkami selekcji sÄ…: A ¸ ½ oraz A ¸ A .
" Każdy atomowy warunek selekcji jest warunkiem selekcji.
" Jeśli E i E są warunkami selekcji, to są nimi również: (E) , ŹE, E (" E , E '" E .
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 ) (t) = t (A) ¸ t (A ),
c) (ŹE) (t) = Ź (E (t)),
d) (E (" E ) (t) = E (t) (" E (t),
e) (E '" E ) (t) = E (t) '" E (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Ä™ ´AB (R) typu W nazywamy przemianowaniem w relacji
R atrybutu A na atrybut B, wtedy i tylko wtedy, gdy

´AB (R) = t " KROTKA (W ) : "r"R t = Ä„U\{A} (r) [B : r (A)] .
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 = {A1, A2, . . . , An}, Y =
{B1, B2, . . . , Bm}. Określmy prefiksowanie atrybutów relacji R i S w następujący sposób R.X =
{R.A1, R.A2, . . . , R.An} , S.Y = {S.B1, S.B2, . . . , S.Bm}. 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 S typu X *" Y nazywamy złączeniem naturalnym (ang. natural join) relacji R (X)
i S (Y ), wtedy i tylko wtedy, gdy
R S = {t " KROTKA (X *" Y ) : Ä„X (t) = R '" Ä„Y (t) = S} ,
albo równoważnie
R S = (t " KROTKA (X *" Y ) : "r"R"s"S t = r s) .
Jeżeli R i S są relacjami odpowiednio typu X i Y oraz X = Y , to R S = R )" S, z kolei jeżeli
X )" Y = ", to R S = R × S.
Właściwości dla relacji R, S, T typu U:
a) R { } = R, d) R Ä…" Ä„X (R) Ä„Y (R), gdzie X *" Y = U,
b) R " = ", e) R S = S R
c) R Ä„X {R} = R, gdzie X Ä…" U, f ) R (S T ) = (R S) T .
3.6. ¸-zÅ‚Ä…czenie, theta-zÅ‚Ä…czenie (¸-join)
Niech R (X) , S (Y ) będą relacjami odpowiednio typu X i Y , gdzie X = {A1, A2, . . . , An} , Y =
{B1, B2, . . . Bm} i niech ¸ " {=, =, <, , >, , like, . . . }.

RelacjÄ™ R S typu X × Y nazywamy ¸-zÅ‚Ä…czeniem relacji R i S wzglÄ™dem warunku
F
złączenia F (analogicznie jak warunek selekcji), wtedy i tylko wtedy, gdy
R S = {t " R × S : F (t) = TRUE} .
F
¸-zÅ‚Ä…czenie jest wiÄ™c selekcjÄ… z iloczynu kartezjaÅ„skiego, a zatem
R S = ÃF (R × S) .
F
3.7. Złączenia zewnętrzne (ang. outer join)
(a) Złączenie zewnętrzne lewostronne (ang. left outer join)
Relację R+ S typu X *" Y nazywamy złączeniem zewnętrznym lewostronnym relacji
F
R (X) i S (Y ), wtedy i tylko wtedy, gdy
R+ S = {t " R × S : F (t) = TRUE} *"
F
*" {Ä„X (t) × null (Y \ X) : t " R × S '" F (t) = 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 s) = TRUE).
(b) Złączenie zewnętrzne prawostronne (ang. right outer join)
Relację R +F S typu X *" Y nazywamy złączeniem zewnętrznym prawostronnym
relacji R (X) i S (Y ), wtedy i tylko wtedy, gdy
R +F S = {t " R × S : F (t) = TRUE} *"
*" {Ä„Y (t) × null (X \ Y ) : t " R × S '" F (t) = 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+ +F S typu X *"Y nazywamy złączeniem zewnętrznym pełnym relacji R (X)
i S (Y ), wtedy i tylko wtedy, gdy
R+ +F S = (R+ S) *" (R +F S) .
F
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 = t " Ä„U\X (R) : "s"S t s " R .
Własności podzielenia:

a) R ÷ S = t " Ä„U\X (R) : S = R [t, X] , gdzie R [t, X] = {s " Ä„X (R) : t 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 (IMIE) = { Adam , Ewa , Karol , Zofia },
dom (NAZW ISKO) = { Kowalska , Kowalski , Nowak },
dom (P RZEDMIOT ) = { ANA , BAD , MAD , SIK },
dom (OCENA) = {2, 3, 4, 5},
dom (P UNKT Y ) = {0, 1, 2, . . . , 220}
dom (INDEKS) = {111111, 222222, 333333, 444444, 555555, 666666}
R1 INDEKS IMIE NAZW ISKO R4 INDEKS P RZEDMIOT OCENA
222222 Ewa Kowalska 111111 ANA 4
333333 Zofia Kowalska 222222 ANA 5
555555 Ewa Nowak 444444 ANA 2
555555 ANA 4
R2 INDEKS IMIE NAZW ISKO
111111 BAD 3
111111 Adam Kowalski
444444 BAD 4
444444 Karol Nowak
111111 MAD 3
222222 MAD 4
R3 IMIE NAZW ISKO P UNKT Y
444444 MAD 5
Karol Kowalski 170
666666 MAD 2
Ewa Nowak 219
222222 SIK 2
Zofia Nowak 165
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) S1 = R1 *" R2, R1 *" R3,
b) S2 = Ä„{P RZEDMIOT } (R4),
c) ŹS1, ŹS2,
d) R2 )" R3,

e) Ä„{IMIE} (S1) × Ä„{NAZW ISKO} (S1) \ Ä„{IMIE, NAZW ISKO} (R3),
f) ÃP UNKT Y >170 (R3),
g) Ã(P RZEDMIOT = ANA (" P RZEDMIOT = BAD ) '" OCENA>2 (R4) , (podać kolejne kroki wartoÅ›ciowania),
h) R4 ÷ S2,
i) S1 S1.INDEKS=R4.INDEKS R4,
j) S1+ S1.INDEKS=R4.INDEKS R4,
k) S1 +S .INDEKS=R4.INDEKSR4,
1
l) S1+ +S .INDEKS=R4.INDEKSR4.
1
Zadanie 2. Udowodnij następujące własności operatora selekcji:
a) ÃE (R *" S) = ÃE (R) *" ÃE (S),
b) ÃE '"E2 (R) = ÃE (ÃE (R)) = ÃE (ÃE (R)) = ÃE (R) )" ÃE (R),
1 1 2 2 1 1 2
c) ÃE ("E2 (R) = ÃE (R) *" ÃE (R).
1 1 2