A Store That Doesn't Keep Time

Every storage engine that lives long enough gets the same request, and it always sounds reasonable. Can the store understand my data a little. Can it know that this field is a timestamp, that these two records are versions of one thing, that this edge stopped being true last March. Each one is small, and each one granted turns the substrate a little more into a database, until it is a specific database that serves only the caller who asked for it.

skeg answers no to all of them. The clearest way to see why the no is the feature is the hardest version of the request: a caller keeping a temporal knowledge graph, where the edges are not merely present or absent but true over intervals, believed over other intervals, and queryable as they stood at any past instant. That is close to the most a caller can ask a storage layer to understand, and what it needs turns out to be four primitives, none of which requires the store to know what a timestamp is.

Most of the difficulty is in the modelling, not the storage, so start there.

Time in a knowledge graph ¶

A plain knowledge graph is a set of statements, each a triple of subject, predicate, object: alice worksAt acme. It asserts the edge as an eternal present. The moment you care that Alice left Acme in March and joined Globex in April, the eternal present breaks, and you have to say when. The literature has been precise about this since the 1990s, and the precision matters because there is not one clock but two [1][2].

Valid time is when a fact is true in the world. alice worksAt acme has a valid interval, say January to March; after March it is simply false, regardless of what anyone recorded. Transaction time is when the system believed it. If you only learned in June that she had left in March, the fact was valid until March but believed until June, and both are true statements about the same edge. A graph that tracks only valid time cannot answer “what did we think last May.” A graph that tracks both is bitemporal, and bitemporality is what lets you reconstruct not just the past but your past beliefs about it, which is the difference between a record and an audit.

Attaching those intervals to a graph edge is its own problem, and the field has tried several shapes. You can reify the statement, turning the edge into a node that other edges annotate with start and end. You can push it into named graphs or quads, tagging each triple with a fourth element that carries the interval [3]. More recent work labels the edge directly, the approach RDF-star formalises, so a statement can be the subject of another statement without exploding into reification [4]. The temporal-RDF line of work worked out the semantics of exactly this: what it means for a graph to entail another when both are stamped with time [5]. Whichever shape you pick, the edge stops being a triple and becomes a triple plus one or two intervals.

Once edges carry intervals, relations between edges become interval relations, and those have their own algebra. Allen enumerated the thirteen ways two intervals can relate, before, meets, overlaps, during, and the rest, and any query that reasons about “was Alice at Acme while the merger was happening” is evaluating an Allen relation whether it names it or not [6]. The storage layer never sees this. It is pure caller-side logic over intervals the caller decoded from bytes.

And the queries change character. A non-temporal graph answers “who does Alice work for.” A temporal one answers as-of queries, the graph as it stood at a valid instant, and as-at queries, the graph as the system believed it at a transaction instant, and the bitemporal cross of the two [7]. A temporal path query is worse still: a path is only valid if every edge on it was co-temporally true, so traversal has to prune edges whose intervals do not overlap the query instant, at every hop. All of this is arithmetic on interval endpoints. None of it is storage.

The last piece is what happens to old facts. In a temporal graph you do not delete; you close. When Alice leaves Acme, the worksAt acme edge is not removed, its valid interval is ended and a new worksAt globex edge is opened. A retraction, learning you were wrong, does not erase either, it ends the belief interval and records the correction. History only ever grows. That single discipline, no deletes only closes, is what makes the audit trail trustworthy, and it is also what makes the storage problem interesting, because the store accumulates forever and someone has to reclaim the dead bytes without the store deciding on its own that a fact has expired.

That is a lot for a storage layer to carry: two clocks, intervals on every edge, an algebra of interval relations, as-of and as-at queries, co-temporal path pruning, monotone history. It does not have to carry any of it, and the reason is worth writing out.

The bitemporal predicate ¶

Start from the notation the temporal-RDF work uses. A temporal triple is a statement tagged with a time it holds at, written $(a,\,p,\,b) : [t]$, and a temporal graph $G$ is a set of them; the snapshot at an instant $t$ is the ordinary graph $G(t) = \{\,(a,p,b) : (a,p,b):[t] \in G\,\}$, and an interval label $[t_1, t_2]$ abbreviates the point labels it covers [5]. That fixes one clock. The bitemporal model adds the second: a fact carries not a point but a bitemporal element, a region of the two-dimensional space whose axes are valid time and transaction time [1][2]. For one assertion that region is a rectangle, and the fact is visible from the query point $(w, s)$ exactly when the point lies in it:

