полняться весьма эффективно. Предположив, что два рассмотренных выше запроса логически эквивалентны, но второй вариант более удобен с точки зрения эффективности реализации, мы придем к выводу, что возможность преобразования запросов, подобных Q1, в запросы, подобные Q2, требует более глубокого изучения. Эта возможность и является предметом обсуждения в [17.39]-[ 17.45]. Ким (Kim) [17.39] был первым, кто обратил внимание на эту проблему. В его работе идентифицировано пять типов вложенных запросов и описаны соответствующие алгоритмы. В ней приводятся результаты экспериментов, которые показывают, что предложенные алгоритмы повышают производительность обработки вложенных запросов (обычно на один-два порядка).

Затем Кесслинг (Kiessling) [17.40] показал, что алгоритмы Кима работают некорректно, если в списке атрибутов выборки вложенного запроса (на любом уровне) содержится обобщающая функция COUNT (алгоритм Кима некорректно обрабатывает случаи, когда аргументы функции COUNT являются пустыми отношениями). Термин семантические рифы в названии работы Кесслинга указывает на сложности, с которыми сталкивается пользователь при попытке получить корректные и непротиворечивые результаты подобных запросов. Более того, Кесслинг показал, что алгоритмы Кима усовершенствовать непросто (поскольку похоже, не существует единого способа выполнить данное преобразование эффективно и корректно при любых условиях ).

В работе Гански (Ganski) и Вонга (Wong) [17.41] описано решение проблемы, обнаруженной Кесслингом. Оно состоит в использовании в преобразованной версии запроса внешнего соедшния (глава 18) вместо обычного внутреннего соединения. (По мнению современных авторов, это усовершенствование не вполне удовлетворительно, потому что оно вводит нежелательную зависимость упорядочения среди операторов в преобразованном запросе.) В данной работе описывается еще одна ошибка в оригинальной работе Кима, которая устраняется аналогичным способом. Тем не менее работа не лишена собственных ошибок. Одни связаны с проблемой строк-дубликатов (печально известные семантические рифы [17.40]), другие - с изъянами в реализации квантора EXISTS в языке SQL [18.6].

В [17.42] предпринята попытка сформулировать всю проблему на теоретической основе (основной проблемой предыдущих работ являлось то, что, как обнаружили различные авторы, поведение - семантическое и синтаксическое - вложений и обобщающих функций в языке SQL не совсем понятно). В ней также определены расширенные версии реляционного исчисления и реляционной алгебры (расширения касались действий над обобщениями и неопределенными значениями (NULLS)) и доказана эквивалентность расширенных формулировок (при этом использовался более элегантный по сравнению с ранее опубликованным метод доказательства). Затем семантика языка SQL представлена с помощью отображения конструкций этого языка на расширенное исчисление, определенное в работе. Тем не менее необходимо отметить следующее.

1. Обсуждаемый диалект языка SQL ближе к диалектам, используемым в коммерческих продуктах, по сравнению с диалектами языка SQL, которые используются в [17.39]-[17.41]. Однако этот диалект еще не стал полностью общепринятым. Он не включает оператора UNION и прямой поддержки операторов типа

=ALL и >ALL (см. приложение А), а трактовка неизвестных истинных значений отличается от трактовки, обусловленной стандартом языка SQL (на самом деле эта трактовка даже лучше).

2. В данной работе для технического упрошения не рассматриваются методы исключения кортежей-дубликатов. Но влияние такого пропуска не совсем ясно просматривается, исходя из того, что (как было показано ранее) наличие или отсутствие кортежей-дубликатов может значительно повлиять на корректность некоторых преобразований [5.6].

Наконец, в [17.43] утверждается, что в некоторых случаях оригинальные алгоритмы Кима [17.39], несмотря на некорректность, могут быть эффективнее обшей стратегии , изложенной в [17.41]. Поэтому автор работы [17.43] предлагает альтернативный способ исправления ошибок в алгоритмах Кима. К тому же в этой работе представлены некоторые улучшения рассматриваемых алгоритмов.

17.44. Baekgrand L., Mark L. Incremental Computation of Nested Relational Query Expressions ACM TODS. - June, 1995. -20, Ш 2.

Еше одна статья об оптимизации запросов, включаюших подчиненные запросы в стиле языка SQL, в частности коррелированные запросы ( вложение , упомянутое в заголовке статьи, относится к вложенным подчиненным запросам в стиле языка SQL). Предлагаемая стратегия включает преобразование исходного запроса в эквивалентный запрос без вложений с последующей инкремент-ной оценкой полученной версии запроса без вложений. Для поддержки первого этапа разработан очень краткий алгоритм преобразования типа алгебра - алгебра ... В [преобразованном] выражении интенсивно используется оператор MINUS. Для реализации второго этапа предложен и проанализирован эффективный алгоритм инкрементной оценки операций MINUS. Термин инкрементное вычисление означает, что для оценки данного запроса могут использоваться предварительно вычисленные результаты.

