Проектування баз даних: ієрархічні структури. Дерева в SQL

1. Переваги і недоліки
2. Переваги і недоліки
3. Переваги і недоліки
4. Оптимізація: зберігання номерів з "дірками"
5. оптимізація
6. Переваги і недоліки

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

* * *

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

Аби не заглиблюватися в теорію графів, в рамках статті ми розглянемо найбільш часто зустрічаються варіанти реалізації деревовидних структур в базах даних. Як приклад використовується Microsoft SQL Server 2005 і вище (будь-яка редакція), але, познайомившись із загальними принципами, ви зможете без труднощів перенести реалізацію на будь-яку іншу СУБД.

Це інтуїтивно зрозумілий спосіб організації дерева: замикаємо зв'язок таблиці на саму себе (рефлексивна зв'язок), рис. 1.

Рис.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 території. [Код території], території. [Код вищестоящої території], Терріторіі.Наіменованіе, Рівень + 1 FROM території INNER JOIN Піддерево ON території. [Код території] = Піддерево. [Код вищестоящої території]) SELECT result = CASE WHEN EXISTS (SELECT 1 FROM Піддерево WHERE [Код території] = 40260000 / * корінь поддерева * /) THEN 'Вузол в ходить в поддерево 'ELSE' Вузол НЕ входить в поддерево 'END

Переваги і недоліки

Простота структури (таблиць / посилань / мінімальна кількість полів) 1/1/3 Пряма вибірка всіх дітей вузла та Пряма вибірка поддерева (всіх нащадків вузла) немає, рекурсія Пряма вибірка шляху від вузла до кореня (всіх предків вузла) немає, рекурсія Швидке визначення кількості всіх нащадків вузла немає, рекурсія Швидке визначення рівня немає, рекурсія Порядок проходження вузлів при сортуванні ні Швидка вставка нових вузлів та Швидке переміщення поддерева та Швидке видалення поддерева так, каскадне Надмірність зберігання немає Кількість рівнів дерева нео ранічено Додаткова підтримка цілісності (крім довідкової) не потрібна

Відразу обмовлюся, до способу, що просувається Джо Селко (Joe Celko) і через непорозуміння званого nested sets (вкладені безлічі), ця схема відношення не має. Тому, щоб уникнути плутанини, я навіть змінив інформативне назву "вкладені безлічі" на більш просте.

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

Рис.2. Подання ієрархії у вигляді вкладених підмножин

У реляционном ж вигляді схема буде виглядати так.

Рис.3. Реалізація методу підмножин

Цілісність підтримується тригерами, які перезаписують список і рівні предків даного вузла при його зміні. Для видалення досить декларативною посилальної цілісності (каскадне). Приклад заповнення таблиць.

ТериторіїКод територіїНайменування

1 Санкт-Петербург 2 Московський район 3 МО Новоізмайловского Підмножини Код безлічі Код підмножини Рівень 1 1 1 2 1 1 2 2 2 3 1 1 3 2 2 3 3 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

Переваги і недоліки

Простота структури (таблиць / посилань / мінімальна кількість полів) 2/2/5 Пряма вибірка всіх дітей вузла та Пряма вибірка поддерева (всіх нащадків вузла) та Пряма вибірка шляху від вузла до кореня (всіх предків вузла) та Швидке визначення кількості всіх нащадків вузла да Швидке визначення рівня та Порядок проходження вузлів при сортуванні ні Швидка вставка нових вузлів немає Швидке переміщення поддерева немає Швидке видалення поддерева так, каскадне Надмірність зберігання та Кількість рівнів дерева необмежена Додаткова підтримка цілісність ності (крім довідкової) потрібна, проста

Як відомо з уже згаданої теорії графів, для обходу дерева існує три способи: можна проходити вузли в префіксному, інфіксне або суффіксном порядку. Префіксний порядок обходу дерева рекурсивно визначається так: спочатку корінь дерева, потім вузли лівого піддерева в префіксному порядку, нарешті, вузли правого піддерева в префіксному порядку. Складно? Погляньте на рис. 4, і все стане гранично ясно.

Рис.4. Маршрут обходу дерева в префіксному порядку

Зберігання маршруту обходу дерева в префіксному порядку і є той самий спосіб, який його шановний автор Джо Селко (або його інтерпретатори), мабуть, через непорозуміння просуває під назвою «вкладені безлічі» (nested sets). Через непорозуміння, тому що з рис. 4 ясно, що про множини тут мови не йде. Однак ця проблема з назвами анітрохи не зменшує практичної цінності методу.

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

Рис.5. Реалізація зберігання маршруту обходу

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

Вибірка поддерева по заданому вузлу:

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.Вход BETWEEN T1.Вход AND T1.Виход 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

