Волшебство состоит в том, чтобы определить, какие именно вспомогательные отношения требуется создать.

(См. [17.25], [17.26], а также список литературы в главе 23.) 17.25.Mumick I.S., Pirahesh Н. Implementation of Magic in Starburst Proc. 1990 ACM

SIGMOD Int. Conf on Management Data. - Minneapolis, Minn., May, 1994. 17.26.Mumick I.S., Finkelstein S.J., Pirahesh H., Ramakrishnan R. Magic Conditions ACM

TODS. - March, 1996. - 21, № 1. 17.27.King J.J. QUIST: A System for Semantic Query Optimization in Relational Databases

Proc. 7th Intern. Conf on Very Large Data Bases. - Cannes, France, September, 1981.

Представлена идея семантической оптимизации (см. раздел 17.4). В статье описана

экспериментальная система QU1ST (QUery Improvement through Semantic

Transformation - улучшение запросов посредством семантических преобразований),

способная выполнять подобные преобразования.

17.28. Shenoy S.T., Ozsoyoglu Z.M. А System for Semantic Query Optimization Proc. 1987 ACM SIGMOD Intern. Conf on Management of Data. - San Francisco, Calif, May-June, 1987. Эта публикация расширяет работу Кинга (King) [17.27], представляя схему, которая динамически выбирает из потенциально очень большого множества ограничений целостности только те ограничения, которые будут полезны для обработки данного запроса. Рассматриваемые ограничения целостности разделены на два типа: ограничения причастности (например, если партия деталей содержит более 300 единиц, то поставшик должен находиться в Лондоне ) и ограничения подмножеств (например, каждый поставщик, находящийся в Лондоне, должен поставлять хотя бы одну деталь ). Подобные ограничения используются для преобразования запросов посредством исключения избыточных выборок и соединений и введения дополнительных выборок для индексированных атрибутов. Случаи, когда результат запроса может быть получен непосредственно из ограничений целостности, также эффективно обрабатываются с помощью изложенного метода.

17.29.Siegel М., Sciore Е., Salveter S. А Method for Automatic Rule Derivation to Support Semantic Query Optimization ACM TODS. - December, 1992. - 17, № 4. Как было показано в этой главе, семантическая оптимизация использует ограничения целостности для преобразования запросов. Тем не менее существует несколько проблем, связанных с этой идеей.

Как оптимизатор может узнать, какое преобразование будет эффективным (т.е. какое преобразование сделает запрос более эффективным)?

Некоторые ограничения целостности не очень полезны для решения задач оптимизации. Например, ограничение, которое требует, чтобы вес детали был больше нуля, важно для целостности базы данных, но по сути бесполезно для целей оптимизации. Как оптимизатор сможет отличить полезные ограничения целостности от бесполезных?

Некоторые утверждения могут быть справедливы для определенных состояний базы данных (даже для большинства состояний), однако они не будут ограничениями целостности. Примером может служить утверждение вида ЕМР.AGE < 50 (возраст сотрудников- не более 50 лет), которое не является

ограничением целостности как таковым (поскольку могут быть сотрудники и старше 50 лет), но в данный момент в компании может действительно не быть сотрудников старше 50 лет.

В этой публикации описана архитектура системы, учитывающей перечисленные

проблемы.

17.30.Chakravarthy U.S., Grant J., Minker J. Logic-Based Approach to Semantic Query Optimization ACM TODS. - June, 1990. - 15, № 2.

Цитата из вступления; В нескольких предыдущих работах авторами была описана и доказана правильность метода семантической оптимизации запросов... В этой работе обобщаются основные результаты из предыдущих работ и особое внимание обращается на методы и их применимость к оптимизации реляционных запросов. Дополнительно в этой работе показано, каким образом описываемый метод подводит итоги и обобщает результаты более ранних работ в области семантической оптимизации. [Кроме того, отмечается] как методы семантической оптимизации запросов могут быть распространены на рекурсивные запросы и ограничения целостности, содержащие дизъюнкции, отрицания и рекурсию . 17.3LAho А.v., Sagiv Y., Ullman J.D. Efficient Optimization of a Class of Relational Expressions ACM TODS. - December, 1979. - 4, № 4.

