Hernich, Andre, Lutz, Carsten, Papacchini, Fabio ORCID: 0000-0002-0310-7378 and Wolter, Frank
(2017)
Dichotomies in Ontology-Mediated Querying with the Guarded Fragment.
In: SIGMOD/PODS'17: International Conference on Management of Data, 2017-5-14 - 2017-5-19, Chicago, IL, USA.
![]() |
Text
PODS17.pdf - Author Accepted Manuscript Download (364kB) |
![]() |
Text (admin)
2017-05-12T15:44:47Z.atom - Unspecified Access to this file is embargoed until Unspecified. Download (11kB) |
Abstract
We study the complexity of ontology-mediated querying when ontologies are formulated in the guarded fragment of first-order logic (GF). Our general aim is to classify the data complexity on the level of ontologies where query evaluation w.r.t. an ontology O is considered to be in PTime if all (unions of conjunctive) queries can be evaluated in PTime w.r.t. O and coNP-hard if at least one query is coNP-hard w.r.t. O. We identify several large and relevant fragments of GF that enjoy a dichotomy between PTime and coNP, some of them additionally admitting a form of counting. In fact, almost all ontologies in the BioPortal repository fall into these fragments or can easily be rewritten to do so. We then establish a variation of Ladner's Theorem on the existence of NP-intermediate problems and use this result to show that for other fragments, there is provably no such dichotomy. Again for other fragments (such as full GF), establishing a dichotomy implies the Feder-Vardi conjecture on the complexity of constraint satisfaction problems. We also link these results to Datalog-rewritability and study the decidability of whether a given ontology enjoys PTime query evaluation, presenting both positive and negative results.
Item Type: | Conference or Workshop Item (Unspecified) |
---|---|
Uncontrolled Keywords: | Ontology-Based Data Access, Query Answering, Dichotomies |
Depositing User: | Symplectic Admin |
Date Deposited: | 09 Mar 2017 08:03 |
Last Modified: | 19 Jan 2023 07:14 |
DOI: | 10.1145/3034786.3056108 |
Related URLs: | |
URI: | https://livrepository.liverpool.ac.uk/id/eprint/3006270 |