Конспект лекцій Суми Видавництво Сумду 2009 Міністерство освіти І науки України Сумський державний університет icon

Конспект лекцій Суми Видавництво Сумду 2009 Міністерство освіти І науки України Сумський державний університет




НазваКонспект лекцій Суми Видавництво Сумду 2009 Міністерство освіти І науки України Сумський державний університет
Сторінка3/19
Дата04.06.2013
Розмір1.62 Mb.
ТипКонспект
1   2   3   4   5   6   7   8   9   ...   19
^

1.3 Реляційна модель даних




1.3.1 Поняття відношення


Широкому поширенню і популярністю реляційна модель даних завдячує двом істотних перевагам:

1) однорідністю подання даних у моделі, що обумовлює простоту сприйняття її конструкцій користувачами БД;

2) наявністю розвиненої математичної теорії реляційних БД, що обумовлює коректність її застосування.

В основі реляційної моделі даних лежить поняття відношення, яке задається переліком своїх елементів і перерахуванням їх значень. Розглянемо приклад на рис. 1.18. На ньому наведений розклад руху автобусів по маршруту "Москва - Черноголовка - Москва". Бачимо певну структуру. Кожен включений у розклад рейс має свій номер, час відправлення й час у дорозі. Розклад може бути подано таблицею. Заголовки колонок таблиці звуться атрибутами. Перелік їх імен носить назви схеми відношення. Кожен атрибут визначає тип даних, що разом з областю його значень називається доменом. Вся таблиця цілком називається відношенням, а кожен рядок таблиці зветься кортежем відношення. Таким чином, відношення можна подати у вигляді двовимірної таблиці.

Підходи до визначення поняття відношення можуть бути різними. Математично відношення може бути визначене як безліч кортежів, що є підмножиною декартового добутку фіксованого числа областей (доменів). У результаті одержуємо, що у кожному кортежі повинне бути однакове число компонентів (атрибутів) і значення кожного з них вибирається з деякого певного домену.





Рисунок 1.18 – Розклад руху автобусів як відношення


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

По-перше, атрибути різних відношень можуть бути визначені на одному домені, так само як й атрибути одного відношення. Це дуже важлива обставина, що дозволяє встановлювати зв'язки за значенням між відношеннями. По-друге, множина математично по своєму визначенню не може мати співпадаючих елементів, і, отже, кортежі у відношенні можна розрізнити лише за значенням їх компонентів. Це теж є дуже важливим для моделі: ніякі два кортежі не можуть мати повністю співпадаючих компонентів. Таким чином, у реляційній моделі повністю виключається дублювання даних про сутності реального світу. По-третє, відзначимо, що схема відношення також є множина, що дозволяє працювати з ними за допомогою теоретико-множинних операцій. Це є важливим моментом для побудови теорії проектування реляційних схем БД.

Існує певне розходження між математичним визначенням відношення й дійсне збереженим відношенням у пам'яті комп'ютера. За визначенням, відношення не може мати два ідентичних кортежі. Однак СКБД, що підтримують реляційну модель даних, зберігають відношення у файлах операційної системи комп'ютера. Розміщення відношень у файлах операційної системи допускає зберігання ідентичних кортежів. Якщо не використовується спеціальна техніка (контроль цілісності за первинним ключем), то звичайно більшість промислових СКБД допускають зберігання двох ідентичних кортежів у БД.

^ Ключем або ключовим полем називається унікальне значення, що дозволяє тим чи іншим способом ідентифікувати сутність або частину сутності ПО, тобто ключ - це значення деякого атрибута або атрибутів у кортежі відношення, що представляє екземпляр сутності у реляційній моделі даних.

Прийнято розрізняти первинні ключі й часткові ключі. Математично первинним ключем відношення є підмножина звуження декартового добутку, що дозволяє однозначно ідентифікувати кортеж. Якщо первинний ключ містить кілька атрибутів, то він називається складеним ключем, у протилежному випадку - атомарним. Частковим ключем називається атрибут складеного ключа, якщо він однозначно визначає сукупність неключових атрибутів відношення. Атрибут кортежу, що є первинним ключем іншого відношення, називається зовнішнім (іноді стороннім) ключем. Із визначення відношення випливає таки важлива властивість реляційної моделі даних: кожне відношення повинне мати первинний ключ. Зазначимо, що ключ у контексті моделі ПО БД завжди відображає той або інший ступінь зв'язку між атрибутами сутностей ПО, тобто семантично ключ є засіб моделювання зв'язків у моделі.

