Реляционная алгебра и язык sql шпора

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

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

Операторы DDL (Data Definition Language) - операторы определения объектов базы данных:

· CREATE TABLE - создать таблицу,

· ALTER TABLE - изменить таблицу,

· DROP TABLE - удалить таблицу,

· CREATE DOMAIN - создать домен,

· ALTER DOMAIN - изменить домен,

· DROP DOMAIN - удалить домен,

· CREATE VIEW - создать представление,

· DROP VIEW - удалить представление.

Операторы DML (Data Manipulation Language) - операторы манипулирования данными:

· SELECT - отобрать строки из таблиц,

· INSERT - добавить строки в таблицу,

· UPDATE - изменить строки в таблице,

· DELETE - удалить строки в таблице,

· COMMIT - зафиксировать внесенные изменения,

· ROLLBACK - откатить внесенные изменения.

Любая операция реляционной алгебры может быть выражена одним оператором SELECT.

Последнее изменение этой страницы: 2016-12-16; Нарушение авторского права страницы

На Хабре и за его пределами часто обсуждают реляционную алгебру и SQL, но далеко не так часто акцентируют внимание на связи между этими формализмами. В данной статье мы отправимся к самым корням теории запросов: реляционному исчислению, реляционной алгебре и языку SQL. Мы разберем их на простых примерах, а также увидим, что бывает полезно переключаться между формализмами для анализа и написания запросов.

Зачем это может быть нужно сегодня? Не только специалистам по анализу данных и администраторам баз данных приходится работать с данными, фактически мало кому не приходится что-то извлекать из (полу-)структурированных данных или трансформировать уже имеющиеся. Для того, чтобы иметь хорошее представление почему языки запросов устроены определенным образом и осознанно их использовать нужно разобраться с ядром, лежащим в основе. Об этом мы сегодня и поговорим.

Большую часть статьи составляют примеры с вкраплениями теории. В конце разделов приведены ссылки на дополнительные материалы, а для заинтересовавшихся и небольшая подборка литературы и курсов в конце.

Основные операторы

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

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

Задачи для разогрева

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


(Схема взята из книги: Elmasri, Navathe – Fundamentals of Database systems; на всякий: крайне НЕ рекомендую книгу; см подборку в конце)

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

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

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

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

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

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

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

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

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

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

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

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

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

(далее решения не убраны под спойлеры)

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

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

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

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

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

Внимательный читатель сейчас мог бы воскликнуть: для чего козе баян? Нам тут что не хватает двух формализмов для написания запросов, к чему третий?

Реляционное исчисление — это адаптация логики первого порядка (FOL: first order logic) для написания запросов. FOL является одним из самых хорошо изученных формализмов математики и даёт возможность использовать уже созданный теоретический аппарат и классические результаты для анализа и написания запросов.

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

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

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

Рассмотрим простые примеры, на которых и разберем формализм:

Пусть R – отношение с тремя атрибутами a,b,c; тогда перепишем следующий запрос реляционной алгебры:

Переводя на простой язык r — это кортеж в R (то есть строка с атрибутами, значения которых можно получить через точку по имени, i.e., r.a — атрибут а кортежа r (строки) в отношении R (таблице)). Как мы видим никаких кванторов здесь нет, так как r — на выходе запроса и должен быть свободным кортежем.

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

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

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

Здесь можно найти краткую подборку задач на реляционное исчисление с решениями.

Говоря простым языком, теорема Кодда звучит так: все три формализма SQL, реляционная алгебра и реляционное исчисление равны. Вот тут много теории для заинтересовавшихся

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

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

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

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

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

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

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

• Если Q — фиксировано, то сложность вычисления f(D) называется сложностью по данным (data complexity)
• Если D — фиксировано, то сложность вычисления f(Q) называется сложностью запроса (query complexity)
• Если ничего не фиксировано, то сложность f(Q,D) называют комбинированной сложностью (combined complexity)

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

С теоретической точки зрения можно взглянуть на вот эту картинку:

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

Для заинтересовавшихся также рекомендую: теорема Трахтенброта

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

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

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

• Показать, что задача внутри NP класса
• Показать, что NP полная задача сводится к данной

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

Пусть D состоит из одного отношения edge = <(red,green),(green,red), (blue, red), (green,blue) … >— всех возможных правильных раскрасок графа, таких что никакие две вершины не имеют одинакового цвета.

Тогда, запишем следующий запрос

Вопрос со звёздочкой: из сегмента select-project-join выкидываем project, как изменится вычислительная сложность?

Определения сложности по данными и по запросу также проливают свет на один известный результат — в классическом SQL (без with) транзитивное замыкание невыразимо при фиксированном запросе т.е. нельзя написать один запрос такой, что для любой базы данных он вычислял бы замыкание предиката. То есть, если у нас есть граф сохраненный в виде отношения edge, то нельзя написать один фиксированный запрос, который бы для произвольного графа вычислял отношение достижимости. Хотя интуитивно кажется, что такой запрос явно должен лежать в классе СQ.

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

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

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

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

P_n(a,b) — из а нет пути в b длины n.

Возьмем следующее конечное множество

P_k(a,b)> — оно выполнимо, так как возьмем путь длины k+1 и T(a,b) выполнено и все

P_k тоже выполнены. Более того любое конечное множество такого вида выполнимо, а значит по теореме о компактности и их бесконечное объединение должно быть выполнимо.

P_k — должно быть верно для ЛЮБОГО k, то есть не должно существовать пути никакой длины из а в b, а для выполнения T(a,b) такой путь должен существовать. Противоречие. Q.E.D.

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

Теперь вернемся к задаче предложенной ранее:

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

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

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

Пусть мы добавили еще одну запись в D

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

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

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

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

Вопрос: является ли исходная задача монотонной? На самом деле нет. Пусть у нас только один работник Петя, который работает над двумя проектами А и Б, и всего у нас 2 проекта А и Б, значит Петя должен быть в выдаче запроса. Пусть мы добавили третий проект C => теперь Пети нет в ответе и ответное множество пусто, а значит запрос не монотонен.

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

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

Однако прежде, чем писать решение сделаем еще одно наблюдение: если контр-примера к утверждению не существуют, то это утверждение всегда верно. Формально:

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

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

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

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

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

Select c равенством константе сильное ограничение, поэтому его нужно вычислять и соединять как можно раньше:

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

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