---

ОТВЕТЫ НА ТЕОРЕТИЧЕСКИЕ ВОПРОСЫ ИЗ СТАРЫХ БИЛЕТОВ

Файл сделан для быстрого копирования.
Все ответы написаны в простом стиле и с примерами.


1. Элементы и описание нотации IDEF1X.

IDEF1X - нотация для моделирования данных. Она используется, чтобы описать сущности, атрибуты, ключи и связи между сущностями.

Основные элементы IDEF1X:
1. сущность - объект предметной области, который потом обычно становится таблицей;
2. атрибут - свойство сущности, которое потом становится столбцом;
3. первичный ключ - набор атрибутов, который уникально определяет строку;
4. внешний ключ - ссылка на ключ другой сущности;
5. связь - линия между сущностями;
6. идентифицирующая связь - ключ родителя входит в ключ потомка;
7. неидентифицирующая связь - потомок имеет свой ключ, а ключ родителя хранится как внешний ключ.

Пример:
Есть сущность aircrafts с ключом aircraft_code и сущность flights с ключом flight_id. В flights есть aircraft_code как внешний ключ. Это связь один ко многим: один самолет может выполнять много рейсов.

В SQL это выглядит так:

CREATE TABLE aircrafts_data (
    aircraft_code bpchar PRIMARY KEY,
    model jsonb,
    range integer
);

CREATE TABLE flights (
    flight_id integer PRIMARY KEY,
    aircraft_code bpchar REFERENCES aircrafts_data(aircraft_code)
);

Главная идея IDEF1X - показать структуру данных до создания таблиц в СУБД.


2. Особенности построения индексных структур: B-деревья, битовые карты и другие.

Индекс - дополнительная структура данных, которая ускоряет поиск строк в таблице. Индекс занимает место и замедляет изменение данных, потому что при INSERT, UPDATE и DELETE его тоже нужно обновлять.

Основной индекс в PostgreSQL - B-tree. Он похож на сбалансированное сильно ветвящееся дерево. В нем данные упорядочены, поэтому можно быстро искать значения и диапазоны.

B-tree хорошо подходит для:
1. равенства;
2. сравнений больше или меньше;
3. BETWEEN;
4. ORDER BY;
5. поиска максимума и минимума.

Пример:

CREATE INDEX ticket_flights_amount_idx
ON ticket_flights(amount);

SELECT *
FROM ticket_flights
WHERE amount > 200000;

Если условие выбирает небольшую часть таблицы, индекс обычно выгоден. Если выбирается почти вся таблица, планировщик может выбрать Seq Scan.

Bitmap-подход:
Сначала по индексу строится битовая карта подходящих строк, потом таблица читается по этой карте. Это удобно, когда строк достаточно много, но не вся таблица.

Пример плана:
Bitmap Index Scan ищет строки в индексе.
Bitmap Heap Scan читает строки из таблицы.

Другие индексы:
Hash - для равенства.
GIN - для массивов, jsonb, полнотекстового поиска.
GiST - для геометрии и специальных типов.
BRIN - для очень больших таблиц, где данные физически упорядочены.


3. Синтаксис, описание и примеры использования хранимых процедур и функций.

Функция - объект БД, который принимает параметры, выполняет код и возвращает значение или таблицу. Ее можно использовать в SELECT.

Общий синтаксис функции:

CREATE OR REPLACE FUNCTION name(param type)
RETURNS type AS $$
BEGIN
    ...
    RETURN ...;
END;
$$ LANGUAGE plpgsql;

Пример функции:

CREATE OR REPLACE FUNCTION get_bookings_by_passenger(p_passenger_id varchar)
RETURNS TABLE(book_ref bpchar, book_date timestamptz, total_amount numeric) AS $$
BEGIN
    RETURN QUERY
    SELECT DISTINCT b.book_ref, b.book_date, b.total_amount
    FROM bookings b
    JOIN tickets t ON t.book_ref = b.book_ref
    WHERE t.passenger_id = p_passenger_id;
