Bazy danych – relacyjny model danych

WYKŁAD 4

PROJEKTOWANIE RELACYJNYCH

SCHEMATÓW BAZ DANYCH

Bazy danych – relacyjny model danych

Anomalie –

problemy ze zbyt dużą liczbą danych w

pojedynczej relacji

redundacja –

dane niepotrzebnie powtarzają się w kilku

rekordach

anomalie modyfikacji –

podczas modyfikacji wartość danych

nie zostanie poprawiona we wszystkich krotkach

anomalie usunięć –

usunięcie wartości atrybutu może

spowodować utratę części danych (całej krotki)

Bazy danych – relacyjny model danych

Dekompozycja relacji –

podział atrybutów relacji R między

dwa schematy nowych relacji

Przykład

Szkoła (nazwa przedmiotu, imię, nazwisko, adres prowadzącego)
Krotka (j. Angielski, Lucyna, Nowak, ul. Cicha 8 Warszawa)

Adres składa się z kilku części

• Redundancja danych - jeden prowadzący może mieć zajęcia z kilku

przedmiotów

• Zmiana jednej z informacji o prowadzącym (np. adresu) powoduje

konieczność zmiany wszystkich krotek zawierających te dane w celu
zachowania integralności

• Nie jest możliwe wprowadzenie informacji o prowadzącym, który w danym

semestrze nie ma żadnych zajęć

• Usuniecie przedmiotu może spowodować również usuniecie wszelkich

informacji o prowadzącym.

• Utrzymanie integralności takiej bazy jest bardzo trudne.

Bazy danych – relacyjny model danych

Dekompozycja relacji –

podział atrybutów relacji R między

dwa schematy nowych relacji

Przykład

Szkoła (nazwa przedmiotu, imię, nazwisko, adres prowadzącego)
Krotka (j. Angielski, Lucyna, Nowak, ul. Cicha 8 Warszawa)

Dekompozycja relacji:

Szkoła na dwie relacje - Nauczyciel i Przedmiot

Nauczyciel (Id_prowadzącego , imię, nazwisko, kod pocztowy,

miejscowość, ulica)

Przedmiot (nazwa przedmiotu, Id_prowadzącego)

Klucz
podstawowy

Klucz obcy

Bazy danych – relacyjny model danych

Normalizacja –

proces przekształcania reprezentacji bazy

danych (nazywany również rozkładem odwracalnym),
polegający na odnajdywaniu logicznych związków między
elementami danych. W każdym etapie normalizacja bazy
strukturę danych dzieli się na coraz więcej tabel z
zachowaniem podstawowych związków między elementami
danych.

Denormalizacja –

wprowadzenie kontrolowanej

nadmiarowości do bazy danych w celu przyśpieszenia
wykonywania na niej operacji (np. obsługiwania zapytań)

Bazy danych – relacyjny model danych

Pierwsza postać normalna (1NF) –

relacja R jest w

pierwszej postaci normalnej, jeśli wartości atrybutów są
elementarne tzn. są to pojedyncze wartości określonego typu,
a nie zbiory wartości.

POWIATY

NrPowiatu

NazwaPowiatu

Miejscowości

Nowosolski

67-100 Nowa Sól, 67-120 Kożuchów, 67-160 Otyń

65-560 Zielona Góra, 65-250 Ochla

Zielonogórski

1

2

POWIATY

67-160

Kod3

Ochla

Kożuchów

M2

65-250

67-120

Kod2

Zielona

Góra

Nowa Sól

M1

65-560

67-100

Kod1

Otyń

M3

Zielonogórski

Nowosolski

NazwaPowiatu

2

1

NrPowiatu

Bazy danych – relacyjny model danych

Druga postać normalna (2NF)–

atrybuty nie wchodzące w skład klucza są zależne od całego
klucza (nie tylko od jego części)

każdy atrybut, który nie wchodzi w skład żadnego klucza
potencjalnego tej relacji jest w pełni funkcjonalnie zależny od
wszystkich kluczy potencjalnych tej relacji

Relacja będąca już w 2NF nie powinna zawierać redundancji

Bazy danych – relacyjny model danych

