Взаимная рекурсия

Проверить, являются ли два отношения или предиката взаимно рекурсивными, можно с помощью теории рафов. Построим граф зависимостей, узлы которого соответствуют отношениям (или предикатам в правилах Datalog). Проведем ориентированное ребро от отношения А к отношению Б, еслн определение В непосредственно зависит от определения А, т.е. при применении Datalog предикат Б входит в голову правила, в геле которого содержится А. В SQL А входит в определение В, обычно в предложение FROM или же в качестве терма о&ьединения, пересечения или разности.

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

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

1) WITH RECURSIVE Reaches(frm, to) AS

2) (SELECT frm, to FROM Flights)

3) UNION

4) (SELECT Rl.frm, R2.to

5) FROM Reaches AS R1, Reaches AS R2

6) WHERE R1.to-R2.frm)

7) SELECT * FROM Raaches;

Рис, 5.22. Запрос аэыно SQL3 о порог городов, сеязонных овиопинипми

Строка (1) лишь вводит определение Reaches, а реальное определение этого отношения находится иа строках (2) - (6). Оно состоит из объединения двух запросов, соответствующих двум правилам, с помощью которых Reaches было определено в примере 4.37. Строка (2) соответствует первому (базисному) правилу н означает, что второй и третий компоненты (frm и to) каждого кортежа отношения Flights являются кортежем отношения Reaches.

Строки (4) - (б) соответствуют второму (индуктивному) правилу в определении Reaches. Две подцели Reaches представлены в пункте FROM двумя псевдонимами отношения Reaches - R1 и R2. Первый компонент R1 соответствует а второй компонент R2 соответствует у в правиле (2). Переменная z представлена и вторым компонентом R1, и первым компонентом R2: на строке (6) эти компоненты приравниваются.

И наконец, строка (7) описывает отношение, которое порождается запросом в целом и является копией отношения Reaches. Эту строку можно заменить более сложным запросом, например:

7) SELECT to

FROM Reaches WHERE frm = DEN;

Этот запрос определяет все города, достижимые из Денвера. □

Заметим, что для SQL-запросов, подобных этому, можно применять описанное в разделе 4.4.2 итеративное вычисление фиксированной точки точно так же, как для правил Daialog. Поскольку рекурсия линейна, факты, содержащиеся в Reaches, можно искать в каком-то другом порядке, но в конечном счете будут найдены все пары городов {х,у), когда из х можно долететь до у.

Рассмотрим первый шаг вычислений на нашем примере данных. Поскольку Reaches изначально пусто, тотько первый терм объединения - Pairs на строке (4) - составляет основу пар городов согласно схеме 5.21. На втором шаге из Pairs и Reaches берется по одному транзитному участку и получаются пары транзитных участков, такие как (SF, CHI). На следующем этапе из Reaches получаются также двойные транзитные участки и больше нельзя добавить никаких пар. В общем случае на /-м шаге получаются все такие пары (х, у), что наикратчайший маршрут т X ку состоит из / ориентированных ребер. □

5.10.3 Применение представлений в выражениях с WITH

Представления, как и таблицы, можно применять в выражениях с WITH. Единственное синтаксическое различие - применение ключевого слова VIEW в определении отношения.

5.10.2 Линейная рекурсия

в примере 5.22 упоминался технический изъян, связанный с тем, что по стандарту SQL3 поддерживается только линейная рекурсия. Формально рекурсия линейна, если предложение FROM для любого определяемого отношения содержит не более одного вхождения отношения, которое взаимно рекурсивно с определяемым отношением. Чаше всего определяемое отношение само появляется в предложении FROM, но возможно также, что там появится и другое отношение, взаимно рекурсивное с определяемым.

Пример 5.53. Интересно, что программу, представленную на рис. 5.22, можно выразить простой заменой любого из применений Reaches в строке (5) на Flights. При этом рекурсия примет форму одного из правил правой или левой рекурсии, введенных в заключенном в рамку тексте раздела 4.4.3. Другой способ состоит в определении дополнительного отношения Pairs в предложении WITH Это отношение представляет проекцию Flights на компоненлы fnn и to, используется в обеих частях объединения.

Рис. 5.23 - новый вариант рис. 5.22. Здесь выбрано определение с правой рекурсией, но, поменяв местами Pairs и Reaches, можно выполнить и левую рекурсию.

1) WITH

2) Pairs AS SELECT frm. to FROM Flights.

3) RECURSIVE Reaches{frm, to) AS

4) Pairs

5) UNION

6) (SELECT Pairs.fnn, Reaches.to

7) FROM Pairs, Reaches

8) WHERE Pairs.to = Reaches.fnm)

9) SELECT * FROM Reaches;

Рис. 5.23. Запрос с линейной рекурсией о порах ropogoe, связонньк овиопиниями

Пример S.S4. Отношение Pairs на строке (2) рис. 5.23 можно определить как представление Для этого строка (2) записывается в следующем виде.

2) VIEW Pairs AS SELECT frm, to FROM Flights

В данном случае есть определенные причины для того, чтобы сделать Pairs именно зредсгавлением. Если Pairs - настоящее отношение, оно будет впервые построено полностью при выполнении предложения WITH, независимо от его применения в начале построения отношения Reaches на строке (4). Если же Pairs - представление, его использование в построении Reaches можно заменить применением компонентов кортежей из Flights. □

5.10.4 Стратифицированное отрицание

Запросы, когорые могут быть определениями рекурсивного отношения, не л[огут быгь .SQL-зипросами произвольной формы. Они должны удовлетворять различным ограничениям. Одно из наиболее важных таких ограничений заключается в том, что отрицание взаимно рекурсивных отношений должно быть стратифици-ронано в смысле, определенном н разделе 4.4.4. В разделе 5.10-5 будет показано, как принцип стратификации распространяется на другие конструкции SQL, но не на конструкции Daialo!; или реляционной алгебры.

Пример 5.55. Вернемся к примеру 4.39, в котором мы искали такие пары Г01ЮЯ0В (х,у), чтобы из X в можно бьцю nepejiercTb рейсом UA но не АА. Для выражения перелета через неопределенное число транзитных участков необходима рекурсия, а отрицание принимает стратифицированную форму: после применения рекурсии для вычисления отношений UAreaches и AAreaches из примера 4.39 вычисляется ич разность.

Такой же метод применим и для записи запроса в SQL3, но тогда нелинейную рекурсию нужно заменить правой или левой линейной рекурсией, как показано в примере 5 53. Для иллюстрации другого способа действий в данном примере рекурсивно определим единственное отношение Reaches(airtine, frm, to), кортежи которого (а, у; /) означают, что из города / можно перелететь в город Л возможно, через несколько транзитных участков, но только рейсами авиалинии а. Мы используем также отношение Triples(airiine, frm, to), являющееся проекцией Flights на Т1)И рслеваншых комгюнента. Составленный таким способом запрос показан на рис. 5.24.

1) WITH

2) Triples AS SELECT airline, frm, to FROM Flights,

3) RECURSIVE Reaches(airline. frm, to) AS

4) Triples

5) UNION

6) (SELECT Triples.alriine. Tripies.frm, Reaches.to

7) FROM Triples, Reaches

8) WHERE Triples.to = Reaches.frm AND

9) Triples.airline = Reaches.airline )

10) (SELECT frm, to FROM Reaches WHERE airline = UA)

11) EXCEPT

12) (SELECT frm, to FROM Reaches WHERE airline =AA);

PiK. 5.24. Стротифицирогаанный зспрос о ropogoi. достижимых с помощью одной из двух оеиолинии