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

2020-12-28T22:43:15Z

Zakhar.Koval: Операции над данными, Свойства, SQL

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

===Расширение===
{{Определение
|definition=
Операция '''расширения''' принимает отношение и возвращает другое, идентичное заданному, если не считать дополнительный атрибут, значения которого получены путём вычисления некоторого выжражения.
}}
Пример: отношение R со значением веса в фунтах
{| class="wikitable" style="background-color:#FFF; text-align:center; padding:1000px"
!'''Id'''
!'''Weight'''
|-
|1
|12.0
|-
|2
|17.0
|}
Применив
EXTEND R ADD ( Weight * 454 ) AS GMWT
Мы добавим значение веса в граммах:
{| class="wikitable" style="background-color:#FFF; text-align:center; padding:1000px"
!'''Id'''
!'''Weight'''
!'''GMWT'''
|-
|1
|12.0
|5448.0
|-
|2
|17.0
|7718.0
|}

===Агрегирование===
{{Определение
|definition=
'''Расширение''' предлагает способ включения ''горизонтальных вычислений'' - вычислений в пределах одного кортежа. '''Агрегирование''' выполняет аналогичную функцию, но для ''вертикальных вычислений'' - в пределах одного столбца.
}}
К типичным разновидностям относятся `SUM`, `COUNT`, `AVG`, `MAX`, `MIN`, `ALL`, `ANY`.
Пример операции `SUM` над отношением
{| class="wikitable" style="background-color:#FFF; text-align:center; padding:1000px"
!'''Supplier'''
!'''Price'''
!'''Items'''
|-
|1
|1
|4
|-
|1
|2
|5
|-
|2
|3
|6
|}
Посчитаем <tex>sum_{Total,{Supplier}} \circ \varepsilon_{Total}=Price*Items</tex>, получаем:
{| class="wikitable" style="background-color:#FFF; text-align:center; padding:1000px"
!'''Supplier'''
!'''Total'''
|-
|1
|14
|-
|2
|18
|}
Ещё один хороший пример - сумма по пустому множеству аттрибутов. Посчитаем <tex>sum_{Total,\emptyset} \circ {\varepsilon_{Total}=Price*Items}</tex> от того же отношения и получим
{| class="wikitable" style="background-color:#FFF; text-align:center; padding:1000px"
!'''Total'''
|-
|32
|}

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

===Свойства операций===
{{Определение
|definition=
'''Идемпотентность''' {{---}} свойство при повторном применении операции давать тот же результат. 
'''Примеры''': унарные <tex>\pi</tex> и <tex>\sigma</tex>, бинарные <tex>\bowtie</tex>, <tex>\cup</tex>, <tex>\cap</tex> и др. значки.
}}

{{Определение
|definition=
'''Коммутативность''' {{---}} свойство переместительностию (<tex>x \circ y = y \circ x</tex>). 
'''Пример''': <tex>\bowtie</tex>, <tex>\cup</tex>, <tex>\cap</tex>.
}}

{{Определение
|definition=
'''Ассоциативность''' {{---}} свойство <tex>\forall x, y, z: {{(x \circ y)} \circ z} = {x \circ {(y \circ z)}} </tex>. 
'''Пример''': <tex>\bowtie</tex>, <tex>\cup</tex>, <tex>\cap</tex>.
}}

===Базис операций===
* Унарные операции (projection, filter и переименование)
* Объединение и разность
* Декартово произведение
* Операции над данными (расширение и агрегирование)
Остальные привычные операции выразимы из этого базиса, например <tex>A \cap B = A \bowtie B</tex>

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

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

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

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

====Проекция <tex>\pi_{A_1,A_2,A_3,\dotsc,A_N}(R)</tex> ====
'''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 -- с повторениями 

====Фильтрация <tex>\sigma_{Condition}(R)</tex>====
'''select''' * '''from''' R '''where''' 'Condition'

====Переименование <tex>\rho_{a=b}(R)</tex>====
'''select''' ..., a '''as''' b, ... '''from''' R

===Операции над множествами===
====Объединение <tex>R1 \cup R2</tex>====
'''select''' * '''from''' R1 '''union''' '''select''' * '''from''' R2
'''select''' * '''from''' R1 '''union''' '''all''' '''select''' * '''from''' R2 -- с повторениями

====Пересечение <tex>R1 \cap R2</tex>====
'''select''' * '''from''' R1 '''intersect''' '''select''' * '''from''' R2
'''select''' * '''from''' R1 '''intersect''' '''all''' '''select''' * '''from''' R2 -- с повторениями

====Разность <tex>R1 - R2</tex>====
'''select''' * '''from''' R1 '''except all''' '''select''' * '''from''' R2
'''select''' * '''from''' R1 '''except''' '''all''' '''select''' * '''from''' R2 -- с повторениями

===Операции над данными===
====Расширение <tex>\sigma_{A=expr}(R)</tex>====
'''select''' *, expr '''as''' A from R

====Агрегирование <tex>Function_{Q, A}(R) </tex>====
'''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''' -- сортировка

===Соединения===
====Полное <tex>R_1 \times R_2 </tex>====
'''select * from''' R1 '''cross join''' R2
'''select * from''' R1, R2
====Естественное <tex>R_1 \bowtie R_2</tex>====
'''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
====Внешние <tex>R_1 \times R_2</tex>====
'''select * from''' R1 ['''full'''] '''outer join''' R2 '''on''' <tex>\theta</tex>
'''select * from''' R1 '''left''' ['''join'''] R2 '''on''' <tex>\theta</tex>
'''select * from''' R1 '''right''' ['''join'''] R2 '''on''' <tex>\theta</tex>

===Структура SQL-запроса===
SQL-запрос иммеет вид <tex>\rho(\pi(\sigma(R_1 \oplus R_2 \oplus \dotsc \oplus R_N)))</tex>
'''select'''
... '''as''' ..., ... '''as''' ... -- <tex>\pi</tex> и <tex>\rho</tex> 
'''from'''
<tex>R_1</tex>
'''xxx join''' <tex>R_2</tex> '''on''' ... -- <tex>\oplus</tex> 
...
'''xxx join''' <tex>R_N</tex> '''on''' ... -- <tex>\oplus</tex> 
'''where'''
... -- <tex>\sigma</tex> 

===Примеры===
* Пусть дана таблица `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
==Литература==
* ''Дейт К. Введение в системы баз данных''
* ''Уидом Д., Ульман Д. Основы реляционных баз данных''

[[Категория: Непроверяемые конспекты]]
[[Категория: Базы данных]]
[[Категория: Реляционная алгебра: деление и операции над данными]]

Викиконспекты - Вклад участника [ru]

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