17.45.Rao J., Ross К.А. Using Invariants: А New Strategy for Correlated Queries Proc. 1998 ACM SIGMOD Int. Conf on Management of Data. - Seattle, Wash., June, 1998.

Еще одна статья об оптимизации запросов, в том числе подчиненных запросов в стиле языка SQL.

17.46.Warren D.H.D. Efficient Processing of Interactive Relational Database Queries Expressed in Logic Proc. 7th Intern. Conf on Very Large Data Bases. - Cannes, France, September, 1981.

Представлен взгляд на оптимизацию запросов с точки зрения формальной логики. Описаны приемы, которые используются в экспериментальной СУБД, для формулировки запросов применяющей язык Prolog. Создается впечатление, что эти приемы очень похожи на приемы, используемые в системе System R, хотя разработаны они были совершенно независимо и с несколько отличными целями. В работе указывается, что в отличие от обычных языков запросов, таких как QUEL и SQL, языки, основанные на логике (подобные языку Prolog), позволяют записывать запросы так, чтобы выделить следующее:

логические цели, которые являются основными компонентами запроса;

логические переменные, связываюшие эти компоненты;

порядок достижения логических целей, который является критическим моментом с точки зрения реализации.

Из этого следует, что подобные языки весьма удобны в качестве базы для выполнения оптимизации. Действительно, такой язык можно рассматривать в качестве еще одного кандидата для внутреннего представления запроса, исходно сформулированного с помощью какого-либо другого языка (см. раздел 17.3). 17.47. loannidis Y.E., Wong Е. Query Optimization by Simulated Annealing Proc. 1987 ACM SIGMOD Intern. Conf. on Management of Data. - San Francisco, Calif, May, 1987. С увеличением числа отношений, используемых в запросе, количество возможных планов выполнения этого запроса растет экспоненциально. В традиционных коммерческих приложениях число отношений в запросе обычно невелико и, следовательно, количество потенциальных планов выполнения запроса ( пространство поиска ) остается в разумных пределах. Тем не менее в современных приложениях количество отношений в запросе может быть достаточно большим (примеры приводятся в главе 21). Более того, в приложениях нового типа ощущается необходимость глобальной (т.е. для многих запросов) оптимизации [17.49] и поддержки рекурсивных запросов. Эти функции также значительно увеличивают пространство поиска. Исчерпывающий поиск в таких условиях становится неэффективным, и возникает настоятельная необходимость в использовании методов сужения пространства поиска.

В публикации содержатся ссылки на более ранние работы по проблеме оптимизации запросов с большим количеством отношений и многозапросной оптимизации. Однако в данной работе утверждается, что для оптимизации рекурсивных запросов не разработано ни одного алгоритма, после чего приводится алгоритм, который, как утверждают авторы, применим даже на пространствах поиска большого размера. В частности, показано, как применять предложенный алгоритм в случае рекурсивных запросов. Данный алгоритм (называемый модельным отжигом , так как он моделирует процесс отжига, с помощью которого выращивают кристаллы, сначала прогревая жидкий раствор, а затем постепенно охлаждая его) является высокоэффективным алгоритмом, который может успешно применяться для решения проблемы оптимизации в других контекстах. См. также [17.48].

17.48.Swami А., Gupta А. Optimization of Large Join Queries Proc. 1988 ACM SIGMOD Intern. Conf on Management of Data. - Chicago, 111., June, 1988. Общая проблема определения оптимального порядка выполнения соединений в запросах, использующих большое количество отношений (что характерно для дедуктивных баз данных, описываемых в главе 23), является комбинаторно сложной. В работе представлен сравнительный анализ нескольких алгоритмов, предназначенных для решения этой проблемы: возмущенный обход, псевдослучайная генерация данных, последовательные улучшения, последовательные эвристики и модельный отжиг [17.47] (названия методов добавляют немного поэзии в предмет обсуждения, который выглядит достаточно прозаично). Согласно результатам проведенного анализа алгоритм последовательных улучшений превосходит все остальные алгоритмы, в частности алгоритм модельного отжига сам по себе нельзя использовать для больших запросов-соединений.

17.49.Sellis Т.К. Multiple-Query Optimization ACM TODS. - March, 1988. - 13, 1.