Checking the data complexity of ontology-mediated queries: a case study with non-uniform CSPs and Polyanna

DOI10.1007/978-3-030-22102-7_15zbMATH Open1444.68067OpenAlexW2954844176MaRDI QIDQ2185474FDOQ2185474

Stanislav Kikot, Michael Zakharyaschev, Olga Gerasimova

Publication date: 4 June 2020

Full work available at URL: https://doi.org/10.1007/978-3-030-22102-7_15

Recommendations

• The data complexity of description logic ontologies
• The data complexity of ontology-mediated queries with closed predicates
• A complete classification of the complexity and rewritability of ontology-mediated queries based on the description logic \(\mathcal{EL}\)
• Ontology-mediated queries. Combined complexity and succinctness of rewritings via circuit complexity
• Complexity and expressive power of ontology-mediated queries (invited talk)

Mathematics Subject Classification ID

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

Cited In (1)

• A tetrachotomy of ontology-mediated queries with a covering axiom

Uses Software

• Datalog
• Ontop
• MASTRO
• Polyanna

This page was built for publication: Checking the data complexity of ontology-mediated queries: a case study with non-uniform CSPs and Polyanna

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