10Технически нелинейная ргкурсия даже без отрицания недопустима в SQL3, хотя о док\ментации по этому языку предполагается, что такая рекурсия появится D S0L4. Однако здесь мы рассма рнвдем бессмысленные или парадоксальные форяы рекурсии, щ, котрос [ляютгью сцщга SC

Определение отношения Reaches на строках (3) - (9) - это объединение двух термов. Базовый терм - это отношение Trip es на строке (4), а индуктивный терм - запрос на строках (б) (9), порождающий объединение отношений Trip es и Reaches В результате объединения этих термов в Reaches попадают все такие кортежи (й,/ /), что из города} можно перелететь в город /; может бьггь, даже через несколько транзитных участков, но только рейсами авиалинии а.

Основной запрос сформулирован на строках (10) - (12). Строка (10) лает пары городов, достижимых с помощью UA, а строка (12) -пары городов, достижимых с помощью АА. Общий результат запроса ~ разность между двумя этими отношениями. Q

Пример 5.56. На рис, 5.24 отрицание, выраженное словом EXCEPT иа строке (11), явно стратифицировано, так как применяется только после завершения рекурсии на строках (3) - (9). Нестратифииированное применение отрицания из примера 4.40 тоже можно перевести в применение EXCEPT в определении рекурсивного отношения. Результат такого прямого перевода в запрос языка SQL3 показан на рис. 5.25. Этот запрос касается значения Я, но можно запросить и значение Q или некоторой функции от Р и Q.

1) WITH

2) RECURSIVE Р(х) AS

3) (SELECT * FROM R)

4) EXCEPT

5) (SELECT FROM Q)

6) RECURSIVE Q(x) AS

7) (SELECT * FROM R)

8) EXCEPT

9) (SELECT * FROM P)

10) SELECT * FROM P; Рис. 5.25. Hegonyovwibiii a S0L3 нестротифицироаонный запрос

Два применения EXCEPT на строках (4) и (8) рис. 5.25 недопустимы в SQL3, так как в каждом случае второй аргумент -это отношение, которое взаимно рекурсивно с определяемым отношением. Оба эти применения отрицания не стратифицированы и потому запрещены. Фактически здесь не может быть верного решения вопроса с помощью SQL3, так как показанная на рис, 5.25 рекурсия на саном деле не определяет значений отношений Р v, Q. □

5.10.5 Выражения рекурсивного SQL3, вызывающие проблемы

В примере 5 56 было показано, что применение EXCEPT в рекурсивном определении нарушает требование SQL3 о стратификации огрицания. Существуют и другие неприемлемые формы запросов, в которых EXCEPT не применяется. Например,

11 При немонотонной рекурсии порядок оценки отношений в пункте with влияет на конечный результат, а при монотонной рекурсии он не зависит от поряяка в этом и 6 следуюшем примерах предполагается, что на каждом этапе Р п Q оцениваются параллельно : старое значение каждого отношения используется для вычисления другого значения на каждом этапе.

отрицание отношения можно выразить с помошью оператора NOT IN Тогда строки (2) - (5) рис. 5.25 можно записать в следующей форме:

RECURSIVE Р(х) AS

SELECT x FROM R WHERE x NOT IN Q

При гаком преобразовании рекурсия остается нестратифицированноЯ и, следовательно, недопустимой. Но если просто применеть NOT и пункте WHERE, внеся в него, например, выражение NOT х = у (эквива-пентное х<>у), автоматического нарушения условия о стратификации отрицания не произойдет. Существует ли общее правило отбора видов SQL-запросов, которые можно применять для определения рекурсивных отношений в SQL3?

Для того чтобы бьггь рекурсией, допустимой в SQL3, определение рекурсивного отношения R должно содержать применение взаимно рекурсивного отношения S (S может совпадать с Л), если такое применение является монотонным. Применение S монотонно, если добавление произвольного кортежа к S способно привести к добавлению одного или нескольких кортежей к R или оставить R неизменным, но никогда не приводит к удалению кортежа из Л.

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

