Rel: Live Programming and Self-Modifying Models

Posted December 7, 2021 by Martin Bravenboer and George Kastrinis ‐ 7 min read

Introducing Rel's semantics for self modification.

The RAI Relational Knowledge Graph Management System (RKGMS) and the Rel language are, from first principles, designed for live programming. The Rel model can be edited by users interactively, and the system incrementally recompiles and reevaluates the model. The system is capable of handling erroneous models and can still evaluate the parts of the model that are correct. This results in a spreadsheet-like experience where results of computations can immediately be inspected by the user while modeling and developing the business logic.

On-Demand and Incremental

At the core of the Rel compiler implementation is Salsa.jl, a framework for on-demand and incremental computation. Salsa makes sure that while the model is changed by the user, everything that depends on these changes gets recompiled and reevaluated. Salsa tracks the dependencies in the model precisely, which makes it virtually impossible for any correctness bugs related to incremental compilation to creep in.

Salsa plays a role here that is similar to a build system that supports separate compilation and memoization of build results. We developed Salsa.jl based on Rust language’s salsa-rs. It is available as an open-source package for the Julia language. The package can be used independent of RelationalAI for building on-demand, incremental systems.

There is a beautiful analogue of incremental compilers with existing database system concepts. The Rel model is source text that is modified over time, similar to how data is modified in database systems. In database systems, there are often temporal features to access the state at different points in time. The compiled Rel model is a materialized view (similar to memoization in programming languages) that is derived from the source Rel model. To understand the provenance of the compiled Rel model to the source code, we use dependency tracking (provenance in databases). Understanding the dependencies and changes enables incremental recompilation, which is similar to incremental view maintenance (IVM) in databases.

Our RKGMS unifies these techniques from programming languages and database systems into a single system that is entirely live and demand-driven, for changes to both the model as well as the data. This architecture is also covered in our JuliaCon 2020 talk Salsa.jl: A framework for on-demand, incremental computation.

The Model as a Relation

To fully integrate the evolving model, Rel now exposes the model as an actual relation that can be updated from within the Rel model itself. Updating this relation is now also the only way to update the model.

At the lowest level, this relation can be used to add to the model, query the model, update the model, or delete from the model.

To add to the model, we insert new values into rel:catalog:model. For example:

def insert:rel:catalog:model["My Model 1"] = """
def foo = 1
def bar = 2
"""
def output = foo

The new model can be used immediately in the same transaction. In the example, the relation foo is immediately queried as well, even though it does not exist until after the model has been modified.

The Rel model can now be queried with arbitrary Rel, for example, we can ask for only one specific model:

def output = rel:catalog:model["My Model 1"]

Or, in order to get the names of only parts of the model:

def output(name) = rel:catalog:model(name, _)

To delete from the model, we delete from the model relation, similar to how Rel supports deleting any data. Deletion from the model is handled in the same transaction and the deleted part of the model no longer exists in the next database state.

def delete:rel:catalog:model["My Model 1"] =
rel:catalog:model["My Model 1"]

It is not necessary for users to directly write Rel to update a Rel model as in the above examples: the existing RAI SDK functions (e.g. the RAI SDK for Python) continue to work as-is and are now implemented internally as rel:catalog:model modifications.

Beyond the Basics

You may be curious how far you can go with this. Technically, the program is self-modifying here, so how far can we push that exactly? The answer is very far, and the exciting thing is that this is largely an emergent property of the system.

The RAI RKGMS supports arbitrary changes to the model within a single transaction. This is similar to making schema or materialized view changes in a relational database system. In database systems, often schema changes are not supported in general or are not ACID (having transactional properties), but because RAI is designed from the ground up to support live programming, we have engineered the entire system to support changes. The actual computations, as well as the arity and types of view definitions, can be changed in any way necessary.

The RAI RKGMS also has temporal capabilities. While not yet exposed in general, Rel is designed to support writing logic spanning multiple database states (full support for temporal features is coming in the first half of 2022!). The design of these capabilities is based on Statelog, an extension of Datalog that provides solid semantics for writing business logic with a temporal dimension. Arbitrary Rel model modifications are supported at every database state, and every transaction can go through a sequence of states.

This all sounds very complicated to implement correctly, but when designed the right way, it essentially becomes an emergent property. This is Salsa all the way down. Salsa has native support for a temporal dimension and dependencies and memoization are correctly handled by the framework. Sequences of modifications to the model can be made within a single database transaction through a sequence of Salsa epochs. Additionally, because Salsa can be used with versioned data structures, it’s possible to explicitly refer to the model at a specific point in time to implement as-of queries and data migration logic if needed.

Thanks to the rigorous foundation in Statelog and the implementation based on the Salsa framework, Rel has clear semantics for self-modification.

As well as intriguing self-modifying programs (we’re looking forward to seeing the exciting applications our users will come up with), there are also very practical applications of general support for self-modification (while hopefully not resulting in the robot apocalypse).

For instance, we could envision a full package management system for Rel, expressed in Rel. Package managers can be seen as a knowledge graph of packages, with constraints on the compatibility of packages and information such as licenses, version history, etc. Package management is not a trivial problem: some sophisticated package managers even use constraint solvers to find a compatible set of packages to install. Rel is an ideal language for this.

Most current package managers destructively update the environment, and if this update needs to be rolled back that is often not possible. With a package manager in Rel, it becomes possible to atomically update packages and apply migration procedures, and only succeed if integrity constraints in the model are not violated. This entire procedure is isolated in an ACID transaction and no user sees any changes until everything is successful.

A simple example of this could be a JSON file in S3 that specifies the content of a package. For example:

{ "name": "My Awesome Package",
  "version": 14,
  "model": [
    {"url": "s3://...", "sha256": "..."},
    {"url": "s3://...", "sha256": "..."}
  ]
}

This JSON file can be loaded into Rel, followed by adding the package to the model:

def pkg_json = load_json[...]

def pkg_model[v, url] = load_binary[url],
pkg_json:model(_, :url, url) and
pkg_json:version(v)

def insert:rel:catalog:model = pkg_model[14]

This example illustrates that the source text of the model can be obtained from arbitrary places and that the choice of the model to enable can be based on arbitrary logic, such as configuration choices, meeting requirements from dependencies, etc.

We are excited about the generalized capabilities to edit the model and we look forward to seeing what our user community will do with this!