Semi-interval Comparison Constraints in Query Containment and Their Impact on Certain Answer Computation
For database query optimization and view-based query answering, the paper provides complexity bounds and tractable cases for CQAC containment and certain answer computation.
The paper studies containment of conjunctive queries with arithmetic comparisons (CQAC), identifying broad classes with semi-interval comparisons where containment is in NP, while some cases remain Π₂ᵖ-complete. It also shows that certain answers can be computed in polynomial time via maximally contained rewritings for these classes.
We consider conjunctive queries with arithmetic comparisons (CQAC) and investigate the computational complexity of the problem: Given two CQAC queries, $Q$ and $Q'$, is $Q'$ contained in $Q$? We know that, for CQAC queries, the problem of testing containment is $Π_2 ^p$ -complete. However, there are broad classes of queries with semi-interval arithmetic comparisons in the containing query that render the problem solvable in NP. In all cases examined the contained query is allowed to be any CQAC. Interestingly, we also prove that there are simple cases where the problem remains $Π_2 ^p$ -complete. We also investigate the complexity of computing certain answers in the framework of answering CQAC queries with semi-interval comparisons using any CQAC views. We prove that maximally contained rewritings in the language of union of CQACs always compute exactly all certain answers. We find cases where we can compute certain answers in polynomial time using maximally contained rewritings.