Навігація по ієрархій і мереж в реляційних базах даних (исходники), CASE-засоби (моделювання), Програмування, статті

Навіщо бувають потрібні ієрархії


Останнім часом часто зустрічаються програмні системи, що використовують ієрархії на рівні реляційної БД. Зазвичай ієрархії потрібні для двох цілей: каталогізація або розмежування прав доступу. Для задач розмежування прав доступу характерний підхід, коли будь-яке право доступу має автоматично поширюватися на деякі нові об’єкти. Така вимога зручно виконувати за допомогою т.зв. “Рекурсивних” прав доступу, поширюються вниз по ієрархії об’єктів. При цьому автоматизм поширення прав доступу досягається за рахунок того, що нові об’єкти додаються у спеціально відведену гілку ієрархії.


Проблематика роботи з ієрархіями в реляційних БД


Не будемо детально зупинятися на тому, яким чином зазвичай реалізують ієрархії в реляційних БД. Отже, нехай є ієрархія, побудована на відношенні з атрибутами id, parent_id. Розглянемо типові задачі, пов’язані з деяким елементом такої ієрархії:



Перші два завдання досить добре оптимізуються за допомогою індексів по полям id і parent_id. Для вирішення решти зазвичай використовується програмний код, що виробляє рекурсивний обхід ієрархії. Деякі СУБД навіть надають мовні розширення SQL, що дозволяють робити подібні рекурсивні обходи (наприклад, в Oracle це start with … connect by …).


Рекурсивний обхід для вирішення зазначених завдань найчастіше є не найкращим рішенням. Причини:



Способи оптимізації для навігації по ієрархії


Якщо ієрархія статична (елементи рідко додаються і видаляються), найпростіша оптимізація – містити послідовність рекурсивного обходу ієрархії в заздалегідь прорахованому вигляді. У самому справі, якщо зіставити з кожним елементом ієрархії номер цього елемента по порядку рекурсивного обходу, то обхід можна буде робити рухом по індексу. Тим самим час вибірки n елементів складе O (n), що істотно краще, ніж O (n ln n).



Рисунок 1


На малюнку 1 показана таблиця, що реалізує такий спосіб оптимізації. Кожен запис у таблиці – елемент ієрархії з ідентифікатором id і покажчиком на батьківський елемент parent_id. Крім цих атрибутів, є ще порядковий номер рекурсивного обходу recursion_order, кількість елементів піддереві subtree_size і рівень елементу в ієрархії absolute_level. Нижче наведено характерні запити, які можна проводити за допомогою цієї оптимізації.


Приклад 1. Вибірка піддереві елемента node (включаючи сам елемент):




 select * from Hierarchy
where recursion_order
between node.recursion_order
and (node.recursion_order + node.subtree_size – 1)

Приклад 2. Вибірка шару (на рівнях 3-5) в піддереві поточного елемента node:




 select * from Hierarchy
where recursion_order
between node.recursion_order
and (node.recursion_order + node.subtree_size – 1)
and absolute_level – node.absolute_level between 3 and 5

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


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


Тепер розглянемо випадок, коли ієрархія не статична. Пропонований спосіб навігації по мінливим ієрархій вимагає побудови транзитивного замикання відносини батько-нащадок. Практично це реалізується наступним чином. Додається нове ставлення з атрибутами upper_id, lower_id, relative_depth, яке містить всі прямі генеалогічні стосунки (в т.ч. батько – нащадок, батько батька – нащадок, батько батька батька – нащадок, і т.д.). Якщо у відповідній таблиці зробити потрібні індекси, з’являється можливість швидкої вибірки як будь-яких батьків, так і будь-яких нащадків (в т.ч. пошарово).



Рисунок 2.


На малюнку 2 показана таблиця Hierarhy, а також пов’язана з нею таблиця Genealogy. У таблиці Genealogy кожен запис – це пряма генеалогічна зв’язок між двома елементами ієрархії. Ідентифікатор верхнього елемента представлений атрибутом upper_id, нижнього елемента – lower_id, рівень одного елемента щодо іншого – атрибутом relative_depth.


