Информационное обеспечение систем автоматизации

Тема 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). Для профиля «анализ данных» уместно сказать: рабочие данные — в реляционной СУБД, аналитические витрины — в колоночных.

Компоненты банка данных подробнее:

• словарь данных (каталог) — «база данных о базе данных»: описания таблиц, атрибутов, типов, ограничений, индексов, представлений, пользователей и привилегий. Хранится в самой СУБД как системные таблицы (в SQL-стандарте — INFORMATION_SCHEMA), поэтому запросом можно узнать структуру любой таблицы;
• администратор БД (АБД) — специалист (или группа), отвечающий за проектирование схемы, разграничение доступа, настройку производительности (индексы, планы запросов), резервное копирование и восстановление, мониторинг;
• технические средства — серверы, дисковые массивы, сеть; организационно-методические средства — регламенты доступа, инструкции, документация.

SELECT column_name, data_type, is_nullable
FROM information_schema.columns
WHERE table_name = 'student';

Классификация СУБД:

• по модели данных — иерархические, сетевые, реляционные, объектно-реляционные, NoSQL;
• по архитектуре — файл-серверные (данные — файл на общем диске, обработка на клиенте: Access, dBase; узкое место — сеть и блокировки), клиент-серверные (запросы выполняет сервер СУБД, клиенту уходит только результат: PostgreSQL, Oracle, MS SQL Server, Interbase/Firebird), встраиваемые (библиотека внутри приложения, без отдельного сервера: SQLite);
• по размещению — централизованные и распределённые (данные на нескольких узлах, для приложения выглядят единой БД; нужны фрагментация, репликация и распределённые транзакции).

Уровни представления. Схема и подсхема

Трёхуровневая архитектура ANSI/SPARC обеспечивает независимость данных:

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

Как уровни связаны. Между соседними уровнями СУБД хранит отображения (mappings): внешне-концептуальное («поле „группа“ представления деканата — это атрибут name таблицы sgroup») и концептуально-внутреннее («таблица student лежит в файле X, проиндексирована B-деревом по id»). Запрос пользователя формулируется в терминах его подсхемы, СУБД по отображениям переводит его к концептуальной схеме, затем к физическим операциям чтения блоков. Именно наличие двух отображений и даёт две независимости: меняется уровень — переписывается только отображение, а не соседние уровни.

Тема 3.2

Модели данных

Иерархическая, сетевая и реляционная модели; отношение, ключи.

Три классические модели

• Иерархическая — данные в виде дерева «предок–потомок»; у записи один родитель. Быстрая навигация вдоль иерархии, но связи «многие-ко-многим» требуют дублирования (IMS).
• Сетевая — граф: запись может иметь много владельцев (модель CODASYL). Гибче иерархической, но сложна в сопровождении, доступ навигационный.
• Реляционная (Э. Кодд, 1970) — данные в виде отношений (таблиц); доступ декларативный: указывается, что найти, а не как. Господствующая модель.

Почему победила реляционная модель: строгая математическая основа (теория множеств и логика предикатов — можно доказывать свойства запросов и преобразовывать их); физическая независимость данных (связи через значения, а не указатели, — СУБД свободна менять хранение); декларативный язык, доступный не только программистам; теория нормализации как формальная методика проектирования. Недостатки иерархической и сетевой моделей — навигационный доступ, жёсткие пути, перестройка структуры при изменении запросов — стали главным аргументом Кодда.

Современные ветви: объектно-ориентированная модель хранит объекты с методами и наследованием (ООСУБД остались нишевыми); объектно-реляционная — реляционная ядро + пользовательские типы, массивы, JSON (PostgreSQL); NoSQL-семейства (документные, ключ-значение, колоночные, графовые) жертвуют универсальностью запросов и строгой согласованностью ради масштабирования.

Реляционная модель: термины

Свойства отношений: нет одинаковых кортежей; порядок кортежей и атрибутов не важен; значения атрибутов атомарны (нормализованность).

