C, PHP, VB, .NET

Дневникът на Филип Петров


* Нормална форма на Бойс-Код и четвърта нормална форма

Публикувано на 08 юни 2014 в раздел Бази от Данни.

Продължавам статията свързана с примери за нормализация. Бяхме стигнали до 3НФ. Следващата нормална форма, която можем да приемем за междинна между 3-та и 4-та, е нормалната форма на Бойс-Код. Нека разгледаме следната таблица:

CREATE TABLE diplomants(
 student_fnum BIGINT(12) NOT NULL,
 FOREIGN KEY(student_fnum) REFERENCES students(fnum),
 scientific_field_id INT NOT NULL,
 FOREIGN KEY(scientific_field_id) REFERENCES scientific_fields(id),
 advisor_id INT NOT NULL,
 FOREIGN KEY(advisor_id) REFERENCES professors(id),
 PRIMARY KEY (student_fnum)
 ) ENGINE=InnoDB;

В тази таблица записваме факултетния номер на студент, идентификатор на научната област, в която ще пише дипломна работа и идентификационен номер на преподавателя, който води неговия учебен предмет. Даден преподавател може да работи само в една конкретна научна област, т.е. имаме функционална зависимост advisor_id -> scientific_field_id. В една научна област обаче може да има повече от един преподавател, т.е. в тази таблица нямаме транзитивна зависимост – научната област е определена според факултетния номер на студента, но преподавателя не се определя еднозначно по научната област. Ето едно примерно попълване на таблицата:

+--------------+---------------------+-------------+
| student_fnum | scientific_field_id | advisor_id  |
+--------------+---------------------+-------------+
|         123  |                   1 |          10 |
|         234  |                   1 |          11 |
|         345  |                   2 |          20 |
|         456  |                   2 |          20 |
|         567  |                   2 |          25 |
|         678  |                   3 |          31 |
+--------------+---------------------+-------------+

Проблемът на тази таблица идва от разнопосочния вид информация, която тя носи. От една страна имаме очевидното „студент с определен факултетен номер пише дипломна работа в дадена научна област и е ръководен от конкретен преподавател“ (с него нямаме никакви проблеми), но също така тя носи и втори вид информация за това, че „даден преподавател работи в конкретна научна област“. Например бихме могли да използваме горната таблица, за да кажем, че преподаватели 10 и 11 работят в област 1, преподаватели 20 и 25 в област 2 и преподавател 31 в област 3. Именно тук се появяват аномалии:

  • Ако има преподавател, който все още не е станал ръководител на нито един дипломант, ние не знаем в коя научна област той работи;
  • Ако в примерната таблица изтрием записа за студент 678, ние ще изгубим информацията, че преподавател 31 работи в научна област 3 – налична е аномалия при изтриване;
  • Ако направим INSERT INTO diplomants (student_fnum, scientific_field_id, advisor_id) VALUES (789, 3, 10), ще предизвикаме аномалия при вмъкване на данни – преподавател 10 вече ще работи в области 1 е 3;
  • Аналогично на предишната точка бихме могли да предизвикаме аномалия при промяна на данни, ако променим научната област или advisor_id на даден студент.

Нормалната форма на Boyce-Codd (БКНФ) гласи, че „всяка нетривиална функционална зависимост трябва да зависи от суперключа“.

Нека дадем по-формални дефиниции на видовете ключове:

  • Суперключ наричаме множество от атрибути, които определят уникално всеки запис в релация;
  • Кандидат-ключ наричаме суперключ, който няма свое подмножество от атрибути, което също е суперключ;
  • Първичен ключ наричаме един от избраните кандидат-ключове;
  • Алтернативни ключове наричаме всички кандодат-ключове, които не са избрани за първичен.

За да премахнем описаните в примерната таблица по-горе аномалии трябва да приведем релацията в БКНФ като я разделим на две части по следния начин:

CREATE TABLE diplomants(
 student_fnum BIGINT(12),
 FOREIGN KEY(student_fnum) REFERENCES students(fnum),
 advisor_id INT NOT NULL,
 FOREIGN KEY(advisor_id) REFERENCES professors(id),
 PRIMARY KEY (student_fnum)
 ) ENGINE=InnoDB;

CREATE TABLE advisors_scientific_field_ids(
 advisor_id INT NOT NULL,
 FOREIGN KEY(advisor_id) REFERENCES professors(id),
 scientific_field_id INT NOT NULL,
 FOREIGN KEY(scientific_field_id) REFERENCES scientific_fields(id),
 PRIMARY KEY (advisor_id)
 ) ENGINE=InnoDB;

