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

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

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

2-аянормальная форма (2НФ) отношения. Определение полной функциональной зависимости и 2НФ. Характеристика отношения во 2НФ. Алгоритм приведения ко 2НФ. Теорема Хита. Примеры.

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

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

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

2NF - вторая нормальная форма.

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

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

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

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

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

Теорема Хита

Пусть дано отношение .

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

3-я нормальная форма (3НФ) отношения. Определение транзитивной зависимости и 3НФ.Алгоритм приведения к 3НФ.Нормальная форма Бойса-Кодда (НФБК).Определение и алгоритм приведения к НФБК. Характеристика отношения в 3НФ и в НФБК. Примеры.

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

Для объяснения понятия функциональной зависимости, рассмотрим следующий пример.

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

Сессия (№ зачетной книжки , Фамилия, Имя, Отчество, Предмет , Оценка);

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

Однако, помимо ограничения уникальности, связанной с этим ключом, на отношение непременно должно быть наложено то условие, что одна зачетная книжка выдается обязательно одному конкретному человеку и, следовательно, в этом отношении кортежи с одинаковым номером зачетной книжки должны содержать одинаковые значения атрибутов «Фамилия», «Имя» и «Отчество».

Если у нас имеется следующий фрагмент какой-то определенной базы данных студентов учебного заведения после какой-то сессии, то в кортежах с номером зачетной книжки 100, атрибуты «Фамилия», «Имя» и «Отчество» совпадают, а атрибуты «Предмет» и «Оценка» – не совпадают (что и понятно, ведь в них речь идет о разных предметах и успеваемости по ним). Это значит, что атрибуты «Фамилия», «Имя» и «Отчество» функционально зависят от атрибута «№ зачетной книжки», а атрибуты «Предмет» и «Оценка» функционально не зависят.

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

Теперь дадим строгое определение функциональной зависимости.

Определение : пусть X, Y – подсхемы схемы отношения S, определяющие над схемой S схему функциональной зависимости X > Y (читается «X стрелка Y»). Определим ограничения функциональной зависимости inv > Y> как утверждение о том, что в отношении со схемой S любые два кортежа, совпадающие в проекции на подсхему X, должны совпадать и в проекции на подсхему Y.

Запишем это же определение в формулярном виде:

Inv > Y> r (S ) = t 1 , t 2 ? r (t 1 [X ] = t 2 [X ] ? t 1 [Y ] = t 2 [Y ]), X , Y ? S;

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

Интересно заметить, что в случае функциональной зависимости Y от X, говорят также, что X функционально определяет Y или что Y функционально зависит от X. В схеме функциональной зависимости X > Y подсхема X называется левой частью, а подсхема Y – правой частью.

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

Конец определения .

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

Inv <K > S > r (S ) = ? t 1 , t 2 ? r (t 1 [K ] = t 2 [K ] > t 1 (S ) = t 2 (S )), K ? S ;

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

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

{№ зачетной книжки} > {Фамилия, Имя, Отчество};

{№ зачетной книжки, Предмет} > {Оценка};

2. Правила вывода Армстронга

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

Хорошим примером таких специальных правил являются правила вывода Армстронга.

Но прежде чем приступать к анализу самих правил вывода Армстронга, введем в рассмотрение новый металингвистический символ «+», который называется символом метаутверждения о выводимости . Этот символ при формулировании правил записывается между двумя синтаксическими выражениями и свидетельствует о том, что из формулы, стоящей слева от него, выводится формула, стоящая справа от него.

Сформулируем теперь сами правила вывода Армстронга в виде следующей теоремы.

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

Правило вывода 1. + X > X;

Правило вывода 2. X > Y+ X ? Z > Y;

Правило вывода 3. X > Y, Y ? W > Z + X ? W > Z;

Здесь X, Y, Z, W – произвольные подсхемы схемы отношения S. Символ метаутверждения о выводимости разделяет списки посылок и списки утверждений (заключений).

1. Первое правило вывода называется «рефлексивность » и читается следующим образом: «выводится правило: “X функционально влечет за собой X”». Это самое простое из правил вывода Армстронга. Оно выводится буквально из воздуха.

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

