Основные требования к организации базы данных (стр. 2 )

Если существует единственная функциональная зависимость В от А, то её обозначают просто А ® В. В случае отсутствия между ними функциональной зависимости вводят обозначение А ¹ В. Если А ® В и одновременно В ® А, то между А и В существует взаимно однозначное соответствие, что записывается как А « В.

Пусть имеется множество атрибутов А1, А2,...,Аn отношения R, а также множество F Ф. З. Х ® Y, где Х и Y - подмножества атрибутов множества А1, А2,...,Аn. Тогда из Ф. З. (функциональные зависимости), входящих в F, могут быть выведены другие Ф. З., присущие отношению R.

Обозначим через F+ замыкание множества ФЗ F, т. е. полное множество зависимостей, которое можно получить из F.

Правило вывода ФЗ :

1. Правило ФЗ 1 (свойство рефлексивности). Если Х £ U, Y £ U и Y £ Х, то имеет место Ф. З. Х ® Y.

Правило ФЗ 2 (свойство пополнения). Если Х £ U, Y £ U и Z £ U и имеет место Ф. З. Х ® U, X È Z ® Y È Z.

В отличии от правила ФЗ 1 данное говорит о том, что для его применения несущественно выполнение условий Y £ Х. Т. е. любые атрибуты из множества U можно одновременно подставлять в левую и правую части выражения Ф. З. F.

Например, имеется универсальное отношение U(A1, A2, A3, A4, A5) и заданы наборы атрибутов X={A1, A3}, Y={A2, A4}, Z={A5}, тогда из условия, что существует Ф. З. Х ® Y : {A1, A3}® {A2, A4}, следует, что имеет место зависимость:

{A1, A3, А5}® {A2, A4, А5},

3. Правило ФЗ 3 (свойство транзитивности) . Если Х £ U, Y £ U и Z £ U и имеют место зависимости Х ® Y и Y ® Z, то Х ® Z. Например, имеются подмножества атрибутов X={A1, A3}, Y={A2, A4}, Z={A5}. Тогда из условия существования зависимостей {A1, A3}® {A2, A4}, {A2, A4}® {A5} следует, что имеет место зависимость {A1, A3}® {A5}.

Кроме этих правил часто используют дополнительные правила следствия ФЗ 1, ФЗ 2, и ФЗ 3.

4. Правило ФЗ 4 (свойство расширения). Если Х £ U, Y £ U и задана ФЗ,

Х ® Y, тогда для любого Z £ U имеет место Ф. З. X ÈZ ® Y.

5. Правило ФЗ 5 (свойство продолжения). Если Х £ U, Y £ U, W £ U, Z £ U и задана Ф. З. Х ® Y, то для любых W £ Z имеет место зависимость X ÈZ ® Y È W.

6. Правило ФЗ 6 ( свойство псевдотранзитивности). Если Х £ U, Y £ U,

W £ U, Z £ U и заданы Ф. З. Х ® Y, Y ÈW ® Z, то имеет место Ф. З. X ÈW ® Z.

7. Правило ФЗ 7 (свойство аддитивности). Если Х £ U, Y £ U, Z £ U, и заданы Ф. З. Х ® Y, Х ® Z, то имеет место Ф. З. X ®Y È Z.

8. Правило ФЗ 8 (свойство декомпозиции). Если Х £ U, Y £ U, Z £ U, и при этом Z £ Y и заданы Ф. З. Х ® Y, то имеет место Ф. З. Х ® Z.

13.  Избыточные функциональные зависимости, минимальное покрытие декомпозиции

Полное множество правил вывода состоит из 3 аксиом Амстронга, а также трёх следующих из этих аксиом правил.

Правила вывода:

1. Аксиомы 1.2.3

1. Рефлексивность: XÍU, YÍU, YÍX, то XàY

2. пополнение: XÍU, YÍU, ZÍU, XàY, то XÈZàYÈZ

3. транзитивность: XÍU, YÍU, ZÍU, XàY, YàZ, то XàZ

2. Из них следуют правила:

1. Объединения AàB, AàC то AàB, C

2. Декомпозиции AàB, C, то AàB, AàC

3. Псевдотранзит: XàY; Y, WàZ; то X, WàZ

По этим правилам определяем избыточные зависимости

Обобщённый алгоритм декомпозиции:

1. Построение универсального отношения для БД.

2. Определение всех ФЗ, существующих между атрибутами универсального отношения.

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