Чудова особливість цього способу навігації – при його використанні переважна більшість завдань за вибіркою даних з ієрархії більше не вимагають розробки процедурного програмного коду. Замість цього, з’являється можливість вибірки з використанням тільки декларативних SQL-запитів.


Приклад 3. Вибірка всіх прямих батьківських вузлів (за всіма рівнями ієрархії вище поточного елемента):




 select upper_id from Genealogy where lower_id = <поточний елемент>

Приклад 4. Вибірка прямого батьківського сайту на другому рівні (батько батька):




 select upper_id from Genealogy where lower_id = <поточний елемент>
and relative_depth = 2

Приклад 5. Вибірка всіх дочірніх вузлів (піддереві поточного елемента):




 select lower_id from Genealogy where upper_id = <поточний елемент>

Приклад 6. Вибірка шару (на рівнях 3-5) в піддереві поточного елемента:




 select lower_id from Genealogy where upper_id = <поточний елемент>
and relative_depth between 3 and 5

Розглянемо типові ємнісні і тимчасові складнощі, пов’язані з цим підходом (без урахування особливостей реалізації СУБД):
























Характеристика Типове значення Граничне значення
Ємнісна складність n ln n n2 
Час вибірки будь-якого прямого предка O(1) O(1)
Час вибірки шару прямих нащадків, у розрахунку на одного нащадка O(1) O(1)
Час додавання / видалення елемента з ієрархії O(ln n) O(n)

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


Навіщо бувають потрібні мережі


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



Рисунок 3.


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


Варіантом вирішення є структурування об’єктів в мережу, з поширенням “рекурсивних” прав доступу вздовж ребер цієї мережі. Принципова відмінність від ієрархії – в можливості “покласти” об’єкт не в один каталог, а відразу в декілька. Задавши різні рекурсивні права доступу до цих каталогів, можна домогтися, щоб документ був видний різним категоріям користувачів. У наведеній вище ситуації для кожного відправника і одержувача буде заведений свій каталог, на вміст яких їм будуть видані права (разом 2n каталогів). Посилається документ буде “покладено” відразу в два каталоги: каталог відправника і каталог одержувача. Таким чином, відправник та одержувач отримають необхідні права доступу до цього документа, а всі інші користувачі – ні.


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


Оптимізація навігації по мережі


Навігація по мережі нагадує навігацію по ієрархії. Що характерно, і оптимізація проводиться аналогічним способом: створенням транзитивного замикання відносини “попередній вузол” – “наступний вузол”. Інакше кажучи, слід створити нове ставлення, яке буде містити всілякі пари таких вузлів (node_from, node_to), що з node_from можна потрапити в node_to.



Рисунок 4.


На малюнку 4 показаний варіант такої оптимізації. Додатково до таблиці Node, яка містить атрибути вузла, і таблиці Link, яка містить ребра мережі, вводиться таблиця Path, яка містить шляху з вузла у вузол. У таблиці Path атрибут from_id вказує на вихідний вузол мережі, атрибут to_id – кінцевий вузол мережі, а атрибут length – на довжину шляху.


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


Приклад 7. Вибірка безлічі вузлів, в які можна потрапити з даного вузла:




 select distinct to from Path where from_id = <поточний елемент>

Приклад 8. Вибірка безлічі вузлів на певній відстані від даного узлa:




 select distinct to from Path where from_id = <поточний елемент> and length = <відстань>

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


Що стосується запиту в прикладі 8, він вибирає всі вузли на певній відстані від даного, і тому таблиця Path повинна містити всі можливі шляхи різної довжини. Природно, цей спосіб оптимізації можливий тільки для ациклічних мереж. Для того, щоб цей запит виконувався найбільш ефективно, можна використовувати унікальний індекс по полях from_id, length, to_id.


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


Висновок


У статті були розглянуті способи, що дозволяють істотно спростити вибірку елементів з ієрархій та мереж, побудованих в реляційних базах даних. Описані підходи несуть в собі відразу дві переваги:



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

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


Схожі статті:


Сподобалася стаття? Ви можете залишити відгук або підписатися на RSS , щоб автоматично отримувати інформацію про нові статтях.

Коментарів поки що немає.

Ваш отзыв

Поділ на параграфи відбувається автоматично, адреса електронної пошти ніколи не буде опублікований, допустимий HTML: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>

*

*