# Verifying Service Choreography Model Based on Description Logic

Authors: Minggang Yu; Zhixue Wang; Xiaoxing Niu
Journal: Mathematical Problems in Engineering
 (2016)

---

## Abstract

Web Services Choreography Description Language lacks a formal system to accurately express the semantics of service behaviors and verify the correctness of a service choreography model. The paper presents a new approach of choreography model verification based on Description Logic. A metamodel of service choreography is built to provide a conceptual framework to capture the formal syntax and semantics of service choreography. Based on the framework, a set of rules and constraints are defined in Description Logic for choreography model verification. To automate model verification, the UML-based service choreography model will be transformed, by the given algorithms, into the DL-based ontology, and thus the model properties can be verified by reasoning through the ontology with the help of a popular DL reasoner. A case study is given to demonstrate applicability of the method. Furthermore, the work will be compared with other related researches.


---

## Body

## 1. Introduction

Web service technology has been popularly applied due to its power of interoperation, which allows various applications to run on heterogeneous platforms. Standards for web service composition cover two different levels of view: choreography and orchestration [1, 2]. The choreography view describes the interactions between services from a global perspective, while the orchestration view focuses on the interactions between one party and others. The web service choreography description language (WS-CDL) [3] is an XML-based language for the description of peer-to-peer collaborations of participants from a global viewpoint. However, WS-CDL is a declarative language and the specified concepts are weakly constrained. It lacks a formal system to accurately express the semantics of service behaviors and verify the correctness of a service choreography model. As a result, the built models may suffer from the problem of inconsistency, conflict, and realizability.A number of approaches are suggested for formally modeling and verifying web services composition. Xiao et al. [4] proposed a process algebra called probabilistic priced process algebra (PPPA) for modeling and analyzing web service composition from both functionality and nonfunctionality, such as reliability and performance. Moreover, they provided a united method based on PPPA to model and analyze both functionality and QoS of web service composition. Cambronero et al. [5] presented an approach to validation and verification of web services choreographies and more specifically for composite web services systems with timing restrictions. They defined operational semantics for a relevant subset of WS-CDL and then provided a translation of the considered subset into a network of timed automata for the validation and verification using the UPPAAL tool. Zhou et al. [6] put forward an approach to testing WS-CDL programs automatically. The dynamic symbolic execution technique was used to generate test inputs, and assertions are treated as the test oracles. An engine that can simulate WS-CDL is used to execute the WS-CDL programs during symbolic execution. Besson et al. [7] adapted the automated testing techniques used by the Agile Software Development community to the SOA context to enable test-driven development of choreographies. They present the first step in that direction, a software prototype composed of ad hoc automated test case scripts for testing a web service choreography. Gu et al. [8, 9] originally advocated for a formal modeling framework, called Abstract WS-CDL. This includes grammar, congruence relations, and operational semantics. They defined a set of mappings of the Abstract WS-CDL global model to the Pi calculus-based local model and subsequently suggested a set of deductive reasoning rules of state reachability and terminability.One of the crucial questions in choreography-based development is to check the realizability and conformance properties. Hallé and Bultan [10] proposed a novel algorithm for deciding realizability by computing a finite state model that keeps track of the information about the global state of a conversation protocol that each peer can deduce from the messages it sends and receives. McNeile [11] provided a new technique that uses compositions of partial descriptions to define a choreography, and he demonstrated that realizability of a choreography defined as a composition only needs to be established individually for the components of the composition. Basu et al. [12] gave necessary and sufficient conditions for realizability of choreographies and implemented the proposed realizability check on three granularities: (1) web service choreographies, (2) singularity OS channel contracts, and (3) UML collaboration (communication) diagrams. Yeung [13] put forward a formal approach to web service composition and conformance verification based on WS-CDL and WS-BPEL. The main contributions included a precise notion of choreography conformance upon which verification is based and support for the complementary use of visual modeling (e.g., UML) and standard WS-
∗ notations in composition.We argue that checking the realizability and conformance properties should be approached in two ways. One is to check the completeness and consistency of a choreography specification to guarantee there are no logical conflicts in the specification. The other is to check whether the specified choreography behaves in a correct way or whether the system functions well to complete its jobs. Having investigated the recent research results, we found that most of them addressed only one side rather than both.To solve the problem above, we propose an approach of choreography model verification based on Description Logic, or CMV-DL. A service choreography modeling framework is provided to support UML-based modeling. The metamodel of service choreography extends the WS-CDL specification. Two algorithms are given to transform the UML-based service choreography model into the DL-based ontology through which the verification can be made using a DL reasoner.To enable automatic verification, we introduce Description Logic (DL) [14] to formalize the choreography model and define a set of rules and constraints for verification. DL is a knowledge representation language and is a decidable subset of first-order predicate logic. It contains a set of basic concept constructors, such as concept consumption (⊑) and universal constraint (∀). As a subset of DL,SHOIN(D) [15] is the logical basis of web ontology language (OWL) [16]. It is powerful in knowledge description ability, reasoning decidability, and knowledge reusability and more importantly there are available supporting reasoners such Pellet [17] and Racer.The rest of the paper is organized as follows. Section2 introduces the service choreography modeling framework, highlighting the metamodel of service choreography. Section 3 discusses CMV-DL further on model verification mechanism and UML-DL conversion and introduces the deductive reasoning rules specified in Semantic Web Rule Language (SWRL) [18]. Section 4 provides a case study to show the potential usage of CMV-DL. Section 5 investigates the related work and draws a comparison between CMV-DL and other choreography verification methods. The final section brings a conclusion and foresees our future work.


## 2. Service Choreography Modeling Framework

According to the OMG’s four-layered metamodel architecture, UML can be extended by defining new stereotypes at metamodel level (M2) [19] and thus becomes a domain-specific language. The modeling framework for service choreography is accordingly defined in two levels, as shown in Figure 1. The metamodel of service choreography is built by extending the concepts of WS-CDL to provide the syntax and semantics for visually presenting a choreography and define a set of domain rules for model checking. The application model specifies the concepts of service choreography of an application (or a system) by instantiating the concepts of the metamodel.Figure 1
Service choreography modeling framework.


### 2.1. Metamodel of Service Choreography

To build the metamodel of service choreography, we define the main concepts of service choreography by referring to the WS-CDL specification.Definition 1 (session (S)).
A session is composed of a set of basic interactive activities which are performed by one or more participants in order to complete a specific function. Sessions can be denoted as a four-tuple structure:S
=
N
,
A
c
t
,
R
o
,
P
r, where N is the name, A
c
t refers to the activities that realize this specific function, R
o is a set of the roles that participate in the activities, and P
r is a set of the preconditions for carrying out this session.Definition 2 (choreography (C
h
o)).
A choreography defines the collaboration contracts between the participants and the interoperations of cross-system behaviors. It can be denoted as a three-tuple structure:C
h
o
=
N
,
R
o
,
S, where N is the name, R
o is a set of the roles that participate in the interoperations, and S represents a set of sessions to be executed in the interoperation processes.Definition 3 (metamodel).
The metamodel of service choreography defines the syntax and semantics for visually presenting a choreography and provides a set of domain rules for checking the correctness properties of a choreography model. It is composed of three parts:〈
MetaConcept,MetaRelation,DomainRule
〉, whereMetaConcept andMetaRelationare sets of metaconcepts and metarelations which are defined by inheriting the counterpart concepts from the WS-CDL specification. The core elements of the metamodel are shown in Figure 2.Figure 2
Metamodel of service choreography based on WS-CDL.


#### 2.1.1.MetaConcept

MetaConcept is a finite set of metaconcepts that originate from WS-CDL but are not limited to it. New concepts, such as Session, AtomicSession, and CompoundSession, are extended for the purpose of formal modeling and verification. Table 1 provides detailed definitions and descriptions of the metaconcepts.Table 1
A summary of metaconcepts of service choreography for the metamodel (a fragment).
Concepts
Definition
Description
Participant
P
a
r
=
〈
N
,
R
o
〉
The business entities or web services that participate in service interaction.N is the name and R
o denotes the roles it implements.
Role
R
o
=
〈
N
,
O
p
,
C
h
,
V
a
〉
The observable behavior a participant exhibits in order to collaborate.R
o initiates the collaborative operations (O
p) through channels (C
h) with other roles, and the local variables (V
a) will be affected.
Activity
A
c
t
=
〈
N
,
C
a
〉
The actual functions performed in the choreography. They (C
a) can be categorized into basic activities and structural activities.
Precondition
P
=
〈
N
,
Boolean
〉
The preconditions of session execution, specified in Boolean type.
Guard
G
=
〈
P
,
S
〉
The bindings of preconditions to sessions.
Variable
V
a
=
〈
N
,
R
o
〉
The variables a role has. It is a component of a role specification.
Operation
O
p
=
〈
N
,
R
o
〉
The operations a role provides. It is a component of a role specification.
Channel
C
h
=
〈
N
,
R
o
,
L
o
c
,
I
n
t
〉
The locations and manners through which information is exchanged between roles.L
o
c and I
n
t denote the channel locations and interaction activities, respectively.
Interface
I
n
=
〈
N
,
P
a
r
〉
The declaration of the participants (P
a
r) that collaborate.
Port
P
o
=
〈
N
,
I
n
〉
The way through which roles interact. One interface may correspond to one role and multiports.The concept activity can be divided into two kinds: BasicActivity (A
b
a
s) and StructuralActivity (A
s
t
r):(1)
Act
⩴
Abas
∣
AstrA
b
a
s is defined as(2)
Abas
⩴
NoAction
∣
SilentAction
∣
Interaction
∣
Assign
∣
PerformA
s
t
r is used to describe a compound activity in following syntax and semantics:(3)
A
s
t
r
⩴
p
A
c
t
condition
∣
p
∗
A
c
t
repeat
∣
p
g
p
r
e
p
∗
A
c
t
workunit
∣
A
c
t
1
·
A
c
t
2
sequence
∣
A
c
t
1
∥
A
c
t
2
parallel
∣
A
c
t
1
Τ
A
c
t
2
non-deterministic
∣
p
1
A
c
t
1
+
p
2
A
c
t
2
choiceThe structure of a compound activity appears either in workunit pattern or in control-flow pattern. The workunit structure is defined in WS-CDL by three substructures. The condition structure is expressed as[
p
]
A
c
t. The repeat structure is expressed as p
∗
A
c
t. A workunit structure is expressed as p
g
p
r
e
p
∗
A
c
t, which means that the activity will be blocked until the precondition p
g is evaluated to be “true”; that is, the activity is triggered by the precondition. If A
c
t terminates successfully and the repetition condition p
r
e
p is “true,” the workunit will repeat; otherwise, it will finish. A control-flow structure is defined as any combination of sequentially executed activities A
c
t
1
·
A
c
t
2, parallel executed activities A
c
t
1
∥
A
c
t
2, nondeterministically executed activities A
c
t
1
Τ
A
c
t
2, or selectively executed activities [
p
1
]
A
c
t
1
+
[
p
2
]
A
c
t
2.The concept session can also be divided into two kinds: AtomicSession (S
a
t
o
m) and CompoundSession (S
c
o
m): (4)
S
⩴
S
a
t
o
m
∣
S
c
o
mAn atomic session may appear in any form of the following:(5)
S
a
t
o
m
⩴
R
o
Ø
S
n
o
∣
R
o
τ
S
silent
∣
assign
R
o
·
x
=
e
S
assign
∣
request
R
o
1
·
x
⟶
R
o
2
·
y
,
C
h
@
R
o
2
S
req
∣
respond
R
o
1
·
x
⟵
R
o
2
·
y
,
C
h
@
R
o
1
S
resp
∣
req-resp
R
o
1
·
x
⟶
R
o
2
·
y
,
R
o
1
·
v
⟵
R
o
2
·
u
,
C
h
@
R
o
2
S
req-resp
∣
C
h
o
x
1
,
x
2
,
x
3
,
…
S
perform
∣
ψ
NULLS
n
o describes that the role R
o does not perform any operation; S
s
i
l
e
n
t means that R
o performs an internal silent action τ; S
a
s
s
i
g
n describes an assignment operation that the value e is assigned to the variable R
o
·
x; S
r
e
q describes a request interaction from R
o
1 to R
o
2 through C
h
@
R
o
2, where the request message is sent from R
o
1
·
x to R
o
2
·
y; S
r
e
s
p describes a response interaction; S
r
e
q
-
r
e
s
p describes request-response interaction; S
p
e
r
f
o
r
m describes invoking operation between sessions; andNULL denotes the termination state of a session.Two or more atomic sessions may be combined with one another by structural connectors to become a compound sessionS
c
o
m. The combination follows the following syntax and semantics:(6)
S
c
o
m
⩴
S
1
∥
S
2
S
p
a
r
a
l
l
e
l
∣
S
1
·
S
2
S
s
e
q
u
e
n
c
e
∣
p
1
S
1
+
p
2
S
2
S
c
h
o
i
c
e
∣
p
g
p
r
e
p
∗
S
S
w
o
r
k
u
n
i
tS
p
a
r
a
l
l
e
l describes two parallel executed sessions; S
s
e
q
u
e
n
c
e describes two sequentially executed sessions where S
1 is the predecessor and S
2 is the successor; S
c
h
o
i
c
e describes two selectively executed sessions that either S
1 or S
2 will be executed depending on whether the precondition p
1 or p
2 is met; S
w
o
r
k
u
n
i
t describes a repeatedly executed session, where S is triggered by the precondition p
g and it will be repeatedly executed until p
r
e
p becomes “false.”


#### 2.1.2.MetaRelation

MetaRelation is a finite set of semantic associations between the metaconcepts appearing in Table 1. It inherits the concepts of semantic verbs, such asSupport,Perform, andDepend, from WS-CDL and is supplemented by some new relations such asSessionDeduction,Congruence, andSequence, to enable comprehensive model checking.Table2 provides a set of core metarelations accompanied with their formal semantics specified in DL. The universal constraint ∀ is a DL symbol interpreted by (
∀
R
·
C
)
I
=
a
∈
Δ
I
∣
∀
b
(
(
a
,
b
)
∈
R
I
→
b
∈
C
I
), where C is a set of metaconcepts, R is a set of metarelations, and Δ
I denotes nonempty set of discourse domains.Table 2
A summary of metarelations of service choreography for the metamodel (a fragment).
Relations
Correlative concepts
Formal semantics
SessionDeduction
Session × Session
Session⊑
∀ SessionDeduction. Session
Congruence
Session × Session
Session⊑
∀ Congruence. Session
Implement
Participant × Role
Participant⊑
∀ Implement.Role
Contain
Choreography × Session
Choreography⊑
∀ Contain.Session
Link
Channel × Role
Channel⊑
∀ Link.Role
Belong_to
Role × Participant
Role⊑
∀ Belong_to.Participant
HasName
Role × Name
Role⊑
∀ HasName.Name
Provide
Role × operation
Role⊑
∀ Provide.operation
Executing
Session ×S
a
t
o
m
Session⊑
∀ Executing. S
a
t
o
m
Sequence
Session × Session
Session⊑
∀ Sequence. Session
Parallel
Session × Session
Session⊑
∀ Parallel. Session
Choice
Session × Session
Session⊑
∀ Choice. Session
WorkUnit
Session × Session
Session⊑
∀ WorkUnit. SessionDefinition 4 (SessionDeduction).
SessionDeduction is defined by a labeled transition system: S
→
p
,
a
S
′, meaning that the session S will become S
′ in the future when the precondition p becomes true and the atomic session a of S has been executed.SessionDeductionis defined for state reachability reasoning.Definition 5 (congruence).
If the two sessionsS and S
′ behave exactly in same way, there is a congruence relation between them, marked with the symbol ≡. The conditions of congruence are listed as follows:(7)
C
1
:
p
1
S
1
+
p
2
S
2
≡
p
2
S
2
+
p
1
S
1
C
2
:
p
1
S
1
+
p
2
S
2
+
p
3
S
3
≡
p
2
S
2
+
p
1
S
1
+
p
3
S
3
C
3
:
p
1
S
1
+
p
2
S
2
≡
p
1
∨
p
2
S
C
4
:
S
1
S
2
≡
S
2
S
1
S
1
∥
S
2
S
3
≡
S
1
S
2
S
3
C
5
:
S
S
n
o
≡
S
S
S
s
i
l
e
n
t
≡
S
S
N
U
L
L
≡
S
C
6
:
S
n
o
.
S
≡
S
S
s
i
l
e
n
t
.
S
≡
S
N
U
L
L
.
S
≡
SDefinitions ofMetaConcept andMetaRelation provide the syntax and semantics for modeling service choreography. In the subsequent sections, we will discuss the operational semantics for session evolution and the deductive domain rules for checking the properties of consistency, completeness, and state reachability of a service choreography model.


#### 2.1.3.DomainRule

