DataModels-Databases.md

Оглавление

• Общие понятия баз данных
• Реляционная модель данных
• Масштабирование баз данных
• Паттерны баз данных
• Движки баз данных

Общие понятия баз данных

• О базе данных
• Нормализация и денормализация базы данных
• Транзакция
• Индекс базы данных
• Курсор

О базе данных

Базой данных (англ. database), БД (англ. DB) называют организованную структуру, которая предназначена для хранения, чтения и изменения данных.

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

Нормализация и денормализация базы данных

• О нормальной форме и нормализации
• О денормализации

Транзакция

• О транзакции
• Свойства транзакции (ACID)
• Пример транзакции

О транзакции

Транзакция (англ. transaction) — это логическая единица (logical unit), которая осуществляет доступ к базе данных и, возможно, изменяет данные в ней.

Транзакции работают с данными, используя операции чтения и записи.

Свойства транзакции (ACID)

• Атомарность (англ. Atomicity) гарантирует, что транзакция не может быть зафиксирована частично: либо выполняются все подоперации транзакции, либо ни одна. Если какая-то операция из последовательности не проходит, то происходит откат (rollback) всей последовательности.
• Согласованность, консистентность (англ. Consistency). Каждая успешная транзакция фиксирует только допустимый для системы результат. База данных должна быть согласованна до и после транзакции, во время проведения транзакции согласованность не требуется.
• Изолированность (англ. Isolation). Во время выполнения транзакции другие параллельные транзакции не должны оказывать влияния на её результат. Требование дорогое, поэтому в реальных базах транзакции изолируются не полностью: создаются уровни изолированности.
• Долговечность (англ. Durability). Если пользователь получил подтверждение от системы, что транзакция выполнена, он может быть уверен, что сделанные им изменения не будут отменены из-за какого-либо сбоя. Изменения, сделанные успешно завершённой транзакцией, должны остаться сохранёнными после возвращения системы в работу.

Пример транзакции

Пусть деньги переводятся с одного счёта на другой. Используются две основные операции: вывод денег с одного счёта 1000$ - 100$ = 400$, зачисление их на другой счёт 500$ + 100$ = 600$. Если первая операция удалась, а вторая нет, то происходит откат, поскольку в противном случае имеем несогласованность (inconsistency) данных до и после транзакции: до транзакции на счетах в сумме было 1500$, после — 1400$.

Индекс базы данных

• Об индексе базы данных
• Проблема дублирования данных

Об индексе базы данных

Индекс базы данных (англ. database index) — это структура данных, ускоряющая операции поиска (англ. speed up querying) в заданной таблице (или коллекции) базы данных за счёт хранения дополнительной информации в базе (говоря простыми словами, тех же данных таблицы, но в другом виде, в упорядоченном).

По умолчанию записи в таблице (коллекции) могут храниться произвольно (неупорядоченно). И если таблица довольно большая, то последовательный просмотр всех записей может занимать довольно продолжительное время. Индексы приводят данные в такой вид (упорядочивают их), чтобы это ускорило поиск. Например, структура индекста может быть представлена сбалансированным деревом поиска, и тогда скорость поиска будет логарифмичной O(log n) вместо линейной O(n).

Индекс формируется из значений одного или нескольких столбцов таблицы (полей документов коллекции) и указателя на соответствующие строки таблицы (документы коллекции). Также иногда индексы могут создаваться из выражений.

Таким образом, если вы создаёте индекс по какому-то столбцу таблицы, скажем, по имени пользователя, вы можете быстрее найти (получить) данные пользователей из таблицы по заданному имени (выигрываете в скорости, во времени), но нужно учитывать, что индекс подразумевает дублирование некоторых данных (проигрываете в памяти).

Проблема дублирования данных

Важно быть аккуратными с индексами, потому что за любым изменением в таблице (коллекции) должно последовать обновление индекса. Когда данных очень много, это может повлечь за собой очень трудоёмкие вычисления и большую нагрузку на сервер соответственно.

Более того, индексы занимают дополнительное место, поэтому не стоит их создавать (хранить) без необходимости.

Курсор

• О курсоре
• Пример курсора в MongoDB
• Пример курсора в SQL

О курсоре

Курсор (англ. cursor) — управляющая структура, которая производит обход записей (англ. traversal) в базе данных.

Принцип работы с курсором похож на работу с итератором (англ. iterator), поскольку курсор позволяет последовательно обработать каждую строку (каждый документ) из выбранного набора строк (документов).

Курсор также можно рассматривать как указатель (pointer) на одну строку таблицы (на один документ). Курсор может ссылаться только на одну строку (один документ) в один момент времени, но может перемещаться к другим строкам при необходимости.

Курсоры подразделяются на явные и неявные.

Явный курсор создаётся разработчиком вручную, неявный курсор создаётся системой автоматически.

Пример курсора в MongoDB

const usersCursor = db.users.find({ role: 'admin' });
/* последовательный перебор всех документов результирующего набора в цикле while */
while (usersCursor.hasNext()) {
   const user = usersCursor.next();
   console.log(user);
}

Пример курсора в SQL

# объявление временных переменных, которые будут использованы для записи данных курсора
DECLARE @id VARCHAR(50);
DECLARE @role VARCHAR(50);
# объявление явного курсора, который будет брать данные столбцов id, role из таблицы users
DECLARE @users_cursor CURSOR FOR
  SELECT id, role
  FROM users
# открытие курсор (наполнение его данными)
OPEN @users_cursor
# последовательное извлечение строк из результирующего набора в цикле WHILTE,
# запись значений в переменные и вывод этих переменных 
WHILE @@FETCH_STATUS = 0
BEGIN
  FETCH NEXT FROM @users_cursor INTO @id, @role
  PRINT @id + ' ' + @role
END
# после извлечения всех строк следует закрыть курсор и освободить занимаемые им ресурсы
CLOSE @users_cursor
# иногда нужно вручную освобождать память курсора (зависит от реализации SQL)
DEALLOCATE @users_cursor

Возможные варианты перемещений с FETCH по результирующему набору строк.

• FIRST — первая строка .
• NEXT — следующая строка после текущей.
• PRIOR — строка, находящаяся перед текущей.
• LAST — последняя строка.
• ABSOLUTE int — строка по её абсолютному порядковому номеру int при отсчёте с начала (конца), если перед int знак + (-). Если указать 0, то ничего не вернётся.
• RELATIVE int — перемещение на int строк вперёд (назад) от текущей, если перед int знак + (-). Если указать 0, то вернётся текущая строка.

Изменение данных таблицы при помощи курсора и CURRENT. Курсор должен быть открыт для операции.

UPDATE new_users
SET ...
WHERE CURRENT OF @sers_cursor

Аналогично можно делать с DELETE.

Масштабирование баз данных

• Репликация
• Шардинг
• Партиционирование

Репликация

Репликация (англ. replication) — это постоянное синхронное или асинхронное копирование (реплицирование) данных между несколькими серверами.

Сервер, копирующий данные другого сервера, называют репликой (replica).

Асинхронное копирование подразумевает, что копирование данных на другие сервера может происходить с некоторой задержкой.

Когда появляется несколько серверов, нужно выбрать основной, ведущий сервер — мастер (Master). Он будет отвечать за все изменения данных (запись).

Остальные сервера называют слейвами (Slaves). Они постоянно копируют данные с мастера и предоставляют их для чтения. Мастер тоже доступен для чтения данных.

В больших системах может быть несколько мастеров, но обычно достаточно одного мастера и нескольких слейвов.

О выходе из строя

Если слейв выходит из строя, нагрузка распределяется между мастером и оставшимися слейвами. Нерабочий слейв восстанавливается и снова подключается.

Если мастер выходит из строя, слейв становится новым мастером. Если старый мастер восстанавливается, он становится новым слейвом.