Ключи: потенциальный ключ — минимальный набор атрибутов, однозначно определяющий кортеж (уникальность + неизбыточность); один из потенциальных выбирается первичным (PRIMARY KEY, не допускает NULL); внешний ключ (FOREIGN KEY) — атрибут, ссылающийся на первичный ключ другого отношения — механизм связи таблиц и ссылочной целостности.

Требования Кодда (выборочно, «на понимание»): вся информация представлена только значениями в таблицах (информационное правило); каждый элемент данных адресуется именем таблицы, значением первичного ключа и именем столбца; системный каталог сам является реляционной БД; поддержка операций над множествами строк, а не только «запись за записью»; независимость данных от физического хранения. Эти правила — критерий «настоящей реляционности» СУБД.

Тема 3.3

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

Стандартные и специальные операции над отношениями.

Стандартные (теоретико-множественные) операции — над совместимыми отношениями: объединение (все кортежи обоих), пересечение, разность (кортежи первого, отсутствующие во втором), декартово произведение (все сочетания кортежей). Специальные: выборка σ (строки по условию), проекция π (заданные столбцы без дубликатов), соединение ⋈ (произведение + условие равенства атрибутов — естественное соединение), деление.

Виды соединений. Общий случай — θ-соединение: σ_θ(A × B), где θ — любое условие сравнения атрибутов (<, >, ≠ …). Если θ — равенство, соединение называется эквисоединением (в результате оба сравниваемых столбца). Естественное соединение — эквисоединение по всем одноимённым атрибутам с удалением дубликата столбца. Внешние соединения (left/right/full) добавляют непарные кортежи, дополняя их NULL, — расширение классической алгебры, вошедшее в SQL.

Тема 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).

Типы данных SQL: числовые точные (INTEGER, SMALLINT, NUMERIC(p,s)/DECIMAL — для денег) и приближённые (REAL, DOUBLE PRECISION); строковые фиксированной (CHAR(n)) и переменной (VARCHAR(n)) длины; дата-время (DATE, TIME, TIMESTAMP); логический BOOLEAN; большие объекты (BLOB/CLOB). Выбор типа — тоже ограничение целостности: домен атрибута в SQL задаётся типом плюс CHECK.

Условия WHERE, о которых спрашивают: BETWEEN a AND b (включительно), IN (список), LIKE с шаблонами % (любая строка) и _ (один символ), IS NULL. Предикаты над подзапросами: EXISTS (подзапрос непуст), ANY/SOME (сравнение хотя бы с одним значением), ALL (со всеми): x > ALL(…) — «больше максимума», x > ANY(…) — «больше минимума». DISTINCT убирает дубликаты строк результата.

GRANT SELECT, INSERT ON student TO dekanat;
GRANT SELECT ON v_stipend TO buhgalteria;   -- доступ только к представлению
REVOKE INSERT ON student FROM dekanat;
GRANT SELECT ON student TO analyst WITH GRANT OPTION; -- может передавать право дальше

Серверная логика: хранимые процедуры — именованные программы на процедурном расширении SQL (PSQL в Interbase/Firebird, PL/pgSQL в PostgreSQL), выполняются на сервере — меньше сетевых обменов, единая бизнес-логика; триггеры — процедуры, автоматически срабатывающие BEFORE/AFTER INSERT/UPDATE/DELETE строки, — сложные правила целостности (журналирование изменений, каскадные пересчёты); генераторы/последовательности (SEQUENCE) — источник уникальных номеров для суррогатных ключей.

SELECT name FROM student
WHERE group_id IN (SELECT id FROM sgroup WHERE course = 3);

SELECT группа, COUNT(*) AS оценок, AVG(оценка) AS средний
FROM ведомость GROUP BY группа HAVING AVG(оценка) >= 4;

SELECT s.name FROM student s
WHERE s.rating > (SELECT AVG(s2.rating) FROM student s2
                  WHERE s2.group_id = s.group_id);

Тема 3.5

Проектирование реляционной БД

Функциональные зависимости, декомпозиция, нормальные формы, метод «сущность–связь».

Функциональные зависимости и нормализация

