Перша і друга нормальні форми схем відношень

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

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

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

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

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

Теорема Хіта. Нехай задана схема відношення R = (U, F) і U = = X ∪ Y ∪ Z, X → Y, тоді декомпозиція R = (R1, R2), де R1 = (X ∪ Y), R2 = (X ∪ Z), володіє властивістю з'єднання без втрат.

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

Нехай U – множина всіх атрибутів відношення R. Присутність щодо неповної залежності від ключа означає, що ∃ A ((A ⊂ K) ∧ (B ⊄ A) ∧ (A → B)). Побудуємо декомпозицію Rl = (A ∪ B), R2 = (U \ B). Відношення R1 і R2 вже не містять зазначеної неповної залежності, і отримана декомпозиція володіє властивістю з'єднання без втрат. Далі аналогічні перевірки застосовуються до відносин R1 і R2, так продовжується до тих пір, поки не отримаємо декомпозицію ρ = (R1, R2,..., Rk), кожна з подсхем якої не містить неповних залежностей непервичных атрибутів від ключа. Декомпозиція ρ і є шуканої другий нормальною формою схеми R.

Описаний спосіб обґрунтовується також наступними властивостями декомпозиції.

а) Нехай задана схема відношення R = (U, F), ρ = (R1, R2,..., Rk) – декомпозиція R володіє властивістю з'єднання без втрат відносно F, a Fi для кожного i означає проекцію U на Ri. Припустимо, що σ = (S1, S2,..., Sm) – декомпозиція Ri, що володіє властивістю з'єднання без втрат щодо Fi. Тоді декомпозиція R в подсхемы (R1,..., Ri – l, S1,..., Sm, Ri + l,..., Rk) – також володіє властивістю з'єднання без втрат щодо F.

б) Припустимо, що R, F, ρ ті ж, що в пункті а). Нехай τ = (R1, R2,..., Rk, Rk + l,..., Rt) – декомпозиція R-деяке безліч схем, яке включає всі схеми з ρ. Тоді τ також володіє властивістю з'єднання без втрат щодо F.

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

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

Нехай задана схема R = (U, F), вважаємо, що всі залежності в F в правій частині містять тільки один атрибут (завжди можна перетворити F до такого виду). Припустимо, будується декомпозиція R1 = (U1) і R2 = (U2), причому Ul = X ∪ {y}, X ⊂ U, y ∈ U, (Х → y) ∈ F+; U2 = U \ {y}.

Для отримання проекції F на U2 достатньо знайти всі залежности вида Xi → y, содержащиеся в F. Затем каждую зависимость, содержащую атрибут у в левой части заменить группой зависимостей, подставляя вместо у множества Xi. Те зависимости, где атрибут y находится в правой части, удаляются, в результате получим проекцию F на U2 (точнее, покрытие проекции). Для получения проекции F на U1 придется просмотреть замыкания подмножеств множества U1 относительно F, но множество U1 обычно невелико. Заметим также, что всегда удобнее работать, если все зависимости F полные (такое преобразование F сделать не сложно), модифицированные зависимости при получении проекции F на U2 также имеет смысл приводить к полным. При рассмотрении U1 в случае, если Х → y – полная зависимость, следует просматривать только замыкания подмножеств, содержащих y. Декомпозицию схемы отношения при переходе ко второй нормальной форме удобно строить в виде дерева. Пусть задана схема R = (U, F). Вначале дерево состоит только из одной вершины, соответствующей отношению R. Далее находим зависимость непервичного атрибута y от части ключа Х, (Х → y) ∈ F, и строим две нижестоящие вершины: одна из них соответствует отношению R1 = (U \ {y}), вторая – отношению R2 = = (X ∪ {y}), далее, если необходимо, аналогичную декомпозицию осуществляем для висящих вершин (листьев) дерева; этот процесс продолжается до тех пор, пока все висящие вершины не будут соответствовать подсхемам во второй нормальной форме, совокупность этих подсхем и является искомой декомпозицией исходной схемы отношения. В принципе можно рассматривать вместо одного атрибута y в правых частях выделяемых зависимостей множества атрибутов, но тогда несколько усложнится задача проектирования F на подсхемы. Желательно также рассматривать только полные функциональные зависимости. П р и м е р Для схемы R = (U, F), U = {A1, A2, А3, А4, А5, А6, А7}, F = {А1 → A3; А3 → А5; А2 → А4; А4 → А6; А5, А6 → А7} требуется получить вторую нормальную форму схемы отношения R. Отношение имеет единственный ключ К = {А1, А2}, множество непервичных атрибутов {А3, А4, А5, А6, А7}. Зависимость А1 → A3 является нежелательной, так как непервичный атрибут A3 зависит от части ключа. Выделяем эту зависимость в отдельное отношение, получаем:

R1 = ({A1, A2, A4, A5, A6, A7}, {Al → A5; А2 → А4; А4 → А6; А5, А6 → А7}). Зависимость А1 → A5 получена в результате проецирования F нa подсхему R1; ключом отношения R1 является {А1, А2}. R2 = ({A1, A3}, {A1 → A3}), единственный ключ R2 – {А1}. R2 находится во второй нормальной форме, в R1 нежелательной является зависимость А1 → А5. Получаем декомпозицию R1: R11 = ({A1, A2, A4, A6, A7}, {A2 → А4; А4 → А6; А1, А6 → А7}), ключ R11 – {А1, А2}, R12 = ({A1, A5}, {A1 → A5}), ключ R12 – {А1}. R12 находится во второй нормальной форме, в R11 нежелательной является зависимость А2 → А4, получаем декомпозицию R11: R111 = ({А1, А2, А6, А7}, {А2 → A6; А1, А6 → А7}), ключ – {А1, А2}, R112 = ({A2, A4}, {A2 → А4}), ключ R112 – {А2}. R112 находится во второй нормальной форме, в R111 нежелательной является зависимость А2 → А6, получаем декомпозицию R111: R1111 = ({A1, A2, A7}, {А1, А2 → А7}), ключ R1111 – {А1, А2}, R1112 = ({A2, A6}, {A2 → A6}), ключ R1112 – {А2}. R1111 и R1112 находятся во второй нормальной форме, искомая декомпозиция (вторая нормальная форма отношения R) имеет вид ρ = (R2, R12, R112, R1111, R1112). Дерево декомпозиции имеет вид:

НАМАЛЮВАТИ СХЕМУ ДЕРЕВА ДЕКОМПОЗИЦІЇ(СТР.39)

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

ρ 1 = ({A1, A3}, {А3, А5}, {А2, А4}, {А4, А6}, {А5, А6, А7}),

причому ρ вдаліше, ніж ρ 1, в сенсі мінімізації аномалій бази даних.

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

4.3.2. Третя нормальна форма схем відношень.

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

Нехай задана схема відношення R = (U, F), A, C ⊆ U. Функціональна залежність А → С називається транзитивною, якщо існує підмножина атрибутів В ⊂ U таке, що

А ⊉, В ⊉ С, А → В, В↛ А і В → С.

Зазначимо, що наявність або відсутність залежності С → В значення не має. Якщо такої залежності немає, то транзитивна залежність називається суворою транзитивною залежністю. Наприклад, R = ({А1, А2, А3, А4, А5}, {А1 → А2; А2 → А3; А1 → А4; А4 → А5; А5 → А1}). Тут залежність А1 → А3 є транзитивною, так як маємо

А1 → А2 → А3 і А2↛ Al.

В той же час залежність Al → А5 не є транзитивною, хоча і є ланцюжок А1 → А4 → А5, але тут (А4 → Al) ∈ F+, що суперечить визначенню транзитивної залежності.

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

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

Третя нормальна форма існує для будь-якої схеми відношення, причому часто не єдина.

Можливість неоднозначного перетворення до ТНФ, а також бажання зберегти в підсхемах більш «близькі» взаємозв'язки між атрибутами приводить до поняття оптимальної ТНФ, що містить найменше число підсхем, і крім того, у випадку залежно А → В → С підсхемы не повинні включати одночасно «несуміжні» компоненти А і С.

