Core schema mappings

ABSTRACT

Research has investigated mappings among data sources under two perspectives. On one side, there are studies of practical tools for schema mapping generation; these focus on algorithms to generate mappings based on visual specifications provided by users. On the other side, we have theoretical researches about data exchange. These study how to generate a solution - i.e., a target instance - given a set of mappings usually specified as tuple generating dependencies. However, despite the fact that the notion of a core of a data exchange solution has been formally identified as an optimal solution, there are yet no mapping systems that support core computations. In this paper we introduce several new algorithms that contribute to bridge the gap between the practice of mapping generation and the theory of data exchange. We show how, given a mapping scenario, it is possible to generate an executable script that computes core solutions for the corresponding data exchange problem. The algorithms have been implemented and tested using common runtime engines to show that they guarantee very good performances, orders of magnitudes better than those of known algorithms that compute the core as a post-processing step.

REFERENCES

• 1: Bogdan Alexe , Wang-Chiew Tan , Yannis Velegrakis, Comparing and evaluating mapping systems with STBenchmark, Proceedings of the VLDB Endowment, v.1 n.2, August 2008 [doi>10.1145/1454159.1454203]
• 2: Y. An, A. Borgida, R. Miller, and J. Mylopoulos. A Semantic Approach to Discovering Schema Mapping Expressions. In Proc. of ICDE, pages 206--215, 2007.
• 3: Catriel Beeri , Moshe Y. Vardi, A Proof Procedure for Data Dependencies, Journal of the ACM (JACM), v.31 n.4, p.718-741, Oct. 1984 [doi>10.1145/1634.1636]
• 4: Philip Bohannon , Eiman Elnahrawy , Wenfei Fan , Michael Flaster, Putting context into schema matching, Proceedings of the 32nd international conference on Very large data bases, September 12-15, 2006, Seoul, Korea
• 5: A. Bonifati , G. Mecca , A. Pappalardo , S. Raunich , G. Summa, Schema mapping verification: the spicy way, Proceedings of the 11th international conference on Extending database technology: Advances in database technology, March 25-29, 2008, Nantes, France [doi>10.1145/1353343.1353358]
• 6: Loreto Bravo , Wenfei Fan , Shuai Ma, Extending dependencies with conditions, Proceedings of the 33rd international conference on Very large data bases, September 23-27, 2007, Vienna, Austria
• 7: Luca Cabibbo, On keys, foreign keys and nullable attributes in relational mapping systems, Proceedings of the 12th International Conference on Extending Database Technology: Advances in Database Technology, March 24-26, 2009, Saint Petersburg, Russia [doi>10.1145/1516360.1516392]
• 8: L. Chiticariu. Computing the Core in Data Exchange: Algorithmic Issues. MS Project Report, 2005. Unpublished manuscript.
• 9: Ronald Fagin , Phokion G. Kolaitis , Renée J. Miller , Lucian Popa, Data exchange: semantics and query answering, Theoretical Computer Science, v.336 n.1, p.89-124, 25 May 2005 [doi>10.1O16/j.tcs.2004.10.033]
• 10: Ronald Fagin , Phokion G. Kolaitis , Alan Nash , Lucian Popa, Towards a theory of schema-mapping optimization, Proceedings of the twenty-seventh ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 09-12, 2008, Vancouver, Canada [doi>10.1145/1376916.1376922]
• 11: Ronald Fagin , Phokion G. Kolaitis , Lucian Popa, Data exchange: getting to the core, ACM Transactions on Database Systems (TODS), v.30 n.1, p.174-210, March 2005 [doi>10.1145/1061318.1061323]
• 12: 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
• 13: Georg Gottlob , Alan Nash, Efficient core computation in data exchange, Journal of the ACM (JACM), v.55 n.2, p.1-49, May 2008 [doi>10.1145/1346330.1346334]
• 14: Todd J. Green , Grigoris Karvounarakis , Zachary G. Ives , Val Tannen, Update exchange with mappings and provenance, Proceedings of the 33rd international conference on Very large data bases, September 23-27, 2007, Vienna, Austria
• 15: Pavol Hell , Jaroslav Nešetřil, The core of a graph, Discrete Mathematics, v.109 n.1-3, p.117-126, Nov. 12, 1992 [doi>10.1016/0012-365X(92)90282-K]
• 16: Alon Y. Levy , Alberto O. Mendelzon , Yehoshua Sagiv, Answering queries using views (extended abstract), Proceedings of the fourteenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.95-104, May 22-25, 1995, San Jose, California, United States [doi>10.1145/212433.220198]
• 17: 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
• 18: 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
• 19: Alessandro Raffio , Daniele Braga , Stefano Ceri , Paolo Papotti , Mauricio A. Hernandez, Clip: a Visual Language for Explicit Schema Mappings, Proceedings of the 2008 IEEE 24th International Conference on Data Engineering, p.30-39, April 07-12, 2008 [doi>10.1109/ICDE.2008.4497411]
• 20: Reinhard Pichler , Vadim Savenkov, Towards Practical Feasibility of Core Computation in Data Exchange, Proceedings of the 15th International Conference on Logic for Programming, Artificial Intelligence, and Reasoning, November 22-27, 2008, Doha, Qatar [doi>10.1007/978-3-540-89439-1_5]
• 21: B. ten Cate, L. Chiticariu, P. Kolaitis, and W. C. Tan. Laconic Schema Mappings: Computing Core Universal Solutions by Means of SQL Queries. Unpublished manuscript -http://arxiv.org/abs/0903.1953, March 2009.
• 22: Ling Ling Yan , Renée J. Miller , Laura M. Haas , Ronald Fagin, Data-driven understanding and refinement of schema mappings, Proceedings of the 2001 ACM SIGMOD international conference on Management of data, p.485-496, May 21-24, 2001, Santa Barbara, California, United States

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT

General Terms:
Algorithms, Design

Keywords:
core computation, data exchange, schema mappings