Не рекомендуется использовать систему, где есть несколько мастеров и отсутствуют слейвы, так как она гарантированно теряет некоторую часть данных при выходе из строя: каждый мастер отвечает за изменение данных и нет слейвов, хранящих резервные копии этих данных.

Для чего нужна репликация

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

Можно организовать систему таким образом, чтобы каждый слейв отвечал за конкретный тип задач. Тогда перегрузка приложения определённым типом задач перегрузит только одного слейва — другие функции приложения не будут затронуты.

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

Шардинг

Шардинг (англ. sharding) — приём масштабирования, который позволяет распределять данные между разными физическими серверами. Процесс шардинга предполагает разнесения данных между отдельными шардами на основе некого ключа шардинга. Связанные одинаковым значением ключа шардинга сущности группируются в набор данных по заданному ключу, а этот набор хранится в пределах одного физического шарда. Это существенно облегчает обработку данных.

Например, в системах типа социальных сетей ключом для шардинга может быть ID пользователя, таким образом все данные пользователя будут храниться и обрабатываться на одном сервере, а не собираться по частям с нескольких.

Партиционирование

Партиционирование (англ. partitioning) — разбиение таблиц, содержащих большое количество записей, на логические части по некоторым выбранным критериям.

Партиционирование таблиц делит весь объем операций по обработке данных на несколько независимых и параллельно выполняющихся потоков, что существенно ускоряет работу СУБД.

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

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

Реляционная модель данных

• О реляционной модели данных
• Коротко о главном из теории множеств
• Тип данных (домен)
• Отношение и его структура
• Свойства отношений
• Графическое представление отношения (таблица)
• Ключи
• Связи между отношениями
• Операции над отношениями (реляционные операции)
• Разновидности операций соединения
• Свойства операций над отношениями
• Функциональная зависимость
• Нормализация и нормальные формы

О реляционной модели данных

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

Коротко о главном из теории множеств

• Множество
• Кортеж
• Декартово произведение множеств
• Отношение в теории множеств
• Операция в теории множеств

Множество

Множество - это неупорядоченный набор уникальных объектов, обладающих схожими признаками. Эти объекты называются элементами множества.

Примеры множеств: множество женских имён: N = { Ася, Сара, Рози }, множество профессий: J = { дизайнер, программист }, множество дат: D = { 2019, 2020 }.

Неупорядоченность множества означает, что множества { 2019, 2020 } и { 2020, 2019 } считаются одинаковыми.

Уникальность элементов множества означает, что множество не может содержать двух и более одинаковых элементов. То есть набор { 3, 2, 2 } - не множество.

Кортеж

Кортежем длины n называют упорядоченный набор объектов (не обязательно уникальных) (x1, x2, ..., xn), где x1, x2, ..., xn принадлежат множествам X1, X2, ... Xn (не обязательно различным).

Примеры кортежей: кортеж из элементов множеств N, J, D соответственно: (Ася, дизайнер, 2019), координаты точки на плоскости: (1, 1), набор аргументов функции f(x1, x2, x3).

Упорядоченность кортежа означает, что кортежи (Рози, 2020) и (2020, Рози) считаются различными. Соблюдение порядка элементов кортежа так же важно, как соблюдение порядка букв в словах и цифр в числах.

Кортеж длины 2 также называют упорядоченной парой, кортеж длины 3 - упорядоченной тройкой.

Декартово произведение множеств

Декартово произведение множеств X1, X2, ..., Xn - это операция над множествами X1, X2, ..., Xn (не обязательно различными), результатом которой является множество всевозможных кортежей (x1, x2, ..., xn), где элементы x1, x2, ..., xn принадлежат множествам X1, X2, ..., Xn соответственно. Обозначение: X1 × X2 × ... × Xn.

Например, декартово произведение N × D = { (Ася, 2019), (Ася, 2020), (Сара, 2019), (Сара, 2020), (Рози, 2019), (Рози, 2020) }, а декартово произведение N × J × D состоит из 3 • 2 • 2 = 12 кортежей. по типу (Ася, дизайнер, 2019).

Отношение в теории множеств

n-арным отношением R между множествами X1, X2, ..., Xn называют подмножество декартового произведения X1 × X2 × ... × Xn, то есть множество, содержащее некоторые элементы (кортежи) множества X1 × X2 × ... × Xn. Число n - арность отношения.

Например, множество { (Сара, 2019), (Рози, 2020) } является бинарным отношением между множествами N и D.

Отношения могут обладать некоторыми свойствамии наделять ими свои элементы.

Примеры известных отношений: меньше (x < y), больше (x > y), равно (x = y), перпендикулярность, параллельность (x || y), x - отец y и так далее.

Операция в теории множеств

Пусть имеются множества X и Y, причём множество X является подмножеством декартова произведения n непустых множеств: X = X1 × X2 × … × Xn. Тогда n-арная операцией называется бинарное отношение f ⊆ X × Y, такое, что каждому значению x ∈ X соответствует единственное значение y ∈ Y. Здесь элемент x представляет собой кортеж (x1, x2, …, xn).

Элементы x1, x2, …, xn называют операндами, а элемент y - результатом операции f.

Общее обозначение n-арной операции f: f(x1, x2, ..., xn) = y.

Операция с одним операндом называется унарной операцией, с двумя - бинарной.

Операции обычно имеют своё уникальное символьное обозначение.

Самыми широко используемыми операциями являются арифметические операции. Например, бинарная операция “сложение” (x1 + x2 = y), бинарная операция “возведение в степень” (x1 ^ x2 = y), унарная операция “факториал” (x! = y) и так далее.

Тип данных (домен)

Тип данных - это множество допустимых значений. Любое значение (переменной, константы, параметра, атрибута и так далее) принадлежит какому-то типу данных.

В реляционной модели данных тип данных также называют доменом.

Вообще говоря, основными типами данных в программировании являются числовой (7, 3.14), строковый ("развитие", 'enginer') и логический (истина, ложь).

На практике же часто выделяют больше типов, чтобы сузить область допустимых значений и, таким образом, больше ограничить пользователя. Например, числа подразделяют на целые (integer) и дробные (float).

Если мы указываем, что значение принадлежит какому-то типу то другому типу оно уже приналежать не может.

Типы, предопределённые в системе, называют базовыми типами. Многие системы позволяют пользователю на основе базовых типов создавать новые типы, называемые в таком случае пользовательскими типами.

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

Отношение и его структура

• Об отношении и его структуре
• Атрибуты и их значения
• Заголовок отношения
• Тело отношения

Об отношении и его структуре

Понятие отношения в реляционной модели данных довольно близко по смыслу к понятию отношения в теории множеств. При этом множествами X1, X2, ..., Xn выступают типы данных T1, T2, ..., Tn, являющиеся множествами по определению.

Ниже рассмотрим несколько видоизменённое математическое определение.

Пусть имеются типы данных T1, T2, ..., Tn (не обязательно различные), тогда n-арным отношением (англ. relation) R называют подмножество декартового произведения T1 × T2 × ... × Tn. Говоря другими словами, отношение - это некоторое множество (набор) кортежей, имеющих одинаковую схему, то есть кортежей (t1, t2, ..., tn), элементы t1, t2, ..., tn которых принадлежат типам данных T1, T2, ..., Tn соответственно.

На деле же отношение реляционной модели данных имеет особую структуру и не является множеством как таковым. Отношение R состоит из заголовка H и тела B. Фактически, его можно рассматривать как упорядоченную пару заголовка и тела: R = (H, B).

Атрибуты и их значения

Атрибут (лат. attributio - признак) в философии - отличительный, существенный, неотъемлемый признак (черта, свойство) предмета или явления. Атрибуты независимы друг от друга, то есть один атрибут не может повлиять на другой.

В программировании атрибут (англ. attribute) представляет собой свойство некоторого объекта, элемента или файла.

Объект характеризуется и определяется значениями своих атрибутов.

