Навігація по суміжній списку

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

Використання стандартної інструкції select

Генерація списку результатів за допомогою всього однієї інструкції SELECT проблематична, оскільки кількість поколінь динамічно, а запит вибірки вимагає відомого набору таблиць Інструкція SELECT може впоратися з відомою кількістю поколінь, але коли воно не відомо, заздалегідь створена інструкція не впорається із завданням Як приклад наведемо запит, який видобуває дані про дідуся і двох наступних поколіннях:

USE Family SELECT

PersonFirstName + 1 + IsNull(PersonSrJr,1) as Grandfather,

GenlFirstName + 1 + IsNull(GenlSrJr,1) as Genl,

Gen2FirstName + 1 + IsNull(Gen2SrJr,’1) as Gen2 FROM Person

LEFT JOIN Person Genl

ON PersonPersonID = GenlFatherlD LEFT JOIN Person Gen2

ON GenlPersonID = Gen2FatherlD WHERE PersonPersonID = 2

Результат буде наступним:

Grandfather Genl    Gen2

James 1                        James 2          Melanie

James 1                        James 2          Corwin

James 1                        James 2          Dara

James 1                        James 2          James 3

Як альтернатива аналогічний запит може витягувати дані про всіх батьків і всіх їхніх дітях, обєднуючи два примірники таблиці Person Однак цей метод не дозволяє створити працездатний дерево

Використання рекурсивного курсора

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

Додаткова Детальну інформацію про програмування курсорів (і, що найголовніше, інформація про те, як їх уникати) ви знайдете в главі 20

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

Для кожної людини викликається рекурсивна процедура, щоб виявити наявність у нього дітей

Рекурсивна природа цієї процедури змушує її послідовно спускатися вниз по дереву, знаходячи першої дитини (РК: 5, 8, 15), а потім його братів і сестер (16, 29) Результати цієї процедури ви побачите в наступному прикладі Потім рекурсивна процедура починає шукати братів дитини 8 і знаходить номер 10. Після цього перевіряється наявність у 10 дітей, і першим знайденим дитиною буде 19. Потім процедура викликається для 19, в результаті чого повертаються 21 і 22. І нарешті процедура викликається для 21 і 22, але дітей у них не знаходить

За замовчуванням область видимості курсору поширюється на всі викликаються процедури, проте завдання побудови ієрархічного дерева вимагає, щоб кожна процедура створювала власний курсор Установка параметра cursor в значення local обмежує область видимості курсора і дозволяє рекурсію Цей параметр може бути заданий при оголошенні курсору або в параметрах бази даних У наступному прикладі продемонстровані обидва цих методу:

ALTER DATABASE Family SET CURSOR_DEFAULT LOCAL

SELECT DATABASEPROPERTYEX(Family7, IsLocalCursorsDefault7)

Результат буде наступним:

l

Наступний пакет створює процедуру ExemineChild, що містить курсор, який перевіряє наявність дітей для поточного рядка таблиці Person Якщо діти будуть виявлені, то ця процедура, що зберігається викликає себе рекурсивно:

CREATE PROCEDURE ExamineChild (@ParentID INT)

AS

SET Nocount On DECLARE @ChildID INT,

@Childname VARCHAR(25)

DECLARE сChild CURSOR LOCAL FAST_FORWARD FOR SELECT PersonID,

Firstname + 1 + LastName + 1 + IsNull(SrJr,1) as PersonName FROM Person

WHERE PersonFatherID = @ParentID OR PersonMotherID = @ParentID ORDER BY PersonDateOfBirth OPEN cChild

FETCH cChild INTO @ChildID, @ChildName — prime the cursor WHILE @@Fetch_Status = 0 BEGIN PRINT

SPACE( tLevel * 2) + +

+ Cast(@ChildID as VARCHAR(4))

+ 1 + @ ChildName – Рекурсивно шукаємо онуків

EXEC ExamineChild @ChildID FETCH cChild INTO @ChildID, @ChildName END

CLOSE cChild DEALLOCATE cChild

