6. Нормальная форма отношений и самогонный аппарат нормализации

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

1. Выбранные для отношения первичные ключи должны быть минимальными.

2. Выбранный состав отношений должен отличаться минимальной избыточностью атрибутов

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

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

5. Перестройка набора отношений при введении новых типов должна быть минимальна.

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

Поставка (Название_фирмы, адрес, товар, количество, цена)

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

Аномалии удаления (например, всех картежей с поставками от некоторого поставщика приведет к потере адреса и других реквизитов фирмы)

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

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

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

1. Первая нормальная форма

2. Вторая нормальная форма

3. Третья нормальная форма

4. Бойса-Котта

5. Четверная нормальная форма

6. Нормальная форма проекции соединения

Основные свойства:

1. Каждая следующая форма в некотором смысле является более ограниченной но лучше предыдущей.

2. При переходе к следующей нормальной форме положительные свойства предыдущих нормальных форм сохраняются

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

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

Полная функциональная зависимость. Поле В находится в полной функциональной зависимости от составного поля А если оно зависит от А и не зависит функционально от любого подмножества поля А.

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

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

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

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

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

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

7. OLTP и OLAP системы. Для адекватного представления предметной области, простоты разработки и поддержки базы данных отношения должны быть приведены к третьей нормальной форме, то есть быть сильно нормализованными. Однако слабо нормализованные отношения имеют свои достоинства, основным из которых является то, что если к базе данным обращаться, в основном только с запросами, а модификацию и добавления делать очень редко, то их выборка проводится значительно быстрее. Это объясняется тем, что в слабо нормализованных отношениях уже как бы произведено их соединение и на это не тратится процессное время.

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

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

OLTP – On-line Transaction processing

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

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

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

Практически все запросы в базе данных OLTP приложения состоят из команд вставки, обновления и удаления. Запросы на выборку в основном предназначены для предоставления пользователям данных из различного рода справочников. Таким образом, большая часть запросов известны заранее еще на этапе проектирования системы. Критическими для OLTP-приложений являются скорость и надежность выполнения коротких операций, обновления данных. Чем выше уровень нормализации данных в OLTP-приложениях, тем оно быстрее и надежнее. Другим типам приложений является OLAP-приложения – Online Analytical processing – приложение оперативной аналитической обработки данных. Это обобщенный термин, характеризующий принципы построения системы, поддержки принятия решений Design Support System (DSS), хранилищ данных Date Warehouse и систем интеллектуального анализа данных, Data Mining

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

1. Добавление в систему новых данных происходит относительно редко крупными блоками (раз в месяц)

2. Данные, добавленные в систему, как правило, никогда не удаляются

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

4. Запросы к системе являются нерегламентированными и достаточно сложными.

5. Скорость выполнения запросов важна, но критична

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

8. Null-значения и трехзначная логика (3VL). Назначение базы данных состоит в хранении и предоставлении информации об интересующей предметной области реального мира. Однако в реальном мире часто встречается ситуация, когда данные неизвестны или неполные. Для решения этой проблемы в базах данным можно использовать типы данных, дополненные новыми значениями, по сути, являются маркером, показывающим, что значение неизвестно. Если значение неизвестно, то алгебраические операции с его участием могут приводить так же к неизвестному значению. При сравнении выражений, содержащих NULL значения, результат так же может быть неизвестен, к примеру. Значение истинности для выражения А=В есть NULL, Если один или оба аргумента есть NULL. Таким образом, определения истинности логических выражений в реляционной модели базируется на трехзначной логике, в которой кроме значений TRUE и False введено значение Unknown. Логическое значение Unknown – это то же самое что и Null-значение. Трехзначная логика базируется на следующих таблицах истинности:

Таблица истинности И

AND	F	T	U
F	F	F	F
T	F	T	U
U	F	U	U

Таблица истинности ИЛИ

OR	F	T	U
F	F	T	U
T	T	T	T
U	U	T	U

Таблица истинности НЕ

NOT
F	T
T	F
U	U

Имеется несколько парадоксальных следствий применения трехзначной логики

