Нормальные формы более высоких порядков

Сентябрь 3, 2022

Главная
Алгебра
Нормальные формы более высоких порядков

Содержание

2. НФБК (Нормальная Форма Бойса-Кодда)
3. НФБК (Нормальная Форма Бойса-Кодда) Опр. Отношение R находится в нормальной форме Бойса-Кодда (НФБК) тогда и только
4. НФБК (Нормальная Форма Бойса-Кодда) Отношение "Поставки" не находится в НФБК, т.к. имеются зависимости (PNUM→PNAME и PNAME→PNUM),
5. НФБК (Нормальная Форма Бойса-Кодда)
6. НФБК (Нормальная Форма Бойса-Кодда) Пример. Предположим, что по-прежнему необходимо учитывать поставки, но каждый акт поставки должен
7. НФБК (Нормальная Форма Бойса-Кодда)
8. НФБК (Нормальная Форма Бойса-Кодда) Одним потенциальным ключом данного отношения является, как и раньше, пара атрибутов {PNUM,
9. НФБК (Нормальная Форма Бойса-Кодда) Зависимость атрибутов от второго ключа отношения: NN → PNUM, NN → DNUM,
10. 4НФ (Четвертая Нормальная Форма) Пусть требуется учитывать данные об абитуриентах, поступающих в ВУЗ. При анализе предметной
11. 4НФ (Четвертая Нормальная Форма)
12. 4НФ (Четвертая Нормальная Форма)
13. 4НФ (Четвертая Нормальная Форма) Опр. Пусть R- отношение, и X, Y, Z- некоторые из его атрибутов
14. 4НФ (Четвертая Нормальная Форма) Для каждого факультета (для каждого значения из X) каждый поступающий на него
15. 4НФ (Четвертая Нормальная Форма) Если в отношении R имеется не менее трех атрибутов X, Y, Z
16. 4НФ (Четвертая Нормальная Форма) Теорема (Фейджина). Пусть X, Y, Z- непересекающиеся множества атрибутов отношения R(X,Y,Z). Декомпозиция
17. 4НФ (Четвертая Нормальная Форма) Опр. Отношение находится в четвертой нормальной форме (4НФ) тогда и только тогда,
18. 5НФ (Пятая Нормальная Форма)
19. 5НФ (Пятая Нормальная Форма) Пусть R является отношением, а A, B, …, Z - произвольными (возможно
20. 5НФ (Пятая Нормальная Форма) Зависимость соединения *(A, B, …, Z) называется нетривиальной зависимостью соединения, если выполняется
21. 5НФ (Пятая Нормальная Форма) Опр. Отношение находится в пятой нормальной форме (5НФ) тогда и только тогда,
22. Алгоритм нормализации (приведение к 5НФ) Шаг 1 (Приведение к 1НФ). Шаг 2 (Приведение к 2НФ). Шаг
23. Алгоритм нормализации (приведение к 5НФ) Шаг 4 (Приведение к НФБК). Если имеются функциональные зависимости, то необходимо
25. Скачать презентацию

Слайд 2

НФБК (Нормальная Форма Бойса-Кодда)

Слайд 3

НФБК (Нормальная Форма Бойса-Кодда)
Опр. Отношение R находится в нормальной форме Бойса-Кодда

(НФБК) тогда и только тогда, когда детерминанты всех функциональных зависимостей являются потенциальными ключами.
Замечание. Если отношение находится в НФБК, то оно автоматически находится и в 3НФ.

Слайд 4

НФБК (Нормальная Форма Бойса-Кодда)
Отношение "Поставки" не находится в НФБК, т.к. имеются

зависимости (PNUM→PNAME и PNAME→PNUM), детерминанты которых не являются потенциальными ключами.
Для того чтобы устранить зависимость от детерминантов, не являющихся потенциальными ключами, необходимо провести декомпозицию, вынося эти детерминанты и зависимые от них части в отдельное отношение.

Слайд 5

НФБК (Нормальная Форма Бойса-Кодда)

Слайд 6

НФБК (Нормальная Форма Бойса-Кодда)
Пример. Предположим, что по-прежнему необходимо учитывать поставки, но

каждый акт поставки должен иметь некоторый уникальный номер ("сквозной номер поставки").

Слайд 7

НФБК (Нормальная Форма Бойса-Кодда)

Слайд 8

НФБК (Нормальная Форма Бойса-Кодда)
Одним потенциальным ключом данного отношения является, как и

раньше, пара атрибутов {PNUM, DNUM}. Другим ключом, в силу уникальности сквозного номера, является атрибут NN.
Зависимость атрибутов от первого ключа отношения:
{PNUM, DNUM} → VOLUME,
{PNUM, DNUM} → NN

Слайд 9

НФБК (Нормальная Форма Бойса-Кодда)
Зависимость атрибутов от второго ключа отношения:
NN →

PNUM,
NN → DNUM,
NN → VOLUME
Зависимости, являющиеся следствием зависимостей от ключей отношения:
{PNUM, DNUM} → {VOLUME, NN},
NN → {PNUM, DNUM},
NN → {PNUM, VOLUME},
NN → {DNUM, VOLUME},
NN → {PNUM, DNUM, VOLUME}.

Слайд 10

4НФ (Четвертая Нормальная Форма)
Пусть требуется учитывать данные об абитуриентах, поступающих в

ВУЗ. При анализе предметной области были выделены следующие требования:
Каждый абитуриент имеет право сдавать экзамены на несколько факультетов одновременно.
Каждый факультет имеет свой список сдаваемых предметов.
Один и тот же предмет может сдаваться на нескольких факультетах.
Абитуриент обязан сдавать все предметы, указанные для факультета, на который он поступает, несмотря на то, что он, может быть, уже сдавал такие же предметы на другом факультете.
Предположим, что нам требуется хранить данные о том, какие предметы должен сдавать каждый абитуриент.

Слайд 11

4НФ (Четвертая Нормальная Форма)

Слайд 12

4НФ (Четвертая Нормальная Форма)

Слайд 13

4НФ (Четвертая Нормальная Форма)
Опр. Пусть R- отношение, и X, Y, Z-

некоторые из его атрибутов (или непересекающиеся множества атрибутов). Тогда атрибуты (множества атрибутов) Y и Z многозначно зависят от (обозначается X→→Y|Z), тогда и только тогда, когда из того, что в отношении R содержатся кортежи r1={x,y,z} и r2={x,y,z} следует, что в отношении содержится также и кортеж r3={x,y,z}.

Слайд 14

4НФ (Четвертая Нормальная Форма)
Для каждого факультета (для каждого значения из X)

каждый поступающий на него абитуриент (значение из Y) сдает один и тот же список предметов (набор значений из Z), и для каждого факультета (для каждого значения из X) каждый сдаваемый на факультете экзамен (значение из Z) сдается одним и тем же списком абитуриентов (набор значений из Y). Именно наличие этой зависимости не позволяет независимо вставлять и удалять кортежи. Кортежи обязаны вставляться и удаляться одновременно целыми наборами.

Слайд 15

4НФ (Четвертая Нормальная Форма)
Если в отношении R имеется не менее трех

атрибутов X, Y, Z и есть функциональная зависимость X→Y, то есть и многозначная зависимость X→→Y|Z. Таким образом, понятие многозначной зависимости является обобщением понятия функциональной зависимости.
Опр. Многозначная зависимость X→→Y|Z называется нетривиальной многозначной зависимостью, если не существует функциональных зависимостей X→Y и X→Z.

Слайд 16

4НФ (Четвертая Нормальная Форма)
Теорема (Фейджина). Пусть X, Y, Z- непересекающиеся множества

атрибутов отношения R(X,Y,Z).
Декомпозиция отношения на проекции R1=R[X,Y] и R2=R[X,Z] будет декомпозицией без потерь тогда и только тогда, когда имеется многозначная зависимость X→→Y|Z.

Слайд 17

4НФ (Четвертая Нормальная Форма)
Опр. Отношение находится в четвертой нормальной форме (4НФ)

тогда и только тогда, когда отношение находится в НФБК и не содержит нетривиальных многозначных зависимостей.
Отношения с нетривиальными многозначными зависимостями возникают, как правило, в результате естественного соединения двух отношений по общему полю, которое не является ключевым ни в одном из отношений. Фактически это приводит к попытке хранить в одном отношении информацию о двух независимых сущностях.

Слайд 18

5НФ (Пятая Нормальная Форма)

Слайд 19

5НФ (Пятая Нормальная Форма)
Пусть R является отношением, а A, B, …,

Z - произвольными (возможно пересекающимися) подмножествами множества атрибутов отношения R. Тогда отношение R удовлетворяет зависимости соединения *(A, B, …, Z) тогда и только тогда, когда оно равносильно соединению всех своих проекций с подмножествами атрибутов A, B, …, Z, т.е.
R=R[A] Join R[B] Join … Join R[Z].
Можно предположить, что отношение в примере 3 удовлетворяет следующей зависимости соединения: *(XY, XZ, YZ).

Слайд 20

5НФ (Пятая Нормальная Форма)
Зависимость соединения *(A, B, …, Z) называется нетривиальной

зависимостью соединения, если выполняется два условия:
Одно из множеств атрибутов A, B, …, Z не содержит потенциального ключа отношения R.
Ни одно из множеств атрибутов A, B, …, Z не совпадает со всем множеством атрибутов отношения R.

Слайд 21

5НФ (Пятая Нормальная Форма)
Опр. Отношение находится в пятой нормальной форме (5НФ)

тогда и только тогда, когда любая имеющаяся зависимость соединения является тривиальной.
Возвращаясь к примеру 3, становится понятно, что не зная ничего о том, какие потенциальные ключи имеются в отношении и как взаимосвязаны атрибуты, нельзя делать выводы о том, находится ли данное отношение в 5НФ (как, впрочем, и в других нормальных формах). По данному конкретному примеру можно только предположить, что отношение в примере 3 не находится в 5НФ.

Слайд 22

Алгоритм нормализации (приведение к 5НФ)
Шаг 1 (Приведение к 1НФ).
Шаг

2 (Приведение к 2НФ).
Шаг 3 (Приведение к 3НФ).
Шаг 4 (Приведение к НФБК).
Шаг 5 (Приведение к 4НФ).
Шаг 6 (Приведение к 5НФ).

Слайд 23

Алгоритм нормализации (приведение к 5НФ)
Шаг 4 (Приведение к НФБК). Если имеются

функциональные зависимости, то необходимо провести дальнейшую декомпозицию отношений. Те атрибуты, которые зависят от детерминантов, не являющихся потенциальными ключами выносятся в отдельное отношение вместе с детерминантами.

Нормальные формы более высоких порядков

Содержание

НФБК (Нормальная Форма Бойса-Кодда)

НФБК (Нормальная Форма Бойса-Кодда)Опр. Отношение R находится в нормальной форме Бойса-Кодда

НФБК (Нормальная Форма Бойса-Кодда)Отношение "Поставки" не находится в НФБК, т.к. имеются

НФБК (Нормальная Форма Бойса-Кодда)

НФБК (Нормальная Форма Бойса-Кодда)Пример. Предположим, что по-прежнему необходимо учитывать поставки, но

НФБК (Нормальная Форма Бойса-Кодда)

НФБК (Нормальная Форма Бойса-Кодда)Одним потенциальным ключом данного отношения является, как и

НФБК (Нормальная Форма Бойса-Кодда)Зависимость атрибутов от второго ключа отношения: NN →

4НФ (Четвертая Нормальная Форма)Пусть требуется учитывать данные об абитуриентах, поступающих в

4НФ (Четвертая Нормальная Форма)

4НФ (Четвертая Нормальная Форма)

4НФ (Четвертая Нормальная Форма)Опр. Пусть R- отношение, и X, Y, Z-

4НФ (Четвертая Нормальная Форма)Для каждого факультета (для каждого значения из X)

4НФ (Четвертая Нормальная Форма)Если в отношении R имеется не менее трех

4НФ (Четвертая Нормальная Форма)Теорема (Фейджина). Пусть X, Y, Z- непересекающиеся множества

4НФ (Четвертая Нормальная Форма)Опр. Отношение находится в четвертой нормальной форме (4НФ)

5НФ (Пятая Нормальная Форма)

5НФ (Пятая Нормальная Форма)Пусть R является отношением, а A, B, …,

5НФ (Пятая Нормальная Форма)Зависимость соединения *(A, B, …, Z) называется нетривиальной

5НФ (Пятая Нормальная Форма)Опр. Отношение находится в пятой нормальной форме (5НФ)

Алгоритм нормализации (приведение к 5НФ) Шаг 1 (Приведение к 1НФ). Шаг

Алгоритм нормализации (приведение к 5НФ)Шаг 4 (Приведение к НФБК). Если имеются

Похожие презентации

НФБК (Нормальная Форма Бойса-Кодда)
Опр. Отношение R находится в нормальной форме Бойса-Кодда

НФБК (Нормальная Форма Бойса-Кодда)
Отношение "Поставки" не находится в НФБК, т.к. имеются

НФБК (Нормальная Форма Бойса-Кодда)
Пример. Предположим, что по-прежнему необходимо учитывать поставки, но

НФБК (Нормальная Форма Бойса-Кодда)
Одним потенциальным ключом данного отношения является, как и

НФБК (Нормальная Форма Бойса-Кодда)
Зависимость атрибутов от второго ключа отношения:
NN →

4НФ (Четвертая Нормальная Форма)
Пусть требуется учитывать данные об абитуриентах, поступающих в

4НФ (Четвертая Нормальная Форма)
Опр. Пусть R- отношение, и X, Y, Z-

4НФ (Четвертая Нормальная Форма)
Для каждого факультета (для каждого значения из X)

4НФ (Четвертая Нормальная Форма)
Если в отношении R имеется не менее трех

4НФ (Четвертая Нормальная Форма)
Теорема (Фейджина). Пусть X, Y, Z- непересекающиеся множества

4НФ (Четвертая Нормальная Форма)
Опр. Отношение находится в четвертой нормальной форме (4НФ)

5НФ (Пятая Нормальная Форма)
Пусть R является отношением, а A, B, …,

5НФ (Пятая Нормальная Форма)
Зависимость соединения *(A, B, …, Z) называется нетривиальной

5НФ (Пятая Нормальная Форма)
Опр. Отношение находится в пятой нормальной форме (5НФ)

Алгоритм нормализации (приведение к 5НФ)
Шаг 1 (Приведение к 1НФ).
Шаг

Алгоритм нормализации (приведение к 5НФ)
Шаг 4 (Приведение к НФБК). Если имеются