Нотатки про SQL і реляційної алгебри



На Хабре і за його межами часто обговорюють реляційну алгебру і SQL, але далеко не так часто акцентують увагу на зв'язку між цими формализмами. У даній статті ми вирушимо до самих коренів теорії запитів: реляционному обчислення, реляційної алгебри та мови SQL. Ми розберемо їх на простих прикладах, а також побачимо, що буває корисно перемикатися між формализмами для аналізу і написання запитів.

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

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

Зміст


Реляційна алгебра
Основні оператори
A— А саме ставлення (відношення тут синонімічне з таблицею і предикатом) є вираженням реляційної алгебри, більше того, так як це алгебра, будь вираження реляційної алгебри повертає ставлення (властивість замикання операторів)

Selection (вибірка; обмеження)
\sigma_\phi (A)— selection (вибірка; обмеження), A — відношення (предикат, таблиця), \phi– булева формула, за якою відбувається відбір рядків (картежей, записів, etc)

Selection є по суті горизонтальним фільтром рядків, тобто можна уявити, що ми йдемо по кожному рядку і залишаємо тільки ті, що задовольняють умові \phi. Простий приклад для наочності:

Projection (проекція)
\Large \pi_{a,b,\dots}(A)— projection (проекція) на атрибути A, B,… Повертає таблицю, в якій залишаються тільки колонки (атрибути) A, B,… Простий приклад нижче. По суті є фільтром за атрибутами тобто це в деякому сенсі вертикальний фільтр.

Перейменування
\rho_{a,b} (A)— перейменовує колонку a в b відносно A (атрибут, аргумент предиката, etc); два чаю тому пану, який покаже, що алгебра строго більше можна виразити з оператором перейменування (потрібно навести приклад запиту, який не виразимо без цього оператора, але виразимо з \rho)

Декартів добуток
A \times B— Декартів добуток двох відносин, велике відношення з всіляких поєднань рядків A і B.

Операції над множинами
Реляційна алгебра є розширенням класичного набору операторів над множинами (відношення — це множина впорядкованих картежей; зауважте, що це зовсім не одно упорядкованому безлічі картежей). Нехай у нас є таблиця StudentMark(Name, Mark, Subject, Date) – тоді кортеж (Вася, 5, Інформатика, 05.10.2010) є впорядкованим – спочатку рядок Name на першій (ок, або нульовий) позиції, ціле число на другий, на третій рядок і дата на четвертій. При цьому самі впорядковані картежа (Name, Mark, Subject, Date) не впорядковані «всередині» відносини.

Об'єднання
A \cup B— об'єднання всіх рядків A і B, обмеження — однакові атрибут

Перетин
A \cap B— перетин рядків, таке ж обмеження

Різниця множин
B \backslash A— B мінус A, всі рядки, що присутні в B, але не присутні в A, таке ж обмеження

(B\A; A — зліва, B — праворуч)

Допоміжні оператори
A \bowtie_{\phi} B \equiv \sigma_{\phi} (A \times 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 та реляційною алгеброю в першому вирішенні

Як це не іронічно, але в SQL SELECT — це project (π; проекція) в реляційної алгебри.

Тепер розглянемо задачу з агрегацією і порівняємо її з рішенням на реляційної алгебри:

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

Реляційне числення
Уважний читач зараз міг би вигукнути: для чого козі баян? Нам тут що не вистачає двох формалізмів для написання запитів, до чого третій?

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

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

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

Нехай φ(Х) — формула першого порядку, а X — це вільні змінні, тобто, вони не квантифицированы (∀ – квантор загальності, ∃ – квантор існування), тоді запит в реляційному обчисленні задає безліч:

{ X | φ(Х) }

Розглянемо прості приклади, на яких і розберемо формалізм:

Нехай R – відношення з трьома атрибутами a,b,c; тоді перепишемо наступний запит реляційної алгебри:

\sigma_{a=b}(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 тобто X 
\subseteq \cup_i X_i, join виражений через рівність змінних X_i, а select через умови на X_iв тілі запиту.

Щоб показати, що задача належить до класу NP-повних, потрібно зробити дві речі
  • Показати, що завдання усередині класу NP
  • Показати, що NP-повна задача зводиться до даної
Перша умова виконується тривіально: так як значення відносин конєчни (т. е. безліч всіляких значень), то ми можемо недетерминированно «вгадати» функцію \alphaтаку, що робить справжніми кожне ставлення під квантором існування.

Покажемо, що завдання про розфарбування графа зводиться до задачі здійсненності CQ запиту.

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

Нехай вихідний граф заданий у вигляді безлічі ребер \textit{edge}=\{(v_i,v_j)\}

Тоді, запишемо наступний запит

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

Тобто кожній дузі у вихідному графі в запиті буде відповідати ставлення edge з відповідними аргументами. Якщо запит повернув порожній кортеж, то значить, що існує така функція \alpha, яка відображає V_i \mapsto \{red,green,blue\}, причому ніякі дві вершини не будуть мати однакову забарвлення (випливає з визначення 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 називається монотонним, тоді і тільки тоді коли для будь-яких двох баз даних D_1 \subseteq D_2вірно, що Q(D_1) \subseteq Q(D_2). Тобто збільшення бази даних може тільки збільшити кількість картежей на виході або залишиться тим самим.

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

Нехай ми додали ще одну запис в D
  • select — фільтрує записи по вертикалі, якщо нова запис задовольняє запиту, то безліч відповідей збільшується, якщо немає залишається тим самим.
  • project — не впливає на додатковий кортеж
  • join — якщо відповідний запис є і в другому множині, то відповідь безліч розшириться, інакше залишиться колишнім.
Суперпозиція монотонних операторів монотонна => CQ — клас монотонних запитів.

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

Звідси логічно випливає наступне запитання: що потрібно додати до select-project-join, щоб задача зважувалася? Це щось має бути немонотонний!

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

Однак перш, ніж писати рішення зробимо ще одне спостереження: якщо контр-приклад до затвердження не існують, то це твердження не завжди вірно. Формально:

\forall x: p(x) \equiv \lnot \exists x: \lnot p(x)— не існує х, такий, що p(x) є хибним.

У завдання ми бачимо в явному вигляді квантор «для всіх» і ми можемо його емулювати використовуючи подвійне заперечення, тобто перефразуємо запит наступним чином: вивести імена всіх співробітників для яких не існують проекту, над яким вони б не працювали

Цей запит виглядає неймовірно просто, якщо б у нас був \forall(а він є в реляційному обчисленні):

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

Приклад використання RA для оптимізації запитів
Також трансформація SQL в реляційну алгебру дозволяє оптимізувати виконання запиту. Розглянемо простий приклад:

Завдання
Вивести всі номери проектів, в яких би працював співробітник з прізвищем Шмідт в якості менеджера департаменту, керуючого цим проектом.
оригінальна формулюванняList all project numbers for projects that іnvolve 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 — ознайомчий матеріал частину перша і друга

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

Непогані слайди з теорії (нетривіальний теоретичний матеріал)

Джерело: Хабрахабр

0 коментарів

Тільки зареєстровані та авторизовані користувачі можуть залишати коментарі.