Объектно-ориентированная СУБД (прототип)

Транзакции

Согласованное управление – это важный аспект управления транзакциями в
СУБД. В обычных базах данных, транзакции являются независимыми
атомарными воздействиями, которые выполняются изолированно, в том числе
от результатов выполнения других транзакций. Однако, для повышения
производительности, для некоторых транзакций составляется расписание
выполнения. Механизм согласованного управления обеспечивает корректное
выполнение этого множества транзакций, в том числе продолжительных.

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

Сериализуемость состоит в том, что результат совместного выполнения
транзакций эквивалентен результату их некоторого последовательного
исполнения, называемого планом выполнения транзакций. Это обеспечивает
реальную независимость пользователей. Существует теорема Эсварана о
двухфазной блокировке: если все транзакции подчиняются протоколу
двухфазной блокировки, то для всех возможных существующих графиков
запуска (порядков выполнения транзакций) существует возможность
упорядочения. Эта тема хорошо освещена в [D] и [E].

В зависимости от организации протокола совместного выполнения транзакций
он является пессимистическим или оптимистическим.

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

Протокол согласованного управления ООСУБД обеспечивает:

Управление совместно выполняющимися продолжительными транзакциями

Усиливает корректность критерия другого, чем сериализуемость

Учитывает объектную ориентированность данных

Допускает обобщение операций (не только чтение и запись)

Определения и запись

Определение 1. Пусть значение объекта O определяется набором его
частей-значений, обозначаемых iv1, iv2, …, ivn. Это могут быть,
например, атрибуты агрегата, элементы списка и др. Обозначим операции
(методы) op1, op2, …, opn. Каждая операция opi имеет множество (возможно
пустое) параметров p1, p2, …, pr.

Каждая операция opi может состоять из более элементарных операций,
представленнных списком opi1,…,opis. Каждая из этих операций является
локальной или глобальной. Локальная операция работает только с
собственными данными объекта O, иначе операция является глобальной.
Глобальная операция состоит в посылке сообщения другому объекту и
получения от него результата.

Говорят, что операция opi на объекте O порождает операцию opj, на
объекте O’, если opj была вызвана глобальным шагом opi, пославшей
сообщение к объекту O’. Это отношение порождения одной операции другой
(отец-сын), может быть представлено отношением предок-потомок через
транзитивное замыкание.

Определение 2. Область действия операции opi на объекте O,
(Scope(opi(O)) ) состоит из следующих объектов:

Все экземпляры переменных объекта O.

Все параметры p1, p2, …, pr, связанные с операцией opi на O.

Все системные объекты

Если O — класс, то область действия операции opi на объекте O включает
в себя непосредственных наследников O (тоже классов) и классы,
являющиеся доменами для iv1, iv2, …, ivn. Дополнительно, все объекты
которые являются экземплярами класса O, также попадают в область
действия opi объекта O.

Иначе говоря, область действия операции opi на объекте O включает все
объекты, которыми операция может непосредственно манипулировать
(собственные данные O), либо объекты, к которым посылаются сообщения
одним из шагов этой операции.

Все воздействия любой операции (на объекте) попадают под одну из четырех
категорий: запрос, создание, модификация, удаление.

Иерархия наследования и отношение класс-экземпляр_класса приводят к
каскадному эффекту. Поэтому для каждой операции opi на объекте O
определяется множество запросов (query set: QS(opi(O)) ), множество
созданий (create set: CS(opi(O)) ), множество модификаций (modify set:
MS(opi(O)) ) и множество удалений (delete set: DS(opi(O)) ).

