Bazy danych, model 

Bazy danych, model 

relacyjny, normalizacja 

relacyjny, normalizacja 

relacji

relacji

Paweł Skrzyński, 

skrzynia@agh.edu.pl

http://home.agh.edu.pl/skrzynia/

wste

 

 

Zależności funkcyjne

Zależności funkcyjne



Najważniejszy rodzaj więzów z jakim mamy do 
czynienia w modelu relacyjnym dotyczy więzów 
jednoznaczności nazywanych zależnościami 
funkcyjnymi



Wiedza dotycząca tych więzów jest nieodzowna w 
przypadku powtórnego definiowania schematu 
relacyjnego (np.. W celu wyeliminowania z niego 
redundancji)



Definicja. Jeżeli dwie krotki relacji R są zgodne dla 
atrybutów A

1

, A

2

, ..., A

n

 to muszą być zgodne również 

w pewnym innym atrybucie B.



Zapis: A

1

, A

2

, ..., A

n

  B

 

 

Uwagi 1

Uwagi 1



Zapis ten czytamy jako A

1

, A

2

, ..., A

n

 

określają funkcyjnie B”



Jeśli zbiór atrybutów A

1

, A

2

, ..., A

n

 określa 

funkcyjnie więcej niż jeden atrybut:

A

1

A

2

...A

n

   B

1

...
A

1

A

2

...A

n

   B

m

to zapisujemy to skrótowo jako:

A

1

A

2

...A

n

 B

1

B

2

..B

m

 

 

Uwagi 2

Uwagi 2



Zależności funkcyjne dotyczą schematu 
bazy a nie określonej instancji. Zatem 
patrząc na jakąś instancję nie możemy 
stwierdzić, że istnieją jakieś zależności 
lub ich nie ma.



Definicja. Zależność trywialna: 
zależność funkcyjna A

1

A

2

A

n

B jest 

trywialna wtw. gdy B jest równe 
któremuś z A.

 

 

Wynik zależności 

Wynik zależności 

funkcyjnej dwóch krotek

funkcyjnej dwóch krotek

A

B

t

u

Jeśli t i u są 
zgodne tutaj 

To muszą być 
też zgodne tutaj

 

 

Przykładowa relacja Film

Przykładowa relacja Film

Tytuł Rok Długoś

ć

TypFilm

u

NazwaStu

dia

Nawisk

oGwiaz

dy

Gwiezdn

e Wojny

1977

124

Kolor

Fox

Carrie 

Fisher

Gwiezdn

e Wojny

1977

124

Kolor

Fox

Mark 

Hamill

Gwiezdn

e Wojny

1977

124

Kolor

Fox

Harrison 

Ford

Potężne 

Kaczory

1991

104

Kolor

Disney

Emilio 

Estevez

Świat 

Wayne’a

1992

95

Kolor

Paramount

Dana 

Carvey

Świat 

Wayne’a

1992

95

Kolor

Paramount

Mike 

Meyers

 

 

Przykład 1

Przykład 1



Rozważając relację film można 

wyodrębnić kilka zależności 

funkcyjnych, na przykład:

Tytuł Rok  Długość
Tytuł Rok  TypFilmu
Tytuł Rok  NazwaStudia



Ponieważ lewe strony zależności są 

takie same możemy zapisać:

Tytuł Rok  Długość TypFilmu 

NazwaStudia

 

 

Przykład 1, c.d.

Przykład 1, c.d.



Powyższy zbiór zależności funkcyjnych można 

nieformalnie odczytać:

–

jeśli 2 krotki maja takie same wartości składowej 

tytuł oraz takie same wartości składowej rok to 

muszą mieć również takie same wartości 

składowych Długość, TypFilmu oraz NazwaStudia.



Można się spodziewać, że atrybuty tytuł oraz 

rok tworzą klucz relacji jednak przy bliższej 

obserwacji widać, że te atrybuty nie określają 

atrybutu NazwiskoGwiazdy zatem zależność: 

Tytuł Rok  NazwiskoGwiazdy jest fałszywa

 

 

Klucze relacji

Klucze relacji



Mówimy, że atrybut lub zbiór atrybutów 
{A

1

, A

2

, ..., A

n

} tworzy klucz relacji jeżeli:

1.

Wszystkie pozostałe atrybuty relacji są 
funkcyjnie zależne od tych atrybutów. Zatem 
nie może się zdarzyć, aby 2 różne krotki 
relacji R były zgodne dla wszystkich 
atrybutów A

1

, A

2

, ..., A

n

.

2.

Nie istnieje taki podzbiór właściwy zbioru 
{A

1

, A

2

, ..., A

n

} od którego pozostałe atrybuty 

są zależne funkcynie tzn. klucz musi być 
minimalny.

 

 

Przykład 2

Przykład 2



Atrybuty {Tytuł, Rok, NazwiskoGwiazdy} 
tworzą klucz relacji Film



Aby to wykazać należy wykazać, że 
wszystkie pozostałe atrybuty są od nich 
funkcyjnie zależne oraz że nie istnieje żaden 
podzbiór tego zbioru, który również by był 
kluczem (zatem określał by funkcyjnie 
pozostałe atrybuty)



Zadanie konkursowe: przeprowadzić dowód 
(4 minuty czasu)

 

 

Przykład 2, dowód

Przykład 2, dowód



Załóżmy, ze 2 krotki są zgodne dla wszystkich 3 
wartości atrybutów: Tytuł, Rok, 
NazwiskoGwiazdy. Ze względu na to, że są zgodne 
dla atrybutów Tytuł i Rok są też zgodne dla 
atrybutów Długość, TypFilmu oraz NazwaStudia 
(na podstawie zależności funkcyjnych)