Викликається рекурсивна процедура, що зберігається ExemineChild, і їй передається ідентифікатор людини, що знаходиться на першому рівні родовідного дерева, – Джеймса Хал-Лоуе (ідентифікатор дорівнює двом)

EXEС ExamineChild 2

Буде отримано наступний результат:

+ 5 James Halloway 2 + 8 Melanie Campbell + 15 Shannon Ramsey + 16 Jennifer Ramsey + 2 9 Adam Campbell + 10 James Halloway 3 + 19 James Halloway 4 + 22 Chris Halloway + 21 James Halloway 5 + 18 Abbie Halloway + 17 Allie Halloway + 9 Dara Halloway

+ 23 Joshua Halloway + 24 Laura Halloway + 7 Corwin Halloway + 14 Logan Halloway

Використання курсора є адекватним вирішенням завдання побудови ієрархічного дерева, коли набір даних невеликий, проте для великих масивів інформації цей метод не підходить, і на те є дві причини По-перше, SQL Server обмежує вкладеність збережених процедур 32 рівнями, так що рекурсії більшої глибини (за вирахуванням вкладеності коду, що викликав рекурсивную процедуру) не будуть виконані Друга причина повязана з питанням продуктивності (це питання завжди постає при використанні курсорів) Так як для кожного вузла потрібно ітерація, продуктивність падає в буквальному сенсі цього слова Семиуровневая ієрархія з пятьма мільйонами вузлів потребують пять мільйонів ітерацій Пакетне рішення зможе виконати ту ж задачу за сім проходів

Використання пакетних рішень

Перше з трьох пакетних рішень починає з однієї людини, приймаючи в розрахунок тимчасову таблицю # FamilyTree Потім пакет покроково проходить по всім поколінням в тимчасовій таблиці, використовуючи обєднання з кількома умовами

Для кожної особи в тимчасовій таблиці # FamilyTree стовпець FamilyLine містить дані FamilyLine предків, обєднані з ідентифікатором батьків (PersonID) Стовпець FamilyLine містить дані, необхідні для сортування дерева

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

CREATE TABLE #FamilyTree (

PersonID INT,

Generation INT,

FamilyLine VarChar(25) Default ‘

)

DECLARE

©Generation INT,

@FirstPerson INT SET ©Generation = 1 SET @FirstPerson = 2

– Готуємо тимчасову таблицю з головною персоною на чолі INSERT # FamilyTree (PersonID, Generation, FamilyLine)

SELECT @FirstPerson, ©Generation, @FirstPerson WHILE @@RowCount &gt 0 BEGIN

SET ©Generation = ©Generation + 1

INSERT #FamilyTree (PersonID, Generation, FamilyLine)

SELECT PersonPersonID,

©Generation,

#FamilyTreeFamilyLine + 1 1 + Str(PersonPersonID,5)

FROM Person

JOIN #FamilyTree

ON #FamilyTreeGeneration = ©Generation – 1 AND

