Keywords: Data services, composition, fuzzy preferences, rank, uncertain service, probabilistic, orchestration, safe. vii

I wish to express my deep

Résumé court: Cette thèse porte sur la composition des services de données et l'étude de l'impact de l'incertitude qui peut être associée à leurs données accessibles sur le processus de composition et de sélection de service. En eet, dans un contexte tel que l'Internet, il est de plus en plus reconnu que les données et les services d'accès aux données sont sujettes à des valeurs d'incertitude tout en exigeant des techniques de gestion plus sophistiquées. Dans cette thèse, nous enrichissons la description sémantique des services Web an de reéter l'incertitude, et nous proposons de nouveaux mécanismes et modèles pour la sélection et la composition des services. Nos mécanismes sont basés sur les ensembles ous et les théories probabilistes. Tout d'abord, nous étendons notre modélisation précédente basée sur les vues RDF an d'inclure les contraintes oues qui caractérisent les données accédées par les services. Nous proposons une algèbre de composition qui permet de classer les résultats retournés en fonction de leur pertinence par rapport aux préférences de l'utilisateur. Notre algèbre proposée repose sur les fondations de bases de données oues. En outre, nous optons pour l'approche probabiliste pour modéliser l'incertitude des données renvoyées par les services incertains. Nous étendons la description du service Web standard pour représenter les probabilités de sortie. L'invocation des services est également étendue pour tenir compte de l'incertitude. Cette extension est basée sur la théorie des mondes possibles utilisée dans les bases de données probabiliste. Nous dénissons un ensemble d'opérateurs de composition qui sont nécessaires pour orchestrer les services de données. Pour chaque composition, plusieurs plans d'orchestration peuvent être possibles mais qui sont pas tous corrects, donc, nous dénissons un ensemble de conditions pour vérier si le plan est correct (Safe) ou pas. Nous fournissons une implémentation de nos diérentes techniques et les appliquer aux domaines de l'immobilier et du commerce électronique. Nous implémentons ces services et nous fournissons également une étude de la performance de notre prototype de composition.

Mots-clefs: Les services de données, composition, préférences oues, classer, service incertain, probabiliste, orchestration, safe v Résumé long de la thèse:

Au cours des dernières années, le Web a subi une transformation majeure, passant d'un web des données à un web de services. Ceci permet essentiellement les organisations d'orir leurs services. Les services Web sont des applications logicielles modulaires autonomes qui sont con us pour eectuer une tâche spécique. Des exemples typiques comprennent les services de retour d'informations à l'utilisateur, tels que les services de prévision de la météo, ou des services altérant l'état du monde, tels que réservation ou achat de services en ligne, etc. En outre, l'utilisation de services Web est généralement au sein des applications d'entreprise et les actifs logiciels sur le Web. Une tendance récente est l'utilisation des services Web comme un moyen able pour la publication et le partage de données. Actuellement, de nombreuses organisations fournissent un accès basé sur les services via leurs données en mettant leurs bases de données derrière les services web en fournissant une méthode indépendante, interopérable et uniforme pour interagir avec les données. Ce type de services web est appelé les services de données (ou services d'accès de données). Cependant, depuis que l'Internet a une croissance exponentielle avec l'augmentation du nombre de sites, la gestion des données devient un enjeu majeur dans l'industrie de la technologie de l'information. L'incertitude et l'incomplétude sont deux caractéristiques communes de l'information que nous traitons dans notre vie quotidienne. La plupart des moteurs de recherche Web lorsqu'ils sont interrogés avec un mot clé, une série de pages web ainsi que leurs probabilités peuvent correspondre le mot fourni. Aujourd'hui, les informations qui nous entourent dans ce monde informatique virtuel sont souvent incertaines et imprécises. La gestion de l'information incertaine et imprécise a re u une haute attention dans de nombreux domaines (commerce électronique, etc.). L'aspect de l'incertitude des données, en dépit de sa grande importance, n'a jamais été considéré dans la recherche autour des services web et leur composition. Cette thèse est parmi les premiers à aborder les problèmes de l'incertitude des données dans la communauté des services web, qui constitue l'une de ses nombreuses contributions originales. Elle introduit les concepts de préférences oues au sein des services web et des services web incertains et étale les fondements de base pour leur description sémantique. Nous proposons des extensions de méthodes de compositions de services DaaS dans un environnement caractérisé par une forte vi présence d'incertitude. En eet, dans un contexte tel que l'Internet, il est de plus en plus reconnu que les données et donc les services d'accès aux données sont sujettes à des valeurs d'incertitude tout en exigeant des techniques de gestion plus sophistiquées. Dans cette thèse, nous enrichissons les annotations sémantiques de services Web an de reéter cette dimension d'incertitude, puis nous avons proposé des mécanismes de composition de services appropriés. Ces mécanismes sont basés sur l'ensemble ou et les théories probabilistes pour tenir compte des diérences d'interprétation des mondes possibles des données incertaines. Tout d'abord, nous avons présenté une approche pour composer les services web tout en tenant compte des préférences oues de l'utilisateur. Nous avons proposé un modèle pour les services de données basés sur des vues plus de RDF sur des ontologies de domaine. Le modèle sémantique permet de caractériser les préférences sous forme de contraintes oues. Ensuite, notre modéle sélectionne les services pertinents qui peuvent mieux satisfaire les préférences des utilisateurs, planie leur ordre d'exécution et génère le plan d'orchestration qui répond mieux à la requête oue. Nous avons proposé une algèbre pour orchestrer les services de données sélectionnés. L'algèbre proposée classe les résultats retournés en fonction de leurs pertinences aux préférences oues. En outre, nous avons proposé une approche probabiliste pour modéliser l'incertitude des résultats retournés par un service incertain. Le modèle estime qu'un service de données incertain a une certaine sémantique et comportement que ces services peuvent retourner des résultats incertains. Nous avons proposé un modèle d'invocation qui permet l'invocation de services de données et avec une certaine incertitude entrée. Dans le premier cas, le processus d'invocation récupère les probabilités des sorties du service. Dans le second cas, le processus d'invocation calcule les probabilités de résultats renvoyés sur la base des probabilités renvoyées par le service et la probabilité de l'entrée. Ensuite, nous avons déni la sémantique de la composition de services incertains basée sur la théorie de mondes possibles et nous avons remarqué que cette théorie nécessite l'exploration de diérentes combinaisons de mondes possibles pour évaluer la composition. Le calcul de mondes possibles après l'invocation de chaque service est inecace que le nombre de ces mondes est exponentiel avec le nombre de lignes. Ainsi, nous avons opté pour l'approche extensionnelle et nous avons proposé une algèbre qui permet de calculer les probabilités des sorties. Ces prob-worlds . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Over the last decade the Web has undergone a major transformation, changing from an environment for mere data sharing among individuals to an environment that also allows organizations across all spectra to oer their services and conduct their daily business. Modern enterprises worldwide have already moved their operations to the Internet by adopting the Web service technology [START_REF] Alonso | [END_REF]] to provide an interoperable and programmatic interface to their internal systems. The Web Service framework embodies the paradigm of Service-Oriented Computing (SOC) [Papazoglou 2003], whereby software applications both within and outside the enterprise walls are encapsulated as services that can be executed, composed and coordinated in a loosely-coupled manner. Simply put, a Web service is a piece of software application whose interface and binding can be dened, described and discovered as XML artifacts [START_REF] Curbera | [END_REF], and is accessible via ubiquitous Web protocols and standard data formats such as HTTP, XML and SOAP. The XML-based standards around the Web service technology are the key contributor to the large adoption and deployment of Web services. Three key XML-based standards have been dened to support Web service deployment: SOAP 1 , WSDL 2 , and UDDI 3 . SOAP denes a communication protocol for Web services. WSDL enables service providers to describe their services. UDDI oers a registry service that allows advertisement and discovery of Web services.

Besides using Web services to provide access to corporate applications and software assets over the Web, a recent trend has been to use Web services as a reliable means for data publishing and sharing among organizations [START_REF] Carey | [END_REF]]. Today, many enterprises provide a service based access to their data on the Web by putting their databases behind Web services, thereby providing a well-documented, platform (and data source) independent, interoperable and uniform method of interacting with their data. We call this type of Web services as data Web Services, where services correspond to calls (i.e. parameterized queries) over the data sources' schemas. This is as opposed to traditional Web services that provide access to 1 Simple Object Access Protocol (SOAP), http://www.w3.org/TR/soap/ 2 Web Services Description Language(WSDL), http://www.w3.org/TR/wsdl 3 Universal Description, Discovery, and Integration (UDDI) http://www.uddi.org/pubs/uddiv3.htm corporate applications and which we call as SaaS Web services (Software-as-a-Service Web Services) in the hereafter.

While individual data Web services may provide interesting information alone, in most cases, users' queries require the invocation of several services. For instance, let us consider the following query: what are the tests performed in ABC Lab by patients who have been administered Glucophage in XWZ hospital? Let us assume that ABC Lab and XWZ hospital provide two data services S ABC and S XY Z , respectively: S ABC returns the tests performed by a given patient in ABC Lab and S XY Z returns the list of patients that have been administered a given drug in XWZ hospital. The execution of the above mentioned query involves the composition of S ABC and S XY Z services. Web service composition is a powerful solution for building value-added services on top of existing ones.

In our PhD dissertation, we focus on the composition of data Web services and study the impact of the uncertainty that may be associated with their accessed data on the service composition and selection processes. Uncertainty and incompleteness are two common characteristics of the information we deal with in our everyday life. For example, most of the Web search engines that we use on a daily basis return, when queried with some keyword, a set of Web pages along with their probabilities of matching the supplied keyword; the products that are returned from querying the e-commerce sites (e.g., eBay.com, apartment.com, amazon.com) that we use daily are often associated with imprecise and incomplete information (e.g., in their prices, locations, descriptions, etc.) and have uncertain character as they may not really match our formulated queries. In the same way, the data that are returned by a Web service may be uncertain. To the best of our knowledge, the data uncertainty aspect, despite its high importance, was never considered in the previous research works around Web services and their composition. Our thesis is among the rst works to address the data uncertainty issues in the Web services research community. Specically, we proposed to describe services with fuzzy preferences" to better characterize their accessed data, and introduced the concept of uncertain Web services" and laid down the basic foundations for their semantic description, selection, composition and execution.

Research challenges

We summarize below the challenges that need to be dealt with when devising advanced techniques for web services composition in uncertain environments.

• Modeling web services with fuzzy constraints: The description of a Web service (e.g., WSDL, OWL-S, etc.) should include some meta information to characterize the data accessed by the service. This would largely improve the service selection and composition processes by allowing to focus on the services that match the user's preferences.

• Modeling the uncertainty of web services: The uncertainty of the data returned by a Web service should be modeled to allow its consumer to interpret and use it correctly. The uncertainty model should be compatible with current service description standards (e.g., WSDL) as these are widely adopted by Web service development community. For example, the proposed model should be integrated in WSDL in a way that does not aect service consumers that are unaware of uncertainty.

• Composition algebra: The conventional services' composition model (i.e., the composition algebra and its implementations by dierent composition execution engines) should be extended to allow for computing the probabilities/grades of the composition's outputs to help users understand and interpret them correctly. An uncertain service should be compose-able with normal and uncertain services alike; i.e., a composition that is unaware of uncertainty should be able to use uncertain services without aecting its normal execution.

• Web services orchestration: Given a composition (i.e., a set of services whose composition can answer a query), dierent orchestrations may be possible. An orchestration denes an execution plan of a composition. In the context of uncertain data Web services, not all orchestrations compute the probabilities of its outputs correctly. The challenge is to nd, for a given query, the composition plan that computes the correct probabilities for the outputs.

Contributions

In this dissertation, we enrich the semantic description of Web services to reect their uncertainty, and propose new mechanisms and models for services selection and composition. Our mechanisms are based on fuzzy set and probabilistic theories and handle the uncertainty eciently. We summarize bellow the major contributions of this thesis:

• Web services annotated with fuzzy constraints: We extended our previous modeling to Web data services as RDF Views [START_REF] Barhamghi | [END_REF]] to include fuzzy constraints that characterize their accessed data. The constraints are expressed as intervals or fuzzy sets.

• A ranking-aware algebra for services composition: We proposed a composition algebra that allows us to rank the returned results based on their relevance to user's preferences. Our proposed algebra relies on fuzzy databases foundations [Dubois 1990].

• A probabilistic model for uncertain data services: We opted for a probabilistic approach to model the uncertainty of the data returned by uncertain services. We extended the web service description standard to represent the outputs' probabilities. We proposed an invocation model for the invocation of uncertain data services with certain and uncertain inputs. The invocation process retrieves the probabilities of the service's outputs and computes the probabilities of returned results based on the probabilities returned by the service and the probability of the input. Moreover, we dened the semantics of uncertain service composition based on the possible world theory [START_REF] Bosc | [END_REF]]. We proposed a probability-aware composition algebra to compute the probabilities of the composition outputs.

• Safe orchestration plan: because not all composition plans compute correctly the output probabilities, we dened a set of conditions to check whether a composition plan computes correctly the outputs' probabilities.

• Implementation and evaluation: We implemented our dierent techniques and models and applied them to the real-estate and e-commerce domains.

We conducted a performance study of our composition framework.

Dissertation outline

The rest of this dissertation is organized as follows.

-In Chapter 2, we provide the necessary background for understanding our dierent proposals in the dissertation. First, we present the key concepts around the Web service technology. We then focus specically on the area of preferences.

We introduce the reader to modeling and querying uncertain data, top-k query processing and ranking queries on uncertain data. Finally, we review the related work that are most related to our approach. This aims to position our work with respect to existing ones.

-In Chapter 3, we proposed a declarative approach for composing Web data services on the y. We proposed to model data services as RDF Views over domain ontologies to represent their semantics declaratively. Our semantic model allows characterizing the returned data using the fuzzy set theory. Our approach is based on the use of the query rewriting techniques to automate the composition process, and allows to rank-order the composition results based on the user preferences.

-In Chapter 4, we proposed a probabilistic approach for modeling uncertain data services for two cases: independent data and Block-Independent-Disjoint data. Specically, we showed how the uncertainty associated with a data service can be modeled, and proposed a composition algebra that can compute the probabilities of the outputs.

-In Chapter 5, we studied through examples the safety of the orchestration plans in two cases: independent tuples and BID tuples. Moreover, we proposed a set of conditions that should be veried to obtain correct probabilities for these two cases.

In this chapter, we review some of the key concepts in the areas of Web services and uncertainty management. Specically, we dene the following concepts and topics: web services, data web services, web services composition, fuzzy preferences processing, modeling and querying uncertain data, top-k query processing and ranking queries on uncertain data. We also report some of the most recent research works in these same areas.

2.1 Overview on Web Services and Data Web Services

Web Services Denition

A variety of denitions about Web services are given in the literature. However, that proposed by the Word Wide Web Consortium (W3C 1 ) is considered as reference: A Web service is a software system designed to support interoperable machine-to-machine interaction over a network. It has an interface described in a machine-processable format (specically WSDL: Web Services Description Language). Other systems interact with the Web service in a manner prescribed by its description using SOAP (Simple Object Access Protocol) messages, typically conveyed using HTTP with an XML serialization in conjunction with other Webrelated standards2 .

This denition highlights the major technological and business benets of Web services, namely:

• Interoperability: This is the most important benet of Web services. Web services typically work outside of private networks, oering developers a nonproprietary route to their solutions. Web services developed are likely, therefore, to have a longer life-span, oering better return on investment of the developed Web service. Web services also let developers use their preferred programming languages. In addition, thanks to the use of standards-based communications methods, Web services are virtually platform-independent.

