<figure><img src="image_57.png" /><figcaption>FIGURE 6.5 – Zoom sur la catégorie Analyse de l'ontologie service type dans BioMoby [LA10]</figcaption></figure>

catégorie Analyse) alors qu'il désigne un service d'alignement et non une catégorie.

– Une fois le service Web enregistré dans une catégorie de services, ses entrées et sorties doivent être identifiées en termes de concepts de l'ontologie des types de données. Comme l'ontologie de type de services, l'ontologie de types de données présente plusieurs inconsistances plus d'ordre conceptuel que structurel comme c'est le cas de la première ontologie. En effet, l'ontologie des types de données ne capture pas les concepts sémantiques du domaine concerné, elle est plutôt orientée syntaxe (format de représentation) en ce sens qu'elle différencie les différents types de formats syntactiques représentant les différents concepts clés du domaine et non la sémantique des concepts en terme de propriétés et de relations. Par exemple, la figure 6.6 montre une sous-hiérachie de types syntactiques. En conclusion, l'ontologie de types de données manque de conceptualisation et se concentre uniquement sur le niveau opérationnel.

La découverte de services dans BioMoby se fait uniquement par le biais d'une API accessible via le Web (figure 6.7); la découverte repose seulement sur la navigation (et non sur une recherche par mots-clés) et les services sont classés par ordre alphabétique, par data-type ou par catégorie. Seulement, le nombre de services étant important, la recherche d'un service pour répondre à un besoin spécifique peut prendre beaucoup de temps. Il est indispensable de disposer de techniques pour l'automatisation du processus de découverte dans BioMoby. Afin de remédier aux inconsistances structurelles et conceptuelles des ontologies conçues dans le cadre du projet BioMoby, [LA10] proposent une approche semi-automatique pour la classification des services BioMoby dans une ontologie du domaine tout en nettoyant les ontologies existantes des inconsistances repérées. Au niveau de notre travail, nous faisons usage de la méta-carte ontologique proposée comme support d'annotation et de raisonnement pour pallier les inconsistances et les incohérences ontologiques. De plus, nous proposons des techniques de raisonnement pour guider la découverte de services dans BioMoby qui reste toujours limitée à la navigation dans [LA10].

### 6.5.2 Un scénario de découverte dans BioMoby

Un scientifique souhaite étudier les mutations connues des gènes APP et Préséniline 1 (PSEN1) chez l'homme dont des recherches ont montré l'implication des mutations de
<figure><img src="image_58.png" /><figcaption>FIGURE 6.6 – Zoom sur le type textFormat de l'ontologie Datatype Ontology dans BioMoby [LA10]</figcaption></figure>

<figure><img src="image_59.png" /><figcaption>FIGURE 6.7 – Interface de l’API BioMoby</figcaption></figure>
ce gène dans la maladie d'Alzheimer. Le scientifique aurait besoin d'un certain nombre
de services afin de répondre à ses besoins. Les questions scientifiques pour lesquelles le
scientifique désire sélectionner des services sont les suivantes :

- $(Q_1)$ Quels sont les services Web permettant de retourner l'ensemble des séquences nucléotidiques d'un gène dont on connaît l'identifiant par exemple les identifiants APP ou PSEN1 ?

- (Q₂) Quels sont les services Web qui permettent de rechercher les séquences d'acides aminées ayant une similitude avec une séquence d'acide aminés résultante de la traduction de la séquence nucléotidique du gène APP ?

- (Q₃) Le scientifique souhaiterait également disposer d'un service pour la prédiction de la structure 3D d'une séquence protéique ?

- (Q₄) Quels sont les services permattant de générer un arbre phylogénétique étant donné une séquence d'acides aminés ?

Les requêtes de découverte exprimées par le scientifique seront formulées sous forme
d'une requête conjonctive comme suit :

- (Q₁) : q(S) :-InputType(S, GeneId), hasInput(S, 'homosapiens'), rdfType('homosapiens', ScientificOrganismName), OutputType(S, NucleotideSequence).

- (Q₂) : q(S) :-InputType(S, NucleotideSequence), OutputType(S, A), rdfBag(A, AminoAcidSequence).

- (Q₃) : q(S) :-InputType(S, AAsequence), OutputType(S, 3DStructure).

- (Q₄) : q(S) :-InputType(S, AminoAcid), InputType(S, 'homosapiens'), OutputType(S, Phylogenetic_tree).

Nous désignons par $KB_O$, la base déductive ontologique du méta-service déductif de BIOMED. $KB_O$ comprend dans sa partie extensionnelle, l'ensemble de faits correspondant aux assertions de déclaration de connaissances de la méta-carte ontologique et dans sa partie intensionnelle, l'axiome de fermeture transitive définie par les deux règles suivantes<fnref n="9" /> :

areSubclasses($C_1$, $C_2$) :-subClassOf($C_1$, $C_2$).

areSubclasses($C_1$, $C_2$) :-subClassOf($C_1$, $C_3$), areSubclasses($C_3$, $C_2$).

D'un autre côté, nous désignons par $KB_S$, la base déductive du méta-service Web déductif comprenant dans sa partie extensionnelle, l'ensemble des annotations sémantiques des services contenues dans le catalogue BioMoby et dans sa partie intensionnelle les huits axiomes explicitant la sémantique inférentielle du méta-framework BIOMED.

Il existe au moins une solution à la requête *q* si et seulement si $KB_O \cup KB_S \models q$. Pour évaluer la requête *q*, nous nous reposons sur le moteur de raisonnement BIOMED développé avec le langage de programmation logique PROLOG, nous décrirons en détail le fonctionnement du moteur de raisonnement BioMed dans la section 6.6.3.

La Table 6.6 résume les solutions des requêtes $Q_1$, $Q_2$, $Q_3$ et $Q_4$, nous distinguons un
seul matching exact entre les contraintes de la requête $Q_4$ et le service runPhylipProtpars
permettant de générer un arbre phylogénétique étant donné une séquence d'acides aminés.
La Table 6.6 montre que le nombre de services découverts augmente considérablement avec
l'utilisation des techniques de relaxation proposées dans BIOMED.

<footnote n="9">9. Pour illustrer, nous prenons à titre d'exemple seulement l'axiome de la fermeture transitive</footnote>
<table><caption>TABLE 6.6 – Solutions des requêtes avec et sans l'utilisation de techniques de raisonnement</caption><thead><tr><th>Requête</th><th>Sans raisonneur</th><th>Avec raisonneur BIOMED</th></tr></thead><tbody><tr><td>Q<sub>1</sub></td><td>Aucun service</td><td>DDBJGetEntry<br>eFetchSequence<br>DBFetch<br>retraire_ensemble_sequence</td></tr><tr><td>Q<sub>2</sub></td><td>Aucun service</td><td>runNCBIBlastp</td></tr><tr><td>Q<sub>3</sub></td><td>Aucun Service</td><td>ShowPDBfromFASTA<br>PDBWebService</td></tr><tr><td>Q<sub>4</sub></td><td>runPhylipProtPars</td><td>runClustalWService<br>PhylipService</td></tr></tbody></table>

Des appariements fonctionnels approximatifs ont été obtenus par le raisonneur BIOMED pour toutes les requêtes. Pour la requête $Q_1$, comme appariement fonctionnel en subsomption, nous obtenons les services DDBJGetEntry<fnref n="10" />, eFetchSequence<fnref n="11" />, DBFeth<fnref n="12" /> et retraire ensemble sequence<fnref n="13" />. Les quatre services offrent un accès à des bases génomiques permettant de retrouver les séquences connues d'un gène. La description des services est plus générale que celle de la requête du fait que ces services retournent en sortie une séquence, couvrant ainsi tous les types de séquences, d'où l'appariement en subsomption. Pour la requête $Q_2$, nous obtenons comme appariement fonctionnel en plugin le service runNCBIBlastp pour l'alignement des séquences nucléotidiques des gènes étudiés après les avoir traduit en six positions de lecture et aligné contre une base de séquences protéiques. Pour la requête $Q_3$, nous identifions comme appariement fonctionnel les services PDB<fnref n="14" /> et ShowPDBFromFASTA. Enfin, comme appariement en subsomption pour la requête $Q_4$, PhylipService<fnref n="15" /> et ClustalW<fnref n="16" /> sont sélectionnés.

## 6.6 Expérimentations et Résultats

Comme l'illustre la figure 6.9, la composante de découverte du méta-service BIOMED repose sur un catalogue de ressources (référentiel de services Web sémantisés), un moteur d'exécution permettant l'appariement fonctionnel des requêtes de découverte étendues en se basant sur les axiomes du modèle inférentiel et un moteur de classement pour le scoring et le rangement des services satisfaisant les contraintes non fonctionnelles de la dite requête. Afin d'évaluer le passage à l'échelle de l'approche proposée, nous avons choisi de générer automatiquement des datasets de services de différentes tailles (nombre de services) allant jusqu'à 16000 services dans le plus grand dataset. Le catalogue de ressources (i.e., la

<footnote n="10">10. http://xml.nig.ac.jp/wsdl/GetEntry.wsdl</footnote>

<footnote n="11">11. http://www.ncbi.nlm.nih.gov/entrez/eutils/soap/v2.0/efetch seq.wsdl</footnote>

<footnote n="12">12. http://www.ebi.ac.uk/Tools/webservices/wsdl/WSDbfetch.wsdl</footnote>

<footnote n="13">13. http://rsat.bigre.ulb.ac.be/rsat/web services/RSATWS.wsdl</footnote>

<footnote n="14">14. http://www.pdb.org/pdb/services/pdbwsfiwsdl</footnote>

<footnote n="15">15. http://www.vbi.vt.edu/pathport/services/wsdl/phylip.wsdl</footnote>

<footnote n="16">16. http://www.ebi.ac.uk/Tools/webservices/wsdl/WSClustalW.wsdl</footnote>
<table><caption>TABLE 6.7 – Les services sélectionnés par requête et par degré d'appariement</caption><thead><tr><th>Requête</th><th>Services Sélectionnés</th><th>Type d'appariement approximatif</th></tr></thead><tbody><tr><td>Q<sub>1</sub></td><td>DDBJGetEntry<br>eFetchSequence<br>retrieve_ensemble_sequence<br>DBFetch</td><td>Appariement en subsomption<br>Appariement en subsomption<br>Appariement en subsomption<br>Appariement en subsomption</td></tr><tr><td>Q<sub>2</sub></td><td>runNCBIblastp</td><td>Appariement en plugin</td></tr><tr><td>Q<sub>3</sub></td><td>ShowPDBfromFASTA<br>PDBWebService</td><td>Appariement fonctionnel<br>Appariement fonctionnel</td></tr><tr><td>Q<sub>4</sub></td><td>runClustalWService<br>PhylipService</td><td>Appariement en subsomption<br>Appariement en subsomption</td></tr></tbody></table>

base extensionnelle du méta-service Web déductif) comprend les descriptions unifiées, les annotations sémantiques et les connaissances ontologiques. Nous présentons les ontologies MESH et PROTEIN ONTOLOGY utilisées pour générer un dataset de services Web dont les entrées et sorties sont annotés avec des concepts des ontologies.

Au niveau opérationnel, le catalogue de ressources correspond à la base extensionnelle d'un programme DATALOG. Quant à la base intensionnelle du programme DATALOG, elle comprend un ensemble de règles logiques implémentant tous les axiomes de la sémantique axiomatique présentée dans le chapitre 5. Le moteur d'exécution est implémenté en tant qu'un méta-interpréteur PROLOG. En premier lieu, le moteur évaluera la base extensionnelle en calculant le modèle minimal de la base et la requête de découverte est évaluée considérant le modèle minimal calculé pour générer l'ensemble des services satisfaisants les contraintes d'une requête de découverte étendue.

Ensuite, un moteur de scoring et classement prendra le relais pour déceler les meilleures solutions parmi celles sélectionnées par le moteur d'exécution. Nous supposons que tous les critères QdS sont d'égale d'importance et nous cherchons les services qui ont les meilleures valeurs du plus grand nombre de critères QdS. Enfin, le fonctionnement de la composante de découverte dans BIOMED est illustré par la figure 6.8. Nous présentons dans ce qui suit et en détails, le catalogue des ressources, le moteur de raisonnement et les résultats des expérimentations.

### 6.6.1 Catalogue de ressources

L'étude menée dans cette expérimentation a considéré un ensemble de services générés automatiquement dont les entrées et les sorties sont annotés avec des termes du vocabulaire contrôlé Mesh et de l'ontologie Protein Ontology. Nous présentons dans ce qui suit une description de ces ontologies. De plus, nous nous sommes basés sur des techniques d'échantillonnage pour associer aux services générés 10 paramètres QdS (dont les valeurs sont normalisées entre 0 et 1) et ce d'une manière aléatoire.
<figure><img src="image_60.png" /><figcaption>FIGURE 6.8 – Fonctionnement Général de la composante de découverte dans BIOMED</figcaption></figure>

<figure><img src="image_61.png" /><figcaption>FIGURE 6.9 – Architecture de la composante de découverte dans BIOMED</figcaption></figure>
<table><caption>FIGURE 6.10 – Extrait de l’arbre ontologique Mesh</caption><thead><tr><th>code hiérarchique</th><th>terme</th></tr></thead><tbody><tr><td>C01</td><td>maladies bactériennes et mycoses</td></tr><tr><td>C01.539</td><td>infections</td></tr><tr><td>C01.539.830</td><td>suppuration</td></tr><tr><td>C01.539.830.025</td><td>abcès</td></tr><tr><td>C01.539.830.025.160</td><td>abcès cerveau</td></tr><tr><td>C01.539.830.025.325</td><td>abcès péridural</td></tr><tr><td>C01.539.830.025.490</td><td>abcès poumon</td></tr><tr><td>[...]</td><td></td></tr><tr><td>C08</td><td>maladies de l'appareil respiratoire</td></tr><tr><td>C08.381</td><td>poumon, maladies</td></tr><tr><td>C08.381.125</td><td>dysplasie bronchopulmonaire</td></tr><tr><td>[...]</td><td></td></tr><tr><td>C08.381.348</td><td>hémoptysie</td></tr><tr><td>C08.381.449</td><td>abcès poumon</td></tr><tr><td>C08.730</td><td>appareil respiratoire, infection</td></tr><tr><td>C08.730.099</td><td>bronchite</td></tr><tr><td>C08.730.407</td><td>abcès poumon</td></tr></tbody></table>

### 6.6.1.1 Le thésaurus Mesh

MeSH (acronyme de Medical Subject Heading) est le thésaurus de référence dans le domaine biomédical produit par le NLM (U.S. National Library of Medicine)<fnref n="17" />. La structure du MeSH est à trois niveaux : un ensemble de termes dont un préférentiel, désigne un concept qui fait partie d'une classe de concepts appelée descripteur. La navigation dans le thésaurus se fait par recherche ou en entrant par les Main Headings. Le MeSH contenait près de 25 000 descripteurs et plus de 455 000 termes en janvier 2009. Trois types de relations, ne reposant pas sur une logique formelle, sont utilisées : hiérarchique, synonymique et proxémique (proximité sémantique).

Produit depuis 1960, le MeSH est utilisé pour l'indexation par de nombreuses bibliothèques et institutions à travers le monde. Le thésaurus a été traduit dans de nombreuses langues mais il est à déplorer qu'il n'existe aucune possibilité de navigation à travers le multilinguisme. Le MeSH n'est conforme à aucune norme, il permet seulement des échanges par le biais du format pivot XML.

Nous avons fait usage de l'arbre ontologique du thésaurus MeSh pour illustrer la relaxation par généralisation et par spécialisation que nous avons proposée. Une des spécificités de l'arbre ontologique MeSh est qu'il présente des cas d'héritage multiple comme l'illustre la figure 6.10. Le terme abcès poumon subsume les trois termes "abcès", "poumon, maladie" et "appareil respiratoire, poumon".

### 6.6.1.2 L'ontologie PO (Protein Ontology)

L'ontologie Protein Ontology (PO) [SDC06] offre un vocabulaire unifié capturant les connaissances du domaine des protéines. D'une part, PO fournit un méta-modèle en définissant les propriétés sémantiques du concept Protéine. Etant donné que ce concept est décrit d'une manière hétérogène entre les sources, PO fournit une sémantique unifiée

<footnote n="17">17. http://www.nlm.nih.gov/</footnote>
<figure><img src="image_62.png" /><figcaption>FIGURE 6.11 – Modélisation du concept Protéine au niveau de l'ontologie PO</figcaption></figure>

telle qu'illustrée par la figure 6.11. D'autres part, PO offre un entrepôt d'instances de protéines selon le format PO, il compte aujourd'hui 7398 protéines classées par famille de protéines (e.g., *growth factor*, *kinase*, *glycoprotein*, etc.). Nous distinguons comme relations sémantiques dans PO, en plus de la relation de subsomption (*subclassOf*), les relations suivantes *PropertyOf* (propriétés sémantiques), *PartOf* (relations de meronymie), *InstanceOf* (instances de concepts) et *ValueOf* (valeurs de propriétés).

## 6.6.2 L'implémentation du méta-service Web déductif dans BioMed

Le méta-service Web BIOMED se présente en l'occurrence comme une base déductive où un langage déclaratif est utilisé pour spécifier des règles DATALOG qui est un sous-ensemble de PROLOG. Nous nous sommes particulièrement intéressés aux techniques développées autour du langage DATALOG ce qui nous incite à les présenter ci-après.

### 6.6.2.1 Datalog

Une limite importante du calcul (algèbre) relationnel(le) est qu'il n'est pas possible d'exprimer des requêtes contenant des chemins entre instances, comme par exemple trouver la fermeture transitive d'un graphe dont les arcs sont stockés dans une relation. DATALOG étend les requêtes conjonctives avec la récursivité pour pouvoir traiter de telles requêtes. La récursivité consiste à utiliser les mêmes noms de relation au niveau de la tête et le corps d'une requête. La sémantique de DATALOG peut être définie à travers trois approches équivalentes : la théorie des modèles, la théorie du point fixe et la théorie de la
preuve. DATALOG hérite cette propriété de la programmation logique et son langage phare
PROLOG.

Syntaxe Datalog

La syntaxe de DATALOG est la même que celle du langage de la programmation logique
PROLOG en éliminant les symboles de fonctions et en considérant les constantes, variables
et prédicats.

**Définition 22** *Une règle DATALOG est définie comme suit :*

$$
T(x) : -q(x, y)
$$

