- Containment of acyclic conjunctive queries with negated atoms or arithmetic comparisons
- Information Processing Letters
- Pages (from-to)
- Document type
- Faculty of Science (FNWI)
- Informatics Institute (IVI)
We study the containment problem for conjunctive queries (CQs) expanded with negated atoms or arithmetic comparisons. It is known that the problem is Π2P-complete. 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.
- go to publisher's site
If you believe that digital publication of certain material infringes any of your rights or (privacy) interests, please let the Library know, stating your reasons. In case of a legitimate complaint, the Library will make the material inaccessible and/or remove it from the website. Please Ask the Library, or send a letter to: Library of the University of Amsterdam, Secretariat, Singel 425, 1012 WP Amsterdam, The Netherlands. You will be contacted as soon as possible.