Реляционная алгебра и основы запросов SQL

В теме 2 отношение было определено как множество кортежей над схемой, а таблица SQL — как его практическое воплощение со своими отступлениями: строки могут повторяться, столбцы упорядочены, значение может отсутствовать (NULL). Там же были введены ключи и ограничения целостности, которые не дают занести в базу заведомо неверные данные. Однако база данных создаётся не ради хранения, а ради ответов на вопросы: какие книги дороже тысячи рублей, какие покупатели живут в городах без склада, какие книги написаны обоими Стругацкими. Остаётся открытым вопрос, на каком языке такие вопросы задавать и как СУБД понимает, что именно у неё спрашивают.

Ответ, предложенный Коддом одновременно с самой реляционной моделью, — реляционная алгебра: небольшой набор операций, каждая из которых получает одно или два отношения и возвращает новое отношение ¹. Алгебра важна по двум причинам. Во-первых, она задаёт точный смысл запроса: любое предложение SQL, о котором пойдёт речь в этой и следующих темах, можно перевести в выражение алгебры, и тогда спор «что вернёт запрос» решается вычислением. Во-вторых, выражения алгебры можно преобразовывать, сохраняя результат, и именно этим занимается оптимизатор СУБД, выбирая из множества эквивалентных выражений самое дешёвое.

Изложение построено так. Первые три раздела посвящены алгебре: основным операциям, соединениям и делению, эквивалентным преобразованиям и связи с реляционным исчислением. Все операции показаны на маленьких отношениях из первых строк учебной базы «Книжный узел», а результаты проверены запросами SQL. Вторая половина темы переходит к языку SQL: логическому порядку выполнения запроса SELECT и его следствиям, условиям и выражениям, сортировке, ограничению выборки и операциям над множествами. Рассматриваются запросы к одной таблице; соединения в SQL изучаются в теме 4, группировка и агрегатные функции — в теме 5.

Реляционная алгебра: основные операции

Операнды, операции и замкнутость

Реляционная алгебра (англ. relational algebra) — совокупность операций над отношениями, результат каждой из которых снова является отношением ¹³⁵. Последнее свойство называется замкнутостью (англ. closure) и составляет главное достоинство алгебры: раз результат операции — отношение, к нему можно применить следующую операцию, и из простых операций строятся выражения любой сложности, как в школьной алгебре из сложения и умножения строятся многочлены. Выражение реляционной алгебры (англ. relational algebra expression) — это либо имя отношения, либо операция, применённая к выражениям.

Операции делятся на унарные, с одним операндом (выборка, проекция, переименование), и бинарные, с двумя (объединение, разность, пересечение, декартово произведение, соединения, деление). Кодд в исходной статье и последующих работах выделил набор, через который выражаются все остальные: выборка, проекция, переименование, объединение, разность и декартово произведение ²³. Пересечение, соединения и деление — производные операции, введённые ради удобства и потому, что для них существуют эффективные алгоритмы выполнения.

Важно помнить, что алгебра работает с отношениями в строгом смысле темы 2: отношение — множество, поэтому в нём нет повторяющихся кортежей и нет порядка ни строк, ни атрибутов; атрибуты различаются по именам. Каждая операция, результат которой мог бы содержать одинаковые кортежи (проекция, объединение), по определению их устраняет. Отсутствующих значений в классической алгебре тоже нет; Дейт последовательно отстаивает именно такую, «чистую» модель и критикует SQL за отступления от неё ⁵. Как SQL отступает от этих правил и к каким последствиям это приводит, обсуждается в разделе о запросе SELECT.

В печатных учебниках условие и список атрибутов операции записываются нижним индексом. В тексте темы принята линейная запись, понятная без набора формул: параметр операции пишется в квадратных скобках сразу после её знака, например σ[цена > 1000](Книга). Выражения алгебры даются моноширинным шрифтом.

Учебные отношения

Для ручных вычислений возьмём из учебной базы шесть книг и их авторов, оставив только нужные атрибуты. Отношения Книга, Автор и Авторство показаны в таблице ниже; их можно создать в схеме ra скриптом ra.sql из окружения лабораторной работы 3 и проверять любое выражение запросом. В SQL имена этих таблиц пишутся строчными буквами: ra.книга, ra.автор, ra.авторство.

Отношение Авторство реализует связь «многие ко многим» между книгами и авторами: у «Пикника на обочине» два автора, и каждый из Стругацких написал две книги. Отношение Класс понадобится для примера соединения по неравенству: нижняя граница класса включается, верхняя нет.

Выборка, проекция и переименование

Выборка (англ. selection, также restriction) σ[F](R) возвращает те кортежи отношения R, для которых истинно условие F. Условие строится из сравнений атрибутов с константами или друг с другом операторами =, ≠, <, ≤, >, ≥ и связок ∧, ∨, ¬. Схема результата совпадает со схемой R, а мощность не больше мощности R. Выборка «вырезает» строки таблицы:

σ[рубрика = 6 ∧ цена > 500](Книга)
  = { (4, Пикник на обочине, 6, 520), (5, Трудно быть богом, 6, 540) }

Проекция (англ. projection) π[A1, …, Ak](R) оставляет в каждом кортеже только перечисленные атрибуты и удаляет получившиеся дубликаты. Проекция «вырезает» столбцы, и именно устранение дубликатов отличает её от простого вычёркивания столбцов таблицы. Из шести кортежей Автор проекция на страну даёт три:

π[страна](Автор) = { (Россия), (СССР), (США) }

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

Переименование (англ. rename) ρ[S(B1, …, Bn)](R) возвращает то же отношение под именем S с атрибутами B1, …, Bn. Операция ничего не вычисляет, но без неё нельзя обойтись в двух случаях: когда отношение участвует в выражении дважды (например, чтобы найти пары соавторов, Авторство соединяется само с собой, и атрибуты двух копий надо различить) и когда атрибуты нужно согласовать по именам для объединения или естественного соединения. В SQL переименованию соответствуют псевдонимы таблиц и столбцов (FROM book AS b, price * 1.2 AS new_price).

Операции комбинируются. Названия и цены книг рубрики 6 записываются выражением π[название, цена](σ[рубрика = 6](Книга)), а в SQL — запросом, в котором проекции соответствует список SELECT, а выборке — предложение WHERE:

SELECT DISTINCT название, цена
FROM ra.книга
WHERE рубрика = 6;

     название      |  цена
-------------------+--------
 Пикник на обочине | 520.00
 Трудно быть богом | 540.00
(2 rows)

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

Объединение, разность и пересечение

Теоретико-множественные операции применимы только к совместимым отношениям (англ. union-compatible): с одинаковым числом атрибутов и одинаковыми доменами соответствующих атрибутов ³. Если имена атрибутов различаются, их предварительно согласуют переименованием. Для совместимых R и S:

• объединение (англ. union) R ∪ S содержит кортежи, входящие хотя бы в одно из отношений;
• разность (англ. difference) R − S — кортежи R, не входящие в S;
• пересечение (англ. intersection) R ∩ S — кортежи, входящие в оба отношения.

Пересечение не является базовой операцией: R ∩ S = R − (R − S). Объединение и пересечение коммутативны и ассоциативны, разность — нет. Типичное применение разности — вопросы с отрицанием «которые не…»: номера книг, у которых нет ни одного автора из США, — это все номера книг минус номера книг американских авторов:

π[книга](Книга) − π[книга](Авторство ⋈ σ[страна = 'США'](Автор))
  = {1, 2, 4, 5, 7, 10} − {7, 10} = {1, 2, 4, 5}

Знак ⋈ обозначает естественное соединение, о котором речь пойдёт в следующем разделе. Заметим характерную ошибку: выражение π[книга](σ[страна ≠ 'США'](Авторство ⋈ Автор)) отвечает на другой вопрос — «у каких книг есть хотя бы один автор не из США» — и для книги, написанной совместно американцем и россиянином, дало бы противоположный ответ. Отрицание «ни одного» выражается разностью, а не условием «не равно» внутри выборки.

На реальных данных учебной базы теоретико-множественные операции хорошо видны на городах. Города, где есть покупатели, но нет склада, дают разность проекций двух таблиц; в SQL ей соответствует оператор EXCEPT, подробно рассмотренный в конце темы:

SELECT city FROM customer
EXCEPT
SELECT city FROM warehouse
ORDER BY city;

     city
--------------
 Екатеринбург
 Самара
 Томск

(4 rows)

Четвёртая, пустая на вид строка — это NULL: у 471 покупателя город не указан. В классической алгебре такого значения нет, а SQL при выполнении EXCEPT считает два NULL «одинаковыми» и потому оставляет NULL в результате. К этой особенности вернёмся в разделе о логическом порядке выполнения.

Соединения и деление

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

Декартово произведение (англ. Cartesian product, cross product) R × S состоит из всех кортежей, полученных приписыванием к каждому кортежу R каждого кортежа S. Схема результата — объединение схем (одноимённые атрибуты предварительно переименовываются), мощность — произведение мощностей: |Книга × Класс| = 6 · 3 = 18. Само по себе произведение редко бывает ответом на вопрос: в нём каждая книга сочетается с каждым ценовым классом, и большинство сочетаний бессмысленны. Но за ним почти всегда следует выборка, отбирающая осмысленные сочетания.

Пара «произведение, затем выборка» настолько частая, что для неё введена отдельная операция — тета-соединение (англ. theta join): R ⋈[θ] S = σ[θ](R × S), где θ — условие, связывающее атрибуты обоих операндов. Название происходит от греческой буквы, которой традиционно обозначают произвольный оператор сравнения. Если условие состоит только из равенств, соединение называют эквисоединением (англ. equijoin). Отнесём каждую книгу к ценовому классу — это соединение по неравенству:

Книга ⋈[от ≤ цена ∧ цена < до] Класс

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

SELECT к.книга, к.название, к.цена, л.класс
FROM ra.книга AS к
JOIN ra.класс AS л ON л.от <= к.цена AND к.цена < л.до
ORDER BY к.книга;

 книга |          название          |  цена   |  класс
-------+----------------------------+---------+---------
     1 | Война и мир                | 1290.00 | средняя
     2 | Преступление и наказание   |  450.00 | дешёвая
     4 | Пикник на обочине          |  520.00 | средняя
     5 | Трудно быть богом          |  540.00 | средняя
     7 | Искусство программирования | 3990.00 | дорогая
    10 | Основание                  |  610.00 | средняя
(6 rows)

Определение через произведение задаёт смысл операции, но не способ её выполнения: СУБД не строит произведение, а применяет специальные алгоритмы соединения — вложенные циклы, хеширование, слияние, — которые изучаются в теме 11.

Естественное соединение

Естественное соединение (англ. natural join) R ⋈ S — эквисоединение по всем одноимённым атрибутам, после которого из каждой пары одинаковых атрибутов оставлен один. Учебные отношения специально построены так, что общие атрибуты имеют общие имена: у Книга и Авторство общий атрибут «книга», у Авторство и Автор — «автор». Поэтому выражение Книга ⋈ Авторство ⋈ Автор соединяет книги с авторами «по смыслу» и даёт восемь кортежей — по одному на каждый кортеж Авторства, со всеми атрибутами книги и автора. Естественное соединение ассоциативно, и скобки в такой цепочке можно не ставить.

Удобство естественного соединения оборачивается хрупкостью: условие соединения не записано явно, а выводится из имён. Если бы у отношений Книга и Автор оказался общий атрибут с одинаковым именем, но разным смыслом (скажем, «страна» как страна издания и страна автора), соединение молча добавило бы бессмысленное условие равенства и потеряло бы кортежи. Если общих атрибутов нет вовсе, естественное соединение вырождается в декартово произведение. По этой причине в SQL естественным соединением пользуются редко — подробно в теме 4.

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

π[автор, соавтор](σ[автор < соавтор](Авторство ⋈ ρ[А2(книга, соавтор)](Авторство)))

Соединение даёт двенадцать кортежей (книга 4 и книга 5 — по четыре сочетания двух авторов, остальные шесть книг — по одному), выборка оставляет два: (4, 4, 5) и (5, 4, 5). Проекция сливает их в единственный кортеж (4, 5): Аркадий и Борис Стругацкие. Здесь хорошо видно, что устранение дубликатов в проекции — не формальность, а часть смысла ответа.