Вывод зависимостей — аксиомы Армстронга. Из заданного множества ФЗ выводятся новые по трём правилам:

Аксиомы корректны (выводят только истинные ФЗ) и полны (выводят все). Замыкание X⁺ — множество всех атрибутов, функционально зависящих от X; практический смысл: X — потенциальный ключ отношения ⇔ X⁺ содержит все атрибуты, а сам X неизбыточен. Так проверка «является ли набор ключом» сводится к механическому вычислению замыкания.

Плохо спроектированное отношение страдает аномалиями: избыточность (дублирование данных), аномалии обновления, вставки и удаления. Лекарство — декомпозиция: разбиение отношения на проекции без потерь (соединение проекций восстанавливает исходное отношение — теорема Хита) и без потери ФЗ.

• 1НФ — все значения атомарны, нет повторяющихся групп.
• 2НФ — 1НФ + каждый неключевой атрибут полностью зависит от составного ключа (нет зависимостей от части ключа).
• 3НФ — 2НФ + нет транзитивных зависимостей неключевых атрибутов от ключа.
• НФБК — каждый детерминант ФЗ является потенциальным ключом (усиление 3НФ).

Выше НФБК (называют, но подробно не разбирают): 4НФ устраняет многозначные зависимости X →→ Y — когда в одной таблице независимо перечислены два множества фактов об X (преподаватель ведёт {предметы} и владеет {языками}: хранение в одной таблице порождает декартово произведение строк); 5НФ — зависимости соединения (отношение восстановимо только соединением трёх и более проекций). На практике проектируют до 3НФ/НФБК.

Этапы проектирования БД целиком: 1) системный анализ предметной области (какие объекты, процессы, документы, запросы); 2) инфологическое (концептуальное) проектирование — ER-модель, независимая от СУБД; 3) даталогическое — отображение в реляционную схему конкретной СУБД + нормализация; 4) физическое — индексы, файловые структуры, распределение по носителям. Ошибка на раннем этапе стоит дороже всего: перестройка схемы работающей БД тянет за собой данные, запросы и приложения.

Метод «сущность–связь» (ER)

Инфологическое проектирование: предметная область описывается сущностями (объекты с атрибутами), связями между ними (1:1, 1:M, M:N) и ключами. Затем — даталогическое проектирование: ER-диаграмма отображается в реляционную схему: сущность → таблица, атрибут → столбец, связь 1:M → внешний ключ на стороне «многих», связь M:N → отдельная таблица-связка из двух внешних ключей.

Словарь ER-модели: сущность — тип объектов (СТУДЕНТ), экземпляр — конкретный объект (Иванов); атрибуты бывают простые и составные (адрес = город + улица), однозначные и многозначные (телефоны — при переводе в схему уходят в отдельную таблицу), производные (возраст вычисляется из даты рождения — не хранят). У связи различают кардинальность (1:1, 1:M, M:N — «сколько максимум») и класс принадлежности / модальность (обязательная или необязательная — «может ли не быть»): студент обязан числиться в группе, группа может быть без куратора. Обязательность определяет NOT NULL у внешнего ключа.

Тема 3.6

Физическая организация, защита и целостность

Хешированные и индексированные файлы, защита БД, транзакции.

Физическая организация данных

• Последовательные файлы — записи подряд; поиск O(n), вставка в конец.
• Хешированные файлы — адрес записи вычисляется хеш-функцией от ключа h(K); поиск по ключу O(1). Проблема — коллизии (разным ключам — один адрес): разрешаются цепочками переполнения или открытой адресацией. Диапазонный поиск неэффективен.
• Индексированные файлы — отдельная структура «значение ключа → адрес записи». Индекс может быть плотным (на каждую запись) и неплотным (на блок); первичным и вторичным. Основная структура — B-дерево/B⁺-дерево: сбалансированное многоветвистое дерево, все листья на одной глубине, поиск/вставка O(log n), листья B⁺-дерева связаны списком — быстрый диапазонный поиск.

