Классика баз данных - статьи
Родственные работы
Разработчики ранних РСУБД, таких как System R [ABC+ 76] и INGRES [SWK76] осознавали важность подстановки представлений и решали эту задачу для частных случаев. Несмотря на признанную важность таких преобразований, эти ранние схемы преобразований были применены лишь в немногих системах.
Ким [Kim82] первым задался вопросом о том, когда квантифицированные подзапросы можно заменить соединениями (или антисоединениями). Гански (Ganski) и Вонг (Wong) [GW87] и Дайал (Dayal) [Day87] проделали дополнительную работу по устранению вложенных подзапросов. В этих статьях признается важность поглощения подзапросов. В [Kim82, GW87] также решается проблема подзапросов, содержащих агрегацию. Мы описывали наш набор правил для работы с такими подзапросами в [MFPR90a, MPR90, MFPR90b].
В статье Гански иллюстрируется сложность перезаписи запросов, поскольку в описываемой работе ему пришлось исправлять некоторые предыдущие преобразования, которые были некоректными. Эта сложность поддерживает наш подход декомпозиции преобразований в расширяемый набор индивидуальных правил, таких что корректность каждого правила может быть показана отдельно.
Мы уделяем особое внимание ортогональности языка. Поэтому такие операции как UNION, INTERSECT и EXCEPT (эквивалент вычитания множеств в SQL) могут появляться в подзапросах, как этого и требует стандарт SQL [ISO91]. В упомянутых выше работах этим более сложным подзапросам внимание не уделяется. Кроме того, наши правила гарантируют поглощение конъюнктов подзапросов с кванторами существования, состоящих из ограничения, проекции и соединения. Частично это стало возможным благодаря нашему аккуратному обращению с дубликатами.
Анфиндсен (Anfindsen) [Anf89] также провел исследования преобразований подзапросов, используя РСУБД DB2 для измерений эффективности. Как и мы, Анфиндсен отмечает улучшение производительности на порядки. Однако автор ограничивается только преобразованиями, выдающими SQL-запрос, который может быть обработан DB2. В отличие от этого, наш подход является составной и интегральной частью РСУБД, что позволяет использовать более развитый внутренний язык и, следовательно, дает возможность производить большее число оптимизационных преобразований.
