Ієрархічні структури та дерева в SQL, Світ ПК, Видавництво «Відкриті системи»
Програмістові, що працює з додатками баз даних, на практиці часто доводиться стикатися з деревоподібними структурами
. Приклади можуть бути знайдені в різних предметних областях: класифікація товарів, контрагентів, комплектація виробу, ієрархія посад, адміністративно-територіальний поділ, генеалогічне дерево, нарешті, просто дерево перебору варіантів або дерево класів. У загальному випадку все зводиться до моделювання багаторівневого зв'язку «головний-підлеглий», «предок-нащадок», «загальний-конкретний». Говорячи суворішою математичною мовою, ми моделюємо граф без циклів. Заглиблюватися в теорію графів у рамках статті ми не будемо, обмежившись мінімальними поясненнями по ходу викладу, і розглянемо варіанти реалізації деревоподібних структур, що найчастіше зустрічаються, в базах даних. Як приклад використовуємо Microsoft SQL Server 2005, але, познайомившись із загальними принципами, ви зможете легко перенести реалізацію на будь-яку іншу СУБД, з якою доведеться працювати.
Список суміжності Це інтуїтивно зрозумілий спосіб організації дерева: замикаємо зв'язок таблиці на саму себе (рефлексивний зв'язок), рис. 1.
Як відомо з теорії, граф можна подати у вигляді матриці, де на перетині i-го рядка і j-го стовпця стоїть 1, якщо між вузлами (вершинами) графа з номерами i і j є зв'язок (ребро, дуга), або 0 інакше. Така абстракція називається матрицею суміжності. Матриця суміжності може бути представлена у вигляді списку (множини) пар з номерами (ідентифікаторами, кодами) вершин за принципом: є пара — є зв'язок, немає пари — немає зв'язку. Корневі вершини відрізняються від інших пар порожнім (NULL) посиланням на предка, у наведеному прикладі цеполе «Код вищої території». Для виконання часто використовуваних вибірок потрібна підтримка рекурсивних запитів. Якщо СУБД не вміє виконувати такі запити, то вибірки доведеться будувати з використанням інших механізмів, наприклад, тимчасових таблиць або процедур і функцій, що зберігаються. Розглянемо приклади запитів. Вибірка піддерева по заданому вузлу (тут і далі текстом використовуємо синтаксис MS SQL Server 2005):
WITH Поддерево ([Код території], [Код вищої території], Найменування, Рівень) AS ( SELECT [Код території], [Код вищої території], Найменування, 1 FROM Території WHERE [Код вищої території] = 40288000 - корінь піддерева або IS NULL для кореня цілого дерева UNION ALL SELECT Території. [Код території], Території. [Код вищої території], Території. Найменування, Рівень + 1>FROM Території INNER JOIN Піддерево ON Території.[Код вищої території] = Піддерево.[Код території] WHERE Території.[Код вищої території] IS NOT NULL ) SELECT [Код території] , [Код вищої території], Найменування, Рівень FROM Поддерево
Вибірка всіх предків (шлях до вузла від кореня):
WITH Поддерево ([Код території], [Код вищої території], Найменування, Рівень) AS ( SELECT [Код території], [Код вищої території], Найменування, 1 FROM Території WHERE [Код території] = 40288000 — вузол UNION ALL SELECT Території.[Код території], Території.[Код вищестоящої території], Території.Найменування, Рівень + 1 FROM Території INNER JOIN ON Території.[Код території] = Поддерево.[Код вищої території] ) SELECT [Код території], [Код вищої території], Найменування, (SELECT MAX(Рівень) FROM Піддерево) — Рівень FROM Піддерево
Перевірка, чи входить вузол у піддерево, яке визначається своїм коренем (наприклад, чи входить даний товар до групи одного з верхніх рівнів, «Пензлик» до «Інструментів для ремонту»):
WITH Поддерево ([Код території], [Код вищої території], Найменування, Рівень) AS ( SELECT [Код території], [Код вищої території], Найменування, 1 FROM Території WHERE [Код території] = 40288000 - вузол, що перевіряється на входження UNION ALL SELECT Території.[Код території], Території>INNER JOIN Піддерево ON Території.[Код території] = Піддерево.[Код вищої території] ) SELECT result = CASE WHEN EXISTS( SELECT 1 FROM Піддерево WHERE [Код території] = 40260000 /* корінь піддерева */) THEN 'Вузол входить у піддерево' ELSE 'Вузол НЕ входить у піддерево' END
Підмножини Одразу обмовлюся: до способу, що просувається Джо Селко (Joe Celko) і з непорозуміння званого nested sets (вкладені множини), ця схема ніякого відношення не має. Тому, щоб уникнути плутанини, я навіть змінив інформативну назву «вкладені множини» на простішу. У цій схемі дерево представляється вкладеними підмножинами: кореневий рівень включає всі підмножини — вузли першого рівня, а вони, у свою чергу, включають всі вузли другого рівня і т.д. Ієрархія територій може бути так, як показано на рис. 2.
У реляційному вигляді схема представлена на рис. 3.
Але за надмірність треба платити. Цілісність даних підтримуватиметься тригерами, які перезаписують список та рівні предків даного вузла при його зміні. Для операції видаленнядостатньо декларативної цілісності посилань (каскадне видалення), якщо ваша СУБД його підтримує. Якщо за зразок прийняти список суміжності, який не містить жодної надмірності, то для методу підмножин на кожен рівень потрібно стільки додаткових записів у таблиці підмножин, скільки елементів знаходиться на даному рівні дерева, помноженому на номер рівня (вершину вважаємо першим рівнем). Кількість записів зростає в арифметичній прогресії. Однак варто подивитися на приклади тих самих типових запитів, як стають очевидними переваги, отримані від надмірності зберігання: запити стали короткими і швидкими. Вибірка піддерева по заданому вузлу: SELECT [Код підмножини], Рівень FROM Підмножини WHERE [Код множини] = 123 - корінь піддерева ORDER BY Рівень Вибірка всіх предків ( шлях до вузла від кореня): SELECT [Код множини], Рівень FROM Підмножини WHERE [Код множини] = 345 - вузол ORDER BY Рівень
Перевірка входження вузла в піддерево:
SELECT result = CASE WHEN EXISTS( SELECT 1 FROM Підмножини WHERE [Код підмножини] = 345 /* вузол */ AND [Код множини] = 211 /* корінь піддерева * /) THEN 'Вузол входить у піддерево' ELSE 'Вузол НЕ входить у піддерево' END
Маршрут обходу Як відомо з вже згаданої теорії графів, для обходу дерева існує три способи: можна проходити вузли в префіксному, інфіксному або суфіксному порядку. Префіксний порядок обходу дерева рекурсивно визначається так: спочатку корінь дерева, потім вузли лівого піддерева у префіксному порядку, нарешті, вузли правого піддерева у префіксному порядку. Важко? Погляньте на рис. 4, і все стане гранично ясно.
SELECT T1.* FROM [Території 3] as T1, [Території 3]as T2 WHERE T1.Вхід BETWEEN T2.Вхід AND T2.Вихід AND T2.[Код території] = 123 - корінь піддерева ORDER BY T1.Вхід
Вибірка всіх предків симетрична попередньому запиту щодо BETWEEN: SELECT T1.* FROM [Території 3] as T1, [Території 3] as T2 WHERE T2>AND T2.[Код території] = 345 - вузол ORDER BY T1.Вхід Перевірка входження вузла в піддерево: SELECT result = CASE WHEN EXISTS( SELECT 1 FROM [Території 3] as T1, [Території 3] as T2 WHERE T1.[Код території] = 456 /* вузол */ AND T2.[Код території] = 123 /* корінь піддерева */ AND T1.Вхід BETWEEN T2.Вхід AND T2.Вихід) THEN 'Вузол входить у піддерево' ELSE 'Вузол НЕ входить у піддерево' END
Оптимізація: зберігання номерів з «дірками» Давним-давно, в епоху поширеності мови Бейсік (не плутати з Visual Basic), рядки програми послідовно нумерувалися. Робилося це для того, щоб, по-перше, інтерпретатору було легше обробляти текст програми, а по-друге, щоб працювали численні оператори безумовного переходу (GOTO, якщо хтось забув) на рядок з таким номером. Існувало й обмеження, згідно з яким на кожному рядку міг перебувати лише один оператор. Оскільки програма під час свого життя зазнавала змін, то до неї додавалися нові оператори. Досвідчені програмісти одразу нумерували рядки не 1, 2, 3, а 10, 20, 30. Це дозволяло вставити в текст новий рядок без повної перенумерації всіх наступних. Думаю, ідею ви вже зрозуміли: треба нумерувати входи та виходи з вузлів з деяким інтервалом, наприклад 100 або 1000, що значною мірою залежить від попередніх оцінок кількості вузлів дерева, що зберігаються.
Матеріалізовані шляхи Суть методуполягає у зберіганні шляху від вершини до даного вузла в явному вигляді та як ключ. Наприклад, раніше наведена малюнку ієрархія територій міг би виглядати так: Як бачите, дуже нагадує нумерацію частин, розділів і розділів у книзі. Цей метод є найбільш наочним з погляду кодифікації елементів: кожен вузол отримує інтуїтивно зрозуміле значення, сам код та його частини несуть смислове навантаження. Подібні властивості важливі у класифікаціях, призначених для широкого використання, наприклад, у стандартизованих довідниках територій (ОКАТО), галузей економіки (ЗКВЕД, NAICS), медичних діагнозів (МКБ – міжнародний класифікатор хвороб) та у багатьох інших областях. Складніша ситуація із запитами. Вони лаконічні, але не завжди ефективні, тому що можуть вимагати пошуку по підрядку. Вибірка піддерева по заданому вузлу:
SELECT * FROM [Території 4] WHERE Шлях LIKE ‘1.2%’ — корінь піддерева ORDER BY Шлях
SELECT * FROM [Території 4] WHERE '1.2.1' /* вузол */ LIKE Шлях + '%' ORDER BY Шлях
SELECT T1.* FROM [Території 4] T1, [Території 4] T2 WHERE T2.Шлях LIKE T1.Шлях + '%' AND T2.Найменування like 'МО Рибальське'
Перевірка входження вузла в піддерево:
SELECT result = CASE WHEN EXISTS( SELECT 1 FROM [Території 4] as T1, [Території 4] as T2 WHERE T1.Найменування = 'МО Рибальське' /* вузол */ AND T2.Найменування = 'Невський район' /* корінь піддерева */ AND T1.Шлях LIKE T2.Шлях + '%') THEN 'Вузол входить у піддерево' ELSE 'Вузол НЕ входить у піддерево' END
Оптимізація Знаючи максимальну кількість рівнів і максимальну кількість прямих нащадків, можна обійтися без роздільників, використовуючи числові кодиз фіксованою розбивкою на групи розрядів. Порожні лідируючі розряди заповнюються нулями. Подібна система використовується в багатьох міжсистемних класифікаторах, наприклад, що належать до державного стандарту ОКАТО (Загальноукраїнський класифікатор об'єктів адміністративно-територіального поділу) або NAICS (North American Industry Classification System — Північноамериканська система класифікації галузей економіки).
Підсумки Настав час підвести межу під нашим невеликим оглядом. Якщо зібрати переваги та недоліки в одну загальну таблицю, ми отримаємо більш повну картину. Слід пам'ятати, що немає «поганих» або «хороших» методів: ви робите оцінки та вибір, виходячи з умов конкретного завдання. Нам хотілося показати вам основні принципи, використовуючи які ви зможете не тільки зробити обґрунтований раціональний вибір одного з відомих методів, а й створити свій оптимізований варіант. Врешті-решт інженер тим і відрізняється від робітника на складанні, що може і повинен вміти знаходити оптимальні засоби для вирішення завдання, а не сліпо копіювати чужі інструкції та шаблони.
Рекомендована література та ресурси