Информатика · объяснение и практика

Конфликтный граф транзакций: цикл запрещает перестановку в последовательное расписание

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

Синие фигурные скобки держат между собой оранжевый квадрат.

В теме Таблицы, базы данных и SQL · Учебная карта

Главная мысль

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

Метод и постановка

Сначала сохраните порядок операций внутри каждой транзакции. Затем сравнивайте только пары из разных транзакций. Два чтения одного объекта не конфликтуют: перестановка не меняет прочитанные версии. Чтение и запись либо две записи одного объекта конфликтуют, и их порядок должен сохраняться при допустимых соседних перестановках.

Для каждого конфликта, где операция T₁ стоит раньше операции T₂, добавьте ребро T₁→T₂. Повторные конфликты с тем же направлением не создают новую вершину или дополнительное условие. Если граф ацикличен, топологический порядок задаёт последовательное расписание с тем же направлением каждого конфликта. Если найден цикл, его требования невозможно одновременно выполнить одним линейным порядком транзакций.

Проверка и границы вывода

Предъявляйте конкретные операции, породившие рёбра. Одного слова «цикл» недостаточно, если граф был построен по неверному правилу, например по любым чтениям. Для положительного ответа укажите топологический порядок; для отрицательного — цикл с именами объектов. Это делает проверку воспроизводимой по исходному журналу.

Критерий относится именно к конфликтной эквивалентности. Наличие цикла не исключает всякую более слабую форму эквивалентности, например эквивалентность по наблюдаемым версиям в отдельных специальных расписаниях. Кроме того, модель одиночных объектов не учитывает автоматически предикатные чтения множества строк. Фантомы могут потребовать расширить набор конфликтов. Сериализуемость не равна восстанавливаемости после отката: работа с незавершёнными записями и каскадные откаты задают отдельные условия. В учебной задаче сначала объявите модель операций, затем применяйте соответствующую ей теорему.

Пример

Расписание r₁(A), w₂(A), r₂(B), w₁(B) даёт ребро T₁→T₂ из чтения A перед чужой записью и ребро T₂→T₁ из чтения B перед чужой записью.

Получился цикл из двух транзакций. Порядок T₁,T₂ нарушил бы конфликт по B, а порядок T₂,T₁ — конфликт по A. Поэтому конфликтно эквивалентного последовательного расписания нет.

От чтения к действию

А теперь — вы

Два чтения одного объекта разными транзакциями создают ребро конфликта?

Частые вопросы

Ацикличный граф даёт какой порядок?

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

Цикл означает невозможность любой эквивалентности?

Нет. Он опровергает конкретно конфликтную сериализуемость; другие определения требуют своих критериев.

Углублённый разбор

Слепые записи и сериализуемость по виду

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

Перед началом: Чтение версии и последняя запись; Конфликтная сериализуемость.

Какие наблюдения должны совпасть

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

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

Слепая перезапись может скрыть промежуточный конфликт

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

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

Проверяйте весь набор объектов и все транзакции

Для небольшого расписания переберите последовательные перестановки транзакций. В каждой перестановке проиграйте операции и сравните карту источников чтений вместе с картой последних писателей. Если чтения отсутствуют, остаётся последняя карта, но ограничения разных объектов могут противоречить друг другу. Порядок, подходящий только для x, ещё не является свидетелем для всего расписания.

Такой перебор экспоненциально растёт и не объявляется промышленным алгоритмом. Его ценность — независимое свидетельство в малой учебной задаче. Также этот критерий не проверяет восстановимость после отката и не добавляет автоматически реальное время клиентов. Эти требования задаются отдельными условиями истории и могут исключить некоторые найденные порядки.

Цикл есть, последовательный вид тоже

