CLAIM – научно-образовательный кластер

Внимание! Некоторые математические знаки могут отображаться неправильно в браузерах, отличных от IE 5.0 и выше.

Филиппович Андрей

Принципы взаимных
функциональных зависимостей

Содержание

1. Введение.

2. Проблемы 3НФ и НФБК.

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

4. Заключение.

Литература.

1. Введение.

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

Теория нормализации (зависимостей) появилась одновременно с теорией реляционной алгебры. Коддом были предложены первые нормальные формы. Впоследствии, третья нормальная форма была уточнена и названа нормальной формой Бойса-Кодда (НФБК). Позже Фэйджином (Fagin) были предложены 4 и 5 нормальная формы, а также альтернативная доменно-ключевая нормальная форма [3, 23]. Существуют и другие нормальные формы, но наиболее популярными являются 3НФ и НФБК.

В основе теории нормализации лежат различные понятия зависимостей между атрибутами БД. В теории Кодда используется понятие функциональной зависимости (ФЗ), реляционный аналог математической функции. Рассмотрение основных вопросов статьи требует четкого определения понятия ФЗ, поэтом приведем формальное определение ФЗ из 6-ого издания книги Дейта [4]. Отметим сразу, что статья ориентирована на читателя, знакомого с основными понятиями реляционной алгебры и теории нормализации.

Пусть R — это отношение, а X и Y — произвольные подмножества множества атрибутов отношения R. Тогда Y функционально зависимо от X (X® Y), тогда и только тогда, когда каждое значение множества X отношения R связано в точности с одним значением множества Y отношения R. Иначе говоря, если два кортежа отношения совпадают по X [t₁(X) = t₂(X)], то они также совпадают и по Y [t₁(Y) = t₂(Y)].

Проектирование схемы базы данных начинается с определения универсального отношения, в которое входят все атрибуты. Для предметной области задается множество ограничений с помощью функциональных, многозначных и других зависимостей. Для вывода новых ФЗ или сокращения их числа используются правила Армстронга. Однако, свободно применять правила Армстронга можно только для проектируемой БД, не имеющей данных [14].

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

Приведение отношений в 3НФ и НФБК направлено на избавление от транзитивных зависимостей (A® B, B® C => A® C). 3НФ позволяет удалить транзитивные зависимости с использованием неключевых атрибутов. В НФБК запрещаются транзитивные зависимости среди ключевых атрибутов.

Наиболее наглядное и простое определение 3НФ и НФБК дает Заниоло [26].

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

1) K Н X , 2) A О K

Для проектирования отношений с использованием ФЗ наиболее часто используют алгоритмы декомпозиции и синтеза. Одним из самых простых алгоритмов синтеза предложен Ульманом [19]:

1. Получение неприводимого (нередуцируемого) справа покрытия ФЗ. Для этого используется правило декомпозиции Армстронга. В результате каждая ФЗ имеет в правой части только один атрибут.

" (X® A) (X Н R, A О R)

2. Получение неизбыточного покрытия. ФЗ исключается из покрытия, если для нее соблюдается следующее условие:

(F–{X® A})⁺=F⁺ => F= F–{X® A}

3. Получение неприводимого (нередуцируемого) слева покрытия ФЗ. Для этого каждая ФЗ проверяется на возможность удаления атрибутов из левой части без изменения замыкания покрытия.

" (X® A), " (B Н X) AО (X-B)⁺ => (X-B)® A

4. Декомпозиция отношения. Для обеспечения свойства сохранения зависимостей отношение декомпозируется на отношения, содержащие охват (все атрибуты) каждой из ФЗ. Количество отношений равняется количеству ФЗ.

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

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

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

F = { AB® C, A® B, C® B }

Если полностью выполнить первые 3 этапа алгоритма, то получим следующее покрытие:

F = { A® C, A® B, C® B }

Полученное покрытие является избыточным, т.к. из него можно исключить транзитивную ФЗ A® B. Чтобы преодолеть этот недостаток следует после выполнения третьего этапа еще раз выполнить второй этап или сначала выполнить 3-ий этап, а потом — 2-ой.

