Введение. СУБД

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

СУБД – системы управления базами данных – это специализированное ПО, призванное, ожидаемо, управлять базами данных. Достигается это взаимодействием с пользователем с одной стороны и собственно с базой данных с другой.

СУБД общего назначения должна позволять определение, создание, изменение, администрирование и произведение запросов к БД.

В качестве примеров СУБД можно назвать такие широко известные пакеты, как

• MySQL
• PostgreSQL
• Microsoft SQL Server
• Oracle
• IBM DB2
• Microsoft Access
• SQLite

Базы данных обычно не являются переносимыми между различными СУБД, однако возможно взаимодействие между СУБД (и с пользовательским ПО) с использованием различных стандартов, таких, как SQL, ODBC или JDBC.

СУБД часто классифицируются по поддерживаемой ими модели данных. С 1980х годов, практически все популярные СУБД поддерживают реляционную модель данных, представленную стандартом языка запросов SQL (хотя последние годы набирает популярность NoSQL).

Итак, основные задачи, выполняемые СУБД включают

Определение схемы данных

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

Изменение данных

Добавление, изменение и удаление самих данных

Получение данных

Предоставление информации в форме, пригодной к непосредственному использованию другими приложениями.

Администрирование БД

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

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

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

Модели БД

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

• Иерархическая, или навигационная модель
• Сетевая модель

Иерархическая модель широко использовалась в СУБД, поставляемых компанией IBM в 1960х. Основная идея заключается в том, что запись в такой БД может иметь несколько “дочерних” и одну “родительскую”. В целом, это подозрительно похоже на иерархическую файловую систему. Чтобы получить запись в такой БД, часто необходим проход по всему дереву.

Сетевая модель – более гибкая версия того же подхода. Она позволяет иметь записи несколько “родительских”. Эта модель, появившись в начале 1970х, не получила широкого распространения, и вскоре была вытеснена реляционной моделью.

В 1970х Эдгаром Коддом (сотрудник IBM) была предложена реляционная модель, которая значительно облегчила задачу поиска информации в БД. О реляционной модели можно думать как о “таблицах”, в которых “строки” – это записи в БД. Записи в реляционной БД так же называются кортежами (tuples), а группы записей (“таблицы”) – отношениями (relations). Реляционная модель способна выразить связи иерархической и сетевой моделей, и добавляла собственные связи, соответствующие табличной модели.

На основе предложений Кодда к середине 1970х была разработана СУБД System R, а к концу в ней появилась поддержка стандартизованного языка запросов SQL.

В 1980х, с появлением объектно-ориентированного программирования, все чаще возникали сложности в трансляции объектов на реляционную модель. В конце концов это привело к появлению подходов NoSQL и NewSQL, которые на текущий момент только развиваются. Примерами реализации NoSQL подхода могут быть т.н. документо-ориентированные БД, построенные на основе XML. Основное преимущество NoSQL – высокая горизонтальная масштабируемость, т.е. возможность увеличивать производительность за счет добавления серверов. С появлением облачных технологий, NoSQL стал особенно востребован.

Тем не менее, реляционная модель пока остается самой распространенной, поэтому более подробно остановимся именно на ней.

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

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

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

Введем некоторые определения.

Домен

Множество, содержащее полный набор всех возможных значений некоторой переменной. Домены часто так же называют типом данных.

Атрибут

Упорядоченная пара названия атрибута и домена \(D_j\).

Кортеж

Конечное упорядоченное множество \((d_1, d_2, \ldots, d_n)\)

Заголовок (схема) отношения

Кортеж \((A_1, A_2, \ldots, A_n)\), где \(A_j\) – атрибуты.

Значение атрибута

Конкретное значение, принадлежащее домену атрибута.

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

Множество кортежей \((d^i_1, d^i_2, \ldots, d^i_n)\), где \(d^i_j \in D_j\), \(D_j\) – домены.

Запись

Кортеж \((d^i_1, d^i_2, \ldots, d^i_n)\) при фиксированном \(i\).

Отношение

Совокупность заголовка отношения и тела отношения.

Схема базы данных

Множество схем всех отношений, входящих в БД.

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

Реляционная модель налагает следующие дополнительные требования на отношения:

• Атрибуты имеют фиксированный тип данных (домен)
• Значения атрибутов атомарны¹
• Записи уникальны
• Порядок записей не имеет значения (нет скрытых атрибутов)
• Порядок атрибутов не имеет значения (нет скрытых зависимостей атрибутов)

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

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

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

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

