Файл: Управление данными (пособие).pdf

ВУЗ: Не указан

Категория: Не указан

Дисциплина: Не указана

Добавлен: 31.03.2021

Просмотров: 1609

Скачиваний: 25

ВНИМАНИЕ! Если данный файл нарушает Ваши авторские права, то обязательно сообщите нам.
background image

 

111

 

При

 

этом

 

атрибуты

 

X

 

называют

 

детерминантом

а

 

атрибуты

 

зависимой

 

частью

 

функциональной

 

зависимости

 

Важное

 

уточнение

 

в

 

этом

 

определении

говорящее

 

о

 

том

что

 

функциональная

 

ависимость

 

и еет

 

м сто

 

д я

 

всех

 

возм жных

 

состояний

 

отношения

показывает

что

з

м

е

л

о

 

определение

 

функциональных

 

зависимостей

для

 

отно

 

ограничений

 

целостности

 

о

 

функциональных
р

Д

шения

относится

 

к

 

разновидности

 

указания

тношения

В

 

конкретном

 

отношении

 

обычно

 

присутствует

 

не

 

одна

а

 

множество

 

 

зависимостей

Например

в

 

отношении

представленном

 

на

 

ис

. 10.1, 

ключом

 

которого

 

является

 

составной

 

атрибут

  {

КОД

_

СТУД

ИСЦИПЛИНА

}, 

имеют

 

место

 

несколько

 

функциональных

 

зависимостей

УСПЕВАЕМОСТЬ

 

 

 

КОД

_

СТУД

 

ИМЯ

_

СТУД

 

ДИСЦИПЛИНА

 

ОЦЕНКА

 

С

Иванов

 

Физика

 5 

С

Иванов

 

Математика

 4 

С

Иванов

 

История

 4 

С

Иванов

 

Информатика

 5 

С

Смирнов

 

Физика

 3 

С

Смирнов

 

Математика

 4 

С

Смирнов

 

Информатика

 3 

С

Попова

 

Математика

 5 

С

Попова

 

Информатика

 5 

С

Попова

 

Химия

 4 

С

Иванов

 

Физика

 5 

С

Иванов

 

Информатика

 4 

Рис

.  10.1.  

Пример

 

отношения

 

с

 

функциональными

 

зависимостями

 

,

 {

КОД

_

СТУД

ДИСЦИПЛИНА

}