$$\operatorname{visible}(f;\,w,s)\;\iff\;(w,s)\in[a,b)\times[c,d)\;\iff\; a \le w < b \;\wedge\; c \le s < d .$$

An as-of query is the valid-timeslice operator $\tau^{v}_{w}$ with $w$ held fixed, an as-at query is the transaction-timeslice $\tau^{t}_{s}$, and the general query is a point whose answer is the set of rectangles it stabs [2].

Relations between facts are then relations between intervals, and those are Allen’s [6]. For $X = [X^-, X^+)$ and $Y = [Y^-, Y^+)$ his thirteen cases are fixed entirely by the ordering of the four endpoints: $X$ before $Y$ is $X^+ < Y^-$, $X$ overlaps $Y$ is $X^- < Y^- < X^+ < Y^+$, $X$ during $Y$ is $Y^- < X^- \wedge X^+ < Y^+$, and so through the rest. A query like “was Alice at Acme while the merger ran” evaluates one of these whether it names it or not, and the one a traversal needs constantly is non-empty intersection, the disjunction of the relations that share a point:

$$X \cap Y \neq \varnothing \;\iff\; X^- < Y^+ \;\wedge\; Y^- < X^+ .$$

None of that is storage yet. Watch where each piece lands.

The transaction axis needs no stored column. Here $c$ is the sequence at which the system asserted the fact and $d$ the sequence at which it retracted or superseded it, and a retraction is itself a durable write, not an edit of $f$. If the store hands out a monotone write sequence $\sigma$, then $c = \sigma_{\text{assert}}$ and $d = \sigma_{\text{retract}}$ (with $d = \infty$ while the fact is still believed), and

$$c \le s < d \;\iff\; \text{asserted by } s \text{ and not yet retracted by } s,$$

answered by reading the graph as of sequence $s$. The transaction-timeslice is the write counter, read at $s$. The store keeps zero bytes of transaction time; it keeps a u64 that only ever goes up.

The valid axis is an interval-stabbing query. The predicate $a \le w < b$ asks for every interval containing the point $w$. In full generality that is what an interval tree answers in $O(\log n + k)$ [12], a structure the store does not build. It offers instead a one-dimensional range over a single opaque u64 per edge. Put $a$, the valid-from, in that column and the filter answers the half of the stab that is a range, $a \le w$; the other endpoint, $w < b$, is one comparison per survivor, run caller-side. The prune is exact but loose: the survivors of $a \le w$ include every edge already closed by $w$, a fraction

$$\varphi(w) \;=\; \frac{\bigl|\{\,f : a \le w \,\wedge\, b \le w\,\}\bigr|}{\bigl|\{\,f : a \le w\,\}\bigr|}$$

that grows as history deepens, and the caller pays it back with the $w < b$ test. The store could tighten it only by carrying $b$ as well and reading the pair as an interval, which is the one thing it will not do.

Path validity is interval intersection. A path $e_1 \ldots e_k$ is usable at $w$ only if its edges are pairwise co-temporal, which by the intersection test above means $w$ lies in every edge’s interval at once, so the path’s valid window is

$$\bigcap_i [a_i, b_i) \;=\; \Bigl[\,\max_i a_i,\ \min_i b_i\,\Bigr), \qquad \text{non-empty} \iff \max_i a_i < \min_i b_i .$$

A temporal traversal carries the running window $[A, B) = [\max a,\ \min b)$ as it extends the path and prunes the branch the instant $A \ge B$. It is arithmetic on endpoints the caller decoded from bytes; the store hands back neighbours as opaque records and never sees the window.

So the bitemporal element of the papers factors, at the storage line, into a counter the store already keeps (the $s$ axis) and a one-dimensional range over one opaque column (the $a \le w$ half of the $w$ axis). The timeslice operators, the endpoint algebra, and the stabbing structure all sit above it as caller code. The store’s whole share is a monotone integer and a numeric range, and everything carrying a unit of time stays above the line.

The line ¶

skeg stores opaque bytes and searches vectors. A value is a run of bytes it will hand back exactly as given; it is never parsed, never compared as anything but bytes, never indexed on a field the engine found inside it. The vector side knows one thing about a value, its position in embedding space, and nothing else. Time, identity, intervals, supersession, none of these exist from the store’s point of view. They are the caller’s, and the caller keeps them in the bytes.

That sounds like a limitation until you ask what it buys. A store that does not read the value can hold any semantics a caller encodes, valid-time intervals today and something nobody has designed yet tomorrow, and can keep the memory envelope that comes from never materialising an interpretation of the data. The engine that starts parsing timestamps has a schema; the engine with a schema has migrations; the engine with a temporal schema is a temporal database, and it has given up being a substrate. The whole point of the layer is that the meaning lives above it, where it can change without a rebuild.

So the interesting question is not whether the store should understand the temporal graph. It should not. The question is what such a caller cannot build for itself and has to be given from below. There are four things.

What the caller needs from storage ¶

Each is a storage guarantee, not a semantic one.

An atomic multi-key write. A single change to a temporal graph is never one record. Closing worksAt acme and opening worksAt globex is two edge writes plus whatever adjacency and reverse indexes the caller maintains, and they have to become visible together or not at all. A crash in the middle leaves a graph that believes Alice works nowhere, or works in two places, with an index pointing at an edge that is not there. The old way to get atomicity from a key-value store is a write-ahead intent log in the caller, replayed on open, which is a small database bolted onto the side of the real one.

skeg gives it directly. A group of records is written behind a single header that names the count, committed in one durable append, and recovery accepts the group whole or discards a torn one whole [8]. The store guarantees that $N$ opaque records land together. It does not know that two of them are edges being swapped and the rest are indexes, or that any of them carry an interval. The atomicity is over bytes; the meaning of the bytes is the caller’s, and stays that way.

A monotone write sequence. The transaction axis, above, is a counter the store already keeps, so the store has only to expose it: every durable write advances an internal u64, and skeg hands it back. A caller could maintain its own, but then it is keeping a clock in sync with the store’s durability, and the two can disagree across a crash; reading the store’s own is one number and no drift.

Besides pinning the as-at view $\sigma_{\text{assert}} \le s < \sigma_{\text{retract}}$, the counter makes a session cache cheap to invalidate: if the sequence has not moved, nothing the cache holds can be stale; if it has, refetch. The store just increments the integer. It does not know the caller reads it as when we learned this, any more than it knows the caller could read it as a Lamport clock or a git-like generation.

Enumeration and reclaim. A temporal graph is append-mostly by construction: no deletes, only closes, so history grows without bound. The caller needs two value-blind operations against that growth. Walk the keys, to rebuild a projection, run a compaction, or sweep one subject’s edges for an erasure request. And physically reclaim the bytes of records that are genuinely dead, a subject fully erased, a botched write superseded, not the merely-historical edges that are the whole point of keeping the graph. Reclaim is the only place bytes actually leave, and it is driven by the caller’s judgement of what is dead, expressed as keys, never by the store deciding an interval has closed. A store that expired closed edges on its own would have to understand their time. This one enumerates and removes on command, and understands nothing.

A range filter over an opaque column. This is the $a \le w$ half of the stab made concrete. skeg carries an optional u64 per vector and restricts a vector search to a range over it, routed so the cost follows the query’s neighbourhood rather than the size of the matching set [9]. The engine treats that column as an opaque integer; the caller puts the valid-from in it and runs the $w < b$ remainder on the survivors. Nothing marks the column as time, so the same filter serves an importance score or a tenant id through the identical path. The mechanism and its limits are their own post [10]; here it is enough that the temporal query reduces to a value-agnostic numeric filter, so the store provides the filter and none of the time.

Four primitives, and the whole apparatus above them is caller code: the two clocks, the interval algebra, the co-temporal path pruning, and past those even the learned tasks, the temporal-graph completion and embedding models that predict the edges yet to be asserted [11]. The store did not learn what a knowledge graph is, let alone a temporal one.

The one thing it refuses ¶

