Нормалізація. Нормальна форма Бойса-Кодда

1. Нормалізація

Лекція 15
Нормалізація
18.03.2018
ОБД - весна 2017
1

2.

Нормалізація
SC
S
S#
S1
S2
S3
S4
S5
S#
S1
S2
S3
S4
S5
SNAME STATUS
CITY
Smith
20 London
Jones
10 Paris
Blake
30 Paris
Clark
20 London
Adams
30 Athens
SP
S#
S1
S1
S2
S2
S3
S4
S5
S6
P#
P1
P2
P1
P2
P2
P2
P4
P5
SCP
QTY
100
100
200
200
300
400
500
600
18.03.2018
SNAME STATUS
Smith
20
Jones
10
Blake
30
Clark
20
Adams
30
S#
S1
S1
S2
S2
S3
S4
S5
S6
ОБД - весна 2017
CITY P#
London P1
London P2
Paris
P1
Paris
P2
Paris
P2
London P2
London P4
London P5
QTY
100
100
200
200
300
400
500
600
3

3. Нормалізація

Нормалізація – формальний метод
аналізу відношень на основі їх
потенційних ключів та існуючих
функціональних залежностей.
Нормалізація - послідовне зведення
заданого набору змінних відношень
до деякої більш бажаної форми.
18.03.2018
ОБД - весна 2017
4

4. Нормалізація

Нормальні форми
Перша нормальна форма
Друга нормальна форма
Третя нормальна форма
Нормальна форма Бойса-Кодда
Четверта нормальна форма
П'ята нормальна форма
18.03.2018
ОБД - весна 2017
5

5. Нормальні форми

Нормальні форм
1НФ
2НФ
3НФ
НФБК
4НФ
5НФ
18.03.2018
ОБД - весна 2017
6

6. Нормальні форм

Перша нормальна форма
S
SNAME
Smith
Ned Flanders
18.03.2018
S
PHONES
555-0121
555-2804
555-8904
SNAME
PHONES
Smith
555-0121
Smith
555-2804
Ned Flanders
555-8904
ОБД - весна 2017
7

7. Перша нормальна форма

SC
SC
S#
S1
S2
S3
S4
S5
SNAME
Smith
Jones
Blake
Clark
Adams
18.03.2018
COLORS
Red, Blue, Green, Brown
Fuchsia, Yellow
Black, Lime, Blue
Gray, Brown
Olive, Silver, Red, Gold
ОБД - весна 2017
S#
S1
S1
S1
S1
S2
S2
S3
S3
S3
S4
S4
S5
S5
S5
S5
SNAME COLORS
Smith
Red
Smith
Blue
Smith
Green
Smith
Brown
Jones
Fuchsia
Jones
Yellow
Blake
Black
Blake
Lime
Blake
Blue
Clark
Gray
Clark
Brown
Adams
Olive
Adams
Silver
Adams
Red
Adams
Gold
8

8. Перша нормальна форма

Змінна відношення знаходиться у
1НФ тоді і тільки тоді, коли в будьякому допустимому значенні цієї
змінної відношення кожний її
кортеж містить тільки одне
значення для кожного з атрибутів.
18.03.2018
ОБД - весна 2017
9

9. Перша нормальна форма

Декомпозиція без втрат
S
S#
S3
S5
STATUS
CITY
30 Paris
30 Athens
SST
а)
S#
S3
S4
SC
STATUS
30
30
S#
CITY
S3
Paris
S5
Athens
SST
б)
S#
S3
S4
18.03.2018
STC
STATUS
30
30
STATUS
CITY
30
Paris
30
Athens
ОБД - весна 2017
10

10. Декомпозиція без втрат

S
S#
S3
S5
STATUS
CITY
30 Paris
30 Athens
S# → STATUS
S# → CITY
SST
а)
S#
S3
S4
STATUS
30
30
SC
S# → STATUS
SST
б)
S#
S3
S4
18.03.2018
STATUS
30
30
S# → CITY
S#
CITY
S3
Paris
S5
Athens
STC
S# → STATUS
ОБД - весна 2017
STATUS
CITY
30
Paris
30
Athens
11

11. Декомпозиція без втрат

