Мережева модель даних

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

Наприклад:

Структура моделі має вершини, зв’язані між собою дугами.

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

Кожний викладач навчає більш ніж одного студента.

Кожний студент навчається більш ніж в одного викладача.

Вершини: V₁ V₂ V₃ … V_n

Дуги: e₁ e₂ e₃ … e_m

Основними поняттями моделі є об'єкти, які поділені на групи, та зв'язки між об’єктами, що належать до різних груп.

Основним недоліком моделі є неможливість відображати зв’язки між об’єктами, які належать до однієї групи (штрихова лінія).

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

2.3. Реляційна модель даних

Реляційна модель – це найбільш поширена модель даних, в якої дані і зв’язки між ними організовані у вигляді таблиць. В її основі лежить математичне поняття «відношення» (relationship).

Відношення являє собою підмножину декартового добутку доменів.

Домен (domain) означає множину всіх значень деякого елемента даних про об’єкт (чи деякого атрибута сутності).

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

Доменом інвентарного № вагона є множина значень – {10000000 – 99999999}.

Для відмітки про ролики доменом є множина – {0, 1}.

Доменом назви залізниці України є множина значень – {Донецька, Львівська, Одеська, Південна, Південно-західна, Придніпровська}.

Декартовим добутком k доменів (D₁,D₂,..,D_k) є множина всіх кортежів виду (V₁,V₂,..,V_k) довжиною k, таких що V₁ÎD₁, V₂ÎD₂,…,V_kÎD_k.

Наприклад: D₁*D₂*D₃ – декартовий добуток доменів D₁, D₂ і D₃.

де D₁={0, 1}, D₂={a, b, c}, D₃={x, z}, тобто це є множина всіх кортежів, що складені з 3-х елементів по 1-му з кожного домену.

Відношення R на множинах D₁,D₂,…,D_k являє собою підмножину в декартовому добутку доменів D₁*D₂*…*D_k. Елементами відношення є кортежі довжиною k.

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

Наприклад: візьмемо рядки 2, 5, 11: - Відношення А на множинах D₁,D₂,…,D_k.

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

В роботі із базами даних використовують паралельно наступні поняття:

Таблиця 1

Проектування БД	Застосування БД	Програмування
відношення	таблиця	файл
кортеж	рядок	запис
атрибут	стовпчик	поле запису

При опрацюванні даних на ЕОМ переважно використовуються поняття: файл, запис, поле.

Приклад: побудуємо відношення (таблицю даних) НАВАНТАЖЕННЯ, де

об'єкт: навантажений вагон;

атрибути: № вагона (множина 8-розрядних цілих чисел з домену D₁);

рід вагона{пв, кр, пл, цс, пр}(множина двосимвольних слів з домену D₂);

найменування вантажу (множина найменувань вантажу з домену D₃);

маса (множина 3-розрядних цілих чисел з домену D₄).

Тобто тут атрибути приймають значення з 4-х доменів.

Таблиця 2

Відношення НАВАНТАЖЕННЯ:

Назва атрибута	®	Інвентарний № вагона	Рід вагона	Найменування вантажу	Маса вантажу
	пв	вугілля
	кр	цукор
	пл	рейки		кардинальність відношення
	цс	бензин
	цс	бензин

ступінь відношення

<Маса_вантажу> – це назва атрибуту, 45,52,46 – це значення атрибута <Маса_вантажу>.

Кожний кортеж відношення НАВАНТАЖЕННЯ складається з чотирьох елементів (компонентів). Кожний елемент кортежу вибирається зі свого домену (1-ий з D₁, 2-ий з D₂,…).

Порядок елементів у кортежі фіксований. Міняти місцями елементи в кортежі заборонено. Тоді як самі кортежі можна міняти місцями довільно. У відношенні всього п’ять кортежів.

Кількість атрибутів у відношенні називається ступенем відношення. Отже маємо четверту ступінь відношення НАВАНТАЖЕННЯ.

Кількість кортежів у відношенні називається кардинальністю відношення. Отже кардинальність відношення НАВАНТАЖЕННЯ дорівнює п’яти.

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

Лекція 4

