Преобразования операций реляционной алгебры

Операндами операций реляционной алгебры (РА) являются отношения, т.е. неупорядоченные множества кортежей. Для выполнения операций необходимо просмотреть все кортежи исходного отношения (или отношений). Следствием этого является большая размерность операций РА. Уменьшения размерности можно достичь, изменяя последовательность выполняемых операций.

В качестве примера приведём отношения R1 и R2, содержащие по 1000 кортежей, причём только 10 кортежей в каждом отношении удовлетворяют условию F. Если выполнять следующую последовательность операций:

s_F(R1 U R2),

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

s_F(R1) U s_F(R2)

то после селекции останется по 10 записей из каждого отношения, объеди-нение которых даст 20 требуемых кортежей. Если учитывать, что объединение выполняется путем сортировки данных (для удаления одинаковых кортежей) и промежуточный результат надо хранить, то выигрыш и по объёму памяти, и по времени очевиден: гораздо быстрее отсортировать 20 кортежей, а не 2000.

Оптимизация выполнения запросов реляционной алгебры основана на понятии эквивалентности реляционных выражений. Операндами выражений являются переменные-отношения R_i и константы. Каждое выражение реляционной алгебры определяет отображение кортежей переменных-отношений R_i (i=1,…,n) в кортежи единственного отношения, которое получается в результате подстановки кортежей каждого R_i и выполнения всех определяемых выражением вычислений.

Существуют законы, которые в соответствии с этим определением позволяют выполнять эквивалентные преобразования выражений реляционной алгебры:

1. Закон коммутативности для декартовых произведений:

R1×R2=R2×R1

1. Закон коммутативности для соединений (F – условие соединения):

R1><_FR2= R2><_FR1

1. Закон ассоциативности для декартовых произведений:

(R1×R2)×R3=R1×(R2×R3)

1. Закон ассоциативности для соединений (F1, F2 – условия соединения):

(R1><_F1R2) ><_F2R3= R1><_F1(R2><_F2R3)

1. Комбинация селекций (каскад селекций):

s_F1(s_F2(R))= s_F1vF2(R)

1. Комбинация проекций (каскад проекций):

p_A1,A2,...Am(p_B1,B2,...Bn(R))=p_A1,A2,...Am(R), где {A_m}d{B_n}

1. Перестановка селекции и проекции:

s_Fp_A1,A2,...,Am(R))= p_A1,A2,...,Am(s_F(R))

1. Перестановка селекции с объединением:

s_F(R1 U R2)=s_F(R1) U s_F(R2)

1. Перестановка селекции с декартовым произведением:
• s_F(R1×R2)= (s_F1(R1))×(s_F2(R2))

(если F = F1vF2, где F1 содержит атрибуты, присутствующие только в R1, а F2 содержит атрибуты, присутствующие только в R2);

• s_F(R1×R2)=(s_F(R1))×R2

(если F содержит атрибуты, присутствующие только в R1);

• s_F(R1×R2)=R1×(s_F(R2))

(если F содержит атрибуты, присутствующие только в R2);

• s_F(R1×R2)= s_F2(s_F1(R1)×R2)

(если F = F1vF2, где F1 содержит атрибуты, присутствующие только в R1, а F2 содержит атрибуты, присутствующие и в R1, и в R2).

1. Перестановка селекции с разностью:

s_F(R1-R2)=s_F(R1)-s_F(R2)

1. Перестановка проекции с декартовым произведением:

p_A1,A2,...,Am(R1×R2)= (p_B1,B2,...,Bn(R1))×(font face=symbol>p_C1,C2,...,Cr(R2))

где атрибуты {B_n} d{A_m}, {С_r}d{A_m} и атрибуты B₁,B₂,...,B_n представлены в отношении R1, а атрибуты С₁,С₂,...,С_r – в R2.

1. Перестановка селекции с пересечением:

s_F(R1 ∪ R2)=s_F(R1) ∪ s_F(R2)