4. Использование ФЗ из минимального покрытия для декомпозиции универсального отношения в набор НФБК - отношений.

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

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

а). выбор оставшихся ФЗ и создание одного отношения для каждых детерминанта и набора зависящих от него атрибутов;

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

ИФЗ

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

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

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

Отношение является избыточным, если

1. Все его атрибуты могут быть найдены в другом отношении проектного набора.

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

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

14.  Нормальные формы схем отношений. 1НФ 2НФ.

Нормальные формы схем отношений

Рассмотрим отношение R{A1, A2,..., An}. Возможный ключ k отношения R - это комбинация атрибутов (возможно, состоящих из одного атрибута), обладающих следующими свойствами:

1. В каждом кортеже отношения R величина ключа k, единственным образом определяет этот кортеж.

2. Не существует атрибута в возможном ключе k, который мог быть удалён без нарушения свойства 1.

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

Аномалия – такая ситуация в таблице БД, которая приводит к противоречиям в БД, либо существенно усложняет обработку данных.

Разновидности аномалий:

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

2. аномалии изменения – один и тот же фрагмент данных изменяется в одном кортеже, но остается нетронутым в другом.

3. аномалия удаления – если множество значений становится пустым, это может косвенным образом привести к потере некоторой другой информации.

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

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

Пример: Автомобиль (модель, марка, изготовитель ( завод, город )).

В данном случае атрибут изготовитель составной. Для приведения к 1НФ отношения необходимо избавится от составного отношения - изготовитель. Этого можно добиться, рассмотрев вместо составного атрибута его составляющие:

Автомобиль (модель, марка, название завода изготовителя, город ).

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

2НФ. Чтобы рассмотреть 2НФ, введём понятие полной зависимости. Пусть X и Y – элементы подмножества атрибутов отношения R и X ® Y. Если Y функционально не зависит от любого подмножества A множества X (причём A не совпадает с X ), то Y называют полностью зависимым от X в R.

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

Пусть имеется отношение ПОСТАВКИ, содержащее данные о поставках (идентифицируемых П№ ), поставляемых ими товарах и их ценах: ПОСТАВКИ (П№, ТОВАР, ЦЕНА)

Предположим, что поставщик может поставлять разные товары, а один и тот же товар могут поставлять разные поставщики. То есть, ключ отношения (выделенный шрифтом) будет состоять из атрибутов П№ и ТОВАР. Известно, что цена любого товара зафиксирована (то есть все поставщики поставляют товар по одной и той же цене). Семантика отношения включает следующие зависимости:

П№, ТОВАР ® цена (по определению КЛЮЧА) ТОВАР ® цена

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

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

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

Разложение отношения ПОСТАВКИ на два отношения устраняет неполную функциональную зависимость.

ПОСТАВКИ (П№, ТОВАР)

ЦЕНА-ТОВАРА (ТОВАР, ЦЕНА)

Цену товара конкретной поставки можно определить путём соединения двух отношений по атрибуту ТОВАР. Изменение цены товара вызовет модификацию лишь одного кортежа второго отношения.

15.  3я нормальная форма

Нормальные формы схем отношений

Рассмотрим отношение R{A1, A2,..., An}. Возможный ключ k отношения R - это комбинация атрибутов (возможно, состоящих из одного атрибута), обладающих следующими свойствами:

1. В каждом кортеже отношения R величина ключа k, единственным образом определяет этот кортеж.

2. Не существует атрибута в возможном ключе k, который мог быть удалён без нарушения свойства 1.

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

Аномалия – такая ситуация в таблице БД, которая приводит к противоречиям в БД, либо существенно усложняет обработку данных.

Разновидности аномалий:

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

2. аномалии изменения – один и тот же фрагмент данных изменяется в одном кортеже, но остается нетронутым в другом.

3. аномалия удаления – если множество значений становится пустым это может косвенным образом привести к потере некоторой другой информации.

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

3НФ. Рассмотрим транзитивную зависимость следующего типа:

Если А ® В, В ® А (В не является ключом) и В ® С, то А ® С.

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

Пусть имеется отношение ХРАНЕНИЕ (ФИРМА, СКЛАД, ОБЪЁМ), которое содержит информацию о фирмах, получающих товары со складов, и объёмах этих складов. В отношении имеются функциональные зависимости:

ФИРМА ® СКЛАД (фирма получает товары только с одного склада)

СКЛАД ® ОБЪЁМ

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

Аномалия удаления. Если последняя фирма перестаёт получать товар со склада, данные о складе и его объёме нельзя сохранить в базе данных.

