Graceful database schema evolution: the PRISM workbench

ABSTRACT

Supporting graceful schema evolution represents an unsolved problem for traditional information systems that is further exacerbated in web information systems, such as Wikipedia and public scientific databases: in these projects based on multiparty cooperation the frequency of database schema changes has increased while tolerance for downtimes has nearly disappeared. As of today, schema evolution remains an error-prone and time-consuming undertaking, because the DB Administrator (DBA) lacks the methods and tools needed to manage and automate this endeavor by (i) predicting and evaluating the effects of the proposed schema changes, (ii) rewriting queries and applications to operate on the new schema, and (iii) migrating the database.

Our PRISM system takes a big first step toward addressing this pressing need by providing: (i) a language of Schema Modification Operators to express concisely complex schema changes, (ii) tools that allow the DBA to evaluate the effects of such changes, (iii) optimized translation of old queries to work on the new schema version, (iv) automatic data migration, and (v) full documentation of intervened changes as needed to support data provenance, database flash back, and historical queries. PRISM solves these problems by integrating recent theoretical advances on mapping composition and invertibility, into a design that also achieves usability and scalability. Wikipedia and its 170+ schema versions provided an invaluable testbed for validating PRISM tools and their ability to support legacy queries.

REFERENCES

• 1: R. B. Almeida, B. Mozafari, and J. Cho. On the evolution of wikipedia. In Int. Conf. on Weblogs and Social Media, March 2007.
• 2: Denilson Barbosa , Juliana Freire , Alberto O. Mendelzon, Designing information-preserving mapping schemes for XML, Proceedings of the 31st international conference on Very large data bases, August 30-September 02, 2005, Trondheim, Norway
• 3: P. A. Bernstein. Applying model management to classical meta data problems. In CIDR, 2003.
• 4: Philip A. Bernstein , Todd J. Green , Sergey Melnik , Alan Nash, Implementing mapping composition, The VLDB Journal — The International Journal on Very Large Data Bases, v.17 n.2, p.333-353, March 2008 [doi>10.1007/s00778-007-0059-9]
• 5: P. A. Bernstein and E. Rahm. Data warehouse scenarios for model management. In ER, 2003.
• 6: Hassina Bounif , Rachel Pottinger, Schema Repository for Database Schema Evolution, Proceedings of the 17th International Conference on Database and Expert Systems Applications, p.647-651, September 04-08, 2006 [doi>10.1109/DEXA.2006.125]
• 7: A. Cleve and J.-L. Hainaut. Co-transformations in database applications evolution. Generative and Transformational Techniques in Software Engineering, pages 409--421, 2006.
• 8: C. A. Curino, H. J. Moon, L. Tanca, and C. Zaniolo. Schema Evolution in Wikipedia: toward a Web Information System Benchmark. ICEIS, 2008.
• 9: C. A. Curino, H. J. Moon, and C. Zaniolo. Managing the history of metadata in support for db archiving and schema evolution. In ECDM, 2008.
• 10: DB2 development team. DB2 Change Management Expert. 2006.
• 11: Alin Deutsch , Val Tannen, Optimization Properties for Classes of Conjunctive Regular Path Queries, Revised Papers from the 8th International Workshop on Database Programming Languages, p.21-39, September 08-10, 2001
• 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: Ronald Fagin, Inverting schema mappings, ACM Transactions on Database Systems (TODS), v.32 n.4, p.25-es, November 2007 [doi>10.1145/1292609.1292615]
• 14: Ronald Fagin , Phokion G. Kolaitis , Wang-Chiew Tan , Lucian Popa, Composing schema mappings: second-order dependencies to the rescue, Proceedings of the twenty-third ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 14-16, 2004, Paris, France [doi>10.1145/1055558.1055572]
• 15: Ronald Fagin , Phokion G. Kolaitis , Lucian Popa , Wang-Chiew Tan, Quasi-inverses of schema mappings, Proceedings of the twenty-sixth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 11-13, 2007, Beijing, China [doi>10.1145/1265530.1265548]
• 16: Nina Edelweiss , Álvaro Freitas Moreira, Temporal and versioning model for schema evolution in object-oriented databases, Data & Knowledge Engineering, v.53 n.2, p.99-128, May 2005 [doi>10.1016/j.datak.2004.07.001]
• 17: M. Golfarelli, J. Lechtenbörger, S. Rizzi, and G. Vossen. Schema versioning in data warehouses. In ER (Workshops), pages 415--428, 2004.
• 18: Jean-Marc Hick , Jean-Luc Hainaut, Database application evolution: a transformational approach, Data & Knowledge Engineering, v.59 n.3, p.534-558, December 2006 [doi>10.1016/j.datak.2005.10.003]
• 19: H. V. Jagadish , Inderpal Singh Mumick , Michael Rabinovich, Scalable Versioning in Distributed Databases with Commuting Updates, Proceedings of the Thirteenth International Conference on Data Engineering, p.520-531, April 07-11, 1997
• 20: T. Lemke and R. Manthey. The schema evolution assistant: Tool description, 1995.
• 21: Jayant Madhavan , Alon Y. Halevy, Composing mappings among data sources, Proceedings of the 29th international conference on Very large data bases, p.572-583, September 09-12, 2003, Berlin, Germany
• 22: 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]
• 23: Hyun J. Moon , Carlo A. Curino , Alin Deutsch , Chien-Yi Hou , Carlo Zaniolo, Managing and querying transaction-time databases under schema evolution, Proceedings of the VLDB Endowment, v.1 n.1, August 2008 [doi>10.1145/1453856.1453952]
• 24: Mirella M. Moro , Susan Malaika , Lipyeow Lim, Preserving XML queries during schema evolution, Proceedings of the 16th international conference on World Wide Web, May 08-12, 2007, Banff, Alberta, Canada [doi>10.1145/1242572.1242841]
• 25: Alan Nash , Philip A. Bernstein , Sergey Melnik, Composition of mappings given by embedded dependencies, Proceedings of the twenty-fourth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 13-15, 2005, Baltimore, Maryland [doi>10.1145/1065167.1065189]
• 26: Oracle development team. Oracle database 10g online data reorganization and redefinition. 2005.
• 27: Y.-G. Ra. Relational schema evolution for program independency. Intelligent Information Technology, pages 273--281, 2005.
• 28: S. Rizzi and M. Golfarelli. X-time: Schema versioning and cross-version querying in data warehouses. In ICDE, pages 1471--1472, 2007.
• 29: J. Roddick. A Survey of Schema Versioning Issues for Database Systems. Information and Software Technology, 37(7):383--393, 1995.
• 30: Jeffrey D. Ullman, Principles of Database Systems, W. H. Freeman & Co., New York, NY, 1983
• 31: 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
• 32: Wikimedia Foundation. Mediawiki http://www.mediawiki.org, 2007. {Online}.
• 33: Wikimedia Foundation. Wikipedia http://en.wikipedia.org/, 2007. {Online}.
• 34: 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.1 Logical Design
          Subjects: Schema and subschema

Additional Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.1 Logical Design
          Subjects: Data models
      H.2.5 Heterogeneous Databases
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.3 Information Search and Retrieval
      H.3.4 Systems and Software
          Subjects: Performance evaluation (efficiency and effectiveness)

General Terms:
Algorithms, Design, Management, Performance