Еще одним недостатком алгоритма Ульмана является порождение схемы базы данных с избыточным количеством отношений. Например, для набора ФЗ (A® B, A® C, A® D) будет порождено три отношения (AB, AC, AD) с одинаковым ключом A. Причиной избыточности отношений является избыточность ФЗ в покрытии. Минимальное покрытие по терминологии Ульмана предпочтительней называть каноническим (по терминологии Мейера). Под минимальным набором ФЗ следует понимать эквивалентное каноническое покрытие, которое содержит наименьшее количество ФЗ.

Пример 1.1.

F=(A® B, A® C, A® D), G=(A® BCD), F=G

F — каноническое покрытие; G — минимальное покрытие.

2. Проблемы 3НФ и НФБК.

Рассмотрим пример приведения отношения в третью нормальную форму, предложенный Ульманом[19] и проблемы, которые при этом возникают. Пусть Задана схема отношения R и множество функциональных зависимостей F. Звездочкой (*) помечены функциональные зависимости, которые отсутствуют в указанном примере.

Пример 2.1

R = (A, B, C, D, E, T), где A – читаемый курс, B – преподаватель,

C – час начала занятий, D – аудитория, E – студент, T – оценка по курсу.

F = {CD® B, CD® A, AC® D, CE® A, A® B, CB® D, AE® T, CE® D}

A® B — каждый курс ведет один преподаватель;

CD® A — в аудитории в один и тот же момент времени может читаться только один курс;

CB® D — преподаватель в один и тот же момент времени может находиться только в одной аудитории;

CE® D — студент в один и тот же момент времени может находиться только в одной аудитории

AE® T — по каждому курсу каждый студент имеет только одну оценку;

AC® D* — каждый курс в один и тот же момент времени может читаться только в одной аудитории;

CD® B*— в аудитории в один и тот же момент времени может быть один преподаватель;

CE® A* — каждый студент в один и тот же момент времени может слушать только один курс;

Для приведения схемы отношения в 3НФ необходимо найти минимальное (по терминологии Ульмана) покрытие множества функциональных зависимостей. В описываемом примере оно будет представлено следующим образом:

F = {A® B, CD® A, CB® D, AE® T, CE® D}

Далее, осуществим декомпозицию схемы отношения:

r ={AB, CDA, CBD, AET, CED}, K=CE

Данная схема находится в НФБК и декомпозируется из исходной схемы с сохранением зависимостей. Недостатком этой декомпозиции является зависимость проекций (по терминологии Риссанена [4, 24]). Отсюда следует, что схема может обладать аномалиями. Проиллюстрируем это на примере:

Рис.1. Противоречивость БД.

На рис.1. представлены три таблицы из полученной схемы отношений. Звездочками отмечены ключевые поля. Пусть в БД хранится информация, что в 10 часов в 12 и 13 аудиториях должны читаться курсы "Базы данных" и "Операционные системы" (CDA). Известно, что эти курсы читают соответственно преподаватели Иванов и Петров (AB). При этом оба преподавателя должны проводить занятия одновременно в одной аудитории (CBD). Данная информация является противоречивой, несмотря на то, что схема отношений находится в НФБК и все ФЗ соблюдены.

Представим теперь, что D — это номер посадочной полосы самолетов с номером рейса из B. По условиям, заданным набором ФЗ такая ситуация невозможна. И тем не менее, в БД, находящейся в НФБК с "сохранением" зависимостей содержится неутешительный приговор двум самолетам.

Рассмотрим другой случай. Пусть D — это сумма в размере 120000$ и ее нужно перечислить только на счет Иванова. Как видно из рис.1. эту сумму может также получить и Петров, а также десятки других сотрудников и это не будет противоречить структуре БД.

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

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

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

3.1. Определения и способы задания ВФЗ.

Определение 1. Взаимной функциональной зависимостью атрибутов A и B называется пара функциональных зависимостей вида B® A, A® B и обозначается как A« B.

Рассмотрим основное свойство ВФЗ. Из функциональной зависимости A® B вытекает утверждение 1. Кроме того, в отношении может существовать множество кортежей с разными значениями в атрибуте А и одинаковыми значениями в атрибуте B (утверждение 2):

(1) A® B у [t_i(A) = t_j(A)] => [t_i(B) = t_j(B)]

