Constraint-based XML query rewriting for data integration

ABSTRACT

We study the problem of answering queries through a target schema, given a set of mappings between one or more source schemas and this target schema, and given that the data is at the sources. The schemas can be any combination of relational or XML schemas, and can be independently designed. In addition to the source-to-target mappings, we consider as part of the mapping scenario a set of target constraints specifying additional properties on the target schema. This becomes particularly important when integrating data from multiple data sources with overlapping data and when such constraints can express data merging rules at the target. We define the semantics of query answering in such an integration scenario, and design two novel algorithms, basic query rewrite and query resolution, to implement the semantics. The basic query rewrite algorithm reformulates target queries in terms of the source schemas, based on the mappings. The query resolution algorithm generates additional rewritings that merge related information from multiple sources and assemble a coherent view of the data, by incorporating target constraints. The algorithms are implemented and then evaluated using a comprehensive set of experiments based on both synthetic and real-life data integration scenarios.

REFERENCES

• 1: Serge Abiteboul , Nicole Bidoit, Non first normal form relations: An algebra allowing data restructuring, Journal of Computer and System Sciences, v.33 n.3, p.361-393, Dec. 1986 [doi>10.1016/0022-0000(86)90058-9]
• 2: Bernd Amann , Catriel Beeri , Irini Fundulaki , Michel Scholl, Querying XML Sources Using an Ontology-Based Mediator, On the Move to Meaningful Internet Systems, 2002 - DOA/CoopIS/ODBASE 2002 Confederated International Conferences DOA, CoopIS and ODBASE 2002, p.429-448, October 30-November 01, 2002
• 3: Catriel Beeri , Alon Y. Levy , Marie-Christine Rousset, Rewriting queries using views in description logics, Proceedings of the sixteenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.99-108, May 11-15, 1997, Tucson, Arizona, United States [doi>10.1145/263661.263673]
• 4: 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]
• 5: Michael Benedikt , Chee-Yong Chan , Wenfei Fan , Juliana Freire , Rajeev Rastogi, Capturing both types and constraints in data integration, Proceedings of the 2003 ACM SIGMOD international conference on Management of data, June 09-12, 2003, San Diego, California [doi>10.1145/872757.872792]
• 6: Diego Calvanese , Moshe Y. Vardi , Giuseppe de Giacomo , Maurizio Lenzerini, View-based query processing for regular path queries with inverse, Proceedings of the nineteenth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.58-66, May 15-18, 2000, Dallas, Texas, United States [doi>10.1145/335168.335207]
• 7: D. Chamberlin, XQuery: An XML query language, IBM Systems Journal, v.41 n.4, p.597-615, October 2002
• 8: A. Chapman, C. Yu, and H. V. Jagadish. Effective integration of protein data through better data modeling. OMICS: A Journal of Integrative Biology, 7(1):101--102, 2003.
• 9: Alin Deutsch , Lucian Popa , Val Tannen, Physical Data Independence, Constraints, and Optimization with Universal Plans, Proceedings of the 25th International Conference on Very Large Data Bases, p.459-470, September 07-10, 1999
• 10: A. Deutsch and V. Tannen. MARS: A system for publishing XML from mixed and redundant storage. In VLDB, 2003.
• 11: Alin Deutsch , Val Tannen, Reformulation of XML Queries and Constraints, Proceedings of the 9th International Conference on Database Theory, p.225-241, January 08-10, 2003
• 12: O. Duschka, M. Genesereth, and A. Levy. Recursive query plans for data integration. Journal of Logic Programming, 43(1):49--73, 2000.
• 13: Oliver M. Duschka , Michael R. Genesereth, Answering recursive queries using views, Proceedings of the sixteenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.109-116, May 11-15, 1997, Tucson, Arizona, United States [doi>10.1145/263661.263674]
• 14: 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
• 15: Mary Fernández , Yana Kadiyska , Dan Suciu , Atsuyuki Morishima , Wang-Chiew Tan, SilkRoute: A framework for publishing relational data in XML, ACM Transactions on Database Systems (TODS), v.27 n.4, p.438-493, December 2002 [doi>10.1145/582410.582413]
• 16: Marc Friedman , Alon Levy , Todd Millstein, Navigational plans for data integration, Proceedings of the sixteenth national conference on Artificial intelligence and the eleventh Innovative applications of artificial intelligence conference innovative applications of artificial intelligence, p.67-73, July 18-22, 1999, Orlando, Florida, United States
• 17: Alon Y. Halevy, Answering queries using views: A survey, The VLDB Journal — The International Journal on Very Large Data Bases, v.10 n.4, p.270-294, December 2001 [doi>10.1007/s007780100054]
• 18: Vanja Josifovski , Peter Schwarz , Laura Haas , Eileen Lin, Garlic: a new flavor of federated query processing for DB2, Proceedings of the 2002 ACM SIGMOD international conference on Management of data, June 03-06, 2002, Madison, Wisconsin [doi>10.1145/564691.564751]
• 19: R. Krishnamurthy, R. Kaushik, and J. F. Naughton. XML-SQL Query Translation Literature: The State of the Art and Open Problems. In XSym, 2003.
• 20: 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]
• 21: 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]
• 22: Ioana Manolescu , Daniela Florescu , Donald Kossmann, Answering XML Queries on Heterogeneous Data Sources, Proceedings of the 27th International Conference on Very Large Data Bases, p.241-250, September 11-14, 2001
• 23: 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
• 24: Yannis Papakonstantinou , Vasilis Vassalos, Query rewriting for semistructured data, Proceedings of the 1999 ACM SIGMOD international conference on Management of data, p.455-466, May 31-June 03, 1999, Philadelphia, Pennsylvania, United States
• 25: Lucian Popa , Val Tannen, An Equational Chase for Path-Conjunctive Queries, Constraints, and Views, Proceeding of the 7th International Conference on Database Theory, p.39-57, January 10-12, 1999
• 26: L. Popa, Y. Velegrakis, R. J. Miller, M. A. Hernández, and R. Fagin. Translating web data. In VLDB, 2002.
• 27: Erhard Rahm , Philip A. Bernstein, A survey of approaches to automatic schema matching, The VLDB Journal — The International Journal on Very Large Data Bases, v.10 n.4, p.334-350, December 2001 [doi>10.1007/s007780100057]
• 28: Jayavel Shanmugasundaram , Jerry Kiernan , Eugene J. Shekita , Catalina Fan , John Funderburk, Querying XML Views of Relational Data, Proceedings of the 27th International Conference on Very Large Data Bases, p.261-270, September 11-14, 2001
• 29: Ron van der Meyden, Logical approaches to incomplete information: a survey, Logics for databases and information systems, Kluwer Academic Publishers, Norwell, MA, 1998