Полусоединение и антисоединение

Часто соединение нужно не для того, чтобы получить атрибуты второго отношения, а лишь чтобы проверить, есть ли для кортежа пара. Для этого служат две производные операции ⁴:

• левое полусоединение (англ. semijoin) R ⋉ S — кортежи R, для которых в S найдётся хотя бы один кортеж с совпадающими общими атрибутами; по определению R ⋉ S = π[атрибуты R](R ⋈ S);
• антисоединение (англ. antijoin, anti-semijoin) R ▷ S — кортежи R, для которых такого кортежа нет: R ▷ S = R − (R ⋉ S).

Схема результата обеих операций совпадает со схемой R, а мощность не превосходит мощности R: полусоединение не размножает кортежи, даже если пара находится многократно. Книги американских авторов — полусоединение, книги, у которых нет авторов из СССР, — антисоединение:

Книга ⋉ (Авторство ⋈ σ[страна = 'США'](Автор))   = книги 7, 10
Книга ▷ (Авторство ⋈ σ[страна = 'СССР'](Автор))  = книги 1, 2, 7, 10

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

SELECT к.книга, к.название
FROM ra.книга AS к
WHERE NOT EXISTS (SELECT 1
                  FROM ra.авторство AS w
                  JOIN ra.автор AS а ON а.автор = w.автор
                  WHERE w.книга = к.книга AND а.страна = 'СССР')
ORDER BY к.книга;

 книга |          название
-------+----------------------------
     1 | Война и мир
     2 | Преступление и наказание
     7 | Искусство программирования
    10 | Основание
(4 rows)

Полусоединение и антисоединение важны и для реализации: планировщик PostgreSQL распознаёт в запросах эти операции и выполняет их специальными узлами плана Semi Join и Anti Join (тема 11).

Деление

Деление (англ. division) отвечает на вопросы с квантором всеобщности: «книги, написанные всеми Стругацкими», «покупатели, купившие все книги серии», «книги, которые есть на всех складах». Пусть R имеет атрибуты X ∪ Y, а S — атрибуты Y. Частное R ÷ S — это множество тех значений x атрибутов X, для которых в R присутствуют сочетания x со всеми кортежами S ¹³:

R ÷ S = { x | для каждого y ∈ S кортеж (x, y) ∈ R }

Название операции оправдано тождеством (R × S) ÷ S = R для непустого S: деление обращает декартово произведение, как деление чисел обращает умножение. Вычислим вручную, какие книги написаны обоими Стругацкими. Делимое — Авторство(книга, автор), делитель — номера авторов-Стругацких:

S = π[автор](σ[имя LIKE '%Стругацкий'](Автор)) = { (4), (5) }
Авторство ÷ S

Сгруппируем кортежи делимого по книге и для каждой книги выпишем множество её авторов: книга 1 — {1}, книга 2 — {2}, книга 4 — {4, 5}, книга 5 — {4, 5}, книга 7 — {7}, книга 10 — {10}. Книга входит в частное, если её множество авторов содержит весь делитель {4, 5}. Ответ — книги 4 и 5. Рисунок показывает эту проверку.

Деление не базовая операция; через базовые она выражается так ³:

R ÷ S = π[X](R) − π[X]((π[X](R) × S) − R)

Смысл формулы прочитывается справа налево. π[X](R) × S — все сочетания «кандидат, требуемый элемент», которые должны были бы присутствовать, если бы каждый кандидат подходил. Вычитая R, получаем недостающие сочетания. Их проекция на X — кандидаты, которым чего-то не хватает, и, вычитая их из всех кандидатов, получаем ответ. Для нашего примера: кандидатов шесть, требуемых сочетаний 6 · 2 = 12, из них в Авторстве есть четыре, недостающих восемь — у книг 1, 2, 7 и 10; остаются книги 4 и 5.

Две тонкости деления встречаются в задачах постоянно. Первая — пустой делитель: если S пуст, условие «для каждого y ∈ S» истинно для любого x, и частное равно π[X](R). Например, «покупатели, купившие все книги несуществующей серии» — это все покупатели, у которых есть хоть одна покупка; на практике такой ответ часто неожидан, и его стоит оговаривать. Вторая — лишние атрибуты делимого: если в R кроме X и Y есть ещё атрибут (например, количество экземпляров на складе), его надо отбросить проекцией до деления, иначе он попадёт в X и разобьёт группы. В SQL деление записывается двойным NOT EXISTS — «нет такого требуемого элемента, для которого нет пары»; эта форма разбирается в теме 4.

Алгебраические выражения, исчисление и оптимизация

Реляционное исчисление и декларативность SQL

Алгебра процедурна в том смысле, что выражение предписывает последовательность операций: сначала выборка, потом соединение, потом проекция. Кодд предложил и другой, непроцедурный язык — реляционное исчисление (англ. relational calculus), основанное на логике предикатов первого порядка ². Запрос исчисления кортежей (англ. tuple relational calculus) описывает свойства искомых кортежей, ничего не говоря о том, как их найти:

{ t | t ∈ Книга ∧ t.цена > 1000 }

{ k.книга | k ∈ Книга ∧
            ∀a ∈ Автор ( a.имя LIKE '%Стругацкий' →
                         ∃w ∈ Авторство ( w.книга = k.книга ∧ w.автор = a.автор ) ) }

Первое выражение читается: «все кортежи t из Книга, у которых цена больше 1000». Второе — запрос с делением: «номера книг k, такие что для любого автора a с фамилией Стругацкий существует кортеж Авторства, связывающий k и a». Квантор всеобщности ∀, который в алгебре приходится выражать хитрой формулой с разностями, здесь записывается прямо. Существует и исчисление доменов (англ. domain relational calculus), в котором переменные пробегают значения атрибутов, а не кортежи; на нём основан язык Query-by-Example.

Кодд доказал, что алгебра и исчисление (в его безопасной форме, исключающей бесконечные ответы вроде «все кортежи, не входящие в Книга») равны по выразительной силе: всякий запрос исчисления выражается в алгебре, и наоборот ². Язык, способный выразить любой запрос реляционной алгебры, называют реляционно полным (англ. relationally complete). SQL реляционно полон и выходит за рамки алгебры: в нём есть агрегирование, сортировка, рекурсия, арифметика.

Синтаксис SQL ближе к исчислению: запрос описывает, что нужно получить (из каких таблиц, при каком условии, какие столбцы), а не как. Это свойство называют декларативностью (англ. declarative language). Задача перевести декларативный запрос в эффективную процедуру ложится на СУБД: запрос разбирается, переводится во внутреннее представление, близкое к дереву операций алгебры, и оптимизатор ищет эквивалентное дерево с наименьшей стоимостью. Так был устроен уже первый оптимизатор System R ⁶, и так устроены оптимизаторы современных СУБД, включая PostgreSQL (тема 11).

Дерево операций

Выражение алгебры удобно изображать деревом операций (англ. expression tree, query tree): листья — исходные отношения, внутренние узлы — операции, корень — последняя операция, дающая ответ. Данные текут снизу вверх: каждый узел получает результаты дочерних узлов и передаёт свой результат родителю. Дерево наглядно показывает, какие промежуточные отношения возникают при вычислении и каков их размер, а размер промежуточных результатов и определяет стоимость запроса.

Возьмём вопрос «названия книг авторов из Германии» над полными таблицами учебной базы. Прямой перевод формулировки даёт выражение

π[title](σ[country = 'Германия'](book ⋈ book_author ⋈ author))

и дерево с выборкой над результатом двух соединений. Это дерево изображено на рисунке ниже слева.

Правила эквивалентности

Два выражения алгебры эквивалентны, если на любых допустимых отношениях дают одинаковый результат. Учебники приводят десятки правил эквивалентности ³⁴; основные из них таковы (R, S — выражения, F, G — условия):

• каскад выборок: σ[F ∧ G](R) ≡ σ[F](σ[G](R)), и выборки перестановочны: σ[F](σ[G](R)) ≡ σ[G](σ[F](R));
• каскад проекций: если список A содержится в B, то π[A](π[B](R)) ≡ π[A](R);
• коммутативность и ассоциативность соединения и произведения: R ⋈ S ≡ S ⋈ R, (R ⋈ S) ⋈ T ≡ R ⋈ (S ⋈ T);
• проталкивание выборки через соединение: если условие F использует только атрибуты R, то σ[F](R ⋈ S) ≡ σ[F](R) ⋈ S;
• проталкивание выборки через объединение, разность и пересечение: σ[F](R − S) ≡ σ[F](R) − σ[F](S);
• проталкивание проекции: до соединения можно отбросить атрибуты, не нужные ни в результате, ни в условии соединения;
• превращение произведения в соединение: σ[F](R × S) ≡ R ⋈[F] S.

Правила обоснованы определениями операций. Например, проталкивание выборки через соединение верно потому, что кортеж соединения удовлетворяет условию на атрибуты R тогда и только тогда, когда ему удовлетворяет образующий его кортеж R. Но правила имеют условия применимости, и их нарушение — источник ошибок: условие, затрагивающее атрибуты обоих операндов, нельзя опустить к одному из них, а проекцию нельзя протолкнуть через разность (π[A](R − S) в общем случае не равно π[A](R) − π[A](S), в чём легко убедиться на двух кортежах, совпадающих по A).

Проталкивание выборки на данных «Книжного узла»

Оценим, что даёт проталкивание выборки в примере с немецкими авторами, по реальным мощностям таблиц учебной базы: в book 2010 строк, в book_author 2424, в author 210, из них 28 авторов из Германии.

Если вычислять выражение буквально по определению, через декартово произведение, промежуточное отношение book × book_author × author содержало бы 2010 · 2424 · 210 = 1 023 170 400 кортежей — миллиард с лишним. Именно поэтому никакая СУБД не выполняет соединение через произведение. Если соединения выполняются как соединения, но выборка стоит над ними (левое дерево на рисунке), оба соединения дают по 2424 кортежа (у каждой строки book_author ровно одна книга и один автор), и лишь затем выборка оставляет 330 кортежей. Если же выборку опустить к author (правое дерево), то первое соединение получает на вход 28 авторов вместо 210, его результат — 330 кортежей, и второе соединение работает уже с ними. Промежуточные результаты сократились в семь с лишним раз, а ответ не изменился: 330 строк, относящихся к 322 различным книгам (несколько книг написаны двумя немецкими авторами, и проекция π[title] в алгебре слила бы такие строки).

Эвристика «выполнять выборки как можно раньше» — одна из первых, которые применяет оптимизатор. Однако окончательный выбор порядка соединений и алгоритмов делается не по эвристикам, а по оценке стоимости с использованием статистики о данных ⁶; об этом — в теме 11. Для автора запросов отсюда следует важный вывод: порядок, в котором записаны таблицы и условия в запросе SQL, не определяет порядок их обработки. Запрос описывает результат, а не план.

Запрос SELECT: структура и логический порядок выполнения

Предложения запроса SELECT

Запрос SELECT состоит из предложений (англ. clauses), каждое из которых отвечает за свой шаг преобразования данных ⁸⁹:

Обязательно только само слово SELECT со списком выражений: SELECT 2 + 2 — корректный запрос PostgreSQL. Предложения записываются в строго определённом порядке, который совпадает с порядком в таблице, за исключением того, что SELECT и DISTINCT пишутся первыми. Простейший запрос к одной таблице выбирает строки по условию:

SELECT book_id, title, price
FROM book
WHERE category_id = 6 AND price < 300;

 book_id |         title          | price
---------+------------------------+--------
     148 | Секреты вычислений 148 | 239.99
     248 | Практика звёзд 248     | 279.99
     385 | Введение в Python 385  | 189.99
     858 | Практика времени 858   | 229.99
(4 rows)

Здесь и далее запросы выполняются в базе bookstore с путём поиска search_path = bookstore, поэтому имена таблиц пишутся без схемы. Порядок строк в выводе этого запроса никак не гарантирован: в нём нет ORDER BY.

