Структури даних.

Структури даних.

Структури файлової моделі даних. Ці структури даних є базовими для файлової моделі даних, але використовуються і в ряді СУБД, що робить ці поняття універсальними. Основні первинні типи структур даних - поле, запис, файл.

Розглянемо ці структури даних на прикладі опису об’єкту «УГОДА»:

Рис. 1.6.а

Деталізуємо і уточнюємо концептуальну модель:

Рис.1.6.б

Рис. 1.6.в

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

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

Модель даних може включати кілька типів записів (об'єктів). Між об'єктами моделі даних встановлюються зв'язки. Зв'язки між двома типами записів (об'єктами моделі) визначаються груповими відношеннями між їх примірниками. Групове відношення (набір) - це строго ієрархічне відношення між записами двох типів: головним записом набору і підпорядкованими записами набору.

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

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

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

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

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

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

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

1, 2,..., n) кількість ребер;
3) не існує циклів.

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

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

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

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

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

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

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

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

Нижче приведений приклад графічного представлення ІМ тематичних збірників видавництв, вид деякої конкретної бази даних і опис схеми ІМ у системі ІMS фірми ІBM.

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

Рисунок 3.5 - Приклад типу набору у виді діаграми Бахмана

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

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

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

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

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

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

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

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

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

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

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

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

Þ Пошук заданого дерево БД;

Þ Перехід від одного дерева до іншого;

Þ Перехід від одного запису до іншого в середині дерева;

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

Þ Установлення нового запис у зазначену позицію;

Þ Видалення поточного запис.

Перевагами деревовидної моделі є:

1) наявність функціональних систем керування базами даних, які підтримують дану модель,

2) простота сприйняття користувачами принципу ієрархії;

3) забезпечення деякого рівня незалежності даних;

4) простота оцінки операційних характеристик системи завдяки апріорно заданим взаємозв'язкам.

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

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

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

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

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

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

О: Б

ВИКЛАДАЧ ДИСЦИПЛІНА

О: Б

СТУДЕНТ ДИСЦИПЛІНА,

де - відношення ОДИН - ДО -БАГАТЬОХ.

Ця інформація в ієрархічній моделі може бути представлена різними способами. Один з варіантів показаний на рис.3.6.

Кореневим вузлом є об'єкт СТУДЕНТ. Для кожного студента при даному представленні є екземпляр кореневого вузла.

Об'єкти ВИКЛАДАЧ, ДИСЦИПЛІНА об'єднані в породжуваний вузол ДИСЦИПЛІНА + ВИКЛАДАЧ. В кожний момент часу база даних, що задана моделлю рис.3.6, може мати записи для N студентів. На рис.3.7 показаний екземпляр запису бази даних для студента Собка Н.Ю.

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

В той же час, якщо необхідно отримати інформацію про те, які викладачі по дисципліні " Схемотехніка" приймають іспити, то прийдеться переглянути всі записи породжуваних вузлів всіх екземплярів кореневого вузла. При такій постановці задачі більше підходить модель, яка представлена на рис.3.8, де кореневим вузлом є об'єкт ВИКЛАДАЧ, а об'єкти СТУДЕНТ та ДИСЦИПЛІНА об'єднані в породжуваний вузол СТУДЕНТ + ДИСЦИПЛІНА.

В моделі на рис.3.8 даними, що дублюються, є відомості про студентів.

Рисунок 3.8 - Альтернативне представлення бази даних СТУДЕНТ- ДИСЦИПЛІНА

На прикладах (див. рис.3.6 та рис.3.8) проілюструємо проблеми, які пов'язані з операціями включення та влучення даних.

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

При вилученні екземплярів вихідного вузла автоматично вилучаються всі екземпляри породжені вузлом. Наприклад, в базі даних, модель якої приведена на рис.3.8, вилучення екземпляра ВИКЛАДАЧ потягне за собою і вилучення всіх екземплярів про студентів, які навчаються в даного викладача. Вказане повністю неприпустиме при розв'язку, наприклад, задачі оцінки якості навчання студентів.

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

Контрольні запитання.

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

2. Чим обумовлено широке використання збалансованих дерев?

3. Перерахуйте типові оператори маніпулювання ієрархічними даними.

4. Перерахуйте основні переваги та недоліки ієрархічних моделей даних.