1. NOT-значение не равно самому себе, то есть выражение null=null дает значение не Истина а Неизвестно, значит выражение Х=Х необязательно истинно.

2. Неверно так же, что null-значение не равно самому себе так же принимает значение не Истина, а Неизвестно. Х=Х тоже необязательно Ложь.

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

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

Транзакция обладает важными свойствами, известными как свойства АСИД:

1. Атомарность. Транзакция выполняется как атомарная операция, то есть либо выполняется вся транзакция целиком либо не выполняется.

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

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

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

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

1. Подана команда зафиксировать транзакцию

2. Подана команда откатить транзакцию

3. Произошло отсоединение пользователя от СУБД

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

При отсоединении пользователя от СУБД происходит автоматическая фиксация транзакции. При сбое системы происходят более сложные процессы. Кратко суть их сводится к тому, что при последующем запуске системы происходит анализ выполнявшихся до момента сбоя транзакций. Те транзакции, для которых была подана команда фиксации, но результата работы, которых не были занесены в базу данных, выполняются снова, то есть накатом. Те транзакции, для которых нет была подана команда фиксации – откатываются. Свойства АСИД транзакций не всегда выполняются в полном объеме. В идеале транзакции разных пользователей не должны мешать друг другу. То есть они должны выполняться так, чтобы у пользователя создавалась иллюзия того, что он в системе один. Простейший способ обеспечить абсолютную изолированность состоит в том чтобы выстроить транзакции в очередь и выполнять их строго одну за другой. Очевидно, что при этом теряется эффективность работы системы. Поэтому реально одновременно выполнение транзакций. Различаются несколько уровней изоляции транзакций. На низшем уровне изоляции транзакции могут реально мешать друг другу. На высшем уровне они полностью изолированы. За большую изолированность транзакций приходится платить большими накладными расходами системы и замедление работы системы

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

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

10. Целкостность и правила целкостности. Целостность понимания как правильность данных в любой момент времени. Но она может быть достигнута лишь в пределах СУБД не может контролировать правильность каждого отдельного значения, вводимого в базу данных, хотя каждое значение можно проверить на правдоподобность. Например, нельзя обнаружить, что вводимое значение «5», представляет собой номер недели, должно быть «3».

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

1. Целостность сущности. Так как потенциальные ключи фактически служат идентификаторами объектов предметной области, то значения этих идентификаторов не могут содержать неизвестные значения. Это и определяет правило целостности сущности: «Атрибуты, входящие в состав некоторого потенциального ключа не могут принимать NULL-значений»

2. Целостность внешних ключей. Так как внешние ключи фактически служат ссылками на картеже в другом или в том же самом отношении, то эти ссылки не должны указывать на несуществующий объект. Это требование и определяет на следующее правило целостности внешних ключей: «Внешние ключи не должны быть несогласованными, то есть для каждого значения внешнего ключа должно существовать соответствующее значение первичного ключа в родительском отношении»

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

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

1. Отказ выполнить незаполненную операцию

2. Выполнение компенсирующих действий

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

1. По способам реализации

Каждая система обладает своими средствами поддержки ограничений целостности. Различают два способа реализации

• Декларативная поддержка ограничения целостности

• Процедурная поддержка ограничения целостности

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

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

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

• При декларировании или объявлении ограничения текст ограничения хранится в виде некоторого объекта СУБД и для реализации ограничения используются встроенные в СУБД функции, представляющие собой внутренние функции ядра СУБД

• При декларировании ограничения СУБД автоматически генерирует триггеры, выполняющие необходимые действия по проверке ограничений.

Если ограничение целостности реализовано в виде триггеров, то этот программный код является просто телом триггера

2. По времени проверки

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

3. По области действий. По области действия ограничения делятся на:

• Ограничение домена

• Ограничение атрибута

• Ограничение картежа

• Ограничение отношения

• Ограничение базы данных

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

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

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

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

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

13. Физическое проектирование баз данных. Физическая модель данных описывает данными средствами конкретной СУБЛЯДь. Отношения, разработанные на стадии формирования логической модели данных преобразуется в таблицу, атрибуты становятся столбцами таблиц, домены преобразуются в типы данных, принятые в конкретной СУБД.

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

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

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

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

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

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

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

