adityamukho · Oct 19, 2026 · Oct 19, 2026
@@ -12,6 +12,7 @@ and this project adheres to [Semantic Versioning](https://semver.org/spec/v2.0.0
 - **A `:db/valid-at` pattern in a `not-join` body binds the query's valid time on every path** (#615). When the body also held an expression, sat in an `or` branch, or ran in a query that invokes a rule, the body bound `nil`, so `(not-join [?e] [?e :db/valid-at ?t] [(> ?t 0)])` never matched and excluded nothing; without the expression the same body excluded every entity. It now binds the query's `:valid-at` value (or the current time) as the other paths do. Present since v0.13.1.
 - **A `:db/valid-at` pattern in a rule definition binds the query's valid time** (#617). The rule evaluators never received it, so in a rule body the pattern bound `nil` and the query failed with `INT-022`; in a rule's `not` / `not-join` body it bound `nil`, so the negation never matched on it; and in a rule's `or` branch it bound the current time instead of the query's `:valid-at`. Rule bodies, their negation bodies and `or` branches now bind the query's `:valid-at` value, the current time without one, and `nil` under `:any-valid-time`, as patterns outside rules do.
 - **An expression reading a variable only an `or` binds keeps its rows** (#625). The planner places expressions among the patterns and `not`s, and `or` / `or-join` run after them, so an expression such as `[(> ?x 1)]` in `[?e :n _] (or [?e :n ?x] [?e :ok ?x]) [(> ?x 1)]` ran before `?x` was bound and dropped every row, in queries and in rule bodies. Such an expression now runs after the `or`s, before the `not`s that wait for them, as those `not`s already did.
+- **A rule calling a rule with `not`, `not-join`, `or` or `or-join` gets all its rows** (#628). Stratification put a rule in the same stratum as the rules it calls, and within a stratum the rules without those clauses run first, so `(rule [(st ?m ?s) [?m :msg/actor ?a] (cur ?a ?s)])` ran before any `cur` row existed when `cur` had a `not-join`, and returned nothing; a caller that had a `not` or `or` of its own ran before or after its callee depending on the query. A rule now sits in a stratum above any rule with such a clause it calls, unless the two call each other.
 - **An `or` / `or-join` branch whose expression reads an outer variable matches** (#620). A branch such as `[(> ?v 1)]` in `[?e :n ?v] (or [(> ?v 1)] [(< ?v 0)])` was evaluated on its own from an empty binding and joined back afterwards, so its expression saw `?v` unbound and the branch matched nothing: the `or` silently dropped rows it should keep, in queries and in rule bodies. A branch whose expression reads a variable the branch does not bind itself is now seeded with each incoming row (an `or-join` branch with the row's join variables).
 
 ## v2.0.7 — 2026-10-16

@@ -121,7 +121,7 @@ cargo run < demos/demo_negation.txt
    - `executor.rs`: Query executor — temporal filter (tx-time → net-assert → valid-time), not/not-join post-filter
    - `matcher.rs`: Pattern matching with variable unification; `edn_to_value`, `edn_to_entity_id`
    - `evaluator.rs`: `RecursiveEvaluator` (semi-naive), `StratifiedEvaluator`, `evaluate_not_join`
-   - `stratification.rs`: `DependencyGraph`, `stratify()` — negative edges + cycle detection
+   - `stratification.rs`: `DependencyGraph`, `stratify()` — negative edges + cycle detection; a positive edge to a rule with `not`/`not-join`/`or`/`or-join` also raises the caller, off a cycle (#628)
    - `rules.rs`: `RuleRegistry` — thread-safe rule management
    - `types.rs`: `EdnValue`, `Pattern`, `DatalogQuery`, `AsOf`, `ValidAt`, `WhereClause` (incl. `Not`, `NotJoin`); `PseudoAttr` enum, `AttributeSpec` wrapper
    - `optimizer.rs`: Selectivity-based join reordering; disabled under `wasm` feature
@@ -174,7 +174,7 @@ Auto-migrates v1/v2/v3/v4/v5/v6 → v7 on open/checkpoint.
 
 ## Test Coverage
 
-**1293 tests** (1284 passing, 9 ignored; unit + integration + doc).
+**1300 tests** (1291 passing, 9 ignored; unit + integration + doc).
 See `docs/TEST_COVERAGE.md` for the full per-file breakdown.
 
 **Testing conventions** — see the Testing Conventions section below before writing any tests.

@@ -105,7 +105,7 @@ let r2 = pq.execute(&[("tx", BindValue::TxCount(2)), ("entity", BindValue::Entit
 
 ```bash
 cargo run          # interactive Datalog REPL
-cargo test         # run 1293 tests
+cargo test         # run 1300 tests
 cargo run < demos/demo_recursive.txt   # recursive rules demo
 ```
 

@@ -4,7 +4,7 @@
 
 **Verified**: 2026-10-16 with `cargo test`
 
-**Result**: 1,284 passing tests and 9 ignored tests (1,293 total), including the golden-file corpus (#391)
+**Result**: 1,291 passing tests and 9 ignored tests (1,300 total), including the golden-file corpus (#391)
 
 For v2.0.5, `tests/edge_cases_test.rs` checks that a file of 1 to 4,095 bytes is `STG-045`, unchanged and with no WAL, when it is a database cut below one page or foreign bytes, and opens as a new database that takes a write and reads it back after reopen when it is a prefix of the initial header or all zeros (#506). Rule-body tests in `tests/recursive_rules_test.rs` check that a `:db/valid-at` pattern in a rule definition, in its `not` and `not-join` bodies and in its `or` branches binds the query's valid time, on the semi-naive, stratified and magic-sets paths (#617).
 
@@ -18,7 +18,7 @@ For v2.0.5, torn-WAL-tail tests (#513) check that opening a WAL writer cuts off
 
 `tests/magic_sets_test.rs` checks rule queries with a literal argument where some call site cannot carry the magic-sets demand (#608): a rule-body call with an argument nothing binds yet, the same rule called with free arguments, a call from a rule called with free arguments, calls inside `or` and `not`, a fully literal call, and a call bound only by a variable; `magic_sets.rs` unit tests check the adornment each shape solves to.
 
-`tests/disjunction_test.rs` checks that an `or` sharing no variable with the earlier clauses joins as a cross product (#610), before or after them, through the seeded path (a branch with `not`) and in a rule body, keeps the earlier clauses' variables and fact metadata (a pseudo-attribute), and gives no rows when no branch matches. It also checks that `or` / `or-join` branches whose expressions read or bind from a variable only the outer row binds match, nested and in rule bodies (#620); a unit test covers `branch_outer_reads`. Expressions reading a variable only an `or` binds, including a chain and a `not` after them, keep their rows in queries, with rules and in rule bodies (#625); optimizer unit tests cover deferring them ahead of the deferred `not`s.
+`tests/disjunction_test.rs` checks that an `or` sharing no variable with the earlier clauses joins as a cross product (#610), before or after them, through the seeded path (a branch with `not`) and in a rule body, keeps the earlier clauses' variables and fact metadata (a pseudo-attribute), and gives no rows when no branch matches. It also checks that `or` / `or-join` branches whose expressions read or bind from a variable only the outer row binds match, nested and in rule bodies (#620); a unit test covers `branch_outer_reads`. Expressions reading a variable only an `or` binds, including a chain and a `not` after them, keep their rows in queries, with rules and in rule bodies (#625); optimizer unit tests cover deferring them ahead of the deferred `not`s. Tests in `tests/not_join_test.rs` check that a rule calling a rule with `not-join`, `not` or `or` returns that rule's rows, with a free and a literal argument and through a forwarding rule, and that a rule with its own `not-join` calling one gets the same rows whether or not the query asks for the callee first; stratification unit tests check that such a caller, a rule forwarding to it and a caller of a recursive one sit above the callee, and that recursion through a rule with a `not` still stratifies (#628).
 
 Not counted above: the `BrowserDb` tests run only on wasm32 with `wasm-bindgen-test` in a browser. Two of them check that the IndexedDB flush returns every page a write dirtied, and that a dirty page that cannot be read is an error rather than left out.
 

@@ -725,16 +725,7 @@ impl StratifiedEvaluator {
 
             for pred in &stratum_preds {
                 for rule in registry.get_rules(pred) {
-                    let has_not = rule.body.iter().any(|c| {
-                        matches!(
-                            c,
-                            WhereClause::Not(_)
-                                | WhereClause::NotJoin { .. }
-                                | WhereClause::Or(_)
-                                | WhereClause::OrJoin { .. }
-                        )
-                    });
-                    if has_not {
+                    if crate::query::datalog::stratification::has_mixed_clause(&rule.body) {
                         mixed_rules.push((pred.clone(), rule));
                     } else {
                         positive_rules.push((pred.clone(), rule));

@@ -1,6 +1,6 @@
 use crate::error::{ErrorCode, err_coded};
 use anyhow::Result;
-use std::collections::{BTreeMap, HashMap};
+use std::collections::{BTreeMap, BTreeSet, HashMap};
 
 use crate::query::datalog::rules::RuleRegistry;
 use crate::query::datalog::types::WhereClause;
@@ -38,6 +38,21 @@ fn collect_clause_deps(clause: &WhereClause, entry: &mut Vec<(String, bool)>) {
     }
 }
 
+/// Whether a rule body holds a `not`, `not-join`, `or` or `or-join`.
+/// `StratifiedEvaluator` runs such a rule once per stratum, after the
+/// positive-only rules, so a rule that calls one must sit above it (#628).
+pub(crate) fn has_mixed_clause(body: &[WhereClause]) -> bool {
+    body.iter().any(|c| {
+        matches!(
+            c,
+            WhereClause::Not(_)
+                | WhereClause::NotJoin { .. }
+                | WhereClause::Or(_)
+                | WhereClause::OrJoin { .. }
+        )
+    })
+}
+
 // ── Structs ───────────────────────────────────────────────────────────────────
 
 pub struct DependencyGraph {
@@ -46,22 +61,45 @@ pub struct DependencyGraph {
     /// A `BTreeMap` so `stratify()` walks heads in a fixed order and always
     /// reports the same pair for a given negative cycle (#410).
     edges: BTreeMap<String, Vec<(String, bool)>>,
+    /// Predicates with at least one rule for which `has_mixed_clause` holds.
+    mixed: BTreeSet<String>,
 }
 
 impl DependencyGraph {
     pub fn from_rules(registry: &RuleRegistry) -> Self {
         let mut edges: BTreeMap<String, Vec<(String, bool)>> = BTreeMap::new();
+        let mut mixed = BTreeSet::new();
 
         for (head_pred, rules) in registry.all_rules() {
             for rule in rules {
+                if has_mixed_clause(&rule.body) {
+                    mixed.insert(head_pred.to_string());
+                }
                 let entry = edges.entry(head_pred.to_string()).or_default();
                 for clause in &rule.body {
                     collect_clause_deps(clause, entry);
                 }
             }
         }
 
-        DependencyGraph { edges }
+        DependencyGraph { edges, mixed }
+    }
+
+    /// Whether `to` is reachable from `from` through one or more edges.
+    fn reaches(&self, from: &str, to: &str) -> bool {
+        let mut seen: BTreeSet<&str> = BTreeSet::new();
+        let mut stack = vec![from];
+        while let Some(p) = stack.pop() {
+            for (dep, _) in self.edges.get(p).into_iter().flatten() {
+                if dep == to {
+                    return true;
+                }
+                if seen.insert(dep.as_str()) {
+                    stack.push(dep.as_str());
+                }
+            }
+        }
+        false
     }
 
     pub fn stratify(&self) -> Result<HashMap<String, usize>> {
@@ -79,18 +117,31 @@ impl DependencyGraph {
         let mut strata: HashMap<String, usize> =
             all_predicates.into_iter().map(|p| (p, 0)).collect();
 
+        // A positive edge to a mixed predicate also needs a higher stratum,
+        // so the callee's not/or rules finish before the caller runs (#628).
+        // Not on a cycle: recursion through a mixed rule stays in one stratum.
+        let mut raised: BTreeSet<(&str, &str)> = BTreeSet::new();
+        for (head, deps) in &self.edges {
+            for (dep, is_negative) in deps {
+                if !*is_negative && self.mixed.contains(dep) && !self.reaches(dep, head) {
+                    raised.insert((head.as_str(), dep.as_str()));
+                }
+            }
+        }
+
         // Bellman-Ford-style constraint propagation
         let mut changed = true;
         while changed {
             changed = false;
             for (head, deps) in &self.edges {
                 for (dep, is_negative) in deps {
                     let dep_stratum = *strata.get(dep).unwrap_or(&0);
-                    let required = if *is_negative {
-                        dep_stratum.saturating_add(1)
-                    } else {
-                        dep_stratum
-                    };
+                    let required =
+                        if *is_negative || raised.contains(&(head.as_str(), dep.as_str())) {
+                            dep_stratum.saturating_add(1)
+                        } else {
+                            dep_stratum
+                        };
                     let head_stratum = strata.entry(head.clone()).or_insert(0);
                     if required > *head_stratum {
                         *head_stratum = required;
@@ -210,6 +261,57 @@ mod tests {
         assert!(s_eligible > s_rejected);
     }
 
+    #[test]
+    fn test_positive_edge_to_mixed_predicate_raises_caller() {
+        // #628: p →⁺ q, q has a `not`; q must finish before p runs.
+        let registry =
+            make_registry_with_rules(vec![positive_rule("p", "q"), negative_rule("q", "r")]);
+        let strata = DependencyGraph::from_rules(&registry).stratify().unwrap();
+        assert!(strata["p"] > strata["q"], "p above its mixed callee");
+        // A chain through a forwarding rule keeps the order.
+        let registry = make_registry_with_rules(vec![
+            positive_rule("p", "f"),
+            positive_rule("f", "q"),
+            negative_rule("q", "r"),
+        ]);
+        let strata = DependencyGraph::from_rules(&registry).stratify().unwrap();
+        assert!(strata["f"] > strata["q"], "forwarding rule above q");
+        assert!(strata["p"] >= strata["f"], "p not below f");
+    }
+
+    #[test]
+    fn test_recursion_through_mixed_predicate_stratifies() {
+        // q →⁺ q with a `not` in q's body: a cycle stays in one stratum and is
+        // not rejected as unstratifiable.
+        let (_, base) = base_rule("q");
+        let (_, neg) = negative_rule("q", "r");
+        let (_, rec) = positive_rule("q", "q");
+        let mut mixed_rec = neg;
+        mixed_rec.body.extend(rec.body);
+        let mut registry = RuleRegistry::new();
+        registry.register_rule_unchecked("q".to_string(), base);
+        registry.register_rule_unchecked("q".to_string(), mixed_rec);
+        let strata = DependencyGraph::from_rules(&registry).stratify().unwrap();
+        assert!(strata["q"] > strata["r"], "q above its negated r");
+    }
+
+    #[test]
+    fn test_caller_of_recursive_mixed_predicate_raised() {
+        // p →⁺ q, where q has a `not` and calls itself: q's cycle does not
+        // reach p, so p still sits above q.
+        let (_, neg) = negative_rule("q", "r");
+        let (_, rec) = positive_rule("q", "q");
+        let mut mixed_rec = neg;
+        mixed_rec.body.extend(rec.body);
+        let mut registry = make_registry_with_rules(vec![positive_rule("p", "q")]);
+        registry.register_rule_unchecked("q".to_string(), mixed_rec);
+        let strata = DependencyGraph::from_rules(&registry).stratify().unwrap();
+        assert!(
+            strata["p"] > strata["q"],
+            "p above its recursive mixed callee"
+        );
+    }
+
     #[test]
     fn test_negative_cycle_returns_error() {
         // p →⁻ q, q →⁻ p

@@ -554,3 +554,90 @@ fn test_not_join_expression_only_body() {
         .unwrap();
     assert_eq!(result_count(&result), 1, "only :a has ?v <= 1");
 }
+
+// ── #628: a rule calling a rule with `not` / `not-join` / `or` ───────────────
+
+fn issue_628_db() -> Minigraf {
+    let db = in_memory_db();
+    db.execute(
+        "(transact [[:m1 :msg/actor :a1]
+                    [:r1 :run/actor :a1] [:r1 :run/to :s1]
+                    [:r2 :run/actor :a1] [:r2 :run/to :s2] [:r2 :run/done true]])",
+    )
+    .unwrap();
+    db
+}
+
+#[test]
+fn test_rule_calling_not_join_rule() {
+    let db = issue_628_db();
+    db.execute(
+        "(rule [(cur ?a ?s) [?r :run/actor ?a] [?r :run/to ?s] (not-join [?r] [?r :run/done true])])",
+    )
+    .unwrap();
+    db.execute("(rule [(st ?m ?s) [?m :msg/actor ?a] (cur ?a ?s)])")
+        .unwrap();
+    db.execute("(rule [(st3 ?a ?s) (cur ?a ?s)])").unwrap();
+
+    let r = db
+        .execute("(query [:find ?m ?s :where [?m :msg/actor ?a] (cur ?a ?s)])")
+        .unwrap();
+    assert_eq!(result_count(&r), 1, "query calling the not-join rule");
+    let r = db
+        .execute("(query [:find ?m ?s :where (st ?m ?s)])")
+        .unwrap();
+    assert_eq!(result_count(&r), 1, "rule calling the not-join rule");
+    let r = db.execute("(query [:find ?s :where (st :m1 ?s)])").unwrap();
+    assert_eq!(result_count(&r), 1, "literal argument");
+    let r = db
+        .execute("(query [:find ?a ?s :where (st3 ?a ?s)])")
+        .unwrap();
+    assert_eq!(result_count(&r), 1, "forwarding rule");
+}
+
+#[test]
+fn test_rule_calling_not_rule() {
+    let db = issue_628_db();
+    db.execute("(rule [(cur ?a ?s) [?r :run/actor ?a] [?r :run/to ?s] (not [?r :run/done true])])")
+        .unwrap();
+    db.execute("(rule [(st ?m ?s) [?m :msg/actor ?a] (cur ?a ?s)])")
+        .unwrap();
+    let r = db
+        .execute("(query [:find ?m ?s :where (st ?m ?s)])")
+        .unwrap();
+    assert_eq!(result_count(&r), 1, "rule calling the not rule");
+}
+
+#[test]
+fn test_mixed_rule_calling_mixed_rule() {
+    let db = issue_628_db();
+    db.execute(
+        "(rule [(cur ?a ?s) [?r :run/actor ?a] [?r :run/to ?s] (not-join [?r] [?r :run/done true])])",
+    )
+    .unwrap();
+    db.execute(
+        "(rule [(stm ?m ?s) [?m :msg/actor ?a] (cur ?a ?s) (not-join [?m] [?m :nope true])])",
+    )
+    .unwrap();
+    let r = db
+        .execute("(query [:find ?m ?s :where (stm ?m ?s)])")
+        .unwrap();
+    assert_eq!(result_count(&r), 1, "caller alone");
+    let r = db
+        .execute("(query [:find ?m ?s :where (cur ?a ?x) (stm ?m ?s)])")
+        .unwrap();
+    assert_eq!(result_count(&r), 1, "callee asked first");
+}
+
+#[test]
+fn test_rule_calling_or_rule() {
+    let db = issue_628_db();
+    db.execute("(rule [(dest ?a ?s) [?r :run/actor ?a] (or [?r :run/to ?s] [?r :run/from ?s])])")
+        .unwrap();
+    db.execute("(rule [(st ?m ?s) [?m :msg/actor ?a] (dest ?a ?s)])")
+        .unwrap();
+    let r = db
+        .execute("(query [:find ?m ?s :where (st ?m ?s)])")
+        .unwrap();
+    assert_eq!(result_count(&r), 2, "rule calling the or rule");
+}