Реляционная алгебра. Язык SQL. Фомина И.А

Реляционная алгебра, операции реляционной алгебры

Реляционная алгебра. Язык SQL. Фомина И.А

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

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

Для каждой операции реляционной алгебры будет дана её реализация в виде запросов на языке SQL.

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

будем выполнять операции над отношениями (таблицами) с абстрактными данными, такими как R1, R2 (названия таблиц — отношений) и т.д. и А1, А2, А3 (названия атрибутов — столбцов) и h15, w11 и т.п.

(содержание записей таблиц базы данных).

Приоритеты выполнения операций реляционной алгебры (в порядке убывания пунктов списка, а в одном пункте — операции с равными приоритетами):

  • селекция, проекция
  • декартово произведение, соединение, пересечение, деление
  • объединение, разность.

Операция выборки работает с одним отношением и определяет результирующее отношение R, которое содержит только те кортежи (или строки, или записи), отношения , которые удовлетворяют заданному условию (предикату P).

Таким образом, операция выборки — унарная операция — и записывается следующим образом:

,

где P — предикат (логическое условие).

Запрос SQL

SELECT * from R3 WHERE A3>'d0'

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

R3
A1A2A3A4
3hhylms
4ppa1sr
1rrylms

Просматриваем столбец А3 и устанавливаем, что предикату A3>'d0' удовлетворяют записи в первой и третьей строках исходного отношения (так как номер буквы y в алфавите больше номера буквы d). В результате получаем следующее новое отношение, в котором две строки:

R
A1A2A3A4
3hhylms
1rrylms

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

А в материалах раздела «Программирование PHP/MySQL» Вы найдёт немало примеров комбинаций различных логических условий для выборок из базы данных.

Операция проекции

Операция проекции () работает, как и операция выборки, только с одним отношением и определяет новое отношение R, в котором есть лишь те атрибуты (столбцы), которые заданы в операции, и их значения.

Запрос SQL

SELECT DISTINCT A4, A3 from R3

Пусть вновь дано то же отношение R3:

R3
A1A2A3A4
3hhylms
4ppa1sr
1rrylms

Из исходного отношения выбираем только столбцы А4 и А3 и видим, что строки со значениями — первая и третья — идентичны. Исключаем дубликат (за это отвечает ключевое слово DISTINCT в SQL-запросе, которое говорит, что нужно выбрать только уникальные записи) и получаем следующее новое отношение, в котором два атрибута и две строки (записи):

Операция объединения

Результатом объединения двух множеств (отношений) А и В () будет такое множество (отношение) С, которое включает в себя те и только те элементы, которые есть или во множестве А или во множестве В.

Говоря упрощённо, все элементы множества А и множества В, за исключением дубликатов, образующихся за счёт того, что некоторые элементы есть и в первом, и во втором множестве.

Операция объединения реляционной алгебры идентична операции объединения множеств, которая также описана в материале «Множества и операции над множествами».

Запрос SQL

SELECT A1, A2, A3 from R1 UNION SELECT A1, A2, A3 from R2

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

R1R2
A1A2A3A1A2A3
Z7aaw11X8ppk21
B7hhh15Q2eeh15
X8ppw11X8ppw11

Объединяем строки первого и второго отношения и видим, что третья строка, которая является третьей и в первом, и во втором отношении — идентичны, поэтому её включаем в новое отношение только один раз. Получаем следующее отношение:

R
A1A2A3
Z7aaw11
B7hhh15
X8ppw11
X8ppk21
Q2eeh15

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

Операция пересечения

Результатом пересечения двух множеств (отношений) А и В () будет такое множество (отношение) С, которое включает в себя те и только те элементы, которые есть и во множестве А, и во множестве В. Операция пересечения реляционной алгебры идентична операции пересечения множеств, которая также описана в материале «Множества и операции над множествами».

Запрос SQL

SELECT A1, A2, A3 from R1 INTERSECT SELECT A1, A2, A3 from R2