Приклад – Розглянемо речення "Громадянин Іванов проживав у місті Москві 10 років". Можливими атрибутами у відношенні Місце_проживання є прізвище громадянина, назва міста проживання й час проживання. Прізвище громадянина може виступати як первинний ключ цього відношення, тому що особистість однозначно визначає час її проживання в конкретному місті. Таким чином, щодо цього моделюється зв'язок "проживав" між атрибутами "прізвище" й "місто".

Відношення у реляційній моделі даних, як правило, представляються за допомогою функціональної форми запису (тому що ми записуємо функції декількох змінних у математичному аналізі), при цьому атрибути первинного ключа підкреслюються:

ІМ'Я_ВІДНОШЕННЯ (Атрибути первинного ключа, неключові атрибути).

^ Приклад. Подання зв'язку відношенням. Представимо зв'язок між особистістю й місцем її проживання через відношення

ПРОЖИВАЄ (Кл. особистість, Кл. населений_пункт, час)

^ Опис особистості:

ОСОБИСТІСТЬ (Кл. особистість, П.І.П/б, вік, стать)

Опис населеного пункту:

НАСЕЛЕНИЙ_ПУНКТ (Кл.населений_пункт, географія, населення)

Однак найбільшого поширення одержало подання відношень у вигляді графічних діаграм, наприклад, ER-діаграм, про які ми говорили раніше. Перевагами такого подання є наочність діаграм і можливість їх побудови у ряді CASE-засобів проектування БД.

У підсумку сформулюємо основні властивості реляційної моделі даних, які випливають із поняття відношення як множини:

  • всі кортежі одного відношення повинні мати ту саму кількість атрибутів;

  • значення кожного з атрибутів повинне належати деякому певному домену;

  • кожне відношення повинне мати первинний ключ;

  • ніякі два кортежі не можуть мати повністю співпадаючих наборів значень;

  • кожне значення атрибутів повинне бути атомарним, тобто не повинне мати внутрішньої структури й містити як компонент інше відношення;

  • реляційна модель даних повинна бути несуперечливою, зокрема повинно виконуватися: 1) принцип посилальної цілісності - зв'язки між відношеннями повинні бути замкнутими, 2) значення колонок повинні належати тому самому визначеному для них домену;

  • порядок проходження кортежів у відношенні не має значення. Порядок є більшою мірою властивістю зберігання даних, ніж властивістю безпосередньо самої реляційної моделі даних.



^

1.3.2 Поняття функціональної залежності в даних


На стадії логічного проектування реляційної БД розробник визначає й вибудовує схеми відношення у рамках деякої ПО, а саме - представляє сутності, групує їх атрибути, виявляє основні зв'язки між сутностями. Так, у самому загальному змісті проектування реляційної БД полягає в обґрунтованому виборі конкретних схем відношення з безлічі різних альтернативних варіантів схем.

На практиці побудова логічної моделі БД, незалежно від моделі даних, виконується з урахуванням двох основних вимог: виключити надмірність і максимально підвищити надійність даних. Ці вимоги випливають із вимоги колективного використання даних групою користувачів.

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

Кортежі відношення можуть представляти екземпляри сутності ПО або фіксувати їх взаємозв'язок. Але навіть якщо ці кортежі відповідають схемі відношень й обрані з припустимих доменів, не кожен з них може бути поточним значенням деякого відношення. Наприклад, вік людини рідко буває більше 120 років, або той самий пілот не може одночасно виконувати два різних рейси. Такі обмеження семантики домену практично не впливають на вибір тієї або іншої схеми відношень. Вони являють собою обмеження на типи даних.

Оскільки функціональну залежність можна задати у вигляді таблиці, а таблиця є форма подання відношень, то стає очевидний зв'язок між функціональною залежністю і відношенням. Відношення може задавати функціональну залежність. Це твердження є першою конструктивною ідеєю, яка покладена в основу теорії проектування реляційних БД.

^ Приклад. Поняття функціональної залежності

Проілюструємо поняття функціональної залежності на прикладі графіка польотів аеропорту.

ГРАФІК_ПОЛЬОТІВ (Пілот, Рейс, Дата_вильоту, Час_вильоту)

Іванов 100 8.07 10:20

Іванов 102 9.07 13:30

Ісаєв 90 7.07 6:00

Ісаєв 103 10.07 19:30

Петров 100 12.07 10:20

Петров 102 11.07 13:30

Фролов 90 8.07 6:00

Фролов 90 12.07 6:00

Відомо: кожному рейсу відповідає певний час вильоту; для кожного пілота, дати й часу вильоту можливий тільки один рейс; на певний день і рейс призначається певний пілот.

Отже: "Час_вильоту" функціонально залежить від {"Рейс"}; "Рейс" функціонально залежить від {"Пілот", "Дата_вильоту", "Час_вильоту"}; "Пілот" функціонально залежний від {"Рейс", "Дата_вильоту"}.

