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

Ієрархічна модель даних уперше була задіяна в системі IMS (Information Manage­ment System - інформаційна керуюча система) у межах проекту висадки на Мі­сяць. У першій ієрархічній системі були повністю реалізовані функції СКБД, а саме: мови визначення та маніпулювання даними, опис і підтримка обмежень цілісності, паралелізм, відновлення, а також механізми ефективної обробки запи­тів. Варто сказати, що IMS і досі використовується на мейнфреймах.

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

Ієрархічна структура даних

Ієрархічна структура даних визначається ієрархічною впорядкованістю своїх ком­понентів (або вузлів), тобто кожен вузол має не більше одного «батька» — стар­шого за ієрархією вузла.

Структура складається зі схем елементів даних (описова інформація) та їхніх екземплярів. Інакше кажучи, схема задає логічну структуру (або тип) елементу да­них, а екземпляр — його значення.

Елементарним значенням структури є пойменоване поле даних, а його екземп­ляр — це елементарне значення.

Схема сегмента (яку називатимемо також просто сегментом) — це пойменова­на впорядкована сукупність імен полів. Сегмент є одиницею доступу до даних ієрархічної структури під час взаємодії зовнішньої та оперативної пам'яті.

Екзем­пляр сегмента — впорядкована сукупність значень полів.

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

• на найвищому рівні ієрархії розташований єдиний сегмент, що називається кореневим)

• кожен інший сегмент, окрім кореневого, зв'язаний з одним і тільки одним сег­ментом вищого рівня, який є для цього сегмента батьківським (початковим);

• сегмент може бути зв'язаний з одним або кількома сегментами нижчого рівня, які називаються дочірніми (породженими);

• сегменти, що підпорядковані одному батьківському сегменту, називаються близнюками;

• сегменти, що не мають дочірніх, вважаються листковими, або їх ще називають листками.

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

Для ієрархічної схеми використовується така графічна нотація.

• Кожний сегмент зображується у вигляді пойменованого прямокутника. Усе­редині прямокутника записуються імена полів.

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

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

Рис 2. Графічне зображення схеми ієрархічної структури даних:

з уточненням (а); без уточнень (б)

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

• кожний екземпляр будь-якого сегмента підпорядкований одному екземпляру батьківського сегмента;

• е кземпляр будь-якого сегмента (окрім кореневого) не може існувати без від­повідного екземпляра батьківського сегмента;

• кожний екземпляр сегмента зв'язаний (підпорядковує собі) з усіма екземпля­рами дочірніх сегментів;

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

У такий спосіб ієрархічна впорядкованість сегментів створює зв'язок «один-до-багатьох» між екземплярами батьківського і дочірнього сегментів. Приклад екземплярів ієрархічної схеми наведений на рис. 2.2.

Ієрархічна схема інколи має розгалуження, як це показано на рис. 2.3. У по­дібному випадку на рівні схеми батьківський сегмент може зв'язуватися з кілько­ма дочірніми сегментами.

Ієрархічна структура даних — це сукупність ієрархічної схеми даних та всіх можливих екземплярів цієї схеми. Сукупність ієрархічних структур даних нази­вається ієрархічною базою даних.

Операції над ієрархічною структурою

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

Зазначимо кілька базових принципів, характерних для мов маніпулювання дани­ми ієрархічних систем.

• Об'єктом маніпулювання є екземпляр сегмента.

• У результаті успішного виконання пошукових операцій визначається поточний екземпляр сегмента, який може відігравати роль стартової позиції для опе­рацій маніпулювання; спочатку поточним є кореневий екземпляр сегмента.

• Пошук необхідного сегмента відбувається за «навігаційним» принципом: не­обхідно прокласти шлях від кореневого екземпляра сегмента (або ж поточно­го) до шуканого, перевіряючи умови, накладені на значення полів сегментів, які розташовані на шляху, що будується. Операція в ієрархічній моделі ви­значається шляхом програмування «навігації» структурою даних.

Вибирання даних

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

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

Переваги та недоліки ієрархічної моделі

До переваг ієрархічної моделі належать:

• розвинені низькорівневі засоби керування даними в зовнішній пам'яті;

• можливість побудови ефективних прикладних систем;

• економне використання пам'яті.

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

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

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

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

• Аномалії додавання, видалення та оновлення даних. Не можна здійснити операцію додавання сегмента ВИКЛАДАЧ без зазначення сегмента КАФЕДРА; не мож­на видалити сегмент КАФЕДРА, на видаляючи сегментів ВИКЛАДАЧ; після оновлен­ня даних один і той самий екземпляр сутності зображується у вигляді багатьох екземплярів об'єктів бази даних.

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

Основні недоліки ієрархічної моделі пов'язані з тим, що не всі предметні об­ласті мають чітко виражену ієрархічну структуру. Наведений на рис. 2.2 приклад добре узгоджується з ієрархічною структурою. Проте, якщо ми розглянемо пред­метну область із сутностями «викладач», «дисципліна», «лекція» в ситуації, коли один викладач читає лекції з багатьох дисциплін і одна й та сама дисципліна чи­тається багатьма викладачами, то вона «погано» піддається ієрархічній структуризації. Справа в тому, що між викладачами і дисциплінами існує зв'язок типу «багато-до-багатьох», який не є адекватним ієрархічній структурі даних (доклад­ніше про це мова йтиме в розділах, присвячених логічному проектуванню).

Для відображення зв'язків цього типу була запропонована мережна модель даних.