2. Второе правило вывода называется «пополнение » и читается таким образом: «если X функционально определяет Y, то выводится правило: “объединение подсхем X и Z функционально влечет за собой Y”». Правило пополнения позволяет расширять левую часть ограничения функциональных зависимостей.

3. Третье правило вывода называется «псевдотранзитивность » и читается следующим образом: “если подсхема X функционально влечет за собой подсхему Y и объединение подсхем Y и W функционально влекут за собой Z, то выводится правило: «объединение подсхем X и W функционально определяют подсхему Z»”.

Правило псевдотранзитивности обобщает правило транзитивности, соответствующее частному случаю W: = 0. Приведем формулярную запись этого правила:

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

Правило вывода 1. inv X> r(S);

Правило вывода 2. inv Y> r(S) ? inv Y> r(S);

Правило вывода 3. inv Y> r(S) & inv Z> r(S) ? inv Z> r(S);

Проведем доказательства этих правил вывода.

1. Доказательство правила рефлексивности следует непосредственно из определения ограничения функциональной зависимости при подстановке вместо подсхемы Y – подсхемы X.

Действительно, возьмем ограничение функциональной зависимости:

Inv Y> r(S) и подставим в него X вместо Y, получим:

Inv X> r(S), а это и есть правило рефлексивности.

Правило рефлексивности доказано.

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

Первая диаграмма – это диаграмма посылки:

посылка: X > Y

Вторая диаграмма:

заключение: X ? Z > Y

Пусть кортежи равны на X ? Z. Тогда они равны на X. Согласно посылке они будут равны и на Y.

Правило пополнения доказано.

3. Доказательство правила псевдотранзитивности также проиллюстрируем на диаграммах, которых в этом конкретном случае будет три.

Первая диаграмма – первая посылка:

посылка 1: X > Y

посылка 2: Y ? W > Z

И, наконец, третья диаграмма – диаграмма заключения:

заключение: X ? W > Z

Пусть кортежи равны на X ? W. Тогда они равны и на X, и на W. Согласно Посылке 1, они будут равны и на Y. Отсюда, согласно Посылке 2, они будут равны и на Z.

Правило псевдотранзитивности доказано.

Все правила доказаны.

3. Производные правила вывода

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

Что это за правила, как они получаются?

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

Необходимо специально отметить, что эти самые произвольные правила являются «производными» именно от пройденных нами ранее правил вывода Армстронга.

Сформулируем производные правила вывода функциональных зависимостей в виде следующей теоремы.

Теорема.

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

Правило вывода 1. + X ? Z > X;

Правило вывода 2. X > Y, X > Z + X ? Y > Z;

Правило вывода 3. X > Y ? Z + X > Y, X > Z;

Здесь X, Y, Z, W, так же как и в предыдущем случае, – произвольные подсхемы схемы отношения S.

1. Первое производное правило называется правилом тривиальности и читается следующим образом:

«Выводится правило: “объединение подсхем X и Z функционально влечет за собой X”».

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

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

2. Второе производное правило называется правилом аддитивности и читается следующим образом: «Если подсхема X функционально определяет подсхему Y, и X одновременно функционально определяет Z, то из этих правил выводится следующее правило: “X функционально определяет объединение подсхем Y и Z”».

3. Третье производное правило называется правилом проективности или правилом «обращение аддитивности ». Оно читается следующим образом: «Если подсхема X функционально определяет объединение подсхем Y и Z, то из этого правила выводится правило: “X функционально определяет подсхему Y и одновременно X функционально определяет подсхему Z”», т. е., действительно, это производное правило является обращенным правилом аддитивности.

Любопытно, что правила аддитивности и проективности применительно к функциональным зависимостям с одинаковыми левыми частями позволяют объединять или, наоборот, расщеплять правые части зависимости.

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

Проведем доказательства перечисленных произвольных правил вывода.

1. Доказательство правила тривиальности .

Проведем его, как и все последующие доказательства, по шагам:

1) имеем: X > X (из правила рефлексивности вывода Армстронга);

Правило тривиальности доказано.

2. Проведем пошаговое доказательство правила аддитивности :

1) имеем: X > Y (это посылка 1);

2) имеем: X > Z (это посылка 2);

3) имеем: Y ? Z > Y ? Z (из правила рефлексивности вывода Армстронга);