Отримати ТНФ (не завжди оптимальну) можна за допомогою модифікації алгоритму Хіта, яку застосовували для отримання другої нормальної форми.

Суть алгоритму полягає в наступному. Нехай задана схема відношення R = (U, F), А, В, C ⊂ U, А → В → С – транзитивна залежність (складається з непервичных атрибутів), тоді переходимо до декомпозиції ρ = (R1 = (U1, F1), R2 = (U2, F2)), де U1 = U \ З, U2 = B ∪ C, F1 і F2 – проекції F відповідно на U1 і U2. Потім, якщо необхідно, проводиться декомпозиція R1 і R2, і так далі до тих пір, поки всі подсхемы не опиняться в ТНФ.

Зауважимо, що задача перевірки, чи є схема відношення в ТНФ, відноситься до NP-важких, що пов'язано із завданням виділення всіх непервинних атрибутів відношення. В принципі можна виконувати декомпозицію залежно А → В → С не перевіряючи, знаходяться первинні атрибути в С чи ні, але це може привести до надлишку підсхем, що знижує «якість» декомпозиції.

ПРИКЛАД

Для схеми R = ({A1, A2,..., А6}, {А1, А2 → А3; А3 → А4; А4 → А5, А4 → А6}) потрібно отримати ТНФ. Первинні атрибутів {А1, А2}, непервичные – {A3, А4, А5, А6}. Транзитивна залежність: А1, А2 → А3 → А4.

На першому етапі отримуємо: R1 = ({A1, A2, A3, А5, А6},

{А1, А2 → A3; А3 → А5; А3 → А6});

R2 = ({A3, A4}, {A3 → A4}). R2 знаходиться в ТНФ.

В R1 небажана транзитивна залежність: А1, А2 → A3 → А5.

Будуємо декомпозицію, отримуємо:

R11 = ({Al, А2, А3, А6}, {А1, А2 → A3; А3 → А6}),

R12 = ({A3, A5}, {A3 → A5}). R12 знаходиться в ТНФ.

У R11 небажана транзитивна залежність: Al, А2 → A3 → А6.

Будуємо декомпозицію, отримуємо:

R111 = ({А1, А2, A3}, {А1, А2 → A3}), R112=({A3, A6}, {A3 → A6}).

R111 і R112 знаходяться в ТНФ.

Маємо ТНФ вихідної схеми ρ = (R2, R12, R111, R112).

Слід зазначити, що простота описаного методу тільки здається, основна складність полягає у виявленні транзитивних залежностей, які не обов'язково «видно» за системою утворюють структури функціональних залежностей, наприклад, у випадку

R = ({А1, А2,..., А5}, {А1, А2 → А3; А1, А2 → А4; А3, А4 → А5})

транзитивної залежністю є ланцюжок А1, А2 → А3, А4 → А5, яка здається очевидною тільки з-за малої кількості атрибутів. Багато в чому процес виявлення транзитивних залежностей полегшується графовым поданням схем відношень. Нижче наводяться алгоритми приведення схеми відношення до ТНФ, не потребують виділення транзитивних залежностей в явному вигляді, але часто дають декомпозиції, далекі від оптимальних.

Алгоритм Делобеля – Кейсі.

Нехай задано схему відношень R = (U, F).

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

2. По кожній залежності (Xi → Yi) ∈ F* утворити подсхему Ri = = (Ui = Xi ∪ Yi); якщо при цьому для деяких i і j, i ≠ j, виявиться, що Uj ⊆ Ui, то Rj видаляється.

3. Якщо хоча б одна з отриманих підсхем містить ключ вихідного відношення (для цього достатньо перевірити, чи виконується хоча б для одного Ui співвідношення F_i⁺ =U)то сукупність отриманих R _i, = + i є відношення R, інакше додати до отриманої декомпозиції ще одну схему, що складається з довільного ключа відношення R.

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

ПРИКЛАД

