A unified apriori-like algorithm for conjunctive query containment

ABSTRACT

The design of containment checking algorithms for conjunctive queries with arithmetic comparisons and safe negations (CQ^­s) is fundamental to many database applications. However, it is a challenging task due to the intractability of the problem. Existing algorithms are either computationally too expensive, or capable to deal with only a fragment of these extensions.

In this paper we propose a novel algorithm for testing containment of CQ^­s. The key idea of the algorithm is to recursively consider only the containment mappings between the positive subgoals of the queries, instead of testing all the symbol mappings. Thus the number of test cases can be drastically reduced. Our algorithm enables further an on the fly execution of the normalization step.

With the observation that the property of anti-monotonicity holds in our problem setting, we develop an Apriori-like algorithm as a sub-function of the containment checking algorithm, to which desirable pruning strategies are applied.

Furthermore, we identify the criteria to reduce the number of test sets, and demonstrate that two additional improvements to the containment checking algorithm: node clustering and tuple pruning can further speed up the checking process.

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, C. Li, and P. Mitra. On containment of conjunctive queries with arithmetic comparisons. In EDBT, pages 459--476, 2004.
• 3: Rakesh Agrawal , Ramakrishnan Srikant, Fast Algorithms for Mining Association Rules in Large Databases, Proceedings of the 20th International Conference on Very Large Data Bases, p.487-499, September 12-15, 1994
• 4: Sergey Brin , Rajeev Motwani , Jeffrey D. Ullman , Shalom Tsur, Dynamic itemset counting and implication rules for market basket data, Proceedings of the 1997 ACM SIGMOD international conference on Management of data, p.255-264, May 11-15, 1997, Tucson, Arizona, United States
• 5: 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]
• 6: Ronald Fagin , Phokion G. Kolaitis , Renée J. Miller , Lucian Popa, Data exchange: semantics and query answering, Theoretical Computer Science, v.336 n.1, p.89-124, 25 May 2005 [doi>10.1O16/j.tcs.2004.10.033]
• 7: G. Gottlob, N. Leone, and F. Scarcello. Hypertree decompositions and tractable queries. J. Comput. Syst. Sci., 64(3):579--627, 2002.
• 8: Ashish Gupta , Yehoshua Sagiv , Jeffrey D. Ullman , Jennifer Widom, Constraint checking with partial information, Proceedings of the thirteenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.45-55, May 24-27, 1994, Minneapolis, Minnesota, United States [doi>10.1145/182591.182597]
• 9: Alon Y. Halevy, Answering queries using views: A survey, The VLDB Journal — The International Journal on Very Large Data Bases, v.10 n.4, p.270-294, December 2001 [doi>10.1007/s007780100054]
• 10: Anthony Klug, On conjunctive queries containing inequalities, Journal of the ACM (JACM), v.35 n.1, p.146-160, Jan. 1988 [doi>10.1145/42267.42273]
• 11: Phokion G. Kolaitis , Moshe Y. Vardi, Conjunctive-query containment and constraint satisfaction, Proceedings of the seventeenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.205-213, June 01-04, 1998, Seattle, Washington, United States [doi>10.1145/275487.275511]
• 12: M. Leclère and M.-L. Mugnier. Some algorithmic improvements for the containment problem of conjunctive queries with negation. In ICDT, pages 404--418, 2007.
• 13: Alon Y. Levy , Yehoshua Sagiv, Queries Independent of Updates, Proceedings of the 19th International Conference on Very Large Data Bases, p.171-181, August 24-27, 1993
• 14: M. Ortiz, D. Calvanese, and T. Eiter. Characterizing data complexity for conjunctive query answering in expressive description logics. In AAAI, 2006.
• 15: Jong Soo Park , Ming-Syan Chen , Philip S. Yu, An effective hash-based algorithm for mining association rules, Proceedings of the 1995 ACM SIGMOD international conference on Management of data, p.175-186, May 22-25, 1995, San Jose, California, United States
• 16: Yatin P. Saraiya, Subtree-elimination algorithms in deductive databases, Stanford University, Stanford, CA, 1991
• 17: Ashoka Savasere , Edward Omiecinski , Shamkant B. Navathe, An Efficient Algorithm for Mining Association Rules in Large Databases, Proceedings of the 21th International Conference on Very Large Data Bases, p.432-444, September 11-15, 1995
• 18: Jeffrey D. Ullman, Information Integration Using Logical Views, Proceedings of the 6th International Conference on Database Theory, p.19-40, January 08-10, 1997
• 19: R. van der Meyden, The complexity of querying indefinite data about linearly ordered domains, Proceedings of the eleventh ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.331-345, June 02-05, 1992, San Diego, California, United States [doi>10.1145/137097.137902]
• 20: Fang Wei , Georg Lausen, Containment of Conjunctive Queries with Safe Negation, Proceedings of the 9th International Conference on Database Theory, p.346-360, January 08-10, 2003
• 21: Mihalis Yannakakis, Algorithms for acyclic database schemes, Proceedings of the seventh international conference on Very Large Data Bases, p.82-94, September 09-11, 1981, Cannes, France
• 22: Xubo Zhang , Z. Meral Ozsoyoglu, Implication and Referential Constraints: A New Formal Reasoning, IEEE Transactions on Knowledge and Data Engineering, v.9 n.6, p.894-910, November 1997 [doi>10.1109/69.649315]

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
          Subjects: Sorting and searching

General Terms:
Algorithms, Design, Performance