We present STEREO, a system that offers an expressive formalism and implements techniques firmly grounded on logic to solve the Service Selection Problem (SSP). STEREO adopts the Local-As-View approach (LAV) to represent services' functionality as views on ontology concepts, while user requests are expressed as conjunctive queries on these concepts. Additionally, users can describe their preferences, which are used to rank the solutions. We discuss the LAV formulation of SSP; then, we illustrate the encoding of SSP as a logical theory whose models are in correspondence with the problem solutions, and in presence of preferences, the best models are in correspondence with the best-ranked solutions. We demonstrate STEREO and the properties of modern SAT solvers that provide an efficient and scalable solution to SSP.
Nowadays, several annotation tools like the one proposed by Ambite et al. [
STEREO is tailored to constantly changing Web service datasets and a
relatively stable set of ontology concepts. STEREO adopts the recent approach of
Ambite et al. [
Encoder Service Views
Ontology reasoner
IS=<D,S,M>
CNF Theory
Finder
Decoder Models www.aa.com www.united.com
Catalog STEREO offers a simple yet expressive language for preferences and supports users’ preferences and constraints on the set of the selected services to satisfy a given request. These preferences and constraints further refine and rank the set of valid rewritings of the posed query, in a way that the best solutions to SSP corresponds to the best-ranked valid rewritings of the corresponding QRP. STEREO constructs a propositional logical theory that captures the features associated with SSPs; each model of the theory encodes a valid combination of services, and these models are ordered by their rank and the best-ranked models are the models with minimum rank. Knowledge encoded in the ontology is used to extend the rules in the logical theory to permit the cover of ontology symbols in the query with symbols in the views according to subsumption relationships represented in the ontology. We demonstrate the benefits of the approach and show the following key issues: the expressiveness by modeling a real-world domain; the scalability by demonstrating how STEREO is able to enumerate realistic instances of SSP in a few seconds; and finally, the performance by enumerating in the same logical theory, the optimal models based on different cost/rewards of the users’ preferences. The demo is published at http://stereo.ldc.usb.ve/STEREO. 2
The STEREO architecture is comprised of a Catalog of service descriptions,
an Ontology Reasoner, the Encoder, the best model Finder, and the Decoder.
Figure 1 depicts the overall architecture. An instance of SSP consists of an
integration framework IS and a user request R. Formally, IS is a tuple hD, S, M i
where D is an ontology1, S is the set of services, and M is the set of LAV
mappings. R is a tuple hQ, P i where Q is a conjunctive query on the ontology
relational symbols and a set of preferences P . The STEREO Catalog is populated
with the integration system components. We developed an Ontology Reasoner to
compute the transitive closure of the subsumption relationships, and the Encoder
module makes use of this information in conjunction with the LAV mappings,
constant symbols, and users’ preferences to encode an input instance of SSP
1 An ontology is comprised of a set of relational and constant symbols from which
logical formulas can be constructed, and a collection of axioms describing the ontology.
as a CNF theory. STEREO uses c2d (http://reasoning.cs.ucla.edu/c2d)
to compute all the best-ranked models of the CNF theory in a certain normal
form called deterministic and decomposable negation normal form (d-DNNF)
[
We illustrate our approach on a simple travel domain that contains information about flight and train trips between cities and information about which cities are in the US. The ontology is comprised of the predicates trip, flight, train and uscity. The first predicate relates cities (x, y) if there is a direct trip either by plane or train between them. The flight predicate relates (x, y, t) whenever there is a direct flight from x to y operated by airline t, and similarly for train, and uscity indicates if a given city is or not a US city. The ontology axioms capture two subsumption relations:
flight(x, y, t) v trip(x, y). train(x, y, t) v trip(x, y).
For the services, we assume the following type of data sources: – nat-flight(x, y, t) relates two US cities that are connected by a direct flight, – one-way-flight(x, y) relates two cities that are connected by a one-way flight, – nat-train(x, y) relates US cities that are connected by a direct train, – to-pa(x) tells if there is a direct flight from x to Paris operated by American, – from-la(x) tells if there is a direct flight from LA to x operated by United.
Based on the ontology concepts the services are described using LAV views: one-way-flight(x, y) :− flight(x, y, t) .
nat-flight(x, y) :− flight(x, y, t), uscity(x), uscity(y) . nat-train(x, y) :− train(x, y, t), uscity(x), uscity(y) .
to-pa(x) :− flight(x, Paris, AA) .
from-la(x) :− flight(LA, x, UA) .
Consider a user that needs to select the services able to retrieve one-stop round trips from a US city x to any city y in the world, and the user prefers flying than traveling by train. This request is represented as follows:
Q(x, y) :− uscity(x), trip(x, u), trip(u, y), trip(y, v), trip(v, x) .
This preference is modeled by assigning a high reward to the symbol flight. Any rewriting of the ontology predicates in terms of the services defined by these predicates, implements the request. In addition, rewritings comprised of services defined by the symbol flight will have higher scores than those with services defined by the symbol train. Thus, this rewriting is valid and highly ranked: I(x, Paris) :− nat-flight(x, u), to-pa(u), one-way-flight(Paris, v), nat-flight(v, x) . But, the following rewriting is not a valid solution because it maps the query variable y into two different constants Paris and LA that denote different cities:
I0(x, y) :− nat-flight(x, u), to-pa(u), from-la(v), nat-flight(v, x) .
Using this travel domain, we consider the following scenarios: – We run STEREO in three different benchmarks. We start with a benchmark of queries with 2 to 5 sub-goals and sets of 10 to 100 services; we show that the sets of 100 airlines with 5-stop flights can be compiled in 328 secs, the best model can be computed in 0.29 secs, and the enumeration of all models in 0.47 secs. We add a second service for each airline and show that STEREO behavior remains similar. Finally, we try services with multiple sub-goals which are randomly generated and show that the compilation time does not grow monotonically with the number of views. The time to find the best model is 0.46 secs while the enumeration of all models is about 17 hours. – We test the system with ontologies of different sizes and show reusability by assigning different cost/reward to the preferences; we also demonstrate that the same d-DNNF can be used to compute the best model, while the execution time remains almost the same. 4
We present a logical-based approach that relies on the LAV formalization to solve SSP; the approach is expressive, efficient and scalable. We illustrate the formalization of service functionalities in terms of simple conjunctive rules. In addition, we demonstrate a propositional logic-based formalization of SSP instances, and different scenarios where the properties STEREO can be observed by users. We show how the approach can be applied to real-sized problems, while the whole approach is only possible when the compilation of the CNF theory into d-DNNF succeeds.