русс | укр

Языки программирования

ПаскальСиАссемблерJavaMatlabPhpHtmlJavaScriptCSSC#DelphiТурбо Пролог

Компьютерные сетиСистемное программное обеспечениеИнформационные технологииПрограммирование

Все о программировании


Linux Unix Алгоритмические языки Аналоговые и гибридные вычислительные устройства Архитектура микроконтроллеров Введение в разработку распределенных информационных систем Введение в численные методы Дискретная математика Информационное обслуживание пользователей Информация и моделирование в управлении производством Компьютерная графика Математическое и компьютерное моделирование Моделирование Нейрокомпьютеры Проектирование программ диагностики компьютерных систем и сетей Проектирование системных программ Системы счисления Теория статистики Теория оптимизации Уроки AutoCAD 3D Уроки базы данных Access Уроки Orcad Цифровые автоматы Шпаргалки по компьютеру Шпаргалки по программированию Экспертные системы Элементы теории информации

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


Дата добавления: 2013-12-23; просмотров: 6362; Нарушение авторских прав


Пусть дана схема R с атрибутами А1, А2, … An и пусть X и Y являются подмножеством R. Тогда говорят, что X функционально определяет Y или Y функционально зависит от X, если для любого отношения r со схемой R невозможно существование двух кортежей, у которых значение атрибутов из Х попарно совпадают, а значения хотя бы одного атрибута из Y отличаются.

Другими словами, для любых двух кортежей t1 и t2 из таблицы r со схемой R и с заданной функциональной зависимостью X->Y, попарное равенство атрибутов из множества Х логически влечет попарное равенство атрибутов из множества Y.

В примере с поставщиками имеются следующие функциональные зависимости:

{Имя }–> {Адрес}

{Имя, товар}->{Цена}

Используя реляционную алгебру, можно дать другое определение функциональной зависимости:

Пусть r – отношение со схемой R. X и Y – подмножества R, тогда отношение r удовлетворяет функциональной зависимости X->Y, если формула 1 всегда имеет не более одного кортежа для любой константы, то есть, если мы имеет зависимость X->Y, то сделав селекцию по атрибутам из Х, а затем сделав проекцию на Y, мы не получим более одного кортежа.

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

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

Определение логического следования.

Пусть F – множество функциональных зависимостей, заданных на схеме R. Будем говорить, что F логически влечет функциональную зависимость X->Y (F), если каждое отношение r со схемой R, удовлетворяющее F, также удовлетворяет и зависимости X->Y.



Пусть задано множество функциональных зависимостей F. Замыканием множества функциональных зависимостей F называется множество всех функциональных зависимостей, которые логически следуют из F. Обозначается F+.

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

Пусть задана схема R с атрибутами А1, А2,…,An и множество функциональных зависимостей F.

2) не существует множества Y, являющегося подмножеством X, такого, что Y->

Второй пункт требует, чтобы ключ был минимальным.

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

 

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

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

Пусть задана схема отношения со множеством атрибутов U.

1) Рефлексивность.

Доказательство. Сделав селекцию по атрибутам X, получаем либо пустое множество, либо множество кортежей, у которых все атрибуты из X имеют одинаковые значения. Спроецировав их на атрибуты из Y после отбрасывания дубликатов, больше одного кортежа мы не получим. Таким образом, X->Y.

Эта аксиома утверждает тривиальные зависимости, которые не зависят от F (которые не могут не выполняться).

2) Пополнение.

Эта аксиома доказывается методом от противного. Допустим, что существуют два кортежа t1 и t2, которые нарушают функциональную зависимость XZ->YZ, но при этом удовлетворяют первой функциональной зависимости, то есть у них атрибуты на XZ совпадают, а на YZ отличаются. В YZ атрибуты Z отличаться не могут, исходя из вышесказанного. Следовательно, должны отличаться атрибуты Y, то есть получается, мы имеем дело с двумя кортежами, у которых атрибуты X совпадают, а атрибуты Y – разные. Это противоречит посылке X->Y.

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

Это можно доказать прямым выводом из функциональных зависимостей. Возьмем два кортежа t1 и t2 из отношения r. Если мы предположим, что t1(x)=t2(x), то мы получим, что t1(y)=t2(y). Следовательно, t1(z)=t2(z), а это является определением функциональной зависимости.

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

