Wolter, Frank, Hernich, Andre, Papacchini, Fabio 
ORCID: 0000-0002-0310-7378 and Lutz, Carsten
(2020)
Dichotomies in Ontology-Mediated Querying with the
Guarded Fragment.
ACM Transactions on Computational Logic, 21 (3).
pp. 1-47.
|
Text
tocl.pdf - Author Accepted Manuscript Download (1MB) | Preview |
Abstract
We study ontology-mediated querying in the case where ontologies are formulated in the guarded fragment of first-order logic (GF) or extensions thereof with counting and where the actual queries are (unions of) conjunctive queries. Our aim is to classify the data complexity and Datalog rewritability of query evaluation depending on the ontology O, where query evaluation w.r.t. O is in PTime (resp. Datalog rewritable) if all queries can be evaluated in PTime w.r.t. O (resp. rewritten into Datalog under O), and coNP-hard if at least one query is coNP-hard w.r.t. O. We identify several fragments of GF that enjoy a dichotomy between Datalog-rewritability (which implies PTime) and coNP-hardness as well as several other fragments that enjoy a dichotomy between PTime and coNP-hardness, but for which PTime does not imply Datalog-rewritability. For the latter, we establish and exploit a connection to constraint satisfaction problems. We also identify fragments for which there is no dichotomy between PTime and coNP. To prove this, we establish a non-trivial variation of Ladner’s theorem on the existence of NP-intermediate problems. Finally, we study the decidability of whether a given ontology enjoys PTime query evaluation, presenting both positive and negative results, depending on the fragment.
| Item Type: | Article |
|---|---|
| Uncontrolled Keywords: | Ontology-based data access, query evaluation, dichotomies |
| Depositing User: | Symplectic Admin |
| Date Deposited: | 27 Feb 2020 10:57 |
| Last Modified: | 19 Jan 2023 00:02 |
| DOI: | 10.1145/3375628 |
| Related URLs: | |
| URI: | https://livrepository.liverpool.ac.uk/id/eprint/3075245 |
Dimensions
Dimensions