• Usability: Web services allow the business logic of many dierent systems to be exposed over the Web. This gives users' applications the freedom to choose the Web services that they need. Instead of re-inventing the wheel for each client, users need only include additional application-specic business logic on the client-side. This allows to develop services and/or client-side code using the languages and tools that users want.

• Reusability: • Deployability: Web services are deployed over standard Internet technologies.

This makes it possible to deploy Web services even over the re wall to servers running on the Internet on the other side of the globe. Also thanks to the use of proven community standards, underlying security is already built-in.

Web Service Model

The Web service model is based upon the interactions between three types of participants including service provider, service registry and service client. Interactions involve three basic operations: service publishing, nding and binding. Participants and operations act upon the Web service artifacts encompassing the service implementation and description. Figure 2.1 shows the dierent participants and the interaction among them. In a typical scenario, a service provider provides a network-accessible software module, i.e., an implementation of a Web service, denes a service description for the Web service and publishes it to a service registry so that the service client can nd it. The service description contains information such as the inputs/outputs of the Web service, the address where the service is located and QoS. The service client queries the service registry and retrieves the service description. Then it uses the information in the service description to bind with the service provider and invoke the Web service implementation. Besides using Web services to provide access to corporate applications and software assets over the Web, a recent trend has been to use Web services as a reliable means for data publishing and sharing among organizations [START_REF] Carey | [END_REF]]. Today, many enterprises provide a service based access to their data on the Web by putting their databases behind Web services, thereby providing a well-documented, platform (and data source) independent, interoperable and uniform method of interacting with their data [Dan 2007]. We call this type of Web services as Data Web Services, where services correspond to calls over the data sources' schemas. A recently released report from Forrester Research [START_REF] Gilpin | [END_REF]] has dened a Data Service as follows: An information service (i.e., data service) provides a simplied, integrated view of real-time, high-quality information about a specic business entity, such as a customer or product. It can be provided by middleware or packaged as an individual software component. The information that it provides comes from a diverse set of information resources, including operational systems, operational data stores, data warehouses, content repositories, collaboration stores, and even streaming sources 5 http://www.uddi.org/pubs/uddi-v3.htm in advanced cases .

Data as a Service brings the notion that data quality can happen in a centralized place, cleansing and enriching data and oering it to dierent systems, applications or users, irrespective of where they were in the organization or on the network. As such, Data as a Service solutions provide the following advantages:

• Heterogeneity : The adoption of data services and the SOA paradigm relieves SOA application developers from having to directly cope with the rst two forms of heterogeneity. That is, in the world of Web services all data sources are described using WSDL and invoked via REST or SOAP calls (thus have the same interface), and all data are in XML form and described using XML Schema (thus have the same data model).

• Agility : the value-added of SOA to application development is reuse and agility, but without exibility at the data tier, that value-added quickly erodes. Instead of relying on non-reusable proprietary codes to access and manipulate data in monolithic application silos, one can exploit data services that can be used and reused in multiple business processes. This greatly simplies development and maintenance of service oriented applications, enforces compliant use of data, and introduces easy-to-use capabilities for using information in dynamic and real-time processes.

• Data quality : Access to data is controlled through the data services, which tends to improve data quality, as there is a single point for updates. Once those services are tested thoroughly, they only need to be regression tested, if they remain unchanged for the next deployment.

Web Services Composition

Web service composition is the process of selecting, combining and executing Web services (WS) in order to resolve user' requests that cannot be resolved based on individual services alone. A sheer number of research works were devoted to Web service composition over the last years [START_REF] Eid | A reference model for dynamic web service composition systems[END_REF][START_REF] Tabatabaei | [END_REF], Weise 2008[START_REF] Yu | [END_REF]]. Much of these works exploit the Semantic Web as a viable means for au-tomating the composition process. Based on the involvement degree of users in the composition process and on the automation degree, WS composition can be conducted in three dierent fashions: manual (using some programming languages), semi-automatic (through a series of interactions with the user), and automatic.

Uncertainty Managing

Data Web services, and Web services in general, have received a considerable attention in the last few years [START_REF] Yu | [END_REF]]. Previous research works [START_REF] Yu | [END_REF]] have addressed the dierent aspects of the Web service lifecycle, including service creation, selection, composition, and execution. However, there are still many issues related to the quality of data Web services themselves that need to be explored and tackled [START_REF] Carey | [END_REF]]. The fuzzy users' preferences and the uncertainty of the data returned by data Web services are one of the key issues that have not been yet fully explored.

Fuzzy Preferences Processing

The handling of user preferences is becoming an increasingly important issue in present-day information systems [Chomicki 2003]. Motivations for such a concern are manifold [START_REF] Hadjali | [END_REF]]. First, it has appeared to be desirable to oer more expressive query languages which can be more faithful to what a user intends to say. Second, the introduction of preferences in queries provides a basis for rank ordering the retrieved items, which is especially valuable in case of large sets of items satisfying a query. Third, on the contrary, a classical query may also have an empty set of answers, while a relaxed (and thus less restrictive) version of the query might be matched by items in the database. User preferences are a key in ranking compositions' results and selecting the best ones. We give below some denitions.

Denitions. A preference is an expression that represents a desire of the user over the attributes of a process model or activity [Abbaci 2011].

User Preference is a concept which enables a choice between several objects and provides rank ordering of these objects, based on user' s satisfaction they provide. Therefore the simplest representation of user preference is object ordering or ranking [Gursky 2008].

Users' preferences can be modeled using fuzzy sets. Fuzzy sets theory [START_REF] Zadeh | Fuzzy sets[END_REF], Dubois 1996, de Calmes 2003, de Calmes 2007] is a exible approach and present convenient tools to model vague criteria and user's preferences. Fuzzy sets are very well suited to the interpretation of linguistic terms and constitute a convenient way for users to express their preferences. Using this paradigm, a preference is represented by means of a set whose boundaries are gradual. Thus, the satisfaction of a tuple t regarding such a fuzzy set F is a matter of degree in the unit interval denoted by μ(t). The underlying fuzzy set theory oers a large panoply of connectives to aggregate these preferences from classical conjunction (min) and disjunction (max) to quantied statements (most of, at least two, around a dozen, ...) and weighted averaging operators. In the context of querying, users dene fuzzy sets to model their preferences that are associated with linguistic labels like `low', `very cheap', etc. Moreover, in accordance with the imprecise nature of the concepts they represent, membership functions associated with the fuzzy sets behind these properties introduce some graduality when checking the satisfaction of the items. The satisfaction degree in [0, 1] provides the necessary information to rank-order the items that somewhat satisfy the user's requirements.

The preferences usually belong to one of the following variants of trapezoidal membership function (gure 2.2):

• Left-trapezoidal function: lower attribute values are better. The satisfaction degree is computed as follows:

μ(t) = ⎧ ⎪ ⎨ ⎪ ⎩ 1 if z ≤ a 0 if z ≥ b b-z b-a if a < z < b • Right-
μ(t) = ⎧ ⎪ ⎨ ⎪ ⎩ 1 if z ≥ b 0 if z ≤ a b-z b-a if a < z < b
• Trapezoidal function: middle values are preferred. The satisfaction degree is computed as follows:

μ(t) = ⎧ ⎪ ⎪ ⎪ ⎪ ⎨ ⎪ ⎪ ⎪ ⎪ ⎩ 1 if b ≤ z ≤ c d-z d-c if c < z < d b-z b-a if a < z < b 0 Otherwise 2.2.

Uncertain Data Management

Uncertainty and Incompleteness are two common characteristics of the information we deal with in our everyday life. Most of the Web search engines that we use on a daily basis return, when queried with some key words, a set of Web pages along with their probabilities of matching the supplied word; the information that we receive from the intelligent objects (e.g., Smart phones, GPSs, ambient sensors, etc.) that surround us in this pervasive computing world are often uncertain and imprecise. For example, the products that are returned from querying the ecommerce sites (e.g., eBay.com, apartment.com, amazon.com) that we use daily are often associated with imprecise and incomplete information (e.g., in their prices, locations, descriptions, etc.) and have uncertain character as they may not really match our formulated queries. Managing such uncertain data is currently receiving increasing attention in many application domains, e.g., e-commerce, sensor networks [Tatbul 2004], scientic data exploration [Buneman 2006], data integration [Marian 2011[START_REF] Agrawal | [END_REF], moving objects tracking [Cheng 2004], data cleaning, information extraction, and location-based services, etc. For example, in the e-commerce domain, a recent study [START_REF] Soliman | [END_REF]] showed that 65% of the business objects (e.g., apartments, cars, products, etc.) that one would nd on business Web sites (e.g., apartments.com, carpages.ca, etc.) are associated with some uncertainty in their basic information (prices, locations, etc.). These domains exhibit uncertainty in their underlying data, coupled with increasing demand from users to eciently derive high-quality answers for the queries posed on such data. • Tuple Level Uncertainty : we do not know whether the tuple belongs to the database instance or not. The variable associated to the tuple has a Boolean domain: it is true when the tuple is present and false if it is absent. Such a tuple is also called a maybe tuple [Widom 2008]. A widely-used model to capture this type of uncertainty is representing tuples as probabilistic events, and model the database as a joint distribution dened on these events. [Sadri 1991[START_REF] Green | [END_REF][START_REF] Abiteboul | [END_REF][START_REF] Bosc | [END_REF]]. Among these models, the probabilistic and the possibilistic models are the most adopted due to their simplicity mainly the probabilistic approach. In the probabilistic data model, data uncertainty is modeled as a probability distribution over the possible tuple attribute values [START_REF] Green | [END_REF][START_REF] Bosc | [END_REF]](each possible tuple/attribute value is assigned a degree of condence, quantifying its probability).

The probabilistic model is a numerical model that relies on an additive assumption and adopts the Possible Worlds Semantics. The Possible Worlds [START_REF] Bosc | [END_REF] is an important concept for understanding the models of uncertain data. In the possible world semantics, data uncertainty is captured by viewing the database as a set of possible instances that correspond to the dierent possible instantiations of the uncertain data items. Many uncertainty models, e.g., [START_REF] Abiteboul | [END_REF], Imielinski 1984], adopt the possible worlds semantics, where a probabilistic database is viewed as a set of possible instances (worlds). The above concepts were the bases of several research projects and systems (e.g., TRIO [Widom 2005], ORION [Cheng 2007] , MystiQ [START_REF] Dalvi | [END_REF]]...)that address modeling and querying uncertain data. The TRIO system introduced working models to capture uncertainty at dierent levels by relating uncertainty with lineage and leveraging existing DBMSs capabilities for uncertain data management. The ORION project deals with constantly evolving data in the form of continuous intervals, and presents query processing and indexing techniques for managing uncertain data in such representation. The possible worlds appraoch is dened as follows:

Denition. Assume a relational schema with k relation names R 1 , ..., R n , a prob- abilistic database is a nite set of possible worlds W = {w 1 , w 2 , ..., w k } where each database instance

w i = (R i
The possible worlds space represents an enumeration of all possible views of the database resulting from the uncertainty or incompleteness in the underlying data.

Possible worlds probabilities are determined based on the probabilistic dependencies among tuples. The most commonly used tuple-level uncertainty model is the independent tuples model [Fuhr 1997]. This model associates existence probabilities with individual tuples and assumes that the tuples are independent of each other. On the other hand, if there are correlations between tuples in a database table, the table should be decomposed into simpler tables and we called them independent-disjoint tables.

Tuple Independent Model. A tuple independent model is a probabilistic model where all the tuples are probabilistic events. If the database consists of a single table, we refer to it a tuple independent table. The database is interpreted as a probability distribution over the set of all possible worlds [Halpern 1990].

Each world contains a subset of the tuples present in the probabilistic database and the probability of each world is calculated by multiplying the existence probabilities of present tuples and non-existence probabilities of non present tuples.

Block Independent Disjoint Model (BID). A block independent disjoint model is a probabilistic database where the set of tuples can be partitioned into blocks [START_REF] Re | Materialized views in probabilistic databases: for information exchange and query optimization[END_REF], Dalvi 2011[START_REF] Stoyanovich | [END_REF]. All tuples in a block are disjoint probabilistic events and all the tuples in dierent blocks are independent probabilistic events. The representation of a BID table is a folows: we choose the key attributes a 1 , a 2 , ..., a n of a relation T that uniquely identify the block to which tuple belongs, then we add a probability attribute P so the schema of a BID table is T (a 1 , ..., a n , b 1 , ..., b k , P ). The probability of a block is the sum of the membership probability values of all tuples in the block and the probability of each possible world is the joint event of the existence of world's blocks, and the absence of all other blocks.

Corresponding possible worlds Probabilistic database with BID

PW1={ l1, l3} PW2={ l2, l3} PW3={ l1 } PW4={ l2 } Block1 Block2 (a) (b) 1 P (P W 5 ) = P (t 1 ) * (1-p(t 2 )) * (1-p(t 3 )) = 0.3 * 0.6 * 0.4 = 0.072 P (P W 4 ) = P (l 2 ) * (1 -p(l 3 )) = 0.7 * 0.4 = 0.
28 [START_REF] Abiteboul | [END_REF], Dalvi 2004, Cheng 2007], treat tuples' uncertainty and attributes' uncertainty separately by introducing two basic types of uncertainty quantied with probability values. The rst type, usually referred to as membership uncertainty" [Dalvi 2004], treats tuples as probabilistic events capturing the belief that they belong to the database. Possible worlds are thus viewed as conjunctions of tuple events. The second uncertainty type, referred to as value uncertainty" [Cheng 2007] represents attributes as probability distributions on continuous or discrete domains of possible values, e.g., modeling readings of sensing devices, or data entry errors in dirty databases.

Queries Semantics

In queries semantics, we need to consider two possible semantics. In the rst, the query is applied to every possible world, and the result consists of all possible answers: called the possible answer sets. In the second, the query is also applied to all possible worlds, but the set of tuples are combined, and a single set of tuples is returned: this is called possible answers semantics. For a query, it is impractical to represent all possible answers but it is convenient to consider one answer at a time.

Denition. There are two approaches to query evaluation: intensional and extensional approach.

Intensional evaluation approach. In intensional query evaluation [Fuhr 1997, Sadri 1995] the probabilistic inference is performed over a propositional formula called lineage. The lineage of a possible output tuple is a propositional formula over the input tuples in the database, which says which input tuples must be present in order for the query to return that output. The intensional approach uses complex events by using the tuple names as atomic events. The calculation of probabilities does not depend on a specic plan. The intensional semantics on probabilistic databases consists of a set of worlds and the content of each world is the output of Q on the database.

Extensional evaluation approach. The extensional approach [Fuhr 1997, Sadri 1995] evaluate queries by reusing standard relational techniques, operators and plans. An extensional operator is an extended relational operator (e.g., join, projection, selection,),to manipulate tuple probabilities. Each extensional operator makes some assumptions on the input tuples (e.g., that they are independent or that they are disjoint) and computes the corresponding probabilities. An extensional plan is a query plan where each operator is an extensional operator. A safe query plan [Dalvi 2004] is an extensional plan that, furthermore, is guaranteed to compute all output probabilities correctly and a query is safe if it admits a safe plan. Thus, if a query is safe, not only can we evaluate it eciently, but we can actually push down the entire query evaluation in a relational database engine, and achieve real scalability. On the other hand, unsafe queries do not have any safe plans. However, in practice, we can always use an extensional plan to compute any unsafe query and obtain some approximate probabilities. Under some restrictions, the probabilities returned by any extensional plan are guaranteed upper bounds of the correct probabilities.

