Базы данных и нормальные формы (НФ)

Элементы теории реляционных БД (ТРБД).

Идеи теории:

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

Рейсы

№	Пункт_от	Пункт_наз	Вр_выл	Вр_пр	чет
	Москва Одесса Москва Москва Киев	Одесса Москва Томск Киев Москва	9.30 13.00 1.15 9.30 13.20	11.05 13.50 5.10 10.15 13.50	Чет Чет Чет Нт Нт

В теории реляционных БД таблицы называются отношениями. Формат отношений определяется множеством имён атрибутов.

R={№, Пункт_от, Пункт_наз, Вр_выл, Вр_пр}

R – Схема отношений (показывает множество имён атрибутов.

Имена атрибутов – имена столбцов.

Любому имени атрибута ставится в соответствие множество допустимых для этого столбца значений – домен.

Любая строка в отношении называется кортежем.

Таблица – множество кортежей

Во множестве имён есть подмножество имён, значения которых уникальны (однозначно определяют кортеж). Такие подмножества назовём ключом (в ТРБД они уникальны).

Формализация отношений.

Схема отношений R – множество имён атрибутов R={A₁, A_2,…, An}_i_=1,2…_n_.

Домен: D_i = dom(A_i) – множество допустимых значений атрибута A_i

D_i – непустое конечное множество.

Отношение: r(R), R – схема. R(R) = {t₁, t₂,…,t_n }.

{t₁, t₂,…,t_n }- конечное множество отображений из R в D, причём отображение должно удовлетворять следующим условиям: - значение кортежа на i-м атрибуте.

В ТРБД исключается любое упорядочение имён атрибутов в схеме, т.к. используются неупорядоченные множества.

Ключ – отношения r(R) - , и никакое подмножество k’ не обладает этим свойством.

Суперключ. K={N,чет} – ключ. В суперключе существует подмножество, которое может быть ключом K={№,чет, пункт_от} – суперключ.

Обновление отношений.

Обновление отношение:

1) Add - добавление

2) Del - удаление

3) Ch – изменение

1. Add (r;A₁=d₁,A₂=d₂…A_n=d_n).

Add(рейсы;№=737,Пункт_от=…)

Ошибки в следующих ситуациях:

· Кортеж не соответствует схеме

· Некоторое значение кортежа не соответствует доменам

· Вводимый кортеж совпадает по ключу с уже введенным кортежем.

2. Del(r;A₁=d₁,A₂=d₂…A_n=d_n). достаточно указать ключевые поля. Del(рейсы; №=736,чет=нт)

3. Ch(r;A₁=d₁,A₂=d₂…A_n=d_n; C₁=l₁,…,C_p=l_p).

Ch(рейсы;№=736,чет=нт,Вр_выл=13.10).

Реляционные операторы.

- это операторы над отношениями. Рассмотрим операторы над отношениями с одинаковой схемой (r(R),s(R)):

а) Пересечение , в q кортежи, которые принадлежат и r и s

б) Объединение Кортежи в 1-й или во 2-й.

в) Разность r-s=q₂(R)

dom(R) – домен – множество всех кортежей над атрибутами схемы R и их доменами.(кортежи появляются комбинированием доменов A_i (domA₁)).

Пример:

dom	(ABC)	domA	domB	domC
	a₁b₁c₁	a₁	b₁	c₁
	a₁b₂c₁	a₂	b₂
	a₂b₁c₁
	a₂b₂c₁

Dom(R)=dom(ABC)

г) Дополнение ř=dom(R)-r. (Некоторые домены могут иметь бесконечное число записей, и это связано с точностью измерения) следовательно, существуют активный домен и активное дополнение.

Активный домен A_i отношения r –

Adom(R,r) – множество всех кортежей над атрибутами схемы R и их доменами.

Активное дополнение. ř=adom(R,r)-r.

Если множество значений в домене конечное, то активный домен не нужен.

д) Выбор.

Пример:

е) Проекция

получено вычёркиванием столбцов соответствующих атрибутам в R –x и исключением из оставшихся столбцов повторяющихся строк.

Пример:

ж) Естественное соединение – комбинируется 2 отношения по всем их общим атрибутам.

Отношения – r(R),s(S)

Пример: ,

з) Деление. r’ = r ÷ s. ,

r ÷ s =

Пример: право управления:

Пилот	Тип самолёта
Е Е Е О О

, право ÷

и) Постоянные отношения. (const в программах). Кортежи, которые не меняются – постоянные кортежи. <C₁:A₁,C₂:A₂,…>

(<E:Пилот><707:номер самолёта>)

Постоянные отношения – множество постоянных кортежей.

