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

САНКТ-ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

На правах рукописи

РГБ ОД

* - к ПРИ

Павлопа Екатерина Юрьенна "

НЕКОТОРЫЕ АСПЕКТЫ ПОДДЕРЖКИ ЦЕЛОСТНОСТИ В БАЗАХ ДАННЫХ

05.13.11 - Математическое и программное обеспечение вычислительных машин, комплексом, систем и сетей

АВТОРЕФЕРАТ

диссертации на соискание ученой степени кандидата физико-математических паук

Санкт-Петербург 2000

Работа выполнена на кафедре исследования операций математико-механического факультета Санкт-Петербургского Государственного Университета.

Научный руководитель: доктор физико-математических наук,

профессор Б. А. Новиков

Официальные оппоненты:

доктор технических паук, профессор С. Д. Кузнецов кандидат физико-математических наук, доцент Ф. А. Новиков

Ведущая организации: Институт проблем информатики

Российской Академии Наук

Защита диссертации состоится иЛ1 " (цг^П&рА_ 2000 года

в часов на заседании диссертационного совета К 063.57.54

но защите диссертаций на соискание ученой степени кандидата наук в Санкт-Петербургском государственном университете по адресу 198904, Санкт-Петербург, Старый Петергоф, Библиотечная пл., 2.

С диссертацией можно ознакомится в Научной библиотеке Санкт-Петербургского государственного университета но адресу: 199034, Санкт-Петербург, Университетская наб. 7/9.

Автореферат разослан " "_2000 года.

Ученый секретарь диссертационного совета

доктор физико-математических наук Б. К. Маргыненко

Общая характеристика работы

Актуальность темы

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

Термин целостность используется для описания точности и корректности данных, хранящихся в базе данных. Для поддержки целостности система должна содержать информацию о тех правилах (ограничениях), которые пользователю не следует нарушать. Кроме того, система управления базами данных, в свою очередь, должна следить за соблюдением заданных правил, в том числе и при параллельной работе с базой данных [4, 7, 10, 1, 2].

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

Так, например, изменение требований предъявляемых к СУБД в системах реального времени [11, 13] влечет за собой необходимость пересмотра и дополнительных исследований во многих областях теории БД, включая вопросы поддержки целостности и, как следствие, протоколы управления транзакциями [23, 2G, 13, 29]. Поскольку методы, применяемые в классических СУБД, совершенно не учитывают особенностей систем реального времени, то для полноценного использования системы управления базами данных в таких системах зачастую необходимо использовать совершенно другие алгоритмы, опираясь на предоставляемые системой реального времени возмож-

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

В последние годы все больше внимания привлекают системы баз данных для слабоструктурированной информации [9]. Методы работы со слабоструктурированной информацией обсуждались многими исследователями [15, 16, 17, 20, 21, 3]. Однако, динамические аспекты работы со слабоструктурированной информацией практически затрагивались крайне редко. В частности, вопросы связанные с согласованностью слабоструктурированной информации практически не обсуждались. Таким образом, изучение возможных подходов к определению согласованности для слабоструктурированных данных является актуальной темой.

Актуальной задачей является также применение формальных методов [14, 18] для доказательства тех или иных свойств системы управления базами данных. Формальные доказательства особенно важны для методов поддержки целостности данных, поскольку они позволяют гарантировать формальную корректность методов поддержки целостности данных.

Цели работы

Изучить вопросы, связанные с поддержкой целостности в системах баз данных в двух новых областях применения СУБД — системах баз данных реального времени и системах баз данных для слабоструктурированной информации. А именно:

• предложил, алгоритмы управления транзакциями, учитывающие специфику систем реального времени;

• построить формальную модель СУБД реального времени;

• доказать корректность работы транзакций в СУБД реального времени в рамках построенной формальной модели;

• разработать систему понятий, пригодных для описания условий согласованности в СУБД со слабоструктурированной информацией.

Общая методика

Изучались особенности специализированных систем реального времени, которые далее использовались для создания эффективных алгоритмов управления транзакциями. Формальная спецификация СУБД реального времени проводилась в рамках Duration Calculus, являющегося расширением интервальной логики. Анализировалось представление понятий, связанных с целостностью информации, используемых в структурированных базах данных с целью получения их обобщенного представления в слабоструктурированпых окружениях.

Основные результаты

В работе получены следующие основные результаты:

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

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

• Построено формальное описание систем баз данных реального времени и критериев корректности в терминах временной логики.

• Построена классификация ограничений целостности для слабоструктурированной информации.

• Получены предикаты коммутативности для базовых операций языка обработки слабоструктурированных данных.

Научная новизна

Все основные научные результаты диссертации являются новыми.

Практическая и теоретическая ценность

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

Апробация работы

Результаты диссертации докладывались на семинаре московской секции ACM SIGMOD, на конференциях по исследованиям в области баз данных (ADBIS'97, Санкт-Петербург, Россия и ADBIS'98, Познань, Польша), электронным библиотекам (DL'2000, Протвино, Россия), формальным методам (APSEC'99, Такаматсу, Япония). Часть результатов была опубликована в журнале "Программирование".

Публикации

Основные результаты диссертации изложены в семи работах [28, 29, 30, 31, 32, 33, 34], перечисленных в конце автореферата.

Структура и объем диссертации

Диссертация состоит из 5 глав со сквозной нумерацией разделов, рисунков и таблиц. Текст диссертации изложен на 98 страницах. Список литературы содержит 67 наименований.

Содержание работы

В первой главе вводятся основные понятия, связанные с вопросами поддержки целостности в БД. Приведен краткий обзор сущесгвую-

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

