Согласованные эволюционные трансформации взаимозависимых слабоструктурированных и реляционных схем тема диссертации и автореферата по ВАК РФ 05.13.11, кандидат физико-математических наук Симановский, Андрей Александрович

• Симановский, Андрей Александрович
• кандидат физико-математических наук
• 2007

Оглавление диссертации кандидат физико-математических наук Симановский, Андрей Александрович

1. Эволюция схем данных

1.1. Изменяющиеся данные.

1.1.1. Схемы и модели данных.

1.1.2. Темпоральные базы данных.

1.2. Системы поддержки эволюции схем данных

1.2.1. Эволюция, контроль версий, интеграция схем.

1.2.2. Метаинформация модели эволюции.

1.2.3. Реляционные модели эволюции.

1.2.4. Объектные модели эволюции.

1.2.5. Модели эволюции для XML.

1.3. XML-реляционные отображения.

1.3.1. Методы сохранения документов, ориентированных на данные и на документы.

1.3.2. Общие XML-реляционные отображения.

1.3.3. Схемоспецифичные XML-реляционные отображения

1.3.4. Пользовательские отображения.

1.3.5. Эволюция схем в присутствии XML-реляционных отображений

1.4. Итоги главы.

2. Модель данных

2.1. Представление схем данных.

2.2. Схема-медиатор

2.2.1. Отображение XML-схемы в схему-медиатор.

2.2.2. Отображение реляционных данных в схему-медиатор

2.3. Аксиомы схемы-медиатора.

2.4. Итоги главы.

3. Таксономия операций системы 38 3.1. Преобразования схемы-медиатора.

3.1.1. Определения.

3.1.2. Свойства.

3.2. Преобразования схемы ХМЬ-документов.

3.2.1. Операции, изменяющие граф ХМЬ-схемы.

3.2.2. Свойства операций, изменяющих граф ХМЬ-схемы

3.2.3. Операции, не меняющие граф ХМЬ-схемы

3.3. Преобразования реляционной схемы.

3.4. Итоги главы.

4. Трансформации схем

4.1. Декларативное описание трансформаций.

4.2. Ранжирование путей трансформации.

4.3. Итоги главы.

5. Описание прототипа

5.1. Архитектура надстройки над базой данных.

5.2. Архитектура и интерфейс клиента.

5.2.1. Визуальное представление схем.

5.2.2. Применение операций к схемам.

5.3. Итоги главы.

Глава 1.

Эволюция схем данных

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

Системы поддержки эволюции схем и контроля версий схем ( [59]) являются решением поставленной задачи в рамках СУБД. Они упорядочивают действия при изменении схем, позволяют описывать семантику изменений в предметной области и отражать изменения предметной области, происходящие со временем, в базе данных, распространяя эти изменения на схему хранимых данных и сами данные. Они избавляют от необходимости создания и реализации ad-hoc алгоритмов по изменению схем и данных при каждой модификации. В настоящее время существуют системы поддержки эволюции схем данных для реляционной ( [15,21,43,45,46,48,58]), объектно-ориентированной ( [5,13,14,33,40,41,47,50-55,61,63,67]), XML ( [1,20,39,74]) моделей данных.

Рассматриваемые приложения часто используют XML и такие языки запросов как XSLT, XPath, XQuery ( [76]) в качестве интерфейса к уровню представления данных, который в свою очередь использует мощные промышленные реляционные СУБД в качестве хранилища данных, реализуя логику преобразования работы с моделью данных XML в работу с реляционной моделью ( [35, 36, 78]). Как следствие, возникает вопрос эволюции связанных отображением пары XML- и реляционной схем.

В последнее время интерес к эволюции связанных отображением пары

XML- и реляционной схем возрос в свете рассмотрения этой задачи как составной части проблемы управления моделями данных ([8]).

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

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

• разработка множества элементарных операций, позволяющих описывать трансформации взаимозависимых схем и и связывающих их отображений;

• выражение трансформаций схем через эволюционные преобразования взаимозависимых схем.

1.1. Изменяющиеся данные

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

Системы поддержки эволюции схем и контроля версий схем являются развитием исследований в области темпоральных данных ( [24]).

1.1.1. Схемы и модели данных

Заключение диссертации по теме «Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей», Симановский, Андрей Александрович

Заключение

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

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

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

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

4. Реализован прототип системы, позволяющий применять изложенные в работе методы построения эволюционных преобразований схем на практике.

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

Прототип системы, реализующей модель эволюции, доступен в сети Интернет по адресу : http://meta.math.spbu.ru/binaries/simanovsky.zip.

Список литературы диссертационного исследования кандидат физико-математических наук Симановский, Андрей Александрович, 2007 год

1. Куке С. В. Аксиоматизация эволюции схемы xml-баз данных // Программирование. - 2003. - Т. 29, № 3. - С. 140-146.

2. Мейер Д. Теория реляционных баз данных: Пер. с англ. — Москва: Мир, 1987.

3. Симановский А. А. Автоматизация разработки схем баз данных для xml-реляционных систем // Методы и средства обработки информации. Труды Второй Всероссийской научно-технической конференции. 2005. - Pp. 113-118.