В качестве более привычного примера функциональной зависимости, можно привести математическое определение функции. Для функции, каждому значению аргументов соответсвтует единственное значение функции. Обратное в общем случае неверно, например, для функции \(y = sin(x)\) любому значению \(y\) из области определения \(1\geq y \geq -1\) соответствует бесконечное множество значений \(x\), но для каждого значения \(x\) есть ровно одно значение \(y\), т.о. \(x \to y\). Заметим, что понятие функциональной зависимости так же применимо и к функциям многих переменных. Для них, значение функции функционально зависит от всех аргументов одновременно. Скажем, для функции \(z = f(x,y)\) выполняется ФЗ \((x,y)\to z\), или сокращенно, \(xy\to z\).

Отношения в данном контексте можно рассматривать как некие табличные или дискретные функции.

Работа с ФЗ

Существуют определенные формальные правила работы с ФЗ отношения.

Формальные правила тесно связаны с понятиями замыкания и неприводимой ФЗ.

Аксиомы Армстронга

Существуют правила вывода новых ФЗ из существующих, называемые аксиомами Армстронга.

Аксиомы Армстронга

1. Правило рефлексивности: если \(B \subset A\), то \(A\rightarrow B\)
2. Правило дополнения: если \(A\rightarrow B\), то \(AC\rightarrow BC\)
3. Правило транзитивности: если \(A\rightarrow B\) и \(B\rightarrow C\), то \(A\rightarrow C\)

Из этих аксиом так же могут быть выведены следующие дополнительные правила:

4. Правило самоопределения: \(A\rightarrow A\)
5. Правило декомпозиции: Если \(A\rightarrow BC\), то \(A\rightarrow B\) и \(A\rightarrow C\)
6. Правило объединения: Если \(A\rightarrow B\) и \(A\rightarrow C\), то \(A\rightarrow BC\)
7. Правило композиции: Если \(A\rightarrow B\) и \(C\rightarrow D\), то \(AC\rightarrow BD\)

Можно заметить, что, вследствие правила рефлексивности, любое множество атрибутов \(A\) подразумевает ФЗ вида \(A\to A\). Такие ФЗ, а так же следующие из них, не представляют интереса, и называются тривиальными.

Тривиальная функиональная зависимость

ФЗ \(A \to B\), такая, что \(B \subset A\).

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

Замыкание множества ФЗ

Замыканием множества ФЗ называется такое множество ФЗ, которое включает все ФЗ исходного множества, а так же все подразумеваемые ими. Другими словами, для отношения \(R\), обладающего функциональными зависимостями \(S\), замыканием \(S^+\) называется множество всех ФЗ, возможных для \(R\), исходя из \(S\).

Как правило, требуется установить, будет ли некая ФЗ \(X\rightarrow Y\) следовать из данного множества ФЗ \(S\). Оказывается, это возможно тогда и только тогда, когда множество атрибутов \(Y\) является подмножеством замыкания атрибутов \(X^+\) в \(S\).

Замыкание атрибутов

Замыканием \(X^+\) атрибутов \(X\) по множеству ФЗ \(S\) называется множество всех атрибутов, которые функционально зависят от какого-либо подмножества \(X\).

Для вычисления замыкания множества атрибутов \(X^+\) по множеству ФЗ \(S\) существует следующее правило: для каждой ФЗ \(A\rightarrow B\) в \(S\), если \(A \subset X^+\), то и \(B \subset X^+\), причем достаточно начать с предположения, что \(X^+ = X\).

Следует заметить, что для любого замыкания \(X^+\), существуют ФЗ вида \(X \to B\), где \(B \subset X^+\), таким образом, замыкания всех атрибутов отношения по его ФЗ описывают замыкание ФЗ этого отношения.

Это правило используется для вычисления неприводимого множества ФЗ, эквивалентного данному (в смысле эквивалентности их замыканий). Уменьшение количества ФЗ при сохранении замыкания (и, следовательно, внутренней логики, описываемой ФЗ) является важным шагом в проектировании БД.

Множество ФЗ называется неприводимым, если:

1. Правая часть каждой ФЗ содержит только один элемент
2. Ни один атрибут ни одной левой части ФЗ множества не может быть удален без изменения замыкания
3. Ни одна ФЗ множества не может быть удалена без изменения замыкания.

Для любого множества ФЗ существует хотя бы одно эквивалентное неприводимое множество. Такое множество называется минимальным покрытием.