8.11. Законы для "множественных" и "мультимножественных" версий операторов

Пытаясь применять законы, справедливые для множеств, к отношениям-мультимножествам, следует быть особо внимательным. Приведем пример. Вам, возможно, известен так называемый дистрибутивный закон (distributive law) пересе­чения множеств, формально записываемый как .Этот закон выполняется только для множеств, но не для мультимножеств. Предпо­ложим, что каждое из мультимножеств А, В и С равно {x}. Тогда {х, х) = {х}. Но ={х, х) - это, разуме­ется, отнюдь не то же самое, что результат вычисления левой части выражения, {х}.

8.11.1. Законы выбора

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

В этом разделе мы рассмотрим алгебраические законы, касающиеся оператора σ. Для начала отметим полезность разбиения громоздких условий выбора, включающих логические операторы and или or, на составные части. Доводы в пользу подобной стратегии таковы: оператор выбора с более простым условием, охватывающим мень­шее количество атрибутов, может быть перемещен в такое место дерева, куда исход­ный оператор со сложным условием продвинуть просто нельзя. Вот как выглядят за­коны расщепления (splitting rules) условий оператора выбора:

.

.

Второй закон, регламентирующий расщепление условия с оператором OR, выполняется только в том случае, если отношение R является множеством. Если бы R оказалось мультимножеством, оператор объединения множеств осуществил бы некорректные действия по удалению дубликатов.

Заметьте, что порядок задания частных условий С₁ и С₂ несуществен. Правую часть первого из законов расщепления, например, вполне правомочно записать так: .

Если говорить в более общем смысле, допустимо задавать любой порядок перечисле­ния операторов выбора:

= .

Пример. Рассмотрим отношение R(a,b,c).

Оператор σ_{(a=1 or a=3) and b<c}(R) на основании первого закона расщепления можно преобразовать к виду σ_{a=1 or a=3}(σ_b<c(R). Далее, применив закон расщепления условий выбора, содержащих оператор or, полу­чим σ_a=1(σ_b<c(R)) σ_a=3(σ_b<c(R)).B данной ситуации кортеж не может единовре­менно удовлетворять условиям а = 1 и а = 3, и поэтому преобразование справедливо независимо от того, является R множеством или мультимножеством и используется ли для объединения оператор . В общем же случае при расщеплении условий выбора, содержащих or, требуется, чтобы к аргументу-множеству применялся оператор .

С другой стороны, можно начать преобразование, сделав σ_b<с внешним операто­ром: σ_b<c(σ_{a=1 or a=3}(R)). Выполнив расщепление условия, содержащего OR, получим равноценное, но несколько иное выражение:

σ_b<c(σ_a=1(R) σ_a=3(R)).

Теперь рассмотрим семейство законов, регламентирующих порядок преобразова­ния операторов выбора, операндами которых служат бинарные операторы декартова произведения (Cartesian product), объединения (union), пересечения (intersection), разности (difference) и соединения (join). Законы подразделяются на три типа в зависимости от того, обязательно ли следует применять оператор выбора к одному или обоим аргу­ментам "вложенного" бинарного оператора.

1. Для объединения — оператор выбора должен применяться к обоим аргументам.

2. Для разности — оператор следует применять к первому и (необязательно) ко второму аргументам.

3. Для остальных операторов — требуется, чтобы оператор выбора был применен по меньшей мере к одному аргументу. Что касается соединения и декартова произведения, применение оператора к обоим аргументам может оказаться ли­бо возможным, либо нет, поскольку не исключено, что то или иное отноше­ние-аргумент не обладает атрибутами, оговоренными в условии выбора. Если применение оператора выбора к обоим аргументам и допустимо, улучшение ка­чества плана запроса в результате принятия подобного решения не гарантиру­ется.

Закон, связывающий операторы выбора и объединения, выглядит так:

σ_C(R S)= σ_C(R) σ_C(S).

В данном случае оператор выбора продвигается "вниз" по обеим ветвям дерева.

Oдин из вариантов закона для оператора разности:

σ_C(R\S)= σ_C(R)\S.

Возможно, однако, применить оператор выбора и к обоим аргументам разности одно­временно:

σ_C(R\S)= σ_C(R)\ σ_C(S).

Другие бинарные операторы позволяют применять оператор выбора к одному или обоим аргументам. Аргументом оператора выбора σ_C может быть только такое отно­шение, которое содержит все атрибуты, упомянутые в условии С. В приведенных ни­же законах подразумевается, что отношение R обладает всеми атрибутами, присутст­вующими в условии С:

σ_C(R×S)= σ_C(R) ×S.

σ_C(R S)= σ_C(R) S.

σ_C(R S)= σ_C(R) S.

σ_C(R S)= σ_C(R) S.

Если в условии С упоминаются только атрибуты S, можно, напротив, воспользоваться соотношением

σ_C(R×S)= R×σ_C(S).

и подобными ему зависимостями, соответствующими операторам , и . Если всеми атрибутами из С обладают оба отношения, R и S, становится справедливым закон вида

σ_C(R S)= σ_C(R) σ_C(S).

Заметим, что такой закон невыполним для операций × и , поскольку схема итого­вого отношения R × S (или R S) представляет собой объединение схем отноше­ний R и S и все их атрибуты строго различаются. С другой стороны, аналогичный за­кон для оператора имеет место, если схемы R и S совпадают.

Пример. Рассмотрим отношения R(a, b), S(b, с) и выражение

σ_{(a=1 or a=3) and b<c}(R S).

Условие b < с может быть применено только к данным отношения S, а a=1 or а = 3 — только к кортежам R. Поэтому уместно начать с расщепления условия с оператором AND:

σ_{a=1 or a=3}(σ _b<c(R S)).

Далее, продвигая оператор σ_b<с "внутрь" R S с применением к отношению S, получим:

σ_{a=1 or a=3}(R σ _b<c(S)).

Наконец, применим "внешний" оператор σ к аргументу R:

σ_{a=1 or a=3}(R) σ _b<c(S)).

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