END;
$$ LANGUAGE plpgsql;

SELECT *
FROM get_bookings_by_passenger('8149 604011');

Процедура похожа на функцию, но вызывается через CALL и обычно используется для действий с данными. Процедура не обязана возвращать значение.

Пример процедуры:

CREATE OR REPLACE PROCEDURE cancel_flights_by_aircraft(p_aircraft bpchar) AS $$
BEGIN
    UPDATE flights
    SET status = 'Cancelled'
    WHERE aircraft_code = p_aircraft;
END;
$$ LANGUAGE plpgsql;

CALL cancel_flights_by_aircraft('733');

Разница:
Функция чаще используется для вычисления и возврата результата.
Процедура чаще используется для выполнения действия.


4. Описание, синтаксис и примеры использования оконных функций.

Оконная функция считает значение по набору строк, связанному с текущей строкой. При этом строки не сворачиваются, в отличие от GROUP BY.

Синтаксис:

function(...) OVER (
    PARTITION BY ...
    ORDER BY ...
    ROWS BETWEEN ... AND ...
)

PARTITION BY делит данные на группы.
ORDER BY задает порядок внутри группы.
ROWS или RANGE задает рамку окна.

Пример ранжирования самолетов:

SELECT aircraft_code,
       model,
       range,
       rank() OVER (ORDER BY range DESC) AS rnk,
       dense_rank() OVER (ORDER BY range DESC) AS dense_rnk
FROM aircrafts_data;

rank делает ранг с пропусками.
dense_rank делает ранг без пропусков.

Пример накопительной суммы:

SELECT b.book_date::date AS day,
       sum(b.total_amount) AS day_sum,
       sum(sum(b.total_amount)) OVER (
           ORDER BY b.book_date::date
       ) AS running_sum
FROM bookings b
GROUP BY b.book_date::date
ORDER BY day;

Оконные функции удобны для рейтингов, накопительных итогов, сравнения строки со средним или максимумом по группе.


5. Уточнение и обобщение, композиция, агрегирование, суперклассы и подклассы в модели сущность-связь.

Обобщение - объединение нескольких похожих сущностей в одну более общую.
Пример: пассажир и сотрудник могут быть обобщены до сущности Человек.

Уточнение - разбиение общей сущности на более частные.
Пример: билет можно уточнить как билет эконом-класса, бизнес-класса и комфорт-класса.

Суперкласс - общая сущность.
Подкласс - частная сущность, которая наследует свойства суперкласса.

Композиция - сильная связь часть-целое. Часть обычно не существует без целого.
Пример: посадочный талон относится к конкретному билету и рейсу. Без них он не имеет смысла.

Агрегирование - когда связь между сущностями рассматривается как отдельная сущность.
Пример: связь "пассажир летит рейсом" можно представить таблицей ticket_flights. У нее есть свои атрибуты: ticket_no, flight_id, fare_conditions, amount.

Пример из авиаперевозок:
Сущности tickets и flights связаны многие ко многим. Эта связь реализована через ticket_flights. Поэтому ticket_flights можно рассматривать как сущность-пересечение.


6. Изучение предметной области. Формализация, смысловое описание, бизнес-правила.

Изучение предметной области - первый этап проектирования БД. На этом этапе выясняют, какие данные нужно хранить, кто ими пользуется и какие операции нужны.

Смысловое описание - текстовое описание предметной области обычным языком.
Например: "Система хранит информацию о рейсах, пассажирах, билетах, бронированиях и самолетах".

Формализация - перевод смыслового описания в строгую модель: сущности, атрибуты, связи, ключи, ограничения.

Бизнес-правила - правила, которые должны выполняться в предметной области.
Примеры:
1. стоимость билета не может быть отрицательной;
2. рейс должен ссылаться на существующий самолет;
3. один билет может включать несколько перелетов;
4. место в посадочном талоне должно быть связано с конкретным рейсом.

Пример реализации бизнес-правила:

ALTER TABLE ticket_flights
ADD CONSTRAINT amount_positive CHECK (amount >= 0);

Пример внешнего ключа:

ALTER TABLE flights
ADD CONSTRAINT flights_aircraft_fkey
FOREIGN KEY (aircraft_code)
REFERENCES aircrafts_data(aircraft_code);


7. Соединения таблиц на основе слияния: особенности реализации, сложность алгоритмов.

Merge Join - соединение на основе слияния. Оно работает, когда оба набора строк отсортированы по ключу соединения.

Алгоритм:
1. первая таблица сортируется по ключу соединения или читается по индексу;
2. вторая таблица тоже сортируется или читается по индексу;
3. СУБД идет по двум отсортированным наборам и соединяет совпадающие ключи.

Сложность:
Если данные уже отсортированы, сложность примерно O(n + m).
Если нужна сортировка, добавляется стоимость сортировки: O(n log n + m log m).

Когда Merge Join выгоден:
1. таблицы большие;
2. данные уже упорядочены индексами;
3. результат нужно вернуть в отсортированном виде.

Пример:

SELECT t.ticket_no, tf.flight_id
FROM tickets t
JOIN ticket_flights tf ON tf.ticket_no = t.ticket_no
ORDER BY t.ticket_no;

Если tickets_pkey и ticket_flights_pkey дают нужный порядок, PostgreSQL может выбрать Merge Join без отдельного Sort.


8. Особенности использования транзакций. Блокировка на уровне строк и таблиц, другой вариант блокировки.

Транзакция - набор действий, который выполняется как единое целое.

Пример:

BEGIN;
UPDATE bookings
SET total_amount = total_amount + 100
WHERE book_ref = '00000F';
COMMIT;

Если нужно отменить изменения:

BEGIN;
UPDATE bookings
SET total_amount = total_amount + 100
WHERE book_ref = '00000F';
ROLLBACK;

Блокировка нужна, чтобы параллельные транзакции не изменяли одни и те же данные некорректно.

Строковая блокировка:

BEGIN;
SELECT *
FROM bookings
WHERE book_ref = '00000F'
FOR UPDATE;
COMMIT;

FOR UPDATE блокирует выбранные строки.

Табличная блокировка:

BEGIN;
LOCK TABLE bookings IN SHARE MODE;
COMMIT;

Другой вариант блокировки - консультативные блокировки advisory locks. Они не привязаны напрямую к строкам таблицы, приложение само решает, что означает такая блокировка.

Пример:

SELECT pg_advisory_lock(100);
SELECT pg_advisory_unlock(100);


9. Соединения таблиц на основе вложенных циклов и хеширования: особенности реализации, сложность алгоритмов.

Nested Loop - соединение вложенными циклами.
Для каждой строки внешней таблицы СУБД ищет подходящие строки во внутренней таблице.

Сложность без индекса примерно O(n * m).
Если есть индекс по ключу внутренней таблицы, может быть намного быстрее.

Пример:

SELECT f.flight_id, a.airport_name
FROM flights f
JOIN airports a ON a.airport_code = f.departure_airport
WHERE f.flight_id = 1;

Hash Join - соединение через хеширование.
Для одной таблицы строится hash-таблица по ключу соединения, затем строки второй таблицы ищутся в ней.

Сложность примерно O(n + m).

Пример:

SELECT f.flight_id, a.airport_name
FROM flights f
JOIN airports a ON a.airport_code = f.arrival_airport;

Nested Loop выгоден для маленьких наборов или при хороших индексах.
Hash Join выгоден для больших неотсортированных таблиц.


10. Способы организации, назначение, характеристики и примеры распределенных СУБД.

Распределенная СУБД хранит данные на нескольких узлах, но предоставляет пользователю единый доступ.

Назначение:
1. масштабирование;
2. отказоустойчивость;
3. распределение нагрузки;
4. хранение данных ближе к пользователям.

