4.3.1.3. Правила реляционной алгебры

Правильно построенная формула на множестве отношений R с помощью операторов ,  и  называется алгебраически выражением.

Так как в результате исполнения алгебраических операций всегда формируется только одно отношение, то алгебраическое выражение, сформированное на множестве отношений, есть отображение <, , >: R r.

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

• r’=_B1(_B2 (r)) = _B2(_B1 (r)) – операция выбора коммутативна;

• r’=_B(r₁r₂)= _B(r₁)_B(r₂) – операция выбора над пересечением отношений равносильна пересечению операций выбора над каждым отношением, но _B(r₁)_B(r₂) более рациональна по времени;

• r’=_B(r₁r₂)= _B(r₁)_B(r₂) – операция выбора над объединением отношений равносильна объединению операций выбора над каждым отношением, но _B(r₁)_B(r₂) более рациональна по времени ;

• r’=_B(r₁\r₂)= _B(r₁)\_B(r₂) – операция выбора над разностью отношений равносильна разности операций выбора над каждым отношением, но _B(r₁)\_B(r₂) более рациональна по времени;

• r’=_B(r₁>< r₂)= _B(r₁)><r₂ – операция выбора над соединением отношений равносильна соединению одного отношения с операцией выбора над другим отношением, но _B(r₁) )><r₂ более рациональна по времени, так как _B(r₁>< r₂) обрабатывает все кортежи прямого произведения r₁ и r₂;

• r’=_B(_rel(r₁))=_rel(_B(r₁)) – операция проекции коммутативна с операцией выбора;

• r’=(r₁><r₂)= (r₂><r₁) - операция соединения коммутативна;

• r’=(r₁><r₂)><r₃=r₁><(r₂><r₃) – операция соединения ассоциативна.

4.3.2. Реляционное исчисление

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

Пусть r’={ t’ F(t’)}, где t’ – кортеж отношения, а F(t) - формула логической функции.

Также как в исчислении предикатов введем понятия переменные и постоянные кортежи. Для обозначения перемен­ных кортежей используем символы x, y, z,... , а для постоянных кортежей - a, b, c,... Любой постоянный или переменный кортеж называют термом и обозначают t_i.

Элементарная формула определяется следующими правилами:

• если r - имя отношения, а t - терм, то r(t) –элементарная формула;

• если x и y – переменные кортежи и задан оператор сравнения двух или нескольких атрибутов A_i и A_j, то x(A_i)y(A_j) - элементарная формула;

• никаких других формул нет.

Также как в исчислении предикатов введем понятия “свободных переменных-кортежей “ и “связных переменных-кортежей” Переменная-кортеж является связанной, если ей предшествует квантор по этой же переменной и свободной в противном случае.

Формулы реляционного исчисления с переменными-кортежами могут быть определены из элементарных формул рекурсивно:

• любая элементарная формула есть формула, т.е. F= r(t) и F= x(A_i)y(A_j);

• если F₁ и F₂ -формулы, то (F₁), (F₁ F₂), (F₁ F₂) также формулы;

• если x - переменный кортеж, F(x) - формула, то _x(F) и _x(F) также формулы.

• никаких иных формул, кроме построенных по 1), 2), и 3) нет.

Итак, r’={t’ F(t)} есть множество свободных переменных-кортежей в F(t), формируемое связанными переменными-кортежами для истинного значения формулы F(t).

Операция выборки

r’={t’| _x(r(x)(x(A_i)k_di))} или r’={t’| _x(r(x)(x(A_i)x(A_j)))}.

Квантор существования используют потому, что накладываемые условия (x(A_i)k_di) или (x(A_i)x(A_j)) формируют частное суждение на множестве кортежей отношения. Условия могут быть заданы функциями k_di:=f(A_i) или A_j:=f(A_i, A_j).

Операция проекции

r’={t’| _x(r(x)(t’[1]=x(A_i))(t’[2]=x(A_j))..(t’[n]=x(A_n))}.

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

Операция объединения

r’={t’| _x _y(r₁(x)r₂(y)((t’=x)(t’=y))}.

Квантор всеобщности используют потому, что в новое отношение следует перенести все кортежи отношений r₁(x) и r₂(y).

Операция разности

r’={t’| _x_y(r₁(x)r₂(y)((t’=x)(t’=y))}.

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

Операция пересечения

r’={t’| _x_y(r₁(x)r₂(y)(t’=x)(t’=y)}.

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

Операция прямого произведения

r’={t’|_x_y(r₁(x)r₂(y)(t’[1]=x[1])(t’[2]=x[2])..(t’[n₁]=x[n₁])

(t’[n₁+1]=y[1]) (t’[n₁+2]=y[2]).. (t’[n₁+n₂]=y[n₂]))}.

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

Операция естественнного соединения

r’={t’|_x_y(r₁(x)r₂(y)(x(A_i)=y(A_j))(t’[1]=x[1])..(t’[i]=x[i]=y[j])..

(t’[n₁]=x[n₁])(t’[n₁+1]=y[1])(t’[n₁+2]=y[2])..(t’[n₁+n₂-1]= y[n₂]))}.

Операция -соединения

r’={t’|_x_y(r₁(x)r₂(y)(x(A_i)y(A_j))(t’[1]=x[1])..(t’[i]=x[i])..

(t’[n₁]=x[n₁])(t’[n₁+1]=y[1])..(t’[n₁+j]=y[j])..(t’[n₁+n₂]= y[n₂]))}.