Even though service discovery is one of the vital steps in Web service invocation, service requests are usually expressed by rather simple means. While syntax-based service descriptions are usually addressed using keyword-based queries, Semantic Web Services are queried using “perfect” service descriptions. Hence, a service requester is not able to control the outcome of the discovery process in-depth by specifying similarity ranges or to explicitly state which syntaxand semantic-based parts of a service description should be addressed. In this paper, we present an analysis of current approaches to service request formulation and identify requirements a query formalism for Semantic Web Services should fulfill. Furthermore, we give a brief preview on SWS2QL, a SPARQL-based query language for Semantic Web Services.