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.

Top-down evaluation works in the opposite direction from bottom-up: instead of saturating all derivable facts upfront, it starts from the query and works backwards through rules, generating only the subgoals needed to answer that specific query. AbcDatalog provides one top-down engine — IterativeQsqEngine — which implements the Query-Subquery (QSQ) algorithm.

​
The QSQ algorithm

QSQ is an adornment-based, demand-driven evaluation method. When a query such as tc(a, Y)? is posed, QSQ adorns the predicate with a binding pattern (here: tc^{bf}, meaning the first argument is bound and the second is free). The engine then generates adorned versions of the rules that define tc, restricting rule evaluation to tuples consistent with the known bindings. Intermediate results are propagated through a set of supplementary relations that carry binding information sideways across the body of each rule. This process continues iteratively until no new answers can be generated. The practical effect is that the engine may explore only a small portion of the full fixpoint, which is beneficial when a query has selective bound arguments and the complete derivation would be much larger than what the query actually needs.

​
IterativeQsqEngine

IterativeQsqEngine extends AbstractQsqEngine, which handles program initialization (separating EDB facts from IDB rules). IterativeQsqEngine provides the concrete query() implementation using the iterative QSQ loop. There is no static factory method; instantiate it directly with new IterativeQsqEngine(). 
// Parse the program
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);
}
DatalogTokenizer t = new DatalogTokenizer(new StringReader(sb.toString()));
Set<Clause> program = DatalogParser.parseProgram(t);

// Create and initialize the engine
DatalogEngine engine = new IterativeQsqEngine();
engine.init(program);

// Query: find all nodes reachable from 'a'
DatalogTokenizer qt = new DatalogTokenizer(new StringReader("tc(a, Y)?"));
PositiveAtom query = DatalogParser.parseQuery(qt);
Set<PositiveAtom> results = engine.query(query);
for (PositiveAtom result : results) {
  System.out.println(result);
}
The Datalog program: 
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).

​
When to prefer top-down evaluation

Top-down evaluation is most advantageous when:
  • The query has one or more bound arguments that significantly restrict the search space (e.g., tc(a, Y)? rather than tc(X, Y)?).
  • The program has large EDB relations but only a small subset of facts is relevant to the query.
  • You want to avoid the upfront cost of saturating the entire fixpoint.
If you need to answer many different queries over the same program, or if most of the fixpoint is needed for any single query, bottom-up engines are typically more efficient.
IterativeQsqEngine does not support negation (stratified or otherwise) or explicit unification/disunification in rule bodies. Programs using not, =, or != in rule bodies must use one of the bottom-up engines instead.

Build docs developers (and LLMs) love

Get started for freeTalk to us