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

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

-Операции над множествами

-Примеры задач

-SQL

-Реляционное исчисление

-Равенство формализмов (теорема Кодда)

-Conjunctive Queries (CQ)

-Вычислительная сложность

-Сложность Conjunctive Queries

-Транзитивной замыкание

-Свойства и анализ запросов

-Пример использования RA для оптимизации запросов

-Список источников

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

Основные операторы — отношение А(отношение здесь является синонимом таблицы и предиката) является реляционным алгебраическим выражением, а также алгеброй, поэтому реляционное алгебраическое выражение возвращает отношение (свойство замыкания оператора).

select (выбрать; ограничить) — select (выбрать; ограничить), A — отношение (предикат, таблица), — логическое выражение, из которого выбираются строки (кортежи, записи и т.п.). Выделение — это, по сути, фильтр горизонтальной строки. Таким образом, вы можете представить, что просматриваете каждую строку и оставляете только те, которые удовлетворяют условию. Простой пример для иллюстрации:

Projections (проекции) — проекции (projections) на атрибуты A, B, возвращает таблицу, оставляя только столбцы (атрибуты) A, B. Простой пример показан ниже. По сути, это фильтр по атрибуту. В каком-то смысле это вертикальный фильтр.

Переименовать — переименовать столбец a в b относительно A (атрибуты, аргументы предиката и т. д.)

Декартово произведение — декартово произведение двух отношений. Большая доля всех возможных комбинаций строк в A и B.

Операции над множествами

Реляционная алгебра — это расширение классического набора операторов множеств (отношение — это упорядоченный набор кортежей, обратите внимание, что это не совсем то же самое, что и упорядоченный набор кортежей). Предположим, у нас есть таблица StudentMark(Имя, Оценка, Тема, Дата) — упорядочены кортежи (Вася, 5, Информатика, 05.10.2010) — сначала строка Имя стоит на первой (ок или нулевой) позиции, целое число второе, третье — строка, четвертое — дата. При этом сами упорядоченные кортежи (имя, марка, тема, дата) не упорядочены «внутри» отношения.

Union — объединение всех строк A и B, ограничение — одинаковые атрибуты

Пересечение — пересечение строк, такое же ограничение

Разница множеств — В минус A, все строки присутствуют в B, но не в A, одно и то же ограничение

(B\A; A — слева, B — справа)

Вспомогательный оператор — join (соединение); объединение объединяет две записи из таблицы А и таблицы Б. Но только если для этих двух записей выполняется условие φ.

Примеры задач

Будем работать со следующей схемой


Схема взята из книги: Elmasri, Navathe — Fundamentals of Database systems

Теперь рассмотрим несколько простых задач реляционной алгебры.

Задача первая. Выведите имена всех сотрудников отдела 5, которые работают более 10 часов в неделю над проектом X.

(Промежуточные результаты можно «сохранить» в новых связях, но это не обязательно.)

Решение первой задачи. Реляционная алгебра

Задача вторая. Вывести имена всех работников, которыми напрямую руководит Франклин Вонг (и найти небольшую ошибку в решении ниже)

Решение второй задачи. Реляционная алгебра

Задача третья. Потребует использования нового оператора — «агрегация». Рассмотрим его на примере:

Для каждого проекта вывести название и общее число часов в неделю, которое все работники тратят на этот проект.

Решение третьей задачи. Реляционная алгебра

Обратите внимание, что запрос имеет вид a F b (A). где a, b — столбцы, A — отношение и агрегатная функция (например, SUM, MIN, MAX, COUNT и т. д.). Прочитайте это так: для каждого значения в столбце a подсчитайте b. То есть одно значение в столбце а, может соответствовать нескольким строкам. Поместим значения столбца b из этого набора строк в функцию и создадим новый атрибут fun_b с соответствующими значениями.

Этот запрос не может быть выражен в «классической» реляционной алгебре (без оператора агрегации F). Другими словами, невозможно написать единственный запрос, дающий правильный ответ, для любой базы данных, удовлетворяющей схеме.

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

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

SQL

В этом разделе представлен SQL (язык структурированных запросов) и на простом примере показано, как SQL сопоставляется с реляционной алгеброй.

Рассмотрим еще раз первую задачу:

Задача первая. Вывести имена всех работников 5го департамента, которые работают более 10 часов в неделю над проектом Х.

Классическое решение выглядит следующим образом:

Классическое решение.

Альтернативно можно написать вот так:

Немного альтернативно.

Или совсем альтернативно:

С подзапросом

Проводим аналогию между SQL и реляционной алгеброй

На втором решении мы видим отчетливую аналогию c реляционной алгеброй:

Теперь используем равенство для join и увидим аналогию между SQL и реляционной алгеброй в первом решении

Как бы это не было иронично, но SELECT в SQL — это project (π; проекция) в реляционной алгебре.

Теперь рассмотрим задачу с агрегацией и сравним её с решением на реляционной алгебре:

Более интересные задачи мы рассмотрим далее (также небольшая подборка здесь), а сейчас рассмотрим еще один формализм запросов.

Реляционное исчисление

Внимательный читатель может воскликнуть: «Зачем козе баян?» Чего здесь не хватает, так это двух форматов написания запросов. Почему 3-й?

Реляционные исчисления — это адаптация FOL (логика первого порядка для формулирования запросов). FOL — один из наиболее изученных формализмов в математике, позволяющий использовать теоретический инструментарий и классические результаты для анализа и формулирования вопросов.

Благодаря реляционным вычислениям многие результаты являются сложными, а (не)выразимость и формирование запросов переносятся из логики в базу данных. Поэтому стоит ознакомиться с этим форматом.

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

Пусть φ(X) — линейное выражение, а X — независимая переменная, т. е. не определяемая количественно (∀ — квантор всеобщности, ∃ — квантор существования), тогда запрос реляционного исчисления определяет множество.

{ X | φ(Х) }

Рассмотрим простой пример анализа формализма.

Пусть R — отношение с тремя свойствами a, b, c. Теперь перепишите следующий вопрос по реляционной алгебре:

В реляционных исчислениях это выглядит так:

{ r.a, r.b, r.c | R® and r.a = r.c }

В переводе на простой язык r — это кортеж R (т. е. строка с атрибутами, значение которой можно получить с помощью точек в ее имени, т. е. r.a — это атрибут a кортежа r(массив) относительно R) (таблица) . Как видите, r — это результат запроса, и он должен быть свободным кортежем, поэтому здесь нет квантификатора.

Рассмотрим еще один простой пример: R(a,b,c) ∗ S(c,d,e). где * — join. Присоединение по имени — атрибуты с одинаковым именем используются в качестве критерия присоединения.

{ r.A, r.B, r.C, s.D, s.E | R® and S(s) and r.C = s.C}

Если бы s.D и S.e не было среди выходных параметров, запрос бы имел следующий вид:

{ r.A, r.B, r.C | R® and ∃s: S(s) and r.C = s.C}

Поскольку S существует только в «теле» запроса, нам нужно определить квантор существования.

При выполнении таких запросов вы всегда должны помнить о глобальных числах при написании следующих выражений (только в качестве примеров):

{ r.A | R® and ∀s: S(s) and r.C = s.C and s.E = «банан»}

Тогда этот запрос всегда возвращает пустой набор. Это связано с тем, что для выполнения условия запроса каждый кортеж в мире длины 3 должен принадлежать S и иметь последнее значение атрибута «банан».

Импликация «=>» обычно используется с квантором всеобщности. Запрос можно переписать так:

{ r.A | R® and ∀s: (S(s) and r.C = s.C) => s.E = «банан»}

Если S и C имеют то же значение, что и C в R, то значение последнего атрибута должно быть «банан».

Равенство формализмов (теорема Кодда)

Проще говоря, теорема Кодда такова: все три формализма SQL, реляционная алгебра и реляционное исчисление одинаковы.

Это означает, что запрос, выраженный на одном языке, можно переформулировать на другом. Этот результат удобен, во-первых, тем, что позволяет использовать наиболее удобную форму для анализа запросов, а во-вторых, сочетает в себе декларативный язык SQL и реляционное исчисление с императивной реляционной алгеброй. Другими словами, у вас уже есть способ выполнять (и оптимизировать) свои запросы, переводя их из SQL в реляционную алгебру.

Conjunctive Queries (CQ)

Запросы, состоящие из частей select(σ)-project(π)-join(⋈), в реляционной алгебре называются запросами на соединение.

Если вы дочитали до этого места, попробуйте решить приведенную ниже задачу, используя только эти три оператора (и, конечно, их отношения).

Задача. Выведите имена всех работников, которые работают над каждым проектом.

Решение

Это невозможно. Почему читаем далее.

