Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
Подписываем
- 10-
Возможно, здесь другое слово (согласованном, непротиворечивом) Было: acceptableКаждый ли? Ведь есть объекты-значенияЕсть ли необходимость в графе зависимостей? Может, достаточно обойтись списком зависимостей?Возможно, номер изменитсяСтоит ли оставлять это предложение?А что с объектами-значениями?Не слишком ли жадно до ресурсов?
Транзакции
Согласованное управление – это важный аспект управления транзакциями в СУБД. В обычных базах данных, транзакции являются независимыми атомарными воздействиями, которые выполняются изолированно, в том числе от результатов выполнения других транзакций. Однако, для повышения производительности, для некоторых транзакций составляется расписание выполнения. Механизм согласованного управления обеспечивает корректное выполнение этого множества транзакций, в том числе продолжительных.
В отличие от традиционных баз данных, исследования в области согласованного управления для объектно-ориентированных баз данных были ограничены. Это в значительной мере связано с уникальностью требований к объектно-ориентированным базам данных. Природа транзакций в таких приложениях, как 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)) ) состоит из следующих объектов:
Иначе говоря, область действия операции 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)), где
{Ogq | opi , посылает сообщение к Os для выполнения метода opj, где Os Scope(opi(O)), и OgqQS(opj(Os))}.
Аналогично определяются можества создания модификации и удаления операции opi на объекте O.
Определение 4. Пусть можество замен (update set) определяется как US(opi(O)) = (CS(opi(O)) MS(opi(O)) DS(opi(O))).
Определение 5. Говорят, что имеется конфликт двух операций opi на объекте O и 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 поставлен в соответствие тип OpTypejOpTypes(O).
Определение 6.
Пусть CG0 -- спецификация k-уровневой группировки для множества OpTypes(O). CG0 определяется так:
Определение 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) определяется так:
Для увеличения производительности СУБД, некоторые операции могут взаимодействовать друг с другом в базе данных. Некоторые из этих операций могут выполняться на одном объекте. Совместное выполнение многих операций (псевдопараллельность) может приводить к произвольному чередованию операций (или их шагов). Порядок чередования называется объектно-ориентированным расписанием. Так как "пользовательские транзакции" являются только операциями на DBIO, ОО-расписание можно определить на DBIO как пару (S,<расп), где S – множество всех шагов (как локальных, так и глобальных), а <расп – частичный порядок на множестве шагов в S. Глобальные шаги в S -- это результат обращения операций к другим объектам, и шаги основанные на результате этих обращений также включаются в расписание.
Пусть T – пользовательская транзакция вида T = {tOP1(DBIO), tOP2(DBIO), …, tOPn(DBIO)}.
Некоторые из вызываемых ей операций могут вызываться другой аналогичной операций на DBIO, т.е. на DBIO могут выполняться несколько независимых копий одной и той же операции. Пусть T’={t’(O’) | t’(O’) порождена операцией t(DBIO)T}.
Определение 9. Расписание Sch для T на DBIO является корректным объектно-ориентированным расписанием, если:
Это означает, что корректное объектно-ориентированное расписание гарантирует, что спецификации точек разрыва для операций будут соблюдаться должным образом, т.е. другие кооперативные (взаимодействующие) операции не могут видеть никаких промежуточных результатов, кроме описанных спецификацией точки разрыва.
Определение 10. Расписание Sch1 эквивалентно Sch2, если
Другими словами, если результат t” получается на основе результата t’, то в любых двух эквивалентных расписаниях операция t’ предшествует операции t”, порядок конфликтующих операций в эквивалентных расписаниях сохраняется. Если конфликта нет, то любой порядок следования операций является допустимым. Если при этом получаются разные результаты, то каждый из них, тем не менее, является правильным. Этот парадокс можно проиллюстрировать на следующем примере:
Положим, имеются две операции: увеличить сумму на счете вдвое и увеличить сумму на счете на 10%. Очевидно, что результат будет разным в зависимости от порядка следования операций. Но, поскольку операции независимы, в любом случае он считается правильным.
Если объекты, которые доступны различным транзакциям, заранее известны, задача механизма согласованного управления относительно проста. Априорная информация облегчает статичное определение конфликтующих операций; следовательно, стратегия управления чередованием операций может быть сформулирована. Однако, позднее связывание (late binding), характерная черта объектно-ориентированных систем, приводит к трудности предварительного определения объектов доступа. При отсутствии такого знания, одним из выходов является блокировка некоторых транзакций до тех пор, пока вид объектов доступа не станет известен. Однако, для продолжительных (long-duration) транзакций, такая блокировка может привести к слишком большому времени ожидания.
Протокол использует оптимистический подход, при котором априорные знания недоступны. Когда протокол использует оптимистичный подход, некорректное выполнение обнаруживается только когда все объекты доступа известны. При обнаружении некорректного чередования, для одной или более транзакций (операций) должен быть произведен обрыв (aborted) или откат (rolled back) к моменту перед некорректным выполнением. Это хорошо зарекомендовавший себя подход, но для продолжительных транзакций откат или обрыв приведет к значительной потери системных ресурсов, которые были использованы и времени, потраченного на бесполезные вычисления.
Одним из методов решения этой проблемы состоит в том, чтобы ограничить сумму откатов. Для этого используется идея точек проверки, ограничивающих глубину отката. Если происходит событие приводящее к обрыву или откату, эффект, произведенный действиями за точкой проверки должен быть отменен. Это минимизирует потери ресурсов и в то же время сокращает продолжительные ожидания.
Идея точки проверки используется для минимизации глубины отката в случае обрыва транзакций. Эти точки могут быть описаны пользователем. Точки проверки связаны с операциями на объектах и могут быть описаны как шаг операции. Нет необходимости иметь спецификацию точки проверки для каждого объекта в системе. Однако пользователь может описать точки проверки в некоторых операциях на некоторых объектах, так, что каждоя точка представляет логическую единицу работы. Идея установки точек проверки предоставляет базе данных возможность определять, находится ли она в стабильном состоянии. Точка проверки служит как механизмом синхронизации, так и заботой о связности базы данных. Любая пользовательская транзакция может иметь зависимость от результатов других транзакций. Таким образом, точка проверки в транзакции имеет значение только если все другие активные операции также согласны с тем, что состояние базы данных в этой точке является непротиворечивым состоянием (consistent state). При этом точка проверки действует как точка встречи, в которой все активные транзакции системы фиксируют (commit) свою (частично сделанную) до этой точки работу.
Приложение базы данных предполагает значительную известность относительно семантики операций в базе данных. Семантика знаний может быть использована для установки точек проверки в транзакциях в точках, которые соответствуют логическому завершению некоторой части работы. В традиционных базах данных с быстро выполняющимися транзакциями сама транзакция является логической единицей работы. Однако в крупных приложениях нельзя трактовать транзакцию целиком как логическую единицу работы. В этом и состоит полезность идеи точек проверки.
Протокол согласованного управления требует размещения некоторой информации в каждом объекте. В некоторых случаях достаточно хранить информацию только в классе объектов, а не в каждом объекте-экземпляре класса.
Каждый объект в системе хранит следующую информацию:
Эта информация получается из точек разрыва и группировки спецификаций для объекта и имеет форму, показанную в таблице:
|
Запрошенная Операция |
Выполняющиеся операции |
|||||
|
op1 |
op2 |
… |
opj |
… |
opn |
|
|
op1 |
||||||
|
op2 |
||||||
|
… |
||||||
|
opi |
EBI(i,j) |
|||||
|
… |
||||||
|
opn |
Ячейка (i,j), т.е. EBI(i,j) – множество точек разрыва opj(O) на которых opi(O) может чередоваться с ней. Статичная информация предоставляемая Таблицей чередований в точках разрыва комбинируется с информацией времени выполнения (run-time) на этапе выполнения операций, т.е. тем шагом каждой операции, который в данный момент выполняется.
Неизвестно является следствием наличия позднего связывания, характерной черты объектно-ориентированных систем. Проверка наличия конфликта производится в соответствии с определением 5.
Список зависимости состоит из нуля или более элементов зависимости. Каждый элемент зависимости имеет вид <Ti,Tj> где Ti и Tj – пользовательские транзакции, так что Ti следует за Tj и конфликтует с ним.
Есть три вида списков зависимости:
Множество зависимостей для O определяется как
DS(O) = DSL(O) DSI(O) DSR(O).
Граф зависимостей DG(O) каждого объекта O -- это графическое представление множества зависимостей DS(O). Узлы этого графа состоят из пользовательских транзакций. Для каждого элемента зависимости <Ti,Tj>, в графе существует ребро TiTj в DG.
Транзакциям доступны промежуточные результаты других транзакций, которые доступны в точках разрыва и сгрупированных спецификациях. В традиционных базах данных элементы зависимостей никогда не удаляются из списка зависимостей. Некоторые элементы зависимостей могут быть удалены при достижении операциями точек разрыва. Наличие циклов в графе означает некорректное выполнение.
Состояние пользовательских транзакций на объектах.
Каждый объект O в системе хранит состояние каждой пользовательской транзакции в системе. Состояние пользовательской транзакции (т.е. операции на DBIO) может принимать одно из следующих значений:
Пример изменения состояния транзакции при ее выполнении:
|
Действия |
Новое состояние транзакции на O |
|
Никогда не активировалась |
|
|
Объект O получил запрос на выполнение op(O) впервые для транзакции Tr(op(O)) и op(O) начинает выполняться |
Выполняется |
|
Операция транзакции достигла описанной для нее точки проверки, все остальные активные операции на O "никогда не активировались" в точке проверки |
Находится в точке проверки |
|
Операция транзакции достигла описанной для нее точки проверки, но активные операции не находятся в своих точках проверки |
Блокирована для точки проверки |
|
Tr(op(O)) закончила все свои шаги |
Завершена |
Таким образом, если объект имеет точки проверки, описанные для своих операций, то операции встречаются (рандеву) в точке проверки. Если операции в точке проверки произведены успешно, то в будущем нет необходимости любой операции откатываться (rollback) за точку проверки.
Определение 1. Пусть объект O состоит из экземпляров переменных
Пусть на объекте O в данный момент выполняется операция {opj1, opj2, …, opjn}.
Пусть CurPoint(opj(O)) обозначает текущий шаг операции opj.
Запрос на операцию op на O получен (через сообщение) от opi(Oi) (вызывающей операции). Сообщение также содержит информацию зависимости (в виде множества зависимостей) из вызывающего объекта. Запрос для операции op(O) обрабатывается следующим образом:
Проверяется: содержит ли DS(O)DS(Oi) цикл с Tr(opi(Oi)).
Если да, то Abort_Processing
Иначе, следующий шаг.
Используется таблица конфликтов
Когда операция op(O) выполняет глобальный шаг, т.е. посылает сообщение другому объекту, следующие шаги выполняются:
Пусть результат глобального шага операции op(O) – в сообщении, вызывающем операцию opr(Or). Когда вызванная операция opr(Or) вернется, список зависимостей DS(Or) также вернется (вместе с результатом выполнения метода).
Тогда производятся следующие шаги:
Протокол согласованного управления является оптимистическим. В отсутствие априорной информации о связя, протокол берет оптимистический взгляд на то, что там может не быть никаких некорректных поведений.
Определение некорректного поведения делается после выполнения, когда все связи известны. Если некорректное выполнение операций (и, следовательно, пользовательских транзакций) замечено, необходимо инициировать корректирующие меры. Можно исправить некорректное выполнение обрывом логически ошибочных операций и перевыполнением их.
Abort_Processing вводится на особых объектах.
Рассмотрим две операции: opi(O) и opj(O) с Tr(opi(O))=Ti и Tr(opj(O))=Tj. Пусть выполнение шага opi(O) (который конфлитует и следует за шагом opj(O)) приводит к добавлению зависимости <Ti, Tj> к DS(O), которая дает цикл в DG(O). Это означает, что перед выполнением этого шага, DG содержал путь от Tj к Ti. Добавление новой зависимости привело к образованию цикла. (Цикл может включать другие транзакции, в дополнение к Ti и Tj.) Поскольку существование этого цикла означает некорректное прерывание выполнения операции, необходимо прервать не менее одной транзакции и разорвать цикл. Если opj(O) еще выполняется на O, можно прервать ее и, таким образом, зависимость <Ti, Tj> не будет добавлена.
Прерывание opj(O) приводит к прерыванию операций, которые могли быть выполнены на других объектах после глобального шага opj(O).
Однако, если opj(O) уже завершена на O, необходимо отменить результат opj(O) (в этом и всех других объектах, которые доступны глобальным шагам opj(O)). Таким образом, сообщение об обрыве должно быть послано всем этим объектам.
Объектам-получателям необъодимо откатить эффекты оборванных операций и все другие операции, зависящие от них.
Когда объект O получает запрос отказа для особенной операции opj(O), производятся следующие шаги:
Если opj(O) выполняется на O
Если opj(O) завершила выполнение на O
Для каждой операции opi(O), которая конфликтует с opi(O) на O и следует за ней