The service-oriented computing research community has devoted a great deal of attention to Web service specification, discovery and composition. The ability to efficiently select and compose services in order to accomplish a complex user goal is of utmost importance. However, the problem of on-demand composition still lacks satisfactory solutions for the case of complex services intending to serve non-elementary goals and adhering to constraints. Current service specification proposals include definitions of preand post-conditions, i.e., conditions that must be satisfied in the state prior to and after the enactment of the service. However, due to the need for complex compositions, conditions and constraints that do not exist in the individual service specifications arise. For the definition of these conditions, we augment service specifications with invariants and demonstrate how such assertions can be exploited for determining service effects and compositionality.