Единица обмена с диском — страница (блок), обычно 4–16 Кбайт: СУБД никогда не читает «одну запись», только страницу целиком, а в оперативной памяти держит буферный пул недавно использованных страниц. Поэтому стоимость запроса меряют числом обращений к диску, и все физические структуры проектируются «страницами»: узел B-дерева = страница, корзина хеш-файла = страница.

Виды индексов подробнее:

• плотный — статья индекса на каждую запись; разреженный (неплотный) — одна статья на страницу (её минимальный ключ), возможен только по упорядоченному файлу: находим нужную страницу по индексу, внутри — последовательно;
• первичный — по ключу упорядочения файла (один на таблицу), вторичные — по прочим атрибутам (всегда плотные: файл по ним не упорядочен);
• кластерный — сами записи физически уложены в порядке ключа индекса (в B⁺-дереве листья и есть данные), один на таблицу; некластерный — листья хранят ссылки на записи. Диапазонный запрос по кластерному индексу читает соседние страницы, по некластерному — прыгает по всему файлу;
• составной — по нескольким столбцам (группа, имя): работает для условий по префиксу списка столбцов.

Хеширование подробнее. Хеш-функция должна равномерно рассеивать ключи; классика — деление с остатком h(K) = K mod M, где M — простое число корзин. При коэффициенте заполнения выше ~0,7–0,8 цепочки растут и поиск деградирует; статический хеш-файл приходится перестраивать целиком. Расширяемое (динамическое) хеширование решает это без полной перестройки: используется каталог указателей на корзины, при переполнении расщепляется лишь одна корзина, а каталог при необходимости удваивается — число дисковых обращений остаётся 1–2 при любом росте данных.

Защита, целостность и сохранность БД

• Защита: идентификация и аутентификация пользователей; привилегии GRANT/REVOKE на таблицы и операции; представления, скрывающие часть данных; шифрование; аудит.
• Целостность — соответствие данных ограничениям предметной области: целостность сущностей (первичный ключ уникален и не NULL), ссылочная целостность (внешние ключи ссылаются на существующие записи; ON DELETE CASCADE/RESTRICT), ограничения CHECK, NOT NULL, UNIQUE, триггеры.
• Сохранность — восстановление после сбоев: транзакции со свойствами ACID (атомарность, согласованность, изоляция, долговечность), журнал изменений (упреждающая запись), контрольные точки, резервное копирование.

Изоляция параллельных транзакций. Без изоляции возникают аномалии: грязное чтение (видны незафиксированные чужие изменения), неповторяющееся чтение (два чтения одной строки дают разное — её успели изменить), фантомы (повторный запрос по условию возвращает новые строки). Стандарт SQL задаёт уровни изоляции — компромисс строгости и параллелизма:

Реализация — блокировки (чтения/записи, строк/таблиц; риск взаимоблокировок) или многоверсионность MVCC: читатели видят «снимок» данных и не блокируют писателей.

Модели разграничения доступа: дискреционная (избирательная) — у каждого объекта есть владелец, раздающий привилегии конкретным пользователям и ролям (GRANT/REVOKE; так работают все SQL-СУБД); мандатная — объектам присваиваются метки секретности, субъектам — уровни допуска, правила сравнения меток задаёт система, а не владелец (защищённые СУБД для гостайны); ролевая (RBAC) — привилегии собираются в роли («деканат», «бухгалтер»), пользователям выдаются роли — на практике дополняет дискреционную.

query = "SELECT * FROM users WHERE name = '" + name + "'";
-- пользователь ввёл:  ' OR '1'='1
SELECT * FROM users WHERE name = '' OR '1'='1';   -- вернёт всех

Резервное копирование: полное — вся БД (долго, но восстановление в один шаг); инкрементное — изменения с последней любой копии (быстро копировать, долго восстанавливать цепочку); дифференциальное — изменения с последнего полного (компромисс: восстановление = полное + одна разностная). Копии хранят отдельно от сервера; вместе с архивом журнала возможно восстановление на момент времени (point-in-time). Репликация — поддержание копий БД на нескольких узлах (синхронная — гарантия идентичности, асинхронная — скорость): отказоустойчивость и разгрузка чтения.