Версія для друку

Основні поняття Мисленого древа 3

Дерево

В основі ієрархічної СУБД «Мислене древо» лежить поняття дерева. Дерево, мовою теорії графів – це однозв’язний граф, тобто такий граф, у якого кожні дві вершини зв’язані між собою безпосередньо або через інші вершини, і цей зв’язок є тільки один. Отже, кожна база даних «Мисленого древа» містить в собі одним-одно дерево, до якого приєднані усі вершини. «Мислене древо» уміє віртуалізувати це дерево і представляти його у вигляді сукупності незалежних дерев, але у файлі зберігається єдине дерево.

Дерево вершин в МД – орієнтоване, тобто кожен зв’язок між вершинами є однонаправленим. Він направлений від вершини-господині до дочірньої вершини. Таким чином, дерево даних містить одну кореневу вершину і ряд підпорядкованих вершин різних рівнів. Воно закінчується термінальними вершинами, які не мають підпорядкованих вершин (але в процесі наповнення БД вони можуть з’явитись).

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

Вершина

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

МД підтримує вершини різних типів, але для користувача найбільше значення має одни тип, який зветься інформаційний об’єкт. Кожен об’єкт відповідає одній вершині у візуальному редакторі дерева (цей візуальний редактор має спеціальну назву інспектор). Тобто ми вживаємо термін вершина, коли говоримо про елемент візуального інтерфейса, і термін інформаційний об’єкт, коли говоримо про фрагмент даних, який зберігається у файлі. Вершина – це інформаційний об’єкт, прочитаний з файлу, завантажений в оперативну пам’ять і представлений в інспекторі.

Терміни спорідненості

Коренева вершина – вершина найвищого ієрархічного положення, яка не має господині.

Вершина-господиня – вершина вищого ієрархічного рівня, якій безпосередньо підпорядкована дана вершина.

Коріння – ланцюжок вершин, який веде від даної вершини до кореневої.

Шлях – строка, яка містить логічні імена вершин коріння. Шлях може відраховуватись від кореня (Україна | Київ | Хрещатик), або від поточної вершини (Хрещатик | Київ | Україна).

Крона – сукупність поточної вершини та всіх підпорядкованих їй вершин.

Рівні вершини – вершини, які підпорядковані одній вершині-господині (в українській мові немає аналога енергійному англійському слову siblings – брати і сестри, діти одних батьків).

Переходи, мости і дзеркала

Окрім регулярних вершин, безпосередньо зв’язаних з інформаційними об’єктами, МД підтримує три типи псевдовершин. Псевдовершина відображається в інспекторі, але не має власного інформаційного об’єкту.

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

Міст є симетричним зв’язком між двома іншими вершинами (які в такому випадку звуться берегами). Візуально він виглядає як вершина, підпорядкована береговій вершині. Основне його призначення – забезпечувати двонаправлений зв’язок між берегами. Наприклад, міст може пов’язувати статтю, в якій зроблено посилання, з цитованою статтею; міст може пов’язувати музейний предмет і колекцію, до якої він належить (в такому випадку вершина «Колекція» автоматично нагромаджує список мостів до предметів, з яких вона складається). Запроектовані нами мости не мають аналогів в інших інформаційних системах.

Дзеркало є асиметричним зв’язком між двома іншими вершинами. На відміну від переходу, при активізації дзеркала крона вершини-цілі відображається в контексті вершини-господині дзеркала. Простою мовою, дзеркало – це спосіб вставити фрагмент дерева в інше місце дерева, не копіюючи при цьому даних. Запроектовані нами дзеркала не мають аналогів в інших інформаційних системах (хіба що hard links у файловій системі NTFS до них наближаються).

Запровадження поняття псевдовершин відхиляє проект від хімічно чистої ієрархічної схеми і запроваджує елементи мережевої моделі даних.

Набори даних

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

В загальному випадку вершина пов’язана з вершиною-господинею, з сусідніми (рівними) вершинами та з підпорядкованими вершинами. Отже, перехід від одного набору даних до іншого (який ми звемо трансформацією набору даних) пов’язана з віртуальною зміною цих зв’язків. Простою мовою, набір даних представляє вершини зв’язаними не так, як у реальному дереві.

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

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

Набір з кроною – містить поточну вершину та її крону; ігноруються рівні вершини та господиня. Надзвичайно корисна річ, дозволяє зосередитись на внутрішній структурі певного об’єкту. Нам постійно не вистачає такої можливості у Windows Explorer : чому не можна обмежити дерево тільки поточним каталогом ?

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

Набір рівних з кронами – об’єднання попередніх двох випадків. Ігнорується вершина-господиня.

Набір-коріння – містить вершини, які утворюють коріння поточної вершини. Ігноруються рівні та підпорядковані вершини.

Набір-гілка – об’єднання коріння і крони поточної вершини. Ігноруються рівні вершини.

Слід пам’ятати, що МД виконує трансформацію в контексті поточного набору даних. Тому, наприклад, якщо поточною є вершина А і застосовано набір з кроною, а потім для підпорядкованої вершини Б застосовано набір-коріння, то коріння закінчиться на вершині А (навіть якщо в головному наборі даних вершина А не є кореневою).

Відмічені вершини

Кожен інспектор має свою власну колекцію відмічених вершин. Користувач може відмічати вершини вручну (за допомогою клавіатури або мишки) або автоматично – командами відмітки групи споріднених вершин. Результатом процесу відбору вершин також є відмічені вершини.

Відмічені вершини – це також група спорідненості, тому на ній можна побудувати трансформатори наборів даних.

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

Відмічені з кронами – набір, подібний до попереднього, але включаються крони відмічених вершин.

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

Відмічені з гілками – об’єднання двох попередніх випадків. Дозволяє компактно представити вибрані дані (наприклад, результати відбору), які в головному наборі даних можуть бути віддаленими на сотні і тисячі вершин.

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

Процесори

Процесом в МД 3 зветься будь-який цикл однотипних операцій над вершинами. Прикладами процесів можуть бути відбір вершин згідно заданого критерію чи експорт вершин.

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

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

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

Ієрархічна навігація

Отже, в ієрархічній СУБД всі операції є ієрархічними. Це ускладнює роботу з ієрархічною СУБД в порівнянні з табличною СУБД, де всі набори даних є лінійними (або в термінології МД 3 – наборами рівних вершин).

Якщо в лінійному наборі даних навігація обмежувалась до 4 команд : перша | попередня | наступна | остання вершини, то в дереві команд значно більше. Розлгянемо пари команд навігації.

Перша / остання вершини – переміщує нас відповідно до першої кореневої вершини або до останньої (ієрархічно наймолодшої) вершини в кроні останньої кореневої вершини.

Перша / остання рівні вершини – переміщують нас серед вершин заданого ієрархічного рівня.

Попередня / наступна рівні вершини – переміщують нас серед вершин заданого ієрархічного рівня. Ці 4 команди є найбільш подібними до команд табличної навігації.

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

Попередня / наступна відмічені вершини – переміщують нас по списку відмічених вершин.

Вершина-господиня, коренева вершина – переміщують нас вгору по корінню даною вершини.

Остання вершина крони – переміщує нас до вершини, яка є наймолодшою серед вершин усіх рівнів, підпорядкованих даній.

Молодша лінія – переміщує нас до вершини, яка є наступною після останньої вершини в кроні (якщо така є).