Тема 3.1
Банки данных, СУБД, уровни представления
Назначение и компоненты систем баз данных — по методичке Дьякова «Базы данных: язык SQL».
Основные понятия
БД — это библиотека: сами книги, расставленные по строгой системе. СУБД — библиотекарь: принимает запросы, знает, где что стоит, не пускает посторонних в хранилище и следит, чтобы две «правки» одной книги не столкнулись. Банк данных — вся библиотека как учреждение: фонд + библиотекарь + здание + каталог + директор (администратор).
Главная идея: приложения никогда не лезут в файлы напрямую — только через СУБД. Поэтому можно менять способ хранения, не переписывая программы.
Функции СУБД: определение данных (DDL), манипулирование данными (DML), управление транзакциями и параллельным доступом, восстановление после сбоев (журнализация), контроль целостности, разграничение доступа, оптимизация запросов, ведение словаря данных.
Обзор современных СУБД: реляционные — PostgreSQL, MySQL, Oracle Database, Microsoft SQL Server, SQLite, встраиваемые (Interbase/Firebird — на них построен практикум ТГТУ); нереляционные (NoSQL) — документные (MongoDB), «ключ–значение» (Redis), графовые (Neo4j).
За пределами реляционной модели (NoSQL) — для задач, где жёсткая схема и джойны мешают масштабированию: документные (MongoDB — JSON-документы), ключ-значение (Redis — кэш в памяти), колоночные (ClickHouse — аналитика), графовые (Neo4j — связи как первичная сущность). Плата за горизонтальное масштабирование — ослабленные гарантии согласованности (BASE вместо ACID). Для профиля «анализ данных» уместно сказать: рабочие данные — в реляционной СУБД, аналитические витрины — в колоночных.
Уровни представления. Схема и подсхема
Трёхуровневая архитектура ANSI/SPARC обеспечивает независимость данных:
- внешний уровень — представления отдельных пользователей и приложений (подсхемы);
- концептуальный уровень — обобщённая логическая модель всей предметной области (схема БД);
- внутренний (физический) уровень — организация хранения: файлы, индексы, кластеры.
Университетская БД на трёх уровнях:
- внешний: деканат видит только «студент – группа – успеваемость», бухгалтерия — только «студент – стипендия»; ни те ни другие не знают о существовании чужих полей;
- концептуальный: полная схема — таблицы СТУДЕНТ, ГРУППА, ВЕДОМОСТЬ, ПРИКАЗ со всеми связями;
- внутренний: файлы данных, B-деревья индексов, страницы по 8 КБ на диске.
Добавили таблицу для военкомата — представления деканата не изменились (логическая независимость). Перенесли файлы на SSD и перестроили индекс — не изменилась даже схема (физическая независимость).
Вопросы к собеседованию
Что такое база данных, СУБД и банк данных?
БД — именованная совокупность структурированных данных предметной области, независимая от прикладных программ. СУБД — программные и языковые средства создания, ведения и совместного использования БД. Банк данных — система в целом: БД + СУБД + технические и организационно-методические средства + администратор.
Перечислите основные функции СУБД.
Определение данных (DDL), манипулирование (DML — поиск, вставка, обновление, удаление), управление транзакциями и параллельным доступом, журнализация и восстановление, контроль целостности, разграничение доступа, оптимизация запросов, словарь данных.
Опишите три уровня представления баз данных. Что такое схема и подсхема?
Внешний уровень — представления пользователей (подсхемы); концептуальный — логическая модель всей предметной области (схема); внутренний — физическое хранение (файлы, индексы). Архитектура даёт логическую (изменение схемы не затрагивает приложения) и физическую (смена хранения не затрагивает схему) независимость данных.
Тема 3.2
Модели данных
Иерархическая, сетевая и реляционная модели; отношение, ключи.
Три классические модели
- Иерархическая — данные в виде дерева «предок–потомок»; у записи один родитель. Быстрая навигация вдоль иерархии, но связи «многие-ко-многим» требуют дублирования (IMS).
- Сетевая — граф: запись может иметь много владельцев (модель CODASYL). Гибче иерархической, но сложна в сопровождении, доступ навигационный.
- Реляционная (Э. Кодд, 1970) — данные в виде отношений (таблиц); доступ декларативный: указывается, что найти, а не как. Господствующая модель.
Реляционная модель: термины
Свойства отношений: нет одинаковых кортежей; порядок кортежей и атрибутов не важен; значения атрибутов атомарны (нормализованность).
Ключи: потенциальный ключ — минимальный набор атрибутов, однозначно определяющий кортеж (уникальность + неизбыточность); один из потенциальных выбирается первичным (PRIMARY KEY, не допускает NULL); внешний ключ (FOREIGN KEY) — атрибут, ссылающийся на первичный ключ другого отношения — механизм связи таблиц и ссылочной целостности.
Вопросы к собеседованию
Сравните иерархическую, сетевую и реляционную модели данных.
Иерархическая — дерево, у записи один предок: быстрый доступ вдоль иерархии, но «многие-ко-многим» требует дублирования. Сетевая — граф с многими владельцами записи: гибче, но сложная навигационная обработка. Реляционная — таблицы-отношения с декларативным доступом (SQL), строгая математическая основа; вытеснила первые две.
Что такое схема отношения, кортеж, атрибут, домен?
Схема отношения — имя и перечень атрибутов с доменами R(A₁…An). Кортеж — строка (набор значений атрибутов), атрибут — именованный столбец, домен — множество допустимых значений атрибута. Степень — число атрибутов, мощность — число кортежей.
Что такое потенциальный, первичный и внешний ключи?
Потенциальный ключ — минимальный набор атрибутов, уникально определяющий кортеж; их может быть несколько. Первичный — выбранный из потенциальных, не допускает NULL. Внешний — атрибут(ы), ссылающийся на первичный ключ другого отношения; обеспечивает связи и ссылочную целостность (нельзя сослаться на несуществующую запись).
Назовите свойства отношения в реляционной модели.
Отсутствие одинаковых кортежей (отношение — множество); порядок кортежей и порядок атрибутов несущественны; атомарность значений (в клетке — одно неделимое значение — первая нормальная форма).
Тема 3.3
Реляционная алгебра
Стандартные и специальные операции над отношениями.
Стандартные (теоретико-множественные) операции — над совместимыми отношениями: объединение (все кортежи обоих), пересечение, разность (кортежи первого, отсутствующие во втором), декартово произведение (все сочетания кортежей). Специальные: выборка σ (строки по условию), проекция π (заданные столбцы без дубликатов), соединение ⋈ (произведение + условие равенства атрибутов — естественное соединение), деление.
Реляционная алгебра на бумаге. СТУДЕНТ(id, имя, группа): {(1, Иванов, ИВТ), (2, Петров, ПИ), (3, Сидоров, ИВТ)}.
Комбинация операций — уже запрос: «имена студентов ИВТ» = πимя(σгруппа='ИВТ'(СТУДЕНТ)) — ровно то, что делает SELECT имя FROM СТУДЕНТ WHERE группа='ИВТ'.
Деление — самая хитрая операция: СДАЛ(студент, предмет) ÷ ПРЕДМЕТ(предмет) = студенты, сдавшие все предметы из второго отношения. Если СДАЛ = {(Иванов, БД), (Иванов, ИИ), (Петров, БД)} и ПРЕДМЕТ = {(БД), (ИИ)}, то результат — {Иванов}: только у него есть пара с каждым предметом делителя. В SQL деление выражается через двойное NOT EXISTS — потому его и спрашивают «на понимание».
Вопросы к собеседованию
Перечислите операции реляционной алгебры.
Стандартные (теоретико-множественные): объединение, пересечение, разность, декартово произведение. Специальные: выборка σ (фильтр строк по условию), проекция π (выбор столбцов с удалением дубликатов), соединение ⋈ (декартово произведение + условие на атрибуты; частный случай — естественное по равенству одноимённых атрибутов), деление. SQL-запрос SELECT реализует комбинацию этих операций.
Чем выборка отличается от проекции?
Выборка σ работает по строкам: оставляет кортежи, удовлетворяющие условию (WHERE). Проекция π — по столбцам: оставляет указанные атрибуты и устраняет дубликаты кортежей (SELECT DISTINCT списка столбцов).
Что такое естественное соединение?
Соединение двух отношений по равенству всех одноимённых атрибутов, при котором повторяющийся атрибут в результат входит один раз. Общий случай — θ-соединение: декартово произведение с произвольным условием сравнения атрибутов. В SQL — JOIN … ON/USING.
Тема 3.4
Язык SQL
Язык манипулирования данными реляционной модели. Создание и модификация БД, поиск, сортировка, индексирование, формы и отчёты.
SQL — декларативный язык; группы операторов: DDL (CREATE, ALTER, DROP), DML (SELECT, INSERT, UPDATE, DELETE), DCL (GRANT, REVOKE), управление транзакциями (COMMIT, ROLLBACK). Бывает интерактивным и вложенным (встроенным в прикладную программу).
-- создание и модификация
CREATE TABLE student (
id INTEGER PRIMARY KEY,
name VARCHAR(60) NOT NULL,
group_id INTEGER REFERENCES sgroup(id),
rating NUMERIC(4,2) DEFAULT 0
);
ALTER TABLE student ADD COLUMN email VARCHAR(80);
CREATE INDEX idx_student_group ON student(group_id);
-- манипулирование
INSERT INTO student(id, name, group_id) VALUES (1, 'Иванов', 3);
UPDATE student SET rating = 4.5 WHERE id = 1;
DELETE FROM student WHERE rating < 2;
-- поиск, сортировка, агрегаты
SELECT g.name, COUNT(*) AS n, AVG(s.rating) AS avg_r
FROM student s
JOIN sgroup g ON g.id = s.group_id
WHERE s.rating >= 3
GROUP BY g.name
HAVING COUNT(*) > 5
ORDER BY avg_r DESC;Порядок логического выполнения SELECT: FROM → JOIN → WHERE → GROUP BY → HAVING → SELECT → ORDER BY. Индекс ускоряет поиск и сортировку по столбцу ценой замедления вставок и дополнительной памяти. Представление (CREATE VIEW) — сохранённый запрос-«виртуальная таблица» — механизм подсхем. Формы — экранный интерфейс ввода и просмотра записей; отчёты — форматированный вывод выборок для печати (строятся средствами конкретной СУБД — практикум ТГТУ использует Interbase/Delphi).
LEFT JOIN против INNER JOIN — группы: ИВТ-41, ПИ-42 и новая пустая АСУ-43.
- INNER JOIN групп со студентами вернёт строки только для ИВТ-41 и ПИ-42 — у АСУ-43 нет пары;
- LEFT JOIN вернёт и АСУ-43 со значением NULL в столбцах студента — «все группы, даже пустые».
Подзапрос — тот же смысл другой записью: «студенты групп 3-го курса»:
SELECT name FROM student
WHERE group_id IN (SELECT id FROM sgroup WHERE course = 3);Агрегаты и HAVING на числах. Оценки: Иванов — 5, 4; Петров — 3; Сидоров — 5, 5, 4 (все из ИВТ, Петров из ПИ).
SELECT группа, COUNT(*) AS оценок, AVG(оценка) AS средний
FROM ведомость GROUP BY группа HAVING AVG(оценка) >= 4;| группа | оценок | средний |
|---|---|---|
| ИВТ | 5 | (5+4+5+5+4)/5 = 4,6 |
Группа ПИ (средний 3) отсечена HAVING после агрегирования — WHERE так не смог бы: он работает до группировки и агрегатов ещё не знает. Частая ошибка на собеседовании — WHERE AVG(...) — как раз про это.
Коррелированный подзапрос — «студенты с оценкой выше средней по своей группе»:
SELECT s.name FROM student s
WHERE s.rating > (SELECT AVG(s2.rating) FROM student s2
WHERE s2.group_id = s.group_id);Подзапрос выполняется для каждой строки внешнего запроса, ссылаясь на неё (s.group_id), — в отличие от независимого подзапроса, который вычисляется один раз.
Вопросы к собеседованию
Какие группы операторов входят в SQL?
DDL — определение данных (CREATE, ALTER, DROP); DML — манипулирование (SELECT, INSERT, UPDATE, DELETE); DCL — управление доступом (GRANT, REVOKE); TCL — транзакции (COMMIT, ROLLBACK, SAVEPOINT). SQL может быть интерактивным и вложенным в прикладную программу.
Опишите структуру оператора SELECT и порядок его выполнения.
SELECT списка выражений FROM таблиц [JOIN … ON] [WHERE условие] [GROUP BY группировка] [HAVING условие на группы] [ORDER BY сортировка]. Логический порядок: FROM/JOIN → WHERE (фильтр строк) → GROUP BY → HAVING (фильтр групп) → SELECT (проекция, агрегаты) → ORDER BY. WHERE отбирает строки до группировки, HAVING — группы после агрегирования.
Что такое индекс и когда его создают?
Дополнительная структура (обычно B-дерево), хранящая значения столбца со ссылками на записи, — ускоряет поиск, соединения и сортировку с O(n) до O(log n). Цена: память и замедление INSERT/UPDATE (индекс надо поддерживать). Создают по столбцам частых условий поиска и соединений; первичный ключ индексируется автоматически.
Что такое представление (VIEW), формы и отчёты?
Представление — именованный сохранённый запрос, ведущий себя как виртуальная таблица; реализует подсхемы и разграничение доступа. Формы — экранный интерфейс ввода/редактирования записей; отчёты — форматированный вывод данных для печати с группировками и итогами. Формы и отчёты строятся инструментами конкретной СУБД или средой разработки.
Чем JOIN отличается от вложенного подзапроса? Какие бывают соединения?
JOIN соединяет строки таблиц по условию: INNER — только совпавшие пары; LEFT/RIGHT OUTER — плюс непарные строки одной из сторон (с NULL); FULL — с обеих; CROSS — декартово произведение. Подзапрос возвращает значение или множество для условия (IN, EXISTS). Многие запросы записываются обоими способами; оптимизатор часто сводит их к одному плану.
Тема 3.5
Проектирование реляционной БД
Функциональные зависимости, декомпозиция, нормальные формы, метод «сущность–связь».
Функциональные зависимости и нормализация
Функциональные зависимости в таблице ВЕДОМОСТЬ(студент, группа, куратор, предмет, оценка):
Каждая «неправильная» зависимость — готовый рецепт декомпозиции: её левую часть делаем ключом новой таблицы (смотрите демо нормализации ниже).
Плохо спроектированное отношение страдает аномалиями: избыточность (дублирование данных), аномалии обновления, вставки и удаления. Лекарство — декомпозиция: разбиение отношения на проекции без потерь (соединение проекций восстанавливает исходное отношение — теорема Хита) и без потери ФЗ.
Вся нормализация — одно правило: каждый факт хранится ровно один раз. «Куратор группы ИВТ-41 — Дьяков» — это факт о группе, а не о каждом её студенте; значит, ему место в таблице групп, одной строкой. Тогда смена куратора — правка одной клетки, и рассогласование невозможно в принципе.
- 1НФ — все значения атомарны, нет повторяющихся групп.
- 2НФ — 1НФ + каждый неключевой атрибут полностью зависит от составного ключа (нет зависимостей от части ключа).
- 3НФ — 2НФ + нет транзитивных зависимостей неключевых атрибутов от ключа.
- НФБК — каждый детерминант ФЗ является потенциальным ключом (усиление 3НФ).
Когда 3НФ мало: пример на НФБК. РАСПИСАНИЕ(студент, предмет, преподаватель): каждый преподаватель ведёт один предмет; у студента по каждому предмету один преподаватель. ФЗ: {студент, предмет} → преподаватель и преподаватель → предмет.
Отношение в 3НФ (неключевых транзитивных зависимостей нет), но детерминант «преподаватель» — не потенциальный ключ ⇒ НФБК нарушена: предмет преподавателя дублируется в каждой его строке, со всеми аномалиями. Декомпозиция: ПРЕПОД(преподаватель, предмет) + СЛУШАЕТ(студент, преподаватель).
Метод «сущность–связь» (ER)
Инфологическое проектирование: предметная область описывается сущностями (объекты с атрибутами), связями между ними (1:1, 1:M, M:N) и ключами. Затем — даталогическое проектирование: ER-диаграмма отображается в реляционную схему: сущность → таблица, атрибут → столбец, связь 1:M → внешний ключ на стороне «многих», связь M:N → отдельная таблица-связка из двух внешних ключей.
Вопросы к собеседованию
Что такое функциональная, полная и транзитивная зависимости?
ФЗ X → Y: значению X соответствует ровно одно значение Y. Полная — Y зависит от всего составного ключа и не зависит от его части. Транзитивная — X → Z через посредника (X → Y, Y → Z, где Y не ключ). Полные и транзитивные зависимости — критерии 2НФ и 3НФ соответственно.
Какие аномалии возникают в ненормализованных отношениях?
Избыточность — многократное дублирование одних данных; аномалия обновления — при изменении факта нужно править много строк, рискуя рассогласованием; аномалия вставки — нельзя записать факт без «лишних» данных (например, преподавателя без группы); аномалия удаления — удаляя строку, теряем последнюю копию независимого факта.
Дайте определения 1НФ, 2НФ и 3НФ.
1НФ: значения атомарны, нет повторяющихся групп. 2НФ: 1НФ + каждый неключевой атрибут полностью функционально зависит от всего составного ключа. 3НФ: 2НФ + нет транзитивных зависимостей неключевых атрибутов от ключа (неключевые атрибуты не зависят друг от друга). НФБК: всякий детерминант — потенциальный ключ.
Что значит «декомпозиция без потерь»?
Разбиение отношения на проекции, естественное соединение которых в точности восстанавливает исходное отношение — ни потери, ни появления ложных кортежей. По теореме Хита декомпозиция R(X, Y, Z) на (X, Y) и (X, Z) без потерь, если X → Y или X → Z. Также стремятся сохранить все функциональные зависимости.
Опишите проектирование БД методом «сущность–связь».
Инфологический этап: выделяются сущности с атрибутами и ключами, связи типов 1:1, 1:M, M:N — строится ER-диаграмма, независимая от СУБД. Даталогический этап: сущность → таблица, атрибут → столбец, 1:M → внешний ключ у стороны «многих», M:N → таблица-связка из внешних ключей. Далее проверка нормальных форм и физическое проектирование (индексы).
Тема 3.6
Физическая организация, защита и целостность
Хешированные и индексированные файлы, защита БД, транзакции.
Физическая организация данных
- Последовательные файлы — записи подряд; поиск O(n), вставка в конец.
- Хешированные файлы — адрес записи вычисляется хеш-функцией от ключа h(K); поиск по ключу O(1). Проблема — коллизии (разным ключам — один адрес): разрешаются цепочками переполнения или открытой адресацией. Диапазонный поиск неэффективен.
- Индексированные файлы — отдельная структура «значение ключа → адрес записи». Индекс может быть плотным (на каждую запись) и неплотным (на блок); первичным и вторичным. Основная структура — B-дерево/B⁺-дерево: сбалансированное многоветвистое дерево, все листья на одной глубине, поиск/вставка O(log n), листья B⁺-дерева связаны списком — быстрый диапазонный поиск.
Почему хватает 3–4 уровней. Узел B-дерева подгоняют под дисковый блок 8 Кбайт: помещается ~200 пар «ключ + ссылка».
Таблица на миллиард строк — 4 чтения с диска до любой записи (а верхние уровни ещё и постоянно сидят в кэше — фактически 1–2 чтения). Двоичному дереву понадобилось бы log₂ 10⁹ ≈ 30 уровней-обращений: вся сила B-дерева — в «ширине» узла, согласованной с блоком диска.
Защита, целостность и сохранность БД
- Защита: идентификация и аутентификация пользователей; привилегии GRANT/REVOKE на таблицы и операции; представления, скрывающие часть данных; шифрование; аудит.
- Целостность — соответствие данных ограничениям предметной области: целостность сущностей (первичный ключ уникален и не NULL), ссылочная целостность (внешние ключи ссылаются на существующие записи; ON DELETE CASCADE/RESTRICT), ограничения CHECK, NOT NULL, UNIQUE, триггеры.
- Сохранность — восстановление после сбоев: транзакции со свойствами ACID (атомарность, согласованность, изоляция, долговечность), журнал изменений (упреждающая запись), контрольные точки, резервное копирование.
Перевод 100 ₽ со счёта А на счёт Б — это два UPDATE. Если между ними выключат свет, без транзакций деньги «испарятся»: с А списано, на Б не зачислено. Транзакция делает пару операций неделимой: либо обе (COMMIT), либо ни одной (ROLLBACK — СУБД откатит по журналу). Попробуйте в демо нажать «сбой» в середине. А кнопка «второй клиент» показывает изоляцию: остановитесь между двумя UPDATE и прочитайте сумму на READ UNCOMMITTED — увидите несуществующие 700 ₽ (грязное чтение); на READ COMMITTED читатель видит только зафиксированные 800.
Изоляция параллельных транзакций. Без изоляции возникают аномалии: грязное чтение (видны незафиксированные чужие изменения), неповторяющееся чтение (два чтения одной строки дают разное — её успели изменить), фантомы (повторный запрос по условию возвращает новые строки). Стандарт SQL задаёт уровни изоляции — компромисс строгости и параллелизма:
| Уровень | Грязное чтение | Неповтор. чтение | Фантомы |
|---|---|---|---|
| READ UNCOMMITTED | возможно | возможно | возможно |
| READ COMMITTED | — | возможно | возможно |
| REPEATABLE READ | — | — | возможно |
| SERIALIZABLE | — | — | — |
Реализация — блокировки (чтения/записи, строк/таблиц; риск взаимоблокировок) или многоверсионность MVCC: читатели видят «снимок» данных и не блокируют писателей.
Как журнал спасает данные (WAL — упреждающая запись). Правило: сначала запись о изменении попадает в журнал на диске, и только потом меняются сами страницы данных. В журнале хранятся до-образ (старое значение) и после-образ (новое).
- Транзакция уменьшила счёт А на 100 ₽ → в журнал пишется «А: было 500, стало 400», затем COMMIT-отметка.
- 💥 Сбой питания до записи страницы данных на диск.
- Восстановление при старте: СУБД читает журнал. Транзакции с COMMIT-отметкой повторяются по после-образам (redo), незавершённые — откатываются по до-образам (undo).
Плюс периодические контрольные точки: все грязные страницы сбрасываются на диск, журнал усечается — восстановление начинается с последней контрольной точки, а не с начала времён. Резервные копии + журнал = восстановление на любой момент времени.
Вопросы к собеседованию
Как устроен хешированный файл? Что такое коллизии и как их разрешают?
Адрес записи вычисляется хеш-функцией от значения ключа — поиск по ключу почти O(1) без индекса. Коллизия — разные ключи дают один адрес; разрешение: цепочки (область переполнения со списками) или открытая адресация (поиск следующего свободного места). Недостатки: неэффективный диапазонный поиск и деградация при заполнении.
Почему индексы СУБД строят на B-деревьях (B⁺-деревьях)?
B-дерево — сбалансированное многоветвистое дерево: узел содержит десятки–сотни ключей и подгоняется под размер дискового блока, поэтому поиск требует лишь нескольких обращений к диску (O(log n) с большим основанием); все листья на одной глубине, дерево само балансируется при вставках. В B⁺-дереве данные в листьях, связанных списком, — эффективен и точечный, и диапазонный поиск.
Какими средствами обеспечивается целостность базы данных?
Целостность сущностей — PRIMARY KEY (уникальность, не NULL); ссылочная — FOREIGN KEY с правилами ON DELETE/UPDATE (RESTRICT, CASCADE, SET NULL); доменные ограничения — типы, NOT NULL, CHECK, UNIQUE; триггеры для сложных правил. Ограничения проверяет сама СУБД, а не приложение.
Что такое транзакция и свойства ACID?
Транзакция — неделимая последовательность операций, переводящая БД из одного согласованного состояния в другое (COMMIT/ROLLBACK). ACID: атомарность — всё или ничего; согласованность — ограничения не нарушаются; изоляция — параллельные транзакции не видят промежуточных состояний друг друга; долговечность — зафиксированные изменения переживают сбой (журнал с упреждающей записью, контрольные точки).
Как защищают базы данных от несанкционированного доступа?
Аутентификация пользователей СУБД; система привилегий GRANT/REVOKE на объекты и операции; представления и хранимые процедуры, скрывающие лишние данные; шифрование хранимых данных и соединений; аудит действий; резервное копирование как защита от потери. Дополняется мерами уровня ОС и сети.