On Containment of Conjunctive Queries with Arithmetic Comparisons (Extended Version)
Foto Afrati, Prasenjit Mitra · 2003
In this paper we study the following problem: how to test whether # # is contained in # # ,where# # and # # are conjunctive queries with arithmetic comparisons? This problem is fundamental in a large variety of database applications. Existing algorithms first normalize the queries, then test a logical implication using multiple containment mappings from # # to # # . We are interested in cases where the containment can be tested more efficiently. This work is mainly motivated by (1) reducing the problem complexity # -completeness to NP-completeness in these cases; and (2) utilizing the advantages of the homomorphism property (i.e., the containment test is based on a single containment mapping), in applications such as those of answering queries using views. The following are our results. (1) We show several cases where the normalization step is not needed, thus reducing the size of the queries and, more importantly, reducing the number of containment mappings. (2) We find large classes of queries where the homomorphism property holds. (3) We further reduce the conditions of these classes using practical domain knowledge that is easily obtainable. (4) We conducted experiments on real queries, and show that most of the queries have this homomorphism property.