A Web service business protocol is used to describe the external behavior of a service and plays an important role in the service discovery, composition, verification, runtime service trustworthy guarantee, and so on. Presently, some research has been done on discovering the Web service business protocol from the invocation logs. Most of these works focused on the control-flow of Web service business protocols that give a temporal constraint among the operations of Web service. However, the data constraints and the consistency between the data-flow and the control-flow are also important and have not received enough attention. This paper studies the Web service business protocol from the service invocation logs and focuses on mining the relations, or the constraints between the message values and service operations. This paper proposes a Petri-net based model, called Business Protocol Net (simply, BPN), to describe the behavior of a service. Based on this model, a mining framework is proposed to automatically generate the BPN model from message traces. Experimental results illustrate that the method is effective in discovering the Web service business protocol from invocation logs.