Domain rules are description of constraints for specific domains [20].DomainRule is a set of rules defined upon the metamodel, providing overall constraints that need to be held by all concepts and relations in the service choreography model.Domain rules of service choreography can be classified into three categories: consistency, completeness, and deductive reasoning. They are not limited to what we give in the following. They may be continuously enriched and improved as applied.Definition 6 (consistency).
A service choreography model is consistent provided that (1) the application model is built consistent with the metamodel and (2) there is not any conflict among the concepts of the application model. A typical set of consistency rules are defined below.(i)
R
c
o
n
1: if there is a metarelation R that associates the metaconcept C
i with C
j (C
i
⊑
∀
R
·
C
j) in the metamodel and r is instance of R that associates the application concept c
i with c
j in the application model, then c
i must be an instance of C
i and c
j must be an instance of C
j.
(ii)
R
c
o
n
2: no more than one relation ofSequence,Parallel,Choice, orWorkUnit is allowed to associate a pair of sessions.
(iii)
R
c
o
n
3: if two sessions are associated with the relations S
e
s
s
i
o
n
D
e
d
u
c
t
i
o
n
(
S
i
,
S
j
) and C
o
n
g
r
u
e
n
c
e
(
S
i
,
S
j
)
(
i
≠
j
) at the same time, the atomic session S
a
t
o
m associated with S
i by theExecuting relation must be in type of S
n
o, S
s
i
l
e
n
t, or N
U
L
L.
(iv)
R
c
o
n
4: if two sessions are associated with the relation E
x
e
c
u
t
i
n
g
(
S
i
,
S
j
) (i
≠
j), S
j must be an atomic session, that is, S
j
:
S
a
t
o
m.
(v)
R
c
o
n
5: if two associated application concepts a and b are declared in the application model, there must be a metaconcept C and a metarelation R that satisfy a
:
C and (
a
,
b
)
:
R.
(vi)
R
c
o
n
6: the two relations S
e
q
u
e
n
c
e
(
S
i
,
S
j
) and S
e
q
u
e
n
c
e
(
S
j
,
S
i
)
,
i
≠
j, are allowed to exist at the same time.The WS-CDL specification includes many clauses stated with the keywords such as MUST/MUSTNOT, SHOULD/SHOULDNOT, and SHALL/SHALLNOT. Those clauses may relate to the consistency and completeness constraints. For example, “a Choreography MUST contain one or more sessions,” from which we can formally define a rule C
h
o
r
e
o
g
r
a
p
h
y
⊑
≥
1
C
o
n
t
a
i
n
.
S
e
s
s
i
o
n in DL. The DL expression ≥
n
R
·
C, used for constraining a relation, is interpreted by (≥n
R
·
C
)
I
=
{
a
∈
Δ
I
∣
#
{
b
∈
Δ
I
∣
(
a
,
b
)
∈
R
I
∧
b
∈
C
I
}
≥
n
}, where R is a metarelation and C is a metaconcept, and Δ
I denotes nonempty set of discourse domains.Definition 7 (completeness).
A service choreography model is complete provided that the number of the relations in the application model satisfies the multiplicity constraint of the corresponding metarelation in the metamodel. A typical set of completeness rules are defined below, according to the WS-CDL specification:(i)
R
c
o
m
1
:
R
o
l
e
⊑
≥
1
B
e
l
o
n
g
_
t
o
.
P
a
r
t
i
c
i
p
a
n
t
⊓
h
R
o
l
e
⊑
≤
1
B
e
l
o
n
g
_
t
o
.
P
a
r
t
i
c
i
p
a
n
t
.
(ii)
R
c
o
m
2
:
S
e
s
s
i
o
n
⊑
≥
1
S
u
p
p
o
r
t
.
A
c
t
i
v
i
t
y.
(iii)
R
c
o
m
3
:
C
h
a
n
n
e
l
⊑
≥
2
L
i
n
k
.
R
o
l
e
⊓
h
C
h
a
n
n
e
l
⊑
≤
2
L
i
n
k
.
R
o
l
e
.
(iv)
R
c
o
m
4
:
I
n
t
e
r
a
c
t
i
o
n
⊑
≥
1
D
e
p
a
n
d
.
C
h
a
n
n
e
l.
(v)
R
c
o
m
5
:
P
a
r
t
i
c
i
p
a
n
t
⊑
≥
1
Implement
.
R
o
l
e
.
(vi)
R
c
o
m
6
:
C
h
o
r
e
o
g
r
a
p
h
y
⊑
≥
1
C
o
n
t
a
i
n
.
S
e
s
s
i
o
n
(vii)
R
c
o
m
7
:
I
n
t
e
r
f
a
c
e
⊑
≥
1
B
i
n
d
.
R
o
l
e
⊓
h
I
n
t
e
r
f
a
c
e
⊑
≤
1
B
i
n
d
.
R
o
l
e
.Deductive reasoning rules relate to operational semantics that describes the evolution of a session. They are used to verify the state reachability of service choreography. Every deductive reasoning rule is a Horn clause in the following form: IFantecedent THEN 〈
c
o
n
s
e
q
u
e
n
t
〉, where the antecedent is a conjunction of one or more clauses and the consequent is an assertion of facts.The relationSessionDeduction defines deduction of session evolution. If the precondition p holds and the session S executes an atomic session a making S become the session S
′, then S is deduced to S
′. In particular, the two sessions can be identified by two states, before and after evolution.Choreography model checking may concern two kinds of state. One is the session state that defines whether a session can normally end and successfully complete its job. The other is the application state that defines whether an application that is running on one or more sessions can normally end. As a session will never end until all atomic sessions end, the state space of a session is determined by all possible states of the atomic sessions. Similarly, the state space of an application is determined by all possible states of the sessions.Definition 8 (state reachability).
A state (session state) is reachable provided that there is an evolving session which can be identified by the state and which can be deduced from its ancestor in its initial state.Inference 1.
If the termination states of an application described by a choreography model are reachable, that is, the termination sessions (denoted asNULL) can be deduced from the initial sessions, then all states of the application are reachable and the choreography models are thereby proven correct.The basic deductive reasoning rules are listed as follows:(i)(8)
R
atom
:
a
→
true
,
a
N
U
L
L(ii)(9)
R
s
t
r
u
c
t
:
S
≡
S
′
S
→
p
,
a
T
T
≡
T
′
S
′
→
p
,
a
T
′(iii)(10)
R
seq
1
:
a
·
S
→
true
,
a
S(iv)(11)
R
seq
2
:
S
→
p
,
a
S
′
S
·
T
→
p
,
a
S
′
·
T(v)(12)
R
parallel
:
S
→
p
,
a
S
′
S
T
→
p
,
a
S
′
T(vi)(13)
R
choice
:
S
1
→
p
1
,
a
S
1
′
p
1
S
1
+
p
2
S
2
→
p
1
,
a
S
1
′(vii)(14)
R
nonblock
:
S
→
¬
p
g
,
NULL
S
p
g
p
r
e
p
∗
S
→
¬
p
g
,
NULL
N
U
L
L(viii)(15)
R
norepeat
:
S
→
p
g
∧
¬
p
rep
,
a
S
′
p
g
p
r
e
p
∗
S
→
p
g
∧
¬
p
rep
,
a
S
′(ix)(16)
R
repeat
:
S
→
p
g
∧
p
rep
,
a
S
′
p
g
p
rep
∗
S
→
p
g
∧
p
rep
,
a
S
′
·
p
rep
∗
SR
a
t
o
m is the rule that holds the indivisibility of an atomic session. R
s
t
r
u
c
t is the rule that keeps the congruence in session deduction. R
s
e
q
1 and R
s
e
q
2 are the deduction rules for the sequence sessions. R
p
a
r
a
l
l
e
l is the deduction rule for parallel session that two sessions are parallel executed and one of them evolves. R
c
h
o
i
c
e is the deduction rule for the choice session that if the precondition is true and the atomic session is executed, one of the two sessions will evolve. R
n
o
n
b
l
o
c
k is the deduction rule for the workunit that if the precondition is false and p
g
p
r
e
p
∗
S works in nonblocking mode, the workunit will be skipped. R
n
o
r
e
p
e
a
t is the deduction rule for the workunit that if p
g is “true” and p
r
e
p is “false” S will become S
′ and the workunit will become S
′ after execution of a. R
r
e
p
e
a
t is the deduction rule for the workunit that if both p
g and p
r
e
p are “true” S will become S
′ and the workunit will become S
′
·
p
r
e
p
∗
S after execution of a, where p
r
e
p
∗
S means if p
r
e
p is “true” then S will be iteratively executed.


### 2.2. Application Model of Service Choreography

The metamodel gives a formal definition of the metaconcepts and relations of service choreography and provides fundamental semantics for service choreography description. An application model, an instantiation of the metaconcept model, gives a UML-compliant description and representation of service choreography. To build the model, software engineers would start with analysis of the objectives to be achieved in the choreography and then describe the roles that participants implement, the activities that the roles perform, and the session execution patterns.Definition 9 (application model of service choreography).
The application model of service choreography formally describes the design of service choreography for a distributed application in a UML-compliant representation within the constraint of the metamodel. It comprises three parts:〈
AppConcept,AppRelation,AppFunction
〉.AppConcept is a finite set of application concepts which are defined by instantiating the metaconcepts of the metamodel.AppRelation is a finite set of application relations which are defined by instantiating the metarelations of the metamodel.AppFunction is a set of functions that mapAppConcepttoMetaConcept orAppRelationtoMetaRelation in order to trace the types of application concepts and relations in the metamodel. For example, Buyer is anAppConcept and Role is the correspondingMetaConcept, and thus the function is built as follows:AppFunction(Buyer) = Role.The application model, if built with a universal UML tool, may suffer from the problems of inconsistency, incompleteness, and unreachable states, as mentioned in Section2.1.3. The next section will discuss the technique of transforming the UML-based model into DL ontology to verify the correctness of the model with the help of a popular reasoner.


## 2.1. Metamodel of Service Choreography

To build the metamodel of service choreography, we define the main concepts of service choreography by referring to the WS-CDL specification.Definition 1 (session (S)).
A session is composed of a set of basic interactive activities which are performed by one or more participants in order to complete a specific function. Sessions can be denoted as a four-tuple structure:S
=
N
,
A
c
t
,
R
o
,
P
r, where N is the name, A
c
t refers to the activities that realize this specific function, R
o is a set of the roles that participate in the activities, and P
r is a set of the preconditions for carrying out this session.Definition 2 (choreography (C
h
o)).
A choreography defines the collaboration contracts between the participants and the interoperations of cross-system behaviors. It can be denoted as a three-tuple structure:C
h
o
=
N
,
R
o
,
S, where N is the name, R
o is a set of the roles that participate in the interoperations, and S represents a set of sessions to be executed in the interoperation processes.Definition 3 (metamodel).
The metamodel of service choreography defines the syntax and semantics for visually presenting a choreography and provides a set of domain rules for checking the correctness properties of a choreography model. It is composed of three parts:〈
MetaConcept,MetaRelation,DomainRule
〉, whereMetaConcept andMetaRelationare sets of metaconcepts and metarelations which are defined by inheriting the counterpart concepts from the WS-CDL specification. The core elements of the metamodel are shown in Figure 2.Figure 2
Metamodel of service choreography based on WS-CDL.


### 2.1.1.MetaConcept

MetaConcept is a finite set of metaconcepts that originate from WS-CDL but are not limited to it. New concepts, such as Session, AtomicSession, and CompoundSession, are extended for the purpose of formal modeling and verification. Table 1 provides detailed definitions and descriptions of the metaconcepts.Table 1
A summary of metaconcepts of service choreography for the metamodel (a fragment).
Concepts
Definition
Description
Participant
P
a
r
=
〈
N
,
R
o
〉
The business entities or web services that participate in service interaction.N is the name and R
o denotes the roles it implements.
Role
R
o
=
〈
N
,
O
p
,
C
h
,
V
a
〉
The observable behavior a participant exhibits in order to collaborate.R
o initiates the collaborative operations (O
p) through channels (C
h) with other roles, and the local variables (V
a) will be affected.
Activity
A
c
t
=
〈
N
,
C
a
〉
The actual functions performed in the choreography. They (C
a) can be categorized into basic activities and structural activities.
Precondition
P
=
〈
N
,
Boolean
〉
The preconditions of session execution, specified in Boolean type.
Guard
G
=
〈
P
,
S
〉
The bindings of preconditions to sessions.
Variable
V
a
=
〈
N
,
R
o
〉
The variables a role has. It is a component of a role specification.
Operation
O
p
=
〈
N
,
R
o
〉
The operations a role provides. It is a component of a role specification.
Channel
C
h
=
〈
N
,
R
o
,
L
o
c
,
I
n
t
〉
The locations and manners through which information is exchanged between roles.L
o
c and I
n
t denote the channel locations and interaction activities, respectively.
Interface
I
n
=
〈
N
,
P
a
r
〉
The declaration of the participants (P
a
r) that collaborate.
Port
P
o
=
〈
N
,
I
n
〉
The way through which roles interact. One interface may correspond to one role and multiports.The concept activity can be divided into two kinds: BasicActivity (A
b
a
s) and StructuralActivity (A
s
t
r):(1)
Act
⩴
Abas
∣
AstrA
b
a
s is defined as(2)
Abas
⩴
NoAction
∣
SilentAction
∣
Interaction
∣
Assign
∣
PerformA
s
t
r is used to describe a compound activity in following syntax and semantics:(3)
A
s
t
r
⩴
p
A
c
t
condition
∣
p
∗
A
c
t
repeat
∣
p
g
p
r
e
p
∗
A
c
t
workunit
∣
A
c
t
1
·
A
c
t
2
sequence
∣
A
c
t
1
∥
A
c
t
2
parallel
∣
A
c
t
1
Τ
A
c
t
2
non-deterministic
∣
p
1
A
c
t
1
+
p
2
A
c
t
2
choiceThe structure of a compound activity appears either in workunit pattern or in control-flow pattern. The workunit structure is defined in WS-CDL by three substructures. The condition structure is expressed as[
p
]
A
c
t. The repeat structure is expressed as p
∗
A
c
t. A workunit structure is expressed as p
g
p
r
e
p
∗
A
c
t, which means that the activity will be blocked until the precondition p
g is evaluated to be “true”; that is, the activity is triggered by the precondition. If A
c
t terminates successfully and the repetition condition p
r
e
p is “true,” the workunit will repeat; otherwise, it will finish. A control-flow structure is defined as any combination of sequentially executed activities A
c
t
1
·
A
c
t
2, parallel executed activities A
c
t
1
∥
A
c
t
2, nondeterministically executed activities A
c
t
1
Τ
A
c
t
2, or selectively executed activities [
p
1
]
A
c
t
1
+
[
p
2
]
A
c
t
2.The concept session can also be divided into two kinds: AtomicSession (S
a
t
o
m) and CompoundSession (S
c
o
m): (4)
S
⩴
S
a
t
o
m
∣
S
c
o
mAn atomic session may appear in any form of the following:(5)
S
a
t
o
m
⩴
R
o
Ø
S
n
o
∣
R
o
τ
S
silent
∣
assign
R
o
·
x
=
e
S
assign
∣
request
R
o
1
·
x
⟶
R
o
2
·
y
,
C
h
@
R
o
2
S
req
∣
respond
R
o
1
·
x
⟵
R
o
2
·
y
,
C
h
@
R
o
1
S
resp
∣
req-resp
R
o
1
·
x
⟶
R
o
2
·
y
,
R
o
1
·
v
⟵
R
o
2
·
u
,
C
h
@
R
o
2
S
req-resp
∣
C
h
o
x
1
,
x
2
,
x
3
,
…
S
perform
∣
ψ
NULLS
n
o describes that the role R
o does not perform any operation; S
s
i
l
e
n
t means that R
o performs an internal silent action τ; S
a
s
s
i
g
n describes an assignment operation that the value e is assigned to the variable R
o
·
x; S
r
e
q describes a request interaction from R
o
1 to R
o
2 through C
h
@
R
o
2, where the request message is sent from R
o
1
·
x to R
o
2
·
y; S
r
e
s
p describes a response interaction; S
r
e
q
-
r
e
s
p describes request-response interaction; S
p
e
r
f
o
r
m describes invoking operation between sessions; andNULL denotes the termination state of a session.Two or more atomic sessions may be combined with one another by structural connectors to become a compound sessionS
c
o
m. The combination follows the following syntax and semantics:(6)
S
c
o
m
⩴
S
1
∥
S
2
S
p
a
r
a
l
l
e
l
∣
S
1
·
S
2
S
s
e
q
u
e
n
c
e
∣
p
1
S
1
+
p
2
S
2
S
c
h
o
i
c
e
∣
p
g
p
r
e
p
∗
S
S
w
o
r
k
u
n
i
tS
p
a
r
a
l
l
e
l describes two parallel executed sessions; S
s
e
q
u
e
n
c
e describes two sequentially executed sessions where S
1 is the predecessor and S
2 is the successor; S
c
h
o
i
c
e describes two selectively executed sessions that either S
1 or S
2 will be executed depending on whether the precondition p
1 or p
2 is met; S
w
o
r
k
u
n
i
t describes a repeatedly executed session, where S is triggered by the precondition p
g and it will be repeatedly executed until p
r
e
p becomes “false.”


### 2.1.2.MetaRelation

MetaRelation is a finite set of semantic associations between the metaconcepts appearing in Table 1. It inherits the concepts of semantic verbs, such asSupport,Perform, andDepend, from WS-CDL and is supplemented by some new relations such asSessionDeduction,Congruence, andSequence, to enable comprehensive model checking.Table2 provides a set of core metarelations accompanied with their formal semantics specified in DL. The universal constraint ∀ is a DL symbol interpreted by (
∀
R
·
C
)
I
=
a
∈
Δ
I
∣
∀
b
(
(
a
,
b
)
∈
R
I
→
b
∈
C
I
), where C is a set of metaconcepts, R is a set of metarelations, and Δ
I denotes nonempty set of discourse domains.Table 2
A summary of metarelations of service choreography for the metamodel (a fragment).
Relations
Correlative concepts
Formal semantics
SessionDeduction
Session × Session
Session⊑
∀ SessionDeduction. Session
Congruence
Session × Session
Session⊑
∀ Congruence. Session
Implement
Participant × Role
Participant⊑
∀ Implement.Role
Contain
Choreography × Session
Choreography⊑
∀ Contain.Session
Link
Channel × Role
Channel⊑
∀ Link.Role
Belong_to
Role × Participant
Role⊑
∀ Belong_to.Participant
HasName
Role × Name
Role⊑
∀ HasName.Name
Provide
Role × operation
Role⊑
∀ Provide.operation
Executing
Session ×S
a
t
o
m
Session⊑
∀ Executing. S
a
t
o
m
Sequence
Session × Session
Session⊑
∀ Sequence. Session
Parallel
Session × Session
Session⊑
∀ Parallel. Session
Choice
Session × Session
Session⊑
∀ Choice. Session
WorkUnit
Session × Session
Session⊑
∀ WorkUnit. SessionDefinition 4 (SessionDeduction).
SessionDeduction is defined by a labeled transition system: S
→
p
,
a
S
′, meaning that the session S will become S
′ in the future when the precondition p becomes true and the atomic session a of S has been executed.SessionDeductionis defined for state reachability reasoning.Definition 5 (congruence).
If the two sessionsS and S
′ behave exactly in same way, there is a congruence relation between them, marked with the symbol ≡. The conditions of congruence are listed as follows:(7)
C
1
:
p
1
S
1
+
p
2
S
2
≡
p
2
S
2
+
p
1
S
1
C
2
:
p
1
S
1
+
p
2
S
2
+
p
3
S
3
≡
p
2
S
2
+
p
1
S
1
+
p
3
S
3
C
3
:
p
1
S
1
+
p
2
S
2
≡
p
1
∨
p
2
S
C
4
:
S
1
S
2
≡
S
2
S
1
S
1
∥
S
2
S
3
≡
S
1
S
2
S
3
C
5
:
S
S
n
o
≡
S
S
S
s
i
l
e
n
t
≡
S
S
N
U
L
L
≡
S
C
6
:
S
n
o
.
S
≡
S
S
s
i
l
e
n
t
.
S
≡
S
N
U
L
L
.
S
≡
SDefinitions ofMetaConcept andMetaRelation provide the syntax and semantics for modeling service choreography. In the subsequent sections, we will discuss the operational semantics for session evolution and the deductive domain rules for checking the properties of consistency, completeness, and state reachability of a service choreography model.


