On the succinctness of query rewriting over shallow ontologies

DOI10.1145/2603088.2603131zbMATH Open1401.68316arXiv1401.4420OpenAlexW1982479815WikidataQ62048610 ScholiaQ62048610MaRDI QIDQ4635642FDOQ4635642

Roman Kontchakov, Stanislav Kikot, Michael Zakharyaschev, Vladimir V. Podolskii

Publication date: 23 April 2018

Published in: Proceedings of the Joint Meeting of the Twenty-Third EACSL Annual Conference on Computer Science Logic (CSL) and the Twenty-Ninth Annual ACM/IEEE Symposium on Logic in Computer Science (LICS) (Search for Journal in Brave)

Abstract: We investigate the size of first-order rewritings of conjunctive queries over OWL 2 QL ontologies of depth 1 and 2 by means of hypergraph programs computing Boolean functions. Both positive and negative results are obtained. Conjunctive queries over ontologies of depth 1 have polynomial-size nonrecursive datalog rewritings; tree-shaped queries have polynomial positive existential rewritings; however, in the worst case, positive existential rewritings can only be of superpolynomial size. Positive existential and nonrecursive datalog rewritings of queries over ontologies of depth 2 suffer an exponential blowup in the worst case, while first-order rewritings are superpolynomial unless $extNPsubseteqextP/extpoly$. We also analyse rewritings of tree-shaped queries over arbitrary ontologies and observe that the query entailment problem for such queries is fixed-parameter tractable.

Full work available at URL: https://arxiv.org/abs/1401.4420

zbMATH Keywords

description logicsuccinctnessBoolean circuit complexityontology-based data accessfirst-order query rewriting

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Data structures (68P05) Knowledge representation (68T30) Database theory (68P15) Logic in artificial intelligence (68T27)

Cited In (6)

• The price of query rewriting in ontology-based data access
• Ontology-Mediated Query Answering with Data-Tractable Description Logics
• Circuit Complexity Meets Ontology-Based Data Access
• Logical foundations of information disclosure in ontology-based data integration
• Query Rewriting and Optimization for Ontological Databases
• Exact query reformulation over databases with first-order and description logics ontologies

This page was built for publication: On the succinctness of query rewriting over shallow ontologies

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4635642)