Логический порядок выполнения

Порядок, в котором предложения записываются, не совпадает с порядком, в котором они логически применяются. Логический порядок выполнения (англ. logical query processing order) определяет, какие имена и значения доступны на каждом шаге ⁸⁹:

1. FROM — формируется исходный набор строк; если таблиц несколько, они соединяются (тема 4).
2. WHERE — отбрасываются строки, для которых условие не истинно (ложно или неизвестно).
3. GROUP BY — оставшиеся строки разбиваются на группы.
4. HAVING — отбрасываются группы, не удовлетворяющие условию.
5. SELECT — вычисляются выражения списка выборки, им присваиваются псевдонимы (здесь же вычисляются оконные функции, тема 5).
6. DISTINCT — устраняются повторяющиеся строки.
7. Операции над множествами UNION, INTERSECT, EXCEPT, если запрос из них состоит.
8. ORDER BY — строки упорядочиваются.
9. LIMIT/OFFSET или FETCH FIRST — выдаётся нужная часть строк.

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

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

Следствия логического порядка: псевдонимы, ORDER BY и DISTINCT

Из логического порядка вытекает правило, на котором спотыкаются почти все начинающие: псевдоним столбца, введённый в списке SELECT, нельзя использовать в WHERE, потому что WHERE применяется раньше, чем вычисляется список выборки.

SELECT title, price * 1.2 AS new_price
FROM book
WHERE new_price > 4000;

ERROR:  column "new_price" does not exist
LINE 3: WHERE new_price > 4000;
              ^

Правильно повторить выражение в условии; в ORDER BY, который выполняется после SELECT, псевдоним уже доступен:

SELECT title, price * 1.2 AS new_price
FROM book
WHERE price * 1.2 > 4000
ORDER BY new_price DESC;

               title               | new_price
-----------------------------------+-----------
 Искусство программирования. Том 1 |  4788.000
(1 row)

По той же причине псевдоним нельзя использовать в GROUP BY и HAVING — так требует стандарт. PostgreSQL в виде расширения разрешает в GROUP BY ссылаться на псевдоним или номер столбца результата, но в WHERE и HAVING — нет ⁹. Когда выражение длинное и повторять его не хочется, его выносят в подзапрос в FROM или в общее табличное выражение WITH (темы 4 и 6).

Второе следствие касается ORDER BY. Сортировка выполняется после SELECT, но в PostgreSQL ей доступны и столбцы исходной таблицы, не вошедшие в список выборки: SELECT title FROM book ORDER BY price корректен. Исключение — запрос с DISTINCT: после устранения дубликатов одной строке результата может соответствовать много исходных строк с разными значениями, и сортировать по ним невозможно.

SELECT DISTINCT city FROM customer ORDER BY registered_at;

ERROR:  for SELECT DISTINCT, ORDER BY expressions must appear in select list
LINE 1: SELECT DISTINCT city FROM customer ORDER BY registered_at;
                                                    ^

Третье следствие — порядок вычисления условий внутри WHERE не определён. Условие price > 0 AND 1000 / price > 2 не защищено от деления на ноль: СУБД вправе вычислить вторую часть первой, и документация PostgreSQL прямо предупреждает, что на порядок вычисления операндов AND и OR полагаться нельзя; если порядок важен, используется выражение CASE ¹⁰.

Мультимножества и NULL: где SQL отступает от алгебры

Таблица SQL — мультимножество (англ. multiset, bag): одинаковые строки допустимы, и запрос не устраняет их, пока его не попросят ³⁸. Так сделано ради скорости — устранение дубликатов требует сортировки или хеширования всего результата — и потому, что иногда дубликаты несут смысл (две одинаковые позиции чека). Поэтому SELECT city FROM customer возвращает 5000 строк, по одной на покупателя, а проекции алгебры π[city](customer) соответствует только запрос с DISTINCT:

SELECT DISTINCT city FROM customer ORDER BY city;

      city
-----------------
 Екатеринбург
 Казань
 Москва
 Новосибирск
 Самара
 Санкт-Петербург
 Томск

(8 rows)

Восьмая строка — NULL. Здесь проявляется второе отступление SQL от алгебры: при устранении дубликатов, группировке и операциях над множествами два NULL считаются неразличимыми (англ. not distinct), хотя в условиях WHERE сравнение NULL = NULL даёт не истину, а неизвестность (тема 2). Стандарт формулирует это различие через два отношения: равенство значений в условиях и «неразличимость» (англ. distinctness) при сравнении строк в DISTINCT, GROUP BY, UNION ⁷.

PostgreSQL дополнительно поддерживает нестандартную форму DISTINCT ON (выражения), которая оставляет из каждой группы строк с одинаковыми значениями выражений первую по порядку ORDER BY ⁹. Это удобный, но непереносимый приём; в стандартном SQL та же задача решается оконными функциями (тема 5).

Условия, выражения и функции

Сравнения, BETWEEN, IN и NULL в условиях

Условие в WHERE — логическое выражение, построенное из сравнений =, <> (или !=), <, <=, >, >= и связок AND, OR, NOT. Приоритет связок обычный: NOT сильнее AND, AND сильнее OR, и условие a OR b AND c означает a OR (b AND c). При смешении связок скобки лучше ставить явно.

Для частых форм условий есть сокращения ¹¹. Предикат x BETWEEN a AND b означает x >= a AND x <= b — обе границы включаются. Предикат x IN (v1, v2, v3) означает x = v1 OR x = v2 OR x = v3. Книг, изданных в 2000–2009 годах, и книг из трёх подрубрик программирования (Python, C и C++, Java — рубрики 18, 19, 20) в учебной базе соответственно:

SELECT count(*) FROM book WHERE pub_year BETWEEN 2000 AND 2009;   -- 575
SELECT count(*) FROM book WHERE category_id IN (18, 19, 20);      -- 315

Функция count(*) подсчитывает строки результата; агрегатные функции подробно рассматриваются в теме 5, здесь она используется лишь как способ узнать число строк. Включение обеих границ в BETWEEN — частый источник ошибок с датами и временем: условие created_at BETWEEN '2024-01-01' AND '2024-01-31' для столбца типа timestamptz не захватит заказы, сделанные 31 января после полуночи. Для интервалов надёжнее полуоткрытая форма created_at >= '2024-01-01' AND created_at < '2024-02-01'.

Главная ловушка условий — NULL. По правилам трёхзначной логики (тема 2) любое сравнение с NULL даёт неизвестность, а WHERE оставляет только строки, где условие истинно. Поэтому условие и его отрицание вместе не покрывают таблицу:

SELECT count(*) FROM book WHERE publisher_id = 4;      -- 186
SELECT count(*) FROM book WHERE publisher_id <> 4;     -- 1729
SELECT count(*) FROM book WHERE publisher_id IS NULL;  -- 95

186 + 1729 = 1915, а книг 2010: 95 книг без издательства (среди них «Искусство программирования» Кнута) не входят ни в первый, ни во второй результат. Вопрос «книги не издательства АСТ» на естественном языке обычно подразумевает и книги без издательства, и тогда условие пишется как publisher_id IS DISTINCT FROM 4 или publisher_id <> 4 OR publisher_id IS NULL. Та же природа у ловушки NOT IN со списком, содержащим NULL, — она подробно разбирается в теме 4.

Поиск по шаблону: LIKE, ILIKE и регулярные выражения

Предикат LIKE сравнивает строку с шаблоном, в котором % обозначает любую последовательность символов (в том числе пустую), а _ — ровно один символ ¹¹. Сравнение учитывает регистр; в PostgreSQL есть нестандартный вариант ILIKE, не учитывающий регистр:

SELECT count(*) FROM book WHERE title LIKE 'Искусство%';   -- 208
SELECT count(*) FROM book WHERE title LIKE '%python%';     -- 0
SELECT count(*) FROM book WHERE title ILIKE '%python%';    -- 167

В названиях книг слово Python пишется с прописной буквы, поэтому LIKE '%python%' не находит ничего. Если сами символы % или _ нужно искать буквально, их экранируют обратной косой чертой: LIKE '%10\%%'. Шаблон, начинающийся с %, требует просмотра каждой строки; когда поиск по шаблону может использовать индекс, а когда нет, — вопрос темы 10.

Для более сложных шаблонов PostgreSQL поддерживает регулярные выражения POSIX операторами ~ (с учётом регистра), ~* (без учёта), !~ и !~* (отрицания). Стандартный предикат SIMILAR TO использует гибрид синтаксисов LIKE и регулярных выражений и на практике применяется редко ¹¹. Найдём книги, название которых начинается со слова «Тайна» или «Хроники» и заканчивается двузначным номером от 10 до 19:

SELECT book_id, title
FROM book
WHERE title ~ '^(Тайна|Хроники) .* 1[0-9]$';

 book_id |        title
---------+---------------------
      13 | Тайна времени 13
      17 | Тайна звёзд 17
      18 | Тайна баз данных 18
(3 rows)

В отличие от LIKE, регулярное выражение ищет совпадение в любом месте строки, если не привязано якорями ^ (начало) и $ (конец). Без якоря $ под шаблон подошли бы и названия с номерами 100–199 и 1000–1999.

Выражение CASE и обзор функций

Выражение CASE — условное выражение SQL: проверяет условия по порядку и возвращает значение первой истинной ветви, а если ни одна не подошла, — значение ветви ELSE или NULL при её отсутствии ¹⁰¹¹. CASE — выражение, а не оператор управления, поэтому его можно использовать всюду, где допустимо значение: в списке SELECT, в WHERE, в ORDER BY. Классифицируем книги по цене:

SELECT book_id, title, price,
       CASE WHEN price = 0    THEN 'бесплатно'
            WHEN price < 500  THEN 'дешёвая'
            WHEN price < 1500 THEN 'средняя'
            ELSE 'дорогая'
       END AS price_class
FROM book
WHERE book_id <= 10
ORDER BY book_id;

 book_id |               title               |  price  | price_class
---------+-----------------------------------+---------+-------------
       1 | Война и мир                       | 1290.00 | средняя
       2 | Преступление и наказание          |  450.00 | дешёвая
       3 | Евгений Онегин                    |  390.00 | дешёвая
       4 | Пикник на обочине                 |  520.00 | средняя
       5 | Трудно быть богом                 |  540.00 | средняя
       6 | Убийство в «Восточном экспрессе»  |  480.00 | дешёвая
       7 | Искусство программирования. Том 1 | 3990.00 | дорогая
       8 | Высоконагруженные приложения      | 2390.00 | дорогая
       9 | PostgreSQL 16 изнутри             |    0.00 | бесплатно
      10 | Основание                         |  610.00 | средняя
(10 rows)

Порядок ветвей важен: бесплатная книга удовлетворяет и условию price < 500, но попадает в первую подходящую ветвь. Вторая форма, CASE выражение WHEN значение THEN …, сравнивает одно выражение с несколькими значениями на равенство. Родственные функции COALESCE(a, b, …) (первое не-NULL значение) и NULLIF(a, b) (NULL, если a = b) — сокращения частых выражений CASE, введённые в теме 2.

Функций в PostgreSQL сотни, и их полный перечень — глава 9 документации ¹¹. Для запросов к одной таблице чаще всего нужны функции, сведённые в таблицу.

Две особенности этих функций заслуживают отдельного внимания. Деление целых чисел в PostgreSQL целочисленное (7 / 2 = 3), как в Python оператор //; чтобы получить дробный результат, один из операндов делают типа numeric. Оператор конкатенации || возвращает NULL, если хотя бы один операнд NULL, а функция concat пропускает NULL-аргументы:

SELECT 'Книга: ' || title || ', издательство ' || publisher_id AS s1,
       concat('Книга: ', title, ', издательство ', publisher_id) AS s2
FROM book
WHERE book_id IN (6, 7);

                           s1                            |                           s2
---------------------------------------------------------+---------------------------------------------------------
 Книга: Убийство в «Восточном экспрессе», издательство 3 | Книга: Убийство в «Восточном экспрессе», издательство 3
                                                         | Книга: Искусство программирования. Том 1, издательство
(2 rows)