Łatwo wykazać, że ani para {Rok, 
NazwiskoGwiazdy} (w danym roku gwiazda może 
wystąpić w wielu filmach) ani {Tytuł, 
NazwiskoGwiazdy} (można nakręcić remake filmu 
po paru latach) nie stanowią klucza tej relacji.

 

 

Nadklucze

Nadklucze



Definicja. Zbiór atrybutów, który 
zawiera klucz nazywa się 
nadkluczem.



Jest to skrót od pojęcia nadzbioru 
klucza. Zatem każdy klucz jest 
nadkluczem ale istnieją nadklucze, 
które nie są kluczami gdyż nie 
spełniają warunku minimalności.

 

 

Reguły dotyczące 

Reguły dotyczące 

zależności funkcyjnych

zależności funkcyjnych



Załóżmy, że mamy informację na temat zależności 

spełnianych przez relację. Często nawet bez 

oglądania przykładów krotek można określić pewne 

warunki, które muszą być spełnione w relacji.



Jeżeli zależności funkcyjne można określić na różne 

sposoby i nie ma to wpływu na instancję relacji to 

takie zależności nazywamy równoważnymi.



Ogólniejsza właściwość: zbiór zależności funkcyjnych 

S wynika ze zbioru zależności funkcyjnych T. Tzn. dla 

dowolnej instancji relacji R spełniającej wszystkie 

zależności w T wynika, że spełnia także wszystkie 

zależności w S.



Spostrzeżenie: S i T są równoważne wtedy gdy z S 

wynika T i z T wynika S.

 

 

Reguła przechodniości

Reguła przechodniości



Jeżeli w relacji R z atrybutami A, B, C 
zachodzą zależności:

A  B
B  C



To w R zachodzi również zależność 
funkcyjna:

A  C



Zadanie konkursowe: wykazać 
prawdziwość tej reguły (4 minuty)

 

 

Reguła przechodniości, 

Reguła przechodniości, 

dowód

dowód



Weźmy dowolne dwie krotki z relacji R, 

które są zgodne dla atrybutu A.



Zatem mają postać:

–

(a, b

1

, c

1

)

–

(a, b

2

, c

2

)



Ponieważ mamy zależność A  B to b

1

=b

2 

(występuje zatem zgodność dla atrybutu B).



Korzystając z drugiej zależności B  C 

otrzymujemy: c

1

 = c

2

.



Zatem zachodzi A  C.

 

 

Zasady podziału i łączenia

Zasady podziału i łączenia



Zasada podziału. Zależność funkcyjną 
A

1

A

2

...A

n

   B

1

B

2

..B

m

 możemy zastąpić 

zbiorem zależności funkcyjnych 
A

1

A

2

...A

n

   B

i

 gdzie i=1, 2, ..., m.



Zasada łączenia. Zbiór zależności 
funkcyjnych A

1

A

2

...A

n

   B

i

 gdzie i=1, 

2, ..., m możemy zastąpić pojedynczą 
zależnością funkcyjną A

1

A

2

...A

n

   

B

1

B

2

..B

m

.

 

 

Zależności trywialne

Zależności trywialne



Zależność trywialna: zależność 
funkcyjna A

1

A

2

...A

n

  B jest trywialna wtw. 

gdy B jest równe któremuś z A.



Zależność A

1

A

2

...A

n

   B

1

B

2

..B

m

 jest:

–

Trywialna, jeśli zbiór B jest podzbiorem zbioru 
A

–

Nietrywialna, jeśli co najmniej jeden z 
atrybutów B nie znajduje się w A

–

Całkowicie nietrywialna: żaden z atrybutów B 
nie znajduje się w A

 

 

Reguła zależności 

Reguła zależności 

trywialnych

trywialnych



Atrybuty, które występują równocześnie 
po lewej i po prawej stronie zawsze 
można pominąć po prawej stronie. Stąd 
wynika reguła zależności trywialnych:



Zależność funkcyjna A

1

A

2

...A

n

   

B

1

B

2

..B

m

 jest równoważna zależności 

A

1

A

2

...A

n

   C

1

C

2

..C

k

 gdzie C są tymi 

elementami z B, które nie są równe A

 

 

Reguła zależności 

Reguła zależności 

trywialnych, c.d.

trywialnych, c.d.

A

B

t

u

Jeśli t i u są 
zgodne dla A

To muszą być 
też zgodne dla B

C

Zatem na pewno 
są zgodne też 
dla C

 

 

Obliczanie domknięcia zbioru 

Obliczanie domknięcia zbioru 

atrybutów

atrybutów



Założenia:

–

A={A

1

, A

2

, ..., A

n

}, zbiór atrybutów

–

S, zbiór zależności funkcyjnych



Domknięciem zbioru A nad zbiorem zależności S 
nazywamy taki zbiór atrybutów B, że jeżeli pewna 
relacja R spełnia wszystkie zależności ze zbioru S, to 
spełnia także zależność A

1

A

2

...A

n

B, a zatem 

zależność ta wynika z S.



Domknięcie zbioru oznaczamy przez {A

1

, A

2

, ..., A

n

}

+

.



Uwagi: dopuszczamy zależności trywialne zatem {A

1

, 

A

2

, ..., A

n

} jest zawsze zawarte w {A

1

, A

2

, ..., A

n

}

+

.

 

 

Obliczanie domknięcia zbioru 

Obliczanie domknięcia zbioru 

atrybutów

atrybutów

Początko

wy zbiór 

atrybutów

Wypychanie

Domknięcie

 

 

Algorytm

Algorytm

1.

X – nazwa zbiru domknięcia, na początku 

X={A

1

, A

2

, ..., A

n

}=A, 

2.

Znajdujemy wszystkie zależności funkcyjne 

postaci: B

1

B

2

...B

m 

C, gdzie B

1

, B

2

,..., B

m

 

należą do X a C nie należy. Wówczas 

dołączamy C do zbioru X.

3.

Powtarzamy krok 2 tak długo jak można 