Przykład (2NF)

• I

- numer identyfikacyjny chorego,

• Im

- imię,

• N

- nazwisko,

• W

- wiek,

• Ods

- odział, •

S

- sala, •

L

- nazwa lekarstwa, •

D

- dawka lekarstwa.

KLUCZ

ANOMALIE:
anomalie dołączania –

chorzy nie otrzymujący lekarstw nie są

uwzględnieni w relacji

anomalie modyfikacji –

zmiana oddziału dla chorego (I = 1) wymaga

trzykrotnej aktualizacji danych

anomalie usunięć –

chory, który przestaje brać leki, jest usuwany z

bazy

Bazy danych – relacyjny model danych

Przykład (2NF)

• I

- numer identyfikacyjny chorego,

• Im

- imię,

• N

- nazwisko,

• W

- wiek,

• Ods

- odział, •

S

- sala, •

L

- nazwa lekarstwa, •

D

- dawka lekarstwa.

KLUCZ

Przyczyny występowania anomalii:

niektóre atrybuty (D) są funkcyjnie zależne od całego klucza IL, inne
natomiast (Im, N, W, Ods, S) zależne są tylko od części tego klucza
(w tym przypadku od I).
W schemacie relacyjnym istnieje niepełna zależność funkcyjna
atrybutów od klucza – niespełniony warunek 2NF

Bazy danych – relacyjny model danych

Przykład (2NF)

• I

- numer identyfikacyjny chorego,

• Im

- imię,

• N

- nazwisko,

• W

- wiek,

• Ods

- odział, •

S

- sala, •

L

- nazwa lekarstwa, •

D

- dawka lekarstwa.

KLUCZ

2 NF

Bazy danych – relacyjny model danych

Druga postać normalna (2NF)–

• schemat jest już w 2NF, jeśli każdy jego klucz jest jednoelementowy;

• przeprowadzanie schematu relacyjnego do 2NF nie jest procesem

jednoznacznym (dla jednego schematu relacyjnego może istnieć wiele
równoważnych informacyjnie układów projekcji tego schematu w 2NF)

PRZED NORMALIZACJĄ

PO NORMALIZACJI DO 2NF

Bazy danych – relacyjny model danych

Postać normalna Boyce’a – Codda

Relacja R jest w postaci BCNF wtedy i tylko wtedy, gdy dla
każdej nietrywialnej zależności A

1

, A

2

, ...., A

n

->B zbiór { A

1

, A2,

...., A

n

} jest nadkluczem R.

Oznacza to, że lewa strona każdej zależności nietrywialnej musi być
nadkluczem.

Bazy danych – relacyjny model danych

Postać normalna Boyce’a – Codda

Przykład – czy przedstawiona relacja Film jest w postaci BCNF

Klucz - tytuł rok nazwiskoGwiazdy

Tytuł

Rok

Dług
ość

Typ filmu Nazwa Studia Nazwisko

Gwiazdy

Gwiezdne
wojny

1997 124 Kolor

Fox

Carrie

Fischer

Gwiezdne
wojny

1997 124 Kolor

Fox

Mark

Hamill

Gwiezdne
wojny

1997 124 Kolor

Fox

Harrison

Ford

Potężne
Kaczory

1991 104 Kolor

Disney

Emilio

Estevez

Swiat
Wayne’a

1992 95 Kolor

Paramount

Dana

Carvey

Swiat
Wayne’a

1992 95 Kolor

Paramount

Mike

Meyers

tytuł rok Æ długość typFilmu nazwaStudia

Przedstawiona zależność jest zależnością funkcyjną, ale lewa strona
nie jest nadkluczem

Bazy danych – relacyjny model danych

Postać normalna Boyce’a – Codda

Przykład – dekompozycja relacji Film

Tytuł

Rok

Dług
ość

Typ filmu Nazwa Studia

Gwiezdne
wojny

1997 124 Kolor

Fox

Potężne
Kaczory

1991 104 Kolor

Disney

Swiat
Wayne’a

1992 95 Kolor

Paramount

Zależność:
tytuł rok Æ długość typFilmu nazwaStudia zachodzi dla relacji Film1

