This paper presents a formal study of the semantics and complexity of SPARQL, a query language for RDF. The authors focus on the graph pattern facility of SPARQL, considering a fragment without literals and a simple version of filters. They provide a compositional semantics, prove the existence of normal forms, and analyze the computational complexity of SPARQL patterns. They show that the evaluation of SPARQL patterns is PSPACE-complete, even without filter conditions. The paper compares two semantics: an operational and a compositional one, and identifies conditions under which they coincide. It also discusses optimization procedures for SPARQL queries. SPARQL is a graph-matching query language that allows querying RDF data by matching patterns against a dataset. The query consists of a pattern matching part, solution modifiers, and an output type. The complexity of SPARQL arises from the combination of its features, making its semantics challenging to define. The current semantics in the SPARQL specification is incomplete and ambiguous. The authors isolate a core fragment of SPARQL that is simple enough for formal analysis but expressive enough to capture the core complexities of the language. They define a formal semantics for this fragment, prove that it is PSPACE-complete, and show that under certain syntactic restrictions, the operational and compositional semantics coincide. They also discuss the complexity of evaluating graph pattern expressions and show that the inclusion of the UNION operator increases the complexity to NP-complete, while the inclusion of the OPT operator makes it PSPACE-complete. The paper also addresses the semantics of UNION-free pattern expressions, showing that the depth-first approach and the compositional approach can yield different results. However, under certain conditions, these approaches coincide. The authors introduce a natural condition ensuring that the compositional and depth-first semantics are equivalent, and show that well-designed patterns can be normalized into a specific form that facilitates optimization. The paper concludes that a formal semantics for SPARQL is essential for understanding its complexity, expressiveness, and for developing efficient query optimization techniques. The authors also highlight the importance of normalization and optimization in the context of SPARQL.This paper presents a formal study of the semantics and complexity of SPARQL, a query language for RDF. The authors focus on the graph pattern facility of SPARQL, considering a fragment without literals and a simple version of filters. They provide a compositional semantics, prove the existence of normal forms, and analyze the computational complexity of SPARQL patterns. They show that the evaluation of SPARQL patterns is PSPACE-complete, even without filter conditions. The paper compares two semantics: an operational and a compositional one, and identifies conditions under which they coincide. It also discusses optimization procedures for SPARQL queries. SPARQL is a graph-matching query language that allows querying RDF data by matching patterns against a dataset. The query consists of a pattern matching part, solution modifiers, and an output type. The complexity of SPARQL arises from the combination of its features, making its semantics challenging to define. The current semantics in the SPARQL specification is incomplete and ambiguous. The authors isolate a core fragment of SPARQL that is simple enough for formal analysis but expressive enough to capture the core complexities of the language. They define a formal semantics for this fragment, prove that it is PSPACE-complete, and show that under certain syntactic restrictions, the operational and compositional semantics coincide. They also discuss the complexity of evaluating graph pattern expressions and show that the inclusion of the UNION operator increases the complexity to NP-complete, while the inclusion of the OPT operator makes it PSPACE-complete. The paper also addresses the semantics of UNION-free pattern expressions, showing that the depth-first approach and the compositional approach can yield different results. However, under certain conditions, these approaches coincide. The authors introduce a natural condition ensuring that the compositional and depth-first semantics are equivalent, and show that well-designed patterns can be normalized into a specific form that facilitates optimization. The paper concludes that a formal semantics for SPARQL is essential for understanding its complexity, expressiveness, and for developing efficient query optimization techniques. The authors also highlight the importance of normalization and optimization in the context of SPARQL.