(2) [" t_i(B)] $ {t(A)} , |{t(A)}|і 1

Аналогично определим соотношения для ФЗ B® A:

(3) B® A у [t_i(B) = t_j(B)] => [t_i(A) = t_j(A)]

(4) [" t_i(A)] $ {t(B)} , |{t(B)}|і 1

Соединяя условия (1), (4) и (2), (3) получаем следующие утверждения:

(5) [" t_i(A)] $ {t(B)} , |{t(B)}|=1

(6) [" t_i(B)] $ {t(A)} , |{t(A)}|=1

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

Для задания ВФЗ в СУБД необходимо атрибуты A и B объединить в одном отношении (таблице) и задать уникальность каждого атрибута. Если части ВФЗ содержат более одного атрибута, то можно использовать первичный и альтернативный ключ (с обязательным заданием уникальности). Надо отметить, что алгоритмы нахождения минимального покрытия Мейера [11] и Бернштейна [21] учитывают ВФЗ, и используют их для сокращения размера покрытия.

Определение 2. Условной взаимной функциональной зависимостью атрибутов A и B называется пара функциональных зависимостей вида СB® A, СA® B, где С — набор атрибутов (условие) такой, что Сщ ® AB. Будем обозначать УВФЗ как С|A« B, при этом C будем называть условием, а A« B — основой УВФЗ.

Смысл УВФЗ заключается в том, что при определенных условиях атрибуты основы находятся во взаимной функциональной зависимости. Из функциональной зависимости CA® B вытекает утверждение 7 и 8:

(7) CA® B у [t_i(C) = t_j(C)]&[t_i(A) = t_j(A)] => [t_i(B) = t_j(B)]

(8) [" t_i(B)] $ {t(СA)} , |{t(СA)}|і 1

Аналогично определим соотношения для ФЗ СB® A:

(9) СB® A у [t_i(C) = t_j(C)]&[t_i(B) = t_j(B)] => [t_i(A) = t_j(A)]

(10) [" t_i(A)] $ {t(СB)} , |{t(СB)}|і 1

Соединяя условия (7-10) и фиксируя значение атрибута С, получаем следующие утверждения:

(11) [" t_i(A)] $ {t(B)} , |{t(B)}|=1

(12) [" t_i(B)] $ {t(A)} , |{t(A)}|=1

Основным свойством УВФЗ является взаимная однозначность значений для атрибутов основы при совпадении значений в атрибутах условия, т.е. для каждого значения атрибутов условия кортеж должен иметь уникальные значения атрибутов основы.

Существует несколько способов задать УВФЗ. Можно ввести понятие условного ключа или условной уникальности. Проиллюстрируем эти понятия. Пусть имеется условная взаимная зависимость (УВФЗ) такая, что условием является набор атрибутов C, атрибуты B и D входят во ВФЗ. Тогда при фиксированном значении атрибутов из С значения атрибутов B и D являются уникальными. Для пояснения приведем пример:

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

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

CREATE VIEW UslFD AS

SELECT Pse1.*

FROM table1 AS Pse1, table1 AS Pse2

WHERE (Pse1.C= Pse2.C) & (Pse1.A<> Pse2.A) & (Pse1.B<> Pse2.B)

При наборе условных атрибутов (C1,.. Cn) конструкция Where изменится:

WHERE (Pse1.C1= Pse2.C1) &(Pse1.C2= Pse2.C2) &…& (Pse1.Cn= Pse2.Cn)

& (Pse1.A<> Pse2.A) & (Pse1.B<> Pse2.B)

Альтернативой может послужить общее ограничения на целостность БД.

CREATE ASSERTION UslFD CHECK (

SELECT Pse1.*

FROM table1 AS Pse1, table1 AS Pse2

WHERE (Pse1.C= Pse2.C) & (Pse1.A<> Pse2.A) & (Pse1.B<> Pse2.B) )

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

3.2. Аксиомы и правила преобразования ВФЗ.

Утверждение 1. Любая УВФЗ может быть преобразована во ВФЗ по правилу (C| A « B у CA « CB). Таким образом, УВФЗ может рассматриваться как частный случай ВФЗ. С другой стороны ВФЗ можно считать частным случаем УВФЗ с пустым условием.

Утверждение позволяет рассматривать ВФЗ и УВФЗ как эквивалентные понятия и применять существующие подходы и алгоритмы для их поиска. В определении УВФЗ на атрибуты условия накладываются ограничение (Сщ ® AB). Если его ослабить, то можно получить вырожденные УВФЗ:

CA® B у CA| A« B

С® AB у C| A« B

Утверждение 2. Набору ВФЗ всегда соответствует множество ФЗ. Следовательно, на основании аксиом Армстронга для ФЗ можно сформулировать аксиомы для преобразования ВФЗ и УВФЗ.

А1. Рефлексивность и самоопределение. Аксиома рефлексивности для ВФЗ вырождается в аксиому самоопределения. Для УФВЗ может существовать рефлесивность условия и атрибутов основы. Сформулируем правила рефлексивности для атрибутов основы.

BН A, AН B => A=B => B« A

A« B, BМ M, A® M => M« A

C| A« B, BМ M, CA® M, Cщ ® M => C| M« B

Аксиому рефлексивности условия можно сформулировать следующим образом: более простые УВФЗ порождают более сложные. Если имеется две УВФЗ такие, что множество условных атрибутов одной зависимости входит во множество условных атрибутов другой зависимости, то такая УВФЗ является более простой:

C|A« B, CН D, Dщ ® AB => D|A« B

А2. Дополнение. Правило дополнения условия для УВФЗ аналогично правилу рефлексивности, поэтому рассмотрим только правила преобразования основы.

A« B => AC« BC

C|A« B, Cщ ® D => C|AD« BD

А3. Транзитивность.

A« B, B« C => A« C => A« B« C

C|A« B, E|B« D => CE|A« D => CE|A« B« D

А4. Декомпозиция.

A« BС, B® A, C® A => A« B, A« С

D|A« BС, DB® A, DC® A => D|A« B, D|A« С

A5. Объединение.

A« B, A« С => A« BС

D|A« B, E|A« С, DEщ ® AB => DE|A« BС

A6. Композиция.

A« B, C« D => AC« BD (AD« BC)

E| A« B, F| C« D, DEщ ® ABCD => EF|AC« BD (EF|AD« BC)

Далее сформулируем несколько дополнительных правил, которые могут быть использованы для преобразования УВФЗ.

R1. Перемещение атрибутов. Атрибуты условия в УВФЗ можно перемещать в основу. При этом они должны быть перемещены в обе части основы. Обратное утверждение также верно: если в обеих частях основы УВФЗ или ВФЗ имеются общие атрибуты, то их можно переместить в условие.

CD| A« B у C|DA« DB (Dщ ® AB)

R2. Удаление атрибутов. Если в основе имеется подмножество атрибутов, которое функционально зависит от условия, то его можно удалить.

C| AD« B, C® D => C| A« B

Доказательство: Преобразуем УВФЗ к множеству ФЗ:

C| AD« B у {CAD® B, CB® AD}у {CAD® B, CB® A, CB® D}

Добавим к полученному множеству ФЗ C® D и приведем к каноническому или минимальному покрытию (редуцированному и неизбыточному)

{CAD® B, CB® A, CB® D, C® D}= {CA® B, CB® A, C® D}

В минимальном покрытии выделим УВФЗ C| A« B.

R3. Замена атрибутов. Если в множестве ФЗ существует УВФЗ C| A« B, то во всех функциональных зависимостях, в которых присутствует набор условных атрибутов С можно заменить A на B или наоборот.

Рассмотрим преобразования для примера 2.1:

F = {CD® B, AC® D, CE® A, A® B, CD® A, CB® D, AE® T, CE® D}

CD® B & CB® D => B® D & D® B => C| D« B

Выберем все зависимости, в которых присутствует C

CD® B, AC® D, CE® A, CD® A, CB® D, CE® D

Заменим B на D и получим.

CD® D, AC® D, CE® A, CD® A, CD® D, CE® D

Сократим одинаковые зависимости (CD® D).

 © НОК CLAIM, 2006-2012. Замечания, вопросы и сведения об ошибках просим сообщать в форуме или присылать администратору сайта.