Базы данных

Множество ФЗ называется неприводимым тогда и только тогда, когда:

Правая (зависимая) часть каждой ФЗ множества S содержит только один атрибут.

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

Ни одна ФЗ в S не может быть опущена из S без изменения S+.

Пояснение:

по п.2, т.е. нельзя преобразовать (конвертировать) S путем удаления некоторых атрибутов из детерминантов S во множество, эквивалентное S.

по п.2, говорят, что множество S в этом случае неприводимое слева.

по п.3, нельзя конвертировать S путем удаления каких-либо Ф.З. из S во множество эквивалентное S.

Пример: Дано: отношение R с атрибутами A={a, b, c, d}; множество ФЗ: S={ { a } ? { b, c }; { b } ? { c }; { a } ? { b }; { a, b } ? { c }; { a, c } ? { d }}

Найти неприводимое множество, эквивалентное S.

Определим во всех ФЗ справа только одноэлементное множество атрибутов

S1={{ a } ? { b }, { a } ? { c }, { b } ? { c }, { a,b } ? { c }, { a,c } ? { d }}.

Напомним, что любое множество содержит только различимые объекты. Множество ФЗ должно содержать только различные функциональные зависимости. Следовательно { a } ? { b } должна встретится только один раз. Мы преобразовали S в S1 , используя правила Амстронга. Следовательно, S и S1 эквивалентные множества (S+=S1+ и замыкание S не изменилось от преобразования его в S1).

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

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

в { a,c } ? { d } - в детерминанте атрибут с можно опустить, т.к.

(a?c) ?(ac>d)~(a>ac) ?(ac>d)~(a>ac) ?(a>d)~(a>c) ?(a>d).

S1 преобразовали с помощью правил Амстронга в

S2={{ a } ? { b }, { a } ? { c }, { b } ? { c }, { a,b } ? { c }, { a } ? { d }}.

При этом S1+=S2+.

Зависимость { a,b } ? { c } из S2 может быть исключена, т.к.

(a?b)?(a>c)~(a>b) ?(ab>bc)~(ab>b)?(ab>c)~ (a>b)?(ab>c), следовательно

(a>b)?(a>c)~(a>b)?(ab>c), но ФЗ (a>b) и (a>c) уже входят в S2 и Зависимость {a,b} ? { c } из S2 может быть исключена. Получим

S3={{ a } ? { b }, { a } ? { c }, { b } ? { c }, { a } ? { d }}.

Ни одна ФЗ не может быть опущена без изменения S+. По третьему правилу Амстронга (транзитивность) ({a} ? {b} ? {b} ? {c})=>{a} ? {c}, следовательно, из S3 можно опустить {a} ? {c} без изменения замыкания. Окончательно получаем S4={ a>b, b>c, a>d} - неприводимое множество ФЗ для S.

Пример: Дано отношение - расписание занятий с атрибутами:

D - день недели (1…5), P - номер урока (1…8), C - номер класса, T - имя учителя, L - название урока.

Кортеж (d,p,c,t,l) является элементом этого отношения тогда и только тогда, когда урок l проводится учителем t в классе с в момент времени d,p. Предположим, что каждый урок имеет название, уникальное по отношению ко всем урокам этой недели.

Ответить на вопросы:

Какие ФЗ выполняются для этого отношения? Какие потенциальные ключи отношения?

Решение: L>D,P,C,T

D,P,C>T

D,P,T>C

D,P,C>L



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

Нормализацию отношения рассмотрим на примере отношения

R: Номер детали - (N), Город - (C), Код поставщика - (P), Количество - (Q).

Понятие нормализованной формы ввел Кодд и определил 3 нормальных формы.

Исходные 3НФ приводит к некоторой неадекватности, переработано Бойсом и названо НФБК (нормальная форма Бойса-Кодда). Позже Фейгин дал определение 4НФ и 5НФ.

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

Замечание:

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

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

45. Декомпозиция без потерь и функциональные зависимости. Теорема Хеза

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

Основной механизм нормализации - декомпозиция исходного отношения (проектирование исходного отношения).

Ясно, что получение новых отношений не должно приводить к потере информации (возникновению противоречий), т. е. соединение полученных проекций должно дать исходное отношение:

Пример:

S:	Код	Статус	Город
	3	30	Казань
	5	50	Новгород

1)	S11	Код	Статус	S12	Код	Город
		3	30		3	Казань
		5	30		5	Новгород

2)	S21	Код	Статус	S22	Статус	Город
		3	30		30	Казань
		5	30		30	Новгород

S11 JOIN S12: = S1

Код	Статус	Город
3	30	Казань
5	50	Новгород

