Containment of acyclic conjunctive queries with negated atoms or arithmetic comparisons
We study the containment problem for conjunctive queries (CQs ) expanded with negated atoms or arithmetic comparisons. It is known that the problem is View the MathML source-complete [14] and [16]. The aim of this article is to find restrictions on CQs that allow for tractable containment. In parti...
| Main Authors: | , |
|---|---|
| Format: | Journal article |
| Published: |
Elsevier
2016
|
| _version_ | 1826291082775756800 |
|---|---|
| author | Sherkhonov, E Marx, M |
| author_facet | Sherkhonov, E Marx, M |
| author_sort | Sherkhonov, E |
| collection | OXFORD |
| description | We study the containment problem for conjunctive queries (CQs ) expanded with negated atoms or arithmetic comparisons. It is known that the problem is View the MathML source-complete [14] and [16]. The aim of this article is to find restrictions on CQs that allow for tractable containment. In particular, we consider acyclic conjunctive queries. Even with the most restrictive form of acyclicity (Berge-acyclicity), containment is coNP-hard. But for a particular fragment of Berge-acyclic CQs with negated atoms or arithmetic comparisons —child-only tree patterns— containment is solvable in PTime. |
| first_indexed | 2024-03-07T02:54:03Z |
| format | Journal article |
| id | oxford-uuid:aeab0f9a-cc3d-468e-9756-15a93bd6048c |
| institution | University of Oxford |
| last_indexed | 2024-03-07T02:54:03Z |
| publishDate | 2016 |
| publisher | Elsevier |
| record_format | dspace |
| spelling | oxford-uuid:aeab0f9a-cc3d-468e-9756-15a93bd6048c2022-03-27T03:44:08ZContainment of acyclic conjunctive queries with negated atoms or arithmetic comparisonsJournal articlehttp://purl.org/coar/resource_type/c_dcae04bcuuid:aeab0f9a-cc3d-468e-9756-15a93bd6048cSymplectic Elements at OxfordElsevier2016Sherkhonov, EMarx, MWe study the containment problem for conjunctive queries (CQs ) expanded with negated atoms or arithmetic comparisons. It is known that the problem is View the MathML source-complete [14] and [16]. The aim of this article is to find restrictions on CQs that allow for tractable containment. In particular, we consider acyclic conjunctive queries. Even with the most restrictive form of acyclicity (Berge-acyclicity), containment is coNP-hard. But for a particular fragment of Berge-acyclic CQs with negated atoms or arithmetic comparisons —child-only tree patterns— containment is solvable in PTime. |
| spellingShingle | Sherkhonov, E Marx, M Containment of acyclic conjunctive queries with negated atoms or arithmetic comparisons |
| title | Containment of acyclic conjunctive queries with negated atoms or arithmetic comparisons |
| title_full | Containment of acyclic conjunctive queries with negated atoms or arithmetic comparisons |
| title_fullStr | Containment of acyclic conjunctive queries with negated atoms or arithmetic comparisons |
| title_full_unstemmed | Containment of acyclic conjunctive queries with negated atoms or arithmetic comparisons |
| title_short | Containment of acyclic conjunctive queries with negated atoms or arithmetic comparisons |
| title_sort | containment of acyclic conjunctive queries with negated atoms or arithmetic comparisons |
| work_keys_str_mv | AT sherkhonove containmentofacyclicconjunctivequerieswithnegatedatomsorarithmeticcomparisons AT marxm containmentofacyclicconjunctivequerieswithnegatedatomsorarithmeticcomparisons |