Теорема Хіта
Нехай R{А, B, С} є змінною
відношенням, де А, B і C — множини
атрибутів цієї змінної відношення.
Якщо R задовольняє функціональній
залежності А→B, то R дорівнює
з'єднанню її проекцій по атрибутам
{А,В} і {А,С}.
Декомпозиція змінної відношення R на
проекції R1, R2, ..., Rn виконується без
втрат, якщо R дорівнює з'єднанню R1,
R2, ..., Rn.
18.03.2018
ОБД - весна 2017
12

12. Теорема Хіта

Діаграми функціональних
залежностей
18.03.2018
ОБД - весна 2017
13

13. Діаграми функціональних залежностей

Перша нормальна форма
FIRST
S#
S1
S1
S1
S1
S1
S1
S2
S2
S3
S4
S4
S4
18.03.2018
CITY
London
London
London
London
London
London
Paris
Paris
Paris
London
London
London
STATUS
20
20
20
20
20
20
10
10
10
20
20
20
P#
P1
P2
P3
P4
P5
P6
P1
P2
P2
P2
P4
P5
ОБД - весна 2017
QTY
300
200
400
200
100
100
300
400
200
200
300
400
14

14. Перша нормальна форма

18.03.2018
ОБД - весна 2017
15

15. Перша нормальна форма

Аномалії оновлення
Операція INSERT. Не можна помістить в змінну
відношення FIRST інформацію про те, що деякий
постачальник знаходиться в певному місті, до тих
пір поки цей постачальник не здійснить поставку
хоча б одної деталі.
Операція DELETE. Якщо із змінної відношення
FIRST видалити кортеж, який є єдиним для деякого
постачальника, буде видалена не тільки інформація
про поставку постачальником деякої деталі, але
також інформація про те, що цей постачальник
знаходиться в певному місті.
Операція UPDATE. У загальному, назва міста для
кожного постачальника повторюється в змінній
відношенні FIRST декілька разів, і ця збитковість
призводить до виникнення проблем при оновленні.
18.03.2018
ОБД - весна 2017
16

16. Аномалії оновлення

Перша нормальна форма
18.03.2018
ОБД - весна 2017
17

17. Перша нормальна форма

Друга нормальна форма
SECOND
S#
S1
S2
S3
S4
S4
S5
18.03.2018
CITY
London
Paris
Paris
London
London
Athens
SP
STATUS
20
10
10
20
20
30
S#
S1
S1
S1
S1
S1
S1
S2
S2
S3
S4
S4
S4
ОБД - весна 2017
P#
P1
P2
P3
P4
P5
P6
P1
P2
P2
P2
P4
P5
QTY
300
200
400
200
100
100
300
400
200
200
300
400
18

18. Друга нормальна форма

18.03.2018
ОБД - весна 2017
19

19. Друга нормальна форма

Операція INSERT. Інформацію про те, що
постачальник з номером S5 знаходиться в Афінах,
можна помістити в базу даних, додавши відповідний
кортеж в змінну відношення SECOND, причому
навіть в тому випадку, якщо він на даний момент не
постачає жодної деталі.
Операція DELETE. Тепер цілком можливо видалити
інформацію про поставку деталі з номером Р2
постачальником з номером S3.
Операція UPDATE. У вдосконаленій структурі назва
міста для кожного постачальника вказується всього
один раз, оскільки існує тільки один кортеж для
даного постачальника в змінній відношенні
SECOND.
18.03.2018
ОБД - весна 2017
20

20. Друга нормальна форма

Змінна відношення знаходиться в
другій нормальній формі тоді й
тільки тоді, коли вона перебуває в
першій нормальній формі й кожний
неключовий атрибут незвідно
залежить від її первинного ключа.
18.03.2018
ОБД - весна 2017
21

21. Друга нормальна форма

Перший етап процедури нормалізації полягає у створенні
проекцій, які дозволяють виключи функціональні
залежності, що не є незвідні.
Нехай дана змінна відносини R, що має наступний вид.
Процедура нормалізації передбачає заміну цієї змінної
відношення наступними двома проекціями, R1 і R2.
R {А, В, С, D} PRIMARY KEY {А, В} /* А → D */
R1 {A, D} PRIMARY KEY {A}
R2 {А, В, С} PRIMARY KEY {А, В} FOREIGN KEY {A} REFERENCES R1
Змінна відношення R завжди може бути відновлена за
допомогою з'єднання змінних відношень R1 і R2 по
зовнішньому ключу й відповідному йому первинному
ключу цих змінних відношень.
18.03.2018
ОБД - весна 2017
22

