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

объектами класса D. Эта проблема рассматривается в работе [10], в которой авторы вводят следующие ограничения целостности структуры объектов:

1. В БД не могут существовать отдельные собственные части подклассов

2. Каждой части сложного объекта должна соответствовать только одна собственная часть.

В качестве решения они предлагают использование ссылок на классы и каждую собственную часть класса хранить отдельно.

В дипломной работе предлагается вместо хранения ссылок на классы установить для каждого поля свой идентификатор. При наследовании поле сохраняет свой иден­ти­фикатор. Таким образом, переименование полей не нарушает связь наследо­вания. Пере­именование может быть автоматическим, например, из-за конфликтов имен полей при множественном наследовании. Аналогично поступает оператор SQL Select, когда в ка­честве результата запроса ему нужно вернуть несколько столбцов, имеющих одина­ко­вые имена.

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

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

2.5 Триггеры. Ограничение доступа

В множество поведений любого объекта можно включить два списка с предопределенными именами «PRE_TRIGGERS» и «POST_TRIGGERS». Список PRE_TRIGGERS содержит объекты, обрабатывающие входящее сообщение. Как правило, это объекты-условия. Такой подход называется фильтрацией [20]. Список POST_TRIGGERS содержит объекты, которые проверяют результат воздействия и могут произвести откат. POST_TRIGGERS вызываются по окончании действия транзакции при выполнении операции удаления транзакционных зависимостей.

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

Список PRE_TRIGGERS позволяет организовать ограничение доступа, фильтруя сообщения, посланные объектом, ктороый не имеет полномочий для выполнения коман­ды, содержащейся в сообщении.

Список POST_TRIGGERS позволяет исключить часть данных из результата выполненной объектом операции, создав тем самым локальное пользовательское представление.

Впрочем, тема безопасности заслуживает отдельного рассмотрения. Как, например, в [9] и [18].

2.6 Действие (knowhow)

Действие представляет собой объект типа “строка”, хранящий текст ДССП-процедуры. Ссылка на действие может хранится в поле OBJKH объекта, через который и происходит вызов действия. Алгоритм выбора выполняемого действия рассматривается ниже. В интерфейсах объектов указаны идентификаторы объектов, которые в поле OBJKH хранят идентификатор действия. Значения этих объектов являются именем действия. Наиболее удобно использовать для этой цели строковые объекты. Использова­ние поля OBJKH позволяет выполнять одно и то же действие для различных методов различных объектов.

При вызове действия с идентификатором OIDKH делается вызов слова с именем kh$. Например, для объекта с OIDKH=0x00000DFC это будет KH$00000DFC. Если возникает ситуация EXERR, значит слово в словаре отсутствует и подлежит компиляции. Для компиляции текст действия дополняется префиксом “: KH$ ” и суффиксом “ ;”, после чего компилируется командой TEXEC и выполняется. Словарь действий называется $KH_VOC.

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

2.7 Объекты-поведения

В отсутствии классов, хранить методы в каждом объекте было бы слишком накладно. Вынесение правил поведения в отдельный объект позволяет уменьшить затраты на хранение объектов-данных. Математическая модель ООБД в [17], также разделяет дан­ные и поведения, что дополнительно дает возможность переиспользовать поведение дру­гого объекта.

Объект-поведение представляет собой множество объектов-методов, которое и назы­ва­ется интерфейсом объекта.

При посылке на вход произвольного объекта OID₂ сообщения OID₁ (которое тоже является объектом), сначала проверяется, содержится ли OID₁ в интерфейсе объекта OID₂ (проверка идентичности). Если да, то выполняется действие объекта OID₁, иначе сравниваются значения OID₁ и объектов интерфейса (проверка эквивалентности). Если соответствие найдено, выполняется действие, указанное в найденном в интерфейсе объекте.

2.8 Принципы взаимодействия объектов

Есть два основных способа управления объектами:

• Посылка сообщений

• Алгебра объектов

