Главная » Microsoft SQL Server, Базы данных » Навигация по смежному списку

0

Хранение данных в любой из вариаций смежного списка не вызывает проблем — обычные вставка, обновление и удаление работают отлично. Вся хитрость состоит в извлечении данных и навигации по иерархии. В следующих разделах будут описаны некоторые решения этих задач — от тривиальных до крайне сложных. Надеюсь, что хотя бы одно из них вам понравится.

Использование стандартной инструкции select

Генерация списка результатов с помощью всего одной инструкции SELECT проблематична, поскольку количество поколений динамично, а запрос выборки требует известного набора таблиц. Инструкция SELECT может справиться с известным количеством поколений, но когда оно не известно, заранее созданная инструкция не справится с задачей. В качестве примера приведем запрос, извлекающий данные о дедушке и двух последующих поколениях:

USE Family SELECT

Person.FirstName + ‘ 1 + IsNull(Person.SrJr,’1) as Grandfather,

Genl.FirstName + ‘ 1 + IsNull(Genl.SrJr,1‘) as Genl,

Gen2.FirstName + 1 ‘ + IsNull(Gen2.SrJr,’1) as Gen2 FROM Person

LEFT JOIN Person Genl

ON Person.PersonID = Genl.FatherlD LEFT JOIN Person Gen2

ON Genl.PersonID = Gen2.FatherlD WHERE Person.PersonID = 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 Person.FatherID = @ParentID OR Person.MotherID = @ParentID ORDER BY Person.DateOfBirth 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 > 0 BEGIN

SET ©Generation = ©Generation + 1

INSERT #FamilyTree (PersonID, Generation, FamilyLine)

SELECT Person.PersonID,

©Generation,

#FamilyTree.FamilyLine + 1 1 + Str(Person.PersonID,5)

FROM Person

JOIN #FamilyTree

ON #FamilyTree.Generation = ©Generation – 1 AND

(Person.MotherID = #FamilyTree.PersonID OR

Person.FatherID = #FamilyTree.PersonID)

END

Когда временная таблица #FamilyTree заполнена, следующий запрос проверяет оперативные данные.

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

PersonID Generation FamilyLine

2                                          12

5                                                           2 2 5

7                                                                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(#FamilyTree.PersonID as VARCHAR(4)) + ‘ ‘

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

ON #FamilyTree.PersonID = Person.PersonID 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 dbo.FamilyTree 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 dbo.Person with (NoLock)

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

SET @LC = @LC + 1 — Вставка всех поколений INSERT @Tree

SELECT Tree.PersonID, Tree.LastName,

Tree.FirstName, @LC FROM dbo.Person FamilyNode with (NoLock)

JOIN dbo.Person Tree with (NoLock)

ON FamilyNode.PersonID = Tree.MotherlD

OR FamilyNode.PersonID = Tree.FatherlD JOIN @Tree CC

ON CC.PersonID = FamilyNode.PersonID WHERE CC.Lv = @LC – 1

END

RETURN

END

Если посмотреть на текст функции, то можно увидеть, что в качестве аргумента она принимает идентификатор лица PersonID. Эта персона будет служить корнем для начала поиска в иерархии. Конечным результатом функции является список всех потомков в иерархическом порядке, начиная с корня дерева. Все данные хранятся в табличной переменной @Тгее, которая передается назад в запрос, вызвавший функцию. Этот запрос может использовать результат в качестве источника данных в предложении FROM.

В первую очередь мы ищем в функции идентификатор класса ClassIDn добавляем его в табличную переменную @Classes. После этого функция проходит по всем уровням иерархии, пока не достигнет уровня, в котором потомков уже нет. Эта пакетная пользовательская функция обладает высокой производительностью и масштабируемостью.

Select * From dbo.FamilyTree(10);

Результат будет следующий.

PersonID LastName FirstName Lv

10       Halloway         James              1

18        Halloway        Abbie             2 17          Halloway          Allie     2

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

Этот метод я широко использовал в своих объектно-реляционных экспериментах. Предлагаю вам загрузить последнюю версию этих экспериментов с сайта www.SQLServerBible.com, опробовать их и убедиться в том, как иерархические пользовательские функции решают задачи наследования классов.

Использование рекурсивных общих табличных выражений

Последним решением задачи навигации в иерархии смежных пар являются рекурсивные общие табличные выражения (СТЕ). Следуя той же базовой логике, что и в тексте программы пользовательской функции, СТЕ изначально устанавливает якорь, который затем итеративно объединяется с идентифицируемыми строками до тех пор, пока ни одной новой строки не будет найдено.

Дополнительная Об основах создания запросов, использующих общие табличные выражения, информаций см. в главе 10.

Основным преимуществом рекурсивных СТЕ является то, что они не используют процедурный код. Вместо этого они используют совершенно новый синтаксис СТЕ. Рекурсивные СТЕ используют два запроса, связанных вместе. Первый запрос служит для выбора якоря. Второй запрос объединяет его с общим табличным выражением для выбора следующего поколения в иерархии. SQL Server продолжает выполнять второй запрос до тех пор, пока не будут обнаружены новые строки. Здесь используется та же логика, что и в пользовательских функциях:

WITH FamilyTree( LastName, FirstName, PersonID, lv)

AS (

– Якорь

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

SELECT Node.LastName, Node.FirstName, Node.PersonID, lv + 1 FROM Person Node JOIN FamilyTree ft

ON Node.MotherlD = ft.PersonID

OR Node.FatherlD = ft.PersonID

)

SELECT PersonID, LastName, FirstName, lv FROM FamilyTree;

В данном случае результат рекурсивного общего табличного выражения будет идентичен результату приведенной ранее пользовательской функции.

Из всех приведенных в настоящей главе решений задачи навигации в иерархических структурах самым быстрым, пожалуй, является пользовательский запрос. Он выполняется вдвое быстрее, чем общее табличное выражение, и в зависимости от конкретного набора данных на порядок быстрее, чем курсор.

Резюме

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

В следующей главе мы продолжим тему выборки данных, изучив средства полнотекстового поиска.

?              

Источник: Нильсен, Пол. Microsoft SQL Server 2005. Библия пользователя. : Пер. с англ. — М. : ООО “И.Д. Вильямс”, 2008. — 1232 с. : ил. — Парал. тит. англ.

По теме:

  • Комментарии