Дерева в SQL
Дерево – спеціальний вид направленого графа. Графи - структури даних, які з вузлів пов'язаних дугами. Кожна дуга показує односпрямований зв'язок між двома вузлами. В організаційній діаграмі вузли – співробітники, а кожна дуга описує підпорядкування. У переліку матеріалів, вузли - модулі (зрештою, що показуються до індивідуальних частин), і дуги описують відношення "зроблено з".
Вершина дерева називається коренем. В організаційній діаграмі це найбільший начальник; у списку матеріалів, це зібрана деталь. Двійкове дерево - це дерево, в якому вузол може мати не більше двох нащадків; У загальному випадку, n-вимірне дерево - те, в якому вузол може мати не більше ніж n вузлів - нащадків.
Вузли дерева, які не мають піддерев, називаються листям. У переліку матеріалів це мінімальні частини, на які може бути розібрана деталь. Нащадки, або діти, батьківського вузла - всі вузли в піддереві, що має батьківський вузол коренем.
Дерева часто зображуються як діаграми. (Див. рисунок 1) Інший шлях уявлення дерев полягає в тому, щоб показувати їх як вкладені множини (див. рисунок 2); Це основа для використовуваного мною уявлення дерев у SQL як вкладених множин.
У SQL, будь-які відносини явно описуються даними. Типовий спосіб представлення дерев полягає в тому, щоб помістити матрицю суміжності в таблицю. Тобто. один стовпець - батьківський вузол, і інший стовпець у тому самому рядку - дочірній вузол (пара є дугою в графі). Наприклад, розглянемо організаційну діаграму компанії із шістьма співробітниками:
Ця модель має переваги та недоліки. ПЕРВИННИЙ КЛЮЧ - emp, але стовпець boss - функціонально залежить від нього, отже ми маємо проблеми з нормалізацією.REFERENCES не дасть вам можливість вказати начальником того, хто не є співробітником. Однак, що станеться, коли 'Jerry' змінює ім'я на 'Geraldo', щоб отримати телевізійне ток-шоу? Ви також повинні зробити каскадні зміни в рядках 'Bert' та 'Chuck'.
Інший недолік цієї моделі - важко вивести шлях. Щоб знайти ім'я боса для кожного службовця, використовується запит, що самооб'єднується, типу:
Але дещо тут немає. Цей запит надає Вам лише безпосередніх начальників персоналу. Бос Вашого боса також має владу по відношенню до Вас, і так далі вгору по дереву. Щоб вивести два рівні в дереві, Вам необхідно написати складніший запит самооб'єднання типу:
Щоб йти більш ніж на два рівні глибше у дереві, просто розширюють зразок:
На жаль, Ви поняття не маєте наскільки глибоко дерево, тому Ви повинні продовжувати розширювати цей запит, поки Ви не отримаєте в результаті порожню безліч.
Листя немає нащадків. У цій моделі, їх досить легко визначити: Це співробітники, які не є босом комусь або ще в компанії:
Біля кореня дерева boss - NULL:
Реальні проблеми виникають при спробі обчислити значення вгору та вниз по дереву. Як вправу, напишіть запит, що підсумовує платню кожного службовця та його/її підлеглих; результат:
Множина дерев.
Інший шлях уявлення дерев полягає в тому, щоб показати їх як вкладені множини. Це найбільш підходяща модель, т.к. SQL - мова, орієнтована на множини. Корінь дерева - безліч, що містить всі інші множини, і відносини предок-нащадок описуються приналежністю множини нащадків множині предка.
Є кілька способів перетворення організаційної діаграми у вкладенінабори. Один шлях полягає в тому, щоб уявити, що Ви переміщаєте підлеглі "овали" всередині їхніх батьків, які використовують лінії краю як мотузки. Корінь – найбільший овал і містить усі інші вузли. Листя - найбільш внутрішні овали, які нічого всередині не містять, і вкладення відповідає ієрархічним відносинам. Це - природне уявлення моделі "перелік матеріалів", тому що заключний блок зроблено фізично із вкладених складових, і розбирається на окремі частини.
Інший підхід полягає в тому, щоб уявити невеликий черв'як, що повзає по "вузлах і дугах" дерева. Черв'як починає згори, з кореня, і робить повну подорож навколо дерева.
Але тепер давайте уявимо сильніший хробак із лічильником, який починається з одиниці. Коли черв'як прибуває у вузол, він поміщає число в комірку з боку, яку відвідав і збільшує лічильник. Кожен вузол отримає два номери, тільки для правої сторони і для лівої сторони.
Це дає передбачувані результати, які можна використовувати для формування запитів. Таблиця Personnel має такий вигляд, з лівими та правими номерами у вигляді:
Корінь завжди має 1 у лівому стовпці та подвоєне число вузлів (2*n) у правому стовпці. Це просто зрозуміти: черв'як повинен відвідати кожен вузол двічі, один раз з лівого боку і один раз з правого боку, так що заключна кількість повинна бути подвоєна кількість вузлів у всьому дереві.
У моделі вкладених множин, різниця між лівими та правими значеннями листя - завжди 1. Уявіть черв'яка, що повертається навколо листа, поки він повзе по дереву. Тому, Ви можете знайти все листя наступним простим запитом:
Ви можете використовувати такий прийом, для прискорення запитів: побудуйте унікальний індекс по лівому стовпцю, потімперепишіть запит, щоб скористатися перевагою індексу:
Причина збільшення продуктивності в тому, що SQL може використовувати індекс по лівому стовпцю, коли він не використовується у виразі. Не використовуйте (left – right) = 1, тому що це дає скористатися перевагами індексу.
У моделі вкладених - множин, шляхи показуються як вкладені множини, які представлені номерами вкладених множин та предикатами BETWEEN. Наприклад, щоб визначити всіх босів певного співробітника, необхідно написати:
Чим більше height, тим далі по ієрархії бос від службовця. Модель вкладених множин використовує факт, що кожна множина, що містить інші, є більшою в розмірі (де розмір = (right - left)) ніж множини, що в ньому містяться. Очевидно, корінь завжди матиме найбільший розмір.
Рівень числа дуг між двома даними вузлами досить просто обчислити. Наприклад, щоб знайти рівні між заданим робітником та менеджером, Ви могли б використати:
(COUNT(*) - 1) використовується для того, щоб видалити подвійний індекс вузла безпосередньо як перебування на іншому рівні, тому що вузол - нульові рівні, видалені із себе.
Ви можете створити інші запити з цього шаблону. Наприклад, щоб знайти спільних босів двох службовців, об'єднують шляхи та знаходять вузли що мають (COUNT(*) > 1). Щоб знайти найближчих спільних предків двох вузлів, об'єднують шляхи, знаходять вузли, які мають (COUNT(*) > 1), і вибирають із найменшою глибиною.