• 
  

Определения операций Select и Pickup алгебры объектов можно найти в [17]. Здесь оно не рассматривается по той причине, что является надстройкой над управлением посылкой сообщений и описывается через механизм посылки сообщений. То есть операции алгебры объектов могут быть заданы через операции посылки сообщений, без исправления структуры СУБД. Полная алгебра объектов является замкнутой и состоит из следующих операций: Select s, Pickup d, Apply r, Expression Apply l, Project p, Combine c, Union И, Interselect З, Subtract -, Collapse v, Assimilate a. Объектная алгебра более выразительна, чем реляционная, поскольку поддерживает полиморфность. Оператор Select, например, может работать с любыми видами операндов, а не только с множествами.

Согласно [17], любое сообщение в системе является объектом. Любой объект может иметь связанное с ним действие (knowhow), или не иметь его.

Алгоритм определения метода для выполнения

При посылке объекта проверяется, находится ли идентификатор объекта-сооб­ще­ния в интерфейсе объекта-получателя. Если да, то выполняется knowhow, связанное с этим идентификатором. Если нет – проверяется, совпадает ли значение объекта-сооб­щения со значением какого-либо метода из интерфейса объекта-получателя. Если да, то выполняется связанное с этим методом действие. Иначе возвращается объект fail.

Параметры методов

Набор_параметров (Blackboard) представляет собой множество меток, аргумент­ных пар { (L₁, arg₁), … , (L_n, arg_n) }. L_i A, arg_i O для 1 i  n и i, j  1,…,n : i  j  L_i  L_i.

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

Синтаксис посылки сообщения

Воздействие(Набор_параметров) ~> Получатель. Объект, называемый Воздействие (Invoker), является сообщением (message) и посылается к другому объекту, названному Получателем (Reciver), используя Набор_параметров, предоставляющий необходимые аргументы. Если параметры в Наборе_параметров отсутствуют, то можно записать короче: Воздействие ~> Получатель. Посланное сообщение всегда возвращает объект, называемый Результат (Result).

Посылка простого сообщения

Пусть B – Набор_параметров и m и r – два объекта в O.

Примитивные взаимодействия

(1) m(B) ~> fail є fail; fail(B) ~> r є fail;

(2) m(B) ~> null є null; null(B) ~> r є null;

(когда m№ fail)

(3) m(B) ~> same є same; same(B) ~> r є r;

(когда m№ fail и m№ null)

При совпадении идентификатора

(4) Если существует метод x из r такой, что x є m и sig(x) = (A₁,c₁) ґ …ґ (A_n,c_n)® c_r и {(A₁,a₁) ґ …ґ (A_n,a_n)} НB и FID каждого поля с_i присутствует в a_i (в терминах ОО-програм­мирования: c_i является предком по значению для a_i), тогда

m(B) ~> r є r.kh(x)(A₁ : a₁, … , A_n : a_n )

иначе проверяется совпадение значения.

При совпадении значения

(5) Если существует метод x в r или его объектах-учителях (объектов, от которых наследуется поведение) такой, что x » m и sig(x) = (A₁,c₁) ґ …ґ (A_n,c_n)® c_r и {(A₁,a₁) ґ …ґ
ґ (A_n,a_n)}НB и FID каждого поля с_i присутствует в a_i, тогда

m(B) ~> r є r.kh(x)(A₁ : a₁, … , A_n : a_n )

иначе

(6) Если r является атомарным, то m(B) ~> r є fail.

Иначе m(B) ~> r является комплексным сообщением (complex message sending), обладает сложной структурой.

Комплексные сообщения

Если Воздействие является объектом-агрегатом, то

s(B) ~> o є null, если s=[ ]

s(B) ~> o є [A₁ : s₁(B) ~> o₁, …, A_n : s_n(B) ~> o_n], если s=[A₁ : s₁, …, A_n : s_n]