Условие. Рассмотрите расписание w₁(x),w₂(x),w₁(x),w₃(y),w₂(y). Транзакция T₁ дважды пишет x; T₂ пишет x, затем y; T₃ пишет y. Чтений нет. Определите две формы сериализуемости.

  1. Первые две записи x дают конфликт T₁→T₂, а следующая запись x даёт T₂→T₁. Конфликтный граф содержит цикл, поэтому конфликтной сериализуемости нет.
  2. Последний писатель x — T₁, последний писатель y — T₂. Для сохранения вида нужен порядок T₂<T₁ по x и T₃<T₂ по y.
  3. Последовательный порядок T₃,T₂,T₁ удовлетворяет обоим требованиям. Внутри T₂ запись x по-прежнему предшествует записи y.
  4. Условий чтения нет, так как в исходном расписании чтения отсутствуют. Поэтому совпадения последних писателей достаточно, и указанный порядок доказывает сериализуемость по виду.

Ответ. По конфликтам — нет; по виду — да, с порядком T₃,T₂,T₁.

Проверка. Перебор шести порядков транзакций даёт единственную карту последних писателей, совпадающую с исходной, именно для T₃,T₂,T₁; конфликтный цикл проверяется отдельно.

Где легко ошибиться. Не переносите отрицательный вывод конфликтного графа на более слабую эквивалентность без проверки её определения. Слепые записи требуют анализа реальных наблюдений.

Проверьте понимание

Какой последовательный порядок сохраняет вид примера?

Вопросы к этой главе

Достаточно совпадения конечных чисел?

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

Любой цикл со слепыми записями допустим по виду?

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

Сверить определения и условия

Объяснение и задачи написаны для erudeet. Эти источники используются для проверки понятий и границ модели.

  • CMU15-445: Concurrency Control Theory

    Прочитаны определение эквивалентности по виду и роль blind writes. Собственное расписание имеет два объекта и три транзакции без чтений; все шесть последовательных порядков проверены по последним писателям.

Строгие двухфазные блокировки и ожидание

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

Перед началом: Совместимые S/X блокировки; Конфликтный граф.

После первого освобождения новые блокировки запрещены

В растущей фазе транзакция получает нужные блокировки и не освобождает их. После первого освобождения начинается сжимающаяся фаза: разрешены только освобождения. Последний момент получения блокировки называют точкой блокирования. Если конфликтующая операция Tᵢ предшествует операции Tⱼ на одном объекте, несовместимая блокировка Tᵢ должна быть освобождена раньше получения блокировки Tⱼ.

При 2PL точка блокирования Tᵢ находится до этого освобождения, а точка Tⱼ — после получения. Поэтому каждое ребро конфликта направлено по возрастанию точек блокирования, и цикл невозможен. Рассуждение относится к успешно выполненным операциям и необходимым режимам блокировок; недостаточная блокировка предикатного чтения может оставить фантомы вне этой упрощённой объектной модели.

Строгость и полный запрет раннего освобождения различаются

Здесь strict 2PL означает двухфазность плюс удержание всех X блокировок до commit или abort. Другие транзакции не читают и не перезаписывают незавершённые изменения через несовместимый доступ. Вариант с удержанием всех S и X до конца часто называют strong strict или rigorous. Термины источников различаются, поэтому конкретное правило важнее одного короткого названия.

Строгий режим упрощает восстановление: после отката не нужно каскадно отменять транзакции, прочитавшие незавершённые значения. Но это не обещает отсутствия ожидания. Транзакция может держать один объект и запрашивать другой, который уже занят соседом. При цикле ожидания никто не способен дойти до конца и освободить свои ресурсы без вмешательства.

Граф ожидания не является графом уже совершённых конфликтов

Ребро Tᵢ→Tⱼ в графе ожидания означает: Tᵢ сейчас ждёт блокировку, удерживаемую Tⱼ. Цикл показывает deadlock в данной модели ожидания. Он не противоречит теореме о конфликтной сериализуемости завершённых 2PL транзакций: ожидаемая операция ещё не была выполнена. Разрыв цикла требует отката жертвы либо иной предусмотренной политики управления.

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

Три удержания и три ожидания

