Karmeliet

Karmeliet is an experimental, in-memory, statically-typed triple store. It's currently missing many features, and is therefore not recommended for use.

See the documentation for examples.

lib.rs:

Karmeliet is an experimental, in-memory, statically-typed triple store. It's currently missing many features, and is therefore not recommended for use.

A triple store is a database that stores triples (subject, attribute, value). In Karmeliet, subjects are unique IDs called "entities", attributes are Rust types, and values are instances of those types.

Differences from other triple stores

Karmeliet is strongly-typed. You can think of it as having a strict schema on the columns of a database. In that sense, it is closer to e.g. Datomic than to Datascript.

Unlike most triple stores out there, Karmeliet is quite bare-bones, and does almost no work for you. For example, Datomic will compute several different indexes to make certain queries faster. Karmeliet does no such thing, and instead leaves it up to the user to build indexes via insertion and removal hooks. Currently, it also provides no declarative query API, which means the user must query data by mapping and filtering over Rust iterators. This might change in the future.

This is a sort of "rusty" trade-off. By being strict about types and not computing any indexes, Karmeliet can enjoy better performance than alternatives, and allows the user to model their domain more precisely. In exchange, it makes the database less flexible and requires more boilerplate to use efficiently.

Basic usage

Here's an example of using Karmeliet to store books in a simple database. It shows the basic API of the crate, but doesn't use any hooks.

use karmeliet::Store;

struct Book {
title: &'static str,
year: u16,
}

// Initialize an empty store
let mut store = Store::default();

// Create a new entity
let psalm = store.entity();

// Attach an attribute to that entity
store.insert(
psalm,
Book {
title: "A Plasm for the Wild-Built",
year: 2021,
},
);

// Retrieve that attribute
assert_eq!(
store.get::<Book>(psalm).unwrap().title,
"A Plasm for the Wild-Built"
);

// Create a few other entities
let song = store.entity();
store.insert(
song,
Book {
title: "The Song of Achilles",
year: 2011,
},
);
let circe = store.entity();
store.insert(
circe,
Book {
title: "Circe",
year: 2018,
},
);

// Iterate over entities with a `Book` attribute
let mut books: Vec<_> = store.iter::<Book>().collect();
books.sort_unstable_by_key(|(_, book)| &book.year);
assert_eq!(books[0].0, song);
assert_eq!(books[1].0, circe);
assert_eq!(books[2].0, psalm);

// Insert a second attribute on an entity
struct CurrentlyReading;
store.insert(circe, CurrentlyReading);

// Find the `Book` with `CurrentlyReading` attribute
let book = store
.iter::<CurrentlyReading>()
.find_map(|(entity, _)| store.get::<Book>(entity));
assert_eq!(book.unwrap().title, "Circe");

// Remove that attribute
store.remove::<CurrentlyReading>(circe);

// There's no longer a book with `CurrentlyReading`
let book = store
.iter::<CurrentlyReading>()
.find_map(|(entity, _)| store.get::<Book>(entity));
assert!(book.is_none());

Using hooks to maintain indexes

Karmeliet only provides fast, O(log N) access when querying an (entity, attribute) pair, or when accessing a range of entities with a specific attribute. If you need to query data by value, you'll have to iterate over every (entity, attribute) pair and keep only the ones that match.

This can be good enough, especially when prototyping. However, if you find that a specific query is too slow, then you might benefit from building an index to speed it up. This can be done with insertion and removal hooks, which are functions that run when attributes are inserted, removed, or updated.

In the following example, we use a hook to build a sorted map from year to entity, which can be used to query the range of all books published in a specific year, as well as just generally querying a range of books pre-sorted by year.

use std::collections::BTreeSet;
use karmeliet::{Entity, Store};

struct Book {
title: &'static str,
year: u16,
}

#[derive(Default)]
struct YearBooks {
index: BTreeSet<(u16, Entity)>,
}

let mut store = Store::default();

// Setup insert and remove hooks
store.hook_before_insert(|store, entity, book: &Book| {
// We store the index as an attribute on the entity `SINGLETON`, which
// exists for this exact purpose.
// `upsert` will create the attribute if it's missing.
store.upsert(Entity::SINGLETON, |YearBooks { index }| {
index.insert((book.year, entity));
});
});
store.hook_after_remove(|store, entity, book: &Book| {
store.upsert(Entity::SINGLETON, |YearBooks { index }| {
index.remove(&(book.year, entity));
});
});

// ...insert data into the store...

// Use the index to query all books published in 2018
let books: Vec<_> = store.get::<YearBooks>(Entity::SINGLETON)
.unwrap()
.index
.range((2018, Entity::MIN)..=(2018, Entity::MAX))
.flat_map(|&(_, entity)| store.get::<Book>(entity))
.collect();

Another common use case for hooks is to maintain indexes on specific entities. For example, we could complement our book database with authors. We'd do that by adding a new Author attribute, and storing the entity of an author inside each book. Now, if we might like to list all the books written by a given author. We can do this by adding a hook on books, which will construct an index for each author, listing the books they've written.

use std::collections::HashSet;
use karmeliet::{Entity, Store};

struct Person {
name: &'static str,
}

struct Book {
title: &'static str,
author: Entity,
}

#[derive(Default)]
struct AuthorBooks {
index: HashSet<Entity>,
}

let mut store = Store::default();

store.hook_before_insert(|store, entity, &Book { author, .. }: &Book| {
store.upsert(author, |AuthorBooks { index }| {
index.insert(entity);
});
});
store.hook_after_remove(|store, entity, &Book { author, .. }: &Book| {
store.update(author, |AuthorBooks { index }| {
index.remove(&entity);
});
});

// ...insert data into the store...

// Use the index to query all book titles from `some_author`
let titles_from_some_author: Vec<_> = store.get::<AuthorBooks>(some_author)
.unwrap()
.index
.iter()
.flat_map(|&entity| store.get::<Book>(entity))
.map(|book| book.title)
.collect();

unstable feature

As an experiment, the unstable feature can be enabled on nightly. This removes the default hook mechanism where hooks are registered with Store::hook_before_insert and Store::hook_after_remove, and instead enables a Hook trait which can be implemented directly on any type. This has several advantages: first, it's more efficient, since there's no longer any hook checks on types that don't have a specific implementation of Hook. Second, it's a better guarantee that invariants are enforced, since it's no longer possible to forget to register a hook.

This feature depends on the min_specialization unstable Rust feature, which makes it possible to give a default (empty) implementation of Hook for all types, and still provide a specialized implementation when needed.