A Practical Acyclicity Notion for Query Answering over Horn-SRIQ Ontologies
This addresses a challenging problem in knowledge representation and reasoning for applications like semantic web and databases, though it appears incremental as it generalizes existing conditions.
The paper tackles the problem of conjunctive query answering over Horn-SRIQ ontologies by defining a novel acyclicity notion that ensures termination of the restricted chase algorithm, and it results in a materialization-based reasoner that outperforms other state-of-the-art systems.
Conjunctive query answering over expressive Horn Description Logic ontologies is a relevant and challenging problem which, in some cases, can be addressed by application of the chase algorithm. In this paper, we define a novel acyclicity notion which provides a sufficient condition for termination of the restricted chase over Horn-SRIQ TBoxes. We show that this notion generalizes most of the existing acyclicity conditions (both theoretically and empirically). Furthermore, this new acyclicity notion gives rise to a very efficient reasoning procedure. We provide evidence for this by providing a materialization based reasoner for acyclic ontologies which outperforms other state-of-the-art systems.