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 with negated atoms or arithmetic comparisons —child-only tree patterns— containment is solvable in PTime.

Publication status:: Published

Peer review status:: Peer reviewed

Actions

Email

Email this record

Send the bibliographic details of this record to your email address.

Your Email
Please enter the email address that the record information will be sent to.

-
Your message (optional)
Please add any additional information to be included within the email.
Cite

Cite this record

APA Style

Sherkhonov, E., & Marx, M. (2016). Containment of acyclic conjunctive queries with negated atoms or arithmetic comparisons. Information Processing Letters, 120, 30–39.

MLA Style

Sherkhonov, E., and M. Marx. “Containment of Acyclic Conjunctive Queries with Negated Atoms or Arithmetic Comparisons.” Information Processing Letters, vol. 120, Elsevier, 2016, pp. 30–39.

Chicago Style

Sherkhonov, E, and M Marx. 2016. “Containment of Acyclic Conjunctive Queries with Negated Atoms or Arithmetic Comparisons.” Information Processing Letters 120: 30–39.
Share
Print

Access Document

Files:: main.pdf

(Preview, Accepted manuscript, pdf, 372.6KB, Terms of use)

Publisher copy:: 10.1016/j.ipl.2016.12.005

Authors

+ Sherkhonov, E More by this author

Institution:: University of Oxford
Division:: MPLS
Department:: Computer Science
Role:: Author

+ Marx, M More by this author

Role:: Author

+ Engineering and Physical Sciences Research Council More from this funder

Grant:: Impact Acceleration Award

+ Netherlands Organisation for Scientific Research More from this funder

Grant:: 612.001.012 (DEX

Publisher:: Elsevier
Journal:: Information Processing Letters More from this journal
Volume:: 120
Pages:: 30-39
Publication date:: 2016-12-23
Acceptance date:: 2016-12-16
DOI:: 10.1016/j.ipl.2016.12.005
EISSN:: 1872-6119
ISSN:: 0020-0190

Keywords:: conjunctive query

query containment

databases
Pubs id:: pubs:668737
UUID:: uuid:aeab0f9a-cc3d-468e-9756-15a93bd6048c
Local pid:: pubs:668737
Source identifiers:: 668737
Deposit date:: 2017-01-10

Terms of use

Copyright holder:: Elsevier
Copyright date:: 2016
Notes:: © 2016 Elsevier B.V. All rights reserved. This is the accepted manuscript version of the article. The final version is available online from Elsevier at: 10.1016/j.ipl.2016.12.005

Licence:: CC Attribution-NonCommercial-NoDerivatives (CC BY-NC-ND)

Views and Downloads

About views and downloads

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

TO TOP