• Операция будет выполнена не целиком или не выполнена

• Во время выполнения этой операции не выполняются никакие другие операции других транзакций.

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

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

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

T = {T₁,T₂,T₃…T_m}

Q = {Q₁,Q₂,Q₃…Q_n}

S = {S₁,S₂,S₃…S_λ},

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

{T₁,Q₁,T₂,S₁,T₃,S₂,S₃,Q₂…}

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

Различают три основные проблемы параллелизма:

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

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

3. Проблема несовместимого анализа

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

Операцию чтения строки P будем обозначать P=P₀

Операцию записи значения P₁ в строку P будем обозначать как P₁→P

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

Две транзакции по очереди записывают некоторые данные в одну и ту же строку и фиксируют изменения

Транзакция А	Время	Транзакция В
Чтение данных P0=P1	t1
	T2	Чтение данных P0=P0
Запись P1→P	T3
	T4	Запись P1→P
Фиксация транзакции	T5
	T6	Фиксация транзакции
Потеря результатов обновления

После окончания обеих транзакций строка P содержит значение P₂, занесенное более поздней транзакцией В. Транзакция А ничего не знает о существовании транзакции В и, естественно, ожидает, что в строке P содержится А.

Таким образом, А потеряла результаты своей работы.

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

Транзакция В изменяет данные в строке. После этого транзакция А читает данные и работает с ними. Транзакция В откатывается и восстанавливает старые значения.

Транзакция А	Время	Транзакция В
	t1	Чтение данных P=P0
	T2	Запись P1→P0
Чтение P=P1	T3
Работа с прочитанными данными P1	T4
	T5	Откат транзакции P0→P
Фиксация транзакции	T6
Работа с «грязными» данными

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

3. Проблема несовместимого анализа.

Включает несколько различных вариантов

1. Неповторяемое считывание

2. Фиктивные элементы (фантомы)

3. Собственно несовместимый анализ

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

Транзакция А	Время	Транзакция В
Чтение данных P=P0	t1
	T2	Чтение данных P=P0
	T3	Запись P1→P
	T4	Фиксация данных
Чтение данных P=P1	T5
Фиксация транзакции	T6
Неповторяемое считывание

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

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

Транзакция А дважды выполняет выборку строк с одним и тем же условием. Между выборками вклинивается транзакция В, которая добавляет новую строку, удовлетворяющую условиям отбора.

Транзакция А	Время	Транзакция В
Выборка строк, удовлетворяющих условию α (n строк)	t1
	T2	Вставка новой строки, удовлетворяющей условию α
	T3	Фиксация транзакции
Повторно отбирает строки (n+1 строк)	T4
Фиксация транзакций	T5
Появление строк, которых раньше не было

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

Собственно несовместимый анализ

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

Транзакция А	Время		Транзакция В
Чтение P1=100, sum= 100	t1
	T2		Снятие денег со счета P3 =100 →50
	T3		Помещение денег на P1 100→50
	T4		Фиксация транзакции
Чтение P2=100 Sum = 200	T5
Чтение P3=50 Sum=250		T6
Фиксация транзакции А sum=250		T7
Sum 250 по всем счетам не правильная. Должна быть 300

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

Пусть на всех счетах находятся одинаковые суммы ($100). Короткая транзакция в этот момент выполняет перевод $50 с одного счета на другой так, что общая сумма по всем счетам не меняется.

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

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

1. Конфликт запись – запись W=W. первая транзакция изменила объект и не закончилась. Вторая транзакция пытается изменить этот объект. Результат – потеря обновления.

2. Чтение – запись R-W. Первая транзакция прочитала объект и не закончилась. Вторая транзакция пытается изменить этот объект. Результат – несовместимый анализ (неповторяемое считывание).

3. Запись – чтение W-R. Первая транзакция изменила объект и не закончилась. Вторая транзакция пытается прочитать этот объект. Результат – чтение грязных данных.

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

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

