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

Проталкивание условий с использованием магии


В основном преобразовании на основе магических множеств, как оно представлено в [MFPR90], не сохраняется семантика дубликатов. Рассмотрим простой пример.

ПРИМЕР 4.1 Рассмотрим следующую программу P, где p1 и p2 – произвольные встроенные предикаты (условия), а u, v, s и w – EDB-отношения. (EDB – extensional database.)

(Pl): r(X,Z) AS ((SELECT X, Z

FROM tcf(X,Y), u(Y,Z) WHERE p1(X)) UNION ALL (SELECT X, Z

FROM tcf(X,Y), v(Y,Z) WHERE p2(X)))

(P2): tcf(X,Z) AS (SELECT X, Z FROM s(X,Y), w(Y,Z))

Пусть s = [(1,2),(1,2)], w = [(2,3)], u = [(3,4)] и v = [(3,4)]. Пусть p1(1) и p2(1) есть true. Тогда в соответствии с семантикой дубликатов программа P определяет r как мультимножество [(1,4),(1,4),(1,4),(1,4)].

GMT преобразует определение P2 в следующее:

(M2): tcf(X,Z) AS (SELECT X, Z FROM m(X,Y), w(Y,Z))

(M3): m(X,Y) AS ((SELECT X, Y FROM s(X,Y) WHERE p1(X)) UNION DISTINCT (SELECT X, Y FROM s(X,Y) WHERE p2(X)))

Для завершения процесса создания магической программы Pl копируется в Ml. В представлении m имеется одна копия кортежа (1,2), и, следовательно, в представлении r будут иметься две копии кортежа (1,4). В результате программы P и M не эквивалентны по отношению к дубликатам. Определение m с использованием UNION ALL нам не помогает, потому что тогда в m будут иметься четыре копии (1,2), и в r будут иметься восемь копий (1,4).

Кстати, если бы либо r, либо t были DISTINCT, GMT сохранял бы семантику запроса.

GMT конструирует специальные магические множества (m), называемые дополнительными магическими множествами, для каждого раздела SELECT путем комбинирования магического множества (p1(X)) с таблицей из раздела FROM. Для сохранения семантики дубликатов требуется удаление накладываемых кортежей (значений X, общих для p1 и p2), в то время как оставшиеся в таблицах дубликаты копируются из раздела(ов) FROM. Такая операция невозможна, если никогда не конструируются магические таблицы, как в случае GMT.

Простое решение состоит в явном конструировании магических таблиц путем следующей перезаписи M2 и M3:

(E2): tcf(X,Z) AS (SELECT X, Z

FROM m(X), s(X,Y), w(Y,Z))

(E3): m(X) AS ((SELECT X FROM s(X,Y) WHERE p1(X)) UNION DISTINCT (SELECT X FROM s(X,Y) WHERE p2(X)))

Здесь m – это магическое множество. Операция UNION DISTINCT удаляет дубликаты после объединения. В приведенной конструкции повторяются некоторые соединения, такие как соединение с s. В реализации Starburst у нас имеется решение, позволяющее использовать дополнительное преобразование; из-за недостатка места мы опускаем описание.



Содержание раздела