Tags:Datalog, existential rules, large-scale reasoning, model construction, restricted chase and tuple-generating dependencies
Abstract:
Existential rules are a syntactic variant of first-order Horn logic that has gained prominence in several communities. Such rules are used to express ontologies in knowledge representation, dependencies in databases, and recursive queries in data analytics. In this system description, we present our recent extension of the rule reasoning and query engine VLog with support for existential rules. Our column-oriented implementation of the restricted chase procedure aims at constructing a universal model for a Horn logic theory. While query answering in this logic is undecidable, and universal models might be infinite, our implementation can find a finite model in many cases. We conduct an evaluation over several real-world theories with millions of facts and thousands of rules, and we show that VLog can compete with the state of the art. Other notable features of our system include support for a variety of input sources and databases, query answering capabilities, cross-platform support, and excellent memory efficiency. The latter makes it possible to compute models with hundreds of millions of relational tuples on a laptop.
Efficient Model Construction for Horn Logic with VLog: System Description