skip to main content
10.1145/1055558.1055601acmconferencesArticle/Chapter ViewAbstractPublication PagespodsConference Proceedingsconference-collections
Article

Processing first-order queries under limited access patterns

Published: 14 June 2004 Publication History

Abstract

We study the problem of answering queries over sources with limited access patterns. Given a first-order query Q, the problem is to decide whether there is an equivalent query which can be executed observing the access patterns restrictions. If so, we say that Q is feasible. We define feasible for first-order queries---previous definitions handled only some existential cases---and characterize the complexity of many first-order query classes. For each of them, we show that deciding feasibility is as hard as deciding containment. Since feasibility is undecidable in many cases and hard to decide in some others, we also define an approximation to it which can be computed in NP for any first-order query and in P for unions of conjunctive queries with negation. Finally, we outline a practical overall strategy for processing first-order queries under limited access patterns.

References

[1]
{AHV95} S. Abiteboul, R. Hull, and V. Vianu. Foundations of Databases. Addison Wesley, 1995.]]
[2]
{BIR01} Biomedical Informatics Research Network Coordinating Center (BIRN-CC), University of California, San Diego. http://nbirn.net/,2001.]]
[3]
{CM77} A. K. Chandra and P. M. Merlin. Optimal Implementation of Conjunctive Queries in Relational Data Bases. In ACM Symposium on Theory of Computing (STOC), pp. 77--90, 1977.]]
[4]
{DBG+03} E. Deelman, J. Blythe, Y. Gil, C. Kesselman, G. Mehta, K. Vahi, K. Blackburn, A. Lazzarini, A. Arbree, R. Cavanaugh, and S. Koranda. Mapping Abstract Complex Workflows onto Grid Environments. Journal of Grid Computing, 1(1):25--39, 2003.]]
[5]
{DGL00} 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.]]
[6]
{DL97} O. M. Duschka and A. Y. Levy. Recursive Plans for Information Gathering. In Proc. IJCAI, Nagoya, Japan, 1997.]]
[7]
{FLMS99} D. Florescu, A. Y. Levy, I. Manolescu, and D. Suciu. Query Optimization in the Presence of Limited Access Patterns. In SIGMOD, PP. 311 322, 1999.]]
[8]
{GLM03} A. Gupta, B. Ludäscher, and M. Martone. BIRN-M: A Semantic Mediator for Solving Real-World Neuroscience Problems. In ACM Intl. Conference on Management of Data (SIGMOD), 2003.]]
[9]
{GT91} A. V. Gelder and R. W. Topor. Safety and Translation of Relational Calculus Queries. ACM Transactions on Database Systems (TODS), 16(2):235--278, 1991.]]
[10]
{HBCS03} R. Hull, M. Benedikt, V. Christophides, and J. Su. E-Services: A Look Behind the Curtain. In ACM Symposium on Principles of Database Systems (PODS), pp. 1--14, 2003.]]
[11]
{LAG03} B. Ludäscher, I. Altintas, and A. Gupta. Compiling Abstract Scientific Workflows into Web Service Workflows. In 15th Intl. Conference on Scientific and Statistical Database Management (SSDBM), Boston, Massachussets, 2003.]]
[12]
{LC01a} C. Li and E. Chang. Answering Queries with Useful Bindings. ACM Transactions on Database Systems (TODS), 26(3), 2001.]]
[13]
{LC01b} C. Li and E. Y. Chang. On Answering Queries in the Presence of Limited Access Patterns. In Intl. Conference on Database Theory (ICDT), 2001.]]
[14]
{LGM03} B. Ludäscher, A. Gupta, and M. E. Martone. Bioinformatics: Managing Scientific Data, chapter A Model-Based Mediator System for Scientific Data Management. Morgan Kaufmann, 2003.]]
[15]
{Li03} C. Li. Computing Complete Answers to Queries in the Presence of Limited Access Patterns. Journal of VLDB, 12:211--227, 2003.]]
[16]
{LP95} E. A. Lee and T. Parks. Dataflow Process Networks. Proceedings of the IEEE, 83(5):773--799, 1995.]]
[17]
{LRO96} A. Y. Levy, A. Rajaraman, and J. J. Ordille. Querying Heterogeneous Information Sources Using Source Descriptions. In Proceedings of the Twenty-second International Conference on Very Large Databases, pp. 251--262, Bombay, India, 1996. VLDB Endowment, Saratoga, Calif.]]
[18]
{Lud03} B. Ludäscher. Kepler: Scientific Workflows Based on Dataflow Process Networks. In e-Science Workflow Services, National e-Science Center, Edinburgh, UK, 2003.]]
[19]
{MLF00} T. D. Millstein, A. Y. Levy, and M. Friedman. Query Containment for Data Integration Systems. In Symposium on Principles of Database Systems, pp. 67--75, 2000.]]
[20]
{NL04} A. Nash and B. Ludäscher. Processing Unions of Conjunctive Queries with Negation under Limited Access Patterns. In Intl. Conference on Extending Database Technology (EDBT), Heraklion, Crete, Greece, 2004.]]
[21]
{RSU95} A. Rajaraman, Y. Sagiv, and J. D. Ullman. Answering Queries Using Templates with Binding Patterns. In ACM Symposium on Principles of Database Systems (PODS), pp. 105--112, 1995.]]
[22]
{SDM01} Scientific Data Management Center (SDM). http://sdm.lbl.gov/sdmcenter/, 2001.]]
[23]
{SEE02} Science Environment for Ecological Knowledge (SEEK). http://seek.ecoinformatics.org/, 2002.]]
[24]
{SY80} Y. Sagiv and M. Yannakakis. Equivalences Among Relational Expressions with the Union and Difference Operators. Journal of the ACM, 27(4):633--655, 1980.]]
[25]
{TKL03} S. Thakkar, C. A. Knoblock, and J. Luis. A View Integration Approach to Dynamic Composition of Web Services. In ICAPS 2003 Workshop on Planning for Web Services, Trento, Italy, June 2003.]]
[26]
{Ull88} J. Ullman. The Complexity of Ordering Subgoals. In ACM Symposium on Principles of Database Systems (PODS), 1988.]]
[27]
{VP00} V. Vassalos and Y. Papakonstantinou. Expressive Capabilities Description Languages and Query Rewriting Algorithms. Journal of Logic Programming, 43(1):75--122, 2000.]]
[28]
{WSD03} Web Services Description Language (WSDL) Version 1.2. http://www.w3.org/TR/wsdl12, June 2003.]]

