Horn-Rewritability vs PTime Query Evaluation in Ontology-Mediated Querying

Hernich, Andre, Lutz, Carsten, Papacchini, Fabio ORCID: 0000-0002-0310-7378 and Wolter, Frank ORCID: 0000-0002-4470-606X (2018) Horn-Rewritability vs PTime Query Evaluation in Ontology-Mediated Querying. In: Twenty-Seventh International Joint Conference on Artificial Intelligence {IJCAI-18}, 2018-7-13 - 2018-7-19.

Access the full-text of this item by clicking on the Open Access link.

Text 0257.pdf - Author Accepted Manuscript Download (149kB)

Abstract

<jats:p>In ontology-mediated querying with an expressive description logic L, two desirable properties of a TBox T are (1) being able to replace T with a TBox formulated in the Horn-fragment of L without affecting the answers to conjunctive queries, and (2) that every conjunctive query can be evaluated in PTime w.r.t. T. We investigate in which cases (1) and (2) are equivalent, finding that the answer depends on whether the unique name assumption (UNA) is made, on the description logic under consideration, and on the nesting depth of quantifiers in the TBox. We also clarify the relationship between query evaluation with and without UNA and consider natural variations of property (1).</jats:p>

Item Type:	Conference or Workshop Item (Unspecified)
Uncontrolled Keywords:	5003 Philosophy, 46 Information and Computing Sciences, 50 Philosophy and Religious Studies
Depositing User:	Symplectic Admin
Date Deposited:	16 Aug 2018 08:18
Last Modified:	07 Dec 2024 10:51
DOI:	10.24963/ijcai.2018/257
Open Access URL:	https://www.ijcai.org/proceedings/2018/0257.pdf
Related URLs:	Author Publisher
URI:	https://livrepository.liverpool.ac.uk/id/eprint/3024614