Условие. T₁ держит X(A) и ждёт X(B); T₂ держит X(B) и ждёт X(C); T₃ держит X(C) и ждёт X(A). Все следуют strict 2PL. Что произойдёт без вмешательства и после отката T₃?

  1. Граф ожидания имеет рёбра T₁→T₂,T₂→T₃,T₃→T₁. Образовался цикл, и ни одна ожидающая блокировка не может быть выдана.
  2. Strict 2PL не позволяет просто освободить X посреди транзакции для продолжения той же операции. Нужен, например, откат одной жертвы.
  3. После отката T₃ её изменения отменяются и C освобождается. T₂ получает C, завершает работу и освобождает B; затем T₁ получает B и заканчивает.
  4. Успешно завершившиеся T₂ и T₁ имеют последовательный порядок T₂,T₁. Отменённая T₃ не включается в расписание зафиксированных изменений.

Ответ. Взаимная блокировка возможна; откат T₃ позволяет завершить T₂, затем T₁.

Проверка. Модель владения блокировками строит точный цикл из трёх рёбер и проверяет доступность C,B после последовательного освобождения ресурсов жертвы и T₂.

Где легко ошибиться. Сериализуемость не равна отсутствию deadlock. Не смешивайте граф ожидания невыполненных запросов с графом конфликтов уже совершённых операций.

Проверьте понимание

Какое утверждение верно для strict 2PL?

Вопросы к этой главе

Можно предотвратить этот цикл порядком A<B<C?

Да, если все транзакции получают нужные блокировки только в этом порядке. Запрос A при уже удерживаемой C нарушил бы установленное правило и не допускался бы.

Тайм-аут доказывает наличие цикла?

Нет. Он может сработать из-за долгой, но конечной работы владельца. Точный детектор deadlock ищет цикл ожидания; политика тайм-аута использует другое основание для отката.

Сверить определения и условия

Объяснение и задачи написаны для erudeet. Эти источники используются для проверки понятий и границ модели.

  • CMU15-445: Two-Phase Locking

    Прочитаны фазы получения/освобождения, блокировки до commit и возможность deadlock. Здесь strict означает 2PL с удержанием X до конца; более сильное удержание всех S/X оговорено отдельно. Собственный цикл ожидания имеет три транзакции.

Wait-die: метки транзакций запрещают цикл ожидания

Поиск цикла обнаруживает уже возникший deadlock. Wait-die устраняет саму возможность такого цикла: ждать разрешается только в одном направлении возраста транзакций. Разберём три конфликта блокировок и покажем, почему отмена не должна выдавать перезапущенной транзакции новую метку.

Перед началом: Граф ожидания блокировок; Отмена транзакции с освобождением её блокировок.

Возраст задаётся строгим порядком

Каждой транзакции назначается уникальная метка ts; меньшее значение означает более старую транзакцию. Если запрашиваемый ресурс уже удерживается несовместимым владельцем, более старый запросчик ждёт младшего. Более молодой запросчик, встретив старшего владельца, отменяется. Название wait-die относится к действию запросчика; оно не означает, что старший принудительно отменяет младшего владельца.

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

Почему разрешённый граф не содержит цикла

Ребро Ti→Tj означает, что Ti ждёт ресурс Tj. Wait-die разрешает такое ребро лишь при ts(Ti)<ts(Tj). Следовательно, вдоль любого пути ожидания метки строго растут. Если бы путь вернулся в исходную вершину, строгая цепочка потребовала бы ts(T0)<ts(T0), что невозможно. Это доказательство не использует ограничение длины цикла или конкретное число транзакций.

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

Отсутствие deadlock не является обещанием завершения

Пусть метки равны 10,20,30. Старейшая транзакция T10 удерживает A, T20 удерживает B, T30 удерживает C. Запросы T10 к B и T20 к C создают разрешённую цепочку 10→20→30. Попытка T30 получить A не добавляет ребро 30→10: запросчик отменяется. После освобождения C транзакция T20 может продолжить работу и затем освободить B.

Слово «может» здесь существенно. Требуются фактический откат, обслуживание ожидающих запросов и выполнение продолжившейся транзакции. Бесконечные внешние сбои или несправедливый планировщик не исчезают из-за временных меток. Сохранение возраста помогает избежать систематического омоложения при рестартах, однако само по себе не даёт конечной верхней границы времени ожидания.

Не дать трём ожиданиям замкнуться

