Навігація по ієрархій та мереж в реляційних базах даних (вихідні коди)

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


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


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


Не будемо детально зупинятися на тому, яким чином зазвичай реалізують ієрархії в реляційних БД. Отже, нехай є ієрархія, побудована на відношенні з атрибутами 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. Нижче наведено характерні запити, які можна проводити за допомогою цієї оптимізації.



Малюнок 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>

*

*