Главная » SQL, Базы данных » УПОРЯДОЧИВАЕМОСТЬ

0

Выше в данной главе была заложена основа для изучения крайне важного понятия упорядочиваемости, к чему мы теперь приступаем. Упорядочиваемость — это общепринятый критерий правильной организации чередующегося выполнения  множества транзакций; иными словами, такая организация выполнения  считается правильной тогда и только тогда, когда она является упорядочиваемой3. Любая конкретная процедура организации выполнения заданного множества транзакций является упорядочиваемой (а следовательно, правильной) тогда и только тогда, когда она эквивалентна некоторой процедуре последовательного выполнения тех же транзакций (т.е. гарантирует достижение таких

3  В литературе фактически можно найти определения двух видов упорядочиваемости — упорядочиваемость по конфликтам (conflict serializability) и упорядочиваемость по просмотру (view serializability). Но понятие упорядочиваемости по просмотру почти не имеет практического значения и поэтому термин "упорядочиваемость" применяется как  обозначение именно  упорядочиваемости по  конфликтам. Дополнительную информацию по этой теме можно, например, найти в [16.21].

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

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

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

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

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

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

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

Снова обратившись к примерам, приведенным в разделе 16.2 (рис. 16.1-16.4), можно убедиться, что в каждом из рассматриваемых случаев проблема состояла именно в том, что применяемая процедура организации чередующегося  выполнения транзакций не была упорядочиваемой. Это означает, что в этих вариантах выполнение "вначале А, затем В" или "вначале в, затем А" не приводит к получению одинаковых результатов. Кроме того, анализ материала, изложенного в разделе 16.4, под этим новым углом зрения показывает, что действие строгого протокола двухфазной блокировки сводится именно к тому, что он в каждом случае обеспечивает соблюдение принципов упорядочиваемости. На рис. 16.7 и 16.8 принятая организация чередующегося выполнения транзакций эквивалентна варианту "вначале в, затем А". На рис. 16.6 и 16.9 показано, что происходит взаимоблокировка, а это означает, что для одной из двух транзакций должен быть выполнен откат (и, предположительно, повторный запуск на выполнение в какой-то последующий

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

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

Следует отметить, что два разных последовательных графика, в которых участвуют одни и те же транзакции, вполне могут вырабатывать разные результаты, и это при том, что оба графика являются правильными. Это означает,  что два разных чередующихся правильных графика, в которых участвуют одни и те же транзакции, также могут вырабатывать различные результаты. В качестве примера рассмотрим транзакцию А, смысл которой сводится к тому, чтобы "сложить 1 с х", и транзакцию в, которая имеет своей целью "удвоить х" (где х — некоторый элемент в базе данных). Предположим также, что начальное  значение  х равно 10. В таком случае последовательный график "А, затем в" приводит к получению результата х = 22, а последовательный график "вначале в, затем А" приводит к получению результатах = 21. Оба эти результата в равной степени являются правильными, и поэтому любой график, который гарантирует эквивалентность последовательным графикам "вначале А, затем В" или "вначале в, затем А", также является правильным.

Понятие упорядочиваемое™ было впервые введено (хотя и не под таким названием)

Эсвараном (Eswaran) и др. в [16.6]. Кроме того, в той же статье была доказана важная теорема, называемая теоремой двухфазной блокировки, которую мы будем рассматривать в приведенной ниже формулировке4.

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

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

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

■     после освобождения любой блокировки транзакция больше не должна приобре тать какие-либо дополнительные блокировки.

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

4 Двухфазная блокировка не имеет ничего общего с двухфазной фиксацией; просто эти два термина имеют внешнее сходство.

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

Рассматриваемое здесь понятие упорядочиваемости оказывает значительную помощь в анализе этой области, которая может стать источником многих затруднений, поэтому в данном разделе приведено еще несколько дополнительных замечаний на эту тему. Предположим,  что  I  —  чередующийся  график,  который  охватывает  некоторое множество транзакций Т1, Т2, . . ., тп. Если график I является упорядочиваемым, то существует по  меньшей  мере  один  последовательный  график  S,  который  включает  множество транзакций Т1, Т2,  .  . ., Тп, такой что I эквивалентен S. График  s называется упорядочением графика I.

Теперь предположим, что Ti и тj — две любые разные транзакции в множестве Т1, Т2, . . ., Тп. Допустим, что Ti предшествует Tj в упорядочении  S. Поэтому в чередующемся графике I  достигнутый эффект организации  чередующегося выполнения должен быть таким, как если бы транзакция Ti  действительно выполнялась перед Tj. Иными словами, неформальной, но очень удобной характеристикой упорядочиваемости является соблюдение того  требования, что если А и в — любые две транзакции, участвующие в некотором  упорядочиваемом графике, то в этом графике либо А логически предшествует в, либо в логически предшествует А; это означает, что либо в может воспользоваться результатами выполнения А, либо А — результатами выполнения в. (Если А вырабатывает  выходные  результаты  х,  у,  …,  z  и  в  получает  в  качестве входных любые из данных х, у, . . ., z, то в в любом  случае получает эти данные либо так, как если бы все они были выведены транзакцией А, либо все они были такими, как перед выводом из транзакции А  (т.е. перед ее выполнением), а не в виде смеси результатов  этих  двух  типов.)   И   наоборот,  если  эффект  действия  чередующегося графика  не  сводится  к  такой  ситуации,  как если  бы  А  выполнялась  перед  в  или  В выполнялась перед А, то этот график нельзя считать упорядочиваемым и правильным.

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

Источник: Дейт К. Дж., Введение в системы баз данных, 8-е издание.: Пер. с англ. — М.: Издательский дом «Вильямс», 2005. — 1328 с.: ил. — Парал. тит. англ.

По теме:

  • Комментарии