Лекція 5. Відношення на базах даних і структури даних

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

1. Відношення і структури. Вище ми підкреслювали можливість задання множин виз­на­ченням властивостей її елементів. Цей зв’язок двобічний. Звичайно, властивість характер­ризує елемент множини. Зв’язок елементів задається від­ношенням. Останнє задається множиною n-ок, тобто графіком відношення. Цю множину можна також задати властивістю, але мова вже йде про властивість n-ок. Як зазначено вище, цей зв’язок також двобічний. Властивість n-ок будемо називати предикатом і зображувати формулою. Істинність останньої взаємно однозначно пов’язана з належністю відношенню відповідної n-ки. Якщо P(x₁,...,x_n) - предикат або формула на змінних x₁,...,x_n, то тоді можна побудувати множину n-ок:

{(x₁,..., x_n): P(x₁,...,x_n) набуває істинного значення}.

Нехай задана множина {(x1,...,xn)}. Тоді формулу P(x1,..., xn) можна розв’язати, тобто з’ясувати істинна вона чи ні, використовуючи належність відповідної n-ки до множини {(x1,...,xn)}. Звичайно, P не обов’язково буде представлено “гарною” формулою. Таким чи­ном, ці два підходи еквівалентні.

Визначення. При обробці даних набори з n елементів називають записами; елементи цих наборів називають полями. Записи, що визначають певне відношення, звичайно містять­ся в одному файлі. Якщо вимагати, щоб декілька файлів містили сукупність записів, що задовільняють деяким відношенням, то ми отримаємо (реляційну) базу даних.

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

Сучасна теорія баз даних забезпечує вивчення так званих нормальних форм, однак обгрунтування деяких з них оче­ви­дне лише в простих випадках. Ми розглянемо тільки три нормальних форми для таких задач:

- вставити новий набір з n елементів;

- вилучити набір з n елементів;

- модифікувати набір, що містить n елементів.

Почнемо з найпростішої нормальної форми.

Визначення. Файли в першій нормальній формі ( 1NF ), чи – простіше - нормалізовані файли, мають записи фіксованої довжини, що складаються з елементів, взятих з множин, чиї елементи далі не можуть бути розбиті, і в кожен момент часу цей файл може бути зо­бражений як масив значень m´n. Кожен запис, будучи набором з n елементів, може бути записаний як рядок масиву.

Приклад 5.1. Розглянемо відношення FAM1 між батьками і дітьми. Кожен запис міс­тить в вказаному порядку прізвище і імена батька, матері і дітей. Отже, можливі записи:

(Коміренко, Петро, Оксана, (Ольга, Тарас)) Î FAM1,

(Заплюйсвічко, Федір, Лідія, (Любов)) Î FAM1.

Тепер, якщо ми позначимо через F і М множини батьків і матерів, то, за означенням, маємо:

Петро (Коміренко) Î F, Оксана (Коміренко) Î М,

Федір (Заплюйсвічко) Î F, Ліза (Заплюйсвічко) Î М.

Таким чином, в сім’ї Коміренко більше однієї дитини, відповідний запис більше, і, отже, порушені умови першої нормальної форми.

З FAM1 ми можемо отримати FAM2, побудувавши його з S, F, M і С, де S – множина прізвищ, а С – множина дітей, шляхом конструювання записів:

(Коміренко, Петро, Оксана, Ольга),

(Коміренко, Петро, Оксана, Тарас),

(Заплюйсвічко, Федір, Лідія, Любов).

Відношення FAM2 знаходиться в 1NF і може бути представлене за допомогою табл.1.

Таблиця 1

Прізвище	Батько	Мати	Дитина
Коміренко Коміренко Заплюйсвічко	Петро Петро Федір	Оксана Оксана Лідія	Ольга Тарас Любов

 

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

Визначення. При використанні таблиці для зображення відношення (файлу з n – вимір­ним наборами/записами, що записується у вигляді рядків) стовпці називаються атpибутами.