Дополнительные правила вывода.

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

1. Аддитивность.

2. Псевдотранзитивность.

3. Проективность.

 

Замыкание множества атрибутов.

Важное следствие правил аддитивности и проективности: если A1, A2,…,An – атрибуты отношения, то X→A1, A2, …, An истинно тогда и только тогда, когда X→Ai, i=1…n

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

Пример:

A1→A2 A3 A4

Используя правило проективности, можно вывести следующие зависимости:

A1→A2

A1→A3

A1→A4

A1→A2 A3

A1→A2 A4

A1→A3 A4

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

Определение. Пусть F – множество функциональных зависимостей на множестве атрибутов U и пусть X с U. Замыканием множеством атрибутов X по отношению к функциональным зависимостям F называется множество атрибутов, для которых функциональная зависимость от X выводится на основе аксиом Армстронга.

Формула х+

Для того, чтобы проверить, что зависимость X→Y следует из F, достаточно проверить принадлежность множества Y к множеству X+. Это следует из определение замыкания множества атрибутов и правила аддитивности.

Алгоритм вычисления замыкания множества атрибутов.

Входные данные:

- множество атрибутов U, определяющих схему отношения,

- F – множество функциональных зависимостей, заданных на U,

- X – множество атрибутов, для которых необходимо построить замыкание X+.

Выходные данные:

Х+ - замыкание множества атрибутов Х+ относительно множества функциональных зависимостей F.

Метод: начнем строить Х+ с множества Х (то есть внесем сначала тривиальные зависимости). Затем будем в цикле добавлять в него новые атрибуты, используя аксиомы транзитивности и рефлексивности.

Нам потребуются две переменные, Xpred и Xsucc.

 

Пример:

Пусть F состоит из следующих 8 зависимостей

1. AB→C

2. C→A

3. BC→D

4. ACD→B

5. D→BG

6. BE→C

7. CG→BD

8. CE→AG

X=BD

 

Применив 6, получаем

2,8 →

В итоге Х+

 

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

Алгоритм:

Вход:

- F

- X→Y.

Выход: истина, если X→Y принадлежит F+

Имея F и X, строим Х+. Если Y принадлежит X+, то истина, иначе ложь. Используя этот алгоритм, можно проверить принадлежность замыканию F+, имея F и не строя F+.

Минимальное покрытие.

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

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

Определение. Два множества функциональных зависимостей F и G, заданные на схеме R, эквивалентны, если F+=G+, то есть если совпадают их замыкания.

Проверим эквивалентность двух множеств функциональной зависимости F и G. Проверим по очереди все зависимости вида X→Y из F на принадлежность к G+ (используя предыдущий алгоритм). Если для всех элементов это справедливо, то есть F является подмножеством G+, то можно заключить, что и F+ является подмножеством G+ (1).

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

Далее проверяем функциональные зависимости из G на принадлежность к F+. Если это так, то G+ является подмножеством F+ (2).

Из условий 1 и 2 имеем, что F+=G+, то есть F эквивалентно G.

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

Определение: Множество функциональных зависимостей F называется минимальным, если

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

- ни для какой зависимости X→A из F не выполняется, что F эквивалентно F-{X→A}, то есть нет такой зависимости в F, выбросив которую F+ не изменится.

- ни у одной функциональной зависимости нет ни одного постороннего атрибута в левой части, то есть такого атрибута, при удалении которого F­­­­­­+, то есть нет функциональной зависимости X→A, у которой для собственного подмножества справедливо F-{X→A}U{Z→A}= F.

Алгоритм построения минимального покрытия.

Имеет те же самые три шага.

1. Каждую функциональную зависимость X→Y, где Y={A1, A2, …, An} заменяем на {X→A1, X→A2, …, X→An}

2. Проверяем каждую функциональную зависимость X→A на избыточность в F. Если X+, вычисленное относительно F-{X→A}, содержит атрибут A, то зависимость X→A избыточна.

3. Определяем, является ли атрибут Bϵ принадлежащий множеству X, посторонним в функциональной зависимости X→A. Можно показать, что его можно удалить, если Aϵ(X-{B})+