### 2.1.3.DomainRule

Domain rules are description of constraints for specific domains [20].DomainRule is a set of rules defined upon the metamodel, providing overall constraints that need to be held by all concepts and relations in the service choreography model.Domain rules of service choreography can be classified into three categories: consistency, completeness, and deductive reasoning. They are not limited to what we give in the following. They may be continuously enriched and improved as applied.Definition 6 (consistency).
A service choreography model is consistent provided that (1) the application model is built consistent with the metamodel and (2) there is not any conflict among the concepts of the application model. A typical set of consistency rules are defined below.(i)
R
c
o
n
1: if there is a metarelation R that associates the metaconcept C
i with C
j (C
i
⊑
∀
R
·
C
j) in the metamodel and r is instance of R that associates the application concept c
i with c
j in the application model, then c
i must be an instance of C
i and c
j must be an instance of C
j.
(ii)
R
c
o
n
2: no more than one relation ofSequence,Parallel,Choice, orWorkUnit is allowed to associate a pair of sessions.
(iii)
R
c
o
n
3: if two sessions are associated with the relations S
e
s
s
i
o
n
D
e
d
u
c
t
i
o
n
(
S
i
,
S
j
) and C
o
n
g
r
u
e
n
c
e
(
S
i
,
S
j
)
(
i
≠
j
) at the same time, the atomic session S
a
t
o
m associated with S
i by theExecuting relation must be in type of S
n
o, S
s
i
l
e
n
t, or N
U
L
L.
(iv)
R
c
o
n
4: if two sessions are associated with the relation E
x
e
c
u
t
i
n
g
(
S
i
,
S
j
) (i
≠
j), S
j must be an atomic session, that is, S
j
:
S
a
t
o
m.
(v)
R
c
o
n
5: if two associated application concepts a and b are declared in the application model, there must be a metaconcept C and a metarelation R that satisfy a
:
C and (
a
,
b
)
:
R.
(vi)
R
c
o
n
6: the two relations S
e
q
u
e
n
c
e
(
S
i
,
S
j
) and S
e
q
u
e
n
c
e
(
S
j
,
S
i
)
,
i
≠
j, are allowed to exist at the same time.The WS-CDL specification includes many clauses stated with the keywords such as MUST/MUSTNOT, SHOULD/SHOULDNOT, and SHALL/SHALLNOT. Those clauses may relate to the consistency and completeness constraints. For example, “a Choreography MUST contain one or more sessions,” from which we can formally define a rule C
h
o
r
e
o
g
r
a
p
h
y
⊑
≥
1
C
o
n
t
a
i
n
.
S
e
s
s
i
o
n in DL. The DL expression ≥
n
R
·
C, used for constraining a relation, is interpreted by (≥n
R
·
C
)
I
=
{
a
∈
Δ
I
∣
#
{
b
∈
Δ
I
∣
(
a
,
b
)
∈
R
I
∧
b
∈
C
I
}
≥
n
}, where R is a metarelation and C is a metaconcept, and Δ
I denotes nonempty set of discourse domains.Definition 7 (completeness).
A service choreography model is complete provided that the number of the relations in the application model satisfies the multiplicity constraint of the corresponding metarelation in the metamodel. A typical set of completeness rules are defined below, according to the WS-CDL specification:(i)
R
c
o
m
1
:
R
o
l
e
⊑
≥
1
B
e
l
o
n
g
_
t
o
.
P
a
r
t
i
c
i
p
a
n
t
⊓
h
R
o
l
e
⊑
≤
1
B
e
l
o
n
g
_
t
o
.
P
a
r
t
i
c
i
p
a
n
t
.
(ii)
R
c
o
m
2
:
S
e
s
s
i
o
n
⊑
≥
1
S
u
p
p
o
r
t
.
A
c
t
i
v
i
t
y.
(iii)
R
c
o
m
3
:
C
h
a
n
n
e
l
⊑
≥
2
L
i
n
k
.
R
o
l
e
⊓
h
C
h
a
n
n
e
l
⊑
≤
2
L
i
n
k
.
R
o
l
e
.
(iv)
R
c
o
m
4
:
I
n
t
e
r
a
c
t
i
o
n
⊑
≥
1
D
e
p
a
n
d
.
C
h
a
n
n
e
l.
(v)
R
c
o
m
5
:
P
a
r
t
i
c
i
p
a
n
t
⊑
≥
1
Implement
.
R
o
l
e
.
(vi)
R
c
o
m
6
:
C
h
o
r
e
o
g
r
a
p
h
y
⊑
≥
1
C
o
n
t
a
i
n
.
S
e
s
s
i
o
n
(vii)
R
c
o
m
7
:
I
n
t
e
r
f
a
c
e
⊑
≥
1
B
i
n
d
.
R
o
l
e
⊓
h
I
n
t
e
r
f
a
c
e
⊑
≤
1
B
i
n
d
.
R
o
l
e
.Deductive reasoning rules relate to operational semantics that describes the evolution of a session. They are used to verify the state reachability of service choreography. Every deductive reasoning rule is a Horn clause in the following form: IFantecedent THEN 〈
c
o
n
s
e
q
u
e
n
t
〉, where the antecedent is a conjunction of one or more clauses and the consequent is an assertion of facts.The relationSessionDeduction defines deduction of session evolution. If the precondition p holds and the session S executes an atomic session a making S become the session S
′, then S is deduced to S
′. In particular, the two sessions can be identified by two states, before and after evolution.Choreography model checking may concern two kinds of state. One is the session state that defines whether a session can normally end and successfully complete its job. The other is the application state that defines whether an application that is running on one or more sessions can normally end. As a session will never end until all atomic sessions end, the state space of a session is determined by all possible states of the atomic sessions. Similarly, the state space of an application is determined by all possible states of the sessions.Definition 8 (state reachability).
A state (session state) is reachable provided that there is an evolving session which can be identified by the state and which can be deduced from its ancestor in its initial state.Inference 1.
If the termination states of an application described by a choreography model are reachable, that is, the termination sessions (denoted asNULL) can be deduced from the initial sessions, then all states of the application are reachable and the choreography models are thereby proven correct.The basic deductive reasoning rules are listed as follows:(i)(8)
R
atom
:
a
→
true
,
a
N
U
L
L(ii)(9)
R
s
t
r
u
c
t
:
S
≡
S
′
S
→
p
,
a
T
T
≡
T
′
S
′
→
p
,
a
T
′(iii)(10)
R
seq
1
:
a
·
S
→
true
,
a
S(iv)(11)
R
seq
2
:
S
→
p
,
a
S
′
S
·
T
→
p
,
a
S
′
·
T(v)(12)
R
parallel
:
S
→
p
,
a
S
′
S
T
→
p
,
a
S
′
T(vi)(13)
R
choice
:
S
1
→
p
1
,
a
S
1
′
p
1
S
1
+
p
2
S
2
→
p
1
,
a
S
1
′(vii)(14)
R
nonblock
:
S
→
¬
p
g
,
NULL
S
p
g
p
r
e
p
∗
S
→
¬
p
g
,
NULL
N
U
L
L(viii)(15)
R
norepeat
:
S
→
p
g
∧
¬
p
rep
,
a
S
′
p
g
p
r
e
p
∗
S
→
p
g
∧
¬
p
rep
,
a
S
′(ix)(16)
R
repeat
:
S
→
p
g
∧
p
rep
,
a
S
′
p
g
p
rep
∗
S
→
p
g
∧
p
rep
,
a
S
′
·
p
rep
∗
SR
a
t
o
m is the rule that holds the indivisibility of an atomic session. R
s
t
r
u
c
t is the rule that keeps the congruence in session deduction. R
s
e
q
1 and R
s
e
q
2 are the deduction rules for the sequence sessions. R
p
a
r
a
l
l
e
l is the deduction rule for parallel session that two sessions are parallel executed and one of them evolves. R
c
h
o
i
c
e is the deduction rule for the choice session that if the precondition is true and the atomic session is executed, one of the two sessions will evolve. R
n
o
n
b
l
o
c
k is the deduction rule for the workunit that if the precondition is false and p
g
p
r
e
p
∗
S works in nonblocking mode, the workunit will be skipped. R
n
o
r
e
p
e
a
t is the deduction rule for the workunit that if p
g is “true” and p
r
e
p is “false” S will become S
′ and the workunit will become S
′ after execution of a. R
r
e
p
e
a
t is the deduction rule for the workunit that if both p
g and p
r
e
p are “true” S will become S
′ and the workunit will become S
′
·
p
r
e
p
∗
S after execution of a, where p
r
e
p
∗
S means if p
r
e
p is “true” then S will be iteratively executed.


## 2.1.1.MetaConcept

MetaConcept is a finite set of metaconcepts that originate from WS-CDL but are not limited to it. New concepts, such as Session, AtomicSession, and CompoundSession, are extended for the purpose of formal modeling and verification. Table 1 provides detailed definitions and descriptions of the metaconcepts.Table 1
A summary of metaconcepts of service choreography for the metamodel (a fragment).
Concepts
Definition
Description
Participant
P
a
r
=
〈
N
,
R
o
〉
The business entities or web services that participate in service interaction.N is the name and R
o denotes the roles it implements.
Role
R
o
=
〈
N
,
O
p
,
C
h
,
V
a
〉
The observable behavior a participant exhibits in order to collaborate.R
o initiates the collaborative operations (O
p) through channels (C
h) with other roles, and the local variables (V
a) will be affected.
Activity
A
c
t
=
〈
N
,
C
a
〉
The actual functions performed in the choreography. They (C
a) can be categorized into basic activities and structural activities.
Precondition
P
=
〈
N
,
Boolean
〉
The preconditions of session execution, specified in Boolean type.
Guard
G
=
〈
P
,
S
〉
The bindings of preconditions to sessions.
Variable
V
a
=
〈
N
,
R
o
〉
The variables a role has. It is a component of a role specification.
Operation
O
p
=
〈
N
,
R
o
〉
The operations a role provides. It is a component of a role specification.
Channel
C
h
=
〈
N
,
R
o
,
L
o
c
,
I
n
t
〉
The locations and manners through which information is exchanged between roles.L
o
c and I
n
t denote the channel locations and interaction activities, respectively.
Interface
I
n
=
〈
N
,
P
a
r
〉
The declaration of the participants (P
a
r) that collaborate.
Port
P
o
=
〈
N
,
I
n
〉
The way through which roles interact. One interface may correspond to one role and multiports.The concept activity can be divided into two kinds: BasicActivity (A
b
a
s) and StructuralActivity (A
s
t
r):(1)
Act
⩴
Abas
∣
AstrA
b
a
s is defined as(2)
Abas
⩴
NoAction
∣
SilentAction
∣
Interaction
∣
Assign
∣
PerformA
s
t
r is used to describe a compound activity in following syntax and semantics:(3)
A
s
t
r
⩴
p
A
c
t
condition
∣
p
∗
A
c
t
repeat
∣
p
g
p
r
e
p
∗
A
c
t
workunit
∣
A
c
t
1
·
A
c
t
2
sequence
∣
A
c
t
1
∥
A
c
t
2
parallel
∣
A
c
t
1
Τ
A
c
t
2
non-deterministic
∣
p
1
A
c
t
1
+
p
2
A
c
t
2
choiceThe structure of a compound activity appears either in workunit pattern or in control-flow pattern. The workunit structure is defined in WS-CDL by three substructures. The condition structure is expressed as[
p
]
A
c
t. The repeat structure is expressed as p
∗
A
c
t. A workunit structure is expressed as p
g
p
r
e
p
∗
A
c
t, which means that the activity will be blocked until the precondition p
g is evaluated to be “true”; that is, the activity is triggered by the precondition. If A
c
t terminates successfully and the repetition condition p
r
e
p is “true,” the workunit will repeat; otherwise, it will finish. A control-flow structure is defined as any combination of sequentially executed activities A
c
t
1
·
A
c
t
2, parallel executed activities A
c
t
1
∥
A
c
t
2, nondeterministically executed activities A
c
t
1
Τ
A
c
t
2, or selectively executed activities [
p
1
]
A
c
t
1
+
[
p
2
]
A
c
t
2.The concept session can also be divided into two kinds: AtomicSession (S
a
t
o
m) and CompoundSession (S
c
o
m): (4)
S
⩴
S
a
t
o
m
∣
S
c
o
mAn atomic session may appear in any form of the following:(5)
S
a
t
o
m
⩴
R
o
Ø
S
n
o
∣
R
o
τ
S
silent
∣
assign
R
o
·
x
=
e
S
assign
∣
request
R
o
1
·
x
⟶
R
o
2
·
y
,
C
h
@
R
o
2
S
req
∣
respond
R
o
1
·
x
⟵
R
o
2
·
y
,
C
h
@
R
o
1
S
resp
∣
req-resp
R
o
1
·
x
⟶
R
o
2
·
y
,
R
o
1
·
v
⟵
R
o
2
·
u
,
C
h
@
R
o
2
S
req-resp
∣
C
h
o
x
1
,
x
2
,
x
3
,
…
S
perform
∣
ψ
NULLS
n
o describes that the role R
o does not perform any operation; S
s
i
l
e
n
t means that R
o performs an internal silent action τ; S
a
s
s
i
g
n describes an assignment operation that the value e is assigned to the variable R
o
·
x; S
r
e
q describes a request interaction from R
o
1 to R
o
2 through C
h
@
R
o
2, where the request message is sent from R
o
1
·
x to R
o
2
·
y; S
r
e
s
p describes a response interaction; S
r
e
q
-
r
e
s
p describes request-response interaction; S
p
e
r
f
o
r
m describes invoking operation between sessions; andNULL denotes the termination state of a session.Two or more atomic sessions may be combined with one another by structural connectors to become a compound sessionS
c
o
m. The combination follows the following syntax and semantics:(6)
S
c
o
m
⩴
S
1
∥
S
2
S
p
a
r
a
l
l
e
l
∣
S
1
·
S
2
S
s
e
q
u
e
n
c
e
∣
p
1
S
1
+
p
2
S
2
S
c
h
o
i
c
e
∣
p
g
p
r
e
p
∗
S
S
w
o
r
k
u
n
i
tS
p
a
r
a
l
l
e
l describes two parallel executed sessions; S
s
e
q
u
e
n
c
e describes two sequentially executed sessions where S
1 is the predecessor and S
2 is the successor; S
c
h
o
i
c
e describes two selectively executed sessions that either S
1 or S
2 will be executed depending on whether the precondition p
1 or p
2 is met; S
w
o
r
k
u
n
i
t describes a repeatedly executed session, where S is triggered by the precondition p
g and it will be repeatedly executed until p
r
e
p becomes “false.”


## 2.1.2.MetaRelation

MetaRelation is a finite set of semantic associations between the metaconcepts appearing in Table 1. It inherits the concepts of semantic verbs, such asSupport,Perform, andDepend, from WS-CDL and is supplemented by some new relations such asSessionDeduction,Congruence, andSequence, to enable comprehensive model checking.Table2 provides a set of core metarelations accompanied with their formal semantics specified in DL. The universal constraint ∀ is a DL symbol interpreted by (
∀
R
·
C
)
I
=
a
∈
Δ
I
∣
∀
b
(
(
a
,
b
)
∈
R
I
→
b
∈
C
I
), where C is a set of metaconcepts, R is a set of metarelations, and Δ
I denotes nonempty set of discourse domains.Table 2
A summary of metarelations of service choreography for the metamodel (a fragment).
Relations
Correlative concepts
Formal semantics
SessionDeduction
Session × Session
Session⊑
∀ SessionDeduction. Session
Congruence
Session × Session
Session⊑
∀ Congruence. Session
Implement
Participant × Role
Participant⊑
∀ Implement.Role
Contain
Choreography × Session
Choreography⊑
∀ Contain.Session
Link
Channel × Role
Channel⊑
∀ Link.Role
Belong_to
Role × Participant
Role⊑
∀ Belong_to.Participant
HasName
Role × Name
Role⊑
∀ HasName.Name
Provide
Role × operation
Role⊑
∀ Provide.operation
Executing
Session ×S
a
t
o
m
Session⊑
∀ Executing. S
a
t
o
m
Sequence
Session × Session
Session⊑
∀ Sequence. Session
Parallel
Session × Session
Session⊑
∀ Parallel. Session
Choice
Session × Session
Session⊑
∀ Choice. Session
WorkUnit
Session × Session
Session⊑
∀ WorkUnit. SessionDefinition 4 (SessionDeduction).
SessionDeduction is defined by a labeled transition system: S
→
p
,
a
S
′, meaning that the session S will become S
′ in the future when the precondition p becomes true and the atomic session a of S has been executed.SessionDeductionis defined for state reachability reasoning.Definition 5 (congruence).
If the two sessionsS and S
′ behave exactly in same way, there is a congruence relation between them, marked with the symbol ≡. The conditions of congruence are listed as follows:(7)
C
1
:
p
1
S
1
+
p
2
S
2
≡
p
2
S
2
+
p
1
S
1
C
2
:
p
1
S
1
+
p
2
S
2
+
p
3
S
3
≡
p
2
S
2
+
p
1
S
1
+
p
3
S
3
C
3
:
p
1
S
1
+
p
2
S
2
≡
p
1
∨
p
2
S
C
4
:
S
1
S
2
≡
S
2
S
1
S
1
∥
S
2
S
3
≡
S
1
S
2
S
3
C
5
:
S
S
n
o
≡
S
S
S
s
i
l
e
n
t
≡
S
S
N
U
L
L
≡
S
C
6
:
S
n
o
.
S
≡
S
S
s
i
l
e
n
t
.
S
≡
S
N
U
L
L
.
S
≡
SDefinitions ofMetaConcept andMetaRelation provide the syntax and semantics for modeling service choreography. In the subsequent sections, we will discuss the operational semantics for session evolution and the deductive domain rules for checking the properties of consistency, completeness, and state reachability of a service choreography model.