{

ИМЯ

_

СТУД

ОЦЕНКА

 {

КОД

_

СТУД

ДИСЦИПЛИНА

ИМЯ

_

СТУД

}

{

ОЦЕНКА

ИНА

}

{

КОД

_

СТУД

 {

КОД

_

СТУД

ДИСЦИПЛИНА

ИМЯ

_

СТУД

}

{

ДИСЦИПЛИНА

т

в

а

 {

КОД

_

СТУД

 

ДИСЦИПЛИНА

} {

ИМЯ

_

СТУД

 {

КОД

_

СТУД

ДИСЦИПЛИНА

}

{

ОЦЕНКА

 {

КОД

_

СТУД

ДИСЦИПЛ

 

Однако

не

 

все

 

имеющие

 

место

 

в

 

отношении

 

функциональные

 

зависимости

 

представляют

 

собой

 

практический

 

интерес

в

 

частности

так

 

называемые

ривиальные

 

функциональные

 

за исимости

 

Функциональную

 

зависимость

 

называют

 

тривиальной

 

тогда

 

и

 

только

 

тогда

когд

 

правая

  (

зависимая

часть

 

символической

 

записи

 

данной

 

зависимости

 

является

 

подмножеством

 

ее

 

левой

 

части

 (

детерминанта

). 

 

Таким

 

образом

в

 

приведенном

 

выше

 

примере

 

зависимости

 

 {

КОД

_

СТУД

ДИСЦИПЛИНА

}

{

КОД

_

СТУД

и

 


background image

 

112

 {

КОД

_

СТУД

ДИСЦИПЛИНА

ИМЯ

_

СТУД

}

{

ДИСЦИПЛИНА

являются

 

тривиальными

Понятно

что

 

фиксация

 

наличия

 

между

 

атрибутами

 

такого

 

рода

 

никакой

 

дополнительной

 

смысловой нагрузки

 

не

 

несет

 

Гов

кци

ависим

 

так

ить

что

 

некоторые

 

за

имости

быть

 

выве

 

других

 

фу циональных

 

зависимостей

висимо

{

КОД

_

СТУД

ДИСЦИПЛИНА

}

{

ИМЯ

КА

}  

следует

 

из

 

за

мостей

{

КОД

_

СТУД

ДИСЦИПЛИНА

}

{

ИМЯ

_

{

КОД

_

СТУД

ДИСЦИПЛИНА

}

{

ОЦЕ

Очевидн

что

 

добавление

 

к

 

множ

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

 

выведенных

 

них

 

ж

е

 

не

 

доба

й

 

новой

 

ормации

 

о

 

характере

 

зависимостей

 

между

 

атрибутами

Тем

 

не

 

менее

то

что

 

одни

 

зависим

что

 

могут

 

существовать

 

множества

 

зависимостей

 

эквивалентных

 

друг

 

другу

 

с

 

точки

 

зрен

 

зависимостей

 

оря

 

о

 

фун

ональных

 

з

остях

можно

же

 

замет

вис

 

могут

 

денными

 

из

нк

За

сть

  

_

СТУД

ОЦЕН

виси

  

СТУД

}

 

и

  

НКА

}

о

еству

 

ф

 

з

из

 

е

 

такж

вляет

 

никако

инф

ости

 

могут

 

быть

 

выведены

 

из

 

других

говорит

 

о

 

том

ия

 

отражаемой

 

ими

 

информации

 

о

 

предметной

 

области

 

Множество

 

всех

 

функциональных

 

зависимостей

которые

 

задаются

 

данным

 

множеством

 

функциональных

 

зависимостей

 S, 

т

.

е

могут

 

быть

 

выведены

 

из

 

этих

 

зависимостей

называется

 

замы анием

 (closure) 

к

множества

 

зависимостей

 S 

и

 

обозначается

 S+. 

 

Правила

позволяющие

 

из

 

данного

 

множества

 

зависимостей

 

S

 

вывести

 

его

 

замыкание

 

S

+

называемые

 

правилами

 

Армстронга

имеют

 

следующий

 

вид

 

Пусть

 

A

B

C

 

и

 

D

 

произвольные

 

подмножества

 

множества

 

атрибутов

 

заданного

 

но ения

 

R

тогд

ля

 

них

 

имеют

 

место

 

следующие

 

правила

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

:  

если

 

B

 

является

 

подмножеством

 

A

то

 

A

B

т

.

е

AB

A

BC

B

 (

это

 

на

 

самом

 

деле

 

тривиальная

 

зависимость

). 

от ш

а

 

д

Допо
Т

и

з
п
в

D

.

 

лнение

:  

 

если

 

A

B

то

 

AC

BC

ранзит вность

:  

если

 

A

B

 

и

 

B

C

то

 

A

C

Эти

 

три

 

правила

 

являются

 

полным

 

набором

позволяющим

 

вывести

 

все

 

ависимости

составляющие

 

замыкание

 

S

множества

 

зависимостей

 

S

Из

 

этих

 

равил

 

для

 

упрощения

 

задачи

 

практического

 

вычисления

 

замыкания

 

S

+

 

можно

 

ывести

 

несколько

 

следствий

Самоопределение

:

  

A

A. 

Декомпозиция

:  

если

 A

BC

то

 

A

B

 

и

 

A

C

.

 

Объе

 

A

BC  

динение

:  

если

 

A B

 

и

 

A C

то

Композиция

:  

если

 

A B

 

и

 

C D

то

 

AC

B


background image

 

113

На

 

практике

 

обычно

 

более

 

важным

 

зави

является

 

не

 

нахождение

 

множества

 

с

х

 

определений

симостей

 

S

+

являющихся

 

замыканием

 

множества

 

функциональных

 

зависимостей

 

S

а

 

нахождение

 

ответа

 

на

 

вопрос

 

может

 

ли

 

данная

 

конкретная

 

функциональная

 

зависимость

 

X

быть

 

выведенной

 

из

 

имеющегося

 

множества

 

зависимо тей

 

S

Дадим

 

еще

 

несколько

 

полезны

Пусть

 S1 

и

 S2 

являются

 

двумя

 

множествами

 

функциональных

 

зависимостей

Если

 

любая

 

функциональная

 

зависимость

которая

 

является

 

зависимостью

 

множества

 S1, 

также

 

является

 

зависимостью

 

множества

 

S2, 

т

.

е

если

 S1

+

   

является

 

подмножеством

 S2

+

то

 S2 

называется

 

покрытием

 (cover) 

для

 S1. 

 

Если

 S2 

является

 

покрытием

 

для

 S1, 

а

 S1 

является

 

покрытием

 

для

 S2, 

т

.

е

если

 S1

+

 = S2

+

то

 S1 

и

 S2 

эквивалентны

 

Функциональная

 

неприводимой

 

слева

 

(

или

 

 

зависимость

 

называется

функциона

 

атрибут

 

не

 

может

 

быть

 

опущен

 

из

 

льно

 

полной

), 

если

  

ни

 

один

ее

 

детерм н

мыкания

  S

+

  (

без

 

преобразования

 

и анта

 

без

 

изменения

 

за

множества

 S  

ляющееся

 

ему

 

эквивалентным

).  

 

в некоторое

 

множество

не

 

яв

Или

менее

 

с р

функциональная

 

неприводимой

 

слева

 

(

или

 

т ого

но

 

более

 

просто

зависимость

 

называется

 

функционально

 

полной

), 

если

  

 

не

 

 

быть

 

опущен

 

из

 

ни

 

один

 

атрибут

может

ее

 

детерминанта

 

без

 

нарушения

 

этой

 

зависимости

.  

10.2. 

Нормализация

 

отношений

 

базы

 

данных

 

в

ос

м

т

 

в

 

теории

 

нормализации

 

называют

 

первой

 

нормальной

 

формой

  (

сокращенно

  1

НФ

). 

Это

однако

не

 

единственная

 

нормальная

 

форма

 

представления

 

реляционных

 

отношений

В

 

настоящее

 

время

 

кроме

 

первой

 

нормальной

 

формы

 

известны

 

еще

 

пять

 

других

Для

 

чего

 

же

 

необходимо

 

введение

 

новых

 

нормальных

 

форм

   

и

 

преобразование

 

отношений

 

в

 

нормальные

 

формы

 

более

 

высокого

 

порядка

Дело

 

в

 

том

что

 

отношения

находящиеся

 

в

 

первой

 

нормальной

 

форме

 

могут

 

Нормальные

 

формы

 

Как

 

уже

 

го орил ь

 

выше реляционная

 

одель

 

поддерживает

 

только

 

нормализованные

 

отношения

т

.

е

о ношения

содержащие

 

только скалярные

 

(

атомарные

значения

 

атрибутов

Такую

 

форму

 

отношений

 


background image

 

114

обладать

 

целым

 

рядом

 

нежелательных

 

свойств

Рассм

отношение

 

УСПЕВАЕМОСТЬ

представленное

 

на

 

рис

.10.2. 

отрим

 

в

 

качестве

 

примера

 

УСПЕВАЕМОСТЬ

 

 

 

КОД

_

СТУД

 

ИМЯ

_

СТУД

 

ДИСЦИПЛИНА

 

ОЦЕНКА

 

С

Иванов

 

Физика

 5 

С

Иванов

 

Математика

 4 

С

Иванов

 

История

 4 

С

Иванов

 

Информатика

 5 

С

Смирнов

 

Физика

 3 

С

Смирнов

 

Математика

 4 

С

Смирнов

 

Информатика

 3 

С

Попова

 

Математика

 5 

С

Попов

Информатика

 5 

а

 

С

Попова

 

Химия

 4 

С

Иванов

 

Физика

 5 

С

Иванов

 

Информатик

а

 

Рис

.  

вой

 

форме

 

Нетрудно

 

заметить

что

 

отнош

твует

 

определенная

 

избыточность

Дей

тельн

огих

 

кор

уется

 

информация

 

о

 

том

какому

 

коду

 

с

тная

 

фамилия

 

студента

Наличие

 

избыточности

 

информации

 

рассматривается

 

как

 

недостаток

 

отно

ма

 

памяти

требуемой

 

для

 

хранения

 

информации

 

системе

Гораздо

жным

 

является

 

то

что

 

и

то

яет

 

поддерж

е ся

 

в

 

отношении

 

и форм

Н

ае

 

амилии

 

студента

отнош

должны

быть

 

коррек

значения

 

соответствующего

 

атри

 

всех

 

кортежах

о

сящих

уденту

в

 

противном

 

с

данн

ошении окажут

против

тоянии

Но

я

ан

авляет

 

10.2.  

Пример

 

отношения

 

в

 

пер

 

нормальной

 

в

 

этом

о

во

 

мн

ении

 

присутс

тежах

 

дублир

стви

тудента

 

соответствует

 

конкре

шения

И

 

дело

 

здесь

 

не

 

только

 

и

 

не

 

столько

 

в

 

том

что

 

дублирование

 

информации

 

приводит

 

к

 

увеличению

 

объе

 

в

 

компьютерной

чность

 

затруд

 

более

 

ва

ие

 

содержащ

з
н

бы

н

ан

й

ации

 

в

 

целостном

 

состоянии

апример

в

 

случ

изменения

 

ф

в

 

ении

 

 

с

тированы

 

бута

 

во

тно

ся

 

к

 

этому

 

ст

лучае

ые

 

в

 

отн

 

ся

 

в

 

оречивом

 

сос

рмализация

 

отношений

 

рел ционной

 

базы

 

д ных

 

предст

собой

зо

т

целью

 

 

формализованные

 

преобра вания

 

этих

 

о ношений

 

с

 

у

ранения

их

 

воз

нежела

свойств

в

 

общем

 

ст

 

в

 

н

можных

 

тельных

 

которыми

 

случае

 

может

 

облад

ическая

 

 

отнош

ихся

 

в

 

ать

 

лог

структура

ений

находящ

перво

ме

без

 

потер и

х ного

 

отношения

в

 

й

 

нормальной

 

фор

ь

 

нформации

 

ис од

том

 

и

о а

числе

 

и

 

о

 

зависимостях

имеющ х

 

место

 

между

 

ег

 

трибутами

Теория

н

какая

 

из

 

двух

 

логическая

 

струк

ний

 

в

редпочт

ношение

 

R1{

КОД

_

СТ

ИМЯ

_

С

Е

ЛИНА

О

или

 

структ

R2{

КОД

_

СТУД

 

ализа

норм

ции

 

позволяет апример

ответить

 

на

 

вопрос

 –  

тура

 

отноше

я ляется

 

п

ительней

от

УД

ТУД

ФАКУЛЬТ Т ДИСЦИП

ЦЕНКА

}

 

ура

 

из

 

двух

 

отношений

 

ИМЯ

_

СТУД

ФАКУЛЬТЕТ

и

 


background image

 

115

R3{

 

КОД

_

СТУД

ДИСЦИПЛИНА

ОЦЕНКА

}

Нормальными

 

формами

 

более

 

высокого

 

порядка

 

являются

 

определенные

 

Коддом

 (Codd) 

первая

вторая

 

и

 

третья

 

нормальные

 

формы

 (1

НФ

, 2

НФ

 

и

 3

НФ

), 

введенная

 

Бойсом

 (Boyce) 

и

 

Коддом

 

так

 

называемая

  

нормальная

 

форма

 

Бойса

-

Кодда

  (

НФБК

и

 

определенные

 

Фейгиным

 (Fagin)

четвертая

 

и

 

пятая

 

нормальные

 

формы

 (4

НФ

 

и

 5

НФ

). 

На

 

рис

.10.3 

показано

что

 

множества

 

отношений

находящихся

 

в

 

различных

 

нормальных

 

формах

оказываются

 

как

 

бы

 

вложенными

 

друг

 

в

 

друга

Так

например

отношение

находящееся

 

в

  3

НФ

 

одновременно

 

будет

 

находиться

 

и

 

в

  2

НФ

 

и

  1

НФ

но

 

не

 

обязательно

 

будет

 

находиться

 

в

 

НФБК

Отношение

 

же

 

находящееся

 

в

  5

НФ

 

одновременно

 

будет

 

находиться

 

и

 

во

 

всех

 

остальных

 

нормальных

 

формах

 

Пространство

 

всех

 

отношений

 (

нормализованных

 

и

 

ненормализованных

Множество

 

отношений

 

в

 1

НФ

 (

нормализованные

 

отношения

Множество

 

отношений

 

во

 2

НФ

 

Множество

 

отношений

 

в

 3

НФ

 

Множество

 

о

 

тношений

 

в

 

НФ

 

БК

Множество

 

отн

в

 4

НФ

 

ошений

 

 

Отношения

 

в

 5

НФ

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Рис

.  10.3.  

Вложенность

 

нормальных

 

форм

 

отношений

 

 

Ниже

 

будет

 

показано

что

 

преобразование

   

отношений

 

в

 

нормальную

 

форму

 

более

 

высокой

 

тепени

 

является

 

в

 

определенном

 

смысле

  «

более

 

желательным

». 

Важно

 

сразу

 

же

 

заметить

что

 

процедура

 

нормализации

 

отношений

 

должна

 

быть

 

обязательно

 

обратимой

Это

 

означает

что

 

преобразование

 

отношений

 

в

 

нормальные

 

формы

 

более

 

высокой

 

степен

с

и

 

осуществляется

тируется

 

возможность

 

обратного

 

п

 

без

 

потерь

 

информации

которую

 

эти

 

отношения

 

представляют

так

 

как

 

всегда

 

гаран

реобразования

т

.

е

полного

 

восстановления

 

исходной

 

информации