Функциональные зависимости. Декомпозиция отношений, транзитивные зависимости.

 

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

Определение:

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

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

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

Некоторые функциональные зависимости могут быть нежелательны.

Определение:

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

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

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

· не должны появляться ранее отсутствовавшие кортежи;

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

Декомпозиция получается приведением к получению двух отношений из одного.

Например, было R(X,Y,Z), а в результате декомпозиции получили два R1(X,Y), R2(Y,Z).

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

Пусть R – отношение, не находящееся в НФБК. Пусть aj зависит от ai (ai ® aj). Эта зависимость препятствует нахождению отношения в НФБК. Пусть ai – некоторый атрибут, детерминант, но не являющийся возможным ключем. Отношение R(a1,…,ai,…,aj) разбивают на два

R1 (a1,…,ai,…,aj-1) и R2(ai,aj)

Отношение R2 называется проекцией отношения R.

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

Теория реляционных баз данных говорит, что результаты запроса будут совпадать, если декомпозиция выполнена способом, при котором соединение R1 и R2 дает в точности исходное соотношение R – это декомпозиция без потерь.

Если естественное соединение R1 и R2 в итоге дает больше кортежей, чем в R – то это декомпозиция с потерями.

Отсутствие потерь при декомпозиции отношения R(X,Y,Z) в R1(X,Y), R2(Y,Z) гарантируется при условии, что от общего атрибута (Y) функционально зависит хотя бы один атрибут из двух оставшихся.

 

Проектирование с использованием метода сущность - связь.

 

Общие положения:

“Сущность-связь” – это модель предметной области, которая позволяет моделировать объекты ПО и их взаимоотношения.

В основе модели лежит три конструктивных элемента:

-Сущность;

-Атрибут;

-Связь;

Сущность - это некоторая абстракция реально существующего объекта, процесса и явления, о котором необходимо хранить информацию в системе.

Атрибут – это характеристика сущности, описание свойств сущности.

КНИГА

Пример:

Сущьность:→

Атрибуты: → Название, фамилия автора, год издания.

Связи – это средства, с помощью которых представляются отношения между сущностями.

Пример:

Это диаграмма ER-типа.

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

Важными характеристиками связи между сущностями является степень связи и класс принадлежности. С понятием степень связи мы уже сталкивались при рассмотрении связей между атрибутами. Между сущностями существует также 4 типа степени связи:

1:1, 1:М, М:1, М,N.

Пример:

1:1 – Преподаватель читает один курс

1:М – Преподаватель читает много курсов.

М:1 – Много преподавателей читают один курс.

M:N – Много преподавателей читают много курсов.

М:1 –много преподавателей читает один курс (редко встречается).

М:N – много преподавателей читает много курсов (в МИРЭА такого нет).

Класс принадлежности сущности определяется правилами регламентирующими деятельность организации.

Он может быть:

-обязательным;

-необязательным;

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

Степень: 1:1

Класс принадлежности: ни одна из сущности не является обязательной.

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

В нашем примере сущность преподаватель имеет первичный ключ – номер преподавателя → НК, курс → номер курса→ НК

Пример 2

Степень 1:1

Класс принадлежности: сущность ПРЕПОДАВАТЕЛЬ является обязательным, а класс принадлежности сущности КУРС является необязательным(Это означает, что каждый преподаватель обязательно читает курс, но не все курсы читаются преподавателями).

Пример 3

Степень: 1:n

Класс принадлежности сущности ПРЕПОДАВАТЕЛЬ – необязательный, КУРС – обязательный(Это означает, что ене каждый преподаватель читает курс т.е. не все преподаватели загружены работой, но каждый курс читается преподавателем).

Получение отношений из ER- диаграмм для бинарных связей.

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

А) Построение предварительных отношений для бинарных связей степени 1:1.

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

Для ER-диаграммы:

Проектируемое отношение назовем Преподаватели с ключом НП и пополним его атрибутами: фамилия преподавателя –ПФАМ

