Containment in Monadic Disjunctive Datalog, MMSNP, and Expressive Description Logics
This work provides a precise complexity classification for query containment in logical formalisms, which is incremental as it extends known decidability results to exact complexity bounds.
The paper tackled the problem of query containment in three formalisms—monadic disjunctive Datalog, MMSNP, and expressive description logics—by proving that it is 2NEXPTIME-complete, resolving the open complexity question for MMSNP.
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.