qualia_core_db/solvers/fuzzy_query/
solution.rs1use super::DegreeNorm;
10use crate::sparql_ast::{BindingRow, VariableId, MAX_BINDINGS};
11
12#[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 {
22 Self {
23 row,
24 degree: degree.clamp(0.0, 1.0),
25 }
26 }
27}
28
29fn 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
41fn 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#[derive(Debug, Clone, Default, PartialEq)]
54pub struct FuzzyResultSet {
55 pub solutions: Vec<FuzzySolution>,
56}
57
58impl FuzzyResultSet {
59 pub fn new() -> Self {
61 Self {
62 solutions: Vec::new(),
63 }
64 }
65
66 pub fn from_solutions(solutions: Vec<FuzzySolution>) -> Self {
68 Self { solutions }
69 }
70
71 pub fn push(&mut self, sol: FuzzySolution) {
73 self.solutions.push(sol);
74 }
75
76 pub fn len(&self) -> usize {
78 self.solutions.len()
79 }
80
81 pub fn is_empty(&self) -> bool {
83 self.solutions.is_empty()
84 }
85
86 pub fn threshold(mut self, alpha: f64) -> Self {
88 self.solutions.retain(|s| s.degree >= alpha);
89 self
90 }
91
92 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 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 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 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 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 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 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); }
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); }
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 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}