tel que x = x₁, ..., xₙ est un tuple de variables distinctes, y = y₁, ..., yₘ est un tuple de variables "existentiellement quantifiées", T est une relation et q est la conjonction d'atomes.
La partie gauche est la tête de la règle alors que la partie droite est le corps de la règle. Notons que toutes les variables apparaissant dans la tête d'une règle doivent impérativement apparaître dans au moins un atome du corps de la règle<fnref n="18" />. Un programme Datalog P est un ensemble fini de règles. L'instanciation d'une règle est la substitution de chaque variable par une constante. L'instanciation d'un programme P; notée Inst(P); est obtenue en instanciant les règles de P de toutes les façons possibles, en utilisant uniquement les constantes présentes dans les règles et dans les faits. Les symboles des relations (prédicats) qui apparaissent seulement dans le corps des règles d'un programme sont nommés prédicats extensionnels, ceux qui apparaissent dans la tête de règles sont nommés prédicats intensionnels. Un programme Datalog définit une requête datalog lorsqu'un prédicat intensionnel est spécifié comme la sortie du programme.

Par exemple, considérons le programme DATALOG suivant pour calculer la fermeture
transitive d'une hiérarchie de concepts comprenant les deux règles IDB₁ et IDB₂ et un
ensemble de trois prédicats extensionnels formant l'EDB du programme DATALOG :

$$
\begin{align*}
IDB_1 : & areSubclasses(X, Y) && :-subClassOf(X, Y) \\
IDB_2 : & areSubClasses(X, Y) && :-subClassOf(X, Z), areSubClasses(Z, Y) \\
EDB =   && \{subClassOf(Peritoneum, Abdominal Cavity), \\
         && \quad subClassOf(Abdominal Cavity, Abdomen), \\
         && \quad subClassOf(Abdomen, Body Region) \}
\end{align*}
$$

Sémantique DATALOG

Nous distinguons trois approches différentes mais équivalentes pour définir la sémantique d'un programme DATALOG P : théorie des modèles, Point fixe, théorie de la preuve. Pour présenter ces approches, nous présentons une synthèse des chapitres 12 et 13 de l'ouvrage de Abiteboul et al. intitulé *Foundations of Databases* [AHV95].

<footnote n="18">18. Nous nommons ce type de règles, règles saines (safe rules)</footnote>
Théorie des modèles

Dans cette approche, le programme Datalog P est vu comme un ensemble de formules du premier ordre. Rappelons qu’à une requête conjonctive de la forme : T(x) :- q(x, y) correspond une formule (en logique du premier ordre) ∀ x (∃ y q(x, y) → T(x)). Les formules de la logique du premier ordre associées à un programme DATALOG sont d’un type spécial de clause, appelées clauses de Horn. Nous rappelons à ce sujet qu’une clause contient au plus un littéral positif alors qu’une clause de Horn contient exactement un littéral positif.

Une interprétation donne à chaque symbole de formule une signification. Nous disons qu'une interprétation *I* satisfait une formule close $\varphi$ (*I* $|=$ *φ*) si $\varphi$ est vrai dans *I*. Dans ce cas, *I* est un modèle de $\varphi$. En général, si une interprétation *I* satisfait toutes les formules d'un ensemble de formules closes *E* (*I* $|=$ *E*), alors *I* est un modèle de *E*. Si tous les modèles d'un ensemble de formules *E* satisfont une formule close $\varphi$; alors $\varphi$ est la conséquence logique de *E* ($E \models \varphi$).

Dans le contexte DATALOG, il est question de tester si un fait est une conséquence d'un programme DATALOG. Néanmoins, il est inconcevable qu'il soit nécessaire de vérifier un nombre infini d'interprétations. Comme un programme DATALOG est constitué d'un ensemble de clauses de Horn, nous parlons d'interprétations de Herbrand dont la caractéristique est d'interpréter chaque constante en elle-même. Par conséquent, deux interprétations de Herbrand distinctes interprètent les constantes de la même façon et diffèrent seulement par leur interprétation des symboles de prédicats.

**Définition 23 (Interprétation de Herbrand)** *Soit L un langage du premier ordre. Une interprétation de Herbrand pour L est définie de la façon suivante :*

1. Le domaine de l'interprétation est l'Univers de Herbrand (HU), c'est-à-dire, l'ensemble de tous les termes clos qui peuvent être construits avec les constantes et les symboles de fonctions de L.

2. Les constantes dans L sont associées à elles-mêmes dans HU :

3. Si $f$ est un symbole de fonction d'arité $n$ dans $L$; alors nous attribuons à $f$ la fonction de $(HU)^n$ dans HU définie par $(t_1, ..., t_n) \mapsto f(t_1, ..., t_n)$.

4. Une fonction qui associe à un élément de $(HU)^n$ un élément de $\{\text{vrai}; \text{faux}\}$ ; c'est-à-dire, une relation sur $(HU)^n$ est associée à chaque symbole de prédicat d'arité $n$ dans $L$.

Dans le contexte de DATALOG, le point 3 ci-dessus peut être omis puisque le langage L considéré ne contient pas de symbole de fonction. Par conséquent, une *interprétation de Herbrand* est caractérisée par l'ensemble de tous les faits qui sont vrais par rapport à cette interprétation. L'ensemble de tous les faits que l'on peut écrire avec les éléments de l'alphabet (c'est-à-dire, avec le langage courant) est appelé *Base de Herbrand (HB)*, une interprétation de Herbrand est un sous-ensemble de HB. Une interprétation de Herbrand qui satisfait une formule close $\varphi$ (ou un ensemble de formules closes E) est appelée *Modèle de Herbrand de $\varphi$* (ou de E).

Toujours dans le contexte de DATALOG, nous considérons que les seuls constantes et prédicats à prendre en compte sont ceux qui apparaissent dans le programme DATALOG.
Nous pouvons alors reformuler la notion de conséquence logique de la manière suivante. Un fait $f$ est conséquence d'un ensemble de clauses de Horn définies $E$ (dénoté $E \models f$) si et seulement si chaque interprétation de Herbrand qui satisfait toutes les clauses de $E$ satisfait $f$.

**Définition 24 (Modèle Minimal)** *Etant donné un programme DATALOG $P$, $\Sigma_P$ l'ensemble des formules du premier ordre correspondant à $P$, $\mathcal{X}$ l'ensemble des modèles de Herbrand satisfaisant $\Sigma_P$, alors :*

1. Le modèle (Herbrand) minimal est l'intersection de tous les modèles $\cap \mathcal{X}$ satisfaisant $\Sigma_P$,

2. Le modèle minimal constitue la sémantique de $P$.

### Point Fixe

Dans cette approche, la sémantique d'un programme DATALOG est définie comme étant la solution d'une équation de point fixe. Il s'agit d'une approche procédurale où le programme est vu comme un ensemble de faits et de règles sur lequel un mécanisme d'inférence est appliqué pour engendrer de nouveaux faits. Un opérateur, appélé opérateur de conséquence immédiate, est défini pour formaliser l'idée de production de nouveaux faits.

**Définition 25 (Opérateur de conséquence immédiate)** *Soit $P$ un programme DATALOG et soit $\mathcal{P}_{HB}$ l'ensemble des interprétations de Herbrand de $P$. L'opérateur de conséquence immédiate associé à $P$; noté $T_P$ est une fonction de $\mathcal{P}_{HB}$ dans $\mathcal{P}_{HB}$ définie par :*

$$T_P(I) = \{ \text{tête}(r) \mid r \in \text{Inst}_P \wedge \forall L \in \text{corps}(r), I \models L \}; \text{ pour tout } I \text{ de } \mathcal{P}_{HB}.$$

Pour un programme Datalog, l'opérateur $T_P$ est monotone et continu et il est défini sur le treillis complet $(\mathcal{P}_{HB}, \subseteq)$. Par conséquent, la suite définie par $T_P^0(\emptyset)=\emptyset$, $T_P^k(I)=T(T_P^{k-1}(I))$, pour $k>0$, possède une limite. Cette limite est le plus petit point fixe de $T_P$ par rapport à $I$, notée, $lfp(T_P)$. Le théorème suivant établit le rapport entre le modèle minimal et l'opérateur de conséquence immédiate.

**Théorème 1** *Soit $P$ un programme Datalog et soit $M_P$ le modèle minimal associé à $P$ :*
Le plus petit point fixe de l'opérateur de conséquence immédiate $T_P$ associé à $P$ coïncide avec $M_P$ ; c'est-à-dire, $M_P = lfp(T_P)$.

En conclusion, cette approche donne une définition constructive de la sémantique d'un programme DATALOG, et peut être considérée comme une implantation de la théorie de modèles.
Théorie de la preuve

Dans cette approche, la sémantique d'un programme DATALOG est définie en fonction
de preuves, c'est-à-dire, la sémantique d'un programme P par rapport à une interprétation
I est l'ensemble de faits à prouver en utilisant P et I : Pour définir la notion de preuve,
nous devons définir d'abord l'arbre de preuve d'un fait.

**Définition 26 (Arbre de preuve d'un fait)** *Soit P un programme Datalog et I une interprétation. Un arbre de preuve d'un fait f à partir de I et P est défini de la façon suivante :*

1. Chaque noeud de l'arbre est étiqueté par un fait.

2. *Chaque feuille est étiquetée par un fait de I :*

3. La racine est étiquetée par f :

4. Pour chaque noeud interne, il existe une instanciation $A_0 \leftarrow A_1, \dots, A_n$ d'une règle de P telle que le noeud est étiqueté par $A_0$ et ses fils sont étiquetés par $A_1, \dots, A_n$.

Un arbre de preuve représente la preuve d'un fait. De plus, dans [AHV95] le résultat suivant est présenté : Un fait *f* est dans *M*<sub>*P*</sub> si et seulement si il y a un arbre de preuve pour *f* à partir de *I* et de *P*.

Étant donné un fait *f* à prouver, il y a deux méthodes pour chercher la preuve de *f* :
bottom up et top down.

La méthode *bottom up* est une autre façon de traiter l'approche par point fixe. Commençant par les faits dans *EDB* ; les règles sont appliquées pour engendrer de nouveaux faits, jusqu'au moment où aucun nouveau fait n'est dérivé. La méthode *top-down* permet l'orientation de la recherche. Si nous voulons prouver *f* ; il est nécessaire de prouver seulement des faits qui ont un rapport avec *f*. Ainsi, la méthode *top-down* inhibe les inférences inutiles à la preuve du fait considéré. La méthode *top down* est fondée sur l'idée suivante : étant donné une formule close $\varphi$ du premier ordre et un ensemble *E* de formules closes du premier ordre, $\varphi$ est conséquence logique de *E* si et seulement si $E \cup \{\neg \varphi\}$ n'est pas satisfaisable.

Le moteur inférentiel de BIOMED se base sur l'approche par point fixe en intégrant les
deux techniques d'évaluation *top-down* et *bottom-up*.

6.6.2.2 Le moteur inférentiel de BioMed

Comme la syntaxe Datalog est un sous-ensemble de la syntaxe PROLOG, nous implémentons
le moteur BIOMED en PROLOG tout en adoptant les techniques d'évaluation de pro-
grammes DATALOG. Ainsi, le moteur de raisonnement a été implémenté comme un méta-
interpréteur Prolog implémentant l'approche d'évaluation semi-naïve de la technique bottom-
up du DATALOG.

En effet, une stratégie d'évaluation simple en bottom-up, appelée *évaluation naïve*, est basée sur la sémantique du point fixe de DATALOG. L'idée est d'appliquer l'opérateur de conséquence immédiate sur les résultats de toutes les étapes précédentes (en commençant par la base extensionnelle initialement définie). Une évaluation naïve aboutit à une redondance des faits inférés. Afin de pallier cette insuffisance, une évaluation semi-naïve permet
de produire à chaque étape seulement les faits qui peuvent être déduits par au moins un des faits inférés pendant l'étape précédente.

L'implémentation du programme *Prolog* de l'approche semi-naive se présente comme suit :

La règle PROLOG implémentant la relaxation assertionnelle est codée comme suit :

inputtypes(S,C) :- hasInput(S,X), (isoftype(X,C,'mesh',S), addInput(S,C)).

Les entrées et les sorties des services sont représentées sous forme de listes. A chaque axiome de relaxation, le prédicat **addInput** permet d'ajouter un nouveau concept à la liste des concepts, tout en vérifiant qu'il n'appartient pas déjà à la liste en retirant de la liste tous ses éléments (prédicat **retractInput**) et vérifiant si le concept en question est dans la liste (prédicat **checkInput**). Le prédicat **addInput** est défini d'une manière disjonctive comme suit :

addInput(S,C) :- retractInput(L,S), checkInput(L,S), not(member(C,L)), append(L,[C],L1),
notExistInput(S,L1), assert(hasInput(S,L1)).

addInput(S,C) :- not(hasInput(S,-)), assert(hasInput(S,[C])).

addInput(-,-).

L'axiome **AddOutput** est défini de la manière similaire que **AddInput** comme suit :

addOutput(S,C) :- retractOutput(L,S), checkOutput(L,S), not(member(C,L)), append(L,[C],L1),
notExistOutput(L1,S), assert(output(L1,S)).

addOutput(S,C) :- not(output(-,S)), assert(output([C],S)).

addOutput(-,-)

L'axiome de relaxation par spécialisation est implémenté avec la règle PROLOG suivante :

inputtypes(S,Y) :- hasInput(S,X), isoftype(X,C,O,S)), (aresubclasses(C,Y), addInput(S,C)).

Le prédicat isoftype est un prédicat avec quatre arguments spécifiant le type sémantique d'un paramètre *X* d'un service *S* en terme d'un concept *C* d'une ontologie *O*. Bien que
les services Web considérés dans notre catalogue aient été annotés en termes des concepts, propriétés et relations de la méta-carte ontologique, nous prévoyons le cas où les paramètres des services sont annotés en nous basant sur plusieurs ontologies dans des travaux futurs.

L'axiome de relaxation par généralisation est implémenté comme suit :

outputTypes(S,Y) :-hasOutput(S,X), isotype(X,C,O,S)),(aresubclasses(C,Y),addOutput(S,C)).

Les axiomes de relaxation fonctionnelle sont implémentés comme suit :

