Аксиома рефлективности . ЕслиY входит вX , аX входит вU , (Y X U ), тоX Y логически следует изF . Это правило дает тривиальные зависимости, так как в этих зависимостях правая часть содержится в левой части.

Аксиома пополнения . ЕслиX Y иZ есть подмножествоU , тоXZ YZ . В данном случае функциональная зависимостьX Y либо содержалась в исходном множествеF , либо может быть выведена изF с использованием описываемых аксиом.

Аксиома транзитивности. Если X Y и Y Z , то X Z .

Справедлива следующая теорема . Аксиомы Армстронга являются полными и надежными.

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

Существует несколько других правил вывода, которые следуют из

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

4.4.3. Декомпозиция схемы отношения

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

Декомпозицией схемы отношения R = {А 1 , А 2 ,…А n } называется замена ее совокупностью подмножествR , таких, что их объединение даетR . При этом допускается, чтобы подмножества были пересекающимися.

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

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

Алгоритм декомпозиции основан на следующей теореме. Теорема Фейджина. ПустьR (A, B, C ) отношение,A, B, C – атри-

Если R удовлетворяет зависимостиA B , тоR равно соединению его проекцийA, B иA, C

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

Пусть есть некоторая схема отношения R = A 1 …A n , множество функциональных зависимостейF и некоторая декомпозиция(R 1 ,…R k ) исходной схемы, состоящая изk подсхем.

Необходимо построить таблицу с n столбцами иk строками. Столбецj соответствует атрибутуA j , строкаk схеме отношенияR k . На пересечении строкиi и столбцаj поместим символa j , еслиА j принадлежитR i . В противном случае поместим туда символb ij .

Рассматриваем каждую зависимость из множества F до тех пор, пока в таблице невозможно сделать какие-либо изменения. Всякий раз, рассматривая зависимостьX Y , мы ищем строки, которые совпадают по всем столбцам, соответствующим атрибутам изX . При обнаружении таких строк, отождествляем символы в столбцах, соответствующих атрибутам изY . Если при этом один из отождествляемых символов равенa j , то приравниваем и другойa j . В том случае, когда они равныb ij иb lj , делаем их оба равнымиb ij илиb lj по своему усмотрению.

После модификации строк таблицы указанным выше способом может обнаружиться, что некоторая строка стала равной a 1 …a k . Тогда декомпозиция обладает свойством соединения без потерь. Если такой строки не получается, то декомпозиция не обладает таким свойством.

Декомпозиция схемы ABCD наAB иACD .

A B ,AC D (AC – сокращенная записьА С ).

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

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

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

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

4.4.4. Выбор рационального набора схем отношений путем нормализации

Вторая нормальная форма (2НФ)

Отношение находится в 2НФ, если оно находится в 1НФ и каждый неключевой атрибут зависит от первичного ключа (не зависит от части ключа).

Для перевода отношения в 2НФ необходимо, используя операцию проекции, разложить его на несколько отношений следующим образом:

1) построить проекцию без атрибутов, находящихся в частичной функциональной зависимости от первичного ключа;

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

Третья нормальная форма (3НФ)

Отношение находится в 3НФ если оно находится во 2НФ и каждый ключевой атрибут нетранзитивно зависит от первичного ключа.

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

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

Мотивировка третьей нормальной формы

Третья нормальная форма исключает избыточность и аномалии включения и удаления. К сожалению, 3НФ не предотвращает все возможные аномалии.

Нормальная форма Бойса-Кодда (НФБК)

Если в R для каждой зависимостиX A , гдеА не принадлежитX ,X включает в себя некоторый ключ, то говорят, что данное отношение находится в нормальной форме Бойса-Кодда.

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

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

НФБК является более строгой версией 3НФ. Иными словами любое отношение, находящееся в НФБК, находится в 3НФ. Обратное неверно.

Пример. Расписание консультаций. Каждая группа может прийти на консультацию один раз в день. Для проведения консультации или консультаций преподавателю на определенный день предоставляется аудитория. В течение дня данная аудитория может использоваться разными преподавателями.

РАСПИСАНИЕ КОНСУЛЬТАЦИЙ (Группа, Дата, Время, Преподаватель, Аудитория)

В качестве первичного ключа выбрали «Группа, Дата». Потенциальные ключи:

«Группа, Дата». «Преподаватель, Дата, Время». «Аудитория, Дата, Время».

Декомпозиция схем отношений

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

· Декомпозицией схемы отношений R называется замена ее совокупностью схем r=(R 1 , R 2 , ... , R K), где R i Ì R и R i такие, что R 1 ÈR 2 È... ÈR K = R, при этом не требуется, чтобы R i Ç R j =Æ, хотя и допустимо.

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

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

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

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

Целостность в БД отражается путем построения логической схемы.

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

· Если состояние БД не соответствует семантике связей между данными, то такое явление называют нарушением целостности данных или БД.

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

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

Ограничения приложений делятся на:

Статические ограничения и ограничения перехода;

Ограничения для кортежей и множеств;

Отложенные и безотлагательные ограничения целостности.

· Статические ограничения - те ограничения, которые выполняются независимо от состояния БД.

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

Пример : при обновлении значения атрибута “давление” новое значение не должно отличаться от старого более чем на 20 %.

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

· Частным случаем такого ограничения является ограничение атрибута.

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

Пример : при измерении температуры очередное значение не должно отличаться от скользящего среднего Mx (текущего математического ожидания) на некоторую величину e. Все значения не попавшие в диапазон [ M x - e, M x + e] отбрасывают.

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

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

Для отложенного ограничения имеет значение следующее понятие:

· Логический элемент работы - непрерывное управление данными, при котором БД из одного целостного состояния переводится в другое целостное состояние. Этот прием еще называют транзакцией.

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