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            AlgebraTermPattern::QuotedTriple(_) => {
186                panic!("RDF-star quoted triples not yet supported in pattern unification")
187            }
188        }
189    }
190
191    /// Create from model SubjectPattern
192    pub fn from_model_subject(subject: &SubjectPattern) -> Self {
193        match subject {
194            SubjectPattern::NamedNode(nn) => UnifiedTermPattern::NamedNode(nn.clone()),
195            SubjectPattern::BlankNode(bn) => UnifiedTermPattern::BlankNode(bn.clone()),
196            SubjectPattern::Variable(var) => UnifiedTermPattern::Variable(var.clone()),
197            // Quoted-triple patterns are represented as wildcards at the unified level;
198            // fine-grained inner-triple matching is handled by the RDF-star evaluator.
199            SubjectPattern::QuotedTriple(_) => UnifiedTermPattern::Wildcard,
200        }
201    }
202
203    /// Create from model PredicatePattern
204    pub fn from_model_predicate(predicate: &PredicatePattern) -> Self {
205        match predicate {
206            PredicatePattern::NamedNode(nn) => UnifiedTermPattern::NamedNode(nn.clone()),
207            PredicatePattern::Variable(var) => UnifiedTermPattern::Variable(var.clone()),
208        }
209    }
210
211    /// Create from model ObjectPattern
212    pub fn from_model_object(object: &ObjectPattern) -> Self {
213        match object {
214            ObjectPattern::NamedNode(nn) => UnifiedTermPattern::NamedNode(nn.clone()),
215            ObjectPattern::BlankNode(bn) => UnifiedTermPattern::BlankNode(bn.clone()),
216            ObjectPattern::Literal(lit) => UnifiedTermPattern::Literal(lit.clone()),
217            ObjectPattern::Variable(var) => UnifiedTermPattern::Variable(var.clone()),
218            // Quoted-triple patterns are represented as wildcards at the unified level.
219            ObjectPattern::QuotedTriple(_) => UnifiedTermPattern::Wildcard,
220        }
221    }
222
223    /// Check if this pattern matches a subject
224    pub fn matches_subject(&self, subject: &Subject) -> bool {
225        match (self, subject) {
226            (UnifiedTermPattern::NamedNode(pn), Subject::NamedNode(sn)) => pn == sn,
227            (UnifiedTermPattern::BlankNode(pb), Subject::BlankNode(sb)) => pb == sb,
228            (UnifiedTermPattern::Variable(_), _) | (UnifiedTermPattern::Wildcard, _) => true,
229            _ => false,
230        }
231    }
232
233    /// Check if this pattern matches a predicate
234    pub fn matches_predicate(&self, predicate: &Predicate) -> bool {
235        match (self, predicate) {
236            (UnifiedTermPattern::NamedNode(pn), Predicate::NamedNode(sn)) => pn == sn,
237            (UnifiedTermPattern::Variable(_), _) | (UnifiedTermPattern::Wildcard, _) => true,
238            _ => false,
239        }
240    }
241
242    /// Check if this pattern matches an object
243    pub fn matches_object(&self, object: &Object) -> bool {
244        match (self, object) {
245            (UnifiedTermPattern::NamedNode(pn), Object::NamedNode(on)) => pn == on,
246            (UnifiedTermPattern::BlankNode(pb), Object::BlankNode(ob)) => pb == ob,
247            (UnifiedTermPattern::Literal(pl), Object::Literal(ol)) => pl == ol,
248            (UnifiedTermPattern::Variable(_), _) | (UnifiedTermPattern::Wildcard, _) => true,
249            _ => false,
250        }
251    }
252
253    /// Get selectivity factor for cost estimation
254    pub fn selectivity_factor(&self) -> f64 {
255        match self {
256            UnifiedTermPattern::NamedNode(_) => 0.001, // Very selective
257            UnifiedTermPattern::BlankNode(_) => 0.01,  // Selective
258            UnifiedTermPattern::Literal(_) => 0.001,   // Very selective
259            UnifiedTermPattern::Variable(_) => 1.0,    // Not selective
260            UnifiedTermPattern::Wildcard => 1.0,       // Not selective
261        }
262    }
263}
264
265/// Pattern conversion utilities
266pub struct PatternConverter;
267
268impl PatternConverter {
269    /// Convert a vector of algebra patterns to model patterns
270    pub fn algebra_to_model_patterns(patterns: &[AlgebraTriplePattern]) -> Vec<TriplePattern> {
271        patterns
272            .iter()
273            .map(|p| UnifiedTriplePattern::from_algebra_pattern(p).to_model_pattern())
274            .collect()
275    }
276
277    /// Convert a vector of model patterns to algebra patterns
278    pub fn model_to_algebra_patterns(
279        patterns: &[TriplePattern],
280    ) -> Result<Vec<AlgebraTriplePattern>, OxirsError> {
281        patterns
282            .iter()
283            .map(|p| UnifiedTriplePattern::from_model_pattern(p).to_algebra_pattern())
284            .collect()
285    }
286
287    /// Extract all variables from a set of algebra patterns
288    pub fn extract_variables_from_algebra(patterns: &[AlgebraTriplePattern]) -> HashSet<Variable> {
289        patterns
290            .iter()
291            .flat_map(|p| UnifiedTriplePattern::from_algebra_pattern(p).extract_variables())
292            .collect()
293    }
294
295    /// Extract all variables from a set of model patterns
296    pub fn extract_variables_from_model(patterns: &[TriplePattern]) -> HashSet<Variable> {
297        patterns
298            .iter()
299            .flat_map(|p| UnifiedTriplePattern::from_model_pattern(p).extract_variables())
300            .collect()
301    }
302
303    /// Estimate combined selectivity for a set of patterns
304    pub fn estimate_pattern_selectivity(patterns: &[UnifiedTriplePattern]) -> f64 {
305        if patterns.is_empty() {
306            return 1.0;
307        }
308
309        patterns
310            .iter()
311            .map(|p| p.selectivity_estimate())
312            .fold(1.0, |acc, s| acc * s)
313    }
314}
315
316/// Query optimization utilities using unified patterns
317pub struct PatternOptimizer;
318
319impl PatternOptimizer {
320    /// Reorder patterns for optimal execution based on selectivity
321    pub fn optimize_pattern_order(patterns: &[UnifiedTriplePattern]) -> Vec<UnifiedTriplePattern> {
322        let mut sorted_patterns = patterns.to_vec();
323
324        // Sort by selectivity (most selective first)
325        sorted_patterns.sort_by(|a, b| {
326            a.selectivity_estimate()
327                .partial_cmp(&b.selectivity_estimate())
328                .unwrap_or(std::cmp::Ordering::Equal)
329        });
330
331        sorted_patterns
332    }
333
334    /// Find optimal join order for patterns
335    pub fn optimize_join_order(patterns: &[UnifiedTriplePattern]) -> Vec<usize> {
336        if patterns.is_empty() {
337            return Vec::new();
338        }
339
340        // Simple greedy algorithm: start with most selective pattern
341        let mut remaining: Vec<usize> = (0..patterns.len()).collect();
342        let mut order = Vec::new();
343
344        // Find most selective pattern as starting point
345        if let Some(min_idx) = remaining
346            .iter()
347            .min_by(|&&a, &&b| {
348                patterns[a]
349                    .selectivity_estimate()
350                    .partial_cmp(&patterns[b].selectivity_estimate())
351                    .unwrap_or(std::cmp::Ordering::Equal)
352            })
353            .copied()
354        {
355            order.push(min_idx);
356            remaining.retain(|&x| x != min_idx);
357        }
358
359        // Greedily add patterns that share most variables with already selected patterns
360        while !remaining.is_empty() {
361            let selected_vars: HashSet<Variable> = order
362                .iter()
363                .flat_map(|&i| patterns[i].extract_variables())
364                .collect();
365
366            if let Some(best_idx) = remaining
367                .iter()
368                .max_by_key(|&&i| {
369                    let pattern_vars = patterns[i].extract_variables();
370                    pattern_vars.intersection(&selected_vars).count()
371                })
372                .copied()
373            {
374                order.push(best_idx);
375                remaining.retain(|&x| x != best_idx);
376            } else {
377                // Fallback: add remaining patterns in selectivity order
378                order.extend(remaining);
379                break;
380            }
381        }
382
383        order
384    }
385}
386
387#[cfg(test)]
388mod tests {
389    use super::*;
390
391    #[test]
392    fn test_unified_pattern_conversion() {
393        // Create an algebra pattern
394        let algebra_pattern = AlgebraTriplePattern::new(
395            AlgebraTermPattern::Variable(Variable::new("s").expect("valid variable name")),
396            AlgebraTermPattern::NamedNode(
397                NamedNode::new("http://example.org/pred").expect("valid IRI"),
398            ),
399            AlgebraTermPattern::Literal(Literal::new("test")),
400        );
401
402        // Convert to unified pattern
403        let unified = UnifiedTriplePattern::from_algebra_pattern(&algebra_pattern);
404
405        // Convert back to algebra pattern
406        let converted_back = unified
407            .to_algebra_pattern()
408            .expect("operation should succeed");
409
410        assert_eq!(algebra_pattern, converted_back);
411    }
412
413    #[test]
414    fn test_pattern_selectivity() {
415        let patterns = [
416            UnifiedTriplePattern::new(
417                UnifiedTermPattern::Variable(Variable::new("s").expect("valid variable name")),
418                UnifiedTermPattern::Variable(Variable::new("p").expect("valid variable name")),
419                UnifiedTermPattern::Variable(Variable::new("o").expect("valid variable name")),
420            ),
421            UnifiedTriplePattern::new(
422                UnifiedTermPattern::NamedNode(
423                    NamedNode::new("http://example.org/s").expect("valid IRI"),
424                ),
425                UnifiedTermPattern::NamedNode(
426                    NamedNode::new("http://example.org/p").expect("valid IRI"),
427                ),
428                UnifiedTermPattern::Variable(Variable::new("o").expect("valid variable name")),
429            ),
430        ];
431
432        // Second pattern should be more selective
433        assert!(patterns[1].selectivity_estimate() < patterns[0].selectivity_estimate());
434    }
435
436    #[test]
437    fn test_pattern_optimization() {
438        let patterns = vec![
439            UnifiedTriplePattern::new(
440                UnifiedTermPattern::Variable(Variable::new("s").expect("valid variable name")),
441                UnifiedTermPattern::Variable(Variable::new("p").expect("valid variable name")),
442                UnifiedTermPattern::Variable(Variable::new("o").expect("valid variable name")),
443            ),
444            UnifiedTriplePattern::new(
445                UnifiedTermPattern::NamedNode(
446                    NamedNode::new("http://example.org/s").expect("valid IRI"),
447                ),
448                UnifiedTermPattern::NamedNode(
449                    NamedNode::new("http://example.org/p").expect("valid IRI"),
450                ),
451                UnifiedTermPattern::Variable(Variable::new("o").expect("valid variable name")),
452            ),
453        ];
454
455        let optimized = PatternOptimizer::optimize_pattern_order(&patterns);
456
457        // More selective pattern should come first
458        assert_eq!(optimized[0], patterns[1]);
459        assert_eq!(optimized[1], patterns[0]);
460    }
461}
oxirs_core/query/pattern_unification.rs

oxirs_core/query/
pattern_unification.rs