4) имеем: X ? Z > Y ? Z (получаем при помощи применения правила псевдотранзитивности вывода Армстронга, а потом как следствие первого и третьего шагов доказательства);

5) имеем: X ? X > Y ? Z (получаем, применяя правило псевдотранзитивности вывода Армстронга, а после следует из второго и четвертого шагов);

6) имеем X > Y ? Z (следует из пятого шага).

Правило аддитивности доказано.

3. И, наконец, проведем построение доказательства правила проективности :

1) имеем: X > Y ? Z, X > Y ? Z (это посылка);

2) имеем: Y > Y, Z > Z (выводится при помощи правила рефлексивности вывода Армстронга);

3) имеем: Y ? z > y, Y ? z > Z (получается из правила пополнения вывода Армстронга и следствием из второго шага доказательства);

4) имеем: X > Y, X > Z (получается, применением правила псевдотранзитивности вывода Армстронга, а затем как следствие из первого и третьего шагов доказательства).

Правило проективности доказано.

Все производные правила вывода доказаны.

4. Полнота системы правил Армстронга

Пусть F (S ) - заданное множество функциональных зависимостей, заданных над схемой отношения S.

Обозначим через inv <F (S )> ограничение, накладываемое этим множеством функциональных зависимостей. Распишем его:

Inv <F (S )> r (S ) = ?X > Y ?F (S ) [inv Y> r (S )].

Итак, это множество ограничений, накладываемое функциональными зависимостями, расшифровывается следующим образом: для любого правила из системы функциональных зависимостей X > Y, принадлежащего множеству функциональных зависимостей F (S ), действует ограничение функциональных зависимостей inv Y> r (S ), определенных над множеством отношения r (S ).

Пусть какое-то отношение r (S ) удовлетворяет этому ограничению.

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

Правило вывода 1. inv < X > X > r (S );

Правило вывода 2. inv Y> r (S ) ? inv ? Z > Y> r (S );

Правило вывода 3. inv Y> r (S ) & inv ? W > Z> r (S ) ? inv ? W > Z>;

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

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

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

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

Если записать только что сказанное в формулярном виде, то получим:

F (S ) ? F + (S ), [F + (S )] + = F + (S );

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

X > Y ? F + (S ) ? ?r (S ) [inv <F (S )> r (S ) ? inv Y> r (S )];

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

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

Метод нормальных форм

Преподаватель

Рис. 6.4. Исходное отношение ПРЕПОДАВАТЕЛЬ

Неявная избыточность проявляется в одинаковых окладах у всех преподавателей и в одинаковых надбавках к окладу за одинаковый стаж. Если оклад изменится с 500 руб. до 510руб., то это значение надо изменить у всех преподавателей. Если при этом будет пропущен Сидоров, то база станет противоречивой. Это пример аномалии редактирования отношения с неявной избыточностью.

Исключение избыточности состоит в нормализации отношений.

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

Атрибут В функционально зависит от атрибута А, если каждому значению А соответствует в точности одно значение В. Математически функциональная зависимость В от А обозначается записью А ® В. Это означает, что во всех кортежах с одинаковым значением атрибута а АТРИБУТ в БУДЕТ ИМЕТЬ ТАКЖЕ ОДНО И ТО ЖЕ ЗНАЧЕНИЕ. Атрибуты А и В могут быть составными – состоять из двух и более атрибутов. В отношении Преподаватель Функциональные зависимости следующие: ФИО ® Каф, ФИО ® Долж, Долж ® Оклад и др.

Функциональная взаимозависимость. Если существует функциональная зависимость вида А ® В и В ® А, то между А и В имеется взаимно однозначное соответствие, или функциональная взаимозависимость. Математически взаимозависимость обозначается как А « В или В « А.

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

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

Полная функциональная зависимость – зависимость неключевого атрибута от всего составного ключа. Например, атрибут ВидЗан находится в полной функциональной зависимости от составного ключа.

Атрибут С зависит от атрибута А транзитивно (существует транзитивная зависимость ), если для атрибутов А, В, С выполняются условия А ® В и В ® С, но обратная зависимость отсутствует. В примере транзитивной зависимостью связаны атрибуты:

ФИО ® Долж ® Оклад