У книги Кнута издательство не указано, и выражение с || целиком превратилось в NULL. Функции дат работают с типами date, timestamp, timestamptz и interval. Например, для первого заказа учебной базы:

SELECT created_at,
       created_at::date                 AS d,
       extract(year FROM created_at)    AS y,
       date_trunc('month', created_at)  AS m,
       created_at + interval '14 days'  AS deadline
FROM orders
WHERE order_id = 1;

          created_at           |     d      |  y   |           m            |           deadline
-------------------------------+------------+------+------------------------+-------------------------------
 2023-09-27 13:27:48.308747+03 | 2023-09-27 | 2023 | 2023-09-01 00:00:00+03 | 2023-10-11 13:27:48.308747+03
(1 row)

Значения типа timestamptz выводятся в часовом поясе сеанса (параметр TimeZone, здесь Europe/Moscow), поэтому при другом поясе у вас время и, возле полуночи, даже дата будут другими. Типы даты и времени и работа с часовыми поясами — предмет темы 9.

Сортировка, ограничение выборки и операции над множествами

ORDER BY: ключи сортировки, NULL и правила сравнения строк

Отношение не упорядочено, и таблица SQL тоже: без ORDER BY СУБД возвращает строки в том порядке, в котором ей удобно, и этот порядок может измениться после обновления данных, создания индекса или смены плана ⁸. Если порядок важен — для отчёта, для постраничного вывода, для сравнения результатов, — он задаётся явно. ORDER BY принимает список ключей сортировки: строки упорядочиваются по первому ключу, при равенстве — по второму и так далее; у каждого ключа своё направление ASC (по возрастанию, по умолчанию) или DESC.

Место NULL при сортировке стандарт оставляет на усмотрение реализации; PostgreSQL считает NULL больше любого значения, поэтому при ASC NULL оказываются в конце, а при DESC — в начале ⁸. Это даёт неожиданный результат в запросе «пять самых молодых авторов»:

SELECT full_name, birth_year FROM author ORDER BY birth_year DESC LIMIT 5;

    full_name     | birth_year
------------------+------------
 Татьяна Попов    |
 Мартин Клеппман  |
 Анна Кузнецов    |
 Егор Рогов       |
 Мария Виноградов |
(5 rows)

У 27 авторов год рождения неизвестен, и все пять мест заняли они (в каком порядке между собой — не определено). Явное указание NULLS LAST и второй ключ сортировки дают осмысленный и воспроизводимый ответ:

SELECT full_name, birth_year
FROM author
ORDER BY birth_year DESC NULLS LAST, full_name
LIMIT 5;

   full_name   | birth_year
---------------+------------
 Андрей Попов  |       2004
 Ирина Волков  |       2004
 Ирина Орлов   |       2004
 Мария Иванов  |       2004
 Ольга Соколов |       2004
(5 rows)

Сортировка строк зависит от правила сравнения (англ. collation) — набора правил, определяющих порядок символов с учётом языка, регистра и диакритики ¹². Правило задаётся при создании базы (обычно по локали операционной системы), может быть указано для столбца и для отдельного выражения конструкцией COLLATE. Разница хорошо видна на кириллице:

SELECT x FROM (VALUES ('ёж'), ('еж'), ('Ель'), ('яблоко'), ('Яма'), ('Эра')) AS v(x)
ORDER BY x COLLATE "C";
-- Ель, Эра, Яма, еж, яблоко, ёж

SELECT x FROM (VALUES ('ёж'), ('еж'), ('Ель'), ('яблоко'), ('Яма'), ('Эра')) AS v(x)
ORDER BY x COLLATE "ru-x-icu";
-- еж, ёж, Ель, Эра, яблоко, Яма

Правило "C" сравнивает коды символов Unicode: все прописные буквы идут раньше строчных, а «ё» (код U+0451) оказывается после «я». Правило "ru-x-icu" из библиотеки ICU сортирует по правилам русского языка. Следствие для практики: результат ORDER BY title на разных серверах может различаться, если базы созданы с разными правилами сравнения. Учебная база в окружении проверки создана с правилом C.UTF-8; на вашем сервере порядок строк в запросах с сортировкой по тексту может отличаться. Подробнее о правилах сравнения и их влиянии на индексы — в темах 9 и 10.

LIMIT, OFFSET и FETCH FIRST

Предложение LIMIT n ограничивает результат первыми n строками, OFFSET m пропускает первые m строк. Стандарт SQL с 2008 года определяет эквивалентную форму OFFSET m ROWS FETCH FIRST n ROWS ONLY; LIMIT — распространённое, но нестандартное расширение, которое PostgreSQL поддерживает наряду со стандартной формой ⁸⁹. Без ORDER BY ограничение выборки бессмысленно: «первые n строк» неупорядоченного множества — это n каких-то строк.

Даже с ORDER BY результат может оказаться неоднозначным, если у строк на границе одинаковые ключи сортировки:

SELECT title, price FROM book ORDER BY price DESC LIMIT 3;

               title               |  price
-----------------------------------+---------
 Искусство программирования. Том 1 | 3990.00
 Теория Python 905                 | 2999.99
 Теория моря 1202                  | 2999.99
(3 rows)

Книг ценой 2999.99 четыре, и какие две из них попадут в ответ, не определено. Есть два честных решения. Первое — добавить ключ, делающий порядок однозначным (ORDER BY price DESC, book_id). Второе — стандартная форма WITH TIES, появившаяся в PostgreSQL 13: она выдаёт вместе с последней строкой все строки с теми же значениями ключей сортировки ⁹:

SELECT title, price FROM book ORDER BY price DESC FETCH FIRST 3 ROWS WITH TIES;

               title               |  price
-----------------------------------+---------
 Искусство программирования. Том 1 | 3990.00
 Теория Python 905                 | 2999.99
 Теория моря 1202                  | 2999.99
 Теория времени 1491               | 2999.99
 Секреты забытого города 1454      | 2999.99
(5 rows)

Пара LIMIT/OFFSET — простейший способ постраничного вывода: страница k по 20 строк — это ORDER BY … LIMIT 20 OFFSET 20 * (k − 1). Способ прост, но плохо масштабируется: чтобы выдать строки с 100 001 по 100 020, СУБД должна получить и отбросить первые 100 000, так что каждая следующая страница дороже предыдущей. Кроме того, если между запросами страниц в таблицу добавлены строки, они сдвигают границы, и пользователь видит повторы или пропуски. Альтернатива — пагинация по ключу (англ. keyset pagination): следующая страница запрашивается условием «ключ больше последнего показанного» (WHERE (price, book_id) > (169.99, 1987)), и при наличии индекса стоимость не зависит от номера страницы ¹³. Этот приём и его связь с индексами подробно рассматриваются в теме 10.

UNION, INTERSECT и EXCEPT

Операции над множествами SQL соответствуют операциям алгебры ∪, ∩ и −: UNION, INTERSECT, EXCEPT ⁸. Операнды должны иметь одинаковое число столбцов совместимых типов; имена столбцов результата берутся из первого запроса, а сопоставление столбцов идёт по позиции, а не по имени. По умолчанию операции устраняют дубликаты, как в алгебре; с ключевым словом ALL они работают с мультимножествами: UNION ALL просто дописывает строки второго запроса к первому, INTERSECT ALL оставляет строку столько раз, сколько минимум её вхождений в операнды, EXCEPT ALL — разность кратностей.

Города, где есть склады или издательства, — объединение (14 строк при UNION ALL, 5 при UNION):

SELECT city FROM warehouse
UNION
SELECT city FROM publisher
ORDER BY city;

      city
-----------------
 Казань
 Москва
 Новосибирск
 Санкт-Петербург

(5 rows)

Пятая строка — снова NULL: у издательства «Северный узел» город не указан. Города, где есть и покупатели, и склады, — пересечение; результат — все четыре города складов. Предложение ORDER BY в составном запросе относится ко всему результату, а не к последнему операнду, и потому пишется один раз в конце; там же пишутся LIMIT и OFFSET. Чтобы отсортировать или ограничить отдельный операнд, его заключают в скобки. Если в одном запросе встречаются несколько операций, INTERSECT связывает сильнее, чем UNION и EXCEPT, а операции одного уровня выполняются слева направо ⁸.

Выбор между UNION и UNION ALL — не стилистический. UNION устраняет дубликаты, для чего СУБД вынуждена сортировать или хешировать весь результат; если операнды заведомо не пересекаются (например, выбирают строки разных статусов), UNION ALL даёт тот же ответ дешевле. Если же дубликаты возможны и важны (подсчёт всех строк), UNION молча исказит результат. Оператор EXCEPT удобен для сравнения двух наборов строк: два запроса возвращают одно и то же множество строк, если обе разности, A EXCEPT B и B EXCEPT A, пусты. Этим приёмом пользуются при проверке переписанных запросов и миграций данных (темы 4 и 8).

Итоги темы

Реляционная алгебра — замкнутый набор операций над отношениями: выборка и проекция вырезают строки и столбцы, переименование согласует имена, объединение, разность и пересечение работают с совместимыми отношениями, декартово произведение и соединения сочетают кортежи разных отношений, полусоединение и антисоединение проверяют наличие пары, деление отвечает на вопросы «для всех». Базовых операций шесть, остальные выражаются через них, но имеют собственные эффективные алгоритмы. Отрицание в вопросах выражается разностью или антисоединением, квантор всеобщности — делением, и умение распознать в формулировке вопроса эти конструкции — главный навык, который даёт алгебра.

Выражение алгебры можно изображать деревом операций и преобразовывать по правилам эквивалентности. Проталкивание выборки к листьям дерева на данных учебной базы уменьшает промежуточные результаты в семь раз, не меняя ответа; такими преобразованиями и оценками стоимости занимается оптимизатор. Реляционное исчисление описывает результат логической формулой, равносильно алгебре по выразительной силе и показывает, откуда в SQL декларативность: запрос задаёт, что нужно получить, а план выполнения выбирает СУБД.

Запрос SELECT записывается в одном порядке, а логически выполняется в другом: FROM, WHERE, GROUP BY, HAVING, SELECT, DISTINCT, ORDER BY, LIMIT. Из этого порядка следуют правила видимости псевдонимов и ограничения на ORDER BY при DISTINCT. SQL отступает от алгебры в двух отношениях — таблицы являются мультимножествами, и в них есть NULL, — и большинство ошибок в простых запросах связано именно с этими отступлениями: забытый DISTINCT, потерянные строки с NULL в условии «не равно», NULL в начале сортировки по убыванию, неоднозначный LIMIT без уникального ключа сортировки.

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

Литература

1. Codd E. F. A Relational Model of Data for Large Shared Data Banks. — Communications of the ACM, 1970, Т. 13, № 6, С. 377–387, DOI: 10.1145/362384.362685.
2. Codd E. F. Relational Completeness of Data Base Sublanguages. — In: Rustin R. (ed.) Data Base Systems. Courant Computer Science Symposia Series, Vol. 6. — Prentice-Hall, 1972, С. 65–98.
3. Silberschatz A., Korth H. F., Sudarshan S. Database System Concepts. 7th ed. — McGraw-Hill, 2019.
4. Garcia-Molina H., Ullman J. D., Widom J. Database Systems: The Complete Book. 2nd ed. — Pearson Prentice Hall, 2008.
5. Дейт К. Дж. Введение в системы баз данных. 8-е изд. — М.: Вильямс, 2005.
6. Selinger P. G., Astrahan M. M., Chamberlin D. D., Lorie R. A., Price T. G. Access Path Selection in a Relational Database Management System. — Proceedings of the 1979 ACM SIGMOD International Conference on Management of Data, 1979, С. 23–34, DOI: 10.1145/582095.582099.
7. ISO/IEC 9075-2:2023. Information technology — Database languages SQL — Part 2: Foundation (SQL/Foundation). — ISO, 2023.
8. PostgreSQL Global Development Group. PostgreSQL 16 Documentation. Chapter 7. Queries. — 2024. https://www.postgresql.org/docs/16/queries.html
9. PostgreSQL Global Development Group. PostgreSQL 16 Documentation. SELECT. — 2024. https://www.postgresql.org/docs/16/sql-select.html
10. PostgreSQL Global Development Group. PostgreSQL 16 Documentation. 4.2. Value Expressions. — 2024. https://www.postgresql.org/docs/16/sql-expressions.html
11. PostgreSQL Global Development Group. PostgreSQL 16 Documentation. Chapter 9. Functions and Operators. — 2024. https://www.postgresql.org/docs/16/functions.html
12. PostgreSQL Global Development Group. PostgreSQL 16 Documentation. 24.2. Collation Support. — 2024. https://www.postgresql.org/docs/16/collation.html
13. Winand M. Paging Through Results. — Use The Index, Luke! https://use-the-index-luke.com/sql/partial-results/fetch-next-page