Здесь также кратко описан Duration Calculus (DC), представляющего собой логический подход, в основе которого лежит интервальная логика [12]. Временная логика очень удобна для описания различных свойств систем реального времени, и поэтому широко используется для этих целей. DC является расширением интервальной логики, где в качестве свойств рассматривается единственное свойство — продолжительность.

Описываются основные понятия, связанные с СУБД со слабоструктурированной информацией. В частности, описывается модель данных OEM [8].

Во второй главе рассматривается управление транзакциями для систем БД реального времени хранимых в оперативной памяти [5]. В рассматриваемой системе используется виртуальная память на базе физически распределенной реальной памяти. Подобные системы в последнее время привлекают много внимания [24, 25].

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

Кроме этого рассматриваемая система имеет ряд дополнительных особенностей:

• большинство транзакций очень короткие и только читающие;

• директивные сроки завершения транзакций очень короткие;

• элементы данных, используемые транзакциями, малы по размеру, но могут иметь сложную структуру.

Несмотря на то, что вся база целиком хранится в оперативной памяти, при таких предположениях применение классических спо-

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

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

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

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

В третьей главе изучаются вопросы управления транзакциями для вложенной модели в системах реального времени. Модель вложенных транзакций, правила и алгоритм управления транзакциями для данной модели транзакций были впервые предложены Эллиотом Моссом [22]. В отличие от классической модели, рассматривается модель, в которой все транзакции существенные.

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

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

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

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

Для проверки построенной модели было построено формальное описание двухфазного протокола блокирования и доказана его корректность.

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

Поскольку слабоструктурированпую информацию молено рассматривать, как обобщение структурированной [19], то одним из возможных подходов к определению и реализации согласованности является расширение традиционных моделей транзакций, разработан-

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

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

• ограничения целостности

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

• ограничения корректности данных

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

Затем рассматривается согласованность в рамках модели многоуровневых транзакций [27]. Согласованность обеспечивается на основе сериализуемости, которая зависит от свойств коммутативности операций манипулирования данными. Для этой цели определяются предикаты коммутативности для операций манипулирования слабоструктурированными данными, составляющими базис алгебры манипулирования данными. Предлагаемые предикаты не зависят от текущего состояния базы, что делает возможным их использование для априорной проверки коммутативности с целью эффективного планирования запросов.

Список литературы

[1] С. Д. Кузнецов. Введение в системы управления базами данных. СУБД, 2:110-124, 1995.

[2] С. Д. Кузнецов. Введение в СУБД: часть 7. СУБД, 3:136-148, 1996.

[3] М. Гринев. Системы управления полуструктурированными данными. Открытые системы, 05-06, 1999.

[4] К. Дейт. Введение в системы баз данных. Вильяме, 1999.

[5] Г.. Никитина. Управление данными, размещенными в оперативной памяти. Открытые системы, 1, 1999.

[6] Е. Павлова. Управление транзакциями в СУБД рояльного времени. Программирование, 2:41-58, 2000.

[7] Database Management Systems. The McGraw-Hill Companies, 199G.

[8] S. Abiteboul, D. Quass, J. McHugh, J. Widom, and J. Wiener. The Lore] query language for semistructured data. International Journal on Digital Libraries, 1:68-88, April 1997.

[9] Serge Abiteboul, Peter Buneman, and Dan Suciu. Data on the Web. Morgan Kaufmann Publishers, 1999.

[10] P. A. Bernstein, V. Hadzilacos, and N. Goodman. Concurrency Control and Recovery in Database Systems. Addison-Wesley, 1987.

[11] Azer Bestavros, Kwei-Jay Lin, and Sang Hyuk Son. Real-Time Database Systems: Issues and Applications. Kluwer Academic Publishers, 1997.

[12] Zhou Chaochen, C. A. R. Hoare, and Anders P. Ravn. A calculus of durations. Information Processing Letters, 40(5):269-276, 1991.

[13] Joakim Eriksson. Real-Time and Active Databases: A Survey. In Active, Real-Time, and Temporal Database Systems, Second International, ARTDB-97, pages 1-23, Como, Italy, September 1997.

[14] Schneider. F. On Concurrent Programming. Springer, 1997-

[15] M. Fernandez, D. Florescu, J. Kang, A. Levy, and D. Suciu. Strudel: a web-site management system. In Proc. of the ACM SIGMOD conference on Management of Data, 1997.

[16] Michael J. Franklin (ed.). Management of semi-structured data. SIGMOD Record, 26(4), 1997.

[17] H. Garcia-Molina, Y. Papakonstantinou, D. Quass, Y. Sagiv, J. Ullman, and J. Widom. The TSIMMIS approach to mediation: Data models and languages. In Proceedings of Second International Workshop on Next Generation Information Technologies and Systems, June 1995.

