A graph database for RDF, with a hybrid
reasoner built in for OWL 2 RL.

Load RDF, query it with SPARQL 1.1, and get back answers that include what the reasoner inferred — forward and backward chaining over OWL 2 RL semantics. Apache-2.0 license.

View on GitHub Get your first reasoned answer

What it is, and why we're building it

HornDB is a graph database: it stores RDF triples — subject, predicate, object — and answers SPARQL queries over them. It isn't a property-graph database like Neo4j; the graph model here is RDF's, the one behind the SPARQL standard and the wider semantic web. What sets it apart is the reasoner built in: load data, and HornDB derives new triples from it under OWL 2 RL semantics, with provenance back to the facts each inference came from. The name comes from Horn clauses, a reasoning primitive HornDB uses to implement OWL 2 RL.

The reasoner space today forces a choice. Pure-materialization commercial engines are fast but give up 100–1000× on backward chaining, and aren't open-source. Open-source toolkits are flexible but slower on the same workload. HornDB takes a different approach: materialize the cheap, regular subset; backward-chain the rest; and treat modern memory hierarchies as a design target from the start, not an afterthought. The full reasoning behind these choices is in the vision spec.

The bets

Six design decisions shape how HornDB works.

  • Hybrid execution

    Not pure materialization. Materialize the schema and transitive-closure subset; backward-chain the rest with magic sets.

  • Provenance as a requirement

    Every inferred triple traces back to its premises. Explainability is a hard constraint, not a feature flag.

  • Compiled rules

    Soufflé-style ahead-of-time compilation: OWL 2 RL rules become native Rust — no rule interpreter in the hot path.

  • Incremental maintenance

    DBSP-style Z-set differences instead of DRed counting, so updates touch only what actually changed.

  • GraphBLAS closure

    Schema-level transitive closure as a semiring matrix multiply on SuiteSparse:GraphBLAS.

  • Modern memory as a target

    A tiered working set — fast memory for the hot data, DRAM for warm, CXL/NVMe for cold — designed in, not bolted on.

What runs today

Every subsystem below has code in the repository today, exercised by tests and the conformance harness.

  • Tiered storage implemented

    Dictionary-encoded terms and predicate-partitioned columnar triples, with an N-Triples loader that already ingests RDF 1.2 triple terms.

  • Worst-case-optimal joins implemented

    Leapfrog Triejoin with cost-based fallback to a binary hash join. Clears its acceptance gate — ≥10× a binary-join baseline on the canonical four-cycle workload (~30–34× measured on a skewed 10⁶-edge graph).

  • Compiled OWL 2 RL rules implemented

    Entailment rules compiled ahead-of-time to native Rust — no interpreter in the hot path — evaluated semi-naïvely to a fixpoint. 100 of 115 selected W3C OWL 2 RL cases pass.

  • GraphBLAS closure implemented

    Schema-level transitive closure runs as a semiring matrix multiply on SuiteSparse:GraphBLAS, linked in natively.

  • Incremental maintenance implemented

    DBSP-style Z-set deltas update only what changed. Insertion is fully incremental, and retraction now lands across both the rule path and the closure path — insert 10K / retract 10K is bit-identical to a clean load.

  • SPARQL 1.1 frontend implemented

    Parser, algebra, planner and an axum HTTP endpoint: SELECT / ASK / CONSTRUCT / DESCRIBE, full aggregation, every property-path operator (including the recursive ones), pattern and graph-management Update, and an EXPLAIN pragma — driven end-to-end against the LDBC Semantic Publishing Benchmark.

  • Provenance & proof trees implemented

    Every inferred triple records the rule and premises that produced it; an explicit proof query walks the recursive tree down to the asserted facts at its leaves.

  • SSSOM crosswalks implemented

    Ontology mapping chains (SKOS / OWL / semapv) close through the compiled rule engine and the GraphBLAS backend, with confidence propagated along each chain.

  • Python / rdflib API implemented

    A PyO3 binding exposing rdflib-shaped terms, a Graph facade, Turtle / N-Triples parse and serialize, and SPARQL query / update passthrough — differential-tested against upstream rdflib.

  • SIMD acceleration implemented

    A shared, runtime-dispatched SIMD layer — AVX-512 / AVX2 on x86, NEON on Apple silicon, scalar fallback always present as the oracle — driving the WCOJ seek / intersect and dictionary-decode / rdf:type-scan hot loops. Every kernel is differential-proven bit-identical to scalar.

  • Observability implemented

    Prometheus metrics across the SPARQL HTTP layer, closure backend, rule engine, incremental maintenance and storage, exposed at a /metrics scrape endpoint. OpenTelemetry traces and logs deferred to a later phase.

What's next

HornDB is young and under active development. The harness comes first by design — every spec's acceptance criteria reference a concrete test subset, and a spec is not satisfied until its subset is green. Here's what we're building toward.

  • Cost-based join planning planned

    HornDB currently runs about 4× behind GraphDB Free on the LDBC Semantic Publishing Benchmark aggregation mix. Cost-based join ordering in the query planner is the next lever to close that gap.

  • Faster materialization planned

    The within-partition object index has shipped. Next: delta-driven semi-naïve rule firing, so rdf:type reasoning scales with what changed rather than the whole store.

  • Crosswalk serving planned

    A compact crosswalk index (~10 bytes per mapping pair) and spine over the SSSOM mapping reasoner, for serving large ontology-alignment sets.

  • Full-scale live benchmarking planned

    The nightly LDBC SPB-256 run already tracks closure and aggregation throughput against GraphDB Free and Oxigraph. Extending it to true full scale (256M triples) with live editorial insert / update / delete agents running throughout is still open.

  • Hardware specialization planned

    The long-term bet: GPU GraphBLAS and worst-case-optimal joins, CXL / HBM memory tiering, and multi-node — without lowering the conformance bar as the hardware grows.

  • Tracing & logs deferred

    OpenTelemetry traces and structured logs alongside the Prometheus metrics already exposed at /metrics.

Non-goals: OWL 2 DL completeness, property-graph compatibility, or embedding-based “neural” reasoning as the source of truth. The symbolic engine is always the source of truth.