Пусть транзакция А заключается в действии «сложить х и единицей», а транзакция В – «удвоить х». Тогда последовательный график {A,B} дает результат 2(х+1). А последовательный график {B,A} дает результат 2х+1. Таким образом, может существовать несколько верных графиков запуска транзакций. Приводящих к разным результатам при одном и том же начальном состоянии базы данных. Задача обеспечения изолированной работы пользователя не сводится просто к нахождению правильных сериальных графиков запусков транзакций. Если бы этого было бы достаточно, то лучшим был бы простейший способ реализации, то есть ставить транзакции в общую очередь по мере их поступления и выполнять строго последовательно. Таким способом будет автоматически получен правильный сериальный график. График будет неоптимальным с точки зрения общей производительности системы. Получается ситуация, в которой борются стремление обеспечить сериальность за счет ухудшения общей эффективности работы и стремление улучшить общую эффективность за счет ухудшения сериальности.

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

1. Время ожидания начала транзакции – то время, которое проходит от момента, когда транзакция возникла до момента, когда началась выполняться ее первая элементарная операция.

2. Сумма времен выполнения элементарных операций транзакции

3. Сумма времен всех элементарных времен других транзакций, вклинившихся между элементарными операциями транзакции

Оптимальным будет график, дающий минимум стоимостной функции.

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

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

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

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

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

1. Монопольные X-locks

2. Блокировки чтения S-locks

Правила доступа можно представить в виде матрицы совместимости блокировки.

Транзакция А наложила блокировку	Транзакция В пытается наложить
	S-блокировку	Х-блокировку
S-блокировку	Да	Нет (конфликт R-W)
Х-блокировку	Нет (конфликт W-R)	Нет (конфликт W-W)

Доступ к объектам базы данных должен осуществляться со следующим протоколом доступа к данным:

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

2. Прежде чем обновить объект, транзакция должна наложить на него Х-блокировку. Если транзакция уже заблокировала этот объект S-блокировкой, S должна быть заменена Х

3. Если блокировка объекта транзакции В отвергается, транзакция В переходит в состояние ожидания до тех пор, пока транзакция А не снимет блокировку объекта.

4. Х-блокировки, наложенные на транзакции, сохраняются до конца.

1) Две транзакции по очереди записывают некоторые данные в одну и ту же строку и фиксируют изменения.

Транзакция А	Время	Транзакция В
S-блокировка Р – успешно	T1
Чтение Р=Р0	T2
	T3	S-блокировка Р – успешно
	T4	Чтение Р=Р0
Х-блокировка строки Р – отмена	T5
Ожидание	T6	Х-блокировка Р - отмена
Ожидание	T7	Ожидание

Обе транзакции ожидают друг друга и не могут продолжаться – тупик.

2) Проблема незафиксированности зависимости или чтение грязных данных.

Транзакция В изменяет данные в строке. После этого транзакция А читает измененные данные и работает с ними. Транзакция В откатывается и восстанавливает старые данные.

Транзакция А	Время	Транзакция В
	T1	S-блокировка Р – успешно
	T2	Чтение Р=Р0
	T3	Х-блокировка Р – успешно
	T4	Запись Р1→Р
S – блокировка Р отвергается	T5
Ожидание	T6
S – блокировка Р успешно	T7
Чтение Р=Р0	T8
Работа с прочитанными данными	T9
	T10
Фиксация транзакции	T11

Всё правильно

1. Транзакция А притормозилась до окончания (отката транзакции В). После этого транзакция А продолжила работу в обычном режиме и работала с правильными данными. Конфликт разрешается за счет некоторого возрастания времени работы транзакции А.

19. Решение проблем неповторяемого считывания, фиктивных элементов (фантомов) и собственно несовместимого анализа с помощью аппарата блокировок. 1) Проблема несовместимого анализа

1. Неповторяемое считывание. Транзакция читает одну и ту же строку. Между этими чтениями вклинивается транзакция В, которая изменяет значение строки.

Транзакция А	Время	Транзакция В
S-блокировка. Р-успешно	T1
Чтение Р=Р0	T2
	T3	Х-блокировка. Р – отвергнута
	T4	Ожидание
Повторное считывание Р=Р0	T5	Ожидание
Фиксация транзакции – блокировка снимается	T6	Ожидание
	T7	Х-блокировка Р-успешно
	T8	Запись Р1→Р
	T9	Фиксация транзакции
