TY - JOUR

T1 - Dichotomies in Ontology-Mediated Querying with the Guarded Fragment

AU - Hernich, André

AU - Lutz, Carsten

AU - Papacchini, Fabio

AU - Wolter, Frank

PY - 2020/5/31

Y1 - 2020/5/31

N2 - 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.

AB - 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.

U2 - 10.1145/3375628

DO - 10.1145/3375628

M3 - Journal article

VL - 21

JO - ACM Transactions on Computational Logic (TOCL)

JF - ACM Transactions on Computational Logic (TOCL)

SN - 1529-3785

IS - 3

M1 - 20

ER -