Пример 5.57. Рис. 5.25 - это реализация правил Datalog из примера 4.40, иллюстрирующая нестратифицированное отрицание. Эти правила допускают две различные фиксированные точки. Определения Р Q немонотонны. В определении Р на строках (2) - (5) Р зависит от Q, с которым оно взаимно рекурсивно, но добаааение кортежа к Q может привести к удалению кортежа из Р. Чтобы показать это, предположим, гго Л состоит из кортежей (а) н (Ь), а О - из кортежей (о) и (с). Тогда />={(*)}. Однако при добавлении (Ь) к Q отношение Р становится пустым. Добавление кортежа привело к удалению кортежа, значит, данная конструкция немонотонна и некорректна.

Утрата монотонности ведет к возникновению колебаний при оценке отношений Р и Q путем вычисления минимальной фиксированной точки. Пусть, например, R имеет кортежи {(о), (Ь)}. Отношения Рн Q первоначально пусты. Значит, на первом шаге строки (3) - (5) рис. 5.25 дают значение Л равное {{а), {Ь)). Согласно строкам (7) - (9), Q имеет точно такое же значение, поскольку- на строке (9) используется старое пустое значение Р.

Теперь R, Р к Q имеют значение {{а), (6)}. Поэтому на втором шаге в строках под номерами (3) - (5) и (7) ~ (9) будут вычислены пустые значения Р ч Q соответственно, а это значит, что на третьем шаге оба они снова получат значение {(д). (*)}. Этот процесс длится бесконечно, и на каждом его четном шаге отношения пусты, а на каждом нечетном имеют значение {{а), (i)}. Следовательно, из определений рнс. 5.25 невозмож)ю получить ясные значения отношений Р а Q. П

Пример 5.58. Агрегация тоже иногда приводит к немонотонности, хотя связь меяшу ними может быть неочевидной. Предположим, унарные (одноатрибутные) отношения Р к Q определяются следующими ycлoвtяи:

1. / есть объединение Q с EDB-отношением R

2. Q имеет один кортеж, являющийся суммой членов Р

Эти условия можно выразить с помощью оператора WiTH, но при этом будет нарушено требование монотонности SQL3. Запрос на рис. 5.26 относится к значению Р.

1) 2) 3) 4) 5)

6) 7)

WITH

RECURSIVE Р{х) AS

(SELECT * FROM R) UNION

(SELECT * FROM Q)

RECURSIVE Q(x) AS

SELECT SUM(x) FROM P

SELECT * FROM P;

Рис 5.26. Недопустоллый в S013 нестротифицирсшонный вопрос с офегацией

Пусть R состоит из кортежей (12) и (34), а /> и Q пусты, как и должно быть в начале вычисления фиксированной точки. На рис. 5.27 показан результат вычисления значений на первых шести шагах.

Рис. 5.27. Итеротиеное вычисление фиксироеонной точки для немонотонной огрвгоции

Напомним, что значения всех отношений на каждом шаге вычисляются из значений, полученных на предыдущем шаге. Значит, на первом шаге значения Р и R совпадают, а Q пусто, поскольку старое пустое значение Р используется на строке (7),

На втором шаге новым значением Р становится объединение строк (3) - (5), т.е. R = {(12), (34)}. Старое значение /было таким же, как и новое, значит, на этом шаге Q= {(4б)} - это сумма 12 и 34.

На третьем шаге из строк (2) (5) получается /*= {(12), (34), (46)). На основе старого значения Р, {(12), (34)}, на строках (6) - (7) значение Q снова определяется как {(46)}.

На четвертом шаге Р имеет прежнее значение {(12), (34), (46)}, а Q получает значение {(92)}, поскольку 12 + 34 + 46 92. Заметим, что из Q исчез кортеж (46), хотя и появился кортеж (92). Иными словами, добавление к Р кортежа (46) привело к удалению (случайно того же самого) кортежа из Q. Такая немонотонность, запрещенная в рекурсивных определениях SQL3, означает, что запрос рис. 5.26 не Допустим. В общем случае на 2/-м шаге Р будет состоять из кортежей (12), (34) и (46/ - 46), й Q только из кортежа (46/). □