Industry has recently recognised the need for additional descriptions ofWeb services beyond those provided by WSDL documents and tModels in UDDI. These descriptions should facilitate discovery, integration and composition ofWeb services in a more ef cient way than supported currently. This need sheds light to the progress on Semantic Web services as provided by initiatives like WSMO and OWL-S. By now many methods have been proposed for composing Web services automatically from existing OWLS and WSML-like Web service descriptions. The methods range from AI planning to automated theorem proving and graph search algorithms. However, the usability of these methods is greatly affected by two constraints. Firstly, it is assumed that developers provide consistent declarative descriptions of Web services. Secondly, it is assumed that there exists a universal set of atomicWeb services, which would facilitate the composition of all otherWeb services. In this paper we are going to tackle these two issues. We apply partial deduction for identifying potential inconsistencies in Web service descriptions. Our method also determines atomic Web services, which should be implemented in order to compose a required composite Web service.