Многотабличные базы данных

Многотабличная база данных – это реляционная схема, в которой предметная область представлена несколькими отношениями (таблицами), соединёнными ограничениями ссылочной целостности и запросами с объединениями. В терминах теории множеств и логики предикатов многотабличность – способ разложения универсального отношения на проекции, удовлетворяющие функциональным зависимостям и нормальным формам, что предотвращает аномалии вставки, обновления и удаления.
Для подготовки к ЕГЭ по информатике данная тема критична: встречаются задания на чтение схем, определение ключей, понимание типов связей, составление и трассировку объединений (JOIN), а также на вычисление агрегатов по нескольким таблицам. Ниже – академический разбор с формальными определениями, доказательными правилами и практическими шаблонами.

Формальная модель реляционной схемы

1. Отношение, кортеж, атрибут
   

   Пусть задано отношение (таблица)

   R(U) = R(A1, A2, …, An),

   где U = {A1, …, An} – конечное множество атрибутов (столбцов), а экземпляр r(R) – множество кортежей (строк), каждое значение берётся из домена соответствующего атрибута.

2. Функциональная зависимость, ключ, суперключ
   

   Функциональная зависимость задаётся как

   X → Y,  где X, Y ⊆ U,

   и означает: любые два кортежа, совпадающие по атрибутам множества X, совпадают по атрибутам множества Y.
   Суперключ K:

   K → U.

   Кандидатный ключ – минимальный по включению суперключ. Первичный ключ (PK) – один из кандидатных ключей, выбранный как основной идентификатор.

3. Нормальные формы (кратко и строго)
   

   • 1НФ: атомарность атрибутов (нет повторяющихся групп и вложенных множеств).

   • 2НФ: 1НФ и отсутствие частичных зависимостей неключевых атрибутов от части составного ключа.

   • 3НФ: 2НФ и любое следствие X → A либо тривиально (A ∈ X), либо X – суперключ, либо A – первичный по домену (зависимость от ключа через «ключевой» атрибут).

   • BCNF: для любой нетривиальной зависимости X → Y множество X – суперключ.
     Практически: 3НФ обеспечивает отсутствие большинства аномалий, BCNF – ещё строже, но иногда нарушается осознанно ради производительности.

Межтабличные связи и ссылочная целостность

1. Типы связей
   

   • 1:1 – каждой записи одной таблицы соответствует не более одной записи другой. Реализуется общим ключом и/или взаимно уникальными внешними ключами.

   • 1:N – одной записи родителя соответствует множество записей потомка. В потомке хранится внешний ключ (FK) на PK родителя.

   • M:N – связь многие-ко-многим реализуется через соединительную таблицу T_link(PK_A, PK_B, …); первичный ключ – составной (PK_A, PK_B) (или с surrogate-id), а оба поля – внешние ключи.

2. Ограничения целостности (копируемо)
   

   PRIMARY KEY (…)

   FOREIGN KEY (child_col) REFERENCES Parent(parent_pk)

     ON UPDATE {CASCADE|RESTRICT|NO ACTION|SET NULL}

     ON DELETE {CASCADE|RESTRICT|NO ACTION|SET NULL}

   UNIQUE (…)

   CHECK (логическое_условие)

   NOT NULL

   Правило корректности 1 (ссылочная целостность):
   Для каждой строки c в дочерней таблице с c.child_col = v существует строка p в родительской, для которой p.parent_pk = v, или v допускается NULL при «необязательной» связи.
   Правило корректности 2 (кардинальность):
   Кардинальность 1:N обеспечивается: Parent.PK – PRIMARY KEY, Child.FK – FOREIGN KEY, а при необходимости «уникального» 1:1 – UNIQUE на стороне потомка.

Реляционная алгебра и объединения (JOIN)

1. Операции 
   

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

   Выборка (предикат):  σ_φ(R)

   Проекция (столбцы):  π_{A1,…,Ak}(R)

   Декартово произв.: R × S

   Естеств. соединение: R ⋈ S

   Тета-соединение (условие θ): R ⋈_θ S

   Левое внешн. соединение: R ⟕ S

   Правое внешн. соединение: R ⟖ S

   Полное внешн. соединение: R ⟗ S

   Разность: R − S

   Объединение: R ∪ S

   Пересечение: R ∩ S

