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

research-article

Free access

Querying data sources that export infinite sets of views

Authors:

Nicola OnoseAuthors Info & Claims

ICDT '09: Proceedings of the 12th International Conference on Database Theory

Pages 84 - 97

https://doi.org/10.1145/1514894.1514905

Published: 23 March 2009 Publication History

Abstract

We study the problem of querying data sources that accept only a limited set of queries, such as sources accessible by Web services which can implement very large (potentially infinite) families of queries. We revisit a classical setting in which the application queries are conjunctive queries and the source accepts families of conjunctive queries specified as the expansions of a (potentially recursive) Datalog program.

We say that query Q is expressible by the program P if it is equivalent to some expansion of P. Q is supported by P if it has an equivalent rewriting using some finite set of P's expansions. We present the first study of expressibility and support for sources that satisfy integrity constraints, which is generally the case in practice.

References

[1]

S. Abiteboul, R. Hull, and V. Vianu. Foundations of Databases. Addison-Wesley, 1995.

Digital Library

[2]

F. N. Afrati, R. Chirkova, M. Gergatsoulis, and V. Pavlaki. Finding equivalent rewritings in the presence of arithmetic comparisons. In EDBT, pages 942--960, 2006.

Digital Library

[3]

F. N. Afrati, C. Li, and P. Mitra. Answering queries using views with arithmetic comparisons. In PODS, 2002.

Digital Library

[4]

B. Cautis, A. Deutsch, and N. Onose. Querying data sources that export infinite sets of views. Technical Report CS2007--0886, UCSD, 2007. Available at http://db.ucsd.edu/index.jsp?pageStr=publications.

[5]

S. Cohen, W. Nutt, and Y. Sagiv. Rewriting queries with arbitrary aggregation functions using views. ACM Trans. Database Syst. (TODS), 31(2):672--715, 2006.

Digital Library

[6]

S. Cosmadakis, H. Gaifman, P. Kanellakis, and M. Vardi. Decidable optimization problems for database logic programs. In STOC, pages 477--490, New York, NY, USA, 1988. ACM Press.

Digital Library

[7]

A. Deutsch, B. Ludaescher, and A. Nash. Rewriting queries using views with access patterns under integrity constraints. In ICDT, 2005.

Digital Library

[8]

A. Deutsch, L. Popa, and V. Tannen. Query reformulation with constraints. SIGMOD Record, 35(1):65--73, 2006.

Digital Library

[9]

A. Deutsch and V. Tannen. Reformulation of XML queries and constraints. In ICDT, 2003.

Digital Library

[10]

R. Fagin, P. G. Kolaitis, R. J. Miller, and L. Popa. Data exchange: Semantics and query answering. In ICDT, 2003.

Digital Library

[11]

D. Florescu, A. Y. Levy, I. Manolescu, and D. Suciu. Query optimization in the presence of limited access patterns. In SIGMOD, pages 311--322, 1999.

Digital Library

[12]

H. Gaifman, H. G. Mairson, Y. Sagiv, and M. Y. Vardi. Undecidable optimization problems for database logic programs. Journal of the ACM (JACM), 40(3):683--713, 1993.

Digital Library

[13]

A. Y. Levy, A. O. Mendelzon, Y. Sagiv, and D. Srivastava. Answering queries using views. In PODS, pages 95--104, 1995.

Digital Library

[14]

A. Y. Levy, A. Rajaraman, and J. D. Ullman. Answering queries using limited external processors. In PODS, pages 227--237, 1996.

Digital Library

[15]

A. Y. Levy, A. Rajaraman, and J. D. Ullman. Answering queries using limited external query processors. J. Comput. Syst. Sci., 58(1):69--82, 1999.

Digital Library

[16]

C. Li and E. Y. Chang. Query planning with limited source capabilities. In ICDE, pages 401--412, 2000.

Digital Library

[17]

A. Maier, A. Mendelzon, and Y. Sagiv. Testing implications of data dependencies. In PODS, 1979.

Digital Library

[18]

A. Motro. An access authorization model for relational databases based on algebraic manipulation of view definitions. In ICDE, pages 339--347. IEEE Computer Society, 1989.

Digital Library

[19]

A. Nash and B. Ludäscher. Processing first-order queries under limited access patterns. In PODS, 2004.

Digital Library

[20]

Y. Papakonstantinou, A. Gupta, H. Garcia-Molina, and J. D. Ullman. A query translation scheme for rapid implementation of wrappers. In DOOD, pages 161--186, 1995.

Digital Library

[21]

S. Rizvi, A. O. Mendelzon, S. Sudarshan, and P. Roy. Extending query rewriting techniques for fine-grained access control. In SIGMOD, pages 551--562, 2004.

Digital Library

[22]

V. Vassalos and Y. Papakonstantinou. Describing and using query capabilities of heterogeneous sources. In VLDB, pages 256--265, 1997.

Digital Library

[23]

