Определения
Преобразование методом магических множеств: Алгоритм магических множеств перезаписывает запрос таким образом, что при вычислении с фиксированной точкой преобразованного запроса не генерируются нерелевантные кортежи. Идея состоит в том, чтобы вычислить набор дополнительных таблиц, которые содержат связывания, используемые для ограничения таблицы. Затем табличные выражения в запросе модифицируются путем соединения дополнительных таблиц, которые действуют как фильтры и препятствуют генерации нерелевантных кортежей. Однако на первом шаге мы производим украшенный (adorned) запрос, в котором таблицы украшаются аннотациями, показывающими, какие аргументы связываются с константами, какие ограничиваются условиями, и какие являются свободными в табличном выражении с данной таблицей. Для каждой таблицы мы имеем украшенную версию, соответствующую всем использованиям этой таблицы с применением паттерна связывания, который описывается данным украшением. Разные украшенные версии, по существу, трактуются как разные таблицы (возможно, по-разному разрешаемые). Например, pbf и pfb трактуются как разные таблицы (имена таблиц). Украшение (adornment) для некоторой n-арной таблицы определяется как строка из символов b, c и f. Позиции аргументов, которые трактуются как свободные (те, на которых нет предикатов), обозначаются как f, а позиции, которые связываются с конечным множеством данных значений (предикатами сравнения на равенство) обозначаются как b. Позиции аргументов, которые ограничены в цели некоторым предикатом, отличным от предиката сравнения на равенство, обозначаются как c.
В преобразованиях методом магических множеств из [BMSU86, BR87] распространяются связывания (предикаты сравнения на равенство) в Datalog с использованием украшений b и f. Условия игнорируются. В [MPR90] преобразования методом магических множеств расширяются для распространение связываний в программах с дубликатами и агрегированием. Расширение для работы с условиями ([MFPR90]) нуждается в адаптации для работы в присутствии дубликатов, и мы представляем эту идею в разд. 4.1.
В следующем определении мы игнорируем украшения и условия.
Алгоритм магических множеств можно понимать как двухшаговое преобразование, в котором мы сначала получаем украшенный запрос Pad, а затем применяем следующее преобразование:
Мы создаем новый запрос Pmq. Изначально этот запрос пуст.
- Для каждой таблицы p из Pad создается новая таблица без дубликатов m_p. Ее арность равна числу связанных аргументов p.
- Для каждого табличного выражения в Pad к Pmq добавляется модифицированная версия. Если у табличного выражения r имеется заголовок, скажем, p(t) (t – это сокращение для всех атрибутов p), то модифицированная версия получается путем присоединения к телу таблицы m_p() (m_p обозначает магическую таблицу p, а
– связанные аргументы p). - Для каждого табличного выражения r в P с заголовком, скажем, p и для каждой таблицы qi
, на которую имеется ссылка в теле выражения, к Pmq добавляется магическое табличное выражение. Его заголовок – m_qi, а тело содержит все таблицы, предшествующие qi в sips (определяется ниже), ассоциированной с r, а также магическую таблицу m_p(
). - Создается начальная (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сс) графа зависимости называются взаимно рекурсивными.
