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


Определения


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

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


Начало  Назад  Вперед