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

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

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

Куке Сергей Владимирович

ЭВОЛЮЦИЯ СХЕМ СЛАБОСТРУКТУРИРОВАННЫХ ДАННЫХ

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

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата физико-математических наук

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

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

государственного университета.

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

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

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

Кузнецов Сергей Дмитриевич

кандидат физико-математических наук Округин Михаил Борисович

Ведущая организация- Южно-Уральский государственный университет

Защита диссертации состоится 2004 года в ¿/_ часов на

заседании диссертационного совета Д212 232.51 по защите диссертаций на соискание ученой степени доктора наук при Санкт-Петербургском государственном университете по адресу. 198504, Санкт-Петербург, Старый Петергоф, Университетский пр., д. 28, математико-механический факультет Санкт-Петербургского государственного университета.

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

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

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

профессор Б.К.Мартыненко

гзаТГ

Общая характеристика работы Актуальность темы

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

Базы данных и программные системы редко сохраняют свой первоначальный дизайн в процессе использования И хотя оценки различаются, большинство исследователей согласны, что не менее 50% усилий программисты затрачивают на внесение изменений в систему после ее ввода в эксплуатацию [5], и чем большее количество прикладных программ написано и чем большие объемы данных подверглись изменениям, тем труднее задача модификации системы. Более того, модификации работающих систем, требующие изменения структуры данных, весьма часто встречаются на практике [12, 13]. Как следствие, внесение изменений в схему базы данных - явление типичное, хотя и весьма хлопотное. Поддержка таких изменений актуальна как для производителей СУБД, так и для пользователей.

Системы поддержки эволюции схем и контроля версий схемы возникли как средства для сохранения данных, внесенных в систему, схема которой изменилась впоследствии [11]. Формальное определения термина "эволюция схемы" дано в главе 1 диссертации, неформально же эволюция схемы - это способность системы управления базой данных отражать изменения, происходящие в реальном мире, путем изменения схемы. Во многих системах под этим свойством также подразумевается способность сохранять предыдущие состояния схемы данных. Такая возможность необходима, если данные, сохраненные в базе при некоторой схеме данных, не устаревают, несмотря на изменения в схеме [10].

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

РОС. НАЦИОНАЛЬНАЯ

БИ-Г, ПОТЕКА С. Петербург >0о£рк

работ в области темпоральных моделей данных (temporal data modeling) и темпоральных баз данных (temporal databases), и, во-вторых, в рамках объектно-ориентированной парадигмы, особенно при разработке архитектур автоматизированного проектирования (CAD) и других систем в области инжиниринга [11].

Вопросы, связанные с эволюцией схем реляционных и объектно-ориентированных баз данных, хорошо исследованы. Однако, множество источников информации значительно шире Одним из таких источников является Ве5. В Веб доступно много информации, которая обладает некоторой определенной структурой (например, электронный каталог товаров) и возможность использования структурированных запросов для таких ресурсов могла бы быть очень полезной. Эти соображения стимулируют исследования в области организации доступа к такой информации, на которую принято ссылаться как на слабоструктурированную информацию [1].

Основным источником слабоструктурированной информации долгое время являлись автоматически сгенерированные HTML-страницы (например, списка рассылки или электронного каталога). С появлением в середине 90-х годов языка XML [15] и XML-QL [16], стало возможным говорить об XML-базах данных, а как следствие об их схемах и эволюции этих схем.

Цели работы

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

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

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

• Разработана аксиоматическая модель описания схем

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

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

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

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

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

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

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

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

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

Разработана аксиоматическая модель описания схем слабоструктурированных данных и прототип системы, позволяющие существенно упростить разработку и сопровождение XML-баз данных.

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

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

Результаты работы докладывались

• на Третьей всероссийской научной конференции RCDL'2001 "Электронные библиотеки" (Петрозаводск, Россия, Октябрь 2001)

• на семинаре Второй международной конференции ISTA'2003 (Харьков, Украина, Июнь, 2003)

• на семинаре Московской секции ACM SIGMOD (Москва, ноябрь, 2003)

• на семинарах группы теории баз данных при лаборатории исследования операций НИММ

Предложенная технология была реализована в виде прототипа системы поддержки эволюции XML-схем EvoXSD, доступного по адресу http-.//meta math spbu.ru/bmaries/evoxsd-setup exe.

Публикации