4. Симановский А. А. Совместные эволюционные трансформации взаимозависимых xml и реляционных схем // Вестник Санкт-Петербургского университета. Серия 10.— 2007.— Vol. 1, no. I.— Pp. 102-111.

5. Andany J., Léonard M., Palisser С. Management of schema evolution in databases. // VLDB. 1991. - Pp. 161-170.

6. Beech D., Malhotra A., Rys M. A formal data model and algebra for xml. — 1999. citeseer.ist.psu.edu/beech99formal.html.

7. Bernstein P. A. Applying model management to classical meta data problems. // CIDR. — 2003.

8. Bernstein P. A., Rahm E. Data warehouse scenarios for model management. // ER. 2000. - Pp. 1-15.

9. Bourret R. Xml database products: Native xml databases.— 2005. http://www.rpbourret.com/xml/ProdsNative.htm.

10. Bourret R., Bornhóvd C., Buchmann A. P. A generic load/extract utility for data transfer between xml documents and relational databases. // WECWIS. 2000. - Pp. 134-143.

11. Chaudhri A., Rashid A., Zicari R. XML Data Management: Native XML and XML-Enabled Database Systems. — Berkeley, CA, USA: Addison Wesley Longman, 2003.- P. 688.

12. Chen J.-L., McLeod D. Schema evolution for object-based accounting database systems. // ISOOMS. 1994. - Pp. 40-52.

13. Claypool K. T., Jin J., Rundensteiner E. A. Serf: Schema evalution through an extensible, re-usable and flexible framework. // CIKM.— 1998.-Pp. 314-321.

14. Clifford J., Croker A. The historical relational data model (hrdm) and algebra based on lifespans // Proceedings of the Third International Conference on Data Engineering. — Washington, DC, USA: IEEE Computer Society, 1987.-Pp. 528-537.

15. Codd E. F. Derivability, redundancy and consistency of relations stored in large data banks // IBM Research Report, San Jose, California. — 1969. — Vol. RJ599.

16. Codd E. F. A relational model of data for large shared data banks. // Commun. ACM. 1970. - Vol. 13, no. 6. - Pp. 377-387.

17. The computer-based patient record: an essential technology for health care / Ed. by R. S. Dick, E. B. Steen. Washington, DC, USA: National Academy Press, 1991.

18. Constraints-preserving mapping algorithm from xml-schema to relational schema. / H. Sun, S. Zhang, J. Zhou, J. Wang // EDCIS. 2002. -Pp. 193-207.

19. Dadam P., Teuhola J. Managing schema versions in a time-versioned nonfirst-normal-form relational database. // BTW. 1987. - Pp. 161-179.

20. Data exchange: semantics and query answering. / R. Fagin, P. G. Kolaitis, R. J. Miller, L. Popa // Theor. Comput. Sei. 2005. - Vol. 336, no. 1.-Pp. 89-124.

21. Date C. J. The Database Relational Model: A Retrospective Review and Analysis. — Berkeley, CA, USA: Addison Wesley Longman, 2000.

22. Date C. JDarwen H., Lorentzos A. Temporal Data and the Relational Model. — San Francisco, CA, USA: Morgan Kaufmann Publishers, 2003.

23. Efficient relational storage and retrieval of xml documents. / A. Schmidt, M. L. Kersten, M. Windhouwer, F. Waas // WebDB (Selected Papers).— 2000. Pp. 137-150.

24. Extensible markup language (xml) 1.0 (third edition). http://www.w3.org/TR/REC-xml/.

25. Fan H., Poulovassilis A. Schema evolution in data warehousing environments a schema transformation-based approach. // ER.— 2004.— Pp. 639-653.

26. Franconi E., Grandi F., Mandreoli F. Schema evolution and versioning: A logical and computational characterisation. // FMLDO. — 2000. — Pp. 8599.

27. Prom xml schema to relations: A cost-based approach to xml storage. / P. Bohannon, J. Freire, P. Roy, J. Siméon // ICDE. 2002. - Pp. 64-. Guerrini G., Mesiti M., Rossi D. Impact of xml schema evolution on valid documents. // WIDM. - 2005. - Pp. 39-44.

28. Kim W., Chou H.-T. Versions of schema for object-oriented databases. // VLDB.- 1988.-Pp. 148-159.

29. Klettke M., Meyer H. Xml and object-relational database systems enhancing structural mappings based on statistics. // WebDB (Selected Papers).-2000.-Pp. 151-170.

30. Krishnamurthy R., Kaushik R., Naughton J. Xml-to-sql query translation literature: The state of the art and open problems.— 2003. cite-seer.ist.psu.edu/krishnamurthy03xmltosql.html.

31. Krishnamurthy R., Kaushik R., Naughton J. F. Efficient xml-to-sql query translation: Where to add the intelligence? // VLDB. 2004. - Pp. 144155.

32. Mallaug T., Bratbergsengen K. Long-term temporal data representation of personal health data. // ADBIS. 2005. - Pp. 379-391. Markowitz V. M., Makowsky J. A. Incremental reorganization of relational databases. // VLDB. - 1987. - Pp. 127-135.

