Простые bcf-украшения
В преобразованиях методом магических множеств, рассматриваемых в [BMSU86, BR87, MFPR90], предполагается, что на вход поступает уже украшенная программа. Поэтому в преобразовании требуются две фазы. На первой фазе программа украшается, а на второй – магически преобразуется. В этом подразделе мы представляем однофазный алгоритм, совместно выполняющий украшение и магическое преобразование, и показываем, как это может помочь для сокращения сложности украшений.
Мы видим, что украшения обеспечивают три функции:
Функция 1: Украшение α на таблице t является абстракцией для ограничения таблицы t в точке ее использования. Эта абстракция α, а не реальное ограничение, используется для принятия решения о том, как будет вычисляться табличное выражение для tα.
Функция 2: tα вычисляется идентичным образом для всех ограничений, абстрагируемых украшением α (одни и те же SIPS, порядок SIPS, порядок соединений и украшения для таблиц, на которые имеются ссылки в табличном выражении t). Следовательно, если абстракция не является хорошей, то для некоторых ограничений tα будет разрешаться не оптимально. Украшение должно быть правильным ([MFPR90]) в том смысле, что оно должно позволять производить выбор оптимального вычисления всех ограничений (внутри класса ограничений, которые пытает фиксировать паттерн украшения), генерирующих это украшение.
Функция 3: Украшения указывают, когда в двух использованиях t может разделяться одна и та же копия t как общее подвыражение. Основанием для того требования, чтобы в использованиях имелось одно и то же украшение, является то, что тогда магические множества генерируются на основе этих использований с одними и теми же аргументами, что позволяет применять объединения.
В паттерне bcf-украшения, введенном в [MFPR90], c-украшение используется только для независимых условий. Условие на атрибуте X называется независимым, если оно может быть выражено без ссылки на какой-либо свободный (f) атрибут. Таким образом, условие X > 10 является независимым.
Условие X > Y независимо, если атрибут Y является связанным, в противном случае это условие зависимо. Алгоритм украшения и следующий за ним GMT из [MFPR90] работают в предположении, что проталкиваются только независимые условия, и что из заданных условий не выводятся какие-либо новые. В [MFPR90] также говорится, что при использовании двухфазного алгоритма невозможно вылавливать и проталкивать зависимые и более общие типы условий на основе паттерна bcf-украшения. Для проталкивания таких условий требуются более сильные паттерны.
В своем однофазном алгоритме мы генерируем магические множества для таблицы t по мере генерации ее украшений, до украшения тела табличного выражения, определяющего t. Далее, когда мы определяем SIPS в табличном выражении tα и украшаем таблицы, на которые в нем имеются ссылки, мы знаем реальные условия на tα (поскольку можем посмотреть на магическое множество). Эти реальные условия используются для обеспечения лучшего выбора способа вычисления табличного выражения.
Определим паттерн простого bcf-украшения аналогично bcf-паттерну из [MFPR90] (обсуждавшегося в разд. 4.1) за исключением того, что украшение c на атрибуте теперь представляет любой тип условия на этом атрибуте, а не только независимое условие.
Теперь мы объясним, каким образом возможность генерации магических множеств при украшении табличного выражения для t обеспечивает поддержку паттерном простого bcf-украшения всех трех упомянутых выше функций украшений, при том, что украшение c представляет произвольное условие.
В следующей лемме мы используем определение опорных (grounding) таблиц из [MFPR90]. При заданном условии p на порождаемой таблице t набор таблиц раздела FROM табличного выражения для t, содержащих все атрибуты, на которые имеются ссылки из p, называется опорным набором. Например, в операторе P2 примера 4.1 s является опорной таблицей для ограничения X > 10.
Лемма 4.1 Пусть p1 и p2 – два ограничения на одних и тех же атрибутах порождаемой таблицы t.
Тогда, если множество G является опорным для p1, то G является опорным множеством и для p2.
Используя Лемму 4.1, мы покажем, что однофазный алгоритм с простыми bcf-украшениями выполняет все функции, которые должны выполнять украшения.
Функция 1: Если реальные ограничения на таблице доступны во время украшения ее тела, то для функции 1 украшения больше не требуются. В результате абстракция, которую они представляют, не является важной.
Функция 2: Функция 2 обеспечивается паттерном простых bcf-украшений для класса произвольных ограничений; это следует из Леммы 4.1 и основного преобразования методом магических множеств [MFPR90]. Проиллюстрируем это на примере.
ПРИМЕР 4.3 (Простое bcf-украшение):
(P1): SELECT X,Y,Z FROM t(X,Y,Z) WHERE X > 10 AND Y > 10
(P2): SELECT X,Y,Z FROM t(X,Y,Z) WHERE X > Y
(P13): t(X,Y,Z) AS (SELECT DISTINCT X,Y,Z FROM q1(X), q2(Y), u(X,Z))
Для обоих запросов P1 и P2 генерируется украшение tccf. По Лемме 4.1 {q1,q2} является опорным множеством для любого ограничения над двумя первыми аргументами t. Таблицы q1 и q2 должны украшаться по-разному для двух использований tccf, а u должно украшаться как ubf для обоих использований. Если бы мы украшали программу без конструирования магических множеств и без использования информации, за исключением украшения ccf на t, то мы не смогли бы произвести желаемое украшение. Однако с использованием своего однофазного алгоритма мы получаем:
(M1): SELECT X, Y, Z FROM tccf(X,Y,Z) WHERE X > 10 AND Y > 10
(M2): SELECT X, Y, Z FROM tccf(X,Y,Z) WHERE X > Y
(M3): tccf (X,Y,Z) AS SELECT DISTINCT X, Y, Z FROM m_tccf (X,Y), ubf (X,Z))
(M4): m_tccf(X,Y) AS ((SELECT X, Y FROM q1c(X), q2c(Y) WHERE X > 10 AND Y > 10) UNION DISTINCT (SELECT X, Y FROM q1f(X), q2c(Y) WHERE X > Y ))
Отметим разные украшения для q1 в двух операторах SELECT в (M4) и украшение b в (M3), появившиеся по причине наличия магических множеств.
Вообще говоря, для c-украшенной таблицы t GMT переводит опорные таблицы tα в дополнительную таблицу. Для любых двух ограничений r1 и r2, генерирующих одно и то же bcf-украшение α на t, опорные таблицы q являются одними и теми же (Лемма 4.1). Таблица q будет копироваться в две таблицы – в (M1) вместе с r1 и в (M2) вместе с r2. Если эти ограничения обладают полностью различной природой, то в (M1) и (M2) для таблиц q могли бы выбираться разные украшения и разные порядки SIPS. Однако в исходном texp для tα в дополнительные магические множества выглядят как генерирующие связывания для всех украшений b или c, независимо от природы ограничений. Поскольку мы не различаем типы связывания при принятии решения о вычислении табличного выражения, вычисление tα будет оптимальным для обоих ограничений.
Функция 3: Паттерн простых bcf-украшений выполняет функцию 3. Если при двух использованиях таблицы в условиях применяются одни и те же аргументы, то и у их опорных магических множеств будут одни и те же аргументы.
7) В разд. 4.3 мы покажим, как можно объединить эти два шага.
8) В запросе с древовидной структурой отсутствуют общие подвыражения.
9) В DAG могут иметься общие подвыражения, но отсутствует рекурсия.
10) Как отмечалось в подразделе 4.1, в некоторых случаях это должно считаться магической таблицей. Это не является проблемой, но для простоты предположим, что у нас всегда имеется дополнительная таблица.
