Функции и архитектура распределённых СУБД

Распределенная СУБД (СУРБД)

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

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

Функции СУБД:

·                     Обеспечивает хранение информации.

·                     Должна позволять организовывать структуры данных.

·                     Обеспечивать эффективный доступ к данным и модернизировать их.

·                     Удаление, добавление, редактирование.

·                     Обеспечивает санкционированный доступ к данным.

·                     Позволяет создавать пользовательский интерфейс.

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

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

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

·        Расширенные средства ведения каталога, позволяющие сохранять сведения о распределенности данных в сети.

Функции и компоненты СУБД

(Коннолли, с. 88-95)

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

Функции СУБД (первые восемь предложены Коддом – сервисы, которые должны быть реализованы в любой полномасштабной СУБД; остальные две – добавлены Коннолли):

1. Хранение, извлечение и обновление данных

СУБД должна предоставлять пользователям возможность сохранять, извлекать и обновлять данные в БД.

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

2. Каталог, доступный конечным пользователям

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

Системный каталог, или словарь данных, является хранилищем информации, описывающей данные в базе данных (по сути, это данные о данных, т.е. метаданные). Обычно в системном каталоге хранятся следующие сведения: 1) имена, типы и размеры элементов данных; 2) имена связей; 3) накладываемые на данные ограничения поддержки целостности; 4) имена санкционированных пользователей, которым предоставлено право доступа к данным; 5) внешняя, концептуальная и внутренняя схемы и отображения между ними; 6) статистические данные, например частота транзакций и счетчики обращений к объектам БД.

Системный каталог позволяет достичь определенных преимуществ: 1) информация о данных может быть централизованно собрана и сохранена, что позволит контролировать доступ к этим данным, как и к любому другому ресурсу; 2) можно определить смысл данных, что поможет другим пользователям понять их предназначение; 3) упрощается сообщение, т.к. сохраняются точные определения смысла данных; 4) благодаря централизованному хранению избыточность и противоречивость описания отдельных элементов могут быть легко обнаружены; 5) внесенные в БД изменения могут быть запротоколированы; 6) последствия любых изменений могут быть определены еще до их внесения; 7) меры обеспечения безопасности могут быть дополнительно усилены; 8) появляются новые возможности организации поддержки целостности данных; 9) может выполняться аудит сохраняемой информации.

Ключи

Ключ – идентификатор, по которому однозначно определяется картеж (строка) в отношении. Ключ – идентификатор, не содержащий внутри себя другого идентификатора.

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

Требования при выборе первичного ключа:

ü         Минимальный по длине (оптимальный вариант, когда ключ из одного атрибута);

ü         Ключ не должен редактироваться в процессе жизни БД. Например, нельзя в качестве первичного ключа использовать № паспорта или какого-либо документа, значение которого может меняться в течение жизни системы.

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

Атрибут, входящий в ключ отношения (первичный или возможный), называется основным атрибутом. Идентификатор, содержащий избыточные атрибуты называется суперключом, суперключ не ключ.

Еще раз сформулируем дополнительные требования к ключам:

·         Ключи не должны содержать NULL признаков атрибутов.

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

·         Если отношение имеет несколько ключей, то предпочтение при выборе первичного ключа следует отдать ключу с меньшим количеством атрибутов.

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

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

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

Ключи Неопределенность значений атрибутов в ключах

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

Как следует из определения, ключ отношения должен отвечать следующим требованиям:

-

идентифицировать кортеж;

-          не содержать "лишних" атрибутов.

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

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

-          Желательно, чтобы ключ был несоставной

-          Его значение не должно меняться в процессе жизни БД.

Когда невозможно найти идентификатор, отвечающий этим требованиям вводится суррогатный

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

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

Внешний ключ отношения r есть множество атрибутов, которые являются первичным ключом в отношении q.

ПРИМЕР:

R(Студент) = {№ зачетки, Фамилия, Имя, Отчество, …}

R(Успеваемость) = {№ зачетки, Название предмета, Название вида отчетности, Оценка}

Внешний ключ - № зачетки.

Отношение, содержащее внешний ключ, называется ссылающимся отношением (в приведенном выше примере это отношение Успеваемость).

