About

RNT is an experimental database kernel written in OCaml, modeled on the Windows NT kernel. As in NT, the kernel doesn't understand any query language itself. It manages objects (relations, tuples, branches, sessions, programs, evaluators) and exposes them through named paths, handles, and protocols. Query languages and data models are meant to sit on top as subsystems, the way Win32 and POSIX sit on top of the NT native API.

The relational model is the common ground. RNT is designed to host several subsystems over it: a purely relational language such as Sakura, a graph view for network design, a SQL interface for legacy compatibility, or a virtual machine for a functional language that treats relations as values. Today it ships one: a first-order logic evaluator for retrieval.

RNT takes its name inspiration on the the NT kernel that inspired it, but it stands for "Relations, Not Tables".

The goal is a small runtime you can read end to end: database state is reached through uniform paths, access goes through explicit handles, and every object follows visible lifecycle rules. The kernel sits between the subsystems, protects the integrity of the data, and keeps the logical representation separate from the physical one.

Motivation

The relational model is one of the most beautiful inventions in computer science (C. J. Date's Introduction to Database Systems citation needed), and in its purest form (that is, the relation theory in mathematics) it renders a disproportionally strong foundation representation of information in comparison to its simplicity. Attempts to design systems relying on other abstractions often fail to provide a generic representation of an algebra with sufficient guarantees. And atop of that, DBMSes usually go for the monolithic route, that usually constraints the system to perform a set of operations and create an ever increasingly complex system, full of potential edge cases. With the borrowed abstractions from a hybrid kernel such as NT, we gain enormous extensibility while keeping a great deal of purity of information representation.

The NT kernel is a good model for a dedicated database kernel for three reasons:

Object management: Every kernel resource in NT has a path in a hierarchical namespace, an access check, and a lifecycle governed by handles. A database needs the same for relations, transactions, cursors, and namespaces. RNT uses this one model for all of them instead of building each mechanism separately, so the whole runtime can be explored through one interface.
Hardware abstraction: NT drivers expose a narrow dispatch table, and the kernel doesn't care what device is behind it. RNT treats storage backends the same way: a backend implements a small interface, and the kernel stays unaware of the engine. The goal is to let each dataset choose its own driver, for example a local key-value store for one dataset and etcd for another, both active at once.
Clients as environment subsystems: In RNT, a query language is a subsystem that translates its own conventions into kernel operations, as Win32, POSIX, and OS/2 do over NT's native API. For relational work, write a first-order logic evaluator. To run a lambda calculus language, write a virtual machine. Because all subsystems share the same objects, they are meant to work with one another.

Design

RNT has very few fixed parts. Most of what a database usually hard-codes, such as what an object can do, which language queries it, and where its bytes live, is something you can add from outside the kernel without touching it.

Everything is an object, and everything has a path

Relations, branches, sessions, evaluators and every object live in one object tree. If you can name it, you can reach it:

Path.lookup root ("system" @/ "session" @/ "client" @/ "branch" @/ this)

See docs/object-system.org and docs/object-taxonomy.org.

Teach objects new tricks

What an object can do is a list of protocols: Directory, Enumerable, Cursor, Evaluator, and so on. The set is open, so your own code can declare a new protocol and build objects that speak it alongside the built-in ones:

type Protocols.Handle.protocol += Describable of < describe : string >

let staff =
  Kernel.Prototype.mixture
    [ Describable (object method describe = "everyone on payroll" end);
      Kernel.Prototype.Directory.of_properties ["employee", employees] ]

Clients that only know Directory keep working. Clients that know Describable ask the handle for it, and get it only if the object supports it.

Bring your own language

The kernel ships no query language. A program names the evaluator that runs it and carries a kind, a constructor that evaluator adds to Program.kind. An evaluator is an object with the Evaluator protocol, which parses source into its kind and evaluates the kind against a directory. Here is a language whose programs count the tuples of the relation at a path:

type Kernel.Program.kind += Count of Kernel.Path.t

let heading = BatMap.String.singleton "n" {Protocols.Schematics.domain= "integer"; provenance= []}

let counter =
  Protocols.Evaluator.make
    (object
       method parse source =
         Ok (Count (Kernel.Path.of_list (String.split_on_char '\\' source)))

       method eval kind _inputs ~within =
         let open Utilities.Result in
         match kind with
         | Count path ->
             let* relation = Kernel.Path.lookup within path in
             let* _, tuples = Protocols.Relation.read relation in
             let n = Concepts.Value.Integer (List.length tuples) in
             Ok
               (Kernel.EphemeralRelation.literal heading
                  [{Concepts.Tuple.type_= "count"; attributes= BatMap.String.singleton "n" n}] )
         | _ -> Error Concepts.Condition.(condition "not-a-count" "Not a count program" empty)
     end )

Register it under \system\evaluator\count, next to the first-order logic evaluator that ships with RNT, and a program built with Kernel.Program.make ~root ~evaluator:"count" runs through it. See docs/evaluators.org.

Bring your own storage

A storage backend implements eight operations: connect, disconnect, start a transaction (read-write or read-only), commit, abort, get, and put. The LMDB driver is about 230 lines. Everything above it, including relations, indexes, and branches, comes from the kernel.

Tuples are content-addressed (SHA-256 of their encoding) and indexed by prolly trees, so every state of a relation has a hash. That gives versioning almost for free: branches are kernel objects, and a session can pin a snapshot while its branch keeps moving.

Nothing happens behind your back

All access goes through an explicit handle, which makes ownership, accounting, and cleanup visible. Opening, closing, pinning, cleanup, and contention are runtime responsibilities with documented rules; see docs/lifecycle.org. Access checks are planned to stay separate from object lookup, so security policy can evolve on its own.

Status

RNT is early and its APIs will change. What works today, with tests:

content-addressed tuple storage on LMDB
prolly-tree indexes (chunking is still naive; see lib/kernel/Merkle.ml)
branches whose earlier states stay reachable under previous, and sessions that pin a snapshot
programs that name their evaluator, stored as ephemeral relations and run against the branch state they are read through
path lookup across the object tree
substantial and ephemeral relations with pull-based cursors
modes that say what each relation can produce and decide, so that a relation without end is never read to its end
denials, which keep a branch head from moving to a state that breaks them
a FOL evaluator supporting scan and projection, which reads programs written in other languages

Building

With Nix (GNU/Linux, macOS)

nix build                          # build and run the tests
nix develop --command dune test    # or work inside the dev shell

License

RNT is free software licensed under the GNU Affero General Public License v3.0. See LICENSE for the full terms.

Maintainers: Marcos Magueta & Estevan Castilho.