After studying queries' evaluation approaches we need also to study how to rank results.

Ranking queries on uncertain data and top-k processing. Few research works have addressed the problem of answering ranking queries in the presence of data uncertainty. Supporting ranking queries on uncertain data has been rst proposed in [START_REF] Soliman | [END_REF]]. That work introduced a framework to rank uncertain data based on the marriage" of traditional top-k semantics and possible worlds semantics. Along the same lines, [Hua 2008, Cormode 2009]proposed similar query semantics and processing algorithms. The uncertainty model in all these works assumes that tuples have deterministic single-valued scores, and they are associated with membership probabilities. In [Hua 2008], computing probabilistic ranking queries with a given probability threshold is addressed. Given a threshold i, the objective is to report each tuple whose probability to appear in the top-k answers is at least i. The given techniques are based on dynamic programming formulation under tuple level uncertainty. The work in [START_REF] Soliman | [END_REF]] adopts the attribute level uncertainty model for formulating uncertain rank join queries, and studies the integration of rank join processing with probabilistic ranking.

Some recent works have addressed the problem of computing a consensus ranking from a space of possible worlds. The work [START_REF] Li | [END_REF]] gives an approximate algorithm for computing a consensus ranking under the Kendall tau distance.

The impact of tuple-level and attribute-level uncertainty on ranking queries has been modeled and addressed by current proposals from dierent perspectives. In most proposals, the two uncertainty types are handled in isolation by assuming that the underlying uncertainty type is either tuple-level (e.g., [Hua 2008]) or attribute-level (e.g., [Soliman 2009]). An important distinction among proposals that handle attribute-level uncertainty is their ability to support discrete and/or continuous domains of the uncertain attributes. For discrete uncertain attributes, a mapping can be constructed to model attribute-level uncertainty as tuple-level uncertainty, and hence leverage the ranking techniques developed for tuple-level uncertainty.

Formulating and processing top-k queries have received a considerable attention in the last years ( [Ilyas 2008]is a thorough survey). Research works in the eld adopt one of two ranking models: (i) top-k selection and (ii) top-k join.

In the top-k selection model, scores are attached to base tuples, and the query reports the k tuples with the highest scores. The NRA (No Random Access) algorithm [Fagin 2003] is one of the prominent top-k techniques that adopt the top-k selection model. The input to the NRA algorithm is a set of sorted lists, each ranks the same set of objects based on one scoring predicate. The output is a ranked list of these objects ordered on the aggregate input scores. In the top-k join model, scores are assumed to be attached to join results rather than base tuples.

A top-k join query joins a set of relations based on a given join condition, assigns scores to join results based on some scoring function, and reports the top-k join results. Many top-k join techniques address the interaction between computing the join results and producing the top-k answers. One example is the Rank-Join algorithm [START_REF] Ilyas | [END_REF]], which eciently integrates the joining and ranking tasks.

Integrating tuples' scores and probabilities as two interacting ranking dimensions is a recent issue [Soliman 2009]. Most current top-k processing proposals assume deterministic data, and hence they are not explicitly designed to treat probability as an additional ranking dimension.

Related work 2.3.1 Web services composition and ranking

Several mashup editors have been introduced by the industry with the objective of making the process of mashups creation as simple and programmable-free" as possible. Examples include Yahoo Pipes6 , Google Mashup Editor7 , Intel Mash Maker8 . These products allow average users to create mashups without any programming involved; the users need just to drag and drop services, operators and/or user inputs and to visually connect them. However, the knowledge required from users is not trivial because they are still expected to know exactly what the mashup inputs and outputs are, and to gure out all the intermediate steps needed to generate the desired outputs from the inputs. This includes selecting the needed services/data sources, mapping their inputs and outputs to each other and probably adding some mediation services/functions when inputs/outputs don't t each other.

The Web Service Management System [START_REF] Srivastava | [END_REF]] models data services as relations and allows users to mashup data services by expressing their mashup queries directly in terms of these relations. Along the same lines, the Web Service Mediator System WSMED [START_REF] Sabesan | [END_REF]] allows users to mashup data services by dening relational views on top of them (called the WSMED Views).

Unfortunately, users in these systems are assumed to have an understanding of the semantics of the data services that are available to them to be able to formulate their queries. Furthermore, users are supposed to import the services relevant to their needs; dene views on top of imported services and enhance the views with primary-key constraints. These tasks are dicult and hinder average users from mashing up data services at large. These systems model data services as relations with inputs and outputs as the relations' attributes.

This modeling is poor in semantics, as opposed to the use of domain ontologies, and may lead to ambiguity when data services have similar inputs and outputs (attributes), but dierent semantics. For example, assume a service S($a, ?b) where a represents a school and b the student, the service S can return students or successful students in a given school. Compared to these works and to other academic mashup systems (e.g., [START_REF] Tatemura | [END_REF]), users of our system are not required to select the services manually, connect them to each other and drop code (in JavaScript) to mediate between incompatible inputs/outputs of involved services. This is completely carried out by the system in a transparent fashion.

That is, our approach is declarative; users need just to specify the information they need without specifying how this information is obtained. Furthermore, the systems mentioned above do not provide any eective means to rank the data results returned by the mashups.

Our work is also related to the works around top-k queries and data ranking.

Ranking queries are becoming dominant in many domain applications such as multimedia databases, middelwares, and datamining. The increasing of ranking works support ranking mainly in relational database management system and recently pay an attention of the research community. The previous research works [Ilyas 2008] in that area adopt one of two ranking models: (i) top-k selection and (ii) top-k join. In the top-k selection model, scores are attached to tuples in one single relation, and the query reports the k tuples with the highest scores [Fagin 2003]. Another research work attempted to integrate these two models [START_REF] Ilyas | [END_REF]]. In contrast, the ranking in our system is complete: it computes the grades of individual data sets returned by data services and the integration thereof to compute the rankings of the nal results based on the users fuzzy preferences.

In addition, our approach adopts a exible approach for preference modeling (i.e., a fuzzy approach) and provides two ranking models: scalar and vector models.

Uncertainty in web services composition

A considerable past work studying uncertain data management. In [Dong 2009], a Local-as-View-like data integration system was proposed for uncertain data sources. However this work has addressed only the issues of creating the probabilistic mappings between the mediated schema and the data sources' schemas, and queries transformation based on these probabilistic mappings. Along the same lines, the authors of [START_REF] Magnani | [END_REF]] survey the dierent approaches (and the used formalisms) for the construction of probabilistic mappings, and the corresponding query transformation mechanisms. However, all of these works have addressed the uncertainty at the schema level only; i.e., the uncertainty resides in the way sources can be mapped to the mediated schema. In contrast, our project complements these works by addressing the uncertainty at the data level; i.e., we assume that there is a deterministic mapping between the sources' schemas and the mediated schema, and focus on computing the probabilities of the integrated data when the data inside the sources are themselves uncertain. Few research works have addressed the uncertainty at the data level. A query rewriting based approach was proposed in [Dalvi 2011] to speed up the query evaluation over uncertain data sources by exploiting the previously answered queries (which are stored as materialized views). In that work, authors dene a partial representation for the materialized views. This representation describes whether the tuples inside the view are independent" or disjoint". However, this approach is limited because when the correlation between tuples is more complex than the independent and disjoint relationships the materialized views become useless. Also, it did not address the issue of nding the query plans that could give the right probabilities for the returned results. In [START_REF] Agrawal | [END_REF]], the authors revisit the main data integration concepts (including the query containment, the certain answers, etc.) in the context of uncertain data sources. However, the issue of computing the tuples' probabilities and the impacts of the potential correlations were not studied. In [START_REF] Hadjali | [END_REF]], an approach was proposed to match queries and views involving some fuzzy predicates. The approach returns the views that do provide answers whose satisfaction degree is over a threshold specied by the user. However, in that work, the tuples' uncertainty was not taken into account. In addition to all of the cited limitations, none of these previous works have addressed the data ranking issue in the data integration context and the usage of probability as a new ranking dimension (in addition to that of the tuples' scores) in the ranking space, which is the main focus of this project.

The uncertainty of the data returned by data services is one of the key issues that have never been explored yet. Uncertainty is an inherent feature of the results returned by data services in many applications including Web data integration [START_REF] Agrawal | [END_REF][START_REF] Soliman | [END_REF], scientic data exploration [Buneman 2006],

sensors networks [Tatbul 2004], objects tracking, etc.

Several works have focused on creating and modeling Data Web services Moreover, the uncertainty aspect was never looked at in these works.

Safe plans

Safe queries and safe query plans are introduced by [Dalvi 2004]. They also prove a dichotomy into polynomial time and #P-hard for conjunctive queries without self-joins over tuple independent tables. Olteanu et al [Olteanu 2009] address the problem of safe plans, by decoupling the data processing part of the query plan from the probabilistic inference part. They introduce a new type of plan that allows the optimizer to choose the best plan for the data processing part, yet allowing the probabilistic inference to take advantage of the query's safety. In that framework, a safe plan is an eager plan, where all probabilistic computations are performed as early as possible; lazy plans are at the other extreme as they compute the probabilities after the result tuples are computed. [Gatterbauer 2010] introduced the dissociation technique; they dene an order between query plans and thus approximate the query probabilities with best possible upper bounds in a database independent way. Query evaluation on BID tables was rst discussed by Andritsos et al. [START_REF] Andritsos | lean answers over dirty databases: A probabilistic approach[END_REF]] and Re et al. [START_REF] Re | Query evaluation on probabilistic databases[END_REF]]. Only conjunctive queries without selfjoins have been studied over BID tables. [Sen 2007] discuss query evaluation over probabilistic databases represented by a graphical model. An optimization to query processing over such probabilistic databases is described by [START_REF] Sen | [END_REF]]. The optimization nds common subgraphs in the GM and applies technique similar to lifted inference [Poole 2003], this can be very eective over large databases because they tend to have a large number of similar repeated subgraphs. All approaches mentioned above cannot be applied in the case of uncertain data services. Thus, we proposed a set of conditions to check the safety for independent and BID tuples.

Conslusion

In this chapter, we presented the main concepts around Web service technology.

We also introduced the reader to fuzzy sets, uncertainty in databases and the

Introduction

Data services compositions (a.k.a., data mashups ) are situational applications (i.e., applications that come together for solving some immediate business problems) that combine data elements from dierent data sources to provide value-added information for immediate business data needs. Typically, the access to these data sources is carried out through data Web services [START_REF] Carey | [END_REF][START_REF] Truong | On Analyzing and Specifying Concerns for Data as a Service[END_REF].

Data services composition has become so popular over the last few years; its applications vary from addressing transient business needs in modern enterprises [START_REF] Guinard | [END_REF], Jhingran 2006] to conducting scientic research in e-science communities [Zhao 2008]. Data services composition involves several challenging tasks including: selecting the data services that are relevant to user's needs, mapping their inputs and outputs to each other (and probably applying some mediation functions when inputs/outputs don't t each other) within a composition plan. In addition, user preferences are an important factor that could be used to customize the composition. A more general and crucial approach to represent preferences is based on the fuzzy sets theory [START_REF] Hadjali | [END_REF], Dubois 2000]. Fuzzy sets are very appropriate for the interpretation of linguistic terms, which constitute a convenient way for users to express their preferences. For example, when expressing preferences about the price of an apartment, users often employ linguistic terms like cheap, aordable and not expensive.

Motivating Example

Consider a Web user Melissa planning to buy a new apartment. Melissa would like to nd an apartment in a clean city, with an aordable price and located near to high schools with cheap tuition fees and good reputation. Melissa needs to retrieve cheap schools along with their tuitions fees and addresses from nces.ed.gov and their ratings from psk12.com. She needs then to connect to some e-commerce sites (e.g., apartments.com) to locate cheap apartments near to the schools found. She needs also to connect to the Outdoor City Pollution Database on who.int to lter out apartments located in polluted cities. Assume that these information are provided by the data services in Table 3.1. The service S 1 returns the schools, along with their tuitions fees, reputations and addresses at a given country; S 2 returns the apartments for sale along with their prices at a given city, and S 3 returns the pollution level at a given city. Input and output parameters are proceeded by $" and ?" respectively. Obviously, Melissa can answer her query by composing the following services. Returns the schools s along with their tuition fees t, reputation r and addresses a in a given country c S 2 ($a, ?ap, ?p)

Returns the apartments for sale ap, their prices p at a given address a S 3 ($a, ?po)

Returns the pollution level po for a given city a

Challenges

Mashing-up data services presents many challenges for the service composer (i.e., Melissa):

• Understanding the semantics of data services. Melissa needs to delve into the data service space and understand the semantics of each individual service in order to identify the services that may contribute to the resolution of her query. The semantics of a data Web service resides not in how" inputs and outputs are related to each other but also in the fuzzy constraints; i.e., many services may have the same functionality types, but have completely dierent constraints. In the lack of a clear semantics denition inside the service description les, service composers will miss much of the services that are relevant to their queries; even worse they may wrongly select services that are irrelevant to their needs.

• Selecting and composing relevant data services. Let us assume now that Melissa is able to understand the semantics of available data services, the next step would be to select participant services which better satisfy the user's preferences, gure out their execution order, and generate the orchestration composition plan that better answer a fuzzy preferences query.

• Ranking the results and selecting the best ones. Let us assume now that Melissa was able to create and execute the composition. Each of the composed services may return a huge number of business objects (e.g., apartments, schools) that may more or less match the user's preferences. As a result, Melissa will be overwhelmed with a great number of answers and may miss the ones that are most relevant to her needs.

Contributions

In this chapter we propose a declarative approach for composing data web services on the y. Based on a semantic model for data web services, and a declarative" composition query formulated against domain ontologies along with a set of preferences formulated as fuzzy constraints, our proposed composition system generates detailed descriptions of the composition that fullls the query. The generated composition plan ranks also the results at the execution time. We summarize below our major contributions:

• A semantic model for data services. We propose to model data services as RDF Views over domain ontologies. An RDF view allows capturing the semantics of the associated service in a declarative" way based on concepts and relations whose semantics are formally dened in domain ontologies. The semantic model allows characterizing the preferences as fuzzy constraints using the fuzzy set theory.

• A declarative model for composing data services. We propose to use the mature query rewriting techniques for composing data services. First, we select the relevant services which satisfy fuzzy users' preferences and rewrites the query in terms of calls to selected services. Our composition model enables average users to compose data services as all what they need to do is just specifying their data needs declaratively.

• A data ranking model to select the best answers. We propose a ranking-aware composition algebra (and implementation thereof) that allows ranking the returned results based on the user preferences at the composition execution time. The remainder of this chapter is organized as follows. In Section 2, we present our declarative approach to construct service compositions. We show also our semantic modeling of data services and queries; present the composition algorithm through an example. In section 3 we introduce our ranking-aware composition algebra and we give an overview of our approach. Finally, in section 4, we summarize our contributions and conclude.

Preferences-Based Data Service Composition Model

