Лекции по теории проектирования баз данных (БД)Теперь, рассматривая БД как часть информационной технологии, необходимо по новому взглянуть на проблему проектирования базы. Проблемы проектирования связаны с функциями БД в программно - технологической среде, поддерживающей информационные технологии. В общем случае место БД можно отразить следующей схемой:
Построение сетевой модели связано скорее с потребностью разработчика графически представить взаимосвязь данных, полученных в результате интеграции представлений пользователей. Преобразование сетевой модели в реляционную дает первую нормальную форму последней. Напомним, что отношение R находится в первой нормальной форме, если значения в dom(A) являются атомарными для каждого атрибута А в R . Вторая и третья нормальные формы позволяют избежать аномалий при обновлении данных и избавится от информационной избыточности в отношениях. Напомним, что отношение R нормальной форме, если оно находится в первой нормальной форме и каждый атрибут не являющийся ключом полностью зависит от любого ключа в R. И отношение R находится в третьей нормальной форме, если оно находится во 2НФ и каждый атрибут, не являющийся первичным ключом не транзитивно зависит от любого возможного ключа. Недостатком такого подхода является то, что в моделях, имеющих десятки и сотни атрибутов очень трудно имперически построить модель, все отношения которой заданы в третьей нормальной форме и связаны между собой таким образом, что составляют единое целое. Пример.
Зависимости между атрибутами устанавливаются на основании смысловой связи. Пример. НОМЕР_ЗАЧЕТКИ - ИМЯ_СТУДЕНТА НОМЕР_РЕЙСА - ДАТА_ВЫЛЕТА Безусловно такой подход к разработке модели базы данных предпочтительнее, так как позволяет автоматизировать процесс моделирования. Для реализации этого подхода необходимо расширение теоретической базы, полученной в курсе АСОЭИ. Теоретические основы проектирования БД. Основные понятия. Поскольку рассматриваемый подход к разработке реляционной модели базируется на формальной логике, то в его основе должны лежать некоторые фундаментальные формализации. В теории реляционных баз данных к ним относятся понятия атрибута, отношения, ключа и функциональной зависимости. Атрибутом будем называть поименованное свойство объекта и обозначать А i , где Пример. СТУДЕНТ[НОМЕР_ЗАЧЕТКИ,ИМЯ,КУРС,ГРУППА] Ключи, явно указанные в модели называются выделенными. Могут быть ключи отличные от выделенных и называемые неявными ключами. Например ИМЯ в предыдущем прмере. Под функциональной зависимостью атрибутов или F-зависимостью понимают такую связь между атрибутами, когда значения кортежа на одном множестве атрибутов единственным образом определяют эти значения на другом множестве атрибутов. Так в отношении: ГРАФИК[ПИЛОТ,РЕЙС,ДАТА,ВРЕМЯ] ПИЛОТ функционально зависит от {РЕЙС,ДАТА} F-зависимости принято обозначать {РЕЙС,ДАТА}-> ПИЛОТ и говорят, что РЕЙС и ДАТА функционально определяют ПИЛОТ. В терминах теории множеств и реляционной алгебры F-зависимость определяется так. Пусть R отношение и X, Y подмножества атрибутов в R. Отношение R удовлетворяет функциональной зависимости X -> Y, если p Y ( s X-x ®) имеет не более чем один кортеж для каждого Х - значения х. В F-зависимости X->Y подмножество X называется левой частью, а Y - правой частью. Лекция 2 Такая интерпретация функциональной зависимости является основой алгоритма SATISFIES, приводимого ниже. SATISFIES Вход: Отншение R и F-зависимость X->Y. Выход: истина, если R удовлетворяет X->Y, ложь - в противном случае. SATISFIES(R,X->Y) Этот алгоритм проверяет, удовлетворяет ли отношение R F-зависимости X -> Y. Пример. В результате выполнения алгоритма SATISFIES выясним удовлетворяет ли F-зависимость РЕЙС -> ВРЕМЯ_ВЫЛЕТА следующему отношению ГРАФИК
Иногда их называют аксиомами Армстронга. Пусть 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} Алгоритм CLOSURE. Вход: Множество атрибутов Х и множество F-зависимостей F. Выход: Замыкание Х над F. CLOSURE(X,F) begin OLDDEP = 0; NEWDEP = X while NEWDEP Теоретической основой для построения такого способа является теория покрытий функциональных зависимостей. Определение. Два множества F-зависимостей F и G над отношением R эквивалентны, Удаление любой F-зависимости из F приведет к множеству, не эквивалентному F. Однако размер можно уменьшить, удалив некоторые атрибуты F-зависимостей F. Определение. Пусть F-множество F-зависимостей над R и X -> Y есть F-зависимость из F. Атрибут А из R называется посторонним в X -> Y относительно F, если Множество F-зависимостей F называется редуцированным (слева, справа), если каждая F-зависимость из F редуцирована (соответственно слева, справа). Пример. Множество G = {A -> BC, B -> C, AB -> D}не является редуцированным ни справа, ни слева. Множество G 1 = {A -> BC, B -> C, A -> D}редуцировано слева, но не справа, а G 2 = {A -> B, B -> C, AB -> D}редуцировано справа, но не слева. Множество G 3 = {A -> B, B -> C, A -> D}редуцировано слева и справа, следовательно, поскольку правые части не пусты, редуцировано. Для нахождения редуцированных покрытий используется алгоритм: REDUCE Вход: множество F-зависимостей G. Выход: редуцированное покрытие G. REDUCE(G) begin F = RIGHTRED(LEFTRED(G)) удалить из F все F-зависимости вида X -> Определение: два множества атрибутов 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зависимостей обозначается Синтез реляционных баз данных База данных состоит из множества атрибутов и ключей. С точки зрения теоретико-множественного описания реляционной базой данных d называется такая совокупность отношений {R 1 , R 2 , ...,R p }, в которой каждое отношение имеет вид R i = (S i ,K i ), где S i - множество атрибутов, а K i - множество атрибутов образующих ключ. Предположим на входе задано множество Fзависимостей F над R. С их помощью требуется создать базу данных R=( R 1 , R 2 , ...,R p ). Эта БД должна удовлетворять следующим требованиям: 1. Определение. Если 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. Редуцируя F , получим Распределенная база данных (РБД) является виртуальным объектом, части которого расположены на удаленных базах данных, связанных каналами связи. Физически РБД состоит из набора узлов, связанных коммуникационной сетью, в которой: · · Каждый узел обладает своими собственными базами данных, собственными локальными пользователями, собственной СУБД и программным обеспечением для управления транзакциями, а так же собственным диспетчером передачи данных. Распределенная СУБД может рассматриваться как некий способ совместной работы отдельных локальных СУБД, расположенных на разных локальных узлах. Причем новый компонент программного обеспечения на каждом узле поддерживает все необходимые функции совместной работы. Комбинация этого компонента и существующей СУБД называется Распределенной Системой Управления Базами Данных (РСУБД). В основе распределённых баз данных лежат следующие требования: 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. Локальная автономия В распределенной системе узлы следует делать автономными. Локальная автономия означает, что функционирование любого узла Х не зависит от успешного выполнения операций на некотором узле У . В противном случае выход из строя узла У может привести к невозможности выполнения операций на узле Х . Из принципа локальной автономии следует, что владение и управление данными осуществляется локально вместе с локальным ведением учета. В действительности цель локальной автономии достигается не полностью, поскольку часто узел Х должен представлять некоторую часть управления узлу У , поэтому говорят не о полной, а о максимально возможной автономии. Независимость от центрального узла. Под локальной автономией понимается, что все узлы должны рассматриваться как равные. Следовательно, не должно существовать никакой зависимости и от центрального «основного» узла с некоторым централизованным обслуживанием, например централизованной обработкой запросов, централизованным управлением транзакциями или централизованным присвоением имен. Зависимость от центрального узла нежелательна по двум причинам. Во-первых, центральный узел может быть «узким» местом всей системы, а во-вторых, более важно то, что система в целом становится уязвимой, т.е. при повреждении центрального узла может выйти из строя вся система. Непрерывное функционирование Одним из преимуществ распределенных систем является то, что они обеспечивают более высокую надежность и доступность. · Надежность (вероятность того, что система выполняет свойственные ей функции в заданный момент времени) повышается благодаря работе распределенных систем не по принципу «все или ничего», а в постоянном режиме; т.е. работа системы продолжается , хотя и на более низком уровне, даже в случае неисправности некоторого отдельного компонента, например узла. · (вероятность того, что система исправна и работает в течение некоторого промежутка времени) повышается частично по той же причине, а частично благодаря возможности репликации данных. Независимость от расположения Эта цель предполагает обеспечение такого режима работы с данными, при котором пользователю не нужно знать, на каком узле находятся требуемые данные. При этом значительно упрощаются пользовательские программы, а также не требуется их изменения при перемещении данных в системе. Независимость от фрагментации В системе поддерживается фрагментация данных, если некоторое отношение из соображений физического хранения необходимо разделить на части или фрагменты. Фрагментация желательна для повышения производительности системы, поскольку данные лучше хранить в том месте, где они наиболее часто используются. При такой организации многие операции становятся локальными, а объем передаваемых в сети данных снизится. Существует два типа фрагментации – горизонтальная и вертикальная, которые связаны с операциями селекции и проекции соответственно, т.е. горизонтальный фрагмент может быть получен с помощью операции селекции, а вертикальный – проекцией. Реконструкцию исходного отношения на основе его фрагментов можно осуществить с помощью операций соединения (для вертикальных фрагментов) и объединения (для горизонтальных фрагментов). В фрагментированной системе необходимо обеспечить поддержку независимости от фрагментации, т.е. пользователь не должен «ощущать» фрагментацию данных. Независимость от репликации В системе поддерживается независимость от репликации, если заданное отношение или фрагмент могут быть представлены различными копиями (репликами) хранимыми на разных узлах. Репликация полезна по двум причинам. Во-первых, благодаря ей достигается большая производительность, т.к. приложения могут работать с локальными копиями , не обмениваясь данными с удаленными узлами. Во-вторых, репликация позволяет обеспечить большую доступность, т.к. реплицированный объект остается доступным для обработки до тех пор, пока остается хотя бы одна его реплика. Главный недостаток репликации заключается в том, что при обновлении реплицируемого объекта, все его копии должны синхронизироваться. В системе, которая поддерживает репликацию данных, должна также поддерживаться независимость от репликации, т.е. пользователь не должен касаться проблем связанных с созданием и синхронизацией копий. Обработка распределенных запросов При обработке в распределенной системе запроса необходимо выработать эффективную стратегию его реализации. Например, запрос на объединение отношений Rx , расположенного на узле X , и отношения Ry , хранимого на узле Y , может быть выполнен с помощью перемещения отношения Rx на узел Y , перемещения отношения Ry на узел X или перемещения этих двух отношений на третий узел Z и т.д. Это означает, что при выполнении запроса на распределенной БД необходим его предварительный анализ с последующим выбором оптимальной стратегии его реализации. Управление распределенными транзакциями В распределенной системе выполнение транзакции связано с исполнением программных кодов на нескольких узлах. Транзакция это логическая единица работы, которая включает всю совокупность действий, необходимых для реализации запроса. Транзакция считается неделимым процессом, т.е. если какое либо из составляющих действий окажется не выполненным, то вся транзакция считается не выполненной. Каждый программный код, исполняемый на каком либо узле при выполнении транзакции, называется агентом. Таким образом, транзакция состоит из нескольких агентов, т.е. процессов реализующих транзакцию. В процессе управления транзакцией выделяют управление восстановлением и управление параллельной обработкой. Первое из них базируется на протоколе двухфазной фиксации. В грубом приближении в соответствии с этим протоколом в начале транзакции устанавливается точка фиксации данных, т.е. как бы создается копия данных, которые предполагается изменить в результате транзакции. Если транзакция завершена нормально, то точка фиксации сохраняется до выполнения следующей транзакции. Если же произошел сбой, то система возвращает состояние данных в точку фиксации, позволяя не допустить необратимого неправильного изменения БД. Управление параллельной обработкой предполагает установку блокировок на отношения, группы записей с целью не допустить изменение данных другим пользователем во время выполнения транзакции. Независимость от аппаратного обеспечения Используемые в настоящее время компьютеры характеризуются большим разнообразием. В связи с этим существует необходимость интеграции данных на всех системах и создания для пользователя представления единой системы. Должна иметься возможность запуска одной и той же СУБД на разном аппаратном обеспечении. Независимость от операционной системы Эта цель является следствием предыдущей. |
оценка ноу хау в Смоленске
оценка стоимости автомобиля для наследства в Курске