Zeina Azmeh
email: zeina.azmeh@lirmm.fr

Marianne Huchard
email: marianne.huchard@lirmm.fr

Chouki Tibermacine
email: chouki.tibermacine@lirmm.fr

Christelle Urtado
email: christelle.urtado@ema.fr

Sylvain Vauttier
email: sylvain.vauttier@ema.fr

WSPAB: A Tool for Automatic Classification & Selection of Web Services Using Formal Concept Analysis

The increased popularity of web services is accompanied with an increase in both provider and service number. This fairly large service number causes a deficiency in the selection of the most pertinent service, and makes it an effortful and time-consuming task. We propose the WSPAB (Web Service Personal Address Book) tool that aims at defining a complete solution for facilitating the task of finding the most pertinent web service. This includes two sub tasks, discovering and selecting. In this paper, we present the first part of the tool concerning the automation of the selection process, taking into consideration the quality of service (QoS) and user preferences. The WSPAB accomplishes the automatic selection of a service by filtering web services according to certain aspects of QoS and certain user requirements; then classifying these services using the formal concept analysis (FCA) approach, enabling users to easily select their needed service, identify its potential substitutes and keep trace of them either for future use, or to be shared with others.

Introduction

Web services are a key concept of service-oriented architecture (SOA). They provide various functionalities that can be accessed via the network. In the vision of SOA, the development of software systems can be performed by rapid, low-cost and easy composition of web services. SOA is defined as "a paradigm for organizing and utilizing distributed capabilities that may be under the control of dif-ferent ownership domains" [START_REF] Papazoglou | Web Services: Principles and Technology[END_REF]. It is built on the basis of three primary roles: service provider, service registry, and service requestor 1 . These primary roles define three primary operations: publishing, finding, and invoking (see figure 1). A provider publishes his services to a registry; a requestor finds a service published on a registry and binds to its provider to invoke it [START_REF] Josuttis | SOA In Practice, The Art of Distributed System Design[END_REF]. Finding the right web service to invoke includes: discovering a set of one or more potential web services, and selecting the most pertinent one to be invoked. The discovery is accomplished by contacting a service registry, and searching for a service that meets search criteria. This may return a set of matching web services. From this returned set, a service that best matches the expected requirements will be chosen.

Figure 1. SOA primary roles and operations

The finding operation described above may become challenging because of certain issues like:

• The absence of a unified public registry, thus the possible unawareness of some available registries, which makes the discovery somewhat, difficult to accomplish

• The possible large number of services in a returned result set makes the selection of the most pertinent service a hard, effortful and time-consuming task.

In this paper, we handle the problem of achieving the automatic selection of potentially pertinent web services out of a fairly large set of services, taking into consideration some quality of service (QoS) aspects with the validation of user preferences. The term quality of service indicates a service's functional and nonfunctional attributes, thus service's usability and utility. There are so many aspects regarding the quality of service such as service's availability, validity, accessibility, integrity, performance, reliability, etc. [START_REF] Mani | Understanding quality of service for web services, improving the performance of your web services -IBM[END_REF]. In this paper, we tried to address a few aspects like availability and validity, in addition to other aspects that reflect user preferences like service providers, free or paid services, number of operations, specific signatures, etc.

The potentially pertinent services are to be classified, in a certain way using a certain method of classification, in order to enable the user of choosing a service and identifying its potential substitutes clearly and easily.

Having a large set of web services may enable a better selection of a service, but will make manual selection more difficult, as mentioned previously. Thus, automatic selection would economize effort and time, and would give more opportunities of a better selection, especially when considering aspects of QoS and user preferences. Furthermore, providing the user with a few number of pertinent web services classified in a way that shows potential services with their potential substitutes will give the user a clearer organized view and thus will enable him to do a better selection.

The rest of the paper is organized as follows: A motivating example is demonstrated in Section 2. In Section 3, we are giving a quick definition of the adopted classification method. The WSPAB tool is described in Section 4 with the demonstration of its processing steps using a real web services example, and interpreting the resulting classification. In Section 5, we present the related work. In Section 6, we summarize our contributions and give our conclusion and perspectives.

A Motivating Example

Along our research, we carried out our experiments on real web services. We obtained these services throughout Seekda.com, which is a global web service search engine based on focused crawling, allowing access to publicly available web services [START_REF] Lausen | Finding web services[END_REF]. It indexes and monitors 27K public web services from over 6K providers [START_REF] Seekda | a web services search engine[END_REF]. In order to understand more the problem of manual selection of web services, we are going to demonstrate an example of a web service that performs currency conversion. We will first obtain a set of web services, by querying seekda.com using the keywords "currency + converter". This returns a result set of 75 web services 2 .

We observed that in order to select a certain service, users follow certain criteria during their search. These criteria are on two levels: functional and nonfunctional (reflects the QoS concept). Functional means that a service provides (a) certain operation(s) that meet(s) the required functionality, and nonfunctional means that a service has certain attributes like availability, performance, free or paid, from specific providers, etc. To verify the functional level, a user must verify each service interface described by WSDL, in order to discover what a service offers.

WSDL, the Web Service Description Language is the standard for defining web service interfaces. It describes two different aspects of a service: its signature (name, operations with their parameters), and its binding and deployment details (protocol and location) [START_REF] Papazoglou | Web Services: Principles and Technology[END_REF]. By analyzing the WSDL file, a user can verify the existence of a required operation, thus, can determine the service pertinency. After this, a user checks the nonfunctional aspects (QoS) of a service, whether it is available or not, its response time, etc. And also attributes like free services, provided by specific providers, etc. For a fairly large set of web services, this manual QoS filtration and selection tasks requires time and effort. The WSPAB automates these tasks, and offers the user a reduced set of services that meet the required functionality and validate a certain level of QoS. Later on, we will demonstrate the same example, but automated using the WSPAB tool.

