A Human-Oriented Approach
Towards Service Composition
Eran Toch*, Dov Dori, Avigdor Gal
and Iris Reinhartz-Berger
Service Oriented Computing Seminar, IBM Haifa Labs
May 2007
*Supported by the Levi Eshkol grant from Israel’s Ministry of Science
Specification and Analysis of Information Systems
Haifa University
Spring 2005
1
Agenda
1. Motivation
2. Crawl
3. Query
2
The Composition Utopia
Bryson et al., Toward Behavioral Intelligence in the Semantic
Web, IEEE Computer, 35(11), November 2002.
User
Agent
Identification
Service
Update Insurance
Company
Update Medical
Records Application
Update Hospital
Records
Web Services Pool
3
However, it did not work so far. Why?
• Matching is difficult
– Slim chance of exact matching
– Execution is very difficult (due to stateful
services, among other reasons)
• Burdon on users
– Requirements must be complete
– Knowledge of syntax is required
• Performance
S Dustdar and W Schreiner, A Survey on Web Services Composition, International
Journal of Web and Grid Services, 2005
C Beeri et al., Querying business processes, VLDB'06
4
Useful Service Compositions
• User interaction
– Explore, rather than plan
– Serve the design phase
– Ranking reflects the amount of approximation
• Retrieval mode
– Avoid fully automated compositions
– Sub-linear performance
5
Opossum
Eran Toch et al., A Semantic Approach to Approximate Service
Retrieval, ACM Transactions on Internet Technology, February 2008.
6
The Process of Service Retrieval
Is there an: OpenID identification
Service?
User
We have only identification
services based on username /
password
Opossum
Ok, can you combine it with the
open-id interface?
Hmmm, maybe...
7
Agenda
1. Motivation
2. Crawl
3. Query
8
What can we Crawl
Service description: WSDL, OWL-S, Web forms...
Identification Service
Input: username, password
Output: user-id
If fails
And tries < 3
if success
Send password
to email
Input: email
BPEL, OWL-S
Process
Model
Registration
Input: username,
personal details
Output: confirmation
9
Extracting Service Networks
Inferred
Dependencies
10
Ontologies
c=0.7
Identification
Service
Update Insurance
Company
11
Semantic Distance
Concept x
Concept b
Concept a
Similarity Radius
dis (a, b) =
Distance function
α - distance coefficient
Semantic edge number / certainty
path =
1
2
logα ( path )
1
+
∑
i∈a → x c (i )
1
∑
j∈b → x c ( j )
c(i), c(j) – certainty value on edges
12
Example Service Network
• 828 services
• 5432 concepts
• 23 ontologies
13
What Makes a Good Ontology?
Approxim ation factor
3000
2500
2000
1500
1000
500
0
0
5
10
15
20
25
30
connectivity
14
Agenda
1. Motivation
2. Crawl
3. Query
15
Simple Query Interface
• Basic:
– “drug”
• Ordered Conjunctions:
– “medical treatment hospital
and map”
• Properties:
– “medical treatment
provider: mount sinai
hospital”
– For example: provider,
price,
16
OPCAT-Based Query Interface
http://www.opcat.com/
17
Retrieval Model
Query - An ontology-labeled
Result:
rooted, directed tree
A ranked set of rooted, directed trees
Geographical
Treatment
Locator
medical
treatment
Map
Hospital
“medical treatment hospital and map”
Insurance
Treatment
Locator
Insurance
treatment
locator
Hospital
Info
Service
Google
Maps
Google
Maps
Check
Hospital
Availability
18
Query/Result Satisfiability
medical
treatment
Map
Address
?
Hospital
Info
Service
Yahoo
Maps
Question: When is a service
composition satisfies a
query?
Assumption: a user would
like to minimize the required
effort of adapting the
composition.
Therefore, we would like the
results ranking to reflect this
notion.
19
Cost Model
score(V , Q) =
∑
v∈V , q∈Q
Semantic
matching score
µ (v, q) + δ edit (V , Q) + ∏ ce
Edit distance
e∈V
Composition
inner certainty
a
A
c=1
b
B
c = 0.8
c
Z
c=1
z
20
A-Priory Ranking
21
Combining Compositions
A
d
B
D
C
E
e
b
e
f
c
f
F
V ′ = {V ∪ Vi | V ∩ Vi = φ ∧ score(Vi , Q) = max{score(Vi ), score(Vk )}}
Vk ⊆ V
22
Query Evaluation
Concepts
Index
Query
Composition
Index
Results
Virtual Service
23
Indexing
“Insurance
Operations”
“Geographical
Operations”
Authorize
Treatment Plan
Retrieve Insurance
Record
Find Position
Find Nearest
Medical Center
Contact
Emergency
Inform
Hospital
Check Hospital
Availability
Check Room
Availability
Check Personnel
Availability
“Hospital
Procedures
Operations”
“Emergency
Operations”
“Medical
Operations”
24
Scalability
P – number of parameters
nc – create new concept
c – concept mapping
Service
Generator
Simulate
d service
processing time (in ms)
60
50
40
30
20
10
Trendline
0
0
500
1000
1500
2000
2500
3000
number of services
25
Thank You.
http://www.technion.ac.il/erant
26