First Order-Rewritability and Containment of Conjunctive Queries in Horn Description Logics

2020/11/19 by Bienvenu, Meghyn, Hansen, Peter, Lutz, Carsten +1 · 1 citation
#Artificial Intelligence (cs.AI) #Databases (cs.DB) #FOS: Computer and information sciences

paper · doi:10.48550/arxiv.2011.09836

Abstract

We study FO-rewritability of conjunctive queries in the presence of ontologies formulated in a description logic between EL and Horn-SHIF, along with related query containment problems. Apart from providing characterizations, we establish complexity results ranging from ExpTime via NExpTime to 2ExpTime, pointing out several interesting effects. In particular, FO-rewriting is more complex for conjunctive queries than for atomic queries when inverse roles are present, but not otherwise.

Cited by

• Tractable Responsibility Measures for Ontology-Mediated Query Answering

Related

• First-Order Rewritability of Frontier-Guarded Ontology-Mediated Queries
• From Conjunctive Queries to Instance Queries in Ontology-Mediated Querying
• A Complete Classification of the Complexity and Rewritability of Ontology-Mediated Queries based on the Description Logic EL
• On the Succinctness of Query Rewriting over OWL 2 QL Ontologies with Shallow Chases
• Conjunctive Query Containment and Answering under Description Logics Constraints