The Adopted Classification Method

As a classification method, we adopt Formal Concept Analysis [START_REF] Ganter | Formal Concept Analysis: Mathematical Foundations[END_REF], a mathematical framework which has already been successfully applied to variants of the practical problem of similarity discovery and abstraction emergence in a wide range of domains including software engineering [START_REF] Tilley | A survey of formal concept analysis support for software engineering activities[END_REF], machine learning [START_REF] Liquiere | Structural machine learning with galois lattice and graphs[END_REF], data mining [START_REF] Stumme | Efficient data mining based on formal concept analysis[END_REF] or linguistics [START_REF] Priss | Linguistic applications of formal concept analysis[END_REF].

The classification we build is based on the partially ordered structure known as Galois lattice or concept lattice [START_REF] Wille | Restructuring lattice theory: an approach based on hierarchies of concepts[END_REF] which is induced by a context K, composed of a binary relation R over a pair of sets O (objects) and A (attributes) (Figure . 2). A formal concept C is a pair of corresponding sets (E, I) such that:

E = { e ∈ O| ∀ i ∈ I, (e, i) ∈ R} is called extent (covered objects), I = { i ∈ A| ∀ e ∈ E, (e, i) ∈ R} is called intent (shared features).
For example, ({1, 2}, {b, c}) is a formal concept because objects 1 and 2 exactly share attributes b and c (and viceversa). On the opposite, ({2}, {b, c}) is not a formal concept.

Furthermore, the set of all formal concepts C constitutes a lattice L when provided with the following specialization order based on intent / extent inclusion:

(E 1 , I 1 ) ≤ L (E 2 , I 2 ) ⇔ E 1 ⊆ E 2 (or equivalently I 2 ⊆ I 1 ).
Figure 3 shows the Hasse diagram of ≤ L . We are using the formal concept analysis method, in order to classify web services. We accomplish this classification by defining a binary relation between services and operation signatures. Thus, the objects set represents the services set, and the attributes set represents the operation signatures set. Later on, we can find further details about this classification, with an illustrating example.

a b c d e f g h 1 × × × × 2 × × × × × 3 × × × × × 4 × × 5 × × 6 × ×

The Web Service Personal Address Book

General Overview

The Web Service Personal Address Book is a tool that aims at providing an environment for a simplified dealing with web services. It consists of two parts: discovery and selection. The discovery part means that users can search, select, organize and share their web services. They will form a community of web service users, in which they can work with each other towards building a collaborative address book of proper recommended web services. And the selection part means that web services are well filtered and classified, to enable users of performing an easy proper selection of the most pertinent service, which meets their needs and validates certain aspects of QoS, and having the ability of finding the potential service substitute, in case of a service failure or discontinuity.

WSPAB-Related Terminology

The WSPAB uses certain concepts during its processing steps. These concepts are defined as follows:

• The filtration criterion is a collection of nonfunctional quality attributes: mandatory and optional.

Mandatory attributes indicate the service usability. They include attributes as availability, validity and performance of a service. Optional attributes present user preferences. They include attributes as free or paid services, the maximum number of service operations, documented or undocumented services, from certain providers, etc.

• A pertinent service is a service that validates the filtration criterion, thus, validates both mandatory and optional nonfunctional quality attributes and provides the needed functionality.

• A service substitute is a service that specializes another service, in other words, it offers an extended functionality and can replace the other service. It will be explained further on when interpreting the lattice that results from the formal concept analysis approach.

WSPAB in Action

In figure 4, we can see an overview of the WSPAB in action. We can divide the execution into the following successive steps:

• Analysis of web services set In the first step, the set of web services is analyzed so to extract the URIs (endpoints) of web services. These URIs are stored in a new set, and are passed to the second step, the filtration of web services. In this step, all of the web services specified by their URIs are filtered according to the filtration criterion. The filtration criterion, as indicated before, contains two kinds of nonfunctional quality attributes; mandatory and optional. Each web service is tested against these attributes, so that, services which do not validate them are discarded. The filtration checks the mandatory attributes first, then if validated, it checks the optional attributes. The filtration step also generates a set of web service URIs, but a reduced set that contains only services that are assured to be pure (validate the filtration criterion). In the step of operation signatures extraction, the service URIs listed in the last produced set are used to obtain the service descriptions represented as WSDL files. Each WSDL file is parsed, and operation signatures are extracted. An operation signature is the combination of the operation name, its input parameters, and its output. A new set is generated from this step. It contains for each service its URI, its name and its operation signatures. This set is used in the following step, the pertinent service identification step. In this step, a comparison is carried out between the service signatures and a user given signature of a potential pertinent operation. For now, we will be comparing the signatures according to the number of input parameters. But with the intention of making the comparisons more precise and accurate later on. After the comparison of the signatures with the user's provided signature, we obtain a reduced set of best matching web services. In the next step, the signatures are sorted according to the number of input parameters in each operation. This gives us groups of operation signatures, and for each group, a new signature will be generated to represent the group. These newly generated signatures are then passed to the final step, the lattice construction step, and are used to build the binary table of the FCA, to define the binary relation between the signatures and the services. Then finally, out of this table, the service lattice is constructed with the help of a tool for formal concept analysis, called Galicia (Galois Lattice Interactive Constructor) [START_REF] Valtchev | GALICIA: an open platform for lattices[END_REF] [START_REF]Galois lattice interactive constructor[END_REF]. The Galicia tool offers many lattice construction algorithms. It analyzes the binary relation between the services and the operations, construct the corresponding lattice and returns a graphical layout of the constructed lattice, showing the resulting concepts with the relations between them.

