Это 𝛼-версия листка. Сохраняйте свои скрипты вне ejudge, там всё может потеряться!

Реляционные базы данных

Практически во всех задачах, которые встречались нам ранее, данные поступали из стандартного ввода или из файла вроде input.txt. Однако в реальных приложениях очень часто данные нужно хранить между запусками и периодически модифицировать. В принципе данные можно хранить в простых текстовых файлах и обновлять их там же. Или использовать библиотеки вроде pickle. Но это не очень удобно и не слишком надёжно, если речь идёт о больших приложениях.

Понятие база данных — крайне общее. Это — совокупность данных, организованная так, чтобы они могли быть найдены и обработаны при помощи ЭВМ. Сейчас практически всегда, когда употребляется словосочетание «база данных», имеется в виду какой-нибудь конкретный подход для хранения и обработки данных, или даже конкретное ПО (конкретная «СУБД», система управления базами данных), которое всё это реализует.

В этой теме мы будем работать с реляционными базами данных. «Реляционные» — это от слова relations — отношения. Если забить на формализм, то суть подхода в следующем. Существует ровно две сущности: элемент (value) и таблица (table). Элемент — это какой-то кусочек данных, которые мы храним: число, строка, время и т.п. Таблица — ну, это прямоугольная таблица, в которой есть строки и столбцы. Множество столбцов (их имён и типов) называется заголовком таблицы.

При помощи таблиц можно хранить разнообразные отношения (relations), в том числе чертовски сложные. Например, вот так можно хранить граф:

Таблица «вершины»

node
A
B
C
D
E
F
G

Таблица «рёбра»

from	to
A	B
B	C
B	D
B	E
C	E
D	E
E	F
G	D

На множестве всех таблиц определены операции, которые все вместе называются «реляционной алгеброй». Вот список почти всех таких операций (тоже по модулю некоторого занудства):

• переименование таблицы — любую таблицу можно переименовать и получить новую таблицу с новым именем;
• переименование столбцов — если поменять в таблице имена столцбов, то тоже получится таблица;
• объединение таблиц — если у двух таблиц одинаковый заголовок (множество столбцов), то их можно объединить: в результате будет таблица с тем же заголовком, и множеством строк, в которой каждая либо лежит в первой, либо во второй таблице, либо в обеих;
• пересечение таблиц — если у двух таблиц одинаковый заголовок, то их можно пересечь: в результате будет таблица с тем же заголовком, и множеством строк, в которой каждая лежит и в первой, и во второй таблице;
• произведение таблиц — у получившийся таблицы будет суммарное количество столбцов, а строки — все возможные наборы, которые начинаются на строчку первой таблицы и заканчиваются на строку второй;
• выборка из таблицы — у любой таблицы можно взять подмножество строк. Получится таблица с тем же заголовком и частью строк;
• проекция таблицы — у любой таблицы можно взять подмножество столбцов, после чего удалить (или не удалять) дубликаты. Получится таблица, в котором меньше столбов, и столько же, либо меньше строк (из-за удаления дублей);
• добавление строк — в таблицу можно добавить новую строку с данными, и получить таблицу с тем же заголовком, но одной «бонусной» строкой;
• добавление столбцов — в таблицу можно добавить столбец с данным именем, значения которого в каждой строчке определяется функцией от значений во всех остальных столбцах данной строки.
• соединение таблиц — если у двух таблиц есть общие столбцы, то соединение таблиц — это новая таблица со всеми уникальными столбцами, строки которой «склеены» по совпадающим значениям общих столбцов. Эта операция — это композиция произведения, выборки и проекции: в произведении таблиц берём только те пары, где значения общих столбцов одинаковы. После чего удаляем общие столбцы;

Примеры всех этих операций будут дальше. Примечательно в них только то, что все они берут на вход одну или две таблицы и, может быть, какие-нибудь дополнительные данные, а на выходе всегда получают новую таблицу. Именно из-за замкнутости это всё называют «алгеброй».

SQL — язык структурированных запросов

Для того, чтобы формально описывать эти реляционные операции над таблицами, придуман специальный язык: SQL (Structured Query Language, язык структурированных запросов). У языка SQL есть некий стандарт (последняя версия ISO/IEC 9075:2016), однако конкретные «фразы» и богатство возможностей языка сильно зависят от конкретной реализации. Кроме реляционных операций язык позволяет создавать новые пустые таблицы с заданными столбцами, добавлять в таблицы новые записи, изменять и удалять строчки, изменять структуру таблиц, объявлять взаимосвязи между таблицами и т.п.