In this section we present a `declarative approach for data services composition that addresses the challenges discussed in the previous section. We show the dierent phases involved in data service composition, starting from the service modeling to the generation of the nal composition that will be returned to users.

Preference Queries

We adopt a declarative approach to Web services composition, i.e., instead of selecting and composing Web services manually, users formulate their composition queries over domain ontologies. We consider conjunctive preference queries expressed over domain ontologies using a slightly modied version of SPARQL, the de facto query language for the Semantic Web. Users express their preference queries over domain ontologies using a slight modication of SPARQL. Figure 3.1 gives the formulated query for the running example in (c), and its graphical representation in (a). The user's preferences are expressed in the PREFERRING" clause. We model user's preferences using the fuzzy sets theory [START_REF] Zadeh | Fuzzy sets[END_REF]]. URL="http://vm.liris.cnrs.fr:36880/FunctionsDescription/index.jsp" SELECT ?x,?y,?z WHERE {?S rdf:type :School ?S :country "France" ?S :name ?u, ?S :city ?z ?S :tuitionsFees ?t ?S :reputation ?r ?A rdf:type :Apartment ?A :city ?z, ?A :price ?y ?A :number ?x ?P rdf:type :Pollution ?P :city ?z, ?P :level ?po} PREFERRING {?y :is "URL/Affordable" ?t :is "URL/Cheap" ?r :is "URL/Good"} WSDL) can be extended straightforwardly with our proposed modeling to data services, as RPVs can be incorporated within the description les (e.g., WSDL) as annotations.

C i x i F uzzyT erm x F uzzyT erm μ F : X → [0, 1] x μ F (x) x F uzzyT erm μ F (x) = 1 x F uzzyT erm μ F (x) = 0
Ω S i Ω S i ($X i , ?Y i ) : -< F (X i , Y i , Z i ), C i > • X i Y i S i • F (X i , Y i , Z i ) is

Query Rewriting

In a previous work [START_REF] Barhamghi | [END_REF]] we proposed an ecient RDF query rewriting algorithm. We exploit that algorithm to compose data services. Given a composition query Q and a set of data services represented by their corresponding RP V s V = v 1 , v 2 , ..., v i , the algorithm rewrites Q as a composition of data services whose union of RDF graphs (denoted to by G V ) covers the RDF graph of Q (denoted to by G Q ). The rewriting algorithm has two phases: 3.2.3.1 Phase-I: Finding Relevant Sub-Graphs

In the rst phase, our composition system compares G Q to every RP V v i in V and determines the class-nodes (i.e., the variables in Q whose types are ontological classes, e.g., A", S" and P" in Figure 3.1) and object properties in G Q that are covered by v i . The system stores information about covered class nodes and object properties as a partial containment mapping in a mapping table. The mapping table points out the dierent possibilities of using an RP V to cover parts of G Q . In this phase, the rewriting algorithm considers each class-node and each object-property in Q and tries to determine the rel-evant views to them. A view is said to be relevant in one of the following two cases: Case1: Covering Class-nodes. v i includes a class-node C v whose type C is the same as the type of a class-node C Q in Q such that the following conditions hold true:

• If the mapped class-node C Q has a distinguished variable x in the query , i.e. a datatype property of C Q is bound to a distinguished variable in Q , then either the same datatype property of C v is projected in v i (i.e. it is bound to a distinguished variable in v i ), or it can be recovered because all datatype properties used in the skolem function of C are projected in v i and thus can be used to recover the missing distinguished variable (i.e. the missing datatype property of C v ) of C v .

• If the mapped class-node C Q has an existential variable x in the query Q (i.e. one of its datatype properties binds to an existential variable x in Q).

• If the mapped class-node C Q has a constant in its triples group in the query, then either the view has to project the datatype property of C v that corre- sponds to the constant, or such datatype property can be recovered.

• If the mapped class-node C Q is involved in an object-property in the query, then the view has either to project the attributes of the skolem function of so that to enforce the join with object-property or it has to cover the object-property as dened by the Case2.

Case 2 (Covering Object-properties).v i includes an object-property p of Q in its denition such that the class-nodes linked by p can be mapped to the corresponding class-nodes of p in Q(i.e. they have the same types). The view v i is relevant to the query if it projects the datatype properties used in the skolem function of each of the class-nodes linked by , or it covers the class-nodes for which it does not project the datatype properties used in their skolem functions.

Example. The service S 1 has a class node S 1 .S that can be matched with Q.S. In the second phase, the RDF query rewriting algorithm explores the dierent combinations from the Mapping-and-Connectivity table. The algorithm needs to consider the combination of disjoint sets of covered object-properties and class-nodes except when some datatype properties are missing in a covered class-node, in which case additional class-nodes are added to recover missing datatypes properties. We consider disjoint sets of covered object-properties and class-nodes for the following reason: each line in the mapping table contains a class-node CN i or an object-property OP i along with the minimum set of classnodes/object-properties (CNs/OPs) that are linked with that classnode/object-property (CN i /OP i ) via some joins that cannot be enforced if other class-nodes/object-properties (CNs/OPs) from a dierent view were used in the combination (this happens when the joins are made over existential variables in the view). This assumption speeds up the second phase of the rewriting algorithm because it prunes the combinations with joins that cannot be enforced.

A combination is a valid rewriting of (a valid composition) if the following two conditions hold true: 1-It covers the whole set of class-nodes and object-properties in Q, and 2-The combination is executable. A composition is said to be executable if all input parameters necessary for the invocation of its component services are bound or can be made bound by the invocation of primitive services whose input parameters are bound.

Example. Continuing with the running example, there is only one possible combination C 1 = {S 1 , S 2 , S 3 }. Only S 1 ($c, ?u, ?t, ?r, ?z) can be invoked at the beginning as its input parameter is bound. After the invocation of S 1 , the variable z become available; hence, the services S 2 , S 3 become invokable. Consequently C 1 is executable and is considered as a valid composition.

A ranking-aware algebra for data services compositions

The obtained composition for a query will be deployed as new permanent data Web service. For this purpose, two essential issues are addressed. First, similarly to traditional Web services composition, a composite Web service (i.e.

a composition)needs to be translated into an execution plan describing both data ow and intermediary data processing among individual web services in a composition. Each service occurrence in the composition (that is obtained from the query rewriting algorithm) will be translated to an "invoke" operation. The outputs of similar web services (services covering the same portion in the query) will be unied by a "`union"' operation that is responsible for removing redundant tuples. "`Join"' operations will be used to feed a service with data tuples coming from its parents in the composition, it joins tuples from parent services in a composition. "`Select"' operations are used to lter out tuples that do not satisfy a specied equality or order constraint. Second, an ecient execution engine that is capable to understand and execute the plan's building constructs needs to be implemented. Component services must be executed in a particular order depending on their access patterns. If a service S i has an input x that is obtained from an output y of S j then S i must be preceded by S j in the execution plan

Weber ⎧ ⎪ ⎪ ⎪ ⎪ ⎪ ⎨ ⎪ ⎪ ⎪ ⎪ ⎪ ⎩ x if y = 1 y if x = 1 0 else Name Conorm :⊥ (x, y) Zadeh max(x, y) Probabilistic min(x + y, 1) Lukasiewicz max(x + y -1, 0) Weber ⎧ ⎪ ⎪ ⎪ ⎪ ⎪ ⎨ ⎪ ⎪ ⎪ ⎪ ⎪ ⎩ x if y = 0 y if x = 0 1 else
In this section, we propose an algebra to orchestrate the data services selected in the previous steps. The proposed algebra allows ranking the returned results based on their relevances to user's preferences. Results ranking is important as the results number may be very large which may cause the users to miss the ones that are most relevant to their needs. To enable ranking-aware query processing, our proposed algebra relies on the mature fuzzy database foundations [Dubois 1999]. This new algebra enables and determines our query execution model and operator implementations.

We describe below two sets of ranking-aware composition operators that follow two approaches to rank data: (i) scalar grades based ranking, and (ii) vector grades based ranking.

Scalar Grade based Results Ranking Algebra

The operators in this set assume that each manipulated tuple is associated with a grade computed as the aggregation of the dierent grades associated to its attributes that are involved in fuzzy preferences. We dene the following operators:

• The Grade-aware Invocation Invoke g (S, t g in , O g ): Let S be a service, t g in the graded input tuple with which S is invoked, O g the graded output, and S.O be the output returned by S. The Invoke g operator relays the tuples from S.O to O g , and for each relayed tuple t i it computes the grade g(t i ) as follows.

First, assume t i is involved in n preference fuzzy constraints P j (where 1≤ j ≤n), the operator computes g 1 (t i )= (μ P 1 (t i ) , μ P 2 (t i ) , ..., μ Pn(t i ) ) where is a t-norm operator (that generalizes the conjunction operation) and μ P i the membership function associated with P i . We implemented the T-norms presented in Table 3.3. The Zadeh t-norm is the greatest t-norm, thus leading to an optimistic aggregation strategy. The Lukasiewicz and Weber t-norm yield a pessimistic aggregation strategy. Second, it computes g(t i ) as follows:

g(t i )= (g(t in ), g 1 (t i )). • Graded Join: ∞ g (I g 1 , I g 2 )
, where I g 1 and I g 2 are two graded data sets. The grade of an outputted tuple is given by:

g(∞ g (t, t )) = (g(t), g(t ))
where is a t-norm, and t and t are tuples from I g 1 and I g 2 respectively.

• Graded Projection g A . The pro jection is an operation that selects specied attributes A={a 1 , a 2 , ...} from a results set. The grade of an outputted tuple t is: g(t) =⊥ (g(t 1 ), .., g(t i ), .., g(t n )) where t = A (t i ) i=1:n and ⊥ is the co-norm corresponding to the t-norm used in the graded join.

• Graded Union ∪ g . The grade of an outputted tuple t is: g(t)= ⊥ (g(t 1 ), .., g(t i ), .., g(t n )), where t i = t and i = 1 : n

• Graded Rank Rank g : the rank operator orders all outputted tuples accord- ing to assigned grades. Let t 1 , t 2 be two tuples and g 1 , g 2 be the grades respectively. If g 2 ≤ g 1 so t 1 appears before t 2 .

• Graded Select Select g : Let c be a set of conditions; The probability of a tuple t in the outputted set is computed as follows:

Invoke g S 1

Data Mashup Plan

prob(t) = ⎧ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎨ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎩ prob(t) if c = true 0 if c = false
Example. We explain the previous operators based on our motivating example. The services S 1 , S 2 and S 3 can be composed to nd the apartments for sale located in cities with low pollution levels and near to schools with good reputations in a given country as shown in Figure 3.3. First, S 1 is invoked with the desired country (e.g., France). The invocation operator Invoke g (S 1 ) computes the grades of obtained tuples. The P rojection g (z) operator projects the obtained tuples on the city attribute (i.e., z ). Then, the obtained cities are used to invoke S 2 to retrieve nearby apartments along with their prices. In parallel, S 3 is invoked to retrieve the pollution levels of obtained cities. The results of S 2 and S 3 are joined over the variable z. Then, the P rojection g (z, x, y) operator retains only the apartments information (i.e., numbers, prices and cities). All of these operators compute the tuples' rankings according to our dened equations presented earlier. Figure 3.4 shows the results (along with their rankings) at the output of each of these operators, and the nal results at the composition's output.

• The Invoke g (S 1 ) operator invokes S 1 with the value France", and computes the dierent grades. For instance the grades of the school s3" are computed as follows: based on the membership functions associated with the tuition fees and the reputation fuzzy predicates, the grade of the tuition fees attribute is 0.22 and the grade of the reputation attribute is 0.05. Hence, Grade zadeh (s3) = min(0.22, 0.05) = 0.05, Grade probabilistic (s3) = 0.22 * 0.05 = 0.011, and Grade Lukasiewicz (s3) = max(0.22 + 0.05 -1, 0) = 0.

• The P rojection g (z) operator projects the obtained tuples on the city attribute (i.e., z ) and computes the grades of obtained tuples. For example, the grade of the outputted tuple corresponding to Lyon" is computed as follows:

Grade zadeh (Lyon) = max(1, 0.4) = 1 Grade probabilistic (Lyon) = min(1 + 0.311, 1) = 1 Grade Lukasiewicz (Lyon) = max(1 + 0.178 -1, 0) = 0.178
• The Invoke g (S 2 ) operator invokes, for each input tuple, the service S 2 and computes the grades of obtained tuples. For example, the grade of the apartment a1" (at the output of Invoke g (S 2)) is computed as follows: given that the apartment a1" accessed by S 2 has a grade of 1, and that the grades of the city Lyon" at the input of Invoke g (S 2 ) are shown above, then the grades of a1" at the output of Invoke g (S 2 ) are:

Grade zadeh (a1) = min(1, 1) = 1, Grade probabilistic (a1) = 1 * 1 = 1, and Grade Lukasiewicz (a1) = max(1 + 0.178 -1, 0) = 0.178. The join operator joins S 2 and S 3 outputted tuples and computes the associated grades. For example, the grade of the tuple corresponding to a3" is computed as follows:

Grade zadeh (a3) = min(0.6, 0.52) = 0.52 Grade P robabilistic (a3) = 0.312 * 0.36 = 0.112 Grade Lukasiewicz (a3) = max(0.12 + 0.15 -1, 0) = 0

• Finally, the Rank g orders results in ascending order(from the most satisfac- tory to the least satisfatory). Merging dierent grades in one aggregated scalar grade is interesting but presents two main drawbacks. First, it does not allow users to know why a given tuple is a good or a bad result. Details on how fuzzy user preferences match data are not kept. Second, the tuples ordering may vary from one t-norm to another.

To overcome these drawbacks, we propose to associate to each tuple a vector of grades. One may not always prefer to aggregate the dierent computed partial grades. In this case, each tuple t is associated with a vector of grades (instead of a scalar grade). To rank query results, one should revisit the above graded algebraic operators. For instance, The following set of revised graded operators are dened.

• Graded Join ∞ g (I g

1 , I g

2 ), where I g 1 and I g 2 are two graded data sets. The revised grade of an outputted tuple is given by:

g(∞ g (t, t )) = ( (g 1 (t), g 1 (t )), • • • , (g d (t), g d (t )))
where is a t-norm and t (resp. t ) is a tuple of the set I g 1 (resp. I g

2 ), and g j (t) is the grade of the tuple t relative to a fuzzy predicate P j .

• Graded Projection g A . The grade of an outputted tuple t is: g(t)= {⊥ (g 1 (t 1 ), .., g 1 (t n )), .., ⊥ (g j (t 1 ), .., g j (t n )), .., ⊥ (g m (t 1 ), .., g m (t n ))} where t = A (t i ) i=1:n and ⊥ is the co-norm corresponding to the t-norm used in the graded join, and g j (t ) is the grade of the tuple t relative to a fuzzy predicate P j . The implemented co-norm are presented in Table 3.3.

• Graded Union ∪ g . The grade of an outputted tuple t is: g(t)= {⊥ (g 1 (t 1 ), .., g 1 (t n )), .., ⊥ (g j (t 1 ), .., g j (t n )), .., ⊥ (g m (t 1 ), .., g m (t n ))}

where t i = t, i=1:n and g j (t ) is the grade of the tuple t relative to a fuzzy predicate P j .

• Graded Select σ g . The grade of an outputted tuple t is: g(t)= {(g 1 (t 1 ), .., g 1 (t n )), .., (g j (t 1 ), .., g j (t n )), .., (g m (t 1 ), .., g m (t n ))} where t i = t, i=1:n and g j (t ) is the grade of the tuple t relative to a fuzzy predicate P j . Table 3.4 shows the nal answers along with the dierent grades (for the fuzzy constraints Cheap, Good, Aordable and Low). 3.5 gives an overview of our proposed composition approach. Our approach is declarative"; i.e., composition creators are relieved from having to select services and build manually the composition plan, a task that would generally require important programming skills. They need only to formulate their declarative queries over domain ontologies using the do facto ontology query language SPARQL1 .

