Нормальні форми відносин (БД)

Етапи розробки бази даних
Метою розробки будь-якої бази даних є зберігання і використовування інформації про яку-небудь предметну область. Для реалізації цієї мети є наступні інструменти:
Реляційна модель даних - зручний спосіб представлення даних предметної області.
Мова SQL - універсальний спосіб маніпулювання такими даними.
Проте очевидно, що для однієї і тієї ж предметної області реляційні відносини можна спроектувати множиною різних способів. Наприклад, можна спроектувати декілька відносин з великою кількістю атрибутів, або навпаки, рознести всі атрибути по великому числу дрібних відносин. Як визначити, по яких ознаках потрібно поміщати атрибути в ті або інші відносини?
У даному розділі розглядаються способи "хорошого" або "правильного" проектування реляційних відносин. Спочатку ми обговоримо, що значить "хороші" або "правильні" моделі даних. Потім будуть введені поняття першою, другою і третьою нормальних форм відносин (1НФ, 2НФ, 3НФ) і показано, що "хорошими" є відносини в третій нормальній формі.
При розробці бази даних звичайно виділяється декілька рівнів моделювання, за допомогою яких відбувається перехід від предметної області до конкретної реалізації бази даних засобами конкретної СУБД. Можна виділити наступні рівні:
Сама предметна область
Модель предметної області
Логічна модель даних
Фізична модель даних
Власне база даних і додатки
Предметна область - це частина реального світу, дані про яку ми хочемо відобразити в базі даних. Наприклад, як предметна область можна вибрати бухгалтерію якого-небудь підприємства, відділ кадрів, банк, магазин і т.д. Предметна область нескінченна і містить як істотно важливі поняття і дані, так і малозначні або взагалі не значущі дані. Так, якщо як предметна область вибрати облік товарів на складі, то поняття "накладна" і "рахунок-фактура" є істотно важливими поняттями, а то, що співробітниця, що приймає накладні, має два дітей - це для обліку товарів неважливо. Проте, з погляду відділу кадрів дані про наявність дітей є істотно важливими. Таким чином, важливість даних залежить від вибору предметної області.
Модель предметної області. Модель предметної області - це наші знання про предметну область. Знання можуть бути як у вигляді неформальних знань в мозку експерта, так і виражені формально за допомогою яких-небудь засобів. Як такі засоби можуть виступати текстові описи предметної області, набори посадових інструкцій, правила ведення справ в компанії і т.п. Досвід показує, що текстовий спосіб представлення моделі предметної області украй неефективний. Набагато більш інформативними і корисними при розробці баз даних є описи предметної області, виконані за допомогою спеціалізованих графічних нотацій. Є велика кількість методик опису предметної області. З найвідоміших можна назвати методику структурного аналізу SADT і засновану на ньому IDEF0, діаграми потоків даних Гейна-Сарсона, методику об'єктно-орієнтованого аналізу UML, і ін. Модель предметної області описує швидше процеси, що відбуваються в предметній області і дані, що використовуються цими процесами. Від того, наскільки правильно змодельована предметна область, залежить успіх подальшої розробки додатків.
Логічна модель даних. На наступному, більш низькому рівні знаходиться логічна модель даних предметної області. Логічна модель описує поняття предметної області, їх взаємозв'язок, а також обмеження на дані, що накладаються предметною областю. Приклади понять - "співробітник", "відділ", "проект", "зарплата". Приклади взаємозв'язків між поняттями - "співробітник числиться рівно в одному відділі", "співробітник може виконувати декілька проектів", "над одним проектом може працювати декілька співробітників". Приклади обмежень - "вік співробітника не менше 16 і не більше 60 років".
Логічна модель даних є початковим прототипом майбутньої бази даних. Логічна модель будується в термінах інформаційних одиниць, але без прив'язки до конкретної СУБД. Більш того, логічна модель даних необов'язково повинна бути виражена засобами саме реляційної моделі даних. Основним засобом розробки логічної моделі даних зараз є різні варіанти ER-діаграм (Entity-Relationship, діаграми сутність-зв'язок). Одну і ту ж ER-модель можна перетворити як в реляційну модель даних, так і в модель даних для ієрархічних і мережних СУБД, або в постреляційну модель даних. Проте, оскільки ми розглядаємо саме реляційні СУБД, то можна вважати, що логічна модель даних для нас формулюється в термінах реляційної моделі даних.
Рішення, прийняті на попередньому рівні, при розробці моделі предметної області, визначають деякі межі, в межах яких можна розвивати логічну модель даних, в межах же цих меж можна ухвалювати різні рішення. Наприклад, модель предметної області складського обліку містить поняття "склад", "накладна", "товар". При розробці відповідної реляційної моделі ці терміни обов'язково повинні бути використані, але різних способів реалізації тут багато - можна створити одне відношення, в якому будуть присутні як атрибути "склад", "накладна", "товар", а можна створити три окремі відношення, поодинці на кожне поняття.
При розробці логічної моделі даних виникають питання: чи добре спроектовані відносини? Чи правильно вони відображають модель предметної області, а отже і саму предметну область?
Фізична модель даних. На ще більш низькому рівні знаходиться фізична модель даних. Фізична модель даних описує дані засобами конкретної СУБД. Ми вважатимемо, що фізична модель даних реалізована засобами саме реляційної СУБД, хоча, як вже сказано вище, це необов'язково. Відносини, розроблені на стадії формування логічної моделі даних, перетворяться в таблиці, атрибути стають стовпцями таблиць, для ключових атрибутів створюються унікальні індекси, домени перетворюються в типи даних, прийняті в конкретній СУБД.
Обмеження, що є в логічній моделі даних, реалізуються різними засобами СУБД, наприклад, за допомогою індексів, декларативних обмежень цілісності, трігерів, ззбережених процедур. При цьому знову-таки рішення, прийняті на рівні логічного моделювання визначають деякі межі, в межах яких можна розвивати фізичну модель даних. Точно також, в межах цих меж можна ухвалювати різні рішення. Наприклад, відносини, що містяться в логічній моделі даних, повинні бути перетворені в таблиці, але для кожної таблиці можна додатково оголосити різні індекси, що підвищують швидкість звернення до даних. Багато що тут залежить від конкретної СУБД.
При розробці фізичної моделі даних виникають питання: чи добре спроектовані таблиці? Чи правильно вибрані індекси? Наскільки багато програмного коду у вигляді трігерів і ззбережених процедур необхідно розробити для підтримки цілісності даних?
Власне база даних і додатки. І, нарешті, як результат попередніх етапів з'являється власне сама база даних. База даних реалізована на конкретній програмно-апаратній основі, і вибір цієї основи дозволяє істотно підвищити швидкість роботи з базою даних. Наприклад, можна вибирати різні типи комп'ютерів, міняти кількість процесорів, об'єм оперативної пам'яті, дискові підсистеми і т.п. Дуже велике значення має також настройка СУБД в межах вибраної програмно-апаратної платформи.
Але знову рішення, прийняті на попередньому рівні - рівні фізичного проектування, визначають межі, в межах яких можна ухвалювати рішення по вибору програмно-апаратної платформи і настройки СУБД.
Таким чином ясно, що рішення, прийняті на кожному етапі моделювання і розробки бази даних, позначатимуться на подальших етапах. Тому особливу роль грає ухвалення правильних рішень на ранніх етапах моделювання.
Критерії оцінки якості логічної моделі даних
Мета даного розділу - описати деякі принципи побудови хороших логічних моделей даних. Хороших в тому значенні, що рішення, прийняті в процесі логічного проектування приводили б до хороших фізичних моделей і зрештою до хорошої роботи бази даних.
Для того, щоб оцінити якість ухвалюваних рішень на рівні логічної моделі даних, необхідно сформулювати деякі критерії якості в термінах фізичної моделі і конкретної реалізації і подивитися, як різні рішення, прийняті в процесі логічного моделювання, впливають на якість фізичної моделі і на швидкість роботи бази даних.
Звичайно, таких критеріїв може бути дуже багато і вибір їх достатньою мірою довільний. Ми розглянемо деякі з таких критеріїв, які є безумовно важливими з погляду отримання якісної бази даних:
Адекватність бази даних предметної області
Легкість розробки і супроводу бази даних
Швидкість виконання операцій оновлення даних (вставка, оновлення, видалення кортежів)
Швидкість виконання операцій вибірки даних
Адекватність бази даних предметної області
База даних повинна адекватно відображати предметну область. Це означає, що повинні виконуватися наступні умови:
Полягання бази даних в кожний момент часу повинне відповідати поляганню предметної області.
Зміна полягання предметної області повинна приводити до відповідної зміни полягання бази даних
Обмеження предметної області, відображені в моделі предметної області, повинні деяким чином відображатися і враховуватися базі даних.
Легкість розробки і супроводу бази даних
Практично будь-яка база даних, за винятком абсолютно елементарних, містить деяку кількість програмного коду у вигляді трігерів і ззбережених процедур.
Збережені процедури - це процедури і функції, що збережуться безпосередньо в базі даних у вигляді, що відкомпілювався, і які можуть запускатися користувачами або додатками, що працюють з базою даних. Збережені процедури звичайно пишуться або на спеціальному процедурному розширенні мови SQL (наприклад, PL/SQL для ORACLE або Transact-SQL для MS SQL Server), або на деякій універсальній мові програмування, наприклад, C++, з включенням в код операторів SQL відповідно до спеціальних правил такого включення. Основне призначення ззбережених процедур - реалізація бізнес-процесів предметної області.
Трігери - це збережені процедури, пов'язані з деякими подіями, що відбуваються під час роботи бази даних. Як такі події виступають операції вставки, оновлення і видалення рядків таблиць. Якщо в базі даних визначений деякий трігер, то він запускається автоматично завжди при виникненні події, з якою цей трігер зв'язаний. Дуже важливим є те, що користувач не може обійти трігер. Трігер спрацьовує незалежно від того, хто з користувачів і яким способом ініціював подію, що викликала запуск трігера. Таким чином, основне призначення трігерів - автоматична підтримка цілісності бази даних. Трігери можуть бути як достатньо простими, наприклад, підтримуючими посилальну цілісність, так і досить складними, реалізовуючими які-небудь складні обмеження предметної області або складні дії, які повинні відбутися при настанні деяких подій. Наприклад, з операцією вставки нового товару в накладну може бути зв'язаний трігер, який виконує наступні дії - перевіряє, чи є необхідна кількість товару, за наявності товару додає його в накладну і зменшує дані про наявність товару на складі, за відсутності товару формує замовлення на поставку бракуючого товару і тут же посилає замовлення по електронній пошті постачальнику.
Очевидно, що чим більше за програмний код у вигляді трігерів і ззбережених процедур містить база даних, тим складніше її розробка і подальший супровід.
Швидкість операцій оновлення даних (вставка, оновлення, видалення)
На рівні логічного моделювання ми визначаємо реляційні відносини і атрибути цих відносин. На цьому рівні ми не можемо визначати які-небудь фізичні структури зберігання (індекси, хешування і т.п.). Єдине, ніж ми можемо управляти - це розподілом атрибутів по різних відносинах. Можна описати мало відносин з великою кількістю атрибутів, або багато відносин, кожне з яких містить мало атрибутів. Таким чином, необхідно спробувати відповісти на питання - чи впливає кількість відносин і кількість атрибутів у відносинах на швидкість виконання операцій оновлення даних. Таке питання, звичайно, не є достатньо коректним, оскільки швидкість виконання операцій з базою даних сильно залежить від фізичної реалізації бази даних. Проте, спробуємо якісно оцінити цей вплив при однакових підходах до фізичного моделювання.
Основними операціями, що змінюють полягання бази даних, є операції вставки, оновлення і видалення записів. В базах даних, що вимагають постійних змін (складський облік, системи продажів квитків і т.п.) продуктивність визначається швидкістю виконання великої кількості невеликих операцій вставки, оновлення і видалення.
Розглянемо операцію вставки запису в таблицю. Вставка запису проводиться в одну з вільних сторінок пам'яті, виділеної для даної таблиці. СУБД постійно збереже інформацію про наявність і розташування вільних сторінок. Якщо для таблиці не створені індекси, то операція вставки виконується фактично з однаковою швидкістю незалежно від розміру таблиці і від кількості атрибутів в таблиці. Якщо в таблиці є індекси, то при виконанні операції вставки запису індекси повинні бути перебудовані. Таким чином, швидкість виконання операції вставки зменшується при збільшенні кількості індексів біля таблиці і мало залежить від числа рядків в таблиці.
Розглянемо операції оновлення і видалення записів з таблиці. Перш, ніж відновити або видалити запис, її необхідно знайти. Якщо таблиця не індексована, то єдиним способом пошуку є послідовне сканування таблиці в пошуку потрібного запису. В цьому випадку, швидкість операцій оновлення і видалення істотно збільшується із збільшенням кількості записів в таблиці і не залежить від кількості атрибутів. Але насправді неіндексовані таблиці практично ніколи не використовуються. Для кожної таблиці звичайно оголошується один або декілька індексів, відповідний потенційним ключам. За допомогою цих індексів пошук запису проводиться дуже швидко і практично не залежить від кількості рядків і атрибутів в таблиці (хоча, звичайно, деяка залежність є). Якщо для таблиці оголошено декілька індексів, то при виконанні операцій оновлення і видалення ці індекси повинні бути перебудовані, на що витрачається додатковий час. Таким чином, швидкість виконання операцій оновлення і видалення також зменшується при збільшенні кількості індексів біля таблиці і мало залежить від числа рядків в таблиці.
Можна припустити, що чим більше за атрибути має таблиця, тим більше для неї буде оголошено індексів. Ця залежність, звичайно, не пряма, але при однакових підходах до фізичного моделювання звичайно так і відбувається. Таким чином, можна прийняти допущення, що ніж більше атрибутів мають відносини, розроблені в ході логічного моделювання, тим повільніше виконуватимуться операції оновлення даних, за рахунок витрати часу на перебудову більшої кількості індексів.
Додаткові міркування на користь приведеної тези про уповільнення виконання операцій оновлення даних (вплив журналізації, довжини рядків таблиць) приведені в роботі А.Прохорова [27].
Швидкість операцій вибірки даних
Одне з призначень бази даних - надання інформації користувачам. Інформація витягується з реляційної бази даних за допомогою оператора SQL - SELECT. Однією з найдорожчих операцій при виконанні оператора SELECT є операція з'єднання таблиць. Таким чином, чим більше за взаємозв'язані відносини було створено в ході логічного моделювання, тим більше вірогідність того, що при виконанні запитів ці відносини з'єднуватимуться, і, отже, тим повільніше виконуватимуться запити. Таким чином, збільшення кількості відносин приводить до уповільнення виконання операцій вибірки даних, особливо, якщо запити наперед невідомі.
Основний приклад
Розглянемо як предметна область деяку організацію, що виконує деякі проекти. Модель предметної області опишемо наступним неформальним текстом:
Співробітники організації виконують проекти.
Проекти складаються з декількох завдань.
Кожний співробітник може брати участь в одному або декількох проектах, або тимчасово не брати участь ні в яких проектах.
Над кожним проектом може працювати декілька співробітників, або тимчасово проект може бути припинений, тоді над ним не працює жоден співробітник.
Над кожним завданням в проекті працює рівно один співробітник.
Кожний співробітник числиться в одному відділі.
Кожний співробітник має телефон, що знаходиться у відділі співробітника.
У ході додаткового уточнення того, які дані необхідно враховувати, з'ясувалося наступне:
Про кожного співробітника необхідно зберігати табельний номер і прізвище. Табельний номер є унікальним для кожного співробітника.
Кожний відділ має унікальний номер.
Кожний проект має номер і найменування. Номер проекту є унікальним.
Кожна робота з проекту має номер, унікальний в межах проекту. Роботи в різних проектах можуть мати однакові номери.
1НФ (Перша Нормальна Форма)
Поняття першої нормальної форми вже обговорювалося на чолі 2. Перша нормальна форма (1НФ) - це звичне відношення. Згідно нашому визначенню відносин, будь-яке відношення автоматично вже знаходиться в 1НФ. Нагадаємо стисло властивості відносин (це і будуть властивості 1НФ):
У відношенні немає однакових кортежів.
Кортежі не впорядковані.
Атрибути не впорядковані і розрізняються по найменуванню.
Всі значення атрибутів атомарні.
У ході логічного моделювання на першому кроці запропоновано берегти дані в одному відношенні, що має наступні атрибути:
СПІВРОБІТНИКИ_ВІДДІЛИ_ПРОЕКТИ (Н_СПІВ, ПРІЗВ, №_ВІДД, ТЕЛ, №_ПРО, ПРОЕКТ, Н_ЗАВД)
де
Н_СПІВ - табельний номер співробітника
ПРІЗВ - прізвище співробітника
Н_ВІД - номер відділу, в якому числиться співробітник
ТЕЛ - телефон співробітника
Н_ПРО - номер проекту, над яким працює співробітник
ПРОЕКТ - найменування проекту, над яким працює співробітник
Н_ЗАВД - номер завдання, над яким працює співробітник
Оскільки кожний співробітник в кожному проекті виконує рівно одне завдання, то як потенційний ключ відношення необхідно узяти пару атрибутів {Н_СПІВ, Н_ПРО}.
У нинішній момент полягання предметної області відображається наступними фактами:
Співробітник Іванов, що працює в 1 відділі, виконує в першому проекті "Космос" завдання 1 і в другому проекті "Клімат" завдання 1.
Співробітник Петров, що працює в 1 відділі, виконує в першому проекті "Космос" завдання 2.
Співробітник Сидоров, що працює в 2 відділі, виконує в першому проекті "Космос" завдання 3 і в другому проекті "Клімат" завдання 2.
Це полягання відображається в таблиці (курсивом виділені ключові атрибути):
Н_СПІВР | ПРІЗВ | Н_ВІД | ТЕЛ | Н_ПРО | ПРОЕКТ | Н_ЗАВД
1 | Іванов | 1 | 11-22-33 | 1 | Космос | 1
1 | Іванов | 1 | 11-22-33 | 2 | Климат | 1
2 | Петров | 1 | 11-22-33 | 1 | Космос | 2
3 | Сидоров | 2 | 33-22-11 | 1 | Космос | 3
3 | Сидоров | 2 | 33-22-11 | 2 | Климат | 2
Таблиця 1 Відношення СПІВРОБІТНИКИ_ВІДДІЛИ_ПРОЕКТИ
Аномалії оновлення
Навіть одного погляду на таблицю відношення СПІВРОБІТНИКИ_ВІДДІЛИ_ПРОЕКТИ достатньо, щоб побачити, що дані збережуться в ній з великою надлишковістю. В багатьох рядках повторюються прізвища співробітників, номери телефонів, найменування проектів. Крім того, в даному відношенні збережуться разом незалежні один від одного дані - і дані про співробітників, і про відділи, і про проекти, і про роботи за проектами. Поки ніяких дій з відношенням не проводиться, це не страшно. Але як тільки полягання предметної області змінюється, то, при спробах відповідним чином змінити полягання бази даних, виникає велика кількість проблем.
Історично ці проблеми одержали назву аномалії оновлення. Спроби дати строге поняття аномалії в базі даних не є цілком задовільними [51, 7]. В даних роботах аномалії визначені як суперечність між моделлю предметної області і фізичною моделлю даних, підтримуваних засобами конкретної СУБД. "Аномалії виникають у тому випадку, коли наші знання про предметну область виявляються, з якихось причин, невимовними в схемі БД або що входять в суперечність з нею" [7]. Ми дотримуємося іншої точки зору, що полягає в тому, що аномалій в значенні визначень згаданих авторів немає, а є або неадекватність моделі даних предметної області, або деякі додаткові труднощі в реалізації обмежень предметної області засобами СУБД. Більш глибоке обговорення проблеми строгого визначення поняття аномалій виходить за межі даної роботи.
Таким чином, ми дотримуватимемося інтуїтивного поняття аномалії як неадекватності моделі даних предметної області, (що говорить насправді про те, що логічна модель даних просто невірна!) або як необхідності додаткових зусиль для реалізації всіх обмежень визначених в предметній області (додатковий програмний код у вигляді трігерів або ззбережених процедур).
Оскільки аномалії проявляють себе при виконанні операцій, що змінюють полягання бази даних, то розрізняють наступні види аномалій:
Аномалії вставки (INSERT)
Аномалії оновлення (UPDATE)
Аномалії видалення (DELETE)
Відносно СПІВРОБІТНИКИ_ВІДДІЛИ_ПРОЕКТИ можна привести приклади наступних аномалій:
Аномалії вставки (INSERT)
У відношення СПІВРОБІТНИКИ_ВІДДІЛИ_ПРОЕКТИ не можна вставити дані про співробітника, який поки не бере участь ні в одному проекті. Дійсно, якщо, наприклад, в другому відділі з'являється новий співробітник, скажімо, Хутровиків, і він поки не бере участь ні в одному проекті, то ми повинні вставити у відношення кортеж (4, Хутровиків, 2, 33-22-11, null, null, null). Це зробити неможливо, оскільки атрибут Н_ПРО (номер проекту) входить до складу потенційного ключа, і, отже, не може містити null-значень.
Точно також не можна вставити дані про проект, над яким поки не працює жоден співробітник.
Причина аномалії - зберігання в одному відношенні різнорідної інформації (і про співробітників, і про проекти, і про роботи за проектом).
Висновок - логічна модель даних неадекватна моделі предметної області. База даних, заснована на такій моделі, працюватиме неправильно.
Аномалії оновлення (UPDATE)
Прізвища співробітників, найменування проектів, номери телефонів повторюються в багатьох кортежах відношення. Тому якщо співробітник міняє прізвище, або проект міняє найменування, або міняється номер телефону, то такі зміни необхідно одночасно виконати у всіх місцях, де це прізвище, найменування або номер телефону зустрічаються, інакше відношення стане некоректним (наприклад, один і той же проект в різних кортежах називатиметься по-різному). Таким чином, оновлення бази даних однією дією реалізувати неможливо. Для підтримки відношення в цілісному стані необхідно написати трігер, який при оновленні одного запису коректно виправляв би дані і в інших місцях.
Причина аномалії - надмірність даних, також породжена тим, що в одному відношенні збережеться різнорідна інформація.
Висновок - збільшується складність розробки бази даних. База даних, заснована на такій моделі, працюватиме правильно тільки за наявності додаткового програмного коду у вигляді трігерів.
Аномалії видалення (DELETE)
При видаленні деяких даних може відбутися втрата іншої інформації. Наприклад, якщо закрити проект "Космос" і видалити всі рядки, в яких він зустрічається, то будуть втрачені всі дані про співробітника Петрове. Якщо видалити співробітника Сидорова, то буде втрачена інформація про те, що у відділі номер 2 знаходиться телефон 33-22-11. Якщо за проектом тимчасово припинені роботи, то при видаленні даних про роботи за цим проектом будуть видалені і дані про самий проект (найменування проекту). При цьому якщо був співробітник, який працював тільки над цим проектом, то будуть втрачені і дані про цього співробітника.
Причина аномалії - зберігання в одному відношенні різнорідної інформації (і про співробітників, і про проекти, і про роботи за проектом).
Висновок - логічна модель даних неадекватна моделі предметної області. База даних, заснована на такій моделі, працюватиме неправильно.
Функціональні залежності
Відношення СПІВРОБІТНИКИ_ВІДДІЛИ_ПРОЕКТИ знаходиться в 1НФ, при цьому, як було показано вище, логічна модель даних не адекватна моделі предметної області. Таким чином, першої нормальної форми недостатньо для правильного моделювання даних.
Визначення функціональної залежності
Для усунення вказаних аномалій (а насправді для правильного проектування моделі даних!) застосовується метод нормалізації відносин. Нормалізація заснована на понятті функціональної залежності атрибутів відношення.
Визначення 1. Хай - відношення. Безліч атрибутів функціонально залежно від безлічі атрибутів ( функціонально визначає ) тоді і тільки тоді, коли для будь-якого полягання відношення для будь-яких кортежів з того, що слідує що (тобто у всіх кортежах, що мають однакові значення атрибутів , значення атрибутів також співпадають в будь-якому поляганні відносини ). Символічно функціональна залежність записується
.
Безліч атрибутів називається детермінантом функціональної залежності, а безліч атрибутів називається залежною частиною.
Зауваження. Якщо атрибути складають потенційний ключ відношення , то будь-який атрибут відношення функціонально залежить від .
Приклад 1. Відносно СПІВРОБІТНИКИ_ВІДДІЛИ_ПРОЕКТИ можна привести наступні приклади функціональних залежностей:
Залежність атрибутів від ключа відношення:
{ Н_СПІВ, Н_ПРО} ПРІЗВ
{ Н_СПІВ, Н_ПРО} Н_ВІД
{ Н_СПІВ, Н_ПРО} ТЕЛ
{ Н_СПІВ, Н_ПРО} ПРОЕКТ
{Н_СПІВ, Н_ПРО} Н_ЗАВД
Залежність атрибутів, що характеризують співробітника від табельного номера співробітника:
Н_СПІВ ПРІЗВ
Н_СПІВ Н_ВІД
Н_СПІВ ТЕЛ
Залежність найменування проекту від номера проекту:
Н_ПРО ПРОЕКТ
Залежність номера телефону від номера відділу:
Н_ВІД ТЕЛ
Зауваження. Приведені функціональні залежності не виведені із зовнішнього вигляду відношення, приведеного в таблиці 1. Ці залежності відображають взаємозв'язки, знайдені між об'єктами предметної області і є додатковими обмеженнями, визначуваними предметною областю. Таким чином, функціональна залежність - семантичне поняття. Вона виникає, коли по значеннях одних даних в предметній області можна визначити значення інших даних. Наприклад, знаючи табельний номер співробітника, можна визначити його прізвище, по номеру відділу можна визначити телефону. Функціональна залежність задає додаткові обмеження на дані, які можуть зберігатися у відносинах. Для коректності бази даних необхідно при виконанні операцій модифікації бази даних перевіряти всі обмеження, визначені функціональними залежностями.
Функціональні залежності відносин і математичне поняття функціональної залежності
Функціональна залежність атрибутів відношення нагадує поняття функціональної залежності в математиці. Але це не одне і те ж. Для порівняння нагадаємо математичне поняття функціональної залежності:
Визначення 2. Функціональна залежність (функція) - це трійка об'єктів , де
- множина (область визначення)
- множина (безліч значень)
- правило, згідно якому кожному елементу ставиться у відповідність один і лише один елемент (правило функціональної залежності).
Функціональна залежність звичайно позначається як або .
Зауваження. Правило може бути задано будь-яким способом - у вигляді формули (частіше всього), за допомогою таблиці значень, за допомогою графіка, текстовим описом і т.д.
Функціональна залежність атрибутів відношення теж нагадує це визначення. Дійсно:
Як область визначення виступає домен, на якому визначений атрибут (або декартовий твір доменів, якщо є множиною атрибутів)
Як безліч значень виступає домен, на якому визначений атрибут (або декартовий твір доменів)
Правило реалізується наступним алгоритмом - 1) по даному значенню атрибуту знайти будь-який кортеж відношення, що містить це значення, 2) значення атрибуту у цьому кортежі і буде значенням функціональної залежності, відповідним даному . Визначення функціональної залежності у відношенні гарантує, що знайдене значення не залежить від вибору кортежу, тому правило
визначено коректно.
Відмінність від математичного поняття відношення полягає в тому, що, якщо розглядати математичне поняття функції, то для фіксованого значення відповідне значення функції завжди одне і те ж. Наприклад, якщо задана функція , то для значення відповідне значення завжди буде рівно 4. В протилежність цьому у відносинах значення залежного атрибуту може приймати різні значення в різних поляганнях бази даних. Наприклад, атрибут ПРІЗВ функціонально залежить від атрибуту Н_СПІВ. Припустимо, що зараз співробітник з табельним номером 1 має прізвище Іванов, тобто при значенні детермінанта рівного 1, значення залежного аргументу рівне "Іванов". Але співробітник може змінити прізвище, наприклад на "Сидоров". Тепер при тому ж значенні детермінанта, рівного 1, значення залежного аргументу рівне "Сидоров".
Таким чином, поняття функціональної залежності атрибутів не можна вважати повністю еквівалентним математичному поняттю функціональної залежності, оскільки значення цієї залежності різні при різних поляганнях відношення, і, найголовніше, ці значення можуть мінятися непередбачувано.
Функціональна залежність атрибутів затверджує лише те, що для кожного конкретного полягання бази даних по значенню одного атрибуту (детермінанта) можна однозначно визначити значення іншого атрибуту (залежної частини). Але конкретні значення залежної частини можуть бути різні в різних поляганнях бази даних.
2НФ (Друга Нормальна Форма)
Визначення 3. Відношення знаходиться в другій нормальній формі (2НФ) тоді і тільки тоді, коли відношення знаходиться в 1НФ і немає неключових атрибутів, залежних від частини складного ключа. (Неключовий атрибут - це атрибут, що не входить до складу ніякого потенційного ключа).
Зауваження. Якщо потенційний ключ відношення є простим, то відношення автоматично знаходиться в 2НФ.
Відношення СПІВРОБІТНИКИ_ВІДДІЛИ_ПРОЕКТИ не знаходиться в 2НФ, оскільки є атрибути, залежні від частини складного ключа:
Залежність атрибутів, що характеризують співробітника від табельного номера співробітника є залежністю від частини складного ключа:
Н_СПІВ ПРІЗВ
Н_СПІВ Н_ВІД
Н_СПІВ ТЕЛ
Залежність найменування проекту від номера проекту є залежністю від частини складного ключа:
Н_ПРО ПРОЕКТ
Для того, щоб усунути залежність атрибутів від частини складного ключа, потрібно провести декомпозицію відношення на декілька відносин. При цьому ті атрибути, які залежать від частини складного ключа, виносяться в окреме відношення.
Відношення СПІВРОБІТНИКИ_ВІДДІЛИ_ПРОЕКТИ декомпозуємо на три відношення - СПІВРОБІТНИКИ_ВІДДІЛИ, ПРОЕКТИ, ЗАВДАННЯ.
Відношення СПІВРОБІТНИКИ_ВІДДІЛИ (Н_СПІВ, ПРІЗВ, Н_ВІД, ТЕЛ):
Функціональні залежності:
Залежність атрибутів, що характеризують співробітника від табельного номера співробітника:
Н_СПІВ ПРІЗВ
Н_СПІВ Н_ВІД
Н_СПІВ ТЕЛ
Залежність номера телефону від номера відділу:
Н_ВІД ТЕЛ
Н_СПІВ | ПРІЗВ | Н_ВІД | ТЕЛ
1 | Іванов | 1 | 11-22-33
2 | Петров | 1 | 11-22-33
3 | Сидоров | 2 | 33-22-11
Таблиця 2 Відношення СПІВРОБІТНИКИ_ВІДДІЛИ
Відношення ПРОЕКТИ (Н_ПРО, ПРОЕКТ):
Функціональні залежності:
Н_ПРО ПРОЕКТ
Н_ПРО | ПРОЕКТ
1 | Космос
2 | Клімат
Таблиця 3 Відношення ПРОЕКТИ
Відношення ЗАВДАННЯ (Н_СПІВ, Н_ПРО, Н_ЗАВД):
Функціональні залежності:
{Н_СПІВ, Н_ПРО} Н_ЗАВД
Н_СПІВ | Н_ПРО | Н_ЗАВД
1 | 1 | 1
1 | 2 | 1
2 | 1 | 2
3 | 1 | 3
3 | 2 | 2
Таблиця 4 Відношення ЗАВДАННЯ
Аналіз декомпозованих відносин
Відносини, одержані в результаті декомпозиції, знаходяться в 2НФ. Дійсно, відносини СПІВРОБІТНИКИ_ВІДДІЛИ і ПРОЕКТИ мають прості ключі, отже автоматично знаходяться в 2НФ, відношення ЗАВДАННЯ має складний ключ, але єдиний неключовий атрибут Н_ЗАВД функціонально залежить від всього ключа {Н_СПІВ, Н_ПРО}.
Частина аномалій оновлення усунена. Так, дані про співробітників і проекти тепер збережуться в різних відносинах, тому при появі співробітників, що не беруть участь ні в одному проекті просто додаються кортежі у відношення СПІВРОБІТНИКИ_ВІДДІЛИ. Точно також, при появі проекту, над яким не працює жоден співробітник, просто вставляється кортеж у відношення ПРОЕКТИ.
Прізвища співробітників і найменування проектів тепер збережуться без надмірності. Якщо співробітник змінить прізвище або проект змінить найменування, то таке оновлення буде вироблено в одному місці.
Якщо за проектом тимчасово припинені роботи, але вимагається, щоб сам проект зберігся, то для цього проекту віддаляються відповідні кортежі відносно ЗАВДАННЯ, а дані про самий проект і дані про співробітників, що брали участь в проекті, залишаються у відносинах ПРОЕКТИ і СОТРУДНикІ_ОТДЕЛИ.
Проте, частину аномалій дозволити не вдалося.
Аномалії вставки, що залишилися (INSERT)
У відношення СПІВРОБІТНИКИ_ВІДДІЛИ не можна вставити кортеж (4, Хутровиків, 1, 33-22-11), оскільки при цьому вийде, що два співробітники з 1-го відділу (Іванов і Хутровиків) мають різні номери телефонів, а це суперечить моделі предметної області. В цій ситуації можна запропонувати два рішення, залежно від того, що реально відбулося в предметній області. Інший номер телефону може бути введений з двох причин - помилково людини, що вводить дані про нового співробітника, або тому що номер у відділі дійсно змінився. Тоді можна написати трігер, який при вставці запису про співробітника перевіряє, чи співпадає телефон з вже наявним телефоном у іншого співробітника цього ж відділу. Якщо номери відрізняються, то система повинна поставити питання, чи залишити старий номер у відділі або замінити його новим. Якщо потрібно залишити старий номер (новий номер введений помилково), то кортеж з даними про нового співробітника буде вставлений, але номер телефону буде у нього буде той, який вже є у відділі (в даному випадку, 11-22-33). Якщо ж номер у відділі дійсно змінився, то кортеж буде вставлений з новим номером, і будуть одночасно змінені номери телефонів у всіх співробітників цього ж відділу. І в тому і в іншому випадку не обійтися без розробки громіздкого трігера.
Причина аномалії - надмірність даних, породжена тим, що в одному відношенні збережеться різнорідна інформація (про співробітників і про відділи).
Висновок - збільшується складність розробки бази даних. База даних, заснована на такій моделі, працюватиме правильно тільки за наявності додаткового програмного коду у вигляді трігерів.
Аномалії оновлення, що залишилися (UPDATE)
Одні і ті ж номери телефонів повторюються в багатьох кортежах відношення. Тому якщо у відділі міняється номер телефону, то такі зміни необхідно одночасно виконати у всіх місцях, де цей номер телефону зустрічаються, інакше відношення стане некоректним. Таким чином, оновлення бази даних однією дією реалізувати неможливо. Необхідно написати трігер, який при оновленні одного запису коректно виправляє номери телефонів в інших місцях.
Причина аномалії - надмірність даних, також породжена тим, що в одному відношенні збережеться різнорідна інформація.
Висновок - збільшується складність розробки бази даних. База даних, заснована на такій моделі, працюватиме правильно тільки за наявності додаткового програмного коду у вигляді трігерів.
Аномалії видалення, що залишилися (DELETE)
При видаленні деяких даних і надалі може відбутися втрата іншої інформації. Наприклад, якщо видалити співробітника Сидорова, то буде втрачена інформація про те, що у відділі номер 2 знаходиться телефон 33-22-11.
Причина аномалії - зберігання в одному відношенні різнорідної інформації (і про співробітників, і про відділи).
Висновок - логічна модель даних неадекватна моделі предметної області. База даних, заснована на такій моделі, працюватиме неправильно.
Помітимо, що при переході до другої нормальної форми відношення сталі майже адекватними предметній області. Залишилися також труднощі в розробці бази даних, пов'язані з необхідністю написання трігерів, що підтримують цілісність бази даних. Ці труднощі тепер пов'язані тільки з одним відношенням СОТРУДНикІ_ОТДЕЛИ.
3НФ (Третя Нормальна Форма)
Визначення 4. Атрибути називаються взаємно незалежними, якщо жоден з них не є функціонально залежним від іншого.
Визначення 5. Відношення знаходиться в третій нормальній формі (3НФ) тоді і тільки тоді, коли відношення знаходиться в 2НФ і всі неключові атрибути взаємно незалежні.
Відношення СОТРУДНикІ_ОТДЕЛИ не знаходиться в 3НФ, оскільки є функціональна залежність неключових атрибутів (залежність номера телефону від номера відділу):
Н_ВІД ТЕЛ
Для того, щоб усунути залежність неключових атрибутів, потрібно провести декомпозицію відношення на декілька відносин. При цьому ті неключові атрибути, які є залежними, виносяться в окреме відношення.
Відношення СПІВРОБІТНИКИ_ВІДДІЛИ декомпозуємо на два відношення - СПІВРОБІТНИКИ, ВІДДІЛИ.
Відношення СПІВРОБІТНИКИ (Н_СПІВ, ПРІЗВ, Н_ВІД):
Функціональні залежності:
Залежність атрибутів, що характеризують співробітника від табельного номера співробітника:
Н_СПІВ ПРІЗВ
Н_СПІВ Н_ВІД
Н_СПІВ ТЕЛ
Н_СПІВ | ПРІЗВ | Н_ВІД
1 | Іванов | 1
2 | Петров | 1
3 | Сидоров | 2
Таблиця 5 Відношення СПІВРОБІТНИКИ
Відношення ВІДДІЛИ (Н_ВІД, ТЕЛ):
Функціональні залежності:
Залежність номера телефону від номера відділу:
Н_ВІД ТЕЛ
Н_ВІД | ТЕЛ
1 | 11-22-33
2 | 33-22-11
Таблиця 6 Відношення ВІДДІЛИ
Звернемо увагу на те, що атрибут Н_ВІД, що не був ключовим відносно СПІВРОБІТНИКИ, ВІДДІЛИ, стає потенційним ключем у відношенні ВІДДІЛИ. Саме за рахунок цього усувається надмірність, пов'язана з багатократним зберіганням одних і тих же номерів телефонів.
Висновок. Таким чином, всі знайдені аномалії оновлення усунені. Реляційна модель, що складається з чотирьох відносин СПІВРОБІТНИКИ, ВІДДІЛИ, ПРОЕКТИ, ЗАВДАННЯ, що знаходяться в третій нормальній формі, є адекватній описаній моделі предметної області, і вимагає наявності тільки тих трігерів, які підтримують посилальну цілісність. Такі трігери є стандартними і не вимагають великих зусиль в розробці.
Алгоритм нормалізації (приведення до 3НФ)
Отже, алгоритм нормалізації (тобто алгоритм приведення відносин до 3НФ) описується таким чином.
Крок 1 (Приведення до 1НФ). На першому кроці задається одне або декілька відносин, що відображають поняття предметної області. По моделі предметної області (не за зовнішнім виглядом одержаних відносин!) виписуються знайдені функціональні залежності. Всі відносини автоматично знаходяться в 1НФ.
Крок 2 (Приведення до 2НФ). Якщо в деяких відносинах знайдена залежність атрибутів від частини складного ключа, то проводимо декомпозицію цих відносин на декілька відносин таким чином: ті атрибути, які залежать від частини складного ключа виносяться в окреме відношення разом з цією частиною ключа. В початковому відношенні залишаються всі ключові атрибути:
Початкове відношення: .
Ключ: - складний.
Функціональні залежності:
- залежність всіх атрибутів від ключа відношення.
- залежність деяких атрибутів від частини складного ключа.
Декомпозірованниє відносини:
- залишок від початкового відношення. Ключ .
- атрибути, винесені з початкового відношення разом з частиною складного ключа. Ключ .
Крок 3 (Приведення до 3НФ). Якщо в деяких відносинах знайдена залежність деяких неключових атрибутів інших неключових атрибутів, то проводимо декомпозицію цих відносин таким чином: ті неключові атрибути, які залежать інших неключових атрибутів виносяться в окреме відношення. В новому відношенні ключем стає детермінант функціональної залежності:
Початкове відношення: .
Ключ: .
Функціональні залежності:
- залежність всіх атрибутів від ключа відношення.
- залежність деяких неключових атрибутів інших неключових атрибутів.
Декомпозірованниє відносини:
- залишок від початкового відношення. Ключ .
- атрибути, винесені з початкового відношення разом з детермінантом функціональної залежності. Ключ .
Зауваження. На практиці, при створенні логічної моделі даних, як правило, не слідують прямо приведеному алгоритму нормалізації. Досвідчені розробники звичайно відразу будують відносини в 3НФ. Крім того, основним засобом розробки логічних моделей даних є різні варіанти ER-діаграм. Особливість цих діаграм в тому, що вони відразу дозволяють створювати відносини в 3НФ. Проте, приведений алгоритм важливий з двох причин. По-перше, цей алгоритм показує, які проблеми виникають при розробці слабо нормалізованих відносин. По-друге, як правило, модель предметної області не буває ніколи правильно розроблена з першого кроку. Експерти предметної області можуть забути про що-небудь згадати, розробник може неправильно зрозуміти експерта, під час розробки можуть змінитися правила, прийняті в предметній області, і т.д. Все це може привести до появи нових залежностей, які були відсутні в первинній моделі предметної області. Тут якраз і необхідно використовувати алгоритм нормалізації хоча б для того, щоб переконатися, що відносини залишилися в 3НФ і логічна модель не погіршилася.
Аналіз критеріїв для нормалізованих і ненормалізованих моделей даних
Порівняння нормалізованих і ненормалізованих моделей
Зберемо воєдино результати аналізу критеріїв, по яких ми хотіли оцінити вплив логічного моделювання даних на якість фізичних моделей даних і продуктивність бази даних:
Критерій | Відношення слабо нормалізовані
(1НФ, 2НФ) | Відношення сильно нормалізовані
(3НФ)
Адекватність бази даних предметній області | ГІРШЕ (-) | КРАЩЕ (+)
Легкість розробки і супроводу бази даних | СКЛАДНІШЕ (-) | ЛЕГШЕ (+)
Швидкість виконання вставки, обновлення, видалення | ПОВІЛЬНІШЕ (-) | ШВИДШЕ (+)
Швидкість виконання вибірки даних | ШВИДШЕ (+) | ПОВІЛЬНІШЕ (-)
Як видно з таблиці, більш сильно нормалізовані відносини виявляються краще спроектовані (три плюси, один мінус). Вони більше відповідають предметній області, легше в розробці, для них швидше виконуються операції модифікації бази даних. Правда, це досягається ціною деякого уповільнення виконання операцій вибірки даних.
Біля слабо нормалізованих відносин єдина перевага - якщо до бази даних поводитися тільки із запитами на вибірку даних, то для слабо нормалізованих відносин такі запити виконуються швидше. Це зв'язано з тим, що в таких відносинах вже як би проведено з'єднання відносин і на це не витрачається час при вибірці даних.
Таким чином, вибір ступеня нормалізації відносин залежить від характеру запитів, з якими частіше за все звертаються до бази даних.
OLTP і OLAP-системи
Можна виділити деякі класи систем, для яких більше підходять сильно або слабо нормалізовані моделі даних.
Сильно нормалізовані моделі даних добре підходять для так званих OLTP-додатків (On-Line Transaction Processing (OLTP) - оперативна обробка транзакцій). Типовими прикладами OLTP-додатків є системи складського обліку, системи замовлень квитків, банківські системи, що виконують операції по перекладу грошей, і т.п. Основна функція подібних систем полягає у виконанні великої кількості коротких транзакцій. Самі транзакції виглядають відносно просто, наприклад, "зняти суму грошей з рахунку А, додати цю суму на рахунок В". Проблема полягає в тому, що, по-перше, транзакцій дуже багато, по-друге, виконуються вони одночасно (до системи може бути підключено декілька тисяч одночасно працюючих користувачів), по-третє, при виникненні помилки, транзакція повинна цілком відкататися і повернути систему до полягання, яке було до початку транзакції (не повинно бути ситуації, коли гроші зняті з рахунку А, але не поступили на рахунок В). Практично всі запити до бази даних в OLTP-додатках складаються з команд вставки, оновлення, видалення. Запити на вибірку в основному призначені для надання користувачам можливості вибору з різних довідників. Велика частина запитів, таким чином, відома наперед ще на етапі проектування системи. Таким чином, критичним для OLTP-додатків є швидкість і надійність виконання коротких операцій оновлення даних. Чим вище рівень нормалізації даних в OLTP-додатку, тим воно, як правило, швидше і надійніше. Відступи від цього правила можуть відбуватися тоді, коли вже на етапі розробки відомі деякі часто виникаючі запити, що вимагають з'єднання відносин і від швидкості виконання яких істотно залежить робота додатків. В цьому випадку можна пожертвувати нормалізацією для прискорення виконання подібних запитів.
Іншим типом додатків є так звані OLAP-додатки (On-Line Analitical Processing (OLAP) - оперативна аналітична обробка даних). Це узагальнений термін, що характеризує принципи побудови систем підтримки ухвалення рішень (Decision Support System - DSS), сховищ даних (Data Warehouse), систем інтелектуального аналізу даних (Data Mining). Такі системи призначені для знаходження залежностей між даними (наприклад, можна спробувати визначити, який зв'язаний об'єм продажів товарів з характеристиками потенційних покупців), для проведення аналізу "що якщо.". OLAP-додатки оперують з великими масивами даних, вже накопиченими в OLTP-додатках, узятими їх електронних таблиць або з інших джерел даних. Такі системи характеризуються наступними ознаками:
Додавання в систему нових даних відбувається відносно рідко крупними блоками (наприклад, раз на квартал завантажуються дані за підсумками квартальних продажів з OLTP-додатку).
Дані, додані в систему, звичайно ніколи не віддаляються.
Перед завантаженням дані проходять різні процедури "очищення", зв'язані з тим, що в одну систему можуть поступати дані з багатьох джерел, що мають різні формати уявлення для одних і тих же понять, дані можуть бути некоректні, помилкові.
Запити до системи є нерегламентованими і, як правило, достатньо складними. Дуже часто новий запит формулюється аналітиком для уточнення результату, одержаного в результаті попереднього запиту.
Швидкість виконання запитів важлива, але не критична.
Дані OLAP-додатків звичайно представлені у вигляді одного або декількох гіперкубів, вимірювання якого є довідковими даними, а в осередках самого гіперкуба збережуться власне дані. Наприклад, можна побудувати гіперкуб, вимірюваннями якого є: час (в кварталах, роках), тип товару і відділення компанії, а в осередках збережуться об'єми продажів. Такий гіперкуб міститиме даних про продажі різних типів товарів по кварталах і підрозділах. Грунтуючись на цих даних, можна відповідати на питання ніби "біля якого підрозділу найкращі об'єми продажів в поточному році?", або "які тенденції продажів відділень Південно-західного регіону в поточному році в порівнянні з попереднім роком?"
Фізично гіперкуб може бути побудований на основі спеціальної багатовимірної моделі даних (MOLAP - Multidimensional OLAP) або побудований засобами реляційної моделі даних (ROLAP - Relational OLAP).
Повертаючись до проблеми нормалізації даних, можна сказати, що в системах OLAP, що використовують реляційну модель даних (ROLAP), дані доцільно берегти у вигляді слабо нормалізованих відносин, що містять наперед обчислені основні підсумкові дані. Велика надмірність і пов'язані з нею проблеми тут не страшні, оскільки оновлення відбувається тільки у момент завантаження нової порції даних. При цьому відбувається як додавання нових даних, так і перерахунок підсумків.
Коректність процедури нормалізації - декомпозиція без втрат. Теорема Хеза
Як було показано вище, алгоритм нормалізації полягає у виявленні функціональних залежностей предметної області і відповідної декомпозиції відносин. Припустимо, що ми вже маємо працюючу систему, в якій накопичені дані. Хай даних коректні у нинішній момент, тобто факти предметної області правильно відображаються поточним поляганням бази даних. Якщо в предметній області знайдена нова функціональна залежність (або вона була пропущена на етапі моделювання предметної області, або просто змінилася предметна область), то виникає необхідність наново нормалізувати дані. При цьому деякі відносини доведеться декомпозувати відповідно до алгоритму нормалізації. Виникають природні питання - що відбудеться з вже накопиченими даними? Чи не будуть дані втрачені в ході декомпозиції? Чи можна повернутися назад до початкових відносин, якщо буде ухвалено рішення відмовитися від декомпозиції, чи відновляться при цьому дані?
Для відповідей на ці питання потрібно відповісти на питання - чим же є декомпозиція відносин з погляду операцій реляційної алгебри? При декомпозиції ми з одного відношення одержуємо два або більш відносин, кожне з яких містить частину атрибутів початкового відношення. В одержаних нових відносинах необхідно видалити дублікати рядків, якщо такі виникли. Це в точності означає, що декомпозиція відношення є не що інше, як узяття однієї або декількох проекцій початкового відношення так, щоб ці проекції в сукупності містили (можливо, з повтореннями) всі атрибути початкового відношення. Тобто, при декомпозиції не повинні втрачатися атрибути відносин. Але при декомпозиції також не повинні загубитися і самі дані. Дані можна вважати не втраченими в тому випадку, якщо можлива зворотна операція - по декомпозованим відносинах можна відновити початкове відношення в точності в колишньому вигляді. Операцією, зворотної операції проекції, є операція з'єднання відносин. Є велика кількість видів операції з'єднання (див. гл. 4). Оскільки при відновленні початкового відношення шляхом з'єднання проекцій не повинні з'явитися нові атрибути, то необхідно використовувати природне з'єднання.
Визначення 6. Проекція відносини на безліч атрибутів називається власною, якщо безліч атрибутів є власною підмножиною безлічі атрибутів відношення (тобто безліч атрибутів не співпадає з безліччю всіх атрибутів відношення ).
Визначення 7. Власні проекції і відносини називаються декомпозицією без втрат, якщо відношення точно відновлюється з них за допомогою природного з'єднання для будь-якого полягання відношення :
.
Розглянемо приклад, що показує, що декомпозиція без втрат відбувається не завжди.
Приклад 2. Хай дано відношення :
НОМЕР | ПРІЗВИЩЕ | ЗАРПЛАТА
1 | Іванов | 1000
2 | Петров | 1000
Таблиця 7 Відношення
Розглянемо перший варіант декомпозиції відношення на два відношення:
НОМЕР | ЗАРПЛАТА
1 | 1000
2 | 1000
Таблиця 8 Відношення
ПРІЗВИЩЕ | ЗАРПЛАТА
Іванов | 1000
Петров | 1000
Таблиця 9 Відношення
Природне з'єднання цих проекцій, що мають загальний атрибут "ЗАРПЛАТА", очевидно, буде наступним (кожний рядок однієї проекції з'єднається з кожним рядком іншої проекції):
НОМЕР | ПРІЗВИЩЕ | ЗАРПЛАТА
1 | Іванов | 1000
1 | Петров | 1000
2 | Іванов | 1000
2 | Петров | 1000
Таблиця 10 Відношення
Отже, дана декомпозиція не є декомпозицією без втрат, оскільки початкове відношення не відновлюється в точному вигляді по проекціях (сірим кольором виділені зайві кортежі).
Розглянемо інший варіант декомпозиції:
НОМЕР | ПРІЗВИЩЕ
1 | Іванов
2 | Петров
Таблиця 11 Відношення
НОМЕР | ЗАРПЛАТА
1 | 1000
2 | 1000
Таблиця 12 Відношення
По даних проекціях, мають загальний атрибут "НОМЕР", початкове відношення відновлюється в точному вигляді. Проте, не можна сказати, що дана декомпозиція є декомпозицією без втрат, оскільки ми розглянули тільки одне конкретне полягання відношення , і не можемо сказати, чи буде і в інших поляганнях відношення відновлюватися точно. Наприклад, припустимо, що відношення перейшло в полягання:
НОМЕР | ПРІЗВИЩЕ | ЗАРПЛАТА
1 | Іванов | 1000
2 | Петров | 1000
2 | Сидоров | 2000
Таблиця 13 Відношення
Здається, що цього не може бути, оскільки значення в атрибуті "НОМЕР" повторюються. Але ми ж нічого не говорили про ключ цього відношення! Зараз проекції матимуть вигляд:
НОМЕР | ПРІЗВИЩЕ
1 | Іванов
2 | Петров
2 | Сидоров
Таблиця 14 Відношення
НОМЕР | ЗАРПЛАТА
1 | 1000
2 | 1000
2 | 2000
Таблиця 15 Відношення
Природне з'єднання цих проекцій міститиме зайві кортежі:
НОМЕР | ПРІЗВИЩЕ | ЗАРПЛАТА
1 | Іванов | 1000
2 | Петров | 1000
2 | Петров | 2000
2 | Сидоров | 1000
2 | Сидоров | 2000
Таблиця 16 Відношення
Висновок. Таким чином, без додаткових обмежень на відношення не можна говорити про декомпозицію без втрат.
Такими додатковими обмеженнями і є функціональні залежності. Має місце наступна теорема Хеза [54]:
Теорема (Хеза). Хай є відношенням, і - атрибути або безліч атрибутів цього відношення. Якщо є функціональна залежність , то проекції і утворюють декомпозицію без втрат.
Доказ. Необхідно довести, що для будь-якого полягання відношення . У лівій і правій частині рівності стоїть безліч кортежів, тому для доказу достатньо довести два включення для двох безлічі кортежів: і .
Доведемо перше включення. Візьмемо довільний кортеж . Доведемо, що він включається також і в . За визначенням проекції, кортежі і . За визначенням природного з'єднання кортежі і , мають однакове значення загального атрибуту , будуть сполучені в процесі природного з'єднання в кортеж . Таким чином, включення доведено.
Доведемо зворотне включення. Візьмемо довільний кортеж . Доведемо, що він включається також і в . За визначенням природного з'єднання одержимо, що в є кортежі і . Оскільки , то існує деяке значення , таке що кортеж . Аналогічно, існує деяке значення , таке що кортеж . Кортежі і мають однакове значення атрибуту , рівне . З цього, через функціональну залежність , витікає, що . Таким чином, кортеж . Зворотне включення доведено. Теорема доведена.
Зауваження. В доведенні теореми Хеза наявність функціональної залежності не використовувалася при доказі включення . Це означає, що при виконанні декомпозиції і подальшому відновленні відношення за допомогою природного з'єднання, кортежі початкового відношення не будуть втрачені. Основне значення теореми Хеза полягає в доказі того, що при цьому не з'являться нові кортежі, відсутні в початковому відношенні.
Оскільки алгоритм нормалізації (приведення відносин до 3НФ) заснований на функціональних залежностях, що є у відносинах, то теорема Хеза показує, що алгоритм нормалізації є коректним, тобто в ході нормалізації не відбувається втрати інформації.
Висновки
При розробці бази даних можна виділити декілька рівнів моделювання:
Сама предметна область
Модель предметної області
Логічна модель даних
Фізична модель даних
Власне база даних і додатки
Ключові рішення, що визначають якість майбутньої бази даних закладаються на етапі розробки логічної моделі даних. "Хороші" моделі даних повинні задовольняти певним критеріям:
Адекватність бази даних предметної області
Легкість розробки і супроводу бази даних
Швидкість виконання операцій оновлення даних (вставка, оновлення, видалення)
Швидкість виконання операцій вибірки даних
Перша нормальна форма (1НФ) - це звичне відношення. Відношення в 1НФ володіє наступними властивостями:
У відношенні немає однакових кортежів.
Кортежі не впорядковані.
Атрибути не впорядковані.
Всі значення атрибутів атомарні.
Відносини, що знаходяться в 1НФ є "поганими" в тому значенні, що вони не задовольняють вибраним критеріям - є велика кількість аномалій оновлення, для підтримки цілісності бази даних потрібна розробка складних трігерів.
Відношення знаходиться в другій нормальній формі (2НФ) тоді і тільки тоді, коли відношення знаходиться в 1НФ і немає неключових атрибутів, залежних від частини складного ключа.
Відносини в 2НФ "краще", ніж в 1НФ, але ще недостатньо "хороші" - залишається частина аномалій оновлення, наДалі потрібні трігери, що підтримують цілісність бази даних.
Відношення знаходиться в третій нормальній формі (3НФ) тоді і тільки тоді, коли відношення знаходиться в 2НФ і всі неключові атрибути взаємно незалежні.
Відносини в 3НФ є самими "хорошими" з погляду вибраних нами критеріїв - усунені аномалії оновлення, потрібні тільки стандартні трігери для підтримки посилальної цілісності.
Перехід від ненормалізованих відносин до відносин в 3НФ може бути виконаний за допомогою алгоритму нормалізації. Алгоритм нормалізації полягає в послідовній декомпозиції відносин для усунення функціональних залежностей атрибутів від частини складного ключа (приведення до 2НФ) і усунення функціональних залежностей неключових атрибутів один від одного (приведення до 3НФ).
Коректність процедури нормалізації (декомпозиція без втрати інформації) доводиться теоремою Хеза.

Внимание, отключите Adblock

Вы посетили наш сайт со включенным блокировщиком рекламы!
Ссылка для скачивания станет доступной сразу после отключения Adblock!

Скачать