dołożyć jakiś atrybut do X.

4.

Jeśli nie można już dołożyć żadnego 

atrybutu do X to koniec. X={A

1

, A

2

, ..., A

n

}

+

 

 

Przykład 3

Przykład 3



Relacja R posiada atrybuty: A, B, C, D, E, F.



Zachodzą zależności: ABC, BCAD, DE, CFB.



Szukamy domknięcia zbioru {A, B}:

1.

X={A, B}, bierzemy zależność ABC gdyż 

wszystkie lewe atrybuty są w X. Dołączamy C do X.

2.

X={A, B, C}, bierzemy zależność BCAD gdyż 

wszystkie lewe atrybuty są w X. Dołączamy D do X 
(A już jest w X).

3.

X={A, B, C, D}, bierzemy zależność DE gdyż 

wszystkie lewe atrybuty są w X. Dołączamy E do X.

4.

X={A, B, C, D, E}. Nie można dołączy więcej 
atrybutów zatem {A, B}

+

={A, B, C, D, E}

 

 

Obliczanie domknięcia zbioru, 

Obliczanie domknięcia zbioru, 

c.d.

c.d.



Jeśli potrafimy obliczyć domknięcie 

dowolnego zbioru atrybutów to możemy 

sprawdzić czy dana zależność funkcyjna 

A

1

A

2

...A

n

B wynika ze zbioru zależności S



Najpierw obliczamy {A

1

, ..., A

n

}

+

 dla zbioru 

zależności S



Jeśli B należy do {A

1

, ..., A

n

}

+

 to A

1

A

2

...A

n

B 

wynika z S



Jeśli B nie należy do {A

1

, ..., A

n

}

+

 to 

A

1

A

2

...A

n

B nie wynika z S

 

 

Przykład 4

Przykład 4



Relacja R i zależności funkcyjne 
takie jak w przykładzie 3



Zadanie: chcemy ustalić czy z tego 
zbioru zależności wynika AB D



Wiemy już że: {A, B}

+

={A, B, C, D, 

E}



Ponieważ D należy do {A, B}

+

 to AB 

D wynika ze zbioru zależności.

 

 

Domknięcia i klucze

Domknięcia i klucze



Zauważmy, że zbiór {A

1

, ..., A

n

}

+ 

zawiera 

wszystkie atrybuty relacji R wtedy i tylko 

wtedy gdy atrybuty A

1

, ..., A

n

 są nadkluczem 

w R. Tylko wtedy wszystkie atrybuty są 

zależnie funkcyjnie od zbioru A.



Stwierdzenie czy atrybuty A

1

, ..., A

n

 stanowią 

klucz relacji może polegać na:

–

Stwierdzeniu czy wszystkie atrybuty R należą do 

zbioru A

+

–

A następnie czy S

+

 otrzymane z dowolnego S, 

które tworzymy poprzez usunięcie co najmniej 

jednego elementu spośród A

1

, ..., A

n

, nie zawiera 

wszystkich atrybutów R

 

 

Aksjomaty Armstronga

Aksjomaty Armstronga



Reguły, które umożliwiają z danego zbioru 

zależności wyprowadzenie wszystkich tych, 

które są od nich zależne funkcyjnie:

1.

Zwrotność. Jeśli {B

1

, ..., B

m

} zawierają się w 

{A

1

, ..., An} to A

1

A

2

...A

n

B

1

B

2

..B

m

2.

Rozszerzenie. Jeśli A

1

A

2

...A

n

B

1

B

2

..B

m

 to 

A

1

A

2

...A

n

C

1

C

2

..C

k

B

1

B

2

..B

m 

C

1

C

2

..C

k

 dla 

dowolnych C

1

, C

2

, ...C

k

3.

Przechodniość. Jeśli A

1

A

2

...A

n

 B

1

B

2

..B

m

 oraz 

B

1

B

2

...B

m

C

1

C

2

..C

k

 to A

1

A

2

...A

n

 C

1

C

2

..C

k

 

 

Domknięcie zbioru zależności 

Domknięcie zbioru zależności 

funkcyjnych

funkcyjnych



Z przedstawionych rozważań wynika, iż 

zbiór zależności można rozszerzyć zarówno 

o zależności trywialne jak i nietrywialne.



Czasami pożądane jest by odróżniać 

zależności zadane w definicji relacji od tych 

wyprowadzonych z tego zbioru



Definicja. Każdy zbiór zależności, z którego 

można wyprowadzić wszystkie inne 

zależności nazywa się bazą tej relacji.



Jeśli żaden z podzbiorów bazy nie umożliwia 

wyprowadzenia wszystkich zależności to 

baza tak jest bazą minimalną.

 

 

Anomalie

Anomalie



Oglądając relację Film łatwo 
zauważyć iż występuję redundancja 
danych. Źródłem takiej redundancji 
często jest próba umieszczenia w 
jednej relacji danych 
jednowartościowych (np. długość 
filmu) wspólnie z danymi 
wielowartościowymi (np. zbiór gwiazd 
jakie grają w filmie)

 

 

Anomalie

Anomalie



Redundancja. Te same dane niepotrzebnie 

powtarzają się w kilku krotkach (Długość, 

TypFilmu w relacji Film).



Anomalie modyfikacji. Gdy wartość danej zostanie 

zmodyfikowana w jednej krotce a w innej nie.



Anomalie usunięć. Gdy dla pewnego atrybutu 

zaczyna obowiązywać wartość pusta to jako efekt 

uboczny może się zdarzyć utrata części danych. 

Jeśli np. ze zbioru gwiazd filmu usuniemy 

nazwisko Emilio Estevez to z relacji Film znikną 

wszystkie dane dotyczące filmu Potężne Kaczory

 

 

Dekompozycja relacji

Dekompozycja relacji



Właściwym sposobem 
eliminowania wymienionych 
anomalii jest dekompozycja relacji.