Условие. T10, T20, T30 с одноимёнными метками удерживают A, B, C соответственно. По очереди поступают запросы T10 к B, T20 к C, T30 к A. Определите действие wait-die и последствия отмены.

  1. T10 старше владельца B, поэтому ждёт: разрешено ребро 10→20.
  2. T20 старше владельца C, поэтому ждёт: разрешено ребро 20→30.
  3. T30 моложе владельца A, поэтому отменяется. Ребро 30→10 не создаётся; C освобождается при откате.
  4. T20 после получения C может завершиться и освободить B для T10. При повторном запуске T30 сохраняет метку 30, а не получает новую.

Ответ. Два ожидания разрешены, третья транзакция отменяется. Цикл ожидания не возникает.

Проверка. Оба сохранённых ребра направлены от меньшей метки к большей. Любая попытка замкнуть их потребовала бы уменьшения метки и потому была бы отклонена правилом.

Где легко ошибиться. Не путайте wait-die с wound-wait: в wait-die молодой запросчик отменяет себя, а старший ждёт.

Проверьте понимание

Как действует wait-die, если запросчик с меткой 30 конфликтует с владельцем 10?

Вопросы к этой главе

Зачем метки должны быть различны?

Доказательство использует строгий порядок. Совпадения требуют заранее заданного уникального правила разрешения равенства, например дополнительного номера транзакции.

Достаточно ли только запретить цикл в графе ожидания для правильности данных?

Нет. Это свойство управления блокировками. Изоляция, длительность удержания блокировок и восстановление после отмены определяются остальным протоколом.

Сверить определения и условия

Объяснение и задачи написаны для erudeet. Эти источники используются для проверки понятий и границ модели.

  • Emory CS554: wait-die

    Правила возраста и сохранение метки при рестарте. Цепочка трёх ресурсов и доказательство через строгий порядок разобраны самостоятельно; условия завершения отделены от отсутствия цикла.

Сеть Петри с ёмкостями: достижимая маркировка вместо одного графа конфликтов

Граф конфликтов оценивает уже выписанное расписание. Сеть Петри задаёт сами возможные исполнения: переход расходует фишки и создаёт новые только при выполненных ресурсных ограничениях. При конечных ёмкостях можно построить весь граф состояний и получить проверяемый ответ о достижимости выбранной маркировки.

Перед началом: Поиск в ширину конечного графа; Векторный материальный баланс ресурса.

Ёмкость является частью разрешения перехода

Конечная сеть мест и переходов с заданными ёмкостями, обычными целочисленными фишками и одновременным срабатыванием одного перехода.

Маркировка m хранит число фишек каждого места. Переход имеет входной вектор a и выходной b. Он разрешён, если m≥a покоординатно и новая маркировка m′=m−a+b не превышает вектор ёмкостей c. Расход и добавление считаются одним атомарным шагом. Нельзя сначала потребовать свободное место для всего b, забыв, что этот же переход освободит a.

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

Из правил строится граф, которого ещё не было во входе

Начальная маркировка становится первой вершиной. Для каждого её разрешённого перехода вычисляем преемника; новую маркировку добавляем в очередь, повторную связываем с уже существующей вершиной. При p местах число возможных состояний не превосходит произведения(cᵢ+1). В инструменте p≤6 и cᵢ≤2, поэтому верхняя граница 729 известна до начала поиска.

Поиск в ширину хранит родителя и номер перехода. Когда цель впервые найдена, эти ссылки задают кратчайшую последовательность срабатываний. Для начальной цели последовательность пуста. Поиск всё равно может закончить весь достижимый граф: тогда можно отдельно перечислить тупики, то есть маркировки без разрешённых переходов. Цель вовсе не обязана быть тупиком.

Инвариант проверяет результат независимо от порядка обхода

Если строка w удовлетворяет w·(b−a)=0 для каждого перехода, величина w·m сохраняется во всех исполнениях. Отличающийся инвариант целевой маркировки сразу доказывает её недостижимость. Обратное неверно: совпадение одного баланса не гарантирует, что требуемый порядок переходов выполним. Полный граф проверяет именно разрешённость каждого промежуточного шага.

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

Две единицы ресурса и два клиента