Отношение, содержащее первичный ключ, адекватный внешнему ключу другого отношения, называется ссылочным

отношением (в приведенном выше примере это отношение Студент).

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

Недопустимо, чтобы атрибуты, входящие в первичный или внешний ключ принимали NULL

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

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

Значение NULL не эквивалентно не нулевому численному значению, не пустой строке.

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

Методы управления параллельностью

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

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

Принцип работы метода блокировок следующий: транзакция должна потребовать выполнить блокировку для чтения (S-блокировка

или разделяемая – с взаимным доступом) или для записи (X-блокировка

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

Основные правила метода блокировки:

1). Если транзакция А блокирует объект при помощи Х-блокировки, то любой доступ к этому объекту со стороны другой транзакции будет отменен.

2). Если транзакция А блокирует объект с помощью S-блокировки, то запросы на Х-блокировку будут отвергнуты со стороны др. транзакций, на S-блокировку будут приняты.

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

1). Прежде чем прочитать объект, транзакция должна наложить на него блокировку чтения (S-блокировку).

2). Прежде чем обновить объект, транзакция должна установить для него блокировку для записи (Х-блокировку).
Если транзакция уже установила для объекта S-блокировку, необходимо расширить S-блокировку до уровня X-блокировки.

3). Если запрашиваемая со стороны транзакции B блокировка отвергается из-за конфликта с блокировкой, установленной транзакцией A, то транзакция B переводится в состояние ожидания, до тех пор, пока не будет снята блокировка, установленная транзакцией А. Во избежание ситуации «зависания» (транзакция В бесконечно долго находится в состоянии ожидания), необходимо обрабатывать запросы на блокировку по принципу «первым поступил - первым обработан».

4). Х-блокировки сохраняются вплоть до конца выполнения установившей их транзакции (до ее фиксации (commit) или отката (rollback)).

Метод временных меток.

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

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

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

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



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

Недостатки:

может откатываться более дорогая транзакция, которая началась позже более дешевой;

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

Необходимость управления параллельностью

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

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

1.

Проблема потери результатов обновления;

Рассмотрим ситуацию, когда транзакция А считывает некоторый кортеж t в момент t1, а транзакция В считывает этот же кортеж t в момент t2. Далее транзакция А обновляет кортеж t в момент t3 (исходя из значений в момент t1), а транзакция В обновляет тот же кортеж t в момент t4 (исходя из значений в момент t2 и аналогичных значений, которые были считаны в момент t1).

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

2.      Проблема незафиксированной зависимости (чтение “грязных” данных, неаккуратное считывание);

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

Транзакция А	Время	Транзакция В
Выборка строк, удовлетворяющих некоторому условию : результат n строк	t1	-
-	t2	Вставка строк, удовлетворяющих условию
-	t3	Фиксация транзакции
Выборка строк, удовлетворяющих условию : результат n+1 строк	t4	-

Нормальные формы Общая классификация Отличие НФБК от НФ

Критерием, по которому определяют необходимость декомпозиции отношения, является нахождение отношения в той или иной нормальной форме. Наибольший интерес и практическую значимость представляют первая, вторая и третья исправленная (НФБК) нормальные формы.

Первая нормальная форма(1НФ). Отношение находится в первой нормальной форме, если все значения его атрибутов атомарны.

Понятие атомарности условно. Атомарность или ограничение на атомарность устанавливается исходя из анализа информационного обеспечения системы и структуры выходной документации (если никогда не возникнет необходимость выводить отдельно фамилию, имя и отчество, то можно принять, что ФИО атомарно).

Отношение, не находящееся в 1НФ:

Отношение, находящееся в 1НФ:

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

Вторая нормальная форма (2НФ) Отношение находится во второй нормальной форме, если оно находится в первой нормальной форме, и каждый его неосновной атрибут функционально полно зависит от возможного ключа, т.е. не зависит ни от какого его подмножества. R={ABCD}

Если ключ отношения состоит из одного атрибута, то оно всегда находится во 2-ой нормальной форме. Однако 2НФ не освобождает от избыточного дублирования.

ПРИМЕР: R={ABCD} F={AB>D, A> C}

