Study notes

Overview

OntoDB is a database management system for ontologies. Data is RDF. The query language is SPARQL. These notes are the map of each feature, and of how a later comparison becomes a writeup.

A query is a pipeline. A committed insert is that same pipeline plus a log. The memory path already answers a SPARQL subset. The index, the optimizer, and recovery are specified and still to build.

The pieces

SPARQLThe language the shell accepts, and the errors it returns on purpose.Query engineBinder, left-deep plans, and volcano executors over term ids.OptimizerStatistics, cardinality, join order, and join method. This will exist.DictionaryIRIs, literals, and blanks interned to 64-bit ids.Triple indexesA 24-byte key and the SPO, POS, and OSP permutations.B+ treeThe index. Leaves hold keys. Parents hold separators.Buffer pool4 KiB pages, LRU-K, guards, and a pageLSN on every page.ConcurrencyStrict 2PL, intention locks, isolation, deadlocks, phantoms.WAL and ARIESSteal/no-force, group commit, analysis, redo, undo.Persistence and snapshotsPage files, in-place deletes, checkpoints, and what a scan freezes.Shell and checksHow to load a file, run a query, and check a feature.Benchmarks and writeupsOne engine, a result table per question, and the writeup that cites it.

Two paths

A read of data/tiny.ttl stays in memory:

The shell collects a query until braces and quotes balance.
The lexer and parser build an AST. a means rdf:type.
The binder resolves prefixes and interns constants.
The planner builds a left-deep tree of triple scans, nested-loop joins, a filter, and a projection.
Volcano Init / Next pulls rows of term ids from MemStore.
The shell prints spellings looked up in MemDictionary.

An insert, once the disk features exist, does not stop at the memory store:

The dictionary turns three spellings into ids. The bytes live in a term heap.
Those ids are packed into a 24-byte big-endian TripleKey.
The indexed store inserts that key into each permutation the catalog has a root for.
The B+ tree pins pages through guards. Frames live in the buffer pool. Eviction is LRU-K.
Before a dirty page is written, the log is flushed through that page's pageLSN. That is the WAL rule.
Commit forces a commit record. On the next open, ARIES runs analysis, redo, and undo.

What already runs

Turtle, N-Triples, and RDF/XML through raptor2. OWL is stored as RDF. There is no reasoner.
PREFIX, SELECT (variables or *), basic graph patterns with a, ;, and ,, and FILTER with = != < > <= >= and &&.
DISTINCT, LIMIT, OFFSET, and ORDER BY are parsed and placed in the plan. Their executors are not built yet, so executing them throws.
INSERT DATA and DELETE DATA.
\explain prints the plan and does not execute. \explain analyze is plan 5.5.

OPTIONAL, UNION, property paths, aggregates, and DELETE/INSERT WHERE fail with a line and a column. That is a finished error, not a crash.

What this site is for

Read a feature before you build it. Each page says what the piece is, how OntoDB uses it, what works today, and the slice that comes next. Benchmarks and writeups is how a finished comparison is recorded. The code repository stays separate. PLAN.md there is the feature list.