• Filtration of web services

In the following Section, the WSPAB processing steps are explained using the example of the currency conversion web service, which was presented previously.

Example: Currency Converter

In Section 2, we demonstrated an example of the manual selection of a currency conversion web service. Next, we will use the same example to show the automatic selection of the WSPAB tool. We are assuming a user with the following filtration criterion:

• Mandatory nonfunctional attributes: available and valid

• Optional nonfunctional attributes: free, with no more than 6 operations

And with a required functionality represented by the signatures convert(with three input parameters: fromCurrency, toCurrency, amount) or convert(with two input parameters: fromCurrency, toCurrency).

We will demonstrate the automated classification and selection step by step as follows:

The result set returned by Seekda.com is distributed on many HTML pages. Thus, the analysis step in this case represents an HTML parser. Each HTML page is parsed, and web services endpoints (URIs) are extracted and saved to a new set. This set (in our example) contains 75 URIs, and is passed to the filtration step. In this step, each URI from the set is checked, so to determine the validity of mandatory nonfunctional attributes then the validity of optional nonfunctional attributes.

These nonfunctional attributes as already specified above are: available, valid, free services with maximum 6 operations. They are checked as follows:

• The "availability" attribute is verified by checking whether the endpoint URI exists or not.

• The "validity" attribute is verified at the WSDL parsing level (signature extraction step), in which the WSDL structure is verified to be valid or not.

• The "free" attribute is verified by two checks, provider name checking and certain keywords checking. The provider name is checked against a modifiable predefined list of provider names who provide only paid services. The keywords checking is done at the WSDL parsing level (signature extraction step), by checking the existence of certain keywords like: license, password, userId, etc. These keywords are also listed in a predefined modifiable list.

• The number of operations will be checked in the signature extraction step.

• Seekda returned result set may contain some repeated services (i.e. services provided by the same provider and offering exactly the same operations). These services are checked and eliminated in the filtration step and also in the signature extraction step.

In the next step, the signature extraction step, services that are invalid, paid, repeated, or having an operation number higher than the user specified number (which is 6 operations) are discarded. This is done by parsing every service WSDL, in order to extract the service signatures. This step generates a new reduced set that contains for each service: its URI, its name, and its operations signatures (operation name with input and output parameter types). These services signatures are used in the identification of pertinent services, in which, a comparison is carried out between a user's given signature of a required operation and each operation signature of a service. Services with matching operation signatures are stored in a final set, others are discarded. This final set is illustrated in figure 5, it contains only 5 services3 .

Figure 5. List of pertinent web services

In the final step, the operation signatures of all services are sorted according to the number of parameters, and are assembled under a unified signature of the form: op (types of input parameters)→type of output parameter, as shown in figure 6.

These unified signatures are then used in the FCA binary table with the final obtained set of services as shown in table 2, in order to build the service lattice using the Galicia tool. The resulting lattice is shown in figure 7. The interpretation of the lattice is given in the following Section.

In table 1, we can find a summary of the outputs after each processing step, describing the resulting set with the obtained number of services.

Service Lattice Interpretation & Use

The service lattice in figure 7 reflects the relation between services and signatures in table 2. It is built by the Galicia tool as mentioned previously. It contains information that can be interpreted using a set of rules that are common in all concept lattices. These rules are:

• The concepts are represented using the intent (I), extent (E), reduced I, and reduced E sets. The reduced sets are deduced from the complete sets as follows:

-A service that appears in the reduced E of a concept is inherited by all the concepts that are above it, and disappears from their reduced E. -A signature that appears in the reduced I of a concept is inherited by all the concepts that are below, and disappears from their reduced I.

• When the reduced E is not empty, the concept represents exactly the service(s) that is/are in reduced E with its/their signatures in the I set.

• When the reduced E is empty, this signifies that the concept represents a new service specification (an abstract service) that does not exist in the services set.

From these rules, we can obtain the following information from our service lattice: • Service3 can substitute Service1 and Service4, because it is a specialization of these services. This means that Service3 offers the same operation that Service1 and Service4 offer, which has the signature op2(string,string)→double, and also offers another operation that these two services do not offer, which has the signature op0()→string.

•
• Service5 is a substitute of Service2, because it is a specialization of it, for similar reasons.

• The top of our lattice (node 1) does not present an interesting concept, because there are no common operations in all the services.

• The bottom of our lattice (node 7) does not present an interesting concept either, because none of the services group all the operations listed in I.

The specialization relations between the services are better shown in figure 8, in which we can clearly notice the possible substitute of each service, and the abstract service deduced from the lattice.

In our approach, we group the operations depending on the input parameter number of each operation, i.e. we consider that the similarity factor between the operations is the number of input parameters. Then we generate signatures that represent these groups of operations, and we use them to classify the services.

