Системы управления базами данных

Методическое пособие для студентов 4-5 курсов специальности 40 01 01 «Программное обеспечение информационных технологий»

ЧАСТЬ 1

Автор к.т.н., доцент кафедры ПОИТ БГУИР Копачев Алексей Геннадьевич

2

Системы управления базами данных....................................................................	1
Транзакции и параллелизм.....................................................................................	4
Работа транзакций в смеси...................................................................................	4
Проблема параллельной работы транзакций...............................................	4
Блокировки..........................................................................................................	7
Разрешение тупиковых ситуаций....................................................................	9
Предикатные блокировки...............................................................................	11
Метод временных меток..................................................................................	12
Механизм выделения версий данных...........................................................	12
Теория Есварана...................................................................................................	13
Протокол двухфазной блокировки ..............................................................	13
Реализация изолированности транзакций средствами языка SQL...........	14
Транзакции и восстановление данных............................................................	14
Виды восстановления данных........................................................................	14
Индивидуальный откат транзакций ............................................................	15
Восстановление после мягкого сбоя .............................................................	15
Восстановление после жесткого сбоя............................................................	17
Представление знаний в интеллектуальных системах. ...............................	17
Данные и знания. Основные определения......................................................	17
Модели представления знаний ......................................................................	18
Способы описания. ...........................................................................................	18
Стратегии решения организации поиска....................................................	20
Логический подход. Представление простых фактов в логических
системах..............................................................................................................	22
Типовая организация СУБД. Внутренняя организация реляционной
СУБД.......................................................................................................................	22
Внутренняя организация реляционной СУБД. ..........................................	22
Хэширование .....................................................................................................	25
Журнальная информация...............................................................................	25
Служебная информация..................................................................................	25
Язык SQL. Функции и основные возможности..........................................	26
Определение ограничения целостности и тригеров..................................	26
Представление БД.............................................................................................	26
Определение управляющих структур ..........................................................	27
Авторизация доступа к отношениям и их полям.......................................	27
Точки сохранения и отката транзакций. Встроенный SQL ....................	27
Динамический SQL ..........................................................................................	27
Определение представлений...........................................................................	28
Определение привилегий. ...............................................................................	28
Средства манипулирования данными. ........................................................	29
Табличные выражения....................................................................................	30
Использование SQL при прикладном программировании.........................	34
Встроенный SQL ...............................................................................................	35

	3
Одиночные операторы манипулирования данных. ..................................	37
Некоторые черты SQL’92 и SQL–3 (SQL’99) .................................................	38

4

Транзакции и параллелизм

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

Работа транзакций в смеси

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

1)	либо		операция выполняется целиком , либо вообще не
выполняются.
2)	во	время выполнения операций (элементарных) не выполняются

операции других транзакций.

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

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

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

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

3 основных конфликта:

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

2)проблема незафиксированной зависимости.

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

Пусть есть 2 транзакции: A и B , которые запускаются с некоторым графиком.

Р=Р0 – операция чтения (Р0 – конкретное значение) Р1 → Р – операция записи Р1 в строку Р.

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

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

	A	t	B			t6	END
	Р=Р0	t1	─
	─	t2	Р=Р0
- транзакция А	Р1→Р	t3	─		потеряла данные.
	END	t4	Р2→Р
А ожидала увидеть в				Р значение Р1 , а на самом
	X	t5	─

5

деле будет Р2 .

2) проблема незафиксированной зависимости.

Транзакция В изменяет данные в строке. После этого транзакция А читает измененные данные и работает с ними и в результате транзакция В откатывается и восстанавливает старые данные. В строке Р как было , так и осталось Р1 . Транзакция А работала с данными , которых нет в БД.

A	t	B
─	t1	Р=Р0
─	t2	Р1→
		Р
Р=Р1	t3	─
обработка	t4	─
Р1
─	t5	Р0→
		Р
END	t6	─

3) проблема несовместимого анализа. Включает несколько аспектов:

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

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

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

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

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

A	t	B
Р=Р0	t1	─
─	t2	Р=Р0
─	t3	Р1→Р
─	t4	END
Р=Р1	t5	─
END	t6

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

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

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

Суть: транзакция дважды выполняет выборку строк с одним и тем же условием. Между ними вклинивается транзакция В и добавляет строку с подходящим условием.

A	t	B
α1 (n)	t1	─

─	t2	Р1→Р1 α
─	t3	END

6

α1(n+1) t4 ─

По условию α отобрано n строк. В результате работы транзакция А получила новый результат.

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

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

		A	t	B
	Р1	=100	t1	─
Реально – 300	Sum = 100
		─	t2	Р3100→50
Находим – 250		─	t3	Р1100→50
		─	t4	END
	Р1	=100	t5
	Sum = 200
	Р1	=50	t6
	Sum = 250

Конфликт между транзакциями. Транзакции не мешают друг другу если они:

1)обращаются к разным данным.

2)Выполняются в разное время.

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

Врезультате доступа к данным возможны следующие виды конфликтов:

1)W - W (write - write) : первая транзакция изменила объект и не закончилась. Вторая транзакция пытается изменить этот объект. Результат – потеря обновления.

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

3)W – R (write - read) : первая – изменила объект и не закончилась , вторая – его читает. Результат - грязные данные.

Конфликта типа R-R нет.

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

7

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

Определение. График запуска транзакций называется правильным (сериализуемым), если он эквивалентен какому-либо последовательному графику.

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

Способы реализаций:

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

2.Предоставить поступающим транзакциям разные версии данных.

Блокировки

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

Существует 2 вида блокировок:

1.Монопольная (X – блокировка) – на запись.

2.Разделяемая (S – блокировка) – на чтение.

Если транзакция А блокирует Х – блокировкой объект О, то любой доступ к О со стороны других транзакций отвергается.

Если блокируется S – блокировкой, то

1.Любой запрос на Х – блокировку на О отвергается.

2.Любой запрос на S – блокировку на О принимается.

Матрица совместимостей блокировок.

		B
A	S		X
S	X		R-W
X	W-R		W-W

R-W – конфликт чтение-запись

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

1.Перед тем, как прочитать О, транзакция накладывает на него S – блокировку.

2.Перед тем, как обновить О, транзакция накладывает X – блокировку.

3.Если блокировка О транзакции B отвергается из-за того, что он уже заблокирован транзакцией А, то транзакция B переходит в состояние ожидания

ибудет в нем находиться, пока А не снимет блокировку с О.

4.Блокировка Х сохраняется до конца выполнения транзакции.

8

Проблемы:

1)

A	T	B
S, P	t1	-
P= P0	t2	-
-	t3	S, P
-	t4	P= P0
X, P	t5	-
Wait	t6	X, P
Wait	t7	Wait

Получим состояние, называемое «клинч» (тупик)

2) Проблема незафиксированной зависимости

A		T	B
-		t1	S, P
-		t2	P= P0
-		t3	X, P
-		t4	P1 → P
S, P		t5	-
Wait		t6	P0 → P (RollBack)
S, P		t7	End
P= P0		t8
OK		t9
Проблема решена.
3) Проблема несовместимого анализа
А) Неповторяемого считывания
A		T	B
S, P		t1	-
P= P0		t2	-
-		t3	X, P
-		t4	Wait
P= P0		t5	Wait
End		t6	Wait
-		t7	X, P
-		t8	P1 → P
-		t9	End
Проблема решена.
Б) Фантомы
A		T	B
S, ά (n)(блокировка S		t1	-