The Preference Query Formulator component provides users with a GUI implemented with Java Swing to interactively formulate their queries over a domain ontology. Users are not required to have knowledge about SPARQL (or any specic ontology query languages) to express their queries, they are assisted interactively in formulating their queries and specifying the desired fuzzy terms.

TheFuzzy Membership Functions Manager component is used to manage fuzzy linguistic terms. It enables users and service providers to dene their desired fuzzy terms along with the associated fuzzy membership functions. The dened terms are stored in a local fuzzy terms knowledge base which can be shared by users, and are linked to their implementing Web services. Examples of fuzzy terms along with their services can be found on http://vm.liris.cnrs.fr:36880/FuzzyTerms. Users and service providers can directly test the proposed membership functions on that link and use the associated fuzzy terms. For each fuzzy term we provide a shape that gives a graphical representation of the associated membership function, a form that helps users to compute the degree to which a given value is in the fuzzy set of the considered fuzzy term, and a WSDL description of the Web service that implements the membership function.

RDF Query Rewriter implements an RDF query rewriting algorithm [START_REF] Barhamghi | [END_REF]] to identify the relevant data services that match (some parts of) a user query. For that purpose, it exploits the annotations that were added to the service description les (e.g., WSDls). The Service Locator feeds the Query Rewriter with data services that most likely match a given query. Our approach exploits the mature query rewriting techniques [START_REF] Barhamghi | [END_REF]] to fully automate the composition process.

The Service Annotator component annotates the service description les (e.g., WSDL les, SA-Rest, etc).

The composition plan generator orchestrates the selected services using a ranking-aware composition algebra that we have devised for that purpose. The composition will be then displayed to users, who will be able to execute it with their inputs.

The Ranking Aware Composition Execution Engine allows to execute our dened algebra. The execution engine assigns grades to results returned from services' calls based on their matching to users' preferences. We detail all of the previous steps in the subsequent subsections.

Conclusion

In this chapter, we proposed a declarative approach to compose data Web services on the y. We proposed to model data services as RDF Views over domain ontolo-gies to represent their semantics declaratively. Our semantic model allows characterizing the returned data using the fuzzy set theory. Our approach is based on the usage of the query rewriting techniques to automate the composition process, and allows to rank-order the composition results based on the user preferences, which are modeled as fuzzy constraints.

Introduction

Data services and Web services in general have received a considerable attention in recent years [START_REF] Yu | [END_REF]]. Previous works have addressed the dierent aspects of the Web service life-cycle, including service creation, selection, discovery, invocation and composition [START_REF] Yu | [END_REF]]. However, there are still many issues related to the quality of data services themselves that need to be explored [Dustdar 2012]. The uncertainty of the data returned by data services and their compositions is one of the key issues that have received little or no consideration, and which is the focus of this chapter.

Motivating Scenario

The Table 4.1 below gives examples of uncertain data services from the eCommerce domain. The service S 1 returns the information of a given product; S 2 returns the products which have been ordered by a given customer; S 3 returns the customers at a given city; S 4 returns the sales representatives along with their phone numbers at a given city. The uncertainty of data services could have dierent origins. A data service may be uncertain because it integrates dierent data sources adopting dierent conventions for naming the same objects set. For example, S 1 provides complete information about products by integrating two Web data sources cdiscount.com, and amazon.com. S 1 joins products from these two sources over the product name. However, the name of the same product may be stored dierently in the two sources, e.g., computer in cdiscount.com versus laptop in amazon.com. Imprecise matches (usually quantied as numbers between 0 and 1) between products in the two sources can be interpreted as the probability the two products match; i.e. S 1 will return for each tuple obtained from the matching, the probability that tuple exists. This type of uncertainty is very common in the Web data integration domain [START_REF] Agrawal | [END_REF][START_REF] Soliman | [END_REF]].

There is a rich literature on record linkage (also known as de-duplication, or merge-purge) [Marian 2011], that oers an excellent collection of techniques for computing matches or probabilities.

The uncertainty associated with S 2 , S 3 and S 4 could come from the fact that the data sources accessed (or integrated) by these services contain conicting information about customers and sales representatives (e.g., conicting addresses for the same custumer, dierent phone numbers for the same representative, etc.). This is especially common in applications like sensor networks [Tatbul 2004] and object tracking [Cheng 2004], where the same data source may be fed by dierent sensors, that often report conicting detections indicating several simultaneous locations for the same object. A common approach for storing such sensor data is to produce one record for each of the possible object locations, and assign a condence degree to each record. Other common uncertainty sources may include privacy concerns [Fung 2012], where data items are deliberately made imprecise (e.g., the salaries are anonymized), or left out altogether; imprecise data production or collection methods as in the scientic data exploration domain [Buneman 2006] (e.g., imprecise scientic experiments, unreliable instruments, etc.). ($p, ?pr, ?sh, ?cl) Returns informations (price pr, shape sh, color cl ) about a given product p Uncertain S 2 ($c, ?p, ?pr)

Returns the products p along their prices pr which have been ordered by a given customer c.

Uncertain S 3 ($a, ?c, ?j)

Returns the customers c and their jobs j at a given city a. Uncertain S 4 ($a, ?s, ?t)

Returns sales representatives s along with their phone t numbers at a given city a. Uncertain

The uncertainty associated with uncertain services must be explicitly modeled and described in order to ensure that service consumers can understand and in-terpret correctly the data returned by services and use them in the right way.

For example, the consumer of S 2 should be advised about the probability of each returned tuple so that he can make the right product choice. The need for a clear uncertainty model for uncertain services is further exacerbated when they are composed to provide value-added services. For example, S 2 and S 3 can be composed to nd the most ordered products in a given city. First, S 3 is invoked with the desired city (e.g., Lyon). Then, the obtained customers are used to invoke S 2 to obtain the ordered products. S 1 can be also included to retrieve the products' prices. If we neglect the probability metadata of the composition's outputs, we risk to select the products that appear rst in the output list, and which may not be the most probable products. The importance of considering the uncertainty of output data becomes clearer when the output includes a sheer number of products where the most probable ones may not appear rst, leading users to miss the most interesting results among the complete results list. The uncertainty of each of these services needs to be explicitly dened to be able to aggregate their returned data pieces and compute the probabilities of the composition's outputted results (which could be used for ranking these results).

Challenges

Handling the uncertainty associated with data services may involves several challenges:

• Uncertain data services modeling: The uncertainty associated with the outputs returned by a data service should be explicitly modeled, as it is necessary for the interpretation of these outputs by service consumers. The proposed modeling should be compatible with the current Web service standards (e.g., WSDL, SOAP, etc.), as they are widely adopted by Web service development community.

• Uncertain data service invocation: We need to dene a generic invocation operator which will be able to invoke an uncertain data service and retrieve the condence degree of its output. An uncertain service may be invoked with both certain and uncertain input data; in the latter case, the invocation operator should take into account the uncertainty of input to compute the condence degree of output.

• Uncertain data services composition: The conventional service composition model (i.e., the composition algebra and its implementations by dierent composition execution engines) should be extended to allow for computing the probabilities of the composition's outputs to help users understand and interpret them correctly. An uncertain service should be compose-able with normal and uncertain services alike; i.e., a composition that is unaware of uncertainty should be able to use uncertain services without aecting its normal execution.

Contributions

We summarize below our contributions in this chapter:

• A probabilistic model for uncertain Data services : we propose a probabilistic approach to model the uncertainty of outputs returned by an uncertain data service. We extend the service description standard WSDL to accommodate the probabilities of outputs.

• A probability-aware data service invocation: We propose an invocation model which allows the invocation of data services with certain and uncertain input. In the rst case, the invocation process retrieves the probabilities of the service's outputs. In the second, the invocation process computes the probabilities of returned results based on the probabilities returned by the service and the probability of the input.

• A composition model for uncertain data services : We dene the semantics of uncertain service composition based on the possible world theory. We propose a probability-aware composition algebra to compute the probabilities of the composition outputs.

The rest of the chapter is organized as follows. In Section 2, we present our probabilistic models for uncertain data services and their invocation. We dene our proposed composition model in Section 3 and we explain our approach for the BID services in Section 4. Finally we conclude the chapter in Section 5.

Uncertain Data Services: A Probabilistic Model 4.2.1 A description model for uncertain data services

Data uncertainty management has received a considerable attention from the database research community over the last decade. Two main challenges were addressed: uncertainty modeling and query processing over uncertain data. Dierent approaches were proposed to model data uncertainty [Sadri 1991[START_REF] Abiteboul | [END_REF][START_REF] Bosc | [END_REF]]. Among these models, the probabilistic and the possibilistic models are the most adopted due to their simplicity. In the probabilistic data model, data uncertainty is modeled as a probability distribution over the possible tuple/attribute values [Marian 2011[START_REF] Abiteboul | [END_REF]; i.e., each possible tuple/attribute value is assigned a degree of condence, quantifying its probability. The probabilistic model is a numerical model that relies on an additive assumption and adopts the possible worlds semantics, where an uncertain relation is viewed as a set of possible instances (worlds). Each instance represents the real world with a condence degree. The structure of these worlds could be governed by underlying generation rules (e.g., mutual exclusion of tuples that represent the same real-world entity). In the possibilistic data model, each possible tuple/attribute value is assigned a (normalized) degree representing how possible?is that value. The possibilistic model is a qualitative, hence a non-additive, uncertainty model.

In this section we give our model for representing uncertain data services.

Our model adopts a probabilistic approach to describe the uncertainty associated with data services. In this dissertation we consider that an uncertain service has certain semantic and behavior, only the services can return uncertain results. An

• I O p S P • p O p 0 1 I p = 1
S p 4 ($city, ?sales, ?phone)

t 1 t 2 t 3
probability p representing the degree of condence. These probabilities are not part of the output parameters, they are simply metadata provided by the service provider.

The semantics of uncertain data service can be explained based on the possible worlds theory [Sadri 1991]. The probabilistic output tuples returned by the invocation can be interpreted as a set of possible worlds (P W 1 ,..., P W n ) and each possible world P W i contains certain tuples and has a probability p P W i which is dependent on its contained tuples. For example, assuming that the output tuples t 1 , t 2 and t 3 returned by S p 4 in Fig. 4.1 are independent probabilistic events, then we obtain eight possible worlds corresponding to the dierent combinations of tuples. For instance the probability of P W 3 is 0.3 * 0.5 * (1 -(0.4)) = 0.09, since it contains the tuples t 1 and t 3 and does not contain t 2 .

Note that the interpretation of the probabilistic outputs depends on how these outputs are correlated because possible worlds' contents and probabilities depend on that correlation. In this present work we suppose that all returned outputs are independent events.

An Invocation Model For Uncertain Data Services

In this section we analyze the impact of data uncertainty on the service invocation process. Our objective is to dene the invocation functionality and give insights on how its semantics should be extended to deal with uncertainty.

Notations. Let S p be an uncertain data service, I denote certain inputs to the invocation process; I p denote uncertain inputs: I p =< I, P >, where P denotes the probability of I. Let O denote certain outputs of the invocation process; O p denote uncertain outputs: O p =<O, P >, where P denotes the probability of O.

Based on the input type (whether it is certain I or uncertain one I p ) we identify the following two invocation classes: conventional invocation and probabilistic invocation. If the input is certain I the invocation is conventional and O p represents the set of returned outputs {O p

1 =< O 1 , P 1 >, ..., O p n =< O n , P n >}.
The probabilistic invocation refers to the service invocation with uncertain inputs I p . We use foundations of possible worlds theory to explain the semantics of the probabilistic

I p = i, i =< customer = "c 1 ", p i = 0.4 > I p {P W 1 , P W 2 } P W 1 = {i} P W 2 = {∅} P W 1 i p P W 1 = P rob(i) = 0.4 P W 2 i p P W 2 = 1 -P rob(i) = 0.6 o p o = p P W 1 * p P W 11 = 0.4 * 0.3 = 0.12 P W 11 o P W 11 = {o}, P W 12 = {∅} Invoke p (S p , I p ) = {(O 1 , P O 1 = P 1 * P i ), ..., (O n , P On = P n * P i )} (1)
position systems [Barhamgi 2013b[START_REF] Srivastava | [END_REF]] don't address the problem of uncertainty. Data uncertainty is an important issue that must be taken into account in composition processes to allow for the right interpretation of returned results. In the following we dene the semantics of uncertain services composition.

Composition Semantics

In the case of uncertain data services, the interpretation of a composition is a bit harder that of deterministic services. In this case, we are interested not only in computing the composition's results, but also in their probabilities. For example, assume that the uncertain services S p 2 and S p 3 are involved in a composition to nd the products ordered in Lyon": The table in Fig. 4.3(b) shows the results returned by S p 3 (along with their probabilities) when invoked with the value Lyon. The tables (c) and (d) in Fig. 4.3 give the results returned by S p 2 when invoked with the values c1 and c2, respectively. S p 3 returns the tuples t 1 , t 2 , and t 3 which are independent. These tuples are interpreted into eight possible worlds [Sadri 1991] and the table in Fig. 4.3(c) shows these worlds with their probabilities. Notice that tuples in each world are considered as certain. For example, the world P W 1 includes the tuples: t 1 , t 2 , and t 3 ; and hence the probability of that world is computed as follows: P P W 1 = prob(t1) * prob(t2) * prob(t3) = 0.3 * 0.4 * 0.5 = 0.06 (we assume that the returned tuples are independent); the probability of P W 2 is P P W 2 = prob(t1) * prob(t2) * (1 -prob(t3)) = 0.3 * 0.4 * (1 -0.5) = 0.06, since that world contains the tuples t 1 and t 2 and does not contain t 3 . Fig. 4.3(e) shows the execution plan for the composition in Fig. 4.3(a). For each of the possible worlds corresponding to the results returned by S p 3 (denoted by I p in the plan in Fig. 4.3(e)), there is an interpretation of the composition, each interpretation has a probability and is represented by a branch in the composition plan. Note that inside each branch we may use the conventional data processing operators (i.e., Projection, Selection, Join, etc.) as exchanged tuples are certain tuples. In each branch, S p 2 is invoked with the tuples of the corresponding world. The invocation operator computes the probability of the outputted tuples by multiplying the probability of the corresponding world with that of the data returned by S p 2 . For instance, the probability of the tuple l 1 outputted (in the rst branch) is computed as follows: I p .P P W 1 * prob(S p 2 .l1) = 0.06 * 0.3 = 0.018. The results returned by the invocation of S p 2 in each branch are probabilistic (and are denoted by p ), and are interpreted as a set of possible worlds. For example, the results L p = l 1 , l 2 , l 3 returned by S p 2 in the rst branch have eight possible worlds. The probabilities of these worlds depend on involved tuples and the considered world of I p . For example, the probability of the rst world in the rst branch is computed as follows:

P = I p .P P W 1 * L p .P P W 1 = 0.06 * [prob(l1) * prob(l2) * prob(l3)] = 0.06 * [0.3 * 0.4 * 0.6] = 0.06 * 0.072.
That is, a composition corresponds to a set of possible compositions. For instance, in our example we have two services, each has eight possible worlds, hence n = 8 * 8 = 64. Each of these compositions may return results dierent from the other compositions. The same tuple may exist in multiple worlds; for instance the tuple < p1 > exists in the rst six worlds of the rst branch. The operator Aggregation at the end of each branch computes the probability of each tuple by summing the probabilities of involved worlds. For example, the probability of the tuple < p1 > at the end of rst branch is computed as follows: p(p1) = P (L p .P W i ) * P (I p .P W 1 ) = (0.072 + 0.048 + 0.108 + 0.072 + 0.168 + 0.112) * 0.06 = 0.0348

The nal aggregation operator computes the probability of tuples across the different worlds corresponding to I p (i.e., across the dierent branches). The - nal probability of p1 added all probabilities where p1 exists so p1 = 0.3238 = 0.0348 + 0.027 + 0.027 + 0.0812 + .0.027 + .0.063 + 0.056. and c= "c2" (d): The tuples returned by S 2 ($c,?p,?pr) when invoked with c= "c1" A composition may include multiple probabilistic Web services. When the outputs of these services are aggregated, the probabilities of the obtained results should be computed. These probabilities may be important for many reasons: computing the best results, to assess the quality of results, to take the right decisions, etc.

Π(c) Π(c) Π(c) Π(c) Π(c) Π(c) Π(c)
Computing nal results' probabilities requires exploring dierent combinations of possible worlds to assess the composition. Computing all possible worlds after the invocation of each service is ineective as the number of these worlds is exponential with the number of tuples.

To solve this problem, we opt for an extensional approach (i.e., an approach that does not require the materialization of the possible worlds) and we dene a set of composition operators that are needed to formulate the orchestration plans of services compositions [START_REF] Yu | [END_REF]] including probabilistic Web services. These operators assume that the processed tuples are uncorrelated (i.e., the processed tuples are independent from each others).

