The goal of Service Oriented Architectures is to enable the creation of business applications through the automatic discovery and composition of independently developed and deployed (Web) services. Automatic discovery of Web Services (WSs) can be achieved by incorporating semantics into a richer WS description model (WSDM) and the use of Semantic Web (SW) technologies in the WS matchmaking and selection models. A sufficiently rich WSDM should encompass not only functional but also non-functional aspects like Quality of Service (QoS). QoS is a set of performance attributes that has a substantial impact on WS requesters' expectations. Thus, it can be used as a discriminating factor of functionally-equivalent WSs. The focus of this paper is twofold: to analyze the requirements of a semantically rich QoS-based WSDM and to provide SW and constrainedbased mechanisms for enriching syntactic QoS-based WS Discovery (WSDi) algorithms. In addition, a roadmap of extending WS standard techniques for realizing semantic, functional and QoS-based WSDi is presented.