Тупики распознавания и разрушения

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

Пример возникновения тупика между транзакциями Т1 и Т2:

1. Транзакции Т1 и Т2 установили монопольные захваты объектов R1 и R2 соответственно.

2. После этого T1 требуется совместный захват R2 а Т2 совместный захват R1.

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

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

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

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

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

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

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

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

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

Альтернативный метод сериализации транзакций хорошо работающий в условиях редких конфликтов транзакций и не требующий построения графа ожидания транзакций основан на использовании временных меток. Основная идея метода состоит в следующем: если транзакция T1 началась раньше транзакции Т2, то система обеспечивает такой режим выполнения, как если бы T1 была целиком выполнена до начала Т2. Для этого каждой транзакции Т предписывается временная метка t соответствующая времени начала транзакции. При выполнении операции над объектом r транзакция Т помечает его своей временной меткой и типом операции (чтение, изменение).

Перед выполнением операции над объектом r транзакция Т1 выполняет следующие действия:

1. Проверяет не закончилась ли транзакция Т пометившая этот объект. Если Т закончилась транзакция Т1 помечает объект r и выполняет свою операцию.

2. Если транзакция Т не завершилась, то Т1 проверяет конфликтность операций. Если операции не конфликтны при объекте r остается или проставляется временная метка с меньшим значением и транзакция Т1 выполняет свою операцию.

3. Если операции Т1 и Т конфликтуют, то если t(T)>t(T1), т.е. транзакция Т1 является более молодой чем Т производится откат Т и Т1 продолжает работу.

4. Если же t(T)<t(T1) (Т старше Т1), то Т1 получается новую временную метку и начинается заново.

 

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

 

Элементы языка SQL

Функции и основные возможности языка SQL

 

Неотъемлемая и важнейшая часть любой системы применяющей базы данных это языковые средства обеспечивающие возможность доступа и действия над данными определения их структур, способов использования и интерпретации. Язык SQL появился в 70-е год как одно из таких средств. Его прототип был разработан фирмой IBM и известен под названием SEQUEL. SQL вобрал в себя достоинство реляционной модели, в частности достоинства лежащего в его основе математического аппарата реляционной алгебры и реляционного исчисления используя при этом сравнительно небольшое число операторов и относительно простой синтаксис. Благодаря своим качествам язык SQL утвержденным в качестве стандарта языком работы с реляционными базами данных. Этот стандарт поддерживается всеми ведущими мировыми фирмами, действующими в сфере технологий баз данных. Использование стандартного языка позволило обеспечить высокую степень независимости разрабатываемых прикладных систем от конкретного типа СУБД существенно поднять уровень и унификацию инструментальных средств разработки приложений, работающих с реляционными базами данных. Большинство коммерческих реализаций SQL имеет некоторые большие или меньшие отличия от стандарта. Это уменьшает совместимость систем использующих различные диалекты SQL, но с другой стороны полезные расширения реализации языка обеспечивает его развитие и со временем включаются в новые редакции стандарта. Настоящее время, ни одна система не реализует стандарт SQL в полном объеме. Во всех диалектах языка имеются возможности не являющиеся стандартными. Таким образом, каждый диалект это надмножество некоторого подмножества стандарта SQL. Это затрудняет переносимость приложений разработанных для одних СУБД в другие.

 

Отличие SQL от процедурных языков программирования

 

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