Аномалия обновления. Если объём склада изменяется, необходим просмотр всего отношения и изменение кортежей для фирм, связанных со складом.

Преобразование отношения в 3НФ устраняет рассмотренные аномалии. Следующее разложение приводит к отношениям во 3НФ:

ХРАНЕНИЕ (ФИРМА, СКЛАД)

С_ОБЪЁМ (СКЛАД, ОБЪЁМ)

16.  Нормальная форма Бойса - Кодда (НФБК)

Отношение R находится в НФ БК, если для всех зависимостей из X® А, когда А не принадлежит Х, Х является возможным ключом отношения R. Обычно атрибут, от которого функционально полно зависит другой, называется детерминантом. Поэтому говорят, что отношение R находится в НФБК, если все детерминанты являются ключами.

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

Д№, ПР№ ® П№ (по определению ключа)

П№ ® ПР№

Рассматриваемое отношение находится в 3НФ, так как в нём отсутствуют неполные функциональные зависимости и транзитивные зависимости не первичных атрибутов от ключей; при этом, однако, наблюдаются следующие аномалии:

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

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

Аномалия обновления. Если меняется поставщик некоторого типа деталей для проекта, необходим просмотр отношения для изменения всех кортежей, содержащих эти детали.

Разложение исходного отношения на отношения в НФБК устраняет перечисленные аномалии. Отношение находится в НФБК, если оно находится в 3НФ и в нём отсутствуют зависимости первичных атрибутов от не первичных. Для этого необходимо устранить в данном отношении зависимость П№ ® ПР№. Следующее разложение приводит к отношениям в НФБК:

ПРОЕКТ - ДЕТАЛЬ (Д№, ПР№)

ПОСТАВКИ (П№, ПР№)

17.  Многозначная зависимость. Аксиомы многозначной зависимости.

Многозначная зависимость существует, если при заданных значениях атрибута X существует множество, состоящее из 0 или более взаимосвязанных значений атрибута Y, причем множество значений атрибута Y связано со значением атрибута в отношении U-X-Y, где U – все множество атрибутов отношений.

Обозначение многозначной зависимости X->>Y.

Аксиомы многозначной зависимости

1. дополнение для многозначной зависимости: Если X<U, Y<U, X->>Y, то X->>U-X-Y

2. пополнение для многозначной зависимости: Если X<U, Y<U, V<U, W<U. Причём V<W, X->>Y, то WuX->>VuY

3. транзитивность для многозначной зависимости: Если X<U, Y<U, X->>Y, Y->>Z, то X->>Z-Y

Дополнительные правила вывода для многозначных зависимостей

1. объединение Если X<U, Y<U, Z<U, X->>Z, X->>Y, то X->>YuZ

2. псевдотранзитивность Если X<U, Y<U, Z<U, W<U, X->>Y, WuY->>Z, то WuX->>Z-(WuY)

3. смешанное правило транзитивности Если X<U, Y<U, Z<U, X->>Y, XuYàZ, то XàZ-Y

4. правило декомпозиции X<U, Y<U, Z<U, X->>Y, X->>Z, то X->>Y^Z, X->>Y-Z, X->>Z-Y

18.  4я нормальная форма

Нормальные формы схем отношений

Рассмотрим отношение R{A1, A2,..., An}. Возможный ключ k отношения R - это комбинация атрибутов (возможно, состоящих из одного атрибута), обладающих следующими свойствами:

1. В каждом кортеже отношения R величина ключа k, единственным образом определяет этот кортеж.

2. Не существует атрибута в возможном ключе k, который мог быть удалён без нарушения свойства 1.

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

Аномалия – такая ситуация в таблице БД, которая приводит к противоречиям в БД, либо существенно усложняет обработку данных.

Разновидности аномалий:

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

2. аномалии изменения – один и тот же фрагмент данных изменяется в одном кортеже, но остается нетронутым в другом.

3. аномалия удаления – если множество значений становится пустым это может косвенным образом привести к потере некоторой другой информации.

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

4НФ

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

Пример: Рассмотрим зависимость (№, курс, дети, должность)

Между преподавателем и курсом связь M:M

Между преподавателем и детьми 1:M

Многозначные зависимости №->>курс, №->>дети

Схема отношения находится в 4НФ, если всякий раз, когда существует многозначная зависимость X->>Y, где Y непусто, и не является подмножеством X, и XvY состоит не из всех атрибутов R, X содержит к-н ключ отношения R, атрибуты, между которыми существует многозначная зависимость, выделяют в отдельные отношения