• Invoke p (S p , I p ): The denition of this operator was given in Section 2.

• Aggregate p (I p 1 , ..., I p n , a):

Let I p i
(where 1 ≤ i ≤ n) be a vector of probabilistic tuples outputted by a given service Si, and aasetof attributes; theaggregateoperatorjoinsthevectorsI p 1 ,...,I p n over a. The probability of an aggregated tuple t is computed as follows: p(t) = p t I 1 * , ..., p t I i * , ...., p t I n , where t I i 1 ≤ i ≤ n are the tuples being aggregated from Ii(1 ≤ i ≤ n).

• P roject P (I p i , a): Let I p i be a vector of probabilistic tuples, and a a set of attributes. The project operator projects the vector over a and the probability of a tuple t in the outputted set is computed as follows:

prob(t) = 1 -t : a (t )=t (1 -prob(t ))
• Select(I p , c): Let c be a set of conditions; The probability of a tuple t in the outputted set is computed as follows:

prob(t) = ⎧ ⎪ ⎪ ⎨ ⎪ ⎪ ⎩ prob(t) if c = true 0 if c = false S p 3 S p 2 P roject p p (Invoke(S p 2 , Invoke(S p 3 , "Lyon"))) 0.3238 #P -complete ?j doctor ?c c2 c1 t1 t2 t3
The tuples returned by S 3 ("Lyon", c, j)

The tuples returned by S 2 P ($c,?p,?pr)

Plan: Project p (Invoke(S 2 , Invoke(S 3 ,"Lyon")))
Invoke(S 2 , Invoke(S 3 ,"Lyon")) Project p (Invoke(S 2 , Invoke(S 3 ,"Lyon")))

Query: Q(p):-S 3 ("Lyon", c, j) S 2 (c, p, pr)

S p 4 S p 4 < " Lyon" > (K; A; P ) K = {K 1 , ..., K n } A = {A 1 , ..., A n } S p i S p S p 4 ($city, ?s, ?phone) K = {s} A = {phone} O p = (s, phone) S p 4 < Lyon > S p 4 < P aris > S p 4 < Lyon > o 11 o 12 S p
Invoke p (S p disjoint , I p j ) = disj j=1:n (S p , I p j ) ( 2 ) disj (o i , P o i ) p o i = P l j |l j = o i ∧ l j ∈ {(S p , I p 1 ), ..., (S p , I p n )} Invoke p (S p Indep , I p j ) = Indep j=1:n (S p , I p j ) ( 3 )
Indep

p o i = 1 -(1 -p l j )(1 -p l k ) o i = l j , l k ... l j , l k ... ∈ {(S p , I p 1 ), ..., (S p , I p n )} Invoke p (S p BID , I p 1 , ..., I p n ) = BID j=1:n (S p , I p j ) ( 4

S p

3 ($a, ?c, ?j) S p 2 ($c, ?p, ?pr) Q 1

Introduction

A composition may accept dierent execution composition plans expressed all with the probabilistic algebra. Not all of these plans compute correctly the probabilities of outputs. The objective of this chapter is to dene the conditions under which a plan returns the correct probabilities, and in which case we call it a safe composition plan.

Motivating scenario

Assume we have two data services: S 1 ($city; ?school; ?zip; ?reputation) returns the schools (along with their zip codes and reputations) in a given city -input parameters are proceeded by $ and the output ones by ?. S 2 ($school; ?course; ?teacher) returns courses (and their teachers) that are taught at a given school. These services are uncertain services as they integrate open Web databases (e.g., S 2 integrates open databases from nces:ed:gov 1 and psk12:com ) 2 . Assume a student, Alice, is looking for the best math courses taught in her city, Washington. Alice expects that the best math courses are those taught in highly rated schools. Therefore, she invokes S 1 with the value city = "DC", then she selects highly rated schools, and invokes S 2 with their names to get their proposed math courses. The mashup shown in gure 5.1 implements the following query:

Q 1 (course, school, teacher) : -S 1 ("DC", ?school, ?zip, "high"), S 2 ($school, ?course, ?teacher) We assume in this example that S 1 and S 2 could return, in addition to their outputs, metadata information representing the probabilities of their returned uncertain output data. For example, S 1 returns two schools Lincoln" and Heritage" with dierent combinations of their reputation and zip code, each combination is associated with a probability. Now, if the mashup plan has computed its output with ignoring the probability metadata, then the order of outputted math courses

Data Mashup Plan

Q1: Find the best Math courses and their teachers in DC city.

correctly. On the other hand, the plans of hard queries are all unsafe. Hard queries are often evaluated using some intensional probabilistic inference techniques which are known to be hard and quite inecient.

Contribution

In this chapter, we propose some conditions to check if the composition plan is safe. The main contributions of this chapter are as follows:

• We dene the notion of a safe orchestration plan which is a query plan P that can be evaluated using extensional semantics on a one instance; in contrast, the standard denition of a safe plan is one where the extensional semantics is correct on any instance.

• We dene a safe orchestration query plan in the case of independent tuples.

We propose a set of conditions to satisfy the safety of the plan.

• We dene a safe orchestration query plan in the case of BID tuples.

The remainder of this chapter is organized as follows. In Section 2, we present a background of safe plan. In section 3 we introduce our safe composition for data services with independent tuples and in the section 4 we show the safe composition for BID services. Finally, in section 4, we summarize our contributions and conclude.

Background

A probabilistic service S p = (S, p) represents a probability distribution over outputs set of S. The outputs of S are modeled as possible worlds also called instances [START_REF] Bosc | [END_REF]]. The evaluation of a Boolean query q on a probabilistic set D of probabilistic services is dened by Pr(q), which is the sum of probabilities of those instances of D that satisfy q. In this thesis we study ecient techniques for evaluating q.

Suppose the input relations to an operator are independent. Then, we dene the extensional semantics of the relational operators as follows: Denition 1. Let P be a query plan and D a probabilistic database instance.

A plan P is called safe if its extensional semantics is equal to the possible worlds semantics.

Denition 2. [Jha 2010] dene safe plan as follows:

Consider a probabilistic database instance D and a query plan P . Let o be an operator in P . A set T of input tuples to o is called set of oending tuples if o becomes safe after removing the tuples in T .

The set of oending tuples do not necessarily come from the database instance; they could also be intermediate tuples generated during the query plan.

So many tuples in the database instance, that make the query unsafe, may actually correspond to just one oending tuple for the query plan. Note that a safe plan has no oending tuples and the output of any plan is an expression with symbols from only the oending tuples. Hence the number of oending tuples is a measure of how safe/unsafe a plan really is for a given database instance.

Safe composition for data services with independent tuples

In this section we focus on the issue of the orchestration issue of p-services participating in a composition. We show, through examples, that not all composition plans give correct probabilities. We dene then a set of criteria under which a composition plan computes the correct probabilities. We assume that the services to be composed are already identied (either automatically by one of the systems in [START_REF] Benaouret | [END_REF][START_REF] Srivastava | [END_REF]][Barhamgi 2013a[START_REF] Sabesan | [END_REF]], or manually by users). All compositions considered in our discussion answer Select-Project-Join (SPJ) queries.

Example

Consider the services S p 1 ($city; ?school; ?zip; ?reputation) and S p 2 ($school; ?course; ?teacher)whose invocation results are shown in gure.5.2. Assume a query Q 1 for the best math courses in Washington: Q 1 (x; y; z) : -S p 1 ("DC"; ?y; ?l; "high")S p 2 ($y; ?x; ?z)

Composition interpretation based on the possible semantics : The composition of S p 1 and S p 2 to answer Q 1 can be interpreted as follows (gure.5.2(B)): S p 1 is invoked with the value DC" and returned the tuples set {t 1 , t 2 , t 3 }. Only the tuples with a high value for the reputation attribute are retained. This set is interpreted into 8 possible worlds, each world corresponds to a branch in gure.5.2(B).

The probability of each world is calculated based on the probabilities of the tuples belonging to this world. For example

P P W 1 = t 3 = (1 -P t 1 ) * (1 -P t 2 ) * P t 3 =
(1-0.2)*(1-0.7)*0.1=0.8*0.3*0.1=0.024.

Then, we project the results on school" attribute and we invoke the service S 2 .

For each world we generate possible worlds. For example for the possible world P W 1 we generate 2 possible worlds: {P W 11 = (o 3 ), P W 12 = (∅)}.

Finally, we calculate the math teachers' probabilities by the sum of the probabil-

Q 1 S p 1 S p 2 Q 2 S p 1 S p 2 Q 2 Q 2 can
be expressed as that of Q 1 except we project the nal result on z which returns only one tuple o =< Bob, 0.495 > where the probability of o is computed as follows:prob(o) = 1 ( 1 -0.228) * (1 -0.304) * (1 -0.06) = 0.495. This probability is not equal to the probability obtained using the possible world semantics (0.3724). This observation is not surprising as it is already known in the literature that not all queries accept an execution plan (called safe plan) that could correctly compute the probabilities [START_REF] Dalvi | [END_REF]]. Such queries are called hard queries as they have a #P-complete data complexity under probabilistic semantics [START_REF] Dalvi | [END_REF]]. However, the hard queries given in the literature do not commonly arise in practice.

For example, only 20% of the TPC/H benchmark queries (www.tpc.org) fall in this category.

Criteria for safe composition plans

A safe composition plan is guaranteed to compute all output probabilities correctly.

We dene bellow a set of conditions under which a composition plan is safe. We call such compositions as safe compositions. We start by dening the dependency graph of a composition.

Denition. (Dependency Graph G):

The dependency graph G of a composition is a directed acyclic graph in which nodes correspond to services and edges correspond to dependency constraints between component services. We say that there is a dependency constraint between two services S i and S j (S j depends on S i ) if one of S i 's output parameters is an input parameter of S j . Safe composition plan p. We say that p is safe if:

1. p respects G, 2. all edges in p are joins that involve the primary key of at least one probabilistic service, 3. p is tree, 4. a probabilistic service appears in p at most once, 5. the primary keys of services that are leaves in p appear at the p's output.

Examples.

• The plan of Q 1 that is shown in (E) satises our conditions thus it is safe.

The one of Q 2 violates the condition 5, thus is unsafe.

• We suppose that we have another probabilistic service S p 3 which returns students in a given city along their level. Assume a query Q 3 to know the best math teachers of the level 7 in Lincoln" school. To answer Q 3 , S p 2 and S p 3 can be composed and the plan is as follows: P: P roject p teacher (Invoke p (S p 2 ("DC")), Invoke p (S p 3 ("NY "))).

However, the two services don't have any dependency so moreover the rst condition is violated that's why the plan P is unsafe.

• Assume a query Q 3 to know the best schools in Washington and New York and the plan is as follows:

P : P roject p school (select p [Invoke p (S p 1 ("DC"))] reputation=high [Invoke p (S p 1 ("NY "))] reputation=high ).
This plan P is unsafe because the service S p 1 appears twice so it violates the fourth condition.

• Assume a query Q 4 to know the students taking courses with the best math teachers. Q 4 can be expressed as that of Q 1 except we invoke in the last the service S p 3 but in this case the plan will not be safe because it violates the rst and the last condition.

• We suppose that the service S p 1 returns another attribute which is address" we have another probabilistic service S p 4 which returns apartments for rent along their price in a given address. Assume a query Q 5 to know the apartments which their price lower than 40000$ and near to the best school in NY". To answer Q 5 we opt for the following plan:

P : P roject p Apart [Aggregate p [Select p (Invoke p (S p 1 ("NY ")) reputation=high , Select p (Invoke p (S p 4 ("Broklyn"))) price<40000 ]]
We notice that P violates the condition 5 thus it is unsafe.

Safe composition for data services with BID tuples

In this section we focus on the orchestration issue of p-services with BID tuples.

We show, through the same example of the previous section, that even in the case of BID tuples not all composition plans give correct probabilities. We dene then a set of criteria under which a composition plan computes the correct probabilities in this case.

The composition of S p 1 and S p 2 to answer Q 1 can be interpreted as follows (gure.5.3(B)): S p 1 is invoked with the value DC" and returned the tuples set {t 1 , t 2 , t 3 , t 4 }. This set is interpreted into 6 possible worlds. Figure.5.3 (C) shows a plan for Q 1 , S p 1 is invoked with the deterministic value (city = DC") and returns a BID table. Only the tuples with high reputation are retained. These tuples are then projected on the school attribute, and the results are used to invoke S p 2 . The gure shows also how we compute the probabilities of both intermediate and the output tuples. The probabilities of output results are correct as they are equal to those obtained using the possible worlds semantics (gure.5.3 (D)).

For the query Q 2 , the same as that of independent tuples, the probability accord- ing to the plan p z Q 1 is equal to 0.7746 which is dierent from the probability obtained using the possible world semantics in 5.3 (E). We can check the same set of conditions dened for the independent tuples to check if an orchestration of

z x Math10 Math12 Q 1 Q 2 Q 1 Q 2 6.

Introduction

This chapter is devoted to the implementation and performance study of our proposed approach for uncertain data web services composition. We implemented our dierent techniques and applied them to the real-estate and e-commerce domains. We provide in this chapter a performance study of our composition framework.

The remainder of this chapter is organized as follows. In Section 2, we present the architecture of our implemented system. In section 3 we provide the technical environment and the experimental results. Finally, in section 4, we summarize our contributions and conclude the chapter.

Prototype

Architecture

The architecture of our implemented system for querying and composing uncertain data services is shown in Figure 6.1. The architecture is organized into four layers. The rst layer contains a set of Oracle/MySQL databases that store the data. The second layer includes a set of proprietary applications developed in Java; each application accesses databases from the rst layer (i.e. it executes parameterized queries over the databases). These proprietary applications are exported as uncertain data web services to the system. These services constitute the third layer. We used the deployment kit bundled with the GlassFish Web server to build and deploy our data Web services over a set of GlassFish Web servers running on top of set of PC machines (running Windows XP).