Основные результаты диссертации изложены в 3-х работах, перечисленных в конце автореферата.

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

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

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

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

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

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

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

данных - это информация, описывающая структуру хранимых данных и операции над ними.

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

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

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

• Семантики изменений: какой эффект изменение схемы оказывает на структуру хранения данных.

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

Вторая проблема решается путем явной модификации хранимых данных так, чтобы они полностью соответствовали новой схеме. Это может делается немедленно (как, например в СетБкопе [8]), либо при первом обращении к ним (так называемое, "ленивое" преобразование [14]), либо постановкой в соответствие каждому элементу данных набора действий (механизма представлений), которые будут применяться при обращении к нему таким образом, чтобы внешние приложения могли работать с данными как если бы их структура не изменилась [7]. К решению же первой задачи существуют несколько разных подходов.

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

• Многомерный XML. Строго говоря, многомерный XML (MXML) является не столько одним из подходов к работе с данными, схема которых изменяется со временем, сколько источником задач, близких к этой области. MXML является расширением XML для описания контекстно-зависимых данных. Таким образом, уже для единственной схемы уместно говорить о различных ее вариантах, а как следствие, возникают задачи, близкие к задачам эволюции схем. Кроме того, если в качестве контекстной метки использовать время, то получается структура, аналогичная темпоральной XML-базе данных типа [6].

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

• Аксиоматическая модель. Авторами системы Tigukat [9] была предложена аксиоматическая модель объектной схемы данных, на основе которой создана система поддержки эволюции объектно-ориентированных схем, интегрированная в СУБД Tigukat.

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

Наиболее частым источником слабоструктурированной информации является XML. Согласно Рональду Буре [2] XML-документы подразделяются на две категории, ориентированные на данные и на документы, различающеся в основном лишь степенью структурированности. Однако, вне зависимости от способа описания схемы XML-документ представляет собой иерархическую структуру элементов данных (тегов), включаемых друг в друга согласно некоторым правилам Подобная схема может быть выделена из HTML-документов с помощью программ-посредников либо явным образом быть описана для XML Предложенная далее аксиоматическая модель позволяет работать с иерархической схемой данных, заданной произвольным образом, за одним исключением: она не поддерживает циклические схемы.

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

Выражение Описание

Т Иерархия типов схемы

s, t, Т, JL Типы

P(t) Множество непосредственных предшественников 1

Pe(t) Множество существенных предшественников 1

PL(t) Граф предшественников 1

N(t) Множество "родных" атрибутов типа 1

H(t) Множество "унаследованных" атрибутов типа 1

Nc(t) Множество существенных атрибутов типа t

I(t) Множество всех (интерфейс) атрибутов типа t

