Managing and querying transaction-time databases under schema evolution

ABSTRACT

The old problem of managing the history of database information is now made more urgent and complex by fast spreading web information systems, such as Wikipedia. Our PRIMA system addresses this difficult problem by introducing two key pieces of new technology. The first is a method for publishing the history of a relational database in XML, whereby the evolution of the schema and its underlying database are given a unified representation. This temporally grouped representation makes it easy to formulate sophisticated historical queries on any given schema version using standard XQuery. The second key piece of technology is that schema evolution is transparent to the user: she writes queries against the current schema while retrieving the data from one or more schema versions. The system then performs the labor-intensive and error-prone task of rewriting such queries into equivalent ones for the appropriate versions of the schema. This feature is particularly important for historical queries spanning over potentially hundreds of different schema versions and it is realized in PRIMA by (i) introducing Schema Modification Operators (SMOs) to represent the mappings between successive schema versions and (ii) an XML integrity constraint language (XIC) to efficiently rewrite the queries using the constraints established by the SMOs. The scalability of the approach has been tested against both synthetic data and real-world data from the Wikipedia DB schema evolution history.

REFERENCES

• 1: Oracle Documentation. http://otn.oracle.com.
• 2: Serge Abiteboul , Richard Hull , Victor Vianu, Foundations of Databases: The Logical Level, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1995
• 3: R. B. Almeida, B. Mozafari, and J. Cho. On the evolution of wikipedia. In ICWSM, 2007.
• 4: Gad Ariav, Temporally oriented data definitions: managing schema evolution in temporally oriented databases, Data & Knowledge Engineering, v.6 n.6, p.451-467, Oct. 1991 [doi>10.1016/0169-023X(91)90023-Q]
• 5: P. A. Bernstein. Applying model management to classical meta data problems. In CIDR, 2003.
• 6: Philip A. Bernstein , Todd J. Green , Sergey Melnik , Alan Nash, Implementing mapping composition, Proceedings of the 32nd international conference on Very large data bases, September 12-15, 2006, Seoul, Korea
• 7: Cristina De Castro , Fabio Grandi , Maria Rita Scalas, Schema versioning for multitemporal relational databases, Information Systems, v.22 n.5, p.249-290, July 1997 [doi>10.1016/S0306-4379(97)00017-3]
• 8: James Clifford , Albert Croker , Fabio Grandi , Alexander Tuzhilin, On Temporal Grouping, Proceedings of the International Workshop on Temporal Databases: Recent Advances in Temporal Databases, p.194-213, September 17-18, 1995
• 9: C. Curino, H. J. Moon, L. Tanca, and C. Zaniolo. Schema evolution in wikipedia: toward a web information system benchmark. In ICEIS, 2008.
• 10: Carlo A. Curino , Hyun J. Moon , Carlo Zaniolo, Graceful database schema evolution: the PRISM workbench, Proceedings of the VLDB Endowment, v.1 n.1, August 2008 [doi>10.1145/1453856.1453939]
• 11: C. Curino, H. J. Moon, and C. Zaniolo. Managing the history of metadata in support for db archiving and schema evolution. In ECDM, 2008.
• 12: Alin Deutsch , Val Tannen, MARS: a system for publishing XML from mixed and redundant storage, Proceedings of the 29th international conference on Very large data bases, p.201-212, September 09-12, 2003, Berlin, Germany
• 13: Dengfeng Gao , Richard T. Snodgrass, Temporal slicing in the evaluation of XML queries, Proceedings of the 29th international conference on Very large data bases, p.632-643, September 09-12, 2003, Berlin, Germany
• 14: S. Kepser. A proof of the turing-completeness of xslt and xquery. In Technical report SFB 441, Eberhard Karls Universitat Tubingen, 2002.
• 15: S. Marche. Measuring the stability of data models. European Journal of Information Systems, 2(1):37--47, 1993.
• 16: E. McKenzie , Richard Thomas Snodgrass, Schema evolution and the relational algebra, Information Systems, v.15 n.2, p.207-232, 1990 [doi>10.1016/0306-4379(90)90036-O]
• 17: Sergey Melnik , Erhard Rahm , Philip A. Bernstein, Rondo: a programming platform for generic model management, Proceedings of the 2003 ACM SIGMOD international conference on Management of data, June 09-12, 2003, San Diego, California [doi>10.1145/872757.872782]
• 18: Alberto O. Mendelzon , Flavio Rizzolo , Alejandro Vaisman, Indexing temporal XML documents, Proceedings of the Thirtieth international conference on Very large data bases, p.216-227, August 31-September 03, 2004, Toronto, Canada
• 19: Gultekin Ozsoyoglu , Richard Thomas Snodgrass, Temporal and Real-Time Databases: A Survey, IEEE Transactions on Knowledge and Data Engineering, v.7 n.4, p.513-532, August 1995 [doi>10.1109/69.404027]
• 20: S. Ram and G. Shankaranarayanan. Research issues in database schema evolution: the road not taken. In Boston University School of Management, Department of Information Systems, Working Paper, 2003.
• 21: Flavio Rizzolo , Alejandro A. Vaisman, Temporal XML: modeling, indexing, and query processing, The VLDB Journal — The International Journal on Very Large Data Bases, v.17 n.5, p.1179-1212, August 2008 [doi>10.1007/s00778-007-0058-x]
• 22: J. Roddick. A Survey of Schema Versioning Issues for Database Systems. Information and Software Technology, 37(7):383--393, 1995.
• 23: Ben Shneiderman , Glenn Thomas, An architecture for automatic relational database sytem conversion, ACM Transactions on Database Systems (TODS), v.7 n.2, p.235-257, June 1982 [doi>10.1145/319702.319724]
• 24: D. I. Sjoberg. Quantifying schema evolution. Information and Software Technology, 35(1):35--44, 1993
• 25: Richard Thomas Snodgrass, The TSQL2 Temporal Query Language, Kluwer Academic Publishers, Norwell, MA, 1995
• 26: Yannis Velegrakis , Renée J. Miller , Lucian Popa, Mapping adaptation under evolving schemas, Proceedings of the 29th international conference on Very large data bases, p.584-595, September 09-12, 2003, Berlin, Germany
• 27: Fusheng Wang , Carlo Zaniolo , Xin Zhou, ArchIS: an XML-based approach to transaction-time temporal database systems, The VLDB Journal — The International Journal on Very Large Data Bases, v.17 n.6, p.1445-1463, November 2008 [doi>10.1007/s00778-007-0086-6]
• 28: Cong Yu , H. V. Jagadish, Querying complex structured databases, Proceedings of the 33rd international conference on Very large data bases, September 23-27, 2007, Vienna, Austria
• 29: Cong Yu , Lucian Popa, Constraint-based XML query rewriting for data integration, Proceedings of the 2004 ACM SIGMOD international conference on Management of data, June 13-18, 2004, Paris, France [doi>10.1145/1007568.1007611]
• 30: Cong Yu , Lucian Popa, Semantic adaptation of schema mappings when schemas evolve, Proceedings of the 31st international conference on Very large data bases, August 30-September 02, 2005, Trondheim, Norway

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems
          Subjects: Transaction processing

Additional Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.1 Logical Design
          Subjects: Schema and subschema
      H.2.4 Systems
          Subjects: Query processing
      H.2.7 Database Administration
          Subjects: Security, integrity, and protection
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.3 Information Search and Retrieval

General Terms:
Algorithms, Design, Management