More Web Proxy on the site http://driver.im/

article

Answering queries with useful bindings

Authors:

Edward ChangAuthors Info & Claims

ACM Transactions on Database Systems (TODS), Volume 26, Issue 3

Pages 313 - 343

https://doi.org/10.1145/502030.502032

Published: 01 September 2001 Publication History

Abstract

In information-integration systems, sources may have diverse and limited query capabilities. To obtain maximum information from these restrictive sources to answer a query, one can access sources that are not specified in the query (i.e., off-query sources). In this article, we propose a query-planning framework to answer queries in the presence of limited access patterns. In the framework, a query and source descriptions are translated to a recursive datalog program. We then solve optimization problems in this framework, including how to decide whether accessing off-query sources is necessary, how to choose useful sources for a query, and how to test query containment. We develop algorithms to solve these problems, and thus construct an efficient program to answer a query.

References

[1]

ABITEBOUL,S.AND DUSCHKA, O. M. 1998. Complexity of answering queries using materialized views. In Proceedings of the ACM Symposium on Principles of Database Systems (PODS), 254- 263.]]

Digital Library

[2]

AHO,A.V.,HOPCROFT,J.E.,AND ULLMAN, J. D. 1983. Data Structures and Algorithms. Addison-Wesley, Reading, Mass.]]

Digital Library

[3]

BANCILHON,F.AND RAMAKRISHNAN, R. 1986. An amateur's introduction to recursive query processing strategies. In Proceedings of ACM SIGMOD, 16-52.]]

Digital Library

[4]

BAYARDO,JR., R. J. ET AL. 1997. Infosleuth: Semantic integration of information in open and dynamic environments (experience paper). In Proceedings of ACM SIGMOD, 195-206.]]

Digital Library

[5]

BEERI,C.AND RAMAKRISHNAN, R. 1987. On the power of magic. In Proceedings of the ACM Symposium on Principles of Database Systems (PODS), 269-283.]]

Digital Library

[6]

CAREY,M.J.,HAAS, L. M., SCHWARZ, P. M., ARYA, M., CODY, W. F., FAGIN, R., FLICKNER, M., LUNIEWSKI, A., NIBLACK, W., PETKOVIC,D.II,J.T.,WILLIAMS,J.H.,AND WIMMERS, E. L. 1995. Towards heterogeneous multimedia information systems: The garlic approach. In Proceedings of RIDE-DOM, 124-131.]]

Digital Library

[7]

CHANDRA,A.K.AND MERLIN, P. M. 1977. Optimal implementations of conjunctive queries in relational data bases. In Proceedings of the Ninth ACMSymposium on Theory of Computing (STOC), ACM, New York, 77-90.]]

Digital Library

[8]

CHAUDHURI,S.AND VARDI, M. Y. 1992. On the equivalence of recursive and nonrecursive datalog programs. In Proceedings of the ACM Symposium on Principles of Database Systems (PODS), 55-66.]]

Digital Library

[9]

CHAWATHE, S., GARCIA-MOLINA, H., HAMMER, J., IRELAND, K., PAPAKONSTANTINOU, Y., ULLMAN,J.D.,AND WIDOM, J. 1994. The TSIMMIS project: Integration of heterogeneous information sources. In Proceedings of the Sixteenth Meeting of the Information Processing Society of Japan (Tokyo), 7-18.]]

[10]

CLUET, S., DELOBEL, C., SIMEON,J.,AND SMAGA, K. 1998. Your mediators need data conversion! In Proceedings of ACM SIGMOD, 177-188.]]

Digital Library

[11]

COSMADAKIS,S.S.,GAIFMAN, H., KANELLAKIS,P.C.,AND VARDI, M. Y. 1988. Decidable optimization problems for database logic programs. In Proceedings of the Twentieth ACMSymposium on Theory of Computing, 477-490.]]

Digital Library

[12]

