English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

Our concern is the problem of efficiently determining the data complexity ofanswering queries mediated by description logic ontologies and constructingtheir optimal rewritings to standard database queries. Originated inontology-based data access and datalog optimisation, this problem is known tobe computationally very complex in general, with no explicit syntacticcharacterisations available. In this article, aiming to understand thefundamental roots of this difficulty, we strip the problem to the bare bonesand focus on Boolean conjunctive queries mediated by a simple covering axiomstating that one class is covered by the union of two other classes. We showthat, on the one hand, these rudimentary ontology-mediated queries, calleddisjunctive sirups (or d-sirups), capture many features and difficulties of thegeneral case. For example, answering d-sirups is Pi^p_2-complete for combinedcomplexity and can be in AC0 or LogSpace-, NL-, P-, or coNP-complete for datacomplexity (with the problem of recognising FO-rewritability of d-sirups being2ExpTime-hard); some d-sirups only have exponential-size resolution proofs,some only double-exponential-size positive existential FO-rewritings andsingle-exponential-size nonrecursive datalog rewritings. On the other hand, weprove a few partial sufficient and necessary conditions of FO- and(symmetric/linear-) datalog rewritability of d-sirups. Our main technicalresult is a complete and transparent syntactic AC0/NL/P/coNP tetrachotomy ofd-sirups with disjoint covering classes and a path-shaped Boolean conjunctivequery. To obtain this tetrachotomy, we develop new techniques for establishingP- and coNP-hardness of answering non-Horn ontology-mediated queries as well asshowing that they can be answered in NL.

A tetrachotomy of ontology-mediated queries with a covering axiom