Horn ontologies consisting of existential rules are used in various fields ranging from reasoning over knowledge graphs [7] and Description Logics (DL) ontologies [5,6], to data integration [4] and social network analysis [10]. To solve conjunctive query answering over these logical theories, we can apply the chase algorithm-a sound and complete (albeit non-terminating) bottom-up materialisation procedure where all relevant consequences are precomputed, allowing queries to be directly evaluated over materialised sets of facts. As our main contribution, we extend the in-memory Datalog engine VLog [11] to support Horn existential rules without equality (a fragment that encompasses HornSRI in terms of expressivity). Namely, we implement the skolem and the restricted variants of the chase on VLog's architecture. In the skolem chase, rules are replaced by their skolemisation. In the restricted chase, new terms are introduced during the reasoning process only if already derived terms and facts cannot be reused to satisfy the corresponding existential restriction. The latter terminates in many more cases than the former [2,3] and often produces smaller models, but termination depends on the rule application order and its implementation requires value reusability checks. We implement a slightly different version of the restricted chase which leads to termination in more cases [3], by prioritising the exhaustive application of Datalog rules (rules without existentially quantified variables). This enables facts derived from Datalog rules to satisfy some existential restrictions that would otherwise lead to non-termination. In our implementation, we exploit the highly memory-efficient architecture of VLog, based on columnar storage: instead of storing a list of tuples (rows), the data is organised into a tuple of columns (value lists). The columns are ordered lexicographically, enabling fast merge joins and duplicate elimination, as well as data compression schemes for low memory usage. Because updates are slow in columnar tables, VLog operates in appendonly mode, applying one rule per materialisation step, and creating separate tables for the derived facts. To reduce redundant derivations, VLog uses semi-naive evaluation, which only considers rule body matches that were not found up to the previous application of the same rule. We adopted the 1-parallel-restricted chase [1] optimisation, in which the facts derived in the ongoing chase step are not checked for value reusability. We evaluate our implementation using existential rule programs from a recent (skolem and restricted) chase benchmark [1]. In addition, we also use rules obtained from translating data-rich, real world OWL ontologies (UOBM, Reactome, and Uniprot). The test data involves programs with millions of facts and thousands of rules, and predicates with relatively large arities (maximum 11). We test increasing partitions of data for the
same rule sets. In each case, we run the skolem and restricted chase on a commodity
laptop, and measure time and peak memory usage. We compare the results against the chase
benchmark leading system, RDFox [
The results for the restricted chase are shown in Figure 1. Both VLog and RDFox require significantly less time and memory for the restricted chase, with only few exceptions (deep-100, deep-200, Ontology-256 require slightly less time and memory in the skolem chase). These findings further motivate the use of the restricted chase.
On average, VLog uses only 40% of the memory required by RDFox, ostensibly due to its compressed data structures. In two cases, RDFox runs out of memory, while VLog terminates (using OS swap space in only one case). Regarding time performance, VLog takes between 5.8% and 137.5% of the time needed by RDFox. RDFox outperforms VLog for only two ontologies, UOBM and doctors. This result is surprising, since VLog ran on a single thread, while RDFox used maximal parallelism (8 cores), in some cases peaking at over 700% of CPU usage.
To summarise, we provide the first implementation of the chase on a columnar architecture, by extending VLog. Our tool is more memory-efficient than the state of the art while being comparatively fast, even on a single thread. VLog is free and open-source. It can be used in two ways: as a command-line client with an optional web interface,3 and through a Java API4 with additional functionality (translating OWL files to rules, executing SPARQL queries against remote endpoints, integrating RDF data, . . . ). We hope our tool proves useful for the community, and encourages a broader adoption of the expressive language of existential rules.
Acknowledgements This work was supported by the DFG within the cfaed Cluster of Excellence, CRC 912 (HAEC), and Emmy Noether grant KR 4381/1-1. 3 VLog core reasoner: https://github.com/karmaresearch/vlog 4 VLog4j: https://github.com/knowsys/vlog4j, also available via Maven