Все правильно

Транзакция В притормазилась до окончания транзакции А. В результате транзакции А дважды читает одни и те же данные правильно. После окончания транзакции А транзакция В продолжила работу в обычном режиме.

2. Фиктивные элементы (фантомы)

Транзакция А дважды выполняет выборку строк с одним и тем же условием. Между выборками вклинивается транзакция В, которая добавляет новую строку, удовлетворяет условию отбора.

Транзакция А	Время	Транзакция В
S-блокировка удовлетворяет условию α	T1
Выборка строк удовлетворяет условию α	T2
	T3	Вставка новой строки. Удовлетворяющей условию α
	T4	Фиксация транзакции
S – блокировка строк удовлетворяет αi (n+1)	T5
Выборка строк удовлетворяет αi (n+1)	T6
Фиксация транзакции	T7

Появляются строки, которых раньше не было

Блокировка на уровне строк не решила проблему фиктивных элементов

3. Несовместимый анализ

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

Транзакция А	Время	Транзакция В
S-блокировка. Р - успешно	T1
Чтение счета Р1 = 100 и SUM = 100	T2
	T3	X – блокировка счета Р3 – успешно
	T4	Снятие денег с Р3 → Р3 = 50
	T5	Х – блокировка Р1 - отвергается
	T6	Ожидание
S-блокировка Р2 – успешно	T7
Чтение Р2 = 100 и SUM = 200	T8
S – блокировка счета Р3 – отвергается	T9
Ожидание	T10

Обе транзакции ожидают друг друга и не могут продолжаться → тупик. 20. Разрешение тупиковых ситуаций. При использовании протокола доступа к данным по методу блокировок часть проблем удалось разрешить , однако, возникла новая проблема – тупики. Ситуация тупика может возникать при наличии не менее двух операций. Так как нормального выхода из тупиковой ситуации нет, то такую ситуацию необходимо распознавать заранее и устранять методом решения тупиковых ситуаций. Таким методом является откат одной из транзакций (транзакции – жертвы) так, чтобы другие транзакции продолжали свою работу. После разрешения тупика транзакцию, выбранную в качестве жертвы, можно повторить заново. Существует два принципиальных подхода к обнаружению тупиковой ситуации и выбору транзакции жертвы:

1. СУБД не следит за возникновением тупиков. Транзакции сами принимают решение, быть ли им жертвой.

2. За возникновением тупиковой ситуации следит сама СУБД, она же принимает решение, какой транзакцией пожертвовать.

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

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

Как видно из анализа поведения транзакций, при использовании протокола доступа к данным не решаются проблема фантомов. Это происходит из-за того, что были рассмотрены только блокировки только на уровне строк. Можно рассматривать и другие блокировки (блокировка самой базы данных, блокировка файлов базы данных, блокировка таблиц базы данных, блокировка страниц, блокировка отдельных строк таблиц, блокировка отдельных полей). Кроме того можно блокировать заголовки таблиц, индексы или другие объекты. Чем крупнее объект блокировки тем меньше возможностей для параллельной работы. Достоинством блокировок крупных объектов является уменьшение накладных расходов системы и решение проблем, не решаемых с использованием блокировок менее крупных объектов. Например, использование монопольной блокировки на уровне таблицы решает проблему фантомов. При использовании блокировок объектов разной величины возникает проблема обнаружения уже наложенных блокировок. Если транзакция А пытается заблокировать таблицу, то необходимо иметь информацию, не наложены ли уже блокировки на уровне строк этой таблицы, несовместимые с блокировкой таблицы. Для решения этой проблемы используется протокол преднамеренных блокировок, являющийся расширением протокола доступа к данным. Суть этого протокола в том, что перед тем как наложить блокировку на объект (например, на строку таблицы, необходимо наложить специальную, преднамеренную блокировку на объекты, в состав которых входит блокируемый объект, на таблицу, содержащую строку, на файл, содержащий таблицу, на базу данных, содержащую файл). Тогда наличие преднамеренной блокировки таблицы будет свидетельствовать о наличии блокировки строк таблицы для другой транзакции, пытающейся блокировать целую таблицу, не нужно будет проверять наличие блокировок отдельных строк.

