Ієрархічна модель даних
Ієрархічна модель даних — це модель даних, де використовується представлення бази даних у вигляді деревовидної (ієрархічної) структури, що складається з об'єктів (даних) різних рівнів.
Між об'єктами існують зв'язки, кожен об'єкт може включати в себе кілька об'єктів більш низького рівня. Такі об'єкти перебувають у відношенні предка (об'єкт більш близький до кореня) до нащадку (об'єкт більш низького рівня), при цьому можлива ситуація, коли об'єкт-предок не має нащадків або має їх декілька, тоді як в об'єкта-нащадка обов'язково тільки один предок. Об'єкти, що мають спільного предка, називаються близнюками (в програмуванні стосовно до структури даних дерево усталена назва брати).
До основних понять ієрархічної структури відносяться: рівень, елемент (вузол), зв'язок. Вузол — це сукупність атрибутів даних, що описують деякий об'єкт. На схемі ієрархічного дерева вузли представляються вершинами графа. Кожен вузол на більш низькому рівні пов'язаний лише з одним вузлом, що знаходиться на більш високому рівні.
Ієрархічне дерево має тільки одну вершину, не підпорядковану ніякий інший вершині і знаходиться на найвищому (першому) рівні. Залежні вузли знаходяться на другому, третьому і т. д. рівнях. Кількість дерев у базі даних визначається числом кореневих записів. До кожного запису бази даних існує тільки один (ієрархічний) шлях від кореневого запису.
Бази даних з ієрархічною моделлю одні з найстаріших і стали першими системами управління базами даних для мейнфреймів. Розроблялися в 1950-х і 1960-х, наприклад, Information Management System (IMS)[1] фірми IBM.
Приклади
Наприклад, якщо ієрархічна база даних містила інформацію про клієнтів та їх замовленнях, то буде існувати об'єкт «покупець» (батько) і об'єкт «замовлення» (дочірній). Об'єкт «покупець» буде мати вказівники від кожного замовника до фізичного розташування замовлень покупця в об'єкт «замовлення».
Так, наприклад, якщо виникне необхідність вказівки варіанта, коли договір складають кілька виконавців і один виконавець формує кілька договорів, тобто між договором і виконавцем використовується зв'язок N: M (багато — до — багатьох), то в ієрархічній моделі необхідно буде повторювати відомості про договори в якості дочірнього елемента до виконавця, що істотно ускладнює саму модель і не дає можливості коректно обробляти подану інформацію.
У цій моделі запит, направлений вниз по ієрархії, простий (наприклад, замовлення, які належать цьому покупцю); проте запит, спрямований вгору по ієрархії, більш складний (наприклад, який покупець розмістив замовлення). Також, важко уявити не-ієрархічні дані при використанні цієї моделі.
Ієрархічною базою даних є файлова система, що складається з кореневого каталогу, в якому є ієрархія підкаталогів і файлів.
Структурна частина ієрархічної моделі
Основними інформаційними одиницями в ієрархічній моделі даних є сегмент і поле. Поле даних визначається як найменша неподільна одиниця даних, доступна користувачеві. Для сегмента визначаються тип сегмента і екземпляр сегмента. Екземпляр сегмента утворюється з конкретних значень полів даних. Тип сегмента — це пойменована сукупність вхідних у нього типів полів даних.
Організація даних в ієрархічної моделі передбачає обов'язкове поєднання батьківського і дочірнього об'єктів даних. Ці об'єкти даних характеризуються такими структурними елементами:
- атрибут — подається найменшою одиницею елемента даних, що позначає функціональну сутність описуваного властивості об'єкта;
- запис — подається групою атрибутів, що позначає конкретний екземпляр описуваного об'єкта;
- групове відношення — подається зв'язком між записами різних типів, яка відображає взаємодію батьківської і дочірньої записів;
- ключовий елемент — подається атрибутом, який може містити тільки унікальні значення для кожного запису.
Як і мережева, ієрархічна модель даних базується на графовій формі побудови даних, і на концептуальному рівні вона є просто частковим випадком мережевої моделі даних. В ієрархічній моделі даних вершині графу відповідає тип сегмента або просто сегмент, а дугам — типи зв'язків предок — нащадок. В ієрархічних структурах сегмент — нащадок повинен мати в точності одного предка.
Ієрархічна модель — це зв'язний неорієнтований граф деревоподібної структури, що об'єднує сегменти. Ієрархічна БД складається з упорядкованого набору дерев.
Приклади типових операторів пошуку даних
- знайти вказане дерево БД;
- перейти від одного дерева до іншого;
- знайти екземпляр сегмента, що задовольняє умовам пошуку;
- перейти від одного сегмента до іншого всередині дерева;
- перейти від одного сегмента до іншого в порядку обходу ієрархії.
Приклади типових операторів пошуку даних з можливістю модифікації:
- знайти і утримати для подальшої модифікації єдиний екземпляр сегмента, що задовольняє умовам пошуку;
- знайти і утримати для подальшої модифікації наступний екземпляр сегмента з тими ж умовами пошуку;
- знайти і утримати для подальшої модифікації наступний екземпляр для того ж батька.
Приклади типових операторів модифікації ієрархічно організованих даних, які виконуються після виконання одного з операторів другої групи (пошуку даних з можливістю модифікації):
- вставити новий екземпляр сегмента у вказану позицію;
- оновити поточний екземпляр сегмента;
- видалити поточний екземпляр сегмента.
В ієрархічній моделі автоматично підтримується цілісність посилань між предками і нащадками. Основне правило: ніякий нащадок не може існувати без свого батька.
Недоліки
До основних недоліків ієрархічних моделей слід віднести:
- неефективність реалізації відносин типу N: N
- повільний доступ до сегментів даних нижніх рівнів ієрархії
- чітка орієнтація на певні типи запитів
У зв'язку з цими недоліками раніше створені ієрархічні СКБД піддаються істотним модифікаціям, що дозволяє підтримувати більш складні типи структур і, в першу чергу, мережеві та їх модифікації.
Керувальна частина ієрархічної моделі
В рамках ієрархічної моделі виділяють мовні засоби опису даних (МЗОД) та засоби маніпулювання даними (ЗМД). Кожна фізична база описується набором операторів, що обумовлюють як її логічну структуру, так і структуру зберігання БД. При цьому спосіб доступу встановлює спосіб організації взаємозв'язку фізичних записів.
Визначено такі способи доступу:
- ієрархічно послідовний;
- ієрархічно індексно-послідовний;
- ієрархічно прямий;
- ієрархічно індексно-прямий;
- індексний.
Крім завдання імені БД та способу доступу описи повинні містити визначення типів сегментів, що складають БД, у відповідності з ієрархією, починаючи з кореневого сегмента. Кожна фізична БД містить тільки один кореневий сегмент, але в системі може бути кілька фізичних БД.
Серед операторів маніпулювання даними можна виділити оператори пошуку даних, оператори пошуку даних з можливістю модифікації, оператори модифікації даних. Набір операцій маніпулювання даними в ієрархічній БД невеликий, але цілком достатній.
Відомі ієрархічні СКБД
Прикладами баз даних з ієрархічною моделлю є[2]:
- Типовим представником (найбільш відомим і поширеним) є Information Management System (IMS) фірми IBM (1966—1968 р.);
- Time-Shared Data Management System (TDMS)[3] компанії System Development Corporation;
- Mark IV MultiAccess Retrieval System компанії Control Data Corporation;
- System 2000 розробки SAS Institute;
- InterSystems Caché[4].
Перетворення концептуальної моделі в ієрархічну модель даних
Перетворення концептуальної моделі в ієрархічну структуру даних багато в чому схоже з перетворенням її в мережеву модель, але й має деякі відмінності у зв'язку з тим, що ієрархічна модель вимагає організації всіх даних у вигляді дерева.
Перетворення зв'язку типу «один до багатьох» між предком і нащадком здійснюється практично автоматично в тому випадку, якщо нащадок має одного предка, і відбувається це наступним чином. Кожен об'єкт з його атрибутами, що бере участь в такому зв'язку, стає логічним сегментом. Між двома логічними сегментами встановлюється зв'язок типу «один до багатьох». Сегмент з боку «багато» стає нащадком, а сегмент з боку «один» стає предком.
Ситуація значно ускладнюється, якщо нащадок в зв'язку має не одного, а двох і більше предків. Так як подібне положення є неможливим для ієрархічної моделі, то відображена структура даних потребує перетворення, які зводяться до заміни одного дерева, наприклад, двома (якщо є два предка). В результаті такого перетворення в базі даних з'являється надмірність, так як єдино можливий вихід з цієї ситуації — дублювання даних.
Примітки
- Database Management System Concepts. FK Publications. с. 32–. ISBN 978-93-80006-33-8.
- Introduction to Database Management System. Laxmi Publications. с. 77–. ISBN 978-93-81159-31-6.
- Setrag Khoshafian (1993). Object-oriented databases. John Wiley. ISBN 978-0-471-57058-5.
- Prakash M. Nadkarni (27 травня 2011). Metadata-driven Software Systems in Biomedicine: Designing Systems that can adapt to Changing Knowledge. Springer Science & Business Media. с. 72–. ISBN 978-0-85729-510-1.