This paper systematically studies the formal semantics of SPARQL, focusing on its graph pattern facility. The authors present a compositional semantics, prove the existence of normal forms, and analyze the computational complexity of evaluating SPARQL patterns. They show that the evaluation of a general graph pattern in SPARQL is PSPACE-complete, even without considering filter conditions. The paper also compares a compositional semantics with an alternative procedural semantics used by developers, demonstrating that they coincide under certain syntactic restrictions. Additionally, the authors discuss optimization procedures and provide a detailed analysis of UNION-free graph pattern expressions. The paper concludes with a discussion on the implications of these findings for the standardization of SPARQL and the extension of its capabilities to RDF Schema.This paper systematically studies the formal semantics of SPARQL, focusing on its graph pattern facility. The authors present a compositional semantics, prove the existence of normal forms, and analyze the computational complexity of evaluating SPARQL patterns. They show that the evaluation of a general graph pattern in SPARQL is PSPACE-complete, even without considering filter conditions. The paper also compares a compositional semantics with an alternative procedural semantics used by developers, demonstrating that they coincide under certain syntactic restrictions. Additionally, the authors discuss optimization procedures and provide a detailed analysis of UNION-free graph pattern expressions. The paper concludes with a discussion on the implications of these findings for the standardization of SPARQL and the extension of its capabilities to RDF Schema.