Протокол преднамеренных блокировок вводит следующие новые типы блокировок:

1. Преднамеренная блокировка с возможностью взаимного доступа. (IS - Intent Shared lock). Накладывается на некоторый составной объект Т, и означает намерение блокировать некоторый входящий в Т объект в режиме S блокировки. Например, при намерении читать строки из таблицы эта таблица должна быть заблокирована в режиме IS (до этого в таком же режиме должен быть заблокирован файл)

2. Преднамеренная блокировка без взаимного доступа (IX – Intent Exclusive lock). Накладывается на некоторые составные объекты и означает намерение блокировать некоторый входящий в Т объект в режиме X блокировки. Например, при намерении удалять или модифицировать строки из таблицы Т, эта таблица должна быть заблокирована в режиме IX (до этого в таком же режиме должен быть заблокирован файл)

3. Преднамеренная блокировка, как с возможностью взаимного доступа, так и без него. (SIX - Shared Intent Exclusive lock). Накладывается на некоторый составной объект Т и означает разделяемую блокировку всего этого объекта с намерением впоследствии блокировать какие-либо входящие в него объекты в режиме Х блокировок. Например, если выполняется длинная операция просмотра таблицы с возможностью удаления некоторых просматриваемых строк, то можно заблокировать эту таблицу в режиме SIX. (до этого должен быть заблокирован файл в режиме IS)

IS, IX и SIX должны накладываться на сложные объекты базы данных (таблицы, файлы). Кроме того на сложные объекты базы данных могут накладываться и блокировки типов S и X.

Для сложных элементов таблица совместимости блокировок имеет следующий вид:

Транзакция А наложила на таблицу блокировку	Транзакция В пытается наложить на таблицу блокировку IS
	IS	S	IX	SIX	X
IS	Да	Да	Да	Да	Нет
S	Да	Да	Нет	Нет	Нет
IX	Да	Нет	Да	Нет	Нет
SIX	Да	Нет	Нет	Нет	Нет
X	Нет	Нет	Нет	Нет	Нет

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

1. При задании X блокировки для сложного объекта неявным образом задается X-блокировка для всех дочерних объектов этого объекта.

2. При задании S или SIX блокировки для сложного объекта неявным образом задается S блокировка для всех дочерних объектов этого объекта

3. Прежде чем транзакция наложит S или IS блокировку на заданный объект она должна задать IS блокировку (или более сильную) по крайней мере, для одного родительского объекта этого объекта.

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

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

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

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

Транзакция А дважды выполняет выборку строк с одним и тем же условием: между выборками вклинивается транзакция В, которая добавляет новую строку, удовлетворяющую условиям отбора. Транзакция В перед попыткой вставить новую строку должна наложить на таблицу IX SIX или X блокировку. Тогда транзакция А для предотвращения конфликта должна наложит такую блокировку на таблицу, которая не позволяла бы транзакции В наложить IX блокировку. По таблице совместимости определяем, что транзакция А должна наложить на таблицу S, X или SIX блокировку. Блокировку IS не достаточно так как эта блокировка позволяет транзакции В наложить IX блокировку для последующей вставки строк.

Транзакция А	Время	Транзакция В
S-блокировка таблицы (с целью потом блокировать строки) – успешно	t1
S-блокировка строк, удовлетворяющих условию α (заблокировано n строк)	T2
Выборка строк, удовлетворяющих условию α (отобрано n строк)	T3
	T4	IX-блокировка таблицы (с целью потом вставлять строки) – отвергается из-за конфликта с S-блокировкой
	t5	Ожидание
	T6	Ожидание
S-блокировка строк, удовлетворяющих условию α. (заблокировано n строк).	T7	Ожидание
Выборка строк, удовлетворяющих условию α (отобрано n строк)	T8	Ожидание
Фиксация транзакции (снятие всех блокировок)	T9	Ожидание
	T10	IX – блокировки всей таблицы (с целью вставить строки ) – успешно
	T11	Вставка новой строки, удовлетворяющей условию α
	T12	Фиксация транзакции
