A Dichotomy in the Complexity of Consistent Query Answering for Two Atom Queries With Self-Join
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , |
|---|---|
| Format: | Preprint |
| Publié: |
2023
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866917673827303424 |
|---|---|
| author | Padmanabha, Anantha Segoufin, Luc Sirangelo, Cristina |
| author_facet | Padmanabha, Anantha Segoufin, Luc Sirangelo, Cristina |
| contents | We consider the dichotomy conjecture for consistent query answering under primary key constraints. It states that, for every fixed Boolean conjunctive query q, testing whether q is certain (i.e. whether it evaluates to true over all repairs of a given inconsistent database) is either polynomial time or coNP-complete. This conjecture has been verified for self-join-free and path queries. We show that it also holds for queries with two atoms. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2309_12059 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | A Dichotomy in the Complexity of Consistent Query Answering for Two Atom Queries With Self-Join Padmanabha, Anantha Segoufin, Luc Sirangelo, Cristina Databases We consider the dichotomy conjecture for consistent query answering under primary key constraints. It states that, for every fixed Boolean conjunctive query q, testing whether q is certain (i.e. whether it evaluates to true over all repairs of a given inconsistent database) is either polynomial time or coNP-complete. This conjecture has been verified for self-join-free and path queries. We show that it also holds for queries with two atoms. |
| title | A Dichotomy in the Complexity of Consistent Query Answering for Two Atom Queries With Self-Join |
| topic | Databases |
| url | https://arxiv.org/abs/2309.12059 |