Общее представление о базе данных (стр. 5 )

­ Все значения атрибутов атомарны.

64. Декомпозиция без потерь. Теорема Хеза.

Очевидно, что процедура нормализации имеет смысл только в том случае, если дробление (разбиение) декомпозиций исходного отношения будет удовлетворять требованиям т к вполне очевидно, что любое отношение имеет огромное число вариантов декомпозиций. Важнейшим критерием процесса нормализации является декомпозиция без потерь. Суть которого состоит в том, что декомпозиция должна быть обратимой. Под потерей понимается избыток информации. В проекционно–соединительной нормализации прямой операцией является проекция, обратной – соединение. Это значит что декомпозиция без потерь означает получение таких проекций исходного отношения , что обратная операция соединения в точности приводила бы к исходному. С другой стороны, хорошо известно, что проблема декомпозиций без потерь тесно связана с концепцией фз. например, рассмотрим отношение S(S#, Status, City). Мы можем получить такие декомпозиции:

А) SST(S#, Status), SC(S#, City)

Б) SST(S#, Status), STC(Status, City)

S# Status City

S3 30 Пенза

S5 30 Пенза

А) S# Status

S3 30

S5 30

S# City

S3 Пенза

S5 Пенза

Б) S# Status

S3 30

S5 30

Status City

30 Пенза

30 Пенза

Рассмотрим подробно. В случае а) никакая информация при декомпозиции не утрачена. В случае б) наоборот часть информации утрачена, поскольку оба поставщика имеют статус 30 и не понятно в каком город они расположены. Возникает вопрос: почему в случае а) информация сохранена в полном объеме и более того при обратном соединении отношений по ключу S# мы в точности получим исходное, а в случае б) нет? Т е действительно обратимость декомпозиции означает, что исходное отношение по определению должно быть равно соединению его проекций. Пусть и – произвольные проекции некоторого отношения . Какие условия должны быть выполнены для того, чтобы при обратном соединении и в точности совпадало с . Ответом на этот вопрос является теорема Хеза. Пусть R – отношение с атрибутами А, В, С. Тогда если R удовлетворяет фз , то R будет равно соединению его проекций.

R=( А, В)UNION( А, С).

Очевидно теорема Хеза устанавливает явную связь между процедурой декомпозиции и декомпозиции без потерь через фз. Например, возвращаясь к а) и б) мы видим, что исходное отношение S удовлетворяет фз S# Status, S# City и не удовлетворяет фз Status City

65. Вторая нормальная форма. Примеры.

