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

qualia_core_db/solvers/fuzzy_query/
solution.rs