Sprowadza się do podziału 
atrybutów relacji wejściowej  R 
pomiędzy nowe relacje (operacja 
rzutowania).

 

 

Dekompozycja relacji, 

Dekompozycja relacji, 

algorytm

algorytm



Relację R o schemacie {A

1

, ..., A

n

} 

dekomponujemy pomiędzy 2 relacje S i T o 

schematach {B

1

, ..., B

m

} oraz {C

1

, ..., C

k

} 

według następujących zasad:

1.

{A

1

, ..., A

n

} = {B

1

, ..., B

m

}  {C

1

, ..., C

k

}

2.

Krotki relacji S powstają poprzez rzutowanie 

wszystkich krotek relacji R na atrybuty {B

1

, 

B

2

, ..., B

m

}

3.

Krotki relacji T powstają poprzez rzutowanie 

wszystkich krotek relacji T na atrybuty {C

1

, 

C

2

, ..., C

k

}

 

 

Dekompozycja, przykład

Dekompozycja, przykład



Dokonamy dekompozycji relacji Film. 
Przykładowy wybór atrybutów do 
nowych relacji (motywy czemu 
właśnie taki podane zostaną później):

–

Do relacji Film1 wchodzą wszystkie 
atrybuty oprócz atrybutu 
NazwiskoGwiazdy

–

Do relacji Film2 wchodzą atrybuty: 
Tytuł, Rok, NazwiskoGwiazdy

 

 

Tytuł Rok Długoś

ć

TypFilm

u

NazwaStu

dia

Nawisk

oGwiaz

dy

Gwiezdn

e Wojny

1977

124

Kolor

Fox

Carrie 

Fisher

Gwiezdn

e Wojny

1977

124

Kolor

Fox

Mark 

Hamill

Gwiezdn

e Wojny

1977

124

Kolor

Fox

Harrison 

Ford

Potężne 

Kaczory

1991

104

Kolor

Disney

Emilio 

Estevez

Świat 

Wayne’a

1992

95

Kolor

Paramount

Dana 

Carvey

Świat 

Wayne’a

1992

95

Kolor

Paramount

Mike 

Meyers

Relacja Film

Relacja Film

 

 

Relacje Film1 i Film2

Relacje Film1 i Film2

Tytuł

Rok

Długoś

ć

TypFilmu

NazwaStudi

a

Gwiezdne 

Wojny

1977

124

Kolor

Fox

Potężne 

Kaczory

1991

104

Kolor

Disney

Świat Wayne’a

1992

95

Kolor

Paramount

Tytuł

Rok NazwiskoGwiazdy

Gwiezdne Wojny

1977 Carrie Fischer

Gwiezdne Wojny

1977 Mark Hamill

Gwiezdne Wojny

1977 Harrison Ford

Potężne Kaczory

1991 Emilio Estevez

Świat Wayne’a

1992 Dana Carvey

Świat Wayne’a

1992 Mike Meyers

 

 

Postać normalna Boyc’a-

Postać normalna Boyc’a-

Codda

Codda



Zadanie dekompozycji polega na zastąpieniu 
relacji równoważnym jej zbiorek relacji, 
których struktura wyeliminuje anomalie



Istnieje prosty warunek, którego spełnienie 
wyeliminuje omówionej anomalii.



Definicja. Relacja R jest w postaci BCNF 
wtw. Dla każdej nietrywialnej zależności 
A

1

A

2

A

n

B zbiór {A

1

, A

2

, ..., A

n

} jest 

nadkluczem R 

 

 

Postacie normalne

Postacie normalne



Warunek równoważny do BCNF: lewa 
strona każdej nietrywialnej zależności 
musi być nadkluczem.



Definicja (alternatywna). Relacja R 
jest w postaci BCNF wtw. Dla każdej 
nietrywialnej zależności 
A

1

A

2

...A

n

B

1

B

2

...B

m

 zachodzącej w R 

zbiór {A

1

, A

2

, ..., A

n

} jest nadkluczem R 

 

 

Czy relacja Film jest w 

Czy relacja Film jest w 

BCNF?

BCNF?



Przypomnijmy iż klucz tej relacji tworzą 
atrybuty: Tytuł, Rok, NazwiskoGwiazdy



Każdy zbiór zawierający te trzy atrybuty 
jest nadkluczem



W relacji tej mamy zależność:

–

Tytuł Rok  Długość TypFilmu NazwaStudia



Lewa strona tej zależności nie jest 
nadkluczem



Zatem relacja Film nie jest w BCNF

 

 

Czy relacja Film1 jest w 

Czy relacja Film1 jest w 

BCNF?

BCNF?



Zachodzi zależność:

–

Tytuł Rok  Długość TypFilmu 

NazwaStudia



Jedynym kluczem tej relacji jest para 

{Tytuł, Rok}



Zatem jedyna nietrywialna zależność 

funkcyjna musi mieć po lewej stronie 

te atrybuty



...i ma 

 

 

Dekompozycja do postaci 

Dekompozycja do postaci 

BCNF

BCNF



Spostrzeżenie: każda relacja binarna (dwu 

atrybutowa) jest w BCNF. (zadanie 

konkursowe: udowodnić to twierdzenie, czas 

10 minut)



Jeśli proces dekompozycji będziemy powtarzać 

dostatecznie długo to każdą relację zapiszemy 

w końcu w postaci kolekcji podzbiorów 

atrybutów, które spełnia następujące warunki:

–

Podzbiory te będą relacjami w postaci BCNF

–

Dane z pierwotnej relacji są wiernie 

reprezentowane w relacjach powstałych w wyniku 

dekompozycji

 

 

Strategia dekompozycji

Strategia dekompozycji



Znajdź nietrywialną zależność 
A

1

A

2

...A

n

B

1

B

2

...B

m

 która narusza BCNF 