R1(№,курс) R2(№,дети) R3(№,должность)

19.  5я нормальная форма

Нормальные формы схем отношений

Рассмотрим отношение R{A1, A2,..., An}. Возможный ключ k отношения R - это комбинация атрибутов (возможно, состоящих из одного атрибута), обладающих следующими свойствами:

1. В каждом кортеже отношения R величина ключа k, единственным образом определяет этот кортеж.

2. Не существует атрибута в возможном ключе k, который мог быть удалён без нарушения свойства 1.

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

Аномалия – такая ситуация в таблице БД, которая приводит к противоречиям в БД, либо существенно усложняет обработку данных.

Разновидности аномалий:

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

2. аномалии изменения – один и тот же фрагмент данных изменяется в одном кортеже, но остается нетронутым в другом.

3. аномалия удаления – если множество значений становится пустым это может косвенным образом привести к потере некоторой другой информации.

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

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

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

Декомпозиция отношений должна гарантировать обратимость. Обратимость предполагает:

1.  отсутствие потери картежей

2.  не появляются ранее отсутствующие картежи

3.  сохранение функциональной зависимости

20.  Соединение без потерь, сохраняющих зависимость

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

Условия отсутствия потерь при соединении:

Если R1 и R2 являются разложением R, с сокращением функциональных зависимостей – это разложение обеспечивает соединение без потерь с сохранением функциональной зависимости <=> если R1^R2àR1-R2 либо R1^R2àR2-R1 при многозначной зависимости R1^R2->>R1-R2, либо R1^R2->>R2-R1

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

Пример:

Служащие(№, отдел, город)

1 разложение E1(№, отдел) E2(№, город)

2 разложение E3(№, отдел) E4(отдел, город)

1. E1^E2=№ E1-E2=отдел E2-E1=город. №àотдел, №àгород условие удовлетворяет, разложение без потерь.

2. E3^E4=отдел E3-E4=№ E4-E3=город. отделà№, отделàгород эти зависимости в исходном разложении не существуют, а исходные функциональные зависимости утеряны, значит это разложение с потерями.

Для разложений более чем из двух отношений можно использовать метод Табло

21.  Условия отсутствия потерь при соединениях

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

Условия отсутствия потерь при соединении:

Если R1 и R2 являются разложением R, с сокращением функциональных зависимостей – это разложение обеспечивает соединение без потерь с сохранением функциональной зависимости <=> если R1^R2àR1-R2 либо R1^R2àR2-R1 при многозначной зависимости R1^R2->>R1-R2, либо R1^R2->>R2-R1

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

Пример:

Служащие(№,отдел, город)

1 разложение E1(№, отдел) E2(№, город)

2 разложение E3(№, отдел) E4(отдел, город)

1. E1^E2=№ E1-E2=отдел E2-E1=город. №àотдел, №àгород условие удовлетворяет, разложение без потерь.

2. E3^E4=отдел E3-E4=№ E4-E3=город. отделà№, отделàгород эти зависимости в исходном разложении не существуют, а исходные функциональные зависимости утеряны, значит это разложение с потерями.

Для разложений более чем из двух отношений можно использовать метод Табло

22.  Метод Табло

Дано множество функциональных зависимостей, схема отношения, полученная в результате разложения. Процедура состоит в построении таблицы, строками которой являются разложенные отношения, а столбцами – список атрибутов этих отношений без повторений. Таблица заполняется символом aj, если элементы строки i в столбце j соответствуют атрибуту Aj отношения Ri в противном случае ставится bij. После построения таблицы следует просмотр всех функциональных зависимостей XàY если для атрибутов из X найдутся строки, где в соответствующих местах стоят aj, то элементы bij этих строк соответствующие столбцам атрибутов из Y заменяется на aj. Если в результате появляется строка таблицы, полностью заполненная aj, то это соединение без потерь.

Пример: R(A, B,C, D) Ф. З. AàC, BàC, CàD.

Разложили: R1(A, B) R2(B, D) R3(A, B,C) R4(B, C,D)

… A B C D R1 a a b b R2 b a b A R3 a a a B R4 b a a a	AàC A B C D R1 a a a b R2 b a b A R3 a a a B R4 b a a a
BàC A B C D R1 a a a b R2 b a a A R3 a a a B R4 b a a a	CàD A B C D R1 a a a A R2 b a a A R3 a a a A R4 b a a A

Есть строки со всеми a, разложение без потерь.