Ontology-Mediated Queries: Combined Complexity and Succinctness of Rewritings via Circuit Complexity

Meghyn Bienvenu 1 Stanislav Kikot 2 Roman Kontchakov 2 Vladimir Podolskii 3 Michael Zakharyaschev 2
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 give solutions to two fundamental computational problems in ontology-based data access with the W3C standard ontology language OWL 2 QL: the succinctness problem for first-order rewritings of ontology-mediated queries (OMQs), and the complexity problem for OMQ answering. We classify OMQs according to the shape of their conjunctive queries (treewidth, the number of leaves) and the existential depth of their ontologies. For each of these classes, we determine the combined complexity of OMQ answering, and whether all OMQs in the class have polynomial-size first-order, positive existential and nonrecursive datalog rewritings. We obtain the succinctness results using hypergraph programs, a new computational model for Boolean functions, which makes it possible to connect the size of OMQ rewritings and circuit complexity.
Type de document :
Article dans une revue
Journal of the ACM (JACM), Association for Computing Machinery, 2018, 65 (5), pp.1-51. 〈10.1145/3191832〉
Liste complète des métadonnées

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

https://hal-lirmm.ccsd.cnrs.fr/lirmm-01892661
Contributeur : Meghyn Bienvenu <>
Soumis le : mercredi 10 octobre 2018 - 17:42:56
Dernière modification le : jeudi 11 octobre 2018 - 01:19:40

Fichier

HyperACM-CR.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

Citation

Meghyn Bienvenu, Stanislav Kikot, Roman Kontchakov, Vladimir Podolskii, Michael Zakharyaschev. Ontology-Mediated Queries: Combined Complexity and Succinctness of Rewritings via Circuit Complexity. Journal of the ACM (JACM), Association for Computing Machinery, 2018, 65 (5), pp.1-51. 〈10.1145/3191832〉. 〈lirmm-01892661〉

Partager

Métriques

Consultations de la notice

128

Téléchargements de fichiers

29