Лекции по теории проектирования баз данных (БД)

Лекции по теории проектирования баз данных (БД)

Лекция 1

Технология проектирования баз данных

Вопросы:

1. Проектирование базы данных как элемент информационной технологии;

Теоретические основы проектирования БД;

1. Синтез БД.

Проектирование базы данных как элемент информационной технологии

Как видно из материалов предыдущих лекций основу большинства

информационных технологий составляют большие массивы накопленной

информации. Основной формой организации хранения данных в информационных

системах являются базы данных. В курсе “Автоматизированные системы

обработки учетной информации” мы рассмотрели основные понятия, связанные

с моделями данных, теоретические основы разработки простейших баз данных

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

информационной технологии, необходимо по новому взглянуть на проблему

проектирования базы.

Проблемы проектирования связаны с функциями БД в программно -

технологической среде, поддерживающей информационные технологии. В общем

случае место БД можно отразить следующей схемой:

Приложения поддержки

информационных

технологий

Прочие

приложения

Поскольку база данных является связующим звеном между

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

проектирование можно разделить на два направления: проектирование

структуры и пользовательских приложений и распределение данных по

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

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

АСОЭИ, рассматривая основы реляционной алгебры и разработки реляционных

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

Одной из распространенных технологий разработки БД является следующая:

1. сбор данных о предметной области;

1. анализ представлений пользователей;

1. интеграция представлений пользователей;

1. разработка сетевой модели;

1. преобразование сетевой модели в первую нормальную форму реляционной

модели;

1. нормализация отношений путем преобразования их к третьей нормальной

форме.

В результате получается модель реляционной базы данных, которая

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

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

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

результате интеграции представлений пользователей. Преобразование

сетевой модели в реляционную дает первую нормальную форму последней.

Напомним, что отношение R находится в первой нормальной форме, если

значения в dom(A) являются атомарными для каждого атрибута А в R .

Вторая и третья нормальные формы позволяют избежать аномалий при

обновлении данных и избавится от информационной избыточности в

отношениях. Напомним, что отношение R нормальной форме, если оно

находится в первой нормальной форме и каждый атрибут не являющийся

ключом полностью зависит от любого ключа в R. И отношение R находится в

третьей нормальной форме, если оно находится во 2НФ и каждый атрибут,

не являющийся первичным ключом не транзитивно зависит от любого

возможного ключа.

Недостатком такого подхода является то, что в моделях, имеющих

десятки и сотни атрибутов очень трудно имперически построить модель,

все отношения которой заданы в третьей нормальной форме и связаны между

собой таким образом, что составляют единое целое.

Пример.

Другим подходом является возможность формального синтеза модели на

основании априорно установленных зависимостей между атрибутами.

Зависимости между атрибутами устанавливаются на основании смысловой

связи.

Пример.

НОМЕР_ЗАЧЕТКИ - ИМЯ_СТУДЕНТА

НОМЕР_РЕЙСА - ДАТА_ВЫЛЕТА

Безусловно такой подход к разработке модели базы данных

предпочтительнее, так как позволяет автоматизировать процесс

моделирования. Для реализации этого подхода необходимо расширение

теоретической базы, полученной в курсе АСОЭИ.

Теоретические основы проектирования БД.

Основные понятия.

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

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

фундаментальные формализации. В теории реляционных баз данных к ним

относятся понятия атрибута, отношения, ключа и функциональной

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

Атрибутом будем называть поименованное свойство объекта и обозначать

Аi , где [pic]. Домен атрибута Аi обозначим dom(Аi). Тогда отношением R

называется конечное множество атрибутов [pic]. Ключ отношения R является

подмножеством К = [pic] со следующим свойством. Для любых двух различных

кортежей t1 и t2 в R существует такое [pic], что t1(B)[pic]t2(B). Другими

словами , не существует двух кортежей, имеющих одно и то же значение на

всех атрибутах из К . Таким образом, достаточно знать К - значение

кортежа, чтобы идентифицировать кортеж однозначно.

Пример.

СТУДЕНТ[НОМЕР_ЗАЧЕТКИ,ИМЯ,КУРС,ГРУППА]

Ключи, явно указанные в модели называются выделенными. Могут быть