In our example above, in the case of Service5 and Service2, we can observe the following: Service2 offers the operation: getCurrecySign(string)→string. This operation takes as an input a string representing a country This operation takes as an input a string representing a currency sign, and returns as an output the currency rate between the input currency sign and the US dollar. We grouped both of these two operations under the same signature, op1(string)→double, while they provide completely different functionalities. And we have also deduced that Service5 is a substitute of Service2, depending on the resulting lattice. While in fact, Service5 cannot provide the getCurrcySign(string)→string that Service2 offers. This limitation is to be met in a further work, by using other similarity measures, such as using a thesaurus to calculate the similarity between operation names, and similarities between parameter names together with their types. Defining an accurate similarity measure will lead us towards optimized results, together with the service lattice structure, which gives us a clear organized view of the pertinent services with their potential substitutes. This enable us of a better and easier selection of the needed service.

Related Work and Discussion

So far, most of the work on web services registries is focused on their architectural styles (centralized, federated, peer-to-peer) and the standardization of APIs to publish and to search for web services descriptions [START_REF] Dustdar | A view based analysis on web service registries[END_REF]. Registries usually provide simple data models with limited capabilities for structuring their contents. UDDI and WSDA registries for instance [START_REF]Discovery and Integration (UDDI)[END_REF][8] are designed essentially for the indexation and the discovery of web services. Their entries do not contain any detailed description of the web services but point to external descriptions (generally WSDL ) maintained by the web service providers. So, the web service classification provided by those registries consist in the use of keywords that enable to associate web services with business categories. On the contrary, ebXML registries [10] contain extensive descriptions of web services, stored thanks to a complex, extensible data model. This data model enables the definition of multiple classifications, such as business categories or packages of logically related web services. However, classification is handled manually by the web service providers, sending explicit classification information in their web service registration requests. This leads to poorly structured contents and erroneous web service retrievals. To address these issues, more recent work have studied more automatic classification schemes.

In the similarity search field, Dong et al. present a search engine called Woogle which is able to make similarity search between web services [START_REF] Dong | Similarity search for web services[END_REF]. This similarity search combines multiple techniques (similarity primitives) to compare web services and their operations. These primitives are applied to different levels of a web service description: input/output parameter names, operation description and web service description. The authors introduce some algorithms to cluster terms in these descriptions into concepts. They use then some information retrieval metrics (such as TF/IDF) to measure the similarity between concepts.

The work presented in the paper cited above is complementary to ours. The techniques presented are purely semantic while our work is purely syntactic (signature-based). The goal of similarity search is to find among all available service operations, which ones are semantically substitutable or composable (the output of one operation is similar to the input of another). The solution that we propose in this paper provides complementary functionalities. Indeed, while Dong's solution returns flat result sets, WSPAB provides, starting from these flat sets, reduced graphs (hierarchical structures) of concepts.

In [START_REF] Peng | Management and retrieval of web services based on formal concept analysis[END_REF], Peng et al. present a method to classify and retrieve web services in a repository using formal concept analysis. The authors propose to build a concept lattice starting from a context where objects are web services in a UDDI repository and attributes represent the operations in these services. In this approach, some optimizations are made in order to reduce the size of operation set used for building the lattice. Similarity search techniques are used to compare operation descriptions and input/output messages' data types, which are extracted from WSDL files. Similar operations are merged and only one operation among these ones is put in the context table. References to the other similar (merged) operations are stored in an external data structure to easily find them during web service retrieval. The authors propose an algorithm for retrieving web services. This algorithm parses the lattice in breadth-first manner from top to bottom to find the concepts (services/operations) that match queries defined by users. These queries are first abstracted as formal sequence of operations to be handled then by this algorithm.

The approach presented in this paper resembles our approach; there are however some differences. First, in our approach the lattice is built starting from the (filtered) result set returned by a web service search engine. In the paper cited above, the lattice is defined for a whole repository of web services. We are convinced that, even with size optimization of operation sets, building a concept lattice for large repositories is a time-consuming task. The obtained lattices are very large and their parsing slows greatly service retrieval. Their experiments have been performed on medium-size repositories (about 2000 web services). In our approach, experiments have been conducted on large web service sources with more than 25000 services. The concept lattice built for the whole services present in this web service source is very large and its parsing will be inevitably not very efficient.

Second, in our work we give a practical view of retrieving web services. Users of WSPAB can use their favorite search engine where they can make lookups of services by simple keywords. Optimization is made on the returned result set as explained in the previous sections. The classification using concept lattices is performed afterwards on a small list of web services. In Peng's work, there is no discussion on how users define their queries. They suppose that these queries can be abstracted as formal expressions representing a web service composed of a sequence of operations. These formal expressions are used in their tool to parse the lattice and retrieve the services that better match the query.

There exists in the literature some other works similar to Peng's one. In [START_REF] Lindig | Concept-based component retrieval[END_REF], FCA is used for component classification based on keywords. Besides the lattice construction, the author investigates incremental specification of queries for refining the search space. The proposal is applied to a large Unix system call documentation. In [START_REF] Aversano | Using concept lattices to support service selection[END_REF], three configurations of FCA are proposed for analyzing web services and facilitating their selection. In the first configuration a lattice is built on services described by keywords extracted from the documentation through a sophisticated process based on morphological analysis and word frequency metric. In the second configuration, a lattice emerges from the description of operations of a given service by their input and output parameters. In the third configuration, the lattice indicates how complex types (in signatures) are composed of simple types. Their case studies use downloads from UDDI registries. We propose a different FCA configuration, where the lattice is designed for operational purpose: services are described by their operations (including input/output parameters) and effective candidates for substitution can be found and adapted rapidly. The tool is conceived as a companion to search engines (where keyword-based search is proposed).

Conclusion & Perspectives

