русс | укр

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

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

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

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


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

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


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


Для множества функциональных зависимостей F вида X→A, заданного на множестве атрибутов А1, А2, …, An можно построить направленный граф, имеющий два типа вершин.

1. Для каждого атрибута Aj строим вершину, помеченную Aj.

2. Для каждой функциональной зависимости Xj→Aj, где Х ={Aj1, Aj2, …, Ajm строим либо дугу, где m=1, либо дополнительную вершину, помечаем ее Xj, а в нее входят дуги от вершин Aj1 и так далее.

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

Пример ПОТОМ

 

Нормализация схем отношений.

Существуют два подхода к нормализации. Один основан на декомпозиции, а другой – на синтезе схемы.

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

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

Алгоритм декомпозиции.

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

1) Частичная зависимость.

R{K1, K2,X, Y}

X, Y – множество неключевых атрибутов,

К1, К2 – ключи

К2 → Х

 

Заменяем R на две схемы.

R1={K1, K2, Y}, R2={K1, X}

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

2) Транзитивная зависимость. Пусть R={K, X1, X2, X3}

K – ключевые атрибуты,

X1, X2, X3 – множество неключевых атрибутов.

K→X1→X

 

Заменяем R на две схемы: R1={K, X1, X3}, R2={X1, X2}

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

3) Сложнотранзитивная зависимость



Пусть R={K1, K12, X1, X2, X3}

K2X1→X2

 


 

CN PN Date CName PName Type Color   PName Color SN SName Q

CN → CName

PN → PName

SN → SName

PName → type

PName → color

CN, PN→SN

CN, PN, SN → Q

Имеется транзитивная зависимость SN → SName

CN PN Date CName PName Type Date CName PName Color SN SName Q

Выделяем схему:

CN PN SN

Остается:

CN PN Date CName PName Color SN SName Q

 


Алгоритм синтеза.

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

1. Разбиваем множество функциональных зависимостей F на подмножество Fi так, чтобы в подмножестве были все функциональные зависимости с одинаковыми левыми частями.

2. Для каждого Fi строим реляционную схему, состоящую из всех атрибутов, участвующих в Fi. Эта схема будет в третьей нормальной форме, а ключ ее – в левой части Fi.

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

 

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

Схема, находящаяся в НФБК, может иметь аномалии обновления. Например, имеется отношение «Студент».

Номер зачетки Предмет Спорт
БД Футбол
БД Теннис
ООП Футбол
ООП Теннис
ИиП Лыжи

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

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

Для того, чтобы избежать избыточности вследствие независимости данных, необходимо изучать многозначные зависимости.

Определение. Пусть имеется схема отношения R={A1, A2, …., An}, а в ней непересекающиеся подмножества X и Y. Z=R - (X U Y). Тогда говорят, что существует многозначная зависимость из X в Y (X→→Y), если для каждого отношения r со схемой R справедливо, что для любых двух кортежей t1 и t2 из r с равными проекциями на х следует, что в r существует кортеж t3, такой что его проекция на х равна проекции на х t2, проекция t3 на y равна проекции на y t1, проекция t3 на z равна проекции на z t2.

То есть для любых двух кортежей t1 и t2, у которых t1(x)=t2(x), обязательно существует в r кортеж t3, такой, что <t1(x), t1(y), t2(z)>. Из соображений симметрии существует кортеж t4, такой, что <t1(x), t2(y), t1(z)>.

Например, в вышестоящей таблице действует многозначная зависимость НомерЗачетки →→Предмет

Поэтому, если взять два кортежа t1=<100, БД, Футбол> и t2=<100, ООП, Теннис>, то из определения многозначной зависимости следует существование еще двух кортежей: t3=<100, ООП, Теннис> и t4=<100, ООП, Футбол>.

 

Многозначная зависимость является свойством предметной области: то есть мы знаем, что если взять какой-то предмет (БД), который читает в t1 в аудитории a1 преподаватель p1 студенту s1 с оценкой m1 и, если этот же предмет читается в t2 в аудитории а2 преподавателем p2 студенту s2 с оценкой m2.

Тривиальная многозначная зависимость время, аудитория →→ аудитория.

Можно доказать, что выполнение функциональной зависимости X→Y влечет выполнение многозначной зависимости X→→Y. Если в отношении R={X, Y, Z} задана многозначная зависимость X→→Y, то справедливо и X→→Z, то есть многозначные зависимости всегда появляются парами (X→→Y|Z).

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

Теорема: R={X, Y, Z}, тогда декомпозиция R на (X, Y) и (X, Z) обладает свойством соединения без потерь, если на R задана многозначная зависимость X→→Y|Z.

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

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

 

 



<== предыдущая лекция | следующая лекция ==>
Нормальные формы. | Лекция 4. Альтернативные подходы построения баз данных


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


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

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

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


 


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

 
 

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

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