Рассмотрим отношение FIRST (S#, STATUS, CITY, P#, Q). По определению это отношение находится в 1 НФ т. к. каждый атрибут определен на домене.

Предположим, что это отношение имеет потенциальный ключ PRIMARY KEY (S#,P#). Это означает, что диаграмма ФЗ отношения FIRST будет иметь вид:

Однако кроме первичного ключа мы имеем объявленную ранее зависимость CITY –> STATUS. В результате мы получаем диаграмму, в которой ФЗ состоит не только из первичного ключа, но и из ключевых атрибутов. Поэтому в отношении FIRST фактически нарушаются оба условия определения 1. Отсюда следует ожидать, что отношение FIRST является «плохим» в смысле наличия избыточности и аномалий. Действительно рассмотрим произвольное тело отношения FIRST

Очевидная избыточность в отношении FIRST приводит к различным аномалиям обновления. Для определенности рассмотри избыточность типа поставщик – город, которая очевидно вытекает из ФЗ S#–>CITY

1. INSERT (аномалия вставки)

Ограничение S#–>CITY означает, что нельзя вставить данные о том, что некоторый поставщик находится в некотором городе до тех пор, пока этот поставщик не поставит хотя бы один товар (P# не NULL).

2. DELETE. Если удалить один из кортежей для некоторого поставщика в связи с отменой поставки товара, то может удалиться не только поставка товара, но и поставщик.

3. UPDATE. Название города для одного поставщика повторяется множество раз, т. е. данное повторение приводит к возникновению проблем при обновлении данных. Например, если поставщик S1 переходит из Самары в Томск, система вынуждена переправлять все строки. Либо эту проблему нужно искать с помощью поисковой системы либо вручную. Таким образом, решение рассмотренных выше проблем заключается в декомпозиции исходного отношения FIRST на несколько проекций.

Например:

SECOND (S#, STATUS, CITY) <– FIRST –> SP (S#, P#, Q)

Действительно, если рассмотреть теперь тело отношения SECOND

Легко проверить что отношение SECOND не испытывает тех проблем какие были отмечены в отношении FIRST. Действительно:

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

2. DELETE. Можно любую поставку из SP удалить и это же отразится в SECOND.

3. UPDATE. – любой поставщик, переехавший в другой город, потребует редактирования только одной строки.

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

Т. е. сравнивая диаграммы ФЗ в FIRST и диаграммы ФЗ SECOND и SP видно, что мы исключили зависимости, которые не были неприводимыми. В результате можно утверждать, что отношение SECOND и SP находится в более высокой степени отношения, чем FIRST. Действительно

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

Очевидно, что отношение SECOND и SP находится в 2 НФ, а отношение FIRST в 2 НФ не находится.

Без доказательства можно утверждать что любое отношение в1 НФ всегда можно привести к декомпозиции отношений во 2 НФ.

Первый этап нормализации

Из рассмотренных примеров интуитивно следует, что на первом этапе процедуры нормализации (перехода от 1 НФ к 2 НФ). Необходимо исключать приводимые ФЗ или другими словами искать (создавать такие проекции, в которых приводимые ФЗ будут удалены).

Пример:

R(A, B,C, D)

K={A, B}. A–>B.

Тогда согласно первому этапу процедуры нормализации это отношение следует заменить двумя проекциями

R1(A, D) K1={A}

R2(A, B,C) K2={A, B} и внешним ключом FK={A}, т. е. мы разделили исходное отношение отделив В.

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

66. Третья нормальная форма. Примеры.

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

ФЗ CITY –> STATUS является избыточным т. к. имеется транзитивная зависимость S# –> STATUS, таким образом, именно транзитивная зависимость является причиной аномалий отношения SECOND.

Упражнение: проверить наличие аномалий на избыточности данных типа CITY–STATUS.

Вновь, как и ранее, решение проблем аномалии обновления состоит в замене исходного отношения SECOND (S#, CITY, STATUS) двумя проекциями:

SC (S#, CITY)

CS (CITY, STATUS)

В результате получим тривиальные диаграммы ФЗ

Если записать тело отношений, то легко можно видеть

Таким образом, благодаря удалению транзитивной зависимости мы получили отношения SC и CS в 3 НФ, более того определение 3 НФ при условии, что отношение имеет только один потенциальный ключ, может звучать так:
Отношение находится в 3 НФ тогда и только тогда когда оно находится в 2 НФ и каждый не ключевой атрибут не транзитивно зависит от первичного ключа, отсюда можно сделать вывод о втором этапе процедуры нормализации (т. е. переход от 2 НФ к 3 НФ). На втором этапе нормализации необходимо избавится от всех транзитивных зависимостей или необходимо построить такие проекции исходного отношения, которые не будут содержать транзитивных зависимостей, при этом следует вновь подчеркнуть, что любое отношение в 2 НФ всегда можно привести к декомпозиции находящихся в 3 НФ. Например, рассмотри отношение R(A, B,C) K={A}, B –> C.

Тогда согласно второму этапу процедуры нормализации отношение R следует заменить двумя проекциями

R1(BC) K1={B}

R2(AB) K2={A}

FK={B}

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

67. Сохранение зависимостей.

Любое отношение имеет множество различных комбинаций декомпозиций. С одной стороны этапы нормализации 1 и 2 дают рекомендации, какие именно проекции следует выбирать, однако даже эти рекомендации не гарантируют однозначности.

Пример:

В отношении SECOND (S#, CITY, STATUS)

S# –> CITY

S# –> STATUS – транзитивно

CITY –> STATUS

Тогда на диаграмме ФЗ:

А) SC (S#, CITY), CS (CITY, STATUS)

Оказывается, имеет место и декомпозиция

В) SC (S#, CITY), CS (S#, STATUS)

Самое удивительное что проекция декомпозиции В тоже находится в 3 НФ. Однако по некоторым причинам декомпозиция В менее эффективна.

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

Действительно если рассмотреть диаграмму в которой зависимости проекций А отмечены сплошной стрелкой, а одна из зависимостей проекций В отмечена пунктиром. Это означает что после декомпозиции по А мы получаем абсолютно независимые проекции, в том смысле что любое обновление в каждой из проекций может быть выполнены совершенно независимо друг от друга, а в декомпозиции В обновление любых из двух проекций необходимо тщательно контролировать чтобы гарантировать отсутствие нарушений в зависимости CITY –> STATUS. Например если мы вводим двух поставщиков из одного города, они должны иметь одинаковый статус проекции декомпозиции в зависимости друг от друга т. е. ФЗ CITY –> STATUS превращается из ограничения на отношение в ограничение между отношениями В декомпозиция А наоборот транзитивная зависимость S# –> STATUS было ограничением между отношениями а теперь стало ограничением внутри отношений благодаря транзитивности сходной ФЗ. Концепция независимых проекций позволяет сформулировать критерий для выбора одной комбинации проекций из множества возможных. Поэтому в рассмотренных выше примерах можно теперь сказать, что декомпозиции с независимыми проекциями являются предпочтительней декомпозиций, в которых проекции зависимы.

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

во–первых:

Каждая ФЗ в отношении R является логическим следствием ФЗ в R1 и R2;

во–вторых: общие атрибуты проекций R1 и R2 образуют потенциальный ключ, по крайней мере, для одной из проекций.

Действительно в декомпозиции А обе проекции независимы, поскольку их общий атрибут CITY является первичным ключом в отношении CS, а каждая ФЗ в отношении SECOND либо находится в одной из проекций, либо является логическим следствием существующих. В декомпозиции В наоборот: две проекции зависимы поскольку зависимость CITY –> STATUS не может быть получена из ФЗ этих проекций, даже не смотря на то что их общий атрибут S# является потенциальным для общих проекций. 3–й вариант

С) SS (S#, STATUS), CS (CITY, STATUS)

Является неприемлемым, поскольку является декомпозицией с потерями.

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

68. Нормальная форма Бойса–Кодда. Примеры.

Отношение R(A1,A2...An) находится в НФБК тогда и только тогда когда каждая нетривиальная и неприводимая слева ФЗ обладает потенциальным ключом в качестве детерминанта.

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

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

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

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

Прежде чем рассмотрим примеры с несколькими потенциальными ключами убедимся что отношение FIRST, SECOND, которые находятся в 3 НФ также не находятся и в НФБК и наоборот убедимся что отношение SP, SC, CS – которые находятся в 3 НФ также находится и в НФБК.

Действительно отношение FIRST (S#, CITY, P#, STATUS, Q) содержит по крайней мере три детерминанта

S# –>

CITY –>

{S#, P#} –>

Из которых только S#, P# являются потенциальным ключом поэтому FIRST по определению не находится в НФБК.

Аналогично можно утверждать что отношение SECOND не находится в НФБК поскольку CITY не является потенциальным ключом и наоборот в отношение SP, SC, CS все детерминанты ФЗ являются потенциальными ключами.

Рассмотрим теперь отношение S (S#, SNAME, STATUS, CITY) в предположении, что имя поставщика является уникальным.

Это означает, что отношение S имеет 2 потенциальных ключа: S#, SNAME.

Предположим далее что теперь ФЗ CITY –> STATUS не выполняется, тогда диаграмма ФЗ будет иметь вид:

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

Наконец рассмотрим пример, в котором потенциальные ключи перекрываются.

В начале рассмотрим SSP (S#, SNAME, P#, Q) с введенным ранее допущением SNAME – уникальное, тогда отношение SSP имеет 2 потенциальных ключа {S#, P#}, {SNAME, P#}.

Эти потенциальные ключи очевидно пересекаются однако, это отношение не находится в НФБК т. к. включают 2 детерминанта S#, SNAME, которые являются потенциальными ключами этого отношения.

Действительно если рассмотрим произвольное тело этого отношения SP:

Из чего следует, что данное отношение страдает избыточностью данных именно благодаря ФЗ S# –> SNAME. Однако самое удивительное, что отношение SSP формально находится в 3 НФ, поскольку, согласно старому определению не требуется, чтобы атрибут был неприводимо зависим от любого потенциального ключа, если он сам является элементом некоторого потенциального ключа.

Таким образом, тот факт, что атрибут SNAME приводимо зависим от S#, P# игнорируется.

Для решения проблем аномалий обновления, очевидно, достаточно декомпозировать отношение SSP на 2 проекции:

А) SS (S#, SNAME), SP (S#, P#, Q)

Б) SS (S#, SNAME), SP1 (SNAME, P#, Q)

Все три проекции или обе декомпозиции находятся в НФБК и естественно, возникает вопрос: какая из этих декомпозиций лучше.

Исходя из здравого смысла декомпозиция А безусловно является «лучшей», т. к. снимается зависимость SNAME –> {P#, Q}.

Наконец рассмотрим отношение SJT (Student, JOB, Teacher)

Предположим что в этом отношении следующие правила целостности данных:

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

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

Например, тело отношения может быть таким:

Возникает вопрос: какие ФЗ выполняются в данном отношении? {S, J} –> T, T –> J

В данном примере есть 2 перекрывающихся потенциальных ключа т. к. {S, J} и {S, T} является являющиеся потенциальными ключами. Отношение SJT так же как и SSP не находится в 3 НФ. Легко увидеть некоторые аномалии обновления.

Например, если удалить предмет мат. анализ или алгебру то случайно удаляться и преподаватели.

Атрибут Т является детерминантом, но не потенциальным ключом.

Очевидно, что решение аномалий заключается в ликвидации ФЗ T –> J следовательно, получаем:

ST (S, T)

TJ (T, J)

Видно, что диаграммы этих ФЗ тривиальны и эти проекции находятся в НФБК.

Выводы

Процесс нормализации для «младших» НФ заканчивается НФБК. При этом каждый этап нормализации фактически предполагает, что n+1 НФ автоматически находится в n НФ, тогда как обратное утверждение не верно. Т. е. существует отношение находящееся в n НФ, но не находящееся в n+1 НФ. Однако существует доказательство, что любое отношение, находящееся в n НФ, может быть, путем декомпозиции на проекции, приведено к эквивалентной паре проекций, находящихся в n+1 форме.

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

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

Было показано, что именно ФЗ играет решающую роль в этом процессе. Например, теорема Хеза утверждает, что если некоторая ФЗ выполняется, то существует декомпозиция, выполняемая без потерь.

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

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

Рассмотрим отношение

CTX (Course, Teacher, teXts)

CTX (C, T, X)

Очевидно, что это ненормализованное отношение, т. к. Teacher, Texts – массивы. Очевидно, что в этом отношении никаких ФЗ кроме тривиальных (С –> С) нет. Поэтому перепишем данное отношение в 1 НФ.

Нормальное отношение СТХ означает, что любой кортеж {C, T, X} принадлежит телу отношения СТХ тогда и только тогда когда выполняются следующие ограничения:

IF THEN .

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

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

Но самое удивительное, что отношение СТХ формально находится в НФБК поскольку является полностью ключевым.

Возникает вопрос: какой же тип ограничений указанный выше в форме IF THEN необходимо ввести чтобы понять источник указанных аномалий. Оказывается в 1971 году Фейгином строго было доказано, что подобные проблемы в НФБК могут быть описаны с помощью многозначных зависимостей. Действительно в отношении СТХ можно выделить такие многозначные зависимости как:

Course –>–> Teacher

Course –>–> Texts

Т. е. многозначные зависимости можно рассматривать как обобщение ФЗ в том смысле, что любая ФЗ автоматически является многозначной, когда правая часть является одноэлементной. Обратное не верно, т. е. существуют МЗ, которые не являются функциональными, например МЗ Course –>–> Teacher означает, что с одной стороны для любого курса не существует одного преподавателя, т. е. ФЗ С–>T не выполняется, тем не менее, для любого курса существует вполне определенное множество преподавателей.

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

CT <– CTX (C, T, X) –> CX

Будем иметь:

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

Действительно, когда мы утверждаем, что любому курсу соответствует вполне определенное множество преподавателей, мы тем самым имеем ввиду, что для данного курса с и данного учебника x существует множество преподавателей t обязательно соответствующих паре {c, x}, т. е. с одной стороны любой кортеж {ctx} зависит от значения с и не зависит от значения x. А из второй многозначной зависимости следует, что, любой кортеж отношения СТХ зависит от с и совершенно не зависит от t. Именно поэтому формальное определение многозначной зависимости имеет вид

R(A, B,C) подмножества тогда и только тогда когда множество значений из В соответствующее любой паре {a, c} зависит только от а и не зависит от с.

Фейгином было показано, что если отношение R в точности состоит из атрибутов АВС, то МС А –>–> B выполняется тогда и только тогда когда выполняется A –>–> С.

Доказанная теорема позволяет утверждать, что МЗ всегда образует связанные пары, вот почему определение МЗ в символическом виде обычно записывают A –>–> B/C, например Course –>–> Teacher/Texts.

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

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

70. Четвертая нормальная форма. Примеры.

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

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

1. Отношение R(A, B,C) – подмножества атрибутов, тогда отношение R будет эквивалентно соединению ее проекций R1(AB), R2(AC), тогда и только тогда когда в этом отношении выполняется МЗ А –>–>B/C.

Вот почему согласно т. Фейгина и вводится определение 4 НФ.

Отношение R находится в 4 НФ тогда и только тогда, когда существует такие подмножества атрибутов {AB}, что выполняется не тривиальное МЗ А –>–> B, причем все остальные атрибуты отношения R функционально зависят от А. Другими словами: отношение R, находящееся в 4 НФ должно содержать только не тривиальные зависимости типа ФЗ и МЗ, причем вида k –> x. Отсюда можно вывести более простое определение:

Отношение – атрибуты находятся в 4 НФ если оно находится в НФБК и все МЗ отношения R являются ФЗ с детерминантами в виде потенциальных ключей.

Например, отношение CTX не смотря на то, что находится в НФБК в 4 НФ не находится, поскольку содержит МЗ, которая не только не является ФЗ, но и не может быть ФЗ от потенциального ключа.

Напротив, обе проекции CT и СХ находятся в 4 НФ, которая по сравнению НФБК избавила нас от аномалий, а значит, позволила получить более высокую форму нормализации.

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

71. Зависимости соединения.

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

Отношения будем называть n–декомпозируемым если для него не существует такого эквивалентного набора из n–1 проекций и существует эквивалентный набор из n проекций.

Рассмотрим в качестве примера отношение SPJ (S#,P#,J#).

Отношение SPJ является полностью ключевым в том смысле, что каждый кортеж в смысле отношений позволяет говорить об отсутствии ФЗ и МЗ а это значит что отношение SPJ формально находится в 4 НФ. Без обсуждения аномалий рассмотрим в этом отношении три проекции

Рассмотрим тела отношений:

Рассмотрим соединение проекций SP и PJ по атрибуту P#

SPJ1

Очевидно, что отношение SPJ1 не эквивалентно отношению SPJ, т. к. мы получили избыточность.

Аналогично если рассмотреть соединение других пар проекций. Соединение других пар так же приведет к не эквивалентному. Однако если дополнительно провести соединение отношений SPJ1 и JS по (S#,J#), то мы в точности получим SPJ, это означает, что SPJ является тридекомпозируемым.

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

Это сложное ограничение истинно, т. к. тройка S1, P1, J1 действительно находится в соединение проекций SP, PJ, JS, исходя из этого, можно сделать вывод:

Любая пара {S1P1} должна присутствовать в отношении SP тогда и только тогда когда кортеж {S1P1Jk}присутствует в отношении SPJ для некоторого отношения Jk. Аналогичное утверждение можно сделать для пар вида {P8,J8}и т. д. Это позволяет записать более простое ограничение: Если кортеж {S1P1J2}, {S2P1J1} и {S1P2J1} принадлежат SPJ то кортеж {S1P1J1} тоже принадлежит SPJ. Последнее ограничение, очевидно, выполняется для любых допустимых значений отношения SPJ, а это значит что приведенное выше ограничение является новым типом зависимости – циклическая. Действительно, если S1 связано с P1, а P1 с J1, а J1 с S1, то кортеж {S1P1J1} принадлежит SPJ. Поэтому имеет место утверждение, что отношение будет n–декомпозируемым, тогда и только тогда когда оно будет удовлетворять некоторому циклическому ограничению. Осталось выяснить какова практическая ценность циклического ограничения. Ответ содержится в следующем этапе процедуры нормализации. Зависимость соединения – елси отношение удовлетворяет циклическим ограничения, это означает что данное отношение равносильно соединению нескольких его проекций (больше двух). Другими словами это ограничение называется зависимость соединения, т. е. ЗС является таким же ограничением на структуру данных отношения как МЗ и ФЗ. Рассмотрим формальное определение ЗС: Пусть R является отношение с атрибутам A1,A2,...An, а A, B,...,Z – подмножество атрибутов. Тогда говорят, что отношение R удовлетворяет ЗС и обозначается *(A, B,...,Z) тогда и только тогда когда отношение R равносильно соединению соответствующих проекций по подмножествам атрибутов R(A1,A2,...An)=.

Например, если вернутся к отношению SPJ то можно утверждать что это отношение удовлетворяет *(SP, PJ, JS) или, что тоже самое – отношение SPJ является тридекомпозируемым. Как и с 4 НФ возникает следующий вопрос, а следует вообще проводить подобные декомпозиции?

Действительно в отношении SPJ наблюдается избыточность данных и аномалия обновления. Вывод: декомпозируемость отношений, в которых выполняется ЗС так же необходимо. По теории Фейгена при наличии МЗ дается критерий декомпозируемости. Оказывается, что ЗС и МЗ могут быть связаны между собой. Существует следующая теорема Фейгена.

Отношение R(A, B,C) удовлетворяет ЗС *(AB, AC) тогда и только тогда когда это отношение удовлетворяет МЗ A –>–> B/C, данную теорему можно рассматривать как еще одно определение МЗ. Отсюда следует, что МЗ частный случай ЗС. Либо PC – обобщение МЗ.

72. Пятая нормальная форма. Примеры.

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

Отсюда следует четвертый (пятый) этап процедуры нормализации. Т. е. необходимо отыскать такие ЗС которые не являются многозначными и ФЗ и провести декомпозицию на основе ЗС. Такой процесс может оказаться многоэтапным. Отсюда вытекает определение 5 НФ.

Отношение R находится в 5 ФН тогда и только тогда когда каждая ЗС в отношении R подразумевается потенциальным ключом. Отношения в 5 НФ часто называют проекционно–соединительной НФ. Фраза «ЗС подразумевается потенциальным ключом» означает, что любая зависимость обязательно должна быть основана на функциональных ключах. Чтобы разъяснить понятие ЗС рассмотрим отношение поставщиков S#, SNAME.

S(S#, SNAME, STATUS, CITY)

Это отношение удовлетворяет нескольким ЗС

*({S#, SNAME, STATUS},{S#, CITY})

Т. е. отношение S равносильно соединению его проекций и по {S#, SNAME, STATUS} и по {S#, CITY}.

Существование данной ЗС следует из того что S# является потенциальным ключом. Однако отношение S удовлетворяет также и ЗС из трех проекций *({S#, SNAME},{S#, STATUS},{S#, CITY})

Эта ЗС следует из того, что оба атрибута S#, SNAME являются потенциальными ключами. В общем случае, Фейган показал, что существует алгоритм, с помощью которого для заданной ЗС и множества потенциальных ключей, можно проверить будет ли данная зависимость подразумеваться этими потенциальными ключами. Хотя на практике это очевидно. Т. о. для произвольного отношения R можно утверждать, что оно находится в 5 НФ при условии, что известны все потенциальные ключи и все ЗС подразумеваемые этими потенциальными ключами.

Однако в общем случае обнаружить все ЗС совсем не просто, так как если МЗ и ФЗ семантически отражают реальные ограничения, то ЗС отражают скорее виртуальные или логические ограничения. Следовательно, этап процедуры нормализации от 4 к 5 НФ не имеют однозначного алгоритма. Замечание. Как следует из определения 5 НФ, 5 НФ является высшей формой отношения если речь идет о проек.–соед. теории организации. Высшая НФ означает что отношение в 5 НФ абсолютно застраховано от наличия, каких либо аномалий обновления или точнее это отношение не может быть освобождено от иных аномалий, которые могли бы быть исключены с помощью декомпозиции на проекции. Действительно если отношение находится в 5 НФ, то единственными ЗС будут только те ЗС, которые подразумеваются потенциальным ключом. Это значит, что единственной истинной будет декомпозиция, основанная на этих потенциальных ключах. Отношение S находится в 5 НФ и теоретически его можно декомпозировать на отношения определяющие данное ЗС. Однако каждая из проекции заведомо будет содержать один из потенциальных ключей.

73. Итоговая схема процедуры нормализации.

Если дано произвольное отношение R которое находится в 1 НФ, то это отношение может быть приведено к 5 НФ. Процедура нормализации основана на систематично приведении отношения R к набору проекций. Причем соединение этих проекций должно быть эквивалентно исходному отношению R. каждый этап процедуры нормализации связан с декомпозицией. Этапы:

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

2. Отношения в 2 НФ следует разбивать на такие проекции, в которых отсутствуют транзитивные ФЗ.

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

В результате третьего этапа будет получена группа отношений в НФБК.

4. Отношения в НФБК подразумевает, что оно может иметь несколько потенциальных ключей. Поэтому НФБК следует разбивать на такие проекции, чтобы исключить любые МЗ, которые одновременно не являются ФЗ.

5. Отношения в 4 НФ следует разбивать на такие проекции, чтобы исключить любые ЗС которые не подразумеваются потенциальными ключами.

В результате будет получен набор отношений в 5 НФ.

Выводы:

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