Эквивалентность выражений реляционной алгебры

Каждое выражение реляционной алгебры определяет отображение кортежей переменных отношений /?,(/ = 1, ТУ) в кортежи единственного отношения, которое получается после подстановки кортежей каждого/?,{/= 1, и) и выполнения всех определяемых выражением вычислений.

Два выражения У] и У₂ реляционной алгебры считаются эквивалентными, т.е. ^ = У₂, если они описывают одно и то же отображение. Иными словами, если выполнить подстановки кортежей каждого /?,(/ = 1, п) как в выражение У_ь так и в выражение У₂, то получим два идентичных результата.

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

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

«Л ^х У2 ⁼ «/2 х •

2. Закон коммутативности для соединений:

3\ ® У₂ — У₂ (8) 3\ \

3\ (8) У₂ ⁼ У₂ ® 3\.

Р Р

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

(У1 ^х «Л) х У₃ = ^ ^х (У₂ х У₃).

4. Закон ассоциативности для соединений:

(У! (8>У₂)(8>У₃=У, (8>(У₂(8>У₃);

®У₂)(8)Уз=У1 ® (У₂®У₃).

Р\ Р2 Р\ Р2

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

^а_х,а₂, ...л» ... «л (^"))⁼

где множество атрибутов Ль А₂, Л_т является подмножеством множества

атрибутов 5_Ь 5₂, •••, В„.

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

^СТ/,(^СТ/,(-^/)) = ^а/,л/-₂(-⁷)-

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

М^,........... _Л,(7)) = П,_{ь А},(а,(У)).

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

a_F(J_[xJ₁) = (G_F(J_l))xJ₂,

если F содержит атрибуты, представленные только в выражении Уь

МЛ ^Х*Л) = Л х(МЛ))>

если F содержит атрибуты, представленные только в выражении У₂;

Ст,.(7, X У₂) = (а,- (7,)) X (а,. (У₂)),

если F может быть представлено в виде ^ л где ^ содержит только атрибуты, представленные в У, а^ содержит только атрибуты, представленные в У₂;

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