o«(f,T') Функция применяемая ко всем элементам Т'

Таблица 1: Нотация модели.

10

Т - Множество всех типов схемы и одновременно граф.

Иерархия узлов графа Т определяется множествами непосредственных предшественников Р(Ь) для каждого типа (;. Этим термином мы будем именовать типы, которые могут явно включать в себя тип 1;. В терминах графа схемы это означает наличие ребра из каждого элемента Р(1) в узел

Существенными предшественниками Ре{€) будем назвать тех предшественников, наличие которых в пути от корня до тега t существенно с точки зрения семантики данных. Это множество, как и множество Ц.00, определяется автором схемы. Включение тега э в Ре(Ч) означает, что тег э будет оставаться предком t при всех изменениях схемы, за исключением непосредственного его удаления из Ре(Ъ) (и собственно Р((;), если он непосредственно включает (;), либо удаления тега в из системы.

Граф предшественников РЬП) типа Ь - это подграф Т, включающий в себя все типы, из которых достижим тип 1;, считая его самого. Легко видеть, что РЬ(Ч) обладает свойствами исходного графа - орграф без циклов с одной начальной (Т) и одной конечной вершиной (1;), а ограничение, налагаемое на существенных предшественников, можно записать в виде РеОО^РВД.

Родными атрибутами типа t мы будем называть атрибуты, определенные в нем.

Унаследованными атрибутами Н(1) типа t мы будем называть объединение атрибутов всех типов, из которых достижим тип t (не включая его самого). Легко видеть, что множества родных и унаследованных атрибутов тега не пересекаются.

Существенные атрибуты N¿(1) типа < - это атрибуты, объявленные автором схемы таковыми для данного типа (аналогично множеству существенных предков). Это множество состоит из всех "родных" атрибутов и, возможно, части унаследованных [N(1;) - Включение

атрибута в это множество означает, что он должен будет оставаться атрибутом типа t (родным или унаследованным) как можно дольше при всех изменениях схемы.

Интерфейс типа I - это множество всех его атрибутов

(объединение множеств N(t) и H(t)).

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

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

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

В пятой главе приведена классификация программных продуктов для XML согласно Рональду Буре [3], сформулированы требования к системе поддержки эволюции XML-схем EvoXSD, прототип которой реализован в рамках данной диссертационной работы, описана архитектура системы и представлен пример ее использования.

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

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

[1] Abiteboul S., Buneman P., Suciu D. Data on the Web // Morgan Kaufmann Publishers - 1999.

[2] Bourret R. XML and databases // http.//www rpbourret.com/ xml/XMLAndDatabases.htm

[3] Bourret R. XML Database products // http-//www rpbourret.com/ xml/XMLDatabaseProds htm

[4] Jensen G., et al. A consensus glossary of temporal database concepts // SIGMOD Ree. - 1994. - 23(l):52-64

[5] Lientz B P Issues in software maintenance // ACM Computing Surveys - 1983 - 15(3):271-278.

[6] Kalinichenko L.A., Manukyan M.G. Tempoial XML // in Proceedings of the Fifth East European Symposium on Advances in Databases and Information Systems (ADBIS'Ol), September 25-28, 2001, Vilnius, Lithuania

[7] Kim W , Chou H -T. Versions of schema for object-oriented databases //In Proc. Fourteenth International Conference on Very Large Databases Los Angeles, CA, Morgan Kaufmann, Palo Alto, CA. - 1988. — pp. 148-159.

[8] Penney D J., Stein J. Class modification in the GemStone object-oriented DBMS // OOPSLA '87 (SIGPLAN Notices). - 1987. - Vol. 22. no. 12. pp. 111-117.

[9] Peters R. J., Ozsu M.T. An Axiomatic Model of Dynamic Schema Evolution in Objectba.se Systems // ACM Transactions on Database Systems, 22(1) (March 1997) 75-114

[10] Roddik J.F. Schema Evolution in Database Systems — An Updated Bibliography // SIGMOD Ree. - Revised, May 1994. - 21(4), pp. 35-40.

[11] Roddik J.F. A Survey of Schema Versioning Issues for Database Systems. // Information and Software Technology. — 1995 — 37(7): 383-393

[12] Sjoberg, D. Measuring schema evolution // Technical Report FIDE/92/36. Department of Computer Science, University of Glasgow. — 1992. —

[13] Sjoberg, D. Quantifying schema evolution // Information and Software Technology. - 1993. - 35(l):35-44.

[14] Tan L , Katayama T Meta operations for type management in object-oriented databases - a lazy mechanism for schema evolution // In Proc. First International Conference on Deductive and Object-Oriented Databases, DOOD '89, Kyoto, Japan, North-Holland, pp 241-258.

[15] Спецификация XML // http://www.w3.org/XML/

[16] Спецификация XML-QL // http-//www.w3 org/TR/NOTE-xml-ql/

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

1 Барашев Д , Высоцкий А., Куке С., Михайлова Е., Некрестьянов И., Новиков В., Павлова Е. Интеграция публично доступных архивов списков рассылки // В Трудах третьей всероссийской научной конференции "Электронные библиотеки", Петрозаводск, Россия, Октябрь 2001.

2. Куке С. Аксиоматизация эволюции схемы XML-базы данных // Программирование — 2003. — J03, с. 1-9.

3. Соох S.V., Simanovsky A. A. Regular Expressions in XML Schema Evolution // Bichhk Национального техшчного ушверситету "Харювський пештехшчний шетитут". Зб1рник наукових праць. Тематичний випуск "Системний анализ, управлшня та шформащйш технологи". Харюв: НТУ "ХПГ. - 2004. - №1., с. 24-38.

Подписано в печать 04 11 2004 г Формат бумаги 60X84 1/16 Бума! а офсетн; Печать офсетная. Объем 1 уел пл Тираж 100 экз Заказ 3402 Отпечатано в отделе оперативной полиграфии НИИХ СПбГУ с оригинал-макета заказчика. 198504, Санкт-Петербург, Старый Петергоф, Университетский пр , 26

РНБ Русский фонд

2006-4 3275