Для оценки качества выполнения параллельных транзакций необходимо иметь средства построения модели, отражающей график чередования операций. Выполнение условий упорядоченности графика достигаются путем определения строгой последовательности выполнения операций чтения и записи элементов данных.
Для проверки упорядоченности графиков используется граф предшествования (граф упорядоченности).
Определение. Для графика выполнения множества транзакций S = {A, B} граф предшествования представляет собой ориентированный граф G = (V, E), состоящий из множества вершин V – определяющих выполняемые транзакции и множества ориентированных ребер или дуг E – формируемых следующим образом:
1. Создается вершина, соответствующая каждой транзакции.
2. Создается дуга A → B, если транзакция B считывает значение элемента данных, записанного транзакцией A.
3. Создается дуга A → B, если транзакция B записывает значение в элемент данных, после того, как он был считан транзакцией A.
4. Создается дуга A → B, если транзакция B записывает значение в элемент данных, после того, как он был записан транзакцией A.
|
|
Если в графе предшествования, соответствующем чередующемуся графику S, существует дуга A ® B, то в любом последовательном графике S¢, транзакция A должна предшествовать транзакции B.
Если граф предшествования содержит цикл, то соответствующий ему график является не упорядочиваемым.
Например. Построим граф предшествования для примера графика демонстрирующего проблему потери обновления (см. график выше).