примера 3.1 предикат Job = 'Sr Programmer' повторяется в операторах M1 и M3. В программе S из примера 2.1 результат выборки сохранялся в s_mag и использовался как общее подвыражение при вычислении Sl и S3. Таблицы, подобные в s_mag, называются дополнительными магическими множествами. Программа D преобразуется в программу S с использованием дополнительных преобразований методом магических множеств ([BR87]). Мы используем дополнительные магические множества в разд. 6, потому что использование общих подвыражений существенно влияет на эффективность. Для простоты объяснений в других разделах мы используем просто магические множества.
SIPS: Sideways Information Passing Strategy определяет решение о том, как передавать информацию сторонним образом в теле табличного выражения при его вычислении. Передаваемая информация поступает из предикатов табличного выражения. SIPS определяется формально в [BR87, MFPR90].
SIPS может быть полной (в том смысле, что все подходящие предикаты используются настолько рано, насколько это возможно) или частичной. Полная SIPS может определяться путем упорядочения таблиц в разделе FROM. Мы называем этот порядок порядком SIPS.
При преобразованиях методом магических множеств информация передается сторонним образом между соединяемыми таблицами в соответствии с заданным порядком SIPS. В этой статье мы предполагаем, что таблицы перечисляются в разделе FROM в порядке SIPS.
Графы зависимости: Графы зависимости широко используются для распознавания рекурсии. В табличном выражении таблицы в теле (в разделе FROM) используются для определения таблицы в заголовке. Если в некотором табличном выражении таблица q определяет таблицу r, мы обозначаем это как q → r, что называется дугой зависимости. Мы определяем →→ как транзитивное замыкание →. Запрос является рекурсивным в том и только в том случае, когда в графе зависимостей имеются циклы, т.е. если существует таблица q, такая что (q →→ q). Все таблицы в сильно связанном компоненте (strongly connected component, sсс) графа зависимости называются взаимно рекурсивными.
4. Расширенное преобразование методом магических множеств
Преобразования методом магических множеств, определенные в разд. 3, применимы к реляционным системам с дубликатами и агрегацией. В этом определении заимствуются результаты из [MPR90], где определяется семантика дубликатов и агрегации в присутствии рекурсии, и использование агрегации ограничивается классом монотонных (monotonic) и магических стратифицируемых (magical stratified) программ, замкнутых относительно преобразований методом магических множеств.
Долгое время преобразования методом магических множеств считались полезными только для распространения связываний (предикатов сравнения по равенству). В нашей недавней статье [MFPR90] затрагивалось расширение метода для распространения условий (предикатов сравнения не по равенству) в программах Datalog с использованием основного преобразования на основе магических множеств (ground magic-sets transformation, GMT). В разд. 4.1 мы расширяем GMT для работы в присутствии дубликатов.
Далее мы обсуждаем, каким образом метод магических множеств может быть полезен в чисто нерекурсивных системах (разд. 4.2), и представляем однофазный алгоритм для украшения и магического преобразования запроса, которые дают нам возможность проталкивания произвольных условий с использованием только украшений b, c и f (разд. 4.3).
4.1. Проталкивание условий с использованием магии
В основном преобразовании на основе магических множеств, как оно представлено в [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 у нас имеется решение, позволяющее использовать дополнительное преобразование; из-за недостатка места мы опускаем описание.
4.2. Преобразования методом магических множеств для нерекурсивных программ
Хорошо известно, что у преобразований методом магических множеств имеется нежелательное свойство слияния сильно связанных компонентов. В результате нерекурсивная программа может стать рекурсивной.
ПРИМЕР 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 является запросом с древовидной структурой8), и (B) если P является направленным ациклическим графом (DAG)9), то в M будет иметься ограниченная рекурсия, которую можно избежать, не образуя общих подвыражений.
4.3. Простые 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α в дополнительную таблицу.10) Для любых двух ограничений 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, в некоторых случаях это должно считаться магической таблицей. Это не является проблемой, но для простоты предположим, что у нас всегда имеется дополнительная таблица.
Назад Содержание Вперёд
🔥 VPS до 5.7 ГГц под любые задачи с AntiDDoS в 7 локациях
) (m_p обозначает магическую таблицу p, а 
и для каждой таблицы qi
, а тело содержит все таблицы, предшествующие qi в sips (определяется ниже), ассоциированной с r, а также магическую таблицу m_p(
Виртуальные VPS серверы в РФ и ЕС