где o_j » o, o_{j не}є o) и orf(o_i) З orf(o) = Ж для j = 1,..,n и для любого i, j О [1,..,n], если i № j тогда o_{j не}є o и orf(o_i) З orf(o_j) = Ж (т.е. o₁,…,o_n являются глубокими копиями объекта-получателя o).

Если Воздействие является объектом-условием, то

s(B) ~> o є s.then(B) ~> o, если s.if(B) П {False, fail}

s(B) ~> o є s.else(B) ~> o, иначе.

Где s.if, s.then, s.else обозначение if-части, then-части и else-части s соответственно.

Если Воздействие является объектом-множеством, то

s(B) ~> o є null, если s={ }

s(B) ~> o є s₁(B) ~> o, если s={s₁}

s(B) ~> o є s’(B) ~> o, s’= s – {x} после x(B) ~> o

где x – произвольно выбранный элемент из множества s.

Если Воздействие является объектом-списком, то

s(B) ~> o є null, если s=( )

s(B) ~> o є s_n(B) ~>(… ~>( s₂(B) ~>( s₁(B) ~> o))…) где s = (s₁, s₂, …, s_n)

Семантика дробящейся посылки

Пусть B – Набор_параметров и пусть s, oОO. Тогда оператор дробящейся посылки, обозначаемый ~¹> определяется следующим образом:

Таблица 1: Семантика дробящейся посылки

Условие	S(B) ~1> o є
s(B) ~> o неє fail	s(B) ~> o
AGG(o) & o = [A1 : o1, …, An : on]	[A1 : s(B) ~> o1, …, An : s(B) ~> on]
BIO(o) & o.if неє null	s(B) ~> o.then
BIO(o) & o.if є null	s(B) ~> o.else
SET(o) & o = {o1,…,on}	{s(B) ~> o1, …, s(B) ~> on}
SEQ(o) & o = (o1,…,on)	(s(B) ~> o1, …, s(B) ~> on)
Иначе	Fail

2.9 Транзакции и механизм согласованного управления

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

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

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

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

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

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

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

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

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

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

Подробное описание и теоретическое обоснование протокола согласованного управления для ООБД содержится в [19].

3. Разработка структуры СУ

3.1 Положение дел в области интероперабельности систем

Рост мощности программных приложений привел к выделению нового архитектурного слоя – информационной архитектуры систем, определяющей способность совместного исполь­зования, совместной деятельности (в дальнейшем будет использоваться термин "интероперабельность") компонентов (информационных ресурсов) для решения задач [21]. Этот слой расположен обычно над сетевой архитектурой, являющейся необходимой предпосылкой такой совместной деятельности компонентов, обеспечивающей их взаимосвязь.

Деятельность по созданию технологии интероперабельных систем охватывает весь мир. Наиболее существенный вклад в принимаемые идеологические, архитектурные и технологические решения интероперабельных систем вносит Object Management Group (OMG) (omg) - крупнейший в мире консорциум разработки программого обеспечения, включающий свыше 600 членов - компаний - производителей програм­мн­ого продукта, разработчиков прикладных систем и конечных пользователей. Целью OMG является создание согласованной информационной архитектуры, опирающейся на тео­рию и практику объектных технологий и общедоступные для интероперабельности спецификации интерфейсов информационных ресурсов. Эта архитектура должна обес­печивать повторное использование компонентов, их интероперабельность и мобиль­ность, опираясь на коммерческие продукты.

Другие организации, которые работают в кооперации с OMG, например, с целью доведения результатов OMG до официальных стандартов в различных аспектах, вклю­чают: ANSI, ISO, CCITT, ANSA, X/Open Company, Object Database Management Group (ODMG).

Развитие возможностей информационных систем и Internet и желание обеспечить их взаимодействие между собой, привело к необходимости разработки единого прото­кола взаимодействия. Для этого была создана OMG, которая и занялась этим вопросом. В результате была разработана эталонная модель, которая определяет концептуальную схему для поддержки технологии, удовлетворяющей техническим требованиям OMG. Она идентифицирует и характеризует компоненты, интерфейсы и протоколы, состав­ляющие Архитектуру Управления Объектами OMG (Object Management Architecture (OMA)), не определяя, впрочем, их детально.

