OntoDB: A Fast and Persistent Query Engine for Ontologies

Read the PDF Extended version Code Manual Playground

Highlights

• On LUBM and the Gene Ontology, OntoDB answers selective triple patterns 3 to 37 times faster than Oxigraph, Jena TDB2 and SQLite, and the instances of a class 2 to 48 times faster.
• With eight threads OntoDB serves 1.46 million lookups per second, 3 to 7 times the other engines and 3.5 times its own single-thread rate. A latch-free buffer-pool hit, an optimistic leaf-only descent for writers and a one-word page latch took the first version, which slowed down with threads, to this.
• Interval labels keep the class hierarchy in the engine's own B+ tree: 8.1 times fewer triples than materializing the closure, 48 times fewer page reads than rewriting the query.
• A plan rewrite answers RDFS subclass entailment of type patterns with those interval scans: the answers of a materialized store, prepared 16 times faster and in 8 times less space, and 1.9 to 6.9 times faster than Oxigraph's subclass-path queries on LUBM(10).
• Exact pre-filtering through the intervals is 100 to 10,000 times faster than any index strategy for classes below about 1,000 members; in an ontology a class filter is correlated with the vectors, so post-filtered IVF can find only 7% of the right answers.
• The whole engine, with its paged B+ trees and semantic search, runs in a browser from a 0.85 MB WebAssembly module.

Abstract

Ontologies are queried in three ways: for the triples that match a pattern, for the instances at or below a class, and for the terms closest in meaning to a given term. Triple stores answer the first well, handle the second by rewriting queries or by materializing entailed triples, and leave the third to a separate vector database; none is built to serve many threads from one embedded engine, or to run in a web page. We present OntoDB, an ontology database that answers all three kinds of query inside one disk-based, multi-threaded engine. Through OntoDB we make the following contributions. (1) A B+ tree triple store of three permutations behind a buffer pool, with algorithms for search, insert, delete, range scan, and bulk load, a bound on the pages a range scan reads, and write-ahead logging with ARIES-style recovery for persistence. (2) A concurrency design that scales: an optimistic leaf-only descent for inserts and deletes, a sharded buffer pool whose hits take no latch, and a one-word page latch. (3) A labelling of the class hierarchy with postorder intervals kept in the same B+ tree, so that ``everything under a class'' is a few range scans and no entailed triple is stored, and a plan rewrite that answers RDFS subclass entailment of exttt{rdf:type} patterns with these scans, with the answers of materialization, prepared 16 times faster and in 8 times less space. (4) Exact, IVF, product-quantized, and HNSW vector indexes in the engine, a proof that no linear order of points keeps neighbors close, and the finding that in an ontology a class filter is correlated with the vectors, so the usual independence assumption fails. (5) A 0.85 MB WebAssembly build that runs the engine in a browser. On LUBM and the Gene Ontology, against Oxigraph, Apache Jena TDB2, and SQLite, OntoDB answers selective triple patterns 3 to 37x faster and the instances of a class 2 to 48x faster, and serves 3 to 7x more lookups per second with eight threads (1.46 million per second). Its interval labels store 8.1x fewer triples than materializing the hierarchy and read 48x fewer pages than rewriting the query, and exact pre-filtering through them is 100 to 10^4 imes faster than any index strategy for classes below about 1,000 members.

Read

On a phone, open the PDF in your browser's reader.

Cite

@misc{nguyen2026ontodb,
  title  = {{OntoDB}: A Fast Ontology Database for Pattern, Hierarchy, and Semantic Queries},
  author = {Lam Nguyen},
  year   = {2026},
  note   = {Preprint},
  url    = {https://github.com/lamng3/OntoDB}
}