algebra relacji

[ Pobierz całość w formacie PDF ]
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
2
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
2
U
zbiór jego warto±ci (prostych) nazywamy dziedzin¡ i oznaczamy
dom
(
A
)
. Zakładamy, »e dla ka»dego A
2
U
zachodzi inkluzja
NULL
2
dom
(
A
)
.
Dla zbioru atrybutów U
=
{
B
1
,B
2
,...,B
n
}
, gdzie B
1
,B
2
,...,B
n
2
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.
gdzie b
i
2
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
2
U,t
(
A
)
2
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
2
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
:
a
1
,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
= [
B
1
:
b
1
,B
2
:
b
2
,...,B
n
:
b
n
]
Operandy:
R
(
U
)
,
S
(
U
) — relacje typu
U
Wynik:
T
(
U
) — relacja typu
U
Suma mnogo±ciowa
(ang. union)
T
=
R[S{
t
:
t
2R_
t
2S}
Ró»nica mnogo±ciowa
(ang. dierence)
T
=
R\S
=
{
t
:
t
2R^
t
2S}
Przekrój mnogo±ciowy
(ang. intersection)
T
=
R\S
=
{
t
:
t
2R_
t
2S
)
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
2
KROTKA
(
Z
) : (
t
0
(
A
) =
t
(
A
) dla
A
2
X
)
^
(
t
0
(
A
) =
null
(
A
) dla
A
2
Z
\
X
)
}
.
W analogiczny sposób tworzymy relacj¦
S
0
(
Z
) typu
Z
, to znaczy
S
0
(
Z
) =
{
r
0
2
KROTKA
(
Z
) : (
r
0
(
B
) =
r
(
B
) dla
B
2
Y
)
^
(
r
0
(
B
) =
null
(
B
) dla
B
2
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
2
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
2
KROTKA
(
X
) :
9
r
2R
t
=
r
[
X
]
}
,
w szczególno±ci
8
<
;
gdy
R
=
;
,
R
[
;
] =
;
(
R
) =
:
{
}
w p.p.
A
2
U
dom
(
A
)
,
2{
=
,
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
2R
:
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
2
U
i
B
2
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
2
KROTKA
(
W
) :
9
r
2R
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
2
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
2
KROTKA
(
X
[
Y
) :
X
(
t
) =
R^
Y
(
t
) =
S}
,
albo równowa»nie
R
1
S
= (
t
2
KROTKA
(
X
[
Y
) :
9
r
2R
9
s
2S
t
=
r
1
s
)
.
3.2.
Selekcja (ang. selection)
Niech
A,A
0
2
U,
2
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
,
d
)
R
X
(
R
)
1
Y
(
R
), gdzie
X
[
Y
=
U
,
b)
R
1
;
=
;
,
e
)
R
1
S
=
S
1
R
c)
R
1
X
{R}
=
R
, gdzie
X
U
,
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
2{
=
,
6
=
,<,
¬
,>,
­
,
like
,...
}
.
Relacj¦
R
R
1
F
S
=
{
t
2R×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)
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
2R×S
:
F
(
t
) =
TRUE
}[
[{
X
(
t
)
×
null
(
Y
\
X
) :
t
2R×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)
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
2R×S
:
F
(
t
) =
TRUE
}[
[{
Y
(
t
)
×
null
(
X
\
Y
) :
t
2R×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
)
.
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
Relacj¦
R
+
Relacj¦
R
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
2
U
\
X
(
R
) :
8
s
2S
t
1
s
2R
o
.
Własno±ci podzielenia:
n
o
, gdzie
R
[
t,X
] =
{
s
2
X
(
R
) :
t
1
s
2R}
.
b)
Je±li przyjmiemy, »e
n
=
count
(
S
)
,m
=
count
(
R
[
t,X
]), gdzie
t
2 R
[
U
\
X
] i
m
=
n
, to
t
2
U
\
X
(
R
) :
S
=
R
[
t,X
]
t
2R÷S
.
Zadania
Zadanie 1.
Niech
dom
(
IMIE
) =
{
0
Adam
0
,
0
Ewa
0
,
0
Karol
0
,
0
Zofia
0
}
,
dom
(
NAZWISKO
) =
{
0
Kowalska
0
,
0
Kowalski
0
,
0
Nowak
0
}
,
dom
(
PRZEDMIOT
) =
{
0
ANA
0
,
0
BAD
0
,
0
MAD
0
,
0
SIK
0
}
,
dom
(
OCENA
) =
{
2
,
3
,
4
,
5
}
,
dom
(
PUNKTY
) =
{
0
,
1
,
2
,...,
220
}
dom
(
INDEKS
) =
{
111111
,
222222
,
333333
,
444444
,
555555
,
666666
}
R
1
INDEKS IMIE NAZWISKO
222222
Ewa Kowalska
R
4
INDEKS PRZEDMIOT OCENA
111111
ANA
4
333333
Zofia Kowalska
222222
ANA
5
555555
Ewa Nowak
444444
ANA
2
555555
ANA
4
R
2
INDEKS IMIE NAZWISKO
111111
Adam Kowalski
444444
Karol Nowak
111111
BAD
3
444444
BAD
4
111111
MAD
3
R
3
IMIE NAZWISKO PUNKTY
Karol Kowalski
170
222222
MAD
4
444444
MAD
5
Ewa Nowak
219
666666
MAD
2
Zofia Nowak
165
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
=
{
PRZEDMIOT
}
(
R
4
),
c)
¬S
1
,
¬S
2
,
d)
R
2
\R
3
,
a)
R÷S
=
[ Pobierz całość w formacie PDF ]