Introduction

Datalog is an important rule language [1] forming the basis for many more complex formalisms such as existential rules [2,3] that are of interest in both theory and practice. Accordingly, many rule reasoning systems have been presented, which we can roughly classify in the following types [4]:

1. Answer set programming solvers [5,6] and logic programming systems such as Prolog [7] 2. Knowledge graph and database engines such as RDFox [8], VLog [9], Vadalog [10], and Graal [11] 3. Data-analytics systems such as Soufflé [12], LogicBlox [13], SocialLite [14], or EmptyHeaded [15] 4. Data management frameworks such as Datomic, Google Logica, and CozoDB Despite the wide variety of tools, many systems described in the literature may not be a viable choice in practice, due to discontinuation or access restrictions of closed-source commercial systems. In the field of logic programming, these problems have been overcome, and advanced open-source systems such as Clingo [16] are available to researchers, whereas the situation in other rule system categories is more precarious. Among the mentioned systems of types (2) and (3), the only open-source tool with a release in the past twelve months is Soufflé.

In this extended abstract, we summarize our recent paper [17] on our new rule reasoning toolkit Nemo built for applications of type ( 2) and (3), where the computation of logical entailments (or query results) from a variety of inputs is the main reasoning task. Nemo's rule language extends Datalog with various datatypes, negation, aggregates (both stratified), and many datatype-specific functions and operators known from query languages like SPARQL while also supporting existential rules with a fast implementation of the restricted (or standard) chase algorithm.

Thanks to Nemo's modular architecture, we can provide command-line clients for all major platforms, a public web application with a built-in rule editor, an IDE plugin for rule editing in VSCode, and APIs for integration in several programming languages. All components of Nemo are free and open source, and their development repositories public. Most of Nemo is written in Rust, a language that emphasizes type and memory safety, and code quality is an explicit concern. The source code is available at https://github.com/knowsys/nemo.

System Overview

The Nemo toolkit consists of several programs and libraries. This includes a command-line application called nmo, and a web application 1 shown in Figure 1 (left). The web application utilizes Nemo's WebAssembly interface, enabling it to run entirely in the browser without any installation. It features a powerful rule editor with syntax highlighting and auto-complete, which is made possible by Nemo's implementation of the open language server protocol [18]. This also enables advanced editor support for Nemo's rule language within compatible IDEs, such as VSCode. Nemo further provides a Python and Rust developer API, which expose import/export, the reasoner, and give access to the internal rule structure.

The core of Nemo is a fast and scalable reasoner that materializes logical consequences using semi-naive bottom-up evaluation [1]. For any inference that is computed, Nemo can also provide a computation trace that encodes a proof tree. This trace is available in machine-readable JSON format or in more visual representations. Figure 1 (right) shows an example use of this feature on the console.

Nemo keeps data in-memory, representing tables as hierarchically-sorted, column-based tables, following the design in VLog [9]. In contrast to VLog, our columns support domain elements of several types: fixed-size values (e.g., 32bit floats or 64bit signed integers) are stored directly, while variable-sized data (e.g., strings and IRIs) is first mapped to integer ids through a dictionary. Data in columns is further compressed using Run-Length-Encoding with increments. Tables in Nemo are accessible via trie iterators [19], which makes it possible to utilize the leapfrog trie-join [20], a multi-way, worst-case optimal join algorithm. In this setting, query plans are largely determined by the variable (column) order, which we heuristically determine by searching for orders that avoid inefficiencies like cross-products and excessive reordering of tables. The implementation for operations like union or difference also make use of this trie-based access. Projection and resorting of tables cannot be implemented efficiently in this way, however, and require row-based temporary tables.

Nemo's efficient storing mechanism combined with its use of state-of-the-art join algorithm and additional optimizations makes its performance competitive with other mature systems, often outperforming them on our benchmarks [17]. We were surprised that our browser-based Nemo Web often competed for second place in these evaluations. Our experiments with a version of the Wikidata knowledge graph [21] show that Nemo can reason with data sets of several billion triples. Further details on these evaluations can be found in Section 5 of [17].

Language Features

Nemo's rule language is based on Datalog [1], which is extended with many features of modern query and rule languages. 2 The syntax largely follows common logic programming conventions, representing rules as implications consisting of conjunctions of first-order atoms where variables are universally quantified.