22. Друга нормальна форма

Третя нормальна форма
SECOND
S#
S1
S2
S3
S4
S4
S5
18.03.2018
CITY
London
Paris
Paris
London
London
Athens
STATUS
20
10
10
20
20
30
ОБД - весна 2017
23

23. Третя нормальна форма

Аномалії оновлення
Операція INSERT. Не можна помістити в базу
даних відомості про те, що певне місто
характеризується деяким статусом, доти, поки в
цьому місті не з'явиться певний постачальник.
Операція DELETE. При видаленні зі змінної
відношення SECOND кортежу для деякого міста,
представленого в ній цим єдиним кортежем, будуть
вилучені не тільки відомості про постачальника з
даного міста, але й інформація про те, який статус
відповідає самому місту.
Операція UPDATE. У змінній відношенні SECOND
значення статусу для кожного міста повторюється
кілька раз (тому вона усе ще має деяку
надмірністю).
18.03.2018
ОБД - весна 2017
24

24. Аномалії оновлення

Третя нормальна форма
18.03.2018
ОБД - весна 2017
25

25. Третя нормальна форма

SC
S#
S1
S2
S3
S4
S5
18.03.2018
СS
CITY
London
Paris
Paris
London
Athens
CITY
London
Paris
Athens
Rome
ОБД - весна 2017
STATUS
20
10
30
50
26

26. Третя нормальна форма

Змінна відношення знаходиться в
третій нормальній формі тоді й
тільки тоді, коли вона перебуває в
другій нормальній формі й жоден
неключовий атрибут не є
транзитивно залежним від її
первинного ключа.
18.03.2018
ОБД - весна 2017
27

27. Третя нормальна форма

Другий етап нормалізації полягає в створенні проекцій
для усунення транзитивних залежностей.
Нехай дана змінна відношення R, що має наступний вид.
Процедура нормалізації передбачає заміну змінної
відносини R наступними двома проекціями, R1 і R2.
R { А, В, С } PRIMARY KEY { A } /* В → C */
R1 { В, С } PRIMARY KEY { В }
R2 { А, В } PRIMARY KEY { A } FOREIGN KEY { В } REFERENCES R1
Змінна відношення R може бути відновлена за допомогою
з'єднання змінних відношень R1 і R2 по зовнішньому
ключу й відповідному йому первинному ключу цих
змінних відношень.
18.03.2018
ОБД - весна 2017
28

28. Третя нормальна форма

Рівень нормалізації змінної відношення
визначається семантикою, а не конкретним
значенням цієї змінної в певний момент часу.
Інакше кажучи, за конкретним значенням деякої
змінної відносини неможливо визначити, чи
перебуває вона, наприклад, у ЗНФ.
Для цього необхідно також знати, які
функціональні залежності визначені в
розглянутій змінній відношенні.
Навіть знаючи про залежності в деякій змінній
відношенні, не можна на підставі конкретного її
значення довести, що вона перебуває в ЗНФ.
18.03.2018
ОБД - весна 2017
29

29. Третя нормальна форма

Збереження залежностей
18.03.2018
ОБД - весна 2017
30

30. Збереження залежностей

SC
S#
S1
S2
S3
S4
S5
СS
CITY
London
Paris
Paris
London
Athens
CITY
London
Paris
Athens
Rome
SC
S#
S1
S2
S3
S4
S5
STATUS
20
10
30
50
СS
S#
S1
S2
S3
S4
S5
CITY
London
Paris
Paris
London
Athens
18.03.2018
ОБД - весна 2017
STATUS
20
10
10
20
30
31

31. Збереження залежностей

Концепція незалежних проекцій надає критерій
вибору одного з можливих варіантів
декомпозиції.
Проекції R1 і R2 змінної відношення R будуть
незалежні тоді й тільки тоді, коли
дотримуються наступні вимоги:
кожна функціональна залежність у змінній
відношенні R є логічним наслідком функціональних
залежностей у її проекціях R1 і R2;
загальні атрибути проекцій R1 і R2 утворюють
потенційний ключ принаймні для однієї із цих двох
проекцій.
18.03.2018
ОБД - весна 2017
32

32. Збереження залежностей