3. РЕЛЯЦІЙНІ БАЗИ ДАНИХ

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

Приклад:

РБД металургійного заводу містить три типи даних:

1. Інформація про одержувачів вантажу – унікальний код одержувача, назва одержувача, залізнична станція призначення, тарифна відстань до станції – міститься у відношенні ОДЕРЖУВАЧ).

2. Інформація про вантажі, що відправляються – унікальний код вантажу, найменування, необхідний рухомий склад, ціна одиниці цього вантажу – міститься у відношенні ВАНТАЖ).

3. Інформація про постачання вантажу – код одержувача, код вантажу, маса відправки – міститься у відношенні ПОСТАЧАННЯ).

Таблиця 3

Відношення ОДЕРЖУВАЧ:

Код одержувача	Назва	Станція	Відстань
	Мех. з-д	Н.Д. Вузол
	Фабрика	Запоріжжя 1
	Мех. з-д	Кр. Ріг-Голов.
	ЗБК	Запоріжжя 1
	Будтрест	Донецьк

Таблиця 4

Відношення ВАНТАЖ:

Код вантажу	Найменування	Тип вагона	Ціна
	Метізи	кр
	Рейки	пл
	Дріт	пв
	Прокат	пл

Таблиця 5

Відношення ПОСТАЧАННЯ:

Код одержувача.	Код вантажу	Маса

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

Вміст (листінг) відношення РБД у поточний момент називається фотографією відношення. В будь який момент часу користувач РБД має справу з фотографієювідношення, тобто з даними, яки містяться у відношенні в певний момент часу.

РБД може бути складеною з одного, двох, чи кількох відношень. Якщо в РБД кілька відношень, то вони обов’язково повинні бути зв’язані між собою. Кількість відношень у РБД (тут – 3) і перелік атрибутів, що залучаються в кожне з них, визначається в процесі проектування бази даних.

Для пошуку даних в РБД використовують ключі відношень. У зв'язку з цим потрібно розрізняти поняття:

- первинний ключ (суперключ) відношення;

- можливий (потенційний) ключ відношення;

- чужий(зовнішній) ключ відношення.

3.1. Первинний ключ (суперключ) відношення

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

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

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

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

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

У даному прикладі первинними ключами є <Код_вантажу> у відношенні ВАНТАЖ, <Код_одержувача> у відношенні ОДЕРЖУВАЧ і пара атрибутів <Код_вантажу, Код_одержувача> у відношенні ПОСТАЧАННЯ.

Як бачимо, у деяких випадках в якості первинного ключа може використовуватися група атрибутів, однак, якщо ми візьмемо як первинний ключ у відношенні ОДЕРЖУВАЧ наприклад пару атрибутів <Код_одержувача, Станція> , то ця пара атрибутів теж однозначно ідентифікує кортеж у відношенні ОДЕРЖУВАЧ. Але таке рішення буде неправильним, тому що первинний ключ в своєму складі не повинен мати додаткових атрибутів. Атрибут <Станція> буде зайвим, адже і без нього можна визначити значення інших атрибутів будь-якого кортежу відношення ОДЕРЖУВАЧ, знаючи тільки <Код_одержувача>.

Якщо виключити з первинного ключа відношення ПОСТАЧАННЯ який-небудь атрибут, то атрибут, що залишиться, не дасть змоги однозначно ідентифікувати кортеж.

3.2. Можливий (потенційний) ключ відношення

Якщо повернутися до попереднього прикладу, то у відношенні ВАНТАЖ як первинний ключ можна було б застосувати атрибут <Найменування_вантажу>.

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

Первинний ключ відношення завжди є можливим ключем цього ж відношення.

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

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

Наприклад, у відношенні ВАНТАЖ є два можливих ключа: <Код_вантажу> і <Найменування_вантажу>. Проектувальник бази даних за своїм розсудом може призначити первинним ключем будь-який з вище названих атрибутів.

3.3. Чужий (зовнішній) ключ відношення

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

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

