Условие

Какие основные операции относятся к реляционной алгебре, и как они соотносятся с SQL-конструкциями?

Решение

Базовые операции

Операция	Символ	Что делает	SQL-эквивалент
Селекция (выборка)	σ (sigma)	Отбор строк по условию	`WHERE`
Проекция	π (pi)	Отбор столбцов	`SELECT col1, col2`
Объединение	∪	Union (множества)	`UNION`
Пересечение	∩	Только общие строки	`INTERSECT`
Разность	−	Строки A не в B	`EXCEPT` / `MINUS`
Декартово произведение	×	Все пары	`CROSS JOIN`
Соединение	⋈	INNER/OUTER JOIN	`JOIN`
Деление	÷	«Все строки B, для которых...»	Через NOT EXISTS
Переименование	ρ (rho)	Алиасы	`AS`

Пример

«Имена студентов из группы Б05-123, получивших 5 по «базам данных»» — две таблицы:

Students(StudentID, Name, Group)
Grades(RecordID, StudentID, Subject, Grade)

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

π_Name (
  σ_(Group='Б05-123') (Students)
    ⋈_StudentID
  σ_(Subject='базы данных' ∧ Grade=5) (Grades)
)

SQL:

SELECT s.Name
FROM   Students s
JOIN   Grades   g ON s.StudentID = g.StudentID
WHERE  s.Group   = 'Б05-123'
  AND  g.Subject = 'базы данных'
  AND  g.Grade   = 5;

Деление: «студенты, изучившие все курсы»

Найти ID студентов, у которых есть оценка по каждому курсу из Courses:

SELECT s.StudentID
FROM   Students s
WHERE  NOT EXISTS (
  SELECT 1 FROM Courses c
  WHERE NOT EXISTS (
    SELECT 1 FROM Grades g
    WHERE g.StudentID = s.StudentID AND g.Subject = c.Subject
  )
);

Зачем знать алгебру

Оптимизатор СУБД работает с алгебраическим планом и применяет эквивалентные преобразования (push-down предикатов и т.п.).
Декларативность SQL — записываете «что», а не «как»; за «как» отвечает преобразование плана в физические операции.
Понимание JOIN'ов — внутреннее соединение это σ(A × B), отсюда понятна тяжесть декартова произведения.

Подводные камни

Базовые операции — пять (σ, π, ∪, −, ×) минимальны; остальные выводимы. Иногда добавляют ⋈ и ∩ как «производные».
Деление — самая «непонятная» операция; в SQL делается через двойной NOT EXISTS.
Реляционная алгебра работает с множествами — без дубликатов. SQL по умолчанию работает с мультимножествами (баги — UNION ALL vs UNION).

Эталонный ответ

Базовые операции: селекция (σ), проекция (π), объединение (∪), разность (−), декартово произведение (×). Производные: ⋈ (соединение), ∩ (пересечение), ÷ (деление). SQL — декларативная надстройка над реляционной алгеброй.

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