(czyli A

1

, A

2

, ...A

n 

nie są nadkluczem)



Podziel atrybuty na 2 podzbiory:

–

Do jednego należą wszystkie atrybuty, które 
pojawiają się w tej zależności

–

A do drugiego atrybuty A (z lewej strony 
zależności) oraz wszystkie pozostałe atrybuty, 
które nie pojawiają się po prawej stronie tej 
zależności

 

 

Dekompozycja schematu relacji na 

Dekompozycja schematu relacji na 

podstawie naruszenia warunku BCNF

podstawie naruszenia warunku BCNF

A B

Inne

 

 

Dekompozycja do BCNF - 

Dekompozycja do BCNF - 

przykład 1

przykład 1



Rozważmy nasza relację Film. Wcześniej 

wykazano, że zależność: Tytuł Rok  

Długość TypFilmu NazwaStudia narusza 

warunek BCNF



Zatem stosując naszą strategię dokonamy 

podziału atrybutów na następujące zbiory:

–

{Tytuł, Rok, Długość, TypFilmu, NazwaStudia}

–

{Tytuł, Rok, NazwiskoGwiazdy}



Zatem są to schematy Film1 i Film2, o 

których już wiemy, że są w BCNF

 

 

Dekompozycja do BCNF – 

Dekompozycja do BCNF – 

przykład 2

przykład 2

Tytuł 

Rok  Długość  TypFilmu  NazwaStudia  AdresStudia 

Gwiezdne wojny 

1977 

124 

Kolor 

Fox 

Hollywood 

Potężne kaczory 

1991 

104 

Kolor 

Disney 

Buena Vista 

Świat Wayn’a 

1992 

95 

Kolor 

Paramount 

Hollywood 

Rodzina Adamsów  1991 

102 

Kolor 

Paramount 

Hollywood 

 

Spostrzeżenie: 
istnieje redundancja - 
adres studia 
Paramount występuje 
dwukrotnie

•W relacji występują dwie zależności:

•Tytuł Rok  NazwaStudia

•NazwaStudia  AdresStudia

•Na podstawie reguły przechodności

•Tytuł Rok  AdresStudia

•Istnieje jeszcze inna oczywista zależność:

•Tytuł Rok  Długość TypFilmu

•Zależność (stosowana w regule przechodności):

•NazwaStudia  AdresStudia

  Nie jest zależnością trywialną, jej lewa strona nie 
jest nadkluczem

•Wniosek: relacja nie spełnia warunku BCNF 

 

 

Przykład 2, c.d.

Przykład 2, c.d.



Atrybuty z powyższej zależności wchodzą do 

schematu pierwszej relacji powstałej w wyniku 

dekompozycji:

–

{NazwaStudia, AdresStudia}



Do drugiego schematu będą należeć wszystkie 

atrybuty relacji poza AdresStudia (występuje 

po prawej stronie zależności na podstawie, 

której dokonujemy dekompozycji), zatem 

schemat drugiej relacji wygląda następująco:

–

{Tytuł, Rok, Długość, TypFilmu, NazwaStudia}



Otrzymujemy zatem dwie nowe relacje

 

 

Przykład 2, c.d.

Przykład 2, c.d.

Tytuł

Rok

Długość

TypFilmu

NazwaStudia

Gwiezdne 

wojny 

1977

124

Kolor

Fox

Potężne 

kaczory 

1991

104

Kolor

Disney

Świat Wayn’a 

1992

95

Kolor

Paramount

Rodzina 

Adamsów 

1991

102

Kolor

Paramount

NazwaStudia

AdresStudia

Fox

Hollywood

Disney

Buena Vista

Paramount

Hollywood

 

 

Projektowanie zależności 

Projektowanie zależności 

funkcyjnych

funkcyjnych



Po wykonaniu dekompozycji trzeba sprawdzić czy otrzymane nowe 
schematy spełniają warunek BCNF.



Problem: jak stwierdzić jakie zależności zachodzą w nowym 
schemacie?

Rozwiązanie:



Załóżmy, że w wyniku dekompozycji relacji R powstaje relacja S 
oraz jakaś inna relacja T.



Oznaczenie: zbiór zależności prawdziwych w R oznaczamy przez F.



Rozważmy podzbiory X zboru atrybutów S. Dla każdego z nich 
obliczamy X

+

 (nad zbiorem F). Wówczas jeśli jakiś atrybut B spełnia 

warunki:

–

B należy do S

–

B należy do X

+

–

B nie należy do X

To zależność funkcyjna XB jest spełniona w relacji S.

 

 

Przykład

Przykład

Sytuacja:



Relacja R: R(A, B, C, D)



Zależności w R: AB, BC



Schemat S: S(A, C) powstał w wyniku 

dekompozycji



Obliczamy domknięcia wszystkich podzbiorów:

–

{A}

+

={A, B, C}, atrybut B nie należy do S zatem w 

S nie zachodzi AB, zachodzi natomiast AC

–

{C}

+

={C}, nie wprowadza nic nowego

–

{A, C}

+

={A, B, C}={A}

+

, również nie wprowadza 

nic nowego



Zatem jedyną zależnością spełnioną w S jest 

AC

 

 

Przykład 2

Przykład 2

Sytuacja:



Relacja R: R(A, B, C, D, E)



Zależności w R: AD, BE, DEC



Schemat S: S(A, B, C) powstał w wyniku 
dekompozycji



Obliczamy domknięcia wszystkich podzbiorów:

–

{A}

+

={A, D}, w schemacie nie występuje atrybut D 

–

{B}

+

={B, E}, również nie wprowadza żadnej zależności

–

{C}

+

={C}, jak wyżej

–

{A, B}

+

={A, B, C, D, E}- zatem w S zachodzi ABC

–

Żadna inna para atrybutów nie dostarczy nowych zależności

–

