Реляционная алгебра: операции над данными, свойства и связь с SQL — различия между версиями
Imka239 (обсуждение | вклад) (→Расширение) |
м (rollbackEdits.php mass rollback) |
||
(не показаны 32 промежуточные версии 2 участников) | |||
Строка 4: | Строка 4: | ||
{{Определение | {{Определение | ||
|definition= | |definition= | ||
− | Операция '''расширения''' позволяет добавить вычисляемый атрибут. Она принимает отношение и возвращает другое, идентичное заданному, добавляя дополнительный атрибут, полученный в результате вычисления произвольных скалярных функций от значений атрибутов. | + | Операция '''расширения''' позволяет добавить вычисляемый атрибут. Она принимает отношение и возвращает другое, идентичное заданному, добавляя к нему дополнительный атрибут, полученный в результате вычисления произвольных скалярных функций от значений атрибутов. |
}} | }} | ||
Пример: отношение R со значением веса в фунтах | Пример: отношение R со значением веса в фунтах | ||
Строка 35: | Строка 35: | ||
{{Определение | {{Определение | ||
|definition= | |definition= | ||
− | + | '''Агрегирование''' позволяет выполнить функцию на нескольних кортежах сразу, с указанием сохраняемых и агрегируемого атрибутов. При этом кортежи группируются по значениям сохраняемых атрибутов, затем над каждой группой применяется функция агрегации. | |
}} | }} | ||
К типичным разновидностям относятся `SUM`, `COUNT`, `AVG`, `MAX`, `MIN`, `ALL`, `ANY`. | К типичным разновидностям относятся `SUM`, `COUNT`, `AVG`, `MAX`, `MIN`, `ALL`, `ANY`. | ||
Строка 80: | Строка 80: | ||
|definition= | |definition= | ||
'''Идемпотентность''' {{---}} свойство при повторном применении операции давать тот же результат. <br> | '''Идемпотентность''' {{---}} свойство при повторном применении операции давать тот же результат. <br> | ||
− | '''Примеры''': унарные <tex>\pi</tex> и <tex>\sigma</tex>, бинарные <tex>\bowtie</tex>, <tex>\cup</tex>, <tex>\cap</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>\bowtie</tex>, <tex>\cup</tex>, <tex>\cap</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>\bowtie</tex>, <tex>\cup</tex>, <tex>\cap</tex> (из теории множеств), <tex>\times</tex>, <tex>⟕, ⟖, ⟗</tex> (внешние соединения и декартово произведение являются ассоциативными операциями). |
}} | }} | ||
Строка 107: | Строка 107: | ||
* Эквивалентность выражений алгоритмически неразрешима | * Эквивалентность выражений алгоритмически неразрешима | ||
− | === | + | ===Применимость=== |
− | * Внутри БД для | + | * Внутри БД для упрощения запроса и оптимизации плана выполнения |
− | * Для запросов, невыразимых в SQL непосредственно | + | * Для запросов, невыразимых в SQL непосредственно (таких как деление и полусоединения) |
==Реляционная алгебра и SQL== | ==Реляционная алгебра и SQL== | ||
Строка 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 | ||
− | |||
====Фильтрация <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''' '''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''' '''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 | + | '''select''' * '''from''' R1 '''except''' '''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>-- подсчёт | + | '''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> | ||
Строка 162: | Строка 162: | ||
'''select * from''' R1 '''left''' ['''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> | '''select * from''' R1 '''right''' ['''join'''] R2 '''on''' <tex>\theta</tex> | ||
+ | ====Полусоединений нет==== | ||
===Структура SQL-запроса=== | ===Структура SQL-запроса=== | ||
Строка 174: | Строка 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> - таблица или подзапросы | ||
===Примеры=== | ===Примеры=== | ||
− | * Пусть дана таблица `Persons (Id, Name, Birthday, MotherId, FatherId)` и требуется получить дни рождения родителей - `(Name, FatherBirthday, MotherBirthday)` | + | * Пусть дана таблица `Persons (Id, Name, Birthday, MotherId, FatherId)` и требуется получить дни рождения родителей - `(Name, FatherBirthday, MotherBirthday)`. |
'''select''' | '''select''' | ||
p.Name '''as''' Name | p.Name '''as''' Name | ||
Строка 185: | Строка 187: | ||
'''inner join''' Persons f '''on''' p.FatherId = f.id | '''inner join''' Persons f '''on''' p.FatherId = f.id | ||
'''inner join''' Persons m '''on''' p.MotherId = m.id | '''inner join''' Persons m '''on''' p.MotherId = m.id | ||
− | * '''Подзапросы''': например, найти людей, у которых родители родились в один день `Name` | + | * '''Подзапросы''': например, найти людей, у которых родители родились в один день `Name`. |
'''select''' p.Name '''as''' Name | '''select''' p.Name '''as''' Name | ||
'''from''' (<font color=gray>предыдущий запрос текстом</font>) | '''from''' (<font color=gray>предыдущий запрос текстом</font>) | ||
'''where''' p.MotherBirthday = p.FatherBirthday | '''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 | ||
+ | |||
==Литература== | ==Литература== | ||
* ''Дейт К. Введение в системы баз данных'' | * ''Дейт К. Введение в системы баз данных'' |
Текущая версия на 19:34, 4 сентября 2022
Операции над данными
Расширение
Определение: |
Операция расширения позволяет добавить вычисляемый атрибут. Она принимает отношение и возвращает другое, идентичное заданному, добавляя к нему дополнительный атрибут, полученный в результате вычисления произвольных скалярных функций от значений атрибутов. |
Пример: отношение R со значением веса в фунтах
Id | Weight |
---|---|
1 | 12.0 |
2 | 17.0 |
Примером будет
— мы добавим значение веса в граммах: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 |
Посчитаем
, получаем:Supplier | Total |
---|---|
1 | 14 |
2 | 18 |
Ещё один хороший пример - сумма по пустому множеству аттрибутов. Посчитаем
от того же отношения и получимTotal |
---|
32 |
Свойства реляционной алгебры
Свойства операций
Определение: |
Идемпотентность — свойство при повторном применении операции давать тот же результат. Примеры: унарные (вторая проекция на одно и то же множество атрибутов не влияет на результат) и (две фильтрации не влияют на результат), бинарные (естественное соединение идемпотентно и слева, и справа), , (аналогично и объединение, и пересечение идемпотентно и слева, и справа), (внешние соединения тоже идемпотентны и слева, и справа), (только справа), (только слева), (только справа). |
Определение: |
Коммутативность — возможность перестановки двух аргументов ( Пример: (ествественное соединение коммутативно), , (из теории множеств коммутативно), , (декартово произведение и внешнее соединение также являются коммутативными операциями). | ).
Определение: |
Ассоциативность — свойство Пример: , , (из теории множеств), , (внешние соединения и декартово произведение являются ассоциативными операциями). | .
Базис операций
- Унарные операции (projection, filter и переименование)
- Объединение и разность
- Декартово произведение
- Операции над данными (расширение и агрегирование)
Остальные привычные операции выразимы из этого базиса, например
Ограничения реляционной алгебры
- Не все операции представимы (например, транзитивное замыкание)
- Следует, что РА не эквивалентна машине Тьюринга
- Эквивалентность выражений алгоритмически неразрешима
Применимость
- Внутри БД для упрощения запроса и оптимизации плана выполнения
- Для запросов, невыразимых в SQL непосредственно (таких как деление и полусоединения)
Реляционная алгебра и SQL
Унарные операции
Проекция
Если нужно дублировать строки с одинаковыми значениями атрибутов, то из запроса надо удалить distinct.
select distinct
from R
Фильтрация
select * from R where Condition
Переименование
select ..., a as b, ... from R
Операции над множествами
Объединение
select * from R1 union all select * from R2 -- с повторениями
Если нужно объединить без повторений, то необходимо убрать из запроса all
Пересечение =
select * from R1 intersect all select * from R2 -- с повторениями
Если нужно объединить без повторений, то необходимо убрать из запроса all
Разность
select * from R1 except select * from R2 -- с повторениями
Чтобы убрать повторения, необходимо добавить all после except
Операции над данными
Расширение
select *, expr as A from R
Агрегирование
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 -- сортировка
Соединения
Полное
select * from R1 cross join R2 select * from R1, R2
Естественное
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
Внешние
select * from R1 [full] outer join R2 onselect * from R1 left [join] R2 on select * from R1 right [join] R2 on
Полусоединений нет
Структура SQL-запроса
SQL-запрос иммеет вид
select ... as ..., ... as ... --и from xxx join on ... -- ... xxx join on ... -- where ... --
где
- таблица или подзапросыПримеры
- Пусть дана таблица `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
Литература
- Дейт К. Введение в системы баз данных
- Уидом Д., Ульман Д. Основы реляционных баз данных