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

       

Определения


Преобразование методом магических множеств: Алгоритм магических множеств перезаписывает запрос таким образом, что при вычислении с фиксированной точкой преобразованного запроса не генерируются нерелевантные кортежи. Идея состоит в том, чтобы вычислить набор дополнительных таблиц, которые содержат связывания, используемые для ограничения таблицы. Затем табличные выражения в запросе модифицируются путем соединения дополнительных таблиц, которые действуют как фильтры и препятствуют генерации нерелевантных кортежей. Однако на первом шаге мы производим украшенный (adorned) запрос, в котором таблицы украшаются аннотациями, показывающими, какие аргументы связываются с константами, какие ограничиваются условиями, и какие являются свободными в табличном выражении с данной таблицей. Для каждой таблицы мы имеем украшенную версию, соответствующую всем использованиям этой таблицы с применением паттерна связывания, который описывается данным украшением. Разные украшенные версии, по существу, трактуются как разные таблицы (возможно, по-разному разрешаемые). Например, pbf и pfb трактуются как разные таблицы (имена таблиц). Украшение (adornment) для некоторой n-арной таблицы определяется как строка из символов b, c и f. Позиции аргументов, которые трактуются как свободные (те, на которых нет предикатов), обозначаются как f, а позиции, которые связываются с конечным множеством данных значений (предикатами сравнения на равенство) обозначаются как b. Позиции аргументов, которые ограничены в цели некоторым предикатом, отличным от предиката сравнения на равенство, обозначаются как c.

В преобразованиях методом магических множеств из [BMSU86, BR87] распространяются связывания (предикаты сравнения на равенство) в Datalog с использованием украшений b и f. Условия игнорируются. В [MPR90] преобразования методом магических множеств расширяются для распространение связываний в программах с дубликатами и агрегированием. Расширение для работы с условиями ([MFPR90]) нуждается в адаптации для работы в присутствии дубликатов, и мы представляем эту идею в разд. 4.1.
В следующем определении мы игнорируем украшения и условия.

Алгоритм магических множеств можно понимать как двухшаговое преобразование, в котором мы сначала получаем украшенный запрос Pad, а затем применяем следующее преобразование:

Мы создаем новый запрос Pmq. Изначально этот запрос пуст.

  1. Для каждой таблицы p из Pad создается новая таблица без дубликатов m_p. Ее арность равна числу связанных аргументов p.


  2. Для каждого табличного выражения в Pad к Pmq добавляется модифицированная версия. Если у табличного выражения r имеется заголовок, скажем, p(t) (t – это сокращение для всех атрибутов p), то модифицированная версия получается путем присоединения к телу таблицы m_p(
    ) (m_p обозначает магическую таблицу p, а
    – связанные аргументы p).
  3. Для каждого табличного выражения r в P с заголовком, скажем, p
    и для каждой таблицы qi
    , на которую имеется ссылка в теле выражения, к Pmq добавляется магическое табличное выражение. Его заголовок – m_qi
    , а тело содержит все таблицы, предшествующие qi в sips (определяется ниже), ассоциированной с r, а также магическую таблицу m_p(
    ).
  4. Создается начальная (seed) таблица m_qi(c) из предикатов сравнения по равенству в наиболее внешнем блоке запроса, где c – это набор констант, участвующих в сравнении связанных аргументов q.


Заметим, что с каждой таблицей в Pad ассоциируется магическая таблица. Если генерируется несколько табличных выражений с одним и тем же заголовком, они заменяются одним табличным выражением, в теле которого содержится объединение соответствующих тел.

Интуитивно преобразование методом магических множеств включает добавление в каждом операторе SQL магических таблиц в раздел FROM и предикатов сравнения по равенству в раздел WHERE.

ПРИМЕР 3.1 (Преобразование методом магических множеств): Рассмотрим запрос D из примера 2.1. Нам требуется вычислить среднюю зарплату в отделах в представлении dep_avgsal в том и только в том случае, когда в отделе имеется старший программист, поскольку в противном случае средняя зарплата не релевантна.




При применении метода магических множеств эта оптимизация достигается путем определения магической таблицы (M3) и перезаписи D1 и D2 как M1 и M2.

(Ml): SELECT Ename FROM emp, dep_avgsalbf

WHERE Job = 'Sr Programmer' AND Sal > Asal AND emp.Dno = dep_avgsalbf.Dno

(M2): dep_avgsalbf(Dno, Asal) AS (SELECT DUO, AVG(Sa1) FROM m_dep_avgsalbf, emp WHERE m_dep_avgsalbf.Dno = emp.Dno GROUPBY Dno)

(M3): m_dep_avgsalbf(Dno) AS (SELECT DISTINCT Dno FROM emp WHERE Job = 'Sr Programmer')

Здесь m_dep_avgsalbf является магической таблицей для представления dep_avgsalbf, выдающей уместные отделы, для которых требуется вычислять представление. Верхний индекс bf показывает, что представление dep_avgsalbf всегда будет вычисляться с использованием первого аргумента, связанного с набром кортежей, а второй аргумент является свободным.

Вспомогательные магические множества: В магическом запросе примера 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сс) графа зависимости называются взаимно рекурсивными.


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