In this paper, we presented the WSPAB tool for the automatic classification and selection of web services from an online web service repository. This tool processes by multiple successive steps. It first analyzes the content of the service repository, querying it to find a first set of candidate services. Secondly, it filters this service set according to functional and nonfunctional criteria, considering user preferences. It then extracts the operation signatures of the services from the resulting set in order to further filter them according to this syntactic information. Finally, the set of remaining services is classified into a service lattice using Formal Concept Analysis. The obtained lattice can be used to identify both the service that best adapts to the user's needs and its possible substitutes when needed. WSPAB conforms to the Web 2.0 philosophy as organized and trusted web service address books enhances sharing and collaborations among web service user communities.

The main originality of our work lies in the fact that we use syntactic information on web services where most existing approaches use manually set quality criteria. This enables our solution to be fully automatic even if some of the information provided on each service indexed in the repository is incorrect or incomplete.

Perspectives for this work are numerous. We plan to refine the process proposed in this paper using a thesaurus to better identify matching services that do not have the exact searched name. We also intent to extend the proposed tool in order to deal with semantic web services. At last, we plan to work on web service discovery, as a preliminary phase of the process described in this paper, in order not to depend on some service repository.

Figure 2 .

 2 Figure 2. Binary relation of K = (O, A, R) where O = {1,2,3,4,5,6} and A = {a,b,c,d,e,f,g,h}.

Figure 3 .

 3 Figure 3. Formal concept lattice L.

Figure 4 .

 4 Figure 4. WSPAB in action

Figure 6 .

 6 Figure 6. The signature sorting step

  It has three concepts presented by the nodes 5, 2, 3 and are respectively: ({Service5, Service2}, {op1(string)→string double, op3(string,string,string double)→double}) ({Service5, Service3}, {op0()→string}) ,string)→double}) • Service4 and Service1 are equivalent because they are in the same reduced E set, and they do offer the same unique operation represented by the signature op2(string,string)→double

Figure 7 .Figure 8 .

 78 Figure 7. Galicia constructed service lattice

Table 1 . Summary of obtained service sets

 1

			In Set	Out Set
	Analysis Step		HTML pages	75 URIs
	Filtration & Signature	30 repeated, 20 un-	17 URIs, service
	Extraction Steps	available or invalid,	names, operation
			28 paid	signatures
	Pertinent	Services	17	5 URIs, service
	Identification Step		names, operation
				signatures

Table 2 . Binary Relation: Services × Signatures

 2

		op 0 ()→string op 1 (string)→string||double	op 2 (string,string)→double	op 3 (string, string, string||double)→double
	Service1			X
	CurrencyConverter
	Webservicex.com
	Service2		X		X
	CurConvert
	mobile88.com
	Service3	X		X
	CurrencyConverter
	petermeinl.de
	Service4			X
	CurrencyConvertor
	alraimedia.com
	Service5	X	X		X
	CurrencyRates
	houseofdev.com

Along the paper, we used the term user to refer to the service requestor role

The search result set is obtained on 12th of June 2008

Service2 has an operation called GetCurrecySign(string), there is an error (service provider error) in the operation name: 'Currecy' instead of 'Currency'


Zeina Azmeh
email: azmeh@lirmm.fr

Marianne Huchard
email: huchard@lirmm.fr

Chouki Tibermacine
email: tibermacin@lirmm.fr

Christelle Urtado
email: christelle.urtado@mines-ales.fr

Sylvain Vauttier
email: sylvain.vauttier@mines-ales.fr

Using Concept Lattices to Support Web Service Compositions with Backup Services

Keywords: Web service discovery, formal concept analysis, service backups

In SOA, composite applications can be developed on the basis of collections of interacting web services. A service's functionality is exposed to the external world by an abstract interface, described by the standard WSDL language, which must be published by service providers to public registries where service consumers can find them. Nowadays, web service discovery has become a real problem, because of the lack of public registries to publish and organize the fairly huge number of existing services. In this paper, we propose an approach based on formal concept analysis (FCA) for classifying and browsing web services. Using this approach, the web services are organized into a lattice structure, to facilitate their browse and selection. A service lattice reveals the invisible relations between the services, enabling the discovery of a needed service as well as the identification of its possible alternatives. Thus, service discovery may be achieved more easily using the service lattice. This facilitates the construction of service compositions and supports them with backup services to ensure a continuous functionality.

I. INTRODUCTION

Web services represent an important realization of serviceoriented architectures (SOA). In SOA, composite applications can be developed on the basis of collections of interacting services offering well-defined interfaces [START_REF] Papazoglou | Web Services: Principles and Technology[END_REF]. When a service is accessed and used through the internet and by open internet-based standards, it results in the concept of web services. A web service exposes its functionality to the external world by an abstract interface expressed by WSDL [23] (Web Service Description Language). A WSDL interface is a uniform mechanism for describing a service's available operations, parameters, data types, and access protocols.

According to the functionalities described in the WSDL interfaces, web services can be assembled to serve a particular function, solve a specific problem, or deliver a particular solution. They represent the building blocks for creating composite applications. When creating a composite application, each selected web service must fulfil a part of the application's functionality. Therefore, each service's WSDL interface must be analyzed to verify its provided operations, and so to decide whether to select the service or not. Due to the big number of web services that exist on the web nowadays, the task of finding an appropriate service to use becomes hard and time-consuming. After identifying the needed services, they can be assembled together in order to form the functionality of the aimed composite application. This application will be functional as long as each of its composing services is functional, but once one of its services breaks, the part of the application represented by this service will break too, causing a total or partial dysfunctionality to the application. The obvious solution in this case, will be to search for another web service to replace the broken one and recover the missing functionality. Thus, the task of finding an appropriate web service to use has to be repeated every time a service breaks and has to be replaced by an equivalent one.

