The homomorphism property in query containment and data integration

We often add arithmetic to extend the expressiveness of query languages, tuple generating dependencies and data exchange mappings, and study the complexity of problems such as testing query containment and finding certain answers. When adding arithmetic comparisons, the complexity of such problems is higher than the complexity of their counterparts without them. It has been observed that we can achieve lower complexity if we restrict some of the comparisons to be closed or open semi-interval comparisons. Here, focusing on the problem of containment for conjunctive queries with arithmetic comparisons (CQAC queries, for short), we prove upper bounds on the computational complexity. Our main methodology uses a general property of CQACs and tuple generating dependencies with arithmetic comparisons which is called the homomorphism property. When the homomorphism property holds, then the complexity of the above problems can be improved. We syntactically characterize subclasses of CQACs queries that have the homomorphism property, and we give a detailed proof that contains components that can be used to prove more results of the same kind. Similar methodology can be applied to achieve better upper bounds on the complexity of testing query containment under dependencies, finding query rewritings, and finding certain answers in data exchange. This is done by improving the complexity of the chase algorithm for tuple generating dependencies with arithmetic comparisons.