ТРАНЗИТИВНОЕ ЗАМЫКАНИЕ

Предположим, нам нужно узнать, является ли один человек предком другого. Получить ответ на этот вопрос может помочь структура данных под названием «транзитивное замыкание». Например, Иван является отцом Петра, а Петр является отцом Федора. Тогда Иван является предком Федора в силу транзитивности отношения «быть предком». Транзитивное замыкание — это простая в реализации структура данных, которая конструируется в данном случае из фамильных деревьев и помогает быстро ответить на подобные вопросы. Более формально, транзитивное замыкание — это расширение или надмножество транзитивного бинарного отношения (т. е. такого отношения, что если (a,b) и (b,c) находятся в этом отношении, то (a,c) также находится в этом отношении). По сути, эта структура данных позволяет отвечать на вопросы «достижимости», такие как «существует ли путь из точки А в точку Б?». Отправной точкой в процессе (в данном случае это код T-SQL), создающем транзитивное замыкание, является ориентированный граф (пары узлов со стрелками, которые могут быть пройдены только в одном направлении).

Во многих базах данных хранятся такие графы — например, материально-технические накладные со списком пар «узел — деталь», Web-ссылки от страницы источника к целевой странице, должностная иерархия. Выходными данными являются пары узлов, для которых существует путь. Например, транзитивное замыкание входных данных вышеупомянутой накладной — это совокупность всех пар «узел — деталь», независимо от того, непосредственно они содержатся друг в друге — как булочка с джемом содержит джем, и при этом на выходе получается (булочка, джем), или не непосредственно — булочка содержит джем, джем содержит сахар, поэтому булочка содержит сахар; на выходе при этом получается (булочка, джем), (джем, сахар), (булочка, сахар).

