Containment in Monadic Disjunctive Datalog, MMSNP, and Expressive Description Logics
2020
Online
report
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.
Titel: |
Containment in Monadic Disjunctive Datalog, MMSNP, and Expressive Description Logics
|
---|---|
Autor/in / Beteiligte Person: | Bourhis, Pierre ; Lutz, Carsten |
Link: | |
Veröffentlichung: | 2020 |
Medientyp: | report |
Schlagwort: |
|
Sonstiges: |
|