The success of the Web Service (WS) paradigm has led to a proliferation of available WSs, which are advertised in WS registries. While sophisticated semantic WS discovery algorithms are operating on these registries to return matchmaking results with high precision and recall, many functionally-equivalent WSs are returned. The solution to the above problem comes in terms of semantic QoS-based description and discovery of WSs. We have already presented a rich and extensible ontology language for QoS-based WS description called OWL-Q. We have also proposed a semantic QoS metric matching algorithm. Based on this algorithm, we have extended a CSP-based approach for QoS-based WS discovery. In this paper, we firstly analyze the evolution of OWL-Q and its extension with SWRL rules, we propose a modification to the metric matching algorithm and we show the way the metric alignment process takes place. Then we propose two novel semantic QoS-based WS Discovery algorithms that return matches even for over-constrained QoS-based WS requests. The first one deals with unary constraints while the second one is more generic. Finally, implementa- tion aspects of our QoS-based WS discovery system are discussed.