Преобразования методом магических множеств для нерекурсивных программ
Хорошо известно, что у преобразований методом магических множеств имеется нежелательное свойство слияния сильно связанных компонентов. В результате нерекурсивная программа может стать рекурсивной.
ПРИМЕР 4.2 (Рекурсия из-за магии): В программе P
(Pl): SELECT A, B FROM r(A,C), q(C,B) WHERE A = 10
(P2): r(A,C) AS (SELECT A, C FROM q(A, D), t(D, C))
(P3): q(E,F) AS (SELECT E, F FROM s(E, F))
q используется дважды, в (Pl) и (P2), в обоих местах с украшением bf. Для qbf имеются связывания из rbf (Pl) и из m_rbf (P2). Поэтому магическим множеством является объединение. Магический запрос выглядит следующим образом:
(Ml): SELECT A, B FROM rbf(A,C), qbf(C,B) WHERE A = 10
(M2): rbf(A,C) AS (SELECT A, C
FROM m_rbf(A), qbf(A,D), t(D,C))
(M3): qbf(E,F) AS (SELECT E, F FROM m_qbf(E), s(E,F))
(M4): m_rbf (l0)
(M5): m_qbf(A) AS (5a) ((SELECT C FROM rbf(A,C) WHERE A = 10) UNION DISTINCT (5b) (SELECT A FROM m_rbf(A)))
Запрос (M) является рекурсивным, поскольку в его графе зависимостей имеется цикл qbf→(M2)rbf→(5a)m_qbf→(M3)qbf.
Во многих существующих СУБД рекурсия не поддерживается. Если в результате преобразований методом магических множеств будут производиться рекурсивные запросы, то применимость расширенных преобразований будет серьезно ограничена.
Рассмотрим пример 4.2. Таблица qbf является рекурсивной, но эта рекурсия введена заново через магическую таблицу m_qbf (как это и должно быть для любой рекурсии, вводимой путем магических преобразований). Кортеж m_qbf (10) вычисляется в (5b) и приводит к кортежам в qbf через (M3). На их основе генерируются кортежи для rbf через (M2). На основе кортежей из rbf генерируются новые кортежи в m_qbf (5a) и, следовательно, в qbf . Но появление новых кортежей в qbf не может возбудить тело (M2) для генерации новых кортежей в rbf. Таким образом, эта рекурсия «сама себя не подкармливает» и заканчивается после первого цикла.
Поэтому данную программу можно переписать без рекурсии.
Можно избежать введения рекурсии в магической программе, если не распознавать общих подвыражений. Если относиться к двум использованиям q в программе P как к двум разным таблицам q1 и q2, то преобразование методом магических множеств не приведет к появлению рекурсии, в чем можно убедиться, произведя преобразование методом магических множеств для программы P’, которая получается из P с использованием q1 и q2, определяемых в соответствии с P2.
Уточним интуитивные размышления, на которых основан приведенный пример.
Утверждение 4.1 Пусть M является запросом, полученным путем магического преобразования заданного запроса P в соответствии с набором полных SIPS. Тогда: (A) Если P является запросом с древовидной структурой, и (B) если P является направленным ациклическим графом (DAG), то в M будет иметься ограниченная рекурсия, которую можно избежать, не образуя общих подвыражений.
