ABSTRACT
In this paper we present a mechanism for translating constraint queries, i.e., Boolean expressions of constraints, across heterogeneous information sources. Integrating such systems is difficult in part because they use a wide range of constraints as the vocabulary for formulating queries. We describe algorithms that apply user-provided mapping rules to translate query constraints into ones that are understood and supported in another context, e.g., that use the proper operators and value formats. We show that the translated queries minimally subsume the original ones. Furthermore, the translated queries are also the most compact possible. Unlike other query mapping work, we effectively consider inter-dependencies among constraints, i.e., we handle constraints that cannot be translated independently. Furthermore, when constraints are not fully supported, our framework explores relaxations (semantic rewritings) into the closest supported version. Our most sophisticated algorithm (Algorithm TDQM) does not blindly convert queries to DNF (which would be easier to translate, but expensive); instead it performs a top-down mapping of a query tree, and does local query structure conversion only when necessary.
- 1.G. Wiederhold. Mediators in the architecture of future information systems. IEEE Computer, 25(3):51-60, 1992. Google Scholar
Digital Library
- 2.J. D. Ullman. Information integration using logical views. In Proc. ICDT, Delphi, Greece, Jan. 1997. Springer, Berlin. Google Scholar
- 3.A. Y. Levy, A. Rajaraman, and J. J. Ordille. Querying heterogeneous information sources using source descriptions. In Proc. I/LDB, Bombay, India, 1996. Google Scholar
- 4.A.Y. Levy, A. Rajaraman, and J. J. Ordille. Query-answering algorithms for information agents. In Proc. of the /3th National Conf. on Artificial Intelligence, AAAI-96, Portland, Oreg., Aug. 1996. AAAI Press, Menlo Park, Calif. Google Scholar
- 5.Y. Papakonstantinou, H. Garcfa-Molina, and J. Ullman. Medmaker: A mediation system based on declarative specifications. In Proc. ICDE, New Orleans, La., 1996. Google Scholar
- 6.Y. Papakonstantinou, H. Garcfa-Molina, A. Gupta, and J. Ullman. A query translation scheme for rapid implementation of wrappers. In Proc. of the 4th International Conf. on Deductive and Object-Oriented Databases, Singapore, Dec. 1995. Google Scholar
- 7.O. M. Duschka. Query Planning and Optimization in Information Integration. PhD thesis, Stanford Univ., 199'7. Google Scholar
- 8.M. R. Genesereth, A. M. Keller, and O. M. Duschka. Infomaster: An information integration system. In Proc. of the 1997 ACM SIGMOD Conf., Tucson, Ariz., 1997. Google Scholar
- 9.L. M. Haas, D. Kossmann, E. L. Wimmers, and J. Yang. Optimizing queries across diverse data sources. In Proc. VLDB, pages 276-285, Athens, Greece, Aug. 1997. Google Scholar
- 10.M. T. Roth and P. M. Schwarz. Don't scrap it, wrap it! a wrapper architecture for legacy data sources. In Proc. VLDB, pages 266-275, Athens, Greece, Aug. 1997. Google Scholar
- 11.O. Kapitskaia, A. Tomasic, and P. Valduriez. Dealing with discrepancies in wrapper functionality. Technical Report RR- 3138, INRIA, 1997.Google Scholar
- 12.H. Garcfa-Molina, W. Labio, and R. Yemeni. Capability sensitive query processing on intemet sources. In Proc. ICDE, Sydney, Australia, Mar. 1999. Google Scholar
- 13.A. Rajaraman, Y. Sagiv, and J. D. Ullman. Answering queries using templates with binding patterns. In Proc. PODS, San Jose, Calif., May 1995. Google Scholar
- 14.A. Y. Levy, A. Rajaraman, and J. D. Ullman. Answering queries using limited external query processors. In Proc. PODS, Montreal, Canada, June 1996. Google Scholar
- 15.C.-C. K. Chang, H. Garcfa-Molina, and A. Paepcke. Boolean query mapping across heterogeneous information sources. IEEE Transactions on Knowledge and Data Engineering, 8(4):515-521, Aug. 1996. Google Scholar
- 16.C.-C. K. Chang, H. Garcfa-Molina, and A. Paepcke. Boolean query mapping across heterogeneous information sources (extended version). Technical Report SIDL-WP-1996- 0044, Stanford Univ., Sept. 1996. http://www-diglib.- stanf ord. edu. Google Scholar
- 17.C.-C. K. Chang and H. Garcfa-Molina. Mind your vocabulary: Query mapping across heterogeneous information sources (extended version). Technical Report SIDL-WP- 1998-0095, Stanford Univ., 1999. htl;p://www-diglih,.- stanford, edu. Google Scholar
- 18.S. Heiler. Semantic interoperability. Computing Surveys, 27(2):271-273, June 1995. Google Scholar
- 19.Y. Papakonstantinou, A. Gupta, and L. Haas. Capabilitiesbased query rewriting in mediator systems. In Proc. PDIS, Miami Beach, Flor., 1996. Google Scholar
- 20.C.-C. K. Chang and H. Garcfa-Molina. Conjunctive constraint mapping for data translation, in Proc. of the Third ACM international Conf. on Digital Libraries, Pittsburgh, Pa., June 1998. ACM Press, New York. Google Scholar
- 21.C.-C. K. Chang, H. Garcfa-Molina, and A. Paepcke. Predicate rewriting for translating boolean queries in a heterogeneous information system. ACM Transactions on Information Systems, 17(1):1-39, Jan. 1999. Google Scholar
- 22.A. V. Aho, J. E. Hopcroft, and J. D. Ullman. The design and analysis of computer algorithms. Addison-Wesley, 1974. Google Scholar
- 23.E. J. McCluskey. Logic Design Principles. Prentice H~all, Englewood Cliffs, N.J., 1986.Google Scholar
Index Terms
- Mind your vocabulary: query mapping across heterogeneous information sources
Recommendations
Mind your vocabulary: query mapping across heterogeneous information sources
In this paper we present a mechanism for translating constraint queries, i.e., Boolean expressions of constraints, across heterogeneous information sources. Integrating such systems is difficult in part because they use a wide range of constraints as ...
Don’t mind your vocabulary: data sharing across heterogeneous peers
OTM'05: Proceedings of the 2005 Confederated international conference on On the Move to Meaningful Internet Systems - Volume >Part IThe strong dynamics of peer-to-peer networks, coupled with the diversity of peer vocabularies, makes query processing in peer database systems a very challenging task. In this paper, we propose a framework for translating expressive relational queries ...
Make up your mind: the price of online queries in differential privacy
SODA '17: Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete AlgorithmsWe consider the problem of answering queries about a sensitive dataset subject to differential privacy. The queries may be chosen adversarially from a larger set Q of allowable queries in one of three ways, which we list in order from easiest to hardest ...
Comments