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.

Bottom-up evaluation starts from the extensional database (EDB) — the base facts supplied to init() — and repeatedly applies rules until no new facts can be derived (fixpoint / saturation). AbcDatalog provides four bottom-up engines: one sequential and three concurrent. All implement the DatalogEngine interface, so the calling code is identical regardless of which engine you choose.

​
How semi-naive evaluation works

Naive bottom-up evaluation joins every rule against the complete set of known facts on each iteration. The semi-naive optimization keeps track of which facts were derived in the most recent iteration (the “delta”) and restricts each join so that at least one body atom matches a new fact. This avoids repeating joins that cannot produce new results, dramatically reducing redundant work for recursive programs.

​
SemiNaiveEngine (sequential)

SemiNaiveEngine is the classic sequential semi-naive engine. It is the most feature-complete engine in AbcDatalog: it supports stratified negation and binary unification/disunification in rule bodies. Factory methods:
  • SemiNaiveEngine.newEngine() — returns a DatalogEngine.
  • SemiNaiveEngine.newEngineWithProvenance() — returns a DatalogEngineWithProvenance that records which rule instance justified each derived fact.
Example (adapted from EngineExample.java): 
// Build a transitive closure program from a string
String[] lines = {
  "edge(a, b).",
  "edge(b, c).",
  "edge(c, d).",
  "edge(d, c).",
  "tc(X, Y) :- edge(X, Y).",
  "tc(X, Y) :- tc(X, Z), tc(Z, Y)."
};
StringBuilder sb = new StringBuilder();
for (String line : lines) {
  sb.append(line);
}
Reader r = new StringReader(sb.toString());
DatalogTokenizer t = new DatalogTokenizer(r);
Set<Clause> prog = DatalogParser.parseProgram(t);

DatalogEngine engine = SemiNaiveEngine.newEngine();
engine.init(prog);

// Query using parsed syntax
DatalogTokenizer qt = new DatalogTokenizer(new StringReader("tc(X, Y)?"));
PositiveAtom q = DatalogParser.parseQuery(qt);
Set<PositiveAtom> results = engine.query(q);
for (PositiveAtom result : results) {
  System.out.println(result);
}
The Datalog program above: 
edge(a, b).
edge(b, c).
edge(c, d).
edge(d, c).
tc(X, Y) :- edge(X, Y).
tc(X, Y) :- tc(X, Z), tc(Z, Y).

​
ConcurrentBottomUpEngine (parallel)

ConcurrentBottomUpEngine runs the same semi-naive saturation algorithm as SemiNaiveEngine but uses concurrent data structures and a thread pool to evaluate rules in parallel. Use it when you have a large program and want to take advantage of multiple CPU cores. Limitations: does not support negation. 
DatalogEngine engine = new ConcurrentBottomUpEngine();
engine.init(program);
Set<PositiveAtom> results = engine.query(query);

​
ConcurrentChunkedBottomUpEngine (parallel, chunked)

ConcurrentChunkedBottomUpEngine is a variant of the concurrent engine that groups newly derived facts into chunks of a configurable size before submitting them as work items to the thread pool. This reduces task-scheduling overhead when many facts are produced in each iteration and can improve throughput for large programs. Constructor: new ConcurrentChunkedBottomUpEngine(int chunkSize) — the chunkSize parameter controls how many facts are bundled per work item. Limitations: does not support negation. 
// Bundle 64 facts per work item
DatalogEngine engine = new ConcurrentChunkedBottomUpEngine(64);
engine.init(program);
Set<PositiveAtom> results = engine.query(query);

​
ConcurrentStratifiedNegationBottomUpEngine (parallel, with negation)

ConcurrentStratifiedNegationBottomUpEngine extends the concurrent approach to also handle stratified negation. It is described in the source as experimental. Choose it when you need both parallel execution and negation-as-failure in a stratifiable program. 
DatalogEngine engine = new ConcurrentStratifiedNegationBottomUpEngine();
engine.init(program);
Set<PositiveAtom> results = engine.query(query);

​
Swapping engines

Because all bottom-up engines implement DatalogEngine, switching between them requires changing only the instantiation line: 
// Sequential with negation support
DatalogEngine engine = SemiNaiveEngine.newEngine();

// Swap to concurrent — no other code changes needed
DatalogEngine engine = new ConcurrentBottomUpEngine();

// Or concurrent with negation
DatalogEngine engine = new ConcurrentStratifiedNegationBottomUpEngine();
All bottom-up engines implement the DatalogEngine interface. Code written against the interface works with any engine, making it straightforward to benchmark or switch strategies without modifying business logic.

Build docs developers (and LLMs) love

Get started for freeTalk to us