Rok, tytuł – samoistnie nie wyznaczają jednoznacznie pozostałych atrybutów
Jedyna nietrywialna zależność funkcyjna musi mieć z lewej strony co najmniej
tytuł i rok – lewe strony zależności muszą być nadkluczem
Relacja Film1 jest w postaci BCNF

Tytuł

Rok

Nazwisko Gwiazdy

Gwiezdne
wojny

1997 Carrie

Fischer

Gwiezdne
wojny

1997 Mark

Hamill

Gwiezdne
wojny

1997 Harrison

Ford

Potężne
Kaczory

1991 Emilio

Estevez

Swiat
Wayne’a

1992 Dana

Carvey

Swiat
Wayne’a

1992 Mike

Meyers

Bazy danych – relacyjny model danych

Dekompozycja do postaci BCNF

Powtarzany dostatecznie długo proces dekompozycji prowadzi
do zapisania każdej relacji w postaci kolekcji podzbiorów
atrybutów spełniających warunki:
- podzbiory są schematami relacji w postaci BCNF
- dane z pierwotnej relacji są wiernie reprezentowane w
relacjach powstałych w wyniku dekompozycji. Powinna być
możliwość dokładnego odtworzenia relacji pierwotnej.

Bazy danych – relacyjny model danych

Problemy z odzyskiwaniem danych po dekompozycji

Przykład

Problemy występują najczęściej wtedy, jeżeli podczas dekompozycji
nie są stosowane zależności funkcyjne

i B Æ C

A B C
1 2 3
4 2 5

A B
1 2
4 2

B C
2 3
2 5

A B

C

1 2

3

1 2

5

4 2

3

4 2

5

Bazy danych – relacyjny model danych

Trzecia postać normalna

Relacja R jest w trzeciej postaci normalnej wtedy i tylko wtedy,
gdy jest spełniony warunek:
Jeśli A

1

, A

2

, ...., A

n

->B jest zależnością nietrywialną to albo

{A

1

, A2, ...., A

n

} jest nadkluczem,

albo B jest elementem

pewnego klucza.

Bazy danych – relacyjny model danych

Trzecia postać normalna

Trzecia postać normalna wymaga, aby wszystkie kolumny nie
należące do klucza, zależały funkcyjnie od klucza
kandydującego.
Klucz kandydujący spełnia te same warunki co klucz główny i
charakteryzuje się tym, że:
- żadne dwa rekordy w tabeli nie mogą mieć tej samej
kombinacji wartości;
- z klucza kandydującego nie można wyodrębnić podgrupy
kolumn również zapewniających unikatowość danego rekordu.

W tej postaci normalnej nie są wymagane zależności pomiędzy
kolumnami poza kluczem

Bazy danych – relacyjny model danych

Trzecia postać normalna

Przykład
Relacja: Zamówienia(tytuł, kino, miasto)

Zależności funkcyjne:
kino Æ miasto
tytuł miasto Æ kino

Określamy klucze:
Żaden pojedynczy atrybut nie jest kluczem
(tytuł, miasto)
(kino, tytuł)
(miasto, kino)

–

nie jest kluczem, bo tytuł nie zależy funkcyjnie od miasta

i kina (np. kino z wieloma salami)

Zależność funkcyjna:
kino Æ miasto – naruszenie warunku BCNF

(kino nie jest nadkluczem)

Bazy danych – relacyjny model danych

Trzecia postać normalna

Przykład
Relacja: Zamówienia(tytuł, kino, miasto)
Próba dekompozycji do relacji (kino, miasto); (kino, tytuł)

kino miasto
Wisła Warszawa
Polonia Warszawa

kino tytuł
Wisła W

sieci

Polonia W

sieci

kino miasto

tytuł

Wisła Warszawa W

sieci

Polonia Warszawa W

sieci

Zależność tytuł miasto

Æ

kino

nie jest spełniona

Bazy danych – relacyjny model danych

Trzecia postać normalna

Relacja R jest w trzeciej postaci normalnej wtedy i tylko wtedy,
gdy jest spełniony warunek:
Jeśli A

1

, A

2

, ...., A

n