Отже, ПРІЗВИЩЕ, БАТЬКО, МАТИ і ДИТИНА є атpибутами різних полів в FAM2. Для отримання доступу до записів у файлі використовується так звані ключі. Більш точно це може бути визначене у термінах атрибутів.

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

Варто зазначитити, що в файлі може бути багато різних ключів.

Кожен ключ відношення/файлу FAM2 повинен містити атрибут ДИТИНА.

Розглянемо інший приклад.

Приклад.Кожен власник комп’ютера змушений придбати до нього запасні частини. Тому ми можемо розглянути файл, структура котрого наведена у табл.2.

Таблиця 2

Компанія	Відділ	Менеджер
“Пріоком” ІНКОМ “Галичина” “МКС” “Золотий лев” “Білайт” ХБК	Київ Київ Львів Харків Львів Київ Херсон	Гудима Шевчук Шевчук Простибоженко Простибоженко Гудима Моргенталлер

 

Атрибут Компанія є ключем в SUP1; вся інша інформація в файлі доступна за до­по­могою ключа. Таким чином, наприклад, можливо отримати атрибут Відділ за допомогою ключа “Золотий лев” чи ж Менеджер з “Білайт”.

Визначення. Якщо запис локалізований за допомогою якогось ключа, то поле, що ви­діляється з цього запису, називається проекцією. В даному контексті проекцією є Відділ, Менеджер. Будемо також говорити, що ці атрибути залежать від ключа.

На рис 14 представлені у графічному вигляді залежності полів в відношенні SUP1.

	Місцезнаходження

Рис. 14

Менеджер

Компанія

 

Приклад 3. Модифікуємо файл SUP1 з метою включення туди інформації про при­сутність на складі запасних частин і про їх кількість, які окремий продавець бажає продати окремою угодою. Включимо в файл також код поставки, з котрого ми можемо з’ясувати швидкість і частоту поставок. Для уникнення зайвої деталізації будемо використовувати номер компанії і номер запасної частини (табл.3.).

Таблиця 3

Компанія	Місцезнаходження	Продавець	Запчастина	Кількість
	Київ Київ Київ Київ Київ Львів Львів Львів Львів Львів Київ

 

З таблиці 3 визначимо, які перетворення ми можемо робити з SUP2, а які ні:

¨ вставка. Наприклад, ми не можемо додати в файл запис, що компанія 4 (“МКС”) знаходиться в Харкові, без вказання деталей, які вона може доставляти;

¨ видалення. Якщо Компанія 6 (“Білайт”) припинила постачання запчастини 1, то ми зобо­в’язані вилучити всі записи, які стосуються цієї компанії і мають в полі Запчастина код 1;

¨ модифікація. Якщо код продавця для Києва змінився, наприклад, через транс­порт, то відповідне поле повинно бути змінене у кожному записі, де є код Київ в полі Місцезнаходження.

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

2. Нормалізація відношень. З практичної точки зору ми повинні розділити інфор­ма­цію в SUP2 так, щоб по можливості уникнути повторів. Таким чином, ми отримаємо мож­ли­вість вставки/вилучення частини запису в SUP2. Можливе і розумне розділення наво­диться в SUP3 (табл.4). Тоді залишок інформації в SUP2 може міститись в відношенні Запчастина(табл.5).

Таблиця 4

Компанія	Місцезнаходження	Продавець
		Київ Київ Львів Львів Київ

Запчастина Таблиця 5

Компанія	Запчастина	Кількість

Використовуючи цю кофігурацію, можна, наприклад:

а) включити в SUP3 запис, що компанія 4 знаходиться в Харкові (код продавця 3);

б) вилучити посилання на компанію 6 як на продавця запчасти 1, але залишити відповідний запис в SUP3;

в) змінити код продавця для Києва на 7 шляхом заміни лише трьох рядків відпо­відним компаніям з кодом 1, а не всіх шести.

Результати цих змін наведені в табл. 6 і табл. 7.

Таблиця 6