Атрибут объекта обычно состоит из имени атрибута (name) и значения атрибута (value).

Например, “цвет глаз” можно назвать атрибутом человека, тогда “карий”, “зелёный”, “голубой” и “серый” - некоторые из возможных значений атрибута.

В реляционной модели данных некоторый класс объектов представляется отношением и характеризуется конечным множеством атрибутов, а информация (данные) о конкретном объекте хранится в виде набора значений атрибутов. В этом и кроется главное различие между отношением (из реляционной модели данных) и множеством (из теории множеств): множество обычно представляет собой набор наименований объектов в то время, как отношение представляет множество характеристик объектов.

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

Фактически, атрибут в реляционной модели данных можно рассматривать как упорядоченную пару (a, t), где a - название атрибута, t - название типа данных, которому принадлежат значения атрибута. В таком случае значение атрибута можно рассматривать как упорядоченную тройку (a, t, v), где v - значение атрибута a типа t.

Заголовок отношения

Говоря простыми словами, заголовок отношения состоит из атрибутов.

Заголовком (схемой) H (англ. header) отношения R называют множество упорядоченных пар (a, t), где a (англ. attribute) - название атрибута, t (англ. type) - название типа данных (не сам тип данных, являющийся множеством), которому принадлежат значения атрибута a.

Таким образом, заголовок n-арного отношения имеет вид: H = { (a1, t2), (a2, t3), ..., (an, tn) }.

Пример заголовка для отношения между множествами N, J, D: H = { (Имя, string), (Профессия, string), (Дата, date) }.

Число атрибутов n называется степенью отношения или арностью отношения.

Отношение с одним атрибутом называют унарным, с двумя — бинарным, с тремя - тернарным и так далее.

Поскольку множество не может содержать одинаковые элементы, а типы данных в заголовке могут повторяться, названия атрибутов должны быть уникальными. Иначе возможна была бы ситуация H = { (Дата, date), (Дата, date) }, что недопустимо для множеств.

Заголовки двух отношений совпадают, если совпадают их количество атрибутов, все названия атрибутов и типы данных атрибутов.

Тело отношения

Говоря простыми словами, тело отношения - это множество кортежей, содержащих значения атрибутов.

Итак, заголовок представляет собой множество атрибутов (a, t): H = { (a1, t1), (a2, t2), ..., (an, tn) }.

Значение атрибута должно быть привязано к самому атрибуту, поэтому оно представляется упорядоченной парой ((a, t), v) или, что то же самое, упорядоченной тройкой (a, t, v), где v (англ. value) - значение атрибута a типа t. Но, поскольку название атрибута уникально, а тип данных привязан к нему парой в заголовке отношения, значение атрибута можно представить ещё проще - упорядоченной двойкой (a, v).

Пусть имеется n атрибутов a1, a2, ..., an. Тогда тело B (англ. body) отношения R - это множество кортежей k = ((a1, v1), (a2, v2), ..., (an, vn)): B = { k1, k1, ..., km }.

Количество упорядоченных пар (a, v) в кортеже k должно совпадать с количеством атрибутов (степенью отношения) n.

Число m (число кортежей k) называется кардинальным числом отношения или кардинальностью отношения.

Стоит отметить, что, несмотря на математическое определение кортежа и начальное определение автора, кортеж k не обязательно должен быть упорядочен. Действительно, значения напрямую привязаны к своим атрибутам упорядоченными парами и в случае перестановки ((a2, v2), (a1, v1)) эта связь не нарушается. Более того, сами атрибуты в заголовке не упорядочены по определению множества, а значит упорядоченность значений избыточна. Упорядоченность имела бы смысл, если бы кортежи k имели вид: (v1, v2, ..., vn). Далее при необходимости в упорядоченности, чтобы не путать упорядоченные математические кортежи и неупорядоченные кортежи k, будем использовать понятия “упорядоченный набор”, “упорядоченная пара” и “упорядоченная тройка”.

Пусть имеется заголовок H вида:

H = { (Имя, string), (Профессия, string), (Дата, date) }

Ниже представлен пример тела B, соответствующего заголовку H:

B = {
  ((Имя, Сара), (Профессия, программист), (Дата, 2019)),
  ((Имя, Рози), (Профессия, дизайнер), (Дата, 2019)),
}

Графически, упорядоченная пара (a, v) - одна ячейка таблицы, а кортеж k - строка таблицы.

Свойства отношений

Свойства отношения опираются на его структуру.

Поскольку заголовок H и тело B отношения R являются множествами, их свойства вытекают из свойств множеств:

1. Тело отношения B не может содержать двух и более одинаковых кортежей.
2. Порядок следования атрибутов в заголовке H отношения не имеет значения.
3. Порядок следования кортежей в теле B отношения не имеет значения.

Графическое представление отношения (таблица)

• Понятие таблицы
• Сравнение понятий отношения и таблицы

Понятие таблицы

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

Отношение R из последнего примера выше можно представить таблицей следующего вида:

Отношение R

Имя	Профессия	Дата
Ася	дизайнер	2019
Сара	программист	2020

Сравнение понятий отношения и таблицы

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

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

Для равнозначности понятий таблицы и отношения на понятие таблицы необходимо накладывать некоторые ограничения:

1. Все свойства отношений должны быть верны для строк и столбцов таблицы.
2. Таблица не должна содержать дополнительных возможностей, выходящих за рамки понятия отношения. (например, скрытые поля с порядком строк и скрытые методы их сортировки, встроенные в строки даты и так далее).

Ключи

• Об идентификации
• Потенциальный ключ
• Первичный ключ
• Простые и составные ключи
• Значение ключа
• Естественный ключ
• Суррогатный ключ
• Внешний ключ

Об идентификации

Идентификатор, ID (англ. identifier — опознаватель) — это уникальный признак объекта.

Идентификаторы позволяют идентифицировать объект, то есть выделить (найти) его среди других объектов.

Например, можно по номеру паспорта определить (идентифицировать) человека, по IP-адресу - физический компьютер, по координатам - точку на карте, по шрих-коду - товар в магазине, по QR-коду - ссылку, по ссылке - сайт и так далее.

Для идентификации кортежей отношения используются ключи.

Потенциальный ключ

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

Пусть имеется отношение R, содержащее в заголовке n атрибутов.

Потенциальным ключом (англ. candidate key) называют подмножество из m <= n атрибутов отношения R, которое удовлетворяет условиям уникальности и минимальности.

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

Важно отметить, что R именно “не может содержать двух кортежей”, а не “не содержит двух кортежей”. Например, если в компании работает несколько сотрудников и все имеют различный цвет глаз, это не означает, что цвет глаз является уникальным идентификатором: всегда может появиться новый сотрудник с уже существующим цветом глаз и идентификация станет невозможной.

Таким образом, уникальность опирается не на наличие объекта в текущий момент времени, а на особенности (природу) класса объектов, которые допускают возможность появления нового объекта в любой момент времени. Неплохими идентификаторами сотрудника компании могут стать: серия и номер паспорта, номер трудовой книги, рабочий email или номер телефона (все они не могут повториться у двух сотрудников).

Условие минимальности (несократимости) требует, чтобы среди атрибутов потенциального ключа отсутствало меньшее подмножество из k <= m атрибутов, которое удовлетворяет условию уникальности.

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

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

В отношении может одновременно существовать несколько потенциальных ключей.

На примере ниже представлено отношение с двумя потенциальным ключами, каждый из которых состоит из одного элемента: { Номер телефона } и { Email }.

Отношение R (пользователи)

Имя	Фамилия	Номер телефона	Email
Джон	Дрим	8768	johndream@example
Фрэнк	Старк	1442	frankstark@example
Ален	Стоун	3567	alenstone@example

Первичный ключ