## 2.1.3.DomainRule

Domain rules are description of constraints for specific domains [20].DomainRule is a set of rules defined upon the metamodel, providing overall constraints that need to be held by all concepts and relations in the service choreography model.Domain rules of service choreography can be classified into three categories: consistency, completeness, and deductive reasoning. They are not limited to what we give in the following. They may be continuously enriched and improved as applied.Definition 6 (consistency).
A service choreography model is consistent provided that (1) the application model is built consistent with the metamodel and (2) there is not any conflict among the concepts of the application model. A typical set of consistency rules are defined below.(i)
R
c
o
n
1: if there is a metarelation R that associates the metaconcept C
i with C
j (C
i
⊑
∀
R
·
C
j) in the metamodel and r is instance of R that associates the application concept c
i with c
j in the application model, then c
i must be an instance of C
i and c
j must be an instance of C
j.
(ii)
R
c
o
n
2: no more than one relation ofSequence,Parallel,Choice, orWorkUnit is allowed to associate a pair of sessions.
(iii)
R
c
o
n
3: if two sessions are associated with the relations S
e
s
s
i
o
n
D
e
d
u
c
t
i
o
n
(
S
i
,
S
j
) and C
o
n
g
r
u
e
n
c
e
(
S
i
,
S
j
)
(
i
≠
j
) at the same time, the atomic session S
a
t
o
m associated with S
i by theExecuting relation must be in type of S
n
o, S
s
i
l
e
n
t, or N
U
L
L.
(iv)
R
c
o
n
4: if two sessions are associated with the relation E
x
e
c
u
t
i
n
g
(
S
i
,
S
j
) (i
≠
j), S
j must be an atomic session, that is, S
j
:
S
a
t
o
m.
(v)
R
c
o
n
5: if two associated application concepts a and b are declared in the application model, there must be a metaconcept C and a metarelation R that satisfy a
:
C and (
a
,
b
)
:
R.
(vi)
R
c
o
n
6: the two relations S
e
q
u
e
n
c
e
(
S
i
,
S
j
) and S
e
q
u
e
n
c
e
(
S
j
,
S
i
)
,
i
≠
j, are allowed to exist at the same time.The WS-CDL specification includes many clauses stated with the keywords such as MUST/MUSTNOT, SHOULD/SHOULDNOT, and SHALL/SHALLNOT. Those clauses may relate to the consistency and completeness constraints. For example, “a Choreography MUST contain one or more sessions,” from which we can formally define a rule C
h
o
r
e
o
g
r
a
p
h
y
⊑
≥
1
C
o
n
t
a
i
n
.
S
e
s
s
i
o
n in DL. The DL expression ≥
n
R
·
C, used for constraining a relation, is interpreted by (≥n
R
·
C
)
I
=
{
a
∈
Δ
I
∣
#
{
b
∈
Δ
I
∣
(
a
,
b
)
∈
R
I
∧
b
∈
C
I
}
≥
n
}, where R is a metarelation and C is a metaconcept, and Δ
I denotes nonempty set of discourse domains.Definition 7 (completeness).
A service choreography model is complete provided that the number of the relations in the application model satisfies the multiplicity constraint of the corresponding metarelation in the metamodel. A typical set of completeness rules are defined below, according to the WS-CDL specification:(i)
R
c
o
m
1
:
R
o
l
e
⊑
≥
1
B
e
l
o
n
g
_
t
o
.
P
a
r
t
i
c
i
p
a
n
t
⊓
h
R
o
l
e
⊑
≤
1
B
e
l
o
n
g
_
t
o
.
P
a
r
t
i
c
i
p
a
n
t
.
(ii)
R
c
o
m
2
:
S
e
s
s
i
o
n
⊑
≥
1
S
u
p
p
o
r
t
.
A
c
t
i
v
i
t
y.
(iii)
R
c
o
m
3
:
C
h
a
n
n
e
l
⊑
≥
2
L
i
n
k
.
R
o
l
e
⊓
h
C
h
a
n
n
e
l
⊑
≤
2
L
i
n
k
.
R
o
l
e
.
(iv)
R
c
o
m
4
:
I
n
t
e
r
a
c
t
i
o
n
⊑
≥
1
D
e
p
a
n
d
.
C
h
a
n
n
e
l.
(v)
R
c
o
m
5
:
P
a
r
t
i
c
i
p
a
n
t
⊑
≥
1
Implement
.
R
o
l
e
.
(vi)
R
c
o
m
6
:
C
h
o
r
e
o
g
r
a
p
h
y
⊑
≥
1
C
o
n
t
a
i
n
.
S
e
s
s
i
o
n
(vii)
R
c
o
m
7
:
I
n
t
e
r
f
a
c
e
⊑
≥
1
B
i
n
d
.
R
o
l
e
⊓
h
I
n
t
e
r
f
a
c
e
⊑
≤
1
B
i
n
d
.
R
o
l
e
.Deductive reasoning rules relate to operational semantics that describes the evolution of a session. They are used to verify the state reachability of service choreography. Every deductive reasoning rule is a Horn clause in the following form: IFantecedent THEN 〈
c
o
n
s
e
q
u
e
n
t
〉, where the antecedent is a conjunction of one or more clauses and the consequent is an assertion of facts.The relationSessionDeduction defines deduction of session evolution. If the precondition p holds and the session S executes an atomic session a making S become the session S
′, then S is deduced to S
′. In particular, the two sessions can be identified by two states, before and after evolution.Choreography model checking may concern two kinds of state. One is the session state that defines whether a session can normally end and successfully complete its job. The other is the application state that defines whether an application that is running on one or more sessions can normally end. As a session will never end until all atomic sessions end, the state space of a session is determined by all possible states of the atomic sessions. Similarly, the state space of an application is determined by all possible states of the sessions.Definition 8 (state reachability).
A state (session state) is reachable provided that there is an evolving session which can be identified by the state and which can be deduced from its ancestor in its initial state.Inference 1.
If the termination states of an application described by a choreography model are reachable, that is, the termination sessions (denoted asNULL) can be deduced from the initial sessions, then all states of the application are reachable and the choreography models are thereby proven correct.The basic deductive reasoning rules are listed as follows:(i)(8)
R
atom
:
a
→
true
,
a
N
U
L
L(ii)(9)
R
s
t
r
u
c
t
:
S
≡
S
′
S
→
p
,
a
T
T
≡
T
′
S
′
→
p
,
a
T
′(iii)(10)
R
seq
1
:
a
·
S
→
true
,
a
S(iv)(11)
R
seq
2
:
S
→
p
,
a
S
′
S
·
T
→
p
,
a
S
′
·
T(v)(12)
R
parallel
:
S
→
p
,
a
S
′
S
T
→
p
,
a
S
′
T(vi)(13)
R
choice
:
S
1
→
p
1
,
a
S
1
′
p
1
S
1
+
p
2
S
2
→
p
1
,
a
S
1
′(vii)(14)
R
nonblock
:
S
→
¬
p
g
,
NULL
S
p
g
p
r
e
p
∗
S
→
¬
p
g
,
NULL
N
U
L
L(viii)(15)
R
norepeat
:
S
→
p
g
∧
¬
p
rep
,
a
S
′
p
g
p
r
e
p
∗
S
→
p
g
∧
¬
p
rep
,
a
S
′(ix)(16)
R
repeat
:
S
→
p
g
∧
p
rep
,
a
S
′
p
g
p
rep
∗
S
→
p
g
∧
p
rep
,
a
S
′
·
p
rep
∗
SR
a
t
o
m is the rule that holds the indivisibility of an atomic session. R
s
t
r
u
c
t is the rule that keeps the congruence in session deduction. R
s
e
q
1 and R
s
e
q
2 are the deduction rules for the sequence sessions. R
p
a
r
a
l
l
e
l is the deduction rule for parallel session that two sessions are parallel executed and one of them evolves. R
c
h
o
i
c
e is the deduction rule for the choice session that if the precondition is true and the atomic session is executed, one of the two sessions will evolve. R
n
o
n
b
l
o
c
k is the deduction rule for the workunit that if the precondition is false and p
g
p
r
e
p
∗
S works in nonblocking mode, the workunit will be skipped. R
n
o
r
e
p
e
a
t is the deduction rule for the workunit that if p
g is “true” and p
r
e
p is “false” S will become S
′ and the workunit will become S
′ after execution of a. R
r
e
p
e
a
t is the deduction rule for the workunit that if both p
g and p
r
e
p are “true” S will become S
′ and the workunit will become S
′
·
p
r
e
p
∗
S after execution of a, where p
r
e
p
∗
S means if p
r
e
p is “true” then S will be iteratively executed.


## 2.2. Application Model of Service Choreography

The metamodel gives a formal definition of the metaconcepts and relations of service choreography and provides fundamental semantics for service choreography description. An application model, an instantiation of the metaconcept model, gives a UML-compliant description and representation of service choreography. To build the model, software engineers would start with analysis of the objectives to be achieved in the choreography and then describe the roles that participants implement, the activities that the roles perform, and the session execution patterns.Definition 9 (application model of service choreography).
The application model of service choreography formally describes the design of service choreography for a distributed application in a UML-compliant representation within the constraint of the metamodel. It comprises three parts:〈
AppConcept,AppRelation,AppFunction
〉.AppConcept is a finite set of application concepts which are defined by instantiating the metaconcepts of the metamodel.AppRelation is a finite set of application relations which are defined by instantiating the metarelations of the metamodel.AppFunction is a set of functions that mapAppConcepttoMetaConcept orAppRelationtoMetaRelation in order to trace the types of application concepts and relations in the metamodel. For example, Buyer is anAppConcept and Role is the correspondingMetaConcept, and thus the function is built as follows:AppFunction(Buyer) = Role.The application model, if built with a universal UML tool, may suffer from the problems of inconsistency, incompleteness, and unreachable states, as mentioned in Section2.1.3. The next section will discuss the technique of transforming the UML-based model into DL ontology to verify the correctness of the model with the help of a popular reasoner.


## 3. Model Transformation and Verification

UML is a semiformal specification language and it does not by itself support logic inference for model checking. A popular solution is to use OCL (Object Constraint Language), a subset of UML for defining domain constraints in first-order predicate logic for model checking. Unfortunately, it is well known that the full expressiveness of OCL may lead to undecidability of reasoning [21]. As a result, the existing methods have to either limit the UML/OCL constructs or decrease the level of automation or balance between the two.To solve the problem, we suggest usingSHOIN(D), the subsystem of DL, to formalize the models. DL is proven powerful in expressibility and decidability for knowledge engineering and allows for making use of some handy reasoning engines, such as Pellet and Racer. But engineers may worry about the fact that it is hard to learn a formal language, hoping that the formal language would be hidden by a software tool.This section will discuss the algorithms for model transformation, the mechanism of model verification based onSHOIN(D), and the way of implementing prototype.


### 3.1. Mechanism for Service Choreography Model Verification Based onSHOIN(D)

In the early stage of our research, we obtained some meaningful achievements in DL-based reasoning. Dong et al. [22, 23] checked the C4ISR (Command, Control, Communication, Computer, Intelligence, Surveillance, and Reconnaissance) domain models to guarantee the consistency and completeness through converting the UML models into the Description Logic ontology and making use of inference engine Pellet. He et al. [24] presented a method of UML behavioral model verification based on Description Logic system. He et al. transformed UML behavioral models to OWL DL ontology, and hence model consistency can be verified with DL supporting reasoner. Zhang [25] tried to transform the service-oriented application models to OWL DL ontology. Based on the above research, we present, as shown in Figure 3, a mechanism for service choreography model verification based onSHOIN(D).Figure 3
Mechanism for service choreography model verification based onSHOIN(D).The principle of conversion and verification is as follows: (1) convert the metaconcepts of service choreography model and domain rules into the axiom sets inSHOIN(D) Tbox and the application concept model into the assertion sets inSHOIN(D) Abox; (2) verify the consistency, completeness, and state reachability with the help of a reasoning engine like Pellet that supports logical reasoning through theSHOIN(D) ontology. The automatic conversion can be realized by Algorithms 1 and 2.Algorithm 1:Construct SHOIN(D) Tbox&Abox.
Input: the meta model and the application model
Output: Tbox, Abox
begin
(1)  Tbox =, Abox = ;
(2) for all  MetaConcepts  C in meta concept model, do
(3)     Tbox =Tbox
∪
c;
(4)if  C
2 is the superclass of C
1, then
Tbox = Tbox
∪
c
1
⊑
c
2;
(5)else if  C has a data attribute X (data type is t), then
Tbox = Tbox
∪
c
⊑
x
⋅
t;
(6)else if  C
1
≠
C
2 and C
1
⊑
C
2
∉ Tbox
andC
2
⊑
C
1
∉ Tbox, then
Tbox = Tbox
∪
c
1
⊓
c
2
=
⌀;
(7)end if;
(8) end for;
(9)
for all  MetaRelation  R
=
(
C
1
,
C
2
) in meta concept model, the relation r
~ is the inverse relation of r, do
Tbox = Tbox
∪
c
1
⊑
∀
r
⋅
c
2
,
c
2
⊑
∀
r
~
⋅
c
1;
(10)end for;
(11)for all the multiplicity constraints in range and domain of every relation R
=
(
C
1
,
C
2
) in meta concept model,
the relationr
~ is the inverse relation of r, do
(12) if multiplicity constraints is “0
⋯
1” then
Tbox = Tbox
∪
c
1
⊑
≤
1
r
⋅
c
2
∪
c
2
⊑
≤
1
r
~
⋅
c
1;
(13) else if multiplicity constraints is “1
⋯
∗” then
Tbox = Tbox
∪
c
1
⊑
≥
1
r
⋅
c
2
∪
c
2
⊑
≥
1
r
~
⋅
c
1;
(14) else if multiplicity constraints is “1” then
Tbox = Tbox
∪
c
1
⊑
≤
1
r
⋅
c
2
,
c
1
⊑
≥
1
r
⋅
c
2
∪
c
2
⊑
≤
1
r
~
⋅
c
1
,
c
2
⊑
≥
1
r
~
⋅
c
1;
(15) end if;
(16)end for;
(17)return Tbox;
(18)for all individuals o in application concept model,
(19)  if  AppFunction(o) = c, do
Abox = Abox
∪
o
∪
o
:
c;
(20)end for;
(21)for all individuals c
1, c
2 in application concept model,
(22)if  AppFunction(r) = R, do
Abox = Abox
∪
c
1
∪
c
2
∪
〈
c
1
,
c
2
〉
:
r;
(23)end for;
(24)return Abox;
endAlgorithm 2:Construct R
SWRL.
Input: Deductive reasoning rules for service choreography model
Output: Deductive reasoning rules based on SWRL, R
SWRL
Begin
Antecedent = , Consequent = , Clause = ;
for all concepts C and relations R in prerequisite and conclusion,
if  C
1,  C
2 has R relation, c
1, c
2 are individuals of C
1, C
2, then
Clause =Clause
∪
R
(
C
1
c
1
,
C
2
c
2
);
else if  C has a attribute P (type is t), then
Clause = Clause
∪
P
(
C
c
,
t
);
end for;
for all clauses cl do
if relation between cl is “and” in prerequisite then
Antecedent =Antecedent
∪
cl
⁡
1
∧
cl
⁡
2;
else if relation between cl is “or” in prerequisite then
Antecedent =Antecedent
∪
cl
⁡
1
∨
cl
⁡
2;
else if relation between cl is “and” in conclusionthen
Consequent =Consequent
∪
cl
⁡
1
∧
cl
⁡
2;
else if relation between cl is “or” in conclusion then
Consequent =Consequent
∪
cl
⁡
1
∨
cl
⁡
2;
end if;
end for;
R
SWRL = Antecedent ∪ Consequent;
return  R
SWRL;
endStep (1) initializes Tbox and Abox. Steps (2)–(10) convert the metaconcepts and relations of the metaconcept model into axiom sets in Tbox. Steps (11)–(17) add multiplicity constraints of metarelations as axiom sets in Tbox. Subsequently, steps (18)–(24) convert application concepts and relations of the application model into assertion sets in Abox. For a more detailed explanation for each step, refer to our previous work in [22, 24]. Our previous work [23] showed that the conversion is correct and there is no semantics loss.The domain rules need to be transformed into axiom sets in Tbox. The consistency and completeness rules are specified in DL and can be added to Tbox through steps (11)–(17), while the deductive reasoning rules need to be specified in SWRL. SWRL combines RuleML and OWL DL. It is popularly applied for formal representation of semantic rules and knowledge-based reasoning, supported by the algorithm Tableau [15].Algorithm2 is provided to convert the deductive reasoning rules in the choreography model into the formally specified rules in SWRL.The concepts and relations appearing in the prerequisite of the deductive reasoning rules are converted to Horn clauses that combine to form the antecedent of SWRL rules, and the concepts and relations appearing in the conclusion are converted to Horn clauses that combine to form the consequent of SWRL rules.For example, the deductive reasoning rulesR
a
t
o
m and R
s
t
r
u
c
t are converted into following SWRL expressions:(17)
i
G
u
a
r
d
S
e
s
s
i
o
n
S
,
P
r
e
c
o
n
d
i
t
i
o
n
p
∧
E
x
c
u
t
i
n
g
S
e
s
s
i
o
n
S
,
S
a
t
o
m
a
∧
B
o
o
l
e
a
n
P
r
e
c
o
n
d
i
t
i
o
n
p
,
t
r
u
e
⟶
S
e
s
s
i
o
n
D
e
d
u
c
t
i
o
n
S
a
t
o
m
a
,
N
U
L
L
ii
S
e
s
s
i
o
n
D
e
d
u
c
t
i
o
n
S
e
s
s
i
o
n
S
,
S
e
s
s
i
o
n
T
∧
C
o
n
g
r
u
e
n
c
e
S
e
s
s
i
o
n
S
,
S
e
s
s
i
o
n
S
′
∧
C
o
n
g
r
u
e
n
c
e
S
e
s
s
i
o
n
T
,
S
e
s
s
i
o
n
T
′
∧
G
u
a
r
d
S
e
s
s
i
o
n
S
,
P
r
e
c
o
n
d
i
t
i
o
n
p
∧
E
x
e
c
u
t
i
n
g
S
e
s
s
i
o
n
S
,
S
a
t
o
m
a
∧
B
o
o
l
e
a
n
P
r
e
c
o
n
d
i
t
i
o
n
p
,
t
r
u
e
⟶
S
e
s
s
i
o
n
D
e
d
u
c
t
i
o
n
S
e
s
s
i
o
n
S
′
,
S
e
s
s
i
o
n
T
′
∧
G
u
a
r
d
S
e
s
s
i
o
n
S
′
,
P
r
e
c
o
n
d
i
t
i
o
n
p
∧
E
x
e
c
u
t
i
n
g
S
e
s
s
i
o
n
S
′
,
S
a
t
o
m
a