Доказательство: Если Aϵ(X-{B})+, то (X-{B})→AϵF+

X→A (X-{B})→A

X→AB

X→A

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

 

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

Декомпозицией реляционной схемы R с атрибутами A1, A2, …, An называется ее замена на множество подмножеств ρ={R1,R2,…,Rk} таких, что Ri с R для каждого i=1…k и R=R1 U R2 U… U Rk.

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

Для заданной схемы отношения R и множества функциональных зависимостей F декомпозиция ρ обладает свойством соединения без потерь и называется декомпозицией без потерь, если для каждого отношения r со схемой R, не нарушающего F, справедливо следующее: r=πR1(r)|><| πR2(r)|><|…|><| πR1(r)

Пример. Возьмем отношение со схемой Поставщик (имя, адрес, товар, цена), которое представлено следующей таблицей:

Имя Адрес Товар Цена
Иванов Бульвар Победы, 1 Кефир
Иванов Бульвар Победы, 1 Молоко
Сидоров Наугорское шоссе, 5 Сметана
Сидоров Наугорское шоссе, 5 Кефир

Имя → адрес

{Имя, товар} → цена

ρ={{имя, адрес},{имя, товар, цена}}

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

Имя Адрес
Иванов Бульвар Победы, 1
Иванов Бульвар Победы, 1
Сидоров Наугорское шоссе, 5
Сидоров Наугорское шоссе, 5

 

Имя Товар Цена
Иванов Кефир
Иванов Молоко
Сидоров Сметана
Сидоров Кефир

Соединим таблицы, соответствующие декомпозиции отношений, получим исходное отношение.

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

Рассмотрим теперь декомпозицию, в которой будут потери.

ρ={{имя, адрес, товар} {товар, цена}}

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

 

Имя Адрес Товар
Иванов Бульвар Победы, 1 Кефир
Иванов Бульвар Победы, 1 Молоко
Сидоров Наугорское шоссе, 5 Сметана
Сидоров Наугорское шоссе, 5 Кефир

 

Товар Цена
Кефир
Молоко
Сметана
Кефир

Соединим таблицы, соответствующие декомпозиции отношений, получим следующее отношение.

Имя Адрес Товар Цена
Иванов Бульвар Победы, 1 Кефир
Иванов Бульвар Победы, 1 Кефир
Иванов Бульвар Победы, 1 Молоко
Сидоров Наугорское шоссе, 5 Сметана
Сидоров Наугорское шоссе, 5 Кефир
Сидоров Наугорское шоссе, 5 Кефир

Отметим, что функциональная зависимость {Имя, товар} → цена перестала работать и появились лишние кортежи (2 и 5). Эта декомпозиция была бы без потерь, если бы для каждого товара была определена фиксированная цена, то есть если бы существовала зависимость товар → цена, либо каждый товар поставлял определенный поставщик, то есть выполнялась бы зависимость товар → {имя, адрес}.

Формально справедливо следующее: декомпозиция ρ={R1,R2} имеет свойство соединения без потерь по отношению к множеству функциональных зависимостей F тогда и только тогда, когда выполняются следующие условия:

(R1∩R2)→(R1-R2)

(R1∩R2)→(R2-R1)

То есть общие атрибуты должны определять остальные атрибуты в каком-либо члене декомпозиции.

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

Алгоритм проверки декомпозиции на соединение без потерь.

Входные данные:

- схема R={A1, A2, …, An}

- множество функциональных зависимостей F

- декомпозиция ρ={R1,R2,…,Rk}

Выходные данные:

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

Метод:

1. Создаем массив размером n*k

  A1 A2 …. Aj An
R1            
R2            
           
Ri            
           
Rk            

 

2. В массив построчно записываем все члены декомпозиции: для каждой декомпозиции в клетку заносим либо аj, если Aj принадлежит Ri, в противном случае заносим bij.

3. Последовательно просматриваем все функциональные зависимости из F: X→Y ищем в массиве две строчки, у которых все атрибуты из X совпадают. Если они находятся, то приравниваем в них символы, соответствующие атрибутам Y. (Если атрибут помечен aj, то и все остальные помечаем aj, если же они равны bij, то делаем их одинаковыми, причем все равно какими, главное что они равны и обрабатываться будут одновременно) Если были просмотрены все функциональные зависимости без изменения массива, то цикл заканчивается

