Transitive closure benchmark
Recursive queries, timed and checked on eight systems.
trans-bench runs one transitive-closure query on SQL, NoSQL and NewSQL databases and on the logic system XSB, over fourteen kinds of graph. Every result is compared with a closure computed independently, so a fast answer that is wrong is reported as wrong.
How it works
How a closure grows
A semi-naive evaluation joins only the pairs found in the last iteration with the edges, and it stops at the first iteration that adds nothing: the fixed point. Scroll to step through it.
Workloads
Fourteen kinds of graph
Each topology tests recursion in its own way. A path needs as many iterations as it has edges, while a complete graph is finished after one, although its closure has n² pairs. Point at a tile to see the pairs its closure adds.
Results
The race at n = 1,000
Mean query time over five runs, left recursion. The clock runs on a log scale, so the 600 second limit passes in a few seconds. A system that failed is shown with the reason.
Campaign verified_2026_v2. Neo4j and MongoDB have one formulation of the query, recorded as left recursion.
Verification
Every answer is checked
A run counts only if its result has the same number of pairs and the same 64-bit hash as the closure computed in Python. Wrong results are kept and marked, because a database that returns an incomplete closure without an error is a finding in itself.
Harness
The same engine for the site and the command line
A campaign started from this site, from transitive.py or from benchmark.py goes through engine/campaign.py. Each run is a separate process with a time limit, and its record is appended to runs.jsonl.