Building a Triple Store in 1,095 Lines of Elixir

VAOS agents need to store and query knowledge graphs. Subject-predicate-object triples. The kind of thing RDF was designed for 25 years ago. The existing tools for this -- Apache Jena, Blazegraph, Oxigraph -- are good. They are also JVM-based (or Rust-based with NIF overhead), heavy to deploy, and impossible to embed inside an Elixir supervision tree.

So I built one. vaos-knowledge is an ETS-backed triple store with a SPARQL subset parser and OWL 2 RL forward-chaining reasoner. It runs as a GenServer inside the BEAM VM. The entire thing is 11 modules, 1,095 lines of code, 108 tests, and 1 dependency (jason).

This post is a walkthrough of what I built, how it works, and where it falls short.

The Problem

VAOS is an agent orchestration system. Agents accumulate knowledge during execution -- facts about their environment, relationships between entities, inferred properties. This knowledge needs to be queryable. Triple stores are the standard data model for this: {subject, predicate, object} triples that form a directed graph.

The requirements were:

1. Embeddable in an Elixir supervision tree (crash isolation, restarts, the usual OTP guarantees)
2. Fast pattern matching on any combination of subject, predicate, object
3. Basic SPARQL queries (agents generate SPARQL, not custom DSLs)
4. Some reasoning capability (at minimum, subclass and subproperty transitivity)
5. Persistence that survives process restarts

Existing options failed requirement 1. Running Jena as a sidecar and talking to it over HTTP adds latency, deployment complexity, and a failure mode that OTP cannot supervise. I needed something that lives inside the BEAM.

Architecture

The supervision tree looks like this:

Application
  -> Registry
  -> DynamicSupervisor
       -> Store GenServer (one per named store)
            -> Backend.ETS
            -> Parser
            -> Executor
            -> Reasoner

Each named store is a GenServer under a DynamicSupervisor. You can spin up as many stores as you need. They are independent -- one corrupted store does not take down the others.

# Open two isolated stores
{:ok, _pid} = VaosKnowledge.open("agent-memory")
{:ok, _pid} = VaosKnowledge.open("domain-ontology")

The Store GenServer owns an ETS backend and delegates parsing, execution, and reasoning to stateless modules.

ETS 3-Way Indexing

This is the core design decision and the thing that makes the store fast.

Each store creates 3 ETS tables with different key orderings of the same triples:

That is all 8 possible query patterns (2^3 combinations of bound/unbound positions). Any pattern can be answered by scanning exactly one index using :ets.match/2 or :ets.lookup/2.

# Internal representation: raw tuples, not structs
# Saves ~40 bytes per triple vs. a %Triple{} struct
triple = {"ex:alice", "ex:knows", "ex:bob"}

# Insert into all three tables
:ets.insert(spo_table, {{"ex:alice", "ex:knows", "ex:bob"}})
:ets.insert(pos_table, {{"ex:knows", "ex:bob", "ex:alice"}})
:ets.insert(osp_table, {{"ex:bob", "ex:alice", "ex:knows"}})

The tradeoff is 3x storage. Every triple is stored three times. For an in-memory store where agent knowledge bases are typically under 10,000 triples, this is a non-issue. A triple with typical IRI lengths costs roughly 200-300 bytes across all three tables. 10,000 triples is under 3 MB.

SPARQL Subset

Agents generate SPARQL queries. Not all of SPARQL -- a subset that covers the common patterns.

Supported:

• SELECT with basic graph patterns (triple patterns with variables)
• INSERT DATA (assert triples)
• DELETE DATA (retract triples)
• ORDER BY (single variable, ASC/DESC)
• LIMIT

Not supported:

• OPTIONAL
• FILTER
• UNION
• Aggregation (COUNT, GROUP BY, etc.)
• Named graphs
• Subqueries
• Property paths

{:ok, results} = VaosKnowledge.query("agent-memory", """
  SELECT ?person ?skill
  WHERE {
    ?person <ex:hasSkill> ?skill .
    ?person <rdf:type> <ex:Developer> .
  }
  ORDER BY ?person
  LIMIT 10
""")

# results => [%{"person" => "ex:alice", "skill" => "ex:elixir"}, ...]

The parser is regex-based. Not a proper grammar, not a PEG, not a parser combinator. Just Regex.scan/3 and String.split/3. This was a deliberate scope choice. A proper SPARQL parser is a significant undertaking -- the SPARQL 1.1 grammar has over 170 production rules. The regex approach handles the patterns that agents actually generate, which in practice covers about 90% of what I need.

Where it breaks: nested queries, unusual whitespace in IRIs, literals with embedded quotes. If you feed it adversarial SPARQL, it will produce garbage or crash. For agent-generated queries against a controlled vocabulary, it works.

# Asserting triples via SPARQL
:ok = VaosKnowledge.query("agent-memory", """
  INSERT DATA {
    <ex:alice> <rdf:type> <ex:Developer> .
    <ex:alice> <ex:hasSkill> <ex:elixir> .
    <ex:alice> <ex:worksAt> <ex:acme> .
  }
""")

OWL 2 RL Reasoning

The OWL 2 RL profile defines roughly 80 entailment rules. I implemented 4 of them:

1. rdfs:subClassOf transitivity -- If A subClassOf B and B subClassOf C, then A subClassOf C.
2. rdfs:subPropertyOf transitivity -- Same logic for properties.
3. owl:sameAs symmetry -- If A sameAs B, then B sameAs A.
4. rdfs:domain inference -- If property P has domain C, and X P Y, then X rdf:type C.

The reasoner uses forward-chaining materialization. It scans the store, applies rules to generate new triples, inserts them, and repeats until no new triples are produced (fixed point).

# Define an ontology
:ok = VaosKnowledge.query("domain-ontology", """
  INSERT DATA {
    <ex:SeniorDev> <rdfs:subClassOf> <ex:Developer> .
    <ex:Developer> <rdfs:subClassOf> <ex:Employee> .
    <ex:alice> <rdf:type> <ex:SeniorDev> .
  }
""")

# Materialize inferences
{:ok, new_triple_count} = VaosKnowledge.materialize("domain-ontology")
# new_triple_count => 3
# Inferred:
#   <ex:SeniorDev> <rdfs:subClassOf> <ex:Employee>   (transitivity)
#   <ex:alice> <rdf:type> <ex:Developer>               (class membership)
#   <ex:alice> <rdf:type> <ex:Employee>                 (class membership)

Complexity is O(n^2) in the worst case -- each iteration scans all triples and checks against all relevant schema triples. For agent knowledge bases under 10,000 triples, materialization completes in milliseconds. This would not scale to millions of triples. A production reasoner would need rule indexing, incremental materialization, and probably Rete-based evaluation. That is a different project.

The reasoner also does not detect cycles. If your ontology has A subClassOf B and B subClassOf A, it will loop until the fixed point (which it does reach, since the inferred triples are duplicates and no "new" triples are generated). But pathological cases with owl:sameAs chains could cause issues.

Persistence

Each store optionally writes to a JSONL journal. Append-only, one JSON object per line:

{"op":"assert","s":"ex:alice","p":"rdf:type","o":"ex:Developer","ts":1711324800}
{"op":"assert","s":"ex:alice","p":"ex:hasSkill","o":"ex:elixir","ts":1711324801}
{"op":"retract","s":"ex:alice","p":"ex:worksAt","o":"ex:acme","ts":1711324900}

Recovery is replay: read the journal line by line, apply each operation. The journal is human-readable, greppable, and trivial to debug.

The tradeoff: writes are synchronous. Every assert or retract calls File.write/3 with the :append flag before returning. This limits write throughput to roughly 5,000 triples/sec on my machine (M2 MacBook, APFS). Async writes with a buffer would push that to 50,000+, but introduce a window where data can be lost on crash. For agent workloads -- which are bursty but low-volume -- synchronous writes are the right call.

Backend Behaviour

The ETS backend implements a behaviour:

defmodule VaosKnowledge.Backend.Behaviour do
  @callback init(opts :: keyword()) :: {:ok, state :: term()}
  @callback assert(state, subject, predicate, object) :: {:ok, state}
  @callback retract(state, subject, predicate, object) :: {:ok, state}
  @callback match(state, subject, predicate, object) :: {:ok, [triple]}
  @callback all(state) :: {:ok, [triple]}
end

Backend.ETS is the default and only implementation today. But the behaviour means you could plug in Mnesia (for distribution), DETS (for disk-backed storage without journals), or a custom NIF-backed store without changing the Store GenServer.

Known Limitations

Writing them down so nobody has to discover them the hard way:

• Regex parser will break on nested queries, literals with special characters, or non-standard whitespace. It is not a SPARQL parser. It is a pattern matcher that handles a useful subset.
• No blank nodes. Every node must be a named IRI or a literal. Blank nodes add complexity to pattern matching and reasoning that was not worth the cost for this use case.
• No named graphs. All triples live in one default graph per store. If you need graph-level isolation, open a separate store.
• Synchronous journal writes. Throughput ceiling of ~5,000 triples/sec. Async would 10x this but risks data loss.
• Reasoner does not detect cycles. Works in practice because duplicate triples are idempotent, but owl:sameAs chains could cause unnecessary iterations.
• 4 out of ~80 OWL 2 RL rules. Enough for class/property hierarchies. Not enough for a general-purpose OWL reasoner.

Testing

$ mix test
..........................................................................
..................................
108 tests, 0 failures

Tests cover the parser, executor, reasoner, backend, and integration paths. The test suite runs in under 2 seconds because everything is in-memory.

Numbers

Was It Worth Building?

For this use case, yes. The alternative was running a JVM triple store as a sidecar, which would have added operational complexity, network latency, and a supervision boundary that OTP cannot cross. The embedded approach gives me crash isolation per store, zero-copy reads from ETS, and the ability to materialize inferences in the same process that runs the agent.

The thing I would do differently: use a proper parser. The regex approach was fast to build and covers current needs, but it is technical debt. When an agent generates a query with a FILTER clause and the parser silently ignores it, that is a bug that will be hard to track down. A parser combinator library like nimble_parsec would have been the right investment.

The full source is part of the VAOS project. If you build something similar or find bugs, I want to hear about it.

References:

• W3C RDF 1.1 Concepts and Abstract Syntax
• W3C SPARQL 1.1 Query Language
• W3C OWL 2 Web Ontology Language Profiles -- RL
• Erlang ETS Documentation