Определение 3. Множество запросов QS(opi(O)) определяется рекурсивно как
QS(opi(O)) = LocalQS(opi(O)) ( GlobalQS(opi(O)), где

LocalQS =

(, если нет собственных ivj из O “запрошенных” операцией opi.

{O}, иначе.

GlobalQS =

{Ogq | opi , посылает сообщение к Os для выполнения метода opj, где Os(
Scope(opi(O)), и Ogq(QS(opj(Os))}.

Аналогично определяются можества создания модификации и удаления
операции opi на объекте O.

Определение 4. Пусть можество замен (update set) определяется как
US(opi(O)) = (CS(opi(O)) ( MS(opi(O)) ( DS(opi(O))).

Определение 5. Говорят, что имеется конфликт двух операций opi на
объекте O и opj на объекте O’, если выполняется хотя бы одно из
следующих условий:

US(opi(O)) ( US(opj(O’)) ( (

QS(opi(O)) ( US(opj(O’)) ( (

US(opi(O)) ( QS(opj(O’)) ( (

Пользовательские транзакции можно рассматривать как методы или операции
специального объекта базы данных: DBIO (Database User-Interface Object)
— пользовательского представления базы данных. Таким образом,
транзакции выглядят как любой другой метод в системе.

Пусть для каждого объекта O в базе данных OpTypes(O) — множество типов
методов или операций, разрешенных для выполнения на объекте O.

Пусть OpTypes(O) = { OpType1(O), OpType2(O), …, OpTypep(O)) }

OpTypes(O) предоставляет механизм классификации операций op1, op2, …,
opn на объекте O. Каждой операции opi поставлен в соответствие тип
OpTypej(OpTypes(O).

Определение 6.

Пусть CG0 — спецификация k-уровневой группировки для множества
OpTypes(O). CG0 определяется так:

CG0(1) состоит только из одного множества — OpTypes.

CG0(k) состоит из множеств с одним элементом (singleton sets) , по
одному на каждый тип операции в множестве OpTypes.

Каждое CG0(i) уточняет CG0(i-1), т.е. для любого множества cgs(CG0(i),
найдется множество cgs'(CG0(i-1) такое, что cgs ( cgs’.

Определение 7. Уровень Level(opi(O),opj(O))=l, где CG0(l) содержит
opi(O) и opj(O) в одном множестве и для каждого m > l, opi(O) и opj(O)
не содержатся в одном множестве CG0(m).

Определение 8. Для каждой операции opi(O) спецификация точки разрыва
k-го уровня B(opi(O),k) определяется так:

B(opi(O),1) состоит только из одного множества — { opi1(O), opi2(O), …,
opik(O)}

B(opi(O),k) состоит из множеств с одним элементом, по одному для каждого
шага операции opi на объекте O.

Каждое B(opi(O),j) представляет собой уточнение B(opi(O),j-1).

Если bl = B(opi(O),j), opij(bl, opin(bl, и существует opim такая, что на
операции opi(O) подоперация opij предшествует opim, которая, в свою
очередь, предшествует opin, тогда opim(bl. (Т.е. если два шага операции
находятся в одном классе эквивалентностей, то любая промежуточная
операция находится в одном с ними классе эквивалентностей.)

Для увеличения производительности СУБД, некоторые операции могут
взаимодействовать друг с другом в базе данных. Некоторые из этих
операций могут выполняться на одном объекте. Совместное выполнение
многих операций (псевдопараллельность) может приводить к произвольному
чередованию операций (или их шагов). Порядок чередования называется
объектно-ориентированным расписанием. Так как “пользовательские
транзакции” являются только операциями на DBIO, ОО-расписание можно
определить на DBIO как пару (S, где Ti и Tj –
пользовательские транзакции, так что Ti следует за Tj и конфликтует с
ним.

Есть три вида списков зависимости:

Локальный список зависимости

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

Список унаследованных зависимостей

Каждый объект O также содержит список унаследованных зависимостей,
обозначаемый DSI(O). Этот список также вначале пуст. Когда операция
op(O) обращается к O как к результату сообщения от opi(Oi) из
вызываемого объекта., вызываемый объект также посылает свое множество
зависимостей DS(Oi), которое добавляется к DSI(O). Список унаследованных
зависимостей можно рассматривать как форму прямого размножения
зависимостей от вызывающей операции (объекта) к вызываемой операции
(объекту).

Список приобретенных зависимостей.

Список приобретенных зависимостей, обозначаемый DSR(O) наращивается,
когда операция opr(Or), вызванная как результат глобального шага
операции op(O) на O, закончила выполнение. Вместе с результататами
вызванной операции, вызванный объект также посылает свое множество
зависимостей DS(Or). Список приобретенных зависимостей можно
рассматривать как форму обратного распространения зависимостей от
вызванного объекта к вызывавшему объекту.

Множество зависимостей для O определяется как

DS(O) = DSL(O)( DSI(O)( DSR(O).

Граф зависимостей DG(O) каждого объекта O — это графическое
представление множества зависимостей DS(O). Узлы этого графа состоят из
пользовательских транзакций. Для каждого элемента зависимости , в
графе существует ребро Ti(Tj в DG.

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

Состояние пользовательских транзакций на объектах.

пользовательской транзакции в системе. Состояние пользовательской
транзакции (т.е. операции на DBIO) может принимать одно из следующих
значений:

Никогда не активировалась (Never Activated)

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

Завершена (Completed)

Пользовательская транзакция находится в состоянии Завершена на O, если
операция вызванная ей на O закончила выполнение всех своих шагов.

Находится в точке проверки (Chekpoint)

Пользовательская транзакция не произвела никаких действий с тех пор, как
оказалась в точке проверки.

Задержана для точки проверки (BlockedForCheckPoint)

Пользовательская транзакция ожидает выполнения условий, которые будут
удовлетворять переводу ее в Точку проверки.

Выполняется (Executing)

Пользовательская транзакция выполняется на O, если операция op(O),
вызванная этой транзакцией выполняется.

Пример изменения состояния транзакции при ее выполнении:

Действия Новое состояние транзакции на O

Никогда не активировалась

Объект O получил запрос на выполнение op(O) впервые для транзакции
Tr(op(O)) и op(O) начинает выполняться Выполняется

Операция транзакции достигла описанной для нее точки проверки, все
остальные активные операции на O “никогда не активировались” в точке
проверки Находится в точке проверки

Операция транзакции достигла описанной для нее точки проверки, но
активные операции не находятся в своих точках проверки Блокирована для
точки проверки

Tr(op(O)) закончила все свои шаги Завершена

Таким образом, если объект имеет точки проверки, описанные для своих
операций, то операции встречаются (рандеву) в точке проверки. Если
операции в точке проверки произведены успешно, то в будущем нет
необходимости любой операции откатываться (rollback) за точку проверки.

Определение 1. Пусть объект O состоит из экземпляров переменных

Протокол согласованного управления

Операция запрошена (requested)

Операция вызывает другую операцию

Вызванная операция возвращается

Операция завершена

Точка разрыва (breakpoint) достигнута

Точка проверки (checkpoint) достигнута

В точке проверки получено сообщение

Обработка запроса для получения операции

Пусть на объекте O в данный момент выполняется операция {opj1, opj2, …,
opjn}.

Пусть CurPoint(opj(O)) обозначает текущий шаг операции opj.

Запрос на операцию op на O получен (через сообщение) от opi(Oi)
(вызывающей операции). Сообщение также содержит информацию зависимости
(в виде множества зависимостей) из вызывающего объекта. Запрос для
операции op(O) обрабатывается следующим образом:

Шаг1

Проверяется: содержит ли DS(O)(DS(Oi) цикл с Tr(opi(Oi)).

Если да, то Abort_Processing

Иначе, следующий шаг.

Шаг2

Используется таблица конфликтов

(k 1(k(n, если ECоп(op(O), opjk(O)) = Нет, то расписать op(O) на
выполнение. Списки зависимостей не меняются. Состояние Tr(op(O))
становится «Выполняется». Если условие (1) не выполнено, то

(k 1(k(n условие (1) или CurPoint(opjk(O))(EBI(op(O), opjk(O)), тогда

(k 1(k(n : ECоп(op(O), opjk(O)) ( Нет; добавить

иначе расписать op(O) для выполнения и изменить состояние Tr(op(O)) в
«Выполняется». Если (2) не выполняется, то (3), иначе выход.

(k 1(k(n : условие (2) или ECоп(op(O), opjk(O)) = Неизвестно, то

(k 1(k(n : ECоп(op(O), opjk(O)) = Да; добавить

Блокировать выполнение op(O) до тех пор, пока каждая операция opjk(O),
для которой ECоп(op(O), opjk(O)) = Да достигнет шага такого, что
CurPoint(opjk(O))(EBI(op(O), opjk(O)). Тогда перейти к (2).

Вызов операции

Когда операция op(O) выполняет глобальный шаг, т.е. посылает сообщение
другому объекту, следующие шаги выполняются:

DS(O):=DSL(O)( DSI(O)( DSR(O)

Сообщение посылается получающему объекту вместе с параметрами сообщения
и DS

Вызванная операция возвращается

Пусть результат глобального шага операции op(O) – в сообщении,
вызывающем операцию opr(Or). Когда вызванная операция opr(Or) вернется,
список зависимостей DS(Or) также вернется (вместе с результатом
выполнения метода).

Тогда производятся следующие шаги:

К списку DSR(O) добавляется DS(Or)

Строится граф зависимостей и проверяется на наличие циклов, содержащих
транзакцию Tr(op(O)), если такой цикл есть, Abort_Processing

Когда операция завершается

Следующие шаги выполняются, когда op(O) заканчивает выполнение:

Строится DS(O). Можно не включать в него зависимости соответствий к
DSI(Oi). DS возвращается в Oi вместе с результатом операции op(O).

Когда достигнута точка останова

Группировка и описание точек разрыва позволяет прерывать порядок
операций. Это означает, что некоторые пункты зависимостей из локального
списка зависимостей могут быть удалены, когда операция достигает точки
разрыва. Когда операция op(O) достигает точки разрыва bk, производятся
следующие шаги:

Из определенной пользователем спецификации точки разрыва определяется
уровень точки разрыва l

Из группировки и спецификаций точек разрыва, пусть Opb = { Opk1(O),
Opk1(O), … ,Opkm(O)} будет множеством операций, которые могут прервать
op в bk.

Удалить каждую зависимость в DSL(O), которая влечет за собой Tr(op(O)) и
Tr(opkr(O)), где opkr(O)(Opb.

Когда точка проверки достигнута

Идея установки точек проверки используется для ограничения длины отката
(rollback), который необходим, когда операция обрывается (aborted). В
этом протоколе такие обрывы операций иногда необходимы, так как
происходит некорректное выполнение. Поскольку известной заранее
информации об объектах, к которым операции имеют доступ, недостаточно,
это ведет к некорректному прерыванию операций.

Когда точка проверки достигнута, будущие обрывы в этой или любой другой
операции не требуют отката за эту точку.

Когда операция op(O) достигает точки проверки ck, производятся следующие
шаги:

Строится DS(O). Пусть DepSet(Tr(op(O)),O)={Tj|

(j: Tj(DepSet(Tr(op(O)),O) если или Tj имеет состояние «Никогда не
активно» на O, или opk(O) (такая, что Trk(op(O))=Tj) есть в точке
проверки, идти к следующему шагу, иначе блокировать до удовлетворения
этого условия.

Состояние Tr(op(O)) изменяется в «Блокировано для точки проверки».

Сообщение точки проверки посылается каждому объекту Or, который получает
сообщение от глобального шага op(O) вызвать opr(Or). Изменяется
состояние Tr(op(O)) на «В точке проверки».

Объект получает сообщение точки проверки.

Когда объект O получает сообщение точки проверки для операции op(O) из
операции opi(Oi), производятся следующие шаги:

Удаление каждой зависимости от DS(O), которая связана с Tr(op(O))

Изменение состояния Tr(op(O)) в «Завершено»

Сообщение точки проверки посылается каждому объекту Or, который получает
сообщение от глобального шага op(O) вызвать opr(Or)

Abort_Processing

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

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

Abort_Processing вводится на особых объектах.

Цикл определения и обрыва

В идеале обрыв должен быть произведен сразу как тоько некорректность
выполняемой операции замечена. В протоколе множество зависимостей DS(O)
объекта O помогает этому. Наличие циклов в связанном графе зависимостей
DG(O), означает существование некорректно выполненяющихся операций.
Другими словами, ациклический граф зависимостей может получить цикл
только тогда, когда добавлено новое ребро, т.е. новая зависимость может
быть добавлена в DS одним из следующих способов: добавлением зависимости
в DSL(O), DSI(O) или DSR(O).

Рассмотрим две операции: opi(O) и opj(O) с Tr(opi(O))=Ti и
Tr(opj(O))=Tj. Пусть выполнение шага opi(O) (который конфлитует и
следует за шагом opj(O)) приводит к добавлению зависимости к
DS(O), которая дает цикл в DG(O). Это означает, что перед выполнением
этого шага, DG содержал путь от Tj к Ti. Добавление новой зависимости
привело к образованию цикла. (Цикл может включать другие транзакции, в
дополнение к Ti и Tj.) Поскольку существование этого цикла означает
некорректное прерывание выполнения операции, необходимо прервать не
менее одной транзакции и разорвать цикл. Если opj(O) еще выполняется на
O, можно прервать ее и, таким образом, зависимость не будет
добавлена.

Прерывание opj(O) приводит к прерыванию операций, которые могли быть
выполнены на других объектах после глобального шага opj(O).

Однако, если opj(O) уже завершена на O, необходимо отменить результат
opj(O) (в этом и всех других объектах, которые доступны глобальным шагам
opj(O)). Таким образом, сообщение об обрыве должно быть послано всем
этим объектам.

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

Получение запросов отказа (обрыва)

Когда объект O получает запрос отказа для особенной операции opj(O),
производятся следующие шаги:

Если opj(O) выполняется на O

Обрыв opj(O)

Отмена эффектов шагов opj(O)

Посылка сообщения обрыва всем объектам, которые получили сообщение от O
как результат глобального шага opj(O)

Если opj(O) завершила выполнение на O

Отмена эффектов шагов opj(O)

Посылка сообщения об обрыве всем объектам, которые получили сообщение от
O как результат глобального шага opj(O)

Послать запрос обрыва в вызывающий объект, т.е. объект, который содержит
операции, глобальные шаги которых вызвали opj(O)

Для каждой операции opi(O), которая конфликтует с opi(O) на O и следует
за ней

Послать запрос обрыва в O (себя) для обрыва opj(O)

– PAGE 10 –

PAGE \# “‘Стр: ‘#’

Возможно, здесь другое слово (согласованном, непротиворечивом) Было:
acceptable

PAGE \# “‘Стр: ‘#’

Каждый ли? Ведь есть объекты-значения

PAGE \# “‘Стр: ‘#’

Есть ли необходимость в графе зависимостей? Может, достаточно обойтись
списком зависимостей?

PAGE \# “‘Стр: ‘#’

Возможно, номер изменится

PAGE \# “‘Стр: ‘#’

Стоит ли оставлять это предложение?

PAGE \# “‘Стр: ‘#’

А что с объектами-значениями?

PAGE \# “‘Стр: ‘#’

Не слишком ли жадно до ресурсов?

Нашли опечатку? Выделите и нажмите CTRL+Enter