Навігація
Головна
 
Головна arrow Інформатика arrow Бази даних
< Попередня   ЗМІСТ   Наступна >

Логічна структура ієрархічної БД

Ієрархічна модель даних була історично першою структурою БД, мабуть, через те, що деревовидні ієрархічні структури широко використовуються в повсякденному людської діяльності. Це всілякі класифікатори, що прискорюють пошук необхідної інформації, ієрархічні функціональні структури управління. Найбільш відомою ієрархічної СУБД досі залишається IMS [1 - 11].

Елементами ієрархічної моделі є поле і сегмент. Структурні зв'язки визначаються підпорядкованістю, в силу чого сегмент більш низького рівня називають породженим, а більш високого рівня - вихідним. Сегмент самого верхнього рівня носить назву кореневої. Саме через нього здійснюється доступ до ієрархічної БД (точка входу). Примірник породженого сегмента не може існувати в відсутність примірника вихідного сегмента. У силу цього положення при видаленні примірника вихідного сегмента видаляються і всі екземпляри породжених сегментів.

Якщо структура запиту збігається зі структурою ієрархічної БД, то така модель даних володіє найвищим швидкодією і тому найчастіше застосовується в суперЕОМ. В іншому випадку швидкодія може різко знизитися або дані зовсім можуть бути не отримані. Щоб уникнути останнього неприємного випадку, в ієрархічній МД вводять ще один тип зв'язку - логічної, про яку поговоримо пізніше. Ієрархічні, як і мережеві, МД можуть бути представлені у вигляді графів: сегмент відбивається у вигляді вузла.

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

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

  • • всі типи зв'язків функціональні (1: 1, 1: Μ, М: 1);
  • • структура зв'язків деревоподібна.

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

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

  • 1) є єдина особлива вершина, звана коренем, в яку не входить жодне ребро;
  • 2) в усі інші вершини заходить тільки одне ребро, а виходить довільну кількість ребер;
  • 3) не є циклів.

У програмуванні використовується інше визначення дерева, що дозволяє при вирішенні завдань розглядати дерево як структуру, що складається з менших дерев (або піддерев), т. Е. Як рекурсивну структуру.

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

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

Дерева T t, Т 2, .... Т т називаються піддеревами кореня.

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

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

  • • вузол складається з одного або декількох атрибутів;
  • • ієрархія завжди починається з кореневого вузла;
  • • на верхньому рівні може перебувати тільки один вузол - кореневої;
  • • на нижніх рівнях знаходяться породжені (залежні) вузли: вони можуть додаватися у вертикальному та горизонтальному напрямках без обмеження;
  • • кожен породжений вузол, що знаходиться на рівні i, пов'язаний тільки з одним безпосередньо вихідним вузлом (безпосереднім батьківським вузлом), що знаходяться на більш високому рівні (/ -1) ієрархії дерева;
  • • кожен вихідний вузол може мати один або кілька безпосередньо породжених вузлів, які називаються подібними (зв'язку 1: М);
  • • доступ до кожного породженому вузлу виконується через його безпосередньо вихідний вузол;
  • • існує єдиний ієрархічний шлях доступу до будь-якого вузла, починаючи від кореня дерева (рис. 6.7), наприклад шлях ABEI.

Ієрархічний шлях доступу

Рис. 6.7. Ієрархічний шлях доступу

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

В ієрархічних моделях даних використовується орієнтація деревовидної структури від кореня, тобто. Е. Дуги, відповідні функціональним зв'язкам, спрямовані від кореня до листя дерева. Графічна діаграма схеми бази даних для ієрархічної бази даних називається деревом визначення.

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

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

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

Знову звернемося до рис. 3.4, в (див.). Тепер доведеться перемістити деякі поля в інші таблиці. На рис. 6.8 показана прямий зв'язок ряду таблиць.

Структура ієрархічної БД

Рис. 6.8. Структура ієрархічної БД

Програмна реалізація ієрархічної БД

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

DBD NAME = DB3, ACCESS = HISAM

DATASET D01 = DEPTD01, DEVICE = 3380, OWFLW = DEPTOVF

SEGM NAME = PART, BYTES-32

LCHILD NAME = (COMP ASSEMB, DB3), PAIR = ASSEMB_COMP

FIELD NAME = (PS, SEQ), BYTES-5, START = 1

FIELD NAME = PD, BYTES = 25, START = 6

FIELD NAME = CL, BYTES = 2, START = 31

SEGM NAME = ASSEMB_COMP, BYTES = 10

POINTER = (LPART, TWIN, LTWIN)

PARENT (PART), SOURCE (PART, PHISICAL, DB3)

FIELD NAME = (PS, SEQ), BYTES = 5, START-1

FIELD NAME = OTY, BYTES = 5, START = 6

SEGM NAME = COMP_ASSEMB, BVTES = 10

POI NTER = RAI DER

FIELD NAME = (PS, SEQ), BYTES = 5, START = 1

PARENT PART, SOURCE (ASSEMB COMP, DB3)

FIELD NAME = (PS, SEQ), BYTES = 5, START = 1

FIELD NAME = OTV, BYTES = 5, START = 6

Реалізація ієрархічної БД

Рис. 6.9. Реалізація ієрархічної БД

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

Створення ієрархічної БД (ЯОД)

Базовими мовами ієрархічної БД раніше може бути COBOL, PL / 1, Assembler.

Ілюстрацію ЯОД зручно вести на основі програми мовою СУБД IMS. Оголошуються імена БД, сегмента і полів. Для одного з полів, по якому йде впорядкування, вказується мітка SEQ і кількість породжених сегментів: один (U) або багато (М). Відзначається вихідний (PARENT) сегмент. Може бути присутнім поле покажчика (POINTER), метод доступу (HISAM).

Введення логічних зв'язків позначається командою LCHILD, в якій вказуються імена породженого логічного сегмента і сегмента БД, а в команді PARENT - вихідні фізичний і логічний сегменти БД.

Використання ієрархічної БД (ЯМД)

Відновлення здійснюється командами REPLACE (замінити) і DELETE (видалити поточний сегмент і породжені). Вставка (INSERT) може бути по відношенню до поточного вихідного сегменту (INSERT S) або за вказівкою (INSERT клієнти WHERE МІСТО = 'СПб' and ІМ'Я АГЕНТА = 'Святослав').

Приміщення сегмента в область введення-виведення здійснюється командою GET:

GET UNIQUE <ім'я сегмента>

WHERE <умова>,

GET NEXT,

GET NEXT WITHIN PARENT.

З опису ієрархічної МД видно, що БД побудувати досить складно. Тут немає чіткого поділу логічної і фізичної структур. Набір структур запитів обмежений, а для неієрархічних зв'язків потрібні додаткові логічні зв'язки, що перетворюють фактично ієрархічну МД в мережеву.

 
Якщо Ви помітили помилку в тексті позначте слово та натисніть Shift + Enter
< Попередня   ЗМІСТ   Наступна >
 
Дисципліни
Агропромисловість
Аудит та Бухоблік
Банківська справа
БЖД
Географія
Документознавство
Екологія
Економіка
Етика та Естетика
Журналістика
Інвестування
Інформатика
Історія
Культурологія
Література
Логіка
Логістика
Маркетинг
Медицина
Нерухомість
Менеджмент
Педагогіка
Політологія
Політекономія
Право
Природознавство
Психологія
Релігієзнавство
Риторика
Соціологія
Статистика
Техніка
Страхова справа
Товарознавство
Туризм
Філософія
Фінанси
Пошук