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

DOI10.1007/978-3-030-22102-7_15MaRDI QIDQ2185474zbMATH OpenOpenAlexFDO

Authors Olga Gerasimova, Stanislav Kikot, Michael Zakharyaschev

Publication date 4 June 2020

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

Mathematics Subject Classification ID

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

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)

Cited in

(1)

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

Describes a project that uses

Uses Software

• Ontop
• Datalog
• Polyanna
• MASTRO

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)