inputtypes(S,Y) :-inputtypes(S,C),(propertyDomain(P,C),(functionalProperty(P), (propertyRange(P,Y),addInput(S,Y)).

outputtypes(S,Y) :-outputtypes(S,C),(propertyDomain(P,C),(functionalProperty(P), (propertyRange(P,Y),addOutput(S,Y)).

Les axiomes de relaxation fonctionnelle inverse sont implémentés comme suit :

inputtypes(S,C) :-inputtypes(S,Y),(propertyRange(P,Y),(inverseFunctionalProperty(P), (propertyDomain(P,C),addInput(S,C)).

outputtypes(S,C) :-outputtypes(S,Y),(propertyRange(P,Y),(inverseFunctionalProperty(P), (propertyDomain(P,Y),addOutput(S,Y)).

Sachant que la définition des règles de relaxation fonctionnelle et non fonctionnelle correspond à des règles récursives, les prédicats **propertyRange** et **propertyDomain** permettent de définir le domaine et le co-domaine d'une propriété. Les prédicats unaires **functional-Property** et **inverseFunctionalProperty** permettent de déclarer les propriétés fonctionnelles et fonctionnelles inverse.

Nous avons utilisé l'environnement SWI-Prolog<sup>19</sup> pour développer le moteur de raisonnement de BIOMED. SWI-Prolog est un compilateur Prolog rapide et puissant, qui possède un large panel de prédicats. Il offre un environnement rapide et robuste. Les services Web générés étaient stockés dans une base de données Oracle 8i. Les tests du moteur de raisonnement BioMed sont décrits dans la section suivante.

### 6.6.3 Résultats des expérimentations

Une première batterie d'expérimentations a été menée avec des *datasets* comprenant entre 1000, 1500, 2000 et 2500 services annotés sémantiquement avec des termes MESH et de PROTEIN ONTOLOGY. Trente requêtes ont été générées comprenant chacune entre 5 et 10 contraintes fonctionnelles et entre 6 et 9 contraintes non fonctionnelles. Les résultats de cette expérimentation sont illustrés dans la figure 6.12. Certes le nombre de services sélectionnés en utilisant des techniques de raisonnement augmente d'une magnitude (d'un

<footnote n="19">19. http://www.swi-prolog.org/</footnote>
<figure><img src="image_63.png" /><figcaption>FIGURE 6.12 – Résultats de la première batterie d'expérimentation</figcaption></figure>

ordre de grandeur) par rapport au nombre de services découverts sans l'usage de ces techniques et cela pour chaque taille du dataset. Cependant, il est à noter que le calcul du modèle minimal est exponentiel par rapport à la taille du dataset ce qui a pris plusieurs jours (3 jours) pour le plus grand dataset.

Une seconde batterie d'expérimentations a été menée avec des datasets comprenant un nombre plus important de services (comparé à la première expérimentation), le processus s'effectuant sur huit machines. Nous avons étudié les performances des tâches de raisonnement en reportant le nombre de services sélectionnés lorsque les tâches de raisonnement sont exécutées. Dans la figure 6.13, nous comparons le nombre moyen de services sélectionnés (à l'échelle logarithmique) dans le cas où le processus de découverte repose sur des tâches de raisonnement (RT : Reasoning Task) ou non (WRT : Without Reasoning Task). Nous avons exécuté les trente requêtes en considérant différents datasets comprenant respectivement 1000, 2000, 4000, 6000 et 16000 de services Web. Nous observons que le nombre de services découverts augmente de deux magnitudes (ordres de grandeur sur l'échelle logarithmique) lorsqu'on utilise des tâches de raisonnement. A titre d'exemple, nous extrayons les trois requêtes de découverte étendues suivantes parmi les trente définies dans les expérimentations.
<figure><img src="image_64.png" /><figcaption>FIGURE 6.13 – Résultats de la seconde expérimentation</figcaption></figure>

query1(S,T,A) :-solveQuery((ifostype(inputatt1,'C04.557.386.480.750.199',_,S), nonFunctionalCondition(S,X,100)),T,A).

query2(S,T,A) :-solveQuery((inputtypes(S,'C04.557.386.480.750.199'), nonFunctionalCondition(S,qosatt4,100)),T,A).

query3(S,T,A) :-solveQuery((((((((((((((((inputtypes(S,'D12'), inputtypes(S,'C10.177'))), inputtypes(S,'C04')), inputtypes(S,'D01.146')), inputtypes(S,'D12.776.828')),inputtypes(S,'D02.522')), output- types(S,'C05')), outputtypes(S,'C15.378')), outputtypes(S,'D08.811')),outputtypes(S,'A06')), outputtypes(S,'C17.800')),outputtypes(S,'D03')), nonFunctionalCondition(S,qosatt2,100)),nonFunctionalCondition(S,qosatt3,100)), nonFunctionalCondition(S,qosatt5,100)),nonFunctionalCondition(S,qosatt8,100)), nonFunctionalCondition(S,qosatt9,100)),T,A).

L'algorithm WTKSF a été implémenté en Java 1.6. L'expérimentation a considéré un
dataset de 10.000 services en exécutant 30 requêtes, définissant chacune 10 paramètres
QdS. Dans la figure 6.14, nous montrons le ratio de la taille du skyline par rapport
au nombre total de services sélectionnés par le moteur de découverte (satisfaisant les
contraintes fonctionnelles de la requête de découverte). D'une manière générale, on ob-
serve que la taille du skyline est plus grande pour les requêtes ayant un grand nombre de
critères QdS. Dans les requêtes étudiées, la taille skyline varie entre 9% et 37% du nombre
total des services qui satisfont fonctionnellement la requête.
<figure><img src="image_65.png" /><figcaption>FIGURE 6.14 – Taille du skyline pour les trente requêtes définies pour les expérimentations</figcaption></figure>
Les expérimentations menées montrent l'impact des techniques de relaxation sur la taille de l'espace de recherche des services découverts (augmentant de deux magnitudes dans la seconde expérimentation). Par ailleurs, la taille du skyline pour les requêtes évaluées variant entre 8 et 37 services justifie l'intérêt des techniques de classement proposées.

## 6.7 Conclusion

Dans ce chapitre, nous avons présenté notre approche de découverte de services Web conçue dans le cadre du méta-framework BIOMED. Dans un premier temps, l'approche proposée repose sur les techniques de raisonnement fondées sur l'axiomatique du méta-framework pour déduire l'ensemble des solutions (services) qui satisfont (dans le cas idéal) de manière exacte ou (dans la plupart des cas) de manière approximative les contraintes de la requête. Les requêtes de découverte ici considérées sont étendues c'est à dire couvrent tant les propriétés fonctionnelles que non fonctionnelles d'un service Web. Nous avons montré l'intérêt des techniques de relaxation développées dans cette thèse en considérant un cas de pratique de découverte de services dans le domaine bioinformatique. En l'occurrence, nous avons étudié le problème de découverte dans le catalogue BioMoby, l'un des plus importants catalogues de services dans ce domaine. La découverte dans ce catalogue est basée uniquement sur la navigation. Bien que certains travaux récents en l'occurrence [LA10] aient étudié le problème de découverte dans l'annuaire BIOMOBY, ils n'ont pas proposé des techniques de raisonnement pour améliorer la qualité du processus comme nous l'avons fait ici. En considérant un certain nombre de questions scientifiques pertinentes, nous avons montré l'impact des approches et techniques développées dans cette thèse sur la taille et la pertinence de l'espace des solutions.

Nous avons proposé une opérationnalisation du méta-framework BIOMED dans sa partie inférentielle qui a été conçue comme un méta-service Web déductif. Ce méta-service est représenté par une base déductive DATALOG, le niveau extensionnel du méta-service comprend la déclaration de toutes les connaissances descriptives (descriptions sémantisées des services) et les connaissances ontologiques de la méta-carte, le niveau intensionnel comprenant un ensemble de règles implémentant les axiomes du modèle inférentiel. Les techniques de DATALOG ont été utilisées afin de représenter le méta-service mais également pour évaluer une requête de découverte représentée sous forme conjonctive.

Les expérimentations menées ont considéré des datasets de services Web synthétiques de différentes tailles. Les services synthétiques ont été générés automatiquement à partir de termes de Mesh et de concepts de Protein Ontology. Les premières expérimentations ont révélé que le calcul du modèle minimal pour un programme DATALOG est exponentiel au nombre de services.

En second lieu, l'approche de découverte a intégré une phase de classement permettant de déceler les meilleurs services parmi ceux sélectionnés par le moteur de raisonnement. L'approche a permis de déterminer le **skyline de services** désignant l'ensemble des services non dominés par aucun autre service au niveau des critères de Qds. La sélection des top-k meilleurs services a été effectuée grâce à l'heuristique maximisant une fonction de score calculant la fréquence du service dans tous les sous-espaces multi-dimensionnels. Cette heuristique repose sur l'algorithme WTKSF [GVRA09, GVRA10].
Enfin, les expérimentations effectuées montrent aussi bien la robustesse que la scalabilité de l'approche proposée.

Dans le chapitre suivant, nous présentons notre approche de composition de services Web qui vise à étendre les techniques de raisonnement afin de résoudre une requête étendue nécessitant l'interaction de plusieurs services.
# Chapitre 7

## La composition de Services Web dans BioMed

### Sommaire

<table><tr><td>7.1</td><td>Introduction</td><td>169</td></tr><tr><td>7.2</td><td>Composabilité fonctionnelle</td><td>170</td></tr><tr><td>7.2.1</td><td>Axiomatique inférant une dépendance logique</td><td>171</td></tr><tr><td>7.2.2</td><td>Mesures de similarité inférant une composabilité empirique</td><td>172</td></tr><tr><td>7.3</td><td>Composabilité non fonctionnelle et Sélection des meilleurs plans</td><td>178</td></tr><tr><td>7.3.1</td><td>Approche globale</td><td>179</td></tr><tr><td>7.3.2</td><td>Approche locale</td><td>183</td></tr><tr><td>7.4</td><td>Conclusion</td><td>188</td></tr></table>

### 7.1 Introduction

Le dernier chapitre de cette thèse présente l'approche de composition de services Web proposée dans le cadre du méta-framework BIOMED. A l'instar de l'approche de découverte, l'approche de composition proposée considère à la fois des contraintes fonctionnelles et non fonctionnelles afin de sélectionner l'ensemble des services composables fonctionnellement, vérifiant les contraintes NF et ayant les valeurs QdS les plus satisfaisantes. Pour ce faire, nous ajoutons deux nouveaux axiomes, au niveau de la sémantique axiomatique, définissant la notion de **composabilité fonctionnelle** entre services. Ainsi, un graphe de composition déduit par le moteur de raisonnement de BIOMED comprend l'ensemble des services vérifiant les critères de composabilité. Ce graphe peut consister en un (ou plusieurs) plans de composition possibles, chacun sera évalué en termes de critères QdS afin de distinguer les **solutions admissibles** (celles qui satisfont les contraintes non fonctionnelles) et ensuite sélectionner les meilleures solutions parmi celles admissibles en se basant sur un algorithme de *ranking*.

Dans la première section de ce chapitre, nous formalisons le problème de composition et définissons la notion de composabilité fonctionnelle. Ensuite, nous discutons la composabilité non fonctionnelle.
## 7.2 Composabilité fonctionnelle

Nous définissions la notion de requête étendue de composition comprenant un ensemble de contraintes fonctionnelles et non fonctionnelles.

**Définition 27 (Requête de composition)** Une requête de composition est définie par un tuplet $Q=\langle F, NF \rangle$, où $F$ et $NF$ désignent respectivement un ensemble de propriétés fonctionnelles et un ensemble de propriétés non fonctionnelles définies telles que :

- $F=(I,O)$ où $I$ est un ensemble d'entrées typées de la requête $Q$ et $O$ est l'ensemble de sorties typées de la requête $Q$.

- $NF$ est un ensemble de quadruplets $(P,C,V,U)$ où $P$ est un paramètre non fonctionnel, $C$ est un opérateur logique de comparaison, $V$ est la valeur du paramètre et $U$ est l'unité du paramètre $P$. L'évaluation de la requête $Q$ doit respecter la conjonction de expressions exprimés par $NF$. Si $(P, C_i, V_i, U_i)$ et $(P, C_j, V_j, U_j) \in NF$ alors $C_i = C_j, V_i = V_j$ et $U_i = U_j$.

Au niveau du méta-framework BIOMED, une requête utilisateur est prise en compte par le moteur de découverte, en premier lieu, si aucun service atomique ne satisfait la requête alors le moteur de composition qui prend le relais.

La composabilité fonctionnelle permet de définir un (voire plusieurs) plan(s) de composition en réponse à une requête $Q$ en sélectionnant **un ensemble de services fonctionnellement composables** et ce en considérant uniquement leurs signatures fonctionnelles (en termes d'entrées et de sorties). Un graphe de composition est l'union de tous les plans de composition identifiés.

Au niveau de ce graphe, les services sont inter-reliés par deux types de dépendance : **logique** ou **empirique** et cela selon l'approche utilisée pour déduire cette dépendance. Sachant qu'une dépendance dans un graphe de composition entre deux services indique que ces deux derniers sont composables. Ainsi, deux services $S_i$ et $S_j$ peuvent être interconnectés par dépendance logique, si (idéalement) l'ensemble des sorties de $S_i$ est sémantiquement équivalent à l'ensemble des entrées de $S_j$, i.e., $\forall o \in O_i : \exists i \in I_j, o \equiv i$. Les techniques de relaxation présentées au niveau du modèle inférentiel de BioMed permettent de relaxer cette propriété afin de déduire une dépendance logique approximative entre services.

Le second type de dépendance dite **empirique** est déduite par calcul de similarité sémantique entre les concepts en sortie d'un service et les entrées de son successeur. Nous faisons usage de certaines métriques exploitant les relations taxinomiques au niveau de la méta-carte ontologique pour déduire une dépendance empirique. Nous annotons les dépendances entre services au niveau du graphe de composition par la valeur de similarité $\gamma_D$ obtenue lors de l'évaluation de la métrique. Sachant que les dépendances logiques sont annotées par l'unique valeur $\gamma_D=1$.

Nous explicitions dans la prochaine section deux nouveaux axiomes proposés formalisant la notion de composabilité fonctionnelle. Nous montrons que ces axiomes garantissent la définition de quatre patrons de composition (sequential, And Join, And Split et Loop illustrés par la figure 7.2.). La section 7.2.2. présente un aperçu des mesures de similarité pouvant être adoptées pour évaluer la similarité entre concepts en se basant sur une
hiérarchie de concepts.

### 7.2.1 Axiomatique inférant une dépendance logique

Nous proposons d'étendre l'axiomatique du modèle inférentiel BIOMED par deux nouveaux axiomes permettant de déduire des dépendances entre services. L'axiome 9 définit formellement trois conditions de composabilité séquentielle entre deux services $S_1=(I_1, O_1)$ et $S_2=(I_2, O_2)$. Le service $S_3=(I_1, O_2)$ est défini comme le service résultat de la composition en séquence des services. L'axiome 9 est énoncé comme suit :

**Axiome 9**

$$ \frac{S_1 \odot S_2}{S_3} \left\{ \begin{array}{l} \text{Composabilité exacte :} \\ \quad \forall c \in O_2, \exists c' \in I_1 \text{ tel que, } c \text{ isEquivalentTo } c'; \\ \\ \text{Composabilité partielle :} \\ \quad \exists c \in O_2, \exists c' \in I_1 \text{ tel que, } c \text{ isEquivalentTo } c'; \\ \\ \text{Composabilité approximative :} \\ \quad \forall c \in O_2, \exists c' \in I_1 \text{ tel que, } c' \in \text{instancesOf}(c) \cup \\ \quad \quad \text{subClasses}(c) \cup \text{functionalProperties}(c) \cup \\ \quad \quad \text{InversefunctionalProperties}(c). \end{array} \right. $$

L'axiome 9 définit les règles de composabilité permettant de déduire une dépendance logique entre services Web en distinguant la composabilité exacte, la composabilité partielle et la composabilité approximative.

1. **La composabilité exacte** implique l'équivalence sémantique entre l'ensemble des sorties d'un service et des entrées de son successeur.

2. **La composabilité partielle** permet de déduire une dépendance logique entre $S_1$ et $S_2$ en considérant seulement un sous-ensemble des sorties de $S_1$ plutôt que l'ensemble de tous les paramètres; en effet, seulement un sous-ensemble des paramètres en sorties de $S_1$ sera matché à un sous-ensemble de paramètres en entrée de $S_2$.

3. **La composabilité approximative** repose sur les différentes techniques de relaxation :

- La relaxation par subsomption. Plutôt que d'avoir une compatibilité exacte, une relaxation par subsomption permet de relaxer les paramètres de sorte d'accepter comme entrées $S_2$ toutes les sorties de $S_1$ qui sont subsumés par une entrée de $S_2$.

- La relaxation assertionnelle. Si la sortie o d'un service $S_1$ appartient à l'ensemble des instances d'une entrée i en entrée à un service $S_2$, une dépendance logique sera établie entre $S_1$ et $S_2$.

- La relaxation fonctionnelle et fonctionnelle inverse. Enfin, il est possible de relaxer les paramètres d'un service avec toutes les propriétés fonctionnelles et non fonctionnelles de ses entrées.

L'axiome 10 permet de déduire un nouveau service $S_3$ comme l'union de deux services $S_1$ et $S_2$ comme suit :
<table><caption>TABLE 7.1 – L'ensemble des services sélectionnés</caption><thead><tr><td>Phase du Workflow</td><td>Services sélectionnés</td></tr></thead><tbody><tr><td>Rechercher les séquences d'un gène</td><td>GetEntryDDBJ<sup>1</sup>, eFetch<sup>2</sup>, eFetchSequence<sup>3</sup></td></tr><tr><td>Recherche de séquences similaires</td><td>WSNCBIBlast<sup>4</sup>, WSFASTA<sup>5</sup>, runBLATService<sup>6</sup></td></tr><tr><td>Construction d'un arbre phylogénétique</td><td>runPhylipFromDna<sup>7</sup>, runCreateTreeFromClustalW<sup>8</sup></td></tr></tbody></table>

<table><caption>TABLE 7.2 – Définitions de quatre patrons de composition</caption><thead><tr><td>Type de patron</td><td>Définition</td></tr></thead><tbody><tr><td>Sequential</td><td>S<sub>1</sub> ⊙ S<sub>2</sub></td></tr><tr><td>And Split (Fork)</td><td>S<sub>1</sub> ⊙ (S<sub>2</sub> ⊕ S<sub>3</sub>....⊕ S<sub>n+1</sub>)</td></tr><tr><td>And Join (Merge)</td><td>(S<sub>1</sub> ⊕ S<sub>2</sub>....⊕ S<sub>n</sub>) ⊙ S<sub>n+1</sub></td></tr><tr><td>Loop</td><td>S<sub>1</sub> ⊕ S<sub>1</sub></td></tr></tbody></table>

### Axiome 10

$$ \frac{S_1 \oplus S_2}{S_3} \begin{cases} si & S_1 = (I_1, O_1) \text{ et } S_2 = (I_2, O_2) \text{ alors} \\ & S_3 = (I_3, O_3) \text{ tel que } I_3 = I_1 \cup I_2 \text{ et } O_3 = O_1 \cup O_2. \end{cases} $$

Les deux axiomes proposés permettent de définir quatre parmi les six patrons de composition comme illustré par la figure 7.2 (exposés dans le chapitre 3 de l'état de l'art). La Table 7.2 résume la définition des quatre patrons de composition en utilisant les deux axiomes.

**Exemple 13** La conception et l'implémentation de workflows scientifiques constituent un des plus puissants outils de la discipline de la biologie "in silico" qui est la bioinformatique. Les workflows scientifiques visent à définir une chaîne de traitement afin de répondre à une question scientifique complexe. Pour illustrer ceci, nous prenons l'exemple d'un scientifique qui désirer étudier l'homologie d'un gène humain avec d'autres gènes provenant d'autres espèces (on parle précisément dans ce cas de gènes orthologues). Ceci peut être réalisé par la construction d'un arbre phylogénétique permettant de mesurer le degré de parenté entre les taxons (les organismes vivants) mettant en évidence les gènes homologues à un gène humain spécifique. Ce workflow nécessite trois étapes : en premier lieu, il s'agit de requêter à partir d'une base de séquence la séquence ADN du gène, puis exécuter un alignement de séquence pour rechercher les séquences similaires à la séquence du gène pour enfin exécuter un service d'analyse phylogénétique afin de générer un arbre phylogénétique.

Comme l'illustre la Table 7.1, un ou plusieurs services peuvent être sélectionnés et puis orchestrés selon les règles de composabilité définis par l'axiome 9.

### 7.2.2 Mesures de similarité inférant une composabilité empirique

Le raisonneur déductif de BioMed permet d'inférer des appariements approximatifs entre les concepts annotant les entrées et les sorties d'un service Web et une requête de découverte comme présenté dans le chapitre 6 de ce mémoire. De plus, par le biais des
<figure><img src="image_66.png" /><figcaption>FIGURE 7.1 – Le Workflow scientifique de l'étude phylogénétique et les différentes alternatives de solutions de composition</figcaption></figure>

<figure><img src="image_67.png" /><figcaption>FIGURE 7.2 – Les quatre patrons choisis : Sequential, AndSplit, AndJoin et Loop</figcaption></figure>
<table><caption>TABLE 7.3 – Ensemble des différents plans de composition</caption><thead><tr><td>Plans</td><td>Services</td></tr></thead><tbody><tr><td>Plan<sub>1</sub></td><td>GetEntryDDBJ, WSNCBIBlast, runPhylipFromDna</td></tr><tr><td>Plan<sub>2</sub></td><td>GetEntryDDBJ, WSNCBIBLAST, runCreateTreeFromClustalW</td></tr><tr><td>Plan<sub>3</sub></td><td>GetEntryDDBJ, WSFasta, runPhylipFromDna</td></tr><tr><td>Plan<sub>4</sub></td><td>GetEntryDDBJ, WSFasta, runCreateTreeFromClustalW</td></tr><tr><td>Plan<sub>5</sub></td><td>GetEntryDDBJ, runClustalW</td></tr><tr><td>Plan<sub>6</sub></td><td>DBFetch, WSNCBIBlast, runPhylipFromDna</td></tr><tr><td>Plan<sub>7</sub></td><td>DBFetch, WSNCBIBLAST, runCreateTreeFromClustalW</td></tr><tr><td>Plan<sub>8</sub></td><td>DBFetch, WSFasta, runPhylipFromDna</td></tr><tr><td>Plan<sub>9</sub></td><td>DBFetch, WSFasta, runCreateTreeFromClustalW</td></tr><tr><td>Plan<sub>10</sub></td><td>DBFetch, runClustalW</td></tr><tr><td>Plan<sub>11</sub></td><td>eFetchSequence, WSNCBIBlast, runPhylipFromDna</td></tr><tr><td>Plan<sub>12</sub></td><td>eFetchSequence, WSNCBIBLAST, runCreateTreeFromClustalW</td></tr><tr><td>Plan<sub>13</sub></td><td>eFetchSequence, WSFasta, runPhylipFromDna</td></tr><tr><td>Plan<sub>14</sub></td><td>eFetchSequence, WSFasta, runCreateTreeFromClustalW</td></tr><tr><td>Plan<sub>15</sub></td><td>eFetchSequence, runClustalW</td></tr></tbody></table>

axiomes 9 et 10 définis dans la section précédente il est possible de déduire une composabilité fonctionnelle empirique entre les entrées d'un service et les sorties de son prédécesseur. Les techniques de relaxation présupposent que les concepts se situent sur le même chemin taxinomique dans l'arbre ontologique. Cependant, si deux concepts ne se trouvent pas sur le même chemin dans l'arbre ontologique, l'appariement approximatif échoue. Nous proposons d'étendre les techniques d'appariement basées initialement sur seulement le raisonnement déductif avec des techniques de mesures de similarité sémantique. L'adoption des mesures de similarité peut être proposée dans le contexte de la découverte et/ou la composition de services Web afin de pallier les insuffisances du raisonnement déductif. Nous illustrons notre propos avec l'exemple suivant.

**Exemple 14** Nous considérons l'exemple de trois services $S_1$, $S_2$ et $S_3$. Le service $S_1$ accepte une entrée de type sémantique un concept $C_2$ et retourne deux sorties de type $C_4$ et $C_2$. Le service $S_2$ accepte en entrée un concept de type $C_3$ et retourne deux sorties de type $C_9$ et $C_7$. Enfin, $S_3$ prend en entrée un concept $C_5$ et renvoie en sortie un concept $C_3$ et $C_6$. La hiérarchie de concept est illustrée par la figure (a). Enfin, la requête Q exprime un besoin d'un service qui accepte en entrée un concept $C_8$ et retourne en sorties deux paramètres de type sémantique respectivement $C_4$ et $C_7$. Il est clair qu'aucun service ne matche exactement la requête Q. Cependant, le service $S_1$ matche en plugin la requête Q en opposition au service $S_2$ qui matche en subsomption la requête Q. Par contre, il est impossible de déduire un matching entre $S_3$ et Q puisque d'une part les concepts $C_5$ et $C_8$ ne sont pas sur le même chemin taxinomique et d'autre part les concepts en sortie ne se trouvent pas sur le même chemin. L'intérêt de techniques de similarité est de mesurer le degré de similarité entre deux concepts ne se trouvent pas sur le même chemin. Evidemment, face à ce problème, la majorité des mesures utilise les liens taxinomiques pour calculer le degré de similarité.
<figure><img src="image_68.png" /><figcaption>(a) Hiérarchie de Concepts</figcaption></figure>

<table><caption>(b) Descriptions de Services et d'une requête</caption><thead><tr><th></th><th colspan="2">INPUT</th><th colspan="2">OUTPUT</th></tr><tr><th>Q</th><th>C<sub>8</sub></th><th>C<sub>4</sub></th><th>C<sub>7</sub></th><th></th></tr></thead><tbody><tr><th>S<sub>1</sub></th><td>C<sub>1</sub></td><td></td><td>C<sub>4</sub></td><td>C<sub>2</sub></td></tr><tr><th>S<sub>2</sub></th><td>C<sub>3</sub></td><td></td><td>C<sub>9</sub></td><td>C<sub>7</sub></td></tr><tr><th>S<sub>3</sub></th><td>C<sub>5</sub></td><td></td><td>C<sub>3</sub></td><td>C<sub>6</sub></td></tr></tbody></table>

### 7.2.2.1 Notion de similarité, de distance et de degré de relation sémantique

Il existe trois types de mesures sémantiques, chacune ayant des propriétés différentes :

- **La similarité sémantique** : On parle de mesure de similarité sémantique (i.e., semantic similarity) lorsque la mesure calcule si deux concepts sont similaires sémantiquement, au sens où ils partagent des propriétés et attributs communs.

- **Le degré de relation sémantique** : On parle de degré de relation sémantique (i.e., semantic relatedness) lorsque la mesure calcule si deux concepts sont reliés sémantiquement, au sens où ils sont liés dans leur fonction.

- **La distance sémantique** : On parle de distance sémantique (i.e. semantic distance) lorsque la mesure calcule si deux concepts sont distant sémantiquement.

La similarité sémantique et le degré de relation sémantique sont intéressants à présenter ensemble car ils ont le même type de monotonie : plus deux concepts sont reliés ou similaire, plus le score sémantique est grand. Autrement dit, soit $scr(x, y) \in [0, 1]$ une mesure donnant un score sémantique entre 0 et 1, alors que $scr$ représente une similarité sémantique ou un degré de relation sémantique, nous avons $scr(x, x) = 1$. Néanmoins, le degré de relation sémantique tient compte de plus d'informations que la similarité sémantique, puisqu'il utilise aussi les relations fonctionnelles entre les concepts. Ainsi, le degré de relation sémantique peut être considéré comme une généralisation de la similarité sémantique [Res95].

D'autre part, la courbe d'une fonction de distance sémantique est l'exact opposé de la courbe de similarité ou de degré de relation (les conversions linéaires d'une forme à l'autre sont ainsi couramment utilisées [Res95, JC97]). En ce sens, en reprenant la notation $scr(x,y)$ précédente, dans une distance sémantique nous avons $scr(x, x) = 0$. L'inconvénient principal de la notation de distance est qu'elle est ambiguë. En effet, elle désigne aussi bien l'inverse de la similarité sémantique que l'inverse du degré de relation sémantique.

L'évaluation du lien sémantique entre deux concepts dans une ontologie est un problème qui se pose de longue date dans le domaine de l'intelligence artificielle. La similarité sémantique est une évaluation du lien sémantique entre deux concepts dont le but est d'estimer le degré par lequel les concepts sont proches dans leur sens [Res99]. La définition donnée par Lin de la similarité sémantique repose sur trois suppositions [Lin98]. La similarité entre deux concepts est liée aux caractéristiques qu'ils ont en commun (plus ils ont de caractéristiques communes, plus les concepts sont similaires) et à leurs différences
(plus deux concepts sont différents, moins ils sont similaires). La similarité maximale est obtenue lorsque deux concepts sont identiques.

### 7.2.2.2 Mesures sémantiques exploitant des taxinomies de concepts

Au départ, nous fixons un certain nombre de notations que nous utiliserons pour décrire les formules sémantiques des différentes mesures présentées dans cette section :

- $c_1$ et $c_2$: Les concepts dont nous chercherons la distance.

- $dist_{XXX}$ et $sim_{XXX}$: Notation pour la distance et la similarité sémantique. Nous remplacerons XXX par l'acronyme du nom des auteurs.

- $ccp(c_1, c_2)$: Le noeud de la hiérarchie qui est le plus proche parent commun de $c_1$ et $c_2$ (i.e. *closest common parent*, notation de Zhong [ZZL+02]). Cette formulation est évidemment plus courante dans les systèmes dont les connaissances sont représentées uniquement sous forme de hiérarchie, mais elle est aussi souvent utilisée dans les systèmes possédant d'autres types de relations, la relation de hiérarchie ayant en général un traitement spécial prioritaire.

- $root$: Le noeud racine de la hiérarchie. Il représente le concept le plus général, englobant tous les concepts. Il est souvent nommé *thing* dans la hiérarchie de concepts (root étant le nom plus calculatoire lié à la structure arborescente d'une hiérarchie).

- $depth(c)$: La profondeur du noeud c dans la hiérarchie avec $depth(root) = 0$.

- $sp(c_1, c_2)$: Le plus court chemin entre $c_1$ et $c_2$ en suivant la hiérarchie (i.e., *shortest path*). Ce plus court chemin est un ensemble de couples de concepts, un couple représentant une arête et l'ensemble de ces arêtes le chemin.

- $len(c_1, c_2) = sp(c_1, c_2)$: La longueur du plus court chemin entre $c_1$ et $c_2$.

- $MAX = maxdepth(c)$: La hauteur maximale de la hiérarchie.

Il est intéressant de noter que par construction, le plus court chemin entre deux concepts dans une hiérarchie passe toujours par leur plus proche parent commun<fnref n="9" />. Cette propriété, bien que rarement directement nommée, permet de rapprocher certaines formules de distance à première vue radicalement différentes.

Nous présentons dans ce qui suit les mesures sémantiques se basant sur les longueurs de chemins. La source de connaissance est vue comme un arbre ontologique et les formules utilisent la longueur des chemins (pondérés ou non) pour déterminer la distance entre deux concepts. Cette idée part d'une intuition naturelle : dans une hiérarchie sémantique, plus deux concepts sont éloignés physiquement, plus ils sont éloignés sémantiquement.

### 7.2.2.3 Rada

**Rada et al.** fut le premier à envisager la distance entre concepts comme une distance métrique[RMB+89]. Il utilise comme source de connaissances la hiérarchie MeSH. En ce sens, il affirme que toute distance sémantique se doit de respecter les hypothèses de bases d'une distance métrique, à savoir si $f(x,y)$ est une distance métrique :

<footnote n="9">9. Cette hypothèse n'est valable que dans le cas où la hiérarchie n'autorise pas de multi-héritage. Dans le cas du multi-héritage, elle ne reste valable que si il n'existe qu'un seul et unique chemin hiérarchique entre les concepts cibles</footnote>
1. Existence du zéro : $\forall x, f(x, x) = 0$

2. Symétrie : $\forall(x, y), f(x,y) = f(y, x)$

3. Positivité : $\forall(x, y) f(x, y) \ge 0$

4. L'inégalité triangulaire : $\forall(x, y, z), f(x,y) + f(y, z) \ge f(x; z)$

Les trois premiers points sont admis par toutes les mesures actuelles. En revanche, l'inégalité triangulaire est souvent discutée et finalement rarement respectée. En effet, si les arêtes sont pondérées, alors elle n'est souvent plus valide [ZZL+02]. De même, la présence d'héritage multiple invalide cette propriété.

**Rada et al.** définit sa mesure de distance simplement :

$$ dist_{RAD}(c1,c2) = \frac{1}{len(c1,c2)} $$

où len est la fonction donnant la longueur du plus court chemin entre c1 et c2.

### 7.2.2.4 Zhong

Zhong dans [ZZL+02] utilise le principe de profondeur de sorte que la profondeur d'un noeud est représentative de la spécificité d'un concept. Pour ce faire, Zhong définit un coefficient (le milestone) pour chaque noeud n de sa hiérarchie. Cette valeur décroît en fonction de la profondeur et rentre en compte dans la formule finale :

$$ milestone(n) = \frac{1}{k^{depth(n)+1}} $$

où k est un paramètre permettant d'intensifier ou de diminuer la rapidité d'évolution du milestone en fonction de la profondeur. En pratique, k est toujours instancié à 2 (tel qu'utilisé entre autres dans le moteur de recherche sémantique Corese [CDF04]). La distance entre deux concepts c₁ et c₂ est alors définie par le milestone de c₁ et c₂ et par celui de leur plus proche parent ccp(c₁, c₂). On obtient alors : $dist_{ZHO}(c₁, c₂) = 2 * milestone(ccp(c₁, c₂)) - (milestone(c₁) + milestone(c₂))$

On remarque qu'en fait cette formule calcule une distance entre c₁ et ccp(c₁, c₂) (avec le calcul milestone(ccp(c₁, c₂) - milestone(c₁)) puis une distance entre c₂ et ccp(c₁, c₂) (avec le calcul milestone(ccp(c₁, c₂) - milestone(c₂)) et les additionne, permettant de faire l'analogie entre cette distance et une distance métrique pondérée.

### 7.2.2.5 Wu et Palmer

Wu et Palmer [WP94] travaillent sur la traduction automatique de l'anglais vers le Mandarin. Leur source de connaissance est WordNet. Leur formule utilise le plus proche parent des deux concepts x et y et de sa profondeur.

La distance sémantique s'énonce :

$$ dist_{WP}(c1, c2) = \frac{len(c1, ccp(c1,c2))+len(c2; ccp(c1,c2))}{len(c1, ccp(c1,c2))+len(c2, ccp(c1,c2))+2*depth(ccp(c1,c2))} $$
Cette distance utilise encore une fois l'hypothèse de profondeur. En effet, si l'on fixe l'ensemble des longueurs entre deux concepts (i.e. $len(c_1, ccp(c_1, c_2))$ et $len(c_2, ccp(c_1, c_2))$ sont alors constants), la distance diminue au fur et à mesure que la profondeur augmente (i.e. le fait que $depth(ccp(c1, c2))$ soit présent au dénominateur diminue la distance quand la profondeur augmente). **Cette mesure est ainsi sûrement l'une des plus précises dans la catégorie des mesures à longueur de chemin.** Cependant, il est à noter que les mesures utilisant la théorie de l'information (i.e., un corpus informationnel) obtiennent encore de meilleurs résultats. Un état de l'art et une comparaison de toutes les mesures dans le mémoire de thèse de Ferihane Kboubi [Kbo10].

Enfin, nous définissons un graphe de composition comme un plan (chemin) de services fonctionnellement composables comme suit.

**Définition 28 (Graphe de composition)** *Un graphe de composition est un graphe étiqueté de services P = ⟨S, D, c, γ_D⟩ tel que :*

- S={S<sub>1</sub>,...,S<sub>n</sub>} est un ensemble fini de services Web de cardinalité *n*,

- D : S × S est un ensemble fini de dépendances entre services,

- c : D → {logique, empirique} permettant d'associer à chaque dépendance un type soit logique ou soit empirique (étiquette de la dépendance),

- γ<sub>D</sub> : D → [0,1].

La première phase de l'approche de composition BIOMED est à construire des chemins (plans) de composition constitués d'un ensemble de services atomiques composables de manière exacte ou approchée selon un ou plusieurs patrons de composition, le tout constituant un graphe de composition.

Un graphe de composition est généré à la suite de cette phase pouvant contenir un ou plusieurs plans de composition entre les entrées et les sorties souhaitées. Chaque plan de composition contient un nombre variable noté *p* de services atomiques composables. La valeur *p* est variable d'un plan de composition possible à un autre; la valeur minimale de *p* étant 2 (un plan comprenant seulement deux services atomiques). Dans une seconde phase, nous identifions parmi les plans de composition ceux qui satisfassent les contraintes non fonctionnelles. Un mécanisme de classement prend place pour identifier les plans les plus optimaux en termes de QdS.

## 7.3 Composabilité non fonctionnelle et Sélection des meilleurs plans

Comme signalé dans le chapitre 4 de ce mémoire la recherche du plan le plus satisfaisant de composition étant un problème NP-difficile nous proposons deux heuristiques pour résoudre approximativement le problème de l'optimisation de la composabilité non fonctionnelle<sup>10</sup>. Ces deux heuristiques permettent d'identifier les plans de composition satisfaisant au mieux les contraintes non fonctionnelles d'une requête Q. Le première est

<footnote n="10">10. Nous avons consacré l'annexe B à l'optimisation multi-critère et à l'heuristique Skyline. Outre cette dernière heuristique, d'autres heuristiques non Pareto-like existent comme les algorithmes génétiques, l'Analyse Formelle des Concepts, le clustering, etc.</footnote>
<table><caption>TABLE 7.4 – Agrégation des paramètres QoS dans un patron de composition</caption><thead><tr><th>Propriété QoS</th><th>Séquentiel</th><th>And</th><th>Loop</th></tr></thead><tbody><tr><td>le temps de réponse</td><td>Σ<sup>n</sup><sub>i=1</sub> rt<sub>i</sub></td><td>max(rt<sub>i</sub>)</td><td>rt × k</td></tr><tr><td>Le débit</td><td>min(th<sub>i</sub>)</td><td>min(th<sub>i</sub>)</td><td>th</td></tr><tr><td>La disponibilité</td><td>Π<sup>n</sup><sub>i=1</sub> av<sub>i</sub></td><td>Π<sup>n</sup><sub>i=1</sub> av<sub>i</sub></td><td>av<sup>k</sup></td></tr><tr><td>La fiabilité</td><td>Π<sup>n</sup><sub>i=1</sub> re<sub>i</sub></td><td>Π<sup>n</sup><sub>i=1</sub> re<sub>i</sub></td><td>re<sup>k</sup></td></tr></tbody></table>

<table><caption>TABLE 7.5 – Les services sélectionnés pour le workflow de l'analyse phylogénétique</caption><thead><tr><th>Service</th><th>Temps de réponse</th><th>Débit</th><th>Disponibilité</th></tr></thead><tbody><tr><td>GetEntryDDBJ (S<sub>1</sub>)</td><td>15</td><td>10</td><td>95</td></tr><tr><td>DBFetch (S<sub>2</sub>)</td><td>10</td><td>12</td><td>98</td></tr><tr><td>eFetchSequence(S<sub>3</sub>)</td><td>10</td><td>18</td><td>96</td></tr><tr><td>WSNCBIBlast (S<sub>4</sub>)</td><td>8</td><td>20</td><td>98</td></tr><tr><td>WSFASTA (S<sub>5</sub>)</td><td>10</td><td>15</td><td>98</td></tr><tr><td>runBlatService (S<sub>6</sub>)</td><td>10</td><td>10</td><td>99</td></tr><tr><td>runPhylipFromDna (S<sub>7</sub>)</td><td>10</td><td>15</td><td>97</td></tr><tr><td>runCreateTreeFromClustalW(S<sub>8</sub>)</td><td>8</td><td>15</td><td>98</td></tr><tr><td>runClustalW (S<sub>9</sub>)</td><td>13</td><td>15</td><td>97</td></tr></tbody></table>

dite approche de composabilité non fonctionnelle globale dans le sens où elle évalue les plans en termes de QdS agrégés et la seconde est dite locale dans le sens où les contraintes non fonctionnelles sont évaluées au niveau de chaque service atomique $S_{ij}$ d'un plan de composition $PC_i$

### 7.3.1 Approche globale

Etant donné un graphe de composition, la seconde phase de l'approche de composition proposée dans cette thèse consiste à étiqueter chaque plan de composition $PC_i$ par les valeurs globales (agrégées) de ses attributs QdS. Le graphe de composition est représenté une matrice de sorte que chaque plan $Plan_i$ sera associé à une valeur de QdS par l'agrégation des valeurs des critères de ses services atomiques selon le Tableau 7.4.

La matrice des plans de composition et des valeurs agrégées de leur QdS se présente comme suit :

$$ \left( \begin{array}{c} \text{QdS}_1 \quad \text{QdS}_2 \quad \dots \quad \text{QdS}_r \\ \text{Plan}_1 \quad \dots \quad \dots \quad \dots \\ \text{Plan}_2 \quad \dots \quad \dots \quad \dots \\ \vdots \\ \text{Plan}_n \end{array} \right) $$

A une requête étendue comprenant $m$ contraintes QdS parmi les $r$ contraintes possibles, la matrice $(n,r)$ sera réduitre à une matrice $(n,m)$ telles que les $m$ colonnes parmi les $r$ correspondent aux attributs QdS choisis par le client. Nous procédons ensuite en deux étapes :
<figure><img src="image_69.png" /><figcaption>FIGURE 7.3 – Exemple de Skyline de Plan de composition</figcaption></figure>

<figure><img src="image_70.png" /><figcaption>FIGURE 7.4 – Skyline de différents types de datasets</figcaption></figure>
<figure><img src="image_71.png" /><figcaption>FIGURE 7.5 – Clusterisation hiérarchique d'un skyline de services</figcaption></figure>
1. La première étape correspond à un filtrage permettant de ne retenir parmi les plans de composition que ceux dont toutes les valeurs QdS agrégées vérifient les contraintes globales de la requête. **Ces plans seront dits admissibles.**

2. La seconde étape consiste à chercher parmi les plans admissibles le meilleur plan, i.e., celui qui maximise au plus les valeurs agrégées des attributs ‘positifs’ et minimise au plus les valeurs agrégées des attributs ‘négatifs’ et ce, en utilisant une méthode de décision multicritère basée l’opérateur *Skyline*. La technique de skyline nous permettra de déterminer l’ensemble de services qui ne sont dominés par aucun autre service. La figure 7.3 illustre un skyline de plans de composition dans un espace bidimensionnel dont le premier axe désigne la disponibilité et le second le temps de réponse. Nous remarquons que le plan *a* appartient au skyline puisqu’il n’existe un plan ayant un meilleur temps de réponse *et* en même temps un prix plus petit. C’est le cas des plans *b*, *c*, *d* et *e*. Contrairement au service *f* qui ne fait pas partie du skyline et il est dominé par les plans *b*, *c* et *d*. Notons qu’un skyline de plans admissibles de composition comprend un ensemble de plans incomparables entre eux, en l’absence de préférences prédéfinies. En l’occurrence, un client pourrait être intéressé par le plan *a* à cause de son temps de réponse minime malgré son prix élevé, un autre client serait plutôt intéressé par le plan *e*. Cependant la taille d’un skyline peut être importante et cela dépend étroitement de la distribution des données QdS et la corrélation entre les différents paramètres QdS. La figure 7.4 illustre l’exemple de trois configurations de taille de skyline dans un espace bi-dimensionnel : (a) des dataset indépendants où les valeurs des deux paramètres QdS sont indépendantes, (b) des datasets corrélés, un service qui est bon par rapport à critère, il l’est aussi par rapport à l’autre critère, (c) des datasets anti-corrélés lorsqu’il y a une véritable distribution au niveau des datasets. Le nombre de services dans un skyline est relativement petit pour les datasets corrélés, moyen pour les datasets indépendants et large pour les datasets anti-corrélés.

Lorsque la taille d'un skyline des plans admissibles de composition est large, il est possible de classer ces plans grâce à une méthode de ranking comme celles de FAGIN et al. (TA : Threshold Algorithm) ou NRA (No Random Access) exposées dans [FLN01, FKS03], LARA (Lattice-based Rank Aggregation ) proposée dans [MYCC07], ou WTKSF [GVRA09] ou encore TKSI proposée dans [GV09]. Bien d'autres algorithmes efficients de ranking sont disponibles et sont cités dans la bibliographie de ce document comme par exemple [YST+09] ou [KPSV09]. Il est aussi tout à fait possible de se baser sur une méthode de clusterisation hiérarchique pour identifier des clusters contenant les plans les plus représentatifs du skyline comme l'illustre la figure 7.5.

**Exemple 15** Nous considérons l'ensemble des services sélectionnés comme candidats pour l'implémentation de l'exemple 13. Nous spécifions pour chacun des services la valeur de leurs propriétés QdS relatives au temps de réponse, débit et disponibilité. Le tableau 7.5 (page 187) illustre toutes les valeurs QdS pour chaque service. Le graphe de composition déduit comprend quinze plans de composition possibles dont les valeurs QdS agrégées sont illustrés par la matrice suivante :
<table><thead><tr><th></th><th>QdS<sub>1</sub></th><th>QdS<sub>2</sub></th><th>QdS<sub>3</sub></th></tr></thead><tbody><tr><td>Plan<sub>1</sub></td><td>33</td><td>10</td><td>96</td></tr><tr><td>Plan<sub>2</sub></td><td>31</td><td>10</td><td>97</td></tr><tr><td>Plan<sub>3</sub></td><td>35</td><td>10</td><td>97</td></tr><tr><td>Plan<sub>4</sub></td><td>33</td><td>11</td><td>97</td></tr><tr><td>Plan<sub>5</sub></td><td>28</td><td>11</td><td>97</td></tr><tr><td>Plan<sub>6</sub></td><td>28</td><td>11</td><td>97.6</td></tr><tr><td>Plan<sub>7</sub></td><td>28</td><td>11</td><td>97.6</td></tr><tr><td>Plan<sub>8</sub></td><td>30</td><td>11</td><td>97.6</td></tr><tr><td>Plan<sub>9</sub></td><td>28</td><td>11</td><td>98</td></tr><tr><td>Plan<sub>10</sub></td><td>26</td><td>11</td><td>98</td></tr><tr><td>Plan<sub>11</sub></td><td>26</td><td>15</td><td>97</td></tr><tr><td>Plan<sub>12</sub></td><td>26</td><td>15</td><td>97.33</td></tr><tr><td>Plan<sub>13</sub></td><td>30</td><td>15</td><td>97</td></tr><tr><td>Plan<sub>14</sub></td><td>28</td><td>15</td><td>97.33</td></tr><tr><td>Plan<sub>15</sub></td><td>23</td><td>15</td><td>97</td></tr></tbody></table>

Supposons que le scientifique soit intéressé par un plan de composition dont le temps de réponse ne dépasse pas 30 ms, avec un débit au moins égal à 10 et une disponibilité au moins égale à 97%. Ainsi, les plans admissibles sont les suivants :

<table><thead><tr><th></th><th>QdS<sub>1</sub></th><th>QdS<sub>2</sub></th><th>QdS<sub>3</sub></th></tr></thead><tbody><tr><td>Plan<sub>6</sub></td><td>28</td><td>11</td><td>97.6</td></tr><tr><td>Plan<sub>7</sub></td><td>28</td><td>11</td><td>97.6</td></tr><tr><td>Plan<sub>8</sub></td><td>30</td><td>11</td><td>97.6</td></tr><tr><td>Plan<sub>9</sub></td><td>28</td><td>11</td><td>98</td></tr><tr><td>Plan<sub>10</sub></td><td>26</td><td>11</td><td>98</td></tr><tr><td>Plan<sub>11</sub></td><td>26</td><td>15</td><td>97</td></tr><tr><td>Plan<sub>12</sub></td><td>26</td><td>15</td><td>97.33</td></tr><tr><td>Plan<sub>13</sub></td><td>30</td><td>15</td><td>97</td></tr><tr><td>Plan<sub>14</sub></td><td>28</td><td>15</td><td>97.33</td></tr><tr><td>Plan<sub>15</sub></td><td>23</td><td>15</td><td>97</td></tr></tbody></table>

Le skyline des services correspondant à l'espace de solutions admissibles comprend les trois services suivants :

<table><thead><tr><th></th><th>QdS<sub>1</sub></th><th>QdS<sub>2</sub></th><th>QdS<sub>3</sub></th></tr></thead><tbody><tr><td>Plan<sub>10</sub></td><td>26</td><td>11</td><td>98</td></tr><tr><td>Plan<sub>12</sub></td><td>26</td><td>15</td><td>97.33</td></tr><tr><td>Plan<sub>15</sub></td><td>23</td><td>15</td><td>97</td></tr></tbody></table>

### 7.3.2 Approche locale

La première étape consiste à sélectionner parmi les plans possibles de composition ceux qui vérifient toutes les contraintes QdS localement, i. e. que tous les services atomiques composant le plan vérifient les contraintes QdS de la requête. La seconde étape est une
étape de classement des services composites sélectionnés lors de l'étape précédente sur la base de leur **fonction d'utilité globale**. Nous nommons la première étape **optimisation locale**. En partant du graphe de composition, nous allons éliminer les plans qui ne répondent pas aux exigences de qualité de la requête au niveau des QdS. Ensuite, pour chaque plan de composition (service composite), nous allons considérer l'ensemble de ses services atomiques lesquels seront affectés de leur vecteur d'attributs QdS

L'heuristique ici proposée vise à ne sélectionner parmi les services composites que ceux dont tous les services atomiques vérifient toutes les *m* contraintes exigées par la requête. L'optimisation locale est, en fait, computationnellement peu coûteuse contrairement aux algorithmes dont la complexité est exponentielle.

Nous allons considérer la matrice suivante listant pour chaque plan de composition *Plan*<sub>*i*</sub>, i allant de 1 à *q* où *q* est le nombre de plans de composition comprenant un ensemble de services atomiques fonctionnellement composables, ces services atomiques lesquels seront affectés leurs vecteurs normalisés d'attributs QdS

$$
\left(
\begin{array}{llccc}
\text{Plan} & \text{Serviceatomique} & \text{QdS}_1 & \text{QdS}_2 & \dots & \text{QdS}_m \\
\text{PC}_1 & \text{SA}_{11} & 10 & 96 & 0 & 0 \\
& \text{SA}_{21} & 10 & 97 & 0 & 0 \\
& \text{SA}_{31} & 10 & 97 & 0 & 0 \\
\text{PC}_2 & \text{SA}_{12} & 11 & 97 & 0 & 0 \\
& \text{SA}_{22} & 11 & 97 & 0 & 0 \\
\text{PC}_3 & \text{SA}_{13} & 11 & 97.6 & 0 & 0 \\
\text{....} & & 11 & 97.6 & 0 & 0 \\
\text{...} & & 11 & 97.6 & 0 & 0 \\
\text{...} & & 11 & 98 & 0 & 0 \\
\text{PC}_n & \text{SA}_{1n} & 11 & 98 & 0 & 0 \\
& \text{SA}_{2n} & 15 & 97 & 0 & 0
\end{array}
\right)
$$

Chaque valeur *q* d'un attribut QdS positif sera normalisé comme suit :

$$q_{\text{norm}} = (q - q_{\text{min}}) / (q_{\text{max}} - q_{\text{min}})$$

où $q_{min}$ (resp. $q_{max}$) est la plus petite (resp. grande) valeur de l'attribut QdS concerné dans tous les services atomiques des divers plans possibles de composition.

Pour chaque attribut $QdS_j$ les valeurs correspondant aux services atomiques sont comprises initialement dans l'intervalle $[q_{jmin}, q_{jmax}]$ avec $j \in [1, m]$, une fois les valeurs normalisées elles seront comprises dans l'intervalle $[0, 1]$.

**Exemple 16** Pour l'ensemble des services du tableau 7.5, les différents intervalles de qualité identifiés sont :

- L'intervalle $[q_{1min}, q_{1max}]$ est $[8, 15]$.

- L'intervalle $[q_{2min}, q_{2max}]$ est $[10, 20]$.

- L'intervalle $[q_{3min}, q_{3max}]$ est $[97, 99]$.

Nous allons choisir *l* niveaux de qualité (le nombre *l* est fixé a priori et plus souvent en accord avec les experts du domaine). Ceci va nous donner la structure suivante : en colonnes
<figure><img src="image_72.png" /><figcaption>FIGURE 7.6 – Différents niveaux de qualité de service</figcaption></figure>

les attributs QdS et en lignes les intervalles de qualité notés IQ. Ainsi, nous disposons de l niveaux de qualité IQ$_k$ avec k variant de 1 à l tel que illustré par la figure 7.6.

Considérons *l*-2 intervalles de qualité en excluant les niveaux *min* et *max*. Pour l'exemple précédent, en choisissant *l* = 5, nous obtiendrons pour les intervalles normalisés les niveaux 0, 0,25, 0,5, 0,75 et 1. Les niveau de qualité qui seront les centroïdes des clusters seront les trois suivants 0,25, 0,5 et 0,75.

<table><thead><tr><td>Niveaux de qualité</td><td>Temps de réponse</td><td>Débit</td><td>Disponibilité</td></tr></thead><tbody><tr><td>IQ<sub>5</sub> = max (1)</td><td>15</td><td>20</td><td>99%</td></tr><tr><td>IQ<sub>4</sub>= 0,75</td><td>13</td><td>17,5</td><td>98%</td></tr><tr><td>IQ<sub>3</sub>= 0,5</td><td>11</td><td>15</td><td>97%</td></tr><tr><td>IQ<sub>2</sub>=0,25</td><td>9</td><td>12,5</td><td>96%</td></tr><tr><td>IQ<sub>1</sub>=min (0)</td><td>7</td><td>10</td><td>95%</td></tr></tbody></table>

Une fois les (*l*-2) valeurs calculées comme valeurs des centroïdes des clusters, nous procédons à la clustérisation à l'aide d'un classifieur sur la matrice donnant en ligne les services candidats *Scandidats* à la composition et comme colonnes le vecteur d'attributs QdS de chaque $S_{candidat}$, ce qui va donner (*l* × 2) × *m* clusters. Dans notre exemple, il s'agira de générer avec l'algorithme de K-Means pour chaque attribut QdS parmi les trois choisis, 3 clusters correspondant aux intervalles de qualité 0,25, 0,5 et 0,75. Cependant, il est possible d'utiliser une des bibliothèques GnuGPL WEKA (Waikato Environment for Knowledge Analysis) de l'université Waikato<sup>11</sup> en Australie ou TANAGRA de l'Université de Lyon 2 en France<sup>12</sup>.

En effet, la clustérisation va servir à réduire l'espace de sélection des plans de compo-

<footnote n="11">11. Le site de WEKA est à l'adresse suivante :
http://www.cs.waikato.ac.nz/ml/weka/</footnote>

<footnote n="12">12. Le site de TANAGRA est à l'adresse suivante :
http://eric.univ-lyon2.fr/ricco/tanagra/fr/tanagra.html</footnote>
sition comme suit :

La clustérisation fait regrouper au sein de chaque cluster et pour chaque attribut QdS les services dont les valeurs sont proches de la valeur du centroïde. Ainsi, pour une requête ayant spécifié une contrainte par exemple temps de réponse inférieur à 8 ms, le cluster autour de la valeur du centroïde 0,25 (normalisée) ou 9 ms comme valeur non normalisée va contenir obligatoirement les services dont la valeur de l'attribut n°1 est comprise entre 7 et 9 ms. Dans ce cas c'est le cluster *min* (pour un attribut 'négatif') qui sera choisi comme espace pouvant contenir les services vérifiant l'attribut n°1 du client.

Les services atomiques d'un cluster seront triés par valeurs décroissantes entre 0,25 et 0 (comme valeurs normalisées); la valeur normalisée de la contrainte usager étant égale à 0,125, seuls les services dont les valeurs normalisées de l'attribut 1 comprises entre 0,125 et 0 seront retenus comme candidats à l'admissibilité. Pour un attribut 'positif', ce sera le cluster *max* qui sera choisi avec une sélection appropriée à l'intérieur de ce cluster des services atomiques respectant la contrainte du client. Un tri croissant à l'intérieur du sous-cluster choisi permettra de sélectionner les services atomiques candidats à l'admissibilité pour ledit attribut entre la valeur normalisée de la contrainte QdS de l'usager et la valeur maximale 1.

Lorsque le nombre de niveaux de qualité est assez élevé, il est possible que dans le cas d'attributs négatifs (resp. positifs), ce soit *hyper-cluster* qui contient les services atomiques susceptibles de vérifier la contrainte QdS de l'usager hyper-cluster constitué par le cluster *min* (resp. *max*) et un ou plusieurs clusters correspondants à des niveaux supérieurs (resp. inférieurs) de qualité. Le tri par valeurs décroissantes (resp. croissantes) à l'intérieur de l'hyper-cluster permet de sélectionner les services atomiques admissibles. Une fois, pour chaque service atomique et pour les attributs QdS, la sélection de ceux qui sont admissibles est effectuée, nous revenons à la matrice des plans possibles de composition en substituant aux valeurs des attributs QdS dans la cas de vérification de la contrainte de l'usager, la valeur 1, sinon 0.

Les éléments de la matrice seront mis à zéro initialement, comme suit :

<table><thead><tr><th>Plan</th><th>ServicesAtomique</th><th>QdS<sub>1</sub></th><th>QdS<sub>2</sub></th><th>...</th><th>QdS<sub>m</sub></th></tr></thead><tbody><tr><td rowspan="3">PC<sub>1</sub></td><td>SA<sub>11</sub></td><td>0</td><td>0</td><td>0</td><td>0</td></tr><tr><td>SA<sub>21</sub></td><td>0</td><td>0</td><td>0</td><td>0</td></tr><tr><td>SA<sub>21</sub></td><td>0</td><td>0</td><td>0</td><td>0</td></tr><tr><td rowspan="2">PC<sub>2</sub></td><td>SA<sub>12</sub></td><td>0</td><td>0</td><td>0</td><td>0</td></tr><tr><td>SA<sub>22</sub></td><td>0</td><td>0</td><td>0</td><td>0</td></tr><tr><td>PC<sub>3</sub></td><td>SA<sub>13</sub></td><td>0</td><td>0</td><td>0</td><td>0</td></tr><tr><td>...</td><td></td><td>0</td><td>0</td><td>0</td><td>0</td></tr><tr><td>...</td><td></td><td>0</td><td>0</td><td>0</td><td>0</td></tr><tr><td>...</td><td></td><td>0</td><td>0</td><td>0</td><td>0</td></tr><tr><td rowspan="2">PC<sub>n</sub></td><td>SA<sub>1n</sub></td><td>0</td><td>0</td><td>0</td><td>0</td></tr><tr><td>SA<sub>2n</sub></td><td>0</td><td>0</td><td>0</td><td>0</td></tr></tbody></table>

Ensuite, à partir des *m* sous-clusters contenant les services atomiques dont l'attribut de qualité *k* (variant de 1 à *m*) vérifie la contrainte de l'usager, l'élément de la ligne du service existant dans le sous-cluster et pour la colonne correspondant à l'attribut *k* sera
mis à 1.

Parmi les N plans possibles seuls les plans dont tous les éléments de la sous-matrice sont à 1 (i. e. tous les services atomiques vérifient toutes les contraintes de l'usager) seront retenus. Le cas illustré dans la matrice suivante montre que seuls les plans $PC_1$ et $PC_n$ sont à retenir :

<table><thead><tr><th>Plan</th><th>ServicesAtomique</th><th>QdS<sub>1</sub></th><th>QdS<sub>2</sub></th><th>...</th><th>QdS<sub>m</sub></th></tr></thead><tbody><tr><td rowspan="3">PC<sub>1</sub></td><td>SA<sub>11</sub></td><td>1</td><td>1</td><td>1</td><td>1</td></tr><tr><td>SA<sub>21</sub></td><td>1</td><td>1</td><td>1</td><td>1</td></tr><tr><td>SA<sub>21</sub></td><td>1</td><td>1</td><td>1</td><td>1</td></tr><tr><td rowspan="2">PC<sub>2</sub></td><td>SA<sub>12</sub></td><td>1</td><td>0</td><td>1</td><td>1</td></tr><tr><td>SA<sub>22</sub></td><td>1</td><td>1</td><td>1</td><td>1</td></tr><tr><td>PC<sub>3</sub></td><td>SA<sub>13</sub></td><td>1</td><td>1</td><td>0</td><td>0</td></tr><tr><td>...</td><td></td><td>0</td><td>0</td><td>0</td><td>0</td></tr><tr><td>...</td><td></td><td>0</td><td>0</td><td>0</td><td>0</td></tr><tr><td>...</td><td></td><td>0</td><td>0</td><td>0</td><td>0</td></tr><tr><td rowspan="2">PC<sub>n</sub></td><td>SA<sub>1n</sub></td><td>1</td><td>1</td><td>1</td><td>1</td></tr><tr><td>SA<sub>2n</sub></td><td>1</td><td>1</td><td>1</td><td>0</td></tr></tbody></table>

Pour l'obtention des ((l-2) × m) clusters en utilisant l'algorithme K-Means, le coût total est en $O(m(l-2)n)$ où m est le nombre d'attributs QdS de la requête qualité de l'usager, l est le nombre d'intervalle de qualité, n le nombre total de services présents dans tous les plans possibles de composition et k le nombre maximal d'itérations de l'algorithmes K-Means.

En conséquence, le coût total de cette première étape est proprement **polynomial** comprenant le coût du prétraitement, le coût de la clustérisation, le coût de l'identification du cluster (ou de l'hyper-cluster) de sélection et le coût du tri. Parmi les services composites admissibles ainsi sélectionnés, il faudra dans l'étape suivante sélectionner le ou les plus satisfaisant (s).

La dernière étape de classement se base sur la fonction globale d'utilité<fnref n="13" /> de sorte que chaque service *admissible* sélectionné au cours de la première étape sera affecté de sa fonction d'utilité globale. Pour un service composite $SC_k$ le vecteur QdS s'écrit comme suit : $Q_{SC_k} = [Q_{SC_k}^1, ..., Q_{SC_k}^m]$ tel que $Q_{SC_k}^l$ est la valeur agrégée de l'attribut $QdS_l$ parmi les m attributs de la requête de l'usager calculée avec les fonctions d'agrégation correspondant à la nature de l'attribut et aux patrons de composition intervenant dans le plan de composition de $SC_k$ pouvant contenir n services atomiques.

Pour un plan de composition $SC_k$, la fonction d'utilité globale normalisée s'écrit :

$$F_{SC_k} = (\sum_j Q_{SC_k}^m) / m, j \in [1,...,m].$$

Pour les attributs qualitatifs négatifs, on prendra le complément à 1 comme valeurs de ces attributs (qu'elles soient normalisées ou non), de sorte que le meilleur service composite est celui qui a la plus forte valeur comme fonction d'utilité globale. Alors, un simple tri des services composites admissibles permet d'identifier le meilleur plan. La méthode reste peu coûteuse même si le nombre de services candidats est très élevé.

<footnote n="13">13. La formule de cette fonction a été présentée dans le chapitre 4 page 89</footnote>
## 7.4 Conclusion

L'approche de composition proposée dans ce chapitre permet de sélectionner un ensemble de services atomiques vérifiant à la fois les conditions de composabilité exacte ou approchée au niveau fonctionnel et les contraintes non fonctionnelles d'une requête étendue. Pour ce faire, nous avons proposé : (1) deux nouveaux axiomes permettant d'inférer une composabilité fonctionnelle logique (exacte ou approchée) entre services et (2) d'utiliser des techniques de similarité sémantique pour calculer la similitude entre concepts au cas où les techniques de raisonnement échouent pour déduire une composabilité fonctionnelle empirique (exacte ou approchée). Un graphe de composition est généré comprenant l'ensemble des chemins (plans) de composition constitués par les services Web atomiques composables de manière exacte ou approchée selon un ou plusieurs patrons de composition ; chaque plan de composition est étiquetée par la valeur agrégée de ses critères QdS. La seconde étape consiste à sélectionner parmi les plans de composition possibles (i.e., vérifiant la composabilité fonctionnelle exacte ou approchée) ceux qui sont dits admissibles (i.e. vérifiant les contraintes de qualité de la requête de l'usager) pour ensuite procéder au classement de ces derniers.

Deux heuristiques de sélection et de classement des plans de composition sont proposées dans cette thèse :

- La première consiste à appliquer la même technique utilisée dans la découverte à savoir une combinaison de l'heuristique de skyline et l'algorithme de classmeent top-k.

- La seconde consiste à sélectionner les plans de composition, parmi les plans possibles de composition, et dont les services atomiques les composant, vérifient toutes les contraintes QdS de la requête de l'usager. Cette sélection s'effectue une fois les valeurs des attributs de qualité normalisées de ces services atomiques et les services atomiques de tous les plans possibles de composition clustérisés en fonction d'un certain nombre de niveaux de qualité choisi entre [0, 1] à l'aide d'un classifieur non supervisé. Une fois les plans de composition admissibles sélectionnés, une étape de classement de ces derniers est effectuée sur la base de la valeur normalisée de la fonction d'utilité globale de chacun des plans admissibles.
Conclusion Générale et
Perspectives
<figure><img src="image_73.png" /></figure>
La thématique de cette thèse traite du partage de données, d'applications et/ou de services dans le domaine bioinformatique ; partage favorisant les recherches multi-centriques tant fondamentales que cliniques dans un domaine qui connaît un grand essor exigeant la mise en œuvre d'infrastructures favorisant le partage, la réutilisation, l'interopérabilité et le retour d'expériences. Rappelons que l'objectif visé par la notion de service Web sémantique est de créer un Web sémantique de services dont les propriétés, les capacités, les interfaces et les effets sont décrits de manière non ambiguë et exploitable par des machines et ce, en utilisant les couches techniques de l'infrastructure existante des services Web et sans être conceptuellement indépendants. Des frameworks de services Web sémantiques ont été proposés depuis l'apparition du concept du Web sémantique en 2001 ayant pour objectifs d'expliciter les propriétés sémantiques pertinentes des services Web garantissant l'automatisation des processus de découverte, sélection, invocation et composition (i.e., tout au long du cycle de vie d'un service Web). Cependant, cet effort de sémantisation apporté par chacun des frameworks a fait émerger des descriptions hétérogènes entre elles rajoutant ainsi une nouvelle forme d'hétérogénéité.

Aujourd'hui que des portails de services Web à l'instar de BioMoby ou Seekda voient leur volume (en termes de nombre de services et de fournisseurs) augmenter à grande allure, il est devenu urgent selon nous de pallier la nouvelle hétérogénéité sémantique induite par les frameworks proposés tant au niveau des descriptions qu'au niveau des annotations qui sont elles-mêmes définies à partir d'ontologies hétérogènes. En effet, au niveau des frameworks de descriptions de services Web sémantiques, le recours aux ontologies est devenu un passage obligé tant que les ontologies favorisent le partage, la réutilisation et l'interopérabilité, mais là aussi une nouvelle hétérogénéité est apparue dès lors que le recours aux ontologies peut se traduire par un choix parmi une large éventail d'ontologies allant de l'informel (thésaurus ou méta-thésaurus comme ceux du domaine du domaine biomédical) au formel pour aboutir aux ontologies lourdes.

## Les contributions de la thèse

Nous avons proposé dans cette thèse un méta-framework stratifié couvrant des ressources hétérogènes, des descriptions hétérogènes et des ontologies hétérogènes. Dans le cadre du méta-framework proposé, le travail mené a consisté à proposer une méthodologie de sémantisation de services Web créés sous différents frameworks réalisant une méta-normalisation sémantique de leurs descriptions donnant lieu à un ensemble de descriptions canoniques, une réconciliation tant sémantique qu'ontologique sur lesquelles s'adossent les services Web sémantiques à une méta-carte ontologique médiant les ontologies de référence et une ontologie fondationnelle. Cette méta-carte est constituée d'hyper-concepts reliés par le biais d'une sémantique référentielle aux concepts (intensions) et leurs instances (extensions) des ontologies originelles. C'est à travers cette sémantique référentielle que se réalise la conceptualisation partagée (méta-conceptualisation) conciliant les points de vue conceptuels des ontologies originelles. C'est aussi sur la base de cette sémantique référentielle et méta-conceptuelle que se sont effectuées les annotations sémantiques des services Web. Par ailleurs, l'engagement sémantique de la méta-carte ontologique vis-à-vis de l'ontologie fondationnelle DOLCE (choisie parmi d'autres) nous a permis de faire émerger une
sémantique inférentielle offrant la possibilité de raisonner sur les connaissances émergentes des descriptions canoniques, des annotations sémantiques et des concepts unifiés grâce à une sémantique formelle valide dans l'univers du discours garantissant ainsi la validité des inférences effectuées.

En résumé, les contributions majeures de cette thèse est un modèle d'alignement sémantique réalisant une méta-normalisation des descriptions émanant des trois frameworks OWL-S, WSMO et SAWSDL, une méta-carte ontologique reflétant les sémantiques référentielle et différentielle des concepts du domaine ciblé et une sémantique axiomatique comprenant des axiomes de relaxation permettant d'élargir la portée et la couverture des annotations sémantiques tout en exploitant les connaissances ontologiques de la méta-carte. Deux grandes classes de processus sont considérées : la découverte et la compositon (vue dans notre approche comme une chorégraphie) de services Web décrits canoniquement et annotés sémantiquement sur la base de la méta-carte ontologique. Ces deux processus sont effectués à travers un moteur inférentiel DATALOG-like conçu comme un méta-service Web déductif et sur la base de l'axiomatique inférentielle proposant des opérateurs de relaxation élargissant, dans le cas d'une découverte, la couverture sémantique des descriptions et l'espace de recherche d'une requête de découverte et, dans le cas d'une composition, en précisant les règles de composabilité des services atomiques. Les expérimentations menées montrent l'impact des techniques de relaxation sur la taille de l'espace de recherche des services découverts au niveau de l'approche de découverte.

Dans le cas de la découverte comme dans celui de la composition, nous avons considéré des requêtes étendues couvrant à la fois des propriétés fonctionnelles et d'autres non fonctionnelle notamment relatives à la QdS. Pour la partie non fonctionnelle, nous avons proposé une heuristique basée sur l'opérateur skyline (qui est une méthode PARETO-like pour la problématique de sélection des services Web répondant aux critères non fonctionnels) suivie d'une procédure de classement des top-k meilleurs services.

L'approche de composition proposée dans ce mémoire se base aussi sur le moteur inférentiel afin de déduire des chemins possibles de services composables constitués de l'ensemble des services atomiques vérifiant les critères de composabilité exacte et approchée. Nous avons redéfini la notion de composabilité afin disposer d'une approche flexible permettant de déduire des dépendances logiques (en se basant sur les techniques de raisonnement) ou empirique (en se basant sur des mesures de similarité).

De ce fait, notre approche est originale à plus d'un titre en offrant une triple sémantique à la fois interprétative avec un ensemble de descriptions canoniques, formelle grâce aux annotations sémantiques définies sur la base de la méta-carte ontologique et inférentielle basée sur une sémantique axiomatique. Enfin, notre approche de découverte et de composition est originale du fait de l'inexistence de techniques de raisonnement et de classement dans la plupart des projets existants, dans la littérature.

## Perspectives

Les contributions proposées dans cette thèse nous ont amené à envisager des perspectives intéressantes tant à caractère théorique que pratique. Nous présentons dans ce qui suit celles qui nous semblent les plus prometteuses.
L'ensemble des techniques de raisonnement proposées dans cette thèse exploitant la triple sémantique interprétative (descriptive), formelle (ontologique) et inférentielle induite par le modèle d'alignement et la méta-carte ontologique est totalement généralisable à n'importe quel domaine ce qui pourrait rendre le méta-framework BIOMED générique. La première perspective à court terme de ce travail de recherche consiste à enrichir les techniques de raisonnement proposées avec de nouveaux opérateurs de relaxation permettant d'exploiter les primitives non logiques d'un domaine ciblé. Notre objectif serait d'enrichir la méta-carte ontologique par un ensemble de règles permettant d'exprimer des contraintes du domaine telles que les propriétés spatio-temporelles des entités décrites par la méta-carte. Cet ensemble de règles serait généré par le langage de règles SWRL<sup>14</sup> (Semantic Web Rule Language) qui a été proposé par le W3C pour le Web sémantique combinant les langages OWL et RuleML.

D'un autre côté, il serait utile de rechercher des techniques d'optimisation de la complexité temporelle du temps de calcul du modèle minimal de la base déductive, l'objectif final étant de considérer des référentiels contenant les descriptions de plusieurs dizaines de milliers de services Web, voire plus. En outre, des techniques telles que celle des *Magic Sets* proposée dans le contexte des bases de données déductives pourrait être suggérées. De plus, un benchmark et une comparaison de le moteur inférentiel de BIOMED avec des raisonneurs tels que KAON2<sup>15</sup>, Pellet<sup>16</sup> ou Racer<sup>17</sup> sont envisageables, sachant que la typologie de techniques de raisonnement de notre approche est, a priori, plus riche que celles de raisonneurs existants. Au niveau empirique, il serait utile d'envisager d'autres expérimentations afin d'évaluer l'approche de composition combinant une large palette d'opérateurs de relaxation pour une composabilité fonctionnelle logique et une composabilité approximative à base de mesures de similarité.

Aussi, nous proposons d'investiguer une perspective considérée actuellement dans le domaine bioinformatique d'un très grand intérêt qui est celle de l'étude de la traçabilité des usagers de workflows scientifiques (*Scientific Workflows*). Dans ce contexte, il est possible de capitaliser l'usage des Workflows en proposant un ou plusieurs workflows scientifiques les plus indiqués (les plus satisfaisants) au contexte de l'usager, à ses besoins et aux QdS exigés.

Enfin, nous envisageons de considérer les profils et les préférences des utilisateurs au sein du processus de découverte et de composition des services à l'instar des propriétés non fonctionnelles (QdS). Les critères de QdS proposés dans un cadre assez général sont indépendants de tout domaine, il serait intéressant de proposer de nouvelles métriques dépendant du domaine afin de guider l'utilisateur dans le choix d'un service ou d'un plan de composition par rapport à d'autres, des métriques liées à la qualité de la découverte (Quality of Discovery, QoD) ou de la composition (Quality of composition, QoC) peuvent être proposées sur la base des préférences des utilisateurs et/ou de leurs *feedbacks*.

<footnote n="14">14. http://www.w3.org/Submission/SWRL/</footnote>

<footnote n="15">15. http://kaon2 semanticweb.org/reasoning</footnote>

<footnote n="16">16. http://www.mindswap.org/2003/pellet/index.shtml</footnote>

<footnote n="17">17. http://www.racer-systems.com/</footnote>
Bibliographie

[ABP06a] Nadia Yaacoubi Ayadi, Mohamed BenAhmed, and Yann Pollet. Formal framework for semantic interoperability. In *Proceedings of the First International Conference on Software and Data Technologies (ICSOFT'06)*, pages 139–144, 2006.

[ABP06b] Nadia Yaacoubi Ayadi, Mohamed BenAhmed, and Yann Pollet. Ontology-Based Meta-Model for Semantically Interoperable Systems. In *Proceedings of the 8th International Conference on Information Integration and Web-based Applications Services IIWAS'06*, pages 413–422, 2006.

[ABPR04] Daniel Austin, Abbie Barbir, Ed Peters, and Steve RossTalbot. Web Services Choreography Requirements. Technical report, W3C, 2004.

[ACD$^{+}$03] Tony Andrews, Francisco Curbera, Hitesh Dholakia, Yaron Goland, Johannes Klein, Frank Leymann, Kevin Liu, Dieter Roller, Doug Smith, Satish Thatte, Ivana Trickovic, and Sanjiva Weerawarana. Business Process Execution Language for Web Services (BPEL4WS) version 1.1, May 2003.

[ACKM04] Gustavo Alonso, Fabio Casati, Harumi Kuno, and Vijay Machiraju. *Web Services: Concepts, Architecture and Applications*. Springer Verlag, 2004.

[ADH$^{+}$04] Xin Dong Alon, Xin Dong, Alon Halevy, Jayant Madhavan, Ema Nemes, and Jun Zhang. Similarity search for web services. In *Proceedings of Very Large Data Bases (VLDB'04)*, pages 372–383, 2004.

[AFJ$^{+}$05] R. Akkiraju, J. Farrell, J.Miller, M. Nagarajan, M. Schmidt, A. Sheth, and K. Verma. Web service semantics -WSDL-S, version 1.0. Technical report, April 2005.

[AHV95] Serge Abiteboul, Richard Hull, and Victor Vianu. *Foundations of Databases*. Addison-Wesley, 1995.

[AL07] Nadia Yacoubi Ayadi and Zoé Lacroix. Resolving scientific service interoperability with schema mapping. In *Proceedings of the 7th IEEE International Conference on Bioinformatics and Bioengineering (BIBE'07)*, pages 448–455, 2007.

[ALM05] Florence Amardeilh, Philippe Laublet, and Jean-Luc Minel. Document annotation and ontology population from linguistic extractions. In *Proceedings of the 3rd international conference on Knowledge capture (K-CAP '05)*, pages 161–168, 2005.
[ALV08a] Nadia Yacoubi Ayadi, Zoé Lacroix, and Maria-Esther Vidal. BiOnMap : a deductive approach for resource discovery. In *Workshop on Resource Discovery in conjunction with International Conference on Information Integration and Web-based Applications (RED'08)*, pages 477–482, 2008.

[ALV08b] Nadia Yacoubi Ayadi, Zoé Lacroix, and Maria-Esther Vidal. A deductive approach for resource interoperability and well-defined workflows. In *OTM Workshops*, pages 998–1009, 2008.

[ALVR07] Nadia Yacoubi Ayadi, Zoé Lacroix, Maria-Esther Vidal, and Edna Ruckhaus. Deductive Web Services : An Ontology-Driven Approach for Service Interoperability in Life Science. In *OTM Workshops* (2), pages 1338–1347, 2007.

[AMM07a] Eyhab Al-Masri and Qusay H. Mahmoud. Crawling multiple UDDI business registries. In *Proceedings of the 16th international conference on World Wide Web (WWW '07)*, pages 1255–1256, 2007.

[AMM07b] Eyhab Al-Masri and Qusay H. Mahmoud. QoS-based Discovery and Ranking of Web Services. In *Proceedings of the 16th International Conference on Computer Communications and Networks (ICCCN 2007)*, pages 529–534, 2007.

[AMSK01] M. Mostofa Akbar, Eric G. Manning, Gholamali C. Shoja, and Shahadat Khan. Heuristic Solutions for the Multiple-Choice Multi-dimension Knapsack Problem. In *Proceedings of the International Conference on Computational Science (ICCS '01)*, pages 659–668, 2001.

[AP05] Danilo Ardagna and Barbara Pernici. Global and Local QoS Constraints Guarantee in Web Service Selection. In *Proceedings of the IEEE International Conference on Web Services (ICWS '05)*, pages 805–806, 2005.

[AP07] Danilo Ardagna and Barbara Pernici. Adaptive service composition in flexible processes. *IEEE Transactions on Software Engineering*, 33(6):369–384, 2007.

[APB06] Nadia Yaacoubi Ayadi, Yann Pollet, and Mohamed BenAhmed. A Semantic-Based Approach to Interoperability of UML Schemas. In *IAT Workshops*, pages 316–319, 2006.

[AR09] Mohammad Alrifai and Thomas Risse. Combining global optimization with local selection for efficient QoS-aware service composition. In *Proceedings of the 18th international conference on World wide web (WWW'09)*, pages 881–890, 2009.

[ARDN08] Mohammad Alrifai, Thomas Risse, Peter Dolog, and Wolfgang Nejdl. A scalable approach for QoS-based web service selection. In *Service-Oriented Computing – ICSOC 2008 Workshops*, pages 190–199, 2008.

[Bac00] Bruno Bachimont. *Engagement Sémantique et Engagement Ontologique : Conception et Réalisation D'ontologies dans Ingénierie Des Connaissances*, chapter 19, pages 305–324. 2000.

[Bal08] Fabien Baligand. Une approche déclarative pour la gestion de la qualité de service dans les compositions de services. Thèse de Doctorat. Ecole Nationale Supérieure des Mines de Paris, 2008.
[BAM08] Devis Bianchini, Valeria De Antonellis, and Michele Melchiori. Flexible semantic-based service matchmaking and discovery. *World Wide Web*, 11(2):227-251, 2008.

[BDDM05] B. Benatallah, R.M. Dijkman, M. Dumas, and Z. Maamar. *Service composition: concepts, techniques, tools and trends*, pages 48–66. Idea Group Publishing, 2005.

[BHL01] Tim Berners-Lee, James Hendler, and Ora Lassila. The Semantic Web. *Scientific American*, 284(5):35–43, May 2001.

[BHL+04] Mark Burstein, Jerry Hobbs, Ora Lassila, Drew McDermott, Sheila McIlraith, Srini Narayanan, Massimo Paolucci, Bijan Parsia, Terry Payne, Evren Sirin, Naveen Srinivasan, and Katia Sycara. OWL-S: Semantic Markup for Web Services. Website, November 2004.

[BK06] Abraham Bernstein and Christoph Kiefer. Imprecise RDQL: towards generic retrieval in ontologies using similarity joins. In *Proceedings of the ACM symposium on Applied computing (SAC '06)*, pages 1684–1689, 2006.

[BKS01] Stephan Börzsönyi, Donald Kossmann, and Konrad Stocker. The Skyline Operator. In *Proceedings of the 17th International Conference on Data Engineering (ICDE'01)*, pages 421–430, 2001.

[BLM+05] Franz Baader, Carsten Lutz, Maja Milicic, Ulrike Sattler, and Frank Wolter. A description logic based approach to reasoning about web services. In *Proceedings of the Workshop on Web Service Semantics (WSS2005)*, 2005.

[BLPF06] Jos De Bruijn, Holger Lausen, Axel Polleres, and Dieter Fensel. The Web Service Modeling Language WSML: An overview. In *Proceedings of the European Semantic Web Conference (ESWC'06)*, pages 590–604, 2006.

[Bou05] Sarah Cohen Boulakia. Intégration de données biologiques: Sélection de sources centrée sur l’utilisateur. Thèse de Doctorat. Université Paris Sud, 2005.

[CAkH05] Daniela Barreiro Claro, Patrick Albers, and Jin kao Hao. J.k.: Selecting web services for optimal composition. In *Proceedings of the 2nd International Workshop on Semantic and Dynamic Web Processes (SDWP 2005)*, pages 32–45, 2005.

[CCDS04] Fabio Casati, Malu Castellanos, Umesh Dayal, and Ming-Chien Shan. Probabilistic, context-sensitive, and goal-oriented service selection. In *Proceedings of the 2nd international conference on Service oriented computing (ICSOC '04)*, pages 316–321, 2004.

[CCGM06] Valeria Cardellini, Emiliano Casalicchio, Vincenzo Grassi, and Raffaela Mirandola. A framework for optimal service selection in broker-based architectures with multiple qos classes. In *Proceedings of the IEEE Services Computing Workshops (SCW '06)*, pages 105–112, 2006.

[CDF04] Olivier Corby, Rose Diengkuntz, and Catherine Faronzucker. Querying the semantic web with the corese search engine. In *Proceedings of European Conference on Artificial Intelligence (ECAI'04)*, pages 705–709, 2004.
[CDG+06] Liliana Cabral, John Domingue, Stefania Galizia, Alessio Gugliotta, Vlad Tanasescu, Carlos Pedrinaci, and Barry Norton. IRS-III: A broker for semantic web services based applications. In *International Semantic Web Conference (ISWC'06)*, volume 4273, pages 201–214, 2006.

[Cha07] Yasmine Charif. Chorégraphie dynamique de services basée sur la coordination d'agents introspectifs. Thèse de Doctorat. Université Pierre et Marie Curie, 2007.

[Cho09] Olfa Chourabi. Un cadre générique de modélisation, de capitalisation et de partage de connaissances métiers situées en ingénierie systèmes. Thèse de Doctorat. Conservatoire National des Arts et Métiers (France) et l'Ecole Nationale des Sciences de l'Informatique (Tunisie), Décembre 2009.

[CIJ+00] Fabio Casati, Ski Ilnicki, Li-jie Jin, Vasudev Krishnamoorthy, and Ming-Chien Shan. Adaptive and dynamic service composition in eflow. In *Proceedings of the 12th International Conference on Advanced Information Systems Engineering (CAiSE '00)*, pages 13–31, 2000.

[CLC07] Lei Cao, Minglu Li, and Jian Cao. Using genetic algorithm to implement cost-driven web service selection. *Multiagent Grid Systems*, 3(1):9–17, 2007.

[CMML03] Monica Crubézy, Mark A. Musen, Enrico Motta, and Wenjin Lu. Configuring online problem-solving resources with the Internet Reasoning Services. *IEEE Intelligent Systems*, 18(2):34–42, 2003.

[CMSA02] Jorge Cardoso, John Miller, Amit Sheth, and Jonathan Arnold. Modeling quality of service for workflows and web service processes. Technical report, University of Georgia, 2002.

[CMSA04] Jorge Cardoso, John Miller, Amit Sheth, and Jonathan Arnold. Quality of service for workflows and web service processes. *Journal of Web Semantics*, 1(3):281–308, 2004.

[CPE+06] Gerardo Canfora, Massimiliano Di Penta, Raffaele Esposito, Francesco Perfetto, and Maria Luisa Villani. Service composition (re)binding driven by application-specific QoS. In *Proceedings of 4th International Conference Service-Oriented Computing (ICSOC 2006)*, pages 141–152, 2006.

[CS01] Fabio Casati and Ming-Chien Shan. Dynamic and adaptive composition of e-services. *Inf. Syst.*, 26(3):143–163, 2001.

[CSG+03] Liming Chen, Nigel Shadbolt, Carole A. Goble, Feng Tao, Simon J. Cox, Colin Puleston, and Paul R. Smart. Towards a knowledge-based approach to semantic service composition. In *Proceedings of International Semantic Web Conference (ISWC'03)*, pages 319–334, 2003.

[DCG+08] John Domingue, Liliana Cabral, Stefania Galizia, Vlad Tanasescu, Alessio Gugliotta, Barry Norton, and Carlos Pedrinaci. IRS-III: A broker-based approach to semantic web services. *Journal of Web Semantics*, 6(2):109–132, 2008.

[DPEV+06] Massimiliano Di Penta, Raffaele Esposito, Maria Luisa Villani, Roberto Codato, Massimiliano Colombo, and Elisabetta Di Nitto. WS binder: a framework to enable dynamic binding of composite web services. In *Proceedings*
of the 2006 international workshop on Service-oriented software engineering (SOSE '06), pages 74-80, 2006.

[DY06] Wen-Li Dong and Hang YU. Optimizing web service composition based on qos negotiation. In *EDOCW '06 : Proceedings of the 10th IEEE on International Enterprise Distributed Object Computing Conference Workshops*, page 46, Washington, DC, USA, 2006. IEEE Computer Society.

[Euz05] Jérôme Euzenat. L'annotation formelle de documents en (8) questions. In *Ingénierie des connaissances*. L'Harmattan, 2005.

[FB02] Dieter Fensel and Christoph Bussler. The web Service Modeling Framework WSMF. *Electronic Commerce Research and Applications*, 1(2):113-137, 2002.

[FKS03] Ronald Fagin, Ravi Kumar, and D. Sivakumar. Efficient similarity search and classification via rank aggregation. In *Proceedings of the 2003 ACM SIGMOD international conference on Management of data (SIGMOD '03)*, pages 301-312, 2003.

[FKT09] Federico Michele Facca, Srdjan Komazec, and Ioan Toma. WSMX 1.0 : A Further Step toward a Complete Semantic Execution Environment. In *Proceedings of the 6th European Semantic Web Conference on The Semantic Web (ESWC'09)*, pages 826-830, 2009.

[FLN01] Ronald Fagin, Amnon Lotem, and Moni Naor. Optimal aggregation algorithms for middleware. In *Proceedings of the twentieth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems (PODS'01)*, pages 102-113. ACM, 2001.

[FMH$^{+}$99] Dieter Fensel, Enrico Motta, Frank Van Harmelen, V. Richard Benjamins, Monica Crubezy, Mauro Gaspari, Rix Groenboom, William Grosso, Mark Musen, Enric Plaza, Guus Schreiber, Rudi Studer, and Bob Wielinga. The Unified Problem-solving Method Development Language UPML. *Knowledge and Information Systems*, 5:2003, 1999.

[Fro07] Annick Fron. *Architecture réparties en Java*. Dunod, 2007.

[GCC07] Chunming Gao, Meiling Cai, and Huowang Chen. QoS-aware Service Composition Based on Tree-Coded Genetic Algorithm. In *Proceedings of the 31st Annual International Computer Software and Applications Conference (COMP-SAC '07)*, pages 361-367, 2007.

[GD04] S. Galizia and J. Domingue. Towards a choreography for IRS-III. In *Proceedings of the Workshop on WSMO Implementations (WIW 2004)*, pages 29-30, 2004.

[GGM99] Jean-Marc Geib, Christophe Gransart, and Philippe Merle. *CORBA : des concepts à la pratique*. Dunod, 1999.

[Gri07] Stephan Grimm. *Discovery Identifying relevant services*, pages 211-244. Springer, 2007.

[Gru93] Thomas R. Gruber. A translation approach to portable ontology specifications. *Knowledge Acquisition*, 5(2):199-220, 1993.
[Gua95] Nicola Guarino. Formal ontology, conceptual analysis and knowledge representation. *International Journal of Human-Computer Studies*, 43(5-6):625-640, 1995.

[Gua99] Nicola Guarino. The role of identity conditions in ontology design. In *Proceedings of the International Conference of Spatial Information Theory: Cognitive and Computational Foundations of Geographic Information Science (CO-SIT '99)*, volume 1661, pages 221-234, 1999.

[GV09] Marlene Goncalves and Maria-Esther Vidal. Reaching the Top of the Skyline: An Efficient Indexed Algorithm for Top-k Skyline Queries. In *Proceedings of the International Conference on Database and Expert Systems Applications (DEXA '09)*, pages 471-485, 2009.

[GVRA09] Marlene Goncalves, Maria-Esther Vidal, Alfredo Regalado, and Nadia Yacoubi Ayadi. Selecting the Top-k Skyline Services. In *Proceedings of Resource Discovery workshop in conjunction with VLDB'09*, pages 10-25, 2009.

[GVRA10] Marlene Goncalves, Maria-Esther Vidal, Alfredo Regalado, and Nadia Yacoubi Ayadi. Efficiently Selecting the Best Web Services. *To appear*, 2010.

[GW02] Nicola Guarino and Christopher Welty. Evaluating ontological decisions with ontoclean. *Communication of The ACM*, 45(2):61-65, 2002.

[GW04] Nicola Guarino and Christopher A. Welty. An Overview of OntoClean. In *Handbook on Ontologies*, pages 151-172. 2004.

[Hay04] Patrick Hayes. RDF Semantics. W3C Recommendation, February 2004.

[HCM+05] Armin Haller, Emilia Cimpian, Adrian Mocan, Eyal Oren, and Christoph Bussler. WSMX - A Semantic Service-Oriented Architecture. In *Proceedings of the International Conference on Web Service (ICWS'05)*, pages 321-328, 2005.

[HK97] Markus Horstman and Mary Kirtland. DCOM Architecture. Technical report, Microsoft Corp., 1997.

[IBS08] Ihab F. Ilyas, George Beskales, and Mohamed A. Soliman. A survey of top-k query processing techniques in relational database systems. *ACM Computing Surveys*, 40(4):1-58, 2008.

[Isa05] Antoine Isaac. Conception et utilisation d'ontologies pour l'indexation de documents audiovisuels. Thèse de Doctorat. Université Paris IV-Sorbonne, Décembre 2005.

[JC97] Jay J. Jiang and David W. Conrath. Semantic similarity based on corpus statistics and lexical taxonomy. *CoRR*, 1997.

[JC02] Tyler Jewell and David Chappell. *Java Web Services*, chapter UDDI: Universal Description, Discovery, and Integration. O'Reilly, 2002.

[JRL+05] Michael Jaeger, Gregor Rojecgoldmann, Christoph Liebetruth, Gero Mühl, and Kurt Geihs. Ranked Matching for Service Descriptions using OWL-S. In *In Proceedings of Kommunikation in Verteilten Systemen (KiVS'2005)*, *Informatik Aktuell*, pages 91-102, 2005.
[KAC+02] Gregory Karvounarakis, Sofia Alexaki, Vassilis Christophides, Dimitris Plexousakis, and Michel Scholl. RQL: A Declarative Query Language for RDF. In *Proceedings of the 11th international conference on World Wide Web (WWW'02)*, pages 592-603, 2002.

[KB08] Christoph Kiefer and Abraham Bernstein. The creation and evaluation of iSPARQL strategies for matchmaking. In *Proceeding of European Semantic Web Conference (ESWC'08)*, pages 463-477, 2008.

[Kbo10] Férihane Kboubi. Médiation et navigation sémantiques dans un corpus textuel annoté conceptuellement et thématiquement. Thèse de Doctorat. Ecole Nationale des Sciences de L'informatique, 2010.

[KFS06] Matthias Klusch, Benedikt Fries, and Katia Sycara. Automated semantic web service discovery with OWLS-MX. In *Proceedings of the fifth international joint conference on Autonomous agents and multiagent systems (AAMAS '06)*, pages 915-922, 2006.

[KFS09] Matthias Klusch, Benedikt Fries, and Katia Sycara. OWLS-MX: A hybrid semantic web service matchmaker for OWL-S services. *Web Semantics*, 7(2):121-133, 2009.

[KG05] Matthias Klusch and Andreas Gerber. Semantic web service composition planning with OWLS-XPlan. In *Proceedings of the 1st Int. AAAI Fall Symposium on Agents and the Semantic Web*, pages 55-62, 2005.

[KK08] Matthias Klusch and Patrick Kapahnke. Semantic web service selection with SAWSDL-MX. In *Proceedings of the Second International Workshop on Service Matchmaking and Resource Retrieval in the Semantic Web (SMR2'08)*, 2008.

[KK09] Matthias Klusch and Frank Kaufer. WSMO-MX: A hybrid semantic web service matchmaker. *Web Intelligence and Agent Systems*, 7(1):23-42, 2009.

[KKD+98] Shahadatullah Khan, C Flmd Shahadatullah Khan, Supervisors Dr, Kin F. Li, Dr. Eric, and G. Manning. Quality adaptation in a multisession multimedia system: Model, algorithms and architecture. Technical report, 1998.

[KKL03] Sravanthi Kalepu, Shonali Krishnaswamy, and Seng Wai Loke. Verity: A qos metric for selecting web services and providers. In *Proceedings of the International Web Information Systems Engineering Workshops (WISE Workshops)*, pages 131-139, 2003.

[KKR07] Ulrich Kuster and Birgitta Konig-Ries. Semantic service discovery with DIANE service descriptions. In *Proceedings of the International Workshop on Service Composition & SWS Challenge at the 2007 IEEE/WIC/ACM International Conference on Web Intelligence (WI 2007)*, pages 152-156, 2007.

[KLL+05] Uwe Keller, Rubén Lara, Holger Lausen, Axel Polleres, and Dieter Fensel. Automatic Location of Web services. In *Proceedings of 2nd European Semantic Web Conference (ESWC'05)*, volume 3532, pages 1-16, 2005.

[KLW95] Michael Kifer, Georg Lausen, and James Wu. Logical foundations of object-oriented and frame-based languages. *Journal of the ACM (JACM)*, 42(4):741-843, 1995.
[KMW03] Rania Khalaf, Nirmal Mukhi, and Sanjiva Weerawarana. Service-Oriented Composition in BPEL4WS. In WWW (Alternate Paper Tracks), 2003.

[KPSV09] Ravi Kumar, Kunal Punera, Torsten Suel, and Sergei Vassilvitskii. op-k aggregation using intersections of ranked inputs. In Proceedings of the Second ACM International Conference on Web Search and Data Mining (WSDM '09 :), pages 222–231, 2009.

[KPT+04] A. Kiryakov, B. Popov, I. Terziev, D. Manov, and D. Ognyanoff. Semantic annotation, indexing, and retrieval. Web Semantics : Science, Services and Agents on the World Wide Web, 2(1) :49–79, December 2004.

[KVBF07] Jacek Kopecký, Tomas Vitvar, Carine Bournez, and Joel Farrell. SAWSDL : Semantic annotations for WSDL and XML schemas. IEEE Internet Computing, 11(6) :60–67, 2007.

[KZ07] Ziad Kobti and Wang Zhiyang. An Adaptive Approach for QoS-Aware Web Service Composition Using Cultural Algorithms. In Australian Conference on Artificial Intelligence (ASWC'07), pages 140–149, 2007.

[LA10] Zoé Lacroix and Maliha Aziz. Resource Description, Ontology, and Resource Discovery. International Journal of Metadata, Semantics and Ontologies (IJMSO) Special Issue On resource Discovery, (To appear), 2010.

[LAB+06] Bertram Ludäscher, Ilkay Altintas, Chad Berkley, Dan Higgins, Efrat Jaeger, Matthew Jones, Edward A. Lee, Jing Tao, and Yang Zhao. Scientific workflow management and the Kepler system. Concurrency and Computation : Practice and Experience, 18(10) :1039–1065, 2006.

[Lam02] S. Lammermann. Runtime Service Composition via Logic-Based Program Synthesis. Thèse de Doctorat. Department of Microelectronics and Information Technology, Royal Institute of Technology, Stockholm, 2002.

[Lin98] Dekang Lin. An Information-Theoretic Definition of Similarity. In Proceedings of the Fifteenth International Conference on Machine Learning (ICML '98), pages 296–304, 1998.

[LRL+97] Hector J. Levesque, Raymond Reiter, Yves Lespérance, Fangzhen Lin, and Richard B. Scherl. Golog : A logic programming language for dynamic domains. Journal of Logic Programming, 31, 1997.

[MB10] Georgios Meditskos and Nick Bassiliades. Structural and Role-Oriented Web Service Discovery with Taxonomies in OWL-S. IEEE Trans. on Knowl. and Data Eng., 22(2) :278–290, 2010.

[MBE03] Brahim Medjahed, Athman Bouguettaya, and Ahmed K. Elmagarmid. Composing Web services on the Semantic Web. The VLDB Journal, 12(4) :333–351, 2003.

[MBM+07] David Martin, Mark Burstein, Drew Mcdermott, Sheila Mcilraith, Massimo Paolucci, Katia Sycara, Deborah L. Mcguinness, Evren Sirin, and Naveen Srinivasan. Bringing Semantics to Web Services with OWL-S. World Wide Web, 10(3) :243–277, 2007.
[Mcd02] Drew Mcdermott. Estimated-Regression Planning for Interactions with Web Services. In *Proceedings of the 6th International Conference on AI Planning and Scheduling*, pages 204–211, 2002.

[MDCG03] Enrico Motta, John Domingue, Liliana Cabral, and Mauro Gaspari. IRS-II: A Framework and Infrastructure for Semantic Web Services. In *Proceeding of the International Conference on Semantic Web (ISWC'03)*, volume 2870, pages 306–318, 2003.

[MGK$^{+}$98] Drew McDermott, Malik Ghallab, Craig Knoblock, Adele Howe, Aschin Ram, Manuela Veloso, Daniel Weld, and David Wilkins. PDDL - The Planning Domain Definition Language. Technical report, Yale Center for Computational Vision and Control, 1998.

[MM10] Moreno Marzolla and Raffaela Mirandola. QoS Analysis for Web Service Applications: a Survey of Performance-oriented Approaches from an Architectural Viewpoint. Technical report, Department of Computer Science, University of Bologna, 2010.

[MPP$^{+}$04] Simon Miles, Juri Papay, Terry Payne, Michael Luck, and Luc Moreau. Towards a protocol for the attachment of metadata to grid service descriptions and its use in semantic discovery. *Scientific Programming*, 12(4):201–211, 2004.

[MS04a] E. Michael Maximilien and Munindar P. Singh. A framework and ontology for dynamic web services selection. *IEEE Internet Computing*, 8(5):84–93, 2004.

[MS04b] E. Michael Maximilien and Munindar P. Singh. Toward autonomic web services trust and selection. In *ICSOC '04: Proceedings of the 2nd international conference on Service oriented computing*, pages 212–221, New York, NY, USA, 2004. ACM.

[MSZ01] S. McIlraith, T.C. Son, and H. Zeng. Semantic Web Services. *IEEE Intelligent Systems. Special Issue on the Semantic Web*, 16(2):46–53, March/April 2001.

[MvH04] Deborah L. McGuinness and Frank van Harmelen. OWL Web Ontology Language Overview. Technical report, W3C Consortium, 2004.

[MW92] Zohar Manna and Richard J. Waldinger. Fundamentals of deductive program synthesis. *IEEE Trans. Software Eng.*, 18(8):674–704, 1992.

[MYCC07] Nikos Mamoulis, Man Lung Yiu, Kit Hung Cheng, and David W. Cheung. Efficient top-k aggregation of ranked inputs. *ACM Transactions on Database Systems*, 32(3):19, 2007.

[NIK$^{+}$03] Dana Nau, Okhtay Ilghami, Ugur Kuter, J. William Murdock, Dan Wu, and Fusun Yaman. SHOP2: An HTN planning system. *Journal of Artificial Intelligence Research*, 20:379–404, 2003.

[NM02] Srini Narayanan and Sheila A. McIlraith. Simulation, verification and automated composition of web services. In *Proceedings of the 11th international conference on World Wide Web (WWW'02)*, pages 77–88, 2002.

[OCF$^{+}$03] Borys Omelayenko, Monica Crubézy, Dieter Fensel, V. Richard Benjamins, Bob J. Wielinga, Enrico Motta, Mark A. Musen, and Ying Ding. UPML:
The Language and Tool Support for Making the Semantic Web Alive. In *Spinning the Semantic Web*. 2003.

[OGA<sup>+</sup>06] Tom Oinn, Mark Greenwood, Matthew Addis, M. Nedim Alpdemir, Justin Ferris, Kevin Glover, Carole Goble, Antoon Goderis, Duncan Hull, Darren Marvin, Peter Li, Phillip Lord, Matthew R. Pocock, Martin Senger, Robert Stevens, Anil Wipat, and Chris Wroe. Taverna: lessons in creating a workflow environment for the life sciences: Research Articles. *Concurr. Comput.: Pract. Exper.*, 18(10):1067–1100, 2006.

[OS99] Aris M. Ouksel and Amit P. Sheth. Semantic interoperability in global information systems: A brief introduction to the research area and the special section. *SIGMOD Record*, 28(1):5–12, 1999.

[Pap03] Mike P. Papazoglou. Service-oriented computing: Concepts, characteristics and directions. In *Proceedings of the Fourth International Conference on Web Information Systems Engineering (WISE '03)*, pages 3–12, 2003.

[Pee04] Joachim Peer. A PDDL based tool for automatic web service composition. In *Proceedings of the Second International Workshop on Principles and Practice of Semantic Web Reasoning (PPSWR)*, pages 149–163, 2004.

[Pee05] Joachim Peer. Web Service Composition as AI Planning - A Survey. Technical report, University of St. Gallen, Switzerland, 2005.

[PF02] Shankar R. Ponnekanti and Armando Fox. SWORD: A developer toolkit for web service composition. In *Proceedings of the 11th International WWW Conference (WWW2002)*, pages 83–107, 2002.

[PKCH05] Jyotishman Pathak, Neeraj Koul, Doina Caragea, and Vasant G. Honavar. A framework for semantic web services discovery. In *Proceedings of the 7th annual ACM international workshop on Web information and data management (WIDM '05)*, pages 45–50, 2005.

[PKP<sup>+</sup>02a] Massimo Paolucci, Takahiro Kawamura, Terry R. Payne, and Katia Sycara. Importing the semantic web in UDDI. In *Proceedings of International Workshop on Web Services, E-Business, and the Semantic Web*, pages 225–236, 2002.

[PKP<sup>+</sup>02b] Massimo Paolucci, Takahiro Kawamura, Terry R. Payne, and Katia Sycara. Semantic matching of web services capabilities. In *Proceedings of International Semantic Web Conference (ISWC'02)*, pages 333–347, 2002.

[POSV04] Abhijit A. Patil, Swapna A. Oundhakar, Amit P. Sheth, and Kunal Verma. Meteor-s web service annotation framework. In *Proceedings of the 13th international conference on World Wide Web (WWW '04)*, pages 553–562, New York, NY, USA, 2004. ACM.

[Pre04] Chris Preist. A conceptual Architetcure for Semantic Web Services. In *Proceedings of the International Semantic Web Conference (ISWC'04)*, pages 395–409, 2004.

[PS08] Eric Prud'hommeaux and Andy Seaborne. SPARQL Query Language for RDF. W3C Recommendation, January 2008.
[PSL03] Chintan Patel, Kaustubh Supekar, and Yugyung Lee. A QoS Oriented Framework for Adaptive Management of Web Service based Workflows. In *Proceedings of the Conference on Database and Expert Systems (DEXA'03)*, pages 826-835. Springer, 2003.

[Ran03] Shuping Ran. A model for web services discovery with QoS. *SIGecom Exch.*, 4(1):1-10, 2003.

[Rao04] Jinghai Rao. Semantic web service composition via logic-based program synthesis. Thèse de Doctorat. Department of Computer and Information Science, Norwegian University of Science and Technology, December 2004.

[Res95] Philip Resnik. Using information content to evaluate semantic similarity in a taxonomy. In *Proceedings of the 14th international joint conference on Artificial intelligence (IJCAI'95)*, pages 448-453, 1995.

[Res99] Philip Resnik. Semantic similarity in a taxonomy: An information-based measure and its application to problems of ambiguity in natural language. *Journal of Artificial Intelligence Research (JAIR)*, 11:95-130, 1999.

[RKL+05a] Dumitru Roman, Uwe Keller, Holger Lausen, Jos de Bruijn, Rubén Lara, Michael Stollberg, Polleres, Cristina Feier, Cristoph Bussler, and Dieter Fensel. Web Service Modeling Ontology. *Applied Ontology*, 1(1):77-106, 2005.

[RKL+05b] Dumitru Roman, Uwe Keller, Holger Lausen, Jos de Bruijn, Rubén Lara, Michael Stollberg, Axel Polleres, Cristina Feier, Cristoph Bussler, and Dieter Fensel. Web Service Modeling Ontology. *Applied Ontology*, 1(1), 2005.

[RMB+89] Roy Rada, Hafedh Mili, Ellen Bicknell, and Maria Blettner. Development and application of a metric on semantic nets. *IEEE Transactions on Systems, Man and Cybernetics*, 19(1):17-30, January/February 1989.

[RPD06] Florian Rosenberg, Christian Platzer, and Schahram Dustdar. Bootstrapping performance and dependability attributes of web services. In *Proceedings of the IEEE International Conference on Web Services (ICWS'06)*, pages 205-212, Washington, DC, USA, 2006. IEEE Computer Society.

[RRV08] Edna Ruckhaus, Eduardo Ruiz, and Maria-esther Vidal. Query evaluation and optimization in the semantic web. *Theory Pract. Log. Program.*, 8(3):393-409, 2008.

[RS03] Jinghai Rao and Xiaomeng Su. Toward the composition of semantic web services. In *Proceedings of the Second International Workshop on Grid and Cooperative Computing (GCC'03)*, pages 760-767, 2003.

[RS04] Jinghai Rao and Xiaomeng Su. A survey of automated web service composition methods. In *Proceedings of the First International Workshop on Semantic Web Services and Web Process Composition (SWSWPC'04)*, pages 43-54, 2004.

[RU93] Raghu Ramakrishnan and Jeffrey D. Ullman. A survey of research on deductive database systems. *Journal of Logic Programming*, 23:125-149, 1993.

[Sal88] G. Salton. Term-weighting approaches in automatic text retrieval. *Information Processing & Management*, 24(5):513-523, 1988.
[SBF98] Rudi Studer, V. Richard Benjamins, and Dieter Fensel. Knowledge engineering : Principles and methods. *Data and Knowledge Engineering*, 25(1-2) :161-197, March 1998.

[Sch06] Hans Albrecht Schmid. Service congestion : The problem, and an optimized service composition architecture as a solution. In *Proceedings of the IEEE International Conference on Web Services (ICWS '06)*, pages 505-514, Washington, DC, USA, 2006. IEEE Computer Society.

[SD02] Michael Sintek and Stefan Decker. TRIPLE - A Query, Inference, and Transformation Language for the Semantic Web. In *Proceedings of the First International Semantic Web Conference on The Semantic Web (ISWC'02)*, pages 364-378, 2002.

[SDC06] Amandeep S. Sidhu, Tharam S. Dillon, and Elizabeth Chang. Integration of protein data sources through PO. In *Proceedings of Database and Expert Systems Applications (DEXA 2006)*, pages 519-527, 2006.

[SdF03] Mithun Sheshagiri, Marie desJardins, and Timothy Finin. A Planner for Composing Services Described in DAML-S. In *Proceedings of the AAMAS Workshop on Web Services and Agent-based Engineering*, 2003.

[SDHS05] M. Adel Serhani, Rachida Dssouli, Abdelhakim Hafid, and Houari Sahraoui. A qos broker based architecture for efficient web services selection. In *Proceedings of the IEEE International Conference on Web Services (ICWS'05)*, pages 113-120, 2005.

[SGR08] Amit P. Sheth, Karthik Gomadam, and Ajith Ranabahu. Semantics enhanced services : METEOR-S, SAWSSDL and SA-REST. *IEEE Data Engineering Bulletins*, 31(3) :8-12, 2008.

[SHS08] Michael Schumacher, Heikki Helin, and Heiko Schuldt. *CASCOM-Intelligent Service Coordination in the Semantic Web*, chapter Service Discovery (Chapter 10), pages 209-238. 2008.

[SK05] Larisa N Soldatova and Ross D King. Are current ontologies in biology good ontologies. *Nature Biotechnology*, 23(9) :1095-1098, 2005.

[SP04] Evren Sirin and Bijan Parsia. Planning for Semantic Web Services. In *Proceedings of Semantic Web Services Workshop at 3rd International Semantic Web Conference*, 2004.

[SPS04] Naveen Srinivasan, Massimo Paolucci, and Katia Sycara. An efficient algorithm for OWL-S based semantic search in UDDI. In *First International Workshop Semantic Web Services and Web Process Composition*, pages 96-110, 2004.

[SSGF06] Gareth Shercliff, Jianhua Shao, W. Alex Gray, and Nick J. Fiddian. Qos assessment of providers with complex behaviours : An expectation-based approach with confidence. In *Proceedings of Service-Oriented Computing (ICSOC 2006)*, pages 378-389, 2006.

[SVSM03] Kaarthik Sivashanmujgam, Kunal Verma, Amit Sheth, and John Miller. Adiding Semantics to Web Services Standards. In *Proceedings of the International Conference on Web Services (ICWS'03)*, pages 395-401, 2003.
[SWK+02] Katia Sycara, Seth Widoff, Matthias Klusch, and Jianguo Lu. Larks : Dynamic matchmaking among heterogeneous software agents in cyberspace. *Autonomous Agents and Multi-Agent Systems*, 5(2):173–203, 2002.

[Tem08] Lynda Temal. Ontologie de partage de données et d'outils de traitement dans le domaine de la neuroimagerie. Thèse de Doctorat. Université de Rennes I, Juin 2008.

[TP04] P. Traverso and M. Pistore. Automated composition of semantic web services into executable processes. In *Proceedings of the 3rd International Semantic Web Conference (ISWC'04)*, pages 380–394, 2004.

[udd01] Universal description, discovery, and integration of business for the web. Technical report, UDDI Specification Technical Committee, October 2001.

[VC05] Emanuele Della Valle and Dario Cerizza. Cocoon glue : a prototype of wsmo discovery engine for the healthcare field. In *In Proceedings of the WIW 2005 Workshop on WSMO Implementations*, pages 1–12, 2005.

[VHA05] Le-Hung Vu, Manfred Hauswirth, and Karl Aberer. Qos-based service selection and ranking with trust and reputation management. In *OTM Conferences (1)*, pages 466–483, 2005.

[VRB08] Yves Vanrompay, Peter Rigole, and Yolande Berbers. Genetic algorithm-based optimization of service composition and deployment. In *SIPE '08 : Proceedings of the 3rd international workshop on Services integration in pervasive environments*, pages 13–18, 2008.

[VSS+05] Kunal Verma, Kaarthik Sivashanmugam, Amit Sheth, Abhijit Patil, Swapna Oundhakar, and John Miller. METEOR-S WSDI : A scalable P2P infrastructure of registries for semantic publication and discovery of web services. *Journal of Information Technology and Management, Special Issue on Universal Global Integration*, 6(1):17–39, 2005.

[W3C03] W3C. QoS for web services : Requirements and possible approaches. Technical report, W3C Working Group Note, 2003.

[Wal01] Richard J. Waldinger. Web agents cooperating deductively. In *Proceedings of the First International Workshop on Formal Approaches to Agent-Based Systems (FAABS '00)*, pages 250–262, 2001.

[WfM05] WfMC. Workflow Reference Model, Workflow Management Coalition. [Online] : http://www.wfmc.org, January 2005.

[Wie92] Gio Wiederhold. Mediators in the Architecture of Future Information Systems. *IEEE Computer*, 25(3):38–49, 1992.

[WL02] Mark D. Wilkinson and Matthew Links. BioMOBY : An Open Source Biological Web Services Proposal. *Briefings in Bioinformatics*, 3(4):331–341, 2002.

[WP94] Zhibiao Wu and Martha Palmer. Verbs semantics and lexical selection. In *Proceedings of the 32nd annual meeting on Association for Computational Linguistics*, pages 133–138, 1994.
[WPS+03] Dan Wu, Bijan Parsia, Evren Sirin, James A. Hendler, and Dana S. Nau. Automating DAML-S Web Services Composition Using SHOP2. In *Proceedings of International Semantic Web Conference (ISWC'03)*, pages 195-210, 2003.

[WSH+03] Dan Wu, Evren Sirin, James Hendler, Dana Nau, and Bijan Parsia. Automatic Web Services Composition Using SHOP2. In *Proceedings of the Workshop on Planning For Web services*, 2003.

[XB05] Jin Xiao and Raouf Boutaba. QoS-aware service composition and adaptation in autonomic communication. *IEEE Journal on Selected Areas in Communications*, 23(12):2344-2360, 2005.

[YL04] Tao Yu and Kwei-Jay Lin. The Design of QoS Broker Algorithms for QoS-Capable Web Services. In *Proceedings of the 2004 IEEE International Conference on e-Technology, e-Commerce and e-Service (EEE'04)*, pages 17-24, Washington, DC, USA, 2004. IEEE Computer Society.

[YL05a] Tao Yu and Kwei-Jay Lin. A Broker-Based Framework for QoS-Aware Web Service Composition. In *Proceedings of the 2005 IEEE International Conference on e-Technology, e-Commerce and e-Service (EEE'05)*, pages 22-29, 2005.

[YL05b] Tao Yu and Kwei-Jay Lin. Service selection algorithms for composing complex services with multiple qos constraints. In *Proceedings of the 3rd Int. Conf. on Service Oriented Computing (ICSOC'05)*, pages 130-143, 2005.

[YST+09] Jing Yuan, Guang-Zhong Sun, Ye Tian, Guoliang Chen, and Zhi Liu. Selective-NRA Algorithms for Top-k Queries. In *Proceedings of the Joint International Conferences on Advances in Data and Web Management*, pages 15-26, 2009.

[Yu06] Tao Yu. Quality of service (QoS) in web services: model, architecture and algorithms. Thèse de Doctorat. California State University, 2006.

[YZL07] Tao Yu, Yue Zhang, and Kwei-Jay Lin. Efficient algorithms for Web services selection with end-to-end QoS constraints. *ACM Transactions on the Web*, 1(1):6, 2007.

[ZBD+03] Liangzhao Zeng, Boualem Benatallah, Marlon Dumas, Jayant Kalagnanam, and Quan Z. Sheng. Quality driven web services composition. In *Proceedings of the 12th international conference on World Wide Web (WWW'03)*, pages 411-421, 2003.

[ZBN+04] Liangzhao Zeng, Boualem Benatallah, Anne H.H. Ngu, Marlon Dumas, Jayant Kalagnanam, and Henry Chang. QoS-Aware Middleware for Web Services Composition. *IEEE Transactions on Software Engineering*, 30:311-327, 2004.

[ZSC06] Chengwen Zhang, Sen Su, and Junliang Chen. A Novel Genetic Algorithm for QoS-Aware Web Services Selection. In *Proceedings of Data Engineering Issues in E-Commerce and Services (DEECS'02)*, volume 4055, pages 224-235, 2006.

[ZZL+02] Jiwei Zhong, Haiping Zhu, Jianming Li, and Yong Yu. Conceptual Graph Matching for Semantic Search. In *Proceedings of the 10th International Conference on Conceptual Structures (ICCS'02)*, pages 92-196, 2002.