Разработка прототипа системы управления объектно-ориентированной базой данных

Содержание 1. Введение 1.1 Причины появления объектно-ориентированных баз данных 1.2 Подходы в разработке ООБД 1.3 Краткий сравнительный анализ постреляционных и традиционных баз данных 1.4 Основания дипломной работы
1.5 Анализ полученного результата 2. Уточнение методов решения задачи 2.1 Наследование 2.2 Инкапсуляция 2.3 Идентификатор объекта 2.4 Идентификатор поля агрегата 2.5 Триггеры. Ограничение доступа 2.6 Действие (knowhow) 2.7 Объекты-поведения 2.8 Принципы взаимодействия объектов 2.9 Транзакции и механизм согласованного управления 3. Разработка структуры СУ 3.1 Положение дел в области интероперабельности систем 3.2 Менеджер памяти 3.3 Виртуальная память и каналы 3.4 Система управления кэшированием объектов 3.5 Система управления журнализацией и восстановлением 3.6 Принципы реализации механизма согласованного управления 4. Представление данных в ООБД 4.1 Базовые объекты системы 4.2 Строение объекта 4.3 Контекст транзакции 5. Описание операций над объектами в БД 6. Требования к техническим и программным средствам 7. Реализация прототипа 7.1 Построитель 7.2 Заголовочный модуль для каналов 7.3 Менеджер виртуальной памяти 7.4 Система управления хранением объектов 7.5 Система управления каналами 7.6 Работа с базовыми объектами 7.7 Выполнение действий 7.8 Кэширование объектов 8. Контрольный пример, демонстрирующий возможности технологии 9. Оценка трудоемкости разработки ПО с использованием традиционного и предлагаемого подходов 9.1 Табличные базы данных с низкоуровневыми операциями доступа 9.2 Реляционные базы данных 9.3 Объектно-ориентированные базы данных 9.4 Будущее применения различных баз данных 10. Литература
1. Введение 1.1 Причины появления объектно-ориентированных баз данных Развитие вычислительной техники и увеличение объемов хра­нимой информации привело к необходимости выделения техноло­гии баз данных в отдельную науку. Как правило, базы данных хранили множество однотипных данных, предоставляя пользо­вателю сервис дос­тупа к нужной ему информации. На смену иерархическим и сете­вым базам данных пришли реляционные базы данных. Успех реля­ционных баз данных обусловлен их более простой архитектурой, на­личием ненавигационного языка запросов и, главное, ясностью ма­те­матики реляционной алгебры. На этапе зарождения технологии баз данных при построении какой-либо базы данных строилась физическая модель. С накоп­лени­ем опыта стало понятно, что нужен переход к даталогической модели, ко­торая позволяет абстрагироваться от конкретной СУБД. Появилось поня­тие схемы базы данных, описывающей организацию данных в СУБД. Программы стали работать с базой данных не напрямую, а через схему БД. Такой подход обеспечил возможность менять струк­туру БД без необходимости изменять логику программ. Появление и стандартизация SQL предоставила единый интерфейс для работы с данными. Иерархическая и сетевая модели баз данных стали применяться крайне редко. Это было вызвано, прежде всего, труд­ностью модификации схем иерар­хических и сетевых баз данных и силь­но зависящей от приложений навигацией в этих базах данных. Далее, развитие объектно-ориенти­рован­ного анализа и объ­ектно-ориентированного про­ек­ти­­ро­ва­ния как эффектив­ных под­ходов для формализации пред­мет­ной об­лас­ти, при­ве­ло к появ­ле­нию инфо­ло­ги­ческой модели пред­мет­ной об­ласти. Теперь, при разработке базы дан­­ных составлялось три модели пред­став­ле­ния информации пред­метной области: инфо­логическая, да­­та­логическая и физическая, не счи­­тая локальных пользовательских пред­став­лений. Рис 1: Этапы проектирования БД Поскольку физи­ческая модель требовала привлечения эксперта в области конкретной СУБД для получения эффективного размещения дан­ных, физическая модель стала строиться самой СУБД из схемы БД, вводимой поль­зователем на основе дата­логической модели предметной области. Затем появились CASE-средства, позволяющие создавать инфо­логи­ческую модель предметной области и транслирующие ее в дата­логи­ческую модель. Казалось бы, что цель достигнута, – проектировщик работает толь­ко с инфо­логи­ческой моделью, но на самом деле, до тех пор, пока работа происходит с реля­ционной базой данных, существует разрыв меж­ду языком программирования (логикой поль­зователя) и языком описания данных (представлением данных), который преодо­левать дол­жен прог­рам­мист. Суть разрыва можно сформулировать так: воз­мож­ности ра­бо­ты с данными программы и с данными СУБД должны быть оди­наковы. В конце 80-х – начале 90-х годов массовое внедрение персо­наль­ных компьютеров привело к развитию мультимедиа-технологий и на­столь­ных САПР, структуры данных в которых слишком сложны для про­цедур­ного программирования или же необычны (нап­ример, звук). Это, а также то, что объектно-ориентированное программирование позво­ляет су­щест­венно снизить сложность разработки и обеспечить адекватное пред­став­ле­нию моделирование предметной области, при­вело к тому, что в области языков програм­мирования произошло сли­яние стилей языков вы­сокого уровня. Доминирующим под­ходом стало внедрение в них технологий объектно-ориентированного прог­рам­ми­рова­ния. Не остались в стороне и языки, встроенные в СУБД. В качестве примера выше­изло­женного можно привести продукт Visual FoxPro фирмы Microsoft. Эта СУБД обла­дает объектно-ориен­тированным языком прог­рам­ми­ро­вания, но, по сути, является реля­цион­ной СУБД, поскольку хранимые дан­ные представлены в виде таб­лиц, а таблицы пред­ставляют собой мно­жество кортежей, которые содер­жат атомарные значения. Такое несо­­ответствие и привело к буму в области разработки постреляционных баз данных. Сложившаяся ситуация хотя чем-то и напоминает время перехода к реляционным базам данных, однако во многом и отли­чается. Прежде всего, отсутствует мате­мати­чес­кая модель, кото­рая бы­ла бы однозначно признана всеми ведущими разра­ботчиками пост­ре­ляционных СУБД. Нет документа, который одноз­начно опре­делил бы требования к таким СУБД. И, наконец, нет самой системы, которая считалась бы эталоном для других систем, как это было с СУБД System-R фирмы IBM. Одним из основных критериев выбора СУБД всегда была произ­водительность. Одна­ко, несмотря на то, что объектно-ориентированные базы данных существуют уже около 10 лет, стандартных тестов на про­из­водительность пока нет. Тому есть несколько причин: отсутствие стандартного языка запросов, канонических приложений, разница в архи­тектуре и т.д. Что же есть? Имеется многочисленный опыт разработок, нап­ри­мер Jasmine, POSTGRES, и других. Три документа, содержащих поже­ла­ния относительно возмож­ностей постреляционных СУБД : [3], [12] и [14]. 1.2 Подходы в разработке ООБД За время существования баз данных накоплено огромное количество инфор­мации. Разработано огромное количество приложе­ний для работы с базами данных. Это при­вело к появлению двух кон­ку­ри­рующих концепций архитектур постреляционных СУБД:
1. Объектно-реляционные базы данных 2. Объектно-ориентированные базы данных Объектно-реляционные базы данных представляют собой реля­цион­ные базы дан­ных, дополненные надстройкой, пред­ставляющей эти дан­ные как объекты. Все по-прежнему хранится в ви­де таблиц. Этот под­ход позволяет плавно перейти от технологии хра­ни­лища таблиц к технологии хранилища объектов. Остается воз­можность выборки данных с помощью SQL-запросов. Сам SQL расширен командами работы с объ­ектами. Наиболее известным про­дуктом, в котором реализован подоб­ный подход является Oracle ver.8. Комитет ANSI X3H2, разработавший стан­дарт SQL–92, сейчас ра­бо­та­ет над SQL3. Основными усо­вер­шен­ство­ваниями в SQL3 должны стать возможность процедурного доступа на­равне с декларативным и под­держка объектов. Основным недос­тат­ком объ­ект­но-реляционных СУБД является необходимость разбирать объ­екты для размещения их в таблицах и собирать их для передачи поль­зователю из таблиц [2].
Объектно-ориентированные базы данных хранят объекты цели­ком. Для выборки объектов с помощью запросов разра­батывается язык OQL (Object Query Language), в который был вклю­чен стандарт SQL'92. Единство описания структуры БД достигается при­менением языка определения объектов ODL (Object Definition Language), пред­ло­женного ODMG (Object Database Management Group), являющегося расширением языка IDL. Эти виды баз данных обладают высокой произ­води­тель­но­стью, часто в несколько раз более высокой, чем реляционные базы дан­ных. Наиболее известными ООСУБД явля­ются Jasmine, ObjectStore и POET. Из отечественных разработок в области пост­реляционных баз дан­ных достоверно извест­но лишь о существовании ООСУБД ODB-Jupiter. Похоже, она была написана специ­ально для создания продукта ODB-Text. По крайней мере, ни о каких других приложениях написанных на ODB-Jupiter ничего не известно. Также в Internet было обнаружено опи­сание некой отечественной объектно-ориентированной базы данных вер­сии 1.2. Точнее, это был модуль, предоставляющий функции объектно-ориен­ти­ро­ван­ной СУБД. Доку­мент даже не имел названия. В нем деталь­но рассматривалась орга­низа­ция хранения данных и принцип работы. Похоже, разработка обос­новывалась лишь на принципах, которым долж­на удовлетворять СУООБД. Наиболее интересная идея: назначение строкам уникальных идентификаторов и удаление строк только при упаковке базы. Это дает существенный выигрыш в сравнении строк, так как объекты-строки с одинаковым содержанием имеют одинаковые идентификаторы. 1.3 Краткий сравнительный анализ постреляционных и традиционных баз данных Постреляционные базы данных вобрали в себя все лучшие черты иерархических, сетевых и реляционных баз данных. Хотя существуют некоторые сходства, как, например, исполь­зование указателей и вложенная структура записей в сетевой модели. Однако надо отметить, что СУООБД используют логические указатели для обеспечения целостности, а также поддерживают иерархию классов, наследование и методы. Таких средств нет в иерархических и сете­вых моделях [4]. Реляционные СУБД, идеально соответствующие своему назна­чению в тради­ци­он­ных областях применения баз данных, — банков­ское дело, системы резервирования и т.д. — в данном случае ока­зыва­ются неудобными и неэффективными по многим при­чи­нам. Основ­ное требо­вание реляционной модели — нормализация — в слу­чае слож­но­структурированных данных с многочисленными взаимо­связями приво­дит к сложным запросам с соединением таблиц. То есть к тому, к чему реляционные СУБД не при­спо­соблены, поскольку не могут обеспечить высокую производительность, требуемую интер­ак­тив­ным системам. Производительность реляционных СУБД в таких случаях может усту­пать СУООБД во много раз. Кроме того, приложения разви­ваются, и число таблиц увеличивается. Небольшое изменение в орга­низации дан­ных может привести к необходимости изменить исходные тексты прог­раммы. При этом вносятся дополнительные ошибки. Объ­ектно-ори­ен­ти­рованные языки БД позволяют достичь того же результата локальными изме­нениями в свойствах и методах интересующих объ­ектов. Кроме того, методы работы с объектами хранятся в базе вместе с объектами. 1.4 Основания дипломной работы В отношении избранных математических моделей Значительная часть этой дипломной работы основывается на двух мате­мати­чес­ких моделях. Модель единого представления данных поведений и сообщений в объектно-ориентированной базе данных Модель [17] замечательна тем, что не только описывает что пред­став­ляют из себя объекты и как они взаимодействуют между собой, но и является замкнутой, само­доста­точной. Она позволяет описать качест­венно новый вид взаимодействия в объектно-ори­ен­ти­ро­ван­ной сис­теме: алгебру объ­ектов. Эта алгебра является по своей сущности и важ­ности аналогом реля­ционной алгебры в теории реляционных баз дан­ных. В этой алгебре объ­ектов определяется что представляют из себя такие операции, как селекция, проекция и другие хорошо из­вест­ные из теории реляционных баз данных операции. Таким обра­зом, эта модель объединяет два спо­соба получения информации: по­сыл­ка сообщения объекту (что типично для объектно-ори­енти­рован­ного программирования) и выполнение за­проса над совокупностью хранимых данных (что типично для реля­ционных баз данных). Модель согласованного управления в объектно-ориентированной базе данных Эта модель [19] также оказала значительное влияние на данную работу, поскольку дополнила собой модель представления данных. Ни одна современная система управ­ления базой данных не может обойтись без подсистемы транзакций. Природа тран­зак­ций в таких при­ложениях, как CAD, мультимедийные базы данных, является весь­ма раз­лич­ной. Эти приложения характеризуются совместно выпол­ня­емыми продол­житель­ными транзакциями с произвольными опера­ци­ями. У продолжительных поль­зова­тель­ских транзакций время выпол­не­ния может быть растянуто на часы, а то и дни. Это усло­вие при­водит к тому, что хорошо извест­ный, и ставший уже классическим для тра­ди­ци­он­ных баз данных, кри­те­рий сериализуемости становится непри­меним непосредственно. О са­мом критерии сериализуемости и спо­собах реализации меха­низ­ма транзакций достаточно подробно из­ло­жено в [9] и [22]. Механизм согласованного управления позволяет повысить про­из­водительность СУООБД за счет составления расписания выпол­не­ния тран­закций, в том числе продол­жи­тельных, предоставляет тран­закциям использовать промежуточные результаты дру­гих транзакций, учитывает объектную ориентированность данных и допускает обоб­ще­ние операций (не только чтение и запись). Другие работы, также повлиявшие на организацию структуры системы управления В статье [20] излагается довольно интересная точка зрения на сос­тояние объектно-ориентированного программирования, а также рас­ска­зывается о применении несколько отличного от традиций объ­ект­но-ориентированного программирования подхода. В част­ности, насле­до­ва­ние реализуется с помощью механизмов включения и деле­гиро­вания. Это позволяет решить проблему множественного насле­дова­ния. Вводит­ся поня­тие филь­тров, представляющих собой продукции, кото­рые могут обрабатывать входя­щие сооб­ще­ния и даже пере­нап­рав­лять их на другие объ­екты, сохраняя в теле этих со­обще­ний ссыл­ку на перво­на­чаль­ный объ­ект, к которому было послано сообщение. При­чем, фильтры мо­гут реа­гировать не только на входящие, но и на исхо­дящие от объекта сообщения.
Принципы журнализации заимствованы из системы POSTGRES [23] и [15]. Принципы кэширования взяты из [1]. В отношении языка реализации Было решено реализовывать прототип СУООБД на ДССП. ДССП – диалоговая система структурного программирования – была разра­ботана в 1980 году Н.П.Брусенцовым в МГУ [5]. Система имеет под собой теоре­ти­ческое обоснование. Принцип ДССП «Слово есть слово», т.е. одно слово программы соответствует одному слову кода. Принципы управляющих конструкций наследуются от троичной вычислительной машины Сетунь-70, имевшей память на магнитных сердечниках. Словарь и обозначения – от языка Ч.Мура Forth. ДССП превосходит Forth по многим параметрам. Язык ДССП обладает существенно более низ­кой, чем язык ассемблера трудоемкостью в прог­рам­­ми­ро­ва­нии, не усту­пая ему в компактности кода и быстродействии, позво­ляет про­верять работу подпрограмм в интерактивном режиме и имеет возможность моди­фи­кации прог­рамм практически без внесения из­ме­нений в осталь­ные части ко­да.
Основные черты ДССП: · Двухстековая архитектура · Обратная польская запись · Словари · Поддержка нисходящего программирования · Встроенный отладчик с рекомпиляцией · Высокоуровневые структуры данных и операции · Высокоуровневый механизм программных прерываний и исключительных ситуаций · Компактный код · Гибкость, мобильность, наращиваемость · Наличие сопрограммного механизма К сожалению, при всех этих достоинствах, ДССП на данный мо­мент является только системой программирования. Она не предос­тав­ляет сервис СУБД и не взаи­мо­действует ни с одной СУБД. Данная рабо­та направлена на то, чтобы обеспечить ДССП воз­можность обра­батывать данные в качестве СУБД, создав тем самым дешевый (Jasmine стоит порядка $15000), но эффективный инструмент, спо­соб­ный работать даже в самых непритязательных условиях, которые так часто встре­чаются сейчас в России. Разработка не ограничивается расширением ДССП и способна работать в ка­честве сервера ООБД на файл-сервере ЛВС. 1.5 Анализ полученного результата В результате проделанной работы изучена литература по организации реля­цион­ных баз данных, подходы к организации объектно-ориентированных баз данных. Были отобраны математические модели, на основании которых была определена архитектура базы данных и принципы ее функционирования. Программно реализованы подсистемы управления виртуальной памятью и кэширования объектов. Сама работа носит исследо­вательский характер, являясь шагом от чистой теории к идеям реализации ООБД. Обширность тематики не позволила проработать детально все вопросы, касающиеся организации ООБД. В частности, очень мало места уделено средствам повышения производительности поиска в БД (индексирование). Тем не менее, некоторые найденные решений, на мой взгляд, являются весьма перспективными. Это касается организации виртуальной памяти, позволяющей организовать произвольную степень вложенности данных, и механизма кэширования, которые подробно рассматриваются в работе. В виде программного кода реализовано: · Создание, открытие ООБД · Менеджер виртуальной памяти · Система управления каналами · Система управления кэшированием объектов · Создание основных объектов · Клонирование объектов · Переопределение поведений и действий · Изменение данных в объектах · Журнализация изменений в объектах · Выполнение действий (knowhow)
2. Уточнение методов решения задачи 2.1 Наследование Наследование является мощным средством моделирования (поскольку кратко и точно описывает мир) и помогает программисту разрабатывать новые версии классов и методов, не опасаясь повредить работающую систему. Наследование способствует повторному использованию кода, потому что каждая программа находится на том уровне, на котором ее может использовать наибольшее число объектов. Совокупности свойств объекта в объектно-ориентированной базе данных уделя­ет­ся большее внимание, чем во многих объектно-ориентированных языках прог­рам­миро­ва­ния, поскольку они являются также целью запросов. Объект=состояние+поведение. Чаще всего существует только одна иерархия наследования. Этот подход перешел и в C++. Однако, возможно разделение иерархий наследования данных и наследования по­ве­де­ний. Не всегда желательно иметь точно такую же иерархию наследования пове­де­ния, как и иерархию наследования свойств. Разделение этих двух иерархий повышает возможности переиспользования (reuse) поведений. Значение переиспользования поведений Предположим, мы имеем класс Студент и хотим создать класс Аспирант. Чтобы стать аспирантом, человек должен сначала получить высшее образование как студент. В общем случае экземпляры этих классов различны. Мы не можем наследовать Аспирант от Студент, т.к. аспирант не является студентом. В противном случае, мы имели бы право рассматривать аспиранта как экземпляр класса Аспирант и, с тем же правом, как экземпляр класса студент. Тем не менее, оба класса обладают общими атрибутами, таки­ми как: имя, адрес, номер_личной_карточки, а также большинством общих пове­де­ний. Это обстоятельство побуждает создать класс Аспирант, унаследовав свойства и по­веде­ния Студента. Однако, хотя экземпляры класса Аспирант будут подмножеством всех экземпляров класса Студент (т.к. все аспиранты были студентами, но не все студенты стали аспирантами), это представление будет некорректно с точки зрения моде­лиро­вания ситуации в реальном мире. На рисунке представлено дерево наследования: Рис. 2: Диаграмма наследования Свойства классов Студент и Аспирант наследуются от класса Учащийся. Поведение класса Аспирант наследуется от Студент. Обычно подкласс наследует все атрибуты и методы из суперклассов. В приложении к наследованию поведений это означает, что класс-ученик (demandclass) состоит в отношении Переиспользовать-от (Reuse-Of) с другим классом, называемым классом-учителем (supplyclass), и класс-ученик должен наследовать все поведения от класса-учителя. Эталоны наследования: классы или прототипы? В системе отсутствуют классы и типы. Роль класса может брать на себя любой объект, называемый объектом-образцом. Такой вид наследования называется насле­до­ванием на основе прототипов. Как правило, системы с наследованием на основе прототипов концептуально более просты по сравнению с системами на основе классов. Порождение экземпляра дости­гает­ся копированием объекта-образца. Копия получает от системы уникальный иденти­фикатор, отличный от идентификатора любого другого объекта в системе. Независимо от модели наследования (классы или прототипы) существует две раз­личные стратегии реализации механизма наследования: делегирование и конкате­нация. Способ наследования: делегирование или конкатенация? Делегирование представляет собой такую форму наследования, в которой объединение интерфейсов реализовано посредством разделения родительских интер­фей­сов, т.е. с использованием ссылок. Конкатенация достигает аналогичного эффекта посредством копирования родительских интерфейсов в интерфейс порож­даемого класса или объекта, – как результат, полученный интерфейс является непре­рывным. В любом случае дочерний объект способен отвечать как на сообщения, опреде­ленные в роди­тельских интерфейсах, так и на сообщения, добавленные к интерфейсу объекта. При делегировании те сообщения, которые не могут быть обработаны объектом, должны быть направлены родителям. При конкатенации каждый объект является самодостаточным, и необходимость перенаправления сообщений отсутствует. Введение идентификаторов полей позволяет распространить подходы делегирования и конкатенации и на агре­гатные объекты.
И конкатенация, и делегирование имеют свои достоинства и недостатки. Делеги­рование обеспечивает возможность гибкого распространения изменений: любое измене­ние свойств родителя автоматически отражается на потомках. Подход, использующий конкатенацию, допускает изменение свойств родителей и потомков независимо друг от друга, что также может быть полезно во многих ситуациях. Делегирование обычно тре­бует меньших затрат по памяти, в то время как конкатенация является более эффек­тивной по времени. Simula и C++ являются примерами языков, которые реализуют на­следование на основе классов с использованием делегирования. В Smalltalk реализовано наследование на основе прототипов с использованием делегирования.
Обоснование избранного механизма наследования Было решено использовать в дипломной работе механизм наследования на основе прототипов с использованием конкатенации, как для состояний, так и для поведений, поскольку для СУБД критично именно время выполнения операций. Разделение наследо­ваний состояния и поведения позволяет уменьшить объем хранимой в каждом объекте информации. В объект помещается ссылка на объект, хранящий его интерфейс (т.е. поведение). Таким образом, интерфейсы многих объектов с одинаковым поведением могут быть сосредоточены в одном месте. Наследование на основе прототипов позволяет управлять конфигурацией объектов-образцов и обеспечивает единство представления данных. Т.е. результатом запроса к базе данных может быть список используемых мето­дов, их аргументы и другая информация, которая в системе с наследованием на основе классов скрыта в классах. Создание экземпляра через копирование снимает необхо­ди­мость введения конструктора по умолчанию, поскольку содержимое копируемого объек­та и задает начальные значения. Система поддерживает множественное наследование. Необходимость множест­венного наследования остается предметом горячих споров. Практика говорит о том, что «множественное наследование играет роль парашюта: в нем нет постоянной необхо­димости, но если он вдруг понадобился, то большое счастье иметь его под рукой» [8]. Определение родства Остается важный вопрос: как определить, является ли объект потомком другого объекта? Разделение наследований состояния и поведения приводит к тому, что слово «потомок объекта» обретает двойственное значение. С одной стороны, это потомок по данным, с другой стороны, это потомок по поведению. На самом деле, в чистой объектно-ориентированной системе данные объектов надежно защищены от вмешательства пользователя через механизм инкапсуляции. Доступ к данным производится через методы. Таким образом, родство объектов следует определять исключительно через их интерфейсы. В системе на основе классов обычно строится дерево наследования. В системе на основе прототипов с конкатенацией опре­деление родства достигается за счет операций пересечения интерфейсов. Поведение объекта составляют методы, хранящиеся в объекте-множестве, а значит для опреде­ления родства необходимо выполнить операцию пересечения множеств. Если получив­шийся в результате пересечения интерфейс совпадает с интерфейсом одного из двух сравниваемых объектов, то другой объект – его потомок. Фактически, это алгоритм оп­ределения общего предка двух объектов. Использование множеств для хранения интер­фейсов позволяет взглянуть на операцию наследования конкатенацией как на операцию слияния множеств. 2.2 Инкапсуляция Идея инкапсуляции в языках программирования происходит от абстрактных типов данных. С этой точки зрения объект делится на интерфейсную часть и реализа­ционную часть. Интерфейсная часть является спецификацией набора допустимых над объектом операций. Только эта часть объекта видима. Реализационная часть состоит из части данных (состояние объекта) и процедурной части (реализация операций). Интерпретация этого принципа для баз данных состоит в том, что объект инкапсулирует и программу и данные. Рассмотрим, например, объект Служащий. В реляционной системе служащий представляется кортежем. Запрос к нему осуществляется с помощью реляционного язы­ка, а прикладной программист пишет программы для изменения этой записи, например повышение зарплаты служащего или прием на работу. Такие программы обычно пишутся либо на императивном языке программирования с включением в него опера­торов языка манипулирования данными или на языке четвертого поколения и хранятся в обычной файловой системе, а не в базе данных. Таким образом, при таком подходе имеются кардинальные различия между программой и данными, а также между языком запросов (для незапланированных запросов) и языком программирования (для приклад­ных программ). В объектно-ориентированной системе служащий определяется как объект, который состоит из части данных (очень даже вероятно, что эта часть практически совпадает с записью, определенной для реляционной системы) и части операций (эта часть состоит из операций повышения зарплаты и приема на работу и других операций для доступа к данным сотрудника). При хранении набора сотрудников, как данные, так и операции хранятся в базе данных. Таким образом, имеется единая модель данных и операций, и информация может быть скрыта. Никакие иные операции, кроме указан­ных в интерфейсе, не выполняются. Это ограничение справедливо как для операций изменения, так и для операций выборки. Инкапсуляция обеспечивает что-то вроде “логической независимости данных”: мы можем изменить реализацию типа, не меняя каких-либо программ, использующих этот тип. Таким образом, прикладные программы защищены от реализационных изменений на нижних слоях системы. Здесь уместно вспомнить о “проблеме 2000 года”, возникшей из-за того, что в СУБД отводилось всего два разряда на год даты. Чтобы исправить возникающую ошиб­ку, нужно пересмотреть заново весь код приложения! В ООБД для решения анало­гичной проблемы требуется исправление небольшого количества методов, работающих с данными даты. 2.3 Идентификатор объекта Назначение идентификатора Объекты в БД обладают индивидуальностью. Даже при изменении структуры и поведения объекта, его индивидуальность сохраняется. Два объекта в системе отлича­ются своими идентификаторами. Идентификатор является характеристикой индиви­дуальности. Понятие индивидуальности ново для реляционных баз данных. В чисто реляционной БД все кортежи в пределах одной таблицы отличаются между собой. Характеристика различия – первичный ключ. Многие современные реляционные базы данных допускают существование в пределах одной таблицы одинаковых кортежей. И потребность в этом есть, иначе не было бы квалификатора DISTINCT в операторе SQL SELECT. Идентификатор объекта в БД позволяет различить между собой два одинаковых по значению объекта. Фактически, он играет роль дескриптора адреса объекта. Таким образом, пользователь работает с объектом не через его адрес, а через его иденти­фи­катор. Строение идентификатора В современных ООБД для ускорения доступа к объектам идентификаторы наде­ляются составной структурой.
Имеются два основных подхода для идентификации объектов: · Составной адрес (Structured address) · Заменитель (Surrogate) Составной адрес состоит из физической части (сегмента и номера страницы) и логической части (внутристраничный индекс), которые являются масками фикси­ро­ван­ной длины и, соединяясь, дают идентификатор. Составные адреса более популярны в современных ООБД как более эффективные: за один дисковый доступ можно получить адрес объекта. Использование составного адреса как идентификаторов приводит к зави­симости от организации физического хранения. Это приводит к трудностям при пере­мещении данных для хранения на другое устройство.
Заменитель – чисто логический идентификатор, генерируемый по некоторому алгоритму, который гарантирует уникальность. В заменителях, индекс (также называет­ся директорией объекта), часто используется для отображения идентификаторов в рас­положение объектов. Эффективность операций с базой данных во многом определяется скоростью доступа к одиночному объекту. Часто объекты связаны между собой и доступ к одному объекту происходит через доступ к другому. Например, через объект-список происходит доступ к его элементам. Во многих случаях создание объекта (например, глубоким копированием) приводит к каскадному созданию других объектов, состав­ляющих его содержимое. Использование кластеризации помогает организации быстрого доступа к группе связанных объектов. Кроме того, размещение объектов в одной области дискового пространства также увеличивает быстродействие. В работе [16] описан подход к построению идентификаторов-заменителей. Иденти­фикатор состоит из двух частей: кода кластера и номера в последовательности. Такой подход основывается на следующих трех принципах: 1) Идентификатор объекта должен содержать информацию о кластере, который группирует совместно используемые объекты 2) Должны быть допустимы произвольные размеры кластеров 3) Идентификаторы объектов должны подчиняться достаточно однообразному представлению, чтобы они могли выступать в качестве псевдоключей динамического хеширования. Есть три признака, по которым СУБД могут принимать решение о месте размещения объектов: 1) Правила, заданные в схеме БД 2) Указание пользователя 3) Статистика доступа В дипломной работе, несмотря на заманчивость идеи кластеризации, принят тривиальный подход: идентификатор нового объекта – это значение максимального идентификатора, использующийся в системе, плюс один. Объекты также хранятся не в виде кластеров и не вкладываются друг в друга. Хотя система управления памятью позволяет организовать и такой способ хранения. Идентичность и эквивалентность В ООБД при сравнении двух объектов между собой различают идентичность и эквивалентность объектов. Определение идентичности Два объекта являются идентичными, если их идентификаторы совпадают. Поскольку в системе не может быть двух объектов с одинаковыми идентификаторами, это означает, что это один и тот же объект, на который ссылаются с двух разных мест. Идентичность обозначается так: o1 º o2. Определение N-эквивалентности Пусть 0-эквивалентность (обозначается »0) то же самое, что проверка идентичности º. Тогда для любых двух объектов o1, o2ÎO, o1 и o2 n-эквивалентны (обозначается o1 »n o2) для n > 0, если: Существует атомарный объект c, такой, что значение(o1) = значение(o2) и их поведения идентичны; Существует объект-агрегат c, такой, что FID каждого поля с присутствует в o1 и o2, а также верно обратное: FID каждого поля o1 (o2) присутствует в c, значение(o1)=[A1 : x1, …, Am : xm] и значение(o2)=[A1 : y1, …, Am : ym], и при этом xi »n-1 yi для 1£ i £ n; или Существует объект-условие c, такой, что значение(o1) = и значение(o2) = и xi »n-1 yi для 1£ i £ 3; или Существует объект-множество c, такой, что значение(o1) = {x1, …, xl} и значение(o2) = {y1, …, ym} и l = m и для каждого xi(yj) существует один yj(xi) : xi »n-1 yj для 1£ i,j £ l; или Существует объект-список c, такой, что значение(o1) = (x1, …, xl) и значение(o2) = (y1, …, ym) и l = m и xi »n-1 yi для 1£ i £ l. Два объекта называются эквивалентными (o1 » o2) тогда и только тогда, когда o1 »n o2 для некоторого n > 0. 2.4 Идентификатор поля агрегата Введение идентификатора поля позволяет преодолеть трудность определения размещения данных полей агрегатов. Суть проблемы заключается в том, что если мы наследуем классы B и C от класса A, а затем наследуем множественно класс D от классов B и C, то экземпляр класса D одновременно является экземпляром классов A, B и C. При этом важно, чтобы "старый" класс (например, A) умел работать с объектами класса 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], также разделяет дан­ные и поведения, что дополнительно дает возможность переиспользовать поведение дру­гого объекта. Объект-поведение представляет собой множество объектов-методов, которое и назы­ва­ется интерфейсом объекта. При посылке на вход произвольного объекта OID2 сообщения OID1 (которое тоже является объектом), сначала проверяется, содержится ли OID1 в интерфейсе объекта OID2 (проверка идентичности). Если да, то выполняется действие объекта OID1, иначе сравниваются значения OID1 и объектов интерфейса (проверка эквивалентности). Если соответствие найдено, выполняется действие, указанное в найденном в интерфейсе объекте. 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) представляет собой множество меток, аргумент­ных пар { (L1, arg1), … , (Ln, argn) }. Li ÎA, argi ÎO для 1 £ i £ n и "i, j Î 1,…,n : i ¹ j Þ Li ¹ Li. Впрочем, базовые методы также используют передачу параметров через стек, как более эффективный способ программирования. Синтаксис посылки сообщения Воздействие(Набор_параметров) ~> Получатель. Объект, называемый Воздействие (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) = (A1,c1) ´ …´ (An,cn)® cr и {(A1,a1) ´ …´ (An,an)} ÍB и FID каждого поля сi присутствует в ai (в терминах ОО-програм­мирования: ci является предком по значению для ai), тогда m(B) ~> r º r.kh(x)(A1 : a1, … , An : an ) иначе проверяется совпадение значения. При совпадении значения (5) Если существует метод x в r или его объектах-учителях (объектов, от которых наследуется поведение) такой, что x » m и sig(x) = (A1,c1) ´ …´ (An,cn)® cr и {(A1,a1) ´ …´ ´ (An,an)}ÍB и FID каждого поля сi присутствует в ai, тогда m(B) ~> r º r.kh(x)(A1 : a1, … , An : an ) иначе (6) Если r является атомарным, то m(B) ~> r º fail. Иначе m(B) ~> r является комплексным сообщением (complex message sending), обладает сложной структурой. Комплексные сообщения Если Воздействие является объектом-агрегатом, то s(B) ~> o º null, если s=[ ] s(B) ~> o º [A1 : s1(B) ~> o1, …, An : sn(B) ~> on], если s=[A1 : s1, …, An : sn] где oj » o, oj неº o) и orf(oi) Ç orf(o) = Æ для j = 1, ,n и для любого i, j Î [1, ,n], если i ¹ j тогда oj неº o и orf(oi) Ç orf(oj) = Æ (т.е. o1,…,on являются глубокими копиями объекта-получателя 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 º s1(B) ~> o, если s={s1}
s(B) ~> o º s’(B) ~> o, s’= s – {x} после x(B) ~> o где x – произвольно выбранный элемент из множества s. Если Воздействие является объектом-списком, то s(B) ~> o º null, если s=( ) s(B) ~> o º sn(B) ~>(… ~>( s2(B) ~>( s1(B) ~> o))…) где s = (s1, s2, …, sn) Семантика дробящейся посылки Пусть B – Набор_параметров и пусть s, oÎO. Тогда оператор дробящейся посылки, обозначаемый ~1> определяется следующим образом: Таблица 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) (http://www.omg.org) - крупнейший в мире консорциум разработки программого обеспечения, включающий свыше 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(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. Множество замен определяется как объединение множеств создания, модифи­ка­ции и удаления. Конфликт операций – выполнение одного из следующих условий: 1. US(opi(O)) Ç US(opj(O')) ¹ Æ 2. QS(opi(O)) Ç US(opj(O')) ¹ Æ 3. US(opi(O)) Ç QS(opj(O')) ¹ Æ Пользовательские транзакции можно рассматривать как операции над специ­альным объектом базы данных. Пользовательские операции могут быть разбиты на ряд шагов, каждый из которых выполняет некоторую логическую единицу работы. Шаги эти также можно считать едиными операциями. Такое разбиение позволяет ввести понятие точки раз­рыва. Точка разрыва ставится между двумя шагами на одном уровне любой операции. Объектно-ориентированное расписание Для увеличения производительности СУБД, некоторые операции могут взаимодействовать друг с другом в базе данных. Некоторые из этих операций могут выполняться на одном объекте. Совместное выполнение многих операций (псевдо­параллельность) может приводить к произвольному чередованию операций (или их шагов). Порядок чередования называется объектно-ориентированным расписанием. Так как "пользовательские транзакции" являются только операциями на специальном объекте, ОО-расписание можно определить на этом объекте как пару (S,Различные пользовательские транзакции могут вызвать один и тот же метод, и одновременно будут выполняться несколько копий одной и той же операции. В работе [19] утверждается, что расписание Sch для T на специальном объекте является корректным объектно-ориентированным расписанием, если: 1. Расписание состоит только из шагов операций, порожденных воздействием T, и каждый из этих шагов выполняется точно раз в Sch. 2. В расписании сохраняется отношение порядка выполнения шагов операций для всех транзакций.
3. Если порожденная от T транзакция имеет две операции над одним объектом, находящиеся в методе на одном уровне вложенности, то времена выполнения этих операций не пересекаются; все вызванные подоперации одной операции завершаются до начала выполнения другой операции. Очередность выполнения задается системой управления транзакциями.
Таким образом, корректное объектно-ориентированное расписание гарантирует, что спецификации точек разрыва для операций будут соблюдаться должным образом, т.е. другие кооперативные (взаимодействующие) операции не могут видеть никаких промежуточных результатов, кроме описанных спецификацией точки разрыва. Этот критерий корректности заменяет собой критерий сериализуемости в ООБД. Эквивалентность расписаний Для определения эквивалентности расписаний: вводится следующее правило: если результат одной операции получается на основе результата другой операции, то в любом корректном расписании порядок следования конфликтующих операций одинаков. Если конфликта нет, то допустимым является любой порядок следования операций. Если при этом получаются разные результаты, то каждый из них, тем не менее, является пра­виль­ным. Этот парадокс можно проиллюстрировать на следующем примере: Положим, имеются две операции: увеличить сумму на счете вдвое и увеличить сумму на счете на 10%. Очевидно, что результат будет разным в зависимости от порядка следования операций. Но, поскольку операции независимы, в любом случае он считается правильным. Влияние наличия позднего связывания на составление расписания операций в ООБД Если объекты, которые доступны различным транзакциям, заранее известны, задача механизма согласованного управления относительно проста. Априорная инфор­мация облегчает статичное определение конфликтующих операций; следовательно, стра­тегия управления чередованием операций может быть сформулирована. Однако, позд­нее связывание (late binding), характерная черта объектно-ориентированных систем, приводит к трудности предварительного определения объектов доступа. При отсутствии такого знания, одним из выходов является блокировка некоторых транзакций до тех пор, пока вид объектов доступа не станет известен. Однако, для продолжительных (long-duration) транзакций (например, запись звука в мультимедийной БД) , такая блокировка может привести к слишком большому времени ожидания. Протокол использует оптимистический подход, при котором априорные знания недоступны. Когда протокол использует оптимистичный подход, некорректное выпол­нение обнаруживается только когда все объекты доступа известны. При обнаружении некорректного чередования, для одной или более транзакций (операций) должен быть произведен обрыв (aborted) или откат (rolled back) к моменту перед некорректным выполнением. Это хорошо зарекомендовавший себя подход, но для продолжительных транзакций откат или обрыв приведет к значительной потери системных ресурсов, которые были использованы и времени, потраченного на бесполезные вычисления. Одним из методов решения этой проблемы состоит в том, чтобы ограничить сумму откатов. Для этого используется идея точек проверки, ограничивающих глубину отката. Если происходит событие приводящее к обрыву или откату, эффект, произведенный действиями за точкой проверки должен быть отменен. Это минимизирует потери ресур­сов и в то же время сокращает продолжительные ожидания. Спецификация точки проверки Идея точки проверки используется для минимизации глубины отката в случае обрыва транзакций. Эти точки могут быть описаны пользователем. Точки проверки свя­заны с операциями на объектах и могут быть описаны как шаг операции. Нет необ­хо­димости иметь спецификацию точки проверки для каждого объекта в системе. Одна­ко пользователь может описать точки проверки в некоторых операциях на некоторых объ­ектах, так, что каждая точка представляет логическую единицу работы. Идея уста­новки точек проверки предоставляет базе данных возможность определять, находится ли она в согласованном состоянии. Точка проверки служит как механизмом синхро­низации, так и заботой о связности базы данных. Любая пользовательская транзакция может иметь зависимость от результатов других транзакций. Таким образом, точка проверки в транзакции имеет значение только если все другие активные операции также согласны с тем, что состояние базы данных в этой точке является непротиворечивым состоянием (consistent state). При этом точка проверки действует как точка встречи, в которой все активные транзакции системы фиксируют (commit) свою, возможно, частично сделан­ную, до этой точки работу. Приложение базы данных предполагает значительную известность относительно семантики операций в базе данных. Семантика знаний может быть использована для установки точек проверки в транзакциях в точках, которые соответствуют логическому завершению некоторой части работы. В традиционных базах данных с быстро выпол­няющимися транзакциями сама транзакция является логической единицей работы. Однако в крупных приложениях нельзя трактовать транзакцию целиком как логическую единицу работы. В этом и состоит полезность идеи точек проверки. Состояние пользовательских транзакций на объектах Каждый объект O в системе хранит состояние каждой пользовательской транзакции в системе. Состояние пользовательской транзакции (т.е. операции на DBIO) может принимать одно из следующих значений: Никогда не активировалась (Never Activated) Любая пользовательская транзакция, которая не воздействовала на O прямо или косвенно, находится в этом состоянии на O. Это эквивалентно тому, что не имеется никакой информации о пользовательской транзакции в O. Завершена (Completed) Пользовательская транзакция находится в состоянии Завершена на O, если операция вызванная ей на O закончила выполнение всех своих шагов. Находится в точке проверки (Chekpoint) Пользовательская транзакция не произвела никаких действий с тех пор, как оказалась в точке проверки. Задержана для проверки (BlockedForCheckPoint) Пользовательская транзакция ожидает выполнения условий, которые будут удовлетворять переводу ее в Точку проверки. Выполняется (Executing) Пользовательская транзакция выполняется на O, если операция op(O), вызванная этой транзакцией выполняется. Рис 4: Диаграмма переходов транзакции из состояния в состояние Таблица 4: Пример изменения состояния транзакции при ее выполнении Действия Новое состояние транзакции Никогда не активировалась Объект O получил запрос на выполнение op(O) впервые для транзакции Tr(op(O)) и op(O) начинает выполняться Выполняется Операция транзакции достигла описанной для нее точки проверки, все остальные активные операции на O "никогда не активировались" в точке проверки Находится в точке проверки Операция транзакции достигла описанной для нее точки проверки, но активные операции не находятся в своих точках проверки Блокирована для точки провер­ки Tr(op(O)) закончила все свои шаги Завершена Таким образом, если объект имеет точки проверки, описанные для своих операций, то операции встречаются (рандеву) в точке проверки. Если операции в точке проверки произведены успешно, то в будущем нет необходимости любой операции откатываться (rollback) за точку проверки. Шаги протокола согласованного управления
1. Операция запрошена (requested) 2. Операция вызывает другую операцию 3. Вызванная операция возвращается 4. Операция завершена 5. Точка разрыва (breakpoint) достигнута 6. Точка проверки (checkpoint) достигнута 7. В точке проверки получено сообщение Детально алгоритм выполнения шагов описан в [19].
4. Представление данных в ООБД 4.1 Базовые объекты системы Системе известны следующие базовые объекты: ROOT, FAIL, NULL, SAME, ATOMIC, INT, STR, DATIME, BIO, AGG, SET, SEQ. 1. ROOT – корень – предок всех объектов. Данных не имеет. 2. FAIL, копия ROOT – возвращается, если при воздействии произошла ошибка. 3. NULL, копия ROOT – объект-заменитель при отсутствующем значении. Эта проблема возникла недавно, но в теории реляционных баз данных пока не нашла приемлемого решения. Суть проблемы заключается в том, что при вводе данных, некоторые из них могут отсутствовать (например, не известен год рождения), поэтому нельзя сказать, чему они в точности равны. В некоторых случаях нуль может являться значением, для этого и вводится специальное обозначение (NULL). 4. SAME, копия ROOT – объект, позволяющий создавать копии. Он означает, что для взаимодействующего с ним объекта создается копия. 5. ATOMIC – предок всех атомарных объектов. Задает для них основные методы поведения. 6. INT – целое. 7. STR – строка. 8. DATIME – дата и время 9. BIO – условный объект 10. AGG – агрегат 11. SET – множество 12. SEQ – последовательность 4.2 Строение объекта Каждому объекту выделяется персональное виртуальное пространство. Объект предваряется заголовком. За заголовком следуют виртуальные пространства данных и журнала. Каждый объект имеет уникальный идентификатор в пределах системы. Таблица 5: Заголовок объекта (все поля 32-битные) Поле Семантика OID Идентификатор объекта (уникальный в пределах системы) OBJBHR Идентификатор объекта-поведения (методы) OBJKH Идентификатор объекта-действия TRCOOBJ Идентификатор транзакционного сообъекта VALUE Адрес заголовка вложенного канала, хранящего значение HISTORY Адрес заголовка вложенного канала, хранящего историю изменений Блок данных объекта Атомарный объект хранит внутри блока данных свое значение. Объект-условие хранит внутри блока данных три идентификатора в следующем порядке: идентификатор метода условия, идентификатор метода, выполняемого, если условие выполнено («истина») и идентификатор метода, выполняемого, если условие не выполнено ( «ложь»). У объектов агрегат, список и множество первое слово блока данных – размер элемента. Для списка и множества он равен 4. Для агрегата – 12. Элементом списка и множества является идентификатор объекта. Элементом агрегата является кортеж: · идентификатор объекта-значения (он обязательно является потомком объекта-образца) · идентификатор поля (FID) · идентификатор объекта-образца Если идентификатор объекта-экземпляра в списке или множестве равен нулю, это означает, что элемент удален. Признаком конца списка, множества, полей объекта служит размер виртуальной памяти, выделенной для размещения данных. Таблица 6: Строение данных для DATIME Длина в байтах Значение 2 Год 1 Месяц 1 День 1 Час 1 Минуты 1 Секунды 2 Доли секунд Такая структура журнала позво­ляет фиксировать изменения не только данных, но и поведений, knowhow… Таблица 7: Структура записи изменений во внутреннем журнале объекта Число байт Значение 4 Номер транзакции 2 Адрес размещения в заголовке 4 Замененное значение 2 Год 1 Месяц 1 День 1 Час 1 Минуты 1 Секунды 2 Доли секунд Информация о транзакциях в системе Все пользовательские объекты в системе имеют транзакционные сообъекты. Транзакционный сообъект – это объект, хранящий информацию о воздействии операций транзакций на состояние пользовательского объекта. Ссылка на сообъект находится внутри объекта, для которого отслеживаются воздействия. Таблица 8: Структура транзакционного сообъекта (агрегата) Имя поля Значение DSL Множество локальных зависимостей DSI Множество унаследованных зависимостей DSR Множество приобретенных зависимостей DS Множество зависимостей Множество зависимостей получается объединением множеств локальных, уна­сле­дованных и приобретенных зависимостей. Каждый элемент какого-либо из этих мно­жеств зависимостей – пара номеров транзакций (Ti,Tj). Если трактовать это мно­жест­во как множество ребер графа, в кото­ром вершины – номера транзакций, а реб­ра – зави­симости между транзакциями, то наличие цикла в графе означает некор­рект­ное выпол­нение транзакций.
В целях упрощения решено отказаться от таблицы конфликтов. Таблица кон­флик­тов описывает какие операции конфликтуют между собой, т.е. может ли выпол­нять­ся операция A, если в данных момент выполняется операция B. Ячейка таблицы может принимать одно из трех значений: «Конфликтует», «Не конфликтует», «Неизвестно». Значение «Неизвестно» вводится по причине наличия механизма позднего связывания, при котором заранее не известно, конфликтуют ли операции. Транзакции и объекты-поведения Объекты поведения представляют собой множество объектов, поле OBJKH кото­рых хранит идентификатор выполняемого действия. Это множество имеет ширину эле­мента не 4, как обычное множество, хранящее данные, а 8. В следующих четырех бай­тах может храниться идентификатор списка – строки таблицы чередований в точках разрыва (части подсистемы транзакций). Таблица чередований образуется из точек раз­рыва и группировки спецификаций для объекта. Она позволяет определить: в каких точ­ках разрыва каких операций можно переключиться на выполнение операции, соответ­ствующей этой строке таблицы чередований. Это статическая информация, ко­торая может быть сформирована перед началом работы системы. Элемент строки та­блицы чередований состоит из 2 значений: идентификатора операции и иденти­фикатора мно­жества, хранящего номера точек разрыва. 4.3 Контекст транзакции В системе есть объект DBIO (Database User-Intarface Object), которому известны состояния всех транзакций. Этот объект представляет собой множество, элементами которого являются объекты-агрегаты, описывающие контекст транзакции. Таблица 9: Контекст транзакции Имя поля Размер в байтах Значение TR_MESS 4 OID сообщения TR_KH 4 OID knowhow TR_PARAM 4 OID агрегата с параметрами TR_TARGET 4 OID целевого объекта сообщения TR_RES 4 OID результата TR_STACK 4 OID стека TR_N 4 Номер транзакции TR_HOSTN 4 Номер вызвавшей транзакции TR_STATUS 1 Состояние транзакции TR_POINT 2 Точка разрыва, в которой находимся Для каждой транзакции выделяется свой стек. Механизм сохранения и вос­ста­нов­ления стеков описан в [7]. Стеки сохраняются в атомарных объектах.
5. Описание операций над объектами в БД [] DB.NEW [] -- создать новую БД [] DB.OPEN [] -- открыть БД [] DB.CLOSE [] -- закрыть БД Операции клонирования: [oid] CLONE [oid'] -- клонировать объект [] CLONE_ROOT [oid'] -- Создать объект от "Корень" [int] CLONE_INT [oid'] -- Создать объект "Целое" ["string"] CLONE_STR [oid'] -- Создать объект "Строка" ["string"] CLONE_AGG [oid'] -- Создать объек-агрегат [oid_if oid_then oid_else] CLONE_BIO [oid'] -- Создать объект-условие [] CLONE_SET [oid'] -- Создать объект-множество [] CLONE_SEQ [oid'] -- Создать объект-последовательность OIDROOT, OIDINT, OIDAGG, …, OIDSEQ -– Узнать идентификаторы соотв. Объектов [oid_bhr] SET_BHR [] -- переопределить поведение [] GET_BHR [oid] -- узнать поведение [oid_kh] SET_KH [] -- переопределить действие [] GET_KH [oid] -- узнать действие [oid] GET_INT [int] -- Получить целое число из объекта-целого [int oid] SET_INT [] -- Занести целое число в объект-целое [oid] PRINT_STR [] -- Печатать на экране содержимое строки ["string" oid] SET_STR [] -- Занести строку в объект-строку [oid_super oid] SUPER+ [] -- наследовать данные из oid_super в oid [oid] DELOBJ [] -- удалить объект Операции над множеством: [oid_el oid] SET+E [] -- добавить элемент в множество [oid_el oid] SET-E [] -- удалить элемент из множества [oid_el oid] SET?E [0/1] -- найти элемент в множестве [oid1 oid] SET+ [] -- объединение [oid1 oid] SET- [] -- разность [oid1 oid] SET* [] -- пересечение Операции над списком: [oid_el n oid] SEQ+E [] -- добавить элемент в последовательность [n oid] SEQ-E [] -- удалить n-й элемент из последовательности [oid_el oid] SEQ?E [0/n] -- найти позицию в последовательности [n oid] SEQ?N [0/oid] -- определить oid n-го элемента послед-ти Операции над агрегатом: [fid oid_etalon oid] AGG+F [] -- добавить поле к объекту [fid oid] AGG-F [] -- удалить поле из объекта [fid oid] ETALON [oid] -- получить идентификатор объекта-эталона [fid oid] FIELD [oid] -- получить идентификатор объекта-значения Операции над объектом-условием: [oid] GET_BIO [oid_else oid_then oid_if] -- Получить параметры объекта-условия [oid_else oid_then oid_if oid] SET_BIO [] -- Сохранить параметры объекта-условия Специальные операции: [oid_str oid] SET_NAMEOBJ [oid] -- именовать объект [oid_str fid] SET_NAMEFID [fid] -- именовать поле [oid_str] NAMEOBJ [oid] -- получить идентификатор по имени [oid_str] NAMEFID [fid] -- получить идентификатор поля по имени [oid_mess oid_par oid] SEND [] -- послать сообщение объекту [oid_mess oid_obj] METHOD? [] -- определить идентификатор метода [oid1 oid] CHIELD [1/0] -- определить, является ли oid1 потомком oid [oid_kh] RUN_KH [] -- выполнить knowhow
[] NCHAN [chan] -- узнать номер текущего канала [chan] !NCHAN [] -- переключиться на заданный канал Операции просмотра: [oid] JVIEW [] -- просмотр журнала [] A.VIEW [] -- просмотр адресов объектов в БД
[] Q.VIEW [] -- просмотр очереди [] IC [] -- просмотр состояния канала
6. Требования к техническим и программным средствам ДССП реа­лизована на множестве компьютерных платформ (VAX, PDP-11, IBM PC, R3000, MC68020, SPARC) и операционных систем (MSDOS, MSDOS-экстендеры, UNIX, RT-11, RSX, OS9, CPM и др.). В дан­ный момент практически закон­чена разработка ДССП на Си, что обес­печивает перенос этой системы на любую платформу, где есть Си. Аппаратные средства: Любая платформа, на которой функционирует ДССП, с объемом оперативной памяти для нужд БД не менее 1 Мб. Программные средства: ДССП с диспетчером параллельных процессов (версия 4.42) и Операционная Система. Разрабатываемая СУООБД может также работать в качестве host-программы на файл-сервере, обрабатывая команды с рабочих станций, поступающие в их персональные ящики на файл-сервере. Ответ рабочие станции получают также через почтовые ящики. В дальнейшем, могут быть реализованы сетевые протоколы и тогда СУООБД будет являться сервером в клиент-серверных приложениях. Использование отдельных почтовых ящиков для нескольких параллельно работающих пользователей позволяет возложить на СУООБД функции монитора [6], осуществляющего линеаризацию поступающих запросов к содержимому СУООБД.
7. Реализация прототипа 7.1 Построитель LOAD TIMEM LOAD M0 LOAD M2 LOAD Soms LOAD CHMS LOAD SYSOBJS LOAD M3 LOAD LS_CASH UNDEF PROGRAM $KH_VOC 7.2 Заголовочный модуль для каналов PROGRAM $M0 B16 1000 VALUE TOTMEMLEN TOTMEMLEN BYTE VCTR MEMORY : T-1 D -1 ; : *4 SHL SHL ; : &0FF 0FF & ; : : >= 1- > ; [20 WORD VCTR CHAN] [каналы. Начиная с 5-го] VAR NCHAN [Номер текущего канала] : !NCHAN ! NCHAN ; 5 VALUE NBASECH [Первый не базовый канал] : GETDATA NCHAN 10 * + CHDATA ; : PUTDATA NCHAN 10 * + ! CHDATA ; [Размер заголовка блока в байтах] FIX VAR HSIZE 10 ! HSIZE : HSIZE+ HSIZE + ; [Pred, Next, BusyLen, Len] 1 *4 VALUE ctfPREDADDR [$M4] [как самодостаточный] 0 VALUE ctLOWCH [Нижний канал.] [0=Оперативная/1=Дисковая память/2=Журнал/-1=свободен] 1 VALUE ctTEKADR [Логический адрес внутри участка (по данным)] 2 VALUE ctBUSYLEN [Длина фрагмента, занятая данными] 3 VALUE ctLEN [Максимальная допустимая длина данных фрагмента] 4 VALUE ctTEKADR0 [=TEKADR, когда TEKADR стоит на нулевом байте данных фрагм] 5 VALUE ctNEXTADDR [Адрес начала заголовка следующего фрагмента (пф)] 6 VALUE ctPREDADDR [Адрес начала заголовка предыдущего фрагмента (пф)] 7 VALUE ctSYNCADDR [Адрес начала заголовка фрагмента (пф)] 8 VALUE ctCHGCTX [признак изменения контекста] 9 VALUE ct1STLONG [Первое число в канале] [в начальном блоке в начальном слове данных лежит адрес начала данных] : LOWCH ctLOWCH GETDATA ; : !LOWCH ctLOWCH PUTDATA ; : TEKADR ctTEKADR GETDATA ; : !TEKADR ctTEKADR PUTDATA ; : TEKADR0 ctTEKADR0 GETDATA ; : !TEKADR0 ctTEKADR0 PUTDATA ; : TEKADR++ TEKADR 1+ !TEKADR ; : !+TEKADR TEKADR + !TEKADR ; : BUSYLEN ctBUSYLEN GETDATA ; : !BUSYLEN ctBUSYLEN PUTDATA ; : LEN ctLEN GETDATA ; : !LEN ctLEN PUTDATA ; : NEXTADDR ctNEXTADDR GETDATA ; : !NEXTADDR ctNEXTADDR PUTDATA ; : PREDADDR ctPREDADDR GETDATA ; : !PREDADDR ctPREDADDR PUTDATA ; : SYNCADDR ctSYNCADDR GETDATA ; : !SYNCADDR ctSYNCADDR PUTDATA ; : CHGCTX ctCHGCTX GETDATA ; : !CHGCTX ctCHGCTX PUTDATA ; : FSTLONG ct1STLONG GETDATA ; : !FSTLONG ct1STLONG PUTDATA ; TRAP NOMEMORY NOMEMORY# : NOMEMORY# ." No free memory" ; TRAP OUTDATA OUTDATA# : OUTDATA# ." Out of data. " ; TRAP OUTMEM OUTMEM# : OUTMEM# ." Out of memory. " ; TRAP UNKCH UNKCH# : UNKCH# ." Unknown primitive channel:" NCHAN .D CR ; TRAP O_NOTFND NOTFND# : NOTFND# ." Object not found. OID=" . CR ; [*** Информация по каналу ***] : IC CR ." NCHAN=" NCHAN .D SP ." LOWCH=" LOWCH .D CR ."SYNCADDR=" SYNCADDR .D SP ."PREDADDR=" PREDADDR .D SP ."NEXTADDR=" NEXTADDR .D CR ." BUSYLEN=" BUSYLEN .D SP ." LEN=" LEN .D CR ." TEKADR0=" TEKADR0 .D SP ." TEKADR=" TEKADR .D CR ; CHANNEL DATACH "DATA." CONNECT DATACH 7.3 Менеджер виртуальной памяти PROGRAM $M2 B16 [физическая организация памяти] [вычисление физического адреса и номера базового канала] :: : POSIX [addr(i)] NCHAN C NBASECH GOTO DELTA2 S( NCHAN ) TOLOW POSIX [addr(i-1)] ; :: : TOLOW LOWCH !NCHAN ; [Пересчет адреса в адрес нижнего уровня: TEKADR(i) -> TEKADR(i-1)] :: : DELTA2 SYNCADDR HSIZE + TEKADR TEKADR0 - + ; :: : IBS EON OUTDATA OUTDATA# LAST? TEKADR POSIX TEKADR++ S( NCHAN ) !NCHAN BSGOTO NCHAN BR 0 IBS0 1 IBS1 [2 IBS2] ELSE UNKCH ; :: : OBS EON OUTDATA OUTDATA# LAST? TEKADR POSIX TEKADR++ S( NCHAN ) !NCHAN BSGOTO NCHAN BR 0 OBS0 1 OBS1 [2 OBS2] ELSE UNKCH ; : LAST? TEKADR BUSYLEN TEKADR0 + = IF0 LEAVE NEXTBLK ; [переход для базового канала ] : BSGOTO [ADDR] NCHAN BR 0 BSGOTO0 1 BSGOTO1 [2 BSGOTO2] ELSE UNKCH ; : BSGOTO0 !TEKADR ; : BSGOTO1 C !TEKADR HSIZE+ SPOS DATACH ; [ : BSGOTO2 C !TEKADR HSIZE+ SPOS JOURCH ;] 0 %IF : ADDR [PARAGRAF OFFSET] + [address] ; [Сейчас пгф=1 байту] [Для файлов можно сделать неск. файлов и распределить по ним пространство] %FI : IBS0 TEKADR HSIZE+ MEMORY &0FF TEKADR++ ; : IBS1 IB DATACH &0FF TEKADR++ ; [: IBS2 IB JOURCH &0FF TEKADR++ ;] : OBS0 &0FF TEKADR HSIZE+ ! MEMORY TEKADR++ ; : OBS1 &0FF OB DATACH TEKADR++ ; [Запись байта] [: OBS2 &0FF OB JOURCH TEKADR++ ;] [Запись байта] :: : GOTO NCHAN NBASECH : VGOTO TEKADR - @GOTO ; [Переход по смещению] :: : @GOTO C BRS @GOTO- D @GOTO+ ; : @GOTO+ DO @GOTO1+ ; : @GOTO- NEG DO @GOTO1- ; : @GOTO1+ EON OUTDATA OUTDATA# TEKADR TEKADR0 BUSYLEN + = IF+ NEXTBLK TEKADR 1+ !TEKADR ; : @GOTO1- EON OUTDATA OUTDATA# TEKADR TEKADR0 = IF+ PREDBLK TEKADR 1- !TEKADR ; : NEXTBLK CHGCTX IF+ SCTX NEXTADDR NOEXIST? !SYNCADDR RELCTX TEKADR !TEKADR0 ; : NOEXIST? [ADDR] C -1 = IF+ OUTDATA [ADDR] ; [Pred, Next, BusyLen, Len] :: : LCTX' [UPCH] PUSH TEKADR ILS ILS ILS ILS POP NCHAN E2 !NCHAN !LOWCH !LEN !BUSYLEN !NEXTADDR !PREDADDR !SYNCADDR 0 !CHGCTX ; [Грузить параметры канала] :: : LCTX [newch] LCTX' 0 !TEKADR 0 !TEKADR0 ;
: RELCTX TEKADR0 TEKADR NCHAN SYNCADDR TOLOW GOTO LCTX !TEKADR !TEKADR0 ; : PREDBLK CHGCTX IF+ SCTX PREDADDR NOEXIST? !SYNCADDR RELCTX TEKADR BUSYLEN - !TEKADR0 ; : IBSC [CHAN] S( NCHAN ) !NCHAN IBS ; : ILSC S( NCHAN ) !NCHAN ILS ;
: OBSC [N CHAN] S( NCHAN ) !NCHAN OBS ; : IOBSCC [SRC DST] C2 IBSC C2 OBSC ; : DO_IOBSCC [SRC_CH DST_CH N] S( NCHAN ) C3 !NCHAN 0 GOTO DO IOBSCC [SRC DST] ; : IWS IBS IBS SWB &0 ; : ILS IWS IWS SETHI ; [SWW &0] : OWS C OBS SWB OBS ; : OLS C OWS SWW OWS ; [Перейти к конечному блоку] : GOTOENDBK NEXTADDR -1 = EX+ BUSYLEN TEKADR0 + NEXTADDR !SYNCADDR RELCTX C !TEKADR0 !TEKADR ; : GOBOTTOM RP GOTOENDBK BUSYLEN TEKADR0 + GOTO ; : LENVMEM GOBOTTOM TEKADR [LEN] ; [длина виртуальной памяти] : LASTADDR SYNCADDR LEN + HSIZE+ ; : OBS-0 NCHAN BR 0 OBS00 1 OBS01 [2 OBS02] ELSE OBS0N ; : OBS00 0 OBS0 ; : OBS01 0 OBS1 ; [: OBS02 0 OBS2 ;] : OBS0N 0 OBS ; [Спецификация: Размер увеличивается на N байт. Если это невозможно, возникает исключительная ситуация NOMEMORY. После работы мы стоим в том же канале в начале выделенного пространства. ] : UPSIZE [N] GOBOTTOM TEKADR E2 UPSIZE' GOTO [] ; : UPSIZE' [N] GOBOTTOM LEN BUSYLEN - CALCOST [HARD SOFT] UPSIZEI C BR0 D UPSIZEO ; : CALCOST [N FREE] C2C2 : COST1 [N FREE] T0 E2 [0 N] ; : COST2 [N FREE] C PUSH - POP [N-FREE FREE] ; : UPSIZEI [N_SOFT] BUSYLEN + !BUSYLEN 1 !CHGCTX SCTX ; : UPSIZEO [N_HARD] NCHAN BR 0 USO0 1 USO1 2 USO1 ELSE USON ; : USO1 C GOBOTTOM TEKADR E2 DO OBS-0 [!TEKADR] BSGOTO C BUSYLEN + !BUSYLEN LEN + !LEN 1 !CHGCTX SCTX ; : USO0 NOMEMORY [Сюда можно вставить упаковку] ; [Спецификация: увеличение размера (жестко, т.е. за счет нижнего уровня)] : USON [N] SYNCADDR LASTADDR USON1 RELCTX [>] UPSIZE' ; : USON1 S( NCHAN ) TOLOW BUSYLEN = BR+ USON_ADD USON_NEW ; [Расширение увеличением длины фрагмента] : USON_ADD C2 [N SYNCADDR N] UPSIZE' C BUSYLEN E2 - HSIZE - E2 [N LEN SYNCADDR] 3 *4 + GOTO OLS [N] [UPSIZEI] ; [Расширение созданием нового фрагмента] : USON_NEW C2 [N SYNCADDR N] [GOBOTTOM] C HSIZE+ UPSIZE' [N SYNCADDR N] C2 -1 0 C4 TEKADR PUSH WRITECTX D 4+ GOTO POP OLS [N] ; : WRITECTX [PRED NEXT BUSY LEN] C4 OLS C3 OLS C2 OLS C OLS DD DD ; FIX VAR UPCONST 10 ! UPCONST [Этому числу байт кратно увеличение] [Увеличение размера нижнего уровня] [увеличение физического размера этого уровня] : SCTX CHGCTX IF0 LEAVE 0 !CHGCTX NCHAN BR 0 NOP 1 SCTX1 [2 SCTX2] 3 NOP 4 NOP ELSE SCTXN ; : SCTXN TEKADR NCHAN LEN BUSYLEN NEXTADDR PREDADDR SYNCADDR TOLOW GOTO 4 DO OLS !NCHAN GOTO ; : SAVEALL NOP ; [СОХРАНИТЬ ВЕСЬ КАНАЛ НА ПЕРВИЧНОМ УСТРОЙСТВЕ (ИСТОЧНИКЕ)] : SCTX1 POS DATACH 8 SPOS DATACH BUSYLEN OL DATACH LEN OL DATACH SPOS DATACH ; [ : SCTX2 POS JOURCH 8 SPOS JOURCH BUSYLEN OL JOURCH LEN OL JOURCH SPOS JOURCH ; ] [Новая виртуальная память] 0 %IF : NEWVM [N] TEKADR C2 HSIZE+ UPSIZE GOTO -1 -1 C3 C WRITECTX D ; %FI : NEWVM [N] C HSIZE+ UPSIZE TEKADR PUSH -1 -1 0 C4 WRITECTX DO OBS-0 POP [SYNCADR] ; : END? NEXTADDR -1 = TEKADR BUSYLEN TEKADR0 + = & ; : NEWVM1 [N] C HSIZE+ UPSIZE TEKADR PUSH -1 -1 E3 C WRITECTX WRI_DATA POP [SYNCADR] ; : LOADCH0 0 !NCHAN 0 !LOWCH 0 !TEKADR 0 !BUSYLEN TOTMEMLEN !LEN 0 !TEKADR0 0 !SYNCADDR -1 !NEXTADDR -1 !PREDADDR ; [ДЛЯ БАЗОВЫХ КАНАЛОВ LOWCH=NCHAN] 7.4 Система управления хранением объектов PROGRAM $SOMS B16 [СИСТЕМА УПРАВЛЕНИЯ ХРАНЕНИЕМ ОБЪЕКТОВ] FIX LONG VAR MAXID 1 ! MAXID : NEWID MAXID !1+ MAXID ; : DEFMAXID 6 EL_MAX 1+ ! MAXID ; [5 КАНАЛ = ОПЕРАТИВНАЯ ПАМЯТЬ; 6 КАНАЛ = ДИСКОВАЯ ПАМЯТЬ] : L_SUHO 0 !NCHAN 0 GOTO 5 LCTX 1 !NCHAN 0 GOTO 6 LCTX ; [создание структуры СУХО для ОП] [9 -- Размер, занимаемый элементом списка] LONG VAR SIZE_EL 8 ! SIZE_EL [создать новый объект] ACT VAR WRI_DATA : M.NEWOBJ [SIZE OID] 0 E2 8 5 X.NEWOBJ [] ; : D.NEWOBJ [SIZE OID] 1 E2 8 6 X.NEWOBJ [] ; : X.NEWOBJ [SIZE LOWCH OID SIZE_EL DIR_CHAN] C PUSH S( NCHAN ) !NCHAN UPSIZE [ OID] OLS [basechan] !NCHAN NEWVM1 [SYNCADDR] POP !NCHAN OLS [] ; :: : M.VIEW 5 !NCHAN CR ."RAM:" VIEW.OBJ' ; :: : D.VIEW 6 !NCHAN CR ."HDD:" VIEW.OBJ' ; :: : A.VIEW M.VIEW D.VIEW ; : IC.VIEW [A L] SHR SHR E2 GOTO DO IC1.V ; : IC1.V TEKADR CR .D #> TOB SP SP ILS .D ; : VIEW.OBJ' 0 GOTO ILS D [Пропустили длину элемента] CR ." OID ADDRESS" RP SHOWPAROBJ ; : SHOWPAROBJ END? EX+ ILS C BR0 SPO1 SPO2 ; : SPO1 D ILS D ; : SPO2 CR .D SP ILS .D SP ; : M.DEL [OID] 5 X.DEL ; : D.DEL [OID] 6 X.DEL ; : A.DEL [OID] C M.DEL D.DEL ; ACT VAR EL_AVAR :: : X.DEL [OID NCHAN] EL_FIND [OID 1/0] IF+ EL_DEL D ; [найти элемент в списке по ID и встать на след. за OID слово] : EL_DEL -4 @GOTO 0 OLS ; :: : EL_FIND [OID NCHAN] '' EL_COMPAR ! EL_AVAR EL_PEREBOR ; : EL_PEREBOR !NCHAN 0 GOTO ILS D RP EL_FIND0 [OID 1/0] ; : EL_FIND0 END? 0 E2 EX+ D ILS C BR0 D EL_AVAR ILS D ; : EL_COMPAR [OUR_OID TEK_OID] C2 = C EX+ D ; :: : EL_MAX [DIR-NCHAN] 0 E2 '' MAX ! EL_AVAR EL_PEREBOR D [OID] ; :: : DB.NEW !1 MAXID WOPEN DATACH -1 OL DATACH -1 OL DATACH 14 OL DATACH 14 OL DATACH -1 OL DATACH -1 OL DATACH 4 OL DATACH 4 OL DATACH 8 OL DATACH CLOSE DATACH [ WOPEN JOURCH -1 OL JOURCH -1 OL JOURCH 14 OL JOURCH 14 OL JOURCH -1 OL JOURCH -1 OL JOURCH 4 OL JOURCH 4 OL JOURCH 8 OL JOURCH CLOSE JOURCH ] DB.OPEN ; : DB.CLOSE CLOSE DATACH [CLOSE JOURCH] ; : DB.OPEN -1 !!! CHDATA [DATA] OPEN DATACH 1 !NCHAN 0 !TEKADR 0 !TEKADR0 1 !LOWCH IL DATACH !PREDADDR IL DATACH !NEXTADDR 0 !SYNCADDR IL DATACH !BUSYLEN IL DATACH !LEN 6 LCTX [RAM] 0 !NCHAN 0 !LOWCH 0 !TEKADR 0 !BUSYLEN TOTMEMLEN !LEN 0 !TEKADR0 0 !SYNCADDR -1 !NEXTADDR -1 !PREDADDR '' WRI_8OLS ! WRI_DATA [длина элемента каталога] 4 [ [SYNCADR] GOTO 5 LCTX [4 UPSIZE 8 OLS] DEFMAXID CHMS.INIT ; : WRI_8OLS 8 OLS ; 7.5 Система управления каналами PROGRAM $CHMS 3 VALUE LENGRP [Вместимость уровня приоритетов] 4 VALUE QChannels LENGRP 3 * 1+ VALUE LenPrioQue [длина очереди приоритетов. Очередь -- с 0] : N2CH [N] QChannels * 0A + [NCHAN] ; LenPrioQue 1+ N2CH 10 * LONG VCTR CHDATA [память параметров каналов] [для каждого канала можно завести 16. различных параметров] : CHMS.INIT 0 !!! PrioQueOID 0 LenPrioQue DO SETNQ D ; : SETNQ C C ! PrioQueNUM C N2CH [NUM CHAN1] [вычислили номер канала для очередного объекта кэша] C C3 1 ! Channels 1+ C C3 2 ! Channels 1+ C C3 3 ! Channels 1+ C C3 4 ! Channels D 1+ ; [при обращении к объекту нужно повысить его приоритет] : HIPRIODD D HIPRIO ; : HIPRIO [OID] FINDOID C BR- D HIPRIO1 ;
: HIPRIO1 [N] C LENGRP / D C IF+ 1- LENGRP * [N N'] E2 UPOID [] ; [Новый объект добавляется на последн. поз-ю, а затем к нему примен. HIPRIO] LenPrioQue LONG VCTR PrioQueOID [список OID] LenPrioQue WORD VCTR PrioQueNUM [номера записей в массиве каналов] LenPrioQue QChannels 2 WORD ARR Channels
[обменять в очереди с соседним вышестоящим] : SWP2OBJ [N] C IF0 LEAVE C PrioQueOID C2 1- PrioQueOID C3 ! PrioQueOID C2 1- ! PrioQueOID C PrioQueNUM C2 1- PrioQueNUM C3 ! PrioQueNUM C2 1- ! PrioQueNUM 1- [N-1] ; : SWP2OBJDD SWP2OBJ DD ; : FINDOID [OID] 0 LenPrioQue DO CMPOID E2D C LenPrioQue = IF+ T-1 [-1/N] ; : CMPOID [OID] C PrioQueOID [OID N OID(N)] C3 = EX+ 1+ ; [Поднять объект от N_DOWN к N_UP в очереди] : UPOID [N_UP N_DOWN ] C E3 - DO SWP2OBJ D [] ; [Просмотр очереди (кэш объектов)] : Q.VIEW 0 LenPrioQue ." M.Hdr D.Hdr M.Dat D.His" DO QELVIEW D ; : QELVIEW [n] CR C C 2 TON LENGRP / E2D BR0 #- #) TOB C PrioQueOID ." OID=" .D C PrioQueNUM ." Num=" . ." Channels= " 1 QChannels DO PriNCH DD 1+ ; : PriNCH [NOID NCH] C2C2 Channels 4 TON SP SP 1+ [NOID NCH+1] ; 7.6 Работа с базовыми объектами PROGRAM $SYSOBJS B16 LONG VAR ADRSTR LONG VAR LENSTR 0 VALUE N_OID 4 VALUE N_BHR 8 VALUE N_KH 0C VALUE N_TRC 10 VALUE N_VAL 14 VALUE N_HIS 13 VALUE JRECLEN : G_OID N_OID GOTO ; : W_OID G_OID OLS ; : G_BHR N_BHR GOTO ; : W_BHR G_BHR OLS ; : G_KH N_KH GOTO ; : W_KH G_KH OLS ; : G_TRC N_TRC GOTO ; : W_TRC G_TRC OLS ; : G_VAL N_VAL GOTO ; : W_VAL G_VAL OLS ; : G_HIS N_HIS GOTO ; : W_HIS G_HIS OLS ; 18 VALUE SZ_HDROBJ : W_NULLBLK -1 OLS -1 OLS 0 OLS 0 OLS ; [Описание системных объектов] ACT VAR DATWR LONG VAR OIDV LONG VAR VALINT [**** ROOT ****] SZ_HDROBJ HSIZE+ HSIZE+ 4+ VALUE SIZE_ROOT :: : CLONE_ROOT '' DATWRROOT ! DATWR NEWOBJ1 ; :: : CLONE_INT ! VALINT '' DATWRINT ! DATWR NEWOBJ1 ; :: : CLONE_SET 4 CLONE_INT ; :: : CLONE_SEQ 4 CLONE_INT ; :: : CLONE_AGG 0C CLONE_INT ; :: : CLONE_STR [A L] ! LENSTR ! ADRSTR '' DATWRSTR ! DATWR LENSTR SIZE_ROOT + 4- ! SIZE_X NEWOBJ3 ; :: : SET_BHR [OID_BHR OID] N_BHR E2 SET_X1 ; :: : SET_KH [OID_KH OID] N_KH E2 SET_X1 ; : SET_X1 [ADR OID] C2C2 N_TRSC E2 NEWJREC C LOADOBJ FINDOID C BR- DD SET_X11 ; : SET_X11 PrioQueNUM 2 Channels !NCHAN GOTO OLS ; :: : SET_INT [int oid] C HIPRIO PUSH ! VALINT 4 '' OLSI POP NEWDREC ; : OLSI VALINT OLS ; :: : GET_INT [OID] TODATA ILS ; :: : TODATA [OID] C LOADOBJ C HIPRIO FINDOID PrioQueNUM 3 Channels !NCHAN 0 GOTO ; :: : SET_STR [A L OID] C HIPRIO PUSH ! LENSTR ! ADRSTR LENSTR '' OLSS POP NEWDREC ; : OLSS ADRSTR LENSTR DO DWS1 D ; ACT VAR BYTE_STR :: : PRINT_STR '' PRIS ! BYTE_STR ACCESS_STR ; :: : COPY2BUF_STR '' C2BUF ! BYTE_STR ACCESS_STR ; :: : ACCESS_STR [OID] TODATA LENVMEM 0 GOTO DO BYTE_STR ; : PRIS IBS TOB ; : C2BUF IBS ABUF !TB !1+ ABUF ; : DD_ROOT OIDV OLS 0 OLS 0 OLS 0 OLS SZ_HDROBJ HSIZE+ OLS [val] SZ_HDROBJ OLS [his] W_NULLBLK [W_NULLBLK] DATWR ; LONG VAR SIZE_X : DATWRROOT -1 OLS -1 OLS 0 OLS 4 OLS 0 OLS ; : DATWRINT -1 OLS -1 OLS 4 OLS 4 OLS VALINT OLS ; : DATWRSTR -1 OLS -1 OLS LENSTR OLS LENSTR OLS ADRSTR LENSTR DO DWS1 D ; : DWS1 [A] C @B OBS 1+ ; : NEWOBJ1 [] SIZE_ROOT ! SIZE_X NEWOBJ3 ; : NEWOBJ3 '' DD_ROOT ! WRI_DATA NEWID C ! OIDV SIZE_X C2 D.NEWOBJ [OID] ; 9 VALUE LCH LCH LONG VCTR CLONEHDR VAR DATCH LONG VAR LENVMEM1 :: : CLONE [OID] C HIPRIO C LOADOBJ FINDOID PrioQueNUM C PUSH 2 Channels !NCHAN 0 GOTO CLONE1 [] '' CC_ROOT ! WRI_DATA NEWID C 0 ! CLONEHDR SZ_HDROBJ HSIZE+ C2 D.NEWOBJ [OID] POP 3 Channels C ! DATCH !NCHAN LENVMEM C ! LENVMEM1 C2 [OID_NEW LEN OID_NEW] CLONE_DATA [OID_NEW] ; : CLONE1 ILS 1 ! CLONEHDR [BHR] ILS 2 ! CLONEHDR [KH] ILS 3 ! CLONEHDR [TRC] 0 4 ! CLONEHDR SZ_HDROBJ 5 ! CLONEHDR -1 6 ! CLONEHDR -1 7 ! CLONEHDR 0 8 ! CLONEHDR 0 9 ! CLONEHDR ; : CCR1 [N] C CLONEHDR OLS 1+ ; : CC_ROOT 0 LCH 1+ DO CCR1 D ; : CLONE_DATA [LEN OID] '' COPY_DATA E2 NEWDREC [] ; : COPY_DATA [] DATCH NCHAN LENVMEM1 DO_IOBSCC DD ; :: 0 VALUE N_TRSC [Запись новых данных, запись в журнал] : NEWDREC [SIZED PROC OID] N_VAL N_TRSC C3 NEWJREC FINDOID PrioQueNUM [SIZE PROC N] C PUSH 2 Channels !NCHAN [SIZED PROC] ! WRI_DATA NEWVM1 G_VAL C OLS [ADR_DATA] [перечитать канал данных] GOTO POP 3 Channels LCTX [] ; [новая запись в журнал. На вх: номер транз. и адрес из заголовка] : NEWJREC [addr_hdr TRANS OID] C LOADOBJ FINDOID PrioQueNUM [. TRANS N] C PUSH 4 Channels !NCHAN JRECLEN UPSIZE OLS POP NCHAN PUSH 2 Channels !NCHAN C GOTO ILS POP !NCHAN E2 OWS OLS W_DATIME [] ; B10 [Запись текущего времени] : W_DATIME 1979 OWS 12 OBS 31 OBS TMGET TMS ; : TMS [num] N2T GBR E2 GBR E2 GBR E2 OBS OBS OBS 100 * OWS ; B16 [просмотр журнала объекта] [Переключиться на журнал] : OBJ.J [OID] C LOADOBJ FINDOID PrioQueNUM 4 Channels !NCHAN ; : JVIEW [oid] CR ."Updated data:" OBJ.J LENVMEM JRECLEN / D 0 GOTO DO JVIEW1 ; : JVIEW1 CR ."Trans= " ILS .D SP IWS BR N_BHR ."Behav.=" N_VAL ."AddrVal=" N_KH ."Knowhow=" ELSE ."?????? =" ILS SP .D SP JDATAV1 ; : JDATAV1 S( BASE@ ) B10 IWS IBS IBS 2 TON #. TOB 2 TON #. TOB 4 TON SP SP #: POS2 #: POS2 #. POS2 # IWS 4 TON TOB ; : POS2 [B] IBS 2 TON TOB ; [Определить размер объекта в памяти = заголовок + данные] : SIZEMEMOBJ [N] C PrioQueOID BR0 T0 SMEMO1 [0/size] ; : SMEMO1 3 Channels !NCHAN LENVMEM HSIZE+ HSIZE+ SZ_HDROBJ + [size] ; 7.7 Выполнение действий PROGRAM $M3 [Выполнение действий (knowhow)] FIX 1000 BYTE VCTR BUFTXT [Буфер для текста действий] FIX LONG VAR ABUF : BEGABUF 0 ' BUFTXT ! ABUF ; : RUNCMD [OID_KH] BEGABUF "KH$" S2BUF N2BUF ABUF BEGABUF ABUF E2 C2 - TEXEC ; : MAKECMD [OID_KH] BEGABUF ": KH$" S2BUF C N2BUF # ABUF !TB !1+ ABUF COPY2BUF_STR " ; " S2BUF ABUF BEGABUF ABUF E2 C2 - TEXEC ; : S2BUF [A L] DO S2BUF1 D ; : S2BUF1 C @B ABUF !TB !1+ ABUF 1+ ; : N2BUF [N] 8 DO CTN-SB D 8 [C1 Cn n] DO CTB ; : CTN-SB [N] C 0F & #0 + E2 -4 SHT [C N'] ; : CTB ABUF !TB !1+ ABUF ; LONG VAR OIDK : NEW_VOC "PROGRAM $KH_VOC" TEXEC ; : RUN_KH [OID_KH] NEW_VOC C MAKECMD RUNCMD ; 7.8 Кэширование объектов PROGRAM $LS_CASH [ Каналы: 1 - Header M.Obj 2 - Header D.Obj 3 - M.Data 4 - D.History ] [Считаем, что все объекты -- стабильные] : LOADOBJ [OID] C FINDOID [искали в кэше] C BR- LOADOBJ-1 DD ; : LOADOBJ-1 D [OID] [Ищем в каталоге БД объект] [C] LOADOBJ1 [LOADOBJ2] LenPrioQue 1- HIPRIO1 [] ;
: LOADOBJ1 6 LOADOBJ3 ; [открыть дисковый объект в кэше] : LOADOBJ3 [OID NDIRCH] EL_FIND [OID 1/0] IF0 O_NOTFND [Нет такого объекта] C LenPrioQue 1- ! PrioQueOID [Занесли в кэш идентификатор объекта] ILS [OID ADDR_MEM] [получили адрес размещения в дисковой памяти]
LenPrioQue 1- PrioQueNUM [получили номер отведенной для работы с объектом группы каналов] [OID ADDR_MEM NUM] C 2 Channels [OID ADDR_MEM NUM CHANOBJ] NCHAN NBASECH - !NCHAN [получили номер базового канала] C3 GOTO LCTX [OID ADDR_MEM NUM] [загрузили заголовок дискового объекта] E2D [O N] C 4 Channels [OID NUM CHANHIST] [получили канал для истории] G_HIS ILS [O N C HISTORY] [HISTORY д.б. 0] GOTO NCHAN E2 LCTX [Открыли историю в канале] !NCHAN [O N] C 3 Channels G_VAL ILS GOTO LCTX [временно открыли канал данных напрямую с жесткого диска] [LOADDM] NOP [Здесь нужно установиться на объект в памяти и канал данных перекл. на него] DD [] ; VAR NCHANDAT VAR NCHANOBJ LONG VAR LENDAT : COPY_DAT1 [] NCHANOBJ 0 GOTOC [NCHANOBJ] NCHAN 0 GOTO 8 DO_IOBSCC D 14 OLS 0 OLS 10 GOTOC NCHAN 4 DO_IOBSCC DD -1 OLS -1 OLS LENDAT OLS LENDAT OLS COPY_DAT ; : GOTOC [NCHAN n] C2 S( NCHAN ) !NCHAN GOTO [NCHAN] ; : COPY_DAT [] NCHANDAT NCHAN [SRC_CH DST_CH] C2 !NCHAN LENVMEM [SRC_CH DST_CH LEN] 0 GOTO DO_IOBSCC DD ;
8. Контрольный пример, демонстрирующий возможности технологии DB.NEW Создадим объект "Поведение клоуна" для клоуна [] "Поведение клоуна" CLONE_STR [oid_str] OIDSET GET_BHR CLONE [oid_str oid] SET_NAMEOBJ [oid] Создадим объект "Клоун": [ ] "Клоун" CLONE_STR [ oid_str] CLONE_AGG [ oid_str oid] SET_NAMEOBJ [ oid] Определим ему поведение [oid_bhr oid] SET_BHR Определим в нем поля: X, Y, Цвет "X" NEWFID SET_NAMEFID [fid] OIDINT "Клоун" NAMEOID AGG+F [] В ДССП можно определить новое слово : NEWFIELD [ "Имя объекта" "Имя поля"] NEWFID SET_NAMEFID [A L FID] OIDINT C4C4 NAMEOID AGG+F DD [] ; "Клоун" "Y" NEWFIELD "Клоун" "Цвет" NEWFIELD Создадим методы. Создать метод "Идти". "" CLONE_STR [oid_kh] [oid_kh] "Идти" CLONE_STR E2 C2 SET_KH [OID_STRKH] "Поведение клоуна" NAMEOBJ SET+E Аналогично создаются другие методы . Подготовка для вызова метода по идентификатору: "Идти" CLONE_STR C "Клоун" NAMEOBJ METHOD? E2 DELOBJ Подготовка для вызова метода по имени: "Идти" CLONE_STR Вызов [oid] 0 "Клоун" NAMEOBJ [oid_mth 0 oid_obj] SEND
9. Оценка трудоемкости разработки ПО с использованием традиционного и предлагаемого подходов В этом разделе будет проведен качественный анализ трудоемкости. Это связано, прежде всего, с особенностью языка реализации, отличного от классических ЯВУ. Далее, в качестве примера, рассматривается следующая задача: Клиенты имеют счета. Каждый счет увеличить на 10% и после этого пометить пользователя как получившего премию. 9.1 Табличные базы данных с низкоуровневыми операциями доступа В качестве примера можно привести FoxPro 2.6 [11]. В ней есть недостаточное для обычных нужд подмножество SQL (SELECT, INSERT INTO); обычно взаимодействие с БД происходит с помощью операторов REPLACE, SCATTER, GATHER, SCAN … ENDSCAN и непосредственного присвоения с указанием в качестве префикса поля имени области, в которой открыта таблица. Такие программы практически непереносимы на клиент-сер­верные технологии, логика программ весьма сложна и приводит при программи­ро­ва­нии к трудно обнаруживаемым ошибкам. Достоинствами же являются простота реа­ли­зации языка таких СУБД и малая требовательность к ресурсам. Программный код обработки (MS FoxPro 2.6): SELECT CLIENT SCAN SELECT SCHET REPLACE SUMMA WITH SUMMA*1.1 FOR SCHET.NUM_SCH=CLIENT.NUM_SCH SELECT CLIENT REPLACE PREMIA WITH .T. ENDSCAN 9.2 Реляционные базы данных Реализация языка SQL позволяет работать с базой данных исключительно средствами SQL. Поддерживаются триггеры, отношения между таблицами, хранимые процедуры. Это типичные клиент-серверные СУБД. Управление целостностью данных возлагается на СУБД. Триггеры позволяют вынести практически все проверки из логики программы. Недостатком является необходимость нормализации таблиц, что затрудняет добавление новых таблиц при сопровождении программного средства, а иногда требует перенор­ма­лизации, что влечет за собой необходимость изменять программный код, а значит, и новые ошибки. Программный код обработки (MS Visual FoxPro 3.0 и выше): BEGIN TRANSACTION UPDATE SCHET SET SUMMA=SUMMA*1.1 WHERE NUM_SCH IN (SELECT NUM_SCH FROM CLIENT) UPDATE CLIENT SET PREMIA = .T. ENDTRANSACTION 9.3 Объектно-ориентированные базы данных Позволяют хранить данные произвольной степени сложности (детали САПР) и вида (звук, изображение). Позволяют программировать на уровне инфологической модели, т.е. исчезают заботы о нормализации. Новые алгоритмы могут работать одновременно со старыми, обеспечивая преемственность. Например, если бухгалтерские проводки в следующем году проходят по новой схеме, переход на нужную схему в зависимости от даты СУБД выполнит сама. Реализация для ООБД на формальном языке: {«*»(1.1) ~> psumma(sClient.num_sch=Schet.num_sch(Schet, Client)), «:=»(True) ~> pPremia(Client)} Порядок действий: 1 Умножение счетов на 1.1 1.1 Операция селекции выбирает множество счетов 1.2 Операция проекции выбирает интересующую часть счета – сумму 1.3 На суммы посылается операция «умножить» с аргументом 1.1 2 Пометка клиентов, как получивших премию 2.1 Операция проекции выделяет интересующую часть информации о клиенте – атрибут «премия» 2.2 Операция присвоения посылается на выделенный атрибут «премия» с аргументом True Примечание 1: В операция селекции и проекции имеется некоторое отличие от операций реляционной алгебры. Например, операция проекции, выбирающая сумму, возвращает множество сумм. На самом деле множество сумм содержит не суммы, а иденти­фи­ка­торы атомарных объектов, хранящих суммы. Поэтому множество может содержать не­сколько одинаковых сумм и не теряется связь данных с оригинальным объектом-хранителем (счетом). Примечание 2: Оба изменения происходят в пределах одной транзакции, посколь­ку эти действия являются экземплярами одного множества. Оба порядка дейст­вий: «сначала умножить, потом – пометить» и «Сначала пометить, потом – умножить» равно­правны, поскольку действия хранятся в множестве. Если порядок ва­жен, т.е. второе воздействие использует результат первого, то необходимо исполь­зовать не множество, а после­дова­тельность.
Операции над сложными структурами транзитивно распространяются на опера­ции над компонентами по алгоритмам, описанным выше в разделе «Уточнение методов решения задачи». Таким образом, нет нужды во многих случаях писать циклы, обработку вло­жен­ных структур. Использование итераторов позволяет создавать собст­венный алго­ритм выбора элементов для обработки циклов.
9.4 Будущее применения различных баз данных В прошлые годы много внимания уделялось вопросу трудоемкости разработки програм­много обеспечения. Возросшая сложность программ и объемы используемых данных не позволяют начать разрабатывать новый продукт «с нуля». Теперь вперед выходят технологии, позволяющие создавать легко сопровождаемые программы. Но реляционные базы данных, скорее всего, по-прежнему останутся в качестве недорогих средств разработки приложений и, во многих случаях, естественных средств представления предметной области, подобно радио и кино, которых не вытеснило телевидение.
10. Литература [1] О.И.Авен Я.А.Коган “Управление вычислительным процессом” М. Энергия 1978 [2] А.М.Андреев Д.В.Березкин, Ю.А.Кантонистов «Среда и хранилище: ООБД» Мир ПК №4 1998 (стр 74-81) [3] М. Аткинсон, Ф. Бансилон и др. «Манифест систем объектно-ориентированных баз данных», СУБД № 4 1995 [4] В.Бобров "Объектно-ориентированные базы данных, мультимедийные типы данных и их обработка" Read.Me №4, 1996 [5] Н.П.Брусенцов, В.Б.Захаров и др. «Развиваемый адаптивный язык РАЯ диалоговой системы программирования ДССП» Москва МГУ 1987 [6] Бурцев А.А "Параллельное программирование. Учебное пособие по курсу "Операционные системы" - Обнинск : ИАТЭ, 1994 - 90 с. [7] Бурцев А.А. «Сопрограммный механизм в ДССП как основа для построения мониторов параллельных процессов» [8] Г.Буч «Объектно-ориентированное проектирование (с примерами применения)» М.Конкорд 1992 [9] К.Дж.Дейт «Введение в системы баз данных» 1998 Киев Диалектика [10] Мутушев Д.М. Филиппов В.И. "Объектно-ориентированные базы данных" Программирование. - М., 1995 №6 стр. 59-76 [11] В.Ремеев «FoxPro. Версия 2.5 для MS-DOS. Описание команд и функций» М. «Мистраль» 1994 [12]СУБД № 2 1995 «Системы баз данных третьего поколения: Манифест» [13]СУБД № 1 1996 «Стандарт систем управления объектными базами данных ODMG-93: краткий обзор и оценка состояния» Л.А.Калиниченко [14]СУБД № 1 1996 «ТРЕТИЙ МАНИФЕСТ» Х.Дарвин, К.Дэйт [15]СУБД № 5-6 1996 “Введение в СУБД часть 9” стр. 136-153 С.Д. Кузнецов [16]Data & Knowledge Engineeging №15 (1995) стр 169-183 “Selection of object surrogates to support clustering” Jukka Teuhola [17] Data & Knowledge Engineering. Amsterdam 1996 Том 18 №1 стр.29-54 "Unifying data, behaviours, and messages in object-oriented databases" Sylvia L. Osborn, Li Yu [18] IEEE Transactions On Knowledge And Data Engineering Том 7 №2 Апрель 1995 стр. 274-292 «Security Constraint Processing in a Multilevel Secure Distributed Database Management System» B.Thuraisingham, W.Ford [19] Journal of systems and software - N.Y., 1996 Том 35 №3 стр. 169-183 Shah P. Wong J. "Concurency control in a object-oriented data base system" Документы в Internet (http://www.citforum.ru): [20] В. Индриков, АО ВЕСТЬ “Объектно-ориентированный подход и современные мониторы транзакций” [21] Л.Калиниченко “Архитектуры и технологии разработки интероперабельных систем”, Институт проблем информатики РАН [22] С.Д. Кузнецов "Основы современных баз данных" [23] С. Кузнецов “Безопасность и целостность, или Худший враг себе - это ты сам”