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(
37    Clone, Copy, Debug, Eq, Hash, Ord, PartialEq, PartialOrd, serde::Serialize, serde::Deserialize,
38)]
39#[serde(deny_unknown_fields)]
40pub enum Aggregator {
41    /// `COUNT(?expr)` — number of distinct `?expr` values that
42    /// appear in the inner result set.
43    Count,
44    /// `SUM(?expr)` — numeric sum of `?expr` values.
45    Sum,
46    /// `MIN(?expr)` — minimum `?expr` value under SPARQL's
47    /// ordering (numeric / lexicographic per term kind).
48    Min,
49    /// `MAX(?expr)` — maximum `?expr` value under the same
50    /// ordering as [`Self::Min`].
51    Max,
52    /// `AVG(?expr)` — numeric mean of `?expr` values. Undefined
53    /// for an empty input.
54    Avg,
55}
56
57impl Aggregator {
58    /// Render the aggregator as its canonical uppercase name.
59    /// Used by diagnostics and rule-name maps.
60    #[must_use]
61    pub fn name(self) -> &'static str {
62        match self {
63            Self::Count => "COUNT",
64            Self::Sum => "SUM",
65            Self::Min => "MIN",
66            Self::Max => "MAX",
67            Self::Avg => "AVG",
68        }
69    }
70}
71
72/// An aggregation sub-query inside a rule body.
73///
74/// Semantically equivalent to a SPARQL `Group { ... } over { ... }`
75/// projection: evaluate `inner_body` as a sub-query, group the
76/// results by `group_by`, fold each group's `input_var` values
77/// with `aggregator`, and bind the per-group result to
78/// `result_var`. The aggregate then participates in the outer
79/// rule body as if `result_var` were produced by a positive
80/// atom that ranges over the per-group results.
81///
82/// # Variable scoping
83///
84/// `inner_body` is its own scope: positive atoms and `BIND`
85/// outputs inside the inner body bind variables that are visible
86/// only within the aggregation. The three sets of variables that
87/// leak out are `group_by`, `input_var`, and (after the
88/// aggregation fires) `result_var`. Concretely:
89///
90/// - `group_by` and `input_var` MUST be bound by some positive atom or `BIND`
91///   inside `inner_body`.
92/// - `result_var` MUST be fresh — it must not appear anywhere else in the outer
93///   rule (head or body).
94///
95/// # Inner-body literal kinds
96///
97/// `inner_body` accepts the same four literal kinds the outer
98/// rule body accepts — [`Literal::Positive`], [`Literal::Negative`],
99/// [`Literal::Filter`], and [`Literal::Bind`] — under the usual
100/// safety rules (negated atoms and filter expressions reference
101/// only inner-body-bound variables; `BIND` expressions reference
102/// only earlier inner positives / binds and bind a fresh variable).
103/// Nested aggregates inside an aggregate's inner body are rejected
104/// at validation time as
105/// [`super::error::ProgramValidationError::NestedAggregateInInnerBody`].
106#[derive(Clone, Debug, Eq, Hash, PartialEq, serde::Serialize, serde::Deserialize)]
107#[serde(deny_unknown_fields)]
108pub struct AggregateBody {
109    /// The variable that receives the per-group aggregate
110    /// result.
111    pub result_var: VariableSymbol,
112    /// Which aggregator to apply.
113    pub aggregator: Aggregator,
114    /// The variable whose values are folded into the aggregate
115    /// (the "input expression" in SPARQL terms).
116    pub input_var: VariableSymbol,
117    /// Group-by keys. The aggregator runs once per distinct
118    /// tuple of `group_by` values; an empty `group_by`
119    /// collapses every inner-body binding into a single group.
120    pub group_by: Vec<VariableSymbol>,
121    /// Literals forming the aggregation's inner sub-query.
122    /// Accepts [`Literal::Positive`], [`Literal::Negative`],
123    /// [`Literal::Filter`], and [`Literal::Bind`] under the
124    /// per-kind safety rules. Nested
125    /// [`Literal::Aggregate`] is rejected at validation time.
126    pub inner_body: Vec<Literal>,
127}
128
129impl AggregateBody {
130    /// Variables bound by the inner body — every variable a
131    /// positive inner atom binds, plus every `BIND`'s output
132    /// variable. Used by safety analysis to verify that
133    /// `input_var` and `group_by` are sourced from the inner
134    /// body and that inner negation / filter / bind references
135    /// stay within the inner scope.
136    #[must_use]
137    pub fn inner_bound_variables(&self) -> BTreeSet<VariableSymbol> {
138        let mut out = BTreeSet::new();
139        for lit in &self.inner_body {
140            match lit {
141                Literal::Positive(atom) => out.extend(atom.variables()),
142                Literal::Bind { var, .. } => {
143                    out.insert(var.clone());
144                }
145                Literal::Negative(_) | Literal::Filter(_) | Literal::Aggregate(_) => {}
146            }
147        }
148        out
149    }
150
151    /// Variables this aggregate exposes to the outer rule body:
152    /// the freshly-bound `result_var` plus every key the
153    /// outer rule groups by. The outer-scope view of an
154    /// aggregate body literal.
155    #[must_use]
156    pub fn exported_variables(&self) -> BTreeSet<VariableSymbol> {
157        let mut out: BTreeSet<VariableSymbol> = self.group_by.iter().cloned().collect();
158        out.insert(self.result_var.clone());
159        out
160    }
161
162    /// Returns `true` when the inner body contains a nested
163    /// `Literal::Aggregate`. Nested aggregates are rejected as
164    /// [`super::error::ProgramValidationError::NestedAggregateInInnerBody`].
165    #[must_use]
166    pub fn contains_nested_aggregate(&self) -> bool {
167        self.inner_body
168            .iter()
169            .any(|lit| matches!(lit, Literal::Aggregate(_)))
170    }
171}
datalog_structural_model/ir/aggregate.rs

datalog_structural_model/ir/
aggregate.rs