2. Семантика JOIN в SQL
   

   • INNER JOIN – R ⋈_θ S (возвращает только совпавшие пары).

   • LEFT JOIN – R ⟕ S (сохраняет все строки R, подставляя NULL при отсутствии пары в S).

   • RIGHT JOIN/FULL JOIN – симметрично.

   • CROSS JOIN – декартово произведение R × S.

   Правило корректности 3 (ключ в условии соединения):
   Условие ON для 1:N должно связывать Child.FK = Parent.PK. Использование неключевых полей в соединении приводит к дублированию и логическим ошибкам.

   Шаблон 1 (анти-джойн – «без потомков»):

   SELECT p.*

   FROM Parent p

   LEFT JOIN Child c ON c.parent_id = p.id

   WHERE c.parent_id IS NULL;

   Шаблон 2 (semi-join «есть потомки, удовлетворяющие φ»):

   SELECT p.*

   FROM Parent p

   WHERE EXISTS (

     SELECT 1 FROM Child c

     WHERE c.parent_id = p.id AND (φ)

   );

Агрегирование и группировка в многотабличных запросах

1. Группировка
   

   SELECT p.id, COUNT(*) AS cnt

   FROM Parent p

   JOIN Child c ON c.parent_id = p.id

   GROUP BY p.id

   HAVING COUNT(*) >= 3;

   Правило корректности 4 (GROUP BY):
   Каждый столбец в SELECT либо агрегирован (COUNT, SUM, AVG, MIN, MAX), либо присутствует в GROUP BY.

2. Объединения множеств
   

   SELECT name FROM A

   UNION            -- удаляет дубликаты

   SELECT name FROM B;

   
   

   SELECT name FROM A

   UNION ALL        -- сохраняет дубликаты

   SELECT name FROM B;

   Правило корректности 5: столбцы, объединяемые через UNION/UNION ALL/INTERSECT/EXCEPT, должны быть совместимы по доменам.

Индексация и производительность

Правило 6 (обязательный индекс):
PRIMARY KEY и все FOREIGN KEY должны иметь индексы: по PK индекс создаётся автоматически; по FK индекс следует создать вручную для ускорения соединений и каскадов.

Правило 7 (составной индекс и порядок ключей):
Для индекса (A, B) эффективны предикаты по A и по (A,B), но не по одному B без A.
Правило 8 (селективность):
Индекс имеет смысл при высокой селективности (доля уникальных значений велика).
Правило 9 (покрывающий индекс):
Если все столбцы запроса находятся в одном индексе, СУБД может выполнить запрос без обращения к таблице.

Транзакции и целостность

ACID:

Atomicity   – атомарность

Consistency – согласованность (сохранение ограничений)

Isolation   – изоляция (уровни: Read Committed, Repeatable Read, Serializable)

Durability  – надёжность фиксации

Правило 10: Изменения нескольких связанных таблиц (например, вставка в Parent и Child) выполняйте в одной транзакции:

BEGIN;

  INSERT INTO Parent(id, ...) VALUES (...);

  INSERT INTO Child(parent_id, ...) VALUES (...);

COMMIT;

Типичные аномалии и способы предотвращения

1. Аномалия вставки: нельзя добавить потомка без существующего родителя → FK с ON INSERT проверкой.
2. Аномалия удаления: удаление родителя «осиротит» потомков → ON DELETE CASCADE или ON DELETE RESTRICT.
3. Дублирование при соединении: соединение по неуникальному атрибуту → всегда соединяйте PK↔FK.
4. NULL-ловушки: при LEFT JOIN фильтра WHERE child.col = … превращают левый во внутренний – переносите условие в ON.
5. Денормализация без инвариантов: вычисляемые поля без триггеров/проверок рассогласовываются.

Мини-шпаргалка

Ключ:      K → U,  K – минимален.

BCNF:      (X → Y) и Y ⊄ X  ⇒  X – суперключ.

1:N:       Child.FK → Parent.PK;  FK индексировать.

M:N:       T_link(PK_A, PK_B, …), PK(T_link) = (PK_A, PK_B). 

INNER:     R ⋈_θ S

LEFT:      R ⟕ S

SEMI:      R ⋉ S   ~ WHERE EXISTS(...)