->B jest zależnością nietrywialną to albo

{A

1

, A2, ...., A

n

} jest nadkluczem,

albo B jest elementem

pewnego klucza.

Zależność:

kino Æ miasto

miasto jest elementem klucza

Relacja spełnia warunki 3NF(PN)

Bazy danych – relacyjny model danych

Przykład 2 (3NF)

WYK

nazwa firmy realizującej projekt,

ADRES

adres firmy,

PROJ

nazwa projektu,

DATA

data ukończenia projektu.

KLUCZ

Atrybuty zależne od
klucza – 2NF

ANOMALIE:
anomalie dołączania –

braku możliwości wpisania projektu do tabeli

dopóki nie zostanie określony przynajmniej jeden wykonawca

anomalie modyfikacji –

zmiana terminu realizacji projektu wymaga

poprawy w wielu miejscach

anomalie usunięć –

przerwanie realizacji projektu powoduje utratę

informacji na temat firm

Bazy danych – relacyjny model danych

Przykład 2 (3NF)

WYK

nazwa firmy realizującej projekt,

ADRES

adres firmy,

PROJ

nazwa projektu,

DATA

data ukończenia projektu.

KLUCZ

Atrybuty zależne od
klucza – 2NF

PO NORMALIZACJI DO 3NF

Atrybuty w 3PN powinny
być zależne od klucza,
całego klucza i tylko od
klucza relacji

Bazy danych – relacyjny model danych

Jak rozpoznać poszczególne postaci relacji ?

•

Relacja jest w 1NF - pierwszej postaci normalnej, jeżeli jej przypadek
(tabela) spełnia założenia tabeli relacyjnej.

•

W przypadku gdy klucz relacji jest jednoelementowy i tabela jest w 1NF, to
jest ona również w drugiej postaci normalnej (nie tylko klucz
jednoelementowy zapewnia własność 2NF !!!!!).

•

Przyczyną anomalii w pierwszej postaci normalnej jest niepełna zależność
atrybutów od klucza, co oznacza, że są atrybuty, zależne od całego klucza,
ale istnieją również atrybuty zależne od jego części.

•

Zjawiska niekorzystne, które mogą wystąpić w drugiej postaci normalnej i
powodować anomalie, to zależność pomiędzy atrybutami nie wchodzącymi
w skład klucza.

•

Rozwiązaniem tych wszystkich problemów jest projektowanie tabel w
trzeciej postaci normalnej w 3NF.

Bazy danych – relacyjny model danych

Wady normalizacji

• wydłużenie czasu wyszukiwania

• „nie należy przechowywać w bazie danych wartości, które

można wyliczyć”

stawka zasadnicza * liczba lat / 100

(stawka zasadnicza + dodatek za szkodliwość) * liczba lat / 100

Bazy danych – relacyjny model danych

Zależność wielowartościowa

A

1

, A

2

, ...., A

n

->->B

1

B

2

...B

m

zachodzi w relacji R jeżeli:
dla krotek o ustalonych wartościach atrybutów typu A, zbiór
wartości atrybutów typu B nie zależy od żadnych wartości tych
atrybutów z relacji R, których nie ma ani w zbiorze atrybutów
typu A, ani w zbiorze atrybutów typu B

Zależności wielowartościowe występują wówczas, gdy

istnieją dwa takie zbiory atrybutów relacji, których

wartości występują w relacji we wszystkich możliwych

kombinacjach

Bazy danych – relacyjny model danych

nazwisko

ulica

miasto

tytuł

rok

C. Fisher

123 Maple St.

Hollywood

Gwiezdne
wojny

1977

C. Fisher

5 Locus Ln.

Malibu

Gwiezdne
wojny

1977

C. Fisher

123 Maple St.

Hollywood

Imperium
kontratakuje

1980

C. Fisher

5 Locus Ln.

Malibu

Imperium
kontratakuje

1980

C. Fisher

123 Maple St.

Hollywood

Powrót Jedi

1983

C. Fisher

5 Locus Ln.

Malibu

Powrót Jedi

1983

klucz relacji Film

Zależność wielowartościowa:

nazwisko Æ Æ ulica miasto

