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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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