Распределенная обработка данных. Найханова Л.В. - 56 стр.

результат х=22, а при последовательном выполнении сначала транзакции В, а затем
транзакции А - х=21. Оба результата одинаково верные, а любой график запуска,
эквивалентный выполнению либо сначала транзакции А, а затем транзакции В, либо
сначала транзакции В, а затем транзакции А, также является верным.
     Концепция способности к упорядочению была впервые предложена (хотя и под
другим названием) Есвараном (Eswaran). В его работе также доказана важная теорема
двухфазной блокировки, которая кратко может быть сформулирована следующим
образом:
     Если все транзакции подчиняются “протоколу двухфазной блокировки”, то для всех
возможных чередующихся графиков запуска существует возможность упорядочения.
     При этом протокол двухфазной блокировки, в свою очередь, формулируется
следующим образом.
     1. Перед выполнением каких-либо операций с некоторым объектом (например, с
        кортежем базы данных) транзакция должна заблокировать этот кортеж.
     2. После снятия блокировки транзакция не должна накладывать никаких других бло-
        кировок.
     Таким образом, транзакция, которая подчиняется этому протоколу, характеризуется
двумя фазами: фазой наложения блокировки и фазой снятия блокировки.
      На практике вторая фаза часто сводится к единственной операции окончания
выполнения (или отмены выполнения) в конце транзакции. Действительно, описанный
выше в этой главе протокол блокировки можно рассматривать как строгую формулировку
двухфазного протокола.
      Понятие способности к упорядочению существенно облегчает понимание этой до-
вольно запутанной области знаний. В дополнение к сказанному следует добавить не-
сколько комментариев. Пусть Е является чередующимся графиком запуска, включающим
некоторый набор транзакций Т1, Т2,,…, Тn. Если Е является графиком, допускающим
возможность упорядочения, то существует некоторый последовательный график запуска
S, содержащий такой набор транзакций Т1, Т2, … Тn, что график Е эквивалентен графику S.
В таком случае S называется упорядочением Е. Как уже было показано ранее, S
необязательно является уникальным, т.е. некоторый график запуска Е может иметь
несколько упорядочений.
      Пусть Тi и Tj - некоторые транзакции множества транзакций Т1, T2,, ..., Тn. Не теряя
общности изложения, предположим, что в упорядочении S транзакция Тi предшествует Тj.
Следовательно, для чередующегося графика запуска E это значит, что транзакция Ti
выполняется перед транзакцией Tj. Иначе говоря, неформальная, но очень полезная
характеристика упорядочения может быть выражена следующим образом. Если А и В
являются любыми двумя транзакциями некоторого графика запуска, допускающего
возможность упорядочения, то либо А логически предшествует B, либо B логически
предшествует A, т.е. либо B использует результаты выполнения транзакции А, либо А
использует результаты выполнения транзакции B. (Если транзакция А приводит к
обновлению кортежей р, q, ... r и транзакция В использует эти кортежи в качестве входных
данных, то используются либо все обновленные с помощью А кортежи, либо полностью
не обновленные кортежи до выполнения транзакции А, но никак не их смесь.) Наоборот,
график запуска является неверным и не подлежит упорядочению, если результат
выполнения транзакций не соответствует либо сначала выполнению транзакции A, а затем
транзакции B, либо сначала выполнению транзакции В, а затем транзакции А.
      В заключение стоит подчеркнуть, что если некоторая транзакция А не является
двухфазной (т.е. не удовлетворяет протоколу двухфазной блокировки), то всегда можно
построить некоторую другую транзакцию B, которая при чередующемся выполнении
вместе с транзакцией А может привести к графику запуска, не подлежащему
упорядочению и неверному. В настоящее время с целью понижения требований к
ресурсам и, следовательно, повышения производительности и пропускной способности в

56