Functional as well as Non-functional specification plays important role in service composition, discovery and selection. Among all the Non-functional specification cost is the most important parameter to handle. Hence optimization of cost is an interesting area of research in the domain of non-functional property aware service provisioning. In order to provide an effective solution; a cost oriented service composition method is presented in this paper. A hierarchical graph based model is proposed, which is constructed offline. It contains cost of single as well as composite services and also checks compliance information at the time of composition and can be used to answer all the queries in the system. Further the lemmas are defined to establish the soundness of the model which is formalized as Hierarchical Service Graph (HSG). © 2016 IEEE.