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        };
234
235        let predicate = match pattern.predicate? {
236            PredicatePattern::NamedNode(n) => TermPattern::NamedNode(n),
237            PredicatePattern::Variable(v) => TermPattern::Variable(v),
238        };
239
240        let object = match pattern.object? {
241            ObjectPattern::NamedNode(n) => TermPattern::NamedNode(n),
242            ObjectPattern::BlankNode(b) => TermPattern::BlankNode(b),
243            ObjectPattern::Literal(l) => TermPattern::Literal(l),
244            ObjectPattern::Variable(v) => TermPattern::Variable(v),
245        };
246
247        Some(AlgebraTriplePattern::new(subject, predicate, object))
248    }
249}
250
251/// A term pattern (can be a concrete term or variable)
252#[derive(Debug, Clone, PartialEq, Eq, Hash, Serialize, Deserialize)]
253pub enum TermPattern {
254    NamedNode(NamedNode),
255    BlankNode(BlankNode),
256    Literal(Literal),
257    Variable(Variable),
258}
259
260impl From<Variable> for TermPattern {
261    fn from(v: Variable) -> Self {
262        TermPattern::Variable(v)
263    }
264}
265
266impl From<NamedNode> for TermPattern {
267    fn from(n: NamedNode) -> Self {
268        TermPattern::NamedNode(n)
269    }
270}
271
272impl From<BlankNode> for TermPattern {
273    fn from(b: BlankNode) -> Self {
274        TermPattern::BlankNode(b)
275    }
276}
277
278impl From<Literal> for TermPattern {
279    fn from(l: Literal) -> Self {
280        TermPattern::Literal(l)
281    }
282}
283
284impl TermPattern {
285    /// Check if this pattern is a variable
286    pub fn is_variable(&self) -> bool {
287        matches!(self, TermPattern::Variable(_))
288    }
289
290    /// Formats using the SPARQL S-Expression syntax
291    pub fn fmt_sse(&self, f: &mut impl fmt::Write) -> fmt::Result {
292        match self {
293            TermPattern::NamedNode(node) => write!(f, "{node}"),
294            TermPattern::BlankNode(node) => write!(f, "{node}"),
295            TermPattern::Literal(literal) => write!(f, "{literal}"),
296            TermPattern::Variable(var) => write!(f, "{var}"),
297        }
298    }
299}
300
301impl fmt::Display for TermPattern {
302    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
303        match self {
304            TermPattern::NamedNode(n) => write!(f, "{n}"),
305            TermPattern::BlankNode(b) => write!(f, "{b}"),
306            TermPattern::Literal(l) => write!(f, "{l}"),
307            TermPattern::Variable(v) => write!(f, "{v}"),
308        }
309    }
310}
311
312/// A graph pattern
313#[derive(Debug, Clone, PartialEq, Serialize, Deserialize)]
314pub enum GraphPattern {
315    /// Basic graph pattern (set of triple patterns)
316    Bgp(Vec<AlgebraTriplePattern>),
317    /// Path pattern
318    Path {
319        subject: TermPattern,
320        path: PropertyPath,
321        object: TermPattern,
322    },
323    /// Join of two patterns
324    Join(Box<GraphPattern>, Box<GraphPattern>),
325    /// Left join (OPTIONAL)
326    LeftJoin {
327        left: Box<GraphPattern>,
328        right: Box<GraphPattern>,
329        condition: Option<Expression>,
330    },
331    /// Filter pattern
332    Filter {
333        expr: Expression,
334        inner: Box<GraphPattern>,
335    },
336    /// Union of patterns
337    Union(Box<GraphPattern>, Box<GraphPattern>),
338    /// Graph pattern (GRAPH)
339    Graph {
340        graph_name: TermPattern,
341        inner: Box<GraphPattern>,
342    },
343    /// Service pattern (federated query)
344    Service {
345        service: TermPattern,
346        inner: Box<GraphPattern>,
347        silent: bool,
348    },
349    /// Group pattern
350    Group {
351        inner: Box<GraphPattern>,
352        variables: Vec<Variable>,
353        aggregates: Vec<(Variable, AggregateExpression)>,
354    },
355    /// Extend pattern (BIND)
356    Extend {
357        inner: Box<GraphPattern>,
358        variable: Variable,
359        expression: Expression,
360    },
361    /// Minus pattern
362    Minus(Box<GraphPattern>, Box<GraphPattern>),
363    /// Values pattern
364    Values {
365        variables: Vec<Variable>,
366        bindings: Vec<Vec<Option<Term>>>,
367    },
368    /// Order by pattern
369    OrderBy {
370        inner: Box<GraphPattern>,
371        order_by: Vec<OrderExpression>,
372    },
373    /// Project pattern
374    Project {
375        inner: Box<GraphPattern>,
376        variables: Vec<Variable>,
377    },
378    /// Distinct pattern
379    Distinct(Box<GraphPattern>),
380    /// Reduced pattern
381    Reduced(Box<GraphPattern>),
382    /// Slice pattern (LIMIT/OFFSET)
383    Slice {
384        inner: Box<GraphPattern>,
385        offset: usize,
386        limit: Option<usize>,
387    },
388}
389
390/// Aggregate expressions
391#[derive(Debug, Clone, PartialEq, Serialize, Deserialize)]
392pub enum AggregateExpression {
393    Count {
394        expr: Option<Box<Expression>>,
395        distinct: bool,
396    },
397    Sum {
398        expr: Box<Expression>,
399        distinct: bool,
400    },
401    Avg {
402        expr: Box<Expression>,
403        distinct: bool,
404    },
405    Min {
406        expr: Box<Expression>,
407        distinct: bool,
408    },
409    Max {
410        expr: Box<Expression>,
411        distinct: bool,
412    },
413    GroupConcat {
414        expr: Box<Expression>,
415        distinct: bool,
416        separator: Option<String>,
417    },
418    Sample {
419        expr: Box<Expression>,
420        distinct: bool,
421    },
422}
423
424/// Order expression for ORDER BY
425#[derive(Debug, Clone, PartialEq, Serialize, Deserialize)]
426pub enum OrderExpression {
427    Asc(Expression),
428    Desc(Expression),
429}
430
431/// SPARQL query forms
432#[derive(Debug, Clone, PartialEq, Serialize, Deserialize)]
433pub enum QueryForm {
434    /// SELECT query
435    Select {
436        /// SELECT * or specific variables
437        variables: SelectVariables,
438        /// WHERE clause pattern
439        where_clause: GraphPattern,
440        /// Solution modifiers
441        distinct: bool,
442        reduced: bool,
443        order_by: Vec<OrderExpression>,
444        offset: usize,
445        limit: Option<usize>,
446    },
447    /// CONSTRUCT query
448    Construct {
449        /// Template for constructing triples
450        template: Vec<AlgebraTriplePattern>,
451        /// WHERE clause pattern
452        where_clause: GraphPattern,
453        /// Solution modifiers
454        order_by: Vec<OrderExpression>,
455        offset: usize,
456        limit: Option<usize>,
457    },
458    /// DESCRIBE query
459    Describe {
460        /// Resources to describe
461        resources: Vec<TermPattern>,
462        /// Optional WHERE clause
463        where_clause: Option<GraphPattern>,
464        /// Solution modifiers
465        order_by: Vec<OrderExpression>,
466        offset: usize,
467        limit: Option<usize>,
468    },
469    /// ASK query
470    Ask {
471        /// Pattern to check
472        where_clause: GraphPattern,
473    },
474}
475
476/// Variables selection in SELECT
477#[derive(Debug, Clone, PartialEq, Serialize, Deserialize)]
478pub enum SelectVariables {
479    /// SELECT *
480    All,
481    /// SELECT ?var1 ?var2 ...
482    Specific(Vec<Variable>),
483}
484
485/// A complete SPARQL query
486#[derive(Debug, Clone, PartialEq, Serialize, Deserialize)]
487pub struct Query {
488    /// Base IRI for relative IRI resolution
489    pub base: Option<NamedNode>,
490    /// Namespace prefixes
491    pub prefixes: HashMap<String, NamedNode>,
492    /// Query form
493    pub form: QueryForm,
494    /// Dataset specification
495    pub dataset: Dataset,
496}
497
498/// Dataset specification for a query
499#[derive(Debug, Clone, PartialEq, Default, Serialize, Deserialize)]
500pub struct Dataset {
501    /// Default graph IRIs (FROM)
502    pub default: Vec<NamedNode>,
503    /// Named graph IRIs (FROM NAMED)
504    pub named: Vec<NamedNode>,
505}
506
507/// SPARQL Update operations
508#[derive(Debug, Clone, PartialEq, Serialize, Deserialize)]
509pub enum UpdateOperation {
510    /// INSERT DATA
511    InsertData { data: Vec<Quad> },
512    /// DELETE DATA
513    DeleteData { data: Vec<Quad> },
514    /// DELETE WHERE
515    DeleteWhere { pattern: Vec<QuadPattern> },
516    /// INSERT/DELETE with WHERE
517    Modify {
518        delete: Option<Vec<QuadPattern>>,
519        insert: Option<Vec<QuadPattern>>,
520        where_clause: Box<GraphPattern>,
521        using: Dataset,
522    },
523    /// LOAD
524    Load {
525        source: NamedNode,
526        destination: Option<NamedNode>,
527        silent: bool,
528    },
529    /// CLEAR
530    Clear { graph: GraphTarget, silent: bool },
531    /// CREATE
532    Create { graph: NamedNode, silent: bool },
533    /// DROP
534    Drop { graph: GraphTarget, silent: bool },
535    /// COPY
536    Copy {
537        source: GraphTarget,
538        destination: GraphTarget,
539        silent: bool,
540    },
541    /// MOVE
542    Move {
543        source: GraphTarget,
544        destination: GraphTarget,
545        silent: bool,
546    },
547    /// ADD
548    Add {
549        source: GraphTarget,
550        destination: GraphTarget,
551        silent: bool,
552    },
553}
554
555/// Graph targets for update operations
556#[derive(Debug, Clone, PartialEq, Eq, Hash, Serialize, Deserialize)]
557pub enum GraphTarget {
558    Default,
559    Named(NamedNode),
560    All,
561}
562
563/// Quad pattern for updates
564#[derive(Debug, Clone, PartialEq, Eq, Hash, Serialize, Deserialize)]
565pub struct QuadPattern {
566    pub subject: TermPattern,
567    pub predicate: TermPattern,
568    pub object: TermPattern,
569    pub graph: Option<TermPattern>,
570}
571
572/// A SPARQL Update request
573#[derive(Debug, Clone, PartialEq, Serialize, Deserialize)]
574pub struct Update {
575    /// Base IRI for relative IRI resolution
576    pub base: Option<NamedNode>,
577    /// Namespace prefixes
578    pub prefixes: HashMap<String, NamedNode>,
579    /// Update operations
580    pub operations: Vec<UpdateOperation>,
581}
oxirs_core/query/algebra.rs

oxirs_core/query/
algebra.rs