Відношення ВАНТАЖ і ПОСТАЧАННЯ зв'язані між собою за допомогою атрибута <Код_вантажу>. Тільки у відношенні ВАНТАЖ атрибут <Код_вантажу> є можливим ключем, а у відношенні ПОСТАЧАННЯ атрибут <Код_вантажу> не є можливим ключем, отже він є чужим ключем відношення ПОСТАЧАННЯ.

Аналогічно відношення ОДЕРЖУВАЧ і ПОСТАЧАННЯ зв'язані за допомогою атрибута <Код_одержувача>. У відношенні ОДЕРЖУВАЧ атрибут <Код_одержувача> є можливим ключем, а у відношенні ПОСТАЧАННЯ атрибут <Код_одержувача> не є можливим ключем, отже він є чужим ключем відношення ПОСТАЧАННЯ.

Відношення ОДЕРЖУВАЧ і ВАНТАЖ безпосередньо між собою не зв'язані, вони зв'язані через відношення ПОСТАЧАННЯ.

Лекція 5

4. ПРОЕКТУВАННЯ РЕЛЯЦІЙНОЇ БАЗИ ДАНИХ

4.1. Цілі проектування РБД

Ціль 1. Забезпечити можливість збереження всіх необхідних даних у РБД. Необхідно визначити всі атрибути, що потрібно помістити в РБД. За умови, що всього таких атрибутів нараховується не більше 20, на початку проектування РБД всі вони залучаються до одного відношення.

Ціль 2. Вилучити явної надлишковості даних. Для того щоб позбавитись явної надлишковості даних потрібно розрізняти поняття дублювання та надлишкового дублювання даних (чи, інакше кажучи, неявної та явної надлишковості даних). Розглянемо 2 відношення

Таблиця 6

Відношення ОДЕРЖУВАЧ 1:

Код_одержувача	Станція
	Запоріжжя 1
	НДВузол
	Запоріжжя 1

Дані про станцію Запоріжжя 1 дублюються (Запоріжжя 1 – 2 рази). Але втрата одного значення станції (де знаходиться одержувач 1423) призведе до того, що ми не зможемо дізнатися станцію примикання для нього. Тут дублювання даних про станцію не є надлишковим. Це приклад неявної надлишковості даних.

Таблиця 7

Відношення ОДЕРЖУВАЧ 2:

Код_одержувача	Станція	Код ЄСР
	Запоріжжя 1
	НДВузол
	Запоріжжя 1

Тут є надлишкове дублювання даних: втрачений код ЄСР станції примикання одержувача 1423 можна дізнатися по назві станції примикання іншого одержувача 1537. Це приклад явної надлишковості даних.

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

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