The description les (i.e. WSDLs) of data Web services in the third layer are annotated with RDF views that describe their semantics from the perspective of RDFS domain ontologies. Annotated description les are published to Web service registries. The upper layer includes a Graphical User Interface (GUI) and our composition system. Users access the system via a GUI implemented using Swing, the widget toolkit for Java. They can submit specic or parameterized queries to the composition system. In the WSDL-S 1 , inputs, outputs and operations can be annotated with concepts from domain ontologies to capture their semantics using the extensibility feature of WSDL. WSDL-S proposal denes a new attribute called modelReference to associate input and output messages and the operations with the corresponding ontological concepts. In our work, we follow the same approach to associate the services' operations with their corresponding RDF views. To do so, for each operation element we dene a new element rdfquery to link each operation with 1 http://www.w3.org/Submission/WSDL-S/ its RDV view. Figure 6.2 shows a part of a WSDL le annotated with RDF views.

<?xml version="1.0" encoding="UTF-8"?> <S:Envelope xmlns:S="http://schemas.xmlsoap.org/soap/envelope/"> <S:Body> <ns2:outputMessage xmlns:ns2="http://org.me/"> <tuple probability ="0.8" grade="0.76" key="S"> <Product>p1</Product> <S>s1</S> <r>good</r> <t>45000$</t> <a>Lyon</a> </tuple> </ns2:outputMessage> </S:Body> </S:Envelope> Probability and grade inclusion in Web service standards. We extended the Web service standards (WSDL, SOAP) to take into account our model of uncertain services. WSDL 2.0 is the last ocial W3C recommendation for Web services description.

WSDL 2.0 denes several extensibility elements that can be used to annotate the service descriptions les with metadata and semantic information.

These elements can either be added to attributes or to XML elements of the service description, the main requirement being that the extensibility elements are dened in their own namespace. We exploited these elements of WSDL2.0 and dened the following three attributes on the output message elements: probability" to specify the probability degree associated with each output element (i.e., tuple), grade" to dene the matching degree relative to users' preferences and Key" to specify that an output parameter plays the role of an identier (i.e. a primary key) -recall that identier attributes are needed for computing the correct plan of a composition. Figure 6.3 shows an example of a SOAP message annotated with the dierent attributes (grade", probability", key").

Service Invocation

The composition system [Barhamgi 2013b[START_REF] Barhamghi | [END_REF]] relies on a standard Java API for Web services invocation JAX-WS (jax-ws.java.net). This Java API allows SOA application developers to call and consume Web services in their applications. Specically, the Dispatch interface (javax.xml.ws.Dispatch) allows invoking a service by constructing/reading the service's input/output (XML) messages. It enables the developers to work on the XML message level by either constructing the invocation messages manually using the desired XML API (e.g. JDOM, etc), or by using the Java Architecture for XML Binding (JAXP jaxb.java.net/) to translate between XML messages and internal Java objects that constitute the SOA application. Fig. 6.4 shows how we extended this API to implement our invocation model. The input I p has the form of a Java object (the probability is simply a led in the corresponding Java class) and is the argument of the whole invocation process. Then, an input XML invocation message will be constructed; this process can be done manually using an XML API or automatically based on JAXB Java/XML mappings. The obtained message is then encapsulated by an SOAP envelope and sent to the Web service. Then, the SOAP message returned by the service is de-encapsulated to extract the output XML message. The latter is then read; if the output XML message is read manually by an XML API, the code should then read the value of the P robability and grade attributes in the WSDL service description, otherwise the P robability (grade) attribute should be mapped to the probability (grade) eld of the Java object by the JAXB Java/XML mappings. Finally, the Probability (grade) will be updated by taking into account the probability (grade) of the input.

Query formulation

The Interactive Query Formulator helps users specify their RDF queries (SPARQL queries) over the mediated ontology in an interactive manner. Users formulate their queries over domain ontologies in SPARQL query language. implemented by a Java package called execution that contains the following main classes:

• Composition: This class represents the composition plan.

• InvocationThread: This class allows invoking a service within an independent thread.

• JoinThread : This class allows to join the outputs of two or more data services. The join is done within an Independent thread.

• UnionThread : This class allows to combine the outputs of multiple similar web services and eliminates data redundancy.

• ProjectionThread : This class allows to project the desired attributes from a data tuple.

• SelectionThread : This class allows ltering tuples based on data values.

6.3 Implementation and experimental results

Technical environment

The development phase is divided into two parts. In the rst, we used two types of web services: those physically deployed on an server application and those created locally. To develop an approach based on Web services, dierent Java middleware exist such as Aparche Axis, JBoss and Glasssh with the features and benets of their own. We chose Glasssh for the following reasons:

• Development environment and tools are fully integrated in the NetBeans IDE.

• Compliance with specications Web services and interoperability standards.

• Open-source project with a strong industrial support from both Sun Microsystems and Microsoft.

Thereafter, we dene the development environment and libraries needed to implement our framework:

• IDE editor: Netbeans 6.9.

• Processes Intel (R) Core (TM) i5 -4GB RAM.

• Web services platform: Glasssh 3.

• ava Web services API: JAX-WS.

6.3.2 Preference-Aware Query Model Figure 6.5: The preference query formulator interface To evaluate and validate our approach, we implemented all of the components shown in gure6.1 in Java. The ranking-aware composition execution engine was implemented to allow for both scalar and vector grades computations and with any of the three T Z , T P , and T L norms.

We conducted a series of experiments to evaluate the ecacy of our approach. The experiments covered many queries from the real estate domain with a rich set of fuzzy preferences over a set of services returning synthetic data about Apartments, Lands, Restaurants, etc. Our experiments shown that the overhead incurred by computing the rankings is negligible compared to the time necessary to execute the same generated compositions without any ranking at all. In addition, the returned top-k tuples were always correct, proving the soundness of our proposed operators. Figure 6.5 shows the preference query formulator interface. The user uses this interface to enter his/her sparql query with fuzzy preferences. This query is formulated over an existing ontology. The user can execute the query and chose any of the displayed compositions. On the left-hand side, the panel Ontology presents a tree-like view of domain ontology, the panel Services presents the services stored inside service registries. The Query Editor on the right-left side is space where users edit their queries. SPARQL savvy users can express their queries directly in the Query Editor of our interface.

Fuzzy terms are those stored in the fuzzy terms knowledge base of our system.

Users can edit and test them via the interface in gure 6.6 to identify the relevant fuzzy terms. Users can also dene their own fuzzy terms. The composition execution plan is then displayed on gure 6.7 and the user is allowed to choose an execution strategy. If the user wants to aggregate the grades of its fuzzy preferences, he/she chooses the scalar grades computing; otherwise if he/she wants to keep an eye on the grades of all of its fuzzy preferences, he/she chooses the vector grades computing. The user has also to set his/her strategy: optimistic (T Z norm), reinforcement (T P norm), and pessimistic (T L norm). In gure 6.9, results are ranked according to their vectors of grades (each grade corresponds to a degree of satisfaction of a fuzzy user preference). To do so, we make use of the leximin ordering which leads to a total order. This ordering is borrowed from the multicriteria decision eld [Dubois 1990]. Figure 6.8: The scalar ranked results panel In case of the user is not satised by the obtained query results, he/she can choose another service composition and execute it. In case of empty (resp. too few) results, users can relax (by introducing some tolerance) their fuzzy constraints present in the initial query. The relaxation operation allows for enlarging the support of the membership functions associated with each constraint, thus making the query less selective. It is worthy to note that this operation requires to re-execute the grades computation step. For example, relaxing the aordable constraint of Q will return more results: some of the tuples previously ranked to 0 in scalar grades, or ranked to 0 in all dimensions in vector grades. We implemented the operators of our probability-aware composition algebra (dened in Section 3.2) within the composition engine of [Barhamgi 2013b[START_REF] Barhamghi | [END_REF]] and extended that engine with our algorithm for computing the correct composition execution plan. Figure 6.10 shows the user interface to our extended service composition system. The panel (a) shows domain ontology. The user edits his SPARQL query in the panel b. Panels (d) the obtained results along with their probabilities. Figure 6.10 (c) shows the composition plans and indicates whether the plan is safe or not.

Experimental results

Composition system with fuzzy preferences. Due to the limited availability of real data services, we implemented a Web service generator. The generator takes as input a set of (real-life) model data services (each representing a class of services) and their associated fuzzy constraints and produces for each model service a set of synthetic data services and their associated synthetic fuzzy constraints. The generated data services satisfy some fuzzy constraints on the attributes of the implemented model service. We measured the average execution time required to solve the composition problem as the number of data services per class increases. We varied the number of data services per class from 200 to 1000. The results of this experiment are presented in Figure . The results show that our framework can handle hundreds of services in a reasonable time. The results of this experiment are presented in gure 6.11 (a). We measured the average execution time required to solve the composition problem as the number of service classes increases. We varied the classes number from 1 to 6. The results of this experiment in gure 6.11 (b). We also made a comparison at runtime level between the normal composition and composition with grades calculation and we noticed that the dierence is minimal. It becomes apparent that the execution time dedicated to the calculation of grade is negligible. Figure 6.12 shows the results. Composition system with uncertainty. We conducted a series of experiments for two main objectives. First, we wanted to verify how much of reallife service compositions accept correct composition execution plans. Second, we wanted to evaluate the cost incurred by the calculation of probabilities in our composition algebra (relative to the initial composition algebra of the system in [START_REF] Barhamghi | [END_REF]. For this purpose, we have implemented web services on top of an uncertain database storing synthetic data about products, consumers, sales representatives, etc. This database has a size of 1000MB and simulates the data of the TPC-H benchmark (www.tpc.org). The obtained initial results gave the following facts. First, 8 out of 10 real life compositions (i.e., queries) accepted correct execution plans, thus computing the correct probabilities for results. The considered compositions answer queries that are considered as common by the TPC-H benchmark. Second, for our second objective, we measured the execution times for a composition with and without the calculation of probabilities. The results in gure 6.13 show that the time incurred by the calculation of probabilities is negligible.

Conclusion

In this chapter, we have presented briey the system we have implemented to evaluate our approach for data service composition with uncertainty. We also conducted a performance analysis on a wide data set to assess the eciency of our proposal. The results showed that our system can handle hundreds of data Web services in a reasonable time even with grades and probabilities calculation.

In this chapter, we summarize the results of our dissertation and discuss future research directions for uncertain data Web service composition.

Conclusions

In this dissertation, we addressed the uncertainty issues of data Web services and their composition. First, we proposed an approach to answer preferences queries over data Web services. Our approach allows us to improve the descriptions of data services by associating them with fuzzy constraints that better characterize their accessed data. Second, we addressed the uncertainty that may be associated with the services' accessed data by proposing a probabilistic modelling for services.

This dissertation covers the dierent aspects of the above problem, starting from modelling uncertain data services, services selection and composition, to ranking the output results of compositions. We summarize below our major contributions:

• Data services composition with user fuzzy preferences. We presented an approach for composing Web services while taking into account the user's fuzzy preferences. We proposed a model for data services based on RDF views over domain ontologies. Our model characterizes also the service's accessed data with fuzzy constraints. In our approach, services that match the best with users' preferences (which are also modelled as fuzzy constraints), are selected, then orchestrated within a composition plan that better answers the fuzzy query. We proposed an algebra to orchestrate the selected data services. The proposed algebra ranks the returned results based on their relevance to user's fuzzy preferences.

• A probabilistic model for uncertain data services We proposed a probabilistic approach to model the uncertainty of the outputs returned by an uncertain data service. The model assumes that an uncertain data service has certain semantics and behaviour. Only its returned results are uncertain. We proposed an invocation model which allows the invocation of data services with certain and uncertain input. In the rst case, the invocation process retrieves the probabilities of the service's outputs. In the second, the invocation process computes the probabilities of returned results based on the probabilities returned by the service and the probability of the input.

• A composition model for uncertain data services. We dened the semantics of uncertain service composition based on the possible world theory [START_REF] Bosc | [END_REF]]. Computing the probabilities of a composition's output based on the possible world theory is inecient as the number of the possible worlds is exponential with the number of tuples. Thus, we opted for an extensional approach and proposed a probability-aware composition algebra to compute the probabilities of the composition outputs. These probabilities are important for computing the best results, assessing the quality of results, taking the right decisions, etc.

• Safe orchestration plan. We showed that not all composition plans compute correctly the output probabilities. We studied through examples the safety of orchestration plans in two cases: independent tuples and BID tuples. Moreover, we proposed a set of conditions that should be met to verify the plan's safety in these two cases.

• Implementation and performance study. We presented the system we have implemented to evaluate our approach for data service composition under uncertainty. We also conducted a performance analysis on a wide data set to assess the eciency of our proposal. The results showed that our system can handle hundreds of data Web services in a reasonable time even with grades and probabilities calculation.

Future works

This dissertation leads to various fertile grounds for future researches. We identify the following main directions for future works:

• Probability-aware optimization of services composition A composition of data services may accept dierent plans that all respect its dependency graph. Some of these plans compute the correct probabilities while others do not. These plans have dierent evaluation costs that could depend on the order of their dierent operators (e.g., invocations, selections, joins, etc.) as well as on services (e.g., the service selectivity, i.e., the average number of output tuples per one input tuple, its ability to be invoked with blocks of tuples, etc.). More research eorts are needed to study the problem of inferring the best composition plan that still correctly computes the outputs' probabilities. In some applications like Web objects ranking, the most important is to eciently rank objects (based on their probabilities) rather than to know their exact probabilities. Therefore, an unsafe, but ecient, composition plan that would compute approximate probabilities (but precise enough for the ranking purpose), would be sometimes preferred over a safe, but inecient, composition plan. Therefore more research eorts are needed to quantify the probability error bounds that could be produced by an unsafe composition plan. The same research goal is benecial to hard compositions (i.e., compositions that do not accept a safe plan).

• Ranking uncertain output data data services (or their composition) often returns an overwhelming number of results (e.g., data tuples), thus leading data consumers to miss the ones that are most relevant to their needs. Top-k queries are a common approach to report the best k answers (of a query) based on matching the processed tuples to users' preferences. In the context of uncertain data services, the outputted tuples should be ranked based not only on their matching degrees with users' preferences, but also on their probabilities, and the probabilities of correlated intermediate tuples. Tuple

4. 2

 2 Semantics of the probability-aware service invocation . . . . . . . . 4.3 Composition and Execution of uncertain Services . . . . . . . . . . 4.4 Evaluation of P roject p p (Invoke(S p 2 , Invoke(S p 3 , "Lyon"))) . . . . . . 4.5 (A)Sample of results returned by the BID-P service S p 4 (B)The possible worlds of S p 4 < " Lyon" > . . . . . . . . . . . . . . . . . . . . 4.6 Composition and Execution of Uncertain BID Services . . . . . . . 4.7 (A)Invocation of S p 3 ($a, ?c, ?j) and S p 2 ($c, ?p, ?pr)(B)The interpretation of a composition (C)The composition Plan of Q 1 (D)The results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.1 An Example of a composition . . . . . . . . . . . . . . . . . . . . . 5.2 Composition Plan . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.3 BID Composition Plan . . . . . . . . . . . . . . . . . . . . . . . . . 6.1 System architecture . . . . . . . . . . . . . . . . . . . . . . . . . . . 6.2 A Portion of a WSDL File Annotated with RDF Views . . . . . . . 6.3 An example of a SOAP message . . . . . . . . . . . . . . . . . . . . 6.4 Implementation of uncertain Invocation based on the JAX-WS API 1.1 Context

Figure 2 . 2 :

 22 Figure 2.2: Basic fuzzy set types