### 3.2. Prototype Implementation

Algorithms1 and 2 have been realized and integrated into our requirement analysis tool, the so-called ontology-based requirements elicitation and analysis tool (OBREAT) [25]. The architecture of OBREAT and the major components can be found in Figure 4.Figure 4
Architecture of service hierarchy of OBREAT.The presentation layer handles the interaction between users and the application. It checks and takes user input, as well as feedbacks on execution information including reasoning results. Currently, there are a variety of modeling notations, such as UML [26–31], Message Sequence Charts (MSCs) [32], and BPMN [33, 34], to visually model the choreography interaction. In our research, the UML class diagrams and collaboration diagrams (or Communication Diagrams in [35]) are preferred for the presentation of service choreography models from structural and behavioral viewpoint, respectively, taking the advantages of rigorous syntax and semantics, easiness to interpret, and various tools such as RSA, EA, and Rose to share some part of models.As the core component of the architecture, the logic layer processes modeling transactions and submits results to the presentation layer, and it also communicates with the data layer for data persistency. TheDL-based Formal Model Generator handles the model conversion with the algorithms mentioned before. The output of the generator is sent to theModel Feature Reasonerand then is saved inFormal Model database. TheModel Feature Reasoner communicates with DL reasoner Pellet to complete DL-based reasoning and sends the results to theExecution Control Interface. At present, theModel Feature Reasoner realizes checking the property of consistency, completeness, and state reachability. Specifically, the results are also exported to theDomain Knowledge base to enrich domain knowledge for reuse and thus knowledge reusability is continuously enhanced with knowledge accumulation.The data layer handles data persistency and maintenance. Most of the input/output data are saved as files, either model files or formalized files, while model management data are saved in the databaseSystem Administration Database.For the sake of model exchange, we adopt XML as the model data description language. Since the DL-based reasoner accepts data only in OWL which is somewhat different from XML, the conversion between two types of XML documents is needed. To automate the conversion, we choose the eXtensible Stylesheet Language Transformation (XSLT) technology [36, 37] which is widely used for XML document conversion. We designed a set of XSLT transformation templates compliant with the Ontology Definition Metamodel (ODM) and the UML profile. Moreover, we integrate MagicDraw [38] in OBREAT as the GUI modeling tool in the presentation layer and Pellet 1.5.0 as the DL-based reasoner in the logic layer for verification reasoning.


## 3.1. Mechanism for Service Choreography Model Verification Based onSHOIN(D)

In the early stage of our research, we obtained some meaningful achievements in DL-based reasoning. Dong et al. [22, 23] checked the C4ISR (Command, Control, Communication, Computer, Intelligence, Surveillance, and Reconnaissance) domain models to guarantee the consistency and completeness through converting the UML models into the Description Logic ontology and making use of inference engine Pellet. He et al. [24] presented a method of UML behavioral model verification based on Description Logic system. He et al. transformed UML behavioral models to OWL DL ontology, and hence model consistency can be verified with DL supporting reasoner. Zhang [25] tried to transform the service-oriented application models to OWL DL ontology. Based on the above research, we present, as shown in Figure 3, a mechanism for service choreography model verification based onSHOIN(D).Figure 3
Mechanism for service choreography model verification based onSHOIN(D).The principle of conversion and verification is as follows: (1) convert the metaconcepts of service choreography model and domain rules into the axiom sets inSHOIN(D) Tbox and the application concept model into the assertion sets inSHOIN(D) Abox; (2) verify the consistency, completeness, and state reachability with the help of a reasoning engine like Pellet that supports logical reasoning through theSHOIN(D) ontology. The automatic conversion can be realized by Algorithms 1 and 2.Algorithm 1:Construct SHOIN(D) Tbox&Abox.
Input: the meta model and the application model
Output: Tbox, Abox
begin
(1)  Tbox =, Abox = ;
(2) for all  MetaConcepts  C in meta concept model, do
(3)     Tbox =Tbox
∪
c;
(4)if  C
2 is the superclass of C
1, then
Tbox = Tbox
∪
c
1
⊑
c
2;
(5)else if  C has a data attribute X (data type is t), then
Tbox = Tbox
∪
c
⊑
x
⋅
t;
(6)else if  C
1
≠
C
2 and C
1
⊑
C
2
∉ Tbox
andC
2
⊑
C
1
∉ Tbox, then
Tbox = Tbox
∪
c
1
⊓
c
2
=
⌀;
(7)end if;
(8) end for;
(9)
for all  MetaRelation  R
=
(
C
1
,
C
2
) in meta concept model, the relation r
~ is the inverse relation of r, do
Tbox = Tbox
∪
c
1
⊑
∀
r
⋅
c
2
,
c
2
⊑
∀
r
~
⋅
c
1;
(10)end for;
(11)for all the multiplicity constraints in range and domain of every relation R
=
(
C
1
,
C
2
) in meta concept model,
the relationr
~ is the inverse relation of r, do
(12) if multiplicity constraints is “0
⋯
1” then
Tbox = Tbox
∪
c
1
⊑
≤
1
r
⋅
c
2
∪
c
2
⊑
≤
1
r
~
⋅
c
1;
(13) else if multiplicity constraints is “1
⋯
∗” then
Tbox = Tbox
∪
c
1
⊑
≥
1
r
⋅
c
2
∪
c
2
⊑
≥
1
r
~
⋅
c
1;
(14) else if multiplicity constraints is “1” then
Tbox = Tbox
∪
c
1
⊑
≤
1
r
⋅
c
2
,
c
1
⊑
≥
1
r
⋅
c
2
∪
c
2
⊑
≤
1
r
~
⋅
c
1
,
c
2
⊑
≥
1
r
~
⋅
c
1;
(15) end if;
(16)end for;
(17)return Tbox;
(18)for all individuals o in application concept model,
(19)  if  AppFunction(o) = c, do
Abox = Abox
∪
o
∪
o
:
c;
(20)end for;
(21)for all individuals c
1, c
2 in application concept model,
(22)if  AppFunction(r) = R, do
Abox = Abox
∪
c
1
∪
c
2
∪
〈
c
1
,
c
2
〉
:
r;
(23)end for;
(24)return Abox;
endAlgorithm 2:Construct R
SWRL.
Input: Deductive reasoning rules for service choreography model
Output: Deductive reasoning rules based on SWRL, R
SWRL
Begin
Antecedent = , Consequent = , Clause = ;
for all concepts C and relations R in prerequisite and conclusion,
if  C
1,  C
2 has R relation, c
1, c
2 are individuals of C
1, C
2, then
Clause =Clause
∪
R
(
C
1
c
1
,
C
2
c
2
);
else if  C has a attribute P (type is t), then
Clause = Clause
∪
P
(
C
c
,
t
);
end for;
for all clauses cl do
if relation between cl is “and” in prerequisite then
Antecedent =Antecedent
∪
cl
⁡
1
∧
cl
⁡
2;
else if relation between cl is “or” in prerequisite then
Antecedent =Antecedent
∪
cl
⁡
1
∨
cl
⁡
2;
else if relation between cl is “and” in conclusionthen
Consequent =Consequent
∪
cl
⁡
1
∧
cl
⁡
2;
else if relation between cl is “or” in conclusion then
Consequent =Consequent
∪
cl
⁡
1
∨
cl
⁡
2;
end if;
end for;
R
SWRL = Antecedent ∪ Consequent;
return  R
SWRL;
endStep (1) initializes Tbox and Abox. Steps (2)–(10) convert the metaconcepts and relations of the metaconcept model into axiom sets in Tbox. Steps (11)–(17) add multiplicity constraints of metarelations as axiom sets in Tbox. Subsequently, steps (18)–(24) convert application concepts and relations of the application model into assertion sets in Abox. For a more detailed explanation for each step, refer to our previous work in [22, 24]. Our previous work [23] showed that the conversion is correct and there is no semantics loss.The domain rules need to be transformed into axiom sets in Tbox. The consistency and completeness rules are specified in DL and can be added to Tbox through steps (11)–(17), while the deductive reasoning rules need to be specified in SWRL. SWRL combines RuleML and OWL DL. It is popularly applied for formal representation of semantic rules and knowledge-based reasoning, supported by the algorithm Tableau [15].Algorithm2 is provided to convert the deductive reasoning rules in the choreography model into the formally specified rules in SWRL.The concepts and relations appearing in the prerequisite of the deductive reasoning rules are converted to Horn clauses that combine to form the antecedent of SWRL rules, and the concepts and relations appearing in the conclusion are converted to Horn clauses that combine to form the consequent of SWRL rules.For example, the deductive reasoning rulesR
a
t
o
m and R
s
t
r
u
c
t are converted into following SWRL expressions:(17)
i
G
u
a
r
d
S
e
s
s
i
o
n
S
,
P
r
e
c
o
n
d
i
t
i
o
n
p
∧
E
x
c
u
t
i
n
g
S
e
s
s
i
o
n
S
,
S
a
t
o
m
a
∧
B
o
o
l
e
a
n
P
r
e
c
o
n
d
i
t
i
o
n
p
,
t
r
u
e
⟶
S
e
s
s
i
o
n
D
e
d
u
c
t
i
o
n
S
a
t
o
m
a
,
N
U
L
L
ii
S
e
s
s
i
o
n
D
e
d
u
c
t
i
o
n
S
e
s
s
i
o
n
S
,
S
e
s
s
i
o
n
T
∧
C
o
n
g
r
u
e
n
c
e
S
e
s
s
i
o
n
S
,
S
e
s
s
i
o
n
S
′
∧
C
o
n
g
r
u
e
n
c
e
S
e
s
s
i
o
n
T
,
S
e
s
s
i
o
n
T
′
∧
G
u
a
r
d
S
e
s
s
i
o
n
S
,
P
r
e
c
o
n
d
i
t
i
o
n
p
∧
E
x
e
c
u
t
i
n
g
S
e
s
s
i
o
n
S
,
S
a
t
o
m
a
∧
B
o
o
l
e
a
n
P
r
e
c
o
n
d
i
t
i
o
n
p
,
t
r
u
e
⟶
S
e
s
s
i
o
n
D
e
d
u
c
t
i
o
n
S
e
s
s
i
o
n
S
′
,
S
e
s
s
i
o
n
T
′
∧
G
u
a
r
d
S
e
s
s
i
o
n
S
′
,
P
r
e
c
o
n
d
i
t
i
o
n
p
∧
E
x
e
c
u
t
i
n
g
S
e
s
s
i
o
n
S
′
,
S
a
t
o
m
a


## 3.2. Prototype Implementation

Algorithms1 and 2 have been realized and integrated into our requirement analysis tool, the so-called ontology-based requirements elicitation and analysis tool (OBREAT) [25]. The architecture of OBREAT and the major components can be found in Figure 4.Figure 4
Architecture of service hierarchy of OBREAT.The presentation layer handles the interaction between users and the application. It checks and takes user input, as well as feedbacks on execution information including reasoning results. Currently, there are a variety of modeling notations, such as UML [26–31], Message Sequence Charts (MSCs) [32], and BPMN [33, 34], to visually model the choreography interaction. In our research, the UML class diagrams and collaboration diagrams (or Communication Diagrams in [35]) are preferred for the presentation of service choreography models from structural and behavioral viewpoint, respectively, taking the advantages of rigorous syntax and semantics, easiness to interpret, and various tools such as RSA, EA, and Rose to share some part of models.As the core component of the architecture, the logic layer processes modeling transactions and submits results to the presentation layer, and it also communicates with the data layer for data persistency. TheDL-based Formal Model Generator handles the model conversion with the algorithms mentioned before. The output of the generator is sent to theModel Feature Reasonerand then is saved inFormal Model database. TheModel Feature Reasoner communicates with DL reasoner Pellet to complete DL-based reasoning and sends the results to theExecution Control Interface. At present, theModel Feature Reasoner realizes checking the property of consistency, completeness, and state reachability. Specifically, the results are also exported to theDomain Knowledge base to enrich domain knowledge for reuse and thus knowledge reusability is continuously enhanced with knowledge accumulation.The data layer handles data persistency and maintenance. Most of the input/output data are saved as files, either model files or formalized files, while model management data are saved in the databaseSystem Administration Database.For the sake of model exchange, we adopt XML as the model data description language. Since the DL-based reasoner accepts data only in OWL which is somewhat different from XML, the conversion between two types of XML documents is needed. To automate the conversion, we choose the eXtensible Stylesheet Language Transformation (XSLT) technology [36, 37] which is widely used for XML document conversion. We designed a set of XSLT transformation templates compliant with the Ontology Definition Metamodel (ODM) and the UML profile. Moreover, we integrate MagicDraw [38] in OBREAT as the GUI modeling tool in the presentation layer and Pellet 1.5.0 as the DL-based reasoner in the logic layer for verification reasoning.


## 4. Case Study

In this section, a simplified case of purchase order application of the e-commerce system is studied, illustrating how to construct the application model and how to realize the model verification.


### 4.1. Construction of Application Model

