Bienvenu, M, Hansen, P, Lutz, C and Wolter, F
(2016)
First order-rewritability and containment of conjunctive queries in horn description logics.
In: IJCAI, 2016-7-10 - 2016-7-20, New York.
Text
ijcaiforewrite16.pdf - Author Accepted Manuscript Download (579kB) |
Abstract
We study FO-rewritability of conjunctive queries in the presence of ontologies formulated in a description logic between EL and Horn-SHIF, along with related query containment problems. Apart from providing characterizations, we establish complexity results ranging from ExpTime via NExpTime to 2ExpTime, pointing out several interesting effects. In particular, FO-rewriting is more complex for conjunctive queries than for atomic queries when inverse roles are present, but not otherwise.
Item Type: | Conference or Workshop Item (Unspecified) |
---|---|
Uncontrolled Keywords: | cs.AI, cs.AI, cs.DB |
Depositing User: | Symplectic Admin |
Date Deposited: | 30 Nov 2017 08:48 |
Last Modified: | 19 Jan 2023 06:49 |
Related URLs: | |
URI: | https://livrepository.liverpool.ac.uk/id/eprint/3013189 |