Лекции и практики (1). Курс лекций и материалы для практических занятий

• Название: Курс лекций и материалы для практических занятий
• Дата: 17.03.2023
• Размер: 1.01 Mb.
• Имя файла: Лекции и практики (1).docx
• Тип: Курс лекций; #996812
• страница: 37 из 75

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

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

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

_F (R1 U R2),

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

_F (R1) U _F (R2),

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


Два выражения реляционной алгебры считаются эквивалентными, если они описывают одно и то же отображение.

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

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

1. 
   Закон коммутативности для декартовых произведений: R1  R2 = R2  R1.
   
2. 
   Закон коммутативности для соединений (F – условие соединения): R1 ⊳⊲ _F R2 = R2 ⊳⊲ _F R1.
   
3. 
   Закон ассоциативности для декартовых произведений:
   

(R1  R2)  R3 = R1  (R2  R3).

4. 
   Закон ассоциативности для соединений (F1, F2 – условия соединения): (R1 ⊳⊲ _F1 R2) ⊳⊲ _F2 R3 = R1 ⊳⊲ _F1 (R2 ⊳⊲ _F2 R3).
   
5. 
   Комбинация селекций (каскад селекций):
   

_F1 ( _F2 (R)) =  _{F1  F2} (R).

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

^A1,A2,...,Am ^(B1,B2,...,Bn^{(R)) = }A1,A2,...,Am^(R),

где {A_m}  {B_n}.

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

^F ^(A1,A2,...,Am^{(R)) = }A1,A2,...,Am^(F ^(R)).

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

_F (R1 U R2) = _F (R1) U _F (R2).

9. 
   Перестановка селекции с декартовым произведением:
   
   • 
     _F (R1  R2) = (_F1 (R1))  (_F2 (R2)),
     

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

• 
  _F (R1  R2) = (_F (R1))  R2,
  

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

• 
  _F (R1  R2) = R1  (_F (R2)),
  

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

• 
  _F (R1  R2) = _F2 (_F1 (R1)  R2),
  

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

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

_F (R1 – R2) = _F (R1) – _F (R2).

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

_F (R1  R2) = _F (R1)  _F (R2).