DUSCHKA, O. M. 1998. Query planning and optimization in information integration. PhD thesis, Stanford University, Stanford, Calif.]]

Digital Library

[13]

DUSCHKA,O.M.AND GENESERETH, M. R. 1997. Answering recursive queries using views. In Proceedings of the ACM Symposium on Principles of Database Systems (PODS), 109-116.]]

Digital Library

[14]

DUSCHKA,O.M.AND LEVY, A. Y. 1997. Recursive plans for information gathering. In Proceedings of the Fifteenth International Joint Conference on Artificial Intelligence (Nagoya, Japan), 778-784.]]

[15]

FLORESCU, D., LEVY, A., MANOLESCU, I., AND SUCIU, D. 1999. Query optimization in the presence of limited access patterns. In Proceedings of ACM SIGMOD, 311-322.]]

Digital Library

[16]

GAIFMAN, H., MAIRSON, H., SAGIV,Y.,AND VARDI, M. Y. 1993. Undecidable optimization problems for database logic programs. J. ACM 40, 3, 683-713.]]

Digital Library

[17]

GENESERETH, M. R., KELLER,A.M.,AND DUSCHKA, O. M. 1997. Infomaster: An information integration system. In Proceedings of ACM SIGMOD, 539-542.]]

Digital Library

[18]

HAAS, L. M., KOSSMANN, D., WIMMERS,E.L.,AND YANG, J. 1997. Optimizing queries across diverse data sources. In Proceedings of VLDB, 276-285.]]

Digital Library

[19]

HAMMER, J., GARCYA-MOLINA, H., NESTOROV, S., YERNENI, R., BREUNIG, M., AND VASSALOS, V. 1997. Template-based wrappers in the TSIMMIS system. In Proceedings of ACM SIGMOD, 532-535.]]

Digital Library

[20]

IVES, Z., FLORESCU, D., FRIEDMAN, M., LEVY, A., AND WELD, D. 1999. An adaptive query execution engine for data integration. In Proceedings of ACM SIGMOD, 299-310.]]

Digital Library

[21]

LEVY,A.Y.,MENDELZON,A.O.,SAGIV,Y.,AND SRIVASTAVA, D. 1995. Answering queries using views. In Proceedings of the ACM Symposium on Principles of Database Systems (PODS), 95-104.]]

Digital Library

[22]

LEVY,A.Y.,RAJARAMAN, A., AND ORDILLE, J. J. 1996. Querying heterogeneous information sources using source descriptions. In Proceedings of VLDB, 251-262.]]

Digital Library

[23]

LI,C.AND CHANG, E. 1999. Testing query containment in the presence of limited access patterns. Tech. Rep., Computer Science Dept., Stanford University.]]

[24]

LI,C.AND CHANG, E. 2000. Query planning with limited source capabilities. In Proceedings of the International Conference on Data Engineering (ICDE), 401-412.]]

Digital Library

[25]

LI,C.AND CHANG, E. 2001. On answering queries in the presence of limited access patterns. In Proceedings of the International Conference on Database Theory (ICDT), 99-113.]]

Digital Library

[26]

LI, C., YERNENI, R., VASSALOS, V., GARCIA-MOLINA, H., PAPAKONSTANTINOU, Y., ULLMAN,J.D.,AND VALIVETI, M. 1998. Capability based mediation in TSIMMIS. In Proceedings of ACMSIGMOD, 564-566.]]

Digital Library

[27]

MALUF,D.A.AND WIEDERHOLD, G. 1997. Abstraction of representation for interoperation. In Proceedings of the International Symposium on Methodologies for Intelligent Systems (ISMIS), 441-455.]]

Digital Library

[28]

MILLSTEIN, T., LEVY, A., AND FRIEDMAN, M. 2000. Query containment for data integration systems. In Proceedings of the ACM Symposium on Principles of Database Systems (PODS).]]

Digital Library

[29]