Согласованная с OMA прикладная система состоит из совокупности классов и экземпляров, взаимодействующих при помощи Брокера Объектных Заявок (Object Request Broker (ORB)). Объектные Службы (Object Services) представляют собой коллек­цию служб, снабженных объектными интерфейсами и обеспечивающих поддержку базо­вых функций объектов. Общие Средства (Common Facilities) образуют набор классов и объектов, поддерживающих полезные во многих прикладных системах функции. При­кладные объекты представляют прикладные системы конечных пользователей и обеспе­чивают функции, уникальные для данной прикладной системы.

CORBA (Common Object Request Broker Architecture) определяет среду для различных реализаций ORB (Object Request Broker), поддерживающих общие сервисы и интерфейсы. Это обеспечивает переносимость клиентов и реализаций объектов между различными ORB.

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

Объектные Службы:

• Служба Уведомления Объектов о Событии (Event Notification Service).

• Служба Жизненного Цикла Объектов (Object Lifecycle Service).

• Служба Именования Объектов (Name Service).

• Служба Долговременного Хранения Объектов (Persistent Object Service).

• Служба Управления Конкурентым Доступом (Concurrency Control Service).

• Служба Внешнего Представления Объектов (Externalization Service).

• Служба Объектных Связей (Relationships Service).

• Служба Транзакций (Transaction Service).

• Служба Изменения Объектов (Change Management Service).

• Служба Лицензирования (Licensing Service)/

• Служба Объектных Свойств (Properties Service).

• Служба Объектных Запросов (Object Query Service).

• Служба Безопасности Объектов (Object Security Service).

• Служба Объектного Времени (Time Service).

Общие Средства заполняют концептуальное пространство между ORB и объект­ными службами с одной стороны, и прикладными объектами с другой. Таким образом, ORB обеспечивает базовую инфраструктуру, Объектные Службы – фундаментальные объектные интерфейсы, а задача Общих Средств – поддержка интерфейсов сервисов высокого уровня. Общие Средства подразделяются на две категории: "горизонтальные" и "вертикальные" наборы средств. "Горизонтальный" набор средств определяет операции, используемые во многих системах, и не зависящие от конкретных прикладных систем. "Вертикальный" набор средств представляет технологию поддержки конкретной при­кладной системы (вертикального сегмента рынка), такого, как здравоохранение, произ­водство, управление финансовой деятельностью, САПР и т.д.

• Средства поддержки пользовательского интерфейса (User Interface Common Facilities)

• Средства управления информацией (Information Management Common Facilities)

• Средства управления системой (System Management Common Facilities)

• Средства управления задачами (Task Management Common Facilities)

• Вертикальные общие средства (Vertical Common Facilities)

• Вертикальные общие средства предназначены для использования в качестве стандартных для обеспечения интероперабельности в специфических прикладных областях.

• Поддержка интероперабельности брокеров в стандарте CORBA 2.0

О роли СУООБД в архитектуре OMG можно прочесть в [13].

На основе анализа вышеизложенного, были выбраны в качестве основания следующие базовые службы СУООБД:

• Служба Долговременного Хранения Объектов – управление хранением объектов

• Служба Управления Конкурентным Доступом и Служба Транзакция – объединены вместе протоколом согласованного управления.

• Служба Изменения Объектов – управление журнализацией изменений

3.2 Менеджер памяти

Менеджер памяти является ключевым модулем системы.

Его наличие позволяет

• Абстрагироваться от особенностей обращения к различным видам памяти.

• Создавать сколь угодно вложенные друг в друга структуры данных.

• Иметь единый интерфейс на каждом уровне вложенности.

• Организовать кэширование объектов

В состав менеджера памяти входит 3 системы управления:

1. Система управления виртуальной памятью

2. Система управления каналами

3. Система управления кэшированием объектов

3.3 Виртуальная память и каналы

Виртуальная память представляет собой непрерывную для пользователя, с ней работающего, область памяти, которая может быть вложена в другую виртуальную память. Виртуальная память состоит из сегментов, связанных между собой в дву­направленную цепь. Каждому сегменту известно его положение относительно нижнего логического уровня. Работа с виртуальной памятью происходит через канал, выделенный для нее. Канал – это набор характеристик описывающих: где расположена виртуальная память, и в каком ее месте мы находимся. Количество каналов ограничено, поэтому канал выделяется той виртуальной памяти, которая нужна в данный момент. Система имеет набор каналов, которые могут иметь ссылку на виртуальную память, либо быть незанятыми. Первые 5 каналов – это базовые каналы, отображенные на физические носители (оперативная память, файл). Вторые 5 каналов – каналы виртуальной памяти, хранящие каталоги объектов. Остальные каналы предназначены для работы с объ­ектами. Все каналы основываются на каких-либо других каналах, образуя, в общем случае, 5 независимых деревьев. Корень – один из базовых каналов (0..4). Одна и та же виртуальная память не может быть загружена в два канала. При переходе от верхнего канала к нижнему выполняется трансляция адреса.

Рис 3: Связь каналов с хранилищами объектов

Таблица 2: Параметры канала

Параметр канала	Семантика
NCHAN	Номер текущего канала
LOWCH	Нижний канал; в него вложен этот канал
CHGCTX	Признак изменения данных заголовка фрагмента
TEKADR	Текущая позиция для чтения/записи
SYNCADDR	Адрес начала заголовка текущего сегмента в нижнем канале
TEKADR0	Позиция, соответствующая началу данных фрагмента
PREDADDR	Адрес заголовка предыдущего фрагмента (–1, если его нет)
NEXTADDR	Адрес заголовка следующего фрагмента (–1, если его нет)
BUSYLEN	Занятая длина
LEN	Выделенная длина

Таблица 3: Операции доступа к данным виртуальной памяти

Операция	Семантика (все операции работают с текущим каналом)
IBS	Чтение байта из канала
OBS	Запись байта в канал
GOTO	Переход по адресу в канале
@GOTO	Переход по смещению в канале
UPSIZE	Выделить доп. память в конце канала и встать на ее начало
DEFRAG	Сделать виртуальную память непрерывной на уровне нижнего канала (т.е. однофрагментной)

Начало виртуальной памяти соответствует нулевому значению TEKADR. Доступ осуществляется через операции позиционирования (GOTO и @GOTO), чтения байта (IBS) и записи байта (OBS). Остальные функции, реализуются через них (например, чтение длинного слова). К памяти может быть применена функция UPSIZE с аргументом, содер­жащим необходимое количество байт для выделения. Память может гаранти­ро­ванно вы­деляться до заполнения всей выделенной длины. При исчерпании выделенной длины, делается запрос к нижестоящему уровню о выделении дополнительной памяти. Если та­кой запрос применяется к каналу ниже 5-го, соответствующего дисковому файлу, файл увеличивается в размере, если его выделен­ная длина исчерпана. Если увеличение раз­мера файла невозможно из-за нехватки дискового пространства, то, в случае невоз­можности выделения памяти за счет упаковки, возбуждается ситуация NOMEMORY. При попытке доступа за пределы определенной вирту­альной памяти (например, чтение после расположения данных), возни­кает ситуация OUTDATA.

3.4 Система управления кэшированием объектов

Самостоятельное кэширование данных – неотъемлемая черта любой СУБД. Кэш состоит из двух частей: очереди кэшируемых объектов и памяти для кэшируемых объектов. Память для кэшируемых объектов – это оперативная память, в которую объект загружается. В этой памяти могут располагаться только те объекты, идентификаторы которых находятся в очереди кэшируемых объектов. Удаляемый из очереди объект выгружается в дисковую память. В данной дипломной работе все создаваемые объекты являются стабильными (Persistent), т.е. они обязательно сохраняются на диске и могут быть использованы после открытия базы данных для использования.

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

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