In this paper, we propose an approach for web service classification and browsing, in order to facilitate the discovery of a web service, the identification and conservation of its candidate backups. This facilitates the construction of service compositions as well as ensuring their continuous functionality, by supporting them with backup services. We use the formal concept analysis formalism to organize web services into lattices according to their functionality domain and depending on the similarity estimated between their operations. The constructed web service lattices group the services into sets of services with similar operations and order these sets according to the number of similar operations they have and according to how similar these operations are. In this way the generated service lattices offer a browsing mechanism that facilitates the discovery of a needed service, along with a set of possible backup services.

The rest of the paper is organized as follows. Section II gives the problem statement with an example of composing web services. Section III gives an overview about formal concept analysis with the basic definitions. In Section IV, we present our approach based on FCA to classify web services. In Section V, we give a case study to explain the use of our approach. Section VI lists and discusses the existing approaches concerning web service classification and discovery. Finally, Section VII concludes the paper and gives some perspectives.

II. PROBLEM STATEMENT

Web services face several challenging issues coming from several factors. Since, they are offered by various providers, remotely accessed, and sometimes provided for free, there is no guarantee of a continuous execution. An available functioning web service may crash and become unavailable at any time, which necessitates finding an equivalent one to replace it. Unfortunately, this can be hard to achieve since there is a lack of WSDL organizing facilities, especially after the deficiency of the UDDI [24] registries: "UDDI did not achieve its goal of becoming the registry for all Web Services metadata and did not become useful in a majority of Web Services interactions over the Web" [START_REF] Newcomer | Understanding SOA with Web Services (Independent Technology Guides)[END_REF].

Thus, a mechanism for finding service backups becomes indispensable, especially when a service represents a part of a composite application.

Let's consider the following travel scenario: a traveller needs to reserve a plane ticket to a desired city. Supposing that this traveller lives in a small city that has no airport, then, he should also travel to the city where the airport is located, in order to take the plane he reserved. Thus, he must also reserve a train ticket, from his home city to the airport city, taking into consideration the flight exact time with the time needed to travel between the two cities. This scenario can be achieved by a travel composite service (TCS), in which 3 functionalities must be satisfied:

• reserve a flight from home city, or airport city, towards a desired city, • if a train reservation is needed (in case that the home city is not the airport city), then calculate the needed time (duration) to travel between the two cities by train, • reserve a train ticket, regarding the exact flight time and the calculated duration. The TCS can be realized by discovering services offering the described functionalities and composing them. It may look like the orchestration in Figure 1. In this orchestration, if the service TrainWS crashes, for example, an equivalent service offering at least the two used operations calcDuration() and resTrain() must be searched and discovered, in order to recover the missing functionality, and ensure the continuity of the composition.

In the following sections, we describe our FCA-based approach that facilitates the construction of such composition and illustrate how to support it with backup services.

III. FCA OVERVIEW

In our approach, we use the FCA formalism in order to construct a classification of web services. FCA is a mathematical theory that permits the identification of groups of objects having common attributes [START_REF] Ganter | Formal Concept Analysis -Mathematical Foundations[END_REF]. FCA takes as input a given data set represented as a formal context and produces the set of all the formal concepts which form a concept lattice. A formal context is denoted by K = (G, M, I) where G is a set of objects, M is a set of attributes, and I is a binary relation between G and M (I ⊆ G × M ). (g, m) ∈ I denotes the fact that object g ∈ G is in relation through I with attribute m ∈ M (also read as g has m). Having a set A ⊆ G,

A = {m ∈ M | ∀ g ∈ A : (g, m) ∈ I}
is the set of common attributes. In the same way, having the set of attributes B ⊆ M ,

B = {g ∈ G | ∀ m ∈ B : (g, m) ∈ I}
is the set of common objects.

In our example, ({o

1 , o 3 }) = {a, b, d} and ({c}) = {o 2 , o 3 }. a b c d e o 1 × × × o 2 × × × o 3 × × × × Table I A FORMAL CONTEXT FOR G × M
A concept is a pair of sets (A, B) where A ⊆ G is called the extent, B ⊆ M is called the intent, and B = (A) , A = (B) . Meaning that, a concept is a maximal collection of objects sharing similar attributes. The set of all concepts is denoted by B(G, M, I). In our example, ({o

1 , o 3 }, {a, b, d}) is a concept while ({c}, {o 2 , o 3 }) is not. In fact, while ({c}) = {o 2 , o 3 }, ({o 2 , o 3 }) = {b, c}. A concept (A1, B1) is a sub-concept of a concept (A2, B2) if A1 ⊆ A2
, which imposes a partial order relation on B(G, M, I) expressed as (A1, B1) ≤ (A2, B2). The partial order relation ≤ can be used to build a structure, which is called a concept lattice and is denoted by B(G, M, I). A concept lattice defines a hierarchical representation of objects and attributes, in which a certain concept inherits all the extents (objects) of its descendants and all the intents (attributes) of its ascendants. Figure 2 illustrates the lattice built for the context 1 shown in table I, we notice that upper labels are the reduced intent sets (attributes) and bottom labels are the reduced extent sets (objects). In this lattice we can reveal the relationships between the present objects, some of them are the following: IV. THE APPROACH Figure 3 gives a general overview of the main steps of our approach, during which two lattices are generated consecutively:

