On containment of conjunctive queries with arithmetic comparisons

Foto Afrati, Chen Li, Prasenjit Mitra

Research output: Contribution to journalArticlepeer-review

12 Scopus citations


We study the following problem: how to test if Q2 is contained in Q1, where Q1 and Q2 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 Q 1 to Q2. We are interested in cases where the containment can be tested more efficiently. This work aims to (a) reduce the problem complexity from IIP2-completeness to NP-completeness in these cases; (b) utilize 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; and (c) observing that many real queries have the homomorphism property. 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 the number of containment mappings. (2) We develop an algorithm for checking various syntactic conditions on queries, under which 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 pass this test.

Original languageEnglish (US)
Pages (from-to)459-476
Number of pages18
JournalLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
StatePublished - Dec 1 2004

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computer Science(all)


Dive into the research topics of 'On containment of conjunctive queries with arithmetic comparisons'. Together they form a unique fingerprint.

Cite this