PAPAKONSTANTINOU, Y., GARCIA-MOLINA, H., AND WIDOM, J. 1995. Object exchange across heterogeneous information sources. In Proceedings of the Eleventh. Conference on Data Engineering (Taipei, Taiwan), P. S. Yu and A. L. P. Chen, Eds., IEEE Computer Society, Los Alamitos, Calif., 251-260.]]

Digital Library

[30]

QIAN, X. 1996. Query folding. In Proceedings of the International Conference on Data Engineering (ICDE), 48-55.]]

Digital Library

[31]

RAJARAMAN, A., SAGIV,Y.,AND ULLMAN, J. D. 1995. Answering queries using templates with binding patterns. In Proceedings of the ACMSymposium on Principles of Database Systems (PODS), 105- 112.]]

Digital Library

[32]

SAGIV,Y.AND YANNAKAKIS, M. 1980. Equivalences among relational expressions with the union and difference operators. J. ACM 27, 4, 633-655.]]

Digital Library

[33]

SHMUELI, O. 1993. Equivalence of datalog queries is undecidable. J. Logic Program. 15, 3, 231- 241.]]

Digital Library

[34]

TOMASIC, A., RASCHID, L., AND VALDURIEZ, P. 1998. Scaling access to heterogeneous data sources with DISCO. IEEE Trans. Knowl. Data Eng. 10, 5, 808-823.]]

Digital Library

[35]

ULLMAN, J. D. 1989. Principles of Database and Knowledge-base Systems, Vol. II: The New Technologies. Computer Science Press, New York.]]

Digital Library

[36]

ULLMAN, J. D. 1997. Information integration using logical views. In Proceedings of the International Conference on Database Theory (ICDT), 19-40.]]

Digital Library

[37]

VASSALOS,V.AND PAPAKONSTANTINOU, Y. 1997. Describing and using query capabilities of heterogeneous sources. In Proceedings of VLDB, 256-265.]]

Digital Library

[38]

WIEDERHOLD, G. 1992. Mediators in the architecture of future information systems. IEEE Comput. 25, 3, 38-49.]]

Digital Library

[39]

YERNENI, R., LI, C., GARCIA-MOLINA, H., AND ULLMAN, J. D. 1999. Computing capabilities of mediators. In Proceedings of ACM SIGMOD, 443-454.]]

Digital Library

[40]

YERNENI, R., LI, C., ULLMAN,J.D.,AND GARCIA-MOLINA, H. 1999. Optimizing large join queries in mediation systems. In Proceedings of the International Conference on Database Theory (ICDT), 348-364.]]

Digital Library

Cited By

Martinenghi D(2023)Access PatternEncyclopedia of Cryptography, Security and Privacy10.1007/978-3-642-27739-9_670-2(1-5)Online publication date: 4-Oct-2023
https://doi.org/10.1007/978-3-642-27739-9_670-2
Afrati FChirkova R(2019)Answering Queries Using Views, Second EditionSynthesis Lectures on Data Management10.2200/S00884ED2V01Y201811DTM05414:3(1-275)Online publication date: 15-Apr-2019
https://doi.org/10.2200/S00884ED2V01Y201811DTM054
Benedikt MBourhis PGottlob GSenellart P(2019)Monadic Datalog, Tree Validity, and Limited Access ContainmentACM Transactions on Computational Logic10.1145/334451421:1(1-45)Online publication date: 4-Oct-2019
https://dl.acm.org/doi/10.1145/3344514
Show More Cited By

Index Terms

Answering queries with useful bindings

Recommendations

Query Planning with Limited Source Capabilities
ICDE '00: Proceedings of the 16th International Conference on Data Engineering

In information-integration systems, sources may have diverse and limited query capabilities. In this paper we show that because sources have restrictions on retrieving their information, sources not mentioned in a query can contribute to the query ...
Decidable containment of recursive queries
Database theory

