A step towards incremental maintenance of the composed schema mapping

ABSTRACT

Schema mapping plays a fundamental role in modern information systems. Mapping composition is an operator that combines a chain of successive schema mappings into a single schema mapping. By pre-computing the composed schema mapping, the system can achieve significant performance benefits. However, when a change occurs on any mapping in the chain, the composed schema mapping has to be maintained correspondingly. In this paper we consider a restricted form of the problem in the XML setting and propose an incremental maintenance approach. Specifically, given a chain of successive mappings, we transform intermediately them into trees that consist of atomic rules and then divide the composition into sub-compositions of the atomic rules. The dividing composition approach provides a fine-grained perspective of the composition relationships between the mappings. We depict such information through an auxiliary data structure called composition relationship graph (CRG). When changes occur on any mapping in the chain, the corresponding maintenance algorithms are developed based on the dividing approach and the CRG, which compute the changes on the composed mapping and then repair it into the new version, such that the computation involves only the atomic rules that are relevant with the maintenance. We evaluate our maintenance approach and report the first experiments results, which show that it is efficient.

REFERENCES

• 1: P. A. Bernstein. Applying Model Management to Classical Meta Data Problems. In Proc. of CIDR, Pages 209--220, 2003.
• 2: Philip A. Bernstein , Sergey Melnik, Model management 2.0: manipulating richer mappings, Proceedings of the 2007 ACM SIGMOD international conference on Management of data, June 11-14, 2007, Beijing, China [doi>10.1145/1247480.1247482]
• 3: Clio. http://www.cs.toronto.edu/db/clio/
• 4: Ronald Fagin , Phokion G. Kolaitis , Renée J. Miller , Lucian Popa, Data Exchange: Semantics and Query Answering, Proceedings of the 9th International Conference on Database Theory, p.207-224, January 08-10, 2003
• 5: 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]
• 6: Ariel Fuxman , Mauricio A. Hernandez , Howard Ho , Renee J. Miller , Paolo Papotti , Lucian Popa, Nested mappings: schema mapping reloaded, Proceedings of the 32nd international conference on Very large data bases, September 12-15, 2006, Seoul, Korea
• 7: Alon Y. Halevy , Zachary G. Ives , Peter Mork , Igor Tatarinov, Piazza: data management infrastructure for semantic web applications, Proceedings of the 12th international conference on World Wide Web, May 20-24, 2003, Budapest, Hungary [doi>10.1145/775152.775231]
• 8: Maurizio Lenzerini, Data integration: a theoretical perspective, Proceedings of the twenty-first ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 03-05, 2002, Madison, Wisconsin [doi>10.1145/543613.543644]
• 9: 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
• 10: Renée J. Miller , Laura M. Haas , Mauricio A. Hernández, Schema Mapping as Query Discovery, Proceedings of the 26th International Conference on Very Large Data Bases, p.77-88, September 10-14, 2000
• 11: Yannis Papakonstantinou , Serge Abiteboul , Hector Garcia-Molina, Object Fusion in Mediator Systems, Proceedings of the 22th International Conference on Very Large Data Bases, p.413-424, September 03-06, 1996
• 12: Lucian Popa , Yannis Velegrakis , Mauricio A. Hernández , Renée J. Miller , Ronald Fagin, Translating web data, Proceedings of the 28th international conference on Very Large Data Bases, p.598-609, August 20-23, 2002, Hong Kong, China
• 13: G. Qian, Y. Dong. Constructing Maintainable Semantic Mappings in XQuery. WebDB 2005:121--126.
• 14: Albrecht Schmidt , Florian Waas , Martin Kersten , Michael J. Carey , Ioana Manolescu , Ralph Busse, XMark: a benchmark for XML data management, Proceedings of the 28th international conference on Very Large Data Bases, p.974-985, August 20-23, 2002, Hong Kong, China
• 15: Igor Tatarinov , Alon Halevy, Efficient query reformulation in peer data management systems, Proceedings of the 2004 ACM SIGMOD international conference on Management of data, June 13-18, 2004, Paris, France [doi>10.1145/1007568.1007629]
• 16: XQEngine. http://www.fatdog.com
• 17: Yannis Velegrakis , J. Miller , Lucian Popa, Preserving mapping consistency under schema changes, The VLDB Journal — The International Journal on Very Large Data Bases, v.13 n.3, p.274-293, September 2004 [doi>10.1007/s00778-004-0136-2]
• 18: 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]
• 19: 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.5 Heterogeneous Databases

General Terms:
Algorithms, Design, Experimentation

Keywords:
mapping composition, schema mapping, xml, xquery