Важливим завданням при виявленні функціональних залежностей на атрибутах відношень, що за визначенням є множиною, необхідно з'ясувати, який з атрибутів виступає як аргумент, а який - як значення функціональна залежність. Найбільш підходящими кандидатами в аргументи функціональної залежності є можливі ключі, тому що кортежі представляють екземпляри сутності, які ідентифікуються значеннями атрибутів свого ключа.

^

1.3.3 Нормальні форми відношень. Створення логічної моделі реляційної БД


Під реляційною БД прийнято розуміти сукупність екземплярів кінцевих відношень. Сукупність схем відношень утворює схему реляційної БД.

Схема реляційної БД є логічною моделлю реляційної БД. На основі інформаційної моделі у процесі проектування створюються логічна й фізична моделі даних. Інформаційна модель даних відбиває потреби системи в даних і зв'язку між даними з погляду їх споживачів - користувачів; логічна модель даних є незалежним логічним поданням даних; фізична модель даних містить визначення всіх реалізованих об'єктів у конкретній БД для конкретної СКБД.

Установлення функціональної залежності й одержання найкращого з погляду мінімальності подання множини функціональних залежностей дозволять побудувати найбільш оптимальний варіант БД, що забезпечує надійність зберігання й обробки даних на основі методів еквівалентних перетворень схем відношень реляційної БД. Процес вирішення такого завдання називається нормалізацією відношень інформаційної моделі ПО й полягає у перетворенні її об'єктів у логічні таблиці БД. Основні вимоги наведені нижче:

  • первинні ключі відношень повинні бути мінімальними;

  • число відношень БД повинне по можливості давати найменшу надмірність даних – вимога надійності даних;

  • число відношень БД не повинне приводити до втрати продуктивності системи;

  • дані не повинні бути суперечливими, тобто при виконанні операцій включення, видалення й відновлення даних їх потенційна суперечливість повинна бути зведена до мінімуму;

  • схема відношень БД повинна бути стійкою, здатною адаптуватися до змін при її розширенні додатковими атрибутами – вимога гнучкості структури БД;

  • розкид часу реакції на різні запити до БД не повинен бути великим;

  • дані повинні правильно відбивати стан ПО БД у кожен конкретний момент часу – вимога актуальності даних;

Створення системи, що одночасно задовольняє всім вищезгаданим вимогам, являє собою складну оптимізаційну задачу, що часом не має однозначного вирішення.

Теорія функціональних залежностей дозволяє встановити певні вимоги до схем відношень у реляційній БД. Ці вимоги формулюються у термінах властивостей відношень і називаються нормальними формами схем відношень. Кожна нормальна форма відношень пов'язана з певним класом функціональної залежності, які представлені у відношеннях. Одним з очевидних засобів усунення потенційної суперечливості даних у відношеннях логічної моделі реляційної БД є їх розбиття на двоє або більше відношень, у кожному з яких є присутньою тільки одна функціональна залежність.

Процес усунення потенційної суперечливості й надмірності даних у відношеннях реляційної БД називається нормалізацією вихідних схем відношень. Нормалізація відношень полягає у виконанні декомпозиції відношень, що перебувають у попередній нормальній формі, на двоє або більше відношень, які задовольняють вимогам наступної нормальної форми.

У теорії реляційних БД звичайно виділяється така послідовність нормальних форм: перша нормальна форма (1NF); друга нормальна форма (2NF); третя нормальна форма (3NF); нормальна форма Бойса-Кодда (BCNF); четверта нормальна форма (4NF); п'ята нормальна форма, або нормальна форма проекції-з'єднання (5NF або PJ/NF).

Основні властивості нормальних форм полягають у такому: кожна наступна нормальна форма у деякому змісті краще попередньої нормальної форми; при переході до наступної нормальної форми властивості попередніх нормальних форм зберігаються.

Перша нормальна форма – відношення перебуває у 1NF, якщо всі атрибути відношення є простими (вимогу атомарності атрибутів), тобто не мають компонентів. Іншими словами, домен атрибута повинен складатися з неподільних значень і не може містити в собі безліч значень із більше елементарних доменів.