4. Если после выполнения цикла обнаруживается строка, имеющая все символы a, то выдаем истину.

Пример: пусть задана декомпозиция, исходные данные представим в таблице:

  Имя Адрес Товар Цена
Поставщик а1 а2 b13 b14
Поставляет а1 b12 а3 а4

Берем функциональную зависимость имя → адрес.

 

  Имя Адрес Товар Цена
Поставщик а1 а2 b13 b14
Поставляет а1 а2 а3 а4

Получаем строчку, состоящую только из символов а.

Пример: задано отношение R{A,B,C,D,E}

{A→C, B→C, C→D, DE→C, CE→A}

ρ={R1, R2, R3, R4, R5}

R1=AD, R2=AB, R3=BE, R4=CDE, R5=AE

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

  A B C D E
R1 а1 b12 b13 a4 b15
R2 a1 a2 b23 b24 b25
R3 b31 a2 b33 b34 a5
R4 b41 b42 a3 a4 a5
R5 a1 b52 b53 b54 a5

 

A→C

  A B C D E
R1 а1 b12 b13 a4 b15
R2 a1 A2 b13 b24 b25
R3 b31 A2 b33 b34 a5
R4 b41 B42 a3 a4 a5
R5 a1 b52 B13 b54 a5

B→C

  A B C D E
R1 а1 B12 b13 a4 b15
R2 a1 A2 b13 b24 b25
R3 b31 A2 b13 b34 a5
R4 b41 B42 a3 a4 a5
R5 a1 B52 B13 b54 a5

C→D

  A B C D E
R1 а1 B12 b13 a4 b15
R2 a1 A2 b13 a4 b25
R3 b31 A2 b13 a4 a5
R4 b41 B42 a3 a4 a5
R5 a1 B52 b13 a4 a5

DE→C

  A B C D E
R1 а1 B12 b13 a4 b15
R2 a1 A2 b13 a4 b25
R3 b31 A2 a3 a4 a5
R4 b41 B42 a3 a4 a5
R5 a1 B52 a3 a4 a5

CE→A

  A B C D E
R1 а1 B12 b13 a4 b15
R2 a1 A2 b13 a4 b25
R3 a1 A2 a3 a4 a5
R4 a1 B42 a3 a4 a5
R5 a1 B52 a3 a4 a5

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

 

Декомпозиция, сохраняющая зависимости.

ρ={R1,R2,…,Rk}

Важным свойством декомпозиции ρ схемы R является сохранение зависимостей, то есть возможность вывода всех зависимостей F схемы R из проекций F+ на Ri.

Проекцией множеств функциональных зависимостей F на множество атрибутов Z называется множество функциональных зависимостей X→Y на F+, для которых справедливо, что объединение X и Y является подмножеством Z.

πz(F)={X→Y|X→Y Є F+ X˄ XUY c Z}

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

Декомпозиция ρ={R1,R2,…,Rk} сохраняет множество зависимостей F, если объединение всех зависимостей πRi(F) логически влечет все зависимости из F.

Пример: Пусть задано отношение R (город, улица, индекс) с зависимостями:

Город, улица → индекс

Индекс → город

Возьмем декомпозицию ρ={{улица, индекс}, {город, индекс}}. Эта декомпозиция обладает свойством соединения без потерь, так как пересечение {улица, индекс} и {город, индекс} => {улица, индекс}-{город, индекс}, следовательно, индекс → город

Однако проекция F на {улица, индекс} дает только тривиальные зависимости, а проекция F на {город, индекс}, помимо тривиальных, дает зависимость индекс → город. Исходную зависимость город, улица → индекс нельзя вывести из проекций. Таким образом, наша декомпозиция не сохраняет зависимости.

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

Город Индекс
Орел
Орел

 

Улица Индекс
Наугорское шоссе
Наугорское шоссе

 

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

 

Город Улица Индекс
Орел Наугорское шоссе
Орел Наугорское шоссе

 

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

Пример: R={A,B,C,D}

F={A→B, C→D}

ρ={AB, CD}

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

{A,B}∩{С,D}→{A,B}\{C,D} – не соединяется без потерь