(PersonMotherID = #FamilyTreePersonID OR

PersonFatherID = #FamilyTreePersonID)

END

Коли тимчасова таблиця # FamilyTree заповнена, наступний запит перевіряє оперативні дані

Результат буде наступним (скорочено):

PersonID Generation FamilyLine

2&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp 12

5                                                           2 2 5

7&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp 3 2                   5 7

14                                                         4 2  5 7 14

22              5                                          2 5 10 19 22

Аналогічно попередньому рішенню з курсором, наступний запит використовує ту ж функцію space () для форматування результатів, після чого результати обєднуються з таблицею Person для відображення імен:

SELECT SPACE(Generation * 2) + + 1

+ Cast(#FamilyTreePersonID as VARCHAR(4)) +

+ FirstName + 1 + LastName + IsNull(SrJr,11) AS FamilyTree FROM #FamilyTree JOIN Person

ON #FamilyTreePersonID = PersonPersonID ORDER BY FamilyLine

Буде отримано наступний результат:

FamilyTree

+ 2 James Halloway 1 + 5 James Halloway 2 + 7 Corwin Halloway + 14 Logan Halloway + 8 Melanie Campbell + 15 Shannon Ramsey + 16 Jennifer Ramsey + 2 9 Adam Campbell + 9 Dara Halloway

+ 23 Joshua Halloway + 24 Laura Halloway + 10 James Halloway 3 + 17 Allie Halloway + 18 Abbie Halloway + 19 James Halloway 4 + 21 James Halloway 5 + 22 Chris Halloway

Використання функцій користувача

Незважаючи на те що пакетні рішення демонструють саму методику, впровадження їх у користувача функції значно підвищує їх здатність використання в різних програмах

Додаткова Цей метод змушує нас зазирнути трохи вперед в розширені засоби інформація програмування SQL Server для вирішення ієрархічних завдань Детальну інформацію про моїх улюблених засобах SQL Server ви знайдете в главі 22

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

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

CREATE FUNCTION dboFamilyTree PersonID CHAR(25))

TURNS @Tree TABLE (PersonID INT, LastName VARCHAR(25), FirstName

VARCHAR(25), Lv INT)

AS

BEGIN

DECLARE @LC INT SET @LC = 1

– Вставка початкового рівня INSERT @ Tree

SELECT PersonID, LastName, FirstName, @LC FROM dboPerson with (NoLock)

WHERE PersonID = @ PersonID – Цикл по подуровням WHILE @ @ RowCount> 0 BEGIN

SET @ LC = @ LC + 1 – Вставка всіх поколінь INSERT @ Tree

SELECT TreePersonID, TreeLastName,

TreeFirstName, @LC FROM dboPerson FamilyNode with (NoLock)

JOIN dboPerson Tree with (NoLock)

ON FamilyNodePersonID = TreeMotherlD

OR FamilyNodePersonID = TreeFatherlD JOIN @Tree CC

ON CCPersonID = FamilyNodePersonID WHERE CCLv = @LC – 1

END

RETURN

END

Якщо подивитися на текст функції, то можна побачити, що в якості аргументу вона приймає ідентифікатор особи PersonID Ця персона буде служити коренем для початку пошуку в ієрархії Кінцевим результатом функції є список всіх нащадків в ієрархічному порядку, починаючи з кореня дерева Всі дані зберігаються в табличній змінної @ Тгее, яка передається назад в запит, що викликав функцію Цей запит може використовувати результат як джерело даних в реченні FROM

У першу чергу ми шукаємо у функції ідентифікатор класу ClassIDn додаємо його в табличну змінну @ Classes Після цього функція проходить по всіх рівнях ієрархії, поки не досягне рівня, в якому нащадків вже немає Ця пакетна користувацька функція має високу продуктивність і масштабованість

Select * From dboFamilyTree(10)

Результат буде наступний

PersonID LastName FirstName Lv

10&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp Halloway         James              1

18&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp Halloway        Abbie             2 17          Halloway          Allie     2

19&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp Halloway        James              2 22         Halloway          Chris    3 21      Halloway          James   3

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

Використання рекурсивних загальних табличних виразів

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

Додаткова Про основи створення запитів, що використовують загальні табличні вирази, інформацій см в главі 10

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

WITH FamilyTree( LastName, FirstName, PersonID, lv)

AS (

– Якір

SELECT LastName, FirstName, PersonID, 1 FROM Person A WHERE PersonID = 10 – Рекурсивний виклик UNION ALL

SELECT NodeLastName, NodeFirstName, NodePersonID, lv + 1 FROM Person Node JOIN FamilyTree ft

ON NodeMotherlD = ftPersonID

OR NodeFatherlD = ftPersonID

)

SELECT PersonID, LastName, FirstName, lv FROM FamilyTree

У даному випадку результат рекурсивного загального табличного виразу буде ідентичний результату наведеної раніше користувача функції

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

Резюме

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

У наступному розділі ми продовжимо тему вибірки даних, вивчивши засоби повнотекстового пошуку

■&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp

Джерело: Нільсен, Пол Microsoft SQL Server 2005 Біблія користувача : Пер з англ – М: ООО ІД Вільямс , 2008 – 1232 с : Ил – Парал тит англ

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


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

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

Ваш отзыв

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

*

*