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

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук

Нормальна форма Бойса — Кодда (або НФБК, або БКННФ, або 3.5НФ) — нормальна форма використовна в нормалізації баз даних. Це трошки сильніша версія третьої нормальної форми (3НФ). Таблиця знаходиться в НФБК тоді і тільки тоді, коли для кожної її нетривіальної функціональної залежності X → Y, X це суперключ — тобто, X або потенційний ключ, або його надмножина.

НФБК була віднайдена в 1974 Реймондом Бойсом і Едгаром Коддом через деякі типи аномалій з якими не спрацьовувала 3НФ як було заявлено.[1]

Крістофер Дейт вказав, що визначення того, що ми знаємо як НФБК в 1971 опублікував Ян Хіт.[2] Дейт писав:

«Через те, що це визначення випередило визначення Бойса і Кодда на три роки, мені здається, що НФБК по праву має називатись нормальна форма Хіта. Але це не так.»[3]

Таблиці в 3НФ, які не відповідають НФБК[ред.ред. код]

Лише зрідка таблиця в 3НФ не відповідає вимогам НФБК. Таблиця в 3НФ, яка не має кількох потенційних ключів, що перетинаються, гарантовано в НФБК.[4] Залежно від своїх функціональних залежностей, таблиця в 3НФ з двома або більше потенційними ключами, що перетинаються може бути або не бути в НФБК.

Приклад таблиці в 3НФ, яка не є в НФБК:

Замовлення кортів на сьогодні
Корт Час початку Час завершення Тип оплати
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)
  • Замовлення визначається замовленим кортом і відтинком часу, на який корт замовлено
  • Додатково, кожне замовлення має «Тип оплати» асоційований з ним. Існує чотири різних типи оплати:
  • БЕРЕЖЛИВИЙ, для замовлень корту 1 членами клубу
  • СТАНДАРТНИЙ, для замовлень корту 1 не членами клубу
  • ПРЕМІАЛЬНИЙ-A, для замовлень корту 2 членами клубу
  • ПРЕМІАЛЬНИЙ-B, для замовлень корту 2 не членами клубу

Потенційні ключі таблиці:

  • {Корт, Час початку}
  • {Корт, Час завершення}
  • {Тип оплати, Час початку}
  • {Тип оплати, Час завершення}

Згадаймо, що 2НФ забороняє часткові функціональні залежності неключових атрибутів від потенційних ключів, і що 3НФ забороняє транзитивні функціональні залежності неключових атрибутів від потенційних ключів. В таблиці «Замовлення кортів на сьогодні» не має неключових атрибутів: тобто, всі атрибути належать потенційним ключам.

Таблиця не знаходиться в НФБК через залежність «Тип оплати» → «Корт», де визначальний атрбут («Тип оплати») ані потенційний ключ, ані його надмножина.

Залежність «Тип оплати» → «Корт» відображає, що певний тип оплати застосовується саме для одного корту.

Дизайн можна виправити так, щоб він відповідав НФБК:

Тип оплати
Тип оплати Корт Членство
БЕРЕЖЛИВИЙ 1 Так
СТАНДАРТНИЙ 1 Ні
ПРЕМІАЛЬНИЙ-A 2 Так
ПРЕМІАЛЬНИЙ-B 2 Ні
Сьогоднішнє замовлення
Тип оплати Час початку Час завершення
БЕРЕЖЛИВИЙ 09:30 10:30
БЕРЕЖЛИВИЙ 11:00 12:00
СТАНДАРТНИЙ 14:00 15:30
ПРЕМІАЛЬНИЙ-B 10:00 11:30
ПРЕМІАЛЬНИЙ-B 11:30 13:30
ПРЕМІАЛЬНИЙ-A 15:00 16:30


Потенційними ключами для таблиці «Тип оплати» є {Тип оплати} і {Корт, Членство}; потенційними ключами для таблиці «Сьогоднішнє замовлення» є {Тип оплати, Час початку} і {Тип оплати, Час завершення}. Обидві таблиці знаходяться в НФБК. Тепер мати один тип оплати асоційований з двома різними кортами неможливо, тож можливі аномалії первісної таблиці виключені.

Досяжність НФБК[ред.ред. код]

В деяких випадках, не НФБК таблиця не може бути розкладена в таблиці, що задовільняють НФБК із збереженням залежностей початкової таблиці. Бірі і Бернштейн у 1979 показали, що, наприклад, набір функціональних залежностей {AB → C, C → B} не може бути представлений НФБК.[5] Таким чином, на відміну від перших трьох нормальних форм, НФБК не завжди досяжна.