V. Vassalos and Y. Papakonstantinou. Expressive capabilities description languages and query rewriting algorithms. J. Log. Program., 43(1):75--122, 2000.

Cited By

Benedikt MPuppis GVu H(2015)The complexity of higher-order queriesInformation and Computation10.1016/j.ic.2015.07.003244:C(172-202)Online publication date: 1-Oct-2015
https://dl.acm.org/doi/10.1016/j.ic.2015.07.003
Arenas MFagin RNash A(2011)Composition with Target ConstraintsLogical Methods in Computer Science10.2168/LMCS-7(3:13)20117:3Online publication date: 8-Sep-2011
https://doi.org/10.2168/LMCS-7(3:13)2011
Le WDuan SKementsietsidis ALi FWang MSadagopan SRamamritham KKumar ARavindra MBertino EKumar R(2011)Rewriting queries on SPARQL viewsProceedings of the 20th international conference on World wide web10.1145/1963405.1963497(655-664)Online publication date: 28-Mar-2011
https://dl.acm.org/doi/10.1145/1963405.1963497
Show More Cited By

Recommendations

Querying Data Sources that Export Infinite Sets of Views

We study the problem of querying data sources that accept only a limited set of queries, such as sources accessible by Web services which can implement very large (potentially infinite) families of queries. We revisit a classical setting in which the ...
Querying XML data sources that export very large sets of views

We study the problem of querying XML data sources that accept only a limited set of queries, such as sources accessible by Web services which can implement very large (potentially infinite) families of XPath queries. To compactly specify such families ...
Querying data provenance
SIGMOD '10: Proceedings of the 2010 ACM SIGMOD International Conference on Management of data

Many advanced data management operations (e.g., incremental maintenance, trust assessment, debugging schema mappings, keyword search over databases, or query answering in probabilistic databases), involve computations that look at how a tuple was ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Other conferences

ICDT '09: Proceedings of the 12th International Conference on Database Theory

March 2009

334 pages

ISBN:9781605584232

DOI:10.1145/1514894

Editor:
Ronald Fagin
IBM Research

Copyright © 2009 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: 23 March 2009

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Research-article

Funding Sources

Division of Information and Intelligent Systems

Conference

EDBT/ICDT '09

EDBT/ICDT '09: EDBT/ICDT '09 joint conference

March 23 - 25, 2009

St. Petersburg, Russia

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

8
Total Citations
View Citations
218
Total Downloads

Downloads (Last 12 months)56
Downloads (Last 6 weeks)10

Reflects downloads up to 12 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Benedikt MPuppis GVu H(2015)The complexity of higher-order queriesInformation and Computation10.1016/j.ic.2015.07.003244:C(172-202)Online publication date: 1-Oct-2015
https://dl.acm.org/doi/10.1016/j.ic.2015.07.003
Arenas MFagin RNash A(2011)Composition with Target ConstraintsLogical Methods in Computer Science10.2168/LMCS-7(3:13)20117:3Online publication date: 8-Sep-2011
https://doi.org/10.2168/LMCS-7(3:13)2011
Le WDuan SKementsietsidis ALi FWang MSadagopan SRamamritham KKumar ARavindra MBertino EKumar R(2011)Rewriting queries on SPARQL viewsProceedings of the 20th international conference on World wide web10.1145/1963405.1963497(655-664)Online publication date: 28-Mar-2011
https://dl.acm.org/doi/10.1145/1963405.1963497
Cautis BDeutsch AOnose NVassalos V(2011)Querying XML data sources that export very large sets of viewsACM Transactions on Database Systems10.1145/1929934.192993936:1(1-42)Online publication date: 18-Mar-2011
https://dl.acm.org/doi/10.1145/1929934.1929939
Preda NKasneci GSuchanek FNeumann TYuan WWeikum GElmagarmid AAgrawal D(2010)Active knowledgeProceedings of the 2010 ACM SIGMOD International Conference on Management of data10.1145/1807167.1807212(399-410)Online publication date: 6-Jun-2010
https://dl.acm.org/doi/10.1145/1807167.1807212
Benedikt MPuppis GVu HParedaens JVan Gucht D(2010)Positive higher-order queriesProceedings of the twenty-ninth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems10.1145/1807085.1807091(27-38)Online publication date: 6-Jun-2010
https://dl.acm.org/doi/10.1145/1807085.1807091
Arenas MFagin RNash A(2010)Composition with target constraintsProceedings of the 13th International Conference on Database Theory10.1145/1804669.1804687(129-142)Online publication date: 23-Mar-2010
https://dl.acm.org/doi/10.1145/1804669.1804687
Cautis BDeutsch AOnose NVassalos V(2009)Efficient rewriting of XPath queries using Query Set SpecificationsProceedings of the VLDB Endowment10.14778/1687627.16876622:1(301-312)Online publication date: 1-Aug-2009
https://dl.acm.org/doi/10.14778/1687627.1687662

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

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 Publication

Media

Figures

Other

Tables

View Table of Contents