D зависит функционально полно от ключа, а C – нет, следовательно отношение не находится во 2НФ. Здесь целесообразно вторую ФЗ вынести в отдельное отношение.

ПРИМЕР приведения ко II НФ: дано отношение со схемой R={ABCD} и минимальным покрытием на этой схеме Fmin={A®C, C®D}. Ключом отношения является множество атрибутов {AB}. Атрибуты С и D зависят от подмножества ключа (атрибута A), следовательно, отношение не находится во 2-ой нормальной форме. При этом избыточное дублирование и все, связанные с этим аномалии возникают на атрибутах, зависящих от собственного подмножества ключа.

Практическая значимость понятий: замыкания ФЗ, замыкание атрибутов

Понятие ФЗ: ФЗ определяют однозначное соответствие м/у значениями атрибутов.

ПР1: A>B {А определяет В, А и В принадлежат некоторой схеме R}.

ПР2: ТАБ_№>ФИО, ТАБ_№>квалификация

Множество функциональных зависимостей, которое не может быть дополнено ни одной новой функциональной зависимостью с помощью аксиом рефлексивности, пополнения и псевдотранзитивности, называется замыканием множества функциональных зависимостей и обозначается F+.

Для получения замыкания F+ используются аксиомы Армстронга. Эти аксиомы могут быть использованы для практического вычисления замыкания, так как эти правила являются полными (в том смысле, что для заданного множества ФЗ F минимальный набор ФЗ, которые подразумевают все зависимости из множества F, может быть выведен из ФЗ множества F на основе этих правил) и исчерпывающими (поскольку никакие ФЗ, которые не подразумеваются ФЗ множества F, с их помощью не могут быть выведены).

Замыканием множества атрибутов {A1, A2, …, An} на схеме R есть множество атрибутов, принадлежащих схеме R и функционально зависящих от A1, A2, …, An. Обозначается замыкание как {A1,A2,…,An}+.

Два множества ФЗ-ей эквивалентны, если имеют одно и тоже замыкание множеств ФЗ.

Два множества атрибутов (принадлежат одному классу эквивалентности) эквивалентны, если они имеют одинаковое замыкание.

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

Пусть дано множество функциональных зависимостей F={A®B, B®C} , на схеме R={ABC} отношения r. Докажем, что ключом данного отношения будет атрибут А. С этой целью построим замыкания для всех атрибутов левых частей функциональных зависимостей (см. Таблица 6).

Таблица 6

Таким образом, атрибут А является ключом отношения, так как от него функционально зависят все атрибуты схемы отношения. Очевидно, что замыканием множеств AB, AC, ABC тоже будет вся схема отношения, однако они не будут являться ключами, поскольку содержат внутри себя ключи.

Проблемы декомпозиции на минимальном покрытии Теорема Хеза

Проблема возникает тогда, когда отношение имеет несколько ключей. Например, отношение R = {A,B,C} и множество Ф/З на этой схеме F = { AB®C, C®B}. Возможные ключи AB и AC, при этом AC не детерминант. В отношении наблюдается аномалия, обусловленная тем, что атрибут B, являясь основным атрибутом зависит от собственного подмножества второго ключа AC, т.е. исходное отношение не находится во 2 НФ. Традиционное выделение в отдельное отношение Ф/З не позволяет решить проблему – появляется новое отношение, со схемой R={C,B}, но при этом сохраняется исходное отношение, что приводит к “абсурду” (избыточность и внедрение дополнительных механизмов, поддерживающих это избыточность).

Решить возникшую проблему можно используя теорему Хеза. Пусть дано отношение со схемой: R = {A, B, C} и множеством Ф/З на этой схеме F = {AB®C, C®B}. Декомпозиция без потерь будет состоять из двух отношений – R1 = {CA} и R2 = {CB}. При этом, остается потерянной зависимость AB®C. Ее необходимо поддерживать программным путем.

Распределённая взаимная блокировка

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

Пример.

·

Транзакция Т1 запускается на сайте S1 и создает агента на сайте S2.

·         Транзакция Т2 запускается на сайте S2 и создает агента на сайте S3.