Podobnie zbiór wszystkich trzech atrybutów



Zatem jedyną zależnością spełnioną w S jest ABC

 

 

Uproszczenie poszukiwania 

Uproszczenie poszukiwania 

zależności

zależności



Nie trzeba rozważać domknięcia zbioru 
wszystkich atrybutów S



Nie trzeba rozważać zbiorów atrybutów, 
do których nie należy żadna lewa strona 
jakiejkolwiek zależności



Nie trzeba rozważać zbirów, do których 
należy jakikolwiek atrybut, który nie 
występuje po lewej stronie jakiejkolwiek 
zależności

 

 

Odzyskiwanie danych po 

Odzyskiwanie danych po 

dekompozycji

dekompozycji



Weźmy relację R(A, B, C), w której zachodzi zależność 
BC naruszająca BCNF (np.. Jest to jedyna zależność 

nietrywialna, wtedy jedynym kluczem jest para A, B)



Dekompozycja dzieli R na schematy S(A, B) i T(B, C)



Niech t będzie pewną krotką z R: t=(a, b, c) (a, b, c, 
składowe t dla atrybutów A, B, C)



W wyniku rzutowania t na schemat

–

S otrzymujemy krotkę (a, b), 

–

T otrzymujemy krotkę (b, c)



Jeśli wartości składowej B w schematach S i T są równe 
to możemy wykonać złączenie odpowiednich krotek ((a, 
b) zawsze można połączyć z (b, c) i otrzymać (a, b, c)).

 

 

Odzyskiwanie danych po 

Odzyskiwanie danych po 

dekompozycji 2

dekompozycji 2



Wykonalność odtworzenia krotek sprzed dekompozycji 
nie świadczy jeszcze o wiernym reprezentowaniu relacji 
R w powstałych schematach S i T



Weźmy krotki t=(a, b, c) i v=(d, b, e), rzutując u na S a 
v na T otrzymujemy:

–

u=(a, b)

–

w=(b, e)



Dokonując teraz złączenia otrzymamy krotkę x=(a, b, e)



Pytanie: czy x jest krotką fałszywą? (a, b, e) nie ma w 
schemacie R



Przypomnijmy  sobie jednak o zależności 

BC zachodzącej 

w R. Czyli jeśli dwie krotki są zgodne dla atrybutu b to są zgodne 
również dla atrybutu C. Krotki t i v są zgodne dla atrybutu b zatem 
muszą być zgodne dla atrybutu C czyli c=e. Zatem krotka (a, b, e) 
jest w zasadzie krotką (a, b, c).

 

 

Złączenie dwóch krotek ze zrzutowanych 

Złączenie dwóch krotek ze zrzutowanych 

relacji

relacji

t

x

u

w

v

rzutowanie

rzutowanie

złączenie

złączenie

A

C

B

 

 

3 postać normalna

3 postać normalna



Czasami okazuje się, że schemat relacji nie 

spełnia BCNF ale dekompozycji się nie 

przeprowadza



Nieznacznie tylko osłabiając wymagania 

BCNF otrzymujemy 3 postać normalną:



Relacja R jest w 3NF wtw. jeśli A

1

A

2

A

n

B jest 

zależnością nietrywialną to albo {A

1

, A

2

, ..., 

A

n

} jest nadkluczem albo B jest elementem 

pewnego klucza.



Jak widać różnica polega na dodaniu: „... albo 

B jest elementem pewnego klucza.”

 

 

Przykład

Przykład



Mamy relację Zamówienia o następujących 

atrybutach: tytuł (tytuł filmu), kino (nazwa kina, 

w którym film jest wyświetlany), miasto (siedziba 

kina)



Zależności funkcyjne:

–

kinomiasto

–

tytuł miasto  kino



Uwagi: zatem przyjmujemy, że w dwóch różnych 

miastach nie mogą istnieć kina o tej samej 

nazwie oraz ten sam film nie może być 

wyświetlany w dwóch kinach w tym samym 

mieście

 

 

Przykład, c.d.

Przykład, c.d.



Ustalenie klucza:

–

Żaden pojedynczy atrybut nie jest kluczem (nie 

określa funkcyjnie pozostałych atrybutów)

–

{tytuł, miasto} jest kluczem

–

{kino, tytuł} też jest kluczem (stosując zasadę 

rozszerzenia dla pierwszej zależności)

–

W relacji nie ma więcej kluczy,



Zależność kinomiasto narusza BCNF gdyż 

kino nie jest nadkluczem



Ale miasto jest elementem pewnego klucza 

zatem relacja jest w 3NF

 

 

Przykład, c.d.

Przykład, c.d.



Stosując dekompozycję musielibyśmy 
utworzyć dwa schematy: {kino, 
miasto} oraz {kino, tytuł}



W schemacie po dekompozycji 
spełniona będzie relacja kino 
miasto, ale po złączeniu nie będzie 

spełniona zależność tytuł miasto  

kino

 

 

Przykład, c.d.

Przykład, c.d.

Kino

Miasto

Multikino

Kraków

Kijów

Kraków

Kino

tytuł

Multikino

Shrek

Kijów

Shrek

Kino

Miasto

Tytuł

Multikino

Kraków

Shrek

Kijów

Kraków

Shrek

Uwaga: po złączeniu nie jest spełniona zależność 

tytuł miasto  kino

 

 

2 postać normalna i 1 postać 

2 postać normalna i 1 postać 

normalna

normalna



1NF  każda składowa w każdej krotce ma 

wartość atomową (wszystkie współczesne 

SZBD uniemożliwiają tworzenie baz danych 

nie będących w 1NF)



2NF  mniej restrykcyjna niż 3NF, zabrania się 

wystąpienia takich zależności nietrywialnych, 

w których lewa strona jest poprawnym 

podzbiorem klucza. Dopuszczalne są w niej 

domknięcia przechodnie relacji.



