KiWi Reasoner

The KiWi reasoner is a powerful and flexible rule-based reasoner that can be used on top of a KiWi Triple Store. Its expressivity is more or less the same as Datalog, i.e. it will always terminate and can be evaluated in polynomial time (data complexity not taking into account the number of rules). In the context of triple stores, the KiWi reasoner can be used to easily implement the implicit semantics of different domain vocabularies. For example, the following rule program expresses SKOS semantics:

@prefix skos: <>

($1 skos:broader $2) -> ($1 skos:broaderTransitive $2)
($1 skos:narrower $2) -> ($1 skos:narrowerTransitive $2)

($1 skos:broaderTransitive $2), ($2 skos:broaderTransitive $3) -> ($1 skos:broaderTransitive $3)
($1 skos:narrowerTransitive $2), ($2 skos:narrowerTransitive $3) -> ($1 skos:narrowerTransitive $3)

($1 skos:broader $2) -> ($2 skos:narrower $1)
($1 skos:narrower $2) -> ($2 skos:broader $1)

($1 skos:broader $2) -> ($1 skos:related $2)
($1 skos:narrower $2) -> ($1 skos:related $2)
($1 skos:related $2) -> ($2 skos:related $1)

Similarly, the reasoner can be used for expressing RDFS subclass and domain inference, as well as a subset of OWL semantics (the one that is most interesting :-P ). Beyond RDFS and OWL, it also allows implementing domain-specific rule semantics. Additional examples for programs can be found in the source code.

The reasoner is implemented as a incremental forward-chaining reasoner with truth maintenance. In practice, this means that:

Maven Artifact

The KiWi Reasoner can only be used in conjunction with the KiWi Triple Store, because it maintains most of its information in the relational database (e.g. the data structures for truth maintenance) and directly translates rule body query patterns into SQL. To include it in a project that uses the KiWi Triple Store, add the following dependency to your Maven project:


Code Usage

The KiWi Reasoner can be stacked into any sail stack with a transactional sail (see kiwi-transactions) and a KiWi Store at its root. The relevant database tables are created automatically when the repository is initialised.A simple repository with reasoner is initialized as follows:

KiWistore store = new KiWiStore("test",jdbcUrl,jdbcUser,jdbcPass,dialect, "http://localhost/context/default", "http://localhost/context/inferred");
KiWiTransactionalSail tsail = new KiWiTransactionalSail(store);
KiWiReasoningSail rsail = new KiWiReasoningSail(tsail, new ReasoningConfiguration());
Repository repository = new SailRepository(rsail);

// add a reasoning program
rsail.addProgram("simple", this.getClass().getResourceAsStream("simple.kwrl"));

// update an existing reasoning program
rsail.updateProgram("simple", ...);

// run full reasoning (delete all existing inferred triples and re-create them)

The reasoner can have any number of reasoning programs. The concept of a program is merely introduced to group different tasks. Internally, all reasoning rules are considered as an unordered collection, regardless which program they belong to.

Performance Considerations

Even though the reasoner is efficient compared with many other reasoners, there are a number of things to take into account, because reasoning is always a potentially expensive operation:

  • reasoning will always terminate, but the upper bound for inferred triples is in theory the set of all combinations of nodes occurring in base triples in the database used as subject, predicate, or object, i.e. n^3
  • specific query patterns with many ground values are more efficient than patterns with many variables, as fixed values can considerably reduce the candidate results in the SQL queries while variables are translated into SQL joins
  • re-running a full reasoning can be extremely costly on large databases, so it is better configuring the reasoning programs before importing large datasets (large being in the range of millions of triples)
  • updating a program is more efficient than first deleting the old version and then adding the new version, because the reasoner compares old and new program and only updates the changed rules

In addition, the reasoner is currently executed in a single worker thread. The main reason is that otherwise there are potentially many transaction conflicts. We are working on an improved version that could benefit more from multi-core processors.