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

Материал из Викиконспекты
Версия от 17:11, 19 декабря 2021; Imka239 (обсуждение | вклад) (Свойства операций)
Перейти к: навигация, поиск

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

Расширение

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

Пример: отношение 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]⟕, ⟖, ⟗[/math], [math]\ltimes[/math] (справа), [math]\rtimes[/math] (слева) .


Определение:
Коммутативность — свойство переместительностию ([math]x \circ y = y \circ x[/math]).
Пример: [math]\bowtie[/math], [math]\cup[/math], [math]\cap[/math], [math]\times[/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], [math]\times[/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

Литература

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