Раздел 3.3. Реляционная алгебра.

Теоретической основой языков запросов к реляционным БД является реляционная алгебра. Операндами в реляционной алгебре являются отношения R_i и их реализации – таблицы r_i, k_i – арность отношения R_i (количество столбцов); n_i – количество строк в R_i.

Базисный набор операций:

1. Объединение: R=R₁  R₂. Результат операции R содержит кортежи из R₁ и R₂. Ограничения на операнды: а) k₁=k₂; б) схемы R₁ и R₂ также должны совпадать; в) дублирующие кортежи в результат включаются только один раз. Пример:

SQL: R₁ UNION R₂;

2. Разность: R=R₁ \ R₂. Результат операции R включает в себя кортежи из R₁, которых нет в R₂. Ограничения на операнды: а) k₁=k₂; б) схемы R₁ и R₂ также должны совпадать. Пример:

SQL: к сожалению в стандарте SQL нет соответствующего оператора, например, как в ORACLE: R₁ MINUS R₂;, поэтому можно воспользоваться другими конструкциями, например: DELETE * FROM R₁ WHERE ID IN (SELECT ID FROM R₂);, где ID – одиночное значение некоторого выражения, например первичного ключа в R₁ и R₂.

3. Декартово произведение. R=R₁  R₂. Результат операции R: каждый кортеж из R₁ дополняется кортежем из R₂; арность результата – k = k₁+k₂; n = n₁*n₂. Результат декартова произведения не может содержать дублирующие кортежи.

Пример: пусть

тогда

SQL: SELECT * FROM R₁, R₂;

4. Селекция: R = _F(R_i), где F - логическая формула над атрибутами из R_i. Результатом операции является таблица R, содержащая те же столбцы, что и R_i и строки из R_i, подстановка которых в F дает значение "истина". Пример: R = _C=c1 (R₁):

Результат имеет ту же схему, что и аргумент операции (тот же набор столбцов). Кортеж аргумента попадает в результирующее отношение, если при подстановке в формулу F он дает значение «истина».

SQL: SELECT * FROM R_i WHERE F;

5. Проекция: R = _X(R_i), где X - подмножество атрибутов из отношения R_i. Результирующее отношение имеет схему, совпадающую с множеством X, и содержит кортежи отношения R_i, из которых «вырезаны» значения, соответствующие атрибутам X. Дублирующие кортежи из результата удаляются. Вырезка по столбцам. Пример: R = _BC(R₁)

SQL: SELECT DISTINCTROW FROM R₁;

Дополнительный набор операций:

1. Пересечение:

Те же ограничения, что у второй базисной операции. Результат содержит кортежи, принадлежащие к и к .

2. Соединение: , где

3. Эквисоединение: Частный случай соединения, когда есть знак =

4. Естественное соединение:

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

Выражение через базисный набор: R=_X(_F(R₁R₂)), где F=_i=1,…,k(R₁.A_i=R₂.A_i) – конъюнкция по всем одноименным атрибутам, X= R₁R₂ – объединение атрибутов из R₁ и R₂.

R₁ = поставщик ([А1] , [А2] наименование поставщика, [А3] адрес поставщика)

R₂ = потребители ([А4] номер потребителя, [А5] наименование потребителя, [А6] адрес потребителя)

R₃ =детали ([А7] номер детали, [А8] наименование детали)

R₄ = поставка ([А1] номер поставщика, [А4] номер потребителя, [А7] номер детали, [А9] цена детали, [А10] дата поставки)

ФОРМУЛИРУЕМ ЗАПРОС: получить список деталей, которые были поставлены поставщиком , потребителем в период с 20.09.10 по 21.10.10

Для формализации запроса воспользуемся так называемым универсальным реляционным запросом:

Проекция

Свойства операции:

1. Коммутативность:

Любая операция соединения, в том числе и естественного.

2. Ассоциативность:

- определена на атрибутах и

- определена на атрибутах и

3. Свойство проекции:

4. Свойство селекции:

- определена на атрибутах из

- определена на атрибутах из

Правила формальной оптимизации запроса:

1. Операция селекции должна выполняться раньше, чем декартово произведение и соединения (см. св-во 4).

2. Операция проекции должна выполняться раньше, чем декартово произведение и соединение (см. св-во 3).

3. Операция селекции и проекции должны выполняться совместно.

4. Порядок выполнения операции должен быть такой, чтобы в системных буферах было минимальное количество памяти для промежуточных результатов (см. св-ва 1,2)

Пример: