Skip to main content

Documentation Index

Fetch the complete documentation index at: https://mintlify.com/HarvardPL/AbcDatalog/llms.txt

Use this file to discover all available pages before exploring further.

AbcDatalog provides several evaluation engines, each implementing the DatalogEngine interface. They differ in their evaluation strategy (bottom-up saturation vs. top-down query-driven), concurrency model, and the Datalog features they support. Because every engine exposes the same init() / query() interface, you can swap engines with a single-line change.

​
Engine comparison

Engine classAlgorithmConcurrentSupports negationSupports unification
SemiNaiveEngineSemi-naive bottom-upNoYes (stratified)Yes
ConcurrentBottomUpEngineSemi-naive bottom-upYesNoYes
ConcurrentChunkedBottomUpEngineSemi-naive bottom-up (chunked)YesNoYes
ConcurrentStratifiedNegationBottomUpEngineSemi-naive bottom-upYesYes (stratified)Yes
IterativeQsqEngineTop-down QSQ iterativeNoNoNo

​
Decision guide

Use SemiNaiveEngine (sequential) or ConcurrentStratifiedNegationBottomUpEngine (parallel). Both handle stratified negation — rules where a negated body literal depends only on predicates in lower strata. If you also need provenance tracking, SemiNaiveEngine.newEngineWithProvenance() is the only option that currently supports it.
Choose one of the concurrent engines:
  • ConcurrentBottomUpEngine — straightforward parallel semi-naive; no negation support.
  • ConcurrentChunkedBottomUpEngine — batches newly derived facts into chunks before submitting work, which can improve throughput when the derived fact set is large.
  • ConcurrentStratifiedNegationBottomUpEngine — concurrent engine that also handles stratified negation.
Use IterativeQsqEngine. It uses the Query-Subquery (QSQ) algorithm, which starts from the query and works backwards through rules, deriving only what is needed to answer the specific query. This is advantageous when only a small fraction of all derivable facts is relevant. Note that it does not support negation or explicit unification/disunification.

​
Common usage pattern

All engines share the same lifecycle, so the code that interacts with a DatalogEngine is engine-agnostic. 
// 1. Create an engine — swap this line to change strategy
DatalogEngine engine = SemiNaiveEngine.newEngine();

// 2. Parse and initialize the program
DatalogTokenizer tokenizer = new DatalogTokenizer(reader);
Set<Clause> program = DatalogParser.parseProgram(tokenizer);
engine.init(program);

// 3. Query
DatalogTokenizer qt = new DatalogTokenizer(new StringReader("tc(X, Y)?"));
PositiveAtom query = DatalogParser.parseQuery(qt);
Set<PositiveAtom> results = engine.query(query);

​
Further reading

  • Bottom-up engines — semi-naive evaluation, sequential and concurrent variants
  • Top-down engine — QSQ algorithm and when to prefer it
  • Provenance — tracing fact derivations with DatalogEngineWithProvenance

Build docs developers (and LLMs) love

Get started for freeTalk to us