oxirs_core/query/
algebra.rs

1//! SPARQL 1.1 Query Algebra representation
2//!
3//! Based on the W3C SPARQL 1.1 Query specification:
4//! <https://www.w3.org/TR/sparql11-query/#sparqlQuery>
5
6use crate::model::*;
7use serde::{Deserialize, Serialize};
8use std::collections::HashMap;
9use std::fmt;
10
11// Re-export TriplePattern from model for public access
12pub use crate::model::pattern::TriplePattern;
13
14/// A property path expression for navigating RDF graphs
15#[derive(Debug, Clone, PartialEq, Eq, Hash, Serialize, Deserialize)]
16pub enum PropertyPath {
17    /// A simple predicate path
18    Predicate(NamedNode),
19    /// Inverse path: ^path
20    Inverse(Box<PropertyPath>),
21    /// Sequence path: path1 / path2
22    Sequence(Box<PropertyPath>, Box<PropertyPath>),
23    /// Alternative path: path1 | path2
24    Alternative(Box<PropertyPath>, Box<PropertyPath>),
25    /// Zero or more: path*
26    ZeroOrMore(Box<PropertyPath>),
27    /// One or more: path+
28    OneOrMore(Box<PropertyPath>),
29    /// Zero or one: path?
30    ZeroOrOne(Box<PropertyPath>),
31    /// Negated property set: !(p1 | p2 | ...)
32    NegatedPropertySet(Vec<NamedNode>),
33}
34
35impl fmt::Display for PropertyPath {
36    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
37        match self {
38            PropertyPath::Predicate(p) => write!(f, "{p}"),
39            PropertyPath::Inverse(p) => write!(f, "^{p}"),
40            PropertyPath::Sequence(a, b) => write!(f, "({a} / {b})"),
41            PropertyPath::Alternative(a, b) => write!(f, "({a} | {b})"),
42            PropertyPath::ZeroOrMore(p) => write!(f, "({p})*"),
43            PropertyPath::OneOrMore(p) => write!(f, "({p})+"),
44            PropertyPath::ZeroOrOne(p) => write!(f, "({p})?"),
45            PropertyPath::NegatedPropertySet(ps) => {
46                write!(f, "!(")?;
47                for (i, p) in ps.iter().enumerate() {
48                    if i > 0 {
49                        write!(f, " | ")?;
50                    }
51                    write!(f, "{p}")?;
52                }
53                write!(f, ")")
54            }
55        }
56    }
57}
58
59/// A SPARQL expression
60#[derive(Debug, Clone, PartialEq, Serialize, Deserialize)]
61pub enum Expression {
62    /// A constant term
63    Term(Term),
64    /// A variable
65    Variable(Variable),
66    /// Logical AND
67    And(Box<Expression>, Box<Expression>),
68    /// Logical OR
69    Or(Box<Expression>, Box<Expression>),
70    /// Logical NOT
71    Not(Box<Expression>),
72    /// Equality: =
73    Equal(Box<Expression>, Box<Expression>),
74    /// Inequality: !=
75    NotEqual(Box<Expression>, Box<Expression>),
76    /// Less than: <
77    Less(Box<Expression>, Box<Expression>),
78    /// Less than or equal: <=
79    LessOrEqual(Box<Expression>, Box<Expression>),
80    /// Greater than: >
81    Greater(Box<Expression>, Box<Expression>),
82    /// Greater than or equal: >=
83    GreaterOrEqual(Box<Expression>, Box<Expression>),
84    /// Addition: +
85    Add(Box<Expression>, Box<Expression>),
86    /// Subtraction: -
87    Subtract(Box<Expression>, Box<Expression>),
88    /// Multiplication: *
89    Multiply(Box<Expression>, Box<Expression>),
90    /// Division: /
91    Divide(Box<Expression>, Box<Expression>),
92    /// Unary plus: +expr
93    UnaryPlus(Box<Expression>),
94    /// Unary minus: -expr
95    UnaryMinus(Box<Expression>),
96    /// IN expression
97    In(Box<Expression>, Vec<Expression>),
98    /// NOT IN expression
99    NotIn(Box<Expression>, Vec<Expression>),
100    /// EXISTS pattern
101    Exists(Box<GraphPattern>),
102    /// NOT EXISTS pattern
103    NotExists(Box<GraphPattern>),
104    /// Function call
105    FunctionCall(Function, Vec<Expression>),
106    /// Bound variable test
107    Bound(Variable),
108    /// IF expression
109    If(Box<Expression>, Box<Expression>, Box<Expression>),
110    /// COALESCE expression
111    Coalesce(Vec<Expression>),
112    /// Literal value
113    Literal(crate::model::Literal),
114    /// Test if term is IRI
115    IsIri(Box<Expression>),
116    /// Test if term is blank node
117    IsBlank(Box<Expression>),
118    /// Test if term is literal
119    IsLiteral(Box<Expression>),
120    /// Test if term is numeric
121    IsNumeric(Box<Expression>),
122    /// String value of term
123    Str(Box<Expression>),
124    /// Regular expression matching
125    Regex(Box<Expression>, Box<Expression>, Option<Box<Expression>>),
126}
127
128/// Built-in SPARQL functions
129#[derive(Debug, Clone, PartialEq, Eq, Hash, Serialize, Deserialize)]
130pub enum Function {
131    // String functions
132    Str,
133    Lang,
134    LangMatches,
135    Datatype,
136    Iri,
137    Bnode,
138    StrDt,
139    StrLang,
140    StrLen,
141    SubStr,
142    UCase,
143    LCase,
144    StrStarts,
145    StrEnds,
146    Contains,
147    StrBefore,
148    StrAfter,
149    Encode,
150    Concat,
151    Replace,
152    Regex,
153
154    // Numeric functions
155    Abs,
156    Round,
157    Ceil,
158    Floor,
159    Rand,
160
161    // Date/Time functions
162    Now,
163    Year,
164    Month,
165    Day,
166    Hours,
167    Minutes,
168    Seconds,
169    Timezone,
170    Tz,
171
172    // Hash functions
173    Md5,
174    Sha1,
175    Sha256,
176    Sha384,
177    Sha512,
178
179    // Type checking
180    IsIri,
181    IsBlank,
182    IsLiteral,
183    IsNumeric,
184
185    // Custom function
186    Custom(NamedNode),
187}
188
189/// A triple pattern in SPARQL algebra (all positions must be specified)
190#[derive(Debug, Clone, PartialEq, Eq, Hash, Serialize, Deserialize)]
191pub struct AlgebraTriplePattern {
192    pub subject: TermPattern,
193    pub predicate: TermPattern,
194    pub object: TermPattern,
195}
196
197impl AlgebraTriplePattern {
198    /// Create a new algebra triple pattern
199    pub fn new(subject: TermPattern, predicate: TermPattern, object: TermPattern) -> Self {
200        Self {
201            subject,
202            predicate,
203            object,
204        }
205    }
206
207    /// Formats using the SPARQL S-Expression syntax
208    pub fn fmt_sse(&self, f: &mut impl fmt::Write) -> fmt::Result {
209        f.write_str("(triple ")?;
210        self.subject.fmt_sse(f)?;
211        f.write_str(" ")?;
212        self.predicate.fmt_sse(f)?;
213        f.write_str(" ")?;
214        self.object.fmt_sse(f)?;
215        f.write_str(")")
216    }
217}
218
219impl fmt::Display for AlgebraTriplePattern {
220    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
221        write!(f, "{} {} {}", self.subject, self.predicate, self.object)
222    }
223}
224
225impl From<crate::model::pattern::TriplePattern> for Option<AlgebraTriplePattern> {
226    fn from(pattern: crate::model::pattern::TriplePattern) -> Self {
227        use crate::model::pattern::{ObjectPattern, PredicatePattern, SubjectPattern};
228
229        let subject = match pattern.subject? {
230            SubjectPattern::NamedNode(n) => TermPattern::NamedNode(n),
231            SubjectPattern::BlankNode(b) => TermPattern::BlankNode(b),
232            SubjectPattern::Variable(v) => TermPattern::Variable(v),
233            SubjectPattern::QuotedTriple(qt) => TermPattern::QuotedTriple(qt),
234        };
235
236        let predicate = match pattern.predicate? {
237            PredicatePattern::NamedNode(n) => TermPattern::NamedNode(n),
238            PredicatePattern::Variable(v) => TermPattern::Variable(v),
239        };
240
241        let object = match pattern.object? {
242            ObjectPattern::NamedNode(n) => TermPattern::NamedNode(n),
243            ObjectPattern::BlankNode(b) => TermPattern::BlankNode(b),
244            ObjectPattern::Literal(l) => TermPattern::Literal(l),
245            ObjectPattern::Variable(v) => TermPattern::Variable(v),
246            ObjectPattern::QuotedTriple(qt) => TermPattern::QuotedTriple(qt),
247        };
248
249        Some(AlgebraTriplePattern::new(subject, predicate, object))
250    }
251}
252
253/// A term pattern (can be a concrete term or variable)
254#[derive(Debug, Clone, PartialEq, Eq, Hash, Serialize, Deserialize)]
255pub enum TermPattern {
256    NamedNode(NamedNode),
257    BlankNode(BlankNode),
258    Literal(Literal),
259    Variable(Variable),
260    /// Quoted triple pattern for RDF-star support
261    QuotedTriple(Box<AlgebraTriplePattern>),
262}
263
264impl From<Variable> for TermPattern {
265    fn from(v: Variable) -> Self {
266        TermPattern::Variable(v)
267    }
268}
269
270impl From<NamedNode> for TermPattern {
271    fn from(n: NamedNode) -> Self {
272        TermPattern::NamedNode(n)
273    }
274}
275
276impl From<BlankNode> for TermPattern {
277    fn from(b: BlankNode) -> Self {
278        TermPattern::BlankNode(b)
279    }
280}
281
282impl From<Literal> for TermPattern {
283    fn from(l: Literal) -> Self {
284        TermPattern::Literal(l)
285    }
286}
287
288impl TermPattern {
289    /// Check if this pattern is a variable
290    pub fn is_variable(&self) -> bool {
291        matches!(self, TermPattern::Variable(_))
292    }
293
294    /// Formats using the SPARQL S-Expression syntax
295    pub fn fmt_sse(&self, f: &mut impl fmt::Write) -> fmt::Result {
296        match self {
297            TermPattern::NamedNode(node) => write!(f, "{node}"),
298            TermPattern::BlankNode(node) => write!(f, "{node}"),
299            TermPattern::Literal(literal) => write!(f, "{literal}"),
300            TermPattern::Variable(var) => write!(f, "{var}"),
301            TermPattern::QuotedTriple(triple) => {
302                write!(f, "<<")?;
303                triple.subject.fmt_sse(f)?;
304                write!(f, " ")?;
305                triple.predicate.fmt_sse(f)?;
306                write!(f, " ")?;
307                triple.object.fmt_sse(f)?;
308                write!(f, ">>")
309            }
310        }
311    }
312}
313
314impl fmt::Display for TermPattern {
315    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
316        match self {
317            TermPattern::NamedNode(n) => write!(f, "{n}"),
318            TermPattern::BlankNode(b) => write!(f, "{b}"),
319            TermPattern::Literal(l) => write!(f, "{l}"),
320            TermPattern::Variable(v) => write!(f, "{v}"),
321            TermPattern::QuotedTriple(triple) => {
322                write!(
323                    f,
324                    "<<{} {} {}>>",
325                    triple.subject, triple.predicate, triple.object
326                )
327            }
328        }
329    }
330}
331
332/// A graph pattern
333#[derive(Debug, Clone, PartialEq, Serialize, Deserialize)]
334pub enum GraphPattern {
335    /// Basic graph pattern (set of triple patterns)
336    Bgp(Vec<AlgebraTriplePattern>),
337    /// Path pattern
338    Path {
339        subject: TermPattern,
340        path: PropertyPath,
341        object: TermPattern,
342    },
343    /// Join of two patterns
344    Join(Box<GraphPattern>, Box<GraphPattern>),
345    /// Left join (OPTIONAL)
346    LeftJoin {
347        left: Box<GraphPattern>,
348        right: Box<GraphPattern>,
349        condition: Option<Expression>,
350    },
351    /// Filter pattern
352    Filter {
353        expr: Expression,
354        inner: Box<GraphPattern>,
355    },
356    /// Union of patterns
357    Union(Box<GraphPattern>, Box<GraphPattern>),
358    /// Graph pattern (GRAPH)
359    Graph {
360        graph_name: TermPattern,
361        inner: Box<GraphPattern>,
362    },
363    /// Service pattern (federated query)
364    Service {
365        service: TermPattern,
366        inner: Box<GraphPattern>,
367        silent: bool,
368    },
369    /// Group pattern
370    Group {
371        inner: Box<GraphPattern>,
372        variables: Vec<Variable>,
373        aggregates: Vec<(Variable, AggregateExpression)>,
374    },
375    /// Extend pattern (BIND)
376    Extend {
377        inner: Box<GraphPattern>,
378        variable: Variable,
379        expression: Expression,
380    },
381    /// Minus pattern
382    Minus(Box<GraphPattern>, Box<GraphPattern>),
383    /// Values pattern
384    Values {
385        variables: Vec<Variable>,
386        bindings: Vec<Vec<Option<Term>>>,
387    },
388    /// Order by pattern
389    OrderBy {
390        inner: Box<GraphPattern>,
391        order_by: Vec<OrderExpression>,
392    },
393    /// Project pattern
394    Project {
395        inner: Box<GraphPattern>,
396        variables: Vec<Variable>,
397    },
398    /// Distinct pattern
399    Distinct(Box<GraphPattern>),
400    /// Reduced pattern
401    Reduced(Box<GraphPattern>),
402    /// Slice pattern (LIMIT/OFFSET)
403    Slice {
404        inner: Box<GraphPattern>,
405        offset: usize,
406        limit: Option<usize>,
407    },
408}
409
410/// Aggregate expressions
411#[derive(Debug, Clone, PartialEq, Serialize, Deserialize)]
412pub enum AggregateExpression {
413    Count {
414        expr: Option<Box<Expression>>,
415        distinct: bool,
416    },
417    Sum {
418        expr: Box<Expression>,
419        distinct: bool,
420    },
421    Avg {
422        expr: Box<Expression>,
423        distinct: bool,
424    },
425    Min {
426        expr: Box<Expression>,
427        distinct: bool,
428    },
429    Max {
430        expr: Box<Expression>,
431        distinct: bool,
432    },
433    GroupConcat {
434        expr: Box<Expression>,
435        distinct: bool,
436        separator: Option<String>,
437    },
438    Sample {
439        expr: Box<Expression>,
440        distinct: bool,
441    },
442}
443
444/// Order expression for ORDER BY
445#[derive(Debug, Clone, PartialEq, Serialize, Deserialize)]
446pub enum OrderExpression {
447    Asc(Expression),
448    Desc(Expression),
449}
450
451/// SPARQL query forms
452#[derive(Debug, Clone, PartialEq, Serialize, Deserialize)]
453pub enum QueryForm {
454    /// SELECT query
455    Select {
456        /// SELECT * or specific variables
457        variables: SelectVariables,
458        /// WHERE clause pattern
459        where_clause: GraphPattern,
460        /// Solution modifiers
461        distinct: bool,
462        reduced: bool,
463        order_by: Vec<OrderExpression>,
464        offset: usize,
465        limit: Option<usize>,
466    },
467    /// CONSTRUCT query
468    Construct {
469        /// Template for constructing triples
470        template: Vec<AlgebraTriplePattern>,
471        /// WHERE clause pattern
472        where_clause: GraphPattern,
473        /// Solution modifiers
474        order_by: Vec<OrderExpression>,
475        offset: usize,
476        limit: Option<usize>,
477    },
478    /// DESCRIBE query
479    Describe {
480        /// Resources to describe
481        resources: Vec<TermPattern>,
482        /// Optional WHERE clause
483        where_clause: Option<GraphPattern>,
484        /// Solution modifiers
485        order_by: Vec<OrderExpression>,
486        offset: usize,
487        limit: Option<usize>,
488    },
489    /// ASK query
490    Ask {
491        /// Pattern to check
492        where_clause: GraphPattern,
493    },
494}
495
496/// Variables selection in SELECT
497#[derive(Debug, Clone, PartialEq, Serialize, Deserialize)]
498pub enum SelectVariables {
499    /// SELECT *
500    All,
501    /// SELECT ?var1 ?var2 ...
502    Specific(Vec<Variable>),
503}
504
505/// A complete SPARQL query
506#[derive(Debug, Clone, PartialEq, Serialize, Deserialize)]
507pub struct Query {
508    /// Base IRI for relative IRI resolution
509    pub base: Option<NamedNode>,
510    /// Namespace prefixes
511    pub prefixes: HashMap<String, NamedNode>,
512    /// Query form
513    pub form: QueryForm,
514    /// Dataset specification
515    pub dataset: Dataset,
516}
517
518/// Dataset specification for a query
519#[derive(Debug, Clone, PartialEq, Default, Serialize, Deserialize)]
520pub struct Dataset {
521    /// Default graph IRIs (FROM)
522    pub default: Vec<NamedNode>,
523    /// Named graph IRIs (FROM NAMED)
524    pub named: Vec<NamedNode>,
525}
526
527/// SPARQL Update operations
528#[derive(Debug, Clone, PartialEq, Serialize, Deserialize)]
529pub enum UpdateOperation {
530    /// INSERT DATA
531    InsertData { data: Vec<Quad> },
532    /// DELETE DATA
533    DeleteData { data: Vec<Quad> },
534    /// DELETE WHERE
535    DeleteWhere { pattern: Vec<QuadPattern> },
536    /// INSERT/DELETE with WHERE
537    Modify {
538        delete: Option<Vec<QuadPattern>>,
539        insert: Option<Vec<QuadPattern>>,
540        where_clause: Box<GraphPattern>,
541        using: Dataset,
542    },
543    /// LOAD
544    Load {
545        source: NamedNode,
546        destination: Option<NamedNode>,
547        silent: bool,
548    },
549    /// CLEAR
550    Clear { graph: GraphTarget, silent: bool },
551    /// CREATE
552    Create { graph: NamedNode, silent: bool },
553    /// DROP
554    Drop { graph: GraphTarget, silent: bool },
555    /// COPY
556    Copy {
557        source: GraphTarget,
558        destination: GraphTarget,
559        silent: bool,
560    },
561    /// MOVE
562    Move {
563        source: GraphTarget,
564        destination: GraphTarget,
565        silent: bool,
566    },
567    /// ADD
568    Add {
569        source: GraphTarget,
570        destination: GraphTarget,
571        silent: bool,
572    },
573}
574
575/// Graph targets for update operations
576#[derive(Debug, Clone, PartialEq, Eq, Hash, Serialize, Deserialize)]
577pub enum GraphTarget {
578    Default,
579    Named(NamedNode),
580    All,
581}
582
583/// Quad pattern for updates
584#[derive(Debug, Clone, PartialEq, Eq, Hash, Serialize, Deserialize)]
585pub struct QuadPattern {
586    pub subject: TermPattern,
587    pub predicate: TermPattern,
588    pub object: TermPattern,
589    pub graph: Option<TermPattern>,
590}
591
592/// A SPARQL Update request
593#[derive(Debug, Clone, PartialEq, Serialize, Deserialize)]
594pub struct Update {
595    /// Base IRI for relative IRI resolution
596    pub base: Option<NamedNode>,
597    /// Namespace prefixes
598    pub prefixes: HashMap<String, NamedNode>,
599    /// Update operations
600    pub operations: Vec<UpdateOperation>,
601}
oxirs_core/query/algebra.rs

oxirs_core/query/
algebra.rs