Limited by the page size, the choreography of the purchase order application is simplified here, and it covers only a few main activities: the buyer sends an order request to the seller, and then the seller checks the buyer’s credit record in the bank and the supplier inventory. If the credit record is good and the inventory is sufficient, then the order will be accepted; otherwise, it will be rejected.The above activities are encapsulated into five sessions: purchase order request (S
_
p
o
R
e
q), credit check (S
_
c
r
e
d
C
h
e), inventory check (S
_
i
n
v
C
h
e), purchase order response (S
_
p
o
R
e
s
p), and purchase order reject (S
_
p
o
R
e
j), where there are four participant roles:Buyer,Seller,Bank, andSupplier.The buyer initiates an interaction with the seller by placing a purchase orderpo through the channelCh@Seller, and then the seller acknowledges the buyer by sending him apoAck. Meanwhile, the states of the purchase orders ofBuyer andSeller are set to “sent” and “received,” respectively. Accordingly, the session S
_
p
o
R
e
q is composed of four atomic sessions which are specified as follows and is modeled as a UML class diagram in Figure 5:(18)
S
_
p
o
R
e
q
=
S
_
p
o
R
e
q
_
r
e
q
B
u
y
e
r
.
p
o
⟶
S
e
l
l
e
r
.
p
o
,
C
h
@
S
e
l
l
e
r
·
S
_
p
o
R
e
q
_
r
e
s
p
B
u
y
e
r
.
p
o
A
c
k
⟵
S
e
l
l
e
r
.
p
o
A
c
k
,
C
h
@
B
u
y
e
r
·
S
_
p
o
R
e
q
_
a
s
s
i
g
n
_
B
u
y
e
r
B
u
y
e
r
.
p
o
S
t
a
t
e
=
"
s
e
n
t
"
·
S
_
p
o
R
e
q
_
a
s
s
i
g
n
_
S
e
l
l
e
r
S
e
l
l
e
r
.
p
o
S
t
a
t
e
=
"
r
e
c
e
i
v
e
d
"Figure 5
Structure ofS_poReq.The other four sessions function as follows:S
_
c
r
e
d
C
h
e checks the buyer’s credit by sending a request to the bank that sends back the state of the credit (good or bad); S
_
i
n
v
C
h
e checks the seller’s inventory by sending a request to the seller who sends back the state of the inventory (sufficient or short); S
_
p
o
R
e
s
p declares that the order has been accepted if the buyer’s credit is good and the inventory is sufficient; and S
_
p
o
R
e
j declares that the order has been rejected if the buyer’s credit is bad or the inventory is short. The four sessions are specified as follows, while the related class models are omitted due to space limitation: (19)
S
_
c
r
e
d
C
h
e
=
S
_
c
r
e
d
C
h
e
_
r
e
q
-
r
e
s
p
(
S
e
l
l
e
r
.
c
c
R
e
q
⟶
B
a
n
k
.
c
c
R
e
q
,
S
e
l
l
e
r
.
c
c
R
e
s
p
⟵
B
a
n
k
.
c
c
R
e
s
p
,
C
h
@
S
e
l
l
e
r
)
·
S
_
c
r
e
d
C
h
e
_
a
s
s
i
g
n
_
S
e
l
l
e
r
.
c
c
R
e
s
p
S
e
l
l
e
r
.
c
c
R
e
s
p
=
"
g
o
o
d
"
/
"
b
a
d
"
·
S
_
c
r
e
d
C
h
e
_
a
s
s
i
g
n
_
B
a
n
k
.
c
c
S
t
a
t
e
B
a
n
k
.
c
c
S
t
a
t
e
=
"
s
e
n
t
"
·
S
_
c
r
e
d
C
h
e
_
a
s
s
i
g
n
_
S
e
l
l
e
r
.
c
c
S
t
a
t
e
S
e
l
l
e
r
.
c
c
S
t
a
t
e
=
"
r
e
c
e
i
v
e
d
"
S
_
i
n
v
C
h
e
=
S
_
i
n
v
C
h
e
_
r
e
q
-
r
e
s
p
(
S
e
l
l
e
r
.
i
c
R
e
q
⟶
S
u
p
p
l
i
e
r
.
i
c
R
e
q
,
S
e
l
l
e
r
.
i
c
R
e
s
p
⟵
S
u
p
p
l
i
e
r
.
i
c
R
e
s
p
,
C
h
@
S
e
l
l
e
r
)
·
S
_
i
n
v
C
h
e
_
a
s
s
i
g
n
_
S
e
l
l
e
r
.
i
c
R
e
s
p
S
e
l
l
e
r
.
i
c
R
e
s
p
=
"
s
u
f
f
i
c
i
e
n
t
"
/
"
s
h
o
r
t
"
·
S
_
i
n
v
C
h
e
_
a
s
s
i
g
n
_
S
u
p
p
l
i
e
r
.
i
c
S
t
a
t
e
S
u
p
p
l
i
e
r
.
i
c
S
t
a
t
e
=
"
s
e
n
t
"
·
S
_
i
n
v
C
h
e
_
a
s
s
i
g
n
_
S
e
l
l
e
r
.
i
c
S
t
a
t
e
S
e
l
l
e
r
.
i
c
S
t
a
t
e
=
"
r
e
c
e
i
v
e
d
"
S
_
p
o
R
e
s
p
=
S
_
p
o
R
e
s
p
_
r
e
s
p
B
u
y
e
r
.
p
o
R
e
s
p
⟵
S
e
l
l
e
r
.
p
o
R
e
s
p
,
C
h
@
B
u
y
e
r
·
S
_
p
o
R
e
s
p
_
a
s
s
i
g
n
_
B
u
y
e
r
.
p
o
S
t
a
t
e
B
u
y
e
r
.
p
o
S
t
a
t
e
=
"
c
o
m
p
l
e
t
e
d
"
·
S
_
p
o
R
e
s
p
_
a
s
s
i
g
n
_
S
e
l
l
e
r
.
p
o
S
t
a
t
e
S
e
l
l
e
r
.
p
o
S
t
a
t
e
=
"
c
o
m
p
l
e
t
e
d
"
S
_
p
o
R
e
j
=
S
_
p
o
R
e
j
_
r
e
s
p
B
u
y
e
r
.
p
o
R
e
s
p
⟵
S
e
l
l
e
r
.
p
o
R
e
s
p
,
C
h
@
B
u
y
e
r
·
S
_
p
o
R
e
j
_
a
s
s
i
g
n
_
B
u
y
e
r
.
p
o
S
t
a
t
e
B
u
y
e
r
.
p
o
S
t
a
t
e
=
"
u
n
c
o
m
p
l
e
t
e
d
"
·
S
_
p
o
R
e
j
_
a
s
s
i
g
n
_
S
e
l
l
e
r
.
p
o
S
t
a
t
e
S
e
l
l
e
r
.
p
o
S
t
a
t
e
=
"
u
n
c
o
m
p
l
e
t
e
d
"The interaction sequence companied with the participants and key messages can be modeled as a UML communication diagram, as shown in Figure6.Figure 6
Interaction between roles in the choreography.Having analyzed the interaction and the functions of the sessions, we can organize the choreography of the purchase order application as follows:(20)
C
h
o
_
p
o
=
S
_
p
o
R
e
q
·
S
_
c
r
e
d
C
h
e
∥
S
_
i
n
v
C
h
e
·
S
_
p
o
R
e
s
p
+
S
_
p
o
R
e
j and specify the preconditions of the sessions as follows: (21)
P
_
c
r
e
d
C
h
e
=
p
_
i
n
v
C
h
e
P
_
c
r
e
d
C
h
e
=
B
u
y
e
r
.
p
o
S
t
a
t
e
=
"
s
e
n
t
"
∧
S
e
l
l
e
r
.
p
o
S
t
a
t
e
=
"
r
e
c
e
i
v
e
d
"
;
P
_
p
o
R
e
s
p
=
(
S
e
l
l
e
r
.
c
c
R
e
s
p
=
"
g
o
o
d
"
∧
S
e
l
l
e
r
.
i
c
R
e
s
p
=
"
s
u
f
f
i
c
i
e
n
t
"
∧
S
e
l
l
e
r
.
c
c
S
t
a
t
e
=
S
e
l
l
e
r
.
i
c
S
t
a
t
e
=
"
r
e
c
e
i
v
e
d
"
)
;
P
_
p
o
R
e
j
=
(
S
e
l
l
e
r
.
c
c
R
e
s
p
=
"
b
a
d
"
∨
S
e
l
l
e
r
.
i
c
R
e
s
p
=
"
s
h
o
r
t
"
∧
S
e
l
l
e
r
.
c
c
S
t
a
t
e
=
S
e
l
l
e
r
.
i
c
S
t
a
t
e
=
"
r
e
c
e
i
v
e
d
"
)
.Furthermore, theSHOIN(D) ontology can be generated by the algorithm Construct Tbox&Abox, and as a result, the axiom set in Tbox and the instance set in Abox are listed as in Table 3.Table 3
Axiom set and instances set of purchase order service choreography model (fragment).
Axiom set in Tbox
Instances set in Abox
NoAction⊑ Abas SilentAction ⊑ Abas InterAction ⊑ Abas Assign ⊑ Abas Perform ⊑ Abas Abas ⊑ Act Astr ⊑ Act
S
a
t
o
m
⊑
Session
S
c
o
m
⊑
Session Session ⊑
∀ SessionDeduction.Session Participant ⊑
∀ Implement.Role Choreography ⊑
∀ Contain.Session Interaction ⊑
∀ Depend.Channel Role ⊑
∀ Belong_to.Participant Interface ⊑
∀ Bind.Role Session ⊑
∀ Executing. S
a
t
o
m Session ⊑
∀ Sequence. Session Session ⊑
∀ Choice. Session ⋮
S_poReq: S
c
o
m
S_poReq_req: S
a
t
o
m
S_poReq_resp: S
a
t
o
m
S_poReq_assign_Buyer: S
a
t
o
m
S_poReq_assign_Seller: S
a
t
o
m
S_credChe: S
c
o
m
S_poResp: S
c
o
m ProductTrader: Participant ServiceProvider: Participant
S_credChe   S_invChe S_Che: S
parallel
S_poResp + S_poRej: S
choice Cho_po: Choreography Buyer: Role Supplier: Role
P_credChe: Precondition
〈Cho_po, S_poReq〉: Contain
〈
S_credChe, P_credChe〉: Guard
〈
S_poReq, S_poReq_req〉: Executing
〈
S_credChe, S_invChe〉: Parallel
〈
S_poReq, S_credChe   S_invChe S_Che〉: Sequence ⋮


### 4.2. Verification of Application Model