Нехай є змінне відношення: Employer_Project_Task {Em_Number, Em_Degrees, Em_Pay, Pr_Number, Em_Task}. Атрибути містять відповідно дані про номер справи, розряд та заробітну платню службовця, номер проекту й про завдання, що виконує службовець у даному проекті. Припустимо, що розряд службовця визначає розмір його заробітної плати й що кожен службовець може брати участь у декількох проектах за умови виконання тільки одного завдання. Тоді очевидно, що єдино можливим ключем відношення є складений атрибут {Em_Number, Pr_Number }. Діаграма мінімальної множини ER показана на рис. 1.19. У наведеному відношенні деякі функціональні залежності атрибутів від можливого ключа не є мінімальними. Це призводить до так званих аномалій відновлення. Під аномаліями відновлення розуміються труднощі, з якими зустрічаються при виконанні операцій додавання кортежів у відношення (INSERT), видалення кортежів (DELETE) і модифікації кортежів (UPDATE).




Рисунок 1.19 – ER-діаграма відношення Employer_Project_Task


Стосовно нашого прикладу:

  • додавання кортежів – ми не можемо доповнити відношення Employer_Project_Task даними про службовця, який ще не бере участь у жодному проекті (Em_Number є частиною первинного ключа й не може містити невизначених значень). Тим часом часто буває, що спочатку службовця беруть на роботу, встановлюють його розряд і розмір заробітної плати, а лише потім призначають для нього проект;

  • видалення кортежів – ми не можемо зберегти у відношенні Employer_Project_Task дані про службовця, який завершив участь у своєму останньому проекті (з тієї причини, що значення атрибута Pr_Number для цього службовця стає невизначеним);

  • модифікація кортежів – щоб змінити розряд службовця, ми будемо змушені модифікувати всі кортежі з відповідним значенням атрибута Em_Number. У іншому випадку буде порушений природний зв'язок Em_Number → Em_Degrees (в одного службовця є тільки один розряд).

Для подолання цих труднощів можна зробити декомпозицію змінного відношення Employer_Project_Task на два змінні відношення – Employer {Em_Number, Em_Degrees, Em_Рау} і Employer_Project_Task {Em_Number, Pr_Number, Em_Task}. На рис. 1.20 показані діаграми ER цих відношень. Тепер ми можемо легко впоратися з операціями відновлення.





Рисунок 1.20 – ER-діаграми у змінних відношеннях Employer і Employer_Project_Task


Друга нормальна форма

Будемо вважати атрибут відношення ключовим, якщо він є елементом якого-небудь ключа відношення. В іншому випадку атрибут буде вважатися неключовим. Відношення перебуває у 2NF, якщо воно перебуває у 1NF, і всі неключові атрибути відношення функціонально мінімально залежать від первинного ключа. Іншими словами, 2NF вимагає, щоб відношення не містило часткових функціональних залежностей.

Стосовно нашого прикладу: відношення Employer знаходиться у 2NF, а відношення Employer_Project_Task – ні, оскільки атрибут Em_Task функціонально залежить від двох ключових атрибутів: Em_Number та Pr_Number. Будь-яке змінне відношення, що перебуває у 1NF, але не перебуває у 2NF, може бути зведене до набору змінних відношень, що перебувають у 2NF. У результаті декомпозиції ми одержуємо набір проекцій вихідного змінного відношення, природне з'єднання значень яких відтворює значення вихідного змінного відношення (тобто це декомпозиція без втрат).

Третя нормальна форма

Відношення перебуває у 3NF, якщо воно перебуває в 2NF, і всі неключові атрибути відношення залежать тільки від первинного ключа. Іншими словами, 3NF вимагає, щоб відношення не містило транзитивних функціонального зв’язку неключових атрибутів від ключа.

