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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Примеры)
м (rollbackEdits.php mass rollback)
 
(не показано 13 промежуточных версий 2 участников)
Строка 80: Строка 80:
 
|definition=
 
|definition=
 
'''Идемпотентность''' {{---}} свойство при повторном применении операции давать тот же результат. <br>
 
'''Идемпотентность''' {{---}} свойство при повторном применении операции давать тот же результат. <br>
'''Примеры''': унарные <tex>\pi</tex> и <tex>\sigma</tex>, бинарные <tex>\bowtie</tex>, <tex>\cup</tex>, <tex>\cap</tex>, <tex>⟕, ⟖, ⟗</tex>, <tex>\ltimes</tex> (справа), <tex>\rtimes</tex> (слева), <tex>-</tex> (справа).
+
'''Примеры''': унарные <tex>\pi</tex> (вторая проекция на одно и то же множество атрибутов не влияет на результат) и <tex>\sigma</tex> (две фильтрации не влияют на результат), бинарные <tex>\bowtie</tex> (естественное соединение идемпотентно и слева, и справа), <tex>\cup</tex>, <tex>\cap</tex> (аналогично и объединение, и пересечение идемпотентно и слева, и справа), <tex>⟕, ⟖, ⟗</tex> (внешние соединения тоже идемпотентны и слева, и справа), <tex>\ltimes</tex> (только справа), <tex>\rtimes</tex> (только слева), <tex>-</tex> (только справа).
 
}}
 
}}
  
 
{{Определение
 
{{Определение
 
|definition=
 
|definition=
'''Коммутативность''' {{---}} свойство переместительностию (<tex>x \circ y = y \circ x</tex>). <br>
+
'''Коммутативность''' {{---}} возможность перестановки двух аргументов (<tex>x \circ y = y \circ x</tex>). <br>
'''Пример''': <tex>\bowtie</tex>, <tex>\cup</tex>, <tex>\cap</tex>, <tex>⟗</tex>,<tex>\times</tex>.
+
'''Пример''': <tex>\bowtie</tex> (ествественное соединение коммутативно), <tex>\cup</tex>, <tex>\cap</tex> (из теории множеств коммутативно), <tex>⟗</tex>,<tex>\times</tex> (декартово произведение и внешнее соединение также являются коммутативными операциями).
 
}}
 
}}
  
Строка 92: Строка 92:
 
|definition=
 
|definition=
 
'''Ассоциативность''' {{---}} свойство <tex>\forall x, y, z: {{(x \circ y)} \circ z} = {x \circ {(y \circ z)}} </tex>. <br>
 
'''Ассоциативность''' {{---}} свойство <tex>\forall x, y, z: {{(x \circ y)} \circ z} = {x \circ {(y \circ z)}} </tex>. <br>
'''Пример''':  <tex>\bowtie</tex>, <tex>\cup</tex>, <tex>\cap</tex>, <tex>\times</tex>, <tex>⟕, ⟖, ⟗</tex>.
+
'''Пример''':  <tex>\bowtie</tex>, <tex>\cup</tex>, <tex>\cap</tex> (из теории множеств), <tex>\times</tex>, <tex>⟕, ⟖, ⟗</tex> (внешние соединения и декартово произведение являются ассоциативными операциями).
 
}}
 
}}
  
Строка 116: Строка 116:
  
 
====Проекция <tex>\pi_{A_1,A_2,A_3,\dotsc,A_N}(R)</tex> ====
 
====Проекция <tex>\pi_{A_1,A_2,A_3,\dotsc,A_N}(R)</tex> ====
 +
Если нужно дублировать строки с одинаковыми значениями атрибутов, то из запроса надо удалить distinct.
 
     '''select''' '''distinct''' <tex>A_1,A_2,A_3,\dotsc,A_N</tex> '''from''' R
 
     '''select''' '''distinct''' <tex>A_1,A_2,A_3,\dotsc,A_N</tex> '''from''' R
    '''select''' <tex>A_1,A_2,A_3,\dotsc,A_N</tex> '''from''' R <font color=green>-- с повторениями </font>
 
  
 
====Фильтрация <tex>\sigma_{Condition}(R)</tex>====
 
====Фильтрация <tex>\sigma_{Condition}(R)</tex>====
Строка 127: Строка 127:
 
===Операции над множествами===
 
===Операции над множествами===
 
====Объединение <tex>R1 \cup R2</tex>====
 