Cited By

View all

Recommendations

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences
PODS '04: Proceedings of the twenty-third ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems
June 2004
350 pages
ISBN:158113858X
DOI:10.1145/1055558
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]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 14 June 2004

Permissions

Request permissions for this article.

Check for updates

Qualifiers

  • Article

Conference

SIGMOD/PODS04

Acceptance Rates

Overall Acceptance Rate 642 of 2,707 submissions, 24%

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)3
  • Downloads (Last 6 weeks)1
Reflects downloads up to 30 Jan 2025

Other Metrics

Citations

Cited By

View all
  • (2025)Access PatternEncyclopedia of Cryptography, Security and Privacy10.1007/978-3-030-71522-9_670(14-18)Online publication date: 8-Jan-2025
  • (2023)Distributed Consistency Beyond QueriesProceedings of the 42nd ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems10.1145/3584372.3588657(47-58)Online publication date: 18-Jun-2023
  • (2023)Access PatternEncyclopedia of Cryptography, Security and Privacy10.1007/978-3-642-27739-9_670-2(1-5)Online publication date: 4-Oct-2023
  • (2022)Generating Plans from ProofsundefinedOnline publication date: 25-Feb-2022
  • (2020)Bounded Evaluation: Querying Big Data with Bounded ResourcesInternational Journal of Automation and Computing10.1007/s11633-020-1236-117:4(502-526)Online publication date: 1-Aug-2020
  • (2019)Parallel-Correctness and Containment for Conjunctive Queries with Union and NegationACM Transactions on Computational Logic10.1145/332912020:3(1-24)Online publication date: 7-Jun-2019
  • (2019)Towards Scalable Hybrid StoresProceedings of the 2019 International Conference on Management of Data10.1145/3299869.3319895(1660-1677)Online publication date: 25-Jun-2019
  • (2018)Logic-based Perspectives on Query Reformulationover Restricted InterfacesACM SIGMOD Record10.1145/3299887.329988947:2(5-16)Online publication date: 11-Dec-2018
  • (2018)Bounded Query Rewriting Using ViewsACM Transactions on Database Systems10.1145/318367343:1(1-46)Online publication date: 23-Mar-2018
  • (2017)Data driven approximation with bounded resourcesProceedings of the VLDB Endowment10.14778/3099622.309962810:9(973-984)Online publication date: 1-May-2017
  • Show More Cited By

View Options

Login options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Figures

Tables

Media

Share

Share

Share this Publication link

Share on social media