2NF (inaczej)  każdy atrybut nie wchodzący w 

skład klucza jest funkcyjnie zależny od 

wszystkich kluczy potencjalnych relacji

 

 

2 postać normalna, 

2 postać normalna, 

formalnie

formalnie



Formalnie. Przypomnienie: atrybut główny – 
atrybut wchodzący w skład pewnego klucza.



Definicja. Pełna zależność funkcyjna – 
zależność funkcyjna A

1

A

2

A

n

B, w której 

usunięcie któregokolwiek atrybutu A

i

 

spowoduje, że zależność nie będzie spełniona



Relacja R jest w drugiej postaci normalnej 
wtedy gdy każdy atrybut niekluczowy jest 
wpełni funkcyjnie zależny od klucza tej relacji

 

 

Przykład

Przykład



Mamy dany schemat relacji R={S,T,D,K} (z 

interpretacją odpowiednio Sklep, Towar, Dział, 

Kierownik) 



Zależności:

–

STD (każdy towar w każdym sklepie sprzedaje się w jednym 

dziale)

–

DK (dział ma jednego kierownika)



Jedynym kluczem jest ST



Żaden podzbiór właściwy klucza nie wyznacza 

funkcyjnie ani D ani K, STK jest zależnością 

przechodnią, zależność STD narusza natomiast 3NF 

(D nie jest elementem klucza)



Relacja jest w 2NF

 

 

Zależności 

Zależności 

wielowartościowe

wielowartościowe



Występują gdy 2 lub więcej 
atrybutów jest od siebie 
niezależnych



Często pomimo, iż schemat spełnia 
BCNF występuje w nim 
redundancja, której źródlem jest 
właśnie niezależność dwóch lub 
więcej atrybutów

 

 

Przykład

Przykład

Nazwisko

Ulica

Miasto

Tytuł

Rok

C. Fisher

123 Maple 

St.

Hollywoo

d

Gwiezdne 

wojny

1977

C. Fisher

5 Locus 

Ln.

Malibu

Gwiezdne 

wojny

1977

C. Fisher

123 Maple 

St.

Hollywoo

d

Imperium 

kontratakuje

1980

C. Fisher

5 Locus 

Ln.

Malibu

Imperium 

kontratakuje

1980

C. Fisher

123 Maple 

St.

Hollywoo

d

Powrót Jedi

1983

C. Fisher

5 Locus 

Ln.

Malibu

Powrót Jedi

1983

 

 

Przykład, c.d.

Przykład, c.d.



Nie ma powodu by wiązać adres z jednym 

filmem a innym nie



Jedyny sposób na to by wyrazić iż adresy filmy są 

niezależnymi od siebie właściwościami gwiazdy 

polega na tym, że każdy adres w połączeniu z 

każdym filmem tworzą osobne krotki



Jak widać jest to źródłem redundancji (każdy 

adres powtarza się 3 razy, każdy film 2 razy)



Schemat jednak nie narusza BCNF (żaden z 5 

atrybutów nie zależy funkcyjnie od pozostałych 

4)

 

 

Zależności wielowartościowe - 

Zależności wielowartościowe - 

definicja

definicja



Zależność wielowartościowa zachodzi dla pewnej relacji R 
wówczas, gdy po ustaleniu wartości pewnego podzbioru atrybutów, 
wartości pewnych innych atrybutów są niezależne od wszystkich 
innych wartości wszystkich pozostałych atrybutów



Zależność wielowartościowa A

1

A

2

...A

n

→→ B

1

B

2

...B

m

 zachodzi w 

relacji R wówczas, gdy wybierając z R te krotki, które mają 
ustalone wartości atrybutów typu A, zbiór wartości typu B nie 
zależy od żadnych wartości tych atrybutów R, których nie ma ani w 
A ani w B



Dla każdej pary krotek t i u relacji R, które mają takie same 
wartości atrybutów typu A, można znaleźć w R taką krotkę v, której 
składowe mają wartości równe:

–

Wartościom atrybutów w A w krotkach t oraz u

–

Wartościom atrybutów B krotki t

–

Wartościom tych składowych krotki u, które nie są ani typu A, ani typu 
B



W poprzednim przykładzie opisano zależność:

–

nazwisko→→ ulica miasto

 

 

Zależności 

Zależności 

wielowartościowe - 

wielowartościowe - 

rysunek

rysunek

t

u

v

A

B

Inne

 

 

Przykład, c.d.

Przykład, c.d.



Wróćmy do zależności wielowartościowej:

–

nazwisko→→ ulica miasto



Weźmy pierwszą i czwartą krotkę naszej relacji:

–

t=(C.Fisher, 123 Maple St., Hollywood, Gwiezdne Wojny, 1977)

–

u=(C.Fisher, 5 Locus Ln., Malibu, Imperium kontratakuje, 

1980)



Na podstawie definicji w R musi istnieć krotka, 

która dla nazwiska ma wartość C. Fisher, dla 

ulicy i mieście ma wartości 123 Maple St. i 

Hollywood, a pozostałe atrybuty (czyli tytuł i 

rok) mają wartości takie jak w drugiej krotce 

(Imperium kontratakuje, 1980)



Taka krotka występuje w R (3 z kolei)

 

 

Wnioskowanie z zależności 

Wnioskowanie z zależności 

wielowartościowych

wielowartościowych



Stosuje się reguły, które są podobne do reguł poznanych wcześniej



Reguła zależności trywialnych: jeśli w R zachodzi zależność 

A

1

A

2

...A

n

→→B

1

B

2

...B

m

 to wówczas, gdy C

1

C

2

...C

k

 są wszystkimi 

atrybutami B oraz część z nich jest typu A to zachodzi również: 

A

1

A

2

...A

n

→→C

1

C

2

...C

k

 



Ponadto zachodzi również związek odwrotny: A

1

A

2

