Semi-interval Comparison Constraints in Query Containment and Their Impact on Certain Answer Computation
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866911714845392896 |
|---|---|
| author | Afrati, Foto N. Damigos, Matthew |
| author_facet | Afrati, Foto N. Damigos, Matthew |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2509_10138 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Semi-interval Comparison Constraints in Query Containment and Their Impact on Certain Answer Computation Afrati, Foto N. Damigos, Matthew Databases H.2.3, F.2.0 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. |
| title | Semi-interval Comparison Constraints in Query Containment and Their Impact on Certain Answer Computation |
| topic | Databases H.2.3, F.2.0 |
| url | https://arxiv.org/abs/2509.10138 |