One of the most important reasoning tasks on queries is checking containment, i.e., verifying whether one query yields necessarily a subset of the result of another one. Query containment is crucial in several contexts, such as query optimization, query ...
Rewriting general conjunctive queries using views

The problem of rewriting queries using views has important applications in data integration, query optimization, and physical data independence maintenance. Previous researchers have proposed rewriting algorithms for queries and views that are Datalog ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Transactions on Database Systems

ACM Transactions on Database Systems Volume 26, Issue 3

September 2001

123 pages

ISSN:0362-5915

EISSN:1557-4644

DOI:10.1145/502030

Issue’s Table of Contents

Copyright © 2001 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 September 2001

Published in TODS Volume 26, Issue 3

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

33
Total Citations
View Citations
284
Total Downloads

Downloads (Last 12 months)9
Downloads (Last 6 weeks)1

Reflects downloads up to 14 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Martinenghi D(2023)Access PatternEncyclopedia of Cryptography, Security and Privacy10.1007/978-3-642-27739-9_670-2(1-5)Online publication date: 4-Oct-2023
https://doi.org/10.1007/978-3-642-27739-9_670-2
Afrati FChirkova R(2019)Answering Queries Using Views, Second EditionSynthesis Lectures on Data Management10.2200/S00884ED2V01Y201811DTM05414:3(1-275)Online publication date: 15-Apr-2019
https://doi.org/10.2200/S00884ED2V01Y201811DTM054
Benedikt MBourhis PGottlob GSenellart P(2019)Monadic Datalog, Tree Validity, and Limited Access ContainmentACM Transactions on Computational Logic10.1145/334451421:1(1-45)Online publication date: 4-Oct-2019
https://dl.acm.org/doi/10.1145/3344514
Benedikt M(2018)Logic-based Perspectives on Query Reformulationover Restricted InterfacesACM SIGMOD Record10.1145/3299887.329988947:2(5-16)Online publication date: 11-Dec-2018
https://dl.acm.org/doi/10.1145/3299887.3299889
Amarilli ABenedikt MVan den Bussche JArenas M(2018)When Can We Answer Queries Using Result-Bounded Data Interfaces?Proceedings of the 37th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems10.1145/3196959.3196965(281-293)Online publication date: 27-May-2018
https://dl.acm.org/doi/10.1145/3196959.3196965
Afrati FChirkova R(2017)Answering Queries Using ViewsSynthesis Lectures on Data Management10.2200/S00805ED1V01Y201709DTM0469:2(1-235)Online publication date: Dec-2017
https://doi.org/10.2200/S00805ED1V01Y201709DTM046
Calí AAkerkar RCuzzocrea ACao JHacid M(2017)Querying and searching the deep webProceedings of the 7th International Conference on Web Intelligence, Mining and Semantics10.1145/3102254.3102257(1-1)Online publication date: 19-Jun-2017
https://dl.acm.org/doi/10.1145/3102254.3102257
Calvanese DDe Giacomo GLenzerini MVardi M(2016)Regular open APIsProceedings of the Fifteenth International Conference on Principles of Knowledge Representation and Reasoning10.5555/3032027.3032067(329-338)Online publication date: 25-Apr-2016
https://dl.acm.org/doi/10.5555/3032027.3032067
Benedikt MLeblay JCate BTsamoura E(2016)Generating Plans from Proofs: The Interpolation-based Approach to Query ReformulationSynthesis Lectures on Data Management10.2200/S00703ED1V01Y201602DTM0438:1(1-205)Online publication date: 14-Mar-2016
https://doi.org/10.2200/S00703ED1V01Y201602DTM043
Benedikt MTen Cate BTsamoura E(2016)Generating Plans from ProofsACM Transactions on Database Systems10.1145/284752340:4(1-45)Online publication date: 3-Feb-2016
https://dl.acm.org/doi/10.1145/2847523
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Issue’s Table of Contents