В некоторых диалектах SQL отсутствует ключевое слово INTERSECT. Поэтому, например, в MySQL и других, операция пересечения множеств может реализована с применением предиката EXISTS.

Теперь посмотрим, что получится в результате выполнения этой операции реляционной алгебры и соответствующего ей запроса SQL. Вновь даны два отношения R1 и R2:

R1R2
A1A2A3A1A2A3
Z7aaw11X8ppk21
B7hhh15Q2eeh15
X8ppw11X8ppw11

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

Операция разности

Разность двух отношений R1 и R2 () состоит из кортежей (или записей, или строк), которые имеются в отношении R1, но отсутствуют в отношении R2. Отношения R1 и R2 должны быть совместимы по объединению. Операция разности реляционной алгебры идентична операции разности множеств, которая также описана в материале «Множества и операции над множествами».

Запрос SQL

SELECT A1, A2, A3 from R2 EXCEPT
SELECT A1, A2, A3 from R1

Установим, что получится в результате выполнения этой операции реляционной алгебры и соответствующего ей запроса SQL. Вновь даны два отношения R1 и R2:

R1R2
A1A2A3A1A2A3
Z7aaw11X8ppk21
B7hhh15Q2eeh15
X8ppw11X8ppw11

Из отношения R2 исключаем строку, которая есть также в отношении R2 — третью — и получаем новое отношение:

В некоторых диалектах SQL отсутствует ключевое слово EXCEPT. Поэтому, например, в MySQL и других, операция пересечения множеств может реализована с применением предиката NOT EXISTS.

Операция декартова произведения

Операция декартова произведения () определяет новое отношение R, которое является результатом конкатенации каждого кортежа отношения R1 с каждым кортежем отношения R2.

Запрос SQL

SELECT * from R3, R4

Установим, что получится в результате выполнения этой операции реляционной алгебры и соответствующего ей запроса SQL. Даны два отношения R3 и R4:

R3R4
A1A2A3A4A5A6
3hhylms3hh
4ppa1sr4pp
1rrylms

В новом отношении должны присутствовать все атрибуты (столбцы) двух отношений. Сначала первая строка отношения R3 сцепляется с каждой из двух строк отношения R4, затем вторая строка отношения R3, затем третья. В результате должно получиться 3 Х 2 = 6 кортежей (строк). Получаем такое новое отношение:

R
A1A2A3A4A5A6
3hhylms3hh
3hhylms4pp
4ppa1sr3hh
4ppa1sr4pp
1rrylms3hh
1rrylms4pp

Операция деления

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

Запрос SQL

SELECT DISTINCT A1, A4 from R5 WHERE
NOT EXIST (SELECT * from R6 WHERE NOT EXIST R6.A2 = R5.A2 AND

R6.A3 = R5.A3)

Давайте посмотрим, что получится в результате выполнения этой операции реляционной алгебры и соответствующего ей запроса SQL. Даны два отношения R5 и R6:

R5R6
A1A2A3A4A2A3
2S34sunR48
3X87kabX87
3R48kab

Комбинации всех кортежей отношения R6 соответствуют вторая и третья строки отношения R5. Но после исключения атрибутов (столбцов) А2 и А3 эти строки становятся идентичными. Поэтому в новом отношении присутствует эта строка один раз. Новое отношение:

Операция тета-соединения

В результате этой операции получается отношение, которое содержит кортежи из декартова произведения отношений R1 и R2 удовлетворяющие предикату Р. Значением предиката Р может быть один из операторов сравнения (, >=, = или !=).

Запрос SQL

SELECT * from R3, R4 WHERE A1>=A5

Посмотрим, что получится в результате выполнения этой операции реляционной алгебры и соответствующего ей запроса SQL. Даны два отношения R3 и R4:

R3R4
A1A2A3A4A5A6
3hhylms3hh
4ppa1sr4pp
1rrylms

Это таблицы (отношения) из главы о декартовом произведении. Выполняем операцию декартового произведения. Видим, что условию предиката Р удовлетворяет один кортеж декартового произведения — первый (так как 3>=3). Получаем следующее новое отношение:

R
A1A2A3A4A5A6
3hhylms3hh

Реляционные базы данных и язык SQL

с друзьями

Источник: https://function-x.ru/relation_algebra.html

Заметки о SQL и реляционной алгебре

Реляционная алгебра. Язык SQL. Фомина И.А

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

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

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

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

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

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

Selection (выборка; ограничение)

— selection (выборка; ограничение), A — отношение (предикат, таблица), – булева формула, по которой происходит отбор строк (кортежей, записей, etc)

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

Projection (проекция)

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

Переименование

— переименовывает колонку a в b в отношении A (атрибут, аргумент предиката, etc); два чая тому господину, который покажет, что алгебра строго более выразима с оператором переименования (нужно привести пример запроса, который не выразим без этого оператора, но выразим с )

Декартово произведение

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

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

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

Пусть у нас есть таблица StudentMark(Name, Mark, Subject, Date) – тогда кортеж (Вася, 5, Информатика, 05.10.2010) является упорядоченным – сначала строка Name на первой (ок, или нулевой) позиции, целое число на второй, строка на третьей и дата на четвертой.

При этом сами упорядоченные кортежи (Name, Mark, Subject, Date) не упорядочены «внутри» отношения.

Объединение

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

Пересечение

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

Разница множеств

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

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

Вспомогательные операторы

— join (соединение); join соединяет две записи таблиц 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 с соотвествующим значением.

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

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

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

SQL

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

{ X | φ(Х) }

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

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

в реляционном исчислении как:

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

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

Рассмотрим еще один простой пример: R(a,b,c) ∗ S(c,d,e), где * — это natural join, т.е. 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 = «банан»}

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

Обычно вместе с квантором всеобщности используют импликацию «=>», мы можем переписать запрос следующим образом:

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

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

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

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

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

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

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

Conjunctive Queries (CQ)

Запросы, которые состоят из 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 – это очень хороший класс сложности, т.е., запросы можно вычислять очень эффективно.

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

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) … }

Где [.] – опциональность квантора. Почему такое представление всегда допустимо? Потому что project здесь всегда может быть выражен через X т.е. , join выражен через равенство переменных в , а select через условия на в теле запроса.

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

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

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

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

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

Пусть исходный граф задан в виде множества ребер

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

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

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

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

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

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

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

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

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

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

Кодд: SQL — логика первого порядка Доказательство от противного, пусть T(a,b) — есть путь из а в б. P_n(a,b) — это путь из а в b длины n. Тогда ~P_n(a,b) — из а нет пути в 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, то есть не должно существовать пути никакой длины из а в b, а для выполнения T(a,b) такой путь должен существовать. Противоречие. Q.E.D. Если запрос не фиксирован, то задача становится тривиально разрешимой. Пусть у меня всего k ребер в базе данных, значит самый большой путь не более k, значит можно в явном виде записать запрос, как объединение путей длины 1, 2,… k и таким образом получить запрос вычисляющий достижимость в графе.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

— не существует х, такой что 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 в реляционную алгебру позволяет оптимизировать выполнение запроса. Рассмотрим простой пример:

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

оригинальная формулировкаList all project numbers for projects that involve an employee whose last name is Smith as a manager of the department that controls the project

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

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

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

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

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

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

Минутка саморекламыЕсть интересные задачи по data science, big data, machine learning, data mining — пишите.

Литература, материалы и слайды

Stanford online course — Jennifer Widom – отличный курс, рекомендую

Alice’s book — Serge Abiteboul — классика жанра

Мартин Грабер — SQL — довольно простые и детальные объяснения работы алгоритмов и синтаксиса SQL

Хабра-статьи про P-NP — ознакомительный материал часть первая и вторая

Мои слайды по теме (исключительно полезно из-за примеров решений задач в разных формализмах — местами смесь голландского и английского)

Неплохие слайды по теории (нетривиальный теоретический материал)

Источник: https://habr.com/post/275251/

Biz-books
Добавить комментарий