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

Нормальная форма, используемая при нормализации базы данных

Нормальная форма Бойса–Кодда ( BCNF или 3.5NF ) — это нормальная форма , используемая при нормализации базы данных . Это немного более строгая версия третьей нормальной формы (3NF). Используя BCNF, база данных удалит все избыточности, основанные на функциональных зависимостях .

История

Эдгар Ф. Кодд опубликовал свою оригинальную статью "Реляционная модель данных для больших общих банков данных" в июне 1970 года. Это был первый раз, когда было опубликовано понятие реляционной базы данных. Все последующие работы, включая метод нормальной формы Бойса-Кодда, основывались на этой реляционной модели.

Нормальная форма Бойса-Кодда была впервые описана Яном Хитом в 1971 году, и Крис Дейт также назвал ее нормальной формой Хита . ^[1]

BCNF была разработана в 1974 году Рэймондом Ф. Бойсом и Эдгаром Ф. Коддом для устранения некоторых типов аномалий, которые не рассматривались в 3NF, как это было изначально определено. ^[2]

Как уже упоминалось, Крис Дейт указал на то, что определение того, что мы теперь знаем как BCNF, появилось в статье Яна Хита в 1971 году. ^[3] Дейт пишет: ^[1]

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

Определение

Если реляционная схема находится в BCNF, то вся избыточность, основанная на функциональной зависимости, была удалена, ^[4] хотя другие типы избыточности все еще могут существовать. Реляционная схема R находится в нормальной форме Бойса-Кодда тогда и только тогда, когда для каждой из ее зависимостей X → Y выполняется по крайней мере одно из следующих условий: ^[5]

• X → Y — тривиальная функциональная зависимость (Y ⊆ X),
• X — суперключ для схемы R. ^[5 ]

Обратите внимание, что если реляционная схема находится в BCNF, то она находится в 3NF.

Таблицы 3NF не всегда соответствуют BCNF

Только в редких случаях таблица 3NF не соответствует требованиям BCNF. Таблица 3NF, не имеющая нескольких перекрывающихся потенциальных ключей , гарантированно находится в BCNF. ^[6] В зависимости от ее функциональных зависимостей таблица 3NF с двумя или более перекрывающимися потенциальными ключами может находиться или не находиться в BCNF.

Пример таблицы 3NF, которая не соответствует BCNF:

• Каждая строка в таблице представляет собой бронирование корта в теннисном клубе. В этом клубе есть один хардовый корт (Корт 1) и один травяной корт (Корт 2)
• Бронирование определяется судом и периодом, на который суд зарезервирован.
• Кроме того, каждое бронирование имеет связанный с ним тип тарифа. Существует четыре различных типа тарифа:
  • SAVER, для бронирования корта 1, сделанного членами
  • СТАНДАРТНЫЙ, для бронирования корта 1 лицами, не являющимися членами клуба
  • PREMIUM-A, для бронирования корта 2, сделанного членами
  • PREMIUM-B, для бронирования корта 2 лицами, не являющимися членами клуба

Суперключи таблицы :

• S ₁ = {Корт, Время начала}
• S ₂ = {Суд, Время окончания}
• S ₃ = {Тип ставки, Время начала}
• S ₄ = {Тип ставки, Время окончания}
• S ₅ = {Суд, Время начала, Время окончания}
• S ₆ = {Тип ставки, Время начала, Время окончания}
• S ₇ = {Суд, Тип ставки, Время начала}
• S ₈ = {Суд, Тип ставки, Время окончания}
• S _T = {Суд, Тип ставки, Время начала, Время окончания}, тривиальный суперключ

Обратите внимание, что хотя в таблице выше атрибуты Start time и End time не имеют повторяющихся значений для каждого из них, мы все равно должны признать, что в некоторые другие дни два разных бронирования на корте 1 и корте 2 могут начаться в одно и то же время или закончиться в одно и то же время . Вот почему {Start time} и {End time} нельзя считать суперключами таблицы.

