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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Агрегирование Function_{Q, A}(R))
Строка 1: Строка 1:
 +
{| class="wikitable" align="center" style="color: red; background-color: black; font-size: 56px; width: 800px;"
 +
|+
 +
|-align="center"
 +
|'''НЕТ ВОЙНЕ'''
 +
|-style="font-size: 16px;"
 +
|
 +
24 февраля 2022 года российское руководство во главе с Владимиром Путиным развязало агрессивную войну против Украины. В глазах всего мира это военное преступление совершено от лица всей страны, всех россиян.
 +
 +
Будучи гражданами Российской Федерации, мы против своей воли оказались ответственными за нарушение международного права, военное вторжение и массовую гибель людей. Чудовищность совершенного преступления не оставляет возможности промолчать или ограничиться пассивным несогласием.
 +
 +
Мы убеждены в абсолютной ценности человеческой жизни, в незыблемости прав и свобод личности. Режим Путина — угроза этим ценностям. Наша задача — обьединить все силы для сопротивления ей.
 +
 +
Эту войну начали не россияне, а обезумевший диктатор. И наш гражданский долг — сделать всё, чтобы её остановить.
 +
 +
''Антивоенный комитет России''
 +
|-style="font-size: 16px;"
 +
|Распространяйте правду о текущих событиях, оберегайте от пропаганды своих друзей и близких. Изменение общественного восприятия войны - ключ к её завершению.
 +
|-style="font-size: 16px;"
 +
|[https://meduza.io/ meduza.io], [https://www.youtube.com/c/popularpolitics/videos Популярная политика], [https://novayagazeta.ru/ Новая газета], [https://zona.media/ zona.media], [https://www.youtube.com/c/MackNack/videos Майкл Наки].
 +
|}
 +
 
==Операции над данными==
 
==Операции над данными==
  

Версия 07:17, 1 сентября 2022

НЕТ ВОЙНЕ

24 февраля 2022 года российское руководство во главе с Владимиром Путиным развязало агрессивную войну против Украины. В глазах всего мира это военное преступление совершено от лица всей страны, всех россиян.

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

Мы убеждены в абсолютной ценности человеческой жизни, в незыблемости прав и свобод личности. Режим Путина — угроза этим ценностям. Наша задача — обьединить все силы для сопротивления ей.

Эту войну начали не россияне, а обезумевший диктатор. И наш гражданский долг — сделать всё, чтобы её остановить.

Антивоенный комитет России

Распространяйте правду о текущих событиях, оберегайте от пропаганды своих друзей и близких. Изменение общественного восприятия войны - ключ к её завершению.
meduza.io, Популярная политика, Новая газета, zona.media, Майкл Наки.

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

Расширение

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

Пример: отношение 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

Литература

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