В отношении R атрибут В многозначно зависит от атрибута А, если каждому значению А соответствует множество значений В, не связанных с другими атрибутами из R. Многозначные зависимости могут быть «один ко многим» (1:М), «многие к одному» (М:1) или «многие ко многим» (М:М), Обозначаемые соответственно: А Þ В, А Ü В и А Û В.

В рассматриваемом примере имеется многозначная зависимость М:М между атрибутами ФИО Û Предмет (один преподаватель может вести несколько предметов и один предмет могут вести несколько преподавателей).

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

Взаимно независимые атрибуты. Два или более атрибутов называются взаимно независимыми, если ни один из этих атрибутов не является функционально зависимым от других атрибутов. Математически отсутствие зависимости атрибута А от атрибута В обозначается как А Ø® В. Если имеет место А Ø® В и В Ø® А, то взаимная независимость обозначается А Ø= В.

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

Пример. Пусть задано отношение R со схемой R(А1, А2, А3) вида:

Априори известно, сто существуют функциональные зависимости:

А1®А2 и А2®А3.

Из анализа видно, что в отношении существуют еще зависимости:

А1®А3, А1А2®А3, А1А2А3®А1А2, А1А2®А2А3 и т.п..

В отношении отсутствует функциональная зависимость атрибута А1 от атрибута А2 и от атрибута А3, т.е.

А2 Ø® А1, А3 Ø® А1.

Отсутствие зависимости А1 от А2 объясняется тем, что одному и тому же значению атрибута А2 (21) соответствуют разные значения атрибута А1 (12 и 17).

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

В отношении Преподаватель можно вывести следующие функциональные зависимости:

ФИО ® Оклад

ФИО ® Долж

ФИО ® Стаж

ФИО ® Надб

ФИО ® Каф

Стаж ® Надб

Долж ® Оклад

Оклад ® Долж

ФИО. Предм. Группа ® Оклад

Рис. 6.5. Зависимости между атрибутами.

Предполагается, что один преподаватель в одной группе может проводить один вид занятий (лекции или лабораторные работы). ФИО – уникальны. Имеется зависимость ФИО ® Стаж, а обратное утверждение не верно, т.к. одинаковый стаж имеют несколько преподавателей. Относительно других зависимостей рассуждения аналогичны. Между должностью и окладом устанавливается взаимно однозначная зависимость.

Один преподаватель в одной группе по разным предметам может проводить разные виды занятий. Определение ВидаЗанятий связано с указанием ФИО, Предмета и Группы. Действительно, Петров М.И. в 256-й группе читает лекции и проводит лабораторные занятия, но лекции читает по СУБД, а лабораторные работы по Графике.

Зависимости между атрибутами ФИО, Предмет и Группа не выведены, т.к. они образуют составной ключ и не учитываются в процессе нормализации отношения (таблицы).

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

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

° Первая нормальная форма (1НФ);

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

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

° Усиленная третья нормальная форма, или нормальная форма Бойса-Кодда (БКНФ);

° Четвертая нормальная форма (4НФ);

° Пятая нормальная форма (5НФ).

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

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

Основной операцией метода декомпозиции является операция проекции.

Пример. Пусть в отношении R(A,B,C,D,E,…) имеется функциональная зависимость С ® D. Декомпозиция отношения R на два новых отношения R1(A, B,C,E,…) и R2(C,D) устранит функциональную зависимость атрибутов и переведет отношение R в следующую нормальную форму. Отношение R2 является проекцией отношения R на атрибуты C и D.

Исходное отношение Преподаватель имеет составной ключ ФИО, Предм, Группа и находится в 1НФ. Атрибуты Стаж, Надб, Каф, Долж, Оклад находятся в функциональной зависимости от части составного ключа – атрибута ФИО . Эта частичная зависимость приводит к явной и неявной избыточности данных, что создает проблемы их редактирования. Часть избыточности устраняется при переводе отношения во 2НФ.

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

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

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

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

Переведем отношение Преподаватель во 2НФ. В результате получим два отношения R1 и R2.

R1

Рис. 6.6. Отношения базы данных ПРЕПОДАВАТЕЛЬ во 2 НФ

В отношении R1 первичный ключ составной ФИО, Предм, Группа , в отношении R2 ключ – ФИО. В результате исключена явная избыточность данных о преподавателях. В R2 по-прежнему имеет место неявное дублирование данных.