Для схеми R = ({А_1, А_2, А_3, А_4, А_{5}, {}А_1, А_{2 →} А_3; А_{3 →} А_4; А_3, А_{4 →} А_5}) отримати ТНФ. Переходимо до елементарного функціонального базису. Залежно А3, А4 → А5 атрибут А4 надлишковий, отримаємо F* = {А1, А2 → А3; А3 → А4; АЗ → А5). Будуємо декомпозицію

ρ = ({А1, А2, А3}, {А3, А4}, {А3, А5}).

Оскільки {А1, А2, А3}+ = {А1, А2, А3, А4, A5} = U, значить, U1 містить ключ вихідного відношення і ρ є ТНФ відношенням R.

Тут підсхеми {А3, А4} і {А3, А5} можна об'єднати в одну {А3, А4, А5}, але в загальному випадку такі об'єднання вимагають додаткової перевірки, так як подсхема, отримана в результаті об'єднання, може не бути в ТНФ.

Можна модифікувати наведений алгоритм наступним чином.

1. Крок 1 попереднього алгоритму.

2. Знайти множину всіх первинних атрибутів вихідного відношення Up і непервинних U \ Up.

3. Переглянути всі залежно Х → Y F*, якщо Х не є ключем і Y – непервинний атрибут (якщо таких залежностей F немає, то R в ТНФ), будуємо декомпозицію Ul = X ∪ Y, U2 = U \ Y, т. e. такі залежності виділяються в окремі відношення.

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

4.3.3. Посилена третя нормальна форма схем відносин (нормальна форма Бойса – Кодда)

Якщо третя нормальна форма схем відносин не містить неповних та транзитивних залежностей будь-яких атрибутів від ключа, то вона називається посиленою третьої нормальної форми (ПТНФ).

Наведене визначення ПТНФ еквівалентно наступного визначення, в якому не використовуються такі поняття, як ключ, первинні і неперввинні атрибути, повна і транзитивна залежність.

Посиленою третьою нормальною формою схеми відношення R = = (U, F) називається ця схема, якщо вона нормалізована і для будь-якого набору атрибутів A ⊂ U вірно, що якщо який-небудь атрибут x ∈ U \ A функціонально залежить від А, то і всі атрибути відношень функціонально залежать від А; декомпозиція схеми R, кожна підсхема якої задовольняє цим вимогам, володіє властивістю з'єднання без втрат.

Таким чином, R знаходиться в ПТНФ тоді і тільки тоді, коли для будь-якої залежності (X → Y) і X ⊉ Y виконується Х⁺ = U. Очевидно, що якщо відношення знаходиться в УТНФ, то воно знаходиться і в ТНФ, зворотне, взагалі кажучи, не вірно. ПТНФ називають також нормальна форма Бойса – Кодда. Будь-яка схема відношення може бути приведена до ПТНФ. Наступний алгоритм отримання ПТНФ ґрунтується на теоремі Хіта.

Нехай задана схема відношення R = (U, F). Потрібно отримати ПТНФ схеми R.

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

2. Далі декомпозицію ρ для R будуємо ітеративним методом, при цьому ρ завжди буде володіти властивістю з'єднання без втрат. Спочатку ρ складається тільки з R. Якщо S – схема з ρ і в S є залежність X → Y, Х ⊇ Y і Х не містить ключа S, то замінюємо S декомпозицією S1 = (U1, F1), S2 = (U2, F2), де U1 = X ∪ Y, U2 = U \ Y (тут треба, що S = (U, F)). Так продовжується до тих пір, поки всі подсхемы ρ не опиняться в ПТНФ.

Зауважимо, що пункт 1 виконувати не обов'язково, але тоді сильно зросте трудомісткість проектування F на підсхемы.

ПРИКЛАД

Для схеми R = (U, F) = ({A1, A2,..., А6}, {А1 → А2, А2, А4 → А1; А2 → A3; А3 → А4; А3, А4 → А5; А5 → А6}) потрібно отримати ПТНФ. Перейшовши до елементарного функціонального базису, отримаємо F *= {А1 → А2; А2 → А1; А2 → A3; А3 → А4; А3 → А5; А5 → А6}.

