Введение в системы БД (542480), страница 170
Текст из файла (страница 170)
17.7). Другими словами, количество операций чтения страниц составит (я/рК) + (и/рЯ). Из этого можно сделать следующие заключения. ° Физическая кластеризация логически связанных данных является одним из важнейших факторов, влияющих на производительность системы, т.е. в высшей степени желательно проводить кластеризацию данных так. чтобы они соответствовали соединениям, наиболее важным для предприятия (! 7.9). ° Если подобная кластеризация отсутствует, то хорошей идеей может быть сортировка непосредственно во время выполнения запроса какого-то одного или обоих отношений произвольным способом с последующим соединением методом слияния. (Безусловно, назначение подобной сортировки состоит в динамическом создании требуемой кластеризации.) На этот метод обычно ссылаются, что вполне логично, как на метод сортировки-слияния (17.10).
Более подробно эта тема обсуждается в [17.35). 662 Часп1ь и дополнительные аспекты /" Кортежи обоих отношений, К и Я, хранятся в последовательности /* значений атрибута С. /ь Здесь приведен код для соединения типа "многие ко многим", */ /ь пример для соединения типа "многие к одному" оставлен */ /* в качестве упражнения для читателя. */ г:= 1; в:= 1; сто зчЫ)е г < ш апс1 в < и; /* Внешний цикл ь/ ч:= В[г).С; с1о ):= в Ьу 1 зчЫ1е Я[Ц.С < ч; епд; в:= ) до 1:= а Ьу 1 зчЫ1е Я[Ц.С = ч; до 1:= г Ьу 1 знЫ1е К[Ц.С = ч; <к результату добавить соединенный кортеж К[1] * Я[Ц> д; епд; в:= ) с1о 1:= г Ьу 1 ьеЫ!е К[Ц.С = ч; епд; г:=1; епд; /ь Внутренний цикл */ Рис. /7.
7. Метод слияния (для соединений тпио ".многие ко многим "1 Хеширование Как и метод слияния, метод хеширования позволяет обойтись одним проходом для каждого из двух соединяемых отношений (рис. 17.8). В результате первого прохода строится хештаблица лля отношения Я по значениям атрибута Я.С. Записи в этой таблице содержат значение соединяемого атрибута (а также, возможно, значения других атрибутов отношения Я) и указатель на соответствуюший кортеж. Во время в~араго прохода сканируются кортежи от.- ношения й и вычисляется та же хеш-функция лля значений соединяемого атрибута й.С.
Когда по вычисленному для кортежа отношения й значению хеш-функции в хеш-таблице обнаруживается один или несколько соответствующих ему кортежей отношения Я, алгоритм проверяет, действительно ли равны значения й. С и Я. С, и, если это так, генерируешься кортеж (или кортежи) результируюшего соединения. Основным преимушеством данного метода по сравнению с мезодом слияния является то, что отношения й и Я можно храпнуть в произвольной последовательности, а значит, не требуется предварительно сортировать. Как и в случае метода поиска по хеш-таблице, вывод оценок затрат, связанных с использованиел1 хеширования, оставлен в качестве упражнения для читателя. 17.8.
Резюме ббЗ Глава 17. Оптильизаг(ия Эта глава начинается с утверждения, что для реляционных систем оптимизация является как иробзечой, так и благоирияиьной возчолсносьиью. Фактически оптимизация является сильной стороной таких систеяй причем по целому ряду причин. Реляционная система с хорошим оптимизатором будет функционировать намного лучше, чем не реля- ционная. Приведенный вступительный пример дает ясное предо~веление о тех поразительных результатах, которых можно достичь благодаря оптимизации (иногда эффективность выполнения запроса повышается в соотношении 10 000:1). Рис.
! 7.8. Метод хемировииия Процесс оптимизации в общем случае включает четыре последовательные стадии. ° Представление запроса во внутренней форме (обычно это дерево запроса или абстрактное синтаксическое дерево, однако подобные представления вполне можно рассматривать как специфическую внутреннюю форму для выражений реляционной алгебры или реляционного исчисления). ° Преобразование в каноническую форму с помощью различных законов преоб- разования. ° Выбор подходящих случаю низкоуровневых процедур реализации различных операторов в каноническом предо~велении запроса.
° Генерация планов запроса и выбор плана с наименьшими затратами, оцениваемы- ми с помощью формул стоимости и статистических показателей базы данных. Далее обсуждались общие законы распределения, коммутативности и ассоциативности и их применение к реляционным операторам, таким как соединение. Кроме того, рассматривалось применение этих законов к арифметическим и логическим операторам, а также к операторам сравнения. Затрагивался и другой общий закон — идемпотентности. Затем обсуждались некоторые специальные преобразования опера~оров проекции и выборки. После этого была представлена идея семантической оптимизации, т.е.
преобразования запросов, которое базируется на знании системой установленных ограничений целостности. В демонстрационных целях был сделан беглый очерк с~атис~ических показателей базы данных, используемых в СУБД 1)В2 и 1ХСэйЕБ. Далее обсуждалась одна из стратегий, построенных по принципу "разделяй и властвуй", — декомпозиция запросов, впервые реализованная в прототипе системы 1ХШЕБ. Было также отмечено, что стра~егин, построенные по принципу "разделяй и властвуй", весьма привлекательны для сред с поддержкой параллельных вычислений и распределенных систем.
И наконец, рассматривались некоторые методы реализации отдельных реляционных опера~оров, в час~ности оператора соединения. Был представлен псевдокод алгоритмов для пяти методов выполнения операции соединения: метода последовательного просмотря, поиска по индексу, поиска по хеш-таблице, метода слияния (включая метод сортировки-слияния) и метода хеширования. Также красько рассматривались стоимостные характеристики описанных методов. бб4 Часть К. Дополнительные аспекты В заключение хотелось бы отметить, что, к сожалению, многие современные программные продукты содержат некоторые замедлители оптимизации, о которых пользователь должен по крайней мере знать (даже если с этим ничего нельзя поделать).
Замедлнтель оптимизации — это функция СУБД, не позволяющая оптимизатору выполнять свою работу так, как она могла бы быть выполнена (например, при отсутствии данной функции). К замедлителям оптимизации можно, например, отнести возможность вставки в таблицу записей-дубликатов !5.6), трехзначную логику (глава 18) и реализацию трелзначнойлогики вязыке 3( И [!8.6], (18.!О]. Упражнения 1?.1. Одни пары выражений в кон~скоте базы данных поставщиков, деталей и проектов эквивалентны, а другие — нет.
Какие пары выражений действительно эквивалентны? а1) Б 001Ы ( ( Р Ю01Ы Ю ) ИНЕКЕ С1ТХ = 'Ьопдоп' а2) ( Р ИНЕКЕ СПХ = 'Ьопдоп' ) Л01Ы ( Ю 101Н Я ) б!) ( Я ИТЫОЯ ( ( Я ТОРЫ ЯРТ ] ИНЕКЕ Р$ = Р$ ( 'Рг' ] ] ( 3$, ЯЫАИЕ, ЯТАТОЯ, С1ТХ ) ) ( Я$, С1ТХ ) б2) Я ( 3$, СПХ ) И1НОЯ ( Я ( 3$, С1ТХ ) Т01Ы ( ЯРТ ИНЕКЕ Р$ = Р$ ( 'Рг' ] ) ) ( 3$, С1ТХ ) в1) ( Я ( СТТХ ) ИТЫОЯ Р ( С1ТХ ) ) ИТЫОЯ Ю ( С1ТХ ) в2) ( Я ( С1ТХ ) ИТЫОЯ,Т ( С1ТХ ) ) М1ЫОЯ ( Р ( С1ТХ ) М1ЫОЯ Ю ( С1ТХ ) ) г!) ( Ю ( С1ТХ ) 1ЫТЕКЯЕСТ Р ( С1ТХ ) ) БЫТОМ ( Я ( С1ТХ ) ) г2) Ю ( С1ТХ ) 1ЫТЕКЯЕСТ ( Я ( С1ТХ ) ОЫ10Ы Р ( С1ТХ ) ) д!] ( ( БИ ИНЕКЕ Я$ = 3$ ( 31' ) ) СЫТОМ ( ЯРЮ ИНЕКЕ Р$ = Р$ ( 'Р1' ) ) ) 1ЫТЕКЯЕСТ ( ( ЯРЯ ИНЕКЕ Л$ = Т$ ( 'Т1' ) ) ОН10Ы ( ЯРЮ ИНЕКЕ 3$ = 3$ ( '31' ) ) ) д2) ( ЯРТ ИНЕКЕ 3$ = 3$ ( '31' ) ) ОЫ10Ы ( ( ЯРЛ ИНЕКЕ Р$ = Р$ ( 'Р1' ) ) 1ЫТЕКЯЕСТ ( ЯРТ ИНЕКЕ Ю$ = 1$ ( 'Ю!' ) ) ) е!) ( Я ИНЕКЕ С1ТХ = 'Ьопдоп' ) ОЫ10Ы ( Я ИНЕКЕ ЯТАТОЯ > 10 ) е2) Я ИНЕКЕ С1ТХ = 'Ьопдоп' АЫО БТАТОЯ > 10 ж1) ( Я ( 3$ ) 1ЫТЕКБЕСТ ( ЯРЮ ИНЕКЕ Ю$ = 0$ ( 'Ю!' ) ) ( 3$ ) ) ОЫ10Ы ( Я ИНЕКЕ С1ТХ = 'Ьопдоп' ) ( 3$ ж2) Я ( 3$ ) 1ЫТЕКЯЕСТ ( ( ЯРЗ ИНЕКЕ 3$ = 0$ ( 'Ю1' ) ) ( 3$ ) ) ОЫ10Ы ( Я ИНЕКЕ С1ТХ = 'Ьопдоп' ) ( 3$ ) ) з1) ( ЯРЛ ИНЕКЕ 1$ = Л$ ( 'Ю!' ) ) ( 3$ ) И1ЫОЯ ( БРЮ ИНЕКЕ Р$ = Р$ ( 'Р1' ] ) ( Я$ 665 Глава 17.
Оппгимизат(ия а) А ОИ10И ( А 1ИТЕЙЯЕСТ В ) ж А; б) А 1ИТЕНЯЕСТ ( А ОИ10И В ) и А, 17.8. 17.9. 17.10.Распространите ответ на предыдущее упражнение, включив в сферу его действия условия, в которых используются кванторы ЕХ1ЯТЯ и ГОВАЬЬ. Примером может служить правило, изложенное в главе 7, и позволяющее преобразовать выражения, использующие квантор РОНАьь, в выражения с отрицаемым квантором ЕХ1ЯТЯ. 17.11.Ниже перечислены ограничения целое~ности для базы данных поставщиков, дета- 666 Часть (г. дополнительные аспекты 17.2. 17.3. 17.4. 17.5. 17.6. 17.7.
з2) ( ( ЯРТ ИНЕВЕ З( = З( ( 'Ю1' ) ) М1ИОЯ ( ЯРЮ ИНЕЙЕ Р( = Р() ( 'Р!' ) ) ) ( Я1 и!) Я 20!И ( Р ( СТТ1 ) М1ИОЯ Ю ( 0171 ) ) и2) ( Я Ю01И Р ( С1ТХ ) ) М1ИОЯ ( Я Ю01И Ю ( С!ТУ ) ) Докажите, что операции соелинения, объелинения и пересечения являются коммутагивными, а операция вычитания — нет. Докажите, что операции соединения, объединения и пересечения являются ассоциативными, а операция вычитания — нет. Докажите, что: а) объединение распределяется по пересечению; б) пересечение распределяется по объединению.
Докажите, что для всех А и В: Замечание. Эти два закона называются законами поглощения. Как и законы илемпотентности, коммутативности и т.д.„они могут оказаться полезными при проведении оптимизации. Докажите следующее. а) Выборка безусловно распределяема по объелииеиию, пересечению и вычитанию и условно распределяема по соединению. б) Проекция безусловно распределяема по объединению и пересечению, условно распределяема по соединению и не распределяема по вычитанию.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
