WWW 2008 / Refereed Track: Web Engineering - Web Service Composition Beijing, China Matching Independent Global Constraints for Composite Web Services Nalaka Gooneratne Zahir Tari School of Computer Science and Information Technology RMIT University Melbourne, VIC 3001, Australia {ngoonera, zahir t}@cs.rmit.edu.au ABSTRACT Service discovery employs matching techniques to select services by comparing their descriptions against user constraints. Semantic-based matching approaches achieve higher recall than syntactic-based ones (as they employ ontological reasoning mechanisms to match syntactically heterogeneous descriptions). However, semantic-based approaches still have problems (e.g. lack of scalability as an exhaustive search is often p erformed to located services conforming to constraints). This pap er prop oses two approaches that deal with the problem of scalability/p erformance for comp osite service location. First, services are indexed based on the values they assign to their restricted attributes (the attributes restricted by a given constraint). Then, services that assign "conforming values" to those attributes are combined to form comp osite services. The first prop osed approach extends a local optimisation technique to p erform the latter, since identifying such values is NP-hard. However, this approach returns false negatives since the local optimisation technique does not consider all the values. Hence, a second approach that derives conforming values using domain rules is defined. The used rules are returned with each comp osite service so that a user can understand the context in which it is retrieved. Results obtained from the exp eriments that varied the numb er of available services demonstrate that the p erformance of the local optimisation-based approach is 76% b etter than existing semantic-based approaches and recall is 98% higher than syntactic-based approaches. user requests against service descriptions to retrieve appropriate services. A service discovery approach is either syntactic-based [11] (where descriptions are represented as a set of strings and "string matching" is used) or semantic-based [2] (where ontological relationships are used to p erform mappings b etween terms of user requests and service descriptions). It is well accepted that semantic-based approaches achieve higher recall than syntactical ones [2]. Therefore the focus of this pap er is on semantic-based matching and we will show the limitations of existing approaches (esp ecially when dealing with complex/comp osite services). Before providing further details ab out existing semanticbased approaches, we will first consider the following scenario which will b e used in the rest of this pap er (to illustrate the use of various concepts). In this scenario, we want to model the "purchase service", where a user wishes to purchase a (Macintosh) computer online and wants it delivered home. A shipp er should b e able to pick up this computer from the dispatch location of a seller, and it should b e insured from the p oint at which the computer is picked up. The computer must not b e insured until it is assembled (so that the insured p eriod can b e maximised), and it should not b e picked up by the shipp er until it is insured. The (comp osite) service shown in Figure 1 is formed by locating, co-ordinating and collab orating the constituent services, and executed to satisfy this request. Computer Sales User Interactions Shipping Insurance Categories and Subject Descriptors H.3.3 [Information Search and Retrieval]: Search process, Selection process; H.3.5 [Online Information Services]: Web-based services General Terms Performance, Theory, Algorithms Figure 1: A Composite Service Locating a comp osite service (like the one shown in Figure 1) would require accurate sp ecifications of b oth service descriptions and user requests. Constraints are used in user requests to accurately describ e the services that need to b e located [2]. They are of two typ es: local and global constraints. The former restricts the values of a particular attribute of a single service (e.g. type.Computer = MACINTOSH), whereas the latter simultaneously restricts the values of two or more attributes of multiple constituent services. Global constraints can b e classified based on the complexity of solving them (i.e. determining the values that should b e assigned to their attributes) as either strictly dep endent or 1. INTRODUCTION Web services are autonomous and modular applications that are located, accessed and executed over the Internet. Service discovery enables such services to b e located based on functional requirements [2], non-functional requirements [12] or b oth [10]. It employs matching techniques to compare Copyright is held by the International World Wide Web Conference Committee (IW3C2). Distribution of these papers is limited to classroom use, and personal use by others. WWW 2008, April 21­25, 2008, Beijing, China. ACM 978-1-60558-085-2/08/04. 765 WWW 2008 / Refereed Track: Web Engineering - Web Service Composition independent. A (global) constraint is strictly dep endent if the values that should b e assigned to all the remaining restricted attributes can b e uniquely determined once a value is assigned to one. location.Dispatch = location.Pickup validRegion.Insurance is an example of a strictly dep endent global constraint. Once MELBOURNE is assigned to location.Dispatch, the same value has to b e assigned to location.Pickup and included in the set of values assigned to validRegion.Insurance. Services that conform to strictly dep endent global constraints can b e easily located in p olynomial time [5]. Any global constraint that is not strictly dep endent, is independent. For example, availableDate.Computer approvalDate.Insurance date.Pickup is an indep endent global constraint. In our opinion, the class of comp osite services that conform to indep endent global constraints is probably the "most" interesting to study, as their location is known to b e NP-hard [3, 12]. Indeed, if a given indep endent global constraint restricts q attributes, and if service descriptions assign p values to each attribute, then a technique locating a conforming service may have to consider pq combinations of values. As a consequence most of the existing matching techniques (for locating comp osite services) do not consider indep endent global constraints [1, 8]. Nonetheless, there are some that consider them [9, 11, 12] and they use integer programming solutions focusing on local optimisations [12] and AI planners [9, 11] to efficiently locate conforming comp osite services. However, all the techniques of the latter typ e are syntactic-based approaches. None of the current semanticbased comp osite matching approaches consider indep endent global constraints. This pap er prop oses a semantic-based matching technique that locates services conforming to indep endent global constraints. A two dimensional data structure, called a slot list, is designed to efficiently find services. Available services are indexed based on the values they assign to the attributes restricted by a global constraint. This index enables the quick retrieval of services that assign a particular value to their restricted attribute. Then, tuples of conforming values are determined using either a greedy approach or derived using domain rules [2]. Finally, services that assign these conforming values to their restricted attributes are retrieved from the slot list and combined to form conforming comp osite services. Exp eriments were p erformed to compare the prop osed techniques against a syntactic-based comp osite matching technique [11] and a relevant semantic-based matching technique [2]. The prop osed technique that incorp orates a greedy algorithm p erforms 76% b etter than the existing techniques. Exp erimental results also show that the prop osed approaches achieve a higher recall than syntacticbased approaches. The rest of his pap er is organized as follows. In the remaining sections we will refer to comp osite services simply as "services" (b ecause the focus of this pap er is only on the discovery of such services). Section 2 overviews some background needed to understand the various parts of the pap er. In Section 3 we provide concise guidelines on how requests for services should b e sp ecified. Section 4 details the prop osed comp osite matching techniques and Section 5 provides a summary of advantages/limitations of the prop osed approaches. Details of the exp eriments are given in Section 6. In Section 7, we review existing comp osite matching techniques. Finally, we summarize and conclude in Section 8. Beijing, China 2. BACKGROUND Meta-Ontology In this pap er we will use the meta-ontology prop osed by Elgedawy et al. in [2]. As p ointed out in [5], in this ontological structure relationships can b e accurately modeled and reasoned using a "simple" mechanism. A meta-ontology consists of four typ es of elements (i.e. concepts, op erations, roles and rules). Concepts are basic entities of a domain. Domain elements with common attributes are abstracted into concepts (e.g. - Computer, Finance, Insurance). Transactions that are p ermitted in a domain are sp ecified with op erations (e.g. - Sales(), Insure(), Ship()). Roles are used to sp ecify the actors such as Sales Assistant, Telemarketer. A description of rules will b e provided later in this section. The relationships b etween the elements of an ontology are sp ecified with substitution graphs and transformation graphs. In a substitution graph, the contextual asp ect of a relationship is sp ecified with a substitution condition. Each (substitution) graph defines a set of attribute mappings. Figure 2 depicts an example of a substitution graph which sp ecifies the relationship b etween Computer and Laptop. A transformation graph models a relationship requiring the metamodel of an element to b e changed. It is sp ecified with one or more consecutive op erations. Figure 3 shows a transformation graph modeling the relationship b etween Del l and Intel (which are brand names of a Computer and a Processor). This is sp ecified with an op eration that lists comp onents and another that returns the typ e of one. battery.Laptop = NOT_REQUIRED Computer Laptop price processor display memory networking options hard disk input devices optical drives sound system price processor size memory networking options hard disk battery Figure 2: Substitution graph DELL Component:list(Computer) ComponentType:typesOf(Component) INTEL Figure 3: Transformation graph 766 WWW 2008 / Refereed Track: Web Engineering - Web Service Composition These two data structures (i.e. substitution and transformation graphs) are sp ecified for every element of an ontology (i.e. concept, op erations, roles). The meta-ontology requires any transitive relationship to b e explicitly sp ecified with the data structures. For example, if Calculator can b e substituted with Laptop, and Laptop can b e substituted with Computer, there is a transitive substitution relationship b etween Calculator and Computer. Then, a substitution graph which allows the concept Calculator to b e substituted with Computer should b e explicitly included in the ontological descriptions. Beijing, China WS-ALU E The prop osed comp osite matching technique assumes that the functional descriptions of services are sp ecified with WSALU E [6]. In such a language, the functionality of a service is describ ed by three elements; its purp ose (goal), state transitions and data transformations. Current description frameworks represent the purp ose with an op eration [2, 6]. The state transitions are describ ed with pre-conditions (describing the state that the execution environment of a service needs to b e in b efore commencing its execution) and postconditions (describing the state after its execution has b een successfully completed). States are describ ed by the values that can b e assigned to the attributes of a service according to the pre-conditions or the p ost-conditions. Data transformations are describ ed with inputs and outputs. Unlike other functional description frameworks, WS-ALU E models all three functional asp ects together [6]. For the approach prop osed in this pap er, descriptions that sp ecify the purp ose and the state transition p erformed by services would b e sufficient. However, WS-ALU E is selected b ecause we intend to develop techniques that verify the comp osability [7] and compatibility [7] of (comp osite) services, in the future. An WS-ALU E 's op eration (used to describ e the purp ose of a service) is constrained by the role it p erforms in a domain and the concepts it affects. For example, a Computer Sales service p erforms the op eration Sales(), affects the concept Computer and p erforms the role of an Sales Assistant. The data transformations are describ ed with inputs and outputs. "in-constraints" and "out-constraints" restrict the values used as inputs and outputs. State transitions are describ ed with pre-conditions and p ost-conditions. The conditions (sp ecifying the in-constraints, out-constraints, pre-conditions and p ost-conditions) model a relationship b etween an attribute and a value. A condition explicitly reduces the scop e of an attribute to a particular domain. The scop e of an attribute is the set of values that can b e assigned to the attribute. It is defined by associating an attribute with a concept. For example, the scop e of the attribute dispatchTime cannot b e determined unless it is sp ecified as dispatchTime.Computer. Then any value (sp ecifying the time taken to dispatch a computer) can b e assigned to the attribute dispatchTime. When an attribute is used in a condition, its scop e is reduced to a particular domain. For example, in a condition of the form dispatchTime.Computer<24 HOURS, the scop e of dispatchTime.Computer is reduced to a value less than 24 hours. should b e picked up a day after it is made available according to standard procedures", "A customer is categorized as VIP if more than 100 purchases are made within a week"). The second matching approach prop osed in this pap er will use these rules to derive values that conform to indep endent global constraints. An exact sp ecification of how these rules are represented is not provided in [2]. Therefore, we assume that a rule is sp ecified as a function, which derives a value that should b e assigned to a derived attribute based on a value that is assigned to a determinant attribute. The context in which these assignments should b e made to the attributes is sp ecified with an op eration, an affected concept and a role. Figure 4 depicts graphical representations of the first two sample rules describ ed ab ove. availableDate.Computer [Sales(), Computer, Sales_Assistant] SAME DAY standardProcedure() approvalDate.Insurance [Insure(), Computer, Sales_Representative] approvalDate.Insurance [Insure(), Computer, Sales_Representative] +1 DAY standardProcedure() date.Pickup [Ship(), Computer, Shipping_Agent] Figure 4: Sample Rules Context Matching Technique Elgedawy's approach [2] matches the contexts of two similar goals. Their notion of "semantically related attributes" will b e used in the prop osed technique to identify the list of attributes related to a given attribute according to ontological relationships. Definition 1 (Semantically Related Attributes). Given two attributes ai and ay where their scopes are defined with the concepts ci and cy respectively, ai is semantical ly related to ay if cy can be substituted with ci using either a substitution graph or a transformation graph, and the substitution results in ai being mapped to ay . The attribute Computer.display is semantically related to Laptop.size according to the substitution graph given in Figure 2, b ecause Computer substitutes Laptop and the substitution results in display b eing mapp ed to size. 3. USER REQUEST Concise guidelines (for creating requests for comp osite services) are given in this section. The prop osed matching technique assumes that a request is structured according the given guidelines. A request consists of a comp osite service template and a constraint model. The former sp ecifies the typ es of services that need to b e aggregated to form a comp osite service. It is defined as a collection of service typ es. A service typ e is describ ed with the triplet [O, C, R], where O is an op eration, C is an affected concept and R is a role. A description of the comp osite service template of the service given in Figure 1 follows. {[S ales(), C omputer, S ales Assistant], [S hip(), C omputer, S hipping Ag ent], [I nsur e(), C omputer, S ales Repr esentativ e]} Constraints are included in a request to provide an accurate description of the required services. For example, the constraint "type.Computer = Macintosh" (which is applied on Rules Rules of a meta-ontology [2] define the legitimate derivations of a domain (e.g."Insurance should b e approved immediately according to standard procedures", "A computer 767 WWW 2008 / Refereed Track: Web Engineering - Web Service Composition services that sell computers) states that only those that sell Macintosh computers are required. The constraint model describ ed here contains an indep endent global constraint. Such constraints are formed with a collection of binary attribute comparisons (binary constraints). For example, availableDate.Computer approvalDate.Insurance date.Pickup is an indep endent global constraint. Typically, a global constraint is sp ecified with a non-empty set of attributes. Additionally, a typ e which indicates whether a constraint restricts attributes that describ e either pre-conditions (of services), p ost-conditions or b oth is included in a sp ecification. The prop osed approach employs b oth a local optimisation technique and derivation-based technique (that uses domain rules) to determine values that conform to a given constraint. The reasons for using these techniques will b e describ ed in the next section. Both of these techniques determine the values that should b e assigned to all the attributes based on a value assigned to one. Hence, they use the values assigned to one particular attribute as a starting p oint. This attribute is referred to as the "free attribute". Unlike the values assigned to the non-free attributes, all the values assigned to this attribute will b e considered by the prop osed approach when determining conforming values. Since an indep endent global constraint is a collection of binary attribute comparisons, the relationships b etween the attributes are sp ecified with a set of binary op erators. Each one of them is sp ecified with two attributes and relational op erator, which can b e either =, <, >, , , =, , , or . Following is the description of availableDate.Computer / approvalDate.Insurance date.Pickup. {av ailableDate.C omputer, appr ov alDate.I nsur ance, date.P ickup}, P OS T , av ailableDate.C omputer {av ailableDate.C omputer appr ov alDate.I nsur ance, appr ov alDate.I nsur ance date.P ickup}, Beijing, China (1) Candidate Acquisition This phase describ es a way of locating candidate services. A candidate service is a service of a particular typ e, and the prop osed approach locates such services for all the typ es in a comp osite service template. By locating candidate services, it ensures that the constituent services of a comp osite service are of appropriate typ es. Let Sm b e a service typ e and sn a given service. We also denote by om , cm and rm the op eration, the affected concept and the role that describ e Sm . For sn we denote its elements by on , cn and rn . The service sn is a candidate of typ e Sm if on substitutes om , cn substitutes cm , and rn substitutes rm . The substitutions are p erformed with the substitution graphs in a meta-ontology [2]. Each candidate si of typ e Si is placed in a list of candidates candidates(Si ). Given the available services W and a comp osite service template CST (defined with the service typ es Sx , . . . , Sy ), this phase generates a set of candidate lists Candidates, where Candidates={candidates(Sx ), . . . , candidates(Sy )}. (2) Service Indexing Phase This phase identifies the restricted attributes of candidate services and indexes them in a two dimensional structure based on the values they assign to these attributes. An attribute is restricted, if the assigned values are restricted by a user constraint. Such attributes need to b e identified b ecause whether a particular candidate service can b e included in a conforming comp osite service is determined based on the values assigned to them. Since this technique is semanticbased, an attribute of a service is considered as a restricted attribute if it is semantically related to one that is used to sp ecify a global constraint. Consider the constraint availableDate.Computer approvalDate.Insurance date.Pickup describ ed in Section 3. This restricts the attributes availableDate.Computer, approvalDate.Insurance and date.Pickup of services of typ es Sales(Computer), Insure(Computer) and Ship(Computer)1 . A service ComputerSales-I of typ e Sales(Computer) describ ed with date.Dispatch exists. date.Dispatch is semantically related to availableDate.Computer according to the ontological relationships. In such a situation, the restricted attribute time.Assemble of ComputerSales-I is a restricted attribute, b ecause the values assigned to it are restricted by date.Dispatch approvalDate.Insurance date.Pickup. Candidate services need to b e indexed based on the values assigned to such attributes b ecause of two reasons. 1. The prop osed approach first determines the values that conform to a given constraint. Then, it combines services that assign those values to their restricted attributes to form comp osite services. Such an approach requires the list of values assigned to each restricted attribute by the candidate services. These lists can b e easily obtained by indexing services based on the assigned values. Let us assume we have the services describ ed in Table 1. If these services are indexed in the way shown in Figure 5, then the lists of values assigned to the restricted attributes can b e easily obtained. We assume that the values assigned to the attributes avail1 Sales(Computer), Insure(Computer) and Ship(Computer) are the abbreviated forms of [Sales(), Computer, Sales Assistant], [Insure(), Computer, Sales Representative] and [Ship(), Computer, Shipping Agent] resp ectively. 4. THE MATCHING APPROACH This section provides details of the prop osed comp osite matching technique. This technique requires: (i) WSALU E [6] service descriptions, (ii) user requests structured according to the guidelines given in Section 3, and (iii) the terms in descriptions (service descriptions and user requests) to b e defined in a meta-ontology [2]. It locates services that conform to indep endent global constraints. Let gc b e a constraint that restricts the attributes [a1 , . . . , an ] of services of typ es [S1 , . . . , Sm ]. A service tuple [s1 , . . . , sm ] is a comp osite service that conforms to gc if: 1. si , si is of typ e Si , 2. si , si is describ ed using an attribute a , where i a {a1 , . . . , an }, and i 3. [v1 , . . . , vn ] assigned to [a1 , . . . , a ] of [sx , . . . , sy ] n conform to g c. [a , . . . , a ] of [s1 , . . . , sy ] are referred to as restricted 1 n attributes. The prop osed approach consists of three phases: (1) candidate acquisition, (2) service indexing and (3) comp osite service acquisition. The first phase locates services of the different typ es in a comp osite service template. The second phase identifies restricted attributes of services and indexes them based on the assigned values. The final phase retrieves the values that conform to a given constraint and combines services that assign those values to their restricted attributes (to form conforming comp osite services). 768 WWW 2008 / Refereed Track: Web Engineering - Web Service Composition ableDate.Computer, approvalDate.Insurance and date.Pickup are sp ecified in date format and that the required ontological descriptions are available. Table 1: Sample services Typ e Assigned Values ComputerSales-I Sales(Computer) 183-2007, 185-2007 Service ComputerSales-I I Insurance-I Insurance-I I Shipping-I Shipping-I I Sales(Computer) Insure(Computer) Insure(Computer) Shipping(Computer) Shipping(Computer) availableDate. Computer 3RD_JULY 5TH_JULY 4TH_JULY ComputerSales-I ComputerSales-I ComputerSales-II approvalDate. Insurance Insurance-I Insurance-II Insurance-I Insurance-II Shipping-I Shipping-II Beijing, China b e assigned to a particular attribute and the numb er of attributes semantically related to a particular attribute are b ounded. Slot Lists L1 L2 L3 l 11 Slots L4 l41 4TH JULY 3RD JULY, 4TH JULY 1ST JULY, 5TH JULY 4TH JULY 2ND JULY, 3RD JULY l21 l31 l12 l13 l14 l15 sx sy sz sa Services date.Pickup sp sq Shipping-I Figure 6: Set of Slot Lists (3) Composite Service Acquisition The task p erformed in this phase is divided into two steps. First, values that conform to a given indep endent global constraint are identified. Then, services that assign these conforming values are combined to form comp osite services. The prop osed approach models an indep endent global constraint as a directed acyclic graph G=(V, E), where V is a set of nodes and E is a set of arcs. The nodes of such a graph represent the attributes and the arcs model the relationships b etween the attributes. Each arc and the two connected attributes model a binary attribute comparison of a constraint. Figure 7 depicts a graph modeling a constraint that restricts a1 -a6 , where the binary attribute comparison are sp ecified with the op erators {o12 , o13 , o24 , o34 , o35 , o46 }. 1ST_JULY 2ND_JULY Figure 5: Indexed Services 2. When combining services to form comp osite services, those that assign a particular value to a restricted attribute can b e retrieved quickly. Let us assume that tuple [3RD JULY, 3RD JULY, 4TH JULY] of conforming values is given for the ab ove scenario. In such a situation if the available services are not indexed, 10 op erations (3+4+3) may have to b e p erformed to locate those services that assign these values to their restricted attributes. However, it would only take 3 op erations if the services are indexed (see Figure 5). The prop osed approach generates a set of Slot Lists to index candidate services based on the values they assign to restricted attributes. Figure 6 provides a global view of this data structure. It depicts a set of Slot Lists {L1 , L2 , L3 , L4 } generated for a global constraint that restricts the attributes [a1 , a2 , a3 , a4 ]. Note that a Slot List Li is generated for every attribute ai . A slot lij is included in a list Li for each value vij that can b e assigned to attribute ai . Each slot contains a set of services. A service sk is included in a slot lij if it is able to assign the value vij to ai . That means, the service description of sk is sp ecified using either · ai : vij is assigned to ai , or · an attribute a to which a value v j is assigned: a is i i i semantically related to ai and the relationship causes vij to b e mapp ed to vij . For example, in Shipping-I in Table 1 the restricted attribute is date.Dispatch and the assigned values are not sp ecified in "date-month" format. However, since the ontological relationships semantically relate date.Dispatch to availableDate.Computer, and map the assigned values to 3RD JULY and 5TH JULY, Shipping-I is placed in the slots that corresp ond to availableDate.Computer, 3RD JULY and availableDate.Computer, 5TH JULY . When generating a set of Slot Lists it is assumed that the domain of values that can o12 a1 a2 o 24 o13 a3 o34 o35 a4 o46 a6 a5 Figure 7: Directed Acyclic Graph modeling an Independent Global Constraint Values that conform to a constraint are identified by generating instances of such graphs. A tuple of values assigned to the nodes of a graph is an instance. For example, the values [v1 , v2 , v3 , v4 , v5 , v6 ], where each value vi is assigned to an attribute ai , forms an instance of the graph depicted in Figure 7. Such an instance conforms to a given constraint if each of its values conform to the binary attribute comparisons represented by the arcs. A value that conforms to the binary attribute comparisons is referred to as an Arc Consistent Value. Definition 2 (Arc Consistent Value). Let gc be an independent global constraint that restricts the values assigned to attributes {a1 , . . . , an }, where ai is a non-free attribute and ai {a1 , . . . , an }. {aj , . . . , ak } is the set of attributes connected to ai with arcs {oij , . . . , oik }, where {aj , . . . , ak }{a1 , . . . , an }. [vj , . . . , vk ] is a tuple of values 769 WWW 2008 / Refereed Track: Web Engineering - Web Service Composition assigned to {aj , . . . , ak }. A value vi assigned to ai is arc consistent, if the relationships represented by the arcs {oij , . . . , oik } exist between vi and the values in {vj , . . . , vk }. An instance of a graph that consists of arc consistent values is a tuple of conforming values. Such tuples are referred to as Arc Consistent Instances. Definition 3 (Arc Consistent Instance). Let gc be an independent global constraint that restricts the values assigned to attributes {a1 , . . . , an }, where ai is a non-free attribute and ai {a1 , . . . , an }. A tuple of values [v1 , . . . , vn ] assigned to {aj , . . . , ak } is an arc consistent instance if each value vj in {aj , . . . , ak } is local ly arc consistent. Identifying an arc consistent instance is NP-Hard. If a given relational constraint restricts n attributes and m arc consistent values can b e assigned to each attribute, then mn combinations of values may have to b e considered to identify an arc consistent instance. The prop osed technique defines two separate approaches to p erform this task. The first approach uses a basic greedy algorithm (backtrack-free search algorithm [3]) to identify arc consistent instances. The second approach derives them using domain rules [2]. The reason for prop osing two separate approaches will b e given later. We will refer to the first one as the optimised approach, and the second as the derivation-based approach. Constraint availableDate. Computer Beijing, China approvalDate. Insurance date.Pickup 3RD_JULY 3RD_JULY 3RD_JULY 5TH_JULY 5TH_JULY 4TH_JULY Assigned Values 4TH_JULY 4TH_JULY 2ND_JULY 1ST_JULY Figure 8: Value Selection The algorithm for the optimised approach is given in Algorithm 1. This requires a set of Slot Lists and an indep endent global constraint. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 locateServices(SL[][], gc) removeEmptySlots(SL); {c0 .a0 , . . . , cn .an } r estr ictedAttr ibutes(gc); {atcp , . . . , atcq } attr ibuteC ompar isons(gc) ; for (1) The Optimised Approach This approach employs a greedy algorithm to locate arc consistent instances in p olynomial time. It attempts to generate an arc consistent instance for each value that is assigned to the free attribute. When generating these instances, first, a value assigned to the free attribute is selected. Then, based on that value, arc consistent values are selected for the remaining attributes. If such a value cannot b e located for a particular attribute, then the technique moves to the next value that is assigned to the free attribute. It does not p erform any backtrack to consider alternative (arc consistent) values for attributes. Figure 8 shows the way in which values are selected by this approach when services are indexed as in Figure 5. A solid line indicates an arc consistent instance, whereas a dashed line indicates that the assignments have led to a dead-end (i.e. an arc consistent instance is not located for the corresp onding value that is assigned to free attribute). When 3RD JULY is selected for availableDate.Computer, the arc consistent instance [3RD JULY, 3RD JULY, 3RD JULY] is located. However, when 5TH JULY is considered, an arc consistent value cannot b e located for date.Pickup. Once an instance is located, the services in the slots that corresp ond to the arc consistent values are combined. Let us consider a constraint gc that restricts the attributes a1 , . . . , an of services of typ es S1 , . . . , Sn . We also assume that a set of Slot Lists SL has b een generated for gc. A slot at a location ai , vi , which corresp onds to an attribute ai and a value vj , contains services of typ e Si which assign the value vj to attribute ai . Therefore, if [v1 , . . . , vn ] is an arc consistent instance, then the services at the slots a1 , v1 , . . . , an , vn would form conforming comp osite services. In the ab ove scenario, when [3RD JULY, 3RD JULY, 3RD JULY] is located, the services at the slots availableDate.Computer.3RD JULY , approvalDate.Insurance.3RD JULY and date.Pickup.3RD JULY are combined to form the conforming comp osite service [ComputerSale-I, Insurance-I, Shipping-I]. i0; i1, n-1 duplicate entries would b e retrieved by these techniques. A Java-based implementation of SHOP. 772 WWW 2008 / Refereed Track: Web Engineering - Web Service Composition a limited numb er of values. Hence, the exhaustive approach retrieved more services than the prop osed approach. The numb er of services retrieved by all the techniques decreased, as the numb er of service typ es increased. The values assigned to the restricted attributes of candidate services had to conform to an increasing numb er of binary attribute comparisons. The derivation-based approach did not retrieve many services b ecause the rules required to approximate a given constraint were not available. The used random process did not generate the required rules. 600 Beijing, China Composite Services 513.91 400 316.68 Syntactic Optimised Derivation in p olynomial time and only combined services that assign those values. The p erformance of the syntactic approach was 32% b etter in the exp eriments that increased the numb er of service typ es in a comp osite service template. Since the optimised approach is semantic-based it retrieved more candidate services than the syntactic approach. The time taken by the devised approach to index services in the Slot Lists increased at a rapid rate with an incrementing numb er of service typ es. The exhaustive approach was the least efficient in the restricted environment. In the two worst cases (with 100 available services and 10 service typ es) it took around 9 minutes 35 seconds, and and 46 minutes and 25 seconds resp ectively, whereas the prop osed approach only took 1.16 seconds and 1.47 seconds. 10000 3424.12 200 90.75 34.5 0.7 1.9 2.2 183.4 0 Time(Seconds) 0 0 0.34 8 2.54 14.04 1000 203.92 1872.26 236.65 160.12 222.14 133.77 89.9 312.47 400 800 1200 1600 2000 Web Services 100 58.77 48.85 (a) Normal Environment 60 53.36 40.68 Syntactic Optimised Derivation 10 Composite Services 40 22.32 Syntactic Optimised Exhaustive 1 400 800 1200 1600 2000 Web Services 20 7.84 0.08 2.6 0 0.6 3.2 9.74 0 1.54 4.5 0 2.02 10.4 0 13.48 2.64 0 Derivation 1000 (a) Normal Environment 0 20 40 60 80 100 574.58 Web Services Time(Seconds) 100 86.94 143.55 (b) Restricted Environment 10 18.13 3.83 1.16 0.53 0.32 0.12 Figure 10: Recall - Varying no. of Available Services 400 2.62 2.85 0.9 1 1.72 0.79 0.49 Syntactic Optimised Derivation Exhaustive Composite Services 334 0 0.1 300 Syntactic 200 119.32 0 20 40 60 80 100 Optimised 81.8 24.9 1.98 0.5 1.02 0.56 0.48 0 0.04 0 0 2.3 0 Derivation Web Services 100 0 (b) Restricted Environment 5 10 15 20 25 Service Types Figure 12: Time taken - Varying no. of Available Services (a) Normal Environment 200 7. RELATED WORK 160.54 105.16 Composite Services 150 100 50 0 2 4 6 8 10 80.46 54.8 22.43 12.2 0 37 25.35 1.7 11.2 0 0.38 0 0.08 1.9 0 0.02 0.2 0 Syntactic Optimised Exhaustive Derivation Service Types (b) Restricted Environment Figure 11: Recall - Varying no. of Service Types The p erformance of the optimised technique was 76% b etter than that of the syntactic approach in the exp eriments varied the numb er of available services. The syntactic approach used JSHOP, which p erforms a combinatorial depthfirst search to locate conforming comp osite services. On the other hand, the prop osed local optimisation-based approach determined the values that conform to a given constraint Semantic-based approaches retrieving comp osite services were introduced in [1, 4, 8]. However, the technique in [4] is an approximate approach which does not consider the values assigned to the attributes. None of the remaining techniques neither consider global constraints nor locate comp osite services that conform to such constraints. Wu et al. in [11] and Sirin et al. in [9] considered b oth local and global constraints. Their approaches require service descriptions and user requests to b e sp ecified with OWLS. SHOP-2 (Simple Hierarchical Planner-2) is used to locate an orchestration of services that form a conforming comp osite service. First, a "SHOP method" is generated according to the OWL-S process in a request. Then, the request and available service descriptions are converted to op erator instances. Both approaches directly used the unification functions of SHOP-2 to match domain instances to op erators. Therefore basic string matching functions were used to match user requests to service descriptions. The 773 WWW 2008 / Refereed Track: Web Engineering - Web Service Composition approach in [9] extends [11] by incorp orating a Description Logic reasoner. However, this is only used to check whether the pre-conditions of a given op erator (in the hierarchy) are entailed by the state of the planner. Therefore, the approach in [9] locates conforming comp osite services when a constraint in a request is sp ecified with attributes that have different scop es, but not when requests and service descriptions are syntactically heterogeneous. 10000 Beijing, China structure (a set of Slot Lists) to improve the p erformance of these approaches. Exp erimental results showed that the prop osed optimised (initial) approach p erforms b etter than any existing technique. It also achieves higher recall than a syntactic-based approach.s As future work, we intend to develop a comp osite matching technique that considers multiple user constraints of various typ es. Acknowledgments We would like to thank the ARC (Australian Research Council) for the supp ort given towards this work, under the Linkage Pro ject no. LP0667600 titled "An Integrated Infrastructure for Dynamic and Large Scale Supply Chain". 1000 949 658.23 Time(Seconds) 131.37 152.9 134.72 100 81.22 68.58 17.67 87.22 85.31 31.72 109.36 Syntactic Optimised Derivation 9. REFERENCES [1] R. Akkira ju, B. Srivastava, A. Ivan, R. Goodwin, and T. Syeda-Mahmood. SEMAPLAN: Combining Planning with Semantic Matching to Achieve Web Service Comp osition. In Proceedings of the International Conference on Web Services, pages 37­44, 2006. [2] I. Elgedawy, Z. Tari, and M. Winikoff. Exact Functional Context Matching for Web Services. In Proceedings of the 2nd International Conference on Service Oriented Computing, pages 143­152, 2004. [3] E. Freuder. A Sufficient Condition for Backtrack-Free Search. Journal of ACM, 29(1):24­32, 1982. [4] N. Gooneratne, Z. Tari, and G. Craske. Comp osite Matching Technique for Semantic-based Service Discovery. In Proceedings of the Australian Undergraduate Conference, 2004. [5] N. Gooneratne, Z. Tari, and J. Harland. Matching Strictly Dep endent Global Constraints for Comp osite Web Services. In Proceedings of the European Conference on Web Services, pages 139­148, 2007. [6] N. Gooneratne, Z. Tari, and J. Harland. Verification of Web Service Descriptions using Graph-based Traversal Algorithms. In Proceedings of the ACM Symposium on Applied Computing, pages 1385­1392, 2007. [7] B. Medjahed and A. Bouguettaya. A Multilevel Comp osability Model for Semantic Web Services. Transactions Know ledge and Data Engineering, 17(7):954­968, 2005. [8] M. Paolucci, K. P. Sycara, and T. Kawamura. Delivering Semantic Web Services. In Proceedings of the International World Wide Web Conference, 2003. [9] E. Sirin and B. Parsia. Planning for Semantic Web Services. In Proceedings of International Semantic Web Conference, Workshop on Semantic Web Services, Novemb er 2004. [10] K. P. Sycara, S. Widoff, M. Klusch, and J. Lu. Larks: Dynamic Matchmaking Among Heterogeneous Software Agents in Cyb erspace. Autonomous Agents and Multi-Agent Systems, 5(2):173­203, 2002. [11] D. Wu, B. Parsia, E. Sirin, J. Hendler, and D. Nau. Automating DAML-S Web Services Comp osition using SHOP2. In Proceedings of the International Semantic Web Conference, pages 195­210, 2003. [12] L. Zeng, B. Benatallah, A. Ngu, M. Dumas, J. Kalagnanam, and H. Chang. QoS-Aware Middleware for Web services Comp osition. Trans. on Software Engineering, 30(5):311­327, 2004. 10 1 5 10 15 20 25 Service Types (a) Normal Environment 10000 2785.11 1000 1686.77 897.01 Time(Seconds) 100 49.95 10 1.37 1.79 1.09 1.98 1.2 0.25 0.09 0.12 2.4 1.47 0.35 1 0.88 0 0 2 Syntactic Optimised Derivation Exhaustive 4 6 8 10 Service Types (b) Restricted Environment Figure 13: Time taken - Varying no. Types of Service Zeng et al. [12] introduced an approach requiring a request (for a comp osite service) to b e sp ecified with a state chart diagram, where each state models a service typ e. Services were describ ed with a quality of service model that consists of attributes such as execution price, execution duration, reliability, availability, and reputation. Both local and global constraints were considered in their approach. However, these constraints were limited to those that can b e sp ecified with an attribute of the quality of service model. A syntactic-based integer programming technique that focuses on local optimisation is used to match the user requests to the service descriptions. 8. CONCLUSION This work prop oses two service discovery approaches that locate services that conform to indep endent global constraints. The first approach uses a greedy algorithm to identify conforming values and locate comp osite services. However, since this approach is not sound, a second approach that approximates a given constraint is prop osed. This approach uses domain rules to derive values that conform to a given constraint and combines services that assign those values to their restricted attributes. The domain rules used to derive the conforming values are returned with each service so that context in which it is located can b e understood by a user. Services are indexed in a two dimensional data 774