Skip to main content

Reasoning over Existential Rules with Acyclicity Notions

David Carral ( Technische Universit├Ąt Dresden )

The chase is a sound and complete (albeit non-terminating) algorithm for conjunctive query
answering over ontologies of existential rules. On the theoretical side, we develop sufficient conditions
to guarantee its termination (i.e., acyclicity notions), and study several restrictions that furthermore ensure
its polynomiality. On the practical side, we empirically study the generality of these conditions and we
extend the Datalog engine VLog to develop an efficient implementation of the chase. Furthermore, we
conduct an extensive evaluation, and show that VLog can compete with the state of the art, regarding
runtime, scalability, and memory efficiency.

Share this: