Введение в системы БД (542480), страница 171
Текст из файла (страница 171)
Запишите соответствующие критерии для условной распределяемости. Распрос~раните правила преобразования, изложенные в разлеле )7.4, так, чтобы учитывались операторы ЕХТЕИО и ЯОММАВ1ХЕ. Можно ли сформулировать какие-либо полезные правила преобразований для опе- рации реляционного деления? Запишите соответствующий набор правил преобразования для условий, в которых используются операторы АИО, ОВ и ИОТ. Примером таких правил может служи~ь за- кон коммутативности для оператора АИО, т.е.
утверждение, что выражение А АИО В тождественно выражению В АИО А. лей и проектов. ° Допустимыми городами являются Лондон ('Болг)оп'), Париж ('Раг1в'), Рим ('Нове'), Афины ('Аслепв'), Осло ('Ов!о'), Стокгольм ('ЯсосХЬо!л'), Мадрид ('Масут!б') и Амстердам ('Алвсегдаж'). ° Никакие лва проекта не могут быть размещены в одном и том же городе.
° В любой момент в Афинах может находиться не более одного поставщика. ° Ни одна поставка по количеству не может превышать удвоенное среднее значение количества по всем поставкам. ° Поставшик с наибольшим статусом не может находиться в одном городе с поставщиком с наименьшим статусом. ° Каждый проект должен находи~ься в городе, в котором есть хотя бы один поставщик этого проекта. ° Должна существовать по крайней мере одна красная деталь. ° Среднее значение статуса поставщика должно быть больше 18. ° Каждый поставшик из Лондона должен поставлять деталь с номером 'Р2'. ° Хотя бы одна красная деталь должна весить меньше 50 фунтов.
° Поставщики из Лондона поставляют больше различных видов деталей, чем поставщики из Парижа. ° Поставшики из Лондона поставляют больше деталей (по обшему количеству), чем поставщики из Парижа. Ниже перечислены простые запросы к этой базе данных: а) выбрать сведения о поставшиках, которые не поставляют деталь с номером 'Р2', б) выбрать сведения о поставшиках, которые не поставляют детали для какого- либо проекта в том же городе, где они находятся; в) выбрать сведения о таких поставшиках, для которых не существует других поставщиков, поставляющих меньше видов деталей; г) выбрать сведения о поставшиках из Осло, которые поставляют по крайней мере два разных вида деталей из Парижа для по крайней мере двух разных проектов в Стокгольме; д) выбрать сведения о парах поставщиков из одного города, поставляющих пары деталей из одного и того же города; е) выбрать сведения о парах поставшиков из одного города, поставляющих детали парам проектов, находяшихся в одном городе; ж) выбрать сведения о деталях, поставляемых хотя бы лля одного проекта, но только теми поставшиками, которые размешены не в том городе, где находится сам проект; з) выбрать сведения о посгавшиках наибольшего количества различных типов деталей, Используйте приведенные выше ограничения целостности для преобразования данных запросов в более простую форму (но все еше на обычном языке — от вас не требуется выполнять это упражнение форивльно).
17.12.Исследуйте доступную вам СУБД. Выполняе~ ли эта система преобразование выражений (сейчас это делают не все СУБД)? Если это так, то какие выполняются преобразования? 17.!З.Попробуйте провести следующий эксперимент. Возьмите простой запрос, например "Выбрать имена поставшиков летали с номером 'Р2'", и запишите его всеми известными вам способами с помощью любого лоступного языка запросов (возможно, это будет язык Б( Н.).
Создай~с и заполните данными подходящую тестовую базу данных, выполните все версии запроса и определи~с время выполнения каждой версии. Если полученные значения будут сильно различаться, значит, экспериментально доказано, Глава 17. Оптимизация 667 что оптимизатор системы не полностью справляется с задачей преобразования выражений.
Повторите этот эксперимент с различными исходными запросами. Если возможно, повторите этот же эксперимен~ в разных СУБД. Замечание. Безусловно, разные версии запроса должны давать идентичные результаты. Если же результа~ы различаю~ся, то, возможно, вы совершили ошибку или ошибка существует в оптимизаторе рассматриваемой СУБД.
Если обнаружена ошибка в оптимизаторе, сообщите об этом разработчику СУБД! 17.14.Исследуйте любую доступную вам СУБД. Поддерживает лн она какие-либо статистические показатели базы данных (это делаю~ не все СУБД)? И если поддерживает, то какие именно? Как эти статистические показатели обновляются — динамически или с помощью какой-либо утилиты? Если статистические показатели обновляются с помощью утилиты, то как называется утилита и как часто она запускается? Насколько выборочно ее действие (в том смысле, что при запуске утилиты со специфическими параметрами обновляется только определенная статистика)? 17.15. В разделе 17.5 было сказано, что в состав статистических показателей, поддерживаемых СУБД ОВ2, входят второе наибольшее и второе наименьшее значения каждого столбца в каждой базовой таблице.
Почему выбраны именно вторые значения? 17.1б.В некоторых коммерческих продуктах пользователю разрешается создавать указатели для оптимизатора. Например, в СУБД ОВ2 спецификация ОР?1Н1ЕЕ РОЕ л ЕОЕЯ в объявлении 5( (.-курсора означает, что пользователь предполагает извлечь с помощью данного курсора не более л строк (т.е. оператор РЕРСН будет выполнен для данного курсора не более л раз).
Такая спецификация иногда может позволить оптимизатору выбрать более эффективный путь доступа, по крайней мере в случае, когда пользователь действительно выполняет оператор РЕТСН не более л раз. Оправдано ли, по вашему мнению, применение таких указателей? Обоснуйте свой ответ. 17.17.разработайте набор процедур реализации для операций выборки и проекции (руководствуясь приведенными в разделе 17.7 псевдокодами процедур для операции соединения). Выведите соответствующий набор формул стоимости для этих процедур, предположив, что в данном случае нас интересует только количество операций ввода-вывода (т.е.
не пытайтесь учесть в своих формулах степень загрузки процессора и других компонентов системы). Запишите и докажите любые утверждения, принятые в процессе вывода этих формул. Список литературы Оптимизация представляет собой чрезвычайно большую и постоянно развивающуюся область исследований. Важность этих исследований становится значительнее, чем когда-либо прежде в связи с все возрастающим интересом к системам поддержки принятия решений, речь о которых пойдет в главе 21. Достаточно сказать, что за последние несколько лет около 5051 докладов на ежегодных конференциях АСМ 51ОМОР в той или иной мере были посвящены именно вопросам оптимизации. Приведенный ниже список предо~валяет собой относительно небольшую выборку из обширной литературы по оптимизации и связанным с ней вопросам.
Условно он разбит на следующие группы. ° В 117.11 — [17.71 содержится обзор общих проблем оптимизации или введение в эту тему. 668 Часть р. дополнительные аспекты ° В [17.8] — [!7.17] рассматриваются эффективные методы реализации отдельных реляционных операций, таких как соединение и обобщение. ° В [17.18] — [17.33] представлены различные приемы преобразования выражений, описанные в разделе 17.4. В частности в [17.27]-[17.30] рассматриваются семантические преобразования. ° В [17.34] — [17.45] обсужлаются приемы, использованные в Бумеш В, СУБД РВ2 и СУБД 1)чОКЕБ, а также общая проблема оптимизации вложенных запросов в стиле языка Я Н.. ° В [17.46]-[17.61] содержится описание многочисленных приемов, хитростей и идей, подлежащих исследованию в будущем, и т.п. В частности, в [17.58]— [! 7.61] рассмотрено влияние параллельной обработки на вопросы оптимизации.
Замечание. Публикации, в которых рассматривается оптимизация в распределенных системах, умышленно исключены из данного списка (см. главу 20). Кпп Чч'., Ке]пег О.Б., Вагогу Р.Б. (ебз.). Оцегу Ргосезгйп8 1и ОагаЪазе Бумегпз.— Ь1езч Уог1с, Ь1.У.: Брппйег-Чег!а8, 1985. Это антология работ, посвященных общим проблемам обработки запросов (не только по оптимизации). Книга состоит из вступительного обозрения Джарка ()агке), Коха (Коей) и Шмидта (БсЬш161), которое перекликается с публикацией [17.3], но не повторяет ее.
Далее следуют работы, описывающие обработку запросов в различных контекстах; распределенные базы данных, гетерогенные СУБД, проблемы обновления представлений (работа [9.11] является одной из статей в этом разделе), нетрадиционные приложения (например, САП/САМ), оптимизация многооператорных запросов [17.49], машины баз данных и физическое проектирование базы данных. Брес(а!! ззце оп Овесу Орйш(аайоп I/1ЕЕЕ ОащЬазе Епй. — Яер1ешЬег, 1982. — 5, № 3. Это сборник из ! 3 коротких статей (академического и коммерческого направлений), в которых описываются различные аспекты оптимизации запросов. 17.1. 17.2.
)аг1ге М., Коей 1. Оцегу Орйпнкабоп 1п РагаЬазе Бузгешз /! АСМ Сощр. Бцгч.— )цпе, 1984. — 16, № 2. Отличное учебное пособие. Включает обобщенную систему взглядов по проблеме вычисления запросов, подобную представленной в разделе 17.3 данной главы, но базирующуюся на реляционном исчислении, а не на алгебре. После этого в рамках описанной системы взглядов обсуждается множество приемов оптимизации: синтаксические и семантические преобразования, низкоуровневые операции реализации и алгоритмы генерации планов запроса и выбора плана с наименьшей стоимостью.
Приводится также обширный набор правил синтаксических преобразований. Имеется достаточно большой список литературы (без аннотаций). Заметьте, однако, что после 1984 года по данной теме было опубликовано на порядок больше работ, чем до 1984 года [17.4]. В работе также кратко обсуждаются другие смежные проблемы, такие как оптимизация высокоуровневых языков запросов (т.е. языков, более мощных по сравнению с реляционной алгеброй или исчислением) и оптимизация в распределенных базах данных.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