What skeg will not add is the obvious next step: parse the interval out of the value, keep native valid-from and valid-to columns, evaluate as of inside the engine. I considered it and turned it down, and the reason is the whole argument. The moment the store reads a field as an interval it has a temporal schema, and it can now only hold callers whose model of time matches the one it chose, in the encoding it chose, on the axes it chose. A caller whose second axis is not transaction time but decision time or a version vector no longer fits. A caller who wants the interval algebra to run over something other than instants no longer fits. And the value that was a run of bytes the store could keep on disk and page in on demand becomes a structure the store must understand resident, which is how a RAM-frugal substrate turns into an ordinary database with an ordinary appetite.

The refusal is not laziness. Native bitemporality is more engine than the four primitives and buys a narrower store. When the primitives are more general than the feature they would enable, the line is in the right place.

Why the discipline pays ¶

A temporal knowledge graph is about as much semantics as a caller can pile onto a store, and it decomposes into storage guarantees that carry no time. Atomic groups of bytes, a monotone counter, key-level enumeration and reclaim, a range over an opaque number. Give a caller those and it can keep a bitemporal graph, correct across crashes, queryable as of any instant and as at any belief, on a store that was never told what a timestamp is. Give it native time instead and you have built more engine to serve fewer callers.

A substrate stays useful by staying value-agnostic under the same reasonable request to understand the data a little. The four primitives are how it says no without becoming useless: it holds the line at the bytes, and the caller builds its two clocks and its interval algebra on top, out of mechanism the store provides and meaning the store never sees.

---

References ¶

[1] Snodgrass, Richard T. Developing Time-Oriented Database Applications in SQL. Morgan Kaufmann, 2000. The standard treatment of valid time and transaction time, and the bitemporal model that combines them.

[2] Jensen, Christian S.; Snodgrass, Richard T. “Temporal Data Management.” IEEE Transactions on Knowledge and Data Engineering, vol. 11, no. 1, 1999. Survey of the two time axes and the consensus terminology the field settled on.

[3] Carroll, Jeremy J.; Bizer, Christian; Hayes, Patrick; Stickler, Patrick. “Named Graphs, Provenance and Trust.” WWW 2005. Quads as the mechanism for annotating triples, the substrate temporal RDF builds on.

[4] Hartig, Olaf. “Foundations of RDF-star and SPARQL-star.” AMW 2017, and the W3C RDF-star Working Group. Labelling a statement as the subject of another statement without full reification.

[5] Gutierrez, Claudio; Hurtado, Carlos A.; Vaisman, Alejandro. “Introducing Time into RDF.” IEEE Transactions on Knowledge and Data Engineering, vol. 19, no. 2, 2007. The semantics of temporal RDF: entailment and consistency over time-stamped graphs.

[6] Allen, James F. “Maintaining Knowledge about Temporal Intervals.” Communications of the ACM, vol. 26, no. 11, 1983. The thirteen interval relations any temporal graph query implicitly evaluates.

[7] Kulkarni, Krishna; Michels, Jan-Eike. “Temporal Features in SQL

.” ACM SIGMOD Record, vol. 41, no. 3, 2012. How the SQL standard exposes as-of and as-at over valid-time and transaction-time periods.

[8] Gray, Jim; Reuter, Andreas. Transaction Processing: Concepts and Techniques. Morgan Kaufmann, 1992. Group commit and durability, the mechanism an atomic multi-key write rests on.

[9] O’Neil, Patrick; Cheng, Edward; Gawlick, Dieter; O’Neil, Elizabeth. “The Log-Structured Merge-Tree (LSM-Tree).” Acta Informatica, vol. 33, no. 4, 1996. The append-mostly log the primitives are built on, where history accumulates and reclaim is a separate pass.

[10] “The Zone-Map That Didn’t Skip.” This series, 2026, /posts/2026-07-18-the-zone-map-that-didnt-skip. The value-agnostic numeric range filter a caller can use as an as-of window, and what it does and does not buy.

[11] García-Durán, Alberto; Dumančić, Sebastijan; Niepert, Mathias. “Learning Sequence Encoders for Temporal Knowledge Graph Completion.” EMNLP 2018. Evidence that time-stamped edges are a first-class modelling concern above the store, not a storage feature.

[12] de Berg, Mark; Cheong, Otfried; van Kreveld, Marc; Overmars, Mark. Computational Geometry: Algorithms and Applications, 3rd ed. Springer, 2008. Interval trees and the stabbing query, the $O(\log n + k)$ structure a full valid-time index would need and the store deliberately does not build.