πAB(F)U πCD (F)={A→B}U{C→D}=F

Алгоритм проверки декомпозиции на сохранение зависимостей.

Есть очевидный способ проверки декомпозиции ρ на сохранение зависимостей F. Нужно вычислить замыкание F+, сделать проекции F+ на каждый член декомпозиции Ri и потом, объединив эти проекции, надо убедиться, что получилось то же самое множество F+.

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

Алгоритм:

Входные данные: схема R, F – множество функциональных зависимостей, декомпозиция ρ={R1,R2,…,Rk},

Результат: истина или ложь, в зависимости от того, сохраняет ли ρ зависимости или нет.

Метод: обозначим символов G объединение всех проекций функциональной зависимости F на члены ρ.

G=πR1(F)U πR(F)U…U πRk(F)

Для того, чтобы доказать, что декомпозиция ρ сохраняет зависимости, необходимо доказать, что G=F или равны их замыкания. Будем брать по очереди зависимости X→Y из F, и проверять, содержится ли Y в F+.

Но можно не строить множество G, а вычислить X+ относительно F и потом спроецировать на элементы декомпозиции. Таким образом, для каждой зависимости X→Y выполняется алгоритм:

Пусть X+old и X+new – переменные для хранения старого и нового значений замыкания.

X+new:=X

Repeat

X+old :=X+new

For i:=1 to k do

X+new:=X+ newU((X+ new ∩Ri)+ ∩Ri)

Until X+old = X+new

X+:=X+new

То есть X+new нужно пересечь с каждой проекцией, построить замыкание относительно F и опять отсечь то, что не входит в проекцию.

Если Y является подмножеством X+new, X→Y принадлежит G+. Если все функциональные зависимости из F встречаются в F+, то выдаем истину, иначе – выдаем ложь.

Пример: пусть задана схема R={A, B, C, D} и F={A→B, B→C, C→D, D→A}. Возьмем декомпозицию ρ={AB, BC, CD}.

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

На первый взгляд кажется, что D→A теряется, но это не так. На самом деле мы проецируем F+, а не только F и таким образом, в проекции F на AB остается не только A→B, но и B→A. Также в проекции на BC остается B→C и C→B. Соответственно, в СD аналогично, а эти зависимости определяют D→A. Наши зависимости сохранились.

При помощи алгоритма:

То же самое должен показать рассмотренный выше алгоритм. Возьмем D→A, начнем вычислять {D}+ относительно G. Сначала X+new={D}

Для проекции АВ ничего нового не получим, так как

{D}U(({D}∩ {AB})+∩{AB}={D}U{(0…)}

То же самое получится и для проекции ВС. Если же взять проекцию CD, то мы получим:

X+new={D}U(({D}∩ {CD})+∩{CD})

={D}U(({D}+∩{CD}))={D}U({ABCD}∩CD)={CD}

На следующем витке цикла, взяв проекцию ВС и имея X+new=CD, получим X+new=BCD, на третьем витке цикла, взяв проекцию АВ, так как A принадлежит X+new, заключаем, что из G можно вывести D→A. Остальные члены F проверяются элементарно, следовательно, мы имеем декомпозицию, сохраняющую зависимости.

 



<== предыдущая лекция | следующая лекция ==>
Проектирование структуры БД на основе функциональных зависимостей. | Нормальные формы.


Карта сайта Карта сайта укр


Уроки php mysql Программирование

Онлайн система счисления Калькулятор онлайн обычный Инженерный калькулятор онлайн Замена русских букв на английские для вебмастеров Замена русских букв на английские

Аппаратное и программное обеспечение Графика и компьютерная сфера Интегрированная геоинформационная система Интернет Компьютер Комплектующие компьютера Лекции Методы и средства измерений неэлектрических величин Обслуживание компьютерных и периферийных устройств Операционные системы Параллельное программирование Проектирование электронных средств Периферийные устройства Полезные ресурсы для программистов Программы для программистов Статьи для программистов Cтруктура и организация данных


 


Не нашли то, что искали? Google вам в помощь!

 
 

© life-prog.ru При использовании материалов прямая ссылка на сайт обязательна.

Генерация страницы за: 0.021 сек.