Bazy danych – relacyjny model danych

Reguła zależności trywialnych

jeżeli w relacji zachodzi zależność: A

1

, A

2

, ...., A

n

->->B

1

B

2

...B

m

to jeżeli C

1

C

2

...C

k

są wszystkimi atrybutami typu B,oraz część

z nich jest typu A zachodzi również:

A

1

, A

2

, ...., A

n

->->C

1

C

2

...C

k

Bazy danych – relacyjny model danych

Reguła przechodniości

jeżeli w relacji zachodzą zależności:

A

1

, A

2

, ...., A

n

->->B

1

B

2

...B

m

B

1

B

2

...B

m

->->C

1

C

2

...C

k

to zachodzi również zależność

A

1

, A

2

, ...., A

n

->->C

1

C

2

...C

k

Bazy danych – relacyjny model danych

Reguły podziału i łączenia

nazwisko Æ Æ ulica miasto

nazwisko Æ Æ ulica ????

nazwisko

ulica

miasto

tytuł

rok

C. Fisher

123 Maple St.

Hollywood

Gwiezdne
wojny

1977

C. Fisher

5 Locus Ln.

Malibu

Gwiezdne
wojny

1977

Zależności wielowartościowe nie spełniają reguły podziału

i reguły łączenia

!!!!!!!!!

Bazy danych – relacyjny model danych

Reguła dopełnienia

jeżeli w relacji R zachodzą zależności:

A

1

, A

2

, ...., A

n

->->B

1

B

2

...B

m

to w relacji R zachodzi również

A

1

, A

2

, ...., A

n

->->C

1

C

2

...C

k

gdzie atrybuty typu C nie są atrybutami typu A ani typu B

Przykład

nazwisko Æ Æ ulica miasto

w wyniku reguły dopełnienia:

nazwisko Æ Æ tytuł rok

Bazy danych – relacyjny model danych

Czwarta postać normalna

Relacja R jest w czwartej postaci normalnej wtedy i tylko

wtedy, jeżeli

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 relacji R

Bazy danych – relacyjny model danych

Czwarta postać normalna

nazwisko

ulica

miasto

tytuł

rok

C. Fisher

123 Maple St.

Hollywood

Gwiezdne
wojny

1977

C. Fisher

5 Locus Ln.

Malibu

Gwiezdne
wojny

1977

C. Fisher

123 Maple St.

Hollywood

Imperium
kontratakuje

1980

C. Fisher

5 Locus Ln.

Malibu

Imperium
kontratakuje

1980

C. Fisher

123 Maple St.

Hollywood

Powrót Jedi

1983

C. Fisher

5 Locus Ln.

Malibu

Powrót Jedi

1983

Zależność wielowartościowa:

nazwisko Æ Æ ulica miasto

jest nietrywialna, jednak nazwisko nie stanowi nadklucza

(jedynym kluczem tej relacji są wszystkie atrybuty)

relacja nie jest w 4NF (4PN)

Bazy danych – relacyjny model danych

Dekompozycja do czwartej postaci normalnej

1. Znajdujemy zależność, która nie spełnia warunków 4NF
np.

A

1

, A

2

, ...., A

n

->->B

1

B

2

...B

m

,

gdzie {A

1

, A

2

, ...., A

n

} nie jest nadkluczem

2. Schemat relacji R, który nie spełnia warunku 4NF dzielimy
na dwa schematy:
- pierwszy schemat zawiera atrybuty typu A i typu B
- drugi schemat zawiera wszystkie atrybuty typu A oraz te
wszystkie atrybuty z relacji R, które nie są ani typu A,
ani typu B

Bazy danych – relacyjny model danych

Dekompozycja do czwartej postaci normalnej - przykład

naruszenie warunku 4NF powoduje zależność:

nazwisko Æ Æ ulica miasto

schemat relacji

{nazwisko, ulica, miasto, tytuł, rok}

zastępujemy schematami:

{nazwisko, ulica, miasto}
{nazwisko, tytuł, rok}

Bazy danych – relacyjny model danych

Zależności między postaciami normalnymi

3NF

BCNF

4NF

2NF