·         Транзакция Т3 запускается на сайте S3 и создает агента на сайте S1.

Эти транзакции устанавлиают блокировки таким образом, что образуется взаимная блокировка по следующей схеме:

Графы ожидания для сайтов

Комбинированный граф ожидания для сайтов

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

Существует 3 общих метода выявления взаимных блокировок в СУРБД: централизованный, иерархический и распределенный.

Централизованный метод

выявления взаимных блокировок, при этом методе один из сайтов системы назначается координатором выявления взаимных блокировок (DDC). Сайт DDC отвечает за построение и обработку глобального графа ожидания. С определенным интервалом каждый менеджер блокировки в системе направляет в адрес DDC свой локальный граф ожидания. Сайт DDC выполняет построение глобального графа ожидания и проверяет его на наличие циклов, если граф содержит 1/более циклов, DDC должен разрушить их, выбрав те транзакции, которые должны быть отменены с выполнением отката, а затем перезапущены. Для минимизации количества пересылаемых данных каждый менеджер блокировки посылает сведения только об удалении/добавлении ребер в локальном графе ожидания, произошедшие с момента последней отправки сведений. Недостаток данного метода: снижение надежности всей системы, т.к.
отказ центрального сайта может вызвать проблемы в функционировании всей системы.

Иерархический метод

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

Распределенный метод

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

на сайте S1

создает агента на другом сайте, например S2, то локальному графу ожидания добавляется ребро, соединяющее узел T1 с узлом ТEXT.

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

Разработка централизованной реляционной БД делится на три этапа проектирования:

1. Концептуальное проектирование

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

2. Логическое проектирование

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

3. Физическое проектирование

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

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

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

2. Распределение – каждый фрагмент сохраняется на сайте, выбранном с учетом «оптимальной» схемы их размещения.

3. Репликация – СУРБД может поддерживать актуальную копию некоторого фрагмента на нескольких различных сайтах.

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

1) Частота запуска приложения на выполнение.

2) Сайт, на котором запускается приложение.

3) Требования к производительности транзакций и приложений.

Качественная информация может включать перечень выполняемых в приложении транзакций, используемые отношения, атрибуты и кортежи, к которым осуществляется доступ, тип доступа (чтение/запись), предикаты, используемые в операциях чтения.

Цели фрагментации:

1) Локальность ссылок - данные должны храниться как можно ближе к местам их пользования.

2) Повышение надежности и доступности за счет использования механизма репликации.

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

4) Баланс между емкостью и стоимостью внешней памяти.

5) Минимизация расходов на передачу данных.

Реализация запросов средствами SQL

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

SELECT [DISTINCT] *|<столбец> [<псевдоним>]

[,<групповая функция>] [,…n]

FROM <таблица>[, …n]| (<подзапрос>)

[WHERE <условие>]

[GROUP BY<выражение группировки>]

[HAVING <условие отбора группы>]

[ORDER BY < столбец >[,…n]]

Ключевое слово DISTINCT используется для возвращения запросом только уникальных строк. При необходимости вывести все записи из отношения используется команда SELECT *. Оператор SELECT устанавливает какие столбцы должны присутствовать в выходных данных. Оператор FROM определяет имена используемой таблицы или нескольких таблиц. WHERE выполняет фильтрации строк объекта в соответствии с заданными условиями. GROUP BY образуются группы строк, имеющих одно и то же значение в указанном столбце. HAVING фильтрует группы строк объекта в соответствии с указанным условием. ORDER BY определяет упорядоченность результатов выполнения оператора. Порядок предложений и фраз в операторе SELECТ не может быть изменен. Только предложения SELECT и FROM являются обязательными, все остальные предложения и фразы могут быть опущены. Операция SELECT является закрытой, т.е. результат запроса к таблице представляет собой др. таблицу. Приведем пример запроса: вывести названия всех предметов, по которым средняя оценка меньше 4.

SELECT

Name_Subject, AVG(Mark)

FROM Progress Pr, Subject S

WHERE Pr.Code_Subject=S.Code_Subject

GROUP BY Name_Subject

HAVING AVG(Mark)<4