Как уже отмечалось ранее, отношение может содержать несколько потенциальных ключей, по каждому из которых можно идентифицировать объект. Один из этих ключей выбирается в качестве основного и называется первичным ключом (англ. primary key) отношения, оставшиеся потенциальные ключи называют альтернативными ключами отношения.

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

Если в отношении содержится несколько потенциальных ключей, то имеется два основных критерия выбора первичного ключа:

1. Удобство использования. Чаще всего выбирается потенциальный ключ с наименьшим физическим размером (занимает меньше памяти на компьютере) или содержит наменьшее количество атрибутов.
2. Сохранение уникальности с течением времени. Некоторые идентификаторы могут утрачивать свою уникальность со временем.

Простые и составные ключи

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

Чаще всего используются простые ключи (id, number, username, email, phone), поскольку их проще хранить, с ними проще работать.

Редко, но бывают случаи, когда удобнее использовать составной ключ или нет возможности использовать простой ключ.

Рассмотрим пример составного ключа, разбив телефонный номер на группы. В системе, работающей с телефонными номерами, разбиение номера могло бы оптимизировать поиск и фильтрацию. Из чего состоит телефонный номер? Его схема различна в разных странах. Например, американский номер состоит из кода страны, кода региона, кода телефонного узла и абонентского номера: +1 (234) 235 1779.

Отношение R

Код региона	Код узла	Абонентский номер	Фамилия владельца
234	145	1984	Ирвинг
234	310	7817	Купер
235	420	6168	Редли

Тогда первичный ключ PK отношения R имеет вид:

{
  (Код региона, integer),
  (Код узла, integer),
  (Абонентский номер, integer)
}

Исключение любых атрибутов из ключа PK приведёт к утрате уникальности этого ключа.

Другие примеры составных ключей: серия и номер паспорта (не уникальны по-отдельности), масть и число на игровой карте, номер ряда и номер места в кинотеатре, составные части URL, составные части адреса электронной почты и так далее.

Значение ключа

Значением ключа называют кортеж, состоящий из значений атрибутов этого ключа.

Отношение R (места в кинозале)

Номер ряда	Номер места	Место для влюблённых	VIP
7	18	true	false
7	19	true	false
3	22	false	false
10	3	false	true

Тогда первичный ключ PK отношения R имеет вид:

{
  (Номер ряда, integer),
  (Номер места, integer)
}

Кортеж ((Номер ряда, 7), (Номер места, 18)) - одно из доступных значений ключа PK.

Естественный ключ

Разделим понятия реального объекта (дом, машина, человек, дерево) и его физического представления в некоторой базе данных (например, набор значений атрибутов).

Естественный ключ (англ. natural key, business key, domain key) - это уникальный ключ, который идентифицирует некоторый реальный объект, при этом полностью зависит от свойств (природы) этого объекта и не зависит от его физического представления (реализации) в конкретной базе данных.

Естественный ключ подбирается на основе реальных наблюдений за объектом, поэтому его уникальность опирается исключительно на уникальные черты реального объекта.

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

Как и в случае с потенциальным ключами, естественных ключей у отношения может быть несколько.

Примеры естественных ключей всё те же, что и примеры потенциальных ключей: человека можно идентифицировать по серии и номеру паспорта, пользователя - по email, дом - по адресу и так далее. Всё это - натуральные ключи, взятые из предметных областей (доменов) соответствующих объектов.

Естественные ключи являются полноценной частью приложения и не скрываются от глаз пользователя (например, на сайтах можно часто видеть email или номер телефона).

Суррогатный ключ

Суррогатный ключ (англ. surrogate key, pseudokey, synthetic key) - это уникальный идентификатор как для реального объекта, так и для его физического представления в базе данных.

В отличии от естественного ключа, суррогатный ключ никак не зависит от свойств реального объекта, а следовательно и от атрибутов. Суррогатный ключ генерируется системой по заданному алгоритму, поэтому не имеет смысла вне системы.

Чаще всего суррогатный ключ представляет собой некоторый хэш (произвольно сгенерированная строка) или целочисленное число.

Самые распространённые способы генерации суррогатного ключа:

1. Universally Unique Identifier (UUID). Пример: 9fc2e9ad-fae7-4f25-ae48-3f45284f2299.
2. Globally Unique Identifier (GUID). Пример: 75f067fa-b95f-405c-a1bd-29164461a65f.
3. Object Identifier (ObjectID). Пример: ObjectId("507f1f77bcf86cd899439017").
4. AUTO_INCREMENT (MySQL), AUTOINCREMENT (SQLite) SEQUENCE (SQL Server, Oracle).

Суррогатные ключи относятся к внутренней логике (внутренней реализации) приложения. Они не несут в себе никакой полезной информации для пользователя и поэтому скрыты от его глаз.

У отношения может быть несколько суррогатных ключей.

Преимущества использования суррогатных ключей:

1. Неизменность (стабильность). Благодаря независимости суррогатного ключа от атрибутов объекта, ключ остаётся неизменным при изменении этого объекта.
2. Компактность. Суррогатный ключ всегда состоит только из одного значения, размер которого фиксирован и обычно невелик (размер ключа зависит от алгоритма генерации, который можно выбирать), что уменьшает расход памяти и увеличивает скорость поиска объектов по ключу.
3. Единообразие. Если все ключи в системе создаются по одному алгоритму (например, везде используется UUID), то логика обработки данных упрощается и становится предсказуемой для разработчика в любом месте системы.
4. Уникальность ключа во всей системе - не только в отдельном отношении.

Основным недостатком суррогатного ключа является то, что он не связан с самим объектом по смыслу: по такому ключу нельзя судить как о содержимом объекта, так и о классе, которому этот объект принадлежит.

Внешний ключ

Внешние ключи подобны ссылкам на объекты. Внешний ключ позволяет в кортеже одного отношения сослаться на кортеж другого отношения, поскольку хранит значение потенциального ключа этого отношения.

Использование внешних ключей лишает нас необходимости в дублировании данных. На эти данные можно просто сослаться из другого места. Такой подход

Пусть имеются отношения R и S (не обязательно различные). Внешним ключом (англ. foreign key) FK называют такое подмножество атрибутов отношения S, для которого выполняются условия:

1. Отношение R имеет такой потенциальный ключ CK, что у ключей CK и FK совпадают количество атрибутов и их типы данных (при переименовании атрибутов ключи совпадают).
2. Каждое значение внешнего ключа FK в некотором кортеже отношения S совпадает со значением потенциального включа CK в некотором кортеже отношения R. Иначе говоря, множество значений ключа FK содержится (является подмножеством) в множестве значений ключа CK.

Обозначение внешнего ключа FK, ссылающегося на потенциальный ключ CK: FK → CK.

Отношение R, содержащее потенциальный ключ CK, называют главным (родительским) отношением, отношение S, содержащее внешний ключ FK, называют подчинённым (дочерним) отношением.

Ниже представлен пример простенькой реализации чата. Родительское отношение R имеет потенциальный ключ ID, дочернее отношение S имеет два внешних ключа: SENDER_ID → ID (идентификатор отправителя) и RECIPIENT_ID → ID (идентификатор получателя).

Отношение R (пользователи)

ID	Имя пользователя
cde	Сара
fkh	Рози

Отношение S (сообщения)

ID	Текст	SENDER_ID	RECIPIENT_ID
erksh	Доброй ночи	cde	fkh
jhtbe	И тебе	fkh	cde

Связи между отношениями

• О связях между отношениями
• Один к одному (1:1)
• Один ко многим (1:M)
• Многие к одному (M:1)
• Многие ко многим (M:M)
• Ссылочная целостность

О связях между отношениями

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

Связи между двумя отношениями устанавливаеются при помощи внешних ключей.

Как уже ранее отмечалось, отношение, содержащее внешний ключ FK → CK, называют дочерним, а отношение, содержащее потенциальный ключ CK, называют родительским.

Между родительским и дочерним отношениями существует 4 вида связей:

• Один к одному (1:1)
• Один ко многим (1:M)
• Многие к одному (M:1)
• Многие ко многим (M:M)

Один к одному (1:1)

Один к одному 1:1 (англ. one-to-one) - такая связь между отношениями R и S, при которой каждому кортежу отношения R соответствует только один (или ни одного) кортеж отношения S и каждому кортежу отношения S соответствует только один (или ни одного) кортеж отношения R. Другими словами, отношение R имеет потенциальный ключ R.CK и внешний ключ R.FK → S.CK, а отношение S имеет потенциальный ключ S.CK и внешний ключ S.FK → R.CK.

Пример связи 1:1: одно королевство - один король (королева).

Отношение R, представленное таблицей ниже, содержит потенциальный ключ R.ID и внешний ключ R.KINGDOM_ID → S.ID, отношение S содержит потенциальный ключ S.ID и внешний ключ S.KING_ID → R.ID.

Отношение R (современные короли и королевы)

ID	Имя	KINGDOM_ID
val	Виллем-Александр	NL
el2	Елизавета II	GB
k16	Карл XVI Густав	SE
ma2	Маргрета II	DK
fil	Филипп	BE
fi6	Филипп VI	ES
ha5	Харальд V	NO

Отношение S (страны)

ID	Название	KING_ID
BE	Бельгия	fil
GB	Великобритания	el2
DK	Дания	ma2
ES	Испания	fi6
NL	Нидерланды	val
NO	Норвегия	ha5
SE	Швеция	k16

Один ко многим (1:M)

Один ко многим 1:M (англ. one-to-many) - такая связь между отношениями R и S, при которой каждому кортежу отношения R соответствует несколько (или ни одного) кортежей отношения S и каждому кортежу отношения S соответствует не более одного кортежа отношения R. Другими словами, отношение R имеет потенциальный ключ R.CK, а отношение S имеет внешний ключ S.FK → R.CK.

Рассмотрим интересный пример связи 1:M: один отец может иметь нескольких детей, но каждый ребёнок имеет лишь одного биологического отца.

Как уже ранее отмечалось, отношения R и S не обязательно различны (они могут представлять собой одно и то же отношение). Отношение R, представленное таблицей ниже, содержит потенциальный ключ R.ID и внешний ключ R.PARENT_ID → R.ID.

Отношение R (отцы и дети)

ID	Имя	Возраст	PARENT_ID
P1	Джон	65	NULL
P2	Джим	43	P1
P3	Джек	20	P2
P4	Джоан	22	P2

Многие к одному (M:1)

Многие к одному M:1 (англ. many-to-one) - зеркальное отражение связи 1:M (в определении достаточно поменять местами отношения R и S).

Пример связи M:1: много городов может принадлежать одной стране, но один город не может принадлежать двум странам одновременно.

Отношение R, представленное таблицей ниже, имеет потенциальный ключ R.ID и внешний ключ R.COUNTRY_ID → S.ID, а отношение S содержит только потенциальный ключ S.ID.

Отношение R (города)

ID	Имя	COUNTRY_ID
kiev	Киев	UA
lviv	Львов	UA
sydney	Сидней	AU

Отношение S (страны)

ID	Название
UA	Украина
AU	Австралия

Многие ко многим (M:M)

Многие ко многим M:M (англ. many-to-many) - такая связь между отношениями R и S, при которой каждому кортежу отношения R соответствует несколько (или ни одного) кортежей отношения S и каждому кортежу отношения S соответствует несколько (или ни одного) кортежей отношения R. С помощью двух отношений такую связь на практике реализовать нельзя.

Другими словами, отношение R имеет потенциальный ключ R.CK, отношение S имеет потенциальный ключ S.CK и существует такое отношение T, тело которого состоит из кортежей (T.FK1 → S.CK, T.FK2 → R.CK), содержащих внешние ключи, ссылающиеся на потенциальные ключи отношений R и S. Отношение T имеет связь M:1 (многие к одному) с каждым из отношений R и S.

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

Отношение R (разговорные языки)

ID	Язык
en	Анлийский
ru	Русский
fr	Французский

Отношение S (сотрудники)

ID	Имя	Должность
sara1	Сара	программист
dina7	Дина	дизайнер

Пусть Сара знает английский и французский, а Дина - английский и русский, тогда:

Отношение T (соответствие между языками и сотрудниками)

ID	WORKER_ID	LANGUAGE_ID
t1	sara1	en
t1	sara1	fr
t2	dina7	en
t2	dina7	ru

В таблице выше можно увидеть, что отношение T имеет внешний ключ T.LANGUAGE_ID → R.ID (связь M:1 между T и R) и внешний ключ T.WORKER_ID → S.ID (связь M:1 между T и S).

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

Ссылочная целостность

Первичные ключи могут изменяться. Простой пример: пользователь хочет сменить email или номер телефона. Если существует связь, использующая подобный потенциальный ключ CK, то ссылающейся на него внешний ключ FK → CK так же должен измениться.

Ссылочной целостностью (англ. referential integrity) называют корректность значений всех внешних ключей, то есть хранение актуального значения потенциального ключа CK в каждом внешнем ключе FK → CK.

Чтобы обеспечить ссылочную целостность, необходимо при изменении значения потенциального ключа CK заменить значения всех ссылающихся на него внешних ключей FK или отменить операцию изменения, если замена невозможна.

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

Операции над отношениями (реляционные операции)

• О реляционных операциях
• Ограничения на применение операций
• Объединение отношений
• Пересечение отношений
• Вычитание отношения
• Декартово произведение отношений
• Проекция отношения
• Выборка (ограничение)
• Соединение
• Деление отношений
• Переименование атрибутов отношения

О реляционных операциях

Большинство операций над отношениями являются бинарными, то есть такими, которые оперируют двумя отношениями. При необходимости произвести бинарную операцию над большим количеством отношений, её необходимо применить последовательно несколько раз: P • R • S • T = ((P • R) • S) • T.

Любая операция над отношениями, результатом которой является отношение, называется реляционной операцией.

Систему реляционных операций называют реляционной алгеброй.

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

Эдгар Кодд, создатель реляционной модели данных, ввёл следующий набор из 8 реляционных операций:

• Объединение отношений
• Пересечение отношений
• Вычитание отношения
• Декартово произведение отношений
• Проекция отношения
• Выборка (ограничение)
• Соединение
• Деление отношений

Операции объединения, пересечения, вычитания и декартова произведения относят к теоретико-множественным операциям: они являются аналогами одноимённых операций над множествами в теории множеств.

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

Операции объединения, вычитания, проекции, декартова произведения и выборки являются примитивными реляционными операциями — такими операциями, которые нельзя выразить друг через друга.

Далее в примерах отношения будут представляться таблицами для наглядности.

Ограничения на применение операций

Операции объединения, пересечения и вычитания требуют совпадения заголовков у своих отношений-операндов.

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

Объединение отношений

Объединения отношений R и S - бинарная операция, требующая совпадения заголовков отношений R и S, результатом которой является отношение с тем же заголовком и телом, содержащим все кортежи обоих отношений. Иначе говоря, каждый кортеж отношения-результата принадлежит или отношению R, или отношению S. Если отношения R и S имеют между собой совпадающие кортежи (пересечения), то в отношение-результат попадает только один из них.

Обозначение объединения отношений R и S: R UNION S.

Объединение отношений является аналогом объединения множеств из теории множеств.

Ниже представлен пример объединения отношений R и S.

Отношение R

Имя	Профессия	Дата
Ася	дизайнер	2019
Сара	программист	2020

Отношение S

Имя	Профессия	Дата
Рози	дизайнер	2020
Сара	программист	2020

Отношение R UNION S

Имя	Профессия	Дата
Ася	дизайнер	2019
Сара	программист	2020
Рози	дизайнер	2020