Компанія	Місцезнаходження	Продавець
	Київ Київ Львів Харків Львів Київ

Запчастина Таблиця 7

Компанія	Запчастина	Кількість

 

Це вже значно краще. Щоб побачити, в якому напрямку продовжувати дослідження, відокремимо ключі і залежні частини (рис.15). Відзначимо, що відношення Запчастина потребує об’єд­наного ключа.

	Місцезнаходження

Компанія

кккваыва

 

 

Продавець

SUP3

 

 

Рис. 15

 

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

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

Приклад 3 (продовження). Файл SUP3 все ще є достатньо незручним в тому розу­мін­ні, що для даного запису продавець може бути встановлений за допомогою встановлення запису з відомим значенням ключового поля Компанія чи ж поля Місцезнаходження. Це є причиною того, що в вимозі включити в SUP3 запис, що компанія 4 знаходиться в Харкові (код продавця 3) код продавця для Харкова повинен бути вставлений перед записом кода компанії, а вимога вилучити посилання на компанію 6 як на продавця запчасти 1, але залишити відповідний запис в SUP3, можливо, потребує змінити більше одного запису для модифікації єдиного поля даних, що відноситься до коду продавця. На практиці ми можемо позбавитися цієї проблеми, перебудувавши відношення SUP3 в SUP4 і DEL (табл.8,9).

Відзначимо, що коди продавця, що змінюються таким чином, виключають мож­ливість того, що будь-які інші записи в файлі містять суперечливу інформацію. В відношенні SUP3, наприклад на деякому етапі модифікації SUP2 можна отримати записи вигляду “Продавець компанії 6 - 2” і “Продавець компанії 1 - 7”, незважаючи на той факт, що обидві компанії знаходяться у Києві.

Залежність полів відношень SUP4 і DEL зображена на рис.16.

Таблиця 8

Компанія	Місцезнаходження
	Київ Київ Львів Харків Львів Київ

Таблиця 9

Місцезнаходження	Продавець
Київ
Львів
Харків

 

Всі не-ключі безпосередньо (будемо говорити нетранзитивно) і повністю залежать від ключів. Саме ця обставина пояснює переваги такого рішення перед попереднім. Таким чи­ном, ми виділили властивість нормальної форми, яка виводить нас за рамки 2NF, і обумов­лює її подальшу нормалізацію. Варто зазначити, що нетранзитивність відношення залежності є внутрішньою властивістю, з якої і виникає поняття третьої нормальної форми.

Визначення. Файл знаходиться в третій нормальній формі (3NF), якщо він є файлом 2NF, і кожен атрибут, що не є ключем, нетранзитивним чином залежить від ключа.

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

 

 

SUP4

 

DEL

Рис. 16

 

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

Практичне використання відношень SUP4 і DEL потребує явного зв’язку атрибуту Місцезнаходження файлу SUP4 з атрибутом Місцезнаходження файлу DEL. Це – відношення екві­валентності (між ком­по­нентами різних файлів, що мають одне і те ж ім’я). Подібні відно­шен­ня еквівалентності можуть бути використані для визначення внутрішніх зв’язків і інших структурних даних. В якості ілюстрації розглянемо рис.17. Діаграма на рис. 17a зображає де­рево, діаграма на рис. 17b подібна діаграмі структурних даних, а діаграми на рис.17 c і d описують їх можливі застосування.

 

a a

Ф

x p

b c

b

c

y z u v

d e

d

e

 

q r s t

a b

a

c

 

b

b

 

c

e

 

d

a

 

e

d

c d

Рис. 17

 

Відзначимо, що відношення еквівалентності різні, але структурні зв’язки, які є результатом, зберігаються. З математичної точки зору це є розбиттям на класи еквівалентності. Отже, ми можемо визначити випадкове представлення цього дерева як елемент множини T = D/E, де

D = {a = (x, a, p), b = (y, b, z), c = (u, c, v), d = (q, d, r), e = (s, e, t)},

E = {(x, b), (y, d), (p, c), (z, e)}.