Нормальная форма Бойса – Кодда - Boyce–Codd normal form

Нормальная форма Бойса – Кодда (или же BCNF или же 3,5 нФ) это нормальная форма используется в нормализация базы данных. Это немного более сильная версия третья нормальная форма (3НФ). BCNF был разработан в 1974 г. Раймонд Ф. Бойс и Эдгар Ф. Кодд для устранения определенных типов аномалий, не рассматриваемых 3NF в соответствии с первоначальным определением.[1]

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

  • Икс → Y является тривиальной функциональной зависимостью (Y ⊆ X),
  • Икс это суперключ для схемы р.

Таблица 3NF всегда соответствует BCNF (нормальная форма Бойса – Кодда)

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

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

Судебные заказы сегодня
СудНачальное времяВремя окончанияТип ставки
109:3010:30SAVER
111:0012:00SAVER
114:0015:30СТАНДАРТНЫЙ
210:0011:30ПРЕМИУМ-Б
211:3013:30ПРЕМИУМ-Б
215:0016:30ПРЕМИУМ-А
  • Каждая строка в таблице представляет бронирование корта в теннисном клубе. В этом клубе есть один корт с твердым покрытием (Корт 1) и один корт с травяным покрытием (Корт 2).
  • Бронирование определяется его судом и периодом, на который зарезервирован суд.
  • Кроме того, с каждым бронированием связан тип тарифа. Существует четыре различных типа ставок:
    • SAVER, для заказов Court 1, сделанных участниками
    • СТАНДАРТ, для заказов Корт 1, сделанных не членами
    • PREMIUM-A, для заказов Court 2, сделанных участниками
    • PREMIUM-B, для заказов Court 2, сделанных не членами

Столы суперключи находятся:

  • S1 = {Суд, время начала}
  • S2 = {Суд, время окончания}
  • S3 = {Тип цены, Время начала}
  • S4 = {Тип цены, Время окончания}
  • S5 = {Суд, время начала, время окончания}
  • S6 = {Тип цены, время начала, время окончания}
  • S7 = {Корт, Тип ставки, Время начала}
  • S8 = {Суд, Тип ставки, Время окончания}
  • SТ = {Суд, Тип ставки, Время начала, Время окончания}, простая суперклавиша

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

Однако только S1, S2, S3 и S4 находятся ключи-кандидаты (то есть минимальные суперключи для этого отношения), потому что, например, S1 ⊂ S5, поэтому S5 не может быть кандидатом ключа.

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

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

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

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

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

Типы ставок
Тип ставкиСудФлаг участника
ЭКОНОМИЯ1да
СТАНДАРТНЫЙ1Нет
ПРЕМИУМ-А2да
ПРЕМИУМ-Б2Нет
Сегодняшние бронирования
Флаг участникаСудНачальное времяВремя окончания
да109:3010:30
да111:0012:00
Нет114:0015:30
Нет210:0011:30
Нет211:3013:30
да215:0016:30

Возможные ключи для таблицы типов ставок: {Тип ставки} и {Суд, флаг члена}; возможные ключи для таблицы сегодняшних бронирований: {Суд, Время начала} и {Суд, Время окончания}. Обе таблицы находятся в 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?» Было бы предпочтительнее держать каждый тип магазина только один раз, так как это предотвратит появление таких аномалий:

Магазин рядом с человеком
ЧеловекМагазин
Дэвидсонорлиный глаз
ДэвидсонФрагменты
РайтКниги Мерлина
ФуллерDoughy's
ФуллерСуини Тодд
Фуллерорлиный глаз
Магазин
МагазинТип магазина
орлиный глазОптик
ФрагментыПарикмахер
Книги МерлинаКнижный магазин
Doughy'sПекарня
Суини ТоддПарикмахер

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

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

Ближайшие магазины
ЧеловекТип магазинаБлижайший магазин
ДэвидсонОптикорлиный глаз
ДэвидсонПарикмахерФрагменты
РайтКнижный магазинКниги Мерлина
ФуллерПекарняDoughy's
ФуллерПарикмахерСуини Тодд
ФуллерОптикорлиный глаз
Магазин
МагазинТип магазина
орлиный глазОптик
ФрагментыПарикмахер
Книги МерлинаКнижный магазин
Doughy'sПекарня
Суини ТоддПарикмахер

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

Несговорчивость

это НП-полный, учитывая схему базы данных в третья нормальная форма, чтобы определить, нарушает ли он нормальную форму Бойса – Кодда.[7]

История

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

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

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

Рекомендации

  1. ^ Кодд, Э. Ф. «Недавние исследования реляционной базы данных» в Proc. 1974 Конгресс (Стокгольм, Швеция, 1974). Нью-Йорк, Нью-Йорк: Северная Голландия (1974).
  2. ^ Зильбершатц, Абрахам (2006). Концепции системы баз данных (6-е изд.). Макгроу-Хилл. стр.333. ISBN  978-0-07-352332-3.
  3. ^ Винсент, М. В. и Б. Сринивасан. «Примечание о схемах Рэнди, которые находятся в 3NF, но не в BCNF». Письма об обработке информации 48 (6), 1993, стр. 281–283.
  4. ^ Бери, Катриэль и Бернштейн, Филип А. "Вычислительные проблемы, связанные с проектированием реляционных схем нормальной формы". Транзакции ACM в системах баз данных 4 (1), март 1979 г., стр. 50.
  5. ^ Заниоло, Карло. «Новая нормальная форма для проектирования схем реляционных баз данных». Транзакции ACM в системах баз данных 7 (3), сентябрь 1982 г., стр. 493.
  6. ^ Бернштейн, П. А. "Синтез отношений третьей нормальной формы из функциональных зависимостей". Транзакции ACM в системах баз данных 1 (4), декабрь 1976 г., стр. 277–298.
  7. ^ Бери, Катриэль; Бернштейн, Филип А. (1979). "Вычислительные проблемы, связанные с проектированием реляционных схем нормальной формы". Транзакции ACM в системах баз данных. Дои:10.1145/320064.320066.закрытый доступ, Следствие 3.
  8. ^ Хит, И. «Недопустимые файловые операции в реляционной базе данных». Proc. 1971 Семинар ACM SIGFIDET по описанию, доступу и контролю данных, Сан-Диего, Калифорния (11–12 ноября 1971 г.).
  9. ^ Дата, К. Дж. База данных в деталях: теория отношений для практиков. О'Рейли (2005), стр. 142.

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

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

внешняя ссылка