...A

n

→→D

1

D

2

...D

r

 

gdzie atrybuty typu D sa tymi atrybutami typu B, które nie są typu 

A



Reguła przechodniości: Jeśli w R zachodzą zależności 

A

1

A

2

...A

n

→→B

1

B

2

...B

m

 oraz B

1

B

2

...B

m

→→C

1

C

2

...C

k

 to zachodzi 

również A

1

A

2

...A

n

→→ C

1

C

2

...C

k



Reguła dopełnienia: Jeśli w R zachodzi A

1

A

2

...A

n

→→B

1

B

2

...B

m

 to 

zachodzi również A

1

A

2

...A

n

→→ C

1

C

2

...C

k

 gdzie atrybuty typu C są 

wszystkimi atrybutami, które nie są ani typu A ani B. (Reguła ta 

nie zachodzi dla zależności funkcyjnych)



Nie zachodzą natomiast reguły podziału i łączenia

 

 

Czwarta postać normalna

Czwarta postać normalna



Definicja. Zależność wielowartościową 
w relacji R: 

A

1

A

2

...A

n

→→B

1

B

2

...B

m

 nazywamy 

nietrywialną jeśli:

–

Żaden atrybut typu B nie jest typu A

–

Każdy atrybut R jest albo typu A, albo typu B



Relacja R jest w czwartej postaci 
normalnej (4NF) wtw. 
A

1

A

2

...A

n

→→B

1

B

2

...B

m

 jest nietrywialną 

zależnością wielowartościową; {A

1

, 

A

2

,

 

..., A

n

} jest nadkluczem w R

 

 

Dekompozycja do 4NF

Dekompozycja do 4NF



Algorytm stanowi pełną analogię do 

algorytmu dekompozycji do BCNF.



Znajdujemy zależność, która nie spełnia 

4NF, dla ustalenia uwagi niech to będzie: 

A

1

A

2

...A

n

→→B

1

B

2

...B

m

 ({A

1

, A

2

, ..., A

n

 nie jest 

nadkluczem)



Dzielimy schemat R na 2 schematy:

–

Pierwszy zawiera wszystkie atrybuty typu A i B

–

Drugi zawiera wszystkie atrybuty A i wszystkie 

te, które nie są ani typu A ani typu B

 

 

Przykład

Przykład



Wróćmy do przykładu i zależności naruszającej 

4NF:

–

nazwisko→→ ulica miasto (nazwisko nie stanowi nadklucza co 

wcześniej wykazaliśmy)



Zastępujemy zatem schemat R przez 2 schematy:

–

{nazwisko, ulica, miasto}

–

{nazwisko, tytuł, rok}



W żadnym z tych schematów nie ma nietrywialnych 

zależności wielowartościowych (ani funkcyjnych) 

zatem spełniają one 4NF



Spostrzeżenie: w pierwszym schemacie zależność 

nazwisko→→ ulica miasto jest trywialna ponieważ obejmuje 

wszystkie atrybuty, podobnie w drugim schemacie 

zależność nazwisko→→ tytuł rok  (wyprowadzona w R z 

pierwszej zależności na podstawie reguły dopełnienia) jest 

trywialna

 

 

Rzutowanie zależności 

Rzutowanie zależności 

funkcyjnych

funkcyjnych



Przed zastosowaniem dekompozycji do 

4NF należy określić wszystkie 

zależności wielowartościowe spełnione 

w relacjach wynikowych



Niestety nie ma prostego algorytmu 

takiego jak domknięcie zbioru w 

przypadku zależności funkcyjnych



Na szczęście można otrzymać właściwą 

zależność dla jednego z wynikowych 

schematów dekompozycji poprzez 

zastosowanie reguły przechodniości, 

dopełnienia lub przecięcia

 

 

Zależności pomiędzy 

Zależności pomiędzy 

postaciami normalnymi

postaciami normalnymi



Z postaci 4NF wynika postać 

BCNF a z tej z kolei postać 3NF.



Zatem zbiór instancji schematu 

relacyjnego spełniających 

poszczególne warunki postaci 

normalnych tworzy hierarchię



Przedstawione jest to na 

poniższym rysunku

 

 

Rysunek – zależności pomiędzy 

Rysunek – zależności pomiędzy 

postaciami normalnymi

postaciami normalnymi

2NF

3NF

BCNF

4NF

 

 

Właściwości postaci 

Właściwości postaci 

normalnych

normalnych

Właściwość

2NF

3NF

BCN

F

4NF

Eliminowanie 
redundancji przez 

zależności funkcyjne

Nie

Większo

ść

Tak

Tak

Eliminowanie 
redundancji przez 

zależności 
wielowartościowe

Nie

Nie

Nie

Tak

Zachowanie 
zależności 
funkcyjnych

Tak

Tak

Możliw

e

Możliw

e

Zachowanie 

zależności 
wielowartościowych

Możliw

e

Możliwe Możliw

e

Możliw

e

 

 

Piąta postać normalna

Piąta postać normalna



Definicja. W schemacie R występuje połączeniowa 
zależność funkcyjna (ozn. R*[R

1

, ..., R

n

]) wtw. gdy możliwa 

jest dekompozycja relacji R na relacje R

1

, ..., R

n

 taka, że 

relację R można zrekonstruować przez wykonanie 
sekwencji operacji połączenia  relacji R

1

, ..., R

n



Dana relacja R jest w piątej postaci normalnej wtw. gdy 
jest w czwartej postaci normalnej i w przypadku 
występowania w niej połączeniowej zależności 
funkcjonalnej *R[R

1

, ..., R

m

] zależność ta wynika z 

zależności atrybutów od klucza. 



Wynika z tego, że w celu doprowadzenia pewnej relacji do 
piątej postaci normalnej konieczne jest podzielenie jej na 
takie relacje, które spełniać będą podany wyżej warunek.