In this paper, we propose a novel way of modeling web services using semantic graph transformations. Each operation supported by a web service is associated with a semantic annotation that describes the input and output messages using RDF graph patterns. The terms used in these patterns are defined in OWL ontologies that describe the application domain. A key difference between our model and existing semantic web service models like OWL-S is that it describes the inputs and outputs in terms of instance-based graph patterns, rather than in terms of concepts. This allows associating a rich set of constraints on the input and output data in terms of relations between instances. We also propose a composition model for web service operations, that describes the conditions for composing services into workflows. The composition model includes the notion of semantic propagation, i.e. the semantic description of the output message of an operation depends on the semantics of the input message. We have developed a planner that uses this model to compose services, automatically. The planner uses DLP reasoning to aid plan search. We present performance results for the planner.