The goal of the Web Service Composition (WSC)problem is to find an optimal composition of Web Services tosatisfy a given request using their syntactic and/or semanticfeatures, when no single service satisfies it. However in manycases such composition is impossible due for example to a badformulation from the user. In this paper, we consider WSCproblem in the Software as a Service layer (SaaS) from semanticaspects, exploiting the super-type and subtype relationship amongparameters. In this paper we investigate the problem of SaaSWeb Service Composition. We formulate the problem of optimalcomposition as the problem of finding the minimal unsatisfiableset of minimum size widely studied in the context of ArtificialIntelligence that encoding the composition problem. Furthermore,we proved that our framework can be extended to take intoaccount the quality of services.