Введение к работе
Актуальность темы
Теория систем управления базами данных представляет собой важную и активно развивающуюся область информатики. За более чем сорокалетнюю историю исследований в этой области было опубликовано огромное количество работ, посвященных, как теоретическим основам баз данных (БД), так и практической разработке инструментальных средств и приложений. Одним из ключевых понятий в области БД является понятие целостности хранящихся в них данных, и поддержка целостности является одной из важнейших обязанностей систем управления базами данных (СУБД).
Термин целостность используется для описания точности и корректности данных, хранящихся в базе данных. Для поддержки целостности система должна содержать информацию о тех правилах (ограничениях), которые пользователю не следует нарушать. Кроме того, система управления базами данных, в свою очередь, должна следить за соблюдением заданных правил, в том числе и при параллельной работе с базой данных [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], перечисленных в конце автореферата.
Структура и объем диссертации