====Объединение <tex>R1 \cup R2</tex>====
    '''select''' * '''from''' R1 '''union''' '''select''' * '''from''' R2
 
 
     '''select''' * '''from''' R1 '''union''' '''all''' '''select''' * '''from''' R2 <font color=green>-- с повторениями</font>
 
     '''select''' * '''from''' R1 '''union''' '''all''' '''select''' * '''from''' R2 <font color=green>-- с повторениями</font>
 +
Если нужно объединить без повторений, то необходимо убрать из запроса '''all'''
  
====Пересечение <tex>R1 \cap R2</tex>====
+
====Пересечение <tex>R1 \cap R2</tex>=====
    '''select''' * '''from''' R1 '''intersect''' '''select''' * '''from''' R2
 
 
     '''select''' * '''from''' R1 '''intersect''' '''all''' '''select''' * '''from''' R2 <font color=green>-- с повторениями</font>
 
     '''select''' * '''from''' R1 '''intersect''' '''all''' '''select''' * '''from''' R2 <font color=green>-- с повторениями</font>
 +
Если нужно объединить без повторений, то необходимо убрать из запроса '''all'''
  
 
====Разность <tex>R1 - R2</tex>====
 
====Разность <tex>R1 - R2</tex>====
     '''select''' * '''from''' R1 '''except all''' '''select''' * '''from''' R2
+
     '''select''' * '''from''' R1 '''except''' '''select''' * '''from''' R2 <font color=green>-- с повторениями</font>
    '''select''' * '''from''' R1 '''except''' '''all''' '''select''' * '''from''' R2 <font color=green>-- с повторениями</font>
+
Чтобы убрать повторения, необходимо добавить '''all''' после '''except'''
  
 
===Операции над данными===
 
===Операции над данными===
Строка 143: Строка 143:
  
 
====Агрегирование <tex>Function_{Q, A}(R) </tex>====
 
====Агрегирование <tex>Function_{Q, A}(R) </tex>====
     '''select''' A, func(Q) '''as''' Q '''from''' R '''group by''' A
+
     '''select''' A, func(Q) '''as''' Q '''from''' R '''group by''' A <font color=green>-- A - сохраняемые атрибуты, func(Q) - агрегирующая функция</font>
     '''select count(*)...''' <font color=green>-- подсчёт всех</font>
+
     '''select count(*)...''' <font color=green>-- подсчёт количества строк</font>
     '''select count(distinct *)...''' <font color=green>-- подсчёт различных</font>
+
     '''select count(distinct *)...''' <font color=green>-- подсчёт различных строк</font>
     '''select count(q)...''' <font color=green>-- подсчёт не '''null'''</font>
+
     '''select count(q)...''' <font color=green>-- подсчёт не '''null''' атрибутов</font>
 
     '''... having Condition''' <font color=green>-- фильтрация после агрегации</font>
 
     '''... having Condition''' <font color=green>-- фильтрация после агрегации</font>
 
     '''... order by Attrs'''<font color=green> -- сортировка</font>
 
     '''... order by Attrs'''<font color=green> -- сортировка</font>
Строка 175: Строка 175:
 
     '''where'''
 
     '''where'''
 
         ...<font color=green> -- <tex>\sigma</tex> </font>
 
         ...<font color=green> -- <tex>\sigma</tex> </font>
 +
где <tex>R_1, R_2, \dotsc , R_n </tex> - таблица или подзапросы
  
 
===Примеры===
 
===Примеры===

Текущая версия на 19:34, 4 сентября 2022

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

Расширение

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

Пример: отношение 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]-[/math] (только справа).


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

Если нужно дублировать строки с одинаковыми значениями атрибутов, то из запроса надо удалить distinct.

   select distinct [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 all select * from R2 -- с повторениями

Если нужно объединить без повторений, то необходимо убрать из запроса all

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

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

Если нужно объединить без повторений, то необходимо убрать из запроса all

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

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

Чтобы убрать повторения, необходимо добавить all после except

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

Расширение [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  -- A - сохраняемые атрибуты, func(Q) - агрегирующая функция
   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] 

где [math]R_1, R_2, \dotsc , R_n [/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
  • Сложный запрос: например, дана таблица `Persons (Id, Name, MotherId, FatherId)` и требуется определить для каждого человека имя его родителя - `(Name, ParentName)`.
   select p.Name as Name, f.Name as ParentName
       from Persons p
       inner join Persons f on f.FatherId = m.Id
   union
   select p.Name as Name, m.Name as ParentName
       from Persons p
       inner join Persons m on p.MotherId = m.Id

Литература

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