S21 JOIN S22 ? S1 и содержит противоречивую информацию (нарушается условие один город - один поставщик).

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

Решение поставленной задачи дает теорема Хеза (Heath).

Теорема Хеза.

Пусть R отношение с атрибутами {A, B, C}. Если R удовлетворяет зависимости A?R, т.е. (А ? В и А ? С), R = AB?AC эквивалентно, т. к. А ? А по 4 правилу Амстронга ,то R равно соединению его проекций {A, B} и {A, C}.

Рассмотрим предыдущий пример.

В исходном отношении, очевидно, есть две ФЗ: S={{код ? статус}{код ? город}}

Очевидно, что S - неприводимое множество ФЗ и по т. Хеза проекции {код, статус} и {код, город} дают исходное отношение {код, статус, город}.

Если рассмотреть проекции: {код, статус} и {статус, город}, то при таком разбиении утрачивается функциональная зависимость {код, город} и соединение проекций не дадут исходное отношение (транзитивности нет, т. к. статус ? город - нет).

Далее рассмотрение нормальных форм будем производить на примере следующего отношения:

поставщики + товары

Код	Город	Товары	Количество
1	Москва	1	300
1	Москва	2	200
1	Москва	3	400
1	Москва	4	200
1	Москва	5	100
1	Москва	6	100
2	Ростов	1	300
2	Ростов	2	400
3	Ростов	2	200
4	Москва	2	200
4	Москва	4	300
4	Москва	5	400



46. ФЗ, неприводимые слева, диаграммы ФЗ, ФЗ как семантические понятия. Допущения, принятые для 1НФ, 2НФ, 3НФ. Взаимно независимые атрибуты

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

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

Пример:

Функциональная зависимость как семантическое понятие.

ФЗ - это особый вид ограничений целостности, т. е. это, несомненно, семантическое понятие.

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

Способом задания ограничений в определении базы данных является объявление ФЗ.

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

Неключевой атрибут - это атрибут, который не входит в первичный ключ рассматриваемого отношения.

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

Физический смысл взаимно независимости: каждый атрибут из множества взаимно независимых атрибутов А может быть обновлен независимо от остальных атрибутов множества А.

47. Недостатки 1НФ. Вторая НФ

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

Любое нормализованное отношение находится в 1НФ.

Недостатки 1НФ рассмотрим на примере:

Отношение R1:

Размещено на http://www.allbest.ru/

S

={{код, товар}? {количество}; {код} ? {город}; {код} ?{статус}; {город} ? {статус}} множество ФЗ отношения R1.

Первичный ключ в отношении {код, товар} Статус поставщика определяется его месторасположением.

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

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

аномалия - удаления DELETE. Возможна, что с удалением некоторой строки таблица (удаление поставки) исчезнет информация о поставщике.

аномалия UPDATE (переписать, обновить) - эта проблема возникает в том случае, если необходимо переместить поставщика из одного города в другой. Например, 1 из Москвы в Новгород. Необходимо откорректировать все записи о поставках от этого поставщика.

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

R2: R3:

Код	Товар	Кол-во		Код	Статус	Город
1	1	300		1	20	Москва
1	2	200		2	10	Ростов
1	3	400		3	10	Ростов
1	4	200		4	20	Москва
1	5	100		5	30	Новгород
1	6	100
2	1	300
2	2	400
3	2	200
4	2	200
4	4	300
4	5	400

ФЗ для отношения R2:{код, товар}>{кол-во}

ФЗ для отношения R3:{код}>{город}, {код}>{статус}, {город}>{статус}

Такие отношения позволяют преодолеть указанные противоречия: INSERT: Можно вставить поставщика из Новгорода, который не поставлял товар; DELETE: Можно удалить товар 2 от поставщика 3, а сведения о поставщике останутся; UPDATE: Для того, чтобы переместить поставщика 1 из Москвы в Новгород, достаточно поменять запись в отношении R3.

Физический смысл противоречия в отношении R1 в том, что это отношение описывает не один объект (поставку товара) а два: поставку и поставщика.

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

48. Недостатки 2НФ. Третья НФ

В общем случае: пусть имеется отношение R: {А, В, С, D} где {А, В} первичный ключ, кроме того, имеется ФЗ A > D, тогда R заменяем на 2 отношения:

R1: {A, B, C} = ПрA,B,C (R), где первичный ключ {A, B}, А - внешний ключ.

R2: {A, D} > первичный ключ {А}.

Исходное: R = R1 JOIN R2.

Проблемы, возникающие в R3.

INSERT: Нельзя включить город с некоторым статусом, из которого нет ни одного поставщика.

DELETE: удалив поставщика 5, удалим информацию о том, что Новгороду был установлен статус 30.