Транзитивное замыкание графа Web-ссылок — это совокупность всех пар «начальная страница» — «целевая страница», опять-таки с прямыми или непрямыми ссылками между ними. Как только транзитивное замыкание входного графа составлено, мы легко можем определить, существует ли конкретная пара, и таким образом ответить на вопросы типа «содержит ли узел A деталь C?» и «можно ли по ссылкам попасть со страницы X на страницу Y?». Найти формальное определение транзитивного замыкания и соответствующих терминов и алгоритмов можно на Web-сайте национального института стандартов и технологии США (NIST) (http://www.nist.gov/dads/HTML/transitiveClosure.html).

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

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

Одной из смежных проблем является нахождение кратчайшего пути между двумя узлами в графе. Например, если в базе данных SQL Server хранится информация о Web-ссылках, то, возможно, приложению приходится отвечать на частые запросы о минимуме Web-ссылок, которые могут потребоваться при переходе с одной страницы на другую. Рекомендуем алгоритмы транзитивного замыкания Роберта Флойда и Стефена Вошала, часто применяемые в других вычислительных средах. Подробности можно найти на сайте http://www.nist.gov/dads, набрав в строке поиска Floyd или Warshall. Однако, несмотря на то что эти алгоритмы могут предоставить наиболее удобные программные решения для упомянутых проблем, в реляционных базах данных они не работают, поскольку не могут быть выражены в запросах SQL.

С появлением в SQL Server 2005 рекурсий для общих табличных выражений (CTE) мы можем создавать чистые T-SQL-решения проблем транзитивного замыкания и кратчайшего пути. Рассмотрим несколько примеров. Сначала представим довольно простое решение для ациклического графа, в котором ни один узел не имеет пути к самому себе. Затем исследуем более сложное решение для циклических графов, в которых уже может существовать путь узла к самому себе. Мы исходим из предположения, что читатели знакомы с рекурсивными CTE.

Ациклические графы

Рисунок 1. Ациклический граф

В наших примерах задействованы сценарии с Web-ссылками. Прежде чем перейти к дальнейшему изложению, следует выполнить код листинга 1, чтобы создать таблицу Links и заполнить ее данными примера. Таблица Links содержит строки для каждой Web-ссылки, в том числе два атрибута: ID страницы-источника (src_pid) и ID целевой страницы (tgt_pid). Данным соответствует ациклический граф, а это означает, что, следуя по ссылкам, никак нельзя попасть со страницы на ту же самую страницу. На рис. 1 изображен ациклический ориентированный граф, соответствующий таблице Links.

Первый пример, который мы рассмотрим, — запрос, создающий транзитивное замыкание таблицы Links. Результат показан в табл. 1, которая содержит все пары ID исходной-целевой страниц, имеющие путь от первой ко второй. В листинге 2 показано решение по этому запросу.

Во фрагменте под меткой A «якорь» CTE с именем TC возвращает из таблицы Links все пары Web-страниц (исходная, целевая), в которых на целевую страницу можно перейти непосредственно с исходной (по одной ссылке). Рекурсивный член во фрагменте B объединяет результаты предыдущего шага (имеющего в TC псевдоним P — Parent, родительский) с таблицей Links (имеющей псевдоним C — Child, дочерний), чтобы возвратить целевые страницы, на которые пользователь может перейти не непосредственно (следуя более чем по одной ссылке). Условие JOIN ищет в таблице Links строки, в которых ID исходной страницы равны ID целевой страницы предыдущего шага. В списке SELECT возвращаются ID исходных страниц шага B и ID целевых страниц шага C.

Первое инициирование работы рекурсивного выражения возвращает целевые страницы, которые отстоят на две ссылки от исходной. Второе инициирование возвращает целевые страницы, которые отстоят на три ссылки от исходной и т. д., пока рекурсивное выражение не исчерпает все связанные страницы. После этого внешний запрос делает выборку чистого списка пар исходная — целевая страница. Мы применили DISTINCT, потому что без него результат имел бы дублирующие строки, когда от исходной страницы к целевой ведет несколько путей. Если удалить DISTINCT, в результирующем наборе мы увидим две дополнительные строки. Обе пары (1, 7) и (1, 8) дублированы, так как во входном графе существуют пути 1-4-7 и непосредственно 1-7 для пары (1, 7) и пути 1-4-7-8 и 1-7-8 для пары (1, 8).

С небольшими добавлениями в CTE, как показано в листинге 3, мы также можем вычислить минимальное расстояние (кратчайший путь) между узлами этого ациклического ориентированного графа. Другими словами, минимальное число ссылок, по которым надо пройти, чтобы попасть с одной страницы на другую. В анкерном члене добавляем константу 1, которая представляет собой расстояние, поскольку якорный член возвращает непосредственную ссылку. Рекурсивный член вычисляет расстояние как родительское расстояние плюс один. Внешний запрос группирует результаты по ID исходной и целевой страниц и возвращает минимальное расстояние для каждой пары. Исполнение кода листинга 3 дает желаемый результат, который показан в табл. 2.

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

Циклический граф

С циклическими графами, в которых может существовать путь от узла к самому себе, обращаться намного сложнее, главным образом потому, что можно зациклиться в бесконечном обходе путей. Пример циклического графа дает Web-сайт, где можно оказаться на той же странице, с которой был начат просмотр, после переходов по нескольким ссылкам. Хитрость в обращении с циклическими графами состоит в выявлении и учете циклов, так чтобы код знал, когда прекратить обход.

Рисунок 2. Циклический ориентированный граф

Выполним код листинга 4, чтобы заново заполнить таблицу Links графом, содержащим циклы. На рис. 2 показаны связи между Web-страницами во вновь заполненной таблице Links. Теперь таблица Links соответствует циклическому ориентированному графу.

В листинге 5 показан код, который возвращает все возможные пути и их длины в циклическом ориентированном графе. Далее мы продемонстрируем две модификации запроса, который составляет транзитивное замыкание и вычисляет кратчайшие пути между любыми двумя узлами циклического ориентированного графа. Запрос в листинге 5 обходит пути, начиная с каждой страницы как якорной, поскольку каждая страница может быть началом навигации. В процессе навигации запрос вычисляет расстояния от якорной страницы и конструирует из ID страниц пронумерованный путь, ведущий от исходной страницы к целевой. Рекурсивное выражение отфильтровывает узлы, для которых оно обнаружило цикл; распознавание цикла происходит в том случае, если ID целевой страницы уже появлялся в пронумерованном пути исходной страницы. Наше CTE распознает цикл, используя предикат LIKE в фильтре рекурсивного члена.