oxirs_core/query/
pattern_unification.rs

1//! Pattern type unification for OxiRS query processing
2//!
3//! This module provides utilities to unify different pattern representations
4//! used across the algebra and model systems, resolving type conflicts and
5//! enabling seamless interoperability.
6
7use crate::model::*;
8use crate::query::algebra::{AlgebraTriplePattern, TermPattern as AlgebraTermPattern};
9use crate::OxirsError;
10use std::collections::HashSet;
11
12/// Unified pattern representation that can handle both algebra and model patterns
13#[derive(Debug, Clone, PartialEq, Eq, Hash)]
14pub struct UnifiedTriplePattern {
15    /// Subject pattern
16    pub subject: UnifiedTermPattern,
17    /// Predicate pattern  
18    pub predicate: UnifiedTermPattern,
19    /// Object pattern
20    pub object: UnifiedTermPattern,
21}
22
23/// Unified term pattern that works with both systems
24#[derive(Debug, Clone, PartialEq, Eq, Hash)]
25pub enum UnifiedTermPattern {
26    /// Named node (IRI)
27    NamedNode(NamedNode),
28    /// Blank node
29    BlankNode(BlankNode),
30    /// Literal value
31    Literal(Literal),
32    /// Variable
33    Variable(Variable),
34    /// Wildcard (matches anything)
35    Wildcard,
36}
37
38impl UnifiedTriplePattern {
39    /// Create a new unified triple pattern
40    pub fn new(
41        subject: UnifiedTermPattern,
42        predicate: UnifiedTermPattern,
43        object: UnifiedTermPattern,
44    ) -> Self {
45        Self {
46            subject,
47            predicate,
48            object,
49        }
50    }
51
52    /// Convert to algebra TriplePattern
53    pub fn to_algebra_pattern(&self) -> Result<AlgebraTriplePattern, OxirsError> {
54        let subject = self.subject.to_algebra_term_pattern()?;
55        let predicate = self.predicate.to_algebra_term_pattern()?;
56        let object = self.object.to_algebra_term_pattern()?;
57
58        Ok(AlgebraTriplePattern::new(subject, predicate, object))
59    }
60
61    /// Convert to model TriplePattern
62    pub fn to_model_pattern(&self) -> TriplePattern {
63        let subject = self.subject.to_model_subject_pattern();
64        let predicate = self.predicate.to_model_predicate_pattern();
65        let object = self.object.to_model_object_pattern();
66
67        TriplePattern::new(subject, predicate, object)
68    }
69
70    /// Create from algebra TriplePattern
71    pub fn from_algebra_pattern(pattern: &AlgebraTriplePattern) -> Self {
72        Self {
73            subject: UnifiedTermPattern::from_algebra_term(&pattern.subject),
74            predicate: UnifiedTermPattern::from_algebra_term(&pattern.predicate),
75            object: UnifiedTermPattern::from_algebra_term(&pattern.object),
76        }
77    }
78
79    /// Create from model TriplePattern
80    pub fn from_model_pattern(pattern: &TriplePattern) -> Self {
81        Self {
82            subject: pattern
83                .subject()
84                .map(UnifiedTermPattern::from_model_subject)
85                .unwrap_or(UnifiedTermPattern::Wildcard),
86            predicate: pattern
87                .predicate()
88                .map(UnifiedTermPattern::from_model_predicate)
89                .unwrap_or(UnifiedTermPattern::Wildcard),
90            object: pattern
91                .object()
92                .map(UnifiedTermPattern::from_model_object)
93                .unwrap_or(UnifiedTermPattern::Wildcard),
94        }
95    }
96
97    /// Extract all variables from this pattern
98    pub fn extract_variables(&self) -> HashSet<Variable> {
99        let mut vars = HashSet::new();
100
101        if let UnifiedTermPattern::Variable(v) = &self.subject {
102            vars.insert(v.clone());
103        }
104        if let UnifiedTermPattern::Variable(v) = &self.predicate {
105            vars.insert(v.clone());
106        }
107        if let UnifiedTermPattern::Variable(v) = &self.object {
108            vars.insert(v.clone());
109        }
110
111        vars
112    }
113
114    /// Check if this pattern matches a concrete triple
115    pub fn matches(&self, triple: &Triple) -> bool {
116        self.subject.matches_subject(triple.subject())
117            && self.predicate.matches_predicate(triple.predicate())
118            && self.object.matches_object(triple.object())
119    }
120
121    /// Get pattern selectivity estimate (0.0 = most selective, 1.0 = least selective)
122    pub fn selectivity_estimate(&self) -> f64 {
123        let subject_selectivity = self.subject.selectivity_factor();
124        let predicate_selectivity = self.predicate.selectivity_factor();
125        let object_selectivity = self.object.selectivity_factor();
126
127        // Combined selectivity using independence assumption
128        subject_selectivity * predicate_selectivity * object_selectivity
129    }
130}
131
132impl UnifiedTermPattern {
133    /// Convert to algebra TermPattern
134    pub fn to_algebra_term_pattern(&self) -> Result<AlgebraTermPattern, OxirsError> {
135        match self {
136            UnifiedTermPattern::NamedNode(nn) => Ok(AlgebraTermPattern::NamedNode(nn.clone())),
137            UnifiedTermPattern::BlankNode(bn) => Ok(AlgebraTermPattern::BlankNode(bn.clone())),
138            UnifiedTermPattern::Literal(lit) => Ok(AlgebraTermPattern::Literal(lit.clone())),
139            UnifiedTermPattern::Variable(var) => Ok(AlgebraTermPattern::Variable(var.clone())),
140            UnifiedTermPattern::Wildcard => Err(OxirsError::Query(
141                "Wildcard patterns cannot be converted to algebra representation".to_string(),
142            )),
143        }
144    }
145
146    /// Convert to model SubjectPattern
147    pub fn to_model_subject_pattern(&self) -> Option<SubjectPattern> {
148        match self {
149            UnifiedTermPattern::NamedNode(nn) => Some(SubjectPattern::NamedNode(nn.clone())),
150            UnifiedTermPattern::BlankNode(bn) => Some(SubjectPattern::BlankNode(bn.clone())),
151            UnifiedTermPattern::Variable(var) => Some(SubjectPattern::Variable(var.clone())),
152            UnifiedTermPattern::Literal(_) | UnifiedTermPattern::Wildcard => None,
153        }
154    }
155
156    /// Convert to model PredicatePattern
157    pub fn to_model_predicate_pattern(&self) -> Option<PredicatePattern> {
158        match self {
159            UnifiedTermPattern::NamedNode(nn) => Some(PredicatePattern::NamedNode(nn.clone())),
160            UnifiedTermPattern::Variable(var) => Some(PredicatePattern::Variable(var.clone())),
161            UnifiedTermPattern::BlankNode(_)
162            | UnifiedTermPattern::Literal(_)
163            | UnifiedTermPattern::Wildcard => None,
164        }
165    }
166
167    /// Convert to model ObjectPattern
168    pub fn to_model_object_pattern(&self) -> Option<ObjectPattern> {
169        match self {
170            UnifiedTermPattern::NamedNode(nn) => Some(ObjectPattern::NamedNode(nn.clone())),
171            UnifiedTermPattern::BlankNode(bn) => Some(ObjectPattern::BlankNode(bn.clone())),
172            UnifiedTermPattern::Literal(lit) => Some(ObjectPattern::Literal(lit.clone())),
173            UnifiedTermPattern::Variable(var) => Some(ObjectPattern::Variable(var.clone())),
174            UnifiedTermPattern::Wildcard => None,
175        }
176    }
177
178    /// Create from algebra TermPattern
179    pub fn from_algebra_term(term: &AlgebraTermPattern) -> Self {
180        match term {
181            AlgebraTermPattern::NamedNode(nn) => UnifiedTermPattern::NamedNode(nn.clone()),
182            AlgebraTermPattern::BlankNode(bn) => UnifiedTermPattern::BlankNode(bn.clone()),
183            AlgebraTermPattern::Literal(lit) => UnifiedTermPattern::Literal(lit.clone()),
184            AlgebraTermPattern::Variable(var) => UnifiedTermPattern::Variable(var.clone()),
185            // Quoted-triple patterns are represented as wildcards at the unified
186            // level (matching the `from_model_subject`/`from_model_object`
187            // handling below); fine-grained inner-triple matching is handled by
188            // the RDF-star evaluator. This avoids panicking on RDF-star input.
189            AlgebraTermPattern::QuotedTriple(_) => UnifiedTermPattern::Wildcard,
190        }
191    }
192
193    /// Create from model SubjectPattern
194    pub fn from_model_subject(subject: &SubjectPattern) -> Self {
195        match subject {
196            SubjectPattern::NamedNode(nn) => UnifiedTermPattern::NamedNode(nn.clone()),
197            SubjectPattern::BlankNode(bn) => UnifiedTermPattern::BlankNode(bn.clone()),
198            SubjectPattern::Variable(var) => UnifiedTermPattern::Variable(var.clone()),
199            // Quoted-triple patterns are represented as wildcards at the unified level;
200            // fine-grained inner-triple matching is handled by the RDF-star evaluator.
201            SubjectPattern::QuotedTriple(_) => UnifiedTermPattern::Wildcard,
202        }
203    }
204
205    /// Create from model PredicatePattern
206    pub fn from_model_predicate(predicate: &PredicatePattern) -> Self {
207        match predicate {
208            PredicatePattern::NamedNode(nn) => UnifiedTermPattern::NamedNode(nn.clone()),
209            PredicatePattern::Variable(var) => UnifiedTermPattern::Variable(var.clone()),
210        }
211    }
212
213    /// Create from model ObjectPattern
214    pub fn from_model_object(object: &ObjectPattern) -> Self {
215        match object {
216            ObjectPattern::NamedNode(nn) => UnifiedTermPattern::NamedNode(nn.clone()),
217            ObjectPattern::BlankNode(bn) => UnifiedTermPattern::BlankNode(bn.clone()),
218            ObjectPattern::Literal(lit) => UnifiedTermPattern::Literal(lit.clone()),
219            ObjectPattern::Variable(var) => UnifiedTermPattern::Variable(var.clone()),
220            // Quoted-triple patterns are represented as wildcards at the unified level.
221            ObjectPattern::QuotedTriple(_) => UnifiedTermPattern::Wildcard,
222        }
223    }
224
225    /// Check if this pattern matches a subject
226    pub fn matches_subject(&self, subject: &Subject) -> bool {
227        match (self, subject) {
228            (UnifiedTermPattern::NamedNode(pn), Subject::NamedNode(sn)) => pn == sn,
229            (UnifiedTermPattern::BlankNode(pb), Subject::BlankNode(sb)) => pb == sb,
230            (UnifiedTermPattern::Variable(_), _) | (UnifiedTermPattern::Wildcard, _) => true,
231            _ => false,
232        }
233    }
234
235    /// Check if this pattern matches a predicate
236    pub fn matches_predicate(&self, predicate: &Predicate) -> bool {
237        match (self, predicate) {
238            (UnifiedTermPattern::NamedNode(pn), Predicate::NamedNode(sn)) => pn == sn,
239            (UnifiedTermPattern::Variable(_), _) | (UnifiedTermPattern::Wildcard, _) => true,
240            _ => false,
241        }
242    }
243
244    /// Check if this pattern matches an object
245    pub fn matches_object(&self, object: &Object) -> bool {
246        match (self, object) {
247            (UnifiedTermPattern::NamedNode(pn), Object::NamedNode(on)) => pn == on,
248            (UnifiedTermPattern::BlankNode(pb), Object::BlankNode(ob)) => pb == ob,
249            (UnifiedTermPattern::Literal(pl), Object::Literal(ol)) => pl == ol,
250            (UnifiedTermPattern::Variable(_), _) | (UnifiedTermPattern::Wildcard, _) => true,
251            _ => false,
252        }
253    }
254
255    /// Get selectivity factor for cost estimation
256    pub fn selectivity_factor(&self) -> f64 {
257        match self {
258            UnifiedTermPattern::NamedNode(_) => 0.001, // Very selective
259            UnifiedTermPattern::BlankNode(_) => 0.01,  // Selective
260            UnifiedTermPattern::Literal(_) => 0.001,   // Very selective
261            UnifiedTermPattern::Variable(_) => 1.0,    // Not selective
262            UnifiedTermPattern::Wildcard => 1.0,       // Not selective
263        }
264    }
265}
266
267/// Pattern conversion utilities
268pub struct PatternConverter;
269
270impl PatternConverter {
271    /// Convert a vector of algebra patterns to model patterns
272    pub fn algebra_to_model_patterns(patterns: &[AlgebraTriplePattern]) -> Vec<TriplePattern> {
273        patterns
274            .iter()
275            .map(|p| UnifiedTriplePattern::from_algebra_pattern(p).to_model_pattern())
276            .collect()
277    }
278
279    /// Convert a vector of model patterns to algebra patterns
280    pub fn model_to_algebra_patterns(
281        patterns: &[TriplePattern],
282    ) -> Result<Vec<AlgebraTriplePattern>, OxirsError> {
283        patterns
284            .iter()
285            .map(|p| UnifiedTriplePattern::from_model_pattern(p).to_algebra_pattern())
286            .collect()
287    }
288
289    /// Extract all variables from a set of algebra patterns
290    pub fn extract_variables_from_algebra(patterns: &[AlgebraTriplePattern]) -> HashSet<Variable> {
291        patterns
292            .iter()
293            .flat_map(|p| UnifiedTriplePattern::from_algebra_pattern(p).extract_variables())
294            .collect()
295    }
296
297    /// Extract all variables from a set of model patterns
298    pub fn extract_variables_from_model(patterns: &[TriplePattern]) -> HashSet<Variable> {
299        patterns
300            .iter()
301            .flat_map(|p| UnifiedTriplePattern::from_model_pattern(p).extract_variables())
302            .collect()
303    }
304
305    /// Estimate combined selectivity for a set of patterns
306    pub fn estimate_pattern_selectivity(patterns: &[UnifiedTriplePattern]) -> f64 {
307        if patterns.is_empty() {
308            return 1.0;
309        }
310
311        patterns
312            .iter()
313            .map(|p| p.selectivity_estimate())
314            .fold(1.0, |acc, s| acc * s)
315    }
316}
317
318/// Query optimization utilities using unified patterns
319pub struct PatternOptimizer;
320
321impl PatternOptimizer {
322    /// Reorder patterns for optimal execution based on selectivity
323    pub fn optimize_pattern_order(patterns: &[UnifiedTriplePattern]) -> Vec<UnifiedTriplePattern> {
324        let mut sorted_patterns = patterns.to_vec();
325
326        // Sort by selectivity (most selective first)
327        sorted_patterns.sort_by(|a, b| {
328            a.selectivity_estimate()
329                .partial_cmp(&b.selectivity_estimate())
330                .unwrap_or(std::cmp::Ordering::Equal)
331        });
332
333        sorted_patterns
334    }
335
336    /// Find optimal join order for patterns
337    pub fn optimize_join_order(patterns: &[UnifiedTriplePattern]) -> Vec<usize> {
338        if patterns.is_empty() {
339            return Vec::new();
340        }
341
342        // Simple greedy algorithm: start with most selective pattern
343        let mut remaining: Vec<usize> = (0..patterns.len()).collect();
344        let mut order = Vec::new();
345
346        // Find most selective pattern as starting point
347        if let Some(min_idx) = remaining
348            .iter()
349            .min_by(|&&a, &&b| {
350                patterns[a]
351                    .selectivity_estimate()
352                    .partial_cmp(&patterns[b].selectivity_estimate())
353                    .unwrap_or(std::cmp::Ordering::Equal)
354            })
355            .copied()
356        {
357            order.push(min_idx);
358            remaining.retain(|&x| x != min_idx);
359        }
360
361        // Greedily add patterns that share most variables with already selected patterns
362        while !remaining.is_empty() {
363            let selected_vars: HashSet<Variable> = order
364                .iter()
365                .flat_map(|&i| patterns[i].extract_variables())
366                .collect();
367
368            if let Some(best_idx) = remaining
369                .iter()
370                .max_by_key(|&&i| {
371                    let pattern_vars = patterns[i].extract_variables();
372                    pattern_vars.intersection(&selected_vars).count()
373                })
374                .copied()
375            {
376                order.push(best_idx);
377                remaining.retain(|&x| x != best_idx);
378            } else {
379                // Fallback: add remaining patterns in selectivity order
380                order.extend(remaining);
381                break;
382            }
383        }
384
385        order
386    }
387}
388
389#[cfg(test)]
390mod tests {
391    use super::*;
392
393    #[test]
394    fn test_unified_pattern_conversion() {
395        // Create an algebra pattern
396        let algebra_pattern = AlgebraTriplePattern::new(
397            AlgebraTermPattern::Variable(Variable::new("s").expect("valid variable name")),
398            AlgebraTermPattern::NamedNode(
399                NamedNode::new("http://example.org/pred").expect("valid IRI"),
400            ),
401            AlgebraTermPattern::Literal(Literal::new("test")),
402        );
403
404        // Convert to unified pattern
405        let unified = UnifiedTriplePattern::from_algebra_pattern(&algebra_pattern);
406
407        // Convert back to algebra pattern
408        let converted_back = unified
409            .to_algebra_pattern()
410            .expect("operation should succeed");
411
412        assert_eq!(algebra_pattern, converted_back);
413    }
414
415    #[test]
416    fn test_pattern_selectivity() {
417        let patterns = [
418            UnifiedTriplePattern::new(
419                UnifiedTermPattern::Variable(Variable::new("s").expect("valid variable name")),
420                UnifiedTermPattern::Variable(Variable::new("p").expect("valid variable name")),
421                UnifiedTermPattern::Variable(Variable::new("o").expect("valid variable name")),
422            ),
423            UnifiedTriplePattern::new(
424                UnifiedTermPattern::NamedNode(
425                    NamedNode::new("http://example.org/s").expect("valid IRI"),
426                ),
427                UnifiedTermPattern::NamedNode(
428                    NamedNode::new("http://example.org/p").expect("valid IRI"),
429                ),
430                UnifiedTermPattern::Variable(Variable::new("o").expect("valid variable name")),
431            ),
432        ];
433
434        // Second pattern should be more selective
435        assert!(patterns[1].selectivity_estimate() < patterns[0].selectivity_estimate());
436    }
437
438    #[test]
439    fn test_pattern_optimization() {
440        let patterns = vec![
441            UnifiedTriplePattern::new(
442                UnifiedTermPattern::Variable(Variable::new("s").expect("valid variable name")),
443                UnifiedTermPattern::Variable(Variable::new("p").expect("valid variable name")),
444                UnifiedTermPattern::Variable(Variable::new("o").expect("valid variable name")),
445            ),
446            UnifiedTriplePattern::new(
447                UnifiedTermPattern::NamedNode(
448                    NamedNode::new("http://example.org/s").expect("valid IRI"),
449                ),
450                UnifiedTermPattern::NamedNode(
451                    NamedNode::new("http://example.org/p").expect("valid IRI"),
452                ),
453                UnifiedTermPattern::Variable(Variable::new("o").expect("valid variable name")),
454            ),
455        ];
456
457        let optimized = PatternOptimizer::optimize_pattern_order(&patterns);
458
459        // More selective pattern should come first
460        assert_eq!(optimized[0], patterns[1]);
461        assert_eq!(optimized[1], patterns[0]);
462    }
463}
oxirs_core/query/pattern_unification.rs

oxirs_core/query/
pattern_unification.rs