Вот примеры некоторых операций для типичной реализации SQL:

CREATE TABLE students (name TEXT, age NUMERIC);

INSERT INTO students VALUES ('Вася', 13), ('Маша', 14);

SELECT * FROM students;

SELECT * FROM students UNION SELECT * FROM students;

SELECT * FROM students INTERSECT SELECT * FROM students;

SELECT * FROM students CROSS JOIN teachers;

SELECT * FROM students WHERE age < 14;

SELECT age FROM students;

SELECT students.*, age*365 as days FROM students;

SELECT * FROM students JOIN names USING (name);

select stud.name as surname, stud.age as old from students as stud;

ALTER TABLE names RENAME TO names2;

ALTER TABLE names2 RENAME COLUMN name TO rname;

SQLite

SQLite — это, пожалуй, самая распространённая СУБД — система управления базами данных. Коротко говоря, SQLite — это одна из программ, которая позволяет работать с базой данных и делать всё, описанное выше. Она очень компактна, быстра, и встроена почти всюду: в браузеры, телефоны, языки программирования и т.п. Её код передан в общественное достояние, она — одно из наиболее протестированного и надёжного ПО в мире.

Для экспериментов со своими данными удобнее всего установить sqlitebrowser. В питоне работа с SQLite находится в модуле sqlite3. Документация о всех командах, которые «понимает» SQLite на sqlite.org.

Запросы данных, ввод-вывод

Во всех задачах на подготовку запросов даётся база данных в db-файле (который при желании можно скачать). В каждой задаче нужно подготовить SQL-запрос, который решает поставленную задачу. И текст самого запроса необходимо сдать в проверяющую систему. Если запросов несколько, то они должны быть отделены точкой с запятой. Готовить запросы удобно во встроенной в эту страницу систему. (Только не пытайте использовать Internet Explorer, в нём работать не будет).

База «Студенты»

В первой части листка все забросы касаются базы «Школьники», в которой ровно одна таблица students:

При необходимости скачать базу можно по ссылке. Первые 5 её строк выглядят так:

Синтаксис SQL и syntax diagrams

Синтакс языка SQL удобно изображать при помощи диаграмм такого вида (они называются railroad diagrams):

Чтобы получить валидный запрос, нужно пройти от начала до конца любым способом. Более того, можно сделать такую схему, что только те запросы, которые получаются таким образом, будут валидными. Их можно найти на sqlite.org/syntaxdiagrams.html. Схема выше — упрощённая схема select-запроса (запрос данных).

Упражнение. Для каждого из запросов ниже пройдите по схеме и разберитесь, как это работает.

• select name
  from students
  where surname = 'Шашков'
  

• values ('Вася', 1), ('Коля', 2)

• select distinct class,
  case when supervisor = 'Шашков' then true else false end as godmode
  from students
  order by class

• select class, max(height)
  from students
  group by class having count(*) > 10
  order by 2
  limit 10

Запросы на выборку данных из одной таблицы

Даты и времена в sqlite

sqlite любит даты в формате YYYY-MM-DD, время в формате HH:MM:SS и timestamp'ы в формате YYYY-MM-DD HH:MM:SS. (Ну, это если упростить. Вообще смотрите документацию) Впрочем, сам sqlite хранит даты и времена как строки и не валидирует, что туда сохраняют. Чтобы дату, время или timestamp создать из строки в правильном формате, нужно применить функцию date, time или timestamp соответственно. Кстати, текущее время — это datetime('now')

Чтобы извлечь из даты или времени какую-то часть, удобнее всего использовать функцию strftime, которую мы уже видели в листке про даты. Вот примеры её вызова (учтите, что она возвращает именно строку)):

VALUES (  strftime('%s','2004-01-01 02:34:56')         )
VALUES (  strftime('%Y-%m-%d','2004-01-01 02:34:56')   )
VALUES (  strftime(some_format, some_datetime_field)   )

Работаем со строками

Лайкаем строки: поиск по шаблону

Если нужно проверить строку на равенстно, то мы используем... равенство. Если нужно проверить строку на принадлежность списку, то мы так и пишем var in ('str1', 'str2', 'etc'). Но иногда нужно проверить, что строка удовлетворяет какому-нибудь шаблону. Для этого используется ключевое слово LIKE:

select * from t where   col LIKE 'some%likes __ hot'

_ — это один любой символ, % — любая последовательность символов. Если вдруг вам нужно использовать процент или подчёркивание как сами символы, то нужно объявить экранирующий символ и их экранировать:

select * from t where   col LIKE '% \% _ \_' ESCAPE '\'

Склейка строк и приведение типов

В отличие от питона в sql'е строки склеиваются при помощи оператора ||. Любители использовать этот оператор для «или» страдают. Чтобы сделать из чего-угодно строку, нужно писать CAST(strange AS TEXT). Кстати, преобразования типов и других сортов устроены точно так же.

Полезные строковые функции

Кроме этого есть ещё пачка функций для работы со строками: instr, length, lower, ltrim, replace, rtrim, substr, trim, upper. Из неочевидного по имени: функция instr находит индекс первого вхождения второй строки-параметра внутри первой, если считать индексы с 1. И 0, если не нашлось. А ещё функции upper и lower работают только с латиницей.

Группировка и агрегирующие функции

Агрегирование

Часто бывает такое, что вместо самих данных нужны какие-нибудь их агрегаты. Например, количество, сумма, минимум, максимум или среднее значение. Это позволяют сделать функции avg, count, group_concat, max, min, sum. Вот документация по всем агрегирующим функциям. Использовать их очень просто:

select count(*), sum(age), min(avg_score), count(distinct classroom),
group_concat(distinct name)  -- Прикиньте, все уникальные имена склеит!
from students

Группировка

А что если такую штуку нужно выполнить, скажем, для каждого класса? 30 запросов выполнять? Вот чтобы ответ на этот вопрос был «нет» существует ещё и группировка. Если забить на занудство и порядок столбцов, то синтаксис такой:

select field1, field2, sum(field3), avg(field4) from table
where field5 between 1 and 5
group by field1, field2  -- В sqlite можно писать и короче: group by 1, 2

В результате этого запроса суммирование будет производиться только по записям с данными значениями первых двух полей. Обратите внимание: сначала идёт отбор, затем группировка.

Последующий отбор

Отбор при помощи WHERE производится до группировки. Если нужно выбросить лишние записи после группировки, то это делается при помощи ключевого слова HAVING. Получается что-то в духе

select country, sum(money) from cities
group by country
having count(*) > 10 and sum(money) > 1000000000000

Подзапросы

Хитрые where

Иногда нужно отобрать какие-нибудь особенно интересные записи. Но чтобы оценить интересность, нужно выполнить ещё один запрос. Так вот, это можно делать:

select * from table

-- поле равно таблице с 1 строкой и 1 столбцом
where fld = (select max(fld) from table)

-- поле лежит в таблице с 1 столбцом
or fld in (select 'foo' || id from table where some=other)

-- несколько полей равны таблице с 1 строкой и соответствующим числом столбцов
or (fld1, fld2) = (select min(fld1), max(fld2) from table limit 1)

-- строка из нескольких полей лежит в таблице с соответствующим числом столбцов
or (fld1, fld2) in (select fld1 * fld1, fld1 + fld2 from table)

В поздапросе можно использовать имена столбцов из основного запроса. Но если имена столбцов совпадают, то нужно указывать, о какой таблице идёт речь в формате таблица.поле:

SELECT name, result FROM students
WHERE  result = (SELECT Max(result) FROM results
                 WHERE students.name = results.name)  -- вот здесь разные поля с одним именем

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

select name, result from students as main  -- Можно использовать любое имя или не добавлять вовсе
where result = (select max(result) from students as sub
                where sub.name = main.name)  --  <-- Вот здесь одинаковые имена стали разными

Таблица как поле

А ещё если результат подзапроса — таблица 1 × 1, то её можно использовать в любом месте на равне с именами полей и прочими выражениями:

select col, (select foo from boo limit 1) from table
where (select zoo from moo where doo = col) = mol
order by (select goo from boo limit 1)

Каскады

Ещё один частый сценарий использования подзапросов — это последовательная обработка и агрегирование:

SELECT supervisor, Avg(cnt)
FROM   (SELECT class, supervisor, Count(*) AS cnt
        FROM   students
        GROUP  BY class, supervisor)
GROUP  BY supervisor

Обобщенные табличные выражения (CTE) (with ... as () ...)

Оконные функции

База «Расписание»

Во второй части листка все запросы касаются базы «Расписание», состоящей из нескольких таблиц.