Эвристические правила эквивалентных преобразований реляционных выражений

1.

Эвристические правила
эквивалентных преобразований
реляционных выражений

2.

Эти правила устанавливают допустимый порядок
перестановок операций в реляционных формулах, и они
должны быть заложены в систему. С их помощью
оптимизатор системы, исходя из стартовой формулы запроса,
строит её наименее затратный вариант, т. е. осуществляет
синтаксическую оптимизацию поступившего запроса.
Буквами R, S, T будем обозначать реляционные таблица, t —
кортежи, p, q — предикаты, , — соединительные
предикаты, A, B — группы атрибутов. Некоторые правила
будут выполняться условно, т. е. при соблюдении некоторых
требований.
2

3.

Правило 1. Каскад селекций.
p( q(R))= p q(R)= q( p(R))
Правило 2. Каскад проекций (идемпотентность проекции).
π A1 π A2 R =π A1 R , условие: A1 A2
Правило 3. Перестановочность селекции и проекции.
p(πA(R))=πA( p(R)), условие: A(p) A
3

4.

Правило 4. Коммутативность бинарных операций.
R∪S=S∪R; R∩S=S∩R; R S=S R; R⨝ S=S⨝ R; R⨝S=S⨝R
Правило 5. Ассоциативность бинарных операций.
(R∪S)∪T=R∪(S∪T); (R∩S)∩T=R∩(S∩T);
(R S) T=R (S T); (R⨝S)⨝T=R⨝(S⨝T);
(R⨝ S)⨝ζT=R⨝ (S⨝ζT) — при условии, что задействует
атрибуты только из R и S, задействует атрибуты только из S и T.
Правило 6. Дистрибутивность соединения и объединения.
(R∪S)⨝ T=(R⨝ T)∪(S⨝ T); (R∪S)⨝T=(R⨝T)∪(S⨝T)
4

5.

Правило 7. Вставка селекции внутрь объединения/пересечения/разности
(дистрибутивность).
p(R∪S)= p(R)∪ p(S); p(R∩S)= p(R)∩ p(S); p(R–S)= p(R)– p(S)
Обоснование. Для пересечения: и левая, и правая части равенства содержат кортежи,
которые одновременно: 1) принадлежат R; 2) принадлежат S; 3) удовлетворяют
предикату p.
Для объединения. Левая часть содержит кортежи t, удовлетворяющие составному
условию: (t R t S) (t удовлетворяет p). Правая часть содержит кортежи t,
удовлетворяющие условию: (t R (t удовлетворяет p)) (t S (t удовлетворяет p))
Согласно логическим законам двойственности, эти условия эквивалентны.
Для разности – предлагается проделать самостоятельно.
5

6.

Правило 8. Вставка проекции внутрь объединения (дистрибутивность).
πA(R∪S)=πA(R)∪πA(S)
Обоснование несложное: и в левой, и в правой части содержатся кортежи
сдвоенного набора R и S, урезанные по вертикали на атрибуты группы A.
Замечание. Для операций пересечения и разности свойство вставки
проекции не выполняется.
Контрпример (проекция на атрибут A1):
6

7.

Правило 9. Вставка селекции внутрь декартова произведения и соединений (дистрибутивность).
p q(R S)= p(R) q(S);
p q(R⨝ S)= p(R)⨝ q(S);
p q(R⨝S)= p(R)⨝ q(S)
Здесь предикат p определён на атрибутах R: A(p) A(R), предикат q определён на атрибутах S: A(q) A(S).
Обоснование. Для декартова произведения. Таблица R S состоит из всевозможных «сцепок» кортежей R с
кортежами S по принципу «каждый с каждым». Таким образом, каждый кортеж R S состоит как бы из
двух частей: «части R» и «части S». Левая часть равенства p q(R S) состоит из всевозможных кортежей«сцепок», у которых «часть R» удовлетворяет p, а «часть S» удовлетворяет q. Правая часть p(R) q(S)
представляет собой набор «сцепок» кортежей R, удовлетворяющих p и кортежей S, удовлетворяющих q.
Понятно, что это одно и то же, только разными словами.
Для -соединения. Используем свойство каскада селекций:
p q(R⨝ S)= p q( (R S))= p q (R S)= p q(R S)= ( p q(R S))= ( p(R) q(S))= p(R)⨝ q(S)
Для естественного соединения делается аналогично.
7

8.

Важные частные случаи.
1) Пусть p определён только на атрибутах R. Тогда:
p(R S)= p(R) S; p(R⨝ S)= p(R)⨝ S; p(R⨝S)= p(R)⨝S
2) Пусть q определён только на атрибутах S. Тогда:
q(R S)=R q(S); q(R⨝ S)=R⨝ q(S); q(R⨝S)=R⨝ q(S)
Обоснование сделаем только для одного из соотношений, для остальных аналогично:
p(R⨝ S)= p true(R⨝ S)= p(R)⨝ true(S)= p(R)⨝ S
8

9.

Правило 10. Вставка проекции внутрь декартова произведения и соединений (дистрибутивность).
Пусть A1 A(R), A2 A(S) и A( ) A1∪A2 (аналогично для соединительных атрибутов естественного
соединения). Тогда:
π A1 A2 (R S) = π A1(R) π A2 (S)
π A1 A2 (R⨝ S) =π A (R) ⨝ π A (S)
2
1
π A1 A2 (R⨝S) = π A1 (R) ⨝ π A2 (S)
Обоснование. Для декартова произведения. Если какой-либо кортеж относится к левой части π A1 A2 (R S),
то он представляет собой «сцепку» кортежа t1 из R и кортежа t2 из S, «урезанную» по вертикали на
атрибуты сдвоенной группы A1∪A2. И тем самым он относится и к правой части, как «сцепка»
«урезанного» на A1 кортежа t1 и «урезанного» на A2 кортежа t2. Аналогичное рассуждение применимо и в
обратную сторону.
Для -соединения. Используем свойство перестановочности селекции и проекции, для которого в данном
случае необходимо условие A( ) A1∪A2:
π A1 A2 (R⨝ S) = π A1 A2 ( (R S)) = ( π A A (R S)) = ( π A (R) π A (S)) = π A(R) ⨝ π A (S)
2
2
1
1
1
2
Для естественного соединения аналогично.
9

10.

Правило 10-a. Применимость правила 10 для соединений в случае
невыполнения условия A( ) A1∪A2.
Если в A( ) имеются атрибуты, не относящиеся ни к A1, ни к A2, то
расширим A1 и A2 дополнительными группами, соответственно, B1 и
B2: B1 A(R), B2 A(S). Расширим по минимуму, но так, чтобы
выполнялось условие A( ) A1∪B1∪A2∪B2. Тогда согласно правилу 2:
π A1 A2 (R⨝ S) = π A1 A2 ( π A1 B1 A2 B2 (R⨝ S)) =
= π A1 A2 ( π A1 B1 (R) ⨝ π A 2 B2 (S))
И аналогично для естественного соединения.
10