Магия сохраняет силу


Преобразования методом магических множеств для нерекурсивных программ


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

ПРИМЕР 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. Таким образом, эта рекурсия «сама себя не подкармливает» и заканчивается после первого цикла.


Начало  Назад  Вперед



Книжный магазин