Нека отбележим, че БКНФ ще бъде нарушена дори да отслабим изискването „един преподавател да води само в една конкретна научна област“. Да, тогава нямаше да има аномалии при изтриване и аномалии при промяна, но първите две аномалии от изброените 4 щаха да продължат да съществуват. В този случай, за да бъде в БКНФ, просто в advisors_scientific_field_ids първичният ключ трябва да се промени на PRIMARY KEY (advisor_id, scientific_field_id).

В крайна сметка виждате, че БКНФ решава частни случаи, които не са покрити от 3НФ. Ако ние не използвахме тази таблица като източник на информация за това „кой преподавател в коя научна област работи“, релацията нямаше да има проблемите, които са описани в БКНФ. Тоест, за разлика от предишните нормални форми, при които правилата бяха ясни и категорични, тук дали една таблица покрива БКНФ или не е малко и плод на тълкуване – зависи много силно от начина, по който ще използваме практически информацията. Имайте предвид, че има случаи, когато една релация НЕ може да бъде нормализирана до БКНФ. Такъв е примерният случай, когато в релация R има следните функционални зависимости: (A, B) -> C и C -> B. Направете пример и обяснете защо е така…

Нека сега въведем още едно ново понятие – множествена зависимост: форма на функционална зависимост, при която едно поле определя два или повече записа на друго поле. Ще бележим това с A->>B. Ето един пример – таблица, в която записваме кой програмист на какъв език за програмиране може да програмира, както и с какви системи за управление на бази от данни може да работи:

CREATE TABLE programmers_knowledge(
 employee_id INT NOT NULL,
 FOREIGN KEY(employee_id) REFERENCES employees(id),
 pl_id INT,
 FOREIGN KEY(pl_id) REFERENCES programming_languages(id),
 dbms_id INT,
 FOREIGN KEY(dbms_id) REFERENCES dbms(id),
 PRIMARY KEY (employee_id, pl_id, dbms_id)
 ) ENGINE=InnoDB;

Тук имаме две множествени зависимости – едната е employee_id ->> pl_id, а другата е employee_id ->> dbms_id. Забележете, че това не са функционални зависимости, защото едно employee_id не определя еднозначно едно pl_id, а определя много (същото е и за dbms_id). Или казано по-просто (от практическа гледна точка) – employee_id определя други полета в тази таблица, но самото то не е UNIQUE, следователно имаме множествени зависимости от employee_id към други полета.

Поотделно множествените зависимости не са проблем – ние например винаги имаме такива при свързващите таблици на връзки М:М, но когато в една таблица имаме две или повече множествени зависимости, тогава може да се получи излишество на данни. Представете си например, че програмист №1 може да програмира на 3 различни езика за програмиране и да работи с 2 системи за управление на бази данни. В таблицата това би се записало по следния начин:

SELECT employee_id, pl_id, dbms_id
FROM programmers
WHERE emplotee_id = 5;
+-------------+-------+---------+
| employee_id | pl_id | dbms_id |
+-------------+-------+---------+
|           5 |     1 |       1 |
|           5 |     3 |       1 |
|           5 |     4 |       1 |
|           5 |     1 |       2 |
|           5 |     3 |       2 |
|           5 |     4 |       2 |
+-------------+-------+---------+

Ето къде е и излишеството на данни – по два пъти сме записали, че програмист 5 програмира на езици 1,3 и 4, както и по три пъти сме записали, че програмист 5 може да работи със СУБД-та 1 и 2. Четвърта нормална форма (4НФ) разрешава този проблем, като казва, че трябва да бъдат премахнати всички независими множествени зависимости.

За да приведем горната таблица в 4НФ трябва да я разделим на две по-малки таблици:

CREATE TABLE programmers_programming_knowledge(
 employee_id INT NOT NULL,
 FOREIGN KEY(employee_id) REFERENCES employees(id),
 pl_id INT NOT NULL,
 FOREIGN KEY(pl_id) REFERENCES programming_languages(id),
 PRIMARY KEY (employee_id, pl_id)
 ) ENGINE=InnoDB;

CREATE TABLE programmers_dbms_knowledge(
 employee_id INT NOT NULL,
 FOREIGN KEY(employee_id) REFERENCES employees(id),
 dbms_id INT NOT NULL,
 FOREIGN KEY(dbms_id) REFERENCES dbms(id),
 PRIMARY KEY (employee_id, dbms_id)
 ) ENGINE=InnoDB;

Така вече примерната информация за програмист №5 ще е в по-малък обем:

+-------------+-------+
| employee_id | pl_id |
+-------------+-------+
|           5 |     1 |
|           5 |     3 |
|           5 |     4 |
+-------------+-------+

+-------------+---------+
| employee_id | dbms_id |
+-------------+---------+
|           5 |       1 |
|           5 |       2 |
+-------------+---------+

 



Добави коментар

Адресът на електронната поща няма да се публикува


*