Класс реляционных выражений, упоминаемый в заголовке этой работы, содержит выражения, использующие только операции отбора по равенству (которые в этой статье называются выборками), проекции и естественного соединения. Этот класс выражений иногда называют SPJ-выражениями (от англ. select , projection , join - выборка , проекция , соединение ). SPJ-выражения соответствуют запросам в реляционном исчислении, в которых используются только сравнения на равенство, операции AND и кванторы EXISTS. В работе приводится определенный вид таблицы (табло - tableau), представляющей двумерный массив, в котором столбцы соответствуют атрибутам, а строки - условиям, в частности условиям принадлежности, которые гласят, что конкретный кортеж значений принадлежит конкретному отношению. Строки табло логически связываются посредством помещения общих символов в связанные строки. Например, табло

St STATUS CITY Р# COLOR

Ы al London - S (поставщики)

bl b2 - SP (поставки)

Ь2 Red - P (детали)

представляет запрос Выбрать статус (al) поставщиков (Ы) в Лондоне, которые поставляют красные детали (Ь2) . Верхняя строка в табло представляет все атрибуты, которые используются в запросе, следующая строка - это итоги (она соответствует кортежу-прототипу в запросе, определенном в исчислении, или финальной проекции в алгебраическом запросе), а оставшиеся строки (как уже говорилось) представляют условия принадлежности. В данном примере эти строки прокомментированы посредством указания относящихся к запросу отношений (точнее, переменных-отношений). Обратите внимание, что Ь используется для ссылок на связанные переменные, а а - для ссылки на свободную переменную. Итоговая строка содержит только переменные типа а.

Табло - это еще один вариант канонической формулировки для представления запросов (см. раздел 17.3), однако оно не является достаточно общим, чтобы представить все возможные реляционные запросы. (Фактически табло можно рассматривать как синтаксическую разновидность языка Query-By-Example (QBE), хотя и менее мощную, чем непосредственно язык QBE.) В работе представлены алгоритмы преобразования одного табло в другое, семантически эквивалентное табло, в котором количество строк уменьщено до минимума. Так как количество строк (не считая двух верхних специальных строк) на единицу больше количества соединений в соответствующем SPJ-выражении, полученное табло представляет оптимальную форму запроса, хотя и в очень специальном смысле (минимальное количество соединений). (В приведенном выше примере количество соединений уже минимально, поэтому подобная оптимизация не дает никакого эффекта.) После этого полученное минимальное табло можно конвертировать обратно в другое представление для последующей дополнительной оптимизации. Идея минимизации количества соединений также применима к запросам, сформулированным в терминах представлений, которые построены на основе операции соединения, в частности к запросам, сформулированным в терминах универсальных отношений (см. список литературы в конце главы 12). Например, предположим, что пользователю предложено представление V, определенное как соединение отношений S и SP по атрибуту S#, и пользователь вводит следующий запрос.

V { Р# }

Прямой алгоритм обработки представлений преобразует данный запрос в следующий.

( SP JOIN S ) { PI }

Тем не менее, как было показано в разделе 17.4, приведенный ниже запрос дает тот же результат, хотя он вовсе не использует операции соединения (т.е. количество соединений в исходном запросе минимизировано).

SP { Р }

Поэтому следует заметить, что, поскольку алгоритмы сжатия табло, описанные в данной работе, учитывают все явно выраженные функциональные зависимости между атрибутами (см. главу 10), они являются офаниченным примером метода семантической оптимизации.

17.32.Sagiv Y., Yannakakis М. Equivalences Among Relational Expressions with the Union and Difference Operators JACM. - October, 1980. - 27, № 4. В этой статье идеи работы [17.31] расширены так, чтобы их можно было применять к запросам, использующим операции объединения и вычитания.

17.33.Levy A.Y., Mumick I.S., Sagiv Y. Query Optimization by Predicate Move-Around Proc. 1979 ACM SIGMOD Int. Conf on Very Large Data Bases. - Santiago, Chile, September, 1994.

17.34. Selinger P.G. et al. Access Path Selection in a Relational Database System Proc. 1979 ACM SIGMOD Intern. Conf on Management of Data. - Boston, Mass., May-June, 1979. В этой важной статье обсуждаются некоторые методы оптимизации, используемые в прототипе системы System R.