Организация баз данных
Выборка кортежей с данными только о группе А-98-51 из отношения Groups. На этом этапе выполняется чтение 100 кортежей и создается результат, состоящий только из 1 кортежа.
Соединение результата, полученного на этапе 1, с отношением Students (по атрибуту GrNo). На этом этапе выполняется считывание данных о 10000 студентов и 10000 раз считывается информация о группе А-98-51, полученная на 1 этапе. Результат содержит 30 кортежей.
Проецирование результата, полученного на этапе 2, по атрибуту StName (аналогично этапу 3 предыдущей последовательности действий). Требуемый результат содержит 30 кортежей.
Первая из показанных процедур выполняет в общем 1010000 операций ввода-вывода кортежа, в то время как вторая процедура выполняет только 20000 операции ввода-вывода. Следовательно, если принять "количество операции ввода-вывода кортежа" в качестве меры производительности, то вторая процедура в 50 раз эффективнее первой. (На практике мерой производительности служит количество операций ввода-вывода страницы, а не одного кортежа, но для данного примера эту поправку можно игнорировать.)
Обзор процесса оптимизации
Стадия 1. Преобразование запроса во внутреннюю форму
На этой стадии выполняется преобразование запроса в некоторое внутреннее представление, более удобное для машинных манипуляций. Это полностью исключает из рассмотрения конструкции внешнего уровня (такие как "игра слов" конкретного синтаксиса рассматриваемого языка запросов) и готовит почву для последующих стадий оптимизации.
Обычно внутреннее представление запросов является определенной модификацией абстрактного синтаксического дерева, или дерева запроса.
Например, на рисунке показано дерево рассматриваемого выше в этой главе запроса ("Получить список фамилий студентов, учащихся в группе А-98-51").
рис. 17.2. Дерево запроса "Получить список фамилий студентов, учащихся в группеА-98-51"
Стадия 2. Преобразование в каноническую форму
На этой стадии оптимизатор выполняет несколько операций оптимизации, которые "гарантированно являются хорошими" независимо от реальных данных, хранящихся в базе данных, и путей доступа к ним. Суть в том, что все запросы (за исключением простейших) реляционные языки обычно позволяют выразить несколькими разными (по крайней мере, внешне) способами.
Замечание о канонической форме. Понятие канонической формы употребляется, во многих разделах математики и связанных с ней дисциплин. Каноническая форма может быть определена следующим образом. Пусть Q – множество объектов (запросов), и пусть существует понятие об эквивалентности этих объектов (а именно: запросы q1 и q2 эквивалентны тогда и только тогда, когда дают идентичные результаты) Говорят, что подмножество C множества Q является подмножеством канонических форм для запросов из Q в смысле определенной выше эквивалентности тогда и только тогда, когда каждому объекту q из Q соответствует только один объект c из C. Тогда говорят, что объект с является канонической формой объекта q. Все "интересующие" свойства, которыми обладает объект q, также присущи и объекту с. Поэтому, чтобы доказать различные "интересующие" результаты, достаточно изучить менее мощное множество объектов C, а не более мощное множество Q.
Чтобы преобразовать результаты стадии 1 в некоторую эквивалентную, но более эффективную форму, оптимизатор использует определенные и хорошо известные правила преобразования, или законы.
Стадия 3. Выбор потенциальных низкоуровневых процедур
После преобразования внутренней формы запроса в более подходящую (каноническую) форму оптимизатор должен решить, как выполнять запрос, представленный в канонической форме. На этой стадии принимается во внимание наличие индексов и других путей доступа, распределение хранимых значений данных, физическая кластеризация хранимых данных и т.п. Заметьте, что на стадиях 1 и 2 этим вопросам совсем не уделялось внимания
Для каждой низкоуровневой операции оптимизатор обладает набором низкоуровневых процедур реализации.
Замечание. С каждой процедурой также связана стоимостная формула, которая указывает "стоимость" выполнения процедуры (т.е. уровень требуемых затрат на ее выполнение). Обычно стоимость вычисляется в контексте операций ввода-вывода с диска, но некоторые системы учитывают также время использования процессора и другие факторы. Эти стоимостные формулы используются на стадии 4.
Следовательно, далее с помощью информации из каталога о состоянии базы данных (существующие индексы, кардинальные числа отношений и т.п.) и данных о зависимостях, описанных выше, оптимизатор выберет одну или несколько процедур-кандидатов для каждой низкоуровневой операции в запросе. Этот процесс обычно называют выбором пути доступа.
Стадия 4. Генерация планов вычисления запроса и выбор плана с наименьшей стоимостью
На последней стадии процесса оптимизации конструируются потенциальные планы запросов, после чего следует выбор лучшего (т.е. наименее дорогого) плана выполнения запроса. Каждый план выполнения строится как комбинация набора процедур реализации, при этом каждой низкоуровневой операции в запросе соответствует одна процедура.
Для выбора плана с наименьшей стоимостью необходим метод привязки стоимости к данному плану. В основном стоимость плана – это просто сумма стоимостей отдельных процедур, которые использованы для его выполнения. Таким образом, работа оптимизатора сводится к вычислению стоимостных формул для каждой такой процедуры. Проблема состоит в том, что стоимость выполнения процедуры зависит от размера отношения (или отношений), которое выбранная процедура обрабатывает.
Преобразование выражений
Выборки и проекции
Последовательность выборок данного отношения может быть преобразована в одну (объединенную операцией AND) выборку этого отношения. Например, выражение
(A WHERE выборка_1) WHERE выборка_2
эквивалентно выражению
A WHERE выборка_1 AND выборка_2
В последовательности проекций данного отношения можно игнорировать все проекции, кроме последней. Таким образом, выражение
(А [проекция_1]) [проекция_2]
эквивалентно выражению
А [Проекция_2]
Конечно, чтобы первое выражение имело смысл, каждый атрибут, используемый в проекции_2, должен присутствовать и в проекции_1.
Выборку проекции можно трансформировать в проекцию выборки. Например, выражение
(А [проекция]) WHERE выборка
эквивалентно выражению
(A WHERE выборка) [проекция]
Заметьте, что в основном всегда полезно выполнять операцию выборки перед операцией проекции, так как выборка приведет к уменьшению размера входных данных для операции проекции и, следовательно, к уменьшению количества данных, которые нужно сортировать для исключения дублирующихся записей в процессе вычисления проекции.
Распределительный закон
Говорят, что унарный оператор распределяется по бинарной операции О, если для всех А и В выполняется условие
F (А О В) є f (А) О f (В).
В реляционной алгебре операция выборки распределяется по операциям объединения, пересечения и вычитания. Операция выборки также распределяется по oneрации соединения, но только тогда, когда условие выборки состоит (в самом сложном случае) из объединенных операцией AND двух отдельных условий выборки – по одному для каждого операнда операции соединения. Для рассматриваемого выше в этой главе примера сформулированное условие соблюдено (условие выборки очень простое и относится лишь к одному операнду), и можно использовать распределительный закон для замены рассматриваемого в примере выражения его более эффективным эквивалентом. Чистый эффект этого закона состоит в том, что можно выполнять "раннюю выборку". Выполнение ранней выборки почти всегда себя оправдывает, так как приводит к значительному уменьшению количества кортежей, которые нужно рассматривать в следующей операции. Кроме того, ранняя выборка может привести к уменьшению количества кортежей и на выходе следующей операции.
Далее приведено несколько более специфических примеров распределительного закона, на этот раз с операцией проекции. Во-первых, операция проекции распределяется по операциям объединения и пересечения (но не по операции вычитания). Во-вторых, эта операция также распределяется по операции соединения, но только в том случае, если в проекцию включены все атрибуты соединения. Точнее, выражение
(A JOIN В) [проекция]
эквивалентно выражению
(А [А_проекция]) JOIN (В [В_проекция])
тогда и только тогда, когда множество использованных в проекции атрибутов равняется объединению множеств атрибутов в А_проекции и В_проекции и включает атрибуты, по которым выполнено соединение. Этот закон можно использовать для выполнения ранних "проекций", которые обычно себя оправдывают по тем же причинам, что и операции выборки.
Коммутативность и ассоциативность
Законы коммутативности и ассоциативности – это еще два общих правила преобразования. Говорят, что бинарная операция О является коммутативной, если для всех А и В истинно равенство
А О В є В О А
Например, в обычной арифметике операции умножения и сложения являются коммутативными, а операции деления и вычитания – нет. В реляционной алгебре коммутативными являются операции объединения, пересечения и соединения, а операции вычитания и деления таковыми не являются.
Перейдем к ассоциативности. Принято считать, что бинарная операция О является ассоциативной, если для всех А, В и С истинно равенство
А О (В О С) є (А О В) О С.
Например, в обычной арифметике произведение и сложение – ассоциативные операции, деление и вычитание – нет. В реляционной алгебре ассоциативными являются операции объединения, пересечения и соединения, а операции вычитания и деления таковыми не являются. Так, например, если в запросе используется соединение трех отношений, А, В и С, то из законов коммутативности и ассоциативности
Идемпотентность
Еще одним важным правилом является закон идемпотентности. Идемпотентной называют такую бинарную операцию О, для которой для всех А выполняется равенство
A О А = А.
Можно ожидать, что свойство идемпотентности также может быть полезным в процессе трансформации выражений. В реляционной алгебре операции объединения, пересечения и соединения являются идемпотентными, а операции деления и вычитания – нет.
Вычисляемые скалярные выражения
Предметом применения законов трансформации являются не только реляционные выражения. Например, уже было показано, что некоторые законы трансформации применимы и к арифметическим выражениям. Ниже приведен пример. Выражение
А * В + А * С
можно трансформировать в выражение
А * (В + С)
вследствие того, что операция умножения "*" распределяется по операции сложения "+". Оптимизатор реляционных выражений должен обладать информацией о подобных преобразованиях, так как он учитывает вычисляемые скалярные выражения в контексте операций EXTEND и SUMMARIZE.
Говорят, что бинарная операция О распределяется по бинарной операции О, если для всех А, В и С истинно равенство
A Ъ (B О C) = (A Ъ B) O ( A Ъ C )
(для приведенного выше арифметического примера замените Ъ на "*", а О на "+").
Условия
Перейдем к обсуждению условий или выражений, результатами которых могут быть истина или ложь. Предположим, что А и В – атрибуты двух различных отношений, тогда условие
А>В AND В>3
(которое может быть частью запроса) абсолютно эквивалентно выражению
А > В AND В > 3 AND A > 3
и потому может быть преобразовано в это выражение.
Данная эквивалентность базируется на том, что операция ">" является транзитивной. Заметьте, что выполнение подобного преобразования весьма полезно, так как позволяет системе создать дополнительную выборку (с помощью условия "А > З") перед выполнением соединения "больше чем", требуемого условием "А > В".
Замечание. Этот прием реализован в различных коммерческих продуктах, включая систему DB2, в которой его называют транзитивным замыканием предикатов. А вот другой пример. Условие
А > В OR (С = D AND Е < F)
можно преобразовать в условие
(A > B OR С = D) AND (А > В OR Е < F)
вследствие того, что операция OR распределяется по операции AND. Этот пример демонстрирует другой общий закон: "Любое условие может быть преобразовано в эквивалентное условие, называемое конъюнктивной нормальной формой (КНФ)". КНФ-выражение имеет вид:
C1 AND C2 AND … AND Cn,
где С1, C2, ..., Cn – условия (называемые частичная конъюнкция), в которых не используется операция AND. Преимущество КНФ состоит в том, что КНФ-выражение истинно, только если истинны все его частичные конъюнкции. Аналогично, КНФ выражение ложно, если ложь является результатом хотя бы одной частичной конъюнкции. Так как операция AND коммутативна (A AND В равно В AND А), то оптимизатор может вычислять отдельные частичные конъюнкции в любом порядке, в частности по возрастанию сложности (сначала простые). И как только найдена частичная конъюнкция, результатом которой является ложь, весь процесс вычисления КНФ-выражения можно останавливать.
Более того, в среде параллельных вычислений возможно параллельное вычисление всех частичных конъюнкций. Опять же, как только найдена первая частичная конъюнкция, результатом которой является ложь, весь процесс вычисления КНФ-выражения можно останавливать.
Семантические преобразования
Рассмотрим следующее выражение:
(Students JOIN Groups) [StName]
Данное соединение относится к соединениям типа внешниий-к-согласованному-потенциалъному-ключу. В этом соединении внешнему ключу в отношении Students ставится в соответствие потенциальный ключ отношения Groups. Следовательно, кортеж в отношении Students связан с определенным кортежем в отношении Groups. Таким образом, из каждого кортежа в отношении Students в общий результат поступает только значение атрибута StName. Другими словами, соединение можно не выполнять! Рассматриваемое выражение можно заменить выражением
Students [StName]
Преобразование, корректное в силу определенного условия целостности, называют семантическим преобразованием, а оптимизацию, полученную в результате подобных преобразований, – семантической оптимизацией. Семантическую оптимизацию можно определить как процесс преобразования запроса в другой, качественно отличный запрос, который, тем не менее, дает результат, идентичный результату исходного запроса, благодаря тому что данные удовлетворяют определенному условию целостности.
Важно понимать, что в принципе любое условие целостности может быть использовано для семантической оптимизации (если это условие не отсрочено и в данный момент действует на базу данных).
Статистики базы данных
На стадиях 3 и 4 общего процесса оптимизации (они называются стадиями "выбора пути доступа") используются так называемые статистики базы данных, которые хранятся в каталоге.
Литература:
Дейт К.Дж. Введение в системы баз данных. –Пер. с англ. –6-е изд. –К. Диалектика, 1998. Стр. 474–516.
Восстановление после сбоев
15.1 Понятие восстановления системы
15.2 Транзакции
15.3 Алгоритм восстановления после сбоя системы
15.4 Параллелизм. Проблемы параллелизма
15.5 Понятие блокировки
15.6 Решение проблем параллелизма
15.7 Тупиковые ситуации
15.8 Способность к упорядочению
15.9 Уровни изоляции транзакции
15.10 Поддержка в языке SQL
Понятие восстановления системы
Восстановление в системе управления базами данных, означает в первую очередь восстановление самой базы данных, т.е. возвращение базы данных в правильное состояние, если какой-либо сбой сделал текущее состояние неправильным или подозрительным. Основной принцип, на котором строится такое восстановление, – это избыточность. Избыточность организуется на физическом уровне. Такая избыточность будет скрыта от пользователя, а следовательно, не видна на логическом уровне. Другими словами, если любая часть информации, содержащаяся в базе данных, может быть реконструирована из другой хранимой в системе избыточной информации, значит, база данных восстанавливаема.
Транзакции
Понятие транзакции
Транзакция – это логическая единица работы. Например. Предположим сначала, что отношение Students (отношение студентов) включает дополнительный атрибут AvgMark, представляющий собой средний балл студента, по результатам сдачи текущей сессии. Значение AvgMark для любой определенной детали предполагается равным среднему арифметическому всех значений Mark из таблицы Marks для всех оценок полученных в текущем семестре.
В приведенном примере предполагается, что речь идет об одиночной, атомарной операции. На самом деле добавление новой оценки в таблицу Marks – это выполнение двух обновлений в базе данных (под обновлениями здесь, конечно, понимаются операции insert, delete, а также сами по себе операции update). Более того, в базе данных между этими двумя обновлениями временно нарушается требование, что значение AvgMark для студента 1 равно среднему арифметическому всех значений поля Mark для студента 1 в текущем семестре. Таким образом, логическая единица работы (т.е. транзакция) – не просто одиночная операция системы баз данных, а скорее согласование нескольких таких операций. В общем, это преобразование одного согласованного состояния базы данных в другое, причем в промежуточных точках база данных находится в несогласованном состоянии.
Из этого следует, что недопустимо, чтобы одно из обновлений было выполнено, а другое нет, так как база данных останется в несогласованном состоянии. В идеальном случае должны быть выполнены оба обновления. Однако нельзя обеспечить стопроцентную гарантию, что так и будет. Не исключена вероятность того, что, система, например, будет разрушена между двумя обновлениями, или же на втором обновлении произойдет арифметическое переполнение и т.п. Система, поддерживающая транзакции, гарантирует, что если во время выполнения неких обновлений произошла ошибка (по любой причине), то все эти обновления будут аннулированы. Таким образом, транзакция или выполняется полностью, или полностью отменяется (как будто она вообще не выполнялась).
Системный компонент, обеспечивающий атомарность (или ее подобие), называется администратором транзакций (или диспетчером транзакций), а ключами к его выполнению служат операторы COMMIT TRANSACTION и ROLLBACK TRANSACTION.
Оператор COMMIT TRANSACTION (для краткости commit) сигнализирует об успешном окончании транзакции. Он сообщает администратору транзакций, что логическая единица работы завершена успешно, база данных вновь находится (или будет находиться) в согласованном состоянии, а все обновления, выполненные логической единицей работы, теперь могут быть зафиксированы, т.е. стать постоянными.
Оператор ROLLBACK TRANSACTION (для краткости ROLLBACK) сигнализирует о неудачном окончании транзакции. Он сообщает администратору транзакций, что произошла какая-то ошибка, база данных находится в несогласованном состоянии и все обновления могут быть отменены, т.е. аннулированы.
Для отмены обновлений система поддерживает файл регистрации, или журнал, на диске, где записываются детали всех операций обновления, в частности новое и старое значения модифицированного объекта. Таким образом, при необходимости отмены некоторого обновления система может использовать соответствующий файл регистрации для возвращения объекта в первоначальное состояние.
Еще один важный момент. Система должна гарантировать, что индивидуальные операторы сами по себе атомарные (т.е. выполняются полностью или не выполняются совсем). Это особенно важно для реляционных систем, в которых операторы многоуровневые и обычно оперируют множеством кортежей одновременно; такой оператор просто не может быть нарушен посреди операции и привести систему в несогласованное состояние. Другими словами, если произошла ошибка во время работы такого оператора, база данных должна остаться полностью неизмененной. Более того, это должно быть справедливо даже в том случае, когда действия оператора являются причиной дополнительной, например каскадной, операции.
Восстановление транзакции.
Транзакция начинается с успешного выполнения оператора BEGIN TRANSACTION) и заканчивается успешным выполнением либо оператора COMMIT, либо ROLLBACK. Оператор COMMIT устанавливает так называемую точку фиксации (которая в коммерческих продуктах также называется точкой синхронизации(syncpoint). Точка фиксации соответствует концу логической единицы работы и, следовательно, точке, в которой база данных находится (или будет находиться) в состоянии согласованности. В противовес этому, выполнение оператора ROLLBACK вновь возвращает базу данных в состояние, в котором она была во время операции BEGIN TRANSACTION, т.е. в предыдущую точку фиксации.
Случаи установки точки фиксации:
Все обновления, совершенные программой с тех пор, как установлена предыдущая точка фиксации, выполнены, т.е. стали постоянными. Во время выполнения все такие обновления могут расцениваться только как пробные (в том смысле, что они могут быть не выполнены, например прокручены назад). Гарантируется, что однажды зафиксированное обновление так и останется зафиксированным (это и есть определение понятия "зафиксировано").
Все позиционирование базы данных утеряно, и все блокировки кортежей реализованы. Позиционирование базы данных здесь означает, что в любое конкретное время программа обычно адресована определенным кортежам. Эта адресуемость в точке фиксации теряется.
Следовательно, система может выполнить откат транзакции как явно – например по команде ПО с которым работает пользователь, так и неявно – для любой программы, которая по какой-либо причине не достигла запланированного завершения операций, входящих в транзакцию.
Из этого видно, что транзакции — это не только логические единицы работы, но также и единицы восстановления при неудачном выполнении операций. При успешном завершении транзакции система гарантирует, что обновления постоянно установлены в базе данных, даже если система потерпит крах в следующий момент. Возможно, что в системе произойдет сбой после успешного выполнения COMMIT, но перед тем, как, обновления будут физически записаны в базу данных (они все еще могут оставаться в буфере оперативной памяти и таким образом могут быть утеряны в момент сбоя системы). Даже если подобное случилось, процедура перезагрузки системы все равно должна устанавливать эти обновления в базу данных, исследуя соответствующие записи в файле регистрации. Из этого следует, что файл регистрации должен быть физически записан перед завершением операции COMMIT. Это важное правило ведения файла регистрации известно как протокол предварительной записи в журнал (т.е. запись об операции осуществляется перед ее выполнением). Таким образом, процедура перезагрузки сможет восстановить любые успешно завершенные транзакции, хотя их обновления не были записаны физически до аварийного отказа системы. Следовательно, как указывалось ранее, транзакция действительно является единицей восстановления.
Свойства АСИД.
Из предыдущих разделов следует, что транзакции обладают четырьмя важными свойствами: атомарность, согласованность, изоляция и долговечность (назовем это свойствами АСИД).
Атомарность. Транзакции атомарны (выполняется все или ничего).
Согласованность. Транзакции защищают базу данных согласованно. Это означает, что транзакции переводят одно согласованное состояние базы данных в другое без обязательной поддержки согласованности во всех промежуточных точках.
Изоляция. Транзакции отделены одна от другой. Это означает, что, если даже будет запущено множество конкурирующих друг с другом транзакций, любое обновление определенной транзакции будет скрыто от остальных до тех пор, пока эта транзакция выполняется. Другими словами, для любых двух отдаленных транзакций Т1 и Т2 справедливо следующее утверждение: Т1 сможет увидеть обновление Т2 только после выполнения Т2, а Т2 сможет увидеть обновление Т1 только после выполнения Т1.
Долговечность. Когда транзакция выполнена, ее обновления сохраняются, даже если в следующий момент произойдет сбой системы.
Алгоритм восстановления после сбоя системы
Система должна быть готова к восстановлению не только после небольших локальных нарушений, таких как невыполнение операции в пределах определенной транзакции, но также и после глобальных нарушений типа сбоев в питании вычислительного устройства и др. Местное нарушение по определению поражает только транзакцию, в которой оно собственно и произошло. Глобальное нарушение поражает сразу все транзакции и, следовательно, приводит к значительным для системы последствиям.
Существует два вида глобальных нарушений:
Отказы системы (например, сбои в питании), поражающие все выполняющиеся в данный момент транзакции, но физически не нарушающие базу данных в целом. Такие нарушения в системе также называют аварийным отказом программного обеспечения.
Отказы носителей (например, поломка головок дискового накопителя), которые могут представлять угрозу для базы данных или для какой-либо ее части и поражать. по крайней мере, те транзакции, которые используют эту часть базы данных. Отказы носителей также называют аварийным отказом аппаратуры.
Восстановление после отказов системы
Критической точкой в отказе системы является потеря содержимого оперативной памяти (в частности, рабочих буферов базы данных). Поскольку точное состояние какой-либо выполняющейся в момент нарушения транзакции не известно, транзакция может не завершиться успешно и, таким образом, будет отменена при перезагрузке системы.
Более того, возможно, потребуется повторно выполнить определенную успешно завершившуюся до аварийного отказа транзакцию при перезагрузке системы, если не были физически выполнены обновления этой транзакции.
Для определения во время перезагрузки, какую транзакцию отменить, а какую выполнить повторно система в некотором предписанном интервале (когда в журнале накапливается определенное число записей) автоматически принимает контрольную точку. Принятие контрольной точки включает физическую запись содержимого рабочих буферов базы данных непосредственно в базу данных и специальную физическую запись контрольной точки, которая предоставляет список всех осуществляемых в данный момент транзакций. На рис. 17.2 рассматривается пять возможных вариантов выполнения транзакций до аварийного сбоя системы.
рис. 17.2 Варианты выполнения пяти транзакций.
Пояснения к рис. 17.2:
Отказ системы произошел в момент времени tf.
Близлежащая к моменту времени tf контрольная точка была принята в момент времени tc.
Транзакция Т1 успешно завершена до момента времени tc.
Транзакция Т2 начата до момента времени tc и успешно завершена после момента времени tc, но до момента времени tf.
Транзакция ТЗ также начата до момента времени tc, но не завершена к моменту времени tf
Транзакция Т4 начата после момента времени tc и успешно завершена до момента времени tf.
Транзакция Т5 также начата после момента времени tc, но не завершена к моменту времени tf.
Очевидно, что при перезагрузке системы транзакции типа ТЗ и Т5 должны быть отменены, а транзакции типа Т2 и Т4 – выполнены повторно. Тем не менее заметьте, что транзакции типа Т1 вообще не включаются в процесс перезагрузки, так как обновления попали в базу данных еще до момента времени tc (т.е. зафиксированы еще до принятия контрольной точки). Отметьте также, что транзакции, завершившиеся неудачно (в том числе отмененные) перед моментом времени tf, вообще не будут вовлечены в процесс перезагрузки.
Параллелизм. Проблемы параллелизма
Термин параллелизм означает возможность одновременной обработки в СУБД многих транзакций с доступом к одним и тем же данным, причем в одно и то же время. В такой системе для корректной обработки параллельных транзакций без возникновения конфликтных ситуаций необходимо использовать некоторый метод управления параллелизмом.
Каждый метод управления параллелизмом предназначен для решения некоторой конкретной задачи. Тем не менее, при обработке правильно составленных транзакций возникают ситуации, которые могут привести к получению неправильного результата из-за взаимных помех среди некоторых транзакций. (Обратите внимание, что вносящая помеху транзакция сама по себе может быть правильной. Неправильный конечный результат возникает по причине бесконтрольного чередования операций из двух правильных транзакций). Основные проблемы, возникающие при параллельной обработке транзакций следующие:
проблема потери результатов обновления;
проблема незафиксированной зависимости;
проблема несовместимого анализа.
Проблема потери результатов обновления
Рассмотрим ситуацию, показанную на , в такой интерпретации: транзакция A извлекает некоторый кортеж p в момент времени t1; транзакция B извлекает некоторый кортеж p в момент времени t2; транзакция A обновляет некоторый кортеж p (на основе значений, полученных в момент времени t1) в момент времени t3; транзакция B обновляет тот же кортеж р (на основе значений, полученных в момент времени t2, которые имеют те же значения, что и в момент времени t1) в момент времени t4. Однако результат операции обновления, выполненной транзакцией A, будет утерян, поскольку в момент времени t4 она не будет учтена и потому будет "отменена" операцией обновления, выполненной транзакцией B.
| Транзакция A | Время | Транзакция B |
| Извлечение кортежа р | t1 | – |
| – | t2 | Извлечение кортежа р |
| Обновление кортежа р | t3 | – |
| – | t4 | Обновление кортежа р |
рис. 17.2. Потеря в момент времени t4 результатов обновления, выполненного транзакцией A.
Проблема незафиксированной зависимости
Проблема незафиксированной зависимости появляется, если с помощью некоторой транзакции осуществляется извлечение (или, что еще хуже, обновление) некоторого кортежа, который в данный момент обновляется другой транзакцией, но это обновление еще не закончено. Таким образом, если обновление не завершено, существует некоторая вероятность того, что оно не будет завершено никогда. (Более того, в подобном случае может быть выполнен возврат к предыдущему состоянию кортежа с отменой выполнения транзакции.) B таком случае, в первой транзакции будут принимать участие данные, которых больше не существует. Эта ситуация показана на , .
В первом примере () транзакция A в момент времени t2 встречается с невыполненным обновлением (оно также называется невыполненным изменением). Затем это обновление отменяется в момент времени t3. Таким образом, транзакция A выполняется на основе фальшивого предположения, что кортеж р имеет некоторое значение в момент времени t2, тогда как на самом деле он имеет некоторое значение, существовавшее еще в момент времени t1. В итоге после выполнения транзакции A будет получен неверный результат. Кроме того, обратите внимание, что отмена выполнения транзакции B может произойти не по вине транзакции B, а, например, в результате краха системы. (К этому времени выполнение транзакции A может быть уже завершено, а потому крушение системы не приведет к отмене выполнения транзакции A.)
| Транзакция A | Время | Транзакция B |
| – | t1 | Обновление кортежа р |
| Извлечение кортежа р | t2 | – |
| – | t3 | Отмена выполнения транзакции |
рис. 17.2. Транзакция A становится зависимой от невыполненного изменения в момент времени t2.
| Транзакция A | Время | Транзакция B |
| – | t1 | Обновление кортежа р |
| Обновление кортежа р | t2 | – |
| – | t3 | Отмена выполнения транзакции |
рис. 17.2. Транзакция A обновляет невыполненное изменение в момент времени t2, и результаты этого обновления утрачиваются в момент времени t3.
Второй пример, приведенный на , иллюстрирует другой случай. Не только транзакция A становится зависимой от изменения, не выполненного в момент времени t2, но также в момент времени t3 фактически утрачивается результат обновления, поскольку отмена выполнения транзакции B в момент времени t3 приводит к восстановлению кортежа р к исходному значению в момент времени t1. Это еще один вариант проблемы потери результатов обновления.
Проблема несовместимого анализа
На показаны транзакции A и B, которые выполняются для кортежей со счетами (табл. 17.1). При этом транзакция A суммирует балансы, транзакция B производит перевод суммы 10 со счета 3 на счет 1. Полученный в итоге транзакции A результат 110, очевидно, неверен, и если он будет записан в базе данных, то в ней может возникнуть проблема несовместимости. В таком случае говорят, что транзакция A встретилась с несовместимым состоянием и на его основе был выполнен несовместимый анализ. Обратите внимание на следующее различие между этим примером и предыдущим: здесь не идет речь о зависимости транзакции A от транзакции B, так как