Введение в системы БД (542480), страница 176
Текст из файла (страница 176)
Ким (Кнп) [17.39] был первым, кто обратил внимание на эту проблему. В его работе идентифицировано пять типов вложенных запросов и описаны соответствующие алгоритмы. В ней приводятся результаты экспериментов, которые показывают, что предложенные алгоритмы повышают производительность обработки вложенных запросов (обычно на один-два порядка). Затем Кесслинг (К]езз11п8) [17.40] показал, что алгоритмы Кима работают некорректно, если в списке атрибутов выборки вложенного запроса (на любом уровне) содержится обобщающая функция С008Т (алгоритм Кима некорректно обрабатывает случаи, когда аргументы функции С008Т являются пустыми отношениями).
Термин "семантические рифы" в названии работы Кесслинга указывает на сложности, с которыми сталкивается пользователь при попытке получить корректные и непротиворечивые результаты подобных запросов. Более того, Кесслинг показал, что алгоритмы Кима усовершенствовать непросто (поскольку "похоже, не существует единого способа выполнить данное преобразование эффективно и корректно при любых условиях"). ' В работе раиски (ОапзЫ) н Вонга (%оп8) [17.41] описано решение проблемы, обнаруженной Кесслингом.
Оно состоит в использовании в преобразованной версии запроса внешнего соединения (глава 18) вместо обычного внутреннего соединения. (По мнению современных авторов, это усовершенствование не вполне удовлетворительно, потому что оно вводит нежелательную зависимость упорядочения среди операторов в преобразованном запросе.) В данной работе описывается еще одна ошибка в оригинальной работе Кима, которая устраняется аналогичным способом. Тем не менее работа не лишена собственных ошибок. Одни связаны с проблемой строк-дубликатов (печально известные "семантические рифы" [17.40]), другие — с изъянами в реализации квантора ЕХ18Т8 в языке БЯ(. [18.6].
В [! 7.42] предпринята попытка сформулировать всю проблему на теоретической основе (основной проблемой предыдущих работ являлось то, что, как обнаружили различные авторы, поведение — семантическое и синтаксическое — вложений и обобщающих функций в языке $Я1. не совсем понятно). В ней также определены расширенные версии реляционного исчисления и реляционной алгебры (расширения касались действий над обобщениями и неопределенными значениями (НЖЬ8)) и доказана эквивалентность расширенных формулировок (при этом использовался более элегантный по сравнению с ранее опубликованным метод доказательства).
Затем семантика языка ЫН. представлена с помощью отображения конструкций этого языка на расширенное исчисление, определенное в работе. Тем не менее необходимо отметить следующее. 1. Обсуждаемый диалект языка БО1. ближе к диалектам, используемым в коммерческих продуктах, по сравнению с диалектами языка БЯ(., которые используются в [17.39Н17.41]. Однако этот диалект еще не стал полностью общепринятым. Он не включает оператора 08108 и прямой поддержки операторов типа Глава 17. Оптимизация 683 "=вйБ" и ">ОБ" (см.
приложение А), а трактовка неизвестных истинных значений отличается от трактовки, обусловленной стандартом языка БОЬ (на самом деле эта трактовка даже лучше). 2. В данной работе для "технического упрощения" не рассматриваются методы исключения кортежей-дубликатов, Но влияние такого пропуска не совсем ясно просматривается, исходя из того, что (как было показано ранее) наличие или отсутствие кортежей-дубликатов может значительно повлиять на корректность некоторых преобразований [5.6]. Наконец, в [17.43] утверждается, что в некоторых случаях оригинальные алгоритмы Кима [17.39], несмотря на некорректность, могут быть эффективнее "обшей стратегии", изложенной в [17.41]. Поэтому автор работы [17.43] предлагает альтернативный способ исправления ошибок в алгоритмах Кима. К тому же в этой работе представлены некоторые улучшения рассматриваемых алгоритмов. 17.44.
Ваеййгапг) Ь., Маг1с Ь.! псгещеп!а! Сощрцгайоп оГХезгед Ке!а11опа! Оцегу Ехргеьаюпа // АСМ ТООБ. — )цпе, 1995. — 20, № 2. Еще одна статья об оптимизации запросов, включающих подчиненные запросы в стиле языка БОЬ, в частности коррелированные запросы (" вложение", упомянутое в заголовке статьи, относится к вложенным подчиненным запросам в стиле языка БОЬ). Предлагаемая стратегия включает преобразование исходного запроса в эквивалентный запрос без вложений с последующей инкрементной оценкой полученной версии запроса без вложений. "Для поддержки первого этапа разработан очень краткий алгоритм преобразования типа "алгебра— алгебра"...
В [преобразованном] выражении интенсивно используется оператор М1И08. Для реализации второго этапа предложен и проанализирован эффективный алгоритм инкрементной оценки операций М1808." Термин инкрементное вычисление означает, что для оценки данного запроса могут использоваться предварительно вычисленные результаты. 17.45.8ао 1.. Коза К.А. Огйп8 !пчапапгз: А Меч Б!гаге8у Гог Сопе!агег! Оцепез // Ргос. 1998 АСМ ЯОМОО! п1. СопГ. оп Мапайепзепг о1 Оага.
— Беап]е, Фазй., )цпе, 1998. Еще одна статья об оптимизации запросов, в том числе подчиненных запросов в стиле языка БЯЬ. 17.4б.%апеп О.Н.О. Ей)с[ел! Ргосезз1п8 ор !пзегасйке Ке!айопа! Оа!аЬазе Яцепез Ехргеззед 1п Ьо81с 0 Ргос. 71Ь 1пгегп. СопГ. оп Чегу Ьагйе Васа Вазез. — Саппез, Ргапсе, БергещЬег, 1981. Представлен взгляд на оптимизацию запросов с точки зрения формальной логики. Описаны приемы, которые используются в экспериментальной СУБД, для формулировки запросов применяющей язык Рго1ой.
Создавая впечатление, что эти приемы очень похожи на приемы, используемые в системе Буз1еш К, хотя разработаны они были совершенно независимо и с несколько отличными целями. В работе указывается, что в отличие от обычных языков запросов, таких как ЯОЕЬ и БОЬ, языки, основанные на логике (подобные языку Рго!о8), позволяют записывать запросы так, чтобы выдели~ь следующее: т логические цели, которые являются основными компонентами запроса; И логические переменные, связывающие эти компоненты; б84 Часть ]г.
дополнительные аспекты ° порядок достижения логических целей, который является критическим моментом с точки зрения реализации. Из этого следует, что подобные языки весьма удобны в качестве базы для выпол- пения оптимизации. Действительно, такой язык можно рассматривать в качестве еще одного кандидата для внутреннего представления запроса, исходно сформулированного с помощью какого-либо другого языка (см. раздел 17.3). 17.47.1оапп[б!з т'.Е., %оп8 Е.
Ооегу Орйпнгагюп Ьу Б!пш!агеб Аппеа11п8 ц Ргос. 1987 АСМ Б!СМОР 1пгегп. Сопб оп Мапайешеп! о( Рага. — Бап Ргапсйсо, Са!1г"., Мау, 1987. С увеличением числа отношений, используемых в запросе, количество возможных пла- нов выполнения этого запроса растет экспоненцнально. В традиционных коммерческих приложениях число отношений в запросе обычно невелико и, следовательно, количество потенциальных планов выполнения запроса (" пространство поиска") остается в разумных пределах. Тем не менее в современных приложениях количество отношений в запросе может быть достаточно большим (примеры приводятся в главе 21).
Более того, в приложениях нового типа ощущается необходимость "глобальной" (т.е. для многих запросов) оптимизации [! 7.49] и поддержки рекурсивных запросов. Эти функции также значительно увеличивают пространство поиска. Исчерпывающий поиск в таких условиях становится неэффективным, и возникает настоятельная необходимость в использовании методов сужения пространства поиска. В публикации содержатся ссылки на более ранние работы по проблеме оптимизации запросов с большим количеством отношений и многозапросной оптимизации.
Однако в данной работе утверждается, что для оптимизации рекурсивных запросов не разработано ни одного алгоритма, после чего приводится алгоритм, который, как утверждают авторы, применим даже на пространствах поиска большого размера. В частности, показано, как применять предложенный алгоритм в случае рекурсивных запросов. Данный алгоритм (называемый "модельным отжигом", так как он моделирует процесс отжига, с помощью которого выращивают кристаллы, сна- чача прогревая жидкий раствор, а затем постепенно охлаждая его) является высо- коэффективным алгоритмом, который может успешно применяться для решения проблемы оптимизации в других контекстах. См.
также [17.48). 17.48.8зтащ1 А., Оорга А. Орпппяайоп о( 1.агйе )о1п Ооег1ез Р Ргос. 1988 АСМ ЫОМОР 1п!егп. Сопб оп Мапа8ещеп! о( Рага. — СЬ!сайо, П1., )опе, 1988. Общая проблема определения оптимального порядка выполнения соединений в запросах, использующих большое количество отношений (что характерно для дедуктивных баз данных, описываемых в главе 23), является комбинаторно сложной. В работе представлен сравнительный анализ нескольких алгоритмов, предназначенных для решения этой проблемы: возмущенный обход, псевдослучайная генерация данных, последовательные улучшения, последовательные эвристики и модельный отжиг [17.47[ (названия методов добавляют немного "поэзии" в предмет обсуждения, который выглядит достаточно прозаично).
Согласно результатам проведенного анализа алгоритм последовательных улучшений превосходит все остальные азгоритмы, в частности алгоритм модельного отжига "сам по себе" нельзя использовать для больших запросов-соединений. 17.49.8еП!з Т.К. Мо!йр!е-()вегу Орг(пиза!юп 0 АСМ ТОРЫ вЂ” МагсЬ, 1988. — ! 3, № 1. Глава 17. Оптимизация б85 Классическое исследование оптимизации, в котором автор сосредоточился на проблеме оптимизации отдельных изолированных реляционных выражений. В будущем, однако, возможность оптимизации нескольких отдельных запросов, как одного модуля, станет, вероятно, весьма важной. Одной из причин такого состояния дел стало то, что единственный запушенный запрос на верхнем уровне может быть преобразован в несколько запросов на реляционном уровне. В работе приведен следующий пример.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