Способы организации:
1. репликация - копии данных на разных узлах;
2. шардирование - разделение строк по узлам;
3. фрагментация - разделение таблиц на части;
4. федерация - объединение нескольких баз.

Характеристики:
1. прозрачность расположения данных;
2. устойчивость к отказам;
3. сложность согласованности;
4. сетевые задержки;
5. необходимость распределенных транзакций или eventual consistency.

Примеры:
Cassandra, MongoDB cluster, CockroachDB, PostgreSQL с репликацией и шардингом.

Пример шардирования:
Бронирования можно распределять по узлам по диапазонам book_ref или по хешу book_ref.


11. Описание и примеры использования уровней изоляции транзакций.

Уровень изоляции определяет, какие изменения других транзакций видит текущая транзакция.

READ UNCOMMITTED:
В PostgreSQL фактически работает как READ COMMITTED. Грязное чтение не допускается.

READ COMMITTED:
Каждый оператор видит только зафиксированные данные на момент начала оператора. Повторный SELECT может увидеть новые данные, если другая транзакция сделала COMMIT.

REPEATABLE READ:
Транзакция видит снимок данных на момент начала транзакции. Повторные SELECT дают один и тот же результат.

SERIALIZABLE:
Самый строгий уровень. Результат должен быть таким, как будто транзакции выполнялись последовательно. Возможны ошибки сериализации, тогда транзакцию надо повторить.

Пример:

BEGIN ISOLATION LEVEL REPEATABLE READ;
SELECT total_amount
FROM bookings
WHERE book_ref = '00000F';
COMMIT;

Что важно:
Чем выше уровень изоляции, тем больше защита от аномалий, но тем выше вероятность ожиданий, конфликтов и ошибок сериализации.


12. Основные системы хранения данных и знаний и их особенности.

Основные виды систем:
1. реляционные БД;
2. key-value хранилища;
3. документоориентированные БД;
4. колоночные БД;
5. графовые БД;
6. хранилища знаний.

Реляционные БД:
Данные хранятся в таблицах. Есть SQL, ключи, ограничения, транзакции.
Примеры: PostgreSQL, MySQL, Oracle.

Key-value:
Данные хранятся как ключ и значение. Очень быстрый доступ по ключу.
Примеры: Redis, DynamoDB.

Документоориентированные:
Данные хранятся как документы JSON или BSON.
Примеры: MongoDB, CouchDB.

Колоночные:
Данные хранятся по столбцам. Хорошо для аналитики и больших объемов.
Примеры: ClickHouse, Cassandra.

Графовые:
Данные хранятся как вершины и ребра.
Пример: Neo4j.

Хранилища знаний:
Хранят факты, правила, связи, онтологии.
Примеры: RDF-хранилища, OWL-онтологии.


13. Чтение плана выполнения запроса. EXPLAIN: синтаксис и использование, ключевые параметры.

EXPLAIN показывает план выполнения запроса.

Синтаксис:

EXPLAIN
SELECT ...

EXPLAIN ANALYZE реально выполняет запрос и показывает фактическое время.

EXPLAIN (ANALYZE, BUFFERS)
SELECT *
FROM ticket_flights
WHERE amount > 200000;

Что смотреть:
1. Seq Scan - последовательное чтение таблицы;
2. Index Scan - чтение через индекс;
3. Bitmap Index Scan и Bitmap Heap Scan - поиск через индекс и чтение таблицы по bitmap;
4. Nested Loop, Hash Join, Merge Join - способы соединения;
5. Sort - сортировка;
6. Aggregate, HashAggregate, GroupAggregate - агрегирование;
7. cost - оценочная стоимость;
8. rows - оценка количества строк;
9. actual time - фактическое время;
10. loops - число повторов узла;
11. Buffers - чтение из памяти и с диска.

Пример пояснения:
Если в плане есть Parallel Seq Scan, Gather, Partial Aggregate и Finalize Aggregate, запрос выполняется параллельно. Рабочие процессы считают частичные суммы, а главный процесс собирает итог.