Дополнительные материалы

Вопросы для самопроверки

1. Что означает замкнутость реляционной алгебры и почему без неё нельзя было бы строить вложенные выражения?
2. Какие операции реляционной алгебры считаются базовыми и как через них выражаются пересечение, тета-соединение, полусоединение и деление?
3. Чем проекция реляционной алгебры отличается от списка столбцов в SELECT без DISTINCT? Приведите пример, когда результаты различаются по числу строк.
4. Какие условия должны выполняться, чтобы к двум отношениям можно было применить объединение или разность? Зачем при этом бывает нужно переименование?
5. Почему вопрос «книги, у которых нет авторов из США» нельзя записать выборкой с условием страна ≠ 'США' после соединения? Как он записывается правильно?
6. В каком случае естественное соединение вырождается в декартово произведение, а в каком — молча теряет кортежи? Приведите пример на отношениях учебной базы.
7. Чем полусоединение R ⋉ S отличается от проекции соединения на атрибуты R при наличии у кортежа R нескольких пар в S?
8. Что вернёт деление при пустом делителе и почему? Почему лишние атрибуты делимого нужно отбросить до деления?
9. Почему проталкивание выборки к листьям дерева операций не меняет результата, но уменьшает стоимость? Через какие операции выборку проталкивать нельзя?
10. Что утверждает теорема Кодда о реляционной полноте и почему SQL называют декларативным языком?
11. Перечислите предложения запроса SELECT в логическом порядке выполнения. Какие ошибки объясняются этим порядком?
12. Почему в PostgreSQL при ORDER BY … DESC строки с NULL оказываются первыми? Как это изменить?
13. Почему сортировка строк по тексту может давать разный порядок на двух серверах с одинаковыми данными?
14. Чем LIMIT/OFFSET отличается от FETCH FIRST … ROWS ONLY и от FETCH FIRST … WITH TIES? Почему глубокая пагинация через OFFSET медленная?
15. Почему EXCEPT оставляет в результате NULL, хотя NULL = NULL не истинно?

Глоссарий темы

Шпаргалка по инструментам

Реляционная алгебра и её запись в SQL (схема ra из окружения ЛР 3):

σ[F](R)            SELECT * FROM r WHERE F
π[a, b](R)         SELECT DISTINCT a, b FROM r
ρ[S(x, y)](R)      SELECT a AS x, b AS y FROM r AS s
R ∪ S, R − S, R ∩ S    UNION, EXCEPT, INTERSECT
R × S              SELECT * FROM r CROSS JOIN s
R ⋈[F] S           SELECT * FROM r JOIN s ON F
R ⋉ S              SELECT * FROM r WHERE EXISTS (SELECT 1 FROM s WHERE …)
R ▷ S              SELECT * FROM r WHERE NOT EXISTS (SELECT 1 FROM s WHERE …)
R ÷ S              двойное NOT EXISTS (тема 4)

Запрос к одной таблице:

SELECT [DISTINCT] выражение [AS псевдоним], ...
FROM таблица [AS псевдоним]
WHERE условие
ORDER BY ключ1 [ASC | DESC] [NULLS FIRST | NULLS LAST], ключ2 ...
LIMIT n OFFSET m;                      -- или: OFFSET m ROWS FETCH FIRST n ROWS ONLY

запрос1 UNION [ALL] запрос2            -- также INTERSECT [ALL], EXCEPT [ALL]
ORDER BY ...;                          -- относится ко всему составному запросу

Условия и выражения:

x BETWEEN a AND b                      -- обе границы включаются
x IN (1, 2, 3)
x IS NULL, x IS NOT NULL
x IS DISTINCT FROM y                   -- «не равно» с NULL как обычным значением
s LIKE 'Ис%_'  s ILIKE '%python%'      -- % — любая строка, _ — один символ
s ~ '^Тайна'   s ~* 'python'           -- регулярные выражения POSIX
CASE WHEN условие THEN v1 WHEN ... ELSE v2 END
coalesce(a, b), nullif(a, b)
length(s), lower(s), upper(s), left(s, n), substr(s, from, len), position(sub IN s),
replace(s, from, to), trim(s), split_part(s, ' ', 2), s1 || s2, concat(s1, s2, ...)
round(x, n), trunc(x), ceil(x), floor(x), abs(x), x % y
now(), current_date, extract(year FROM ts), date_trunc('month', ts), age(ts1, ts2),
ts + interval '14 days', ts::date, to_char(ts, 'DD.MM.YYYY')
x COLLATE "C", x COLLATE "ru-x-icu"

Метакоманды psql, полезные в теме:

\pset null '∅'        показывать NULL видимым символом
\x auto               расширенный вывод для широких строк
\d таблица            столбцы, типы, ограничения
\df lower             сигнатуры функции
\dOS+ ru*             правила сравнения
\timing on            время выполнения запросов
\o файл / \o          перенаправить вывод в файл и обратно

Что почитать и посмотреть

• Codd E. F. A Relational Model of Data for Large Shared Data Banks — https://doi.org/10.1145/362384.362685. Основополагающая статья: определение отношения, операции над отношениями, мотивация независимости данных. Короткая и до сих пор понятная.
• Silberschatz A., Korth H. F., Sudarshan S. Database System Concepts, 7th ed., глава 2 «Introduction to the Relational Model» и глава 16 «Query Optimization» (правила эквивалентности). Наиболее систематическое учебное изложение алгебры и её связи с оптимизатором; сайт книги — https://db-book.com.
• Garcia-Molina H., Ullman J. D., Widom J. Database Systems: The Complete Book, глава 2 (алгебра) и глава 5 (алгебра мультимножеств, расширенные операции). Подробно разобрано, как алгебра меняется при переходе к мультимножествам — именно то, чем SQL отличается от классической модели.
• Дейт К. Дж. Введение в системы баз данных — главы о реляционной алгебре и реляционном исчислении. Строгое изложение с критикой отступлений SQL от реляционной модели (дубликаты, NULL, порядок столбцов).
• PostgreSQL 16 Documentation. Chapter 7. Queries — https://www.postgresql.org/docs/16/queries.html. Официальное описание табличных выражений, списка выборки, DISTINCT, сортировки, LIMIT/OFFSET и операций над множествами; короткие примеры к каждой конструкции.
• PostgreSQL 16 Documentation. 9.7. Pattern Matching — https://www.postgresql.org/docs/16/functions-matching.html. LIKE, SIMILAR TO и регулярные выражения POSIX с полным описанием синтаксиса и отличий от Perl.
• Use The Index, Luke! Paging Through Results — https://use-the-index-luke.com/sql/partial-results/fetch-next-page. Объяснение, почему OFFSET дорог, и как устроена пагинация по ключу; продолжение — в теме 10.
• CMU 15-445/645 Database Systems (Andy Pavlo), лекция «Relational Model & Algebra» — https://15445.courses.cs.cmu.edu. Видеолекция и слайды: алгебра, её роль в оптимизаторе, история SQL.
• RelaX — relational algebra calculator — https://dbis-uibk.github.io/relax/. Онлайн-калькулятор реляционной алгебры: можно вводить выражения с σ, π, ⋈, ÷ над собственными малыми отношениями и смотреть дерево операций и результат. Удобен для самопроверки задач практического занятия.
• Википедия, статья «Relational algebra» (англ.) — краткая сводка операций с обозначениями, в том числе полусоединения, антисоединения и внешних соединений.

Углубление (по желанию)

Алгебра мультимножеств

Поскольку таблицы SQL — мультимножества, для точного описания смысла запросов SQL используется алгебра мультимножеств (англ. bag algebra). В ней каждый кортеж имеет кратность, и операции определены через кратности: при объединении кратности складываются (UNION ALL), при пересечении берётся минимум (INTERSECT ALL), при разности — разность, но не меньше нуля (EXCEPT ALL), при проекции кратности суммируются, а при произведении — перемножаются. Часть законов классической алгебры в алгебре мультимножеств перестаёт выполняться. Например, для множеств R ∩ (S ∪ T) = (R ∩ S) ∪ (R ∩ T), а для мультимножеств с объединением-суммой это неверно: пусть R, S и T содержат по одному кортежу t; слева кратность t равна min(1, 2) = 1, справа — 1 + 1 = 2. Оптимизатор обязан учитывать такие различия: преобразование, корректное для UNION, может быть некорректным для UNION ALL.

Почему SQL допускает дубликаты

Кодд считал отношения множествами, а в System R, первом прототипе SQL, решили не устранять дубликаты автоматически. Причины прагматические: устранение дубликатов требует сортировки или хеширования, то есть дополнительной работы над всем результатом, а пользователю часто нужны все строки (например, для подсчёта). Дейт и Дарвен многие годы критикуют это решение: из-за дубликатов перестают выполняться законы алгебры, и два запроса, эквивалентные для множеств, дают разное число строк. Результат компромисса виден в синтаксисе: в SQL множество — это то, о чём надо попросить словом DISTINCT, а мультимножество — поведение по умолчанию; у операций над множествами наоборот — по умолчанию дубликаты устраняются, а мультимножественная форма требует слова ALL.

Реляционное исчисление в языках запросов

Кроме SQL, на идеях реляционного исчисления построены и другие языки. QUEL, язык СУБД Ingres, был ближе к исчислению кортежей, чем SQL: переменные кортежей объявлялись явно (range of b is book). Язык Query-by-Example, созданный в IBM в 1970-х, основан на исчислении доменов: пользователь заполняет «шаблоны таблиц» значениями и переменными, и этот подход до сих пор живёт в визуальных конструкторах запросов. Datalog — язык логического программирования без функций — позволяет записывать запросы правилами вида «ответ(x) ← книга(x, …), авторство(x, y), автор(y, …, 'США')» и естественно выражает рекурсию; его идеи повлияли на рекурсивные запросы SQL (тема 6) и на современные системы анализа программ и графов.

Практическое занятие 3. Реляционная алгебра

• Раздел курса: тема 3 «Реляционная алгебра и основы запросов SQL»

Цель занятия

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

Краткая теория

Параметр операции записывается в квадратных скобках после её знака: σ[цена > 1000](Книга). R и S — отношения, F — условие, A — список атрибутов.

Требования и полезные тождества:

• объединение, разность и пересечение применимы только к совместимым отношениям: одинаковое число атрибутов, одинаковые домены; при разных именах атрибутов их согласуют переименованием;
• мощности: |σ[F](R)| ≤ |R|, |π[A](R)| ≤ |R|, |R × S| = |R| · |S|, |R ⋉ S| ≤ |R|;
• R ∩ S = R − (R − S); R ⋉ S = π[атрибуты R](R ⋈ S); R ▷ S = R − (R ⋉ S);
• R ÷ S = π[X](R) − π[X]((π[X](R) × S) − R); при пустом S частное равно π[X](R); лишние атрибуты делимого отбрасываются проекцией до деления;
• если в естественном соединении у операндов нет общих атрибутов, оно вырождается в декартово произведение; если общих атрибутов больше, чем нужно по смыслу, оно молча добавляет лишние условия равенства.

Правила эквивалентности: σ[F ∧ G](R) ≡ σ[F](σ[G](R)); σ[F](R ⋈ S) ≡ σ[F](R) ⋈ S, если F использует только атрибуты R; σ[F](R − S) ≡ σ[F](R) − σ[F](S) ≡ σ[F](R) − S; σ[F](R ∪ S) ≡ σ[F](R) ∪ σ[F](S); соединение коммутативно и ассоциативно; проекция не проталкивается через разность.