к) Переименование атрибутов. δ_A₌_B(r). Имя атрибута A будет заменено на B.

л) Эквисоединение. Соединение по условию: r[условие]r – условие только типа равенство.

м) Тетта – соединение (Θ – соединение).

r[A ΘD]r – условие – любой оператор сравнения(=,<,>,…)

δ_A_Θ_B(r) – расширенный оператор выбора.

Реляционная алгебра.

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

Операторы, не вошедшие в реляционную алгебру (дают два отношения):

1) Оператор расщепления.

SPLIT_β(r)

β(t) – предикат(результат – либо истина, либо ложь).

Пример:

список	(сотрудники,	Пол,	Курящий)
Иванов Петров Петрова Сидоров Попов Попова	М М Ж М М Ж	Да Да Да Нет Нет Нет

β(t) =(t(пол)=М и t(кур)=да)

список	(сотрудники,	Пол,	Курящий)
Иванов Петров	М М	Да Да

SPLIT _β(список)=

Получаем два отношения – (S,S’).

Список’	(сотрудники,	Пол,	Курящий)
Петрова Сидоров Попов Попова	Ж М М Ж	Да Нет Нет Нет

2) Фактор.

r(R) b₁,b₂,….,b_m R,

Factor (r; b₁,b₂,….,b_m; L) – оператор, который удаляет столбцы, соответствующие b₁,b₂,….,b_m из отношения R с целью образования нового отношения и добавлением в новое отношение и в R специального столбца L, причём по L осуществляется соединение.

Список1	(сотр.,	L)
	Иванов Петров Петрова Сидоров Попов Попова

Пример:

Список2	(L	Пол,	Кур.,)
	М М Ж Ж	Да Нет Да Нет

Factor (список; пол, кур;L)

Легко проверить, что:

список =

Функциональные зависимости.

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

В реальных таблицах существуют ограничения на данные. Пусть существуют ограничения на график.

График	(Пилот,	Рейс,	Дата,	Вр.выл)
	Y Y L L L I I A A A		9авг. 10авг.	10.15 13.25 5.50 18.35 10.15 10.15 13.25 5.50 5.50 13.25

Не любое сочетание дата – время допустимо. Ограничения:

1. Для каждого рейса – одно время вылета

2. Для данного пилота, даты и времени вылета – один рейс

3. Для данного рейса – один пилот

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

1. Рейс→Вр_Выл

2. Пилт Дата Вр_Выл → Рейс

3. Рейс Дата → Пилот

В ТРБД пробел означает объединение.

Опр. Функциональная зависимость (F-зависимость)

r(R) x,yR

r удовлетворяет зависимости x→y если имеет не более 1 кортежа для любого значения x. (Если заданно отношение r, то y функционально зависит от x когда каждое значении x в R связанно только с одним значением в y.

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

Для проверки функциональной зависимости используется алгоритм Satisfies(r;x→y).

Вход алгоритма –r, x→y

Выход алгоритма – И (удовл.) или Л (не удовл.)

Шаги алгоритма:

1) Пересортируем r по x – столбцам, чтобы строки с равными значениями стояли рядом.

2) Если любая совокупность кортежей с каждыми x- значениями имеет также равные y-значения, то на выходе получаем Истину, иначе – Ложь.

Пример: Satifies (график; Рейс→Вр_Выл).

Все сходятся, истина.

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

НФ – ограничение на схему БД, которое избавляет БД от некоторых нежелательных свойств.

Схема БД (R) – множество схем – отношений, входящих в БД: R ={R₁,R₂,…,R_m}.

Общее правило: Если БД находится в НФ, то и все отношения находятся в НФ.

1НФ. R находится в первой нормальной форме, если значения в доменах A_i являются атомарными для каждого атрибута.

Пример1. (Имя Дата_рожд Знак_Зодиака)

День месяц →знак_зодиака (дата рождения – день, месяц, год – не атомарная)

Пример2. (Автор Книга Год) – Автор – неатом.

2НФ. Пример:

График	(Рейс,	Дата,	Пилот,	Галерея)
		6.06 7.06 9.06	Иванов Петров Иванов

F={рейс→галерея}

Меняем 3 на 4 (галерея 3 на ремонте) много изменения – аномалия.

Противоречие:

Опр. Схема отношения R находится во второй НФ относительно множества функциональных зависимостей F, если она находится в 1НФ и любой атрибут полностью зависит от любого ключа для R.

Схема БД R находится во 2-й НФ относительно F, если любая сема отношения R находится во 2НФ.

Алгоритм устранения:

1. Определить ключ;

2. определить множество функциональных зависимостей из схемы БД.