ANTI:      R ▷ S   ~ WHERE NOT EXISTS(...) 

Группировка: SELECT agg, … FROM … GROUP BY … HAVING …

Объединение: R ∪ S / R ∩ S / R \ S  ↔ UNION / INTERSECT / EXCEPT

Транзакция:  BEGIN; …; COMMIT;

Практические шаблоны (SQL)

Шаблон «список родителей без детей»

SELECT p.id, p.name

FROM Parent p

LEFT JOIN Child c ON c.parent_id = p.id

WHERE c.parent_id IS NULL;

Шаблон «подсчитать количество детей по категории родителя»

SELECT p.category, COUNT(c.id) AS cnt

FROM Parent p

LEFT JOIN Child c ON c.parent_id = p.id

GROUP BY p.category;

Шаблон «связь M:N: найти все документы, где участвует тег t»

SELECT d.id, d.title

FROM Doc d

JOIN DocTag dt ON dt.doc_id = d.id

JOIN Tag t ON t.id = dt.tag_id

WHERE t.name = 't';

Шаблон «выбрать ровно одну запись из дубликатов»

SELECT DISTINCT ON (email) id, email, created_at

FROM Users

ORDER BY email, created_at DESC;

Связь с ЕГЭ по информатике

• Чтение схемы: распознавание PK/FK, типов связей, кардинальностей.
• Алгебра запросов: понимание JOIN, эквивалентность EXISTS и INNER JOIN для фильтрации.
• Анализ корректности: определять причины дубликатов и «пропаж» из-за условий в WHERE vs ON.
• Сложность: оценка эффекта индексов и группировок на объёмах данных.
• Логическая строгость: умение рассуждать через функциональные зависимости и нормальные формы.

Пять упражнений (академический формат в стиле ЕГЭ)

Упражнение 1. Идентификация ключей и нормализация
Дана таблица Orders(id_order, order_date, id_client, client_name, client_phone).
a) Укажите функциональные зависимости и кандидатные ключи.
b) Приведите таблицу к 3НФ: укажите получившиеся отношения и ключи.
c) Объясните, какие аномалии устраняются.

Упражнение 2. Типы связей и ограничения
Есть предметная область: «Факультеты – Кафедры – Преподаватели».
a) Смоделируйте связи и запишите SQL-ограничения PRIMARY KEY, FOREIGN KEY (включая ON DELETE политику).
b) Покажите, как реализовать 1:1 между Person и Passport.
c) Обоснуйте выбор CASCADE/RESTRICT на удаление.

Упражнение 3. Соединения и фильтры
Схема: Student(id, group_id), Group(id, name), Mark(stud_id, subject, grade).
a) Выведите студентов без ни одной оценки (анти-джойн).
b) Для каждой группы выведите среднюю оценку по предмету «Информатика» (включая группы без оценок).
c) Объясните, почему перенос условия subject='Информатика' из ON в WHERE меняет результат для LEFT JOIN.

Упражнение 4. Группировка и M:N
Схема: Book(id, title), Author(id, name), BookAuthor(book_id, author_id).
a) Найдите авторов, у которых более 3 книг.
b) Найдите книги, у которых соавторов больше, чем среднее число соавторов по всем книгам.
c) Оцените, какие индексы повысят эффективность запросов.

Упражнение 5. Эквивалентность формулировок
Схема: Product(id, category), Sale(prod_id, sold_at, qty).
a) Запишите два эквивалентных запроса «вывести категории, по которым были продажи в прошлом месяце»: через INNER JOIN и через EXISTS.
b) Докажите эквивалентность на уровне реляционной алгебры (⋉ vs ⋈ + проекция).
c) Обсудите случаи, когда эквивалентность может нарушаться из-за дубликатов и SELECT DISTINCT.

Заключение

Многотабличные базы данных опираются на строгий аппарат функциональных зависимостей и нормальных форм, а корректная реализация связей – на ограничения ссылочной целостности. Понимание семантики соединений, правил группировки и влияния индексов превращает работу с данными из ремесла в точную инженерную дисциплину. Это напрямую повышает результативность на ЕГЭ: вы умеете читать схемы, строго обосновывать корректность запросов, избегать аномалий и уверенно работать с объединениями и агрегатами.