Шпаргалка по "Базам Данных"

Взаимная  блокировка

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

В состоянии  взаимной блокировки ни одна из транзакций не в состоянии продолжить свою работу, поскольку каждая ожидает завершения работы другой. Если в системе возникает  состояние взаимной блокировки, вовлеченные  в него приложения не смогут разрешить данную проблему собственными силами. Ответственность за обнаружение взаимных блокировок и выхода тем или иным образом из этой тупиковой ситуации должна быть возложена на СУБД.

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

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

Предупреждение  взаимных блокировок

Один  из возможных подходов предупреждения взаимных блокировок состоит в установлении порядка выполнения транзакций на основе использования временных отметок. Были предложены два возможных алгоритма. Первый алгоритм, получивший название "ожидание-отмена", требует, чтобы более старые транзакции ожидали завершения более новых. В противном случае транзакция отменяется и перезапускается с той же самой временной отметкой. Однако рано или поздно она станет самой старой из активных транзакций и уже не будет отменена. Второй алгоритм, "отмена-ожидание", использует диаметрально противоположный подход: только более новые транзакции могут ожидать завершения более старой транзакции. Если более старая транзакция потребует выполнения блокировки элемента данных, уже заблокированного более новой транзакцией, последняя будет отменена.

Выявление взаимных блокировок

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

Взаимная  блокировка имеет место в том  и только в том случае, если граф ожиданий содержит петлю.

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

Распределенные  базы данных (РБД) – совокупность логически  взаимосвязанных баз данных, распределенных в компьютерной сети.

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

а)каждый узел – это полноценная СУБД сама по себе;

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

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

Фундаментальный принцип создания распределенных баз  данных («правило 0»): Для пользователя распределенная система должна выглядеть так же, как нераспределенная система.

Фундаментальный принцип имеет следствием определенные дополнительные правила или цели. Таких целей всего двенадцать:

1.Локальная  независимость. Узлы в распределенной  системе должны быть независимы, или автономны. Локальная независимость означает, что все операции на узле контролируются этим узлом.

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

3.Непрерывное  функционирование. Распределенные  системы должны предоставлять  более высокую степень надежности и доступности.

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

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

6.Независимость  от репликации. Система поддерживает  репликацию данных, если данная  хранимая переменная-отношение –  или в общем случае данный  фрагмент данной хранимой переменной-отношения – может быть представлена несколькими отдельными копиями или репликами, которые хранятся на нескольких отдельных узлах.

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

8.Управление  распределенными транзакциями. Существует 2 главных аспекта управления  транзакциями: управление восстановлением и управление параллельностью обработки. Что касается управления восстановлением, то чтобы обеспечить атомарность транзакции в распределенной среде, система должна гарантировать, что все множество относящихся к данной транзакции агентов (агент – процесс, который выполняется для данной транзакции на отдельном узле) или зафиксировало свои результаты, или выполнило откат. Что касается управления параллельностью, то оно в большинстве распределенных систем базируется на механизме блокирования, точно так, как и в нераспределенных системах.

9.Аппаратная  независимость. Желательно иметь  возможность запускать одну и  ту же СУБД на различных аппаратных платформах и, более того, добиться, чтобы различные машины участвовали в работе распределенной системы как равноправные партнеры.

10.Независимость  от операционной системы. Возможность  функционирования СУБД под различными операционными системами.

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

12.Независиомть  от типа СУБД. Необходимо, чтобы  экземпляры СУБД на различных узлах все вместе поддерживали один и тот же интерфейс, и совсем необязательно, чтобы это были копии одной и той же версии СУБД. 

Билет 10.Модели распределенных баз данных. Однородные и неоднородные системы.

Однородные  распределенные базы данных:

Однородная  СУБД

Однородные  распределенные СУБД относительно просты и имеют в своей основе одинаковые СУБД с единственным языком запросов (обычно SQL). Однородные системы являются сильносвязанными системами. Их встроенные средства поиска данных и средства обработки запросов оптимизированы и обеспечивают максимальную производительность системы. Существует множество вариантов однородных систем РБД.

Вариант 1:

Вариант 2:

Однородные распределенные СУБД обычно проектируются сверху вниз.

Неоднородная  СУБД

Неоднородные  системы включают в себя две и  более различающихся СУБД. Неоднородные системы строятся снизу вверх  с целью создания общей среды  управления над существующими ранее  разрозненными информационными ресурсами. 

Билет 11. Методы построения распределенных БД

1 метод:

проектирование  БД сверху вниз осуществляется в целом  аналогично проектированию централизованных БД:

а) концептуальная модель;

б) логическая модель;

в) реализационная модель;

г) фрагментированная  модель.

При проектировании распределенной БД методом 1 предполагается, что её объекты не будут храниться  в одном месте, а будут распределены по нескольким вычислительным системам. Распределение производится путем  фрагментации или тиражирования.

Фрагментация – декомпозиция объектов БД на 2 или несколько частей.

Горизонтальная  фрагментация – распределение кортежей таблицы по фрагментам. Обычно фрагменты не пересекаются (SELECT <условие>).

Вертикальная  фрагментация – разделение множества атрибутов реляционной таблицы на возможно пересекающиеся подмножества. Фрагменты получаются путем проецирования исходных таблицы.

R1 = R[<список атрибутов>]

Исходную  таблицу можно получить из фрагментов, используя операцию соединения.

Независимо от того, применяется горизонтальная или вертикальная фрагментация, поддерживается глоб. схема, позволяющая воссоздать из имеющихся фрагментов логически централизованную таблицу или другую структуру БД.

1. Значительная доля обработки, запрашиваемой приложениями, скорее всего будет относиться к локальным данным.
2. использование глобальных схем для обработки локальных запросов – не самый рациональный подход в организации обработки данных.

2 метод:

Тиражирование (репликация) – создание дубликатов данных

Репликанты – это множество различных копий некоторого объекта данных, для которых в соответствии с определенными в БД правилами поддерживаются синхронизация с некоторой главной копией.

Принципы  тиражирования:

1. Полное или частичное копирование
2. Синхронное или асинхронное обновление копий
3. Стратегии доступа: копии доступа для обновления или только для чтения

Тиражирование может быть реализовано разными  способами: с помощью программного интерфейса прикладных программ; с помощью встроенных средств самой БД.