Однако только S ₁ , S ₂ , S ₃ и S ₄ являются потенциальными ключами (то есть минимальными суперключами для этого отношения), поскольку, например, S ₁ ⊂ S ₅ , поэтому S ₅ не может быть потенциальными ключами.

Учитывая, что 2NF запрещает частичные функциональные зависимости непервичных атрибутов (т. е. атрибута, который не встречается ни в одном ключе-кандидате ), а 3NF запрещает транзитивные функциональные зависимости непервичных атрибутов от ключей-кандидатов.

В таблице «Сегодняшние суды» нет не-простых атрибутов: то есть все атрибуты принадлежат какому-то потенциальному ключу. Поэтому таблица придерживается как 2NF, так и 3NF.

Таблица не придерживается BCNF. Это происходит из-за зависимости Rate type → Court, в которой определяющий атрибут Rate type – от которого зависит Court – (1) не является ни потенциальным ключом, ни надмножеством потенциального ключа и (2) Court не является подмножеством Rate type.

Тип ставки зависимости → Суд учитывается, поскольку тип ставки должен применяться только к одному суду.

Проект может быть изменен таким образом, чтобы он соответствовал BCNF:

Ключами-кандидатами для таблицы Rate types являются {Rate type} и {Court, Member flag}; ключами-кандидатами для таблицы Today's bookings являются {Court, Start time} и {Court, End time}. Обе таблицы находятся в BCNF. Когда {Rate type} является ключом в таблице Rate types, невозможно связать один тип Rate с двумя разными Courts, поэтому при использовании {Rate type} в качестве ключа в таблице Rate types аномалия, влияющая на исходную таблицу, была устранена.

Достижимость BCNF

В некоторых случаях таблица, не соответствующая BCNF, не может быть разложена на таблицы, которые удовлетворяют BCNF и сохраняют зависимости, которые содержались в исходной таблице. Бири и Бернстайн показали в 1979 году, что, например, набор функциональных зависимостей {AB → C, C → B} не может быть представлен схемой BCNF. ^[7]

Рассмотрим следующую таблицу, не являющуюся BCNF, функциональные зависимости которой следуют шаблону {AB → C, C → B}:

Для каждой комбинации типа Человек/Магазин таблица сообщает нам, какой магазин этого типа географически ближе всего к дому человека. Для простоты мы предполагаем, что один магазин не может быть более чем одного типа.

Возможные ключи таблицы:

• {Персона, Тип магазина},
• {Персона, Ближайший магазин}.

Поскольку все три атрибута являются первичными атрибутами (т.е. принадлежат к потенциальным ключам), таблица находится в 3NF. Однако таблица не находится в BCNF, поскольку атрибут типа Shop функционально зависит от не-суперключа: Nearest shop.

Нарушение BCNF означает, что таблица подвержена аномалиям. Например, Eagle Eye может изменить свой тип магазина на "Optometrist" в своей записи "Fuller", сохранив тип магазина "Optician" в своей записи "Davidson". Это будет означать противоречивые ответы на вопрос: "Каков тип магазина Eagle Eye?" Удержание типа магазина каждого магазина только один раз, казалось бы, предпочтительнее, так как это предотвратит возникновение таких аномалий:

В этом пересмотренном дизайне таблица "Магазин рядом с человеком" имеет ключ-кандидат {Персона, Магазин}, а таблица "Магазин" имеет ключ-кандидат {Магазин}. К сожалению, хотя этот дизайн придерживается BCNF, он неприемлем по другим причинам: он позволяет нам регистрировать несколько магазинов одного типа для одного и того же человека. Другими словами, его ключи-кандидаты не гарантируют, что функциональная зависимость {Персона, Тип магазина} → {Магазин} будет соблюдена.

