A bitwise-based indexing and heuristic-driven on-the-fly approach for Web service composition and verification
Vietnam J Comput Sci (2017) 4:111–126
DOI 10.1007/s40595-016-0079-8
REGULAR PAPER
A bitwise-based indexing and heuristic-driven on-the-fly approach
for Web service composition and verification
Khai T. Huynh1 · Tho T. Quan1 · Thang H. Bui1
Received: 6 February 2016 / Accepted: 27 August 2016 / Published online: 9 September 2016
© The Author(s) 2016. This article is published with open access at Springerlink.com
Abstract During the last decade, software engineering
community has witnessed the emerging of SOA architec-
ture, where Web services play a crucial role. It prompts the
concept of Web Service Composition (WSC). Even though
interesting, this issue posed some remarkable challenges, one
of which is constraint handling. To be more precise, one
needs to ensure that the composite Web service fulfills, at
the same time, many constraints, including functional con-
straints, Quality of Service (QoS), and the execution order of
the component services, or temporal relations. Those con-
straints are of different natures, thus finding an efficient
verification on all kinds of constraints during the compo-
sition process is by no means a trivial task. Backed by a
solid foundation of temporal logic, model checking (MC) is
a suitable approach to handle this issue. However, MC-based
approach suffers from the infamous problem of state-space
explosion, making it limited when applied to real-life sit-
uations. The work in this paper addresses the problem by
proposing various approaches for handling the state-space
exploration, including (i) an introduction of an LTS-based
model known as LTS4WS, which can avoid generating full
schema of Web service composition and allow on-the-fly ver-
ification on the state space; (ii) heuristics strategies to find the
best potential composition, and (iii) a bitwise-based index-
ing mechanism for fast location of suitable Web services.
All of those approaches are unified in a single tool, known as
WSCOVER. As a result, a significant improvement of per-
formance has been made, especially as compared with the
other existing works in the same field.
Keywords Web service composition · On-the-fly Web
service composition and verification · Web service
composition tool · Bitwise-based Web service indexing ·
Heuristic-driven Web service composition
1 Introduction
1.1 Web service composition and verification
Nowadays, Web Service Composition (WSC) has been
raised as an important issue of Service-Oriented Architec-
structured composite Web services from component Web ser-
in recent years, when the number of provided component
Web services increases and the composition requirements
from users become more complex. When composing Web
services, in addition to the requirements on functional prop-
erties, also known as hard constraints, the requirements on
Quality of Service (QoS) properties, also known as soft con-
straints, are also a very important factor determining the
outcome of the composition. There are many QoS proper-
ties of Web services, such as response time, execution cost,
availability, or reputation, etc. In some circumstances, many
services that satisfy hard constraints cannot be used in a com-
position, because of the dissatisfactions of soft constraints.
Let us consider the following example. Suppose that
a user is organizing his trip using the Web services pre-
(Sightseeing) and the traveling dates (Dates), the user
Khai T. Huynh
B
Tho T. Quan
Thang H. Bui
1
Faculty of Computer Science and Engineering, Ho Chi Minh
City University of Technology, Ho Chi Minh City, Vietnam
123
112
Vietnam J Comput Sci (2017) 4:111–126
Table 1 Travel Booking Web
service repository
#
Service name
Input(s)
Output(s)
respTime
1
2
3
4
5
6
7
8
9
10
HotelReserveService (HR)
CityHotelService (CH)
Dates, Hotel
City
HotelReservation
Hotel
5
3
HotelCityService (HC)
Hotel
City
3
HotelPriceInfoService (HP)
SightseeingCityService (SC)
SightseeingCityHotelService (SCH)
CitySightseeingService (CS)
ActivityBeachService (ABS)
AreaWeatherService (AWS)
CityWeatherService (CWS)
Hotel
Price
10
2
Sightseeing
Sightseeing
City
City
City, Hotel
Sightseeing
Beach
16
4
Activity
Area
5
Weather
Weather
5
City
5
s5
s6
Table 2 Requirements for travel booking Web service
Constraint
Value
s1
s7
Hard constraint:
Input:
Dates, Sightseeing
s0
s11
s3
Output:
Price, Hotel Reservation
s8
s9
s2
Soft constraint:
respTime ≤ 30
Temporal relation:
ꢀ(¬Hotel Reservation U Price)
s4
s10
Fig. 1 Full composition schema for travel booking problem
wants to find hotel booking price (Price) and the hotel reser-
vation information (Hotel Reservation) of the hotels near
is no individual Web service that can completely fulfill the
requirement from the user. Thus, one needs to find a composi-
tionoftheavailableWebservices. Besidetherequirementson
the above functional constraints (hard constraints), the user
can also specify soft constraints, such as “The total response
time of the composite Web service should not exceed 30 s”.
In addition, the user may also want a certain order of service
execution, or temporal relation. For instance, we may also
need to obtain the information about Price before proceed-
ing on Hotel Reservation. All of requirements discussed
Typically, a WSC problem is a Satisfiability (SAT) prob-
lem, such that the composition of Web services is considered
as a process that creates new logic formula which can satisfy
the target formula, known as goal. Verifying the satisfaction
of composition with the constraints becomes a theoretical
verification problem. Since the hard constraint is typically
represented by a traditional form of logic, often as First-
hard constraint or not can adopt a traditional approach, such
However, theformalverificationofsoftconstraintbecomes
more difficult, because the soft constraint conditions may
be mathematical expressions representing QoS properties.
These functions can be of the non-linear form, which causes
serious difficulties for the current provers.
Due to such characteristics, research on the verification
of composite Web services often focuses on hard constraint.
Recently, an approach that can verify combination of both
first of all, all compositions which satisfy the hard con-
straint are created, forming a full composition schema. For
travel booking problem. Subsequently, model checking can
be used to verify whether the compositions satisfy the soft
constraint or not. As a result, only compositions satisfy-
ing soft constraints, for instance, denoted by solid line in
{s0 → s2 → s4 → s10 → s11} should be kept. To our
knowledge, this is the sole work claimed to verify hard and
softconstraintsatthesametime. Unfortunately, thisapproach
must be extremely expensive for the creation of full schema,
which is a classic N P-hard problem. Intuitively, one of the
ways that can handle this is to build the schema in an on-the-
fly manner to find a satisfied composition without building
a full schema in advance. However, unfortunately, in this
approach, the full composition schema is used as the model
to be verified, and hence, it has to be constructed beforehand.
1.2 Web service indexing
When the number of Web services in repository increases,
the cost of composition problem also increases significantly.
123
Vietnam J Comput Sci (2017) 4:111–126
113
There have been many given suggestions to resolve this
clustering approach, we have to address a variety of prob-
lems, suchashowtocomputethesimilaritybetweenservices,
how many clusters should be generated, or which clustering
algorithm should be chosen, etc.
To extend this work, we propose a bitwise-based indexing
technique to organize the Web services in the repository to
supporttheWebserviceretrievalprocessmoreaccuratelyand
efficiently. For the motivating example above, our approach
just needs to traverse 18 states in the case of using on-the-fly
tactic, and is further reduced to 10 states when heuristics are
applied (as compared with 108 states needed to be visited to
Alternatively, indexingisconsideredasasimpleandeffec-
tive approach to reduce the composition time. In literature,
there are many ways to index, such as using the hashtable
approaches, the construction of index structure and the appli-
cation of the processing functions are in high complexity. In
general, Web service indexing is a preprocessing step of the
Web service composition process. Once an index structure
is available, the composition process can quickly retrieve
the needed Web services. However, the indexing process
is definitely computationally expensive, and it also requires
additional space to store the index table. Therefore, we need
an effective and low-cost method to build the index table,
which should be updated easily when the stored data are
modified.
The contributions of our extension can be summarized as
follows.
• We proposed an approach which combines indexing and
model checking for composition and verification of Web
indexing technique to enjoy a significant improvement of
performance.
• We presented a bitwise-based approach to present Web
services and indexing technique. This representation
allows us to use the bitwise operators in processing and
further enjoy more improvement on performance.
• The experiments are performed on multiple real data sets
and the results show the effectiveness of this approach
Contributions In this paper, we introduce an extension of our
Web service composition approach. It bases on the model
checking approach, but does not require prior full schema
of compositions. Instead, the composition will be generated
according to the path condition on the state space when
the model is verified. Thus, if we use an on-the-fly model
will be processed in an on-the-fly manner, as well. As a result,
we can find a solution that simultaneously satisfies the hard
without the need of creating a full composition schema. In
addition, this approach makes room for some performance
improvement when the outcome of a composition step can be
usedtooptimizethecandidateselectionforthenextstep. This
optimization process can be implemented by some heuristic
rules.
Regarding the novelty of the work presented in this paper,
we want to note that using model checking to solve the Web
service composition or Web service verification has already
However, this paper is the first work proposing the combina-
tion of these two techniques.
Outline The rest of the paper is organized as follows.
the Web service composition performance. We propose a
experimentations from a repository of real Web services. In
• We propose an approach to represent the Web services by
theLabelledTransitionSystem (LTS), knownasLTS4WS,
to serve for the application of model checking for Web
service composition.
• We use the LTS4WS model to verify the hard and soft
constraints on WSC. This model checking approach
allows us to verify temporal relation on the constraints as
well.
2 LTS4WS—the model for Web service
composition
In this paper, we formalize the composition task as a
state-based searching problem. Each state corresponds to a
composition of multiple Web services, from which new state
can be generated by extending the current composition with
another Web service, bringing a new composition. That is,
we regard the set of all possible Web services as a model,
whose states are feasible combinations of them. Meanwhile,
• We apply some heuristic based on the characteristics of
Web service when performing model checking, so veri-
fication performance is improved visibly.
1
Currently, we only support Linear Temporal Logic (LTL).
123
114
Vietnam J Comput Sci (2017) 4:111–126
[Hotel ∧ Dates]
[HotelReservation]
HR
user requirements are regarded as properties, which can be
verified over the model using the model checking techniques,
in an on-the-fly manner. To carry out this study, our model is
developed based on the following definitions.
start
end
Fig. 2 Visual representation of an LTS
Definition 1 (Web Service) A web service W is a six-tuple
W = (N, I, O, P, E, Q), where
the reservation information of this hotel (HotelReservation),
ꢀ
i.e., Hotel Reservation = true. It needs five units of time
• N is a string representing the unique name of W.
(respTime: 5) in execution.
• I = {t1i , t2i , . . . , tni } is a set of input functional properties.
ꢀ
We denote tij as an input logical term representing the
Definition 2 (Labelled Transition System) A Labelled Tran-
sition System (LTS) is a five-tuple L = (V, S, s0, L, δ),
where
ꢀ
current informative status of the property tij . tij = true
means that the information of tij is currently available and
vice versa.
• O = {t1o, t2o, . . . , tmo } is a set of output functional proper-
• V is a set of variables,
o
ꢀ
• S is a set of states,
ties. We denote tk as an output logical term representing
the current informative status of the property tko. Like-
• s0 ∈ S is the initial state,
wise, tk = true means that the information of tko is
o
ꢀ
• L is a set of action labels,
• δ : S×L → S is a transition relation, where (s, a, s ) ∈ δ
is denoted as (s × a → s ). A transition may also have
a pre-condition (or the guard), a logical expression built
over V , which must always hold before the transition is
fired. In addition, a transition may also have an effect, a
set of expressions built over V , which expresses the effect
after firing the transition. A LTS that supports those kinds
of transitions is called guarded LTS, whose transition is
represented as:
currently available and vice versa.
• P is a logic expression representing the pre-condition
of W that must hold before W is invoked. It is simply
a conjunctive normal form of all input logical terms, as
ꢁ
n
ꢀ
ꢀ
ꢀ
P = t1 ∧ t2 ∧ . . . ∧ tni = j tij .
i
i
ꢀ
• E is a set of assignment expressions describing the effect
ꢀ
o
ꢀ
after W is invoked. E has the form of {∀k = 1..m : tk =
ꢀ
o
ꢀ
true}, where = is the assignment operator. Because tk
is a logical term, we can simply represent it as {∀k =
o
o
o
ꢀ
ꢀ
ꢀ
1 . . . m : tk } or {t1 ; . . . ; tm; }.
[guard]transition[effect]
• Q is a set of QoS properties, each of which is a pair of
ꢀname : valueꢁ, where name is the name of the prop-
erty and value is a numerical amount which evaluates the
value returned by W w.r.t this property.
Example 2 Given a simple LTS containing two states
ꢀ ꢀ
and a set of variables V consist of Hotel, Dates, and
ꢀ
Hotel Reservation. This LTS describes that in the initial
which provides the hotel reservation information (Hotel-
Reservation) of a specific hotel (Hotel) and the reservation
dates (Dates). The response time (respTime) of this service
is of 5 s. This Web service is described by Definition 1 as
follows.
state, if we fire the transition (or invoke the service) HR
(HotelReserveService), the system will switch to state end.
System = (V, S, s0, L, δ), where
ꢀ ꢀ
ꢀ
• V = {Hotel, Dates, Hotel Reservation},
W = (N = H R,
• S = {start, end},
I = {Hotel, Dates},
O = {Hotel Reservation},
• s0 = start,
• L = {H R},
ꢀ
ꢀ
ꢀ
ꢀ
ꢀ
P = Hotel ∧ Dates,
• δ = {[Hotel ∧ Dates]start × H R → end
ꢀ
[Hotel Reservation]}
E = {Hotel Reservation},
Q = {respTime : 5})
(HotelReservation) as a transition in an LTS system, where
the pre-condition and effect of the Web service are also used
as the guard and effect of the transition. In general, all of Web
services can be represented as this transition with appropriate
guards and effects.
ꢀ
ꢀ
The logic expression Hotel ∧ Dates is the pre-condition
that must hold before the Web service is invoked. It means
that to invoke the service HR (HotelReserveService), we must
have the information of Hotel and Dates to reserve this hotel.
The effect of this Web service invocation is that we have
123
Vietnam J Comput Sci (2017) 4:111–126
115
HR
HR
Definition 3 (LTS for Web Services)Let W S = {W1,
AWS
[P
AW S
] [E
]
HR
W2, . . . , Wn} be a set of Web services, where Wi
=
[E
AW S
]
CH
[P
]
[P
]
CH
W S
Web Services (LTS4WS) of W S is a guarded LTS L
(V, {s0}, s0, L, δ), where
=
[E
]
[E
]
CW S
CH
CWS
ABS
[P
]
HC
HC
[P
]
CW S
ꢂ
ꢂ ꢂ
[E
]
]
s0
HC
n
i
n
i
• V = (
Ii )
(
Oi ).
[E
]
[P
]
ABS
HP
• {s0} is a set of states, which has only one state s0,
• s0 is the initial state,
[P
]
ABS
[E
HP HP
[E
]
[E
]
SC
SC
• L = {N1, N2, . . . , Nn},
[P
]
SC
[P
]
SC
• δ is a transition relation of the form [Pi ]s0×Ni → s0[Ei ].
[P
SCH
]
SCH
CS
SC
[E
]
SCH
Fig. 3 Example of the LTS4WS model
Example 3 The LTS4WS model of the ten Web services in
ꢀ
ꢀ
ꢀ
• The set of variables:
V
=
{Dates, Hotel,
ꢀ
ꢁ
ꢀ
Hotel Reservation, City, Price, Sightseeing,
ꢀ
ꢀ
shows a situation, where the goal is found without searching
the whole space. Note that we can always prune the paths
that violate soft constraints, but virtually, we cannot justify
whether a path that will eventually satisfy a hard constraint or
not. However, we can choose to explore the path that is most
potential. If this path happens to reach the desired goal, other
In the following section, we introduce the heuristic-based
approach for doing so.
ꢀ
ꢀ
ꢁ
ꢀ
Activity, Beach, Area, Weather}
• The set of states: {s0}
• The initial state: s0
• The set of label actions is the acronym of the name of
web services: L={H R, C H, HC, H P, SC, SC H, CS,
ABS, AW S, CW S}
ꢀ
ꢀ
• The transition relations: δ = { [Hotel ∧ Dates] s0 ×
ꢀ
H R → s0 [Hotel Reservation],
ꢁ
ꢀ
ꢁ
ꢀ
[City] s0 × C H → s0 [Hotel],
format of the XML language. Under this structure, the decla-
ration of variables and constants is presented in Declaration
section; Process contains the main contents of the model.
In particular, States contains the states of the model, which
has only one state s0 as discussed; Transitions contains
the transitions of the model. In this section, Event contains
the names of transitions; Guard contains the expressions
describing the guards of transitions; and Effect contains the
expressions describing the effects of transitions.
ꢀ
[Hotel] s0 × HC → s0 [City],
ꢀ
[Hotel] s0 × H P → s0 [Price],
ꢀ
ꢁ
[Sightseeing] s0 × SC → s0 [City],
ꢀ
ꢁ ꢀ
[Sightseeing] s0 × SC H → s0 [City; Hotel],
ꢁ
ꢀ
[City] s0 × CS → s0 [Sightseeing],
ꢀ
ꢀ
[Activity] s0 × ABS → s0 [Beach],
ꢁ
ꢀ
ꢀ
ꢀ
ꢀ
[Area ∧ Dates] s0 × AW S → s0 [Weather],
ꢁ
[City ∧ Dates] s0 × CW S → s0 [Weather]}
where PX and EX are the pre-condition and effect of Web
service X, respectively.
Listing 1 LTS4WS model is represented in XML-style
<Declaration >
<!-- variables , constants declaration -->
</ Declaration >
this is an LTS which has only one state, from and to which all
oftransitionscorrespondingtotheWebservicescomeandgo.
This simplicity of this LTS renders an important advantage
when performing composition and verification as we do not
need to generate the full schema in advance like the previous
A model checker will search over the state space gen-
erated from this LTS for a state meeting the requirement
specified by hard and soft constraints. For example, the
searching problem given in the motivating example can be
<ProcessName =" System ">
<States >
<State Name =" s0" Init =" True "/>
</States >
<Transitions >
<Transition From =" s0" To =" s0"
<Event > WebService_Name </ Event >
<Guard > Guarded_Expression </ Guard >
<Effect > Effect_Expression </ Effect >
</ Transition >
<!-- Other transitions -->
</ Transitions >
</ Process >
</LTS4WS >
ꢀ
ꢀ
represented as an LTL formula of (Dates ∧ Sightseeing →
123
116
Vietnam J Comput Sci (2017) 4:111–126
Pruned due to violate the constraints
Pruned due to duplicated state
HR
[Dates, Sightseeing, City,
[Dates, Sightseeing, City, Hotel,
Hotel, Price, respTime=26] Price, HotelReser, respTime=31]
Pruned due to violate the constraints
HR
HP
[Dates, Sightseeing, City, [Dates, Sightseeing, City, Hotel,
[Dates, Sightseeing, City, Hotel,
Price, HotelReser, respTime=31]
Hotel, respTime=16]
HotelReser, respTime=21]
HR
[Dates, Sightseeing, respTime=0]
[Dates, Sightseeing, City, Hotel,
Price, respTime=15]
[Dates, Sightseeing, City, Hotel,
Price, HotelReser, respTime=20]
[Dates, Sightseeing, City,
Hotel, respTime=5]
{no need to expand}
[Dates, Sightseeing,
City, respTime=26]
{no need to expand}
Fig. 4 State-space exploration
Fig. 5 Example illustrates the
calculation of the value of
G, H1, H2, and F
CH (CityHotelService)
...
...
(Sightseeing, Dates, City, Hotel)
SC (SightseeingCityService)
(Sightseeing, Dates, City)
G=1, H1=0.1508, H2=1, F=2.1508
G=0.5, H1=0.1169, H2=1, F=1.6169
...
...
...
HP (HotelPriceInfoService)
SCH (SightseeingCityHotelService)
(Sightseeing, Dates, City, Hotel, Price)
(SightseIeninigt, Dates)
(Sightseeing, Dates, City, Hotel)
G=0.5, H1=0.6067, H2=0.5, F=1.6067
G=0.5, H1=0.4542, H2=1, F=1.9542
...
...
3 Heuristics-based approaches for web service
composition
• H(n) is the estimated cost (heuristic) from n to goal, as
H(n) = β1 H1(n) + β2 H2(n), (2)
where
In our research, to perform the process of Web service
composition and verification, we use the model checker
has main functionality of verifying a temporal expression
on a model. When the verification fails, a counter example
is returned. It is not guaranteed to be an optimal path (the
shortest path for instance). This is a general drawback of
the model checkers. Another downside of model checkers is
the state-space explosion problem. These two disadvantages
originate from the causes that PAT (and other model check-
ers) typically adopts an exhaustive search algorithm, such
as breadth first search or depth first search. Therefore, to
apply PAT to our research and overcome its weaknesses, this
study proposes using the heuristic search method (inspired
from the well-known A∗ algorithm) to improve the search
process.
• H1(n) is the estimated cost based on the QoS properties,
• H2(n) is the estimated cost based on the functional prop-
erties,
• β1, β2 are the corresponding weights of H1(n) and
H2(n).
The value of α, β, β1, and β2 can be empirically determined
and adjusted by users. By default, all of those parameters
have the same influence value of 1.
The real cost function—G(n)
i
G(n) =
,
(3)
l
Heuristic function—F(n)
where
To apply heuristic search, we define the heuristic function
F(n) as the following formula:
• i is the number of composition step from init to n.
• l is the number of functional properties that composite
Web service must be satisfied.
F(n) = αG(n) + βH(n),
where
(1)
We assume that each functional property needs one Web ser-
vice. With l properties, the smaller i, the smaller G(n) value.
• G(n) is the real cost from state init to state n,
Example 4 Supposed that we have a set of Web services as
• α, β are the corresponding weights of H(n) and G(n).
123
Vietnam J Comput Sci (2017) 4:111–126
117
number of functional properties is l = 2. In the composition
For example, at a state immediately, after the Init state, we
have i = 1 and G = 1/2.
• The initial state (init): H1 = 0
• The state after invoking the SC service (SightseeingCi-
2−1
– The response time: qnrm
=
= 0.0169
1
60−1
ꢅ
– H1 = wi ∗ qnrm = 0.0169
i
Estimated cost function based on QoS properties—H1(n)
Similarly, we will calculate the value of H1 for every state,
The QoS properties are divided into two categories, pos-
negativepropertyindicatesthelowerqualitywhilstthehigher
one in positive property reflects higher quality and vice versa.
In addition, each QoS property has a different calculation
unit, such as second (s) for response time, % for availability,
etc. Therefore, we also normalize the value sets of the QoS
propertiesbeforeprocessing. WithtwodifferentkindsofQoS
properties, we then have the different normalized functions,
respectively.
The estimated cost function based on functional proper-
ties—H2(n)
For each state in the state space, we have a set of variables
so-called environment variables, describing the considered
properties. For the functional properties, the corresponding
variables will have values of 0 or 1, which implies whether
the corresponding property has sufficient information or not.
H2(n) function aims to look ahead, evaluate, and select
the state which has the most functional properties satisfying
the goal state. H2(n) is calculated by the following formula:
Let Q be a QoS property and q the value of Q. Then,
the normalized value (qnrm) is calculated as the following
formula:
diff(funcvar(goal), funcvar(n))
H2(n) =
(7)
• If Q is a negative property, then
l
ꢃ
q−qmin
where
if qmax − qmin = 0
if qmax − qmin = 0.
qmax−qmin
qnrm
=
(4)
(5)
1
• funcvar(x) is a set of functional properties which we will
have (whose value is 1) at the state x.
• If Q is a positive property, then
• diff(A, B) is a function which counts the number of
functional properties appear in A, but does not appear
in B. Thus, diff(funcvar(goal), funcvar(n)) is the num-
ber of functional properties required by users that have
not yet achieved at state n. When diff(funcvar(goal),
funcvar(n)) = 0, in aspect of functionality, state n satis-
fies the user requirements.
ꢃ
qmax−q
if qmax − qmin = 0
if , qmax − qmin = 0.
qmax−qmin
qnrm
=
1
Here qmax and qmin is the upper bound and lower bound of
q, respectively.
After obtaining the normalized value for each property, we
calculate the overall average value (H1(n)) for all QoS prop-
erties of Web services. The formula for calculating H1(n) is
as follows:
Example 6 Supposed that we have a set of Web services
of functional properties of state goal is funcvar (goal) =
{Price, Hotel Reservation}, l = 2. The value of H1 of
each state is calculated as follows:
ꢄ
H1(n) =
wi ∗ qnrm
(6)
i
where
• The initial state (init):
– funcvar (init) = {Sightseeing, Dates}
• wi is the weight of property ith, which can be changed
by user. By default, all QoS properties have wi = 1.
diff(funcvar(goal),funcvar(init))
2
2
– H2(init) =
=
= 1
l
• qnrm is a normalized value of property ith at state n.
• The state after invoking the H P service (HotelPriceIn-
i
Example 5 Concerning the previous example, we now con-
sider a Web service with a QoS property of response time.
The response time has value in range from 1 (qmin = 1) to 60
s (qmax = 60) and the weight (w1) of 1. The values of QoS
–
funcvar (H P)
=
{Sightseeing, Dates,
City, Hotel, Price}
– H2(H P) =
diff(funcvar(goal),funcvar(H P))
1
2
=
= 0.5.
l
After calculating all values G, H1, H2, we will calcu-
late the value of the heuristic cost function F by formula
With the given QoS property, the value of H1 of each state
is calculated as follows:
123
118
Vietnam J Comput Sci (2017) 4:111–126
G, H1, H2, and F calculated in the process of composition,
with the α, β, β1, and β2 are equal to 1 and the value of the
at each processing step, composition process will select the
state, whose value of cost F is the lowest, to perform further
processing.
(S) of the Web service repository is an ordered set with k
be represented by an ordered set with 12 sorted features as
follows. S ={Activity, Adventure, Area, Beach, City, Dates,
Hotel, HotelReservation, Price, RuralArea, Sightseeing, and
Weather}.
4 Bitwise-based Web service indexing
4.1.2 Bitwise-based vectors of a Web service and user
functional requirements
In the previous sections, we have presented an approach
of representing a repository of Web services as an LTS
model, based on which a WSC request will be considered
a state-space search problem. We have also discussed using
heuristics to reach the search goal on the state space poten-
tially faster. Hence, each composition step corresponds to a
subgoal of the search problem.
Definition 4 (Bitwise-based vector of feature set) Let S be
a set of properties, or features, and ꢁ, an order relation on
S. We denote ꢁ(V, i) as the ith element of S when sorted
by ꢁ. The bitwise-based vector of a subset s of S, denoted
as V s , is given as follows:
S
Obviously, when looking for the candidates of the next
composition step, one should only consider the Web services
that are relevant to the current subgoal and discard the rest.
However, it is not easy to quickly identify the relevant Web
services at a current state. In this section, we address this
problem by presenting a bitwise-based indexing technique to
index the Web service repository. Based on the index infor-
mation, one can easily locate the Web services relevant to
some desired properties.
The idea of this technique is summarized as follows. Each
Web service in the repository is represented as a pair of
bitwise-based vectors, consisting an input vector and an out-
put vector. In these vectors, each element is a bit representing
a property, or feature. If the value of a bit is 0, the correspond-
ing feature is not covered by the Web service and vice versa.
The user requirements and subgoals are represented as a pair
of bitwise-based vectors in similar manner.
ꢃ
1
0
if ꢁ (V, i) ∈ s;
V s [i] =
(8)
S
otherwise.
Example 8 For the ordered feature set S given in Example
bitwise-based vector of s on S as follows:
V s = 000001100000.
(9)
S
For each Web service, we have two kinds of features (func-
tional properties), which are inputs and outputs. Therefore,
we construct the corresponding input and output bitwise-base
vectors as follows.
Definition 5 (Bitwise-based vector of Web service) The
bitwise-based vectors of a Web service is a pair ꢀVi , Voꢁ,
where Vi and Vo arethebitwise-basedvectorsoftheinputfea-
tures and output features, respectively. Vi and Vo are defined
4.1 Index table construction and manipulation
Example 9 The bitwise-based input and output vectors of all
In the index table, each index item is a vector representing
one feature. Web services are indexed using bitwise and (ꢀ)
operator between its input vector and the vector of each index
item. Thus, we can quickly select Web services relevant to
the feature represented by the index item. The selection of
index items relevant to the user requirements/subgoals is also
done in the same way. As a result, we can find Web services
relevant to user requirement/subgoals within almost constant
complexity. The details of these steps are represented as fol-
lows.
Similarly, the user requirement is also represented as two
bitwise-based vectors. They are so-called the bitwise-based
supplied vector and the bitwise-based goal vector.
4.1.3 Bitwise-based indexing for Web service repository
After vectorizing Web services inthe repository, weconstruct
the indexing table based on the input vectors of Web services.
4.1.1 The ordered feature set of Web service repository
2
Given a repository of n Web services with k distinct func-
tional properties (k distinct features), an ordered feature set
Wecanapplyanysortingcriterionhere. However, forconvenience, the
features are sorted by the alphabetical order unless indicated otherwise.
123
Vietnam J Comput Sci (2017) 4:111–126
119
Table 3 Bitwise-based input
and output vectors of Web
#
Web service
Bitwise-based input vector
Bitwise-based output vector
services in Table 1
1
HotelReserveService (HR)
CityHotelService (CH)
000001100000
000010000000
000000100000
000000100000
000000000010
000000000010
000010000000
010000000000
100000000000
001000000000
000000010000
000000100000
000010000000
000000001000
000010000000
000010100000
000000000010
000000000100
000100000000
000000000001
2
3
HotelCityService (HC)
4
HotelPriceInfoService (HP)
SightseeingCityService (SC)
SightseeingCityHotelService (SCH)
CitySightseeingService (CS)
AdventureRuralAreaService (ARA)
ActivityBeachService (ABS)
AreaWeatherService (AWS)
5
6
7
8
9
10
Table 4 Bitwise-based vector
of user requirement
User requirement
Bitwise-based supplied vector
000001000010
Bitwise-based goal vector
000000011000
Input: Dates, Sightseeing
Output: Price, Hotel Reservation
The indexing table is a two-column table. The first column
contains unit vectors, each of which represents a feature in
the ordered feature set. To represent the ith feature, the ith
bit of the corresponding unit vector is set as 1, whereas other
bits of the vector are kept as 0. In the same row of the index
table, the second column stores the Web services relevant to
the feature represented by the unit vector at the first column.
The process of construction of the index table is presented
Table 5 Indexing table of Web service repository
Index item
List of Web services
100000000000
010000000000
001000000000
000100000000
000010000000
ꢀ100000000000,000100000000ꢁ (ABS)
ꢀ010000000000,000000000100ꢁ (ARA)
ꢀ001000000000,000000000001ꢁ (AWS)
ꢀ000010000000,000000100000ꢁ (CH),
ꢀ000010000000,000000000010ꢁ (CS)
ꢀ000001100000,000000010000ꢁ (HR)
ꢀ000001100000,000000010000ꢁ (HR),
ꢀ000000100000,000010000000ꢁ (HC),
ꢀ000000100000,000000001000ꢁ (HP)
000001000000
000000100000
Algorithm 1 Index table construction
Input: A Web service repository with n Web services
Output: The index table
000000010000
000000001000
000000000100
000000000010
Step 1. Build the ordered feature set S
1: Extract features from Web services and build the ordered feature set
S
Step 2. Build the initial index table – T
ꢀ000000000010,000010000000ꢁ (SC),
ꢀ000000000010,000010100000ꢁ (SCH)
2: for i from 0 to S.size() − 1 do
3:
4:
Build the unit vector vi of which bit ith is 1
T [i][0] ← vi
000000000001
Step 3. Update the index table
5: for each Web service w in the repository do
6:
7:
8:
9:
Build the input vector vw and output vector vw of w
in
out
4.1.4 Choosing indexing items and choosing Web services
for i from 0 to T.size() − 1 do
vi ← T[i][0]
As discussed earlier in this text, at each composition, the
Web services that are matched with indexing items corre-
sponding with the current subgoal (i.e., they are relevant to
the subgoal features) will be chosen as the candidates for
the next step. The matching mechanism is implemented as
follows.
if vi ꢁ vw = 0 then // ꢁ is the bitwise AND operator
in
10:
11: return T
T [i][1].add(w)
Example 11 The index table of the Web service repository
123
120
Vietnam J Comput Sci (2017) 4:111–126
Definition 6 (Bitwise-basedmatching) Let V bethebitwise-
based input vector of the current subgoal, and Vk be the
bitwise-based vector representing the kth index item. The
kth item is a matched index item iff:
obtained features, i.e., the 1-valued bits on the bitwise-
based vector of the current composite Web service, obviously
increases. Therefore, the number of selected index item and
selected Web services considered as candidates for each step
also increases. After several steps, the number of chosen
index items will be enormous and almost all of Web services
will be selected. This unfavorably increases the complexity
of the composition process. Therefore, we need to consider
reducing the number of selected Web services at each com-
position step reasonably.
V ꢀ Vk = Vk
(10)
where ꢀ is the bitwise AN D operator.
the initial current subgoal, the inputs at the first composi-
tion step are Sightseeing, Dates with the corresponding
input vector 000001000010. The chosen index items are
000001000000 (corresponding to the value of sixth bit being
1) and 000000000010 (corresponding to the value of eleventh
bit being 1). Therefore, the chosen Web services are HR, SC,
SCH. In this case, the model checker will verify and choose
rejected, as it requires the input of Dates that we do not
have at that point.
To reduce the number of selected Web services, we con-
sider the following remarks.
Eliminating the redundant Web services
The redundant Web service is the Web service of which
the bitwise-based output vector is contained in bitwise-
based vector of the current input. The contained relation-
ship between two bitwise-based vectors is defined as in
Definition 8 (The bitwise-based contained relationship) Let
V and Vk are two bitwise-based vectors. V contains Vk
After selecting the Web services to put into the com-
position process at each composition step, the composition
process will execute normally and the heuristic function will
choose the best Web service to compose first, as previously
discussed. The output of this web service is added the current
input of the next subgoal. In that case, a Composite Bitwise-
based Vector is generated as follows.
out
out
or Vk is contained in V iff
out
V ꢀ Vk = Vk
(13)
out
out
where ꢀ is the bitwise AN D operator.
Definition 7 (Composite bitwise-based vector) Let V be the
bitwise-based vector of the input of the current subgoal, W Sk
Example 14 Suppose that at a specific composition step,
we have obtained information of the features of Sightsee-
ing, Dates, City, corresponding to the bitwise-based vector
of the current input V = 000011000010. The index items
which satisfy vector V are 000010000000, 000001000000,
and 000000000010, and the satisfied Web services which will
be used in the composition process are H R, SC, SC H, C H,
vice CS (CitySightseeingService), which takes in the City
and returns the Sightseeing, corresponding to the bitwise-
based out vector is Vk = 00000000010. Since Vk and V
be the chosen Web service to compose, Vk be the bitwise-
out
based vectors of the output of W Sk. The bitwise-based vector
Vc of the resulted composite Web service is calculated as
follows:
Vc = V ꢂ Vk
(11)
out
where ꢂ is the bitwise O R operator.
out
out
Example 13 Assumed that the input of current subgoal is
Sightseeing, Dates, corresponding to vector
satisfy the bitwise-based contained relationship as follows:
V = 000001000010. Supposed that the Web service Sight-
V ꢀ Vk = 000011000010 ꢀ 00000000010
seeingCityService is selected with Vk = 000000000010
out
in
and Vk = 000010000000. The bitwise-based vector of the
= 000000000010 = V
(14)
out
kout
composite Web service (Vc) is calculated as follows:
the Web service CS is a redundant Web service and will not
be selected to put into the considered set.
Vc = V ꢂ Vk = 000001000010 ꢂ 000010000000
out
= 000011000010.
(12)
4.1.5 Reducing the number of chosen Web services
4.1.6 The satisfied composite Web service
In the approach of selecting Web services, as presented
The composition process stops when the obtained features
satisfy the initial user requirement. It means that the bitwise-
123
Vietnam J Comput Sci (2017) 4:111–126
121
based vector of current input (V ) contains the bitwise-based
vector of user goal (Vg), or
The Web service selection process is represented as in the
following table. The strike-through lines are the eliminated
Web services.
V ꢀ Vg = Vg
(15)
Current input features
Current input vector (V )
Chosen index
Chosen web services
WS
Bitwise-based input vector
Bitwise-based output vector
Sightseeing, Dates, City
000011000010
000001000000
000000000010
000010000000
HR
SCH
CH
000001100000
000000000010
000010000000
000000010000
000010100000
000000100000
4.2 Case study
As in above table, we have three Web services used in
composition (H R, SC H, and C H). The heuristic function
chooses the Web service C H to compose in next step. After
invokingthisWebservice, thebitwise-basedvectorofcurrent
In this case study, we consider the set of Web services listed
with the following steps.
input V = V ꢂVC H = 000011000010ꢂ000000100000 =
out
000011100010. This vector does not contain the vector of
user goal (V ꢀ Vg = Vg). The composition process will be
continued.
Step 1
Current input features
Current input vector (V )
Chosen index
Chosen web services
WS
Bitwise-based input vector
Bitwise-based output vector
Sightseeing, Dates
000001000010
000001000000
000000000010
HR
SC
SCH
000001100000
000000000010
000000000010
000000010000
000010000000
000010100000
Supposed that in the composition process, the heuris-
tic function evaluates that the Web service SC is the
most suitable Web service to be invoked. After invoking
Web service CS, the bitwise-based vector of current input
Step 3
At this step, we have four chosen index items with seven
Web services (HR, SC, SCH, CH, CS, HC, HP), as in the
table below.
V = V ꢂ VCS = 000001000010 ꢂ 000010000000 =
out
Current input features
Current input vector (V ) Chosen index
Chosen web services
WS Bitwise-based input vector Bitwise-based output vector
Sightseeing, Dates, City, Hotel 000011100010
000001000000 HR
000000000010
000010000000
000000100000
HP
000001100000
000000100000
000000010000
000000001000
000011000010. This vector does not contain the vector of
user goal (V ꢀVg = Vg). Therefore, the composition process
will be continued.
According to above table, many Web services will be fil-
tered out. In particular, SC, C H, SC H, CS, and HC are
thrown away, because they are the redundant Web service;
H R in the sixth row is removed, because it is duplicated.
Therefore, we have only two remained Web services of H R
and H P. The heuristic function will choose the Web ser-
vice H P to compose, and the current input vector is updated
Step 2
At this step, we have three chosen index items with five
Web services (HR, SC, SCH, CH, CS). However, the Web
services SC and CS are eliminated, as they are redundant.
123
122
Vietnam J Comput Sci (2017) 4:111–126
Table 6 Experiment data sets
Data set
No. of Web services
Description
Travel Booking (TB)
Medical Services (MS)
Education Services (EDS)
Economy Services (ECS)
Global
20
50
Including web services providing information to serve the travel booking
Services support to look up hospital, treatment, medicine, etc.
Services related to education, such as scholarship, courses, degrees, etc.
Including services provided information on goods, restaurant, food, etc.
1000 random services from OWL-S-TC [17]
100
200
1000
as V = V ꢂ VH P = 000011100010 ꢂ 000000001000 =
five sub-data sets, whose numbers of web services are varied
out
000011101010. This vector does not contain the vector of
user goal (V ꢀ Vg = Vg). The composition process will be
continued in Step 4.
We conduct experiment scenarios based on four different
approaches, named full schema verification, on-the-fly com-
position and verification, heuristic-driven on-the-fly compo-
sition and verification, and combined bitwise-based indexing
withheuristic-drivenon-the-flycompositionandverification.
three approaches are our proposed ones, with and without
using heuristics, and combined heuristic with bitwise-based
Step 4
At this step, with the input vector of V = 000011101010,
we have one more index item, corresponding to the vector
000000001000. However, this index item does not contain
any Web service. Therefore, there is only one service H R to
compose, as depicted in the following table.
Current input features
Current input vector (V )
Chosen index
Chosen web services
WS
Bitwise-based input vector
Bitwise-based output vector
000000010000
Sightseeing, Dates, City
000011100010
000001000000
000000000010
000010000000
000000100000
000000001000
HR
000001100000
There is no web service
After invoking the Web service H R, the up-to-date
bitwise-based vector V is 000011111010 (for obtained
features of Sightseeing, Dates, City, Hotel, Price and Hotel-
Reservation). Thisvectorcontainsthevectorofusergoal(V ꢀ
Vg = 000011111010 ꢀ 000000011000 = 000000011000 =
Vg). Therefore, the composition process stops.
In summary, we have the composite Web service which
consists of four Web services as SC • C H • H P • H R.
indexing. The experiment is performed on a PC with core
i5-5200 processor (4 x 2.7 GHz), 8.0 GB RAM, running on
the 64-bit Windows 7 operating system. The experimental
results are evaluated in three aspects: the number of expanded
states, the number of visited states, and the execution time,
The experimental results confirm our hypothesis that the
indexing helps in reducing the number of expanded states
Note that the heuristic algorithm in the WSCOVER tool
always chooses the best way, i.e., the way that is evaluated
most potential to reach to goal, to travel in the state space. Our
heuristic approach showed it efficiency when there is almost
no back-tracking step taken when the model checker explores
the state space (i.e., the states suggested by the heuristic algo-
rithm are, in fact, the states in the right path to the goal).
Thus, the third and the fourth approaches, empowered by
this heuristic strategy, enjoy a far less numbers of visited
states, as compared with those in the first and the second
5 Experimentations
In this section, we present the experimental results of our
The tool WSCOVER is experimented on the real data sets
provides over 1000 Web services classified into different
3
This tool and its guidelines and also all experimental data sets can
be downloaded from http://cse.hcmut.edu.vn/~save/project/wscover/
123
Vietnam J Comput Sci (2017) 4:111–126
123
Table 7 Experimentation results
Data sets
TB (20)
Approaches
Expanded states
Visited states
Execution time (s)
Full schema verification
1100
825
316
316
56
56
35
35
0.250
0.210
0.155
0.155
On-the-fly composition and verification
Heuristic-driven on-the-fly composition and verification
Combined bitwise-based indexing with heuristic-driven
on-the-fly composition and verification
MS (50)
Full schema verification
16,720
12,331
2143
210
210
119
35
2.597
2.022
1.538
0.155
On-the-fly composition and verification
Heuristic-driven on-the-fly composition and verification
Combined bitwise-based indexing with heuristic-driven
on-the-fly composition and verification
316
EDS (100)
ECS (200)
Global (1000)
Full schema verification
27,400
20,824
3021
275
275
151
35
5.570
4.579
3.294
0.155
On-the-fly composition and verification
Heuristic-driven on-the-fly composition and verification
Combined bitwise-based indexing with heuristic-driven
on-the-fly composition and verification
316
Full schema verification
102,800
76,586
8324
515
515
287
35
28.198
23.030
18.273
0.155
On-the-fly composition and verification
Heuristic-driven on-the-fly composition and verification
Combined bitwise-based indexing with heuristic-driven
on-the-fly composition and verification
316
Full schema verification
Out-of-memory
Out-of-memory
91,457
Out-of-memory
Out-of-memory
1429
Out-of-memory
Out-of-memory
597.228
On-the-fly composition and verification
Heuristic-driven on-the-fly composition and verification
Combined bitwise-based indexing with heuristic-driven
on-the-fly composition and verification
316
35
0.155
Fig. 6 Visual representation of the experimental results
123
124
Vietnam J Comput Sci (2017) 4:111–126
As expected result, where the execution time mostly
unfixed, which depends on the number of back-tracking steps
from the error state.
depends on the number of expanded states and visited states,
all of our proposed methods are faster than the original one in
existing work and our new proposed bitwise-based indexing
6.1.3 Web service verification
As discussed, most of current researches of Web service ver-
ification only verify separately hard or soft constraints of the
vice verification based on the functional properties. A recent
study carried out to verify combined functional and non-
which takes in a full composition schema expressed in BPEL
and uses the model checker to verify.
6 Related works
6.1 Web service composition and verification
Research community has a lot of work related to WSC prob-
lem, which can be classified into three groups as follows.
6.1.1 Composition based on hard constraints
6.2 Web service indexing
WSC only involves the functional properties (hard con-
straints) which is the classic problem of SOA, which are
mostly based on the theory of planning of the artificial intel-
studies are based on abstract models, such as Petri net or Col-
on the requirements on input and output of the services. Sim-
by OWL-S to transform the problem from WSC domain to
planning domain and uses the planner named XPlan, con-
WSC techniques based on Petri net (or Colored Petri net).
The number of web services is increasing rapidly. That makes
the Web service composition approaches become more com-
plex and face many difficulties. Therefore, the Web service
indexing was suggested to support Web service accessing
more efficient. This issue has received the attention of many
researchers.
on the services descriptions represented by the WSDL lan-
guage. This approach uses the hash table to implement the
index. The index structure consists of two tables, Partname
Index and Service Index. Partname Index uses a hashtable
to maintain the mapping from each partname into two lists
of service names, namely, in list and out list. The Service
Index utilizes a hashtable that maps a service name into detail
information of the correspondent service. The information is
was implemented as the VitaLab system which performs the
indexing of a large collection of WSDL service description
following a semantic description of operations (given as a
tree of “is-a” relations) and, given a request for a service,
composes the available services to satisfy the request.
indexing can be used for fast discovery of Web services.
The indexing mechanisms can be either inverted indexing or
latent semantic indexing. Here, inverted index can be used
as a measure to check OWL-S description contain the given
term. Each keyword is connected to a list of document ids,
in which keyword occurs.
6.1.2 Composition based on hard and soft constraints
WSC method which combines functional properties (hard
constraints) and QoS properties (soft constraints) has been
ing genetic algorithm (GA) to solve the problem with each
possible composition encoded as a gene, to calculate value
for specific kinds of QoS properties. However, this study
only provides us a mechanism to choose the best (possible)
composition from a set of composition ways (full compo-
sition schema) rather than composes from the component
Web services. Besides, the application of genetic algorithms
has increased the complexity of the problem and thus very
difficult to apply in practice.
A different approach proposes the automated recovery
when a WSC falls into the failure state (a Web service could
With this approach, we have to have a full composition
formed into a Labelled Transition System (LTS), monitored
by a monitor automata. When an error arises (a state that
cannot be reached, corresponding to a Web service cannot
be accessed), the system will start calculating to choose the
recovery plan using the genetic algorithm. The difference
for the problem of Web service retrieval by presenting a
new approach to indexing of both SOAP and RESTful Web
services. This approach uses index structure called para-
metric index that allows users to retrieve ranked results in
accordance with specific parameters. The parameters refer to
service’s integral components and are covered in presented
formal definition of a Web service. Second, the services are
123
Vietnam J Comput Sci (2017) 4:111–126
125
Table 8 Comparison on some
Tool
Composition
Verification
Hard const.
Soft const.
Temporal
Input
of Web service composition and
verification tools
OWL-S-XPlan
X
X
X
X
X
OWL-S
OWL-S
BPEL
PORSCE II
WS-Engineer
AgFlow
X
X
X
X
X
X
X
Statechart
BPEL
VeriWS
X
X
X
X
WSCOVER
X
OWL-S
modelled in vector space that allows the evaluation of their
mutualrelevanceandenablesobtainingrankedsearchresults.
To reduce the index size and to decrease the search time,
which groups relevant service components into concepts.
work that combines formal verification with indexing
techniques in the area of Web services processing.
7 Conclusion and future work
The tool WSCOVER, developed in this research, has offered
several useful functions that the other similar works do not
support, including the capability of composing and verify-
ing Web services, in an on-the-fly manner; and extending the
model checker by applying the heuristics specifying the Web
service nature. In addition, also through this paper, we have
some contributions about the formal representation of Web
service; the bitwise-based Web service indexing method to
index the Web service repository using the bitwise opera-
tors. This helps the building of the index table as well as the
retrieval of Web services more efficient.
As a result, WSCOVER can locate a composition solution
faster and more optimally. However, in the future, this effort
also needs to be compared with some other techniques, such
as the clustering approaches to learn more about the pros and
cons of our approach. In addition, in this work, we have not
yet considered the semantic aspect of the features of Web
services. We are going to develop a mechanism to calculate
the similarity between two sets of features when they do not
match completely.
6.3 Evaluation and comparison of our approach with
other studies
others previously discussed. As observed, WSCOVER can
perform both composition and verification at the same time
and on-the-fly. Our tool composes and verifies a composite
Web service on all kinds of constraints, hard and soft con-
straint, and also the temporal relations between component
Web services.
To support model checking for composition and verifica-
tion of Web services against a pre-defined goal in an effective
manner, our work suggested representing a repository of
Web services as a mathematical model, based on Labelled
Transition System (LTS), known as LTS for Web Services
propose using LTS models for enabling the formal verifica-
tion of a WSC composition. However, our work distinguishes
to this work as follows:
Acknowledgements ThisresearchisfundedbyVietnamNational Uni-
versity HoChiMinh City under Grant Number C2015-20-10.
composition goal, even though the repository remains the
same. In contrast, our LTS4WS model can be applied for
several various goals without being rebuilt.
it does not perform the composition phase. Meanwhile,
our approach combines composition and verification at
the same time.
Open Access This article is distributed under the terms of the Creative
Commons Attribution 4.0 International License (http://creativecomm
ons.org/licenses/by/4.0/), which permits unrestricted use, distribution,
and reproduction in any medium, provided you give appropriate credit
to the original author(s) and the source, provide a link to the Creative
Commons license, and indicate if changes were made.
• We apply the heuristic search to model checking engine
based on the characteristics of Web service, so the veri-
fication performance is improved significantly.
References
• We also apply the bitwise-based indexing technique to
index the Web service repository. This approach helps
us to retrieve the Web services further faster and more
reasonably. To the best of our knowledge, it is the first
1. Yin, R.: Study of composing web service based on soa, In:
Proceedings of the 2nd International Conference on Green Com-
munications and Networks 2012 (GCN 2012), vol. 2, pp. 209–214.
Springer (2013)
123
126
Vietnam J Comput Sci (2017) 4:111–126
2. Rostami, N. H., Kheirkhah, E., Jalali, M.: Web services composi-
12. Fan, G., Yu, H., Chen, L., Liu, D.: Petri net based techniques
for constructing reliable service composition. J Syst Softw 86(4),
1089–1106 (2013)
tion methods and techniques: a review. Int J Comput Sci Eng Inf
Technol 3(6), 15–29 (2013)
3. Fitting, M.: First-order logic. In: First-order logic and automated
13. Maung, Y.W.M., Hein, A.A.: Colored petri-nets (cpn) based model
for web services composition. IJCCER 2, 169–172 (2014)
14. Tian, B., Gu, Y.: Formal modeling and verification for web service
composition. J Softw 8(11), 2733–2737 (2013)
15. Zhou, B., Huang, T., Liu, J., Shen, M.: Using inverted index-
ing to semantic web service discovery search model. In: Wire-
less Communications, Networking and Mobile Computing, 2009.
WiCom’09. 5th International Conference on. IEEE, pp. 1–4 (2009)
16. AllamehAmiri, M., Derhami, V., Ghasemzadeh, M.: Qos-based
web service composition based on genetic algorithm. J AI Data
Min 1(2), 63–73 (2013)
theorem proving, pp. 97–125. Springer, US (1990)
4. Hatzi, O., Vrakas, D., Bassiliades, N., Anagnostopoulos, D., Vla-
havas, I.: The porsce ii framework: using ai planning for automated
semantic web service composition. Knowl Eng Rev 28(02), 137–
156 (2013)
5. Chen, M., Tan, T. H., Sun, J., Liu, Y., Dong, J. S.: Veriws: a tool for
verification of combined functional and non-functional require-
ments of web service composition. In: Proceedings of the 36th
International Conference on Software Engineering. ACM, pp. 564–
567 (2014)
6. Kumara, B.T., Paik, I., Chen, W., Ryu, K.H.: Web service clustering
using a hybrid term-similarity measure with ontology learning. Int
J Web Serv Res (IJWSR) 11(2), 24–45 (2014)
7. Du, Y.Y., Zhang, Y.J., Zhang, X.L.: A semantic approach of service
clustering and web service discovery. Inf Technol J 12(5), 967–974
(2013)
17. Klusch, M.: Owls-tc: Owl-s service retrieval test collection, version
18. Burstein, M., Hobbs, J., Lassila, O., Mcdermott, D., Mcilraith, S.,
Narayanan, S., Paolucci, M., Parsia, B., Payne, T., Sirin, E., et al.:
Owl-s: Semantic markup for web services. W3C Member Submis-
sion (2004)
8. Aiello, M., Platzer, C., Rosenberg, F., Tran, H., Vasko, M., Dustdar,
S.: Web service indexing for efficient retrieval and composition.
In: E-Commerce Technology, 2006. The 8th IEEE International
Conference on and Enterprise Computing, E-Commerce, and E-
Services, The 3rd IEEE International Conference on. IEEE, pp.
63–63 (2006)
9. Czyszczon´, A., Zgrzywa, A.: Indexing method for effective web
service retrieval. Int J Intell Inf Database Syst 8(3), 189–208 (2014)
10. Huynh, K. T., Quan, T. T., Bui, T. H.: Fast and formalized:
Heuristics-based on-the-fly web service composition and verifi-
cation. In: Information and Computer Science (NICS), 2015 2nd
National Foundation for Science and Technology Development
Conference on. IEEE, pp. 174–179 (2015)
19. Klusch, M., Gerber, A., Schmidt, M.: Semantic web service com-
position planning with owls-xplan. In: Proceedings of the AAAI
Fall Symposium on Semantic Web and Agents. AAAI Press, USA
(2005)
20. Tan, T. H., Chen, M., André, É., Sun, J., Liu,Y., et al.: Automated
runtime recovery for qos-based service composition. In: Proceed-
ings of the 23rd international conference on World wide web.
International World Wide Web Conferences Steering Committee,
pp. 563–574 (2014)
21. Jordan, D., Evdemon, J., Alvesetal.:Webservicesbusinessprocess
execution language version 2.0. OASIS Stand 11, 10 (2007)
22. Foster, H., Uchitel, S., Magee, J., Kramer, J.: Wsengineer: A
model-based approach to engineering web service compositions
and choreography. In: Test and analysis of web services, pp. 87–
103. Springer, Berlin, Heidelberg (2007)
11. Liu, Y., Sun, J., Dong, J. S.: Developing model checkers using PAT.
In: International symposium on automated technology for verifi-
cation and Analysis, pp. 371–377. Springer, Berlin, Heidelberg
(2010)
123
16 trang
17320
Free
Bạn đang xem tài liệu "A bitwise-based indexing and heuristic-driven on-the-fly approach for Web service composition and verification", để tải tài liệu gốc về máy hãy click vào nút Download ở trên
File đính kèm:
- a_bitwise_based_indexing_and_heuristic_driven_on_the_fly_app.pdf