UPDATE: информация о статусе повторяется, т.о. изменив статус Москвы с 20 на 30 необходимо откорректировать несколько записей.

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

Формальным признаком проблем в R3 является наличие транзитивной ФЗ. Для этого отношения неприводимое множество ФЗ: {код} > {город} и {город} > {статус}.

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

R5: R6:

Код	Город		Город	Статус
1	Москва		Москва	20
2	Ростов		Ростов	10
3	Ростов		Новгород	30
4	Москва		Казань	40
5	Новгород

ФЗ для отношения R5: {код} >{город}

ФЗ для отношения R6: {город}> {статус}

Каждое отношение описывает только одну сущность (объект предметной области).

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

Размещено на http://www.allbest.ru/

Н

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

Пример: Отношение R с атрибутами {A, B, C}, где {A} - первичный ключ; есть ФЗ: B>C (A > B и A > C - очевидно).

R1: {A, B}, где {A} - первичный ключ, В - внешний ключ, А>В.

R2: {B, C}, где {B} - первичный ключ, В>С.

Отношение R может быть восстановлено соединением R1 и R2: R = R1 join R2

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

49. Нормализация и сохранение ФЗ. Условия декомпозиции с независимыми проекциями

Рассмотрим отношение R с ФЗ код>город и город>статус, и, следовательно, транзитивной зависимостью код>статус.

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

Ранее это отношение (в 2НФ) мы заменили на два отношения 3НФ, чтобы устранить аномалии 2НФ.



А:

R1A R2A

Код	Город		Город	Статус
1	Москва		Москва	20
2	Ростов		Ростов	10
3	Ростов		Ростов	10
4	Москва		Москва	20
5	Новгород		Новгород	30

B:

R1B R2B

Код	Город		Код	Статус
1	Москва		1	20
2	Ростов		2	10
3	Ростов		3	10
4	Москва		4	20
5	Новгород		5	30

При декомпозиции В оба отношения R1B и R2B также находятся в 3НФ, и R1B Join R2B=R (нет потери информации).

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

Рассмотрим этот пример подробнее.

Заметим, что в разбиении А изменять отношения R1A и R2A можно независимо друг от друга. Единственно, что необходимо проверять уникальность ключей в этих отношениях, а ФЗ код>статус будет выполняться автоматически.

В разбиении В недостаточно обеспечить уникальность первичных ключей в отношениях R1B и R2B, т.к. ничего не может указать статус. Например, у поставщика 4 указать статус 10, тогда у Москвы по коду 1 - статус 20, а по коду 4 - 10. Таким образом, при модификациях отношений R1B и R2B необходимо проверять ФЗ город>статус.

Разбиение А ФЗ: код>город и город>статус - естественно выполняются за счет уникальности ключей. Ограничения между отношениями код>статус выполняются автоматически.

Разбиение В ФЗ: код>город и код>статус - выполняются при условии уникальности ключей. ФЗ между отношениями город>статус необходимо проверять. Заметим, что ФЗ город>статус не могут быть получены из код>город и код>статус.

Разбиение В пример зависимых проекций.

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

Условия декомпозиции с независимыми проекциями.

Дано отношение R. Проекции R1 и R2 этого отношения являются независимыми (в указанном выше смысле) тогда и только тогда, когда:

Каждая ФЗ в отношении R является логическим следствием функциональных зависимостей в проекциях R1 и R2.

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

В декомпозиции А: проекции R1A и R2A - являются независимыми, т.к.:

ФЗ код>город и город>статус являются естественными, а ФЗ код>статус является их логическим следствием.

Общий атрибут (город) является первичным ключом в одной из проекций (в R2A).

Декомпозиция В: проекции R1B и R2B не являются независимыми, т.к.: ФЗ код>город и код>статус являются естественными, но ФЗ город>статус не является логическим следствием этих зависимостей. Хотя их общий атрибут (код), является потенциальным ключом в обеих проекциях (и R1B и R2B).



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

Рассмотрим более общий случай отношения.

Пусть:

Отношение имеет два (или более) потенциальных ключа.

Два потенциальных ключа является сложными.

Потенциальные ключи перекрываются

Замечание: отношения, у которых имеются условия 1, 2, 3, встречаются редко, если у отношения нет условий 1, 2, 3, то 3НФ совпадает с НФБК.

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

Менее формальное определение имеет формулировку:

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

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

Примеры НФБК.

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

Размещено на http://www.allbest.ru/

С

Схема ФЗ имеет вид:

Детерминанты:{код}, {город}, {код, товар}, только {код, товар}> потенциальный ключ. Таким образом отношение R1 не находится в НФБК.

