Реферат: Лекции по теории проектирования баз данных (БД)
<span Courier New";mso-bidi-font-family:«Times New Roman»">Лекция1<span Courier New";mso-bidi-font-family:«Times New Roman»">Технологияпроектирования баз данныхВопросы:
<span Times New Roman"">
Теоретические основы проектирования БД;
<span Times New Roman"">
<span Times New Roman",«serif»">Проектирование базыданных как элемент информационной технологииКак видно из материалов предыдущих лекций основубольшинства информационных технологий составляют большие массивы накопленнойинформации. Основной формой организации хранения данных в информационныхсистемах являются базы данных. В курсе “Автоматизированные системы обработкиучетной информации” мы рассмотрели основные понятия, связанные с моделямиданных, теоретические основы разработки простейших баз данных и жизненный циклбаз данных. Теперь, рассматривая БД как часть информационной технологии,необходимо по новому взглянуть на проблему проектирования базы.
Проблемы проектирования связаны с функциями БД впрограммно — технологической среде, поддерживающей информационные технологии. Вобщем случае место БД можно отразить следующей схемой:
<img src="/cache/referats/13059/image001.gif" v:shapes="_x0000_s1053 _x0000_s1057">
База
данных
<img src="/cache/referats/13059/image002.gif" v:shapes="_x0000_s1055">Операционная система
<img src="/cache/referats/13059/image003.gif" v:shapes="_x0000_s1051"><img src="/cache/referats/13059/image004.gif" v:shapes="_x0000_s1049">Аппаратная
среда
<img src="/cache/referats/13059/image005.gif" v:shapes="_x0000_s1047"><img src="/cache/referats/13059/image006.gif" v:shapes="_x0000_s1040"><img src="/cache/referats/13059/image007.gif" v:shapes="_x0000_s1042"><img src="/cache/referats/13059/image008.gif" v:shapes="_x0000_s1027"><img src="/cache/referats/13059/image009.gif" v:shapes="_x0000_s1046"><img src="/cache/referats/13059/image010.gif" v:shapes="_x0000_s1044"><img src="/cache/referats/13059/image011.gif" v:shapes="_x0000_s1038"><img src="/cache/referats/13059/image012.gif" v:shapes="_x0000_s1032"><img src="/cache/referats/13059/image013.gif" v:shapes="_x0000_s1035"><img src="/cache/referats/13059/image014.gif" v:shapes="_x0000_s1026"><img src="/cache/referats/13059/image008.gif" v:shapes="_x0000_s1028">информационных
технологий
<img src="/cache/referats/13059/image015.gif" v:shapes="_x0000_s1059">
Прочие
приложения
Поскольку база данных является связующим звеноммежду пользовательскими приложениями и аппаратными средствами, еепроектирование можно разделить на два направления: проектирование структуры ипользовательских приложений и распределение данных по аппаратным средствам (вслучае баз данных на сетях). В данном разделе мы рассмотрим вопросыпроектирования структуры базы данных. В дисциплине АСОЭИ, рассматривая основыреляционной алгебры и разработки реляционных моделей, мы коснулись вопросовпроектирования реляционных баз данных. Одной из распространенных технологийразработки БД является следующая:
<span Times New Roman"">
<span Times New Roman"">
<span Times New Roman"">
<span Times New Roman"">
<span Times New Roman"">
<span Times New Roman"">
В результате получается модель реляционной базыданных, которая представляет собой совокупность взаимосвязанных отношений.
Построение сетевой модели связано скорее спотребностью разработчика графически представить взаимосвязь данных, полученныхв результате интеграции представлений пользователей. Преобразование сетевоймодели в реляционную дает первую нормальную форму последней. Напомним, чтоотношение R находится в первой нормальной форме, если значения в dom(A) являютсяатомарными для каждого атрибута А в R. Вторая и третья нормальные формыпозволяют избежать аномалий при обновлении данных и избавится от информационнойизбыточности в отношениях. Напомним, что отношение R нормальной форме, если ононаходится в первой нормальной форме и каждый атрибут не являющийся ключом полностьюзависит от любого ключа в R. И отношение R находится в третьей нормальнойформе, если оно находится во 2НФ и каждый атрибут, не являющийся первичнымключом не транзитивно зависит от любого возможного ключа.
Недостатком такого подхода является то, что вмоделях, имеющих десятки и сотни атрибутов очень трудно имперически построитьмодель, все отношения которой заданы в третьей нормальной форме и связаны междусобой таким образом, что составляют единое целое.
Пример.
А В С
D F G H
G V M N
B M T X
<img src="/cache/referats/13059/image016.gif" v:shapes="_x0000_s1029 _x0000_s1033 _x0000_s1036 _x0000_s1039 _x0000_s1041 _x0000_s1043 _x0000_s1045 _x0000_s1048 _x0000_s1050 _x0000_s1052 _x0000_s1054 _x0000_s1056 _x0000_s1058 _x0000_s1060 _x0000_s1061 _x0000_s1062 _x0000_s1063 _x0000_s1064 _x0000_s1065 _x0000_s1066 _x0000_s1067 _x0000_s1068">Другим подходом является возможность формальногосинтеза модели на основании априорно установленных зависимостей междуатрибутами. Зависимости между атрибутами устанавливаются на основании смысловойсвязи.
Пример.
НОМЕР_ЗАЧЕТКИ — ИМЯ_СТУДЕНТА
НОМЕР_РЕЙСА — ДАТА_ВЫЛЕТА
Безусловно такой подход к разработке модели базыданных предпочтительнее, так как позволяет автоматизировать процессмоделирования. Для реализации этого подхода необходимо расширение теоретическойбазы, полученной в курсе АСОЭИ.
<span Courier New";mso-bidi-font-family:«Times New Roman»">Теоретическиеосновы проектирования БД.Основные понятия.
Поскольку рассматриваемый подход к разработкереляционной модели базируется на формальной логике, то в его основе должнылежать некоторые фундаментальные формализации. В теории реляционных баз данныхк ним относятся понятия атрибута, отношения, ключа и функциональной зависимости.
Атрибутом будем называть поименованное свойствообъекта и обозначать Аi, где <img src="/cache/referats/13059/image018.gif" v:shapes="_x0000_i1025">i обозначим dom(Аi).Тогда отношением R называется конечное множество атрибутов <img src="/cache/referats/13059/image020.gif" v:shapes="_x0000_i1026"><img src="/cache/referats/13059/image022.gif" v:shapes="_x0000_i1027"> со следующим свойством.Для любых двух различных кортежей t1 и t2 в R существуеттакое <img src="/cache/referats/13059/image024.gif" v:shapes="_x0000_i1028">1(B)<img src="/cache/referats/13059/image026.gif" v:shapes="_x0000_i1029">2(B). Другими словами, не существует двухкортежей, имеющих одно и то же значение на всех атрибутах из К. Таким образом,достаточно знать К — значение кортежа, чтобы идентифицировать кортеж однозначно.
Пример.
СТУДЕНТ[НОМЕР_ЗАЧЕТКИ, ИМЯ, КУРС, ГРУППА]
Ключи, явно указанные в модели называютсявыделенными. Могут быть ключи отличные от выделенных и называемые неявнымиключами. Например ИМЯ в предыдущем прмере.
Под функциональной зависимостью атрибутов илиF-зависимостью понимают такую связь между атрибутами, когда значения кортежа наодном множестве атрибутов единственным образом определяют эти значения надругом множестве атрибутов. Так в отношении:
ГРАФИК[ПИЛОТ, РЕЙС, ДАТА, ВРЕМЯ]
ПИЛОТ функционально зависит от {РЕЙС, ДАТА}F-зависимости принято обозначать {РЕЙС, ДАТА}->ПИЛОТ и говорят, что РЕЙС и ДАТА функционально определяют ПИЛОТ.
В терминах теории множеств и реляционной алгебрыF-зависимость определяется так. Пусть R отношение и X, Y подмножества атрибутовв R. Отношение R удовлетворяет функциональной зависимости X -> Y, если <span Times New Roman";mso-hansi-font-family: «Times New Roman»;mso-char-type:symbol;mso-symbol-font-family:Symbol">p
Y(<span Times New Roman";mso-hansi-font-family: «Times New Roman»;mso-char-type:symbol;mso-symbol-font-family:Symbol">sX-x®)имеет не более чем один кортеж для каждого Х — значения х. В F-зависимостиX->Y подмножество X называется левой частью, а Y — правой частью. <span Courier New";mso-bidi-font-family:«Times New Roman»">Лекция2Такая интерпретация функциональной зависимостиявляется основой алгоритма SATISFIES, приводимого ниже.
SATISFIESВход: Отншение R и F-зависимость X->Y.
Выход: истина, если R удовлетворяет X->Y, ложь — в противном случае.
SATISFIES(R,X->Y)<span Times New Roman"">
<span Times New Roman"">
Этот алгоритм проверяет, удовлетворяет ли отношение RF-зависимости 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
<img src="/cache/referats/13059/image027.gif" v:shapes="_x0000_s1030"><img src="/cache/referats/13059/image029.gif" v:shapes="_x0000_i1030">
Рефлексивность: 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}
<img src="/cache/referats/13059/image030.gif" v:shapes="_x0000_s1031"> X -> Y <img src="/cache/referats/13059/image032.gif" v:shapes="_x0000_i1031"> F+ .
<span Courier New";mso-bidi-font-family:«Times New Roman»">Лекция3<img src="/cache/referats/13059/image033.gif" v:shapes="_x0000_s1037">+ не обязательно для установления F = X -> Y.
Для этого достаточно воспользоваться алгоритмомMEMBER .
Алгоритм MEMBER.
Вход: Множество F-зависимостей F и F-зависимость X-> Y.
<img src="/cache/referats/13059/image034.gif" v:shapes="_x0000_s1034">
MEMBER(F, X -> Y)begin
if Y <img src="/cache/referats/13059/image032.gif" v:shapes="_x0000_i1032"> CLOSURE(X,F) then return (истина)
else return(ложь)
end
Здесь CLOSURE алгоритм, позволяющий выявить списокатрибутов входящих в множество F, который имеет вид.
Алгоритм CLOSURE.
Вход: Множество атрибутов Х и множествоF-зависимостей F.
Выход: Замыкание Х над F.
CLOSURE(X,F)begin
OLDDEP = 0; NEWDEP = XwhileNEWDEP <img src="/cache/referats/13059/image026.gif" v:shapes="_x0000_i1033"> OLDDEP do begin
OLDDEP = NEWDEPfor каждаяF- зависимостьW -> Z вF do
if NEWDEP <img src="/cache/referats/13059/image036.gif" v:shapes="_x0000_i1034"> W then
NEWDEP =NEWDEP <img src="/cache/referats/13059/image038.gif" v:shapes="_x0000_i1035"> Z
end
return(NEWDEP)
end
ПримерработыалгоритмаMEMBERПусть F = {НОМЕР_РЕЙСА ДАТА_ВЫЛЕТА ->КОЛИЧЕСТВО_МЕСТ,
НОМЕР_РЕЙСА -> ПУНКТ_ОТПРАВЛЕНИЯ, НОМЕР_РЕЙСАДАТА_ВЫЛЕТА -> ПИЛОТ} и необходимо установить F |= НОМЕР_РЕЙСА -> ПИЛОТ
Используем для этого алгоритм MEMBER
<span Courier New";mso-bidi-font-family:«Times New Roman»">Покрытияфункциональных зависимостейДля формирования БД, как системы взаимосвязанныхотношений на основании известных (из семантических соображений) F-зависимостейнеобходимо иметь способ минимизации первоначального множества F-зависимостей.Это необходимо для минимизации дублирования данных, обеспечения ихсогласованности и целостности. Теоретической основой для построения такогоспособа является теория покрытий функциональных зависимостей.
Определение.
Два множества F-зависимостей F и G над отношением Rэквивалентны, <img src="/cache/referats/13059/image040.gif" v:shapes="_x0000_i1036"> , если F+ =G+ . Если <img src="/cache/referats/13059/image040.gif" v:shapes="_x0000_i1037">покрытиедля G. Предполагается, что имеет смысл рассматривать в качестве покрытий такиемножества F, которые не превосходят множество G по числу F-зависимостей.
Из этого определения следует, что для установленияфакта, что множество функциональных зависимостей F является покрытием G,необходимо определить эквивалентность F и G. Практически это достигается путемиспользования следующего алгоритма:
Алгоритм EQUIV
Вход: два множества F- зависимостей F и G.
Выход: истина, если <img src="/cache/referats/13059/image040.gif" v:shapes="_x0000_i1038">
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’<img src="/cache/referats/13059/image043.gif" v:shapes="_x0000_i1039">
Пример. Пусть 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 <img src="/cache/referats/13059/image040.gif" v:shapes="_x0000_i1040"> , так как 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 из Gdo
if MEMBER(F-{X->Y],X->Y) thenF=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, если
<span Times New Roman"">
<img src="/cache/referats/13059/image045.gif" v:shapes="_x0000_i1041"> и (F — {X -> Y}) <img src="/cache/referats/13059/image038.gif" v:shapes="_x0000_i1042"> {Z -> Y}<img src="/cache/referats/13059/image043.gif" v:shapes="_x0000_i1043"><span Times New Roman"">
Y = AW, Y<img src="/cache/referats/13059/image026.gif" v:shapes="_x0000_i1044"><img src="/cache/referats/13059/image038.gif" v:shapes="_x0000_i1045"> {X -> W}<img src="/cache/referats/13059/image043.gif" v:shapes="_x0000_i1046">Иными словами, А — посторонний атрибут, если онможет быть удален из правой или левой части 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 <img src="/cache/referats/13059/image047.gif" v:shapes="_x0000_i1047">
Определение. Множество F-зависимостей F называетсяредуцированным (слева, справа), если каждая F-зависимость из F редуцирована(соответственно слева, справа).
Пример. Множество G = {A -> BC, B -> C, AB-> D} не является редуцированным ни справа, ни слева. Множество G1= {A -> BC, B -> C, A -> D} редуцировано слева, но не справа, а G2= {A -> B, B -> C, AB -> D} редуцировано справа, но не слева.Множество G3 = {A -> B, B -> C, A -> D} редуцировано слеваи справа, следовательно, поскольку правые части не пусты, редуцировано.
Для нахождения редуцированных покрытий используетсяалгоритм:
REDUCEВход: множество F-зависимостей G.
Выход: редуцированное покрытие G.
REDUCE(G)begin
F = RIGHTRED(LEFTRED(G))
удалить из F всеF-зависимости вида X -> <img src="/cache/referats/13059/image049.gif" v:shapes="_x0000_i1048">
return(F)
end
здесь RIGHTRED и LEFTRED алгоритмы редуцированиясоответственно справа и слева, которые имеют вид:
RIGHTREDВход: множество F-зависимостей G.
Выход: редуцированное справа покрытие G.
RIGHTRED(G)begin
F = G
for каждая зависимость X -> Y из Gdo
for каждый атрибут А из Ydo
if MEMBER(F — {X -> Y} <img src="/cache/referats/13059/image038.gif" v:shapes="_x0000_i1049"> {X ->(Y — A)}, X -> A) then
удалить А из Y в X -> Y из F<img src="/cache/referats/13059/image029.gif" v:shapes="_x0000_i1050">
end
end
return(F)
end
Алгоритм LEFTRED
Вход: множество F-зависимостей G.
Выход: редуцированное слева покрытие G.
Begin
F = G
for каждая зависимостьX -> Y из G do
for каждый атрибут Аиз Х do
if MEMBER(F,{X — A) -> Y) then
удалить А из X в X -> Y из F<img src="/cache/referats/13059/image029.gif" v:shapes="_x0000_i1051">
end
end
return(F)
end
Пример. ПустьG’= {A-> C, AB -> DE, AB ->CDI, AC -> J}.ИзLEFTRED(G’) получаемG” = {A -> C, AB -> DE, AB -> CDI, A-> J} иизRIGHTRED(G”) получаемF= {A -> C, AB -> E, AB ->DI, A -> J}, ужередуцированное.
Далее потребуется находить разбиение множества F-зависимостей, заданных на отношении R на подмножества, которые представляютсобой классы F- зависимостей с эквивалентной левой частью.
Определение: два множества атрибутов X и Yназываются эквивалентными на множестве F- зависимостей F, если F |= X->Y и F|= Y ->X.
Например пусть дано F={A -> BC, B -> A, AD-> E}, найдем все F- зависимостиэквивалентные левой части первой, т.е. А. Левая часть второй F- зависимости (В)эквивалентна А? Проверим F |= A -> B и F |= B -> A. Это действительнотак. Следовательно А эквивалентно В и первые две F- зависимости можно объединитьв один класс эквивалентности, который обозначается в общем случае ЕА(Х).Множество классов эквивалентности для заданного множества F- зависимостейобозначается <img src="/cache/referats/13059/image051.gif" v:shapes="_x0000_i1052">F . Сокращенным способом записи F- зависимостей сэквивалентными левыми частями является составная функциональная зависимость(CF-зависимость), которая имеет вид:
<span Times New Roman",«serif»;mso-ansi-language: EN-US">(X1, X2, ..., Xk) -> Yгде X1, X2, ..., Xk ,множество эквивалентных левых частей F- зависимостей, а Y объединение правыхчастей F- зависимостей.
<span Times New Roman",«serif»">Синтез реляционных базданныхБаза данных состоит из множества атрибутов и ключей.С точки зрения теоретико-множественного описания реляционной базой данных dназывается такая совокупность отношений {R1, R2, ...,Rp},в которой каждое отношение имеет вид Ri= (Si,Ki), где Si — множество атрибутов, а Ki — множество атрибутов образующих ключ.
Предположим на входе задано множество F-зависимостей F над R. С их помощью требуется создать базу данных R=( R1,R2, ...,Rp). Эта БД должна удовлетворять следующим требованиям:
1.<span Times New Roman"">
<img src="/cache/referats/13059/image053.gif" v:shapes="_x0000_s1071">множество F полностьюхарактеризуется с помощью R, т.е.
где К – выделенный ключ Ri}
2.<span Times New Roman"">
Ri находится в третьей нормальной форме.3.<span Times New Roman"">
4.<span Times New Roman"">
Ri дает исходное отношение R.Алгоритмпорождающий базу данных из заданных F-зависимостей называется алгоритмом синтеза.
Определение.Если R – база данных ина ней задано множество F-зависимостейG, то в ней существуетпо крайней мере |EG|отношений. Это означает, что в Rстолько же отношений, сколько и классов эквивалентности. Из этого следуетследующее.
Пусть F — множество F –зависимостей. Любая база данных должна иметь |EF’| отношений,где F’ неизбыточноепокрытие для F.
Исходя изэтого строится способ построения структуры базы данных.
Сначаланаходится неизбыточное покрытиеF’для F и в EF’вычисляем классы эквивалентности. Для каждого EF’(X) строим отношение,состоящее из всех атрибутов, появляющихся в EF’(X). При этом атрибуты левой части каждого класса эквивалентностиобразуют выделенный ключ.
Реализация этого способапозволяет получить алгоритм SYNTHESIZE
Вход: множество F – зависимостей F над R.
Выход: полная схема базданных для F.
1.<span Times New Roman"">
F редуцированное минимальное покрытие G.2.<span Times New Roman"">
<img src="/cache/referats/13059/image054.gif" v:shapes="_x0000_s1072">CF – зависимости (X1,X2,…,Xk) Y из Gпостроить отношение Rj=X1X2…XkY с выделеннымиключами K={X1,X2,…Xk).3.<span Times New Roman"">
Пример.
<img src="/cache/referats/13059/image055.gif" v:shapes="_x0000_s1073">A B1B2C1C2DEI1I2I3J
<img src="/cache/referats/13059/image056.gif" v:shapes="_x0000_s1074">B1B2C1 AC2DEI1I2I3J
<img src="/cache/referats/13059/image057.gif" v:shapes="_x0000_s1075">B1B2C2 AC1DEI1I2I3J
E I1I2I3
<img src="/cache/referats/13059/image058.gif" v:shapes="_x0000_s1083"><img src="/cache/referats/13059/image058.gif" v:shapes="_x0000_s1081"><img src="/cache/referats/13059/image059.gif" v:shapes="_x0000_s1077"><img src="/cache/referats/13059/image059.gif" v:shapes="_x0000_s1076">C1D J C2D J
<img src="/cache/referats/13059/image060.gif" v:shapes="_x0000_s1080"><img src="/cache/referats/13059/image061.gif" v:shapes="_x0000_s1079"><img src="/cache/referats/13059/image061.gif" v:shapes="_x0000_s1078">I1I2 I3 I2I2 I1 I1I3 I2
ИпустьR= AB1B2C1C2DEI1I2I3J
Множествоминимально, но не редуцировано. РедуцируяF, получим
<img src="/cache/referats/13059/image061.gif" v:shapes="_x0000_s1082">F’= {A B1B2C1C2DE E I1I2
<img src="/cache/referats/13059/image062.gif" v:shapes="_x0000_s1085">B1B2C1 A B1B2C2 A
<img src="/cache/referats/13059/image063.gif" v:shapes="_x0000_s1089"><img src="/cache/referats/13059/image061.gif" v:shapes="_x0000_s1088"><img src="/cache/referats/13059/image057.gif" v:shapes="_x0000_s1086"><img src="/cache/referats/13059/image057.gif" v:shapes="_x0000_s1084">C1D J C2D J
<img src="/cache/referats/13059/image064.gif" v:shapes="_x0000_s1087">I1I2 I3 I2I2 I1 I1I3 I2}
Образуяклассы эквивалентности имеем
<img src="/cache/referats/13059/image062.gif" v:shapes="_x0000_s1090">G={ (AB1B2C1,B1B2C2) DE
<img src="/cache/referats/13059/image065.gif" v:shapes="_x0000_s1091">(E) I1I2
<img src="/cache/referats/13059/image065.gif" v:shapes="_x0000_s1093"><img src="/cache/referats/13059/image055.gif" v:shapes="_x0000_s1092">(C1D) J (C2D) J
(I1I2, I2I2,I1I3)}
Преобразуякаждую CF – в отношенияс выделенными ключами, получим
R1=AB1B2C1C2DE K1= {AB1B2C1,B1B2C2}
R2= EI1I2 K2={E}
R3= C1DJ K3={C1D}
R4= C2DJ K4={C2D}
R5= I1I2I3 K5={ I1I2,I2I2, I1I3}
Окончательнаясхема БД будет R=( R1, R2, R3, R4,R5)
Распределенная обработка данныхПод распределеннойобработкой данных понимается такой способ хранения и обработки данных, когда отдельное приложениеможет обрабатывать данные,, распределенные на множестве различных баз данных,управление которыми осуществляют различными СУБД, работающие на различныхмашинах с различными операционными системами, соединенных коммуникационнымисистемами. Распределенная база данных (РБД) является виртуальным объектом,части которого расположены на удаленных базах данных, связанных каналами связи.
Физически РБД состоит изнабора узлов, связанныхкоммуникационной сетью, в которой:
·<span Times New Roman"">
·<span Times New Roman"">
Каждыйузел обладает своими собственными базами данных, собственными локальными пользователями,собственной СУБД и программным обеспечением для управления транзакциями, а также собственным диспетчером передачи данных. Распределенная СУБД можетрассматриваться как некий способ совместной работы отдельных локальных СУБД,расположенных на разных локальных узлах. Причем новый компонент программногообеспечения на каждом узле поддерживает все необходимые функции совместнойработы. Комбинация этого компонента и существующей СУБД называетсяРаспределенной Системой Управления Базами Данных (РСУБД).
В основе распределённых базданных лежат следующие требования:
1.<span Times New Roman"">
2.<span Times New Roman"">
3.<span Times New Roman"">
4.<span Times New Roman"">
5.<span Times New Roman"">
6.<span Times New Roman"">
7.<span Times New Roman"">
8.<span Times New Roman"">
9.<span Times New Roman"">
10.<span Times New Roman"">
11.<span Times New Roman"">
12.<span Times New Roman"">
Локальная автономияВ распределенной системе узлы следует делать автономными. Локальная автономия означает, чтофункционирование любого узла Х не зависит от успешного выполнения операций нанекотором узле У . В противном случаевыход из строя узла У может привести к невозможности выполнения операций наузле Х. Из принципа локальной автономии следует, что владение и управлениеданными осуществляется локально вместе с локальным ведением учета. Вдействительности цель локальной автономии достигается не полностью, посколькучасто узел Х должен представлять некоторую часть управления узлу У , поэтому говорят не о полной, а омаксимально возможной автономии.
Независимость от центрального узла.Под локальной автономией понимается, что все узлы должнырассматриваться как равные. Следовательно, не должно существовать никакойзависимости и от центрального «основного» узла с некоторым централизованнымобслуживанием, например централизованной обработкой запросов, централизованнымуправлением транзакциями или централизованным присвоением имен. Зависимость отцентрального узла нежелательна по двум причинам. Во-первых, центральный узелможет быть «узким» местом всей системы, а во-вторых, более важно то, чтосистема в целом становится уязвимой, т.е. при повреждении центрального узламожет выйти из строя вся система.
Непрерывное функционированиеОдним из преимуществ распределенных систем является то, чтоони обеспечивают более высокую надежность и доступность.
·<span Times New Roman"">
Надежность(вероятность того, что система выполняет свойственные ей функции в заданный момент времени) повышается благодаря работераспределенных систем не по принципу «все или ничего», а в постоянном режиме;т.е. работа системы продолжается, хотя и на более низком уровне, даже в случаенеисправности некоторого отдельногокомпонента, например узла.·<span Times New Roman"">
(вероятность того, что система исправна и работает в течение некоторогопромежутка времени) повышается частично по той же причине, а частично благодарявозможности репликации данных.Независимость от расположенияЭта цель предполагает обеспечение такого режима работы сданными, при котором пользователю не нужно знать, на каком узле находятсятребуемые данные. При этом значительно упрощаются пользовательские программы, атакже не требуется их изменения при перемещении данных в системе.
Независимость от фрагментацииВ системе поддерживается фрагментация данных, если некотороеотношение из соображений физического хранения необходимо разделить на части илифрагменты. Фрагментация желательна для повышения производительности системы,поскольку данные лучше хранить в том месте, где они наиболее частоиспользуются. При такой организации многие операции становятся локальными, аобъем передаваемых в сети данных снизится.
Существует два типа фрагментации – горизонтальная ивертикальная, которые связаны с операциями селекции и проекции соответственно,т.е. горизонтальный фрагмент может быть получен с помощью операции селекции, авертикальный – проекцией. Реконструкцию исходного отношения на основе егофрагментов можно осуществить с помощью операций соединения (для вертикальныхфрагментов) и объединения (для горизонтальных фрагментов).
В фрагментированной системе необходимо обеспечить поддержкунезависимости от фрагментации, т.е. пользователь не должен «ощущать»фрагментацию данных.
Независимость от репликацииВ системе поддерживается независимость от репликации, еслизаданное отношение или фрагмент могут быть представлены различными копиями(репликами) хранимыми на разных узлах. Репликация полезна по двум причинам.Во-первых, благодаря ей достигается большая производительность, т.к. приложениямогут работать с локальными копиями, не обмениваясь данными с удаленнымиузлами. Во-вторых, репликация позволяет обеспечить большую доступность, т.к.реплицированный объект остается доступным для обработки до тех пор, покаостается хотя бы одна его реплика. Главный недостаток репликации заключается втом, что при обновлении реплицируемого объекта, все его копии должны синхронизироваться.
В системе, которая поддерживает репликацию данных, должнатакже поддерживаться независимость от репликации, т.е. пользователь не долженкасаться проблем связанных с созданием и синхронизацией копий.
Обработка распределенных запросовПри обработке в распределенной системе запроса необходимовыработать эффективную стратегию его реализации. Например, запрос наобъединение отношений Rx, расположенного на узле X, и отношения Ry, хранимого на узле Y, может быть выполнен спомощью перемещения отношения Rxна узел Y, перемещенияотношения Ry на узел X или перемещения этих двухотношений на третий узел Zи т.д. Это означает, что при выполнении запроса на распределенной БД необходимего предварительный анализ с последующим выбором оптимальной стратегии его реализации.
Управление распределенными транзакциямиВ распределенной системе выполнение транзакции связано сисполнением программных кодов на нескольких узлах. Транзакция это логическаяединица работы, которая включает всю совокупность действий, необходимых дляреализации запроса. Транзакция считается неделимым процессом, т.е. если какоелибо из составляющих действий о