Для дальнейшего совершенствования переведем отношения в 3НФ.

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

Цель нормализации

Нормализация - метод создания набора отношений с заданными свойствами на основе требований к данным, установленным в некоторой орга­низации.

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

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

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

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

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

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

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

Зависимость между атрибу­тами А и В можно схематически представить в виде диаграммы, показанной на рисунке 5.

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

Рисунок 5 - Диаграмма функциональной за­висимости

При наличии функциональной зависимости атрибут или группа атрибутов, распо­ложенная на ее диаграмме слева от символа стрелки, называется детерминантом (determinant). Например, на рис. 6.1 атрибут А является детерминантом атрибута В.

Концепция функциональной зависимости является центральным понятием про­цесса нормализации.

Объединение нескольких атрибутов в одно отношение выполняется не случайным образом. Данные, которые будут храниться в этом отношении, взаимосвязаны между собой. Эта взаимосвязь определяется множеством функциональных зависимостей между атрибутами отношения. Это означает, что значения одного атрибута зависят от значений других атрибутов, т. е. допустимы не любые сочетания значений атрибутов. Зависимости эти вытекают из ограничений предметной области. Например, в отношении Поставки существуют следующие ограничения:

· каждый поставщик имеет только один адрес,

· каждый поставщик поставляет товар по определенной цене,

· товары, поставленные разными поставщиками, могут быть распределены по разным складам, но товар одного наименования, поставляемый одним поставщиком, должен храниться только на одном складе,

· каждый склад имеет свой объем.

Эти ограничения являются зависимостями, которые можно сформулировать следующим образом:

· адрес функционально зависит от поставщика,

· цена функционально зависит от товара и поставщика,

· номер склада функционально зависит от товара и поставщика,

· объем функционально зависит от номера склада.

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

Пусть отношение r имеет схему R , X и Y – подмножества R . Отношение r удовлетворяет функциональной зависимости X→Y , если π Y (σ X=x (r)) имеет не более чем один кортеж для каждого значения xÎX , т. е. значения атрибутов X однозначно определяют значения атрибутов Y.

Функциональную зависимость будем обозначать следующим образом:

· Поставщик → Адрес,

· {Товар, Поставщик}→ Цена,

· {Товар, Поставщик}→ Склад,

· Склад → Объем.

А читаются они так:

· Поставщик определяет Адрес,

· Товар и Поставщик определяют Цену,

· Товар и Поставщик определяют Склад,

· Склад определяет Объем.

На языке функциональных зависимостей ключ для схемы R – это подмножество KÍR , такое, что K →R , и никакое собственное подмножество K¢ÍK этим свойством не обладает.

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

Сформулируем правила, по которым следует проводить де­компо­­зицию отношения. Этот процесс называется нормализацией, т. е. при­­ведением отношения к нормальной форме.

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

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

Например, атрибут ФИО является составным, состоит из трех данных: фамилии, имени и отчества.

Чтобы привести схему в 1НФ, нужно все составные атрибуты заменить простыми.

Чтобы избавиться от избыточности информации, хранящейся в базе данных, существуют вторая и третья нормальные формы.

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

Что такое неполная функциональная зависимость от ключа? Такая зависимость присутствует в отношении, если какой-либо атрибут, не входящий в ключ, функционально зависит от части атрибутов, входящих в ключ. Любой непервичный атрибут обязательно функционально зависит от всех первичных атрибутов по определению ключа отношения. А если какой-либо непервичный атрибут, кроме того, функционально зависит не от всех, а от части первичных атрибутов, то это и есть неполная функциональная зависимость.

Например, в отношении Поставка первичными атрибутами являются Товар и Поставщик . Атрибут Цена функционально полно зависит от ключа, а атрибут Адрес зависит от части ключа, т. е. только от атрибута Поставщик , это неполная функциональная зависимость. Значит, схема Поставки не находится во 2НФ.

Чтобы привести схему, находящуюся в 1НФ, ко 2НФ, нужно разбить ее на несколько схем:

· выполнить проекцию схемы R на первичные атрибуты и атрибуты, функционально полно зависящие от ключа, т. е. исключить непервичные атрибуты, которые неполно зависят от ключа,

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