Обобщающая функция AVG возвращает усредненное значение в указанном столбце. Стандарт ISO содержит определение 5 обобщающих функций: 1.COUNT возвращает количество значений в указанном столбце. 2.SUM возвращает сумму значений в указанном столбце. 3.AVG. 4.MIN возвращает минимальное значение в указанном столбце. 5.MAX возвращает максимальное значение в указанном столбце.

Запрос, в котором присутствует фраза GROUP BY называется группирующим запросом; столбцы, перечисленные в данной фразе называются группируемыми столбцами. Все имена столбцов, приведенные в предложении SELECT, должны присутствовать и во фразе GROUP BY. За исключением случаев, когда имя столбца используется в обобщающей функции. Предложение ORDER BY всегда ставится в конец команды SELECT. По умолчанию сортировка идет по возрастанию. Для изменения порядка сортировки используется опция DESC. При сортировке по нескольким столбцам столбцы перечисляются через запятую. ORDER BY всегда стоит в конце запроса. Пример: Вывести список имен оценок студентов, расположив их по возрастанию имен и оценок.

SELECT DISTINCT Sname ФИО

FROM Student, Progress

WHERE Student.N_record_book= Progress.N_record_book;

ORDER BY Sname

Составные части языка SQL

SQL является примером языка предназначенного для работы с таблицами с целью преобразования входных данных к требуемому выходному виду. Язык SQL имеет два основных компонента:

язык DDL (Data Definition Language), предназначенный для определения базы данных:

CREATE – создание таблицы;

DROP – удаление таблицы;

ALTER – внесение изменений в описание таблицы, в том числе:

добавление и изменение столбцов;

добавление, разрешение, запрет и удаление ограничений).

язык DML (Data Manipulation Language), предназначенный для выборки и обновления данных:

INSERT – ввод новых строк в таблицу;

DELETE – удаление строк из таблицы;

UPDATE – редактирование данных в таблице;

SELECT – оператор выбора.

Транзакция и ее свойства

Транзакция - действие или серия действий, выполняемых одним пользователем или прикладной программой, которые осуществляют доступ или изменение содержимого БД. Транзакция является логической единицей работы, выполняемой в БД. Она может быть представлена отдельной программой, являться частью алгоритма программы или даже отдельной командой (например, insert, update в SQL) и включать произвольное количество операций, выполняемых в БД. С точки зрения БД, выполнение программы некоторого приложения может расцениваться как серия транзакций, в промежутках между которыми выполняется некоторая обработка данных, осуществляемая вне среды БД. Любая транзакция всегда должна переводить базу данных из одного согласованного состояния в другое, хотя допускается, что согласованность состояния базы будет нарушаться в ходе выполнения транзакции. Любая транзакция завершается одним из двух возможных способов. В случае успешного завершения результаты транзакции фиксируются (commit) в БД, и транзакция переходит в новое согласованное состояние. Если выполнение транзакции не прошло успешно, она отменяется, в этом случае в БД должно быть восстановлено то согласованное состояние, в котором она находилась до начала данной транзакции. Этот процесс называется откатом

(roll back) транзакции. Зафиксированная транзакция не может быть отменена. Если оказывается, что зафиксированная транзакция была ошибочной, потребуется выполнить другую транзакцию, отменяющую действия, выполненные первой транзакцией. В большинстве языков манипулирования данными для указания границ отдельных транзакций используются операторы BEGIN TRANSACTION, COMMIT

и ROLLBACK.

Свойства транзакций.

Существуют некоторые свойства, которыми должна обладать любая из транзакций, это 4 основных свойства (ACID-аббревиатура, составленная из первых букв их английских названий). Атомарность. Это свойство типа «все или ничего». Любая транзакция представляет собой неделимую единицу работы, которая может быть выполнена либо вся целиком, либо не выполнена вовсе. Согласованность.

Трёхуровневая архитектура ANSI-SPARC

ANSI-SPARC - Комитет планирования стандартов и норм SPARC (Standards Planning and Requirements Committee) Национального Института Стандартизации США (American National Standard Institute - ANSI).