• a lattice for indexing the services by keywords extracted from their WSDLs, • a lattice for service classification, which organizes the services according to the similar operations they provide. As a start, WSDL files coming from various repositories are analysed and automatically tagged with the significant keywords [START_REF] Falleri | Automatic tag identification in web service descriptions[END_REF]. The extracted keywords are used to generate the first lattice, which represents an indexation of services by keywords. Supposing a set of random web services for travel facilities, the corresponding lattice may resemble the lattice in Figure 4. In lattices, some intermediate concepts (white nodes) can be removed without losing information, which makes the structure more scalable [START_REF] Ganter | Formal Concept Analysis -Mathematical Foundations[END_REF]. From this lattice, we can retrieve services in a certain domain by enquiring the lattice using keywords. Such a query returns a sub-lattice of services sharing the specified set of keywords, which are highly probable to provide similar functionalities. We extract these services, and apply a similarity measure on their operations, pair by pair. We will not consider the similarity between operations provided by the same service, because when a service becomes dysfunctional, all of its operations become dysfunctional too.

Several similarity measures for web services exist in the literature. They evaluate the similarity according to the syntactic and semantic levels, such like [START_REF] Dong | Similarity search for web services[END_REF], [START_REF] Stroulia | Structural and semantic matching for assessing web-service similarity[END_REF], [START_REF] Kokash | A comparison of web service interface similarity measures[END_REF].

Measuring the similarity between the operations enables us of identifying groups of similar operations, in order to build a context of service × operation. This results in a new lattice that reveals the relations between the services according to the provided functionality. Searching for a certain operation returns a sub-lattice of services providing the operation and showing the replaceable services. We better explain the presented approach using a case study described in the next section.

V. CASE STUDY

In this section, we return to the scenario of TCS described in Section II, and we explain how to build such a composition and support it with backups using the generated lattices. Figure 4 illustrates the lattice of services and their keywords as explained before. We want to use this lattice to discover the required services in order to build the TCS. We begin by specifying the set of keywords describing the needed composite service. They are of two categories, plane reservation and train reservation. Thus, we form two queries, we perform a query on a lattice by expressing the set of keywords as a new line, added to the context service × keyword. This results in a new concept in the lattice, labelled query. The services that answer the specified query are represented by the sub-concepts of the concept query. In our scenario, we perform two keyword queries: query1 = {reserve, plane} and query2 = {reserve, train, duration}. This results in the lattice shown in Figure 5, in which, we extract the services answering the two queries and they are:

• for query1: ws 1 , ws 2 , ws 3 , ws 4 , ws 9 and ws 10 ,

• for query2: ws 5 , ws 6 , ws 8 , ws 9 , ws 10 . We further analyse the two sets of services corresponding to the two queries. We apply a similarity measure on the operations according to each set and we identify the groups of similar operations. For example, an operation labelled reserveF in the lattice, represents a group of similar operations for performing a flight reservation. This way, we can build a new context of service × operation for each set of services. The lattice that corresponds to query1 is shown in Figure 6 (top), and the one corresponding to query2 in Figure 6 (bottom).

Using these two lattices, the selection of services offering required operations is straightforward. In our scenario, we need three functionalities as indicated before in Section II: flight reservation, train reservation (if needed), and calculating the duration needed to travel by train to the aimed destination. By regarding the lattice in Figure 6 (top), we notice that all of the services offer an operation for plane reservation. In this case, a service selection might be done regarding the extra operations that the services provide, like for example the operation rentCar. When we select a certain service, we can immediately extract the set of backup services that are able to replace it if it fails. In the same way, we can select a service for train reservation with obtaining the duration information. Thus, the composition in Figure 1 can be easily achieved and supported with backups, as in Figure 6. Supposing that we selected the service Figure 6. The TCS composition with its corresponding backups. ws 4 named P laneW S, and used its operation resF light (which is grouped with other similar operations under the name reserveF in the lattice). We can notice that for the operation resF light, any other service in the lattice can be a backup for ws 4 . In case where all of the operations of ws 4 were used, we notice that only ws 10 and ws 1 can be backups for ws 4 . Similarly, we selected the service ws 6 , named T rainW S, and used two of its provided operations: calcDuration and resT rain. We notice that ws 6 can be replaced by the services ws 10 , ws 8 and ws 5 . Thus, we have discovered immediate backups for the service T rainW S as we did for the service P laneW S. We can notice that the service ws 10 exists in the two lattices, as a backup for T rainW S and P laneW S together. In this case, if both of these services crash, we can replace them both by only one service, which is ws 10 . This service provides the same functionalities of the two services, with three extra operations that are priceT , rentCar and durationF as can be seen in the lattices in Figure 6.

Our approach has enabled us of an easy service discovery and selection, in order to build our aimed scenario. It has also facilitated the discovery of backup services to support our service composition and ensure its continuous functionality.

VI. RELATED WORK

Several works have been proposed for web service classification, in order to facilitate browsing, discovery and selection. A quick overview of some of the works can be obtained from [START_REF] Brockmans | Service-finder deliverable d4.1. research report about current state of the art of matchmaking algorithms[END_REF], [START_REF] Lausen | Survey of current means to discover web services[END_REF]. Below, we describe a selection of works, classified according to their adapted techniques.

A. Using formal concept analysis (FCA)