Having constructed the application model which is subsequently converted into theSHOIN(D) ontology, we can check the correctness properties of consistency, completeness, and state reachability of the specified choreography separately in the following cases.Case 1 (consistency checking).
Consistency checking is to check whether there is a conceptual conflict against modeling semantics; that is, giving a group of related concepts in the application model, the relationships defined between the concepts should semantically abide by the metarelation declared in the metamodel.Suppose that the modeler tries to add in the application model a relation ofExecuting between theRole Buyer and thesession S_poReq. But according to the constraints of themetamodel, such relation should only appear between two sessions and thus the consistency rule R
c
o
n
1 is broken. The error can be easily found through ontology consistency checking using Pellet.Case 2 (completeness checking).
The completeness checking is to check whether there is a lack of concept or relation in the application model; that is, giving a group of related concepts, the relationships defined between the concepts should quantitatively abide by the multiplicity constraint of the corresponding metarelation in the metamodel.Suppose that the modeler tries to build aBelong_to relation between theRole Supplier and theParticipantProductTrader, meaning that Supplier belongs to a product trader, but wrongly add at the same time anotherBelong_to relation between Supplier and ServiceProvider. Such relation violates the multiplicity constraint R
c
o
n
1 that means eachRole must belong to only oneParticipant at any time. The checking result is prompted by Pellet as follows: “Consistent: No Reason: The individual Supplier has more than one value for property Belong_to violating the cardinality restriction.”Case 3 (state reachability checking).
The state reachability checking is to examine whether the termination state of a session defined in the application model is reachable; that is, the session can be deduced using the deductive reasoning rules given in Section2.1.3. If all sessions are deducible, implying that all session states are reachable, the application behavior is verified.Session S_poReq is deduced with the deductive reasoning rules R
a
t
o
m and R
s
e
q
2 and as a result, poState of Buyer will be set to “sent” and the poState of Seller will be set to “received.” The reasoning process is shown as follows:(22)
S
_
p
o
R
e
q
=
S
_
p
o
R
e
q
_
r
e
q
B
u
y
e
r
.
p
o
⟶
S
e
l
l
e
r
.
p
o
,
C
h
@
S
e
l
l
e
r
S
_
p
o
R
e
q
=
·
S
_
p
o
R
e
q
_
r
e
s
p
B
u
y
e
r
.
p
o
A
c
k
⟵
S
e
l
l
e
r
.
p
o
A
c
k
,
C
h
@
B
u
y
e
r
S
_
p
o
R
e
q
=
·
S
_
p
o
R
e
q
_
a
s
s
i
g
n
_
B
u
y
e
r
B
u
y
e
r
.
p
o
S
t
a
t
e
=
"
s
e
n
t
"
S
_
p
o
R
e
q
=
·
S
_
p
o
R
e
q
_
a
s
s
i
g
n
_
S
e
l
l
e
r
S
e
l
l
e
r
.
p
o
S
t
a
t
e
=
"
r
e
c
e
i
v
e
d
"
→
t
r
u
e
,
a
=
S
_
p
o
R
e
q
_
r
e
q
B
u
y
e
r
.
p
o
→
S
e
l
l
e
r
.
p
o
,
C
h
@
S
e
l
l
e
r
S
_
p
o
i
R
e
q
=
N
U
L
L
S
_
p
o
R
e
q
=
·
S
_
p
o
R
e
q
_
r
e
s
p
B
u
y
e
r
.
p
o
A
c
k
⟵
S
e
l
l
e
r
.
p
o
A
c
k
,
C
h
@
B
u
y
e
r
S
_
p
o
R
e
q
=
·
S
_
p
o
R
e
q
_
a
s
s
i
g
n
_
B
u
y
e
r
B
u
y
e
r
.
p
o
S
t
a
t
e
=
"
s
e
n
t
"
S
_
p
o
R
e
q
=
·
S
_
p
o
R
e
q
_
a
s
s
i
g
n
_
S
e
l
l
e
r
S
e
l
l
e
r
.
p
o
S
t
a
t
e
=
"
r
e
c
e
i
v
e
d
"
→
t
r
u
e
,
a
=
S
_
p
o
R
e
q
_
r
e
s
p
B
u
y
e
r
.
p
o
A
c
k
←
S
e
l
l
e
r
.
p
o
A
c
k
,
C
h
@
B
u
y
e
r
S
_
p
o
i
R
e
q
=
N
U
L
L
S
_
p
o
R
e
q
=
·
S
_
p
o
R
e
q
_
a
s
s
i
g
n
_
B
u
y
e
r
B
u
y
e
r
.
p
o
S
t
a
t
e
=
"
s
e
n
t
"
S
_
p
o
R
e
q
=
·
S
_
p
o
R
e
q
_
a
s
s
i
g
n
_
S
e
l
l
e
r
S
e
l
l
e
r
.
p
o
S
t
a
t
e
=
"
r
e
c
e
i
v
e
d
"
→
t
r
u
e
,
a
=
S
_
p
o
R
e
q
_
a
s
s
i
g
n
_
B
u
y
e
r
B
u
y
e
r
.
p
o
S
t
a
t
e
=
"
s
e
n
t
"
S
_
p
o
i
R
e
q
=
N
U
L
L
S
_
p
o
R
e
q
=
·
S
_
p
o
R
e
q
_
a
s
s
i
g
n
_
S
e
l
l
e
r
S
e
l
l
e
r
.
p
o
S
t
a
t
e
=
"
r
e
c
e
i
v
e
d
"
→
t
r
u
e
,
S
_
p
o
R
e
q
_
a
s
s
i
g
n
_
S
e
l
l
e
r
S
e
l
l
e
r
.
p
o
S
t
a
t
e
=
"
r
e
c
e
i
v
e
d
"
S
_
p
o
i
R
e
q
=
N
U
L
LThe other four sessions credit check (S
_
c
r
e
d
C
h
e), inventory check (S
_
i
n
v
C
h
e), purchase order response (S
_
p
o
R
e
s
p), and purchase order reject (S
_
p
o
R
e
j) can be deduced in the same way.The whole reasoning process for the application choreography modelC
h
o
_
p
o is shown as follows, where the deduction rules applied to each step are bracketed with :(23)
C
h
o
_
p
o
=
S
_
p
o
R
e
q
·
S
_
c
r
e
d
C
h
e
∥
S
_
i
n
v
C
h
e
·
S
_
p
o
R
e
s
p
+
S
_
p
o
R
e
j
→
R
a
t
o
m
,
R
s
e
q
2
t
r
u
e
,
a
∗
N
U
L
L
·
S
_
c
r
e
d
C
h
e
∥
S
_
i
n
v
C
h
e
·
S
_
p
o
R
e
s
p
+
S
_
p
o
R
e
j
→
C
6
S
_
c
r
e
d
C
h
e
∥
S
_
i
n
v
C
h
e
·
S
_
p
o
R
e
s
p
+
S
_
p
o
R
e
j
→
R
a
t
o
m
,
R
p
a
r
a
l
l
e
l
P
_
c
r
e
d
C
h
e
,
a
∗
∗
N
U
L
L
∥
S
_
i
n
v
C
h
e
·
S
_
p
o
R
e
s
p
+
S
_
p
o
R
e
j
→
C
5
S
_
i
n
v
C
h
e
·
S
_
p
o
R
e
s
p
+
S
_
p
o
R
e
j
→
R
a
t
o
m
,
R
s
e
q
2
p
_
i
n
v
C
h
e
,
a
∗
∗
∗
N
U
L
L
·
S
_
p
o
R
e
s
p
+
S
_
p
o
R
e
j
→
C
6
S
_
p
o
R
e
s
p
+
S
_
p
o
R
e
j
→
P
_
p
o
R
e
s
p
,
a
∗
∗
∗
∗
N
U
L
LThe atomic sessions in each step are as follows:(24)
a
∗
=
S
_
p
o
R
e
q
_
r
e
q
·
S
_
p
o
R
e
q
_
r
e
s
p
·
S
_
p
o
R
e
q
_
a
s
s
i
g
n
_
B
u
y
e
r
·
S
_
p
o
R
e
q
_
a
s
s
i
g
n
_
S
e
l
l
e
r
a
∗
∗
=
S
_
c
r
e
d
C
h
e
_
r
e
q
-
r
e
s
p
·
S
_
c
r
e
d
C
h
e
_
a
s
s
i
g
n
_
S
e
l
l
e
r
.
c
c
R
e
s
p
·
S
_
c
r
e
d
C
h
e
_
a
s
s
i
g
n
_
B
a
n
k
.
c
c
S
t
a
t
e
·
S
_
c
r
e
d
C
h
e
_
a
s
s
i
g
n
_
S
e
l
l
e
r
.
c
c
S
t
a
t
e
a
∗
∗
∗
=
S
_
i
n
v
C
h
e
_
r
e
q
-
r
e
s
p
·
S
_
i
n
v
C
h
e
_
a
s
s
i
g
n
_
S
e
l
l
e
r
.
i
c
R
e
s
p
·
S
_
i
n
v
C
h
e
_
a
s
s
i
g
n
_
S
u
p
p
l
i
e
r
.
i
c
S
t
a
t
e
·
S
_
i
n
v
C
h
e
_
a
s
s
i
g
n
_
S
e
l
l
e
r
.
i
c
S
t
a
t
e
a
∗
∗
∗
∗
=
S
_
p
o
R
e
s
p
_
r
e
s
p
·
S
_
p
o
R
e
s
p
_
a
s
s
i
g
n
_
B
u
y
e
r
.
p
o
S
t
a
t
e
·
S
_
p
o
R
e
s
p
_
a
s
s
i
g
n
_
S
e
l
l
e
r
.
p
o
S
t
a
t
eThe application behavior is proven correct provided that the reasoning process may eventually end byNULL. Otherwise, there must be a session failed to be deduced (i.e., its termination state is not reachable). If the application may reach the final state, the key attribute poState of both Buyer and Seller will be set to either “completed” or “uncompleted” (this may happen when B
y
u
e
r
.
c
c
R
e
s
p
=
"
b
a
d
" or S
e
l
l
e
r
.
i
c
R
e
s
p
=
"
s
h
o
r
t
").To give a negative example, we deliberately assign Seller.poState = “” to make false the preconditionP_credChe. As a result, the reasoning process rests on the second step, as the session S_credChe cannot be deduced, and therefore all states of the sessions followed cannot be reached. The exception can be found by entering the following DL-based query command in the form of SPARQL [24]:SELECT ? a WHERE? a rdf:type xmlns: Session.? a xmlns: SessionDeduction ? N
U
L
L
..Figure7 shows the query result in the human interface panel of the reasoner Pellet, indicating that the session S_poReq and its four atomic sessions are deduced (or can be successfully executed), while all of the subsequent sessions are not shown (or the corresponding states of these sessions may not be reached). The rules 〈
R
a
t
o
m
,
R
s
e
q
2
〉 are applied to the reasoning process to find the exception where theSessionDeduction relation is broken between the sessions S_poReq and S_credChe and all of the followed sessions cannot be deduced.Figure 7
The query command window for checking the state reachability.Beside the above experiment, we have also modeled and verified several other cases, including the online shopping example given in [39], the buyer-seller example given in [40], and the example from the supply chain management [41].The verification is processed efficiently. The reasoning for each case is finished within a second, tested on a laptop computer with a 2 GHz Intel processor and 1 GB of RAM. That accords with the comments by Haarslev and Möller [42] who pointed out that even for the hardest problems the query time for DL reasoning would be within three seconds. But, is it always true?In order to evaluate the efficiency of reasoning for CML-DL models, we choose the four popular ontologies, VICODI, LUBM, Semintec, and Wine which are used in previous benchmarks, carry out experiment, and lead a statistical analysis by comparing the average response times against the increasing size of Abox. The detailed descriptions about these ontologies can be found in [43].The ontologies represent four standard benchmark datasets with different complexity. The VICODI ontology is relatively small and simple since it does not contain any disjunctions, existential quantification, or number restrictions. The LUBM ontology and the Semintec ontology are also relatively simple like the VICODI ontology, while the Semintec ontology is more complex since it contains functional properties and disjointness constraints and is constructed using OWL DL. The Wine ontology is the most complex one. It contains a classification of wines and is established using advanced DL constructors.The above ontologies are too small in Abox for our intended performance evaluations. Therefore, we generate different sizes of datasets, ranging from 100 to 1 million, to increase the Aboxes of the ontologies for test.To evaluate the query times for various sizes of the datasets, we use several query patterns covering all cases from the simplest one that retrieves all individuals of one concept to the most complex one that retrieves all individuals of the concept. The test method can be referenced by [44].Figure8 shows the average time for query response for the four ontologies with the generated datasets sizing from 100 to 1 Mio. All the results reported are averaged over 100 queries. The test is led on a laptop computer with one 2 GHz Intel processor and 1 GB of RAM, running Windows XP Service Pack 4.Figure 8
Average query time for the four ontologies (VICODI, LUBM, Semintec, and Wine).As expected, there is a significant increase of query time as the size of the ontology increases from the 100 to 1 million. For the example of the Semintec ontology, the average query time for smaller size from 100 to 10,000 is less than a second (<1). But, the time increases sharply as the size exceeds 10,000, and for the maximum size of 1 Mio., the time is about 800 seconds or about 17 minutes.Our ontology of CML-DL may match the Semintec ontology since the domain of the CML-DL application is not more complex than that of the financial services, and the model can be constructed using a fragment of OWL DL without advanced DL constructors. Therefore, we expect that the number of individuals of the CML-DL application model, for most projects, would be less than 100000, and thus the reasoning time would be within a few minutes at worst.


## 4.1. Construction of Application Model

Limited by the page size, the choreography of the purchase order application is simplified here, and it covers only a few main activities: the buyer sends an order request to the seller, and then the seller checks the buyer’s credit record in the bank and the supplier inventory. If the credit record is good and the inventory is sufficient, then the order will be accepted; otherwise, it will be rejected.The above activities are encapsulated into five sessions: purchase order request (S
_
p
o
R
e
q), credit check (S
_
c
r
e
d
C
h
e), inventory check (S
_
i
n
v
C
h
e), purchase order response (S
_
p
o
R
e
s
p), and purchase order reject (S
_
p
o
R
e
j), where there are four participant roles:Buyer,Seller,Bank, andSupplier.The buyer initiates an interaction with the seller by placing a purchase orderpo through the channelCh@Seller, and then the seller acknowledges the buyer by sending him apoAck. Meanwhile, the states of the purchase orders ofBuyer andSeller are set to “sent” and “received,” respectively. Accordingly, the session S
_
p
o
R
e
q is composed of four atomic sessions which are specified as follows and is modeled as a UML class diagram in Figure 5:(18)
S
_
p
o
R
e
q
=
S
_
p
o
R
e
q
_
r
e
q
B
u
y
e
r
.
p
o
⟶
S
e
l
l
e
r
.
p
o
,
C
h
@
S
e
l
l
e
r
·
S
_
p
o
R
e
q
_
r
e
s
p
B
u
y
e
r
.
p
o
A
c
k
⟵
S
e
l
l
e
r
.
p
o
A
c
k
,
C
h
@
B
u
y
e
r
·
S
_
p
o
R
e
q
_
a
s
s
i
g
n
_
B
u
y
e
r
B
u
y
e
r
.
p
o
S
t
a
t
e
=
"
s
e
n
t
"
·
S
_
p
o
R
e
q
_
a
s
s
i
g
n
_
S
e
l
l
e
r
S
e
l
l
e
r
.
p
o
S
t
a
t
e
=
"
r
e
c
e
i
v
e
d
"Figure 5
Structure ofS_poReq.The other four sessions function as follows:S
_
c
r
e
d
C
h
e checks the buyer’s credit by sending a request to the bank that sends back the state of the credit (good or bad); S
_
i
n
v
C
h
e checks the seller’s inventory by sending a request to the seller who sends back the state of the inventory (sufficient or short); S
_
p
o
R
e
s
p declares that the order has been accepted if the buyer’s credit is good and the inventory is sufficient; and S
_
p
o
R
e
j declares that the order has been rejected if the buyer’s credit is bad or the inventory is short. The four sessions are specified as follows, while the related class models are omitted due to space limitation: (19)
S
_
c
r
e
d
C
h
e
=
S
_
c
r
e
d
C
h
e
_
r
e
q
-
r
e
s
p
(
S
e
l
l
e
r
.
c
c
R
e
q
⟶
B
a
n
k
.
c
c
R
e
q
,
S
e
l
l
e
r
.
c
c
R
e
s
p
⟵
B
a
n
k
.
c
c
R
e
s
p
,
C
h
@
S
e
l
l
e
r
)
·
S
_
c
r
e
d
C
h
e
_
a
s
s
i
g
n
_
S
e
l
l
e
r
.
c
c
R
e
s
p
S
e
l
l
e
r
.
c
c
R
e
s
p
=
"
g
o
o
d
"
/
"
b
a
d
"
·
S
_
c
r
e
d
C
h
e
_
a
s
s
i
g
n
_
B
a
n
k
.
c
c
S
t
a
t
e
B
a
n
k
.
c
c
S
t
a
t
e
=
"
s
e
n
t
"
·
S
_
c
r
e
d
C
h
e
_
a
s
s
i
g
n
_
S
e
l
l
e
r
.
c
c
S
t
a
t
e
S
e
l
l
e
r
.
c
c
S
t
a
t
e
=
"
r
e
c
e
i
v
e
d
"
S
_
i
n
v
C
h
e
=
S
_
i
n
v
C
h
e
_
r
e
q
-
r
e
s
p
(
S
e
l
l
e
r
.
i
c
R
e
q
⟶
S
u
p
p
l
i
e
r
.
i
c
R
e
q
,
S
e
l
l
e
r
.
i
c
R
e
s
p
⟵
S
u
p
p
l
i
e
r
.
i
c
R
e
s
p
,
C
h
@
S
e
l
l
e
r
)
·
S
_
i
n
v
C
h
e
_
a
s
s
i
g
n
_
S
e
l
l
e
r
.
i
c
R
e
s
p
S
e
l
l
e
r
.
i
c
R
e
s
p
=
"
s
u
f
f
i
c
i
e
n
t
"
/
"
s
h
o
r
t
"
·
S
_
i
n
v
C
h
e
_
a
s
s
i
g
n
_
S
u
p
p
l
i
e
r
.
i
c
S
t
a
t
e
S
u
p
p
l
i
e
r
.
i
c
S
t
a
t
e
=
"
s
e
n
t
"
·
S
_
i
n
v
C
h
e
_
a
s
s
i
g
n
_
S
e
l
l
e
r
.
i
c
S
t
a
t
e
S
e
l
l
e
r
.
i
c
S
t
a
t
e
=
"
r
e
c
e
i
v
e
d
"
S
_
p
o
R
e
s
p
=
S
_
p
o
R
e
s
p
_
r
e
s
p
B
u
y
e
r
.
p
o
R
e
s
p
⟵
S
e
l
l
e
r
.
p
o
R
e
s
p
,
C
h
@
B
u
y
e
r
·
S
_
p
o
R
e
s
p
_
a
s
s
i
g
n
_
B
u
y
e
r
.
p
o
S
t
a
t
e
B
u
y
e
r
.
p
o
S
t
a
t
e
=
"
c
o
m
p
l
e
t
e
d
"
·
S
_
p
o
R
e
s
p
_
a
s
s
i
g
n
_
S
e
l
l
e
r
.
p
o
S
t
a
t
e
S
e
l
l
e
r
.
p
o
S
t
a
t
e
=
"
c
o
m
p
l
e
t
e
d
"
S
_
p
o
R
e
j
=
S
_
p
o
R
e
j
_
r
e
s
p
B
u
y
e
r
.
p
o
R
e
s
p
⟵
S
e
l
l
e
r
.
p
o
R
e
s
p
,
C
h
@
B
u
y
e
r
·
S
_
p
o
R
e
j
_
a
s
s
i
g
n
_
B
u
y
e
r
.
p
o
S
t
a
t
e
B
u
y
e
r
.
p
o
S
t
a
t
e
=
"
u
n
c
o
m
p
l
e
t
e
d
"
·
S
_
p
o
R
e
j
_
a
s
s
i
g
n
_
S
e
l
l
e
r
.
p
o
S
t
a
t
e
S
e
l
l
e
r
.
p
o
S
t
a
t
e
=
"
u
n
c
o
m
p
l
e
t
e
d
"The interaction sequence companied with the participants and key messages can be modeled as a UML communication diagram, as shown in Figure6.Figure 6
Interaction between roles in the choreography.Having analyzed the interaction and the functions of the sessions, we can organize the choreography of the purchase order application as follows:(20)
C
h
o
_
p
o
=
S
_
p
o
R
e
q
·
S
_
c
r
e
d
C
h
e
∥
S
_
i
n
v
C
h
e
·
S
_
p
o
R
e
s
p
+
S
_
p
o
R
e
j and specify the preconditions of the sessions as follows: (21)
P
_
c
r
e
d
C
h
e
=
p
_
i
n
v
C
h
e
P
_
c
r
e
d
C
h
e
=
B
u
y
e
r
.
p
o
S
t
a
t
e
=
"
s
e
n
t
"
∧
S
e
l
l
e
r
.
p
o
S
t
a
t
e
=
"
r
e
c
e
i
v
e
d
"
;
P
_
p
o
R
e
s
p
=
(
S
e
l
l
e
r
.
c
c
R
e
s
p
=
"
g
o
o
d
"
∧
S
e
l
l
e
r
.
i
c
R
e
s
p
=
"
s
u
f
f
i
c
i
e
n
t
"
∧
S
e
l
l
e
r
.
c
c
S
t
a
t
e
=
S
e
l
l
e
r
.
i
c
S
t
a
t
e
=
"
r
e
c
e
i
v
e
d
"
)
;
P
_
p
o
R
e
j
=
(
S
e
l
l
e
r
.
c
c
R
e
s
p
=
"
b
a
d
"
∨
S
e
l
l
e
r
.
i
c
R
e
s
p
=
"
s
h
o
r
t
"
∧
S
e
l
l
e
r
.
c
c
S
t
a
t
e
=
S
e
l
l
e
r
.
i
c
S
t
a
t
e
=
"
r
e
c
e
i
v
e
d
"
)
.Furthermore, theSHOIN(D) ontology can be generated by the algorithm Construct Tbox&Abox, and as a result, the axiom set in Tbox and the instance set in Abox are listed as in Table 3.Table 3
Axiom set and instances set of purchase order service choreography model (fragment).
Axiom set in Tbox
Instances set in Abox
NoAction⊑ Abas SilentAction ⊑ Abas InterAction ⊑ Abas Assign ⊑ Abas Perform ⊑ Abas Abas ⊑ Act Astr ⊑ Act
S
a
t
o
m
⊑
Session
S
c
o
m
⊑
Session Session ⊑
∀ SessionDeduction.Session Participant ⊑
∀ Implement.Role Choreography ⊑
∀ Contain.Session Interaction ⊑
∀ Depend.Channel Role ⊑
∀ Belong_to.Participant Interface ⊑
∀ Bind.Role Session ⊑
∀ Executing. S
a
t
o
m Session ⊑
∀ Sequence. Session Session ⊑
∀ Choice. Session ⋮
S_poReq: S
c
o
m
S_poReq_req: S
a
t
o
m
S_poReq_resp: S
a
t
o
m
S_poReq_assign_Buyer: S
a
t
o
m
S_poReq_assign_Seller: S
a
t
o
m
S_credChe: S
c
o
m
S_poResp: S
c
o
m ProductTrader: Participant ServiceProvider: Participant
S_credChe   S_invChe S_Che: S
parallel
S_poResp + S_poRej: S
choice Cho_po: Choreography Buyer: Role Supplier: Role
P_credChe: Precondition
〈Cho_po, S_poReq〉: Contain
〈
S_credChe, P_credChe〉: Guard
〈
S_poReq, S_poReq_req〉: Executing
〈
S_credChe, S_invChe〉: Parallel
〈
S_poReq, S_credChe   S_invChe S_Che〉: Sequence ⋮


## 4.2. Verification of Application Model

Having constructed the application model which is subsequently converted into theSHOIN(D) ontology, we can check the correctness properties of consistency, completeness, and state reachability of the specified choreography separately in the following cases.Case 1 (consistency checking).
Consistency checking is to check whether there is a conceptual conflict against modeling semantics; that is, giving a group of related concepts in the application model, the relationships defined between the concepts should semantically abide by the metarelation declared in the metamodel.Suppose that the modeler tries to add in the application model a relation ofExecuting between theRole Buyer and thesession S_poReq. But according to the constraints of themetamodel, such relation should only appear between two sessions and thus the consistency rule R
c
o
n
1 is broken. The error can be easily found through ontology consistency checking using Pellet.Case 2 (completeness checking).
The completeness checking is to check whether there is a lack of concept or relation in the application model; that is, giving a group of related concepts, the relationships defined between the concepts should quantitatively abide by the multiplicity constraint of the corresponding metarelation in the metamodel.Suppose that the modeler tries to build aBelong_to relation between theRole Supplier and theParticipantProductTrader, meaning that Supplier belongs to a product trader, but wrongly add at the same time anotherBelong_to relation between Supplier and ServiceProvider. Such relation violates the multiplicity constraint R
c
o
n
1 that means eachRole must belong to only oneParticipant at any time. The checking result is prompted by Pellet as follows: “Consistent: No Reason: The individual Supplier has more than one value for property Belong_to violating the cardinality restriction.”Case 3 (state reachability checking).
The state reachability checking is to examine whether the termination state of a session defined in the application model is reachable; that is, the session can be deduced using the deductive reasoning rules given in Section2.1.3. If all sessions are deducible, implying that all session states are reachable, the application behavior is verified.Session S_poReq is deduced with the deductive reasoning rules R
a
t
o
m and R
s
e
q
2 and as a result, poState of Buyer will be set to “sent” and the poState of Seller will be set to “received.” The reasoning process is shown as follows:(22)
S
_
p
o
R
e
q
=
S
_
p
o
R
e
q
_
r
e
q
B
u
y
e
r
.
p
o
⟶
S
e
l
l
e
r
.
p
o
,
C
h
@
S
e
l
l
e
r
S
_
p
o
R
e
q
=
·
S
_
p
o
R
e
q
_
r
e
s
p
B
u
y
e
r
.
p
o
A
c
k
⟵
S
e
l
l
e
r
.
p
o
A
c
k
,
C
h
@
B
u
y
e
r
S
_
p
o
R
e
q
=
·
S
_
p
o
R
e
q
_
a
s
s
i
g
n
_
B
u
y
e
r
B
u
y
e
r
.
p
o
S
t
a
t
e
=
"
s
e
n
t
"
S
_
p
o
R
e
q
=
·
S
_
p
o
R
e
q
_
a
s
s
i
g
n
_
S
e
l
l
e
r
S
e
l
l
e
r
.
p
o
S
t
a
t
e
=
"
r
e
c
e
i
v
e
d
"
→
t
r
u
e
,
a
=
S
_
p
o
R
e
q
_
r
e
q
B
u
y
e
r
.
p
o
→
S
e
l
l
e
r
.
p
o
,
C
h
@
S
e
l
l
e
r
S
_
p
o
i
R
e
q
=
N
U
L
L
S
_
p
o
R
e
q
=
·
S
_
p
o
R
e
q
_
r
e
s
p
B
u
y
e
r
.
p
o
A
c
k
⟵
S
e
l
l
e
r
.
p
o
A
c
k
,
C
h
@
B
u
y
e
r
S
_
p
o
R
e
q
=
·
S
_
p
o
R
e
q
_
a
s
s
i
g
n
_
B
u
y
e
r
B
u
y
e
r
.
p
o
S
t
a
t
e
=
"
s
e
n
t
"
S
_
p
o
R
e
q
=
·
S
_
p
o
R
e
q
_
a
s
s
i
g
n
_
S
e
l
l
e
r
S
e
l
l
e
r
.
p
o
S
t
a
t
e
=
"
r
e
c
e
i
v
e
d
"
→
t
r
u
e
,
a
=
S
_
p
o
R
e
q
_
r
e
s
p
B
u
y
e
r
.
p
o
A
c
k
←
S
e
l
l
e
r
.
p
o
A
c
k
,
C
h
@
B
u
y
e
r
S
_
p
o
i
R
e
q
=
N
U
L
L
S
_
p
o
R
e
q
=
·
S
_
p
o
R
e
q
_
a
s
s
i
g
n
_
B
u
y
e
r
B
u
y
e
r
.
p
o
S
t
a
t
e
=
"
s
e
n
t
"
S
_
p
o
R
e
q
=
·
S
_
p
o
R
e
q
_
a
s
s
i
g
n
_
S
e
l
l
e
r
S
e
l
l
e
r
.
p
o
S
t
a
t
e
=
"
r
e
c
e
i
v
e
d
"
→
t
r
u
e
,
a
=
S
_
p
o
R
e
q
_
a
s
s
i
g
n
_
B
u
y
e
r
B
u
y
e
r
.
p
o
S
t
a
t
e
=
"
s
e
n
t
"
S
_
p
o
i
R
e
q
=
N
U
L
L
S
_
p
o
R
e
q
=
·
S
_
p
o
R
e
q
_
a
s
s
i
g
n
_
S
e
l
l
e
r
S
e
l
l
e
r
.
p
o
S
t
a
t
e
=
"
r
e
c
e
i
v
e
d
"
→
t
r
u
e
,
S
_
p
o
R
e
q
_
a
s
s
i
g
n
_
S
e
l
l
e
r
S
e
l
l
e
r
.
p
o
S
t
a
t
e
=
"
r
e
c
e
i
v
e
d
"
S
_
p
o
i
R
e
q
=
N
U
L
LThe other four sessions credit check (S
_
c
r
e
d
C
h
e), inventory check (S
_
i
n
v
C
h
e), purchase order response (S
_
p
o
R
e
s
p), and purchase order reject (S
_
p
o
R
e
j) can be deduced in the same way.The whole reasoning process for the application choreography modelC
h
o
_
p
o is shown as follows, where the deduction rules applied to each step are bracketed with :(23)
C
h
o
_
p
o
=
S
_
p
o
R
e
q
·
S
_
c
r
e
d
C
h
e
∥
S
_
i
n
v
C
h
e
·
S
_
p
o
R
e
s
p
+
S
_
p
o
R
e
j
→
R
a
t
o
m
,
R
s
e
q
2
t
r
u
e
,
a
∗
N
U
L
L
·
S
_
c
r
e
d
C
h
e
∥
S
_
i
n
v
C
h
e
·
S
_
p
o
R
e
s
p
+
S
_
p
o
R
e
j
→
C
6
S
_
c
r
e
d
C
h
e
∥
S
_
i
n
v
C
h
e
·
S
_
p
o
R
e
s
p
+
S
_
p
o
R
e
j
→
R
a
t
o
m
,
R
p
a
r
a
l
l
e
l
P
_
c
r
e
d
C
h
e
,
a
∗
∗
N
U
L
L
∥
S
_
i
n
v
C
h
e
·
S
_
p
o
R
e
s
p
+
S
_
p
o
R
e
j
→
C
5
S
_
i
n
v
C
h
e
·
S
_
p
o
R
e
s
p
+
S
_
p
o
R
e
j
→
R
a
t
o
m
,
R
s
e
q
2
p
_
i
n
v
C
h
e
,
a
∗
∗
∗
N
U
L
L
·
S
_
p
o
R
e
s
p
+
S
_
p
o
R
e
j
→
C
6
S
_
p
o
R
e
s
p
+
S
_
p
o
R
e
j
→
P
_
p
o
R
e
s
p
,
a
∗
∗
∗
∗
N
U
L
LThe atomic sessions in each step are as follows:(24)
a
∗
=
S
_
p
o
R
e
q
_
r
e
q
·
S
_
p
o
R
e
q
_
r
e
s
p
·
S
_
p
o
R
e
q
_
a
s
s
i
g
n
_
B
u
y
e
r
·
S
_
p
o
R
e
q
_
a
s
s
i
g
n
_
S
e
l
l
e
r
a
∗
∗
=
S
_
c
r
e
d
C
h
e
_
r
e
q
-
r
e
s
p
·
S
_
c
r
e
d
C
h
e
_
a
s
s
i
g
n
_
S
e
l
l
e
r
.
c
c
R
e
s
p
·
S
_
c
r
e
d
C
h
e
_
a
s
s
i
g
n
_
B
a
n
k
.
c
c
S
t
a
t
e
·
S
_
c
r
e
d
C
h
e
_
a
s
s
i
g
n
_
S
e
l
l
e
r
.
c
c
S
t
a
t
e
a
∗
∗
∗
=
S
_
i
n
v
C
h
e
_
r
e
q
-
r
e
s
p
·
S
_
i
n
v
C
h
e
_
a
s
s
i
g
n
_
S
e
l
l
e
r
.
i
c
R
e
s
p
·
S
_
i
n
v
C
h
e
_
a
s
s
i
g
n
_
S
u
p
p
l
i
e
r
.
i
c
S
t
a
t
e
·
S
_
i
n
v
C
h
e
_
a
s
s
i
g
n
_
S
e
l
l
e
r
.
i
c
S
t
a
t
e
a
∗
∗
∗
∗
=
S
_
p
o
R
e
s
p
_
r
e
s
p
·
S
_
p
o
R
e
s
p
_
a
s
s
i
g
n
_
B
u
y
e
r
.
p
o
S
t
a
t
e
·
S
_
p
o
R
e
s
p
_
a
s
s
i
g
n
_
S
e
l
l
e
r
.
p
o
S
t
a
t
eThe application behavior is proven correct provided that the reasoning process may eventually end byNULL. Otherwise, there must be a session failed to be deduced (i.e., its termination state is not reachable). If the application may reach the final state, the key attribute poState of both Buyer and Seller will be set to either “completed” or “uncompleted” (this may happen when B
y
u
e
r
.
c
c
R
e
s
p
=
"
b
a
d
" or S
e
l
l
e
r
.
i
c
R
e
s
p
=
"
s
h
o
r
t
").To give a negative example, we deliberately assign Seller.poState = “” to make false the preconditionP_credChe. As a result, the reasoning process rests on the second step, as the session S_credChe cannot be deduced, and therefore all states of the sessions followed cannot be reached. The exception can be found by entering the following DL-based query command in the form of SPARQL [24]:SELECT ? a WHERE? a rdf:type xmlns: Session.? a xmlns: SessionDeduction ? N
U
L
L
..Figure7 shows the query result in the human interface panel of the reasoner Pellet, indicating that the session S_poReq and its four atomic sessions are deduced (or can be successfully executed), while all of the subsequent sessions are not shown (or the corresponding states of these sessions may not be reached). The rules 〈
R
a
t
o
m
,
R
s
e
q
2
〉 are applied to the reasoning process to find the exception where theSessionDeduction relation is broken between the sessions S_poReq and S_credChe and all of the followed sessions cannot be deduced.Figure 7
The query command window for checking the state reachability.Beside the above experiment, we have also modeled and verified several other cases, including the online shopping example given in [39], the buyer-seller example given in [40], and the example from the supply chain management [41].The verification is processed efficiently. The reasoning for each case is finished within a second, tested on a laptop computer with a 2 GHz Intel processor and 1 GB of RAM. That accords with the comments by Haarslev and Möller [42] who pointed out that even for the hardest problems the query time for DL reasoning would be within three seconds. But, is it always true?In order to evaluate the efficiency of reasoning for CML-DL models, we choose the four popular ontologies, VICODI, LUBM, Semintec, and Wine which are used in previous benchmarks, carry out experiment, and lead a statistical analysis by comparing the average response times against the increasing size of Abox. The detailed descriptions about these ontologies can be found in [43].The ontologies represent four standard benchmark datasets with different complexity. The VICODI ontology is relatively small and simple since it does not contain any disjunctions, existential quantification, or number restrictions. The LUBM ontology and the Semintec ontology are also relatively simple like the VICODI ontology, while the Semintec ontology is more complex since it contains functional properties and disjointness constraints and is constructed using OWL DL. The Wine ontology is the most complex one. It contains a classification of wines and is established using advanced DL constructors.The above ontologies are too small in Abox for our intended performance evaluations. Therefore, we generate different sizes of datasets, ranging from 100 to 1 million, to increase the Aboxes of the ontologies for test.To evaluate the query times for various sizes of the datasets, we use several query patterns covering all cases from the simplest one that retrieves all individuals of one concept to the most complex one that retrieves all individuals of the concept. The test method can be referenced by [44].Figure8 shows the average time for query response for the four ontologies with the generated datasets sizing from 100 to 1 Mio. All the results reported are averaged over 100 queries. The test is led on a laptop computer with one 2 GHz Intel processor and 1 GB of RAM, running Windows XP Service Pack 4.Figure 8
Average query time for the four ontologies (VICODI, LUBM, Semintec, and Wine).As expected, there is a significant increase of query time as the size of the ontology increases from the 100 to 1 million. For the example of the Semintec ontology, the average query time for smaller size from 100 to 10,000 is less than a second (<1). But, the time increases sharply as the size exceeds 10,000, and for the maximum size of 1 Mio., the time is about 800 seconds or about 17 minutes.Our ontology of CML-DL may match the Semintec ontology since the domain of the CML-DL application is not more complex than that of the financial services, and the model can be constructed using a fragment of OWL DL without advanced DL constructors. Therefore, we expect that the number of individuals of the CML-DL application model, for most projects, would be less than 100000, and thus the reasoning time would be within a few minutes at worst.


## 5. Related Work Discussion

System verification accounts for a larger proportion in the domain of system engineering. There are two categories: testing and formal verification. Testing is the process in which testers input the use case through access point and then observe the corresponding output to discover potential error. Formal verification, which can be further divided into model checking based on exhausting searching and model verification based on logic reasoning, expresses system specification by using mathematical methods and then proves whether the designed system meets the desired properties according to mathematical theory.The initial progress of testing static system properties converts static properties into hard-code and calls these codes during program compilation. Because system specification and system implementation are bounded together, the method does not have flexibility and reusability; that is, when the system static properties to be checked change, the hard-code must be updated as well [45].The emergence of the open-source projects WS-CDL Eclipse Plugin [46] and Pi4SOA [47] makes it possible to separate system specification and implementation. The engines of these projects provide an execution and simulation environment for WS-CDL documents. When the properties to be checked change, the corresponding descriptions can be revised without any modification to the inspection program. Reference [48] notes that although the WS-CDL is just a description language, it is essentially an XML document; therefore, Eclipse Plugin simulators regard the WS-CDL as executable script language for interpretation and implementation. Nevertheless, the verification methods based on the simulation engine need to traverse the entire value space when handling existential and universal quantifiers, leading to a higher complexity of time and space.Workflow based web service composition and formal verification techniques are broadly applied. They can be divided into three categories: PN- (Petri Net-) based, FSA- (Finite State Automate-) based, and PA- (process algebra-) based techniques.Xia et al. [49, 50] achieved the complete conversion from a WS-CDL document to stochastic Petri Nets; moreover, they make assessments of time expectations, probability, and cost expectations of services that normally end due to the index of performance, reliability, and execution cost, respectively. Foster et al. [51] proposed a type of service modeling and verification method called model-based service compositions engineering for the first time. The method maps the service composition model to a finite state process (FSP), aiming at verifying the compatibility between composite services and their environment by using a labeled transition system analyzer (LTSA). Molina-Jimenez and Shrivastava [52] developed the concept of conformance between a contract and a choreography by assuming that they can be modeled by Finite Automaton (FA). The choreography specifications and contracts, specified by the BPMN notation and the event-condition-action rules, describe permissible interactions between partners from different viewpoints. They established a process to automatically check whether all the behaviors permissible in a choreography are also permissible in the corresponding contract and vice versa. Díaz and Llana [53] mapped the service composition model in WS-CDL to a timed automation and then simulated the dynamic behavior of the system using the automatic verification tool UPPAAL. The literature [54] provided the basis for formalizing and reasoning on the mobility characteristics of web services choreography using the process algebra π-calculus which is, according to Robin Milner, a model of concurrent computation based on the notion of naming. They argued that the process algebras, such as π-calculus, can be used to formalize web services characteristics to ensure that they satisfy some conditions required in SOA. Salaün et al. [55] presented a method of encoding the collaboration diagrams into the LOTOS process algebra. This encoding allows checking realizability of the collaboration diagrams for both synchronous communication and bounded asynchronous communication.Gu et al. [8, 9] presented a formal modeling framework Abstract WS-CDL with grammar, congruence relations, and operational semantics. They defined a set of mappings of the Abstract WS-CDL global model to the Pi calculus-based local model and accordingly suggested a set of deductive reasoning rules of state reachability and terminability. Unfortunately, they failed to provide the consistency and completeness verification mechanism as well as the corresponding reasoning engine.Temporal logic (TL) can be used to assert the behavior change with time evolution. The model verification techniques based on TL model the finite states of systems with Promela and specify the system properties with TL expressions to enable verification by checking whether the intersection between the Promela models and the TL expressions is empty. Zhang and Liu [56] presented a formal verification method for CCML (Cooperative Composition Modeling Language) based web service composition. They build a mapping of CCML description to CCS expression and approach property verification and service compatibility verification with the help of a TL based checking mechanism and an automated tool.The above verification methods, either based on workflow or based on TL, may lead an exhaustive search for all states of system execution, which may cause the state explosion problem when the number of the states exponentially increases as the system scales up.The DL-based logic reasoning technique is applied to service modeling and verification. Liu et al. [57] proposed a service modeling and composition method based on DL rules using a uniform way of characterizing the static semantic and dynamic interaction characteristics of web services. The method unifies the service composition model within the framework of DL rules to remedy the defect that DL cannot describe the dynamic characteristics of web services. Chang et al. [58, 59] proposed an Extended Dynamic Description Logic EDDL(X) by extending the traditional Dynamic Description Logic (DDL) to transform the web service composition model into the EDDL(X)-based one. However, the above methods focus more on service discovery, service matching, and service composition while addressing less the property verification of service choreography model.Over the past decade, many organizations and individuals have conducted in-depth and fruitful research in the field of service choreography model verification. Their achievements can be categorized, according to their underlying methods, into hard-coding, simulation engine, workflow, temporal logic, and Abstract WS-CDL. As shown in Table4, we have made a primary comparison of our method with those techniques by the important features such as description ability, degree of automation, knowledge reusability, efficiency of verification, and state explosion.Table 4
Comparison between several typical verification methods of service choreography model.
Features
Methods
Hard-coding
Simulation engine
Workflow
Temporal logic
Abstract WS-CDL
CMV-DL
Description ability
+++
+++
+
+
+
++
Degree of automation
+
+
++
++
−
++
Knowledge reusability
−
−
−
−
−
+
Efficiency of verification
+
++
+++
+++
+
+++
State explosion
−
−
+
+
−
−
+: support/existence, −: nonsupport/nonexistent.Regarding description ability, the methods of hard-coding and the simulation engine rank highest since they allow compiling the XML scripts of WS-CDL models. CMV-DL ranks second high due to the strong ability of induction and high level of abstraction with DL [60]. The methods based on workflow and TL are weak in description ability, because they cannot ensure the completeness of mapping one form of model to another, especially when the model is complex in its structure. The current methods based on PA, for example, provide only a few of simple mapping rules and thus do not guarantee a strict conversion, which may cause loss of semantics during conversion [61].Automation is an important feature for model verification. Each of the methods listed has related supporting tools, except for Abstract WS-CDL. CMV-DL is graded comparatively high in automation, because it takes advantage of available reasoning engines such as Pellet which are based on the mature algorithm Tableau and which have been integrated into the requirement analysis tool OBREAT.Regarding knowledge reusability, the workflow based, the TL based, and the other three techniques do not provide the mechanism for knowledge accumulation and reuse, while OBREAT allows enriching domain knowledge by adding new reasoning rules to theDomain Knowledge base and importing the reasoning results back into the knowledge base for further reasoning. But the process relies on human interference and thus the capability is graded low.The verification efficiency is determined by both human interference and time consumption in validation process. The hard-code method and CMV-DL depend heavily on human interference and therefore are graded lowest. The simulation engine technique needs to traverse the entire value space when handling existential and universal quantifiers, which leads to a higher complexity and therefore a low efficiency. The other three methods, supported by automated tools, work highly efficiently for verification.When a system has many concurrent components, the state space of system execution might expand infinitely beyond ordinary computation capability. Based on exhaustive search, workflow and TL may suffer from the problem of state explosion which has long been the bottleneck for their development [62]. In contrast, CMV-DL works on deduction reasoning where the space of deduction reasoning is limited by the size of the generated ontology and the computation complexity is decreased by the high efficient reasoner algorithm Tableau [63, 64].In general, CMV-DL has an obvious advantage in knowledge reusability and is free of state explosion without the loss of description ability, and it has a modest degree of automation and efficiency compared to the other methods.


## 6. Conclusion and Future Work

This paper focuses on service choreography modeling and verification. It proposes a new approach of choreography model verification based on Description Logic to verify the service choreography model based onSHOIN(D) of DL. The main contributions are as follows:(1)
A metaconcept model of service choreography based on WS-CDL is proposed, providing a framework to formally define a service choreography model.
(2)
Domain rules of consistency, completeness, and deductive reasoning are defined, enabling formal verification of the service choreography model.
(3)
The model transformation algorithms are provided and thus the service choreography model and domain rules can be converted into the DL ontology and model verification can be thereby made automatically with an available reasoner, such as Pellet.
(4)
The related work on service choreography verification is investigated. The representative methods are analytically compared with CMV-DL on such features as description ability, degree of automation, knowledge reusability, efficiency of verification, and state explosion.Currently, CMV-DL focuses only on a few key issues of web service choreography. The goal of the metaconcept model and CMV-DL is to verify several key properties of service choreography models. Therefore, CMV-DL captures only a core set of WS-CDL features while omitting some advanced features, such as exception and finalizing blocks. Future work involves extending the service choreography metaconcept model to cover more properties of WS-CDL, such as the consistency between choreography models and orchestration models. Moreover, the domain rules need to be enriched and improved as the approach is applied to more projects.



---

*Source: 8947157-2016-01-19.xml*