30.Ієрархічна модель даних.

Ієрархічна модель даних

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

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

Орієнтація на кореневому дереві визначається або від коріння, або до коріння.

Кореневе дерево можна визначити наступним чином:

1) є єдиний особливий вузол , який називається корінням, в який не заходить жодне ребро;

2) в всі інші вузли заходить тільки одне ребро, а виходить довільна (0, 1,

2,..., п) кількість ребер;

3) не існує циклів.

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

Рекурсивне дерево визначається як кінцева множина Т, яка складається з одного або більш вузлів, таких, що: 1) існує один спеціально виділений вузол, який називається корінням дерева;

2) інші вузли розбиті на m>0 неперетинаючихся підмножини T1,T2, …, Tm, кожна з яких в свою чергу є деревом. T1,T2, …, Tm, називаються піддеревами.

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

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

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

.

Прикладом простого ієрархічного представлення може служити адміністративна структура вищого учбового закладу: університет - відділення - факультет - група (студентська).

Пошук даних у ієрархічній структурі виконується завжди по одній із гілок, починаючи з кореневого елемента, тобто повинний бути зазначений повний шлях руху по гілкам. Так, для пошуку і вибірки одного або декількох екземплярів запису типу СТУДЕНТ необхідно вказати кореневий елемент ФАКУЛЬТЕТ і елементи КУРС, ГРУПА. У операційній системі для пошуку файла використовується такий же принцип - вказуються послідовно ім'я диска, ім'я каталогу, ім'я підкаталогів, ім'я файла.

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

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

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

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

Ієрархічна деревоподібна структура, що орієнтована від коріння, задовольняє наступним умовам:

1) ієрархія завжди починається з кореневого вузла;

2) на першому рівні може знаходитися тільки один вузол- кореневий;

3) на нижніх рівнях знаходяться породжені (залежні) вузли;

4) кожний породжений вузол, який знаходиться на рівні і , зв'язаний тільки

з одним вхідним вузлом , який знаходиться на рівні (і-1) ієрархії дерева;

5) кожний вхідний вузол може мати один або декілька породжених вузлів,

які називаються подібними;

6) доступ до кожного породженого вузла виконується через йому

відповідний вхідний вузол;

7) існує єдиний ієрархічний шлях доступу до будь-якого вузла, починаючи

від кореневого вузла дерева.

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

· Знайти задане дерево БД ; · Перейти від одного дерева до іншого;

· Перейти від одного запису до іншого в середині дерева ;

· Перейти від одного запису до іншого в порядку обходу ієрархії;

· Уставити новий запис у зазначену позицію;

· Видалити поточний запис.

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

До недоліків ієрархічних структур відносять :

- надлишковість зберігання інформації, так як ієрархічні структури не підтримують взаємозв'язки Б:Б;

- строгу ієрархічну впорядоченість , яка ускладнює процедури включення

та вилучення записів; - вилучення вихідних вузлів призводить до вилучення відповідних їм породжених , що вимагає особливої обережності;

- ускладнюється доступ до даних , які лежать на більш низьких рівнях ієрархії, так як кореневий вузол завжди є головним, а доступ до любого породженого вузла може здійснюватись через вихідний. В ієрархічні базі даних проблеми, пов'язані з операціями включення нових записів і вилучення старих, а також проблеми часткового дублювання інформації виникають в результаті того, що відношення БАГАТО-ДО-БАГАТЬОХ безпосередньо не підтримується, що і є основним недоліком ієрархічних моделей.