Querying data sources that export infinite sets of views

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: Serge Abiteboul , Richard Hull , Victor Vianu, Foundations of Databases: The Logical Level, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 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: Foto Afrati , Chen Li , Prasenjit Mitra, Answering queries using views with arithmetic comparisons, Proceedings of the twenty-first ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 03-05, 2002, Madison, Wisconsin [doi>10.1145/543613.543641]
• 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: Sara Cohen , Werner Nutt , Yehoshua Sagiv, Rewriting queries with arbitrary aggregation functions using views, ACM Transactions on Database Systems (TODS), v.31 n.2, p.672-715, June 2006 [doi>10.1145/1138394.1138400]
• 6: Stavros Cosmadakis , Haim Gaifman , Paris Kanellakis , Moshe Vardi, Decidable optimization problems for database logic programs, Proceedings of the twentieth annual ACM symposium on Theory of computing, p.477-490, May 02-04, 1988, Chicago, Illinois, United States [doi>10.1145/62212.62259]
• 7: A. Deutsch, B. Ludaescher, and A. Nash. Rewriting queries using views with access patterns under integrity constraints. In ICDT, 2005.
• 8: Alin Deutsch , Lucian Popa , Val Tannen, Query reformulation with constraints, ACM SIGMOD Record, v.35 n.1, March 2006 [doi>10.1145/1121995.1122010]
• 9: Alin Deutsch , Val Tannen, Reformulation of XML Queries and Constraints, Proceedings of the 9th International Conference on Database Theory, p.225-241, January 08-10, 2003
• 10: Ronald Fagin , Phokion G. Kolaitis , Renée J. Miller , Lucian Popa, Data Exchange: Semantics and Query Answering, Proceedings of the 9th International Conference on Database Theory, p.207-224, January 08-10, 2003
• 11: 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
• 12: Haim Gaifman , Harry Mairson , Yehoshua Sagiv , Moshe Y. Vardi, Undecidable optimization problems for database logic programs, Journal of the ACM (JACM), v.40 n.3, p.683-713, July 1993 [doi>10.1145/174130.174142]
• 13: Alon Y. Levy , Alberto O. Mendelzon , Yehoshua Sagiv, Answering queries using views (extended abstract), Proceedings of the fourteenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.95-104, May 22-25, 1995, San Jose, California, United States [doi>10.1145/212433.220198]
• 14: Alon Y. Levy , Anand Rajaraman , Jeffrey D. Ullman, Answering queries using limited external query processors (extended abstract), Proceedings of the fifteenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.227-237, June 04-06, 1996, Montreal, Quebec, Canada [doi>10.1145/237661.237716]
• 15: Alon Y. Levy , Anand Rajaraman , Jeffrey D. Ullman, Answering queries using limited external query processors, Journal of Computer and System Sciences, v.58 n.1, p.69-82, Feb. 1999 [doi>10.1006/jcss.1998.1599]
• 16: Query Planning with Limited Source Capabilities, Proceedings of the 16th International Conference on Data Engineering, p.401, February 28-March 03, 2000
• 17: David Maier , Alberto Mendelzon , Yehoshua Sagiv, Testing implications of data dependencies, Proceedings of the 1979 ACM SIGMOD international conference on Management of data, May 30-June 01, 1979, Boston, Massachusetts [doi>10.1145/582095.582119]
• 18: Amihai Motro, An Access Authorization Model for Relational Databases Based on Algebraic Manipulation of View Definitions, Proceedings of the Fifth International Conference on Data Engineering, p.339-347, February 06-10, 1989
• 19: Alan Nash , Bertram Ludäscher, Processing first-order queries under limited access patterns, Proceedings of the twenty-third ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 14-16, 2004, Paris, France [doi>10.1145/1055558.1055601]
• 20: Yannis Papakonstantinou , Ashish Gupta , Hector Garcia-Molina , Jeffrey D. Ullman, A Query Translation Scheme for Rapid Implementation of Wrappers, Proceedings of the Fourth International Conference on Deductive and Object-Oriented Databases, p.161-186, December 04-07, 1995
• 21: Shariq Rizvi , Alberto Mendelzon , S. Sudarshan , Prasan Roy, Extending query rewriting techniques for fine-grained access control, Proceedings of the 2004 ACM SIGMOD international conference on Management of data, June 13-18, 2004, Paris, France [doi>10.1145/1007568.1007631]
• 22: Vasilis Vassalos , Yannis Papakonstantinou, Describing and Using Query Capabilities of Heterogeneous Sources, Proceedings of the 23rd International Conference on Very Large Data Bases, p.256-265, August 25-29, 1997
• 23: V. Vassalos and Y. Papakonstantinou. Expressive capabilities description languages and query rewriting algorithms. J. Log. Program., 43(1):75--122, 2000.