Отношение R3, R5 и R6, которые находятся в 3НФ.

R3:



R5: R6:

Эти отношения также находятся в НФБК, т.к. единственный потенциальный ключ является и единственным детерминантом.

Рассмотрим отношение: {код, имя-поставщика, статус, город}.

Допустим, что код и имя-поставщика являются потенциальным ключом (т.е. поставщик имеет уникальный код и уникальное имя).

Кроме того, пусть ФЗ город>статус не выполняется (ранее введенная такая зависимость использовалась только для иллюстрации).

Диаграмма ФЗ имеет вид:

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

Рассмотрим отношение: {код, имя-поставщика, товар, кол-во} предположим, что имена поставщиков и код являются уникальными.

Потенциальные ключи в этом отношении {код, товар} и {имя-поставщика, товар}, ясно, что имеется ФЗ код>имя_поставщика и имя_поставщика>код. Таким образом данное отношение не находится в НФБК, т.к. есть детерминанты, которые не являются потенциальными ключами.

Пусть часть этого отношения имеет вид:

Размещено на http://www.allbest.ru/

Э

Єто отношения обладает избыточностью => есть аномалии обновления, но заметим, что отношения находятся в ЗНФ т.к. для ЗНФ (в определении Кодда) требуется, чтобы каждый не ключевой атрибут неприводимо зависел от потенциального ключа, т.е. то, что атрибут имя_поставщика приводимо зависит от потенциального ключа {код, товар} игнорируется.

Для решения проблемы разобьем отношение на 2 проекции:

А: {код, имя_поставщика}, {код, товар, количество};

В: {код, имя_поставщика}, {имя_поставщика, товар, количество}.

Обе композиции находятся в НФБК.

Рассмотрим отношение: {студент, курс, преподаватель}.

(кортеж означает, что студент обучается предмету некоторым преподавателям).

Пусть накладываются некоторые ограничения:

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

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

Схема ФЗ имеет вид:



В рассматриваемом примере есть два перекрывающихся потенциальных ключа: {студент, курс} и {студент, преподаватель}. Отношение находится в ЗНФ, т.к. нет неключевых полей вообще, но не в НФБК опять есть аномалии удаления: удалив запись о том, что Петров изучает физику, удаляем сведения о том, что Лимонов преподает физику. Проблема в том, что {преподаватель} является детерминантом, но не является потенциальным ключом. Построим разбиение.

А: {студент, преподаватель} и {преподаватель, курс}

СТУДЕНТ	ПРЕПОДАВАТЕЛЬ		ПРЕПОДАВАТЕЛЬ	КУРС
Иванов	Белов		Белов	Математика
Иванов	Сидоров		Сидоров	Физика
Петров	Белов		Лимонов	Физика
Петров	Лимонов

Потенциальные ключи:

{студент, преподаватель} {преподаватель}

Отношения находятся в НФБК. Имеется естественная ФЗ {преподаватель}>{курс}. Кроме того, должно иметь место ФЗ связывающая отношения {студент, курс}>{преподаватель}.

Устранены некоторые противоречия (убрать запись Петров, Лимонов, но сведения о том, что Лимонов преподает физику останется). Но имеется другие проблемы: добавим запись Иванов, Лимонов.

Формально это можно сделать, но это противоречит тому, что Иванов уже изучает физику у Сидорова, т.е. эти два отношения связаны (не являются независимыми): ФЗ {студент, курс}>{преподаватель} нельзя получить из ФЗ этого разбиения (только одна ФЗ {преподаватель}>{предмет}, т.е. добавить запись в отношение 1 нельзя без проверки отношения 2). Таким образом декомпозиция на компоненты в НФБК и композиция на независимые компоненты может вступить в конфликт.

Рассмотрим отношения R с атрибутами: {студент, предмет, номер_в_списке}

Кортеж: (S,P,N)?R, если студент S сдает экзамен по предмету P, если он занесен в список сдающих под номером N.

Имеют места следующее ограничение: никакие два студента не могут иметь один и тот же номер по списку по одному и тому же предмету; имеют место следующие ФЗ: {студент, предмет}>{номер}, {предмет, номер}>{студент}

В отношении имеются два перекрывающихся ключа:{студент, предмет} и {предмет номер}, т.к. оба потенциальных ключа являются детерминантами и других детерминантов нет, то отношение находится в НФБК.

У этого отношения нет аномалий.

Преимущества НФБК.

Позволяет избавится от некоторых проблем, присущих (хотя бы теоретически) форме ЗНФ.

Определение НФБК концептуально проще ЗНФ (нет: 1НФ, 2НФ, первичного ключа, транзитивной зависимости).

Размещено на Allbest.ru