A complete classification of the complexity and rewritability of ontology-mediated queries based on the description logic EL

DOI10.1016/J.ARTINT.2022.103709zbMATH Open1495.68211arXiv1904.12533OpenAlexW2940854778MaRDI QIDQ2144172FDOQ2144172

Authors: Carsten Lutz, Leif Sabellek 

Publication date: 1 June 2022

Published in: Artificial Intelligence (Search for Journal in Brave)

Abstract: We provide an ultimately fine-grained analysis of the data complexity and rewritability of ontology-mediated queries (OMQs) based on an EL ontology and a conjunctive query (CQ). Our main results are that every such OMQ is in AC0, NL-complete, or PTime-complete and that containment in NL coincides with rewritability into linear Datalog (whereas containment in AC0 coincides with rewritability into first-order logic). We establish natural characterizations of the three cases in terms of bounded depth and (un)bounded pathwidth, and show that every of the associated meta problems such as deciding wether a given OMQ is rewritable into linear Datalog is ExpTime-complete. We also give a way to construct linear Datalog rewritings when they exist and prove that there is no constant Datalog rewritings.

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

Recommendations

• The data complexity of description logic ontologies
• Ontology-mediated queries. Combined complexity and succinctness of rewritings via circuit complexity
• The data complexity of ontology-mediated queries with closed predicates
• Dichotomies in Ontology-Mediated Querying with the Guarded Fragment
• Tree-like queries in OWL 2 QL: succinctness and complexity results

zbMATH Keywords

description logiccomplexity classificationrewritabilitylinear Datalogontology-mediated querying

Mathematics Subject Classification ID

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

Cites Work

• Deciding inseparability and conservative extensions in the description logic
• Tractable reasoning and efficient query answering in description logics: The DL-Lite family
• Query Answering in the Description Logic Horn- $\mathcal{SHIQ}$
• Title not available (Why is that?)
• The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
• Title not available (Why is that?)
• Taming the infinite chase: query answering under expressive relational constraints
• Data complexity of query answering in description logics
• Dualities for Constraint Satisfaction Problems
• Ontology-based data access: a study through disjunctive Datalog, CSP, and MMSNP
• Tractable query answering and rewriting under description logic constraints
• Alternating automata on infinite trees
• Title not available (Why is that?)
• Ontologies and Databases: The DL-Lite Approach
• Majority constraints have bounded pathwidth duality
• Data Complexity in the $\mathcal{EL}$ Family of Description Logics
• Linear Datalog and Bounded Path Duality of Relational Structures
• Title not available (Why is that?)
• CSP duality and trees of bounded pathwidth
• Transforming Two-Way Alternating Finite Automata to One-Way Nondeterministic Automata
• An introduction to description logic
• The Complexity of Conjunctive Query Answering in Expressive Description Logics
• The complexity of boundedness for guarded logics
• Ontology-Mediated Query Answering with Data-Tractable Description Logics
• PREDICATE BOUNDEDNESS OF LINEAR MONADIC DATALOG IS IN PSPACE
• \(n\)-permutability and linear Datalog implies symmetric Datalog
• The data complexity of ontology-mediated queries with closed predicates
• Rewritability in monadic disjunctive Datalog, MMSNP, and expressive description logics

Cited In (11)

• First-Order Rewritability and Complexity of Two-Dimensional Temporal Ontology-Mediated Queries
• Datalog rewritability and data complexity of \(\mathcal{ALCHOIQ}\) with closed predicates
• The data complexity of description logic ontologies
• Rewritability in monadic disjunctive Datalog, MMSNP, and expressive description logics
• The data complexity of ontology-mediated queries with closed predicates
• Deciding FO-rewritability of Regular Languages and Ontology-Mediated Queries in Linear Temporal Logic
• Ontology-mediated queries. Combined complexity and succinctness of rewritings via circuit complexity
• Checking the data complexity of ontology-mediated queries: a case study with non-uniform CSPs and Polyanna
• Ontology-based data access: a study through disjunctive Datalog, CSP, and MMSNP
• Query rewriting under linear \(\mathcal {EL}\) knowledge bases
• When is ontology-mediated querying efficient?

This page was built for publication: A complete classification of the complexity and rewritability of ontology-mediated queries based on the description logic \(\mathcal{EL}\)

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