First Order-Rewritability and Containment of Conjunctive Queries in Horn Description Logics

Meghyn Bienvenu 1, * Peter Hansen 2 Carsten Lutz 2 Frank Wolter 3
* Corresponding author
1 GRAPHIK - Graphs for Inferences on Knowledge
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier, CRISAM - Inria Sophia Antipolis - Méditerranée
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.
Document type :
Conference papers
Liste complète des métadonnées

Cited literature [10 references]  Display  Hide  Download

https://hal-lirmm.ccsd.cnrs.fr/lirmm-01367863
Contributor : Meghyn Bienvenu <>
Submitted on : Friday, September 16, 2016 - 7:49:58 PM
Last modification on : Thursday, May 24, 2018 - 3:59:22 PM
Document(s) archivé(s) le : Saturday, December 17, 2016 - 2:27:01 PM

File

BieHanLutWol-IJCAI16.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : lirmm-01367863, version 1

Collections

Citation

Meghyn Bienvenu, Peter Hansen, Carsten Lutz, Frank Wolter. First Order-Rewritability and Containment of Conjunctive Queries in Horn Description Logics. IJCAI: International Joint Conference on Artificial Intelligence, Jul 2016, New York, United States. ⟨lirmm-01367863⟩

Share

Metrics

Record views

181

Files downloads

445