Abstract
We address the problem of answering queries using expressive symmetric inter-schema constraints which allow to establish mappings between several heterogeneous information systems. This problem is of high relevance to data integration, as symmetric constraints are essential for dealing with true concept mismatch and are generalizations of the kinds of mappings supported by both local-as-view and global-as-view approaches that were previously studied in the literature. Moreover, the flexibility gained by using such constraints for data integration is essential for virtual enterprise and e-commerce applications. We first discuss resolution-based methods for computing maximally contained rewritings and characterize computability aspects. Then we propose an alternative but semantically equivalent perspective based on a generalization of results relating to the database-theoretic problem of answering queries using views. This leads to a fast query rewriting algorithm, which has been implemented and experimentally evaluated.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
S. Adali, K. S. Candan, Y. Papakonstantinou, and V. S. Subrahmanian. “Query Caching and Optimization in Distributed Mediator Systems”. In Proceedings of the 1996 ACM SIGMOD International Conference on Management of Data (SIGMOD’96), pages 137–146, Montreal, Canada, June 1996.
Y. Arens and C. A. Knoblock. “Planning and Reformulating Queries for Semantically-Modeled Multidatabase Systems”. In Proceedings of the First International Conference on Information and Knowledge Management (CIKM’92), Baltimore, MD USA, 1992.
D. Calvanese, G. De Giacomo, and M. Lenzerini. “On the Decidability of Query Containment under Constraints”. In Proc. PODS’98, pages 149–158, 1998.
D. Calvanese, G. De Giacomo, M. Lenzerini, D. Nardi, and R. Rosati. “Information Integration: Conceptual Modeling and Reasoning Support”. In Proc. CoopIS’98, pages 280–291, 1998.
M. Carey, L. Haas, P. Schwarz, M. Arya, W. Cody, R. Fagin, M. Flickner, A. Luniewski, W. Niblack, D. Petkovic, J. Thomas, J. Williams, and E. Wimmers. “Towards Heterogeneous Multimedia Information Systems: The Garlic Approach”. In Proceedings of the Fifth International Workshop on Research Issues in Data Engineering: Distributed Object Management (RIDE-DOM’95), 1995.
A. K. Chandra and P. M. Merlin. “Optimal Implementation of Conjunctive Queries in Relational Data Bases”. In Conference Record of the Ninth Annual ACM Symposium on Theory of Computing (STOC’77), pages 77–90, Boulder, USA, 1977.
E. Dantsin and A. Voronkov. “Complexity of Query Answering in Logic Databases with Complex Values”. In LFCS’97, LNCS 1234, pages 56–66, 1997.
O. M. Duschka and M. R. Genesereth. “Answering Recursive Queries using Views”. In Proc. PODS’97, Tucson, AZ USA, 1997.
O. M. Duschka, M. R. Genesereth, and A. Y. Levy. “Recursive Query Plans for Data Integration”. Journal of Logic Programming, 43(1):49–73, 2000.
H. Garcia-Molina, Y. Papakonstantinou, D. Quass, A. Rajaraman, Y. Sagiv, J. D. Ullman, V. Vassalos, and J. Widom. “The TSIMMIS Approach to Mediation: Data Models and Languages”. Journal of Intelligent Information Systems, 8(2), 1997.
M. R. Genesereth, A. M. Keller, and O. M. Duschka. “Infomaster: An Information Integration System”. In Proceedings of the 1997 ACM SIGMOD International Conference on Management of Data (SIGMOD’97), pages 539–542, 1997.
J. Gryz. “Query Rewriting Using Views in the Presence of Functional and Inclusion Dependencies”. Information Systems, 24(7):597–612, 1999.
C. Koch. “Cindrew Home Page”. http://cern.ch/chkoch/cindrew/.
C. Koch. “Data Integration against Multiple Evolving Autonomous Schemata”. PhD thesis, TU Wien, Vienna, Austria, 2001.
C. T. Kwok and D. S. Weld. “Planning to Gather Information”. In Proc. AAAI’96, Portland, OR USA, Aug. 1996.
A. Y. Levy, A. O. Mendelzon, Y. Sagiv, and D. Srivastava. “Answering Queries Using Views”. In Proc. PODS’95, San Jose, CA USA, 1995.
A. Y. Levy, A. Rajaraman, and J. J. Ordille. “Querying Heterogeneous Information Sources Using Source Descriptions”. In Proceedings of the 1996 International Conference on Very Large Data Bases (VLDB’96), pages 251–262, 1996.
R. Pottinger and A. Y. Levy. “A Scalable Algorithm for Answering Queries Using Views”. In Proceedings of the 26th International Conference on Very Large Data Bases (VLDB’2000), 2000.
X. Qian. “Query Folding”. In Proceedings of the 12th IEEE International Conference on Data Engineering (ICDE’96), pages 48–55, New Orleans, LA USA, 1996.
M. F. Sipser. Introduction to the Theory of Computation. PWS Publishing, 1997.
S. Vorobyov and A. Voronkov. “Complexity of Nonrecursive Logic Programs with Complex Values”. In Proc. PODS’98, 1998.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2002 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Koch, C. (2002). Query Rewriting with Symmetric Constraints. In: Eiter, T., Schewe, KD. (eds) Foundations of Information and Knowledge Systems. FoIKS 2002. Lecture Notes in Computer Science, vol 2284. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-45758-5_9
Download citation
DOI: https://doi.org/10.1007/3-540-45758-5_9
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-43220-3
Online ISBN: 978-3-540-45758-9
eBook Packages: Springer Book Archive