In [START_REF] Aversano | Using concept lattices to support service selection[END_REF], Aversano et al. classify web services using FCA as a means for WSDL browsing. Their formal contexts are composed according to three levels, service level, operation level and type level, together with keywords. These keywords are identified from the WSDL files by applying vector space metrics with the help of WordNet to discover the synonyms. The resulting service lattice represents an indexing of web services, it highlights the relationships between the services and permits the identification of different categorizations of a certain service.

In [START_REF] Bruno | An approach to support web service classification and annotation[END_REF], Bruno et al. also use keywords extracted from services' interfaces together with FCA to build a web services lattice. They analyze the extracted words, process them using WordNet and other IR techniques. Then, they classify them into vectors using support vector machines (SVM). The obtained vectors categorize the services into domains, then service lattices can be obtained for each category using FCA.

In Peng et al. [START_REF] Peng | Concept-based retrieval of alternate web services[END_REF], similarity values are calculated for service operations, and depending on a chosen threshold, a service lattice is built.

B. Using machine learning

Many approaches adapt techniques from machine learning field, in order to discover and group similar services. In [START_REF] Crasso | Awsc: An approach to web service classification based on machine learning techniques[END_REF], [START_REF] Heßand | Learning to attach semantic metadata to web services[END_REF], service classifiers are defined depending on sets of previously categorized services. Then the resulting classifiers are used to deduce the relevant categories for new given services. In case there were no predefined categories, unsupervised clustering is used. In [START_REF] Ma | Efficiently finding web services using a clustering semantic approach[END_REF], CPLSA approach is defined that reduces a services set then clusters it into semantically related groups.

C. Using service matching

In [START_REF] Lu | Web service search: Who, when, what, and how[END_REF], a web service broker is designed relying on approximate signature matching using XML schema matching. It can recommend services to programmers in order to compose them. In [START_REF] Günay | Structural and semantic similarity metrics for web service matchmaking[END_REF], a service request and a service are represented as two finite state machines then they are compared using various heuristics to find structural similarities between them. In [START_REF] Dong | Similarity search for web services[END_REF], the Woogle web service search engine is presented, which takes the needed operation as input and searches for all the services that include an operation similar to the requested one. In [START_REF] Bouillet | A folksonomy-based model of web services for discovery and automatic composition[END_REF], tags coming from folksonomies are used to discover and compose services.

D. Using vector space model techniques

The vector space model is used for service retrieval in several existing works as in [START_REF] Platzer | A vector space search engine for web services[END_REF], [START_REF] Wang | Semantic structure matching for assessing web service similarity[END_REF], [START_REF] Crasso | Query by example for web services[END_REF]. Terms are extracted from every WSDL file and the vectors are built for each service. A query vector is also built, and similarity is calculated between the service vectors and the query vector. This model is sometimes enhanced by using WordNet, structure matching algorithms to ameliorate the similarity scores as in [START_REF] Wang | Semantic structure matching for assessing web service similarity[END_REF], or by partitioning the space into subspaces to reduce the searching space as in [START_REF] Crasso | Query by example for web services[END_REF].

E. Discussion on the related work

In FCA approaches based on keywords, similar operations can't be determined and thus, web service substitutes can't be identified either. In our approach, we use the lattice based on keywords as a preliminary index together with operation similarity measuring, in order to generate our concept lattices. We have proposed several uses of the generated lattices, as for service discovery, selection and supporting service compositions with backup services. One of our main contributions is the idea of supporting the continuity of service compositions.

A service lattice is an organization of services that reveals the relations between them according to the operations provided in common. It offers a structure of navigation that enables better discovery and browsing than in structures such as lists and sets in other approaches (described in subsections VI-B, VI-C and VI-D). New services can be classified in existing lattices by incremental algorithms for lattice generation. Thus, there is no need to regenerate the whole lattice, if a new service is to be added. A query represents a new concept in the lattice, and the services that offer the minimum required functionality represent the concepts that are closest to the query concept, while further situated services offer extra functionalities. In the lattice, when selecting a service, a sub-lattice that is descendant from this service can be extracted. This sub-lattice contains the possible backups that can replace this service to ensure a recovered functionality.

VII. CONCLUSION

In this paper, we proposed an approach based on formal concept analysis (FCA) for classifying web services. A web service lattice reveals the invisible relations between web services in a certain domain, showing the services that are able to replace other ones. Thus, facilitating service browsing, selecting and identifying possible substitutions. We explained how to exploit the resulting lattices to build orchestrations of web services and supporting them with backup services. An obvious drawback of current web services is the lack of a common definition, which hardens the identification of similar services and necessitates more adaptations when replacing a service with another.

Our work in progress is to enrich the service lattices with quality of service (QoS) aspects, in order to enable an automatic selection of a service that corresponds to a requested level of QoS. We are also working on the dynamic substitution of a web service by one of its backups, to ensure a continuous functionality of a service orchestration.

Figure 1 .

 1 Figure 1. The travel composite service (TCS).

Figure 2 .

 2 Figure 2. The concept lattice for the context in tableI.

• o 1

 1 , o 2 and o 3 share the attribute {b}, thus, they can replace each other for this attribute, • o 1 and o 3 share the attributes {a, b, d}, • o 3 can replace o 1 since it shares all of its attributes in addition to c, • o 2 and o 3 share together the attributes {b, c}, • o 2 can replace o 1 for the attribute b.

Figure 3 .

 3 Figure 3. The main steps of our approach.

Figure 4 .

 4 Figure 4. The concept lattice for a set of services and their keywords.

Figure 5 .

 5 Figure 5. Queries as concepts in the service × keyword lattice.

The lattices are generated by Conexp -http://conexp.sourceforge.net/