Уявімо таблицю не в НФБК чиї функціональні залежності відповідають шаблону {AB ? C, C ? B}:

Найближчий магазин
Особа Тип магазину Найближчий магазин
Скиба Оптика Орлине око
Скиба Перукарня Клаптики
Пасічник Книжний Книжки Мерліна
Ковтун Пекарня Тістечка
Ковтун Перукарня Шпилька
Ковтун Оптика Орлине око

Для кожної комбінації «Особа» / «Тип магазину», таблиця каже нам який з магазинів цього типу географічно найближчий до помешкання певної особи. Для простоти ми припускаємо, що один магазин не може одночасно бути декількох типів.

Потенційні ключі таблиці:

  • {Особа, Тип магазину}
  • {Особа, Найближчий магазин}

Через те, що всі три атрибути ключові (тобто належить потенційному ключу), таблиця в 3НФ. Таблиця не в НФБК, бо «Тип магазину» функціонально залежний від не суперключа: «Найближчий магазин».

Невідповідність до НФБК значить, що таблиця вразлива для аномалій. Наприклад, Орлине око може змінити свій тип на «Оптометрія» на запису для Ковтуна залишив тип «Оптика» на запису для Скиби. Це викличе суперечливі відповіді на запитання: «Який тип має магазин Орлине око?» Здається розумним зберігати тип для кожного магазину тільки один раз, це унебезпечить від цієї аномалії:

Магазин біля особи
Особа Магазин
Скиба Орлине око
Скиба Клаптики
Пасічник Книжки Мерліна
Ковтун Тістечка
Ковтун Шпилька
Ковтун Орлине око
Магазин
Магазин Тип магазину
Орлине око Оптика
Клаптики Перукарня
Книжки Мерліна Книжний
Тістечка Пекарня
Шпилька Перукарня


В цьому переглянутому дизайні, таблиця «Магазин біля особи» має потенційний ключ {Особа, Магазин}, і таблиця «Магазин» має потенційний ключ {Магазин}. Хоча цей дизайн знаходиться у НФБК, він неприйнятний з іншої причини: він дозволяє нам записати декілька магазинів одного типу для ожнієї особи. Інакше кажучи, цей дизайн не гарантує виконання функціональної залежності {Особа, Тип магазину} → {Магазин}.

Дизайн, який виключає всі ці аноммалії (але не задовільняє умовам НФБК) можливий.[6] Цей дизайн містить початкову таблицю «Найближчий магазин» і додає таблицю «Магазин» описану нижче.

Найближчий магазин
Особа Тип магазину Найближчий магазин
Скиба Оптика Орлине око
Скиба Перукарня Клаптики
Пасічник Книжний Книжки Мерліна
Ковтун Пекарня Тістечка
Ковтун Перукарня Шпилька
Ковтун Оптика Орлине око
Магазин
Магазин Тип магазину
Орлине око Оптика
Клаптики Перукарня
Книжки Мерліна Книжний
Тістечка Пекарня
Шпилька Перукарня


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


Примітки[ред.ред. код]

  1. Codd, E. F. "Recent Investigations into Relational Data Base Systems." IBM Research Report RJ1385 (April 23rd, 1974). Republished in Proc. 1974 Congress (Stockholm, Sweden, 1974). New York, N.Y.: North-Holland (1974).
  2. Heath, I. "Unacceptable File Operations in a Relational Database." Proc. 1971 ACM SIGFIDET Workshop on Data Description, Access, and Control, San Diego, Calif. (November 11th–12th, 1971).
  3. Date, C.J. Database in Depth: Relational Theory for Practitioners. O'Reilly (2005), p. 142.
  4. Vincent, M.W. and B. Srinivasan. "A Note on Relation Schemes Which Are in 3NF But Not in BCNF." Information Processing Letters 48(6), 1993, pp. 281–83.
  5. Beeri, Catriel and Bernstein, Philip A. "Computational problems related to the design of normal form relational schemas." ACM Transactions on Database Systems 4(1), March 1979, p. 50.
  6. Zaniolo, Carlo. "A New Normal Form for the Design of Relational Database Schemata." ACM Transactions on Database Systems 7(3), September 1982, pp. 493.

Посилання[ред.ред. код]