Селекция σ и проекция π

В прошлом уроке мы договорились, что реляция — это множество кортежей. Хорошо, теперь хочется уметь что-то с ней делать. Кодд показал, что почти всё, что нужно для работы с данными, выражается через шесть базовых операций. В этом уроке разбираем две первые — самые частые в любом запросе.

Селекция: σ

σ (сигма)

— это операция «отфильтровать кортежи». Она принимает отношение и предикат, возвращает новое отношение тех же атрибутов, но содержащее только те кортежи, для которых предикат истинен.

Формально:

$\sigma_p(R) = \{ t \in R \mid p(t) \text{ истинен} \}$

В SQL это WHERE. Запрос SELECT * FROM customers WHERE country = 'RU' — это буквально σ[country='RU'](customers).

Селекция σ — фильтр кортежей

Атрибуты остаются те же. Меняется только число кортежей.

до: customers12 кортежей

кортеж(Аня, RU, 1998)

кортеж(Виктор, DE, 1986)

кортеж(Ханна, DE, 2000)

кортеж...

σcountry = 'DE'

после3 кортежа

кортеж(Виктор, DE, 1986)

кортеж(Феликс, DE, 1988)

кортеж(Ханна, DE, 2000)

Проверим:

σ[country='DE'](customers) — все клиенты из Германии:

PostgreSQL

Селекция не меняет схему результата: те же атрибуты, та же арность. Меняется только число кортежей. Это важно: значит, к результату σ можно применять любую другую операцию, ожидающую такую же схему — например, ещё одну σ.

Проекция: π

π (пи)

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

Арность

— это число столбцов. Если у customers арность 6, то после проекции на один атрибут получится отношение арности 1.

Формально:

$\pi_{A_1, ..., A_n}(R) = \{ (t.A_1, ..., t.A_n) \mid t \in R \}$

В SQL это SELECT col1, col2. Запрос SELECT email, country FROM customers — это π[email, country](customers).

Проекция π — фильтр атрибутов

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

до: customersарность = 6

кортеж(1, anya@…, Аня, RU, 1998, 2023-03-12)

кортеж(2, boris@…, Борис, RU, 1990, 2022-11-04)

кортеж...

π{country}

после (теория)арность = 1, без дублей

кортеж(RU)

кортеж(DE)

кортеж(IL)

кортеж(GE)

кортеж(US)

Вот тут и начинается разница между теорией и практикой. Посмотри:

π[country](customers) — а сколько строк ожидаешь?

PostgreSQL

В чистой реляционной алгебре результат — множество стран без повторов: {RU, DE, IL, GE, US}, всего 5 кортежей. Но PostgreSQL вернул 12 строк, потому что в customers 12 клиентов, и многие из одной страны. Почему?

Почему теория и практика расходятся: DISTINCT

Здесь видно фундаментальный компромисс. В чистой реляционной модели проекция возвращает множество, и оно автоматически без дубликатов. Но удалить дубликаты — дорогая операция: нужно либо отсортировать всё, либо построить hash-таблицу. На таблицах в миллионы строк это секунды CPU и гигабайты памяти.

Поэтому SQL в 1986 году принял прагматичное решение: проекция (SELECT col) по умолчанию возвращает мультимножество — с возможными дубликатами. Хочешь поведения чистой алгебры — пиши явно DISTINCT, и ты платишь за уникализацию только когда это действительно нужно.

То же самое, но с DISTINCT — настоящая проекция:

PostgreSQL

5 строк, как и положено множеству. Запомни: в SQL SELECT без DISTINCT — это не чистая проекция, это её bag-вариант (от англ. bag — «сумка с возможными повторениями»). Это одна из главных точек расхождения между академической реляционной моделью и тем, как реально работает SQL.

Композиция: σ и π вместе

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

$\pi_{email}(\sigma_{country='DE'}(\text{customers}))$

— это «email’ы только тех клиентов, кто из Германии». В SQL:

Композиция σ и π — email немецких клиентов:

PostgreSQL

Здесь две операции встречаются в одном SQL-запросе. PostgreSQL внутри выполнит их в порядке σ → π — отсортирует кортежи фильтром, потом отдаст только нужные столбцы. Можно было бы сделать в обратном порядке: сначала спроецировать все email’ы, потом… но тогда нужен country для фильтра, а его уже нет. Поэтому если предикат использует атрибут, его нужно сохранить до фильтра.

Эта свобода менять порядок операций называется push-down — оптимизатор СУБД старается «протолкнуть» селекцию как можно ближе к источнику данных, чтобы дальше работать с меньшим объёмом. Мы вернёмся к этой идее в модуле про индексы и EXPLAIN.

Проверка знанийKnowledge check

Запрос SELECT country FROM customers вернул 12 строк, а SELECT DISTINCT country FROM customers — 5. Разные результаты — это значит, у нас не реляция?

ОтветAnswer

Формально — да, без DISTINCT мы работаем с мультимножеством (bag), а не с настоящей реляцией. SQL принял это как практический компромисс, потому что устранение дубликатов дорого, а в большинстве запросов оно не нужно. Когда тебе нужно строго множественное поведение — пиши DISTINCT. Когда не нужно (например, считаешь total по бирже сделок) — экономишь время и не пишешь. В обоих случаях операция называется «проекцией» в SQL-сленге, но академический термин для второго варианта — «extended projection».

Реляционная алгебра: все шесть операторов Как Postgres исполняет запрос: парсер, планировщик, executor

Чек-лист

σ (селекция) — фильтр кортежей по предикату. В SQL это WHERE. Схема не меняется.
π (проекция) — выбор столбцов. В SQL это SELECT col1, col2. Арность уменьшается.
В чистой алгебре проекция убирает дубликаты автоматически (множество). В SQL — нет, для этого нужен DISTINCT.
Композиция σ и π даёт большую часть простых аналитических запросов. Оптимизатор может менять их порядок (push-down).