TY - GEN

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

AU - Hernich, André

AU - Papacchini, Fabio

AU - Lutz, Carsten

AU - Wolter, Frank

PY - 2018/7/13

Y1 - 2018/7/13

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

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

U2 - 10.24963/ijcai.2018/257

DO - 10.24963/ijcai.2018/257

M3 - Conference contribution/Paper

SP - 1861

EP - 1867

BT - Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence, IJCAI 2018, July 13-19, 2018, Stockholm, Sweden

PB - IJCAI

ER -