Journal article icon

Journal article

Containment of acyclic conjunctive queries with negated atoms or arithmetic comparisons

Abstract:

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 wi...

Expand abstract
Publication status:
Published
Peer review status:
Peer reviewed
Version:
Accepted manuscript

Actions


Access Document


Files:
Publisher copy:
10.1016/j.ipl.2016.12.005

Authors


More by this author
Department:
Oxford, MPLS, Computer Science
Publisher:
Elsevier Publisher's website
Journal:
Information Processing Letters Journal website
Volume:
120
Pages:
30-39
Publication date:
2016-12-23
Acceptance date:
2016-12-16
DOI:
EISSN:
1872-6119
ISSN:
0020-0190
Pubs id:
pubs:668737
URN:
uri:aeab0f9a-cc3d-468e-9756-15a93bd6048c
UUID:
uuid:aeab0f9a-cc3d-468e-9756-15a93bd6048c
Local pid:
pubs:668737

Terms of use


Metrics



If you are the owner of this record, you can report an update to it here: Report update to this record

TO TOP