Ціль 4. Звести до мінімуму кількість відношень, що зберігатимуться у РБД. Прагнути треба до мінімуму відношень. Розбивка одного відношення на декілька дозволяє уникнути ряду проблем (у тому числі і пов'язаних з надлишковим дублюванням даних), але це незручно для користувача, якому інколи важко визначити в якому саме відношенні знаходиться потрібна інформація.

В процесі проектування РБД необхідно розв'язати компроміс між 3-ю і 4-ю цілями.

4.2. Універсальне відношення

Відповідно до першої цілі процес проектування РБД розпочинається зі складання відношення, в яке залучаються всі потрібні для зберігання у РБД атрибути.

Якщо РБД складається всього з одного відношення, то це відношення називають універсальним.

Розглянемо етап складання універсального відношення на прикладі.

Допустимо, що потрібно створити РБД для підприємства, що відправляє вантажі клієнтам. По-перше виявимо, які атрибути потрібно залучити до РБД та встановимо для них обмеження і зв'язки між ними. Візьмемо такі атрибути:

1 Код_одержувача – ціле число, унікальне для кожного одержувача.

2 Назва_одержувача – символьний атрибут, кожний одержувач має 1 назву, але 1 назва може бути у декількох одержувачів (за кодом одержувача можна знайти його назву, зворотна операція неможлива).

3 Код ЄСР – ціле число, код ЄСР станції, на якій знаходиться одержувач, кожний одержувач пов'язаний з 1 станцією, на кожній станції може бути декілька одержувачів.

4 Код_вантажу – ціле число, кожний вантаж має унікальний код, кожний одержувач може одержувати декілька різних вантажів.

5 Найм_вантажу – символьний атрибут, кожний код вантажу має єдине відповідне найменування вантажу, кожному найменуванню відповідає єдиний код вантажу.

6 Маса_вантажу – ціле число, кожний одержувач одержує вантаж одного найменування і визначеної маси (значення маси можуть повторюватися).

Запишемо в таблицю зразок даних про навантаження за минулу добу:

Таблиця 8

Код_одержувача	Назва_одержувача	Код_ЄСР	Код_вантажу	Найм_вантажу	Маса_вантажу
	Мех. з-д			Метізи Рейки Дріт Прокат
	Ф-ка			Метізи Дріт Прокат
	Мех. з-д			Рейки Дріт Прокат
	ЗБК			Дріт
	Будтрест		-	-	-

4.2.1. Поняття форми відношення. Перша нормальна форма.

Не кожна таблиця даних є відношенням. Лише та таблиця, яка знаходиться в першій нормальній формі є відношенням. Тобто відношення обов’язково повинне знаходитися в першій нормальній формі (1НФ).

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

Ця таблиця не є відношенням. Значення перших 3-х атрибутів є атомарними, значення інших 3-х атрибутів є множинними, тобто не кожний рядок є кортежем. Наприклад, одержувачу 1010 відповідає по одному значенню атрибутів <Назва_одержувача> та <Код_ЄСР> і відразу по чотири значення атрибутів <Код_вантажу>, <Найм_вантажу> та <Маса_вантажу>. Тобто значення перших трьох атрибутів є атомарними, а решти – множинними.

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

Таблиця 9

Відношення: НАВАНТАЖЕННЯ:

Код_одержувача	Назва_одержувача	Код_ЄСР	Код_вантажу	Найм_вантажу	Маса_вантажу
	Мех. з-д			Метізи
1010	Мех. з-д	4500		Рейки
1010	Мех. з-д	4500		Дріт
1010	Мех. з-д	4500		Прокат
	Ф-ка			Метізи
1234	Ф-ка	4607		Дріт
1234	Ф-ка	4607		Прокат
	Мех. з-д			Рейки
1425	Мех. з-д	4671		Дріт
1425	Мех. з-д	4671		Прокат
	ЗБК			Дріт
	Будтрест		-	-	-

Перетворена таким чином таблиця є відношенням, що перебуває в 1НФ. Це відношення називається універсальним, тому що РБД складається всього з одного відношення і в ньому міститься вся потрібна інформація.

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

Таким чином перший етап проектування РБД полягає у складанні універсального відношення.

4.2.2. Проблеми, що можуть виникнути при роботі з РБД

Відомі 3 такі проблеми. Вони пов’язані головним чином з недостатньою кількістю відношень в РБД. Це проблемивставки, модифікаціїтавилученняданих. Розберемо їх на прикладах з універсального відношення:

1. Проблема вставки даних. Потрібно залучити до РБД нового одержувача 1572, котрому ще не відправляли в дану добу вантажі. Але порожні поля, як правило, не допускаються, тому що можуть виникнути проблема при складанні довідок на основі цих даних. (Наприклад, потрібна довідка про одержувачів, які отримають відправи масою до 100 тон. В довідку може бути залучений одержувач 1572, який такі вантажі не одержував).

2. Проблема вилучення даних. Якщо одержувач 1537 поданий одним кортежем зі всіма заповненими полями і дізналися, що вантаж ще не відправлений, то потрібно видалити цей рядок, і тоді зникнуть разом всі дані про одержувача 1537.

3. Проблема модифікації даних. Якщо одержувач (1010) повідомить, що змінюється код ЄСР станції примикання, на якій знаходяться декілька одержувачів (1010 та 1572), то її прийдеться змінювати не тільки у всіх рядках цього одержувача (1010), але й у інших одержувачів (1572) на цій станції, інакше виникне протиріччя: обидва одержувача як і раніше знаходяться на одній станції, а коди ЄСР в них різні. Така невідповідність неприпустима. Причиною протиріччя є явна надлишковість даних.

Лекція 6

4.3. Нормалізація відношення

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

Перед нормалізацією відношення повинно знаходитися в першій нормальній формі.