Признаки в формулировке вопроса: «хотя бы один», «есть» — соединение или полусоединение; «ни одного», «не», «никогда» — разность или антисоединение; «все», «каждый», «любой» — деление; «только», «исключительно» — разность «все минус те, у кого есть что-то другое».

Отношения для задач

Отношения взяты из учебной базы «Книжный узел» (книги и авторы) и дополнены условными данными. Их можно создать в схеме ra базы bookstore скриптом ra.sql из окружения лабораторной работы 3 и проверять ответы запросами; в SQL имена пишутся строчными: ra.книга.

Обратите внимание на одноимённые атрибуты: «книга» связывает Книгу, Авторство, Наличие и Покупку; «автор» — Автор и Авторство; «покупатель» — Покупателя и Покупку; «склад» — Склад и Наличие. Атрибуты «имя» (у Автора и Покупателя) и «город» (у Склада и Покупателя) совпадают по имени, но не по смыслу — это источник ошибок в естественных соединениях.

Разобранные примеры

Пример 1. Вычисление выражения по шагам

Условие. Вычислить π[название](σ[страна = 'СССР'](Автор) ⋈ Авторство ⋈ Книга) и сформулировать вопрос, на который отвечает выражение.

Решение. Вычисляем изнутри наружу, выписывая промежуточные отношения.

1. σ[страна = 'СССР'](Автор) = {(4, Аркадий Стругацкий, СССР), (5, Борис Стругацкий, СССР)} — два кортежа.
2. Соединение с Авторством по общему атрибуту «автор»: каждому из двух авторов соответствуют кортежи Авторства (4, 4), (5, 4) для автора 4 и (4, 5), (5, 5) для автора 5. Результат — четыре кортежа со схемой (автор, имя, страна, книга): (4, Аркадий Стругацкий, СССР, 4), (4, Аркадий Стругацкий, СССР, 5), (5, Борис Стругацкий, СССР, 4), (5, Борис Стругацкий, СССР, 5).
3. Соединение с Книгой по атрибуту «книга»: к каждому кортежу добавляются название, рубрика и цена. Общих атрибутов, кроме «книга», нет (у Книги нет атрибутов «имя» и «страна»), поэтому лишних условий не возникает. Четыре кортежа.
4. Проекция на «название»: «Пикник на обочине» встречается дважды (от двух авторов), «Трудно быть богом» — дважды. После устранения дубликатов остаются два кортежа.

Ответ: {(Пикник на обочине), (Трудно быть богом)}. Вопрос: «названия книг, у которых есть хотя бы один автор из СССР». Заметим, что выборка применена к Автору до соединения — это то же выражение, что и π[название](σ[страна = 'СССР'](Автор ⋈ Авторство ⋈ Книга)), но с меньшими промежуточными отношениями: четыре кортежа вместо восьми.

Пример 2. Отрицание: разность вместо «не равно»

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

Решение. Сначала найдём тех, кто покупал книги Стругацких, — это «положительная» часть вопроса:

С  = π[книга](Авторство ⋈ σ[имя LIKE '%Стругацкий'](Автор))      = {4, 5}
ПС = π[покупатель](Покупка ⋈ С)                                     = {1, 2, 3}

Покупка ⋈ С оставляет кортежи (1, 4), (1, 5), (2, 4), (3, 4), (3, 5), проекция даёт покупателей 1, 2, 3. Ответ — все покупатели, кроме них:

π[покупатель, имя](Покупатель) − π[покупатель, имя](Покупатель ⋈ ПС)
  = {(4, Пётр), (5, Елена)}

Равносильная запись с антисоединением: π[покупатель, имя](Покупатель ▷ ПС). Пётр не покупал ничего — он тоже входит в ответ, и это правильно: он «не покупал ни одной книги Стругацких».

Теперь ошибочный вариант: π[покупатель](Покупка ⋈ Авторство ⋈ σ[имя NOT LIKE '%Стругацкий'](Автор)). Он находит покупателей, купивших хотя бы одну книгу не Стругацких: {1, 3, 5}. Анна и Мария покупали и Стругацких, и других авторов — они ошибочно попали в ответ; Пётр, не покупавший ничего, ошибочно выпал. Проверка в SQL:

SELECT покупатель, имя FROM ra.покупатель
EXCEPT
SELECT п.покупатель, п.имя
FROM ra.покупатель п
JOIN ra.покупка USING (покупатель)
JOIN ra.авторство USING (книга)
JOIN ra.автор а USING (автор)
WHERE а.имя LIKE '%Стругацкий'
ORDER BY 1;

 покупатель |  имя
------------+-------
          4 | Пётр
          5 | Елена
(2 rows)

Пример 3. Деление: покупатели, купившие все книги рубрики

Условие. Найти покупателей, купивших все книги рубрики 5. Вычислить по формуле деления через базовые операции и записать в SQL.

Решение. Делимое — Покупка(покупатель, книга), X = покупатель, Y = книга. Делитель — требуемые книги: S = π[книга](σ[рубрика = 5](Книга)) = {1, 2}.

1. Кандидаты: π[покупатель](Покупка) = {1, 2, 3, 5}.
2. Все требуемые сочетания: {1, 2, 3, 5} × {1, 2} — восемь кортежей: (1, 1), (1, 2), (2, 1), (2, 2), (3, 1), (3, 2), (5, 1), (5, 2).
3. Недостающие сочетания: вычитаем Покупку. В Покупке есть (1, 1), (3, 1), (3, 2); остаются (1, 2), (2, 1), (2, 2), (5, 1), (5, 2).
4. Кандидаты, которым чего-то не хватает: проекция на покупателя — {1, 2, 5}.
5. Ответ: {1, 2, 3, 5} − {1, 2, 5} = {3}, то есть Мария.

Проверка по определению: множество книг Марии {1, 2, 4, 5} содержит {1, 2}; у Анны {1, 4, 5} нет книги 2. В SQL деление записывается двойным отрицанием — «нет такой книги рубрики 5, которую покупатель не купил»:

SELECT п.покупатель, п.имя
FROM ra.покупатель п
WHERE EXISTS (SELECT 1 FROM ra.покупка x WHERE x.покупатель = п.покупатель)
  AND NOT EXISTS (
        SELECT 1 FROM ra.книга к
        WHERE к.рубрика = 5
          AND NOT EXISTS (SELECT 1 FROM ra.покупка x
                          WHERE x.покупатель = п.покупатель AND x.книга = к.книга));

 покупатель |  имя
------------+-------
          3 | Мария
(1 row)

Условие EXISTS в первой строке ограничивает кандидатов теми, кто что-то купил, как π[X](R) в формуле деления. Без него при пустом делителе в ответ попал бы и Пётр, у которого нет покупок. Конструкции EXISTS и NOT EXISTS подробно разбираются в теме 4.

Пример 4. Эквивалентные выражения и размер промежуточных результатов

Условие. Даны два выражения для вопроса «названия книг, купленных покупателями из Казани»:

E1 = π[название](σ[город = 'Казань'](Покупатель ⋈ Покупка ⋈ Книга))
E2 = π[название](σ[город = 'Казань'](Покупатель) ⋈ Покупка ⋈ Книга)

Доказать их эквивалентность и сравнить размеры промежуточных отношений.

Решение. Условие «город = 'Казань'» использует только атрибут Покупателя. По правилу проталкивания выборки через соединение σ[F](R ⋈ S) ≡ σ[F](R) ⋈ S выборку можно опустить к Покупателю (соединение ассоциативно, поэтому Покупатель ⋈ Покупка ⋈ Книга можно рассматривать как Покупатель ⋈ (Покупка ⋈ Книга)). Тонкость: атрибут «город» есть только у Покупателя, у Книги и Покупки его нет, иначе условие стало бы неоднозначным.

Размеры для E1: Покупатель ⋈ Покупка — 9 кортежей (по одному на покупку), ⋈ Книга — 9, выборка — 2. Для E2: выборка — 2 покупателя (Иван, Елена), соединение с Покупкой — 2 кортежа: (2, 4) и (5, 7), соединение с Книгой — 2. Ответ обоих: {(Пикник на обочине), (Искусство программирования)}. На маленьких отношениях выигрыш невелик, но отношение размеров промежуточных результатов (9 к 2) сохраняется и на миллионах строк.

Задачи для самостоятельного решения

Если не сказано иное, вычислите результат и укажите его мощность.

1. Вычислите σ[цена < 600 ∧ рубрика ≠ 5](Книга).
2. Вычислите π[рубрика](Книга). Чем мощность результата отличается от числа строк запроса SELECT рубрика FROM ra.книга?
3. Вычислите π[город](Покупатель) ∪ π[город](Склад). Почему эти отношения совместимы? Что пришлось бы сделать, если бы у Склада атрибут назывался «адрес»?
4. Вычислите π[город](Покупатель) − π[город](Склад), π[город](Склад) − π[город](Покупатель) и π[город](Склад) ∩ π[город](Покупатель). Сформулируйте каждый результат словами.
5. Сколько кортежей и атрибутов в Книга × Склад? А в Книга ⋈ Склад? Почему?
6. Запишите выражение и вычислите: названия книг, которые купила Анна.
7. Запишите двумя способами (разностью и антисоединением): номера покупателей, не купивших ни одной книги.
8. Запишите выражение и вычислите: книги (номер и название), которые никто не купил.
9. Вопрос «покупатели, купившие хотя бы одну книгу Стругацких» записан так: Покупатель ⋉ (Покупка ⋈ Авторство ⋈ σ[имя LIKE '%Стругацкий'](Автор)). Вычислите его выражение. Найдите ошибку и исправьте.
10. Запишите выражение и вычислите: покупатели, купившие все книги Стругацких.
11. Запишите выражение и вычислите: книги, которые есть на всех складах (кортеж в Наличии есть для каждого склада). Как изменится выражение и ответ, если «есть» означает «количество больше нуля»?
12. Что вернёт выражение Наличие ÷ π[склад](Склад) — без предварительной проекции Наличия? Объясните результат через схему частного.
13. Вычислите Покупка ÷ π[книга](σ[рубрика = 99](Книга)). Совпадает ли результат с интуитивным ответом на вопрос «покупатели, купившие все книги рубрики 99»?
14. Эквивалентны ли выражения: а) σ[F](R − S) и σ[F](R) − S; б) σ[F](R ∪ S) и σ[F](R) ∪ S; в) π[A](R − S) и π[A](R) − π[A](S)? Для эквивалентных дайте обоснование, для неэквивалентных — контрпример.
15. Сформулируйте на естественном языке и вычислите: π[покупатель, имя](Покупатель ▷ (Покупка ⋈ σ[цена > 1000](Книга))).
16. Запишите тета-соединением и вычислите: номера книг среднего ценового класса.
17. С помощью переименования запишите выражение и вычислите: пары номеров покупателей из одного города (каждая пара — один раз, без пар покупателя с самим собой).
18. Запишите выражение и вычислите: покупатели, которые покупали только книги Стругацких (и хотя бы одну покупку сделали).
19. Запишите выражение и вычислите: склады, на которых в положительном количестве есть все книги, купленные Иваном.
20. Переведите в SQL выражения задач 4 (первая разность), 7 и 10 и проверьте ответы на отношениях схемы ra.

Ответы

1. {(4, Пикник на обочине, 6, 520), (5, Трудно быть богом, 6, 540)}; мощность 2. Книга 10 не проходит по цене, книги 1 и 2 — по рубрике.

2. {(5), (6), (12), (23)}; мощность 4. Запрос SELECT рубрика без DISTINCT вернёт 6 строк: SQL не устраняет дубликаты.

3. {Москва, Казань, Томск, Санкт-Петербург, Новосибирск}; мощность 5. Отношения унарные, атрибут один и тот же («город», домен — строки). Если бы атрибут назывался «адрес», его надо было бы переименовать: ρ[С(город)](π[адрес](Склад)).

4. {Томск} — города покупателей без склада; {Санкт-Петербург, Новосибирск} — города складов без покупателей; {Москва, Казань} — города, где есть и склады, и покупатели.