Подумайте какому сегменту SQL и реляционного исчисления относится данный класс реляционной алгебры.

Вычислительная сложность

Существует несколько способов измерения вычислительной сложности при выполнении запросов, но они часто сбивают с толку, поэтому делаем определение и название:

Пусть Q — запрос, а D — база данных, тогда нам нужно вычислить Q(D).

• Когда Q фиксировано, вычислительная сложность f(D) называется сложностью данных.

• Если D постоянно, вычислительная сложность f(Q) называется сложностью запроса.

• Если ничего не фиксировано, сложность f(Q,D) называется сложной сложностью.

Важный факт: сложность SQL (и других) для данных относится к классу AC0. Это очень хорошая категория сложности. Это означает, что запросы могут быть рассчитаны очень эффективно.

С теоретической точки зрения вы можете увидеть схему ниже.

AC0 находится внутри NL (точнее, он также находится внутри одного из «слоев» NC внутри NL).

Рассмотрим этот интересный вопрос, связанный со сложностью вычислений: пусть f — удовлетворяющая функция выражения. То есть для каждого запроса указывается, существует ли база данных, чтобы Q(D) было истинным. Теорема Кодда говорит нам, что реляционная алгебра и SQL эквивалентны реляционному исчислению. Это означает, что вычисление f эквивалентно проблеме завершения (логика первого порядка SAT не может быть вычислена). Так что да: ни один алгоритм не может определить согласованность любого SQL-запроса.

Сложность Conjunctive Queries

CQ — один из наиболее изученных классов запросов, так как он составляет большинство запросов к базе данных (я видел 90% в одной презентации, но сейчас не могу найти источник). Итак, давайте рассмотрим сложность более подробно и докажем, что на самом деле комбинированная сложность такая же, как NP. Задача является NP-полной. (Вы можете прочитать больше о NP здесь и здесь.)

Для этого запишите любой CQ-запрос в следующем виде в реляционном вычислении:

{X | [∃X0:] p0(X0) and [∃X1:] p1(X1) and [∃X1:] p(X2) …}

Где [.] — необязательный квантор. Почему такие выражения всегда разрешены? Потому что работу здесь всегда можно выразить через X, то есть объединение можно выразить через переменные уравнения и выбрать через условия в теле запроса.

Чтобы показать, что проблема принадлежит к NP-полному классу, нам нужно сделать две вещи:

• указывает, что присвоение относится к классу NP

• Даны NP-полные задачи

Первое условие легко выполняется. Поскольку отношения имеют конечные значения (то есть множество возможных значений), мы можем недетерминистически «угадать» функцию так, чтобы все отношения под квантором существования были истинными.

Покажем, что задача раскраски графа сводится к задаче удовлетворения CQ-запроса.

Пусть D состоит из реляционного ребра = {(red, green), (green, red), (blue, red), (green, blue) … } — две вершины одного цвета.

дает исходный граф в виде набора ребер

Затем напишите следующий запрос

{ () | ∃X0… ∃XN: edge(V1,V2) and … edge(V_i, V_j)… }

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

Транзитивной замыкание

Определения сложности для данных и для каждого запроса также описывают хорошо известный результат. В традиционном SQL (без with) транзитивные замыкания не могут быть выражены в постоянном запросе. Вы не можете написать запрос, который оценивает предикат закрытия для какой-либо базы данных. Это означает, что невозможно написать один фиксированный запрос для вычисления отношения edge каждого графа, если граф хранится как отношение ребер. Интуитивно такой запрос, очевидно, должен подпадать под категорию CQ.

Это видно либо из «заданной» вычислительной сложности, либо, что гораздо более конструктивно и интересно, из теоремы компактности и теоремы Кодда (SQL = логика первого порядка).

Доказательство не является тривиальным и может быть опущено без дальнейшего ухудшения понимания материала.

Набросок доказательства

Теорема о компактности: бесконечный набор выражений возможен только в том случае, если допустимы конечные подмножества этого набора (модель — все выражения имеют истинную интерпретацию).

Гёдель: логика первого порядка компактна.
Кодд: SQL — логика первого порядка

Доказательство от противного, предположим, что T(a,b) — это путь из a в b. P_n(a,b) — это путь от a до b длины n. Тогда ~P_n(a,b) — нет пути из a в b длины n.

