Abstract
We study query containment in three closely related formalisms: monadic disjunctive Datalog (MDDLog), MMSNP (a logical generalization of constraint satisfaction problems), and ontology-mediated queries (OMQs) based on expressive description logics and unions of conjunctive queries. Containment in MMSNP was known to be decidable due to a result by Feder and Vardi, but its exact complexity has remained open. We prove 2NExpTime-completeness and extend this result to monadic disjunctive Datalog and to OMQs.
| Original language | English |
|---|---|
| Pages (from-to) | 207-216 |
| Number of pages | 10 |
| Journal | Proceedings of the International Conference on Knowledge Representation and Reasoning |
| Publication status | Published - 1 Jan 2016 |
| Externally published | Yes |
| Event | 15th International Conference on Principles of Knowledge Representation and Reasoning, KR 2016 - Cape Town, South Africa Duration: 25 Apr 2016 → 29 Apr 2016 |