[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ skip to main content
10.1145/1514894.1514905acmotherconferencesArticle/Chapter ViewAbstractPublication PagesedbtConference Proceedingsconference-collections
research-article
Free access

Querying data sources that export infinite sets of views

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.
[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.
[3]
F. N. Afrati, C. Li, and P. Mitra. Answering queries using views with arithmetic comparisons. In PODS, 2002.
[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.
[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.
[7]
A. Deutsch, B. Ludaescher, and A. Nash. Rewriting queries using views with access patterns under integrity constraints. In ICDT, 2005.
[8]
A. Deutsch, L. Popa, and V. Tannen. Query reformulation with constraints. SIGMOD Record, 35(1):65--73, 2006.
[9]
A. Deutsch and V. Tannen. Reformulation of XML queries and constraints. In ICDT, 2003.
[10]
R. Fagin, P. G. Kolaitis, R. J. Miller, and L. Popa. Data exchange: Semantics and query answering. In ICDT, 2003.
[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.
[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.
[13]
A. Y. Levy, A. O. Mendelzon, Y. Sagiv, and D. Srivastava. Answering queries using views. In PODS, pages 95--104, 1995.
[14]
A. Y. Levy, A. Rajaraman, and J. D. Ullman. Answering queries using limited external processors. In PODS, pages 227--237, 1996.
[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.
[16]
C. Li and E. Y. Chang. Query planning with limited source capabilities. In ICDE, pages 401--412, 2000.
[17]
A. Maier, A. Mendelzon, and Y. Sagiv. Testing implications of data dependencies. In PODS, 1979.
[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.
[19]
A. Nash and B. Ludäscher. Processing first-order queries under limited access patterns. In PODS, 2004.
[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.
[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.
[22]
V. Vassalos and Y. Papakonstantinou. Describing and using query capabilities of heterogeneous sources. In VLDB, pages 256--265, 1997.
[23]
V. Vassalos and Y. Papakonstantinou. Expressive capabilities description languages and query rewriting algorithms. J. Log. Program., 43(1):75--122, 2000.

Cited By

View all

Recommendations

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
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.

Check for updates

Qualifiers

  • Research-article

Funding Sources

Conference

EDBT/ICDT '09
EDBT/ICDT '09: EDBT/ICDT '09 joint conference
March 23 - 25, 2009
St. Petersburg, Russia

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)56
  • Downloads (Last 6 weeks)10
Reflects downloads up to 12 Dec 2024

Other Metrics

Citations

Cited By

View all
  • (2015)The complexity of higher-order queriesInformation and Computation10.1016/j.ic.2015.07.003244:C(172-202)Online publication date: 1-Oct-2015
  • (2011)Composition with Target ConstraintsLogical Methods in Computer Science10.2168/LMCS-7(3:13)20117:3Online publication date: 8-Sep-2011
  • (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
  • (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
  • (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
  • (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
  • (2010)Composition with target constraintsProceedings of the 13th International Conference on Database Theory10.1145/1804669.1804687(129-142)Online publication date: 23-Mar-2010
  • (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

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Login options

Media

Figures

Other

Tables

Share

Share

Share this Publication link

Share on social media