Containment of acyclic conjunctive queries with negated atoms or arithmetic comparisons

作者：Sherkhonov Evgeny^*; Marx Maarten

来源：Information Processing Letters, 2017, 120: 30-39.

DOI：10.1016/j.ipl.2016.12.005

• Databases
• Query containment
• Conjunctive query

We study the containment problem for conjunctive queries (CQs) expanded with negated atoms or arithmetic comparisons. It is known that the problem is pi(p)(2)-complete [14,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.

• 出版日期2017-4