datalog_structural_model/ir/
aggregate.rs

1//! Aggregation IR for extension.
2//!
3//! Datalog with aggregation extends pure Datalog by allowing a
4//! body literal that folds a set of inner bindings into a single
5//! aggregate value, optionally grouped by a chosen set of
6//! variables. The aggregate result is bound to a fresh variable
7//! that downstream body literals (and the rule head) can consume.
8//!
9//! This module defines the IR data types only:
10//! [`Aggregator`] (the SQL/SPARQL aggregator vocabulary) and
11//! [`AggregateBody`] (an aggregation sub-query). The
12//! corresponding body-literal variant is
13//! [`Literal::Aggregate`](super::literal::Literal::Aggregate),
14//! and rule-level safety analysis is in
15//! [`Rule::unsafe_aggregate_variables`](super::rule::Rule::unsafe_aggregate_variables).
16//!
17//! **Stratification**: an aggregation depends on the *complete*
18//! extension of its inner predicates, so each predicate referenced
19//! from the aggregate's inner body forms a polarity-bearing
20//! dependency edge analogous to a negative literal — those
21//! predicates must sit in a strictly lower stratum than the
22//! rule's head predicate.
23
24use std::collections::BTreeSet;
25
26use super::literal::Literal;
27use super::symbols::VariableSymbol;
28
29/// SQL/SPARQL aggregator vocabulary supported in rule bodies.
30///
31/// Mirrors the subset called out in the extension deliverable
32/// (the rule validation specification):
33/// MIN, MAX, SUM, COUNT, AVG. SPARQL's `SAMPLE` and
34/// `GROUP_CONCAT` are not in scope for extension — they map onto
35/// SPARQL's `Group` operator rather than a Datalog rule body.
36#[derive(Clone, Copy, Debug, Eq, Hash, Ord, PartialEq, PartialOrd)]
37pub enum Aggregator {
38    /// `COUNT(?expr)` — number of distinct `?expr` values that
39    /// appear in the inner result set.
40    Count,
41    /// `SUM(?expr)` — numeric sum of `?expr` values.
42    Sum,
43    /// `MIN(?expr)` — minimum `?expr` value under SPARQL's
44    /// ordering (numeric / lexicographic per term kind).
45    Min,
46    /// `MAX(?expr)` — maximum `?expr` value under the same
47    /// ordering as [`Self::Min`].
48    Max,
49    /// `AVG(?expr)` — numeric mean of `?expr` values. Undefined
50    /// for an empty input.
51    Avg,
52}
53
54impl Aggregator {
55    /// Render the aggregator as its canonical uppercase name.
56    /// Used by diagnostics and rule-name maps.
57    #[must_use]
58    pub fn name(self) -> &'static str {
59        match self {
60            Self::Count => "COUNT",
61            Self::Sum => "SUM",
62            Self::Min => "MIN",
63            Self::Max => "MAX",
64            Self::Avg => "AVG",
65        }
66    }
67}
68
69/// An aggregation sub-query inside a rule body.
70///
71/// Semantically equivalent to a SPARQL `Group { ... } over { ... }`
72/// projection: evaluate `inner_body` as a sub-query, group the
73/// results by `group_by`, fold each group's `input_var` values
74/// with `aggregator`, and bind the per-group result to
75/// `result_var`. The aggregate then participates in the outer
76/// rule body as if `result_var` were produced by a positive
77/// atom that ranges over the per-group results.
78///
79/// # Variable scoping
80///
81/// `inner_body` is its own scope: positive atoms and `BIND`
82/// outputs inside the inner body bind variables that are visible
83/// only within the aggregation. The three sets of variables that
84/// leak out are `group_by`, `input_var`, and (after the
85/// aggregation fires) `result_var`. Concretely:
86///
87/// - `group_by` and `input_var` MUST be bound by some positive atom or `BIND`
88///   inside `inner_body`.
89/// - `result_var` MUST be fresh — it must not appear anywhere else in the outer
90///   rule (head or body).
91///
92/// # Inner-body literal kinds
93///
94/// `inner_body` accepts the same four literal kinds the outer
95/// rule body accepts — [`Literal::Positive`], [`Literal::Negative`],
96/// [`Literal::Filter`], and [`Literal::Bind`] — under the usual
97/// safety rules (negated atoms and filter expressions reference
98/// only inner-body-bound variables; `BIND` expressions reference
99/// only earlier inner positives / binds and bind a fresh variable).
100/// Nested aggregates inside an aggregate's inner body are rejected
101/// at validation time as
102/// [`super::error::ProgramValidationError::NestedAggregateInInnerBody`].
103#[derive(Clone, Debug, Eq, Hash, PartialEq)]
104pub struct AggregateBody {
105    /// The variable that receives the per-group aggregate
106    /// result.
107    pub result_var: VariableSymbol,
108    /// Which aggregator to apply.
109    pub aggregator: Aggregator,
110    /// The variable whose values are folded into the aggregate
111    /// (the "input expression" in SPARQL terms).
112    pub input_var: VariableSymbol,
113    /// Group-by keys. The aggregator runs once per distinct
114    /// tuple of `group_by` values; an empty `group_by`
115    /// collapses every inner-body binding into a single group.
116    pub group_by: Vec<VariableSymbol>,
117    /// Literals forming the aggregation's inner sub-query.
118    /// Accepts [`Literal::Positive`], [`Literal::Negative`],
119    /// [`Literal::Filter`], and [`Literal::Bind`] under the
120    /// per-kind safety rules. Nested
121    /// [`Literal::Aggregate`] is rejected at validation time.
122    pub inner_body: Vec<Literal>,
123}
124
125impl AggregateBody {
126    /// Variables bound by the inner body — every variable a
127    /// positive inner atom binds, plus every `BIND`'s output
128    /// variable. Used by safety analysis to verify that
129    /// `input_var` and `group_by` are sourced from the inner
130    /// body and that inner negation / filter / bind references
131    /// stay within the inner scope.
132    #[must_use]
133    pub fn inner_bound_variables(&self) -> BTreeSet<VariableSymbol> {
134        let mut out = BTreeSet::new();
135        for lit in &self.inner_body {
136            match lit {
137                Literal::Positive(atom) => out.extend(atom.variables()),
138                Literal::Bind { var, .. } => {
139                    out.insert(var.clone());
140                }
141                Literal::Negative(_) | Literal::Filter(_) | Literal::Aggregate(_) => {}
142            }
143        }
144        out
145    }
146
147    /// Variables this aggregate exposes to the outer rule body:
148    /// the freshly-bound `result_var` plus every key the
149    /// outer rule groups by. The outer-scope view of an
150    /// aggregate body literal.
151    #[must_use]
152    pub fn exported_variables(&self) -> BTreeSet<VariableSymbol> {
153        let mut out: BTreeSet<VariableSymbol> = self.group_by.iter().cloned().collect();
154        out.insert(self.result_var.clone());
155        out
156    }
157
158    /// Returns `true` when the inner body contains a nested
159    /// `Literal::Aggregate`. Nested aggregates are rejected as
160    /// [`super::error::ProgramValidationError::NestedAggregateInInnerBody`].
161    #[must_use]
162    pub fn contains_nested_aggregate(&self) -> bool {
163        self.inner_body
164            .iter()
165            .any(|lit| matches!(lit, Literal::Aggregate(_)))
166    }
167}
datalog_structural_model/ir/aggregate.rs

datalog_structural_model/ir/
aggregate.rs
