Jatalog: Why Jatalog?

Jatalog: Why Jatalog?

I recently posted an entry on my Jatalog project, which is a Java implementation of the Datalog deductive database system. I thought I could elaborate on why I created it.

At some point in my career I was working at a department of a cellphone company that developed all sorts of software to keep the network operational. We were always wondering about ways to do Root Cause Analysis: If a network link broke down somewhere, then everything that relies on that link also fails. Being able to identify the failed link would've sped up the troubleshooting process immensely.

Unfortunately the network was old and a lot of equipment in it was added and removed and replaced over the years so there was no complete database of exactly what equipment was in the network and how they depended on each other.

It is by some coincidence that I learned of Datalog, but the concepts behind it made me think back to the root cause analysis problem, and so I was inspired to create my own Datalog implementation.

Datalog on its own wouldn't have been able to solve root cause analysis, but I imagined that it could be used track the pieces of equipment and to model the relationships between them. The Datalog queries could then be used to derive new relationships that can be processed later.

Another motivation for trying to create a Datalog implementation was a series of articles by Jonathan Blow on Predicate Logic and the implementation of his programming language Lerp (part 1, part 2 and part 3).

Blow describes a computer game scripting language where predicate logic is used as a first class construct. The facts can be used to describe states in the game, like "the ogre is at the tavern", "the ogre is carrying the sword" and then to use predicate logic to infer new facts, like "the sword is at the tavern".

I liked his ideas: I imagined a system where NPCs could have their own goals and motivations, so that the story could be more emergent on the player's actions. As an example, the Ogre carries the sword. The ogre wants revenge on the troll. If the player fights the troll, the ogre might be willing to give his sword to the player, otherwise the ogre might go and fight the troll himself, and if the ogre loses, the troll might end up with the sword.

However, I didn't think it was necessary to implement predicate logic as a first order construct in a new programming language. It would suffice to create a Datalog implementation as a library that is exposed to an existing language.

I decided to implement the Jatalog engine in Java as a proof-of-concept first. The source code is now available on GitHub under the Apache license.

It took me a while to finish my implementation. Looking back on it now, the engine doesn't feel that complex, but reading the literature and understanding how to implement algorithms took up so much time.

There are several open-source implementations available online, but I couldn't find any modern implementations that has all the features of Jatalog. Stratified negation is a particularly rare feature, for example, but Jatalog wouldn't have been complete without it.

The README.md as well as my previous blog entry contains a lot of notes about the implementation.