[

  [START_REF] Truong | On Analyzing and Specifying Concerns for Data as a Service[END_REF][START_REF] Carey | [END_REF]. In[START_REF] Truong | On Analyzing and Specifying Concerns for Data as a Service[END_REF], the authors proposed an XML-based modeling for data Web services along with a platform (called AquaLogic) for building data Web services on top of heterogeneous data sources.[START_REF] Carey | [END_REF]] identied the dierent data quality aspects that a data Web service should specify in its description. Unfortunately, these works do not pay any attention to the uncertainty character that may be associated with the services' accessed data, nor provide eective means for an automatic selection and composition of data Web services.A considerable body of works has addressed the services composition problem[START_REF] Balbiani | [END_REF][START_REF] Wu | [END_REF]]. Most of these works are inspired by the Articial Intelligence (AI) planning techniques; i.e., they are based on (1) transforming the WS composition problem into an AI planning problem and (2) on the use of AI planning techniques to automate the service composition. In[START_REF] Wu | [END_REF]], the authors proposed a Bayesian-based approach to select the services compositions (called sequences) that has the largest probability as the best choice among the possible ones. In[START_REF] Balbiani | [END_REF]], authors model Web services as automata executing actions and formalize the problem of computing Boolean formulas characterizing the conditions required for services to answer the client's request. Unfortunately, these composition approaches take into account only SaaS (Software-as-a-Service) Web services. They are inappropriate for the class of services we are targeting in our work, i.e., the Data Web services, which cannot be modeled as actions to apply the AI planning techniques[START_REF] Barhamghi | [END_REF]].

Figure 3 .

 3 Figure 3.2 gives graphical representations of the RDF Parametrized Views of our sample services. Note that, the current Web service description standards (e.g., WSDL) can be extended straightforwardly with our proposed modeling to data services, as RPVs can be incorporated within the description les (e.g., WSDL) as annotations.

Figure 3 . 4 :

 34 Figure 3.4: The intermediate and nal results along with their grades

4 S

 4 p (I, O p )

  : The tuples returned by S 3 ($a,?c,?j) when invoked with a= "lyon"

Figure 6 . 2 :

 62 Figure 6.2: A Portion of a WSDL File Annotated with RDF Views

Figure 6 . 3 :

 63 Figure 6.3: An example of a SOAP message

Figure 6 . 6 :

 66 Figure 6.6: The fuzzy term editing

Figure 6 . 7 :

 67 Figure 6.7: The execution strategy panel Scalar Ranked results are displayed in gure 6.8. The results are ordered by their aggregated grades.

Figure 6 Figure 6 .

 66 Figure 6.9: The vector ranked results panel

Figure 6 .

 6 Figure 6.11: Performance results

Figure 6 .

 6 Figure 6.12: Performance results: measuring execution time with and without grades calculation

Figure 6 .

 6 Figure 6.13: Performance results: measuring execution time with and without probabilities calculation

  scores and uncertainty interplay to decide the top-k outputted data. The interaction between data uncertainty and the top-k" gives rise to dierent possible interpretations of uncertain top-k queries: (i) the top-k" tuples in the most probable" world; (ii) the most probable top-k" tuples that belong to valid possible world(s); (iii ) the set of most probable top ith" tuples across all possible worlds, where i = 1...k, etc. More research eorts are needed to devise new ecient ranking methods and techniques that implement these interpretations and view the data's probabilities as an important ranking dimension. Eorts are also needed to optimize the execution of compositions neering @orkshop on ystems hevelopment in ye invironmentsAD PHHUF @gited on pge IPFA de glmes PHHQ wrtine de glmesD hidier huoisD iyke rullermeierD renri rde et plorene ädesF Flexibility and fuzzy case-based evaluation in querying. en illustrtion in n experimentl settingF sntF tF of nertintyD puzziness nd unowledgeEfsed ystemsD volF IID pges RQ!TTD PHHQF @gited on pge ISFA de glmes PHHU wrtine de glmesD renri rde et plorene edesF Flexible Querying of Semi-Structured Data: a Fuzzy Set-Based Approach. snternE tionl tournl of sntelligent ystemsD volF UD pges UPQ!UQUD PHHUF @gited on pge ISFA hong PHHW in vun hong et elon F rlevyF Data integration with uncertaintyF vhf tournlD volF IVD pges RTW!SHHD PHHWF @gited on pge PTFA huois IWWH hidier huois et renri rdeF Beyond min agregation in multicriteria decision : (ordered) weighted mean, discri-min, leximin. uluwer ulishersFD pges IVI!IWPD IWWHF @gited on pges S et WIFA huois IWWT hidier huois et renri rdeF Using fuzzy sets in exible querying: Why and how? sn roF of the IWWT orkshop on plexile ueryEenswering ystemsD pges VW!IHQD IWWTF @gited on pge ISFA huois IWWW hidier huoisD renri wF rde et tmes gF fezdekF Fuzzy Sets in Approximate Reasoning and Information Systems. uluwer ulishersD IWWWF @gited on pge RPFA huois PHHH hidier huois et renri rdeF Fundamentals of Fuzzy Sets. he rndooks of puzzy ets eries uluwer foston wssFD volF UD PHHHF @gited on pge QIFA hustdr PHIP hhrm hustdrD einhrd ihlerD dim venkov et rongE vinh ruongF Quality-aware service-oriented data integration: requirements, state of the art and open challenges. egw sqwyh eordD volF RID pges II!IWD PHIPF @gited on pge SPFA

  Web services provide not a component-based model of application development, but the closest thing possible to zero-coding deployment of such Web services. This makes it easy to reuse Web service components

as appropriate in other Web services. It also makes it easy to deploy legacy code as a Web service.

  The most used application protocol to transmit SOAP messages is HTTP, but it is also possible to use the SMTP or FTP protocols. A SOAP message contains one XML element (Envelope) and two child elements (Header and Body). The Envelope denes the namespaces for the remaining content of a SOAP message. The Header is an optional element. It can carry auxiliary information in a SOAP message. The Body is the mandatory part of a SOAP message. It species the information to be carried from the initial message sender to the ultimate message receiver. Discovery and Integration(UDDI 5 ): UDDI is a platform independent, XML-based registry by which businesses worldwide can list themselves on the Internet, and a mechanism to register and locate web service applications. UDDI is an open industry initiative, sponsored by the Organization for the Advancement of Structured Information Standards (OASIS), for enabling businesses to publish service listings and discover each other, and to dene how the services or software applications interact over the Internet.

		Service Registry
	Publish		Bind
	Service Provider	Find	Service Client
	Figure 2.1: The Web Service Model
	2.1.3 Web Services Standards

Standards are key enablers of Web services

[START_REF] Curbera | [END_REF][START_REF] Vaughan-Nichols | [END_REF]

]. The service model from above is realized via the following XML-based standards:

• Web Services Description Language(WSDL 3 ): WSDL is an XML-based language that is used for describing the functionality oered by a Web service. A WSDL description of a Web service provides a machine-readable description of how the service can be called, what parameters it expects, and what data structures it returns. A WSDL document describes a Web service at two levels: the abstract level and the concrete level. At the abstract level, the WSDL description includes three basic elements: Type, Message, and PortType. At the concrete level, the WSDL description provides information about binding.

• Simple Object Access Protocol(SOAP 4 ): SOAP is a wrapper around the implementation of the OSI network model layer.

• Universal Description, 2.1.4 Data Web Services

  , t 3 ... that are identical to t except for the attribute A, whose values are t 1 .A = a 1 , t 2 .A = a 2 etc. Now each tuple t i is uncertain and the tuples t 1 , t 2 , ... are mutually exclusive.

	• Attribute Level Uncertainty : tuple attributes may have uncertain values. A widely-used model to capture this type of uncertainty is representing tuple attributes as probability distributions dened on discrete or continuous do-mains. We will nd it convenient to convert attribute-level uncertainty into tuple-level uncertainty and consider only tuple-level uncertainty during query pro-cessing. This translation is done as follows. For every tuple t , where the attribute A takes possible values a 1 , a 2 , a 3 , we create several tuples t 1 , t 2 2.2.2.2 Uncertain Data Models Dierent approaches were proposed to model data uncertainty

Table 3 .

 3

		1: Available Web Services
	Service	Functionality
	S 1 ($c, ?s, ?t, ?r, ?a)

  the functionality of the service and represents the semantic relationship between input and output variables. Z i is the set of existential variables relating X i and Y i . F (X i , Y i , Z i ) has the form of RDF triples where each triple is of the form subject.property.object.• C i is a set of value constraints expressed over the X i , Y i or Z i variables. C i may include fuzzy constraints to characterize the data manipulated by S i . Each data service requires a particular set of inputs (parameter values) to retrieve a particular set of outputs; i.e., outputs cannot be retrieved unless inputs are bound. For example, one cannot invoke data service S 2 without specifying the address for which it need to know the apartment for sale and the price. Inputs and Outputs are prexed with '$' and ' ?', respectively in the head of the view S i ($X i , ?Y i ). X i and Y i variables are dened in the WSDL description of data services.The data services S 1 , S 2 and S 3 are described by the following RDF view where School ", Apartment and Pollution are the ontological concepts, country", name", tuitionfees", reputation", city", number ", price" and level "

	?A :price	?p}
	Constraints: {?p is URL/AFFORDABLE}
	S3($a,?po):-
	F:{ ?P rdf:type :Pollution,
	?P :city	$a,
	?P :level ?po}
	are the dierent attributes.
	S1($c,?s,?t,?r,?a):-
	F:{ ?S rdf:type :School,
	?S :country		$c,
	?S :name		?s,
	?S :tuitionFees	?t,
	?S :reputation ?r,
	?S :city ?a}
	Constraints: {?t is URL/CHEAP, ?r is URL/GOOD}
	S2($a,?ap,?p):-
	F:{ ?A rdf:type :Apartment,
	?A :city	$a,
	?A :number ?ap,

  All the data-type properties of Q.S that bound to distinguished variables in

	Service	Covered classnodes & properties
	S1($c, ?u, ?t, ?r, ?z)	Q.S("france", u, t, r, z)
	S2($z, ?x, ?y)	Q.A(z, x, y)
	S3($z, ?po)	Q.P (z, po)

Table 3 .

 3 2: Mapping Table: the covered sub graphs by sample data servicesQ also bound to distinguished variables in S 1 . Furthermore, Q.S is involved in a join over the variable ?z with the class-nodes Q.A and Q.P . Even though S 1 does not cover the class-nodes Q.A and Q.P , the join over ?z can be still enforced as ?z is a distinguished variable in S 1 . Therefore, S 1 can be used to cover Q.S, and thus inserted in the Table3.2. The same discussion applies to S 2 and S 3 .

3.2.3.2 Phase-II: Generating data service compositions

Table 3 .

 3

		3: Implemented norms and conorms
	Name	T Norm : (x, y)
	Zadeh	min(x,y)
	Probabilistic	xy
	Lukasiewicz max(x + y -1, 0)
	Hamacher	xy γ+(1-γ)(x+y-xy)

Table 3 .

 3

				4: Vector Ranking results
	ap	a	p	po	Cheap Good	Aordable	Low
	a1	Lyon	50000$	20	1.00	1.00	1.00	1.00
	a2	Paris	120000$	80	0.22	0.05	0.00	0.00
	a3	Nice	45000$	35	0.60	0.80	0.52	0.75
	a4	Nancy	60000$	65	1.00	0.55	0.60	0.25

Table 4 .

 4 1: Examples of Data Web Services

	Service	Semantics	Service
			Type
	S 1

•

  Invoke p (S p , I p ): it represents the invocation operator. It invokes S p with the input I p . Extensional operators can be computed eciently, and they return what looks like a representation of an independent relation. Suppose we take the output of an extensional plan, and interpret it as an independent probabilistic relation. If this probabilistic relation is the same as the possible worlds semantics then we say that the plan is safe :

	• Aggregate p (I p 1 , ..., I p n , a): it represents the join operator. It aggregates I p 1 ,..,I	p n
	according to the attribute a.
	• P roject P (I p i , a): it represents the projection operator. It projects I p i accord-
	ing to the attribute a.
	• Select(I p , c) it represents the selection operator. It selects I p which check
	the condition c.

http://www.w3.org/

http://www.w3.org/TR/ws-arch/

http://www.w3.org/TR/wsdl

http://www.w3.org/TR/soap12

, ..., R i n ).

Yahoo Inc, Yahoo Pipes, http://pipes.yahoo.com/pipes/

Google Inc. Google Mashup Editor, http://code.google.com/gme/

Intel Inc. Intel Mash Maker. http://mashmaker.intel.com/web/

probabilistic theory. Based on the key concepts and the notions reviewed in this chapter, the next three chapters present our approach to compose uncertain data services.

http://sparql.org/

S1($city, ?school,?zip, ?reputation) S2($school, ?course, ?teacher) «Project» Π(school) school S 2

Acknowledgments

In this section we intuitively dene the semantics of uncertain service composition through an example.

Consider the services S p 3 ($a, ?c, ?j) and S p 2 ($c, ?p, ?pr) whose invocation results are shown in gure.4.7. The composition of S p 3 and S p 2 to answer a query Q 1 : Q 1 (p) : -S p 3 ($a, ?c, ?j)S p 2 ($c, ?p, ?pr) S p 3 is invoked with the value "Lyon " and returned the tuples {t1, t2, t3}. Then S p 2 is invoked obtained tuples in each branch are, in turn, interpreted into possible worlds represented as sub branches. For example the branch involving the possible worlds P W 1 and P W 11 constitutes a possible composition P C 1 whose probability is simply the product of the probabilities of involved possible worlds: P P C 1 = P P W 1 * P P W 11 = 0.18 * 0.108 = 0.01944. In our example we have 20 (6+6+4+4) dierent possible compositions. The probability of a tuple o in the composition result is the sum of the probabilities of all possible compositions that return o. For example the tuple o 1 is returned by the possible composi- tions: P C 1 , P C 2 , P C 7 , P C 10 , P C 13 , P C 15 , P C 17 and P C 19 so probability(o 1 ) = 0.01944+0.03024+0.04536+0.03024+0.0216+0.0144+0.0504+0.0336 = 0.24528.

Another approach to compute the composition results is to express the composition plan using the operators presented in section 4.3.2:

2 )(P roject p c (Invoke p (S p 3 ))). The gure.4.7 shows how we compute the probabilities of both intermediate and the output tuples. The probabilities of output results are correct as they are equal to those obtained using the possible worlds semantics. However, not all composition plans expressed in that algebra give the correct probabilities.

Conclusion

In this chapter, we proposed a probabilistic approach for modeling uncertain data services for two cases: independent data and Block Independent Disjoint data.

Specically, we showed how the uncertainty associated with a data service can be modeled, and proposed a composition algebra (i.e., a set of operators) that can compute the probabilities of the outputs of a composition. Last but not least, we integrated our model within an existing composition system.

Chapter 5

Safe Plan

answering top-k queries in such a way to stop the composition execution as soon as top-k answers are produced.

• The consideration of other modelling approaches of uncertain data.

In this dissertation we assumed that data providers adopt a probabilistic approach for modelling data uncertainty; i.e., services provide data items and their probabilities. However, this assumption may not always hold true.

Some data providers may adopt other approaches to quantify the uncertainty. For example, in the sensors application domain the possibilistic approach may be more convenient; i.e., (uncertain) services provide in this case data items and their possibilities. While in such cases, our service description model remain always reusable (e.g., with replacing the probability information by the possibility information), the invocation and the composi-