Semantics and Complexity of SPARQL

Paper by Pérez, Arenas and Gutiérrez giving SPARQL a compositional formal semantics and proving the complexity of evaluating it; general SPARQL patterns are PSPACE-complete.