Комитете ANSI/SPARC признал необходимость использования трехуровневого подхода общей архитектуры СУБД. Выделены 3 уровня абстракции, т.е. трех различных уровней описания элементов данных. Эти уровни формируют трехуровневую архитектуру, которая охватывает внешний, концептуальный и внутренний уровни.

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

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

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

2.      Пользователи не должны непосредственно иметь дело с такими подробностями физического хранения данных в базе, как индексирование и хеширование . Иначе говоря, взаимодействие пользователя с базой не должно зависеть от особенностей хранения в ней.

3.      Администратор базы данных (АБД) должен иметь возможность изменять структуру хранения данных в базе, не оказывая влияния на пользовательские представления.

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

5.      АБД должен иметь возможность изменять концептуальную или глобальну. Структуру базы данных без какого-либо влияния на всех пользователей.

Внешний уровень – представление базы данных с точки зрения пользователей. Этот уровень описывает ту часть базы данных, которая относится к каждому пользователю.
Внешний уровень состоит из нескольких различных внешних представлений базы данных. Каждый пользователь имеет дело с представлением “реального мира”, выраженным в наиболее удобной для него форме. Внешнее представление содержит только те сущности, атрибуты и связи “реального мира”, которые интересны пользователю.

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

·         Все сущности, их атрибуты, связи;

·         Накладываемые на данные ограничения;

·         Семантическая информация о данных;

·         Информация о мерах обеспечения безопасности и поддержки целостности данных.

Однако этот уровень не содержит никаких сведений о методах хранения данных (например, объем занятого пространства в байтах).

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

На внутреннем уровне хранится следующая информация:

·         Распределение дискового пространства для хранения данных и индексов;

·         Описание подробностей сохранения записей (с указанием реальных размеров сохраняемых элементов данных);

·         Сведения о размещении записей;

·         Сведения о сжатии данных и выбранных методах шифрования.

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

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

Логическая независимость от данных

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

Физическая независимость от данных

– означает защищенность концептуальной схемы от изменений, вносимых во внутреннюю схему (например, использование различных файловых систем или структур хранения, разных устройств хранения, модификация индексов или хеширование).

Управление распределённой параллельностью

Хороший механизм управления параллельностью в распределенной СУБД должен обеспечивать:

1.      устойчивость к отказам на сайтах и в линиях;

2.      высокий уровень параллельности, удовлетворяющий существующим требованиям производительности;

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

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

5.      отсутствие дополнительных ограничений на структуру атомарных действий.

Управление параллельностью

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

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

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

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

Уровни моделирования базы данных

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

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

В основе КМ лежит понятие сущности

– класс объектов, представляющих интерес в рамках данной задачи (Пр: класс-студент, объекты – студент Иванов, студент Петров (объекты-ФИО, преподаватель и т.п. ??? неправильно)).

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

Концептуальный уровень моделирования включает этапы:

1.      Изучение предметной области.

1.1.  Определяется цель автоматизации.

1.2.  Выявляется, с чьей точки зрения, будет создаваться проект.

Выявляются основные процессы, подлежащие автоматизации

2.      Определение типов сущностей.

3.      Определение типов связей.

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

5.      Определение доменов атрибутов.

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

7.      Специализация или генерализация типов сущностей (необязательный этап).

8.      Создание диаграммы «сущность-связь».

9.      Обсуждение локальных концептуальных моделей данных с конечным пользователем.

Виды декомпозиций Декомпозиция без потерь

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

·

или поддерживать избыточное дублирование;

·         или теряем ФЗ и поддерживаем ее программным путем.

Выбор должен быть обоснован.

Существуют следующие виды декомпозиций (можно доб. вопрос 4.-классиф.покрытий и вопрос 5 - теорема Хеза)

1.      Декомпозиция на минимальном покрытии (если в отношении только один ключ);

2.      Декомпозиция на кольцевом покрытии (если в отношении несколько ключей и существуют эквивалентные левые части функциональных зависимостей);

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

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

Процесс декомпозиции следует всегда начинать со следующих операций:

·         с определения (идентификации) всех атрибутов, подлежащих хранению в БД.

·         установления между ними функциональных зависимостей.

