Movie Movie

Рис. 4.7. Дерево выражений длв вырожений реляционной алгебры

Это же выражение можно представить в обычной линейной нотации со скобками, а и.менно, в В1щ.е формулы:

(f/n ,i 100 (Movie) п c , .v =w (Movie))

Часто одно и то же вычисление можно представить несколькими выражениями реляшюнной алгебры. Например, вышеприведенный запрос можно написать, заменив пересечение логической связкой AND с единственной операцией выбора:

iiengim lOOANDiiKrto.vems-Fcx (Movie)) в результате получается запрос, эквивалентный исходному. □

4.1.7 Комбинирование операций для построения запросов

Если бы в качестве запроса pa3peuiajiocb писать только единичные операции на одном или двух отношениях, от реляционной алгебры было бы мало пользы. Однако она, как и все алгебры, позволяет строить выражения произвольной сложности путем применения операторов к заданным отношениям или к отношениям, уже полученным в результате применения операторов.

Выражения реляционной алгебры можно строить, пр]1мсняя операции к подвыражениям и при необходимости выделяя скобками группы операнд. Выражения представляются в виде дерева, чтобы их легче было прочесть, хотя они меньше подходят в качестве нотации для машинного чтения.

Пример 4.10. Рассмотрим декомпозированное отношение Movie из примера 3.32. Допустим, нужно узнать названия и годы выпуска фильмов студии Fox, которые длятся более 100 мин. Это можно вычислить следующим образом.

1. Выбрать кортежи Movie, имеющие length >)00.

2. Выбрать кортежи Movie, имеющие studioNaine = foy..

3. Вычислить пересечение (1) и (2).

4. Построить проекцию отношения из пункта (3.) на атрибуты title и year.

На рис. 4.7 эти четыре шага изображены в виде дерева выражений. Два узла отбора соответствуют шагам (1) и (2). Узел пересечения соответствует шагу (3), а узел проекции шагу (4).

title.year

Эквивалентные выражения и оптимизация запросов

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

4-1.8 Переименование

Контроль за именами атрибутов, используемых в отноше1Н1ях, которые построены с помощью одной или нескольких операций реляционной атгебры, по-.пезно осугнсствлять с помощью оператора, явным образом переи.мсновываюшего oTHOHjeHHfl. Для переименования отношения R будем использовать оператор р , , j ,(/J). Результирующее отношение имеет в точности те же кортежи, чго и йс именем отношения J. Его атрибугы получают имена A.A1, ....А в порядке слева направо. Если нужно изменить только имя отношения, но не его атрибутов, люжно писать просто р.у(Л).

1 Учтите, что схема отношения Uovie того примера отличалась от р 1яивонноЙ схемы щношеиия MovjB, введенной н разделе 3.9 и использованной в примерах 4.2, 4.3 и 4.4.

Пример 4.П. Оператор натурального соединения применяется для восстановления отношений, которые были декомпозированы для приведения в BCNF. Напомним декомпозированное отношение из примера 3.32И

Moviel со схемой {title, year, length, filmType, studioName} Movle2 CO схемой {title, year, starName)

Запишем выражение для ответа на запрос: найти кинозвезд, играющих в фильмах, которые длятся больше 100 мин. Этот запрос связывает атрибут starName отношения Moviel с атрибутом length отношения Movie2. Атрибуты можно связать, соединив два данных отношения. Натуральное соединение успешно соединяет в пары только кортежи, совпадающие по атрибутам title и year, т.е. относящиеся к одному и тому же фильму. Значит, Moviel IX Movie2 - выражение реляиионной алгебры, порождающее отношение, названное Movie в примере 3.32. Оно не находится в BCNF, а его схема состоит из шести атрибутов и содержит несколько кортежей для одного и того же фильма, когда в нем играет несколько кинозвезд.

К соединению Moviel и Movie2 необходимо применить оператор отбора С условием, согласно которому длина фильма не превышает 100 мин. Затем строится проекция на требуемые множесгва атрибутов title и year. Рассматриваемый запрос принимает вид выражения реляиионной алгебры

П/мс, .v,w (сад, 100 (Moviel м Movie2)) □

Пример 4.12. В примере 4.3 мы брали произведение отношений Л и 5 из рис. 4.3 и следовали соглашению, что при появлении атрибута сразу в обеих операндах он переименовывается префиксированием ему имени отношения. Эти отношения R н S повторяются далее на рис. 4.8.

Предположим, однако, что мы не хотим называть две версии В именами KB и S.B, а хотим использовать ммя В для атрибута, происходящего из /?, и имя X для атрибута, происходящего из S. Тогда можно переименовать атрибуты S так, чтобы первый из них имел имя X. Результат выражения р.ял. с. о - это таблица с именем 5, которая выглядит точно так же, как и таблица S из рис. 4.3, но в ее перво.м столбце вместо атрибута S находится атрибут X.

Когда берется произведение Л с этой новой таблицей, конфликта и.мен атрибутов не возникает, поэтому дальнейшее переименование не производится. Таким образом результэт выражения /?х рда с и(-5) - это отношение В S ю рис. 4.3, за исключением того, что пя1Ь его столбцов отмечены буквами А В, X, С ц D слева направо. Это отношение изображено на рис. 4.8.

Отношение R

Отношение S

Результат R х pstx с. о,

Рие. 4.8. Дао отноиенин и их произведение

Можно также взять продукт без переименования, как п примере 4 5, а затем переименовать результат. Выражение pgsi/i. в. \, с. т - -5) Диет то же самое отношение, которое изображено на рис. 4.8 с тем же самым множеством атрибутов, но теперь у него нмя RS, которого не имеет результирующее отношение иа рис. 4.8. □