Главная | Обратная связь

Мотивування нормальної форми Бойса-Кодда

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

 

31. Приклади нормалізації до 3НФ

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

Продовжимо розгляд прикладу з відношенням ІСПИТОВА ВІДОМІСТЬ На початку цієї лекції ми привели відношення до першої нормальної форми.

Код студента	Прізвище	Код іспиту	Предмет	Дата	Оцінка
	Сергєєв		Математика	5.08.03
	Іванов		Математика	5.08.03
	Сергєєв		Фізика	9.08.03
	Іванов		Фізика	9.08.03

Ключем даного відношення буде сукупність атрибутів – Код студента і Код іспиту.

Для коротшого запису процесу нормалізації введемо наступні позначення:

КС – код студента, КЕ – код іспиту, Ф – прізвище, П – предмет, Д – дата, О – оцінка.

Випишемо функціональні залежності

КС, КЕ ® Ф, П, Д, О КС, КЕ ® Ф КС, КЕ ® П КС, КЕ ® Д КС, КЕ ® ОКЕ ® П КЕ ® Д КС ® Ф

Відповідно до визначення, відношення знаходиться у другій нормальній формі (2НФ), якщо воно знаходячись в 1НФ і кожному неключовий атрибут залежить від первинного ключа і не залежить від частини ключа. Тут атрибути П, Д, Ф залежать від частини ключа. Аби позбавитися від цих залежностей необхідно провести декомпозицію відношення. Для цього використовуємо теорему про декомпозицію.

Маємо відношення R(КС, Ф, КЕ, П, Д, О). Візьмемо залежність КС ® Ф відповідно до формулювання теореми вихідне відношення дорівнює з'єднанню його проекцій R1(КС, Ф) і R2(КС, КЕ, П, Д, О).

У відношенні R1(КС, Ф) існує функціональна залежність КС ® Ф, ключ КС – складений не ключовий атрибут Ф не залежить від частини ключа. Це відношення знаходиться у 2НФ. Оскільки в цьому відношенні немає транзитивних залежностей, відношення R(КС, Ф) знаходиться у 3НФ, що й вимагалося від нас.

Розглянемо відношення R2(КС, КЕ, П, Д, О) із складеним ключем КС, КЕ. Тут є залежність КЕ ® П, КЕ ® Д, КЕ ® П, Д. Атрибути П, Д залежать від частини ключа, отже відношення не знаходиться у 2НФ. Відповідно до теореми про декомпозицію вихідне відношення (використовуємо функціональну залежність КЕ ® П, Д) дорівнює з'єднанню проекцій R3(КЕ, П, Д), R4(КС, КЕ, О). Відносно R3( КЕ, П, Д) існують функціональні залежності КЕ ® П, КЕ ® Д, КЕ ® П, Д. Залежності неключових атрибутів від частини ключа немає, отже відношення знаходиться у 2НФ. Транзитивних залежностей в цьому відношенні так само немає, отже відношення знаходиться у 3НФ.

Таким чином, вихідне відношення приведене до трьох відношень, кожне з яких знаходиться у третій нормальній формі R1(КС, Ф), R3(КЕ, П, Д), R4(КС, КЕ, О).

Відмітимо, що відносно R4 атрибути КС, КЕ є зовнішніми ключами, використовуваними для встановлення зв'язків з іншими відношеннями. Представимо отриману модель у вигляді діаграми об'єктів-зв'язків (ER-діаграми). Для наочності і можливості подальшого програмування перейдемо до англійських назв об'єктів (відношень) і атрибутів.

Відношення R1 представляє об'єкт student з атрибутами id_st (первинний ключ), surname.Відношення R3 представляє об'єкт exam_st з атрибутами id_ex (первинний ключ), subject, date.Відношення R4 представляє об'єкт mark_st з атрибутами id_st (зовнішній ключ), id_ex (зовнішній ключ), mark. Первинний ключ тут id_st, id_ex.

 

32. Фізичні моделі даних (внутрішній рівень). Структура пам’яті комп’ютера

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

Фізичні моделі даних служать для відображення моделей даних. Основними поняттями моделі даних є поле, логічний запис, логічний файл. Слово "логічний" введене, аби відрізняти поняття, що відносяться до логічної моделі даних, від понять, що відносяться до фізичної моделі даних. Основними поняттями фізичної моделі даних, використовуваними для представлення логічної моделі даних, є поле, фізичний запис, фізичний файл. Зокрема, логічний запис, що складається з полів, може бути представлений у вигляді фізичного запису (з тих же полів), логічний файл – у вигляді фізичного файлу. Перш ніж конкретизувати поняття, що відносяться до фізичної моделі даних, розглянемо структуру пам'яті ЕОМ.

Найважливішою особливістю пам'яті ЕОМ, що в значній мірі визначає методи організації даних і доступу до них, є її неоднорідність. Існують два різні типи пам'яті – оперативна (ОП) і зовнішня (ВП), причому процесор працює лише з даними з оперативної пам'яті.

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

Відзначимо основні властивості оперативної пам'яті:

· одиницею пам'яті є байт;

· пам'ять безпосередньо (прямо) адресована – кожен байт має адресу;

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

Відзначимо основні властивості зовнішньої пам'яті:

· мінімальною одиницею, що адресується, є фізичний запис;

· для подальшої обробки (наприклад, роботи з полями) запис має бути прочитаний в оперативну пам'ять;

· час читання запису в ОП на декілька порядків вищий (більший) за час обробки процесором запису з ОП;

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

 

33. Представлення екземпляра логічного запису

Логічний запис представляється в оперативній пам'яті таким чином:

Логічний запис		Послідовність байтів ОП
Поле 1	Поле 2	...	Поле N		B1	B2	...	BN
Тип поля		Bi – послідовність байтів ОП, використовувана для зберігання поля i
Характеристика поля
Довжина

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

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

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

Конкретною реалізацією такої схеми є поле типа МЕМО в СУБД (dBase III+, FoxPro, Access і т.д.).

 

34. Організація обміну між оперативною і зовнішньою пам’яттю

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

Введення вихідних даних у БД здійснюється таким чином:

· в ОП послідовно вводяться k екземплярів логічних записів (кортежів);

· введені k екземпляри об'єднуються у фізичний запис (блок);

· фізичний запис заноситься в зовнішню пам'ять.

Введення k екземплярів записів вихідної таблиці, що складають i‑ий фізичний запис.

Обробка даних, що зберігаються в зовнішній пам'яті, здійснюється таким чином:

· фізичний запис (блок) прочитується в оперативну пам'ять;

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

У деяких СУБД (наприклад, MS SQL Server) одиницею обміну між оперативною і зовнішньою пам'яттю є сторінка (вид фізичного запису, розмір якого фіксований і не залежить від довжини логічного запису). Організація обміну між оперативною і зовнішньою пам'яттю у цьому випадку аналогічна вищеописаній. Відмінність тут полягатиме в тому, що екземпляри логічних записів формуються в буфері, розміром у сторінку, якщо розмір сторінки не кратний довжині логічного запису, сторінка може бути заповнена неповністю, фізичний запис на зовнішньому носієві, відповідно, буде заповнений не повністю.

 

35. Структура зберігання даних у зовнішній пам’яті комп’ютера. Послідовне розміщення фізичних записів

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

Фізичний запис з номером I містить логічні записи з номерами

(I – 1) k+1(I – 1) k+2...(I – 1) k+k I = 1, 2, ..., [N/k];

знаком [N/k] позначимо найближче ціле, більше або рівне N/k, ‑ ціле зверху.

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