Нормальна форма Бойса-Кодда
Змінна відношення знаходиться в
нормальній форм Бойса-Кодда тоді
й тільки тоді, коли кожна її
нетривіальна й незвідна зліва
функціональна залежність, має в
якості детермінанта потенційний
ключ.
18.03.2018
ОБД - весна 2017
33

33. Нормальна форма Бойса-Кодда

S
S#
S1
S2
S3
S4
S5
18.03.2018
SNAME STATUS
CITY
Smith
20 London
Jones
10 Paris
Blake
30 Paris
Clark
20 London
Adams
30 Athens
ОБД - весна 2017
34

34. Нормальна форма Бойса-Кодда

SSP
S#
S1
S1
S1
S1
S1
S1
S2
S2
S3
S4
S4
S4
SNAME
Smith
Smith
Smith
Smith
Smith
Smith
Jones
Jones
Blake
Clark
Clark
Clark
P#
P1
P2
P3
P4
P5
P6
P1
P2
P2
P2
P4
P5
QTY
300
200
400
200
100
100
300
400
200
200
300
400
{S#, P#} і {SNAME, P#} – потенційні ключі SSP
18.03.2018
ОБД - весна 2017
35

35. Нормальна форма Бойса-Кодда

SS
S#
S1
S2
S3
S4
18.03.2018
SP
SNAME
Smith
Jones
Blake
Clark
S#
S1
S1
S1
S1
S1
S1
S2
S2
S3
S4
S4
S4
ОБД - весна 2017
P#
P1
P2
P3
P4
P5
P6
P1
P2
P2
P2
P4
P5
QTY
300
200
400
200
100
100
300
400
200
200
300
400
36

36. Нормальна форма Бойса-Кодда

SS
S#
S1
S2
S3
S4
18.03.2018
SP
SNAME
Smith
Jones
Blake
Clark
SNAME
Smith
Smith
Smith
Smith
Smith
Smith
Jones
Jones
Blake
Clark
Clark
Clark
ОБД - весна 2017
P#
P1
P2
P3
P4
P5
P6
P1
P2
P2
P2
P4
P5
QTY
300
200
400
200
100
100
300
400
200
200
300
400
37

37. Нормальна форма Бойса-Кодда

S – студент
T – викладач
J – предмет
18.03.2018
Кожний студент вивчає певний предмет
тільки в одного викладача.
Кожний викладач веде тільки один
предмет, але кожний предмет ведуть
декілька викладачів.
ОБД - весна 2017
38

38. Нормальна форма Бойса-Кодда

STJ
S
Smith
Smith
Jones
Jones
J
Math
Physics
Math
Physics
T
Prof. White
Prof. Green
Prof. White
Prof. Brown
S – студент
T – викладач
J – предмет
Кожний студент вивчає певний предмет
тільки в одного викладача.
Кожний викладач веде тільки один
предмет, але кожний предмет ведуть
декілька викладачів.
{ S, J } → { T }
{T}→{J}
18.03.2018
ОБД - весна 2017
39

39. Нормальна форма Бойса-Кодда

ST
S
Smith
Smith
Jones
Jones
TJ
T
Prof. White
Prof. Green
Prof. White
Prof. Brown
T
J
Prof. White Math
Prof. Green Physics
Prof. Brown Physics
{T}→{J}
{ S, J } → { T } ?
18.03.2018
ОБД - весна 2017
40

40. Нормальна форма Бойса-Кодда

Дано змінну відношення EXAM з атрибутами S
(студент), J (предмет) і Р (позиція).
Кожний кортеж (s, j, р) змінної відношення
EXAM відображає відомості про те, що деякий
студент s екзаменується по певному предмету j
і займає певну позицію р в екзаменаційній
відомості.
Крім того, ніякі два студенти не можуть
займати ту саму позицію в екзаменаційній
відомості, яка відноситься до того самого
предмету.
18.03.2018
ОБД - весна 2017
41

41. Нормальна форма Бойса-Кодда

EXAM {S, J, P}
18.03.2018
ОБД - весна 2017
42

42. Нормальна форма Бойса-Кодда

Змінна відношення знаходиться в
нормальній форм Бойса-Кодда тоді
й тільки тоді, коли кожна її
нетривіальна й незвідна зліва
функціональна залежність, має в
якості детермінанта потенційний
ключ.
18.03.2018
ОБД - весна 2017
43