Реляционная алгебра: операции над данными, свойства и связь с SQL

Операции над данными

Расширение

Определение:

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

Пример: отношение R со значением веса в фунтах

Id	Weight
1	12.0
2	17.0

Примером будет [math]\varepsilon_{GMWT=Weight*454}[/math] — мы добавим значение веса в граммах:

Id	Weight	GMWT
1	12.0	5448.0
2	17.0	7718.0

Агрегирование

Определение:

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

К типичным разновидностям относятся `SUM`, `COUNT`, `AVG`, `MAX`, `MIN`, `ALL`, `ANY`. Пример операции `SUM` над отношением

Supplier	Price	Items
1	1	4
1	2	5
2	3	6

Посчитаем [math]sum_{Total,{Supplier}} \circ \varepsilon_{Total=Price*Items}[/math], получаем:

Supplier	Total
1	14
2	18

Ещё один хороший пример - сумма по пустому множеству аттрибутов. Посчитаем [math]sum_{Total,\emptyset} \circ {\varepsilon_{Total}=Price*Items}[/math] от того же отношения и получим

Total
32

Свойства реляционной алгебры

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

Определение:

Идемпотентность — свойство при повторном применении операции давать тот же результат. Примеры: унарные [math]\pi[/math] и [math]\sigma[/math], бинарные [math]\bowtie[/math], [math]\cup[/math], [math]\cap[/math] и др. значки.

Определение:

Коммутативность — свойство переместительностию ([math]x \circ y = y \circ x[/math]). Пример: [math]\bowtie[/math], [math]\cup[/math], [math]\cap[/math].

Определение:

Ассоциативность — свойство [math]\forall x, y, z: {{(x \circ y)} \circ z} = {x \circ {(y \circ z)}} [/math]. Пример: [math]\bowtie[/math], [math]\cup[/math], [math]\cap[/math].

Базис операций

• Унарные операции (projection, filter и переименование)
• Объединение и разность
• Декартово произведение
• Операции над данными (расширение и агрегирование)

Остальные привычные операции выразимы из этого базиса, например [math]A \cap B = A \bowtie B[/math]

Ограничения реляционной алгебры

• Не все операции представимы (например, транзитивное замыкание)
• Следует, что РА не эквивалентна машине Тьюринга
• Эквивалентность выражений алгоритмически неразрешима

Зачем?

• Внутри БД для оптимизации запроса и плана выполнения
• Для запросов, невыразимых в SQL непосредственно

Реляционная алгебра и SQL

Унарные операции

Проекция [math]\pi_{A_1,A_2,A_3,\dotsc,A_N}(R)[/math]

   select distinct [math]A_1,A_2,A_3,\dotsc,A_N[/math] from R
   select [math]A_1,A_2,A_3,\dotsc,A_N[/math] from R -- с повторениями 

Фильтрация [math]\sigma_{Condition}(R)[/math]

   select * from R where Condition

Переименование [math]\rho_{a=b}(R)[/math]

   select ..., a as b, ... from R

Операции над множествами

Объединение [math]R1 \cup R2[/math]

   select * from R1 union select * from R2
   select * from R1 union all select * from R2 -- с повторениями

Пересечение [math]R1 \cap R2[/math]

   select * from R1 intersect select * from R2
   select * from R1 intersect all select * from R2 -- с повторениями

Разность [math]R1 - R2[/math]

   select * from R1 except all select * from R2
   select * from R1 except all select * from R2 -- с повторениями

Операции над данными

Расширение [math]\sigma_{A=expr}(R)[/math]

   select *, expr as A from R

Агрегирование [math]Function_{Q, A}(R) [/math]

   select A, func(Q) as Q from R group by A
   select count(*)... -- подсчёт всех
   select count(distinct *)... -- подсчёт различных
   select count(q)... -- подсчёт не null
   ... having Condition -- фильтрация после агрегации
   ... order by Attrs -- сортировка

Соединения

Полное [math]R_1 \times R_2 [/math]

   select * from R1 cross join R2
   select * from R1, R2

Естественное [math]R_1 \bowtie R_2[/math]

   select * from R1 natural join R2
   select * from R1 inner join R2 using (A)
   select * from R1 inner join R2 on R1.A = R2.A

Внешние [math]R_1 \times R_2[/math]

   select * from R1 [full] outer join R2 on [math]\theta[/math]
   select * from R1 left [join] R2 on [math]\theta[/math]
   select * from R1 right [join] R2 on [math]\theta[/math]

Структура SQL-запроса

SQL-запрос иммеет вид [math]\rho(\pi(\sigma(R_1 \oplus R_2 \oplus \dotsc \oplus R_N)))[/math]

   select
       ... as ..., ... as ... -- [math]\pi[/math] и [math]\rho[/math] 
   from
       [math]R_1[/math] 
       xxx join [math]R_2[/math] on ... -- [math]\oplus[/math] 
       ...
       xxx join [math]R_N[/math] on ... -- [math]\oplus[/math] 
   where
       ... -- [math]\sigma[/math] 

Примеры

• Пусть дана таблица `Persons (Id, Name, Birthday, MotherId, FatherId)` и требуется получить дни рождения родителей - `(Name, FatherBirthday, MotherBirthday)`

   select
       p.Name as Name
       f.Birthday as FatherBirthday
       m.Birthday as MotherBirthday
     from
       Persons p
       inner join Persons f on p.FatherId = f.id
       inner join Persons m on p.MotherId = m.id

• Подзапросы: например, найти людей, у которых родители родились в один день `Name`

   select p.Name as Name
       from (предыдущий запрос текстом)
       where p.MotherBirthday = p.FatherBirthday

Литература

• Дейт К. Введение в системы баз данных
• Уидом Д., Ульман Д. Основы реляционных баз данных