This work addresses the question of how to efficiently find business partners with matching business processes. In particular, the input business process enforces that some parts of the business process be mandatory. Current Web service standards around UDDI do not address this problem as they are limited to atomic service discovery. BPEL which is currently used to express business processes in Web service environments does not have a solid formal model, thus lacks formal semantics for querying business processes. A formal model is required to express business processes and enable their querying. Based on this formal model, appropriate indexing techniques are needed to efficiently query large service repositories. In this work a formal model and algorithms for indexing and querying business processes are presented. This work should help shed some light on how to automate the discovery of compatible business partners on the basis of their business processes. It is suitable for professionals and researchers involved in business process modeling, engineering and implementation.