Переваги і недоліки

Простота структури (таблиць / посилань / мінімальна кількість полів) 1/0/4 Пряма вибірка всіх дітей вузла та Пряма вибірка поддерева (всіх нащадків вузла) та Пряма вибірка шляху від вузла до кореня (всіх предків вузла) та Швидке визначення кількості всіх нащадків вузла да Швидке визначення рівня та Порядок проходження вузлів при сортуванні та Швидка вставка нових вузлів немає Швидке переміщення поддерева немає Швидке видалення поддерева та Надмірність зберігання та Кількість рівнів дерева необмежена Додаткова підтримка цілісності (крім посилальної) потрібна, складна

Оптимізація: зберігання номерів з "дірками"

Давним-давно в епоху поширеності мови Бейсік (Basic, не плутати з Visual Basic) рядки програми послідовно нумеровались. Щоб, по-перше, інтерпретатора було легше обробляти текст програми, а, по-друге, щоб працювали численні оператори безумовного переходу GOTO на рядок з таким-то номером, причому оператор відповідав рядку. Програма під час свого життя модифікувалася, в неї додавалися нові оператори. Тому досвідчені програмісти нумерували рядки не 1,2,3 ..., а 10, 20, 30. Це дозволяло вставити новий рядок без повної перенумерации всіх наступних.

Думаю, принцип ви вже зрозуміли: нумерувати входи і виходи з вузлів з деяким інтервалом, наприклад 100 або 1000, що в значній мірі залежить від попередніх оцінок кількості збережених рядків.

Ідея методу полягає в зберіганні шляху від вершини до даного вузла в явному вигляді і в якості ключа. Наприклад, ієрархія територій на рис.4 могла б виглядати так:

ТериторіїНайменуванняШлях

Санкт-Петербург 1 Московський район 1.1 МО Новоізмайловского 1.1.1 МО Кузнецовське 1.1.2 Невський район 1.2 МО Рибальське 1.2.1 Центральний район 1.3

Даний метод є найбільш наочним з точки зору кодифікації елементів: кожен вузол отримує інтуїтивно зрозуміле значення, сам код і його частини несуть смислове навантаження. Подібні властивості важливі в класифікаціях, призначених для широкого використання, наприклад в стандартизованих довідниках територій (ОКАТО), галузей економіки (КВЕД, NAICS), медичних діагнозів (МКБ - міжнародний класифікатор хвороб) і в багатьох інших областях.

Рис.6. Реалізація зберігання матеріалізованих шляхів

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

Вибірка поддерева по заданому вузлу:

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 - Північноамериканська система класифікації галузей економіки).

Переваги і недоліки

Простота структури (таблиць / посилань / мінімальна кількість полів) 1/0/2 Пряма вибірка всіх дітей вузла та Пряма вибірка поддерева (всіх нащадків вузла) та Пряма вибірка шляху від вузла до кореня (всіх предків вузла) та Швидке визначення кількості всіх нащадків вузла да Швидке визначення рівня та Порядок проходження вузлів при сортуванні та Швидка вставка нових вузлів немає Швидке переміщення поддерева немає Швидке видалення поддерева немає Надмірність зберігання та Кількість рівнів дерева обмежена Додаткова підтримка цілісності (крім силочной) потрібна, складна Списки суміжності Підмножини Зберігання маршруту обходу Матеріалізовані шляху Простота структури (таблиць / посилань / мінімальна кількість полів) 1/1/3 2/2/5 1/0/4 1/0/2 Пряма вибірка всіх дітей вузла та да да да Пряма вибірка поддерева (всіх нащадків вузла) немає, рекурсія да да да Пряма вибірка шляху від вузла до кореня (всіх предків вузла) немає, рекурсія да да да Швидке визначення кількості всіх нащадків вузла немає, рекурсія да да да Швидке визначення рівня немає, рекурсія да да да Порядок проходження вузлів при сортуванні ні ні так а Швидка вставка нових вузлів так ні ні ні Швидке переміщення поддерева так ні ні ні Швидке видалення поддерева так, каскадне так, каскадне так ні Надмірність зберігання немає да да да Кількість рівнів дерева необмежену необмежену необмежену обмежене Додаткова підтримка цілісності (крім довідкової) не потрібна потрібна потрібна потрібна

1. Joe Celko. Trees in SQL. Some answers to some common questions about SQL trees and hierarchies
2. Vadim Tropashko. Trees in SQL: Nested Sets and Materialized Path
3. Джо Селко. Стиль програмування Джо Селко на SQL. Пер. з англ. СПб .: Питер, 2006.

Сергій Тарасов, жовтень 2006

Стаття також опублікована в "Світ ПК" №3 2007 р Журнальний варіант статті на сайті видання