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

↑

▷ Содержание

⇐ ПредыдущаяСтр 10 из 19Следующая ⇒

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

1) свойство соединения без потерь:

,

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

Метод, проверяющий сохраняется ли свойство соединения без потерь:

Строится таблица с n столбцами и k строками. Столбец j соответствует атрибуту , а i-я строка отношению . На пересечении строки i и столбца j поместим символ a_j, если . В противном случае туда поместим символ b_ij.

Повторно рассматриваем каждую из зависимостей в до тех пор, пока в таблице невозможно будет сделать какие-либо изменения. Всякий раз, рассматривая зависимости , мы ищем строки, которые совпадают по всем столбцам, соответствующим атрибутам из X. При обнаружении двух таких строк отождествляем их символы в столбцах, соответствующих атрибутам из Y. Если при этом один из отождествляемых символов = a_j, приравниваем и другому a_j. В том случае, когда они равны b_lj и b_lj, делаем их оба равными b_lj или b_lj по своему усмотрению.

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

Пример:

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

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

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

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

Может выполняться только одно из свойств. Декомпозиция может сохранять , не обладая свойством соединения без потерь. Например, . И, наоборот.

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

НОРМАЛИЗАЦИЯ ОТНОШЕНИЙ.

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

Пример: Поставщик (ФИО; номер; адрес; товар; количество)

Избыточность: если разный товар поставляется одним и тем же поставщиком, то его адрес повторяется всякий раз. Þ Обновление: если изменяется адрес поставщика, то его надо менять во всех кортежах; если этого не случится, то у поставщика будут разные адреса. Удаление: если в данный момент прекратил поставлять товар, то его адрес утрачивается. Включение: не может быть включена запись о поставщике, не поставляющем в данный момент товар.

Все проблемы исчезают, если заменить это отношение двумя:

Поставщик (ФИО; номер; адрес)

Поставка (номер поставщика; товар; количество)

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

1НФ: Схема отношений находится в 1НФ т. и т.т., когда все входящие в нее атрибуты являются атомарными (неделимыми).

1НФ достаточна для рассматриваемых языков запросов.

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

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

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

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

Любая схема отношений, находящаяся в 3НФ относительно , находится во 2НФ относительно . 3НФ избавляет от аномалий включения, удаления, модификации.

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

Схема отношений может быть в 3НФ, но не быть при этом в НФБК; но если отношение находится в НФБК, то всегда находится в 3НФ.

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

Пример: номер поставщика → товар

ФИО, адрес → товар

– 2НФ

номер поставщика → индекс товара товар - 3НФ

Познавательные статьи:



Как правильно слушать собеседника

Типичные ошибки при выполнении бросков в баскетболе

Принятие христианства на Руси и его значение

Средства массовой информации США