Нормальная форма Бойса-Кодда
Нормальная форма Бойса-Кодда ( BCNF или 3.5NF ) — это нормальная форма, используемая при нормализации баз данных . Это немного более строгая версия третьей нормальной формы (3НФ). Используя 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.
[ редактировать ] | этого раздела Фактическая точность оспаривается . ( декабрь 2019 г. ) |
Лишь в редких случаях таблица 3NF не соответствует требованиям BCNF. Таблица 3NF, не имеющая нескольких перекрывающихся ключей-кандидатов , гарантированно находится в BCNF. [6] В зависимости от ее функциональных зависимостей таблица 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, для заказов на корт 1, сделанных участниками
- СТАНДАРТ, для бронирований Корта 1, сделанных лицами, не являющимися членами клуба.
- ПРЕМИУМ-А, для заказов на корт 2, сделанных участниками
- ПРЕМИУМ-B, для бронирований Court 2, сделанных лицами, не являющимися членами клуба.
таблицы Суперключи :
- S 1 = {Суд, Время начала}
- S 2 = {Суд, Время окончания}
- S 3 = {Тип тарифа, Время начала}
- S 4 = {Тип тарифа, Время окончания}
- S 5 = {Суд, Время начала, Время окончания}
- S 6 = {Тип тарифа, Время начала, Время окончания}
- S 7 = {Порт, Тип ставки, Время начала}
- S 8 = {Суд, Тип ставки, Время окончания}
- S T = {Суд, Тип ставки, Время начала, Время окончания}, тривиальный суперключ
Обратите внимание: хотя в приведенной выше таблице атрибуты «Время начала» и «Время окончания» не имеют повторяющихся значений для каждого из них, мы все равно должны признать, что в некоторые другие дни два разных бронирования на корте 1 и корте 2 могут в одно и то же время. начаться или закончиться в то же время . Именно по этой причине {Время начала} и {Время окончания} не могут рассматриваться как суперключи таблицы.
Однако только S1 , S2 , S3 и S4 являются ключами -кандидатами (то есть минимальными суперключами для этого отношения), поскольку, например, S1 ⊂ S5 , поэтому S5 не может быть ключом-кандидатом.
Учитывая, что 2NF запрещает частичные функциональные зависимости непростых атрибутов (т. е. атрибут, который не встречается ни в одном ключе-кандидате ) и что 3NF запрещает транзитивные функциональные зависимости непростых атрибутов от ключей-кандидатов.
В таблице «Сегодняшние записи в суд» нет непростых атрибутов: то есть все атрибуты принадлежат некоторому потенциальному ключу. Таким образом, таблица соответствует как 2НФ, так и 3НФ.
Таблица не соответствует BCNF. Это происходит из-за зависимости Тип ставки → Суд, в которой определяющий атрибут Тип ставки, от которого зависит Суд, (1) не является ни потенциальным ключом, ни расширенным набором потенциального ключа, и (2) Суд не является подмножеством типа Ставки.
Тип ставки зависимости → Суд соблюдается, поскольку тип ставки должен применяться только к одному суду.
В конструкцию можно внести изменения, чтобы она соответствовала BCNF:
|
|
Возможными ключами для таблицы типов ставок являются {Тип ставки} и {Суд, флаг участника}; возможные ключи для таблицы сегодняшних заказов — {Суд, время начала} и {Суд, время окончания}. Обе таблицы находятся в BCNF. Когда {Тип ставки} является ключом в таблице типов ставок, невозможно иметь один тип ставки, связанный с двумя разными судами, поэтому при использовании {Тип ставки} в качестве ключа в таблице типов ставок аномалия, влияющая на исходную таблицу, была устранена. устранено.
Достижимость BCNF
[ редактировать ]В некоторых случаях таблицу, не являющуюся BCNF, невозможно разложить на таблицы, удовлетворяющие BCNF и сохраняющие зависимости, содержащиеся в исходной таблице. Бери и Бернштейн показали в 1979 году, что, например, набор функциональных зависимостей {AB → C, C → B} не может быть представлен схемой BCNF. [7]
Рассмотрим следующую таблицу, не относящуюся к BCNF, функциональные зависимости которой соответствуют шаблону {AB → C, C → B}:
| Человек | Тип магазина | Ближайший магазин |
|---|---|---|
| Дэвидсон | Оптик | Орлиный глаз |
| Дэвидсон | Парикмахер | Фрагменты |
| Райт | Книжный магазин | Книги Мерлина |
| Фуллер | Пекарня | Дауи |
| Фуллер | Парикмахер | Суини Тоддс |
| Фуллер | Оптик | Орлиный глаз |
Для каждой комбинации типа «Человек/Магазин» таблица показывает, какой магазин этого типа географически находится ближе всего к дому человека. Для простоты будем считать, что один магазин не может относиться к более чем одному типу.
Возможные ключи таблицы:
- {Человек, Тип магазина},
- {Человек, Ближайший магазин}.
Поскольку все три атрибута являются простыми атрибутами (т.е. принадлежат потенциальным ключам), таблица находится в 3NF. Однако таблица не находится в BCNF, поскольку атрибут типа магазина функционально зависит от несуперключа: Ближайший магазин.
Нарушение BCNF означает, что таблица подвержена аномалиям. Например, тип магазина Eagle Eye может быть изменен на «Оптометрист» в записи «Фуллер», сохраняя при этом тип магазина «Оптик» в записи «Дэвидсон». Это означало бы противоречивые ответы на вопрос: «Какой тип магазина Eagle Eye?» Было бы предпочтительнее сохранить тип магазина каждого магазина только один раз, поскольку это предотвратит возникновение таких аномалий:
|
|
В этом обновленном дизайне таблица «Магазин рядом с человеком» имеет потенциальный ключ {Person, Shop}, а таблица «Магазин» имеет потенциальный ключ {Shop}. К сожалению, хотя эта конструкция соответствует BCNF, она неприемлема по разным причинам: она позволяет нам регистрировать несколько магазинов одного типа против одного и того же человека. Другими словами, его потенциальные ключи не гарантируют, что функциональная зависимость {Человек, Тип магазина} → {Магазин} будет соблюдаться.
Возможна конструкция, которая устраняет все эти аномалии (но не соответствует BCNF). Этот дизайн вводит новую нормальную форму, известную как Нормальная форма элементарного ключа . [8] Этот дизайн состоит из оригинальной таблицы «Ближайшие магазины», дополненной описанной выше таблицей «Магазин». Структура таблицы, созданная алгоритмом генерации схемы Бернштейна. [9] на самом деле это EKNF, хотя это усовершенствование 3NF не было признано на момент разработки алгоритма:
|
|
Если определено ограничение ссылочной целостности , согласно которому {Тип магазина, Ближайший магазин} из первой таблицы должен ссылаться на {Тип магазина, Магазин} из второй таблицы, то описанные ранее аномалии данных предотвращаются.
несговорчивость
[ редактировать ]Это NP-полная схема базы данных в третьей нормальной форме , позволяющая определить, нарушает ли она нормальную форму Бойса-Кодда. [10]
Разложение на BCNF
[ редактировать ]Если отношение R не находится в BCNF из-за функциональной зависимости X → Y, то R можно разложить на BCNF, заменив это отношение двумя подотношениями:
- Один с атрибутами X + ,
- и еще один с атрибутами RX + +Х. Обратите внимание, что R представляет все атрибуты исходного отношения.
Проверьте, находятся ли оба подотношения в BCNF, и рекурсивно повторите процесс с любым подотношением, которого нет в BCNF. [11]
Ссылки
[ редактировать ]- ^ Перейти обратно: а б Дата, CJ. База данных в глубине: реляционная теория для практиков . О'Рейли (2005), с. 142.
- ^ Кодд, Э.Ф. «Недавние исследования реляционных баз данных» в Proc. Конгресс 1974 г. (Стокгольм, Швеция, 1974 г.). Нью-Йорк, штат Нью-Йорк: Северная Голландия (1974).
- ^ Хит, И. «Недопустимые файловые операции в реляционной базе данных». Учеб. 1971 г. Семинар ACM SIGFIDET по описанию, доступу и контролю данных , Сан-Диего, Калифорния (11–12 ноября 1971 г.).
- ^ Келер, Хеннинг; Линк, Себастьян (01 июля 2018 г.). «Проектирование схемы SQL: основы, нормальные формы и нормализация» . Информационные системы . 76 : 88–113. дои : 10.1016/j.is.2018.04.001 . hdl : 2292/31753 .
- ^ Перейти обратно: а б Зильбершац, Авраам (2006). Концепции системы баз данных (6-е изд.). МакГроу-Хилл. стр. 333 . ISBN 978-0-07-352332-3 .
- ^ Винсент, MW и Б. Шринивасан. «Заметка о реляционных схемах, которые есть в 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 в системах баз данных . 4 : 30–59. дои : 10.1145/320064.320066 . S2CID 11409132 .
, Следствие 3. - ^ Разложение BCNF , получено 15 марта 2023 г.
Библиография
[ редактировать ]- Дата, CJ (1999). Введение в системы баз данных (8-е изд.). Эддисон-Уэсли Лонгман. ISBN 0-321-19784-4 .
Внешние ссылки
[ редактировать ]- Правила нормализации данных
- Расширенная нормализация от ITS, Техасский университет.