Пересечение отношений

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

Обозначение пересечения отношений R и S: R INTERSECT S.

Пересечение отношений является аналогом пересечения множеств из теории множеств.

Операция пересечения отношений не является примитивной, поскольку её можно выразить через операцию вычитания отношения: R INTERSECT S = R MINUS (R MINUS S).

Ниже представлен пример пересечения отношений R и S.

Отношение R

Имя	Профессия	Дата
Ася	дизайнер	2019
Сара	программист	2020

Отношение S

Имя	Профессия	Дата
Рози	дизайнер	2020
Сара	программист	2020

Отношение R INTERSECT S

Имя	Профессия	Дата
Сара	программист	2020

Вычитание отношения

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

Обозначение вычитания отношения S из R: R MINUS S.

Вычитание отношения является аналогом разности множеств из теории множеств.

Ниже представлен пример вычитания отношения S из R.

Отношение R

Имя	Профессия	Дата
Ася	дизайнер	2019
Сара	программист	2020

Отношение S

Имя	Профессия	Дата
Рози	дизайнер	2020
Сара	программист	2020

Отношение R MINUS S

Имя	Профессия	Дата
Ася	дизайнер	2019

Декартово произведение отношений

Пусть имеются отношение R с атрибутами a1, a2, ..., an и значениями атрибутов x1, x2, ..., xn в кортежах и отношение S с атрибутами b1, b2, ..., bm и значениями атрибутов y1, y2, ..., ym в кортежах.

Декартово произведение отношений R и S - это бинарная операция, требующая отсутствия совпадающих названий атрибутов между заголовками отношений R и S (между { a1, a2, ..., an } и { b1, b2, ..., bm }), результатом которой является новое отношение T, заголовок которого получается в результате конкатенации (соединения, сцепления) заголовков отношений R и S, а тело состоит из упорядоченных пар ((x1, x2, ..., xn), (y1, y2, ..., ym)), содержащих всевозможные комбинации кортежей отношений R и S соответственно. Для упрощения можно раскрыть скобки внутри упорядоченной пары (порядок элементов сохранится): (x1, x2, ..., xn, y1, y2, ..., ym).

Обозначение декартова произведения R и S: R TIMES S.

Декартово произведение отношений является аналогом декартова произведения множеств из теории множеств.

Ниже представлен пример декартова произведения отношений R и S.

Отношение R(Имя, Фамилия)

Имя	Фамилия
Ася	Тургенева
Рози	Фицджеральд
Сара	Фаулз

Отношение S(Профессия, Дата)

Профессия	Дата
дизайнер	2019
программист	2020

Количество атрибутов в отношении R TIMES S: n(R) + n(S) = 2 + 2 = 4, количество кортежей: m(R) • m(S) = 3 • 2 = 6.

Отношение R TIMES S = T(Имя, Фамилия, Профессия, Дата)

Имя	Фамилия	Профессия	Дата
Ася	Тургенева	дизайнер	2019
Ася	Тургенева	программист	2020
Рози	Фицджеральд	дизайнер	2019
Рози	Фицджеральд	программист	2020
Сара	Фаулз	дизайнер	2019
Сара	Фаулз	программист	2020

Проекция отношения

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

Графически проекция отношения R - это выборка столбцов таблицы.

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

Если отношение R имеет n атрибутов, то его можно обозначить: R(a1, a2, ..., an). Тогда проекция, включающая в себя первый и третий атрибуты отношения R обозначается: PROJECT R { a1, a3 } или R[a1, a3].

Ниже представлен пример проекции отношения R.

Отношение R(Имя, Профессия, Дата)

Имя	Профессия	Дата
Ася	дизайнер	2019
Рози	дизайнер	2019
Сара	программист	2020
Рози	дизайнер	2020

Отношение R[Имя, Профессия]

Имя	Профессия
Ася	дизайнер
Рози	дизайнер
Сара	программист
Рози	дизайнер

Перечёркнутая строка является дубликатом второй строки, поэтому она не попадает в результат.

Выборка (ограничение)

Выборка из (ограничение, селекция) отношения R - унарная операция над отношением R, результатом которой является отношение с тем же заголовком, что и у R, содержащее в своём теле те кортежи из R, которые удовлетворяют некоторому условию c.

Условие c задаётся логическим выражением (его результатом являются истина или ложь), которое может содержать названия атрибутов и константы (числа, строки, даты и так далее). Если результат выполнения выражения c - истина, то кортеж попадает в результат выборки, иначе - не попадает.

Обозначение выборки из отношения R: R WHERE c.

Ниже представлен пример выборки из отношения R.

Отношение R

Имя	Профессия	Дата
Ася	дизайнер	2019
Сара	программист	2020
Рози	дизайнер	2020

Отношение R WHERE (Профессия = дизайнер)

Имя	Профессия	Дата
Ася	дизайнер	2019
Рози	дизайнер	2020

Отношение R WHERE (Дата > 2019)

Имя	Профессия	Дата
Сара	программист	2020
Рози	дизайнер	2020

Отношение R WHERE (Имя != Рози)

Имя	Профессия	Дата
Ася	дизайнер	2019
Сара	программист	2020

Соединение

Соединение отношений R и S - бинарная операция, результатом которой является результат последовательного применения операций декартового произведения R TIMES S и выборки из получившегося отношения с условием c.

Как и в случае с декартовым произведением, в заголовках отношений R и S не должно быть совпадающих атрибутов. Если такие имеются, то их необходимо переименовать перед тем, как производить операцию соединения.

Обозначение соединения отношений R и S: (R TIMES S) WHERE c.

Одним из самых простых соединений является то соединение, в условии которого используются константа (например, число или строка) и один атрибут одного из отношений-операндов соединения. Такое соединение отношений R и S представлено на примере ниже.

Отношение R

Имя	Фамилия
Ася	Тургенева
Рози	Фицджеральд
Сара	Фаулз

Отношение S

Профессия	Дата
дизайнер	2019
программист	2020

Отношение R TIMES S

Имя	Фамилия	Профессия	Дата
Ася	Тургенева	дизайнер	2019
Ася	Тургенева	программист	2020
Рози	Фицджеральд	дизайнер	2019
Рози	Фицджеральд	программист	2020
Сара	Фаулз	дизайнер	2019
Сара	Фаулз	программист	2020

Отношение (R TIMES S) WHERE (Дата = 2019)

Имя	Фамилия	Профессия	Дата
Ася	Тургенева	дизайнер	2019
Рози	Фицджеральд	дизайнер	2019
Сара	Фаулз	дизайнер	2019

Деление отношений

Пусть имеются отношение R с заголовком { a1, a2, ..., an, b1, b2, ... bm } и телом, содержащим множество кортежей вида (x1, x2, ... xn, y1, y2, ... ym), и отношение S с заголовком { b1, b2, ... bm } и телом, содержащим множество кортежей вида (y1, y2, ... ym).

Делением отношения R на отношение S называют бинарную операцию над отношениями R и S, результатом которой является отношение T с заголовком { a1, a2, …, an } и телом, содержащим множество таких кортежей (x1, x2, …, xn), что для каждого кортежа (y1, y2, …, ym) отношения S в R существует кортеж (x1, x2, …, xn, y1, y2, …, ym). В этом случае отношение R называют делимым, отношение S - делителем, отношение T - частным.

Другими словами, в результат деления отношения R на отношение S попадают такие кортежи x = (x1, x2, ... xn) делимого R, c которыми каждый кортеж y = (y1, y2, …, ym) делителя S (то есть все кортежи отношения S без исключения) состоит в упорядоченной паре (x, y), или, что то же самое, в кортеже (x1, x2, ..., xn, y1, y2, ..., ym), принадлежащим отношению R.

Обозначение деления отношения R на S: R DIVIDEBY S.

