Коректність процедури нормалізації. Теорема Хеза
Як було показано вище, алгоритм нормалізації складається з виявлення функціональних залежностей предметної області і відповідної декомпозиції відношень. Припустимо, що ми вже маємо працюючу систему, у якій накопичені дані. Нехай дані коректні в сучасний момент, тобто факти предметної області правильно відбиваються поточним станом бази даних. Якщо в предметній області виявлена нова функціональна залежність (або вона була пропущена на етапі моделювання предметної області, або просто змінилася предметна область), то виникає необхідність заново нормалізувати дані. При цьому деякі відношення доведеться декомпонувати відповідно до алгоритму нормалізації. Виникають природні питання - що відбудеться з уже накопиченими даними? Чи не будуть дані втрачені в ході декомпозиції? Чи можна повернутися назад до вихідних відношень, якщо буде прийняте рішення відмовитися від декомпозиції, чи відновляться при цьому дані?
Для відповідей на ці питання потрібно відповісти на питання - що ж являє собою декомпозиція відношень з погляду операцій реляційної алгебри? При декомпозиції ми з одного відношення одержуємо два чи більше відношень, кожне з який містить частину атрибутів вихідного відношення. В отриманих нових відношеннях необхідно видалити дублікати рядків, якщо такі виникли. Це в точності означає, що декомпозиція відношення є не що інше, як узяття однієї чи декількох проекцій вихідного відношення так, щоб ці проекції в сукупності містили (можливо, з повтореннями) всі атрибути вихідного відношення. Тобто, при декомпозиції не повинні втрачатися атрибути відношень. Але при декомпозиції також не повинні втратитися і самі дані. Дані можна вважати не втраченими в тому випадку, якщо можлива зворотна операція - по декомпонованих відношенням можна відновити вихідне відношення в точності в колишньому вигляді. Операцією, зворотною операції проекції, є операція з'єднання відношень. Є велика кількість видів операції з'єднання (див. лекцію по реляційній алгебрі). Оскільки при відновленні вихідного відношення шляхом з'єднання проекцій не повинні з'явитися нові атрибути, то необхідно використовувати природне з'єднання.
|
|
|
Визначення 6. Проекція R [ X ] відношення R на множину атрибутів X називається власною, якщо множина атрибутів X є власною підмножиною множини атрибутів відношення R (тобто множина атрибутів X не збігається з множиною всіх атрибутів відношення R).
Визначення 7. Власні проекції R1 і R2 відношення R називаються декомпозицією без втрат, якщо відношення R точно відновлюється з них за допомогою природного з'єднання для будь-якого стану відношення R:
|
|
|
R1 JOIN R2 = R.
Розглянемо приклад, що показує, який декомпозиція без утрат відбувається не завжди.
Приклад. Нехай дане відношення R::
| НОМЕР | ПРІЗВИЩЕ | ЗАРПЛАТА |
| Іванов | ||
| Петров |
Розглянемо перший варіант декомпозиції відношення R на два відношення:
Відношення R1.
| НОМЕР | ЗАРПЛАТА |
Відношення R2.
| Прізвище | ЗАРПЛАТА |
| Іванов | |
| Петров |
Природне з'єднання цих проекцій, що мають спільний атрибут "ЗАРПЛАТА", мабуть, буде наступним (кожний рядок однієї проекції з'єднається з кожним рядком іншої проекції):
| НОМЕР | ПРІЗВИЩЕ | ЗАРПЛАТА |
| Іванов | ||
| Петров | ||
| Іванов | ||
| Петров |
Відношення R1 JOIN R2 ¹ R
Отже, дана декомпозиція не є декомпозицією без утрат, тому що вихідне відношення не відновлюється в точному вигляді за проекціями (сірим кольором виділені зайві кортежі).
Розглянемо інший варіант декомпозиції:
| НОМЕР | ПРІЗВИЩЕ |
| Іванов | |
| Петров |
Відношення R1
| НОМЕР | ЗАРПЛАТА |
Відношення R2
За даними проекціями, що мають спільний атрибут "НОМЕР", вихідне відношення відновлюється в точному вигляді. Проте, не можна сказати, що дана декомпозиція є декомпозицією без утрат, тому що ми розглянули тільки один конкретний стан відношення R, і не можемо сказати, чи буде й в інших станах відношення R відновлюватися точно. Наприклад, припустимо, що відношення R перейшло в стан:
|
|
|
| НОМЕР | ПРІЗВИЩЕ | ЗАРПЛАТА |
| Іванов | ||
| Петров | ||
| Ситник |
Відношення R
Здається, що цього не може бути, тому що значення в атрибуті "НОМЕР" повторюються. Але ми ж нічого не говорили про ключ цього відношення! Зараз проекції будуть мати вигляд:
| НОМЕР | ПРІЗВИЩЕ |
| Іванов | |
| Петров | |
| Ситник |
Відношення R1
| НОМЕР | ЗАРПЛАТА |
Відношення R2
Природне з'єднання цих проекцій буде містити зайві кортежі:
| НОМЕР | ПРІЗВИЩЕ | ЗАРПЛАТА |
| Іванов | ||
| Петров | ||
| Петров | ||
| Ситник | ||
| Ситник |
Відношення R1 JOIN R2 ¹ R
Висновок. Таким чином, без додаткових обмежень на відношення R не можна говорити про декомпозицію без утрат.
Такими додатковими обмеженнями і є функціональні залежності. Має місце наступна теорема Хеза [54]:
Теорема (Хеза). Нехай R (A, B, C) є відношенням, і A, B, C атрибути чи множини атрибутів цього відношення. Якщо є функціональна залежність A ® B, то проекції R1 [ A, B ] і R2 [ A, C ] утворять декомпозицію без утрат.
|
|
|
Доказ. Необхідно довести, що R1 JOIN R2 = R для будь-якого стану відношення. В лівій і правій частині рівності стоять множини кортежів, тому для доказу досить довести два включення для двох множин кортежів: R1 JOIN R2 Ê R і R1 JOIN R2 Í R.
Доведемо перше включення. Візьмемо довільний кортеж r (a, b, c)Î R. Згідно до визначення проекції, кортежі r1= (a, b)Î R1 і r2= (a, c)Î R2. Згідно до визначення природного з'єднання кортежі r1= (a, b)і r2= (a, c), що мають однакове значення a спільного атрибута A, будуть з'єднані в процесі природного з'єднання в кортеж r= (a, b, c)Î R1 JOIN R2. Таким чином, включення доведене.
Доведемо зворотне включення. Візьмемо довільний кортеж r= (a, b, c)Î R1 JOIN R2. Доведемо, що він включається також і в R. З визначення природного з'єднання отримаємо, що в R1 JOIN R2 є кортежі r1= (a, b)Î R1 і r2= (a, c)Î R2. Оскільки R1 = R [ A, B ], то існує деяке значення c1, таке що кортеж r1= (a, b, c1)Î R. Аналогічно, існує деяке значення b1, таке що кортеж r2= (a, b1, c)Î R. Кортежі r1 і r2 мають однакове значення атрибута a спільного атрибута A. З цього, у силу функціональної залежності A ® B, випливає, що b=b1. Таким чином, кортеж r2= (a, b1, c)=(a, b, c)Î R. Зворотне включення доведене. Теорема доведена.
Зауваження. У доведенні теореми Хеза наявність функціональної залежності не використовувалося при доведенніі включення R1 JOIN R2 Ê R. Це означає, що при виконанні декомпозиції і наступному відновленні відношення за допомогою природного з'єднання, кортежі вихідного відношення не будуть втрачені. Основний зміст теореми Хеза полягає в доведенні того, що при цьому не з'являться нові кортежі, які відсутні у вихідному відношенні.
Оскільки алгоритм нормалізації (приведення відношень до 3НФ) заснований на наявних у відношеннях функціональних залежностях, то теорема Хеза показує, що алгоритм нормалізації є коректним, тобто в ході нормалізації не відбувається втрати інформації.
Висновки
Ключові рішення, що визначають якість майбутньої бази даних, закладаються на етапі розробки логічної моделі даних. "Хороші" моделі даних повинні задовольняти певним критеріям:
· Адекватність бази даних предметної області
· Легкість розробки і супроводження бази даних
· Швидкість виконання операцій оновлення даних (вставка, відновлення, видалення)
· Швидкість виконання операцій вибірки даних
Перша нормальна форма (1НФ) - це звичайне відношення. Відношення в 1НФ має наступні властивості:
· У відношенні немає однакових кортежів.
· Кортежі не упорядковані.
· Атрибути не упорядковані.
· Усі значення атрибутів атомарні.
Відношення, що знаходяться в 1НФ є "поганими" у тому сенсі, що вони не задовольняють обраним критеріям - є велика кількість аномалій оновлення, для підтримки цілісності бази даних потрібно розробляти складні тригери.
Відношення R знаходится в другій нормальній формі (2НФ) тоді і тільки тоді, коли відношення знаходиться в 1НФ і не має неключових атрибутів, що залежать від частини складеного ключа.
Відношення в 2НФ "кращі", ніж у 1НФ, але ще недостатньо "хороші" - залишається частина аномалій оновлення, як і раніше потрібні тригери, що підтримують цілісність бази даних.
Відношення R находиться в третій нормальній формі (3НФ) тоді і тільки тоді, коли відношення знаходиться в 2НФ і всі неключові атрибути взаємно незалежні.
Відношення в 3НФ є самими "хорошими" з погляду обраних нами критеріїв - усунуті аномалії оновлення, потрібні тільки стандартні тригери для підтримки посилальної цілісності.
Перехід від ненормалізованих відносин до відношень у 3НФ може бути виконаний за допомогою алгоритму нормалізації. Алгоритм нормалізації полягає в послідовній декомпозиції відношень для усунення функціональних залежностей атрибутів від частини складеного ключа (приведення до 2НФ) і усунення функціональних залежностей неключових атрибутів один від одного (приведення до 3НФ).
Коректність процедури нормалізації (декомпозиція без втрати інформації) доводиться теоремою Хеза.
[1] Пояснення 1. Говорять, що відношення R находится в 1НФ, якщо воно задовольняє визначенню відношення. Це, власне, тавтологія, адже з визначення відношення випливає, що інших відношень не буває. Дійсно, визначення відношення описує, що є відношенням, а що - ні, отже, відношень у непершій нормальній формі просто немає.
Пояснення 2. Говорять, що відношення R знаходиться в 1НФ, якщо його атрибути містять тільки скалярні (атомарні) значення. Знову ж, визначення відношення спирається на поняття домену, а домени визначені на простих типах даних.
Непершу нормальну форму можна одержати, якщо допустити, що атрибути відношення можуть бути визначені на складних типах даних - масивах, структурах, чи навіть на інших відношеннях. Легко собі представити таблицю, у якої в деяких комірках містяться масиви, в інших комірках - визначені користувачами складні структури, а в третіх комірках - цілі реляційні таблиці, що у свою чергу можуть містити такі ж складні об'єкти. Саме такі можливості надаються деякими сучасними постреляційними й об'єктними СУБД.
Вимога, що відношення повинно містити тільки дані простих типів, пояснює, чому відношення іноді називають плоскими таблицями (plain table). Дійсно, таблиці, що задають відношення двумірні. Один вимір задається списком стовпців, другий вимір задається списком рядків. Пара координат (Номер рядка, Номер стовпця) однозначно ідентифікує комірку таблиці і значення, що міститься в ній. Якщо ж допустити, що в комірці таблиці можуть міститися дані складних типів (масиви, структури, інші таблиці), то така таблиця буде вже не плоскої. Наприклад, якщо в комірці таблиці міститься масив, то для звертання до елемента масиву потрібно знати три параметри (Номер рядка, Номер стовпця, номер елемента в масиві).
У такий спосіб з'являється третє пояснення Першої Нормальної Форми:
Пояснення 3. Відношення R знаходиться в 1НФ, якщо воно є плоскою таблицею.
Ми свідомо обмежуємося розглядом тільки класичної реляційної теорії, у якій усі відношення мають тільки атомарні атрибути і свідомо знаходяться в 1НФ.
Дата добавления: 2016-01-05; просмотров: 22; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!