Організація баз даних та знань (стр. 9 из 26)

У відношенні 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;

· не існує варіанта БД з меншим числом схем, що задовольняють перерахованим вище властивостям.

2 Введення в структуровану мову запитів - SQL

2.1 Елементи мови SQL

У даній темі розглянемо елементи мови SQL (Structured Query Language). Мова SQL стала фактично стандартною мовою доступу до БД. Всі СКБД, що претендують на назву "реляційні", реалізують той або інший діалект SQL. Багато які нереляційні системи також мають у цей час засоби доступу до реляційних даних. Метою стандартизації є переносимість додатків між різними СКБД.

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