Skip to main content

qualia_core_db/solvers/fuzzy_query/
solution.rs

1//! Degree-annotated solutions and the algebra that composes them.
2//!
3//! A [`FuzzySolution`] is one of the engine's [`BindingRow`]s plus a truth degree. A
4//! [`FuzzyResultSet`] is a sequence of them, with the relational-algebra-over-degrees
5//! operations f-SPARQL needs: conjunctive **join** (BGP / `AND`, degree via t-norm),
6//! **union** (`UNION`, t-conorm), **projection** (existential, max degree per distinct
7//! projection), **negation**, **α-cut** threshold, and **ranking** by degree.
8
9use super::DegreeNorm;
10use crate::sparql_ast::{BindingRow, VariableId, MAX_BINDINGS};
11
12/// One solution with its truth degree in `[0, 1]`.
13#[derive(Debug, Clone, Copy, PartialEq)]
14pub struct FuzzySolution {
15    pub row: BindingRow,
16    pub degree: f64,
17}
18
19impl FuzzySolution {
20    /// Creates a solution row with membership `degree`.
21    pub fn new(row: BindingRow, degree: f64) -> Self {
22        Self {
23            row,
24            degree: degree.clamp(0.0, 1.0),
25        }
26    }
27}
28
29/// Two rows are *compatible* iff every variable bound in both holds the same value.
30fn compatible(a: &BindingRow, b: &BindingRow) -> bool {
31    for i in 0..MAX_BINDINGS {
32        if let (Some(x), Some(y)) = (a.slots[i], b.slots[i]) {
33            if x != y {
34                return false;
35            }
36        }
37    }
38    true
39}
40
41/// Merge two compatible rows (union of bindings).
42fn merge(a: &BindingRow, b: &BindingRow) -> BindingRow {
43    let mut out = *a;
44    for i in 0..MAX_BINDINGS {
45        if out.slots[i].is_none() {
46            out.slots[i] = b.slots[i];
47        }
48    }
49    out
50}
51
52/// A bag of degree-annotated solutions.
53#[derive(Debug, Clone, Default, PartialEq)]
54pub struct FuzzyResultSet {
55    pub solutions: Vec<FuzzySolution>,
56}
57
58impl FuzzyResultSet {
59    /// Creates an empty result set.
60    pub fn new() -> Self {
61        Self {
62            solutions: Vec::new(),
63        }
64    }
65
66    /// Creates a result set from `solutions`.
67    pub fn from_solutions(solutions: Vec<FuzzySolution>) -> Self {
68        Self { solutions }
69    }
70
71    /// Appends a solution.
72    pub fn push(&mut self, sol: FuzzySolution) {
73        self.solutions.push(sol);
74    }
75
76    /// Result count.
77    pub fn len(&self) -> usize {
78        self.solutions.len()
79    }
80
81    /// `true` when empty.
82    pub fn is_empty(&self) -> bool {
83        self.solutions.is_empty()
84    }
85
86    /// α-cut: keep only solutions with degree `>= alpha`.
87    pub fn threshold(mut self, alpha: f64) -> Self {
88        self.solutions.retain(|s| s.degree >= alpha);
89        self
90    }
91
92    /// Sort by degree, highest confidence first (stable).
93    pub fn order_by_degree_desc(mut self) -> Self {
94        self.solutions.sort_by(|a, b| {
95            b.degree
96                .partial_cmp(&a.degree)
97                .unwrap_or(core::cmp::Ordering::Equal)
98        });
99        self
100    }
101
102    /// Keep the `k` highest-degree solutions.
103    pub fn top_k(mut self, k: usize) -> Self {
104        self = self.order_by_degree_desc();
105        self.solutions.truncate(k);
106        self
107    }
108
109    /// Fuzzy negation: replace each degree with its complement under `norm`. (Used for
110    /// `NOT`/`MINUS`-style scoring of how *un*-matched a solution is.)
111    pub fn negate(mut self, norm: DegreeNorm) -> Self {
112        for s in &mut self.solutions {
113            s.degree = norm.not(s.degree);
114        }
115        self
116    }
117
118    /// Conjunctive **join** (basic graph pattern / `AND`): every compatible pair of
119    /// solutions across the two sets yields a merged solution whose degree is the
120    /// t-norm of the two input degrees.
121    pub fn join(&self, other: &FuzzyResultSet, norm: DegreeNorm) -> FuzzyResultSet {
122        let mut out = Vec::new();
123        for a in &self.solutions {
124            for b in &other.solutions {
125                if compatible(&a.row, &b.row) {
126                    out.push(FuzzySolution::new(
127                        merge(&a.row, &b.row),
128                        norm.and(a.degree, b.degree),
129                    ));
130                }
131            }
132        }
133        FuzzyResultSet { solutions: out }
134    }
135
136    /// **Union** (`UNION`): solutions from both sets. Where the *same* row appears in
137    /// both, its degrees combine via the t-conorm (the most confident wins under
138    /// Gödel) rather than duplicating.
139    pub fn union(&self, other: &FuzzyResultSet, norm: DegreeNorm) -> FuzzyResultSet {
140        let mut out: Vec<FuzzySolution> = self.solutions.clone();
141        for b in &other.solutions {
142            if let Some(existing) = out.iter_mut().find(|a| a.row == b.row) {
143                existing.degree = norm.or(existing.degree, b.degree);
144            } else {
145                out.push(*b);
146            }
147        }
148        FuzzyResultSet { solutions: out }
149    }
150
151    /// **Projection** onto `vars` (existential): drop all other variable bindings; rows
152    /// that become identical are merged, keeping the maximum degree (∃ over the
153    /// projected-away variables — the t-conorm under Gödel).
154    pub fn project(&self, vars: &[VariableId], norm: DegreeNorm) -> FuzzyResultSet {
155        let keep = |row: &BindingRow| {
156            let mut r = BindingRow::new();
157            for &v in vars {
158                if let Some(val) = row.get(v) {
159                    r.set(v, val);
160                }
161            }
162            r
163        };
164        let mut out: Vec<FuzzySolution> = Vec::new();
165        for s in &self.solutions {
166            let pr = keep(&s.row);
167            if let Some(existing) = out.iter_mut().find(|e| e.row == pr) {
168                existing.degree = norm.or(existing.degree, s.degree);
169            } else {
170                out.push(FuzzySolution::new(pr, s.degree));
171            }
172        }
173        FuzzyResultSet { solutions: out }
174    }
175}
176
177#[cfg(test)]
178mod tests {
179    use super::*;
180
181    fn row(pairs: &[(VariableId, u64)]) -> BindingRow {
182        let mut r = BindingRow::new();
183        for &(v, val) in pairs {
184            r.set(v, val);
185        }
186        r
187    }
188
189    fn sol(pairs: &[(VariableId, u64)], d: f64) -> FuzzySolution {
190        FuzzySolution::new(row(pairs), d)
191    }
192
193    #[test]
194    fn join_combines_compatible_rows_by_tnorm() {
195        // ?x bound in both; compatible where ?x=1.
196        let left = FuzzyResultSet::from_solutions(vec![sol(&[(0, 1)], 0.8), sol(&[(0, 2)], 0.9)]);
197        let right = FuzzyResultSet::from_solutions(vec![sol(&[(0, 1), (1, 7)], 0.6)]);
198        let j = left.join(&right, DegreeNorm::Godel);
199        assert_eq!(j.len(), 1);
200        assert_eq!(j.solutions[0].row.get(0), Some(1));
201        assert_eq!(j.solutions[0].row.get(1), Some(7));
202        assert!((j.solutions[0].degree - 0.6).abs() < 1e-6); // min(0.8, 0.6)
203    }
204
205    #[test]
206    fn union_merges_same_row_by_tconorm() {
207        let a = FuzzyResultSet::from_solutions(vec![sol(&[(0, 1)], 0.4)]);
208        let b = FuzzyResultSet::from_solutions(vec![sol(&[(0, 1)], 0.7), sol(&[(0, 2)], 0.5)]);
209        let u = a.union(&b, DegreeNorm::Godel);
210        assert_eq!(u.len(), 2);
211        let merged = u
212            .solutions
213            .iter()
214            .find(|s| s.row.get(0) == Some(1))
215            .unwrap();
216        assert!((merged.degree - 0.7).abs() < 1e-6); // max(0.4, 0.7)
217    }
218
219    #[test]
220    fn threshold_and_ranking() {
221        let set = FuzzyResultSet::from_solutions(vec![
222            sol(&[(0, 1)], 0.2),
223            sol(&[(0, 2)], 0.9),
224            sol(&[(0, 3)], 0.5),
225        ]);
226        let cut = set.clone().threshold(0.5);
227        assert_eq!(cut.len(), 2);
228        let ranked = set.top_k(1);
229        assert_eq!(ranked.solutions[0].row.get(0), Some(2));
230    }
231
232    #[test]
233    fn projection_takes_max_over_dropped_vars() {
234        // Two rows agree on ?x but differ on ?y; projecting onto ?x existentially
235        // keeps the max degree.
236        let set = FuzzyResultSet::from_solutions(vec![
237            sol(&[(0, 1), (1, 10)], 0.3),
238            sol(&[(0, 1), (1, 11)], 0.8),
239        ]);
240        let p = set.project(&[0], DegreeNorm::Godel);
241        assert_eq!(p.len(), 1);
242        assert_eq!(p.solutions[0].row.get(1), None);
243        assert!((p.solutions[0].degree - 0.8).abs() < 1e-6);
244    }
245
246    #[test]
247    fn negation_complements_degree() {
248        let set = FuzzyResultSet::from_solutions(vec![sol(&[(0, 1)], 0.3)]);
249        let n = set.negate(DegreeNorm::Godel);
250        assert!((n.solutions[0].degree - 0.7).abs() < 1e-6);
251    }
252}