Чем деление отношений похоже на деление чисел? При делении чисел x ÷ y мы считаем, сколько раз делитель y целиком поместится в делимое x. Пример: 7 ÷ 3 = 3 + 3 + 1 = 2 полных раза. При делении отношений в результат попадает каждый кортеж x, который связан упорядоченными парами со всеми без исключения кортежами y, заданными в отношении-делителе.

Деление отношений проще понять на примере. Ниже представлен пример деления отношения R на отношение S.

Отношение R

Имя	Работа	Разговорный язык
Ася	дизайнер	русский
Ася	дизайнер	немецкий
Сара	программист	английский
Сара	программист	французский
Дина	программист	русский
Дина	программист	итальянский
Дина	программист	английский
Рози	дизайнер	русский
Рози	дизайнер	английский

Отношение S

Разговорный язык
русский
английский

Кто из сотрудников компании в отношении R знает все перечисленные в отношении S языки?

Отношение R DIVIDEBY S

Имя	Работа
Сара	программист
Рози	дизайнер

Сара и Рози знают все перечисленные языки.

Кортежи x = (x1, x2) = (Сара, программист) и x = (x1, x2) = (Рози, дизайнер) попали в результат, поскольку они состоят в упорядоченных парах с каждым из кортежей y = (y1) = (русский), y = (y1) = (английский) отношения S.

В отличие от остальных операций, предложенных Эдгаром Коддом, деление отношений не обрело широкой популярности и используется крайне редко. Такой же результат можно получить комбинацией операций выборки и проекции - такой подход будет гораздо гибче.

Переименование атрибутов отношения

Переименование атрибутов отношения R - унарная операция над отношением R, результатом которой является отношение с телом отношения R и изменёнными названиями указанных атрибутов в заголовке.

Результатом применения операции переименования атрибутов является отношение с изменёнными именами атрибутов.

Обозначение переименования атрибутов { a1, a2, ..., am } отношения R на новые имена { b1, b2, ..., bm }: R RENAME a1, a2, …, an AS b1, b2, …, bn.

Отношение R

Имя	Профессия	Дата
Ася	дизайнер	2019
Сара	программист	2020
Рози	дизайнер	2020

Отношение R RENAME Профессия, Дата AS Специальность, Год

Имя	Специальность	Год
Ася	дизайнер	2019
Сара	программист	2020
Рози	дизайнер	2020

Разновидности операций соединения

• Тэта-соединение
• Экви-соединение
• Естественное соединение

В зависимости от вида условия c различают несколько разновидностей соединений.

Тэта-соединение

Пусть a - один из атрибутов отношения R, b - один из атрибутов отношения S.

Тэта-соединением (Θ-соединением) отношения R по атрибуту a с отношением S по атрибуту b называют соединение отношений R и S с условием c вида a Θ b, где символ Θ является одним из следующих символов сравнения { <, >, ≤ (<=), ≥ (>=), =, ≠ (!=) }.

Обозначение Θ-соединения отношения R по атрибуту a с отношением S по атрибуту b: (R TIMES S) WHERE a Θ b, или более кратко R(a Θ b)S.

Рассмотрим Θ-соединение на примере продажи и покупки некоторого предмета, имеющего в качестве характеристик цвет и качество материала. Пусть имеются отношение R, содержащее запросы на покупку предмета, и отношение S, содержащее выставленные на продажу предметы.

Отношение R (запросы на покупку предмета)

Покупатель	Желаемая цена
magic	240
woodruf	180

Отношение S (выставленные на продажу предметы)

Продавец	Предлагаемая цена	Качество материала	Цвет
evergreen	230	0.7	зелёный
funnyrabbit	180	0.5	бирюзовый
redhot	300	1.0	красный

Найдём все соответствия между запросами на покупку предметов и выставленными на продажу предметами при условии, что желаемая цена покупателя выше (или равна) установленной цены продавца.

Отношение (R TIMES S) WHERE Желаемая цена >= Предлагаемая цена

Покупатель	Желаемая цена	Продавец	Предлагаемая цена	Качество материала	Цвет
magic	240	evergreen	230	0.7	зелёный
magic	240	funnyrabbit	170	0.5	бирюзовый
woodruf	180	evergreen	230	0.7	зелёный

Итак, пользователь magic по своему запросу может купить предмет у пользователя evergreen или у funnyrabbit, а пользователь woodruf - только у evergreen. Пользователь redhot остался без потенциальных покупателей, поскольку установил слишком высокую цену.

Экви-соединение

Экви-соединением отношения R по атрибуту a с отношением S по атрибуту b называют тэта-соединение, при котором символ Θ является символом равенства =.

Обозначение экви-соединения отношения R по атрибуту a с отношением S по атрибуту b: (R TIMES S) WHERE a = b, или более кратко R(a = b)S.

Рассмотрим экви-соединение на примере отношений R и S, имеющих связь 1:1 и представленных таблицами ниже.

Отношение R (современные короли и королевы)

ID	Имя	KINGDOM_ID
val	Виллем-Александр	NL
el2	Елизавета II	GB
k16	Карл XVI Густав	SE
ma2	Маргрета II	DK
fil	Филипп	BE
fi6	Филипп VI	ES
ha5	Харальд V	NO

Отношение S (страны)

ID	Название	KING_ID
BE	Бельгия	fil
GB	Великобритания	el2
DK	Дания	ma2
ES	Испания	fi6
NL	Нидерланды	val
NO	Норвегия	ha5
SE	Швеция	k16

Операцией экви-соединения получим новое отношение, содержащее и страны, и их королей одновременно.

Благодаря тому, что между R и S установлена связь 1:1 (взаимооднозначное соответствие), можем использовать одно из двух условий c (результат будет тот же):

1. R.KINGDOM_ID = S.ID.
2. S.KING_ID = R.ID.

Отношение R(ID = KING_ID)S = R(KINGDOM_ID = ID)S

R.ID	Имя	KINGDOM_ID	S.ID	Название	KING_ID
val	Виллем-Александр	NL	NL	Нидерланды	val
el2	Елизавета II	GB	GB	Великобритания	el2
k16	Карл XVI Густав	SE	SE	Швеция	k16
ma2	Маргрета II	DK	DK	Дания	ma2
fil	Филипп	BE	BE	Бельгия	fil
fi6	Филипп VI	ES	ES	Испания	fi6
ha5	Харальд V	NO	NO	Норвегия	ha5

Понятно, что получившееся отношение имеет избыточные атрибуты. После применения операций проекции и переименования атрибутов получим новое отношение P:

Отношение P

ID	Имя правителя	Название страны
NL	Виллем-Александр	Нидерланды
GB	Елизавета II	Великобритания
SE	Карл XVI Густав	Швеция
DK	Маргрета II	Дания
BE	Филипп	Бельгия
ES	Филипп VI	Испания
NO	Харальд V	Норвегия

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

Естественное соединение

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

Пусть имеются отношение R с заголовком { a1, a2, ..., an, b1, b2, ... bk } и телом, содержащим кортежи вида (x1, x2, ..., xn, y1, y2, ..., yk), и отношение S с заголовком { b1, b2, ..., bk, c1, c2, ..., cm) и телом, содержащим кортежи вида (y1, y2, ..., yk, z1, z2, ..., zm). Атрибуты b1, b2, ..., bk отношений R и S совпадают (то есть совпадают их имена и типы).

Тогда естественным соединением отношений R и S называют соединение T, имеющее заголовок { a1, a2, ..., an, b1, b2, ... bk, c1, c2, ..., cm }, и тело, содержащее кортежи вида (x1, x2, ..., xn, y1, y2, ..., yk, z1, z2, ..., zm).

Таким образом, при естественном соединении кортежи вида (x1, x2, ..., xn, y1, y2, ..., yk) и (y1, y2, ..., yk, z1, z2, ..., zm) объединяются в один кортеж при совпадении между ними значений y1, y2, ..., yk.