[18] Dang Van Hung. Modelling and verification of biphase mark protocols in Duration Calculus using PVS/DC. In Proceedings of the 1998 IEEE International Conference on Application of Concurrency to System Design (CSD'98), pages 88-98, Aizu-wakamatsu, Fukushima, Japan, March 1998.

[19] Gerti Kappel, Elisabeth Kapsammer, and Werner Retschitzegger. X-Ray - Towards Integrating XML and Relational Database Systems. Technical report, Johannes Kepler University Linz, July 2000.

[20] Giansalvatore Mecca and Paolo Atzeni. Cut and paste. Journal of Computer and System Sciences (JCSS), 58(3):453-482, 1999.

[21] Giansalvatore Mecca, Paolo Merialdo, Paolo Atzeni, and Valter Crescenzi. The (short) Araneus guide to \veb-sit,e development. In Proc. ot the WebDB, pages 13-18, 1999.

[22] J. E. В. Moss. Nested Transactions: An Approach to Reliable Distributed Computing. PhD thesis, MIT Press, Cambridge, MA, 1985.

[23] K. Ramamritham. Real-time databases. International Journal of Distributed and Parallel Databases, 1(1), 1992.

[24] R. Schmidt, J. Chase, and H. Levy. Using Shared Memory for Read-Mostly RPC Services. In Proceedings of the 29th Hawaii International Conference on System Sciences, January 1996.

[25] Marc Shapiro and Paulo Ferreira. Larchant-RDOSS: a Distributed Shared Persistent Memory and its Garbage Collector. In Proceedings of the 9th International Workshop on Distributed Algorithms, September 1995.

[2C[ J. Stankovic, S. H. Son, and J. Hansson. Misconceptions about real-time databases. IEEE Computer, 32(G):29-3G, June 1999.

[27] G. Weikuin. Principles and realization strategies of multilevel transaction management. ACM Transactions on Database Systems, 16(1):132-180, March 1991.

Работы автора по теме диссертации

[28] Е. А. Горшкова, И. С. Некрестьянов, Б. А. Новиков, Е. Ю. Павлова. Поддержка согласованности для елабоструктурированных данных. Программирование, 3:23-30, 2000.

[29] Е. Павлова. Управление транзакциями в СУБД реального времени. Программирование, 2:41-58, 2000.

[30] I. Nekrestyanov, В. Novikov, and Е. Pavlova. Constraints for semistured data. In Proc. of the Russian DL'2000, pages 214-219, Protvino, Russia, September 2000.

[31] Igor Nekrestyanov, Boris Novikov, and Ekaterina Pavlova. Designing persistence for real-time distributed object systems. In

Proceedings of the second East European symposium on advances in Databases and information systems (ADBIS'98), pages 248-259, Poznan, Poland, September 1998.

[32] Igor Nekrestyanov, Boris Novikov, Ekaterina Pavlova, and Serge Pikalev. Concurrency control protocols for persistent shared virtual memory systems. In Proceedings of the Second International Workshop on Advances in Databases and Information Systems (ADBIS"97), volume 1, pages 35-40, St. Petersburg, Russia, September 1997.

[33] Igor Nekrestyanov and Ekaterina Pavlova. Concurrency control protocol for nested transactions in real-time databases. In Proceedings of the Second International Workshop on Advances in Databases and Information Systems (ADBIS"97), volume 1, St. Petersburg, Russia, September 1997.

[34] Ekaterina Pavlova and Van Hung Dang. A formal specification of the concurrency control in real-time databases. In Proceedings of the 6th Asia-Pacific Software Engineering Conference (APSEC'99), Takamatsu, Japan, December 1999.

Санкт-Петербургский государственный университет

ЯГБ ОД

На правах рукописи

Жильцов Андрей Евгеньевич

Организация электронной библиотеки с учетом принципов оптимизации реляционных СУБД

Специальность 05.13.11 - "Математическое и программное обеспечение вычислительных машин, комплексов, систем и сетей "

Автореферат диссертации на соискание ученой степени кандидата технических наук

Санкт-Петербург - 2000

Работа выполнена в Санкт-Петербургском государственном университете, на факультете Прикладной математики - процессов управления.

Научный руководитель -кандидат физико-математических наук, доцент

Официальные оппоненты: доктор физико-математических наук, профессор кандидат физико-математических наук

Ведущая организация -Институт прикладных математических исследований Карельского научного центра Российской академии наук

Защита диссертации состоится «22 » цочГй^а 2000 г. в Л часов на заседании Диссертационного Совета К-063.57.48 по защите диссертаций на соискание ученой степени кандидата технических наук в Санкт-Петербургском государственном университете по адресу: 199004, Санкт-Петербург, В.О., 10-я линия, д.ЗЗ, ауд. 39.

С диссертацией можно ознакомиться в библиотеке имени А.М.Горького Санкт-Петербургского государственного университета по адресу: 199034, Санкт-Петербург, Университетская наб., 7/9.

Автореферат разослан «¿7 » ря 2000 года.

Ученый секретарь Диссертационного

Совета, кандидат технических наук М.А.Галактионов

С.Л.Сергеев.

И.Л.Братчиков, А.Н.Кривцов

Общая характеристика работы

Актуальность темы. Работа посвящена разработке структуры организации электронной библиотеки (в дальнейшем ЭБ) и поиску оптимальньтх методов доступа к хранимой в ней информации. Необходимость решения такой задачи вызвана наступлением информационной революции, в частности, повсеместным распространением электронной печати и развитием технологии World Wide Web, позволяющей получать доступ к информации, находящейся на удаленных компьютерах. В настоящее время электронное информационное пространство стремительно развивается, образуя как бы параллельный мир традиционной коммуникационной инфраструктуре. Библиотеки, как одни из ведущих субъектов информационной деятельности, должны быть готовы испытать качественные преобразования под воздействием новых условий.

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

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

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

Научная новизна и практическая значимость. Предлагаемый в диссертации метод, по мнению автора, впервые реализует полнофункциональную ЭБ с применением современных технологий, обеспечивая ее доступность и удобство для пользователей, достаточно высокую скорость операций поиска и выдачи информации. В отличие от большинства представленных сети Internet публичных и научных библиотек, ограничивающихся опубликованием электронного каталога, который зачастую является неполным, малофункцнональным и неудобным, предлагаемый метод реализует все привычные для пользователя функции обычной библиотеки. Разработанная схема проектирования может быть использована как для построения библиотечного сервера в компьютерной сети, так и для организации личной электронной библиотеки на персональной ЭВМ.

Апробация работы. На основе предложенного метода спроектирована реляционная база данных с использованием СУБД Paradox и написана программа на языке С++ с применением среды Borland С++ Builder. Разработанный проект внедрен в эксплуатацию в мае 2000 г. в Институте по болезням уха, горла, носа и речи (г. Санкт-Петербург) для автоматизации медицинской научной библиотеки.

Публикации. По основным вопросам диссертации опубликованы 2 работы, список которых приведен в конце автореферата.

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

Содержание работы

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

Функция хранения в обязательном порядке подразумевает хранение библиотечного каталога в электронной форме. Наиболее удобный способ организации каталога ЭБ заключается в создании базы данных (БД) реляционного типа. При этом каждому объекту библиотеки сопоставляется запись в таблице, которая содержит атрибуты, характерные для обычного, неэлектронного каталога. Хранение фондов ЭБ, в идеале, также должно быть полностью организовано на ЭВМ - каждый библиотечный объект представляется в виде файла.

Организация доступа к ЭБ подразумевает обращение к электронному каталогу в поисках необходимого объекта из хранилища, которое осуществляется при помощи программы. Предоставляемый программой интерфейс позволяет сформулировать запрос по отдельному атрибуту каталога или их совокупности. Так как каталог ЭБ представляет собой БД, то для обращения к нему можно использовать СУБД, которая уже предлагает набор базовых методов для выполнения запроса. По выбранным из каталога ссылкам программа предоставляет доступ к хранилищу.

Администрирование ЭБ заключается в обеспечении программой

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

Схема предлагаемой модели ЭБ изображена на рис. 1.

пользовательские процессы служебные процессы

Рис. 1.

Электронное хранилище в простейшем варианте представляет собой набор обычных файлов, размещенных в одном из каталогов (или в иерархии каталогов) на жестком магнитном или оптическом носителе

ЭВМ. Более сложные способы хранения информации могут использовать упакованные алгоритмами сжатия файлы или файлы специального формата.

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

1. Основные атрибуты издания: автор, название, год издания, издательство, источник;

2. Атрибуты оригинала: автор оригинала, название оригинала, год издания оригинала, издательство оригинала, источник оригинала;

3. Дополнительные атрибуты: резюме, библиография (количество ссылок);

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

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

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

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

Предложенная реляционная модель реализует все функции библиотечного каталога. Для пользователя библиотеки можно организовать поиск по каталогу, формируя при помощи СУБД запрос к базе и выдавая результаты обработки этого запроса. Персонал библиотеки (администратор) может вносить изменения в каталог, добавляя, удаляя или редактируя записи.

Оптимизация предложенной модели заключается в достижении наиболее удобной организации данных и "наилучшем" выполнении запросов к ним. Для разработки первой задачи решаются проблемы физического и логического проектирования реляционной БД. Процесс выбора структуры для хранения информации, ее пошагового приведения к третьей НФ показан на примере использования СУБД Paradox. Критерием оптимизации при проектировании БД являлась минимизация ресурсов, необходимых для хранения информации при приемлемом предполагаемом времени выполнения запросов. Это достигалось путем исключения хранения пустых полей (особенно строкового типа Alpha и типа Memo, под которые необходимо выделять значительный объем памяти). Для этого были созданы таблицы "оригиналы", "источники", "файлы" и "темы", а также поля логического типа "перевод", "часть" и "темы" в основной таблице "каталог" для сигнализации о необходимости обращения к новым таблицам. Кроме того, производились замены повторяющихся строковых данных косвенными обращениями к ним по номеру-коду; для этого используются таблицы "языки", "носители", "сиисоктем". При распределении данных между основными и Memo файлами мы старались сократить предполагаемое время доступа к информации, учитывая характеристики объектов среднестатистической

библиотеки. Сохранение поля "автор" в таблице "каталог" при наличии таблицы "авторы" диктуется экономией времени при выполнении запросов к БД с большим количеством записей при поиске автора издания и выдаче ответов на запрос пользователя. В результате была получена такая структура БД каталога ЭБ (символом "*" отмечены первичные ключи таблиц):

Таблица КАТАЛОГ Таблица ОРИГИНАЛЫ

ун индекс* n

автор м40

название м50

год а4

издательство м50

резюме м1

библиография 5

код языка б

код носителя 8

перевод ь

часть ь

темы ь

Таблица АВТОРЫ

ун индекс* n

номер списка* 8

автор а20

Таблица НОСИТЕЛИ

код носителя* 8

носитель а10

Таблица ФАЙЛЫ

ун индекс* n

имя файла м50

ун индекс* n

название оригинала м50

год оригинала а4

издательство оригинала м50

источник оригинала м80

Таблица А НТО Р ЫО Р И Г ИII АЛОВ

ун индекс* n

номер списка* 8

автор оригинала а20

Таблица ИСТОЧНИКИ

ун индькс* n

источник м80

Таблица ЯЗЫКИ

код языка* 8

язык а15

Таблица ТЕМЫ

ун индекс* n

код темы* я

Таблица СПИСОК_ТЕМ

код темы* б

название темы мзо

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

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

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

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

SELECT списоктем .нлзвлние_темы

FROM списоктем. (1)

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

Пусть поле "тема" формы запроса содержит набор "tt,t2,...,t„", где каждая тема t,,i = \,m является элементом множества, полученного запросом (1), и t,*tj при i*J,Vi,j = l,m. Этому набору сопоставляется список кодов тем из таблицы "СПИСОК_ТШ'\ через который производится выборка множества R, уникальных индексов из таблицы "ТЕМЫ":

SELECT DISTINCT ТЕМЫ.УНИНДЕКС FROM ТЕМЫ, СПИСОК_ТЕМ WHERE

ТЕМЫ.КОД_ТЕМЫ = СПИСОК_ТЕМ.КОД_ТЕМЫ AND

СШ1СОК_ТЕМ.НАЗВЛ1ШЕ_ТЕМЫ IN (t,,l2,...,l„). (2)

Обозначим содержимое полей формы запроса "название" н "издательство" соответственно через h и р, а интервал "года издания" -через [у, >] (год издания не ранее у и ire позднее у). В общем виде запрос

на поиск по названию, издательству и интервалу года издания по таблице "КАТАЛОГ" имеет вид:

SELECT КАТЛЛОГ.УН_ИНДЕКС

FROM КАТАЛОГ

WHERE

КАТАЛОГ.НАЗВАНИЕ LIKE %/;% AND

КАТАЛОГ.ИЗДАТЕЛЬСТВО LIKE % р % AND

Y (КАТАЛОГ.I ОД_ИЗДАНИЯ, у, у), (3)

где ограничение Г на год издания определяется так:

У, У

F BETWEEN у AND у, 3у,у.у_* у F = >', 3 у, у. у = v 1~>у, 3у,Эу F <~у, 3у,3у

(4)

Обозначим полученное в результате (3) множество через Кс.

Теоретические расчеты и результаты практических исследовании доказывают преимущества использования таблицы "АВТОРЫ" для

выполнения запроса по заданному набору авторов a,,i = 1,и:

SELECT DISTINCT АВТОРЫ.УН_ИНДЕКС

FROM АВТОРЫ

WHERE АВТОРЫ.АВТОР LIKE %«,%. (5)

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

множеством Ra - Р| Rtl .

i-i

Запросы (2), (3) и (5) можно выполнять параллельно, что позволит увеличить общую скорость получения ответа. Пересечение трех полученных множеств даст множество уникальных индексов R = /?, П R, П /?,, на котором через (6) будет сформирован ответ на стандартный запрос:

SELECT

КАТАЛОГ.УН_ИНДЕКС, КАТАЛОГ.АВТОР, КАТАЛОГ.НАЗВАНИЕ, КАТАЛОГ.ГОД, КАТАЛОГ.ИЗДАТЕЛЬСТВО

FROM КАТАЛОГ, R

WHERE КАТАЛОГ.УН ИНДЕКС = R ,УН_ИНДЕКС.

(6)

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

упомянутых при описании стандартного запроса операций, содержащиеся в полях формы логические выражения приводятся к ДНФ. Алгоритм заключается в последовательном выполнении операций конъюнкции для всех составных операндов с учетом приоритета на основе дистрибутивного закона, а также в нахождении и исключении дубликатов конъюнктивных групп с точностью до перестановки операндов в группе. Приведенное к ДНФ логическое выражение преобразуется к запросу SQL: условия для операндов внутри каждой конъюнктивной группы соединяются оператором "AND", а сами группы - оператором "OR". Тогда ограничение G на поле F таблицы БД, удовлетворяющее нормализованному

логическому выражению X = \J<j~}x,j, будет иметь вид

G(F,X) = (F LIKE %х,,% AND F LIKE %xr% AND...AND F LIKE %x]n %) OR (F LIKE %x2l % AND F LIKE %.v2, % AND...AND F LIKE%xlm %) OR

(F LIKE %.v-„„ % AND F LIKE %xml % AND...AND F LIKE %). (7)

Пусть поле "источник" формы запроса содержит нормализованное логическое выражение вида = - Тогда множество индексов л,

1=1 j.i

удовлетворяющих выражению S объектов будет определяться запросом

SELECT ИСТОЧНИКИ. УН J1НДНКС FROM ИСТОЧНИКИ

WHERE G(HCT04HHKIi.IiCT04HIIK, S). (8)

Пусть поле "автор" формы расширенного запроса содержит

приведенное к ДНФ выражение = , где .(, • Для каждой

¡-1 /=i

конъюнктивной группы А, будем выполнять алгоритм, используемый для обработки поля "автор" стандартной формы запроса: для каждого фиксированного / = 1,и получать набор уникальных индексов R, как результат пересечения п, запросов

SELECT лвторы.униндекс FROM авторы

WHERE ЛВТОРЫ.ЛВТОР LIKE %чч %. (9)

Объединение наборов индексов по всем группам дает множество

уникальных индексов объектов, удовлетворяющих запросу по

¡=1

полю "автор". Если выставлен флаг "наличие оригинала", то проведем аналогичную обработку поля формы "автор оригинала", содержащего

выражение А" =иП"</ > с получением множества R",:

i-i j=I

SELECT авторыоригиналов.уннндекс

FROM авторыоригиналов

WHERE

лвторы_оригинллов.лвтор_орип1нллл LIKE %«;;%.

(10)

Для эффективного выполнения запросов в случаях, когда выставлены флаги "один автор" или "первый автор", введем правило заполнения поля номерсписка таблицы авторы: присваивать автору номер списка "0", если автор один, и номера "Г', "2",..., если авторов несколько. Выполняя запросы

SELECT лвторы.ун_индекс

FROM авторы

WHERE

авторы.автор LIKE %« , % AND

АВТОРЫ.НОМЕРСПИСКА - 0 (11)

для каждого = получаем т множеств уникальных индексов, объединение которых дает искомый набор объектов по полю "автор" формы запроса при выставленном флаге "один автор". При выставленном флаге "первый автор" последнее ограничение в (11) заменится на АВТОРЫ.НОМЕР_СПИСКА IN (0,1).

Пусть логическое выражение в поле "тема" формы запроса

т

приведено к виду Г = (J 7,, где Т: = Р) . Тогда, с учетом необходимости

обращения к каждой теме i. по ее коду, запрос для поиска уникальных индексов будет иметь вид

SELECT ТЕМЫ.УНИНДЕКС FROM ТЕМЫ, С11ИСОКТЕМ WHERE

ТЕМЫ.КОД_ТЕМЫ =■ СИ 11СОКТЕМ.КОДТЕМ Ы AND

сппсоктем.названиетемы = t... (12)

Для каждого Т, i ---1, m будем выполнять п, запросов (12). Пересечение полученных по каждому из них множеств уникальных индексов будет соответствовать выражению Т:. Объединяя полученные для каждого Т{ результаты по всем i = \,m, получаем множество индексов RT для содержимого поля "тема" расширенной формы запроса.

Пусть поля "название" и "издательство" расширенной формы запроса содержат соответственно нормализованные логические выражения

1! R! 1, __

// = UO. н /, = Uf>, > 11 задан интервал года издания: \y.y\- Набор

1-1 " .м ~

удовлетворяющих этим трем условиям объектов определяется множеством уникальных индексов Rv, полученным в результате запроса

SELECT КАТАЛОГ.УНИНДЕКС

FROM КАТАЛОГ

WHERE

G (КАТАЛОГ.НАЗВАНИЕ, Н) AND

G ( КАТАЛОГ.ИЗДАТЕЛЬСТВО, Р) AND

Y (КАТАЛОГ.ГОД_ИЗДАНИЯ, у, у), (13)

где ограт1чепия G и У задаются формулами (7) и (4) соответственно. Выставленный флаг "наличие оригинала" сигнализирует о необходимости обрабатывать поля расширенной формы запроса, относящиеся к оригиналу. Пусть поля "название оригинала", "издательство оригинала" и

"источник оригинала" содержат соответственно выражения вида /Г=0ПЛ,;, P"=UfW и а также указан интервал года

<=| j=1 /=i i=I j=\

издания оригинала [•>''>']• Тогда запрос к таблице "ОРИГИНАЛЫ"

выглядит так:

SELECT ОРИГШГАЛЫ.УН_ИНДЕКС

FROM ОРИГИНАЛЫ

WHERE

G ( ОРИГИНАЛ Ы.НАЗВАНИЕ_ ОРИГИНАЛА, Н") AND

G ( ОРИГИНАЛЫ.ИЗДАТЕЛЬСТВО_ ОРИГИНАЛА, Р°) AND

G( ОРИГ1ШАЛЫ.ИСТОЧНИК_ ОРИГИНАЛА, 5")

AND _

У ( ОРИ ГШ Ь\ЛЫ.Г()Д^ИЗД/\НИЯ_ОРИГШШ1А, v'J ), (14)

где ограничения G и У задаются формулами (7) и (4) соответственно. Полученное множество уникальных индексов обозначим R".

В результате выполнения (8)-(14) получаем набор множеств уникальных индексов. В общем случае, множество объектов, удовлетворяющих расширенному запросу пользователя, определяется множеством уникальных индексов ^А^П^П^П/^П-КсП/^. Аналогично стандартному запросу, необходимая информация для формирования краткого ответа пользователю выбирается из БД выполнением запроса (6).

Для обеспечения доступа к ЭБ по Internet наилучшим вариантом представляется организация публичной ЭБ на базе WWW-сервсра. Современные технологии Web-дизайна позволяют организовать удобный многоязычный интерфейс между пользователем и библиотечной программой. Этот же интерфейс решает проблемы многопользовательского доступа. Для локального доступа к библиотеке разработан графический интерфейс, обеспечивающий также выполнение функций администрирования.

Основные результаты работы таковы:

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

2. На основе построенной модели спроектирован каталог универсальной ЭБ с использованием СУБД Paradox с учетом принципов оптимизации реляционных СУБД и предполагаемых запросов.

3. Разработана схема доступа к каталогу ЭБ путем организации оптимальных запросов на языке SQL на основе заполняемых пользователем стандартной и расширенной форм запросов.

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

По теме диссертации автором опубликованы работы:

1. Жильцов А.Е. Подход к организации специализированных электронных библиотек. НИИ вычислит, математики и процессов управления. С.-Петерб. ун-т. С.-Петерб., 1999. Деп. в ВИНИТИ 16.12.99, № 3752-В99,-8 с.

2. Жильцов А.Е. Организация электронной библиотеки с учетом принципов оптимизации реляционных СУБД. С.-Петерб., 2000. http://andrezh.chat.ru

\

1 Поддержка целостности

1.1 Поддержка целостности в классических СУБД.

1.1.1 Пессимистический подход

1.1.2 Оптимистический подход.

1.1.3 Сравнение подходов.

1.2 СУБД реального времени.

1.2.1 Управление транзакциями.

1.2.2 Системы с устаревающими данными.

1.3 Слабоструктурированная информация.

1.3.1 Модель данных OEM.

1.4 Применение формальных методов.

1.4.1 Duration Calculus

2 Управление транзакциями в базах данных реального времени хранимых в оперативной памяти

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

2.1.1 Общий механизм работы.

2.2 Управление транзакциями для систем с виртуальной памятью

2.2.1 Модель.

2.2.2 Постановка задачи.

2.2.3 Мотивация.

2.2.4 Основная идея — "Грубый" подход.

2.2.5 Подход, основанный на версиях.

2.2.6 Вариации алгоритма и близкие вопросы

2.3 Сравнительный анализ.

2.3.1 "Грубый" подход и подход, основанный на версиях

2.3.2 Сравнение с другими алгоритмами

3 Управление вложенными транзакциями в БДРВ

3.1 Модель вложенных транзакций.

3.1.1 Алгоритм управления транзакциями для модели вложенных транзакций.

3.1.2 Преимущества модели.

3.2 Рассматриваемая модель.

3.3 Мотивировка.

3.4 Основные понятия.

3.5 Алгоритм.

4 Формализация систем БД реального времени

4.1 Базовая модель.

4.2 Сериализуемость.

4.3 Формализация двухфазного протокола блокирования

4.4 Модель системы БД реального времени

5 Целостность слабоструктурированных данных

5.1 Ограничения целостности.

5.1.1 Ограничения в структурированных БД.

5.1.2 Ограничения в слабоструктурированных БД

5.2 Ограничения корректности данных.

5.2.1 Временные ограничения

5.2.2 Описание ограничений корректности данных в существующих моделях.

5.3 Коммутативность операций над слабоструктурированными данными

5.3.1 Модель данных

5.3.2 Предикаты коммутативности.

Заключение

В работе получены следующие основные результаты:

• предложена серия оптимистических алгоритмов управления транзакциями в многопроцессорных системах реального времени специального вида. Основным достоинством предлагаемых алгоритмов является очень низкая дополнительная нагрузка на "только читающие" транзакции.

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

• Построено формальное описание систем баз данных реального времени и критериев корректности в рамках временной логики (Duration Calculus).

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

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

• Предложена классификация подходов к определению понятия согласованности для систем обработки слабоструктурированных данных.

1. Е. А. Горшкова, И. С. Некрестьянов, Б. А. Новиков, Е. Ю. Павлова. Поддержка согласованности для слабоструктурированных данных. Программирование, 3:23-30, 2000.

2. С. Д. Кузнецов. Введение в СУБД: часть 7. СУБД, 3:136-148, 1996.

3. А. Саймон. Стратегические технологии баз данных. Финансы и статистика, 1999.

4. М. Гринев. Системы управления полуструктурированными данными. Открытые системы, 05-06, 1999.

5. К. Дейт. Введение в системы баз данных. Вильяме, 1999.

6. Е. Павлова. Управление транзакциями в СУБД реального времени. Программирование, 2:41-58, 2000.

7. R. Abbott and Н. Garcia-Molina. Scheduling real-time transactions: A performance evaluation. In Procedings of the 14th VLDB Conference, August 1988.

8. R. Abbott and H. Garcia-Molina. Scheduling real-time transactions with disk resident data. In Procedings of the 15th VLDB Conference, August 1989.

9. S. Abiteboul. Querying semistructured data. In Proceedings of the International Conference on Database Theory, Delphi, Greece, jan 1997.

10. S. Abiteboul, D. Quass, J. McHugh, J. Widom, and J. Wiener. The lorel query language for semistructured data. Journal of Digital Libraries, 1(1), nov 1996.

11. S. Abiteboul, D. Quass, J. McHugh, J. Widom, and J. Wiener. The Lorel query language for semistructured data. International Journal on Digital Libraries, 1:68-88, April 1997.

12. S. Abiteboul and V. Vianu. Regular path queries with constraints. In Proc. of the PODS'1991, 1997.

13. Serge Abiteboul, Peter Buneman, and Dan Suciu. Data on the Web. Morgan Kaufmann Publishers, 1999.

14. Rakesh Agrawal, Michael J. Carey, and Miron Livny. Concurrency control performance modeling: alternatives and implications. ACM Transactions on Database Systems, 12(4):609-654, December 1987.

15. P. A. Bernstein, V. Hadzilacos, and N. Goodman. Concurrency Control and Recovery in Database Systems. Addison-Wesley, 1987.

16. Azer Bestavros and Spyridon Braoudakis. Timelines via speculation for real-time databases. In Proceedings of RTSS'94: The 14th IEEE Real-time Systems Symposium, San Juan, Puetro Rico, December 1994.

17. Azer Bestavros, Kwei-Jay Lin, and Sang Hyuk Son. Real-Time Database Systems: Issues and Applications. Kluwer Academic Publishers, 1997.

18. Angela Bonifati and Stefano Ceri. Comparative Analysis of Five XML Query Languages. SIGMOD Record, 29(1), March 2000.

19. Peter Buneman, Wenfei Fan, and Scott Weinstein. Path constraints on semistructured and structured data. In Proc. of the PODS'1998, June 1998.

20. Peter Buneman, Wenfei Fan, and Scott Weinstein. Interaction betwen path and type constraints. In Proc. of the PODS'1999, 1999.

21. M. J. Carey and M. R. Stonebraker. The performance of concurrency control algorithms for database management systems. In Proceedings of the 10th VLDB Conference, Singapore, August 1984.

22. R. G. G. Cattell, editor. The Object Database Standard: ODMG-93 (Release 1.2). Morgan Kaufmann Publishers, 1996.

23. Zhou Chaochen, C. A. R. Hoare, and Anders P. Ravn. A calculus of durations. Information Processing Letters, 40(5):269-276, 1991.

24. S. Chawathe, S. Abiteboul, and J. Widom. Representing and querying changes in semistructured data. In Proceedings of the Fourteenth International Conference on Data Engineering, February 1998.

25. Sophie Cluet and Tova Milo, editors. ACM SIGMOD Workshop on The Web and Databases (WebDB), Philadelphia, Pennsylvania, USA, June 1999.

26. Lee Dongwon and W. Chu Wesley. Comparative Analysis of Six XML Schema Languages. SIGMOD Record, 29(3), September 2000.

27. Curtis E. Dyreson, Michael H. Bohlen, and Christian S. Jensen. Capturing and querying multiple aspects of semistructured data. In Proc. of the 25th VLDB Conference, Edinburgh, Scotland, 1999.

28. Joakim Eriksson. Real-Time and Active Databases: A Survey. In Active, Real-Time, and Temporal Database Systems, Second International, ARTDB-97, pages 1-23, Como, Italy, September 1997.

29. K. Eswaran, J. Gray, R. Lorie, and I. Traiger. The notions of consistency and predicate locks in a database system. In ACM, November 1976.

30. Schneider. F. On Concurrent Programming. Springer, 1997.

31. M. Fernandez, D. Florescu, J. Kang, A. Levy, and D. Suciu. Strudel: a web-site management system. In Proc. of the A CM SIGMOD conference on Management of Data, 1997.

32. Mary Fernandez, Daniela Florescu, Alon Levy, and Dan Suciu. Verifying integrity constraints on web sites. In Proc. of the IJCAI'99, August 1999.

33. Michael J. Franklin (ed.). Management of semi-structured data. SIGMOD Record, 26(4), 1997.

34. D. Georgakopoulos. Multidatabase recoverability and recovery. In Proceedings of First International Workshop on Interoperability in Multidatabase Systems, Kyoto, Japan, April 1991.

35. R. Goldman and J. Widora. Dataguides: Enabling query formulation and optimization in semistructured databases. In Proceedings of the Twenty-Third International Conference on Very Large Data Bases, pages 436445, Athens, Greece, August 1997.

36. Michael R. Hansen and Zhou Chaochen. Duration calculus: Logical foundations. Formal Aspects of Computing, 9:283-330, 1997.

37. J. R. Haritsa, M. J. Carey, and M. Livny. Dynamic real-time optimistic concurrency control. In Procedings of the IEEE Real-Time Systems Simposium, Orlando, Florida, December 1990.

38. Lee Juhnyoung and H. Son Sang. Concurrency Control Algorithms for Real-Time Database Systems, chapter Performance of Concurrency Control Mechanisms in Centralized Database Systems, pages 429-460. Prentice-Hall, 1996.

39. Yaron Kanza, Werner Nutt, and Yehoshua Sagiv. Incomplete answers for queries over semistructured data. January 1999.

40. Gerti Kappel, Elisabeth Kapsammer, and Werner Retschitzegger. X-Ray Towards Integrating XML and Relational Database Systems. Technical report, Johannes Kepler University Linz, July 2000.

41. Woosaeng Kim and Jaideep Srivastava. Enhancing real-time dbms performance with multiversion data and priority based disk scheduling. In Proceedings of the 12th Real-time Systems Symposium, San Francisco, California, December 1991.

42. H. T. Kung and J. T. Robinson. On optimistic methods for concurrency control. ACM Transactions on Database Systems, 6(2), June 1981.

43. K. Lam, S. H. Son, V. Lee, and S. Hung. Using separate algorithms to process read-only transactions in real-time systems. In Proceedings of the IEEE Real-Time Systems Symposium (RTSS'98), pages 50-59, Madrid, Spain, December 1998.

44. A. Layman, E. Jung, E. Maler, H. J. Thompson, J. Paoli, J. Tigue, N. J. Mikula, and S. De Rose. XML Data. World Wide Web Consortium, 1998.

45. J. McHugh, S. Abiteboul, R. Goldman, D. Quass, and J. Widom. Lore: A database management system for semistructured data. Technical report, Database Group, Stanford University, feb 1997.

46. Jason McHugh and Jennifer Widom. Compile-time path expansion in lore. January 1999.

47. Giansalvatore Mecca and Paolo Atzeni. Cut and paste. Journal of Computer and System Sciences (JCSS), 58(3):453-482, 1999.

48. Giansalvatore Mecca, Paolo Merialdo, Paolo Atzeni, and Valter Crescenzi. The (short) Araneus guide to web-site development. In Proc. ot the WebDB, pages 13-18, 1999.

49. J. E. B. Moss. Nested Transactions: An Approach to Reliable Distributed Computing. PhD thesis, MIT Press, Cambridge, MA, 1985.

50. K. Ramamritham. Real-time databases. International Journal of Distributed and Parallel Databases, 1(1), 1992.

51. R. Schmidt, J. Chase, and H. Levy. Using Shared Memory for Read-Mostly RPC Services. In Proceedings of the 29th Hawaii International Conference on System Sciences, January 1996.

52. Marc Shapiro and Paulo Ferreira. Larchant-RDOSS: a Distributed Shared Persistent Memory and its Garbage Collector. In Proceedings of the 9th International Workshop on Distributed Algorithms, September 1995.

53. S. H. Son, S. Park, and Y. Lin. An integrated real-time locking protocol. In Eighth IEEE International Conference on Data Engineering, pages 527-534, Phoenix, Arizona, February 1992.

54. Sang H. Son, J. Lee, and Yi Lin. Hybrid protocols using dynamic adjustment of serialization order for real-time concurrency control. The Journal of Real-Time Systems, 4:269-276, 1992.

55. J. Stankovic, S. H. Son, and J. Hansson. Misconceptions about real-time databases. IEEE Computer, 32(6):29-36, June 1999.

56. Jeffrey D. Ullman. Principles Of Database And Knowledge-Base Systems. W.H. Freeman &: Company, 1988.

57. O. Ulusoy. Analysis of concurrency control protocols for real-time database systems. Technical Report BU-CEIS-9514, Bilkent University, 1995.

58. O. Ulusoy. Research issues in real-time database systems. Information Sciences, 87(1-3), November 1995.

59. O. Ulusoy and G. G. Belford. A performance evaluation model for distributed real-time database systems. International Journal of Modeling and Simulation, 15(2), 1995.

60. G. Weikum. Principles and realization strategies of multilevel transaction management. ACM Transactions on Database Systems, 16(1): 132-180, March 1991.

61. World Wide Web Consortium. Extensible Markup Language (XML) 1.0, February 1998.

62. World Wide Web Consortium. XML Linking Language (XLink), July 1999.

63. M. Xiong, K. Ramamritham, J. A. Stankovic, D. Towsley, and R. Sivasankaran. Maintaining temporal consistency: Issues and algorithms. In First International Workshop on Real-Time Databases, Newport Beach, California, March 1996.