ключи отличные от выделенных и называемые неявными ключами. Например ИМЯ

в предыдущем прмере.

Под функциональной зависимостью атрибутов или F-зависимостью понимают

такую связь между атрибутами, когда значения кортежа на одном множестве

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

множестве атрибутов. Так в отношении:

ГРАФИК[ПИЛОТ,РЕЙС,ДАТА,ВРЕМЯ]

ПИЛОТ функционально зависит от {РЕЙС,ДАТА}

F-зависимости принято обозначать {РЕЙС,ДАТА}-> ПИЛОТ и говорят, что

РЕЙС и ДАТА функционально определяют ПИЛОТ.

В терминах теории множеств и реляционной алгебры F-зависимость

определяется так. Пусть R отношение и X, Y подмножества атрибутов в R.

Отношение R удовлетворяет функциональной зависимости X -> Y, если (Y((X-

x®) имеет не более чем один кортеж для каждого Х - значения х. В F-

зависимости X->Y подмножество X называется левой частью, а Y - правой

частью.

Лекция 2

Такая интерпретация функциональной зависимости является основой

алгоритма SATISFIES, приводимого ниже.

SATISFIES

Вход: Отншение R и F-зависимость X->Y.

Выход: истина, если R удовлетворяет X->Y, ложь - в противном случае.

SATISFIES(R,X->Y)

1. Отсортировать отношение R по Х-столбцам так, чтобы собрать кортежи с

равными Х-значениями вмести.

1. Если каждая совокупность кортежей с равными Х-значениями имеет также

равные Y-значения, то на выходе получаем истину, а в противном случае -

ложь.

Этот алгоритм проверяет, удовлетворяет ли отношение R F-зависимости

X -> Y.

Пример.

В результате выполнения алгоритма SATISFIES выясним удовлетворяет ли

F-зависимость РЕЙС -> ВРЕМЯ_ВЫЛЕТА следующему отношению

ГРАФИК

|ПИЛОТ |РЕЙС |ДАТА |ВРЕМЯ_ВЫЛЕТА |

|А... |83 |9 авг |10:15 |

|П... |83 |11 авг |10:15 |

|А... |116 |10 авг |13:25 |

|Р... |116 |12 авг |13:25 |

|П... |281 |8 авг |5:50 |

|С... |281 |9 авг |5:50 |

|П... |301 |12 авг |18:35 |

|С... |412 |15 авг |13:25 |

Однако F-зависимость ВРЕМЯ_ВЫЛЕТА -> РЕЙС согласно этому алгоритму не

выполняется для этого отношения

ГРАФИК

|ПИЛОТ |РЕЙС |ДАТА |ВРЕМЯ_ВЫЛЕТА |

|П... |281 |8 авг |5:50 |

|С... |281 |9 авг |5:50 |

|А... |83 |9 авг |10:15 |

|П... |83 |11 авг |10:15 |

|А... |116 |10 авг |13:25 |

|Р... |116 |12 авг |13:25 |

|С... |412 |15 авг |13:25 |

|П... |301 |12 авг |18:35 |

Для разработки модели базы данных необходимо знать полное множество F-

зависимостей. Чтобы найти их, необходимы семантические знания об исходном

отношении R. Поэтому можно считать семейство F-завсимостей заданным.

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

найдены все F-зависимости отношения R. Для того, чтобы найти все F-

зависимости, если известны некоторые из них, можно воспользоваться

аксиомами вывода. Возможность получения новых F-зависимостей с помощью

аксиом вывода базируется на следующем правиле. Мнжество F-зависимостей F

влечет за собой F-зависимость X -> Y (обозначение: F =[pic]X -> Y ), если

каждое отношение удовлетворяющее всем зависимостям в F, удовлетворяет также

зависимости X -> Y. Аксиома вывода - это правило, устанавливающее, что если

отношение удовлетворяет определенным F-зависимостям, то оно должно

удовлетворять и некоторым другим F-зависимостям. Существует шесть аксиом

вывода:

Рефлексивность: X -> X.

Пополнение: X -> Y влечет за собой XZ -> y.

Аддитивность: X -> Y и X -> Z влечет за собой X -> YZ.

Проективность: X -> YZ влечет за собой X -> Z.

Транзитивность: X -> Y и Y -> Z влечет за собой X -> Z.

Псевдотранзитивность: X -> Y и YZ -> W влечет за собой XZ -> W.

Пример.

Пусть дано отношение R , а X , Y и Z подмножества R . Предположим,

что отношению удовлетворяет XY -> Z и X -> Y . Согласно аксиоме

псевдотранзитивности получим XX -> Z или X -> Z.

Если даны аксиомы рефлексивности, пополнения и псевдотранзитивности,

то из них можно вывести все остальные. Иногда их называют аксиомами

Армстронга.

Пусть F-множество F-зависимостей для отношения R . Замыкание F ,

обозначаемое F+ , - это наименьшее содержащее F множество, такое что при

применении к нему аксиом Армстронга нельзя получить ни одной F -

зависимости, не принадлежащей F.

Пример.

Пусть F = {AB -> C, C -> B } - множество F-зависимостей на R(ABC). F+

= {A -> A, AB -> A, AC -> A, ABC -> A, B -> B, AB -> B, BC -> B, ABC ->

B, C -> C, AC -> C, BC -> C, ABC -> C, AB -> AB, ABC -> AB, AC -> AC, ABC

-> AC, BC -> BC, ABC -> BC, ABC -> ABC, AB -> C, AB -> AC, AB -> BC, AB

-> ABC, C -> B, C -> BC, AC -> B, AC -> AB}

Таким образом, если известно множество F-зависимостей удовлетворяющих

отношению R, можно найти все F- зависимости, удовлетворяющие этому

отношению. Говорят, что F = X -> Y ,если X -> Y [pic] F+ .

Лекция 3

Получение замыкания F+ не обязательно для установления F = X ->

Y.

Для этого достаточно воспользоваться алгоритмом MEMBER .

Алгоритм MEMBER.

Вход: Множество F-зависимостей F и F-зависимость X -> Y.

Выход: истина, если F = F = X -> Y, ложь в противном случае.

MEMBER(F, X -> Y)

begin

if Y [pic] CLOSURE(X,F) then return (истина)

else return(ложь)

end

Здесь CLOSURE алгоритм, позволяющий выявить список атрибутов входящих

в множество F, который имеет вид.

Алгоритм CLOSURE.

Вход: Множество атрибутов Х и множество F-зависимостей F.

Выход: Замыкание Х над F.

CLOSURE(X,F)

begin

OLDDEP = 0; NEWDEP = X

while NEWDEP [pic] OLDDEP do begin

OLDDEP = NEWDEP

for каждая F- зависимость W -> Z в F do

if NEWDEP [pic] W then

NEWDEP = NEWDEP [pic] Z

end

return(NEWDEP)

end

Пример работы алгоритма MEMBER

Пусть F = {НОМЕР_РЕЙСА ДАТА_ВЫЛЕТА -> КОЛИЧЕСТВО_МЕСТ,

НОМЕР_РЕЙСА -> ПУНКТ_ОТПРАВЛЕНИЯ, НОМЕР_РЕЙСА ДАТА_ВЫЛЕТА -> ПИЛОТ} и

необходимо установить F |= НОМЕР_РЕЙСА -> ПИЛОТ

Используем для этого алгоритм MEMBER

Покрытия функциональных зависимостей

Для формирования БД, как системы взаимосвязанных отношений на

основании известных (из семантических соображений) F-зависимостей

необходимо иметь способ минимизации первоначального множества F-

зависимостей. Это необходимо для минимизации дублирования данных,

обеспечения их согласованности и целостности. Теоретической основой для

построения такого способа является теория покрытий функциональных

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

Определение.

Два множества F-зависимостей F и G над отношением R эквивалентны,

[pic] , если F+ = G+ . Если [pic], то F есть покрытие для G.

Предполагается, что имеет смысл рассматривать в качестве покрытий такие

множества F, которые не превосходят множество G по числу F-зависимостей.

Из этого определения следует, что для установления факта, что

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

определить эквивалентность F и G. Практически это достигается путем

использования следующего алгоритма:

Алгоритм EQUIV

Вход: два множества F- зависимостей F и G.

Выход: истина, если [pic]; ложь в противном случае.

EQUIV(F,G)

begin

v=DERIVES(F,G) and DERIVES(G,F);

return(v)

end

Здесь DERIVES алгоритм проверяет условие F |= G и имеет вид:

Алгоритм DERIVES

Вход: два множества F- зависимостей F и G.

Выход: истина, если F |= G; ложь в противном случае.

DERIVES(F,G)

begin

v= истина

for каждая F-зависимость X -> Y из G do

v = v and MEMBER(F, X -> Y)

end

return(v)

end

Множество F-зависимостей F не избыточно, если у него нет такого

собственного подмножества F’ , что F’[pic]F . Если такое множество F’

существует, то F избыточно. F является не избыточным покрытием G, если F

есть покрытие G и F не избыточно.

Пример. Пусть G = { AB -> C, A -> B, B -> C, A -> C}. Множество F=

{AB -> C, A -> B, B -> C} эквивалентно G, но избыточно, потому что F’ =

{A -> B, B -> C} также является покрытием G. Множество F’ представляет

собой не избыточное покрытие G.

Действительно, согласно алгоритму EQUIV [pic] , так как DERIVES(F,G)

дает истину и DERIVES(G,F) так же истина. То же самое можно сказать

относительно F’ и G.

(Подробнее)

Множество F не избыточно, если в нем не существует F-зависимости X ->

Y, такой, что F - { X -> Y} |= X -> Y . Назовем F-зависимость из F

избыточной в F , если F - { X -> Y} |= X -> Y.

Для любого множества F-зависимостей G существует некоторое

подмножество F, такое, что F является не избыточным покрытием G. Если G

не избыточно, то F=G. Для определения не избыточного покрытия множества F-

зависимостей G существует алгоритм NONREDUN, который имеет вид:

Вход: множество F-зависимостей G.

Выход: не избыточное покрытие G.

NONREDUN(G)

begin

F=G

for каждая зависимость X -> Y из G do

if MEMBER(F-{X->Y],X->Y) then F=F-{X->Y}

end

return(F)

end

Пример: Пусть G= {A -> B, B -> A, B -> C, A -> C}.

Результатом работы алгоритма является множество:

{A -> B, B -> A, A -> C}.

Если бы G было представлено в порядке {A -> B, A -> C, B -> A , B ->

C} , то результатом работы алгоритма было бы

{A -> B, B -> A, B -> C}.

Из примера видно, что множество F-зависимостей G может иметь более

одного неизбыточного покрытия. Могут так же существовать неизбыточные

покрытия G, не содержащиеся в G. В приведенном примере таким неизбыточным

покрытием будет множество

F = {A -> B, B -> A, AB -> C}.

Если F-неизбыточное множество F-зависимостей, то в нем нет “лишних”

зависимостей в том смысле, что нельзя уменьшить F , удалив некоторые из

них. Удаление любой F-зависимости из F приведет к множеству, не

эквивалентному F. Однако размер можно уменьшить, удалив некоторые

атрибуты F-зависимостей F.

Определение. Пусть F-множество F-зависимостей над R и X -> Y есть F-

зависимость из F. Атрибут А из R называется посторонним в X -> Y

относительно F, если

1. [pic] и (F - {X -> Y}) [pic] {Z -> Y}[pic]F или

1. Y = AW, Y[pic]W и (F - {X -> Y}) [pic] {X -> W}[pic]F.

Иными словами, А - посторонний атрибут, если он может быть удален из

правой или левой части X -> Y без изменения замыкания F.

Пример. Пусть G = {A -> BC,B -> C,AB -> D}. Атрибут С является

посторонним в правой части A -> BC, а атрибут B - в левой части AB -> D.

Определение. Пусть F - множество F-зависимостей над R и X -> Y

принадлежит F. F-зависимость X -> Y называется редуцированной слева, если

Х не содержит постороннего атрибута А и редуцированной справа, если Y не

содержит атрибута А , постороннего для X -> y. Зависимость X -> Y

называется редуцированной, если она редуцирована слева и справа и Y

[pic]. Редуцированная слева F-зависимость называется также полной F-

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

Определение. Множество F-зависимостей F называется редуцированным

(слева, справа), если каждая F-зависимость из F редуцирована

(соответственно слева, справа).

Страницы: 1, 2