Relacja
Schemat relacji
Schemat relacji jest to zbiór R = {A
1
, ...,
A
n
}, gdzie A
1
, ...,
A
n
są artybutami (nazwami kolumn)
np. Loty = {Numer, Skąd, Dokąd, Odlot, Przylot}
KaŜdemu atrybutowi A przyporządkowana jest dziedzina Dom(A), czyli zbiór dopuszczalnych
wartości.
np. Dom(Numer) = NUMBER(3), DOM(Skąd) = CHAR (15), .....
Dziedziną relacji o schemacie R = {A
1
, ...,
A
n
} nazywamy sumę dziedzin wszystkich trybutów
relaci: Dom(R) = Dom(A
1
) ∪ Dom(A
2
) ∪ ... ∪ Dom(A
n
)
Relacja o schemacie R = {A
1
, ..., A
n
} jest to skończony zbiór r = { t
1
,...,
t
m
}odwzorowań
t
i
: R → Dom(R) takich, Ŝe dla kaŜdego j , 1 ≤ j ≤ n, t
i
(A
j
) ∈ Dom(A
j
).
Krotka
KaŜde odwzorowanie t
i
: R → Dom(R) nazywa się krotką (lub wierszem).
Krotkę moŜna określić przez podanie wartości dla poszczególnych atrybutów:
t(Numer)=83, t(Skąd)='Warszawa', t(Dokąd)='Wrocław', t(Odlot)='6:50', t(Przylot)='8:00'
albo graficznie (wiersz tabeli)
Numer
Skąd
Dokąd
Odlot
Przylot
83
Warszawa
Wroclaw
6:50
8:00
Ograniczenie krotki t relacji r o schemacie R do zbioru atrybutów X ⊆ R to odwzorowanie:
t
|X
: X → Dom(X)
Na przykład: ograniczeniem krotki t (zdefiniowanej jak wyŜej) do zbioru X={Skąd, Dokąd}
jest krotka:
t
|X
(Skąd) = 'Warszawa', t
|X
(Dokąd) = 'Wrocław'
co graficznie jest:
Skąd
Dokąd
Warszawa
Wroclaw
ZaleŜność funkcyjna
Relacja r o schemacie R = {A
1
, ...,
A
n
}spełnia zaleŜność funkcyjną X → Y (X,Y ⊆ R)
jeśli dla kaŜdych dwóch krotek t, u ∈ r zachodzi warunek:
jeśli t
|X
= u
|X
to t
|Y
= u
|Y
tzn. w ramach krotek relacji r wartości atrybutów zbioru X determinują jednoznacznie
wartości atrybutów zbioru Y (dla kaŜdej wartości w kolumnie Y istnieje dokładnie jedna
związana z nią wartość w kolumnie X).
Zakłada się, Ŝe z kaŜdym schematem relacji związany jest zbiór spełniających ją zaleŜności
funkcyjnych (zaleŜnych od konkretnego zastosowania). Na przykład:
Numer → {Skąd, Dokąd, Odlot, Przylot}
{Skąd, Dokąd, Odlot} → {Numer, Przylot}
{Skąd, Dokąd, Przylot} → {Numer, Odlot }
Klucze
Nadkluczem relacji r o schemacie R ={A
1
, ...,
A
n
}nazywamy dowolny zbiór atrybutów X ⊆ R
taki, Ŝe zachodzi zaleŜność funkcyjna X → R. Tzn. wartość kaŜdego atrybutu jest
jednoznacznie zdeterminowana przez wartości atrybutów zbioru X . Jednym z nadkluczy jest
zawsze zbiór wszystkich atrybutów R.
Kluczem relacji r o schemacie R ={A
1
, ...,
A
n
} nazywamy kaŜdy minimalny nadklucz (nie
zawierający Ŝadnego nadklucza). A więc zbiór atrybutów X jest kluczem, jeśli wartość
kaŜdego atrybutu w R jest jednoznacznie zdeterminowana przez wartości atrybutów zbioru
X
i Ŝaden podzbiór zbioru X nie ma juŜ tej własności.
Zawsze istnieje co najmniej jeden klucz, a moŜe być ich więcej, np.
{Numer}
{Skąd, Dokąd, Odlot}
{Skąd, Dokąd, Przylot}
WyróŜniony klucz nazywa się klucze głównym. Wchodzące w jego skład atrybuty są
podkreślane.
Loty = {Numer, Skąd, Dokąd, Odlot, Przylot}
Operatory relacyjne
Operatory teorio-mnogościowe
∪ (suma), ∩ (przecięcie), - (róŜnica)
Selekcja
dla atrybutu A∈R, oraz a∈Dom(A)
{
}
( )
| ( )
A a
r
t
r t A
a
σ
=
=
∈
=
(tzn. zbiór krotek relacji r, w których wartością atrybutu jest element a)
dla dowolnego warunku logicznego F
{
}
( )
| spelnia warunek
F
r
t
r t
F
σ
=
∈
(tzn. zbiór krotek relacji r spełniający warunek F)
Pewne własności selekcji:
(
)
( )
( )
F
F
F
r
s
r
s
σ
σ
σ
∪
=
∪
(
)
(
)
( )
( )
( )
( )
( )
F G
F
G
G
F
F
G
r
r
r
r
r
σ
σ
σ
σ
σ
σ
σ
∧
=
=
=
∩
( )
( )
( )
F G
F
G
r
r
r
σ
σ
σ
∨
=
∪
Rzut
Rzut (projekcja) relacji na zbiór atrybutów X ⊆ R:
{
}
|
( )
:
X
X
r
t
t
r
π
=
∈
(tzn. ograniczenie wszystkich krotek relacji r do atrybutów zbioru X)
Przykładowe własności:
π
X
(
π
Y
(r)) =
π
X
(r) - przy załoŜeniu X ⊆ Y
π
X
(r ∪ s) =
π
X
(r) ∪
π
X
(s) - dla ∩ nie zachodzi
(
)
(
)
( )
( )
F
X
X
F
r
r
σ
π
π
σ
=
- przy załoŜeniu F(X)
RównowaŜności:
SELECT
1
,
,
n
A
A
K
FROM r WHERE F
(
)
1
{
, ,
}
( )
n
A
A
F
r
π
σ
K
Iloczyn kartezjański
Dla dwóch relacji: r o schemacie R ={A
1
, ...,
A
n
} oraz s o schemacie S ={ B
1
, ...,
B
m
}, przy
załoŜeniu
R
S
∩
= ∅
, iloczynem kartezjańskim nazywamy relację q = r ⊗ s o schemacie
Q = {A
1
, ...,
A
n
,B
1
, ...,
B
m
}, składającą się z krotek
t
q
∈
, dla których istnieją krotki u ∈ r oraz
v ∈ s, takie, Ŝe:
( )
( )
i
i
t A
u A
=
dla 1 ≤ i ≤ n, (tzn.
|R
u
t
=
)
( )
( )
i
i
t B
u B
=
dla 1 ≤ i ≤ n (tzn.
|S
v
t
=
)
(tzn. iloczyn kartezjański relacji r i s jest zbiorem wszystkich moŜliwych kombinacji krotek
tych relacji).
RównowaŜnie:
|
|
oraz
R
S
t
r
s
t
r
t
s
∈ ⊗ ⇔
∈
∈
W przypadku, gdy schematy relacji nie są rozłączne, najpierw zmieniamy nazwy atrybutów
jednej z relacji (np. na
1
. ,
, .
n
r A
r A
K
), a następnie stosujemy powyŜszą definicje.
Przykładowe własności:
(
)
(
)
(
)
r
s
q
r
q
s
q
∪
⊗ =
⊗
∪
⊗
(
)
( )
( )
F G
F
G
r
s
r
s
σ
σ
σ
∧
⊗
=
⊗
jeśli F(R), F(S)
(
)
( )
( )
X
Y
X
Y
r
s
r
s
π
π
π
∪
⊗
=
⊗
jeśli
,
X
R Y
S
⊆
⊆
RównowaŜności:
SELECT
1
,
,
k
C
C
K
FROM r,s WHERE F
(
)
1
{
,
,
}
(
)
k
C
C
F
r
s
π
σ
⊗
K
gdzie
{
} {
}
1
1
1
,
,
,
,
,
,
,
k
n
m
C
C
A
A B
B
⊆
K
K
K
Złączenie naturalne
Dla dwóch relacji : r o schemacie R = {A
1
, ...,
A
n
} oraz s o schemacie S = {B
1
, ..., B
m
}
złączenie naturalne to relacja
q
r
s
= ⊕
o schemacie
Q
R
S
=
∪
taka, Ŝe:
{
}
|
|
:
,
|
= ,
R
S
q
t
u
r v
s u
t v
t
=
∃ ∈
∈
=
(tzn. złączeniem naturalnym relacji r i s jest zbiór wszystkich moŜliwych połączeń krotek obu
relacji, przy których ich wspólne atrybuty mają takie same wartości i nie są powtarzane.
RównowaŜna definicja:
|
|
oraz
R
S
t
r
s
t
r
t
s
∈ ⊕ ⇔
∈
∈
Uwagi:
Kolejność atrybutów w relacji jest nieistotna, podobnie jak kolejność krotek.
R
S
r
s
r
s
∩
= ∅ ⇒ ⊕ = ⊗
Złączenie naturalne da się równieŜ zdefiniować w następujący sposób:
1
1
.
.
.
.
(
(
))
k
k
R S
r D
s D
r D
s D
r
s
r
s
π
σ
∪
=
∧
=
⊕ =
⊗
K
gdzie
{
}
1
,
,
k
R
S
D
D
∩
=
K
Podstawowe własności złączenia naturalnego:
1.
q
q
q
⊕ =
2.
q
r
r
q
⊕ = ⊕
3.
(
)
(
)
q
r
s
q
r
s
⊕
⊕ = ⊕
⊕
4.
(
)
oraz
(
)
R
S
r
s
r
r
s
s
π
π
⊕
⊆
⊕
⊆
5.
( )
( )
R
S
q
q
q
π
π
⊆
⊕
Gdy zachodzi 4), złączanie nie traci informacji zawartych w r i s. Złączanie naturalne jednak
nie wyklucza tracenia informacji (porównaj ze złączaniem zewnętrznym).
Gdy zachodzi 5), relacja q rozkłada się względem podziału na R i S z zachowaniem
informacji. Tylko w takim przypadku moŜna zastąpić w bazie danych relację q przez relacje
( )
R
q
π
i
( )
S
q
π
.
Przykład:
Q={A,B,C}, R={A,B}, S={B,C}
1
1
1
A
B
C
q
a
b
c
a
b
c
=
( )
1
1
R
A
B
q
a
b
a
b
π
=
( )
1
1
S
B
C
q
b
c
b
c
π
=
( )
( )
1
1
1
1
1
R
S
A
B
C
a
b
c
q
q
q
a
b
c
a
b
c
a
b
c
π
π
⊕
=
≠
Ocena poprawności relacji
Przykład:
relacja (zła): Dostawcy={Nazwa_dostawcy, Adres_dostawcy, Nazwa_towaru, Cena}
zaleŜności funkcyjne: Nazwa_dostawcy → Adres_dostawcy
Nazwa_dostawcy, Nazwa_towaru → Cena
relacja (zła): Pracownicy={Id_pracownika, Nazwisko, Instytucja, Nazwa_instytucji,
Adres_instytucji}
zaleŜności funkcyjne: Id_pracownika → Nazwisko, Nazwa_instytucji
Nazwa_instytucji → Adres_instytucji
Ze schematem relacji wiąŜe się pewien zbiór zaleŜności funkcyjnych F.
ZaleŜność funkcyjna X →Y wynika logicznie z zaleŜności funkcyjnych F
(oznaczenie F
|=
X → Y), jeśli kaŜda relacja r spełniająca wszystkie zaleŜności w zbiorze F
spełnia równieŜ zaleŜność X → Y.
Jeśli
F= {Nazwa_dostawcy → Adres_dostawcy; Nazwa_dostawcy, Nazwa_towaru → Cena}
to
F
|=
Nazwa_dostawcy, Nazwa_towaru → Adres_dostawcy, Cena}
Domknięcie
Domknięcie zaleŜności funkcyjnych F, oznaczane przez F
+
to zbiór wszystkich zaleŜności
funkcyjnych wynikających logicznie z zaleŜności funkcyjnych F.
Przykładowo: A → C
∈
{A → B; B → C}
+
Klucze – rozszerzona definicja
Nadkluczem relacji r o schemacie R ={A
1
, ...,
A
n
} i zbiorze zaleŜności funkcyjnych F
nazywamy dowolny zbiór atrybutów X
∈
R taki, Ŝe: X
→ R
∈
F
+
Kluczem relacji r o schemacie R ={A
1
, ...,
A
n
} i zbiorze zaleŜności funkcyjnych F nazywamy
dowolny minimalny nadklucz relacji r, tzn. dowolny zbiór atrybutów X
∈
R, taki, Ŝe:
1.
X
→ R
∈
F
+
2.
dla Ŝadnego Y
⊆ X, X ≠ Ynie zachodzi Y → R
∈
F
+
Przykład:
R={Miasto, Ulica, Kod}, F={Miasto,Ulica
→ Kod; Kod → Miasto}
Kluczami tego schematu są: {Miasto, Ulica}, {Ulica, Kod}
R={A,B,C,D}, F={A
→ C;B → D}
Kluczem jest {A,B}
ZaleŜność funkcyjna nie od klucza
ZaleŜność funkcyjna X
→ Y jest zaleŜnością od klucza, jeśli zbiór atrybutów X jest
nadkluczem.
ZaleŜność funkcyjna X
→ Y jest zaleŜnością nie od klucza, jeśli:
1.
jest nietrywialna (tzn. zbiór Y nie jest podzbiorem X)
2.
nie jest zaleŜnością od klucza
ZaleŜności nie od klucza dla relacji Dostawcy: Nazwa_dostawcy
→ Adres_dostawcy
ZaleŜności nie od klucza dla relacji Pracownicy: Nazwa_instytucji
→ Adres_instytucji
Algorytmy sprowadzania relacji do poprawnej postaci
Domknięcie tranzytywne
Dla zbioru X
R
⊆
jego domknięciem tranzytywnym względem zbioru zaleŜności funkcyjnych
F nazywamy następujący zbiór atrybutów: X
+
= {A
∈R: X → A ∈ F
+
}
(tzn. zbiór wszystkich atrybutów, których wartości są w pełni zdeterminowane przez wartości
atrybutów ze zbioru X)
Aby sprawdzić, czy dana zaleŜność funkcyjna X
→ Y wynika logicznie ze zbioru zaleŜności
funkcyjnych F wystarczy wyznaczyć domknięcie tranzytywne zbioru X, tj. X
+
. Zachodzi
bowiem własność: X
→ Y ∈ F
+
⇔ X ⊆ X
+
.
Algorytm wyznaczania domknięcia tranzytywnego:
Konstruujemy ciąg zbiorów:
1. X
0
= X
2. X
i+1
= X
i
plus zbiór atrybutów A takich, Ŝe
•
istnieje pewna zaleŜność funkcyjna X
→ Z ∈ F
•
A naleŜy do Z
•
Y
⊆ X
i
dopóki nie zajdzie X
i
= X
i+1
.
3. Wtedy X
+
=
i
X
Inaczej mówiąc: Jeśli w F istnieje zaleŜność funkcyjna Y
→ Z oraz wszystkie atrybuty zbioru
Y zostały juŜ wygenerowane, wówczas mamy prawo wygenerować kaŜdy z atrybutów zbioru
Z.
Przykład:
R={A,B,C,D,E,G}
F={A,B
→ C; D → E,G; C → A; B,E → C; B,C → D; C,G → B,D; A,C,D → B; C,E → A,G}
X={B,D}
Wówczas
X0={B,D}
X1={B,D,E,G}
X2={B,C,D,E,G}
X3={A,B,C,D,E,G}=R
Czyli X
+
=R, co oznacza, Ŝe zbiór {B,D} jest nadkluczem. PoniewaŜ {B}
+
={B},
{D}
+
={D,E,G}, więc {B,D} jest kluczem.
Niech Q ={A
1
, ...,
A
n
}będzie schematem relacji, a F zbiorem zaleŜności funkcyjnych.
Usunięcie anomalii i redundancji relacji o schemacie Q odbywa się przez rozkład Q = R
∪ S
na dwa schematy R i S.
Niech
π
Z
(F) = { X
→ Y ∈ F
+
: X
∪Y ⊆ Z} - rzut F na Z. Mówimy, Ŝe rozkład Q = R ∪ S
zachowuje:
1.
informacje, gdy dla kaŜdej relacji q spełniającej zaleŜności funkcyjne F zachodzi:
q =
π
R
(q)
⊕
π
S
(q)
2.
zaleŜności funkcyjne, gdy
F
+
= (
π
R
(F)
∪
π
S
(F))
+
(czyli kaŜda zaleŜność funkcyjna X
→ Y ∈ F daje się wyprowadzić ze zbioru rzutów
zaleŜności
π
R
(F)
∪
π
S
(F))
Własność: Rozkład
Q
R
S
=
∪
zachowuje informacje wtedy i tylko wtedy gdy
albo (R
∩ S) → (R - S) ∈ F
+
albo (R
∩ S) → (S - R) ∈ F
+
Przykład:
Relacja dostawcy i jej zaleŜności funkcyjne
Q={D,A,T,C}, F={D
→ A; D,T → C}
Proponowany podział: R = {D,A}, S = {D,T,C}
ZauwaŜmy, Ŝe: R - S = {A}, R
∩ S = {D}, S - R = {T,C}.
A stąd:
poniewaŜ D
→ A ∈ F, więc rozkład zachowuje informacje;
poniewaŜ F =
π
R
(F)
∪
π
S
(F), więc rozkład zachowuje funkcyjne zaleŜności.