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

Meghyn Bienvenu 1, * Peter Hansen 2 Carsten Lutz 2 Frank Wolter 3
* Auteur correspondant
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.
Type de document :
Communication dans un congrès
IJCAI: International Joint Conference on Artificial Intelligence, Jul 2016, New York, United States. 25th International Joint Conference on Artificial Intelligence, 2016, 〈http://ijcai-16.org/〉
Liste complète des métadonnées

Littérature citée [10 références]  Voir  Masquer  Télécharger

https://hal-lirmm.ccsd.cnrs.fr/lirmm-01367863
Contributeur : Meghyn Bienvenu <>
Soumis le : vendredi 16 septembre 2016 - 19:49:58
Dernière modification le : jeudi 24 mai 2018 - 15:59:22
Document(s) archivé(s) le : samedi 17 décembre 2016 - 14:27:01

Fichier

BieHanLutWol-IJCAI16.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • 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. 25th International Joint Conference on Artificial Intelligence, 2016, 〈http://ijcai-16.org/〉. 〈lirmm-01367863〉

Partager

Métriques

Consultations de la notice

109

Téléchargements de fichiers

213