Телефон преподавателя –ПТЕЛ

К сущностям курс добавим один атрибут наименование курс – имя_курса.

Тогда схема отношения будет иметь вид: ПРЕПОДАВАТЕЛЬ(НД, ПФАМ, ПТЕЛ,НК)

Постоим структуру функциональных связей между атрибутами таблицы «Преподаватель»

Выводы: 1.Требуется дальнейшая декомпозиция в НФБК.

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

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

Пример:

Степень: 1:1

Класс принадлежности сущности преподаватель – необязательный, Класс принадлежности сущности курс – обязательный.

По правилу 2 получаем следующие схемы отношения ПРЕПОДАВАТЕЛЬ(НП, ПФАМ, ПТЕЛ), КУРС(НК, ИМЯ_КУРСА, НП)

Или:

Степень: 1:1

Класс принадлежность: Преподаватель – обязательный, курс – необязательный.

По правилу 2:

ПРЕПОДАВАТЕЛЬ(НП, ПФАМ, ПТЕЛ,НК), КУРС(НК, ИМЯ_КУРСА)

Правило3: Если степень бинарной связи равна 1:1 и класс принадлежности одной из сущностей не является обязательным, то необходимо использовать три отношения:

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

Пример:

По правилу 3:

Преподаватель(НП,ПФАМ,ПТЕЛ)

Курс(НК,ИМЯ_КУРСА)

Читает(НП,НК)

Б) Построение предварительных отношений для бинарных связей степени 1:М

Для бинарных связей степени 1:М формулируются два правила по классу принадлежности m-связной сущности.

Правило4: Если степень бинарной связи равна 1:m и класс принадлежности m-связной сущности является обязательным,то достаточным является использование двух отношений, по одному на каждую сущность, при условии, что ключ каждой сущности служит в качестве первичного ключу для соответствующего отношения. Дополнительно ключ 1- связной сущности должен быть добавлен как атрибут в отношение отводимое

m-связной сущности.

Пример.

По правилу 4

Курс(НК,ИМЯ_КУРСА,НП)

Преподаватель(НП, ПФАМ,ПТЕЛ)

Правило5: Если степень бинарной связи равна 1:m и класс принадлежности m-связной сущности является необязательным, то необходимо формирование трех отношений: по одному для каждой сущности, причем ключ каждой сущности служит ключом соответствующего отношения и одного отношения для связи. Связь должна иметь среди своих атрибутов ключ от каждой сущности.

Пример:

По правилу 5:

Преподаватель(НП, ПФАМ, ПТЕЛ)

Курс(НК,,ИМЯ_КУРСА)

Читает(НК, НП)

В) Построение предварительных отношений для бинарных связей степени m:n

Правило 6:Для всех классов принадлежности сущностей. Если степень бинарной связи равна m:n, то вне зависимости от класса принадлежности сущности, для хранения данных необходимо три отношения: по одному для каждой сущности, причем ключ каждой сущности используется в качестве первичного ключа соответствующего отношения, и одного отношения для связи. Последнее отношение должно иметь сложный ключ соответствующий ключу каждой сущности.

Пример:

По правилу 6:

Преподаватель(НП, ПФАМ, ПТЕЛ)

Курс(НК, ИМЯ_КУРСА)

Читает(НП, НК)

НП и НК – сложный ключ

 

1, 2, 3 и 4 нормальные формы. Нормальная форма Бойса-Кодда.

 

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

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

В теории реляционных баз данных обычно выделяется следующая последовательность нормальных форм:

• первая нормальная форма (1NF);
• вторая нормальная форма (2NF);
• третья нормальная форма (3NF);
• нормальная форма Бойса-Кодда (BCNF);
• четвертая нормальная форма (4NF);
• пятая нормальная форма, или нормальная форма проекции-соединения (5NF или PJ/NF).

Основные свойства нормальных форм:

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

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

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