Возьмем следующее конечное множество {T(a,b), ~P_1(a,b), ~P_2(a,b)… ~P_k(a,b)} — возьмем путь длины k, так что он удовлетворяет + 1 и выполняется T (a,b), а также выполняются все ~P_1… ~P_k. Более того, каждое конечное множество этого типа может быть удовлетворено, так что по теореме о компактности также выполняются их бесконечные комбинации.

Однако ~P_k должно выполняться для ЛЮБОГО k. То есть не может быть пути длины от a до b и должно быть выполнено T(a,b). Противоречие.

Если запрос не исправлен, проблема становится легко решаемой. Предположим, что в базе данных всего k ребер. Это означает, что максимальное количество путей равно k или меньше. Это означает, что запрос можно явно записать как объединение путей длины 1, 2, … k для получения a. Запрос, вычисляющий достижимость графа.

Свойства и анализ запросов

Вернемся теперь к предложенной ранее задаче.

Теперь выведите имена всех сотрудников, работающих над каждым проектом.

Причину, по которой класс CQ не решает эту проблему, можно понять, определив сам запрос и основные свойства класса CQ.

По определению Q-запрос предназначен для любых двух баз данных, то есть по мере увеличения количества баз данных количество кортежей в выходных данных увеличивается или остается неизменным.

Примечание: CQ — это монотонно возрастающий класс запросов. Представьте произвольный запрос CQ к Q. Он состоит из select-project-join. Покажем, что каждый из них является монотонным оператором.

Добавим еще одну запись в D:

• select — Отфильтровать записи по вертикали. Если новая запись удовлетворяет запросу, пул ответов будет увеличен. В противном случае он остается прежним.

• project — не влияет на дополнительные кортежи

• join — набор ответов расширяется, если есть записи, соответствующие второму набору. в остальном он остается прежним.

Суперпозиция монотонных операторов монотонна => CQ — это класс монотонных запросов.

Вопрос: была ли исходная задача монотонной? Предположим, что есть только один сотрудник, Петя, работающий над двумя проектами A и B, поэтому всего два проекта A и B, и Петя должен быть включен в запрос. Допустим, вы добавляете третий проект C => Петя в настоящее время не отвечает, а набор ответов пуст. Это значит, что запросы не однообразны.

Отсюда логично вытекают следующие вопросы: что нужно добавить в select-project-join для выполнения задачи? Он должен быть немонотонным.

Конечно, как может догадаться читатель, это явная разница. Этот вид асимметрии побудил нас выбрать именно его.

Но, прежде чем писать решение, сделаем еще одно наблюдение. Это утверждение всегда истинно, если оно не имеет контрпримеров. Официально:

— Нет x, поэтому p(x) ложно.

В задании квантификатор «для всех» появляется явно, и для его имитации можно использовать двойное отрицание. Другими словами, перефразируйте запрос следующим образом:

Вывести имена всех сотрудников, у которых нет проектов, над которыми они не работают.

Этот же запрос выглядит невероятно просто, если бы у нас был  (а он есть в реляционном исчислении):

{ e.fname, e.lname | EMP(e) and  PRJ(p)  WORKS_ON(w) and w.Pno = p.Pnumber and e.Ssn = w.Essn}

Пример использования RA для оптимизации запросов

Также трансформация SQL в реляционную алгебру позволяет оптимизировать выполнение запроса. Рассмотрим простой пример:

Задача
Вывести все номера проектов, в которых бы работал сотрудник с фамилией Шмидт в качестве менеджера департамента, управляющего этим проектом.

Простое решение выглядит следующим образом:

Которое можно переписать в реляционную алгебру следующим образом:

Первая оптимизация — нужно использовать select как можно раньше, тогда Декартово произведение получит на вход отношения меньшего размера:

Select с равенством с константами является сильным ограничением и должен оцениваться и объединяться как можно раньше:

Сворачиваем Декартово произведение и select в join (эффективно реализовано с помощью настраиваемых индексов и структур данных):

Держите свой проект как можно более сдержанным, чтобы в дерево передавалась только необходимая информация:

Список источников

1. https://infopedia.su/14×5825.html

2. https://knowledge.allbest.ru/programming/3c0a65635a2ac79b4d43b88521216c26_0.html
3. https://elar.urfu.ru/bitstream/10995/40612/1/978-5-7996-1622-9_2016.pdf

4. https://savepearlharbor.com/?p=272335

5. https://lektsii.org/6-42451.html

6. https://habr.com/ru/post/275251/
7. https://www.pvsm.ru/logika/109259

Leave a Comment

3 + = 13