Бойс-Кодда нормальной формой (или BCNF или 3.5NF ) является нормальной формой используется в нормализации баз данных . Это немного более сильная версия третьей нормальной формы (3NF). BCNF был разработан в 1974 году Раймондом Ф. Бойсом и Эдгаром Ф. Коддом для устранения определенных типов аномалий, которые не рассматривались 3NF в соответствии с первоначальным определением. [1]
Если реляционная схема находится в BCNF, то вся избыточность, основанная на функциональной зависимости , была удалена, хотя другие типы избыточности все еще могут существовать. Реляционная схема R находится в нормальной форме Бойса – Кодда тогда и только тогда, когда для каждой из ее зависимостей X → Y выполняется хотя бы одно из следующих условий: [2]
- X → Y - тривиальная функциональная зависимость (Y ⊆ X),
- X представляет собой суперключ для схемы R .
Таблица 3NF всегда соответствует BCNF (нормальная форма Бойса – Кодда)
Только в редких случаях таблица 3NF не соответствует требованиям BCNF. Таблица 3NF, которая не имеет нескольких перекрывающихся ключей-кандидатов, гарантированно находится в BCNF. [3] В зависимости от функциональных зависимостей таблица 3NF с двумя или более перекрывающимися ключами-кандидатами может находиться или не входить в BCNF.
Примером таблицы 3NF, которая не соответствует BCNF, является:
Суд | Время начала | Время окончания | Тип ставки |
---|---|---|---|
1 | 09:30 | 10:30 | ЭКОНОМИЯ |
1 | 11:00 | 12:00 | ЭКОНОМИЯ |
1 | 14:00 | 15:30 | СТАНДАРТ |
2 | 10:00 | 11:30 | ПРЕМИУМ-Б |
2 | 11:30 | 13:30 | ПРЕМИУМ-Б |
2 | 15:00 | 16:30 | ПРЕМИУМ-А |
- Каждая строка в таблице представляет бронирование корта в теннисном клубе. В этом клубе есть один корт с твердым покрытием (Корт 1) и один корт с травяным покрытием (Корт 2).
- Бронирование определяется его судом и периодом, на который зарезервирован суд.
- Кроме того, с каждым бронированием связан тип тарифа. Существует четыре различных типа ставок:
- SAVER, для заказов Court 1, сделанных участниками
- СТАНДАРТ, для заказов Корт 1, сделанных не членами
- PREMIUM-A, для заказов Court 2, сделанных участниками
- PREMIUM-B, для заказов Court 2, сделанных не членами
Суперключи таблицы :
- S 1 = {Суд, время начала}
- S 2 = {Суд, время окончания}
- S 3 = {Тип ставки, время начала}
- S 4 = {Тип ставки, Время окончания}
- S 5 = {Суд, время начала, время окончания}
- S 6 = {Тип ставки, время начала, время окончания}
- S 7 = {Корт, Тип ставки, Время начала}
- S 8 = {Суд, Тип ставки, Время окончания}
- S T = {Суд, Тип ставки, Время начала, Время окончания}, простая супер-клавиша
Обратите внимание , что даже если в приведенной выше таблице Время начала и Время окончания атрибуты не имеют повторяющиеся значения для каждого из них, мы все равно должны признать , что в некоторых других дней две различные заказы на суда 1 и суд 2 может начаться в то же время или конец в то же время . По этой причине {Время начала} и {Время окончания} нельзя рассматривать как суперключи таблицы.
Однако только S 1 , S 2 , S 3 и S 4 являются ключами-кандидатами (то есть минимальными суперключами для этого отношения), потому что, например, S 1 ⊂ S 5 , поэтому S 5 не может быть ключом-кандидатом.
Напомним, что 2NF запрещает частичные функциональные зависимости непервичных атрибутов (т. Е. Атрибут, который не встречается ни в одном из ключей-кандидатов. См. Ключи-кандидаты ) от ключей-кандидатов, и что 3NF запрещает транзитивные функциональные зависимости непервичных атрибутов от ключей-кандидатов.
В сегодняшней таблице судебных заказов нет неосновных атрибутов: то есть все атрибуты принадлежат некоторому ключу-кандидату. Таким образом, таблица соответствует как 2NF, так и 3NF.
Таблица не соответствует BCNF. Это связано с зависимостью Тип ставки → Суд, в которой определяющий атрибут Тип ставки - от которого зависит Суд - (1) не является ни кандидатным ключом, ни надмножеством кандидата-ключа и (2) Суд не является подмножеством типа ставки.
Тип ставки зависимости → Суд соблюдается, поскольку тип ставки должен применяться только к одному суду.
Конструкцию можно изменить, чтобы она соответствовала BCNF:
|
|
Возможные ключи для таблицы типов ставок: {Тип ставки} и {Суд, флаг члена}; возможные ключи для таблицы сегодняшних бронирований: {Суд, Время начала} и {Суд, Время окончания}. Обе таблицы находятся в BCNF. Когда {Тип ставки} является ключевым в таблице типов ставок, невозможно связать один тип ставки с двумя разными судами, поэтому при использовании {Тип ставки} в качестве ключа в таблице типов ставок аномалия, влияющая на исходную таблицу, была устранена. устранено.
Достижимость BCNF
В некоторых случаях таблица, не относящаяся к BCNF, не может быть разложена на таблицы, которые удовлетворяют BCNF и сохраняют зависимости, которые содержались в исходной таблице. Бери и Бернштейн показали в 1979 году, что, например, набор функциональных зависимостей {AB → C, C → B} не может быть представлен схемой BCNF. [4]
Рассмотрим следующую таблицу, не относящуюся к BCNF, функциональные зависимости которой следуют шаблону {AB → C, C → B}:
Человек | Тип магазина | Ближайший магазин |
---|---|---|
Дэвидсон | Оптик | орлиный глаз |
Дэвидсон | Парикмахер | Фрагменты |
Райт | Книжный магазин | Книги Мерлина |
Фуллер | Пекарня | Doughy's |
Фуллер | Парикмахер | Суини Тодд |
Фуллер | Оптик | орлиный глаз |
Для каждой комбинации типов "Человек / Магазин" в таблице указывается, какой магазин этого типа географически ближайший к дому человека. Для простоты мы предполагаем, что один магазин не может быть более одного типа.
Возможные ключи таблицы:
- {Человек, Тип магазина},
- {Человек, ближайший магазин}.
Поскольку все три атрибута являются основными атрибутами (т. Е. Принадлежат ключам-кандидатам), таблица находится в 3NF. Однако таблица отсутствует в BCNF, поскольку атрибут типа Shop функционально зависит от не суперключи: ближайший магазин.
Нарушение BCNF означает, что таблица подвержена аномалиям. Например, для Eagle Eye тип магазина может быть изменен на «Оптометрист» в записи «Фуллера», при этом сохранен тип магазина «Оптик» в записи «Дэвидсон». Это означало бы противоречивые ответы на вопрос: «Что такое тип магазина Eagle Eye?» Было бы предпочтительнее удерживать тип магазина каждого магазина только один раз, так как это предотвратит возникновение таких аномалий:
|
|
В этом пересмотренном дизайне таблица «Магазин рядом с человеком» имеет ключ-кандидат {Person, Shop}, а таблица «Магазин» - ключ-кандидат {Shop}. К сожалению, хотя этот дизайн соответствует BCNF, он неприемлем по разным причинам: он позволяет нам регистрировать несколько магазинов одного типа против одного и того же человека. Другими словами, его ключи-кандидаты не гарантируют, что функциональная зависимость {Person, Shop type} → {Shop} будет соблюдаться.
Возможна конструкция, которая устраняет все эти аномалии (но не соответствует BCNF). Этот дизайн представляет новую нормальную форму, известную как нормальная форма элементарного ключа . [5] Этот дизайн состоит из оригинальной таблицы «Ближайшие магазины», дополненной таблицей «Магазин», описанной выше. Структура таблицы, сгенерированная алгоритмом генерации схемы Бернштейна [6], на самом деле является EKNF, хотя это усовершенствование 3NF не было распознано во время разработки алгоритма:
|
|
Если ограничение ссылочной целостности определено таким образом, что {Тип магазина, Ближайший магазин} из первой таблицы должен ссылаться на {Тип магазина, Магазин} из второй таблицы, то аномалии данных, описанные ранее, предотвращаются.
Несговорчивость
Он является NP-полным , учитывая схему базы данных в третьей нормальной форме , чтобы определить, нарушает ли она нормальную форму Бойса – Кодда. [7]
История
Крис Дейт указал, что определение того, что мы теперь знаем как BCNF, появилось в статье Яна Хита в 1971 году. [8] Дейт пишет: [9]
Поскольку это определение предшествовало собственному определению Бойса и Кодда примерно на три года, мне кажется, что BCNF по праву следует называть нормальной формой Хита . Но это не так .
Эдгар Ф. Кодд выпустил свою оригинальную статью «Реляционная модель данных для больших общих банков данных» в июне 1970 года. Это была первая публикация понятия реляционной базы данных. Вся последующая работа, включая метод нормальной формы Бойса – Кодда, была основана на этой реляционной модели.
Рекомендации
- ^ Кодд, EF "Недавние исследования реляционной базы данных" в Proc. Конгресс 1974 г. (Стокгольм, Швеция, 1974 г.). Нью-Йорк, штат Нью-Йорк: Северная Голландия (1974).
- ^ Silberschatz, Abraham (2006). Концепции системы баз данных (6-е изд.). Макгроу-Хилл. С. 333 . ISBN 978-0-07-352332-3.
- ^ Винсент, М. В. и Б. Сринивасан. «Примечание о схемах Рэнди, которые входят в 3NF, но не входят в BCNF». Письма об обработке информации 48 (6), 1993, стр. 281–283.
- ^ Бери, Катриэль и Бернштейн, Филип А. "Вычислительные проблемы, связанные с проектированием реляционных схем нормальной формы". Транзакции ACM в системах баз данных 4 (1), март 1979 г., стр. 50.
- ^ Заниоло, Карло. «Новая нормальная форма для проектирования схем реляционных баз данных». Транзакции ACM в системах баз данных 7 (3), сентябрь 1982 г., стр. 493.
- ^ Бернштейн, П. А. "Синтез отношений третьей нормальной формы из функциональных зависимостей". Транзакции ACM по системам баз данных 1 (4), декабрь 1976 г., стр. 277–298.
- ^ Бери, Катриэль; Бернштейн, Филип А. (1979). «Вычислительные проблемы, связанные с проектированием реляционных схем нормальной формы». ACM-транзакции в системах баз данных . DOI : 10.1145 / 320064.320066 ., Следствие 3.
- ^ Хит, I. «Недопустимые файловые операции в реляционной базе данных». Proc. 1971 г. Семинар ACM SIGFIDET по описанию, доступу и управлению данными , Сан-Диего, Калифорния (11–12 ноября 1971 г.).
- ^ Дата, C.J. База данных в глубине: реляционная теория для практиков . О'Рейли (2005), стр. 142.
Библиография
- Дата, CJ (1999). Введение в системы баз данных (8-е изд.). Эддисон-Уэсли Лонгман. ISBN 0-321-19784-4 .
Внешние ссылки
- Правила нормализации данных
- Продвинутая нормализация, разработанная ITS Техасского университета.