Критерием, по которому определяют необходимость декомпозиции отношения, является нахождение отношения в той или иной нормальной форме. (можно добавить вопр. 7 - норм.формы).

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

		A B C a1 b1 c1 a1 b1 c2 a2 b1 c2 a2 b1 c1 a1 b2 c3
	Восстановление распределенных баз данных (Коннолли, с.740-752). Существует 4 типа отказов, характерных для СУРБД: ·          потеря сообщения; ·          отказ линии связи; ·          аварийный останов одного из сайтов; ·          расчленение сети. Если СУРБД обнаружит, что некоторый сайт отказал/стал недоступным, она должна выполнить следующие действия: 1.            отменить выполнение всех транзакций, затронутых данным отказом; 2.            отметить сайт как отказавший, чтобы предотвратить любые попытки его использования другими сайтами; 3.            периодически проверять состояние отказавшего сайта для восстановления его функционирования или ожидать поступления от этого сайта широковещательного сообщения с указанием о восстановлении его нормальной работы; 4.            при перезапуске сайта после отказа на нем должна выполняться процедура восстановления, предназначенная для отката любых транзакций, выполненных на момент отказа лишь частично; 5.            после завершения процедуры локального восстановления отказавший сайт должен обновить свою копию БД, чтобы привести ее в соответствие с остальной частью системы. Процессы восстановления в СУРБД усложняются тем фактом, что соблюдение свойства атомарности требуется как в отношении локальных субтранзакций, так и всей глобальной транзакции. По этой причине в процедуре фиксации и отката транзакций необходимо внести такие изменения, которые не позволят глобальной транзакции зафиксировать/отменить результаты ее выполнения, пока все ее субтранзакции не будут успешно зафиксированы/отменены. Работоспособные сайты не должны оказаться заблокированными из-за отказа др. сайтов, протоколы, обеспечивающие выполнение этого требования называются неблокирующими. Существует 2 широко используемых протокола фиксации транзакций в СУРБД: 1.            протокол двухфазной фиксации транзакций (2PC) 2.            неблокирующий протокол трехфазной фиксации транзакций (3РС). Протокол двухфазной фиксации транзакций выполняется в 2 этапа: этап голосования и принятия решений. Идея состоит в том, что координатор должен опросить всех участников, готовы ли они к фиксации транзакций. Если хотя бы 1 из участников не ответит на запрос в пределах заданного тайм-аута/потребует отката, то координатор (сайт, следящий за выполнением глобальной транзакции) укажет всем участникам на необходимость отката данной транзакции. Данный протокол предполагает, что каждый сайт имеет свой собственный локальный журнал и с его помощью может надежно откатить/зафиксировать транзакцию. Двухфазный протокол включает в себя этап ожидания сообщения от др. сайтов. Во избежание блокировок процессов система использует механизм тайм-аута. Двухфазный протокол не является неблокирующим, т.к. при его использовании возможны ситуации, когда некоторый сайт остается в заблокированном состоянии (процесс, зафиксировавший тайм-аут после отправки согласия на фиксацию транзакции, но так и не получивший глобального подтверждения от координатора, остается в заблокированном состоянии). На практике вероятность блокирования процесса достаточно мала, поэтому в большинстве СУРБД используется именно этот протокол. Трехфазная фиксация транзакций. Для использования этого протокола необходимо выполнение следующих условий: расчленение сети не должно иметь места, по крайней мере 1 сайт всегда должен быть доступен, самое большое К сайтов может отказать одновременно. Трехфазная фиксация является неблокирующей в отношении отказов сайтов, за исключением ситуации одновременного отказа всех сайтов. Основная идея данного протокола состоит в устранении неопределенного периода ожидания, в который попадают участники после согласия на фиксацию транзакции и до получения от координатора извещения о глобальной фиксации/глобальном откате.Для этого вводится третья фаза – предфиксация (PRE-COMMIT), помещаемая между фазами голосования и принятия глобального решения. Участник, получивший глобальное извещение о предфиксации знает, что все участники проголосовали за фиксацию результатов транзакции и что со временем сам участник тоже выполнит фиксацию, если не наступит отказ. Каждый участник подтверждает получение сообщения о предфиксации. После того как координатор получит эти подтверждения, он рассылает команду глобальной фиксации транзакций.