As usual in logic programming, anonymous body variables are denoted by _ and treated like different variables, i.e. variables _ in Line 6 are distinct. Moreover, Nemo considers variables that occur only in negated body atoms to be existentially quantified beneath the negation. Hence, ~sibling(?C,_) requires that all sibling facts do not match this pattern, whereas child(?C,_) requires some matching fact. A similar convention is used in the answer set programming, e.g., in current versions of Clingo [5].

Data Import and Export

External data can be imported into Nemo using the following syntax:

7 @import parents :-csv { resource = "parents.csv.gz", limit = 100 } . 8 @import nameAndYearOfBirth :-csv { resource = "https://www.data.com/name_year.csv" } .

When providing an online resource through a URL as shown in Line 8, data will be downloaded upon program evaluation. Currently, Nemo is able to process data encoded as CSV (with user-set delimiter) or RDF. For RDF, triples (NTriples, Turtle, RDF/XML) and quads (TRiG, NQuads) are supported. All formats are available for export using analogous syntax via the @export directive. On the command-line, results may also be printed on the console. Various details of the import and export can be controlled through optional parameters, and data can be processed with GZip compression.

Datatypes and Functions

Nemo natively supports values of many different data types, including integer, string, language-tagged string, single and double precision float, and Boolean. To manipulate such values, Nemo offers a wide range of built-in functions, which largely correspond with SPARQL FILTER expressions. Such functions include standard arithmetic operators and mathematical functions on numbers such as SQRT, functions for string manipulation such as CONCAT, Boolean operators, as well as comparison operators such as < or !=. Functions can be nested arbitrarily and may occur anywhere in the rule. Bindings for any variable used within a function must be sufficiently determined, similar to the standard safety condition used for Datalog rules.

Nemo is dynamically typed and therefore allows values of any type to be used in any position, without requiring a fixed schema. Most functions, such as STRLEN are not defined for all types of inputs, instead producing no result when given a value of unsupported type.

Aggregation Nemo supports common aggregates such as #count, #sum, or #max, as shown next:

9 childCount(?P, #count(?C)) :-child(?C, ?P) .

Rule 9 counts, for each value of ?P, the number of distinct values of ?C that satisfy the rule body. We distinguish three kinds of variables: aggregate variables occur in aggregate functions (in the head), group-by variables are the head variables that are not aggregate variables; and body-only variables that do not appear in the head. Aggregation is evaluated as follows: (1) find all rule matches, (2) project away bindings of body-only variables and remove duplicates that agree on all remaining variables, (3) group the set of projected matches by distinct values of group-by variables, and (4) apply the aggregation function on each group. Duplicate elimination in (2) means we always aggregate over sets, corresponding to the keyword DISTINCT in many query languages. Users control the semantics through variables in the head: 10 sum1(?A, ?B, #sum(?N)) :-p(?A, ?B, ?N) . Existential Rules Existential rules, also known as tuple-generating dependencies, are an important formalism used to describe integrity constraints [23] or to formulate dependencies within a data exchange setting [24]. Syntactically, they are represented by introducing existentially quantified variables in the rule head, denote by ! in Nemo, as shown in the next example:

13 child(?C, !P), child(!P, ?G) :-grandchild(?C, ?G) .

Nemo supports reasoning over existential rules by implementing the restricted (a.k.a. standard) chase [2,3]. For each match of the body of rule 13, Nemo creates a fresh value for !P, provided that the head is not satisfied for any existing value yet. Fresh values are represented in Nemo by named nulls, which we treat as a separate type of domain element distinct from other elements. Named nulls are identified with RDF blank nodes in data import and export, and denoted accordingly (using notation like _:42).

Conclusion and Future Work

Nemo is a comprehensive framework for rule reasoning that includes a scalable rule engine, a feature-rich rule language, and advanced user interfaces with strong developer support. Further development of Nemo will focus on enhancing its expressive power by introducing native support for complex types such function terms and sets, and adding user-defined functions to increase flexibility and unlocking additional use cases. To further improve performance, we will transition Nemo's implementation to being able to utilize multi-threading. Next steps to improve developer tools include better highlighting of static analysis results to the user and better tracing support in the Nemo web application, which will simplify debugging and create a more robust and explainable reasoning system.