Abstract: The effectiveness of Web service composition depends on the real-time network environment, but most of the current service composition method is to provide an optimal result of Web service composition. The composition will have to be requested again when the combination fails. While selecting and matching related Web services for a specific Web service request, the composition method based on AND-OR Relationship is used to gradually builds Web service composition map in the form of AND-OR relationship. By accessing the plan, the composition results can be obtained as much as possible. If one combination is not available, other combination can be conditionally selected as an alternative, which improves the efficiency of requesting and generating of service compositions. The effectiveness of this method is demonstrated by an example.