Processing first-order queries under limited access patterns

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: Serge Abiteboul , Richard Hull , Victor Vianu, Foundations of Databases: The Logical Level, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1995
• 2: {BIR01} Biomedical Informatics Research Network Coordinating Center (BIRN-CC), University of California, San Diego. http://nbirn.net/,2001.
• 3: Ashok K. Chandra , Philip M. Merlin, Optimal implementation of conjunctive queries in relational data bases, Proceedings of the ninth annual ACM symposium on Theory of computing, p.77-90, May 04-04, 1977, Boulder, Colorado, United States [doi>10.1145/800105.803397]
• 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: Daniela Florescu , Alon Levy , Ioana Manolescu , Dan Suciu, Query optimization in the presence of limited access patterns, Proceedings of the 1999 ACM SIGMOD international conference on Management of data, p.311-322, May 31-June 03, 1999, Philadelphia, Pennsylvania, United States
• 8: Amarnath Gupta , Bertram Ludäscher , Maryann E. Martone, BIRN-M: a semantic mediator for solving real-world neuroscience problems, Proceedings of the 2003 ACM SIGMOD international conference on Management of data, June 09-12, 2003, San Diego, California [doi>10.1145/872757.872869]
• 9: Allen Van Gelder , Rodney W. Topor, Safety and translation of relational calculus, ACM Transactions on Database Systems (TODS), v.16 n.2, p.235-278, June 1991 [doi>10.1145/114325.103712]
• 10: Richard Hull , Michael Benedikt , Vassilis Christophides , Jianwen Su, E-services: a look behind the curtain, Proceedings of the twenty-second ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.1-14, June 09-11, 2003, San Diego, California [doi>10.1145/773153.773154]
• 11: Bertram Ludascher , Ilkay Altintas , Amarnath Gupta, Compiling abstract scientific workflows into web service workflows, Proceedings of the 15th international conference on Scientific and statistical database management, p.251-254, July 09-11, 2003, Cambridge, MA [doi>10.1109/SSDM.2003.1214990]
• 12: Chen Li , Edward Chang, Answering queries with useful bindings, ACM Transactions on Database Systems (TODS), v.26 n.3, p.313-343, September 2001 [doi>10.1145/502030.502032]
• 13: Chen Li , Edward Y. Chang, On Answering Queries in the Presence of Limited Access Patterns, Proceedings of the 8th International Conference on Database Theory, p.219-233, January 04-06, 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: Chen Li, Computing complete answers to queries in the presence of limited access patterns, The VLDB Journal — The International Journal on Very Large Data Bases, v.12 n.3, p.211-227, October 2003 [doi>10.1007/s00778-002-0085-6]
• 16: {LP95} E. A. Lee and T. Parks. Dataflow Process Networks. Proceedings of the IEEE, 83(5):773--799, 1995.
• 17: Alon Y. Levy , Anand Rajaraman , Joann J. Ordille, Querying Heterogeneous Information Sources Using Source Descriptions, Proceedings of the 22th International Conference on Very Large Data Bases, p.251-262, September 03-06, 1996
• 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: Todd Millstein , Alon Levy , Marc Friedman, Query containment for data integration systems, Proceedings of the nineteenth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.67-75, May 15-18, 2000, Dallas, Texas, United States [doi>10.1145/335168.335208]
• 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: Anand Rajaraman , Yehoshua Sagiv , Jeffrey D. Ullman, Answering queries using templates with binding patterns (extended abstract), Proceedings of the fourteenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.105-112, May 22-25, 1995, San Jose, California, United States [doi>10.1145/212433.220199]
• 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: Yehoshua Sagiv , Mihalis Yannakakis, Equivalences Among Relational Expressions with the Union and Difference Operators, Journal of the ACM (JACM), v.27 n.4, p.633-655, Oct. 1980 [doi>10.1145/322217.322221]
• 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: Jeffrey D. Ullman , Moshe Y. Vardi, The complexity of ordering subgoals, Proceedings of the seventh ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.74-81, March 1988, Austin, Texas, United States [doi>10.1145/308386.308417]
• 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.