5. Книга × Склад — 6 · 4 = 24 кортежа, 4 + 2 = 6 атрибутов. У Книги и Склада нет общих атрибутов, поэтому Книга ⋈ Склад вырождается в произведение: те же 24 кортежа.

6. π[название](Книга ⋈ Покупка ⋈ σ[имя = 'Анна'](Покупатель)) = {Война и мир, Пикник на обочине, Трудно быть богом}. Атрибут «имя» есть только у Покупателя, поэтому соединение корректно.

7. π[покупатель](Покупатель) − π[покупатель](Покупка) или π[покупатель](Покупатель ▷ Покупка); ответ {4}.

8. π[книга, название](Книга ▷ Покупка) = {(10, Основание)}.

9. Это выражение возвращает пустое отношение: у Покупателя и правого операнда два общих атрибута — «покупатель» и «имя», и полусоединение требует, чтобы имя покупателя совпало с именем автора («Анна» = «Аркадий Стругацкий» и т. п.). Исправление — отбросить лишние атрибуты до соединения: Покупатель ⋉ π[покупатель](Покупка ⋈ Авторство ⋈ σ[имя LIKE '%Стругацкий'](Автор)) = покупатели 1, 2, 3 (Анна, Иван, Мария).

10. Покупка ÷ π[книга](Авторство ⋈ σ[имя LIKE '%Стругацкий'](Автор)) = {1, 3}. Делитель — {4, 5}; Иван купил только книгу 4.

11. π[книга, склад](Наличие) ÷ π[склад](Склад) = {1, 4}. С условием на количество: π[книга, склад](σ[кол > 0](Наличие)) ÷ π[склад](Склад) = {1}: книги 4 на складе 3 ноль экземпляров.

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

13. {1, 2, 3, 5} — все покупатели, у которых есть хоть одна покупка: делитель пуст, и условие «для каждой книги рубрики 99» истинно автоматически. Интуитивно ожидают пустой ответ или вопрос считают некорректным; на практике случай пустого делителя оговаривают явно.

14. а) Эквивалентны: кортеж входит в левую часть, если он из R, не из S и удовлетворяет F, — ровно то же означает правая часть. б) Не эквивалентны: в правую часть входят кортежи S, не удовлетворяющие F. Контрпример: R пусто, S = {(1)}, F — «a > 5»: слева пусто, справа {(1)}. в) Не эквивалентны: R = {(1, 1)}, S = {(1, 2)}, A = a. R − S = {(1, 1)}, проекция {(1)}; π[a](R) − π[a](S) = {(1)} − {(1)} = ∅.

15. «Покупатели, ни разу не купившие книгу дороже 1000 рублей». Книги дороже 1000 — 1 и 7, их покупали 1, 3 и 5. Ответ {(2, Иван), (4, Пётр)}.

16. π[книга](Книга ⋈[цена ≥ от ∧ цена < до] σ[класс = 'средняя'](Класс)) = {1, 4, 5, 10}.

17. π[п1, п2](σ[п1 < п2](ρ[П1(п1, имя1, город)](Покупатель) ⋈ ρ[П2(п2, имя2, город)](Покупатель))) = {(1, 3), (2, 5)}. Переименование имён нужно, чтобы естественное соединение шло только по городу.

18. π[покупатель](Покупка) − π[покупатель](Покупка ▷ С), где С — книги Стругацких {4, 5}; Покупка ▷ С — покупки других книг: (1, 1), (3, 1), (3, 2), (5, 7). Ответ {2}.

19. π[склад, книга](σ[кол > 0](Наличие)) ÷ π[книга](σ[покупатель = 2](Покупка)). Делитель {4}; книга 4 в положительном количестве есть на складах 1, 2, 4. Ответ {1, 2, 4}.

20. Задача 4: SELECT город FROM ra.покупатель EXCEPT SELECT город FROM ra.склад;. Задача 7: SELECT покупатель FROM ra.покупатель EXCEPT SELECT покупатель FROM ra.покупка;. Задача 10:

    SELECT DISTINCT x.покупатель
    FROM ra.покупка x
    WHERE NOT EXISTS (
            SELECT 1
            FROM ra.авторство w JOIN ra.автор а USING (автор)
            WHERE а.имя LIKE '%Стругацкий'
              AND NOT EXISTS (SELECT 1 FROM ra.покупка y
                              WHERE y.покупатель = x.покупатель AND y.книга = w.книга));
    

    Результаты совпадают с ответами 4, 7 и 10: {Томск}, {4}, {1, 3}.

Лабораторная работа 3. Запросы к одной таблице

• Раздел курса: тема 3 «Реляционная алгебра и основы запросов SQL»

Введение

В лабораторной работе 1 была создана учебная база «Книжный узел» и выполнены первые запросы SELECT … FROM … WHERE … ORDER BY … LIMIT, в лабораторной работе 2 — изучены ограничения целостности и поведение NULL. Настоящая работа систематически отрабатывает запрос к одной таблице: условия отбора, выражения и функции, сортировку, ограничение выборки и операции над множествами. Главное требование работы — до выполнения каждого запроса предсказать его результат (хотя бы число строк) и объяснить расхождение, если оно возникло. Большинство ошибок в простых запросах связано с тем, что SQL работает с мультимножествами и NULL, а не с отношениями классической алгебры; предсказание заставляет эти особенности заметить.

Вторая линия работы — связь SQL с реляционной алгеброй: выражения из практического занятия 3 переводятся в запросы и проверяются на малых отношениях. Соединения нескольких таблиц и подзапросы изучаются в лабораторной работе 4, группировка и агрегатные функции — в лабораторной работе 5; здесь используется только функция count(*) для подсчёта строк.

Работа состоит из основной части (части 1–6) и продвинутой (часть 7), которую можно выполнить по желанию.

Цель работы

Научиться формулировать запросы к одной таблице на SQL с учётом логического порядка выполнения, мультимножественной семантики и NULL, а также переводить выражения реляционной алгебры в SQL.

После выполнения работы можно будет:

• предсказать число строк простого запроса и объяснить расхождение предсказания с фактом;
• записать условие отбора с BETWEEN, IN, LIKE/ILIKE, регулярными выражениями и корректной обработкой NULL;
• классифицировать строки выражением CASE и построить вычисляемые столбцы функциями для строк, чисел и дат;
• задать однозначный порядок строк с несколькими ключами сортировки, NULLS FIRST/LAST и получить заданную страницу результата;
• решить задачу операциями UNION, INTERSECT, EXCEPT и объяснить различие форм с ALL и без;
• перевести выражение реляционной алгебры в SQL и проверить результат на малых отношениях;
• найти и исправить логическую ошибку в запросе, который выполняется без сообщений об ошибке.

Теоретический минимум

Теория изложена в теме 3: разделы «Реляционная алгебра: основные операции», «Соединения и деление», «Запрос SELECT: структура и логический порядок выполнения», «Условия, выражения и функции», «Сортировка, ограничение выборки и операции над множествами». Ниже — сжатая справка.

Логический порядок выполнения запроса: FROM → WHERE → GROUP BY → HAVING → SELECT → DISTINCT → UNION/INTERSECT/EXCEPT → ORDER BY → LIMIT/OFFSET. Псевдонимы столбцов из SELECT доступны только в ORDER BY.

Таблицы учебной базы, нужные в работе (схема bookstore):

book      (book_id, isbn, title, publisher_id → publisher, category_id → category,
           pub_year, pages, price, attrs, description)
author    (author_id, full_name, birth_year, country)
publisher (publisher_id, name, city)
category  (category_id, parent_id → category, name)
customer  (customer_id, email, full_name, city, registered_at)
orders    (order_id, customer_id → customer, created_at, status, warehouse_id → warehouse)
warehouse (warehouse_id, city)

Столбцы, которые могут содержать NULL: book.publisher_id, book.description, author.birth_year, publisher.city, customer.city, category.parent_id.

Полезные метакоманды psql: \d book — описание таблицы, \x auto — расширенный вывод для широких строк, \pset null '∅' — отображать NULL видимым символом (рекомендуется на всю работу), \i файл.sql — выполнить файл, \o файл — выводить результаты в файл, \timing — время выполнения.

Перечень оснащения

• ОС Ubuntu 24.04 (физическая машина, виртуальная машина или WSL2), PostgreSQL 16 из лабораторной работы 1, psql.
• Учебная база bookstore масштаба scale=1 из файлов schema.sql и data.sql лабораторной работы 1.
• Пакет psycopg 3 для самопроверки: sudo apt install python3-psycopg или pip install "psycopg[binary]" в виртуальном окружении.
• Архив окружения lr-env: ra.sql (малые отношения ПЗ 3), bugs.sql (запросы с ошибками), check.py (самопроверка), README.md.
• Ресурсы: менее 100 МБ дискового пространства.

Порядок выполнения работы

Распакуйте архив, создайте каталог для решений и подключитесь к базе:

unzip lr-env.zip -d ~/lab03 && cd ~/lab03/lr-env
psql -d bookstore -f ra.sql
psql -d bookstore

В начале сеанса psql выполните:

SET search_path = bookstore;
SET TimeZone = 'Europe/Moscow';
\pset null '∅'

Часовой пояс задаётся, чтобы границы дат в заданиях совпадали с эталоном. Если база повреждена, пересоздайте её командами из README.md. Задания, отмеченные номером файла (например, «сохраните в q04.sql»), проверяются скриптом python3 check.py; столбцы результата должны идти ровно в указанном порядке.

В журнал работы по каждой части записываются: предсказания, сделанные до выполнения, тексты запросов, результаты (полностью, если строк не больше 15, иначе первые строки и общее число строк), объяснения расхождений и ответы на вопросы. Порядок строк при сортировке по тексту зависит от правила сравнения базы (тема 3, «ORDER BY: ключи сортировки, NULL и правила сравнения строк»); во всех проверяемых заданиях сортировка идёт по числам.

Часть 1. Отбор строк и предсказание результата

Задание

1. Изучите таблицы book, author, customer командой \d. Выпишите, какие столбцы допускают NULL и какие ограничения CHECK наложены на book.

2. Предсказание. Не выполняя запросов, запишите ожидаемое число строк каждого из них (о данных известно: книг 2010, авторов 210 из семи стран, покупателей 5000, у 471 покупателя город не указан, городов покупателей семь):

   SELECT city FROM customer;
   SELECT DISTINCT city FROM customer;
   SELECT DISTINCT country FROM author;
   SELECT city FROM customer WHERE city = 'Москва' OR city <> 'Москва';
   SELECT DISTINCT city, full_name FROM customer WHERE city = 'Томск';
   SELECT * FROM book WHERE price > 5000;
   

3. Выполните запросы и сравните с предсказанием. Почему SELECT DISTINCT city возвращает восемь строк, а не семь? Какое отношение реляционной алгебры соответствует каждому из первых двух запросов?

4. Узнайте номер издательства «ДМК Пресс» запросом к publisher. Найдите книги этого издательства дороже 1500 рублей, изданные в 2016 году или позже. Столбцы: book_id, title, price, pub_year; порядок: по убыванию цены, при равной цене — по возрастанию book_id. Сохраните запрос в q01.sql.

5. Получите список стран авторов без повторов (один столбец country). Сохраните в q02.sql.

6. Выполните запрос SELECT title, price * 0.9 AS sale FROM book WHERE sale < 200;. Прочитайте сообщение об ошибке и объясните его через логический порядок выполнения. Исправьте запрос двумя способами: повторив выражение и переписав условие относительно price.

Что должно получиться

Таблица «запрос — предсказанное число строк — фактическое — объяснение расхождения»; запросы q01.sql, q02.sql и результат самопроверки; объяснение ошибки пункта 6 и два исправления.

Часть 2. NULL в условиях и сортировке

Задание

