ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 07.11.2023
Просмотров: 408
Скачиваний: 6
ВНИМАНИЕ! Если данный файл нарушает Ваши авторские права, то обязательно сообщите нам.
F1. Рефлексивность. Х → Х.
F2. Пополнение. Х → Y влечет за собой XZ → Y.
F3. Аддитивность. X → У и X → Z влечет за собой X → YZ.
F4. Проективность. X → YZ влечет за собой X → Y.
F5. Транзитивность. Х → Y и Y → Z влечет за собой X → Z.
F6. Псевдотранзитивность. X → Y и YZ → W влечет за собой XZ → W.
Некоторые аксиомы вывода могут быть получены из других. Например, транзитивность F5 является частным случаем псевдотранзитивности F6 при Z =
∅
Приведенная система аксиом F1-F6 является полной. Это означает, что каждая F-зависимость, которая следует из множества F, может быть выведена путем одно- или многократного применения к F
этих аксиом.
Из аксиом F1, F2 и F6 можно вывести остальные, а значит, они образуют полное подмножество для
F1-F6. Аксиомы F1, F2 и F6 являются также независимыми: ни одна из этих аксиом не может быть получена из двух других. Иногда эти три аксиомы называются аксиомами Армстронга.
Пусть F – множество F-зависимостей для отношения r(R). Замыкание F, обозначаемое F
+
, – это наименьшее содержащее F множество, такое, что при применении к нему аксиом Армстронга нельзя получить ни одной F-зависимости, не принадлежащей F. Так как F
+
должно быть конечно, то можно вычислить его, начиная с F путем применения F1, F2 и F6 и добавления полученных F-зависимостей к
F до тех пор, пока не перестанут получаться новые зависимости. Замыкание F зависит от схемы R.
Из множества F можно вывести F-зависимость X → Y, если X → Y принадлежит F
+
. Так как аксиомы вывода порождают только функциональные зависимости, то F влечет за собой X → Y, если X → Y
выводится из F.
Пример 2.5. Пусть F = {AB → C, С → В} - множество F-зависимостей на r(АВС).
Тогда:
В свете новых знаний об F-зависимостях, следует уточнить понятия ключа и суперключа.
Для данной схемы отношения R ключ - это подмножество К
⊆
R, такое, что для любого допустимого отношения r(R) не существует двух различных кортежей t
1
и t
2
в r, таких, что r
1
К) = t
2
(К), и никакое собственное подмножество K'
⊂
K не обладает этим свойством.
Для некоторых допустимых отношений со схемой R подмножество К' может быть ключом, но
57
Сотрудники
НОМЕР
ФИО
23
Вербов Александр Владимирович
24
Фисенко Александр Сергеевич
25
Фатхи Дмитрий Владимирович
Если понадобится указать только фамилии сотрудников, то указанное отношение не находится в
1НФ, так как требуемые значения являются частью атрибута ФИО. Чтобы отношение в таких условиях находилось в 1НФ, атрибут ФИО должен быть разбит на части, как показано ниже.
Сотрудники
НОМЕР
ФАМИЛИЯ
ИМЯ
ОТЧЕСТВО
23
Вербов
Александр
Владимирович
24
Фисенко
Александр
Сергеевич
25
Фатхи
Дмитрий
Владимирович
Пример 2.7. Отношение Род, представленное ниже, не находится в первой нормальной форме потому, что оно включает величины, являющиеся совокупностью атомарных значений.
Род
ИМЯ
ПОЛ
Иван, Александр, Сергей мужской
Мария, Ирина женский
Чтобы отношение Род находилось в 1НФ, оно должно быть представлено следующим образом.
Род
ИМЯ
ПОЛ
Иван мужской
Александр мужской
Сергей мужской
Мария женский
Ирина женский
В чем преимущество применения 1НФ? В том, что 1НФ позволяет выражать F-зависимости с той степенью детализации, с какой требует приложение, что невозможно без 1НФ.
Но и 1НФ обладает рядом существенных недостатков [2, 7, 10]. На первых этапах проектирования базы данных, после анализа предметной области и определения состава информации для хранения в БД обычно формируется так называемое универсальное отношение.
Универсальное отношение – одна таблица, находящаяся в 1НФ, в которой может храниться вся
информация об интересующей предметной области. Другими словами схему этого отношения образует весь перечень интересующих атрибутов предметной области [5].
При использовании универсального отношения возникают следующие проблемы [5, 10].
1. Избыточность. Данные многих столбцов многократно повторяются. Повторяются и некоторые наборы данных.
2. Аномалии обновления:
а) аномалии добавления;
б) аномалии изменения;
в) аномалии удаления.
Аномалии обновления являются нежелательным побочным эффектом, обусловленным избыточностью хранимых данных при внесении изменений в отношение.
Рассмотрим отношение График.
График
РЕЙС
ДАТА
ПИЛОТ
ГАЛЕРЕЯ
112 6 июня
Иванов
7 112 7 июня
Петров
7 203 9 июня
Иванов
12
Атрибуты РЕЙС ДАТА являются ключом отношения График, и это отношение должно также
59
2.4.3.5. Третья нормальная форма
Рассмотрим другое отношение График, представленное ниже. Предположим, что это отношение имеет ключ РЕЙС ДЕНЬ и к тому же удовлетворяет функциональным зависимостям КОД-ПИЛОТА →
ИМЯ и ИМЯ → КОД-ПИЛОТА.
Если выполнить операцию обновления
ИЗМЕНИТЬ (График; 112, б июня,
КОД-ПИЛОТА=31039, ИМЯ=Иванов),
то изменяется функциональная зависимость ИМЯ → КОД-ПИЛОТА. Кроме того, имеется избыточная информация в виде пар КОД-ПИЛОТА, ИМЯ.
Проблема здесь не из-за частичной зависимости непервичного атрибута, хотя решение получается то же самое.
Это отношение можно представить в виде базы данных следующим образом.
Пилот-График
РЕЙС
ДАТА
КОД-ПИЛОТА
112 6 июня
31174 112 7 июня
30046 203 9 июня
31174
Код
КОД-ПИЛОТА
ИМЯ
31174
Иванов
30046
Петров
Возможность восстановления первоначального отношения сохраняется.
Перед определением третьей нормальной формы характеризуется транзитивная зависимость атрибутов.
Для данной схемы отношения R, подмножества X множества R, атрибута А в R и множества функциональных зависимостей F атрибут А называется транзитивно зависимым от X в R, если существует подмножество Y
⊆
R, такое, что X → Y, Y не определяет функционально X, Y → А
относительно F и А
∉
ХY [10].
Пример 2.10. Пусть R(РЕЙС, ДАТА, КОД-ПИЛОТА, ИМЯ) и множество F={PEHC ДАТА →
КОД-ПИЛОТА ИМЯ, КОД-ПИЛОТА → ИМЯ, ИМЯ → КОД-ПИЛОТА}.
Атрибут ИМЯ является транзитивно зависимым от РЕЙС ДАТА, так как РЕЙС ДАТА
®
КОД-
ПИЛОТА, КОД-ПИЛОТА не определяет функционально РЕЙС ДАТА и КОД-ПИЛОТА
®
ИМЯ.
Схема отношения R находится в третьей нормальной форме (ЗНФ) относительно множества функциональных зависимостей F, если она находится в 1НФ и ни один из непервичных атрибутов в R
не является транзитивно зависимым от ключа для R [10].
Схема базы данных R находится в третьей нормальной форме относительно F, если каждая схема отношения R в R находится в ЗНФ относительно F.
Пример 2.11. Пусть R и множество F те же, что и в примере 2.10, R=(R).
Схема базы данных R не находится в ЗНФ относительно F, потому что ИМЯ является транзитивно зависимым от РЕЙС ДАТА.
Если R={(PEHC, ДАТА, КОД-ПИЛОТА); (КОД-ПИЛОТА, ИМЯ)}, то R находится в ЗНФ относительно F.
Следует заметить, что любая схема отношения, находящаяся в ЗНФ относительно F, находится в
2НФ относительно F [10].
2.4.3.6. Нормализация через декомпозицию
Всегда можно начать с того, что, взяв некоторую схему отношения R, не находящуюся в ЗНФ
61
К
2
={ВРЕМЯ-ОТПРАВЛЕНИЯ ДЛИТЕЛЬНОСТЬ-ПОЛЕТА}.
Схема R
2
находится в ЗНФ, а схема R
1
– нет, так как I-КЛАСС, II-КЛАСС и КОЛИЧЕСТВО-
ПОСАДОЧНЫХ-МЕСТ транзитивно зависят от РЕЙСА через ТИП-САМОЛЕТА. Схема R
1 разлагается на схему
R
11
(РЕЙС, ПУНКТ-ОТПРАВЛЕНИЯ, ПУНКТ-НАЗНАЧЕНИЯ, ВРЕМЯ-ВЫЛЕТА, ВРЕМЯ-
ПРИБЫТИЯ, ДЛИТЕЛЬНОСТЬ-ПОЛЕТА, ТИП-САМОЛЕТА)
с выделенными ключами
К
11
={РЕЙС, ПУНКТ-ОТПРАВЛЕНИЯ ПУНКТ-НАЗНАЧЕНИЯ ВРЕМЯ-ВЫЛЕТА, ПУНКТ-
ОТПРАВЛЕНИЯ ПУНКТ-НАЗНАЧЕНИЯ ВРЕМЯ-ПРИБЫТИЯ}
и схему
R
12
(ТИП-САМОЛЕТА, I-КЛАСС, II-КЛАСС, КОЛИЧЕ-СТВО-ПОСАДОЧНЫХ-МЕСТ)
с выделенным ключом
К
12
={ТИП-САМОЛЕТА}.
Схема отношения R
11
находится теперь в ЗНФ относительно F, a R
12
– нет, поскольку
КОЛИЧЕСТВО-ПОСАДОЧНЫХ-МЕСТ транзитивно зависит от ТИПА-САМОЛЕТА через I-
КЛАСС II-КЛАСС. Схема R
12
разлагается на
R
121
(ТИПА-САМОЛЕТА, I-КЛАСС, II-КЛАСС) с выделенным ключом
К
121
={ТИП-САМОЛЕТА}. и схему отношения
R
122
(I-КЛАСС, II-КЛАСС, КОЛИЧЕСТВО-ПОСАДОЧНЫХ-МЕСТ)
с выделенным ключом
К
122
={I-КЛАСС II-КЛАСС}.
Декомпозиция R реализована до такой стадии, когда каждая схема отношения находится в ЗНФ относительно F. Следовательно, схема базы данных находится в ЗНФ.
Схема базы данных R не однозначна. Есть точки, в которых можно выбирать пути декомпозиции определенного отношения с целью удаления транзитивно зависимого атрибута.
Так, на первом шаге можно было выбрать
R
2
(ВРЕМЯ-ПРИБЫТИЯ, ДЛИТЕЛЬНОСТЬ-ПОЛЕТА, ПИТАНИЕ),
так как ПИТАНИЕ также транзитивно зависит от РЕЙСА через ВРЕМЯ-ПРИБЫТИЯ
ДЛИТЕЛЬНОСТЬ-ПОЛЕТА. На третьем шаге существует три варианта декомпозиции R
12
(Какие?
) Некоторые ключи для схем отношений не указаны как выделенные, например I-КЛАСС
63
КОЛИЧЕСТВО-ПОСАДОЧНЫХ-МЕСТ и II-КЛАСС КОЛИЧЕСТВО-ПОСАДОЧНЫХ-МЕСТ для
R
122
2.4.3.7. Недостатки нормализации посредством декомпозиции
При нормализации схемы отношения посредством декомпозиции возникает ряд проблем.
Во-первых, временная сложность процесса не ограничивается полиномиальной [10]. В терминах размера схемы отношения и заданного множества F-зависимостей схема отношения может обладать экспоненциальным числом ключей. Кроме того, проверка атрибута схемы на непервичность является
NP-полной задачей.
Во-вторых, число порожденных процессом схем отношения может оказаться большим, чем в действительности необходимо для ЗНФ.
Пример 2.13. Пусть заданы схема R(A, В, С, D, Е) и F={AB→CDE, AC→BDE, B→C, С→В,
C→D, В→Е}. Ключами R относительно F являются АВ и АС. Используя транзитивную зависимость D от АВ через С, разлагаем R следующим образом:
Далее в R
1
используем транзитивную зависимость Е от АВ через B для получения
Окончательная схема базы данных в ЗНФ имеет вид
Существует декомпозиция R в ЗНФ с двумя схемами отношений, а именно:
Третья проблема состоит в том, что при декомпозиции схемы отношения могут возникнуть частичные зависимости. Эти зависимости могут породить в окончательной схеме базы данных больше схем, чем это в действительности необходимо.
Пример 2.14. Для схемы отношения R(A, В, С, D) и F={A→BCD, С→D}. атрибут А является единственным ключом в R относительно F. Атрибут D транзитивно зависит от А через ВС.
Разлагая, получаем
Фактическим ключом R
2
является ВС, но D от него частично зависит. Следовательно, D
транзитивно зависит от ВС. Схему R
2
следует разложить в
Схемы R
1
, R
21
и D
22
образуют схему базы данных в ЗНФ для R. Однако схемы отношений R
1
и
R
22
также образуют схему базы данных в ЗНФ для R.
Этих недостатков можно избежать, если при декомпозиции следить за тем, чтобы промежуточное множество атрибутов в разлагаемой транзитивной зависимости было минимальным. В примере 2.14 атрибут D транзитивно зависел через ВС от А, но ВС не
64
F2. Пополнение. Х → Y влечет за собой XZ → Y.
F3. Аддитивность. X → У и X → Z влечет за собой X → YZ.
F4. Проективность. X → YZ влечет за собой X → Y.
F5. Транзитивность. Х → Y и Y → Z влечет за собой X → Z.
F6. Псевдотранзитивность. X → Y и YZ → W влечет за собой XZ → W.
Некоторые аксиомы вывода могут быть получены из других. Например, транзитивность F5 является частным случаем псевдотранзитивности F6 при Z =
∅
Приведенная система аксиом F1-F6 является полной. Это означает, что каждая F-зависимость, которая следует из множества F, может быть выведена путем одно- или многократного применения к F
этих аксиом.
Из аксиом F1, F2 и F6 можно вывести остальные, а значит, они образуют полное подмножество для
F1-F6. Аксиомы F1, F2 и F6 являются также независимыми: ни одна из этих аксиом не может быть получена из двух других. Иногда эти три аксиомы называются аксиомами Армстронга.
Пусть F – множество F-зависимостей для отношения r(R). Замыкание F, обозначаемое F
+
, – это наименьшее содержащее F множество, такое, что при применении к нему аксиом Армстронга нельзя получить ни одной F-зависимости, не принадлежащей F. Так как F
+
должно быть конечно, то можно вычислить его, начиная с F путем применения F1, F2 и F6 и добавления полученных F-зависимостей к
F до тех пор, пока не перестанут получаться новые зависимости. Замыкание F зависит от схемы R.
Из множества F можно вывести F-зависимость X → Y, если X → Y принадлежит F
+
. Так как аксиомы вывода порождают только функциональные зависимости, то F влечет за собой X → Y, если X → Y
выводится из F.
Пример 2.5. Пусть F = {AB → C, С → В} - множество F-зависимостей на r(АВС).
Тогда:
В свете новых знаний об F-зависимостях, следует уточнить понятия ключа и суперключа.
Для данной схемы отношения R ключ - это подмножество К
⊆
R, такое, что для любого допустимого отношения r(R) не существует двух различных кортежей t
1
и t
2
в r, таких, что r
1
К) = t
2
(К), и никакое собственное подмножество K'
⊂
K не обладает этим свойством.
Для некоторых допустимых отношений со схемой R подмножество К' может быть ключом, но
57
рассматриваются все допустимые отношения со схемой R.
Суперключ – это любая совокупность атрибутов, содержащая ключ.
Нормализация - формальный метод анализа отношений на основе их первичного ключа (или потенциальных ключей) и существующих функциональных зависимостей [2, 7, 10].
Цель нормализации – получение такого проекта базы данных, в котором каждый факт хранится в
одном месте, т.е. исключена избыточность информации. Это делается не столько с целью экономии памяти, сколько для исключения возможной противоречивости хранимых данных из-за их избыточности.
Нормальная форма представляет собой ограничение на схему базы данных (отношения), которое избавляет базу данных от некоторых нежелательных свойств.
Нормализация чаще всего выполняется в несколько последовательных этапов, результатом каждого из которых является некоторая нормальная форма с известными свойствами.
В теории реляционных баз данных разработано несколько нормальных форм (НФ), которые подчиняются правилу вложенности (рис. 2.25).
Рис. 2.25. Вложенность нормальных форм
Смысл вложенности нормальных форм в следующем: каждая нормальная форма является в некотором смысле более ограниченной, но и более желательной, чем предшествующая [17]. Это связано с тем, что (N + 1)-я нормальная форма не обладает некоторыми недостатками, свойственным N-й нормальной форме. Общий смысл дополнительного условия, налагаемого на (N + 1)-ю нормальную форму по отношению к N-йнормальной форме, состоит в исключении этих недостатков.
При реализации реляционной БД важно понимать, что только удовлетворение требований первой нормальной формы (1НФ) обязательно для создания отношений приемлемого качества. Все остальные формы могут использоваться по желанию проектировщика. Однако чтобы избежать аномалий обновления, описываемых ниже, нормализацию рекомендуется проводить как минимум до ЗНФ.
2.4.3.3. Первая нормальная форма
Схема отношения R находится в первой нормальной форме (1НФ), если значения в домене D(A)
являются атомарными для каждого атрибута А в JR. Другими словами, значения в домене не являются ни списками, ни множествами простых или сложных значений [10].
Схема базы данных R находится в первой нормальной форме, если каждая схема отношения в R находится в 1НФ.
Определить понятие атомарности трудно: значение атомарное в одном приложении, может быть неатомарным в другом. Можно руководствоваться общим принципом, что значение неатомарно, если в приложении оно используется по частям.
Пример 2.6. Имеется отношение Сотрудники:
58
Суперключ – это любая совокупность атрибутов, содержащая ключ.
Нормализация - формальный метод анализа отношений на основе их первичного ключа (или потенциальных ключей) и существующих функциональных зависимостей [2, 7, 10].
Цель нормализации – получение такого проекта базы данных, в котором каждый факт хранится в
одном месте, т.е. исключена избыточность информации. Это делается не столько с целью экономии памяти, сколько для исключения возможной противоречивости хранимых данных из-за их избыточности.
Нормальная форма представляет собой ограничение на схему базы данных (отношения), которое избавляет базу данных от некоторых нежелательных свойств.
Нормализация чаще всего выполняется в несколько последовательных этапов, результатом каждого из которых является некоторая нормальная форма с известными свойствами.
В теории реляционных баз данных разработано несколько нормальных форм (НФ), которые подчиняются правилу вложенности (рис. 2.25).
Рис. 2.25. Вложенность нормальных форм
Смысл вложенности нормальных форм в следующем: каждая нормальная форма является в некотором смысле более ограниченной, но и более желательной, чем предшествующая [17]. Это связано с тем, что (N + 1)-я нормальная форма не обладает некоторыми недостатками, свойственным N-й нормальной форме. Общий смысл дополнительного условия, налагаемого на (N + 1)-ю нормальную форму по отношению к N-йнормальной форме, состоит в исключении этих недостатков.
При реализации реляционной БД важно понимать, что только удовлетворение требований первой нормальной формы (1НФ) обязательно для создания отношений приемлемого качества. Все остальные формы могут использоваться по желанию проектировщика. Однако чтобы избежать аномалий обновления, описываемых ниже, нормализацию рекомендуется проводить как минимум до ЗНФ.
2.4.3.3. Первая нормальная форма
Схема отношения R находится в первой нормальной форме (1НФ), если значения в домене D(A)
являются атомарными для каждого атрибута А в JR. Другими словами, значения в домене не являются ни списками, ни множествами простых или сложных значений [10].
Схема базы данных R находится в первой нормальной форме, если каждая схема отношения в R находится в 1НФ.
Определить понятие атомарности трудно: значение атомарное в одном приложении, может быть неатомарным в другом. Можно руководствоваться общим принципом, что значение неатомарно, если в приложении оно используется по частям.
Пример 2.6. Имеется отношение Сотрудники:
58
Сотрудники
НОМЕР
ФИО
23
Вербов Александр Владимирович
24
Фисенко Александр Сергеевич
25
Фатхи Дмитрий Владимирович
Если понадобится указать только фамилии сотрудников, то указанное отношение не находится в
1НФ, так как требуемые значения являются частью атрибута ФИО. Чтобы отношение в таких условиях находилось в 1НФ, атрибут ФИО должен быть разбит на части, как показано ниже.
Сотрудники
НОМЕР
ФАМИЛИЯ
ИМЯ
ОТЧЕСТВО
23
Вербов
Александр
Владимирович
24
Фисенко
Александр
Сергеевич
25
Фатхи
Дмитрий
Владимирович
Пример 2.7. Отношение Род, представленное ниже, не находится в первой нормальной форме потому, что оно включает величины, являющиеся совокупностью атомарных значений.
Род
ИМЯ
ПОЛ
Иван, Александр, Сергей мужской
Мария, Ирина женский
Чтобы отношение Род находилось в 1НФ, оно должно быть представлено следующим образом.
Род
ИМЯ
ПОЛ
Иван мужской
Александр мужской
Сергей мужской
Мария женский
Ирина женский
В чем преимущество применения 1НФ? В том, что 1НФ позволяет выражать F-зависимости с той степенью детализации, с какой требует приложение, что невозможно без 1НФ.
Но и 1НФ обладает рядом существенных недостатков [2, 7, 10]. На первых этапах проектирования базы данных, после анализа предметной области и определения состава информации для хранения в БД обычно формируется так называемое универсальное отношение.
Универсальное отношение – одна таблица, находящаяся в 1НФ, в которой может храниться вся
информация об интересующей предметной области. Другими словами схему этого отношения образует весь перечень интересующих атрибутов предметной области [5].
При использовании универсального отношения возникают следующие проблемы [5, 10].
1. Избыточность. Данные многих столбцов многократно повторяются. Повторяются и некоторые наборы данных.
2. Аномалии обновления:
а) аномалии добавления;
б) аномалии изменения;
в) аномалии удаления.
Аномалии обновления являются нежелательным побочным эффектом, обусловленным избыточностью хранимых данных при внесении изменений в отношение.
Рассмотрим отношение График.
График
РЕЙС
ДАТА
ПИЛОТ
ГАЛЕРЕЯ
112 6 июня
Иванов
7 112 7 июня
Петров
7 203 9 июня
Иванов
12
Атрибуты РЕЙС ДАТА являются ключом отношения График, и это отношение должно также
59
удовлетворять F-зависимости РЕЙС→ГАЛЕРЕЯ. Пусть требуется обновить отношение, указав значение ключа и задавая значения всем остальным атрибутам. Однако если выполнить операцию
ИЗМЕНИТЬ (График; 112, 6 июня, ПИЛОТ=Иванов, ГАЛЕРЕЯ=8),
то отношение перестанет удовлетворять F-зависимости РЕЙС→ГАЛЕРЕЯ. Чтобы избежать нарушения F-зависимости, необходимо после каждого выполнения операции обновления просмотреть полученное отношение и везде (во всех кортежах), где появляется указанный в операторе номер рейса, изменить номер галереи на указанный в операторе. А требовалось всего лишь изменить один кортеж.
Кроме того, информация о связи между номером рейса и номером галереи дублируется с рассмотренном отношении, что ведет к избыточности информации.
С точки зрения как обновления, так и устранения избыточности лучше представить ту же информацию в виде базы данных из двух отношений Пилот-График и Галерея-График.
Пилот-График
РЕЙС
ДАТА
ПИЛОТ
112 6 июня
Иванов
112 7 июня
Петров
203 9 июня
Иванов
Галерея-График
РЕЙС
ГАЛЕРЕЯ
112 7
203 12
При этом сохраняется возможность восстановить первоначальное отношение График из двух новых отношений (см. гл.4). Указанной аномалии обновления больше не существует, так как нужно изменить только один кортеж, чтобы поменять назначение галереи. При этом устраняется и некоторая избыточность данных, так как каждая пара (номер рейса, номер галереи) записывается только однажды.
2.4.3.4. Вторая нормальная форма
Для данной схемы отношения R, атрибута А в Л и множества функциональных зависимостей F на R
атрибут А называется первичным в R относительно F, если А содержится в каком-нибудь ключе схемы
R. В противном случае А называется непервичным в R.
Ключи в этом определении не следует путать с выделенными ключами для R, так как последние могут быть на самом деле суперключами. Кроме того, могут существовать ключи для R, не являющиеся выделенными.
Пример 2.8. Пусть Д(РЕЙС, ДАТА, ПИЛОТ, ГАЛЕРЕЯ) и множество F={РЕЙСДАТА →
ПИЛОТ ГАЛЕРЕЯ, РЕЙС → ГАЛЕРЕЯ}.
Атрибуты РЕЙС и ДАТА являются первичными, ПИЛОТ и ГАЛЕРЕЯ - непервичными. (Допустимо, чтобы один пилот имел два рейса в день, так что ПИЛОТ ДАТА ключом не является.)
Схема отношения R находится во второй нормальной форме (2НФ) относительно множества функциональных зависимостей F, если она находится в первой нормальной форме (1НФ) и каждый непервичный атрибут полностью зависит от каждого ключа для R [10].
Схема базы данных R имеет вторую нормальную форму относительно F, если каждая схема отношения R из R находится в 2НФ относительно F.
Пример 2.9. Пусть R(РЕЙС, ДАТА, ПИЛОТ, ГАЛЕРЕЯ) и множество F={РЕЙС ДАТА →
ПИЛОТ ГАЛЕРЕЯ, РЕЙС → ГАЛЕРЕЯ}, R={R}.
Схема не находится в 2НФ, так как ГАЛЕРЕЯ частично зависит от РЕЙС ДАТА. Если положить R={(PEHC, ДАТА, ПИЛОТ); (РЕЙС, ГАЛЕРЕЯ)}, тогда схема будет находиться во второй нормальной форме. РЕЙС теперь является ключом для схемы отношения (РЕЙС,
ГАЛЕРЕЯ).
60
ИЗМЕНИТЬ (График; 112, 6 июня, ПИЛОТ=Иванов, ГАЛЕРЕЯ=8),
то отношение перестанет удовлетворять F-зависимости РЕЙС→ГАЛЕРЕЯ. Чтобы избежать нарушения F-зависимости, необходимо после каждого выполнения операции обновления просмотреть полученное отношение и везде (во всех кортежах), где появляется указанный в операторе номер рейса, изменить номер галереи на указанный в операторе. А требовалось всего лишь изменить один кортеж.
Кроме того, информация о связи между номером рейса и номером галереи дублируется с рассмотренном отношении, что ведет к избыточности информации.
С точки зрения как обновления, так и устранения избыточности лучше представить ту же информацию в виде базы данных из двух отношений Пилот-График и Галерея-График.
Пилот-График
РЕЙС
ДАТА
ПИЛОТ
112 6 июня
Иванов
112 7 июня
Петров
203 9 июня
Иванов
Галерея-График
РЕЙС
ГАЛЕРЕЯ
112 7
203 12
При этом сохраняется возможность восстановить первоначальное отношение График из двух новых отношений (см. гл.4). Указанной аномалии обновления больше не существует, так как нужно изменить только один кортеж, чтобы поменять назначение галереи. При этом устраняется и некоторая избыточность данных, так как каждая пара (номер рейса, номер галереи) записывается только однажды.
2.4.3.4. Вторая нормальная форма
Для данной схемы отношения R, атрибута А в Л и множества функциональных зависимостей F на R
атрибут А называется первичным в R относительно F, если А содержится в каком-нибудь ключе схемы
R. В противном случае А называется непервичным в R.
Ключи в этом определении не следует путать с выделенными ключами для R, так как последние могут быть на самом деле суперключами. Кроме того, могут существовать ключи для R, не являющиеся выделенными.
Пример 2.8. Пусть Д(РЕЙС, ДАТА, ПИЛОТ, ГАЛЕРЕЯ) и множество F={РЕЙСДАТА →
ПИЛОТ ГАЛЕРЕЯ, РЕЙС → ГАЛЕРЕЯ}.
Атрибуты РЕЙС и ДАТА являются первичными, ПИЛОТ и ГАЛЕРЕЯ - непервичными. (Допустимо, чтобы один пилот имел два рейса в день, так что ПИЛОТ ДАТА ключом не является.)
Схема отношения R находится во второй нормальной форме (2НФ) относительно множества функциональных зависимостей F, если она находится в первой нормальной форме (1НФ) и каждый непервичный атрибут полностью зависит от каждого ключа для R [10].
Схема базы данных R имеет вторую нормальную форму относительно F, если каждая схема отношения R из R находится в 2НФ относительно F.
Пример 2.9. Пусть R(РЕЙС, ДАТА, ПИЛОТ, ГАЛЕРЕЯ) и множество F={РЕЙС ДАТА →
ПИЛОТ ГАЛЕРЕЯ, РЕЙС → ГАЛЕРЕЯ}, R={R}.
Схема не находится в 2НФ, так как ГАЛЕРЕЯ частично зависит от РЕЙС ДАТА. Если положить R={(PEHC, ДАТА, ПИЛОТ); (РЕЙС, ГАЛЕРЕЯ)}, тогда схема будет находиться во второй нормальной форме. РЕЙС теперь является ключом для схемы отношения (РЕЙС,
ГАЛЕРЕЯ).
60
2.4.3.5. Третья нормальная форма
Рассмотрим другое отношение График, представленное ниже. Предположим, что это отношение имеет ключ РЕЙС ДЕНЬ и к тому же удовлетворяет функциональным зависимостям КОД-ПИЛОТА →
ИМЯ и ИМЯ → КОД-ПИЛОТА.
Если выполнить операцию обновления
ИЗМЕНИТЬ (График; 112, б июня,
КОД-ПИЛОТА=31039, ИМЯ=Иванов),
то изменяется функциональная зависимость ИМЯ → КОД-ПИЛОТА. Кроме того, имеется избыточная информация в виде пар КОД-ПИЛОТА, ИМЯ.
Проблема здесь не из-за частичной зависимости непервичного атрибута, хотя решение получается то же самое.
Это отношение можно представить в виде базы данных следующим образом.
Пилот-График
РЕЙС
ДАТА
КОД-ПИЛОТА
112 6 июня
31174 112 7 июня
30046 203 9 июня
31174
Код
КОД-ПИЛОТА
ИМЯ
31174
Иванов
30046
Петров
Возможность восстановления первоначального отношения сохраняется.
Перед определением третьей нормальной формы характеризуется транзитивная зависимость атрибутов.
Для данной схемы отношения R, подмножества X множества R, атрибута А в R и множества функциональных зависимостей F атрибут А называется транзитивно зависимым от X в R, если существует подмножество Y
⊆
R, такое, что X → Y, Y не определяет функционально X, Y → А
относительно F и А
∉
ХY [10].
Пример 2.10. Пусть R(РЕЙС, ДАТА, КОД-ПИЛОТА, ИМЯ) и множество F={PEHC ДАТА →
КОД-ПИЛОТА ИМЯ, КОД-ПИЛОТА → ИМЯ, ИМЯ → КОД-ПИЛОТА}.
Атрибут ИМЯ является транзитивно зависимым от РЕЙС ДАТА, так как РЕЙС ДАТА
®
КОД-
ПИЛОТА, КОД-ПИЛОТА не определяет функционально РЕЙС ДАТА и КОД-ПИЛОТА
®
ИМЯ.
Схема отношения R находится в третьей нормальной форме (ЗНФ) относительно множества функциональных зависимостей F, если она находится в 1НФ и ни один из непервичных атрибутов в R
не является транзитивно зависимым от ключа для R [10].
Схема базы данных R находится в третьей нормальной форме относительно F, если каждая схема отношения R в R находится в ЗНФ относительно F.
Пример 2.11. Пусть R и множество F те же, что и в примере 2.10, R=(R).
Схема базы данных R не находится в ЗНФ относительно F, потому что ИМЯ является транзитивно зависимым от РЕЙС ДАТА.
Если R={(PEHC, ДАТА, КОД-ПИЛОТА); (КОД-ПИЛОТА, ИМЯ)}, то R находится в ЗНФ относительно F.
Следует заметить, что любая схема отношения, находящаяся в ЗНФ относительно F, находится в
2НФ относительно F [10].
2.4.3.6. Нормализация через декомпозицию
Всегда можно начать с того, что, взяв некоторую схему отношения R, не находящуюся в ЗНФ
61
относительно множества F-зависимостей F, разложить ее в схему базы данных, имеющую ЗНФ относительно F.
Разложение схемы отношений означает разбиение схемы отношения на пару схем отношений R
1
и R
2
(возможно, пересекающихся) так, чтобы любое отношение r(R), удовлетворяющее F, разлагалось без потерь на R
1
и R
2
. Возможно, нужно будет повторить процесс декомпозиции отношений R
1
и R
2
, если какое-нибудь из них не окажется в ЗНФ. Декомпозиция продолжается до тех пор, пока все полученные отношения не окажутся в третьей нормальной форме относительно F.
На самом деле процесс декомпозиции схемы не бесконечен. Каждый раз, когда разлагается схема отношения, обе получившиеся в результате схемы становятся меньше, а в схеме отношения, содержащей только два атрибута, не может быть никакой транзитивной зависимости [10].
Пример 2.12. Пусть
R (РЕЙС, ПУНКТ-ОТПРАВЛЕНИЯ, ПУНКТ-НАЗНАЧЕНИЯ, ВРЕМЯ-ВЫЛЕТА, ВРЕМЯ-
ПРИБЫТИЯ, ДЛИТЕЛЬНОСТЬ-ПОЛЕТА, ТИП-САМОЛЕТА, I-КЛАСС, II-КЛАСС,
КОЛИЧЕСТВО-ПОСАДОЧНЫХ-МЕСТ, ПИТАНИЕ)
где I-КЛАСС и II-КЛАСС – количество посадочных мест в каждом салоне. Пусть множество выделенных ключей
К={РЕЙС, ПУНКТ-ОТПРАВЛЕНИЯ ПУНКТ-НАЗНАЧЕНИЯ ВРЕМЯ-ВЫЛЕТА, ПУНКТ-
ОТПРАВЛЕНИЯ ПУНКТ-НАЗНАЧЕНИЯ ВРЕМЯ-ПРИБЫТИЯ}.
Предполагается, что в одно и то же время не может быть двух рейсов с одинаковыми пунктами отправления и назначения. Пусть все выделенные ключи действительно являются ключами, и пусть имеются также следующие F-зависимости в множестве F:
ТИП-САМОЛЕТА→I-КЛАСС II-КЛАСС КОЛИЧЕСТВО-ПОСАДОЧНЫХ-МЕСТ,
ВРЕМЯ-ВЫЛЕТА ДЛИТЕЛЬНОСТЬ-ПОЛЕТА→ПИТАНИЕ,
ВРЕМЯ-ПРИБЫТИЯ ДЛИТЕЛЬНОСТЬ-ПОЛЕТА→ПИТАНИЕ,
I-КЛАСС II-КЛАСС→КОЛИЧЕСТВО-ПОСАДОЧНЫХ-МЕСТ,
I-КЛАСС КОЛИЧЕСТВО-ПОСАДОЧНЫХ-МЕСТ→II-КЛАСС,
II-КЛАСС КОЛИЧЕСТВО-ПОСАДОЧНЫХ-МЕСТ→I-КЛАСС.
Казалось бы, ВРЕМЯ-ВЫЛЕТА ВРЕМЯ-ПРИБЫТИЯ→ДЛИТЕЛЬНОСТЬ-ПОЛЕТА также должна быть F-зависимостью, но, из-за того что время прибытия и время отправления указывается местное, ДЛИТЕЛЬНОСТЬ-ПОЛЕТА зависит от часовых поясов, к которым принадлежат соответствующие аэропорты.
Сначала удалим транзитивную зависимость атрибута ПИТАНИЕ от РЕЙСА через ВРЕМЯ-
ВЫЛЕТА ДЛИТЕЛЬНОСТЬ-ПОЛЕТА. Получим схему отношения
R
1
(РЕЙС, ПУНКТ-ОТПРАВЛЕНИЯ, ПУНКТ-НАЗНАЧЕНИЯ, ВРЕМЯ-ПРИБЫТИЯ,
ДЛИТЕЛЬНОСТЬ-ПОЛЕТА, ТИП-САМОЛЕТА, I-КЛАСС, II-КЛАСС, КОЛИЧЕСТВО-
ПОСАДОЧНЫХ-МЕСТ)
с выделенными ключами
K
1
={PEHC, ПУНКТ-ОТПРАВЛЕНИЯ ПУНКТ-НАЗНАЧЕНИЯ ВРЕМЯ-ВЫЛЕТА, ПУНКТ-
ОТПРАВЛЕНИЯ ПУНКТ-НАЗНАЧЕНИЯ ВРЕМЯ-ПРИБЫТИЯ}
и схему отношения
R
2
(ВРЕМЯ-ОТПРАВЛЕНИЯ, ДЛИТЕЛЬНОСТЬ-ПОЛЕТА, ПИТАНИЕ)
с выделенным ключом
62
Разложение схемы отношений означает разбиение схемы отношения на пару схем отношений R
1
и R
2
(возможно, пересекающихся) так, чтобы любое отношение r(R), удовлетворяющее F, разлагалось без потерь на R
1
и R
2
. Возможно, нужно будет повторить процесс декомпозиции отношений R
1
и R
2
, если какое-нибудь из них не окажется в ЗНФ. Декомпозиция продолжается до тех пор, пока все полученные отношения не окажутся в третьей нормальной форме относительно F.
На самом деле процесс декомпозиции схемы не бесконечен. Каждый раз, когда разлагается схема отношения, обе получившиеся в результате схемы становятся меньше, а в схеме отношения, содержащей только два атрибута, не может быть никакой транзитивной зависимости [10].
Пример 2.12. Пусть
R (РЕЙС, ПУНКТ-ОТПРАВЛЕНИЯ, ПУНКТ-НАЗНАЧЕНИЯ, ВРЕМЯ-ВЫЛЕТА, ВРЕМЯ-
ПРИБЫТИЯ, ДЛИТЕЛЬНОСТЬ-ПОЛЕТА, ТИП-САМОЛЕТА, I-КЛАСС, II-КЛАСС,
КОЛИЧЕСТВО-ПОСАДОЧНЫХ-МЕСТ, ПИТАНИЕ)
где I-КЛАСС и II-КЛАСС – количество посадочных мест в каждом салоне. Пусть множество выделенных ключей
К={РЕЙС, ПУНКТ-ОТПРАВЛЕНИЯ ПУНКТ-НАЗНАЧЕНИЯ ВРЕМЯ-ВЫЛЕТА, ПУНКТ-
ОТПРАВЛЕНИЯ ПУНКТ-НАЗНАЧЕНИЯ ВРЕМЯ-ПРИБЫТИЯ}.
Предполагается, что в одно и то же время не может быть двух рейсов с одинаковыми пунктами отправления и назначения. Пусть все выделенные ключи действительно являются ключами, и пусть имеются также следующие F-зависимости в множестве F:
ТИП-САМОЛЕТА→I-КЛАСС II-КЛАСС КОЛИЧЕСТВО-ПОСАДОЧНЫХ-МЕСТ,
ВРЕМЯ-ВЫЛЕТА ДЛИТЕЛЬНОСТЬ-ПОЛЕТА→ПИТАНИЕ,
ВРЕМЯ-ПРИБЫТИЯ ДЛИТЕЛЬНОСТЬ-ПОЛЕТА→ПИТАНИЕ,
I-КЛАСС II-КЛАСС→КОЛИЧЕСТВО-ПОСАДОЧНЫХ-МЕСТ,
I-КЛАСС КОЛИЧЕСТВО-ПОСАДОЧНЫХ-МЕСТ→II-КЛАСС,
II-КЛАСС КОЛИЧЕСТВО-ПОСАДОЧНЫХ-МЕСТ→I-КЛАСС.
Казалось бы, ВРЕМЯ-ВЫЛЕТА ВРЕМЯ-ПРИБЫТИЯ→ДЛИТЕЛЬНОСТЬ-ПОЛЕТА также должна быть F-зависимостью, но, из-за того что время прибытия и время отправления указывается местное, ДЛИТЕЛЬНОСТЬ-ПОЛЕТА зависит от часовых поясов, к которым принадлежат соответствующие аэропорты.
Сначала удалим транзитивную зависимость атрибута ПИТАНИЕ от РЕЙСА через ВРЕМЯ-
ВЫЛЕТА ДЛИТЕЛЬНОСТЬ-ПОЛЕТА. Получим схему отношения
R
1
(РЕЙС, ПУНКТ-ОТПРАВЛЕНИЯ, ПУНКТ-НАЗНАЧЕНИЯ, ВРЕМЯ-ПРИБЫТИЯ,
ДЛИТЕЛЬНОСТЬ-ПОЛЕТА, ТИП-САМОЛЕТА, I-КЛАСС, II-КЛАСС, КОЛИЧЕСТВО-
ПОСАДОЧНЫХ-МЕСТ)
с выделенными ключами
K
1
={PEHC, ПУНКТ-ОТПРАВЛЕНИЯ ПУНКТ-НАЗНАЧЕНИЯ ВРЕМЯ-ВЫЛЕТА, ПУНКТ-
ОТПРАВЛЕНИЯ ПУНКТ-НАЗНАЧЕНИЯ ВРЕМЯ-ПРИБЫТИЯ}
и схему отношения
R
2
(ВРЕМЯ-ОТПРАВЛЕНИЯ, ДЛИТЕЛЬНОСТЬ-ПОЛЕТА, ПИТАНИЕ)
с выделенным ключом
62
К
2
={ВРЕМЯ-ОТПРАВЛЕНИЯ ДЛИТЕЛЬНОСТЬ-ПОЛЕТА}.
Схема R
2
находится в ЗНФ, а схема R
1
– нет, так как I-КЛАСС, II-КЛАСС и КОЛИЧЕСТВО-
ПОСАДОЧНЫХ-МЕСТ транзитивно зависят от РЕЙСА через ТИП-САМОЛЕТА. Схема R
1 разлагается на схему
R
11
(РЕЙС, ПУНКТ-ОТПРАВЛЕНИЯ, ПУНКТ-НАЗНАЧЕНИЯ, ВРЕМЯ-ВЫЛЕТА, ВРЕМЯ-
ПРИБЫТИЯ, ДЛИТЕЛЬНОСТЬ-ПОЛЕТА, ТИП-САМОЛЕТА)
с выделенными ключами
К
11
={РЕЙС, ПУНКТ-ОТПРАВЛЕНИЯ ПУНКТ-НАЗНАЧЕНИЯ ВРЕМЯ-ВЫЛЕТА, ПУНКТ-
ОТПРАВЛЕНИЯ ПУНКТ-НАЗНАЧЕНИЯ ВРЕМЯ-ПРИБЫТИЯ}
и схему
R
12
(ТИП-САМОЛЕТА, I-КЛАСС, II-КЛАСС, КОЛИЧЕ-СТВО-ПОСАДОЧНЫХ-МЕСТ)
с выделенным ключом
К
12
={ТИП-САМОЛЕТА}.
Схема отношения R
11
находится теперь в ЗНФ относительно F, a R
12
– нет, поскольку
КОЛИЧЕСТВО-ПОСАДОЧНЫХ-МЕСТ транзитивно зависит от ТИПА-САМОЛЕТА через I-
КЛАСС II-КЛАСС. Схема R
12
разлагается на
R
121
(ТИПА-САМОЛЕТА, I-КЛАСС, II-КЛАСС) с выделенным ключом
К
121
={ТИП-САМОЛЕТА}. и схему отношения
R
122
(I-КЛАСС, II-КЛАСС, КОЛИЧЕСТВО-ПОСАДОЧНЫХ-МЕСТ)
с выделенным ключом
К
122
={I-КЛАСС II-КЛАСС}.
Декомпозиция R реализована до такой стадии, когда каждая схема отношения находится в ЗНФ относительно F. Следовательно, схема базы данных находится в ЗНФ.
Схема базы данных R не однозначна. Есть точки, в которых можно выбирать пути декомпозиции определенного отношения с целью удаления транзитивно зависимого атрибута.
Так, на первом шаге можно было выбрать
R
2
(ВРЕМЯ-ПРИБЫТИЯ, ДЛИТЕЛЬНОСТЬ-ПОЛЕТА, ПИТАНИЕ),
так как ПИТАНИЕ также транзитивно зависит от РЕЙСА через ВРЕМЯ-ПРИБЫТИЯ
ДЛИТЕЛЬНОСТЬ-ПОЛЕТА. На третьем шаге существует три варианта декомпозиции R
12
(Какие?
) Некоторые ключи для схем отношений не указаны как выделенные, например I-КЛАСС
63
КОЛИЧЕСТВО-ПОСАДОЧНЫХ-МЕСТ и II-КЛАСС КОЛИЧЕСТВО-ПОСАДОЧНЫХ-МЕСТ для
R
122
2.4.3.7. Недостатки нормализации посредством декомпозиции
При нормализации схемы отношения посредством декомпозиции возникает ряд проблем.
Во-первых, временная сложность процесса не ограничивается полиномиальной [10]. В терминах размера схемы отношения и заданного множества F-зависимостей схема отношения может обладать экспоненциальным числом ключей. Кроме того, проверка атрибута схемы на непервичность является
NP-полной задачей.
Во-вторых, число порожденных процессом схем отношения может оказаться большим, чем в действительности необходимо для ЗНФ.
Пример 2.13. Пусть заданы схема R(A, В, С, D, Е) и F={AB→CDE, AC→BDE, B→C, С→В,
C→D, В→Е}. Ключами R относительно F являются АВ и АС. Используя транзитивную зависимость D от АВ через С, разлагаем R следующим образом:
Далее в R
1
используем транзитивную зависимость Е от АВ через B для получения
Окончательная схема базы данных в ЗНФ имеет вид
Существует декомпозиция R в ЗНФ с двумя схемами отношений, а именно:
Третья проблема состоит в том, что при декомпозиции схемы отношения могут возникнуть частичные зависимости. Эти зависимости могут породить в окончательной схеме базы данных больше схем, чем это в действительности необходимо.
Пример 2.14. Для схемы отношения R(A, В, С, D) и F={A→BCD, С→D}. атрибут А является единственным ключом в R относительно F. Атрибут D транзитивно зависит от А через ВС.
Разлагая, получаем
Фактическим ключом R
2
является ВС, но D от него частично зависит. Следовательно, D
транзитивно зависит от ВС. Схему R
2
следует разложить в
Схемы R
1
, R
21
и D
22
образуют схему базы данных в ЗНФ для R. Однако схемы отношений R
1
и
R
22
также образуют схему базы данных в ЗНФ для R.
Этих недостатков можно избежать, если при декомпозиции следить за тем, чтобы промежуточное множество атрибутов в разлагаемой транзитивной зависимости было минимальным. В примере 2.14 атрибут D транзитивно зависел через ВС от А, но ВС не
64