Условие. Места(F,A,B) имеют ёмкости(2,1,1), начало(2,0,0), цель(0,1,1). Переходы захвата: (1,0,0)→(0,1,0) и(1,0,0)→(0,0,1); освобождения — обратные переходы. Найдите кратчайший путь и полный набор достижимых маркировок.

  1. Сумма F+A+B сохраняется и равна 2. С учётом ёмкостей возможны только(2,0,0),(1,1,0),(1,0,1),(0,1,1). Все четыре удовлетворяют этому балансу.
  2. Из начала можно захватить ресурс клиентом A либо B. Первый слой поиска: (1,1,0) и(1,0,1). Ни одна маркировка первого слоя не совпадает с целью.
  3. После захвата A переход захвата B разрешён: остаётся одна свободная единица и место B пусто. Получаем(0,1,1) за два шага. Симметричный порядок B,A даёт вторую кратчайшую последовательность.
  4. В каждой из четырёх маркировок ровно два разрешённых перехода; всего восемь ориентированных дуг. Из цели доступны два освобождения, поэтому она не тупик. Перебор закончился четырьмя вершинами, дополнительных состояний нет.

Ответ. Цель достижима за 2 срабатывания; достижимы ровно четыре перечисленные маркировки, тупиков нет.

Проверка. Независимый перебор всех 3·2·2=12 допустимых по ёмкости векторов оставляет ровно четыре с суммой 2. Для каждого предъявлен путь из начала. Цель(1,1,1) по ёмкостям допустима, но недостижима, поскольку её сумма равна 3.

Где легко ошибиться. Не выдавайте «цель не найдена» за ошибку формата. Если цель сама допустима по ёмкостям, отсутствие пути является содержательным отрицательным результатом полного конечного поиска.

Достижимость сети Петри с конечными ёмкостями

До6 мест, ёмкости0–2; маркировки от0 до соответствующей ёмкости. До8 переходов: строка входного вектора -> выходной. Дуги имеют веса0–2. Переполнение места запрещает переход. Полный поиск посещает не более3⁶=729 состояний; пустой список переходов допустим.

Данные для расчёта

Проверьте понимание

Для разобранных ёмкостей(2,1,1), начала(2,0,0) и цели(0,1,1) каков результат?

Вопросы к этой главе

Почему цикл в графе маркировок не доказывает тупик?

Цикл показывает возможность вернуться к состоянию. Тупик, напротив, не имеет исходящих разрешённых переходов. В примере есть циклы захвата и освобождения, но ни одной тупиковой маркировки.

Почему одного сохранённого количества недостаточно для положительного ответа?

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

Сверить определения и условия

Объяснение и задачи написаны для erudeet. Эти источники используются для проверки понятий и границ модели.

  • University of Freiburg — Petri Nets, §12.5 Place Capacities

    Правило разрешения перехода с конечными ёмкостями и ресурсные инварианты. Наш протокол двух клиентов, полный граф четырёх маркировок и отрицательная контрольная цель заданы отдельно.

Восстанавливаемость журнала не следует из конфликтной сериализуемости

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

Перед началом: Конфликтный граф расписания; Версия, commit и abort.

Порядок фиксации проверяется по источнику чтения

Одноверсионный журнал чтений, записей, commit и abort. Для чтений явно известна породившая версия; собственные чтения транзакции не создают межтранзакционной зависимости.

Запись w₁(x) создаёт версию, чтение r₂(x) может её использовать. Если T₂ фиксируется, восстанавливаемость требует более раннего commit T₁. Недостаточно, чтобы T₁ когда-нибудь завершилась: abort не подтверждает использованную версию. Начальная версия считается заранее зафиксированной и отдельного ожидания не требует.

В журнале w₁(x),r₂(x),c₂,a₁ граф конфликтов имеет единственное ребро T₁→T₂ и не содержит цикла. Но T₂ уже зафиксировала результат, опирающийся на отменённое изменение. Такой журнал невосстанавливаем. Значит конфликтная сериализуемость и корректный порядок commit отвечают на разные вопросы; ни одну проверку нельзя заменить другой.

Три вложенных ограничения имеют разные свидетели