Обозначение естественного соединения отношений R и S: R JOIN S.

Отношение G (Товары)

Название	Количество	Номер товара
Стол	16	501
Стул	64	502
Шкаф	8	503

Отношение P (Цена)

Цена	Номер товара
1000	502
2000	501
5000	503

Общим атрибутом отношений G и P является только Номер товара.

Отношение G JOIN P

Название	Количество	Цена	Номер товара
Стол	16	2000	501
Стул	64	1000	502
Шкаф	8	5000	503

Свойства операций над отношениями

Рекомендуется сперва прочесть: «Свойства бинарных операций (теория множеств)».

Обозначим символом ◇ произвольную реляционную операцию, тогда при изучении свойств обозначение ◇ ∈ { INTERSECT, UNION } будет означать, что свойство выполняется для операций пересечения и объединения .

1. Идемпотентность унарных операций: ◇ R = ◇ (◇ R), ◇ ∈ { PROJECT, WHERE }. То есть R[a] = (R[a])[a] и R WHERE c = (R WHERE c) WHERE c.
2. Идемпотентность бинарных операций: R ◇ R = R , ◇ ∈ { UNION, INTERSECT }.
3. Коммутативность: R ◇ S = S ◇ R , ◇ ∈ { TIMES, JOIN, UNION, INTERSECT }. То есть R TIMES S = S TIMES R.
4. Ассоциативность: (R ◇ S) ◇ T = R ◇ (S ◇ T) , ◇ ∈ { TIMES, JOIN, UNION, INTERSECT }.
5. Дистрибутивность

• выборки относительно пересечения, объединения, разности и декартова произведения: (R ◇ S)[a] = R[a] ◇ S[a], ◇ ∈ { INTERSECT, UNION, MINUS, TIMES }.
• проекции относительно объединения декартова произведения: (R ◇ S) WHERE c = (R WHERE c) ◇ (S WHERE c), ◇ ∈ { UNION, TIMES }.

6. Выборку R WHERE c и проекцию R[a] можно менять местами при условии, что c зависит только от выбранных атрибутов a: (R WHERE c)[a] = R[a] WHERE c.

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

Операция переименования атрибутов в общем случае не идемпотентна.

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

Функциональной зависимостью (англ. functional dependency) называют бинарное отношение между двумя подмножествами атрибутов некоторого отношения R.

Фактически, функциональная зависимость - это бинарное отношение между двумя ключами (англ. constraint between two keys) в некотором отношении R. Обычно функциональная зависимость отражает связь "один-ко многим" (1:M).

Пусть у нас имеются два подмножества атрибутов A и B отношения R. Говорят, что множество B функционально зависит (англ. A functionally determine B) от множества A тогда и только тогда, когда каждое значение множества A связано в точности с одним значением множества B.

Говоря другими словами, если два кортежа отношения R совпадают по значением в подмножестве атрибутов A, то эти кортежи также должны совпадать по значениям и в подмножестве атрибутов B.

Функциональную зависимость B от A обозначают: A → B, при этом подмножество атрибутов A называют детерминантом (англ. determinant set), а подмножество атрибутов B называют зависимой частью (англ. dependent set).

Функциональную зависимость называют тривиальной (англ. trivial), если B ⊆ A, то есть если зависимая часть является подмножеством детерминанта.

Отношение R (Работник)

ID	Дата поступления	Название проекта
ID1001	2019	Jest
ID1001	2020	Graphql Apollo
ID7017	2020	Graphql Apollo
ID7017	2021	Koa

Нормализация и нормальные формы

• О нормальной форме и нормализации
• О денормализации
• Первая нормальная форма

О нормальной форме и нормализации

Нормальной формой (англ. normal form) называют некоторое требование или совокупность требований, которым должно удовлетворять отношение для устранения избыточности.

Если эти требования выполняются для каждого отношения некоторой базы данных, то её называют нормализованной базой данных (англ. normalized database). Сам процесс приведения базы данных к нормализованному виду называется нормализацией этой базы данных (англ. database normalization).

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

Понятие нормализации ввёл Эдгад Кодд как часть своей реляционной модели.

О денормализации

Денормализацией базы данных (англ. database denormalization) называют процесс, обратный нормализации. В этом случае в базу данных умышленно добавляют избыточные данные (дубликаты данных) для ускорения получения данных.

Когда отношений слишком много и они тесно связаны друг с другом, группировка (операция соединения) данных может занимать продолжительное время (скажем, сделать соединение INNER JOIN десяти таблиц), что плохо сказывается на производительности системы, а значит и на пользовательском опыте.

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

Денормализованный вид усложняет операции создания, обновления и удаления данных (ведь нужно изменять не только сами данные, но и все их дубликаты), а также увеличивает размер базы данных. Зато существенно снижается время отклика системы при чтении данных.

Ниже представлен пример денормализации в табличном виде.

Публикация (дублирует только те поля пользователя, которые нужны для отображения на странице)

ID	Заголовок	Текст	Автор
N1	Нормализация	Нормализацией базы данных называют....	ID: U1 Никнейм: @max.starling Почта: max.starling@email
N2	Денормализация	Денормализацией базы данных называют....	ID: U1 Никнейм: @max.starling Почта: max.starling@email
N3	Реляционная модель данных	Реляционной моделью данных называют....	ID: U2 Никнейм: @ray.gray Почта: ray.gray@email

Пользователь (хранит идентицикаторы публикаций, чтобы публикации было проще найти на странице пользователя)

ID	Никнейм	Почта	Возраст	Публикации
U1	@max.starling	max.starling@mail	23	[N1, N2]
U2	@ray.gray	ray.gray@mail	27	[N3]

Ниже представлен пример денормализации в документном виде.

Публикации в формате JSON

[{
  "_id": "N1",
  "title": "Нормализация",
  "text": "Нормализацией базы данных называют....",
  "user": {
    "_id": "U1",
    "username": "@max.starling",
    "email": "max.starling@email"
  }
},
{
  "_id": "N2",
  "title": "Денормализация",
  "text": "Денормализацией базы данных называют....",
  "user": {
    "_id": "U1",
    "username": "@max.starling",
    "email": "max.starling@email"
  }
},
{
  "_id": "N3",
  "title": "Реляционная модель данных",
  "text": "Реляционной моделью данных называют....",
  "user": {
    "_id": "U2",
    "username": "@ray.gray",
    "email": "ray.gray@email"
  }
}]

Пользователи в формате JSON

[{
  "_id": "U1",
  "username": "@max.starling",
  "email": "max.starling@email",
  "age": 23,
  "posts: ["N1", "N2"]
}, {
  "_id": "U2",
  "username": "@ray.gray",
  "email": "ray.gray@email",
  "age": 27,
  "posts: ["N3"]
}]

Первая нормальная форма

Отношение находится в первой нормальной форме (англ. first normal form), 1НФ (англ. 1NF) тогда и только тогда, когда любой кортеж отношения может содержать только одно значение для каждого из атрибутов.

Таким образом, значение атрибута не может быть представлять собой набор значений (массив, множество, таблицу и так далее), если отношение находится в 1НФ.

В реляционной модели данных отношение всегда находится в 1НФ по своему определению.

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

Например, SQL не поддерживает использование столбцов с табличными значениями (англ. table-valued columns).

Пример ненормализованной таблицы:

Страна	Город
Россия	Москва, Санкт-Петербург
Украина	Киев, Львов
Беларусь	Минск

Пример нормализованной таблицы:

Страна	Город
Россия	Москва
Россия	Санкт-Петербург
Украина	Киев
Украина	Львов
Беларусь	Минск

Базы данных, которые нарушают первую нормальную форму, обычно называют NoSQL базами данных. Примером такой базы данных является документная база данных MongoDB, которая позволяет хранить любые JSON-документы (значения могут быть массивами или объектами).

Паттерны баз данных

Движки баз данных