Наиболее популярны следующие пять алгоритмов замещения:

1. Случайное замещение (СЗ): с равной вероятностью может быть замещен любой объект,

2. Раньше пришел – раньше ушел (РПРУ, или FIFO): замещается объект дольше всех находившийся в оперативной памяти,

3. Замещение наиболее давно использовавшегося объекта (НДИ),

4. Алгоритм рабочего комплекта (РК): хранятся в памяти только те объекты, к которым было обращение в течении времени t, назад от текущего момента,

5. Лестничный алгоритм (ЛЕСТН): в списке объектов при обращении к объекту он ме­ня­ется местами с объектом, находящемся ближе к голове списка. При обращении к от­сутствующему в ОП объекту объект, находящийся в последней позиции вытесняет­ся.

Для алгоритма замещения желательно, чтобы он обладал двумя отчасти противоречивыми свойствами: с одной стороны, он должен сохранять в ОП объекты к которым обращения происходят наиболее часто, с другой – быстро обновлять содер­жимое ОП при смене множества рабочих объектов.

Например, алгоритм РПРУ эффективен только в отношении быстрого обновления ОП, он не выделяет в списке объектов объекты, обращения к которым происходят чаще, чем к остальным. Алгоритм НДИ также позволяет быстро обновлять содержимое ОП. Однако последовательность одиночных обращений достаточной длины к объектам, находящимся во ВП, вытеснит из ОП все объекты, к которым, в среднем, обращения происходят чаще всего.

В [1] описывается класс многоуровневых алгоритмов замещения c, которые поз­воляют решить эту проблему. Они зависят от конечного числа параметров и при адап­тивном подборе этих параметров соединяют свойство быстрого обновления части ОП со свойством сохранения в ОП тех объектов, которые наиболее часто запра­ши­ва­ются.

В дипломной работе решено использовать алгоритм замещения из класса c, при следующих параметрах: лимит времени нахождения объекта в ОП отсутствует, размеры подсписков на всех уровнях одинаковы, параметр l=1 (это соответствует алгоритму замещения НДИ для объектов всех подсписков; если i – положение объекта в подсписке, и i Ј l, то при обращении к нему применяется алгоритм РПРУ, иначе НДИ).

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

Для определения подмножества объектов кэша, подлежащих вытеснению, можно применить алгоритм решения задачи о рюкзаке. Если бы все объекты имели одинаковую длину, без этого можно было бы обойтись. Хотя алгоритм решения задачи о рюкзаке NP-сложен, решение можно компактно записать в виде рекурсивного алгоритма, нахо­дя­ще­го решение за счет применения принципа динамического программирования Беллмана. Такой способ наиболее эффективен, когда размер кэша составляет 32 объекта, посколь­ку множество выбранных объектов можно представить битовыми полями в длинном слове. При большем размере кэша возрастают потери памяти и быстродействия, и во­зникает вопрос о месте расположения данных промежуточных вызовов. Рекурсивный вызов в среде ДССП требует малых затрат ресурсов, а время расчета окупается за счет времени обмена с внешней памятью, работа с которой много медленнее, чем с оператив­ной.

3.5 Система управления журнализацией и восстановлением

Журнализация предназначена во-первых, для обеспечения возможности отката некорректных действий транзакций, и, во-вторых, для восстановления базы данных после аппаратного сбоя. В ООБД журнализацию можно проводить на трех уровнях: инфологическом, даталогическом и физическом. На инфологическом уровне журнал фиксирует сообщения, циркулирующие в системе. На даталогическом уровне фик­си­руется какие примитивы были вызваны на выполнение сообщениями. На физи­че­ском уровне фиксируются низкоуровневые операции: по какому адресу в какой вирту­альной памяти производилась запись, как изменились границы виртуальной памяти.