33. McBrien P., Poulovassilis A. Schema evolution in heterogeneous database architectures, a schema transformation approach. // CAiSE. — 2002.— Pp. 484-499.

34. Novak L., Zamulin A. V. Algebraic semantics of xml schema. // ADBIS. — 2005. Pp. 209-222.

35. Osborn S. L. The role of polymorphism in schema evolution in an object-oriented database // IEEE Transactions on Knowledge and Data Engineering. 1989. - Vol. 1, no. 3. - Pp. 310-317.

36. Penney D. J., Stein J. Class modification in the gemstone object-oriented dbms // OOPSLA '87: Conference proceedings on Object-oriented programming systems, languages and applications. — New York, NY, USA: ACM Press, 1987.- Pp. 111-117.

37. Peters R. J., Ozsu M. T. An axiomatic model of dynamic schema evolution in objectbase systems // ACM Trans. Database Syst. — 1997.— Vol. 22, no. 1. Pp. 75-114.

38. Ra Y.-G., Rundensteiner E. A. Towards supporting hard schema changes in tse // CIKM '95: Proceedings of the fourth international conference on Information and knowledge management. — New York, NY, USA: ACM Press, 1995. Pp. 290-295.

39. Relational databases for querying xml documents: Limitations and opportunities. / J. Shanmugasundaram, K. Tufte, C. Zhang et al. // VLDB.— 1999. Pp. 302-314.

40. Robie J., Lapp J., Schach D. Xml query language (xql). // QL. — 1998.

41. Roddick J. F. Sql/se: a query language extension for databases supporting schema evolution // SIGMOD Rec. 1992. - Vol. 21, no. 3. - Pp. 10-16.

42. Roddick J. F. A survey of schema versioning issues for database systems // Information and Software Technology. —1995. — Vol. 37, no. 7. — Pp. 383393. citeseer.ist.psu.edu/roddick95survey.html.

43. Roddick J. F., Craske N. G., Richards T. J. A taxonomy for schema versioning based on the relational and entity relationship models. // ER. — 1993. Pp. 137-148.

44. Semantics and implementation of schema evolution in object-oriented databases. / J. Banerjee, W. Kim, H.-J. Kim, H. F. Korth // SIGMOD Conference. 1987. - Pp. 311-322.

45. Shimura T., Yoshikawa M., Uemura S. Storage and retrieval of xml documents using object-relational databases. // DEXA. —1999. — Pp. 206-217.

46. Si A., Leong H. V., Wu P. Y. 4dis: a temporal framework for unifying meta-data and data evolution // SAC '98: Proceedings of the 1998 ACM symposium on Applied Computing. — New York, NY, USA: ACM Press, 1998. Pp. 203-210.

47. Simanovsky A. Applying the reconfiguration-design formalism to xml stored in a relational database //In Proceedings of the Spring Young Researcher's Colloquium on Database and Information Systems. — 2004. — Pp. 75-77.

48. Simanovsky A. Evolution of schema of xml-documents stored in a relational database // Proceedings of 6th Baltic DBIS Conference. — 2004. — Pp. 192-204.

49. Simanovsky A. Three layer evolution model for xml stored in relational databases. // ADBIS Research Communications. — 2005. — Pp. 66-79.

50. Skarra A. H., Zdonik S. B. The management of changing types in an object-oriented database. // OOPSLA. 1986. - Pp. 483-495.

51. Snodgrass R. T., Ahn I. A taxonomy of time in databases. // SIGMOD Conference. 1985.- Pp. 236-246.

52. Timber: A native xml database. / H. V. Jagadish, S. Al-Khalifa, A. Chapman et al. // VLDB J. 2002. - Vol. 11, no. 4. - Pp. 274-291.

53. Tiirker C. Schema evolution in data warehousing environments a schema transformation-based approach. // 9th International Workshop on Foundations of Models and Languages for Data and Objects. — 2000. — Pp. 1-32.

54. Velegrakis Y., Miller R. J., Popa L. Mapping adaptation under evolving schémas. // VLDB. 2003. - Pp. 584-595.

55. Vianu V. Dynamic functional dependencies and database aging. // J. ACM. 1987. - Vol. 34, no. 1. - Pp. 28-59.

56. World wide web consortium, http://www.w3.org/.

57. Xem: Managing the evolution of xml documents. / H. Su, D. Kramer, L. Chen et al. // RIDE-DM.- 2001.- Pp. 103-110.

58. Xml schema specification. http://www.w3.org/TR/xmlschemarO/.

59. Xquery 1.0: An xml query language. http://www.w3.org/TR/xquery.

60. Xquery 1.0 and xpath 2.0 data model (xdm).— 2005. http://www.w3.org/TR/xpath-datamodel/.

61. Xquery implementation in a relational database system / S. Pal, I. Cseri, O. Seeliger et al. // VLDB '05: Proceedings of the 31st international conference on Very large data bases. — VLDB Endowment, 2005. — Pp. 11751186.

62. Yu C., Popa L. Semantic adaptation of schema mappings when schémas evolve. // VLDB. 2005. - Pp. 1006-1017.