В примере с отношением Поставки в результате приведения схемы ко 2НФ получатся два отношения:

Поставки_1 (Товар , Поставщик , Цена, Склад, Объем ),

Поставки_2 (Поставщик , Адрес ).

Однако информация об объеме склада продолжает дублироваться. Для устранения этого недостатка схемы существует третья нормальная форма.

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

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

Схема отношения Поставки_1 (Товар , Поставщик , Цена, Склад, Объем ) не находится в 3НФ, так как в ней присутствует транзитивная зависимость:

{Товар, Поставщик } → Склад , Склад → Объем .

Чтобы привести схему, находящуюся во 2НФ, в 3НФ, нужно:

· выполнить проекцию схемы R на первичные атрибуты и атрибуты, транзитивно не зависящие от ключа, т. е. исключить непервичные атрибуты, которые транзитивно зависят от ключа,

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

В примере с отношением Поставки_1 в результате приведения схемы к 3НФ получатся два отношения:

Поставки_1_1 (Товар , Поставщик , Цена, Склад ),

Поставки_1_2 (Склад , Объем ).

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

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

В рассмотренном примере в результате декомпозиции вместо одного отношения Поставки мы получили три новых отношения:

Поставки_1_1 (Товар , Поставщик , Цена, Склад ),

Поставки_1_2 (Склад , Объем ),

Поставки_2 (Поставщик , Адрес ).

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

Как вы заметили, схема в 3НФ избавляет базу данных от дублирования информации и аномалий обновления, но не всегда.

Рассмотрим отношение Лекции (Студент , Предмет , Преподаватель ), которое хранит информацию о том, какие предметы изучают студенты и кто ведет эти предметы. Предметная область накладывает следующие ограничения:

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

· каждый преподаватель ведет только один предмет, но каждый предмет может вести несколько преподавателей.

Из этих ограничений вытекают следующие функциональные зависимости:

· {Студент, Предмет} → Преподаватель;

· Преподаватель → Предмет.

Из функциональных зависимостей вытекает, что ключом отношения Лекции будет набор атрибутов {Студент , Предмет }.

Отношение Лекции находится в 3НФ. Но оно страдает аномалиями обновления. Если требуется удалить информацию о том, что Петров изучает Физику, то утратится информация о том, что профессор Серов преподает Физику. В то же время информация о том, что профессор Белый ведет Алгебру, дублируется.

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

Отношение находится в нормальной форме Бойса–Кодда (НФБК) , если оно находится в 3НФ и в нем отсутствуют зависимости первичных атрибутов от непервичных. Эквивалентное определение требует, чтобы все левые части функциональных зависимостей были потенциальными ключами.

Приведя отношение к НФБК, мы получим два отношения: Лекции_1 (Студент, Преподаватель ) и Лекции_2 (Преподаватель, Предмет ).

Многозначные зависимости

Атрибут X многозначно определяет атрибут Y в R (или Y многозначно зависит от X ), если каждому значению атрибута X соответствует множество (возможно, пустое) значений атрибута Y , никак не связанных с другими атрибутами R . То есть для наличия в отношении многозначной зависимости необходимо иметь как минимум три атрибута.

Многозначная зависимость обозначается двойной стрелкой: X→→Y .

Рассмотрим отношение Преподаватель (Номер , Имя_ребенка , Предмет , Должность ). Предметная область накладывает следующие ограничения:

· каждый преподаватель может иметь несколько детей,

· каждый преподаватель может вести несколько предметов,

· каждый преподаватель может занимать только одну должность,

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

Тогда отношение Преподаватель имеет две многозначные зависимости и одну функциональную:

· Номер→→Имя_ребенка,

· Номер→→Предмет,

· Номер→Должность.

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

Для избавления от этих аномалий необходимо привести отношение к четвертой нормальной форме.

Отношение находится в четвертой нармальной форме (4НФ ), если оно находится в нормальной форме Бойса–Кодда и в нем отсутствуют многозначные зависимости, которые не являются функциональными.

После приведения отношения Преподаватель к 4НФ мы получим три отношения:

Преподаватель_1 (Номер , Должность ),

Преподаватель_2 (Номер , Имя_ребенка ),

Преподаватель_3 (Номер , Предмет ).

Свойства декомпозиции