Abstract
Composing Web services to fulfill a user query remains one of the most challenging research problems due to its importance to the world economy. Several composition techniques have been proposed, but these techniques are becoming more and more expensive due to the tremendous growth of data over the internet, the intensive use of services, and the continuous changes of available services. The workflow-based Web service composition problem is an NP-complete problem, due mainly to the property of the workflow structuring the composition and the diversity of underlying constraints. Reinforcing local consistency is one of the well-known pre-processing techniques to reduce the complexity of most NP-complete problems. These techniques are mainly dedicated to binary constraint satisfaction problems. Therefore, only few researchers devoted their efforts toward reinforcing some level of local consistency on Web service composition problems that can be semantically defined in the Ontology Web Language for Web Services (OWL-S) control structure based constraints. The main goal of this paper is to propose a novel approach for reinforcing a reasonable level of local consistency, node and arc-consistency on any Web service composition problems. It is expected to provide a more up-to-date and realistic representation of any Web service composition problems without any user interactions, but with the ability to cope with any types of user’s query, such as incomplete, ambiguous, and others. This is due to the existence of several novel rules for reinforcing node and arc-consistency on all types of control structure constraints. Experiments were performed on random problems of different levels of complexity to evaluate the performance of the proposed approach.