Efficiently ordering subgoals with access constraints

ABSTRACT

In this paper, we study the problem of ordering subgoals under binding pattern restrictions for queries posed as nonrecursive Datalog programs. We prove that despite their limited expressive power, the problem is computationally hard—PSPACE-complete in the size of the nonrecursive Datalog program even for fairly restricted cases. As a practical solution to this problem, we develop an asymptotically optimal algorithm that runs in time linear in the size of the query plan. We also study extensions of our algorithm that efficiently solve other query planning problems under binding pattern restrictions. These problems include conjunctive queries with nested grouping constraints, distributed conjunctive queries, and first-order queries.

REFERENCES

• 1: J. L. Ambite, V. K. Chaudhri, R. Fikes, J. Jenkins, S. Mishra, M. Muslea, T. Uribe, and G. Yang. Integration of heterogeneous knowledge sources in the CALO query manager. In ODBASE, 2005.
• 2: Yigal Arens , Craig A. Knoblock , Wei-Min Shen, Query reformulation for dynamic information integration, Journal of Intelligent Information Systems, v.6 n.2-3, p.99-130, June 1996 [doi>10.1007/BF00122124]
• 3: A. Deutsch, B. Ludäscher, and A. Nash. Rewriting queries using views with access patterns under integrity constraints. In ICDT, 2005.
• 4: O. M. Duschka, M. R. Genesereth, and A. Y. Levy. Recursive query plans for data integration. Journal of Logic Programming (JLP), 43(1):49--73, 2000.
• 5: 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]
• 6: 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
• 7: 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
• 8: Chen Li , Ramana Yerneni , Vasilis Vassalos , Hector Garcia-Molina , Yannis Papakonstantinou , Jeffrey Ullman , Murty Valiveti, Capability based mediation in TSIMMIS, Proceedings of the 1998 ACM SIGMOD international conference on Management of data, p.564-566, June 01-04, 1998, Seattle, Washington, United States
• 9: Katherine A. Morris, An algorithm for ordering subgoals in NAIL?, Proceedings of the seventh ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.82-88, March 1988, Austin, Texas, United States [doi>10.1145/308386.308419]
• 10: 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]
• 11: A. Nash and B. Ludäscher. Processing unions of conjunctive queries with negation under limited access patterns. In EDBT, 2004.
• 12: Christos H. Papadimitriou, NP-Completeness: A Retrospective, Proceedings of the 24th International Colloquium on Automata, Languages and Programming, p.2-6, July 07-11, 1997
• 13: 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]
• 14: Arie Segev, Optimization of join operations in horizontally partitioned database systems, ACM Transactions on Database Systems (TODS), v.11 n.1, p.48-80, March 1986 [doi>10.1145/5236.5241]
• 15: Jeffrey D. Ullman, Principles of Database and Knowledge-Base Systems: Volume II: The New Technologies, W. H. Freeman & Co., New York, NY, 1990
• 16: 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]
• 17: V. Vassalos and Y. Papakonstantinou. Expressive capabilities description languages and query rewriting algorithms. Journal of Logic Programming (JLP), 43(1):75--122, 2000.
• 18: Ramana Yerneni , Chen Li , Hector Garcia-Molina , Jeffrey Ullman, Computing capabilities of mediators, Proceedings of the 1999 ACM SIGMOD international conference on Management of data, p.443-454, May 31-June 03, 1999, Philadelphia, Pennsylvania, United States

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems
          Subjects: Query processing

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems

General Terms:
Algorithms, Theory

Keywords:
binding pattern, executability, nonrecursive datalog, query