1. Предсказание. Сколько строк вернёт каждый запрос? Сначала запишите предсказание, затем выполните:

   SELECT count(*) FROM book WHERE publisher_id = 4;
   SELECT count(*) FROM book WHERE publisher_id <> 4;
   SELECT count(*) FROM book WHERE NOT (publisher_id = 4);
   SELECT count(*) FROM book WHERE publisher_id IS DISTINCT FROM 4;
   SELECT count(*) FROM book WHERE publisher_id = NULL;
   

   Почему сумма первых двух результатов не равна 2010? Почему последний запрос возвращает 0, хотя у 95 книг издательство не указано?

2. Найдите покупателей, у которых не указан город и которые зарегистрировались в 2024 году. Столбцы: customer_id, email. Условие на дату запишите полуоткрытым интервалом (>= начала и < начала следующего периода). Сохраните в q03.sql.

3. Предсказание. Какие строки окажутся первыми в запросе «пять самых молодых авторов» SELECT full_name, birth_year FROM author ORDER BY birth_year DESC LIMIT 5;? Выполните его. Затем выполните тот же запрос с ORDER BY birth_year ASC и объясните, где теперь оказались NULL.

4. Найдите десять самых молодых авторов с известным годом рождения. Столбцы: author_id, full_name, birth_year; порядок: по убыванию года, при равенстве — по author_id. Сохраните в q07.sql. Объясните, зачем нужен второй ключ сортировки: сколько авторов родились в том же году, что и десятый в списке, и какие из них попали бы в ответ без второго ключа?

Что должно получиться

Предсказания и фактические результаты пункта 1 с объяснением по таблицам истинности трёхзначной логики; q03.sql, q07.sql; объяснение расположения NULL при сортировке по возрастанию и убыванию.

Часть 3. Выражения, CASE и поиск по шаблону

Задание

1. Для книг рубрики «Базы данных» (номер рубрики найдите в category) выведите book_id, title, price и ценовой класс: «бесплатно» при цене 0, «дешёвая» — дешевле 500, «средняя» — от 500 до 1500 (не включая 1500), «дорогая» — от 1500. Сохраните в q04.sql. Предсказание: изменится ли результат, если ветвь «бесплатно» переставить в конец, перед ELSE? Изменится ли он для книги 9 («PostgreSQL 16 изнутри»), если применить то же выражение к ней? Проверьте.
2. Найдите книги, в названии которых встречается «баз данных» в любом регистре, изданные с 2020 по 2024 год включительно. Столбцы: book_id, title, pub_year. Сохраните в q05.sql. Сколько книг нашлось бы с LIKE вместо ILIKE и почему здесь результат совпадает?
3. Найдите книги, название которых состоит ровно из двух слов и трёхзначного номера (например, «Путь звёзд 495»). Слово — последовательность символов без пробелов. Столбцы: book_id, title. Используйте регулярное выражение. Сохраните в q06.sql. Почему без якорей ^ и $ результат получается больше (проверьте: 1911 строк против 565 у правильного запроса)?
4. Найдите заказы, сделанные с 24 по 31 декабря 2024 года включительно и ещё не отправленные (статус new или paid). Столбцы: order_id, customer_id, status. Сохраните в q12.sql.
5. Для первого заказа (order_id = 1) выведите дату заказа, номер дня недели (extract(isodow FROM …)), начало месяца заказа (date_trunc), срок доставки «плюс 14 дней» и возраст заказа на 1 января 2025 года (age). Повторите запрос после SET TimeZone = 'UTC' и объясните, что изменилось.
6. Вычислите выражения 7 / 2, 7 / 2.0, 7 % 2, round(2390 * 0.85), trunc(2390 * 0.85), 'а' || NULL, concat('а', NULL), length('Война и мир'), upper('ёж'). Для каждого объясните результат.

Что должно получиться

Запросы q04.sql, q05.sql, q06.sql, q12.sql и результат самопроверки; ответы на вопросы пунктов 1–3; результаты пунктов 5–6 с объяснениями.

Часть 4. Сортировка и постраничный вывод

Задание

1. Найдите пять самых дорогих книг рубрики «Фантастика» (рубрика 6). Столбцы: book_id, title, price; порядок: по убыванию цены, при равной цене — по book_id. Сохраните в q08.sql.
2. Предсказание. Сколько строк вернёт SELECT title, price FROM book ORDER BY price DESC FETCH FIRST 3 ROWS WITH TIES;? Проверьте и объясните. Чем этот запрос отличается от варианта с LIMIT 3?
3. Каталог рубрики «Классическая проза» (рубрика 5) выводится страницами по 10 книг в порядке возрастания цены, при равной цене — по book_id. Получите третью страницу. Столбцы: book_id, title, price. Сохраните в q09.sql. Запишите тот же запрос в стандартной форме OFFSET … ROWS FETCH FIRST … ROWS ONLY и убедитесь, что результат совпадает.
4. Объясните, почему без book_id в ORDER BY одна и та же книга в общем случае могла бы оказаться и на второй, и на третьей странице, а другая — ни на одной. Найдите в рубрике 5 цены, которые имеют несколько книг (выведите первые 40 книг рубрики в порядке цены), и проверьте, приходится ли какая-либо из них на границу страниц.

Что должно получиться

q08.sql, q09.sql, результат самопроверки; ответ на вопрос пункта 2 с выводом обоих запросов; пример равных цен и объяснение пункта 4.

Часть 5. Операции над множествами

Задание

1. Предсказание. Запишите ожидаемое число строк, затем выполните:

   SELECT city FROM warehouse UNION     SELECT city FROM publisher;
   SELECT city FROM warehouse UNION ALL SELECT city FROM publisher;
   SELECT city FROM customer  INTERSECT SELECT city FROM warehouse;
   SELECT city FROM customer  EXCEPT    SELECT city FROM warehouse;
   SELECT city FROM warehouse EXCEPT    SELECT city FROM customer;
   

   Почему в результате EXCEPT для покупателей присутствует NULL? Почему в последнем запросе результат пуст?

2. Найдите города, где живут покупатели, но нет склада (интересуют только настоящие города, без NULL). Столбец: city. Сохраните в q10.sql.

3. Найдите города, где есть и склад, и издательство. Столбец: city. Сохраните в q11.sql.

4. Выполните SELECT city FROM publisher EXCEPT ALL SELECT city FROM warehouse; и SELECT city FROM publisher INTERSECT ALL SELECT city FROM warehouse;. Объясните результаты через кратности строк в мультимножествах.

5. Выполните SELECT 1 AS n, 'a' AS s UNION SELECT 'b', 2; и объясните сообщение об ошибке. Как сопоставляются столбцы операндов — по именам или по позициям? Какие имена получают столбцы результата?

6. Убедитесь, что SELECT DISTINCT city FROM customer и SELECT city FROM customer UNION SELECT city FROM customer возвращают одно и то же множество строк, проверив обе разности EXCEPT.

Что должно получиться

Предсказания и результаты пункта 1 с объяснениями; q10.sql, q11.sql; объяснения пунктов 4–6.

Часть 6. Найти ошибку

Задание

Файл bugs.sql содержит четыре запроса. Каждый выполняется без сообщений об ошибке, но отвечает не на тот вопрос, который сформулирован в комментарии к нему.

1. Предсказание. Прочитайте запросы, не выполняя их. Для каждого запишите, в чём, по-вашему, ошибка и каких строк не хватает или какие лишние.
2. Выполните bugs.sql (\i bugs.sql). Для каждого запроса найдите строки, на которых проявляется ошибка, и посчитайте их число (например, для ошибки 3 — заказы, потерянные из-за неверной границы интервала).
3. Исправьте запросы и сохраните исправления в q13.sql … q16.sql. Проверьте самопроверкой.
4. Для ошибки 2 запишите условие исходного запроса выражением со скобками, расставленными так, как его понимает СУБД. Для ошибки 4 предложите два способа исправления и объясните, чем concat отличается от ||.

Что должно получиться

Для каждого запроса: предсказание, найденная ошибка, число строк, на которых она проявляется, исправленный запрос; результат самопроверки q13–q16.

Часть 7. Реляционная алгебра в SQL, правила сравнения и глубокая пагинация (продвинутая)

Задание

1. Схема ra содержит малые отношения практического занятия 3 (создана скриптом ra.sql). Переведите в SQL выражения задач ПЗ 3 с номерами 1, 2, 3, 4 (все три выражения), 7 и 8 (для задачи 8 — только номера книг), используя только запросы к одной таблице и операции над множествами. Сверьте результаты с ответами ПЗ. В SQL имена отношений пишутся строчными: ra.книга.

2. Проверьте контрпример задачи 14в ПЗ 3 запросом с VALUES: постройте R и S как (VALUES (1, 1)) AS r(a, b) и (VALUES (1, 2)) AS s(a, b) и вычислите обе части неравенства π[a](R − S) и π[a](R) − π[a](S).

3. Отсортируйте строки ('ёж'), ('еж'), ('Ель'), ('яблоко'), ('Яма'), ('Эра') по правилам сравнения "C", "ru-x-icu" и правилу по умолчанию вашей базы (SELECT datcollate FROM pg_database WHERE datname = current_database();). Объясните различия. Доступен ли в вашей установке ICU (SELECT collname FROM pg_collation WHERE collname LIKE 'ru%';)?

4. Сравните постраничный вывод заказов «смещением» и «по ключу»:

   EXPLAIN (ANALYZE, COSTS OFF, TIMING OFF)
   SELECT order_id, created_at FROM orders ORDER BY order_id LIMIT 10 OFFSET 19000;
   
   EXPLAIN (ANALYZE, COSTS OFF, TIMING OFF)
   SELECT order_id, created_at FROM orders WHERE order_id > 19000 ORDER BY order_id LIMIT 10;
   

   Найдите в планах число строк, прочитанных узлом под Limit (actual rows), и объясните разницу. Выполните оба запроса с \timing при смещениях 100, 10 000 и 19 000. Почему пагинация по ключу требует уникального ключа сортировки? Подробно планы выполнения разбираются в теме 11, индексы — в теме 10.

Что должно получиться

Запросы пункта 1 с результатами и сверкой с ПЗ; результат пункта 2; результаты сортировки пункта 3 и объяснение; фрагменты планов и таблица времени выполнения пункта 4 с выводом.

Журнал работы

Журнал работы — записи для себя в формате «предсказание — команда или запрос — фактический результат — объяснение». Для каждой части полезно записать предсказание до выполнения, текст запроса или команды, существенный фрагмент результата и объяснение расхождений. Файлы q01.sql … q16.sql и вывод check.py удобно хранить рядом. В конце стоит сформулировать несколько выводов: какие предсказания не оправдались и почему.

Контрольные вопросы

1. Почему псевдоним столбца из списка SELECT можно использовать в ORDER BY, но нельзя в WHERE? Как обойти это ограничение, не повторяя длинное выражение?
2. Какой операции реляционной алгебры соответствует SELECT DISTINCT a, b FROM t WHERE …, а какой — тот же запрос без DISTINCT? Почему SQL по умолчанию не устраняет дубликаты?
3. Почему условия x = 4 и x <> 4 вместе не покрывают всю таблицу? Как записать «не равно 4, включая неизвестные значения»?
4. Где оказываются NULL при сортировке по возрастанию и по убыванию в PostgreSQL? Как сделать запрос переносимым между СУБД с разным поведением?
5. Почему created_at BETWEEN '2023-01-01' AND '2023-12-31' теряет заказы для столбца типа timestamptz и почему тот же предикат корректен для столбца типа date?
6. Почему запрос с LIMIT без ORDER BY или с неуникальным ключом сортировки может возвращать разные строки при повторном выполнении? Чем помогает WITH TIES?
7. Чем UNION отличается от UNION ALL по результату и по стоимости выполнения? Когда UNION ALL даёт тот же результат?
8. Почему NULL попадает в результат EXCEPT, хотя сравнение NULL = NULL не истинно?
9. Как средствами EXCEPT проверить, что два запроса возвращают одно и то же множество строк? Почему одной разности недостаточно?
10. Как в выражении CASE важен порядок ветвей? Приведите пример, когда перестановка ветвей меняет результат.
11. Почему глубокая пагинация через OFFSET дорожает с ростом номера страницы и что предлагает пагинация по ключу?
12. Как деление реляционной алгебры выражается через базовые операции и почему его нельзя записать одной выборкой с условием?