Восстанавливаемый журнал может разрешать раннее чтение, пока читатель не фиксируется раньше автора. Более сильное требование отсутствия каскадных откатов запрещает само чтение чужой незавершённой версии. Строгий журнал дополнительно запрещает чужую перезапись объекта до завершения его последнего писателя. Поэтому строгость влечёт отсутствие каскадных чтений, а оно — восстанавливаемость.

Журнал w₁(x),r₂(x),c₁,c₂ восстанавливаем, но чтение сделано до c₁. Журнал w₁(x),w₂(x),c₁,c₂ вообще не содержит межтранзакционных чтений, однако грязная перезапись нарушает строгость. Наконец w₁(x),c₁,r₂(x),w₂(x),c₂ строгий. Это свойства уже записанного расписания; конкретный протокол блокировок является лишь одним способом обеспечить их заранее.

Каскад распространяется по использованным версиям

Построим граф Tᵢ→Tⱼ, если Tⱼ использовала ещё не подтверждённую версию Tᵢ. После abort Tᵢ надо отменить её незавершённых читателей, затем их читателей и так далее. Получается достижимое замыкание. Ребро конфликта из двух записей само по себе не доказывает чтение и не должно автоматически добавляться в этот граф причинных зависимостей.

Если среди зависимых уже есть committed-транзакция, обычный откат только живых транзакций не исправляет нарушенную гарантию. Поэтому порядок фиксации проверяется до подтверждения результата. У отмены грязных перезаписей есть собственные сложности журналирования: нельзя просто восстановить старый байт поверх чужого подтверждённого значения. Отсутствие каскадных чтений не делает любой способ undo безопасным.

Один abort отменяет две зависимые вычислительные ветви

Условие. До каких-либо commit выполнены w₁(x),r₂(x),w₂(y),r₃(y),w₄(z). Чтения берут непосредственно указанные новые версии. Затем T₁ откатывается. Какие ещё транзакции должны откатиться по зависимостям чтения?

  1. Чтение r₂(x) использовало версию T₁, поэтому есть ребро 1→2. Запись w₂(y) затем стала источником чтения r₃(y), что даёт ребро 2→3.
  2. T₄ только записала независимый z. Ребра от T₁,T₂,T₃ к ней нет: одной одновременности операций недостаточно для зависимости.
  3. Начинаем множество отмен с {1}. Первый шаг добавляет 2, второй — 3, после чего новых читателей нет. Минимальное замыкание равно {1,2,3}.
  4. T₂ и T₃ ещё не фиксировались, поэтому их можно отменить до подтверждения результатов. T₄ не обязана откатываться именно по этому каскаду; её прочие условия корректности проверялись бы отдельно.

Ответ. После T₁ отменяются T₂ и T₃. T₄ не входит в замыкание зависимостей чтения.

Проверка. Прямой журнал источников версий даёт рёбра (1,2),(2,3). Поиск достижимости от 1 и последовательное добавление читателей независимо возвращают одно множество {1,2,3}.

Где легко ошибиться. Не стройте каскадный откат по каждому конфликту. Для зависимости результата существенно, какую версию действительно прочитали.

Проверьте понимание

Кто входит в минимальное замыкание отмен после a₁ в разобранном журнале?

Вопросы к этой главе

Может ли восстанавливаемый журнал требовать каскадного отката?

Да. До фиксации автора его версию могут читать несколько незавершённых транзакций. Восстанавливаемость ограничивает их commit, а запрет раннего чтения был бы более сильным условием.

Всегда ли два чтения одного x зависят от одной записи?

Нет. Между ними могли появиться новые версии или завершиться откат. Поэтому связь read-from должна быть восстановлена по конкретному журналу, а не только по имени объекта.

Сверить определения и условия

Объяснение и задачи написаны для erudeet. Эти источники используются для проверки понятий и границ модели.

  • Database System Concepts: recoverability

    Прочитаны слайды15.22–15.24 об источниках чтения, commit и каскадных откатах. Журналы с четырьмя транзакциями, грязной перезаписью и вычисление замыкания составлены отдельно.

Источники и работа с материалом

Объяснение, примеры и вопросы написаны для erudeet. Факты и определения сверены по источникам ниже; это ссылки для самостоятельной проверки.

Продолжить разбираться