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

(X₁, X₂, ..., X_k) -> Y

где X₁, X₂, ..., X_k , множество эквивалентных левых частей F- зависимостей, а Y объединение правых частей F- зависимостей.

Синтез реляционных баз данных

База данных состоит из множества атрибутов и ключей. С точки зрения теоретико-множественного описания реляционной базой данных d называется такая совокупность отношений {R₁, R₂, ...,R_p}, в которой каждое отношение имеет вид R_i= (S_i,K_i), где S_i- множество атрибутов, а K_i - множество атрибутов образующих ключ.

Предположим на входе задано множество F- зависимостей F над R. С их помощью требуется создать базу данных R=( R₁, R₂, ...,R_p). Эта БД должна удовлетворять следующим требованиям:

1.

множество F полностью характеризуется с помощью R , т.е.

где К – выделенный ключ Ri}

2. Каждое отношение Ri находится в третьей нормальной форме.

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

4. Соединение всех полученных отношений Ri дает исходное отношение R.

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

Определение. Если R – база данных и на ней задано множество F-зависимостей G, то в ней существует по крайней мере |E_G| отношений. Это означает, что в R столько же отношений, сколько и классов эквивалентности. Из этого следует следующее.

Пусть F - множество F – зависимостей. Любая база данных должна иметь |E_F’| отношений, где F’ неизбыточное покрытие для F.

Исходя из этого строится способ построения структуры базы данных.

Сначала находится неизбыточное покрытиеF’ для F и в E_F’ вычисляем классы эквивалентности. Для каждого E_F’(X) строим отношение, состоящее из всех атрибутов, появляющихся в E_F’(X). При этом атрибуты левой части каждого класса эквивалентности образуют выделенный ключ.

Реализация этого способа позволяет получить алгоритм SYNTHESIZE

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

Выход: полная схема баз данных для F.

1. Наити для F редуцированное минимальное покрытие G.

2.

Для каждой CF – зависимости (X₁,X₂,…,X_k) Y из G построить отношение R_j= X₁X₂…X_kY с выделенными ключами K={X₁,X₂,…X_k).

3. Вернуться к п. 2.

Пример.

A B₁B₂C₁C₂DEI₁I₂I₃J

B₁B₂C₁ AC₂DEI₁I₂I₃J

B₁B₂C₂ AC₁DEI₁I₂I₃J

E I₁I₂I₃

C₁D J C₂D J

I₁I₂ I₃ I₂I₂ I₁ I₁I₃ I₂

И пусть R= AB₁B₂C₁C₂DEI₁I₂I₃J

Множество минимально, но не редуцировано. Редуцируя F , получим

F’= {A B₁B₂C₁C₂DE E I₁I₂

B₁B₂C₁ A B₁B₂C₂ A

C₁D J C₂D J

I₁I₂ I₃ I₂I₂ I₁ I₁I₃ I₂}

Образуя классы эквивалентности имеем

G={ (AB₁B₂C₁ ,B₁B₂C₂) DE

(E) I₁I₂

(C₁D) J (C₂D) J

(I₁I₂, I₂I₂, I₁I₃)}

Преобразуя каждую CF – в отношения с выделенными ключами, получим

R₁=AB₁B₂C₁C₂DE K₁= {AB₁B₂C₁ ,B₁B₂C₂}

R₂= EI₁I₂ K₂={E}

R₃= C₁DJ K₃={C₁D}

R₄= C₂DJ K₄={C₂D}

R₅= I₁I₂I₃ K₅={ I₁I₂, I₂I₂, I₁I₃}

Окончательная схема БД будет R=( R₁, R₂, R₃, R₄ ,R₅)

Распределенная обработка данных

Под распределенной обработкой данных понимается такой способ хранения и обработки данных, когда отдельное приложение может обрабатывать данные,, распределенные на множестве различных баз данных, управление которыми осуществляют различными СУБД, работающие на различных машинах с различными операционными системами, соединенных коммуникационными системами. Распределенная база данных (РБД) является виртуальным объектом, части которого расположены на удаленных базах данных, связанных каналами связи.

Физически РБД состоит из набора узлов, связанных коммуникационной сетью, в которой:

· Каждый узел обладает своими собственными системами баз данных;

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

Каждый узел обладает своими собственными базами данных, собственными локальными пользователями, собственной СУБД и программным обеспечением для управления транзакциями, а так же собственным диспетчером передачи данных. Распределенная СУБД может рассматриваться как некий способ совместной работы отдельных локальных СУБД, расположенных на разных локальных узлах. Причем новый компонент программного обеспечения на каждом узле поддерживает все необходимые функции совместной работы. Комбинация этого компонента и существующей СУБД называется Распределенной Системой Управления Базами Данных (РСУБД).

В основе распределённых баз данных лежат следующие требования:

1. Локальная автономия;

2. Независимость от центрального узла;

3. Непрерывное функционирование;

4. Независимость от расположения;

5. Независимость от фрагментации;

6. Независимость от репликации;

7. Обработка распределённых запросов;

8. Управление распределёнными транзакциями;

9. Независимость от аппаратного обеспечения;

10. Независимость от операционной системы;

11. Независимость от сети;

12. Независимость от СУБД.

Локальная автономия

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

Независимость от центрального узла.

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

Непрерывное функционирование

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

· Надежность (вероятность того, что система выполняет свойственные ей функции в заданный момент времени) повышается благодаря работе распределенных систем не по принципу «все или ничего», а в постоянном режиме; т.е. работа системы продолжается , хотя и на более низком уровне, даже в случае неисправности некоторого отдельного компонента, например узла.

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

Независимость от расположения

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