Крок 1. Перевіряємо залежності:

1) для залежності А1 → А2 виконується {Al}⁺ = U, отже, залежність А1 → А2 задовольняє ПТНФ;

2) для залежностей А2 → А1 і А2 → A3 виконується {A2}⁺ = U, отже, ці залежності задовольняють ПТНФ;

3) для залежностей A3 → А4 виконується {A3}⁺ ≠ U. Отже, залежність A3 → А4 не задовольняє ПТНФ. Виділяємо залежність A3 → А4 в окрему схему, отримуємо:

R1 = ({A3, A4}, {A3 → А4}),

R2 = ({A1, A2, A3, A5, A6}, {A1 → А2; А2 → А1; А2 → A3; A3 → А5; А5 → A6}).

Крок 2. R1 знаходиться в ПТНФ. Перевіряємо залежність A3 → А5; для неї виконується {А3}⁺ ≠ U2. Отже, вона не задовольняє ПТНФ. Виділяємо залежність A3 → А5 в окрему схему. Отримуємо:

R21 = ({A3, A5) {A3 → А5}),

R22 = ({A1, A2, A3, A6}, {A1 → A2; А2 → А1; А2 → А3; A3 → А6}).

Крок 3. R21 знаходиться в ПТНФ. Розглядаємо залежність A3 → А6; для неї виконується {А3}⁺ ≠ U22. Отже, вона не задовольняє ПТНФ. Виділяємо залежність A3 → А6 в окрему схему. Отримуємо:

R221 = ({A3, A6}, {A3 → A6}),

R222 = ({A1, A2, A3), {A1 → А2; А2 → А1; А2 → А3}). R221 і R222 знаходяться в ПТНФ. Отже,

ПТНФ ρ = (R1, R21, R221, R222) для схеми R.

Дерево декомпозиції має вигляд: (стр.46)

Однак отримана декомпозиція має такі суттєві недоліки.

1. R1 і R21 можна об'єднати в одну схему, одержимо R1 = ({A3, A4, A5}, {A3→ А4; А3 → А5}). Зауважимо, що так робити не можна не завжди. Наприклад, якщо б була залежність А4 → А5, то R1 отримали б транзитивную залежність A3 → А4 → А5.

2. А3 і А6 недоцільно об'єднувати в одну підсхему, оскільки у вихідній схемі є транзитивна залежність A3 → А5 → А6, де А3 і А6 не суміжні, і тому таке об'єднання призведе до надмірності даних в базі. Краще замість {А3, А6} використовувати подсхему {А5, А6}. Легко бачити, що така заміна не порушує властивості з'єднання без втрат, просто функціональні залежності перевіряються в іншому порядку. Таким чином, прийшли до декомпозиції:

ρ = (({А3, А4, А5}, {А3 → А4; А3 → А5}), ({А5, А6}, {А5 → А6}),

({А1, А2, А3), {А1 → А2; А2 → А1; А2 → А3})).

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

1.Знайти довільний ключ К.

2. Побудувавши К⁺, виписати всі К⁽¹⁾ (див. алгоритм побудови замикань).

3.Переглядати К^(і) у зворотному порядку і виділяти в окремі підсхеми залежності X → Y, що порушують ПТНФ і такі, що Х і Y належать до К^(і) найбільшими номерами i.

У багатьох випадках такий підхід виключає включення в подсхемы несуміжних транзитивних компонент.

Зауважимо, що не завжди можна перетворити схему відношення до ПТНФ із збереженням залежностей.

Наприклад, R = ({A1, A2, A3}, {A1, A2 → A3; А3 → Al}).

Схема R знаходиться в ТНФ, але не ПТНФ, оскільки для залежності A3 → А1 виконується {A3}⁺ ≠ {А1, А2, А3}. ПТНФ дає декомпозиція: R1 = ({A1, A3), {A3 → A1}), R2 = ({A2, A3}), але при цьому втрачається залежність А1, А2 → A3, і, отже, побудувати УТНФ із збереженням цієї залежності неможливо.