Всё правильно. Ошибок не обнаружено.	T13

Проблема фиктивных элементов решается если транзакция А использует преднамеренную S-блокировку или более сильную. Так как транзакция А собирается только читать строки таблицы то минимально необходимым условием в соответствии с протоколом преднамеренных блокировок является преднамеренная IS – блокировка таблицы. Однако этот тип блокировки не предотвращает появления фантомов. Таким образом, транзакцию А можно запускать с разными уровнями изолированности, то есть, предотвращая или допуская появление фантомов. Причем, оба способа запуска соответствуют протоколу преднамеренных блокировок для доступа к данным.

Предикатные блокировки. Другим способом блокирования является блокировка не объектов базы данных, а условий, которым могут удовлетворять объекты. Такие блокировки называются предикатными блокировками. Поскольку любая операция над реляционной базой данных задается некоторым условием, то удобным способом было бы S или X блокирование именно этого условия. Однако при попытке использования этого метода в реальной СУБД возникает трудность определения совместимости различных условий. В языке SQL допускаются условия с подзапросами и другими сложными предикатами. Таким образом, проблема совместимости сравнительно легко решается для случая простых условий. Проблема фиктивных элементов (фантомов) решается как раз с использованием предикатных блокировок, так как вторая транзакция не может вставить новые строки, удовлетворяющие уже заблокированному условию. 22. Метод временных меток и механизм выделения слизи версий данных. Альтернативный метод сериализации транзакции, хорошо работающий в условиях редких конфликтов транзакций и не требующий построения графа ожидания транзакций основан на использовании временных меток. Основная идея метода состоит в следующем: если транзакция А началась раньше транзакции В то система обеспечивает такой режим выполнения как если бы А была целиком выполнена до начала В. Для этого каждой транзакции Т предписывается временная метка t, соответствующая времени начала транзакции. При выполнении операции над объектом к базы данных транзакция Т помечает его своей временной меткой и типом операции (чтение / изменение). Перед выполнением операции над объектом r транзакция В выполняет следующие действия:

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

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

3. Если операции В и А конфликтуют, то если временная метка t (A)> t(B) то транзакция А откатывается и, получив новую временную метку, начинается заново. Транзакция В продолжает работу.

4. Если t (A) < t(B) (А старше В), то транзакция В откатывается и, получив новую временную метку, начинается заново. В итоге транзакция обеспечивает такую работу, при которой в случае возникновения всегда откатывается более молодая транзакция.

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

Механизм выделения версий данных

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

1. Для каждой транзакции или запроса запоминается текущий системный номер (SCN – System Current Number). Чем позже начата транзакция, тем больше ее SCN.

2. При записи страниц данных на диск фиксируется SCN транзакции, производящей эту запись. Этот SCN становится текущим системным номером страницы данных.

3. Транзакции, только читающие базы данных не блокируют ничего в базе данных.

4. SCN транзакции А сравнивается с SCN читаемой страницы данных

5. Если SCN страницы данных меньше или равен SCN транзакции А то транзакция А читает эту страницу.

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

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

Транзакция А	Время	Транзакция В
Проверка SCN счета p1 –SCN транзакции больше SCN счета чтение p1 = 100 без наложения блокировки и суммирование SUM = 100	t1
	t2	Х-блокировка счета р3 – успешно.
	t3	Снятие денег со счета р3 -
	t4	Х-блокировка счета р1. успешно
	t5	Помещение денег на счета р1. 100→150
	t6	Фиксация транзакции. Снятие блокировки
Проверка SCN счета р2. SCN транзакции больше SCN счета. Разрешается чтение счета р2 = 100 без наложения блокировки.	t7
Проверка SCN счета р3. SCN транзакции меньше SCN счета. Чтение старого варианта счета р3. Р3 = 100. Суммирование SUM = 300	t8
Фиксация транзакции	t9

Сумма на счетах посчитана верно.

