Evaluation order and nontermination in query languages
The article discusses how evaluation order in Datalog and similar query languages affects nontermination and recursion handling, contrasting bottom-up and top-down evaluation strategies and their implications for program behavior and expressiveness.
Background
- Datalog is a logic-based query language (a subset of Prolog) used for database and AI reasoning. Unlike SQL, it's purely declarative — you state facts and rules, but not *how* to compute them. This makes it both powerful and tricky.
- The article explores a subtle failure mode of Datalog: non-termination (infinite loops) caused by how the query engine *evaluates* rules, not by the logic itself. This contrasts with SQL, where evaluation order is explicit and predictable.
- The author is Michael Arntzenius, a researcher in programming languages and declarative systems (known for work on the "Datafun" language). They're writing for an audience of PL/DB researchers.
- Key context: Datalog engines traditionally evaluate rules in a fixed order (left-to-right, top-down). Changing that order — or using "stratified negation" — can break or slow down queries. This post highlights a known but under-documented class of bugs where correct Datalog programs hang due to engine choice, not user error.