Automated discovery and composition of Web services and the representation of service semantics required to automate these tasks are active research areas that play a large role in current work on service oriented architectures. In this paper, we investigate the feasibility of service composition powered by a consistency-based approach for candidate selection during composition. The modeling restraints imposed by the existing proposals for candidate selection often result in undesired implications in the form of unintuitive candidates during composition. We formulate a consistency-based candidate selection procedure, which uses specifications based on classical software engineering notations (UML and OCL), and use the selection procedure within a configuration based web service composition setting. The consistency-based matchmaking technique is robust in handling overspecified profiles, assumes a closed world by default and provides provisions to include ?nonexistence? semantics in addition to the standard formalisms. Finally, we formulate service composition as a constraint satisfaction problem (CSP) and provide a CSP based algorithm which uses the consistency-based semantic matchmaking scheme while enabling interactive operation.