Обычные БД хранят мгновенный снимок модели предметной области. Любое изменение в момент времени t некоторого объекта приводит к недоступности состояния этого объекта в предыдущий момент времени. Интересно, что при этом в большинстве развитых СУБД предыдущее состояние объекта сохраняется в журнале изменений, но возможность доступа к этим данным для пользователей закрыта.

Для журнализации избран подход, примененный в СУБД Postgres, разработанной в университете г.Беркли, Калифорния под руководством М.Стоунбрейкера, как наиболее простой в реализации и предоставляющий полезные возможности, недоступные в базах данных с обычным типом журнализации (см. [23]). В этой системе, во-первых, не ведется обычная журнализация изменений базы данных, и мгновенно обеспечивается корректное состояние базы данных после перевызова системы с утратой состояния оперативной памяти. Во-вторых, система управления памятью поддерживает истори­ческие данные. Запросы могут содержать временные характеристики интересующих объектов. Реализационно эти два аспекта связаны.

СУБД, имеющие такой вид журнализации, называются темпоральными СУБД. Основной тезис темпоральных систем состоит в том, что для любого объекта данных, созданного в момент времени t1 и уничтоженного в момент времени t2, в БД сохраняются (и доступны пользователям) все его состояния во временном интервале [t1, t2). Система не только хранит информацию о прошлых состояниях объекта, но и предоставляет пользователю доступ к ней через язык запросов.

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

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

1. Канал объекта в кэше

2. Канал объекта на диске

3. Канал данных объекта в кэше

4. Канал истории изменений объекта на диске

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

3.6 Принципы реализации механизма согласованного управления

Область действия операции

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

Областью действия операции на объекте являются:

Данные состояния объекта, входные параметры операции, системные объекты, а также все объекты, обладающие определенным поведением, если это поведение является объектом, над которым выполняется операция.

Воздействие операции

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

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

• LocalQS = Ж, если нет собственных iv_j из O "запрошенных" операцией op_i. {O}, иначе.

• GlobalQS =

{O_gq | op_i , посылает сообщение к O_s для выполнения метода op_j, где O_sО Scope(op_i(O)), и O_gqОQS(op_j(O_s))}.

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

Множество замен определяется как объединение множеств создания, модифи­ка­ции и удаления. Конфликт операций – выполнение одного из следующих условий:

1. US(op_i(O)) З US(op_j(O')) № Ж

2. QS(op_i(O)) З US(op_j(O')) № Ж

3. US(op_i(O)) З QS(op_j(O')) № Ж

Пользовательские транзакции можно рассматривать как операции над специ­альным объектом базы данных.

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

Объектно-ориентированное расписание

Для увеличения производительности СУБД, некоторые операции могут взаимодействовать друг с другом в базе данных. Некоторые из этих операций могут выполняться на одном объекте. Совместное выполнение многих операций (псевдо­параллельность) может приводить к произвольному чередованию операций (или их шагов). Порядок чередования называется объектно-ориентированным расписанием. Так как "пользовательские транзакции" являются только операциями на специальном объекте, ОО-расписание можно определить на этом объекте как пару (S,<_расп), где S – множество всех шагов (как локальных, так и глобальных), а <_расп – частичный порядок на множестве шагов в S. Глобальные шаги в S – это результат обращения операций к другим объектам, и шаги основанные на результате этих обращений также включаются в расписание.

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

В работе [19] утверждается, что расписание Sch для T на специальном объекте является корректным объектно-ориентированным расписанием, если:

1. Расписание состоит только из шагов операций, порожденных воздействием T, и каждый из этих шагов выполняется точно раз в Sch.

2. В расписании сохраняется отношение порядка выполнения шагов операций для всех транзакций.

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

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

Этот критерий корректности заменяет собой критерий сериализуемости в ООБД.

Эквивалентность расписаний

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