Возможен дизайн, который устраняет все эти аномалии (но не соответствует BCNF). Этот дизайн вводит новую нормальную форму, известную как Elementary Key Normal Form . ^[8] Этот дизайн состоит из исходной таблицы «Ближайшие магазины», дополненной таблицей «Магазин», описанной выше. Структура таблицы, сгенерированная алгоритмом генерации схемы Бернштейна ^[9] , на самом деле является EKNF, хотя это улучшение 3NF не было распознано во время разработки алгоритма:

Если ограничение ссылочной целостности определено таким образом, что {Тип магазина, Ближайший магазин} из первой таблицы должен ссылаться на {Тип магазина, Магазин} из второй таблицы, то аномалии данных, описанные ранее, будут предотвращены.

Неразрешимость

Это NP-полная задача , если задана схема базы данных в третьей нормальной форме , чтобы определить, нарушает ли она нормальную форму Бойса-Кодда. ^[10]

Разложение в BCNF

Если отношение R не находится в BCNF из-за функциональной зависимости X→Y, то R можно разложить в BCNF, заменив это отношение двумя подотношениями:

1. Один с атрибутами X ⁺ ,
2. и другой с атрибутами RX ⁺ +X. Обратите внимание, что R представляет все атрибуты в исходном отношении.

Проверьте, находятся ли оба подотношения в BCNF, и повторите процесс рекурсивно с любым подотношением, которое не находится в BCNF. ^[11]

Ссылки

1. Date, C. J. База данных в деталях: реляционная теория для практиков . O'Reilly (2005), стр. 142.
2. Кодд, Э. Ф. «Последние исследования реляционных баз данных» в Трудах Конгресса 1974 г. (Стокгольм, Швеция, 1974 г.). Нью-Йорк, Нью-Йорк: Северная Голландия (1974).
3. Хит, И. «Недопустимые файловые операции в реляционной базе данных». Труды семинара ACM SIGFIDET 1971 года по описанию, доступу и управлению данными , Сан-Диего, Калифорния (11–12 ноября 1971 г.).
4. Кёлер, Хеннинг; Линк, Себастьян (2018-07-01). «Проектирование схемы SQL: основы, нормальные формы и нормализация». Информационные системы . 76 : 88–113. doi :10.1016/j.is.2018.04.001. hdl : 2292/31753 .
5. Зильбершац, Авраам (2006). Концепции системы баз данных (6-е изд.). МакГроу-Хилл. стр. 333. ISBN 978-0-07-352332-3.
6. Винсент, М. В. и Б. Шринивасан. «Заметка о реляционных схемах, которые находятся в 3NF, но не в BCNF». Information Processing Letters 48(6), 1993, стр. 281–283.
7. Бири, Катриэль и Бернстайн, Филип А. «Вычислительные проблемы, связанные с разработкой реляционных схем нормальной формы». ACM Transactions on Database Systems 4(1), март 1979 г., стр. 50.
8. Заниоло, Карло. «Новая нормальная форма для проектирования схем реляционных баз данных». ACM Transactions on Database Systems 7(3), сентябрь 1982 г., стр. 493.
9. Бернстайн, П. А. «Синтез отношений третьей нормальной формы из функциональных зависимостей». ACM Transactions on Database Systems 1(4), декабрь 1976 г., стр. 277–298.
10. Бири, Катриель; Бернстайн, Филип А. (1979). «Вычислительные проблемы, связанные с разработкой реляционных схем нормальной формы». ACM Transactions on Database Systems . 4 : 30–59. doi : 10.1145/320064.320066 . S2CID  11409132., Следствие 3.
11. BCNF Decomposition, 5 февраля 2022 г. , получено 15.03.2023 г.

Библиография

• Дейт, К. Дж. (1999). Введение в системы баз данных (8-е изд.). Эддисон-Уэсли Лонгман. ISBN 0-321-19784-4 . 

Внешние ссылки

• Правила нормализации данных
• Расширенная нормализация от ITS, Техасский университет.