14. Описание, синтаксис и примеры использования сложных подзапросов.

Сложный подзапрос - вложенный запрос, который может возвращать одно значение, строку, столбец или таблицу. Он может быть коррелированным, то есть зависеть от внешнего запроса.

Пример подзапроса в WHERE:

SELECT book_ref, total_amount
FROM bookings
WHERE total_amount > (
    SELECT avg(total_amount)
    FROM bookings
);

Пример IN:

SELECT passenger_name
FROM tickets
WHERE ticket_no IN (
    SELECT ticket_no
    FROM ticket_flights
    WHERE amount > 200000
);

Пример EXISTS:

SELECT t.ticket_no, t.passenger_name
FROM tickets t
WHERE EXISTS (
    SELECT 1
    FROM ticket_flights tf
    WHERE tf.ticket_no = t.ticket_no
);

Пример коррелированного подзапроса:

SELECT a.aircraft_code,
       (
           SELECT count(*)
           FROM flights f
           WHERE f.aircraft_code = a.aircraft_code
       ) AS flight_count
FROM aircrafts_data a;

Минус коррелированного подзапроса:
Он может выполняться много раз, по одному разу для каждой строки внешнего запроса.


15. Способы организации, назначение, характеристики и примеры хранилищ ключ-значение.

Key-value хранилище хранит данные в виде ключ - значение.

Пример:
ключ: passenger:123
значение: Ivan Petrov

Назначение:
1. кеш;
2. сессии пользователей;
3. счетчики;
4. быстрый доступ по идентификатору;
5. временные данные.

Характеристики:
1. очень быстрый доступ по ключу;
2. простая модель данных;
3. хорошее горизонтальное масштабирование;
4. нет сложных JOIN;
5. сложные выборки обычно делает приложение.

Пример Redis:

SET passenger:123 "Ivan Petrov"
GET passenger:123

Плюс:
Очень быстро.

Минус:
Если нужно искать по множеству условий и соединять данные, реляционная БД удобнее.


16. Транзакции. Атомарность, согласованность, изолированность, долговечность. Сериализация транзакций.

Транзакция - логическая единица работы с БД.

ACID:
Atomicity - атомарность. Все действия выполняются полностью или не выполняются.
Consistency - согласованность. После транзакции данные остаются корректными.
Isolation - изолированность. Параллельные транзакции не должны мешать друг другу.
Durability - долговечность. После COMMIT изменения сохраняются.

Пример:

BEGIN;
UPDATE bookings
SET total_amount = total_amount + 100
WHERE book_ref = '00000F';
COMMIT;

Если произошла ошибка:

ROLLBACK;

Сериализация транзакций - свойство, при котором результат параллельного выполнения такой же, как если бы транзакции выполнялись последовательно.

Пример:
Если две транзакции одновременно меняют одну сумму бронирования, СУБД должна не допустить потерянного изменения. Для этого используются изоляция, блокировки и MVCC.


17. Способы организации, назначение, характеристики и примеры документоориентированных баз данных.

Документоориентированная БД хранит данные в виде документов, чаще всего JSON или BSON.

Пример документа:

{
  "ticket_no": "0005432000987",
  "passenger_name": "Ivan Petrov",
  "flights": [
    {"flight_id": 10, "amount": 12500},
    {"flight_id": 11, "amount": 9300}
  ]
}

Назначение:
1. хранение данных с гибкой структурой;
2. хранение вложенных объектов;
3. быстрые веб-приложения;
4. работа с JSON-документами.

Характеристики:
1. нет жесткой схемы как в реляционной БД;
2. данные могут быть вложенными;
3. часто используется денормализация;
4. горизонтальное масштабирование обычно проще;
5. JOIN ограничены или отсутствуют.

Примеры:
MongoDB, CouchDB.

Плюс:
Удобно хранить сложные JSON-объекты.

Минус:
Сложнее поддерживать строгую целостность и сложные связи между данными.