нормальная форма Бойса – Кодда (или BCNF или 3.5NF ) - это нормальная форма, используемая в нормализации базы данных. Это немного более сильная версия третьей нормальной формы (3NF). BCNF был разработан в 1974 году Рэймондом Ф. Бойсом и Эдгаром Ф. Коддом для устранения определенных типов аномалий, которые не рассматривались 3NF, как это было первоначально определено.
Если реляционная схема находится в BCNF, тогда вся избыточность, основанная на функциональной зависимости, имеет был удален, хотя другие типы избыточности все еще могут существовать. Реляционная схема R находится в нормальной форме Бойса – Кодда тогда и только тогда, когда для каждой из ее зависимостей X → Y выполняется хотя бы одно из следующих условий:
Только в редких случаях таблица 3NF не удовлетворяет требованиям BCNF. Таблица 3NF, которая не имеет нескольких перекрывающихся ключей-кандидатов, гарантированно находится в BCNF. В зависимости от того, каковы ее функциональные зависимости, таблица 3NF с двумя или более перекрывающимися ключами-кандидатами может быть или не находиться в BCNF.
Примером таблицы 3NF, которая не соответствует BCNF, является:
Суд | Время начала | Время окончания | Тип ставки |
---|---|---|---|
1 | 09:30 | 10:30 | SAVER |
1 | 11:00 | 12:00 | SAVER |
1 | 14:00 | 15:30 | СТАНДАРТ |
2 | 10:00 | 11:30 | ПРЕМИУМ-Б |
2 | 11:30 | 13:30 | PREMIUM-B |
2 | 15:00 | 16:30 | PREMIUM-A |
В таблице суперключи :
Обратите внимание, что хотя в приведенной выше таблице атрибуты Время начала и Время окончания не имеют повторяющихся значений для каждого из них, мы все же должны признать, что в некоторые другие дни два разных бронирования на корте 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 и сохраняют зависимости, которые содержались в исходной таблице. Бери и Бернштейн показали в 1979 году, что, например, набор функциональных зависимостей {AB → C, C → B} не может быть представлен схемой BCNF.
Рассмотрим следующую таблицу, отличную от BCNF, функциональные зависимости которой следуют паттерн {AB → C, C → B}:
Лицо | Тип магазина | Ближайший магазин |
---|---|---|
Davidson | Оптик | Eagle Eye |
Davidson | Парикмахер | Snippets |
Wright | Bookshop | Merlin Books |
Fuller | Пекарня | Doughy's |
Fuller | Парикмахер | Sweeney Todd's |
Fuller | Optician | Eagle Eye |
Для каждой комбинации типов "Человек / Магазин" в таблице указывается, какой магазин этого типа географически ближайший к дому человека. Для простоты мы предполагаем, что один магазин не может быть более одного типа.
Возможные ключи таблицы:
Поскольку все три атрибута являются основными атрибутами (т.е. принадлежат в ключи-кандидаты), таблица находится в 3НФ. Однако таблица отсутствует в BCNF, так как атрибут типа Shop функционально зависит от не суперключи: Nearest shop.
Нарушение BCNF означает, что таблица подвержена аномалиям. Например, для Eagle Eye тип магазина может быть изменен на «Оптометрист» в записи «Фуллера», но при этом сохранен тип магазина «Оптик» в записи «Дэвидсон». Это означало бы противоречивые ответы на вопрос: «Что такое тип магазина Eagle Eye?» Удерживать каждый тип магазина только один раз было бы предпочтительнее, поскольку это предотвратит возникновение таких аномалий:
|
|
В этом измененном дизайне стол «Магазин рядом с человеком» имеет кандидата ключ {Person, Shop}, а таблица "Shop" имеет ключ кандидата {Shop}. К сожалению, хотя этот дизайн соответствует BCNF, он неприемлем по разным причинам: он позволяет нам регистрировать несколько магазинов одного типа против одного и того же человека. Другими словами, его ключи-кандидаты не гарантируют, что функциональная зависимость {Person, Shop type} → {Shop} будет соблюдаться.
Возможна конструкция, которая устраняет все эти аномалии (но не соответствует BCNF). Этот дизайн представляет новую нормальную форму, известную как нормальная форма элементарного ключа. Этот дизайн состоит из оригинальной таблицы «Ближайшие магазины», дополненной таблицей «Магазин», описанной выше. Структура таблицы, сгенерированная алгоритмом генерации схемы Бернштейна, на самом деле является EKNF, хотя это усовершенствование 3NF не было распознано на момент разработки алгоритма:
|
|
Если ссылка ограничение целостности определяется таким образом, что {Тип магазина, Ближайший магазин} из первой таблицы должен ссылаться на {Тип магазина, Магазин} из второй таблицы, тогда аномалии данных, описанные ранее, предотвращаются.
Это NP-полная, учитывая схему базы данных в третьей нормальной форме, чтобы определить, нарушает ли она нормальную форму Бойса – Кодда.
Крис Дейт указал, что определение того, что мы теперь знаем как BCNF, появилось в статье Яна Хита в 1971 году. Дейт пишет:
Поскольку это определение предшествовало Бойсу. и собственное определение Кодда, примерно за три года, мне кажется, что BCNF по праву следует называть нормальной формой Хита. Но это не так..
Эдгар Ф. Кодд выпустил свою оригинальную статью «Реляционная модель данных для больших общих банков данных» в июне 1970 года. Это была первая публикация понятия реляционной базы данных. Вся последующая работа, включая метод нормальной формы Бойса – Кодда, была основана на этой реляционной модели.