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

DOI10.1016/J.ARTINT.2022.103709MaRDI QIDQ2144172zbMATH OpenOpenAlexFDO

Authors Carsten Lutz, Leif Sabellek

Publication date 1 June 2022

Published in Artificial Intelligence (Search for Journal in Brave)

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

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)

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.

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

Cites work

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

Cited in

(11)

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

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)