Ontology-Mediated Queries: Combined Complexity and Succinctness of Rewritings via Circuit Complexity - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier Accéder directement au contenu
Article Dans Une Revue Journal of the ACM (JACM) Année : 2018

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

Résumé

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.
Fichier principal
Vignette du fichier
HyperACM-CR.pdf (1.35 Mo) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

lirmm-01892661 , version 1 (10-10-2018)

Identifiants

Citer

Meghyn Bienvenu, Stanislav Kikot, Roman Kontchakov, Vladimir V Podolskii, Michael Zakharyaschev. Ontology-Mediated Queries: Combined Complexity and Succinctness of Rewritings via Circuit Complexity. Journal of the ACM (JACM), 2018, 65 (5), pp.1-51. ⟨10.1145/3191832⟩. ⟨lirmm-01892661⟩
283 Consultations
206 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More