Результат: транзакция А, начавшаяся первой не тормозит конкурирующую транзакцию В. При обнаружении конфликта (чтение транзакцией А измененного счета) транзакции А предоставляется своя версия данных, которая была на момент начала транзакции А. 23. Теорема несварения Есварана о сериализуемости и уровни изоляции. Концепция способности упорядочиванию была впервые предложена Есвараном. В ней был сформулирован протокол двухфазной блокировки.

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

2. После снятия блокировки транзакция не должна накладывать никаких других блокировок.

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

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

1. Нарастание блокировок – во время этой фазы накладываются блокировки, и производится работа с заблокированными объектами.

2. Снятие блокировок – во время этой фазы блокировки только снимаются. Работа с ранее заблокированными данными может продолжаться.

Р абота транзакции может выглядеть:

А и В – объекты, с которыми работают транзакции.

Если транзакция не подчиняется протоколу двухфазной блокировки, то она выглядит так:

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

Реализация изолированности

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

Стандарт SQL предусматривает четыре уровня изоляции:

1. Read Uncommitted

2. Read committed

3. Repeatable Read

4. Serialize able

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

• Неаккуратное считывание

• Неповторяемое считывание

• Фантомность

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

Различные уровни изоляции определяются по возможности или исключению этих особых случаев нарушения способности к упорядочиванию.

Уровень изоляции	Неаккуратное считывание	Неповторяемое считывание	фантомный
Read Uncommitted	да	да	Да
Read committed	нет	Да	да
Repeatable Read	нет	нет	да
Serialize able	нет	нет	нет

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

Виды восстановления данных

Восстановление базы данных может производиться в следующих случаях:

1. Индивидуальный откат транзакции. Откат индивидуальной транзакции может быть инициирован либо самой транзакцией путем подачи команды или системой. СУБД может инициировать откат транзакции в случае возникновения какой-либо ошибки в работе транзакции или если эта транзакция выбрана в качестве жертвы при разрешении тупика.

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

3. Жесткий сбой системы. Аварийный отказ аппаратуры. Он характеризуется повреждением внешних носителей данных

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

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

1. Буферы страниц базы данных

2. Буферы журнала транзакций

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

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

2. Гарантия того, что при возникновении сбоя данные завершенной транзакции можно было бы восстановить, а данные незавершенной транзакции бесследно удалить, то есть обеспечение восстановления последнего согласованного состояния базы данных. Для этого что-то выталкивать на диск все-таки необходимо, даже если мы обладали бы бесконечной ОЗУ.

Таким образом, имеется две причины для периодического восстановления страниц во внешнюю память – недостаток ОЗУ и возможность сбоев. Основным принципом согласованной политики выталкивания буфера журнала и буфера страниц базы данных является то, что запись об изменении объекта базы данных должна попадать во внешнюю память журнала раньше, чем изменение объекта оказывается во внешней памяти базы данных. Соответственно, протокол журнализации называется Write Ahead Log (WAL) и состоит в том, что если требуется вытолкнуть во внешнюю память измененный объект базы данных, то перед этим нужно гарантировать выталкивание во внешнюю память журнала записей о его изменении. Это означает, что если во внешней памяти базы данных содержится объект, к которому применена некоторая команда модификации, то во внешней памяти журнала транзакций содержится запись об этой операции. Обратное неверно. То есть, если во внешней памяти журнала содержится запись о некотором изменении объекта, то во внешней памяти базы данных может и не быть самого измененного объекта. Дополнительным условием на выталкивание буферов накладывается тем требованием, что каждая успешно завершенная транзакция должна быть реально зафиксирована во внешней памяти. Какой бы сбой ни произошел – система должна быть в состоянии восстановить состояние базы данных, содержащей результаты всех зафиксированных к моменту сбоя транзакций. Периодически или при наступлении определенного события (количество страниц в грязном списке превзошло определенный порог) система принимает так называемую контрольную точку. Принятие контрольной точки включает выталкивание во внешнюю память содержимого буферов базы данных и специальную физическую запись контрольной точки, которая представляет собой вписок всех осуществляемых в данный момент транзакций.

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

Индивидуальный откат транзакции

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

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

2. Выбирается очередная запись из списка данной транзакции.

3. Выполняется противоположная по смыслу операция

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

5. При успешном завершении отката в журнал заносится запись о конце транзакции