On the succinctness of query rewriting over shallow ontologies

DOI10.1145/2603088.2603131MaRDI QIDQ4635642zbMATH OpenOpenAlexWikidataFDO

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

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)

Full work available at URL https://arxiv.org/abs/1401.4420, https://eprints.bbk.ac.uk/id/eprint/10350/1/Hyper-LICS-final.pdf

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)

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.

Recommendations

• The price of query rewriting in ontology-based data access
• Tree-like queries in OWL 2 QL: succinctness and complexity results
• Ontology-mediated queries. Combined complexity and succinctness of rewritings via circuit complexity
• Exponential lower bounds and separation for query rewriting
• Rewriting Conjunctive Queries over Description Logic Knowledge Bases

Cited in

(13)

• Optimized query rewriting for OWL 2 QL
• The price of query rewriting in ontology-based data access
• Circuit complexity meets ontology-based data access
• Metamodeling and metaquerying in \texttt{OWL 2 QL}
• Ontology-Mediated Query Answering with Data-Tractable Description Logics
• Rewritability in monadic disjunctive Datalog, MMSNP, and expressive description logics
• Ontology-mediated queries. Combined complexity and succinctness of rewritings via circuit complexity
• \(\mathcal{EL}\)-ifying ontologies
• Logical foundations of information disclosure in ontology-based data integration
• Exponential lower bounds and separation for query rewriting
• Tree-like queries in OWL 2 QL: succinctness and complexity results
• 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)