это название алгоритма преобразования запросов
«Магические множества» – это название алгоритма преобразования запросов ([BMSU86]) (а теперь класса алгоритмов – обобщенные магические множества (Generalized Magic-sets) в [BR87], магические шаблоны (Magic Templates) в [Ram88], магические условия в [MFPR90]) для обработки рекурсивных запросов, написанных на языке Datalog. Ранее эти алгоритмы не применялись в стандартных реляционных системах баз данных, и их значение для таких систем не было оценено.
В системах реляционных баз данных поддерживается ряд возможностей, находящихся за пределами средств Datalog, включая дубликаты (ведущие к мультимножествам), агрегирование и группировку. Мы расширили подход магических множеств (и язык Datalog) для обработки этих особенностей ([MPR90]), а также показали, что магические множества можно расширить для распространения условий, отличных от сравнения по равенству [MFPR90]. В данной статье эти результаты интегрируются, расширяются и применяются; наша цель состоит в том, чтобы показать, что магические множества обеспечивают надежный метод, который может быть с пользой применен в практических реляционных системах не только для рекурсивных запросов (например, ведомость материалов), но и для не рекурсивных запросов. Этот метод особенно важен для сложных запросов, таких как запросы в системах поддержки принятия решений.
Статья организована следующим образом. Мы представляем короткий подраздел, описывающий SBSQL – язык SQL системы Starburst, в котором поддерживается рекурсия, и приводим пример нелинейного запроса. В разд. 2 обосновывается практичность метода магических множеств путем описания его взаимосвязи с традиционными преобразованиями (такими как выдавливание предикатов) нерекурсивных сложных SQL-запросов. В разд. 3 определяются преобразование магических множеств и некоторые общепринятые родственные понятия. В разд. 4 описывается наше расширение преобразования магических множеств для реляционных систем баз данных, разрешающее сложности, которые возникают при объединении наших предыдущих результатов [MFPR90, MPR90] и их применении к SBSQL. Мы показываем, что можно избежать рекурсии, возникающей при преобразовании нерекурсивных запросов методом магических множеств, и что комбинирование фазы украшения (adornment phase) с преобразованием методом магических множеств позволяет распространять произвольные условия с использованием простого паттерна украшения. В разд. 5 содержится обзор реализации метода магических множеств в прототипе расширяемой реляционной системы баз данных Srarburst в IBM Almaden Research Center ([HFLP89]). В разд. 6 приводятся результаты измерения производительности показывающие, что применение метода магических множеств может повысить эффективность выполнения сложных нерекурсивных SQL-запросов по сравнению с применением традиционных методов, таких как корреляция и декорреляция. В разд. 7 содержится заключение.