Функціональні залежності відношення Employer як і раніше породжують деякі аномалії відновлення. Вони викликаються наявністю транзитивного зв’язку Em_Number → Em_Рау (через зв'язок Em_Number → Em_Degrees і Em_Degrees → Em_Рау). Ці аномалії пов'язані з надмірністю зберігання значення атрибута Em_Рау у кожному кортежі, що характеризує службовців із тим самим розрядом:

  • додавання кортежів – неможливо зберегти дані про новий розряд (і відповідному йому розміру зарплати), поки не з'явиться службовець із новим розрядом. Первинний ключ не може містити невизначені значення;

  • видалення кортежів – при звільненні останнього службовця з даним розрядом ми втратимо інформацію про наявність такого розряду й відповідному розміру зарплати;

  • модифікація кортежів – при зміні розміру зарплати, що відповідає деякому розряду, ми будемо змушені змінити значення атрибута Em_Рау у кортежах всіх службовців, яким призначений цей розряд (інакше не буде виконуватися зв'язок Em_Degrees → Em_Рау).

Можлива декомпозиція: для подолання цих труднощів зробимо декомпозицію змінного відношення Employer на два змінні відношення – Employer1 {Em_Number, Em_Degrees} й Degrees {Em_Degrees, Em_Рау}. На рис. 1.21 показані ER-діаграми цих змінних відношень.




Рисунок 1.21 – ER-діаграми у змінних відношеннях Employer1 і Degrees


Таким чином, процедура зведення відношення до 3NF складається у виконанні двох проекцій: по правій і по лівій частині транзитивного функціонального зв’язку.

Зрозуміло, що в процесі нормалізації декомпозиція відношення на незалежні проекції є кращою. Необхідні й достатні умови незалежності проекцій відношення забезпечує теорема Риссанена: проекції r1 і r2 відношення r є незалежними тоді й тільки тоді, коли кожний зв'язок у відношенні r логічно виходить зі зв'язку у r1 і r2; загальні атрибути r1 і r2 утворять можливий ключ хоча б для одного з цих відношень.

Проілюструємо вірність цієї теореми на прикладі декомпозиції відношення Employer. У декомпозиції на проекції Employer1 і Degrees загальний атрибут Em_Degrees є можливим (і первинним) ключем відношення Degrees, а єдиний додатковий зв’язок відношення Employer (Em_Number→Em_Рау) логічно виходить зі зв'язку Em_Number→Em_Degrees і Em_Degrees→Em_Рау, які виконуються для відношення Employer1 й Degrees відповідно.

Атомарним відношенням називається відношення, яке неможливо декомпозувати на незалежні проекції. Далеко не завжди для неатомарних відношень потрібна декомпозиція на атомарні проекції. При виборі способу декомпозиції необхідно прагнути до одержання незалежних проекцій, але не обов'язково атомарних.

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

Наприклад, нехай є змінне відношення Employer_Project_Task1 { Em_Number Em_Nаme, Pr_Number, Em_Task} з множиною зв'язків, зображених на рис. 1.22.





Рисунок 1.22 – Діаграма функціонального зв’язку відношення Employer_Project_Task1


У відношенні Employer_Project_Task1 службовці унікально ідентифікуються як за номерами справ, так і за іменами. Отже, існують зв’язки Em_Number→Em_Nаme й Em_Nаme→Em_Number. Але один службовець може брати участь у декількох проектах, тому можливими ключами є {Em_Number, Pr_Number} і {Em_Nаme, Pr_Number}.

Очевидно, що, хоча у відношенні Employer_Project_Task1 всі зв’язки неключових атрибутів від можливих ключів є мінімальними й транзитивні зв’язки відсутні, цьому відношенню властиві аномалії відновлення. Наприклад, у випадку зміни імені службовця необхідно обновити атрибут Em_Nаme у всіх кортежах відношення, що відповідають даному службовцеві. Інакше буде порушений зв'язок Em_Number→Em_Nаme, і БД виявиться у неузгодженому стані.

Причиною відзначених аномалій є те, що у вимогах 2NF і 3NF не була потрібна мінімальна функціональна залежність від первинного ключа атрибутів, що є компонентами інших можливих ключів. Проблему вирішує нормальна форма, що історично прийнята називати нормальною формою Бойса-Кодда і яка є уточненням 3NF у випадку наявності декількох можливих ключів, що перекриваються.

Змінна відношення перебуває в нормальній формі Бойса-Кодда (BCNF) у тому і тільки в тому випадку, коли будь-який виконуваний для цього змінного відношення нетривіальний і мінімальний функціональний зв'язок має як детермінант деякий можливий ключ даного відношення.

Відношення Employer_Project_Task1 може бути наведене до BCNF шляхом однієї з двох декомпозицій: Employer_Number_Nаme {Em_Number, Em_Nаme} і Employer_Number_Рroject_Task {Em_Number, Pr_Number, Pr_Task} з множиною зв’язків, показаними на рис. 7.5, і Employer_Number_Nаme {Em_Number, Em_Nаme} і Employer_Nаme_Project_Task {Em_Nаme, Pr_Number, Pr_Task} (зв’язки і значення результуючих змінних відношень виглядають аналогічно).

Четверта нормальна форма

Розглянемо ще одну можливу інтерпретацію змінної відношення Employer_Project_Task. Припустимо, що кожен службовець може брати участь у декількох проектах, але в кожному проекті ним повинні виконуватися ті самі завдання. Можливе значення змінної відношення Employer_Project_Task показано на рис. 1.24.

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





Рисунок 1.23 – ER-діаграми відношень Employer_Number_Nаme і Employer_Number_Рroject_Task





Рисунок 1.24 – Можливе значення змінної відношення Employer_Project_Task


Видалення кортежів – якщо службовець припиняє участь у проектах, то відсутня можливість зберегти дані про завдання, які він може виконувати.

Модифікація кортежів – при зміні одного з завдань службовця необхідно змінити значення атрибута Em_Task у скількох кортежах, у скількох проектах бере участь службовець.

Труднощі, пов'язані з відновленням змінної відношення Employer_Project_Task, вирішуються шляхом його декомпозиції на два змінні відношення: Employer_Project_Number {Em_Number, Pr_Number} і Employer_Task {Em_Number, Em_Task}. Значення цих змінних відношень, що відповідають значенню змінної відношення Employer_Project_Task показані на рис. 1.25.





Рисунок 1.25 – Діаграми відношень Employer_Project_Number і Employer_Task


Зверніть увагу, що останній варіант змінної відношення Employer_Project_Task в BCNF, оскільки всі атрибути заголовка відношення входять до складу єдино можливого ключа. Раніше обговорені принципи нормалізації тут не застосовані, але ми одержали корисну декомпозицію. Справа в тому, що у випадку останнього варіанта відношення, ми маємо справу з новим видом залежності, уперше виявленим Роном Фейджином у 1971 р. Фейджин назвав залежності цього виду багатозначними (multi-valued dependency - MVD).

У відношенні Employer_Project_Task виконуються дві MVD: Em_Number→Pr_Number і Em_Number→Em_Task. Перша MVD означає, що кожному значенню атрибута Em_Number відповідає обумовлена тільки цим значенням множина значень атрибута Pr_Number. Аналогічно трактується друга MVD.

У змінній відношення r з атрибутами A, B, C (у загальному випадку складовими) є багатозначна залежність B від A (AB) у тому і тільки в тому випадку, коли множина значень атрибута B, що відповідає парі значень атрибутів A й C, залежить від значення A і не залежить від значення C. Багатозначні залежності мають цікаву властивість "подвійності", що демонструє така лема Фейджина:

У відношенні r {A, B, C} виконується MVD A→→B у тому і тільки в тому випадку, коли виконується MVD A→→C.

Функціональний зв'язок є частковим випадком MVD, коли множина значень залежного атрибута обов'язково складається з одного елемента. Таким чином, якщо виконується зв'язок A→B, то виконується й MVD A→→B.

^ Теорема Фейджина. Нехай є змінна відношення r з атрибутами A, B, C (у загальному випадку, складовими). Відношення r декомпозується без втрат на проекції {A, B} й {A, C} тоді й тільки тоді, коли для нього виконується MVD A→→B | C.

Відношення перебуває у 4NF, якщо воно перебуває в 3NF або BCNF і всі незалежні багатозначні функціональні зв’язки рознесені в окремі відношення з тим самим ключем. Іншими словами, 4NF застосовується при наявності у відношенні більш ніж однієї MVD і вимагає, щоб відношення не містило незалежних багатозначних MVD.

П'ята нормальна форма

Приведення відношення до 4NF припускає його декомпозицію без втрат на дві проекції (як й у випадку 2NF, 3NF й BCNF). Однак бувають (хоча й нечасто) випадки, коли декомпозиція без втрат на дві проекції неможлива, але можна зробити декомпозицію без втрат на більше число проекцій. Будемо називати
n-декомпозованими відношеннями відношення, що може бути декомпозовано без втрат на n проекцій.

У змінній відношення r з атрибутами (можливо, складовими) A й B MVD A→→B називається тривіальною, якщо або A€B, або A UNION B збігається із заголовком відношення r.

Тривіальна MVD завжди задовольняється. При A€B вона вироджується у тривіальний зв'язок. У випадку A UNION B = Hr вимоги багатозначної залежності дотримуються очевидним способом.

Для прикладу n-декомпозованого відношення при n > 2 розглянемо п'ятий варіант змінної відношення Employer_Project_Task, у якій є єдино можливий ключ {Em_Number, Pr_Number, Em_Task} і відсутні нетривіальні MVD (рис.1.26).





Рисунок 1.26 – Можливі значення змінної відношення Employer_Project_Task та результати проекцій


Залежність проекції/з'єднання. Твердження про те, що тіло відношення Employer_Project_Task відновлюється без втрат шляхом природного з'єднання його проекцій Employer_Project_Number, Project_Number_Task і Employer_Task еквівалентно наступному звичайному обмеженню реального світу, що для відношення Employer_Project_Task може бути сформульовано природною мовою в такий спосіб (BEPT, BEPN, BPNT і BET позначають тіла значень змінних відношення Employer_Project_Task, Employer_Project_Number, Project_Number_Task і Employer_Task відповідно): якщо службовець із номером en бере участь у проекті pn, і в проекті pn виконується завдання et, і службовець із номером en виконує завдання et, то службовець із номером en виконує завдання et у проекті pn.

У загальному вигляді таке обмеження називається залежністю проекції/з'єднання і має таке формальне визначення.

Нехай задана змінна відношення r, і A, B, ..., Z є довільними підмножинами заголовка r (складовими, що перекриваються атрибутами). У змінної відношення r задовольняється залежність проекції/з'єднання (Project-Join Dependency - PJD) *( A, B, ..., Z) тоді й тільки тоді, коли будь-яке припустиме значення r можна одержати шляхом природного з'єднання проекцій цього значення на атрибути A, B, ..., Z.

У змінної відношення Employer_Project_Task виконується PJD* ({Em_Number, Pr_Number}, {Pr_Number, Em_Task}, {Em_Number, Em_Task}). Наявність такого PJD забезпечує можливість декомпозиції відношення на три для уникнення аномалії відновлення.

У змінної відношення r PJD *( A, B, ..., Z) називається можливими ключами, що маються на увазі, в тому і тільки в тому випадку, коли кожен складений атрибут A, B, ..., Z є суперключем r, тобто включає хоча б один можливий ключ r.

У змінної відношення r залежність проекції/з'єднання *(A, B, ..., Z) називається тривіальною, якщо хоча б один зі складених атрибутів A, B, ..., Z збігається із заголовком r.

Загальноприйняте визначення 5NF має такий вигляд: змінна відношення r перебуває в 5NF, або в нормальній формі проекції/з'єднання (5NF, або PJ/NF - Project-Join Normal Form) у тому і тільки в тому випадку, коли кожна нетривіальна PJD в r розуміється можливими ключами r.

Таким чином, щоб розпізнати, що дана змінна відношення r перебуває в 5NF, необхідно знати всі можливі ключі r і всі PJD цієї змінної відношення. Виявлення всіх залежностей з'єднання є нетривіальним завданням, і для його вирішення немає загальних методів. Тому на практиці проектування реляйціних БД методом нормалізації звичайно завершується після досягнення 4NF, і відношення, що перебувають в 4NF, як правило, перебувають і в 5NF. 5NF є "остаточною" нормальною формою, яку можна досягти в процесі нормалізації на основі проекцій.

Нормальні форми характеризуються такими властивостями:

1NF - всі атрибути відношення прості;

2NF - відношення перебуває в 1NF і не містить часткових залежностей;

3NF - відношення перебуває в 2NF і не містить транзитивних залежностей від ключа;

ВКNF - відношення перебуває в 3NF і не містить залежностей ключів від неключових атрибутів;

4NF - застосовується при наявності більш ніж одної багатозначної залежності - відношення перебуває в ВКNF або 3NF і не містить незалежних багатозначних функціональних залежностей;

5NF - відношення перебуває в 4NF і не містить залежностей по з'єднанню.
^

1.3.4 Алгоритм методу декомпозиції відношення


Тепер нам відомо, із чого почати нормалізацію - з універсального відношення; що перевірити - знаходження вихідного відношення в ВКNF; що почати - декомпозицію вихідного відношення на два інших відношення; і коли зупинитися - всі відношення БД у ВКNF. Таким чином, можна сформулювати загальний алгоритм проектування логічної моделі реляційної БД методом декомпозиції:

Алгоритм методу декомпозиції відношення

  1. Розроблення універсального відношення для БД.

  2. Визначення всіх функціональних залежностей між атрибутами відношення.

  3. Визначення, чи перебуває відношення в ВКNF. Якщо так, то завершити проектування; в іншому випадку відношення повинне бути розбите на два інших відношення.

  4. Повторення пунктів 2 й 3 для кожного нового відношення, отриманого у результаті декомпозиції.

Правило ланцюжка полягає в такому:

Якщо А>В>С, то в якості функціональної залежності для здійснення проекції використовується крайня права залежність або "кінець ланцюжка" В>С.

^

1.3.5 Методи проектування на основі синтезу відношення


Виключити надмірність у вихідному наборі функціональних залежностей можна шляхом застосування правил виводу. Як відомо, для класу F-залежностей досить використовувати шість таких правил. При цьому критерієм завершення процедури виключення може служити одержання мінімального покриття вихідного набору функціональних залежностей.

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

Алгоритм методу синтезу відносин

Причиною втрати функціональної залежності є деяка функціональна залежность , що не може бути виключена з множини F-залежностей, пов'язаних з одержуваними відношеннями r1 або r2. Таким чином, суть проблеми зводиться до порушення замкнутості реляційних операцій над функціональними залежностями на отриманій схемі БД. Для вирішення цієї проблеми необхідно поповнити мінімальне покриття функціональних залежностей, або, як говорять, підсилити мінімальне покриття.

На шляху вирішення цієї проблеми було б непогано підсилити всі функціональні залежності, зв'язавши їх з унікальними ключами, скажемо, описуючи для них унікальні індекси. Тоді можна контролювати цілісність БД. Для цього необхідно підсилити мінімальне покриття. Просто кажучи, підсилювання мінімального покриття означає, що виділено множину первинних ключів, і всі функціональні залежності з мінімального покриття переглянуті через призму цієї множини з погляду виводності функціональних залежностей розглянутої БД.

Реляційна БД називається повною, якщо:

  • всі функціональні залежності посилені ключами;

  • всі відношення перебувають в 3NF;

  • не існує варіанта БД з меншим числом схем, що задовольняють перерахованим вище властивостям.
1   2   3   4   5   6   7   8   9   ...   19

Схожі:

Конспект лекцій Суми Видавництво Сумду 2009 Міністерство освіти І науки України Сумський державний університет iconКонспект лекцій Суми Сумський державний університет 2012 Міністерство освіти і науки, молоді та спорту України Сумський державний університет
Внутрішній економічний механізм підприємства: конспект лекцій / укладач Н. В. Мішеніна.– Суми : Сумський державний університет, 2012....
Конспект лекцій Суми Видавництво Сумду 2009 Міністерство освіти І науки України Сумський державний університет iconКонспект лекцій Суми Видавництво Сумду 2010 міністерство освіти І науки україНи
Затверджено на засіданні кафедри фінансів як конспект лекцій з дисципліни "Інформаційні системи і технології у фінансах"
Конспект лекцій Суми Видавництво Сумду 2009 Міністерство освіти І науки України Сумський державний університет iconМіністерство освіти І науки україни сумський державний університет до друку та в світ дозволяю на підставі «Єдиних правил»
Методи прийняття управлінських рішень. Конспект лекцій / Укладач Д. О. Смоленніков. – Суми: Вид-во СумДУ, 2008. – 89 с
Конспект лекцій Суми Видавництво Сумду 2009 Міністерство освіти І науки України Сумський державний університет iconКонспект лекцій Суми Видавництво Сумду 2009
Внутрішній економічний механізм підприємства: Конспект лекцій/ Укладач І. В. Новикова. – Суми: Вид-во СумДУ, 2009. – 185с
Конспект лекцій Суми Видавництво Сумду 2009 Міністерство освіти І науки України Сумський державний університет iconМіністерство освіти І науки україНи Сумський державний університет Менеджмент персоналу
Менеджмент персоналу: конспект лекцій / Укладач: К. В. Ілляшенко. – Суми: Вид-во СумДУ, 2010. – 78с
Конспект лекцій Суми Видавництво Сумду 2009 Міністерство освіти І науки України Сумський державний університет iconКонспект лекцій Суми Видавництво Сумду 2009
Психологія творчості : Конспект лекцій / Укладач О. А. Кривопишина.– Суми: Вид-во СумДУ, 2009.– 81 с
Конспект лекцій Суми Видавництво Сумду 2009 Міністерство освіти І науки України Сумський державний університет iconКонспект лекцій Суми Видавництво Сумду 2009
Психологія творчості : Конспект лекцій / Укладач О. А. Кривопишина.– Суми: Вид-во СумДУ, 2009.– 81 с
Конспект лекцій Суми Видавництво Сумду 2009 Міністерство освіти І науки України Сумський державний університет iconМіністерство освіти І науки україни сумський державний університет граматичні таблиці з української мови для студентів-іноземців підготовчого відділення Суми Видавництво СумДУ
Граматичні таблиці з української мови для студентів-іноземців підготовчого відділення / Уклад.: Н. О. Ворона, Т. О. Дегтярьова, Н....
Конспект лекцій Суми Видавництво Сумду 2009 Міністерство освіти І науки України Сумський державний університет iconМіністерство освіти І науки україни сумський державний університет історія України
України: навчальні матеріали для студентів-іноземців підготовчого відділення / Укладачі: М. С. Казанджиєва, О. П. Коньок, Н. О. Тубол,...
Конспект лекцій Суми Видавництво Сумду 2009 Міністерство освіти І науки України Сумський державний університет iconМіністерство освіти І науки україни сумський державний університет медичний інститут кафедра інфекційних хвороб І епідеміології
Методичні рекомендації до семінарських занять лікарів-інтернів спеціальності “Інфекційні хвороби” / Укладачі М. Д. Чемич, Н.І. Ільїна,...
Додайте кнопку на своєму сайті:
Документи


База даних захищена авторським правом ©zavantag.com 2000-2013
При копіюванні матеріалу обов'язкове зазначення активного посилання відкритою для індексації.
звернутися до адміністрації
Документи