Введение в системы БД (542480), страница 174
Текст из файла (страница 174)
"Волшебный" подход исключает оба нежелательных варианта, повторное вычисление средней зарплаты и обработку не относящихся к запросу кортежей за счет генерации "вспомогательных" отношений. /* Первое вспомогательное отношение: '/ /' Имена, отделы и зарплата клерков "/ Т1 := ( ЕМР.ЕМАМЕ, ЕМР.ОЕРТ)), ЕМР.ЯАЬ ) МНЕНЕ ЕМР,ЗОВ = 'С1егй' ) /* Второе вспомогательное отношение: */ /* Отделы, в которых работают клерки «/ Т2 := Т!.ОЕРТ() /« Третье вспомогательное отношение: «/ /« Отделы, в которых работают клерки, '/ /« и средняя зарплата для каждого отдела '/ ТЗ := ( Т2.РЕРТ(), АЧО ( ЕМР ННЕНЕ ЕМР.РЕРТ() = Т2.0ЕРТ(), БАР ) йЯ АВАР ) ) /' Отношение-результат "/ Н := Т!.ЕНАМЕ МНЕНЕ ЕХ1ЯТЯ ТЗ ( Т!.ОЕРТ() = ТЗ.РЕРТ)) АМО Т!.ЯАР > ТЗ.АНАР 676 Часть Р'. Дополнительные аспекты "Волшебство" состоит в том, чтобы определить, какие именно вспомогательные отношения требуется создать.
(См. [17.25), [! 7.26), а также список литературы в главе 23.) 17.25.Миш!с)» 1.5., Р[гайезй Н. 1гпр!егпеп»абоп о( Марс»п 5»агЬцгз» // Ргос. !990 АСМ 5!ОМОВ 1п». Соп( оп Мапайетеп» Оа»а. — М(ппеаро!1з, Мшп., Мау, 1994. 17.26.Мшп!сй!.5., Г!п1»е1где!и 5.1., Р!гайезЬ Н., Кагпа!»г!зЬпап К. Марс Соп»!1»1опз // АСМ ТОР5.
— Магсй, 1996. — 21, №! . 17.27.К!п8 1.1. О(/15Т: А 5уьзегп Гог 5егпапбс Оцегу Ор»[гп!га»!оп 1п Ке!а»!опа1 Оа»аЬазез // Ргос. 7»Ь!п»егп, Соп(. оп Чету 1 агйе Оа»а Вазез. — Саппез, Ггапсе, 5ер»егпЬег, 1981. Представлена идея семантической оптимизации (см. раздел 17.4). В статье описана эксперил»ентальная система О(315Т (О(/егу !гпрготе»пеп»»Ьгоц8Ь 5егпапбс Тгапз(оггпабоп — улучшение запросов посредством семантических преобразований), способная выполнять подобные преобразования. 17.28.
5йепоу 5.Т., Огзоуо8!н Х.М. А 5уз»егп Гог 5е»папбс ()негу Ор»!»и!га»юп // Ргос. 1987 АСМ 5!ОМОВ!п»егп. Соп( оп Мапа8етеп» о(Оа»а. — 5ап Ггапсйсо, СаЫ., Мау-/шпе, 1987. Эта публикация расширяет работу Кинга (К»п8) [17.27), представляя схему, которая динамически выбирает из потенциально очень большого множества ограничений целостности только те ограничения, которые будут полезны для обработки данного запроса. Рассматриваемые ограничения целостности разделены на два типа: ограничения причастности (например, "если партия деталей содержит более 300 единиц, то поставшик должен находиться в Лондоне*') и ограничения поди»»ожеств (например, "каждый поставщик, находящийся в Лондоне, должен поставлять хотя бы одну деталь"). Подобные ограничения используются для преобразования запросов посредством исключения избыточных выборок и соединений и введения дополнительных выборок для индексированных атрибутов.
Случаи, когда результат запроса может быть получен непосредственно из ограничений целостности, также эффективно обрабатываются с помошью изложенного метода. 17.29.5!е8е! М., 5сюге Е., 5а!те»ег 5. А Ме»йо»! 1ог Ац»она»!с Кц!е Оепвабоп»о 5цррог» 5етапбс снегу Орбппхабоп // АСМ ТОО5. — ОесегпЬег, 1992. — 17, № 4. Как было показано в этой главе, семантическая оптимизация использует ограничения целостности для преобразования запросов. Тем не менее сушествует несколько проблем, связанных с этой идеей. ° Как оптимизатор может узнать, какое преобразование будет эффективным (т.е.
какое преобразование сделает запрос более эффективным)? ° Некоторые ограничения целостности не очень полезны для решения задач оптимизации. Например, ограничение, которое требует, чтобы вес детали был больше нуля, важно для целостности базы данных, но по сути бесполезно для целей оптимизации. Как оптимизатор сможет отличить полезные ограничения целостности от бесполезных? ° Некоторые утверждения могут быть справедливы для определенных состояний базы данных (даже для большинства состояний), однако они не будут ограничениями целостности.
Примером может служить утверждение вида ЕИР.л08 < 50 (возраст сотрудников — не более 50 лет), которое не является Глава 17. Опт»с»»иза»/ия Я(! ЯТАТОБ С1ТУ Р1 СОЬОЕ а1 Ы а1 'Ьопбоп' Ы вЂ” Я (поставщики) БР (поставки) — Р (детали) Ь2 Ь2 'Кег)' представляет запрос "Выбрать статус (а1) поставщиков (Ы) в Лондоне, которые поставляют красные летали (Ь2)". Верхняя строка в табло представляет все атрибуты„которые используются в запросе, следующая строка — это "итоги" (она соответствует кортежу-прототипу в запросе, определенном в исчислении, или финальной проекции в алгебраическом запросе), а оставшиеся строки (как уже говорилось) представляют условия принадлежности.
В данном примере эти строки прокомментированы посредством указания относящихся к запросу отношений (точнее, переменных-отношений). Обратите внимание, что Ь используется для ссылок на связанные переменные, а а — для ссылки на свободную переменную. Итоговая строка содержит только переменные типа а. 67а Часть г'. Дополнительные аспекты ограничением целостности как таковым (поскольку могут быть сотрудники и старше 50 лет), но в данный момент в компании может действительно не быть сотрудников старше 50 лет. В этой публикации описана архитектура системы, учитывающей перечисленные проблемы. 17.30.СЬа!сгачаг!Ьу 1).Я., Огапс 1., М!и!сег 1.
Е.ой!с-Вазео Арргоасй го Яепзапг!с Оцегу Орйгпгдайоп П АСМ ТОРЯ. — )цпе, 1990. — 15, )зя 2. Цитата из вступления: "В нескольких предыдуших работах авторами была описана и доказана правильность метода семантической оптимизации запросов... В этой работе обобщаются основные результаты из предыдущих работ и особое внимание обращается на методы и их применимость к оптимизации реляционных запросов. Дополнительно в этой работе показано, каким образом описываемый метод подводит итоги и обобщает результаты более ранних работ в области семантической оптимизации.
[Кроме того, отмечается) как методы семантической оптимизации запросов могут быть распространены на рекурсивные запросы и ограничения целостности, содержащие дизъюнкции, отрицания и рекурсию". 17.31.АЬо А.ч'., Бай!ч У., ()!!гпап 1.Р. Е(бс!еп! Орйппкагюп о( а С!аьа оГ йе!а!!опа! Ехргеааюпз П АСМ ТОРЯ. — РесешЬег, 1979. — 4, № 4. Класс реляционных выражений, упоминаемый в заголовке этой работы, содержит выражения, использующие только операции отбора по равенству (которые в этой статье называются еыборкаии), проекции и естественного соединения.
Этот класс выражений иногда называют ЯРЛ-выражениями (от англ. "зе!ест, "рго)ес!!оп", ")о!и" — "выборка", "проекция", "соединение"). ЯР)-выражения соответствуют запросам в реляционном исчислении, в которых используются только сравнения на равенство, операции айО и кванторы ЕХ1БТЯ. В работе приводится определенный вид таблицы (табло — гаЫеац), представляющей двумерный массив, в котором столбцы соответствуют атрибутам, а строки — условиям, в частности условиям принадлежности, которые гласят, что конкретный кортеж значений принадлежит конкретному отношению. Строки табло логически связываются посредством помещения общих символов в связанные строки.
Например, табло Табло — это еше один вариант канонической формулировки для представления запросов (см. раздел 17.3), однако оно не является достаточно общим, чтобы представить все возможные реляционные запросы. (Фактически табло можно рассматривать как синтаксическую разновидность языка ()негу-Ву-Ехаюр1е (ОВЕ), хотя и менее мошную, чем непосредственно язык ОВЕ.) В работе представлены алгоритмы преобразования одного табло в другое, семантически эквивалентное табло, в котором количество строк уменьшено до минимума. Так как количество строк (не считая двух верхних специальных строк) на единицу больше количества соединений в соответствуюшем ЗР)-выражении, полученное табло представляет оптимальную форму запроса, хотя и в очень специальном смысле (минимальное количество соединений).
(В приведенном выше примере количество соединений уже минимально, поэтому подобная оптимизация не дает никакого эффекта.) После этого полученное минимальное табло можно конвертировать обратно в другое представление лля последуюшей дополнительной оптимизации. Идея минимизации количества соединений также применима к запросам, сформулированным в терминах представлений, которые построены на основе операции соединения, в частности к запросам, сформулированным в терминах "универсальных отношений" (см, список литературы в конце главы 12). Например, предположим, что пользователю предложено представление Ч, определенное как соединение отношений Б и ЯР по атрибуту И, н пользователь вводит следующий запрос, 9 ( Р1 ) Прямой алгоритм обработки представлений преобразует ланный запрос в следуюший.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
