Понятие СУБД. Основные задачи СУБД

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

Задачи:

Управление схемой данных (определение, изменение, удаление)
Управление данными (добавление, изменение, удаление)
Получение данных
Администрирование БД (управление доступом, контроль целостности, и и.п.)

Модели БД.

Модели БД:

Иерархическая
Сетевая
Реляционная

Иерархическая модель использует древовидную схему для описания связей между данными, и отражает связи типа 1:М, когда у одного “родительского” узла может быть множество “потомков” (ветвей), но только один “родительский”

Сетевая модель – расширение иерархической, и допускает множество “родительских” узлов.

Реляционная модель. Основные определения

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

Домен: Множество, содержащее полный набор всех возможных значений некоторой переменной. Домены часто так же называют типом данных.
Атрибут: Упорядоченная пара названия атрибута и домена \(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\).
Отношение: Совокупность заголовка отношения и тела отношения.
Схема базы данных: Множество схем всех отношений, входящих в БД.

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

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

Понятие функциональной зависимости

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

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

Более простая (но менее точная) формулировка: \(A \to B\) означает “B функционально зависит от A”, или, “значение A однозначно определяет значение B”.

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

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

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

Следствия:

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

Замыкание атрибутов по множеству ФЗ

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

Нормальные формы

Мы рассматриваем четыре основных нормальных формы (НФ). Нормальная форма – описание зависимостей внутри одного отношения. Если все отношения схемы находятся в некоторой нормальной форме, можно сказать, что схема находится в этой нормальной форме.

Суперключ: Множество атрибутов отношения, от которого функционально зависят все атрибуты этого отношения.
Тривиальный суперключ: Суперключ, состоящий из всех атрибутов отношения. Всегда существует (по правилу рефлексивности).
Потенциальный ключ: Минмальное множество атрибутов отношения, от которого функционально зависят все атрибуты отношения (минимальный суперключ). Всегда является подмножеством какого-либо суперключа.
Ключевой атрибут: Атрибут, входящий в какой-либо потенциальный ключ.
Неключевой атрибут: Атрибут, не входящий ни в один потенциальный ключ.
1НФ (первая): Любое отношение находится в 1НФ по определению.
2НФ (вторая): Все атрибуты отношения функционально зависят от какого-либо потенциального ключа. Подразумевает 1НФ.
3НФ (третья): Отсутствуют транзитивные функциональные зависимости неключевых атрибутов от потенциального ключа. 3НФ подразумевает 2НФ.
НФБК (Бойса-Кодда): Отсутствуют функциональные зависимости между подмножествами разных потенциальных ключей. НФБК подразумевает 3НФ.

Способ приведения отношения в нормальную форму – декомпозиция, то есть разделение исходного отношения на несколько других.

Декомпозиция без потерь

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

Всегда возможна декомпозиция без потерь до 3НФ. Этого нельзя сказать о НФБК.

Виды связей между отношениями

Для двух отнощений \(R\) и \(S\) могут быть следующие виды связей:

Один-к-одному (1:1) – существует взаимно однозначное соответствие между записями отношений
Многие-к-одному (М:1) – для любой записи отношения \(R\) существует ровно одна соответствующая ей запись отношения \(S\). Обратное неверно.
Один-ко-многим (1:М) – обратное к предыдущему. Для любой записи отношения \(S\) существует ровно одна соответствующая ей запись отношения \(R\). Обратное неверно.
Многие-ко-многим (М:М) – не существует однозначного соответствия между записями отношений (но существует многозначное)

Проектирование баз данных.

Этапы проектирования:

Концептуальное (инфологическое) проектирование.
Логическое (даталогическое) проектирование
Физическое проектирование

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

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

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

ER-диаграммы

Один из возможных инструментов инфологического проектирования.

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

Атрибутами связи обладают только связи типа “М:М”.

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

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

Переводится в \[\text{Идентифицирующий атрибут} \to (\text{Атрибут сущности 1}, \text{Атрибут сущности 2})\]

Переводится в \[\text{Сущность 1.id} \to \text{Сущность 2.id},\] где \(\text{Сущность 1.id}\) – идентифицирующий атрибут или атрибуты сущности “Сущность 1”, \(\text{Сущность 2.id }\) – идентифицирующий атрибут сущности 2.

Переводится в \[(\text{Сущность 1.id}, \text{Сущность 2.id}) \to \text{Атрибут связи}\]

Диаграммы атрибутов

Способ графического представления функциональных зависимостей. Как правило, применяется для нормализации отношения из 1НФ в 3НФ. Атрибуты обозначаются овалами, функциональные зависимости – стрелками на диаграмме. Если в левой части ФЗ несколько атрибутов, стрелки сливаются.

Множество ФЗ отношения \(R(A,B,C,D,E)\) в 1НФ:

\[(A, B) \to C\] \[(A, B) \to D\] \[C \to E\]

Диаргамма:

Язык SQL.

SQL – декларативный язык высокого уровня. Это означает, что на SQL пишется, что Вы хотите получить, а не как.

Общий синтаксис: ОПЕРАТОР аргументы...;

Операторы управления схемой

Основных операторов управления схемой 3:

CREATE создает объект схемы
DROP удаляет объект схемы
ALTER изменяет определение объекта схемы

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

DATABASE (синоним SCHEMA) – база данных
TABLE – таблица (отношение)
PROCEDURE – хранимая процедура
VIEW – отображение

Операторы управления данными

Основных 4:

SELECT – чтение (выборка)
DELETE – удаление
INSERT – добавление (вставка)
UPDATE – изменение (обновление)

Операции реляционной алгебры

Выборка

Выборка

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

\(\sigma_{a<10} R\) выбирает из отношения \(R\) записи, в которых атрибут \(a\) меньше \(10\).

В SQL реализуется посредством оператора SELECT. Выборка \(\sigma_\theta(R)\) по условию \(\theta\) из отношения \(R\) соответствует выражению SQL SELECT * FROM R WHERE θ

Проекция

Проекция

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

\(\pi_{a,b} R\) выбирает атрибуты \(a\), \(b\) из отношения \(R\).

В SQL реализуется посредством оператора SELECT. Проекция \(\pi_{a, b \ldots}(R)\) на множество атрибутов \(a, b \ldots\) из отношения \(R\) соответствует выражению SQL SELECT a, b ... FROM R

Переименование

Переименование

Возвращает отношение, содержащее все записи (кортежи) заданного отношения, при этом название одного атрибута заменяется на другое.

\(\rho_{a/b} R\) возвращает все записи отношения R, в которых атрибут \(a\) переименован в \(b\).

В SQL реализуется посредством оператора SELECT. Переименование \(\rho_{a/b, c/d \ldots}(R)\) атрибутов \(a\) в \(b\), \(c\) в \(d\) и т.д. соотвтетсвутет выражению SQL SELECT a AS b, c AS d ... FROM R

Произведение

Произведение

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

\(R \times S\) возвращает отношение, в котором присутствуют все атрибуты отношений \(R\) и \(S\) во всех возможных комбинациях.

В SQL реализуется посредством оператора SELECT. Произведение \(R \times S\) отношений \(R\) и \(S\) соотвтетсвутет выражению SQL SELECT * FROM R CROSS JOIN S, или, в некоторых реализациях, SELECT * FROM R JOIN S.

Объединение

Объединение

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

\(R \cup S\)

В SQL реализуется оператором UNION, действующийм на результаты выборки. Аналогом \(R \cup S\) будет (SELECT * FROM R) UNION (SELECT * FROM S)

Пересечение

Пересечение

Возвращает отношение, содержащее все кортежи, которые принадлежат одновременно двум заданным отношениям.

\(R \cap S\)

В SQL реализуется оператором INTERSECT, действующийм на результаты выборки. Аналогом \(R \cup S\) будет (SELECT * FROM R) INTERSECT (SELECT * FROM S)

Разность

Разность

Возвращает отношение, содержащее все кортежи, которые принадлежат первому из двух заданных отношений и не принадлежат второму.

\(R - S\)

В SQL реализуется оператором EXCEPT, действующийм на результаты выборки. Аналогом \(R \cup S\) будет (SELECT * FROM R) EXCEPT (SELECT * FROM S)

Соединение

Соединение

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

\(R \bowtie S\)

В SQL реализуется оператором NATURAL INNER JOIN в блоке FROM оператора SELECT. Аналогом \(R \bowtie S\) будет SELECT * FROM R NATURAL INNER JOIN S

θ-соединение

θ-соединение

\(R \bowtie_\theta S = \sigma_\theta (R \times S)\)

В SQL реализуется оператором INNER JOIN в блоке FROM оператора SELECT. Аналогом \(R \bowtie_\theta S\) будет SELECT * FROM R INNER JOIN S ON θ

Другие типы соединений

OUTER LEFT JOIN
OUTER RIGHT JOIN
OUTER FULL JOIN

Т.н. внешние соединения. В то время как INNER JOIN – внутреннее. Внешние соединения включают не только записи, удовлетворяющие условию, но так же и вообще все записи из левого (в случае LEFT-варианта), правого (в случае RIGHT-варианта) или обоих (в случае FULL-варианта) отношений. При этом, у “дополнительных” записей отсутствует соответственно часть, относящаяся ко второму отношению (все атрибуты имеют значение NULL)

Например,

Отношение R
id	value
1	a
2	b
4	d
5	e

Отношение S
id	value
1	α
2	β
3	γ

`SELECT * FROM R INNER JOIN S ON R.id = S.id`
R.id	R.value	S.id	S.value
1	a	1	α
2	b	2	β

`SELECT * FROM R OUTER LEFT JOIN S ON R.id = S.id`
R.id	R.value	S.id	S.value
1	a	1	α
2	b	2	β
4	d
5	e

`SELECT * FROM R OUTER RIGHT JOIN S ON R.id = S.id`
R.id	R.value	S.id	S.value
1	a	1	α
2	b	2	β
		3	γ

`SELECT * FROM R OUTER FULL JOIN S ON R.id = S.id`
R.id	R.value	S.id	S.value
1	a	1	α
2	b	2	β
4	d
5	e
		3	γ

Теоретический минимум