8.11.2. Некоторые тривиальные законы

Разумеется, мы не собираемся подтверждать или опровергать справедливость каж­дого закона реляционной алгебры. Тем не менее читатель должен быть осведомлен, в частности, о действии законов в некоторых "экстремальных" случаях: примерами могут служить применение оператора к пустому множеству, использование опера­торов выбора или тета-соединения с условием, которое всегда истинно или всегда ложно, или проекция отношения на список всех атрибутов. Вот несколько из многих возможных вариантов законов для частных случаев:

результат операции выбора из пустого отношения является пустым отношением;

если некоторое условие С справедливо всегда (скажем, x>10 or x≤10 для отно­шения, где x is not null), тогда σ_C(R) = R;

если R = , то R S = S.

8.11.3. Законы проекции

Операторы проекции (projection), как и операторы выбора, допускают возможность "продвижения" вниз по дереву выражений. Продви­жение операторов проекции, однако, отличается от перемещения операторов выбора тем, что зачастую первые остаются на месте, а где-либо "ниже" в дереве создаются вершины, отвечающие новым операторам проекции.

Техника продвижения операторов проекции довольно полезна, хотя и не в такой степени, как перемещение операторов выбора. Причина очевидна: применение опера­торов выбора часто приводит к многократному снижению количества кортежей отно­шения, но оператор проекции, не влияя на число кортежей, только уменьшает их длину. Более того, при использовании оператора расширенной проекции (extended projection) длина кортежей на самом деле способна даже возрасти.

Для описания алгебраических законов расширенной проекции нам понадобятся некоторые новые термины. Рассмотрим элемент E x списка проекции, где E представляет собой атрибут или выражение, состоящее из атрибутов и констант. Все атри­буты, упомянутые в составе Е, мы будем называть входными (input), а атрибут x — вы­ходным (output). Если элемент списка является отдельным атрибутом, такой атрибут будет одновременно входным и выходным. Заметим, что иные формы выражений без стрелки и переименования, отличные от представления отдельного атрибута, недопус­тимы — это позволяет охватить все возможные случаи.

Если список проекции состоит только из отдельных атрибутов и не включает эле­менты со стрелками и иные выражения, такую проекцию мы будем называть простой (simple). Все операторы проекции, рассматриваемые в рамках классической реляци­онной алгебры, являются простыми.

Пример. Оператор проекции π_а,b,c(R) относится к категории простых — атрибуты а, b и с являются одновременно входными и выходными. С другой стороны, оператор π_{а+b x,c}(R) нельзя считать простым; а, b и с служат входными , а x и с — выходными атрибутами.

Основной принцип, лежащий в основе законов проекции, таков:

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

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

π_L(R S)= π_L(π_M(R) π_N(S)), где М— список всех атрибутов R, которые являются либо общими атрибутами R и S, либо входными атрибутами L, а N — список атрибутов S, принадлежащих либо к числу общих атрибутов R и S, либо к категории входных атрибутов L.

π_L(R S)= π_L(π_M(R) π_N(S)), где М— список всех атрибутов R, которые являются либо атрибутами тета-соединения R и S, упомянутыми в условии С, либо входными атрибутами L, а N — список атрибутов S, принадлежащих либо к числу атрибутов тета-соединения R и S, либо к категории входных атрибутов L.

π_L(R×S)= π_L(π_M(R)×π_N(S)), где М и N — списки всех атрибутов R и S соответственно, являющихся входными атрибутами L.

Пример. Рассмотрим отношения R(a, b, с), S(c, d, e) и выражение π_{a+e x, b y}(R S). Входные атрибуты проекции — а, b и e, а с — единственный об­щий атрибут соединяемых отношений R и S. На основании соответствующего закона имеем право применить к отношениям R и S (аргументам соединения) операторы проекции со списками, учитывающими номенклатуру атрибутов R и S:

π_{a+e x, b y}(π_a,b,c(R) π_c,e(S)).

Заметьте, что оператор π_a,b,c(R) тривиален — он выполняет проекцию на все атрибуты отношения R. Удаление этого оператора приводит к третьей эквивалентной форме вы­ражения, π_{a+e x, b y}(R π_c,e(S)), которая отличается от исходной тем, что предполагает удаление атрибута d отношения S непосредственно перед выполнением соединения.

Помимо того, допустимо заменять проекцию "мультимножественной" версии объ­единения отношений объединением отношений-проекций:

π_L(R S)=π_L(R) π_L(S).

Аналогичные преобразования операций объединения множеств, а также пересечения и разности (в версиях для множеств и мультимножеств), напротив, применять нельзя.

Пример. Допустим, что отношение R(a,b) содержит единственный кортеж {(1,2)}, а отношение S(a, b) — единственный кортеж {(1,3)}. Тогда

π_a(R S)= π_a( )= . Однако

π_a(R) π_a(S)={(1)} {(1)}= {(1)}.

Если проецирование сопряжено с выполнением определенных вычислений и входные атрибуты некоторого элемента списка проекции целиком принадлежат од­ному из аргументов оператора соединения (или декартова произведения), служащего операндом проекции, есть возможность (но не обязанность) осуществить вычисления непосредственно над аргументом. Проиллюстрируем сказанное примером.

Пример. Вновь обратимся к отношениям R(a,b,c), S(c,d,e) и рассмотрим следую­щую операцию проекции, применяемую к результату соединения:

π_{a+b x, d+c} (R S).

Допустимо применить операции суммирования а + b и переименования суммы в x непо­средственно к отношению R, а аналогичные операции получения суммы d + e и ее пере­именования в у — к отношению S. Эквивалентное выражение примет вид

π_x,y(π_{a+b x,c}(R) π_{d+e y,c}(S)).

Один из заслуживающих внимания частных случаев связан с совпадением с с х или у. В подобной ситуации переименовать сумму в с нельзя, поскольку отношение не мо­жет иметь два атрибута с именем с. Поэтому следует воспользоваться новым времен­ным именем и выполнить соответствующее переименование в условии "внешнего" оператора проекции. Например, выражение π_{a+b c,d+e y}(R S) в преобразованном виде можно было бы записать как π_{z c,y}(π_{a+b z,c}(R) π_{d+e y,c}(S)).

Допустимо также применение нового оператора проекции к аргументу "внутреннего" оператора выбора.

π_L(σ_C(R))= π_L(σ_C(π_M(R))),

где М— список всех атрибутов, которые либо являются входными атрибутами из списка L, либо упоминаются в условии С.

Как и в примере, имеется возможность выполнения вычислений над списком М вместо L — при условии, что в С не упоминаются входные атрибуты из L, вовлечен­ные в процесс вычислений.

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

Пример. Рассмотрим запрос, обращаемый к отношению

StarsIn (movieTitle, movieYear, starName) и предполагающий отыскание све­дений об актерах, которые снимались в фильмах, вышедших на экраны в 1996 году:

SELECT starName

FROM StarsIn

WHERE movieYear = 1996;

Результат прямой трансляции запроса в логический план показан на рис. 23.

Перед выполнением операции выбора можно осуществить операцию проекции на следующие атрибуты:

1) starName — требуемый для включения в схему итогового отношения;

2) movieYear — необходимый для условия выбора.

Если бы отношение starsln было не хранимой таблицей, а результатом другой опе­рации, такой как соединение, план, представленный на рисунке 8.11, имел бы очевидный смысл: нам удалось бы передавать результат проекции по "каналу" (pipeline) по мере генерирования кортежей в процессе соединения, опуская "лишний" атрибут movieTitle. Однако starsin является храни­мым отношением. Применение оператора проекции π_{starName, movieYear} действительности способно повлечь необоснованные затраты времени, особенно в том случае, если атри­бут movieYear снабжен индексом. В физическом плане, сконструированном на основе исходного логического плана на рисунке 8.11, напротив, тот же индекс удалось бы исполь­зовать для выбора только таких кортежей starsin (их наверняка оказалось бы не мно­го), значения компонентов movieYear которых равны 1996. Но если первой выполнять операцию проекции (как на рисунке 8.12), придется считывать (а затем проецировать) каждый кортеж starsIn. Что еще хуже, индекс, созданный для атрибута movieYear отношения starsin, окажется абсолютно бесполезным при работе с совершенно другим отношением π_{starName, movieYear}(StarsIn), так что для выполнения оператора выбора придется применять полномасштабное сканирование всех кортежей результата "вредоносной" проекции.

π_starName

σ_{movieYear= 1996}

Starsin

Рис. 8.11 - Логический план запроса к примеру

π_starName

σ_{movieYear= 1996}

π_{starName, movieYear}

Starsin

Рис. 8.12 - Результат добавления оператора проекции