Dans la littérature, il y a une distinction entre deux types de composition : l'orchestration [TP04] et la chorégraphie [ABPR04]. Dans le cas d'une orchestration, un processus principal (service Web) prend le contrôle du déroulement de la composition et coordonne donc les différentes opérations des différents services Web. À aucun moment les autres services contribuant à la composition n'ont connaissance de cette composition : ils remplissent leur rôle de service sans se soucier si un client humain ou un applicatif interagit avec eux. Le processus d'orchestration est connu a priori et mis en oeuvre à partir d'un coordinateur central. L'orchestration est une méthode très utilisée, et ce pour deux raisons :

1. Il est relativement simple d'écrire un processus centralisé gérant l'invocation de sous-services ;

2. dans le cas d'une réutilisation de services Web basiques, seule la partie centrale est à développer.

Dans le cas d'une chorégraphie, il n'existe pas de coordinateur central. Chacun des services intervenant dans la composition sait exactement ce qu'il doit faire, quand il doit le faire et avec qui le faire. Ainsi, ils ont tous une connaissance plus ou moins globale du processus métier dans lequel ils se retrouvent. Contrairement à la méthode basée sur l'orchestration, la chorégraphie demande nettement plus de développement et de test : il faut développer chaque service dans le but de la composition auquelle il peut participer. L'intérêt de la mise en place d'une chorégraphie de services est principalement lié à la non-centralisation du traitement. C'est la raison pour laquelle, nous placerons le présent travail dans le cas d'une chorégraphie de services Web atomiques.

### 4.1.2 La composition de services et ses catégories

Ces dernières années, plusieurs communautés se sont intéressées à la problématique de la composition de services. Des solutions ont été proposées par les communautés des bases de données, du Web sémantique, et plus récemment par la communauté de l'Intelligence Artificielle (IA).

Les solutions proposées peuvent être classées selon deux axes orthogonaux (figure 4.1) :

1. En fonction du degré de participation de l'utilisateur dans la définition du schéma de composition, ces propositions peuvent être manuelles, semi-automatiques ou automatiques.

2. Selon que la sélection des services et la gestion du flot soient faites ou non a priori, une approche sera dite *statique* ou *dynamique*.

Une composition est dite *statique* lorsqu'elle prend place à l'étape de conception, au moment où l'architecture et la conception du système logiciel sont planifiées. Les composants (ou services) qui seront utilisés sont préalablement choisis et reliés, et la gestion du flot est effectuée a priori. Les approches statiques de composition de services sont celles adoptées par l'industrie. Elles s'inspirent de la gestion de processus métiers quant à la description des données et des flots de contrôle pour le processus de composition.

Par opposition, une composition de services est dite *dynamique* si les services sont sélectionnés et composés à la volée en fonction des besoins formulés par l'utilisateur. Une approche dynamique pour la composition de services offre le potentiel de réaliser des
<figure><img src="image_32.png" /><figcaption>FIGURE 4.1 – Classification des principaux travaux de composition de services [Cha07]</figcaption></figure>

applications flexibles et adaptables en sélectionnant et en combinant les services de manière appropriée sur la base de la requête et du contexte de l'utilisateur. Ce type de composition peut engendrer de nombreuses applications utiles qui n'ont pas été prévues à l'étape de conception. Notons que la composition dynamique de services est tout à fait intéressante dans un environnement ouvert tel que le Web ou l'informatique pervasive (diffuse ou ambiante) où les composants disponibles sont dynamiques et les attentes des utilisateurs variables et personnalisées ce qui est le.

Nous présentons dans ce qui suit les approches de composition selon le premier axe de la classification, soit les approches manuelles/semi-automatiques et automatiques. Lors de notre présentation, nous catégoriserons chacune des approches selon le deuxième axe en précisant si la sélection ou le moteur de composition y sont statiques ou dynamiques. Nous présentons, dans ce qui suit, les principales approches de composition selon la catégorisation de la figure 4.1.

### 4.1.2.1 Composition manuelle/semi-automatique

Les techniques de composition manuelle supposent qu'un expert se charge de définir et générer, graphiquement ou moyennant un éditeur de texte, des scripts de workflow<fnref n="1" /> qui

<footnote n="1">1. Un workflow est une représentation d'un procédé métier dans un format interprétable par la machine. Il est constitué d'un réseau d'activités et de dépendances entre elles, des critères pour spécifier le démarrage et la terminaison d'un procédé et des informations sur les activités individuelles (participants, applications,</footnote>
<figure><img src="image_33.png" /><figcaption>FIGURE 4.2 – Langages de définition d'orchestration et de chorégraphie par dates de publication</figcaption></figure>

sont ensuite soumis à un moteur d'exécution de workflows. La plupart d'entre elles sont entièrement statiques puisque les services à composer sont préalablement sélectionnés, et le flot de composition est défini a priori. BPEL4WS<fnref n="2" /> (*Business Process Execution Language for Web Services*) [KMW03, ACD+03] qui est un exemple de langage d'orchestration, permet de décrire les interactions des services composants à travers un plan en spécifiant les flots de contrôle quant à l'invocation des services, ainsi que les dépendances des données existantes entre plusieurs processus métiers. Les approches manuelles de composition reposent toutes sur un langage de description de workflows. La figure 4.2 résume les différents langages de définition de workflows développés essentiellement dans l'industrie.

D'autres approches manuelles comportent en revanche des moteurs de composition dynamiques. C'est par exemple le cas de *eFlow* [CIJ+00] qui est un système spécifiant, ordonnant et surveillant des e-services<fnref n="3" /> composés.

Du côté des approches semi-automatiques, des outils sont développées afin de guider l'utilisateur dans la sélection des services à composer (par exemple, en fonction de leurs entrées/sorties, annotations, etc.) au cours du processus de composition. Par exemple, l'outil graphique IRS-III développé par Dominique et Gualizia [GD04] guide l'utilisateur étape par étape pour la composition de services décrits en WSMO. Durant le processus de composition, le framework propose à l'utilisateur de sélectionner des buts, des médiateurs et des opérateurs de flot de contrôle. Une fois que le service composé est défini, l'outil instancie les opérateurs de contrôle ainsi que le workflow. Un framework de composition de services basé sur les connaissances (Knowledge-based Semantic Service Composition Framework) est décrit dans [CSG+03] permet d'exploiter les connaissances du domaine pour guider l'utilisateur voulant construire un workflow. L'outil fournit à cet utilisateur des suggestions de sélection et d'instanciation des services et lui permet de mémoriser les workflows pour en faciliter la réutilisation.

<footnote>données informatiques associées, etc.) [WfM05].</footnote>

<footnote n="2">2. http://www.ibm.com/developerworks/library/specification/ws-bpel/</footnote>

<footnote n="3">3. Un e-service est le moyen par lequel une entreprise offre ses produits, ses services et ses ressources via Internet.</footnote>
<figure><img src="image_34.png" /><figcaption>FIGURE 4.3 - Cadre général d'un système de composition automatique de services Web [RS03]</figcaption></figure>

### 4.1.2.2 Composition automatique

Les approches automatiques de composition de services Web permettent d'automatiser entièrement le processus de composition en le traitant généralement comme un problème de planification [Pee05]. Dans ce cas, le moteur de composition y est toujours dynamique.

Nous présentons un cadre générique de composition automatique de services tel que proposé par Jinghai Rao en 2003 [RS03] puis développés dans [Rao04, RS04]. Il constitue une abstraction de haut niveau sans aucune considération de langage particulier, ou de plate-forme ou méthode particulières utilisées au cours du processus de composition. L'objectif de ce cadre est de constituer le fondement sur lequel sont identifiées les similarités et les différences entre les diverses méthodes de composition disponibles. Le cadre général d'un système de composition de SW est illustré par la figure 4.3.

Le système de composition est constitué de deux composants essentiels : l'approvisionneur de services (service provider) et le requêteur de services (service requester). L'approvisionneur de services propose des services Web pour usage en publiant leurs descriptions dans un entrepôt de services. Le requêteur de services consomme les informations et/ou les services offerts par l'approvisionneur de services. En outre, le système comprend les composants suivants : traducteur, générateur de processus, évaluateur, moteur d'exécution et entrepôt de services. Le traducteur traduit les langages externes utilisés par les usagers vers les langages internes utilisés par le générateur de processus. A chaque requête, le générateur de processus tente de générer un plan qui compose les services disponibles dans l'entrepôt de services en vue de satisfaire au mieux la requête. Si plus d'un plan est proposé, l'évaluateur compare les plans proposés et décide lequel est le meilleur pour son exécution. Le moteur d'exécution exécute le plan et retourne les résultats au client.

Les méthodes de composition dynamique sont multiples. La plupart de ces approches rencontrées dans l'état de l'art utilisent soit les techniques d'Intelligence Artificielle de planification, soit l'approche déductive utilisée pour la preuve de théorèmes. L'hypothèse la plus courante sur laquelle reposent ces méthodes est que chaque service est spécifié en ses pré-conditions et ses effets. Ces approches considèrent un service Web comme un composant logiciel qui prend des données en entrée pour produire des données en sortie, de sorte que les pré-conditions et les effets ne sont que les paramètres d'entrées et de sorties du service. Les pré-conditions représentent l'état pré-requis du monde pour l'exécution
du service et les nouveaux états du monde générés suite à l'exécution représentent les effets du service. Ainsi donc les modèles de composition considèrent comme hypothèses la connaissance des spécifications de l'usager relatives aux pré-conditions et aux effets (PE) attendus du service composite. Ces modèles génèrent un plan ou un processus soit par un prouveur logique de théorèmes soit par un planificateur d'Intelligence Artificielle (IA). Dans la prochaine section, nous nous focalisons sur les approches de composition dynamiques de services Web qu'elles soient automatiques et/ou semi-automatiques dans le domaine de l'Intelligence Artificielle.

## 4.2 Composition de Services Web et les techniques de l'IA

La composition dynamique de services Web par des techniques d'intelligence artificielle (IA), et plus particulièrement par des techniques de planification, a été considérée depuis des années comme la voie la plus prometteuse. En effet, les concepts de OWL-S sont très fortement inspirés de ceux de la planification : les pré-conditions présentent les conditions qui doivent être satisfaites pour garantir la bonne exécution d'un service Web. Les effets sont le résultat du succès de l'exécution d'un service.

Dans ce qui suit, nous présentons quelques axes de recherche actuels concernant la composition par planification et par d'autres techniques d'intelligence artificielle. C'est ainsi que les méthodes de composition de services Web que nous allons présenter seront classées en cinq classes, comme suit :

1. Composition de Services à base de logique (calcul situationnel : situation calculus),

2. Composition de Services à base de planification avec PDDLP,

3. Composition de Services à base de règles,

4. Composition de Services à base de planification hiérarchique,

5. Composition de Services à base de la synthèse de programmes

6. Composition orientée QdS (en anglais QoS).

### 4.2.1 Composition à base de la logique de premier ordre ou du calcul situationnel (Situation Calculus)

McILRAITH et. al. [MSZ01, NM02] adaptent et étendent le langage Golog<sup>4</sup>[LRL<sup>+</sup>97] pour la composition automatique de services Web. Les auteurs de [MSZ01, NM02] utilisent une version étendue de Golog intégrant la sémantique des actions pour résoudre les

<footnote n="4">4. Le langage GOLOG (alGOL in LOGic) a été proposé en 1997 par l'équipe de Hector LEVESQUE à l'Université de Toronto (Canada) comme langage de programmation logique pour des domaines dynamiques basé sur le calcul de situation qui permet de raisonner sur le monde et sur ses évolutions (tous les mondes pouvant résulter d'une ou de plusieurs actions de l'agent). Les programmes en GOLOG spécifiant le comportement d'un agent peuvent être écrits avec un niveau élevé d'abstraction : les actions complexes d'un agent se dé composent en actions primitives qui font référence normalement à des actions externes aux agents comme par exemple ramasser un objet, par opposition à des actions qui n'affectent que leur état interne. Le modèle de l'environnement est mis à jour dynamiquement en fonction des règles définies par le programmeur.</footnote>
problèmes de composition automatique de services Web. L'idée générale de cette méthode est que les agents logiciels peuvent raisonner sur les services Web en vue de réaliser automatiquement les opérations de découverte, d'exécution et de composition. La procédure générique ainsi que les contraintes peuvent être formulées dans une logique du premier ordre (LPO) du calcul situationnel, i. e. une logique permettant de raisonner à propos des actions et des changements. Les auteurs, à cet égard, conçoivent les services Web soit comme des actions primitives (PrimitiveAction) soit comme des actions complexes (ComplexAction). Les actions primitives sont conçues soit comme des actions modifiant l'état du monde, soit comme des actions modifiant l'état de connaissance de l'agent. Les actions complexes sont des combinaisons d'actions primitives.

La connaissance de base de l'agent permet d'encoder logiquement les pré-conditions et les effets du service Web dans un langage de calcul situationnel. Les agents utilisent les constructeurs d'un langage de programmation procédurale avec des concepts définis pour les services et des contraintes utilisant une machine déductive. Un service composite est un ensemble de service atomiques reliés par des constructeurs d'un langage de programmation procédurale du genre : (if-then-else, while et so forth). Les auteurs ont, aussi, proposé un moyen de personnaliser les programmes en Golog en incorporant les contraintes formulées par le requêteur, de sorte qu'il puisse soit effectuer un choix non déterministe dans une situation donnée soit renforcer un ordre d'exécution entre deux actions. La génération du plan de composition est effectuée en respectant les contraintes prédéfinies.

### 4.2.2 Composition à base du langage PDDL (Planning Domain Definition Language)

Le grand intérêt accordé par la communauté de la composition de services aux méthodes de planification IA peut être expliqué par la grande similarité entre le langage de description OWL-S (et son prédesseur DAML-S) et les représentations de PDDL<fnref n="5" /> (Planning Domain Definition Language) [MGK+98] qui est considéré comme un standard de fait de l'état de l'art des planificateurs. En effet, la communauté du Web sémantique s'est forte-ment inspirée du langage PDDL lors de la conception du langage de description OWL-S. Ainsi une description OWL-S peut être facilement traduite en une représentation PDDL : les services Web sont représentés par des opérateurs ayant des pré-conditions et produisant des effets. Puis un planificateur peut alors être utilisé pour produire un plan qui corres-pond à la composition des services Web. Pour disposer d'un état de l'art complet de la composition dynamique par planification, nous pouvons nous reporter aux travaux de J. PEER publiés en 2005 [Pee05].

De nombreux travaux ont été produits ces dernières années. Les travaux de SHESHA-GIRI et al. [SdF03] proposent l'utilisation d'ontologies de domaine afin d'ajouter des contraintes pour optimiser la recherche dans un espace de plans. Ceux de McDERMOTT [Mcd02] proposent d'utiliser la planification par régression estimée (Estimated-Regression

<footnote n="5">5. Le formalisme de planification classique étant très restreint, des extensions ont été nécessaires afin de décrire des domaines plus complexes. Ces principales extensions sont le typage des variables, les opérateurs de planification conditionnelle, les expressions de quantification, les pré-conditions disjonctives ou encore les axiomes d'inférences. Le langage de planification PDDL (Planning Domain Description Language) permet d'exprimer ces différentes extensions.</footnote>
Planning) qui permet d'utiliser des heuristiques pour guider la recherche dans un espace
de situations. Le principe est le suivant : un agent qui désire interagir avec un service
Web va construire un plan puis l'exécuter. Si l'exécution échoue, l'agent aura appris de
nouvelles informations de cette interaction, qui seront utilisées dans le prochain cycle de
planification et exécution.

**SIRIN et al.** [SHP03] présentent une méthode semi-automatique pour la composition de services Web. A chaque fois qu'un utilisateur doit sélectionner un service Web, tous les services disponibles qui correspondent au service sélectionné, sont présentés à l'utilisateur qui fait alors le choix à la place du système. L'idée de la composition semi-automatique est assez intéressante car il est très difficile de capturer le comportement des services Web dans leurs moindres détails, puis de les composer automatiquement. Bien que cette méthode soit simple, elle permet de voir comment un planificateur automatique et un humain peuvent travailler ensemble pour répondre au mieux à la requête de l'utilisateur.

Enfin, **PEER** [Pee04] propose une approche basée sur le langage PDDL dans laquelle, après la création du domaine de planification à partir de la description sémantique, un planificateur est choisi parmi plusieurs en fonction des instructions PDDL utilisées dans le domaine ou de la complexité du but à atteindre. Dans la composition de services à base du langage PDDL, **McDERMOTT** [Mcd02] a introduit un nouveau type de connaissance appelée valeur d'une action (value of an action), qui est persistante et qui n'est pas traitée comme une valeur littérale. Du point de vue de la construction d'un service Web, cette caractéristique permet de distinguer la transformation de l'information de l'état de changement provoqué par l'exécution du service. L'information est représentée par les paramètres d'entrée/sortie lesquels sont réutilisables dans l'exécution de plusieurs services. Au contraire, les états du monde ne sont modifiés que par l'exécution du service. Ainsi le changement peut être interprété comme la consommation des anciens états du monde pour en produire de nouveaux.

4.2.2.1 Composition avec une planification à base de règles (Rule-based Planning)

MEDJAHED et al. [MBE03] présentent une technique pour générer des services composites partant du haut niveau jusqu'au niveau de la description déclarative. La méthode utilise les règles de composition afin de déterminer si deux services sont disponibles ou non. Cette approche de composition consiste en quatre phases :

1. La phase de spécification permet une description de haut niveau des compositions désirées par l'usage du langage CSSL pour (Composite Service Specification Language).

2. La phase de matching (makematcher) qui utilise les règles de composition afin de générer des plans de composition conformes aux spécifications du requêteur.

3. Si plus d'un plan est généré durant la phase de sélection, le service requêteur choisit un plan basé sur les critères de qualité de composition (Quality of Composition (QoC) comme le rang, le coût etc.).

4. La phase finale est une phase de génération. Une description détaillée du service composite est générée automatiquement et présentée au service requêteur.
Les règles de composabilité constituent le coeur de l'opération de composition, en ce sens qu'elles définissent comment le plan doit être généré. Ces règles considèrent à la fois les propriétés syntactiques et celles sémantiques des services Web. Les règles syntactiques couvrent les règles des modes opératoires ainsi que les règles d'interaction des services à travers les liaisons protocolaires (binding protocols). Les règles sémantiques incluent ce sous-ensemble de règles :

1. La composabilité indique si deux services Web sont composables et ce, si le message de sortie d'un service est compatible avec le message d'entrée d'un autre ; nous proposons un extension de la notion de composabilité dans le chapitre 7.

2. l'opération de la composabilité sémantique définit la compatibilité entre le domaine, les catégories et les objectifs de deux services ;

3. La composabilité qualitative définit les préférences du requêteur en matière de qualité des opérations du service composite ;

La principale contribution de cette approche est la notion de règles de composabilité qui considèrent les propriétés syntactiques et sémantiques des services Web. Les règles syntactiques incluent des règles pour les types d'opérations possibles et pour les liaisons protocolaires entre les services (i.e., bindings). Les règles sémantiques incluent des règles concernant la compatibilité des messages échangés et la compatibilité des domaines sémantiques des services, mais également des règles de qualité de la composition. Cette notion de règles de composabilité met en avant les attributs possibles des services Web qui peuvent être utilisés dans la composition de services et peut ainsi jouer le rôle de directive pour d'autres méthodes de composition par planification.

Un autre outil de composition de services Web générant des plans à base de règles est **SWORD** [PF02]. SWORD n'utilise pas les standards des services Web comme WSDL ou DAML-S, il utilise le modèle entité-relation pour spécifier les services Web. Il modélise un service Web par ses pré- et post-conditions. Plus précisément, SWORD représente un service sous la forme d'une règle de HORN pour dénoter les post-conditions que le composeur doit réaliser. L'outil SWORD automatise la tâche de composition en utilisant des descriptions de services basées sur les règles. L'utilisateur spécifie les faits des états initial et final. Le planificateur tente alors de construire une chaîne de services pouvant satisfaire ces besoins.

### 4.2.3 Planification à base de réseaux HTN

D'autres planificateurs IA ont été proposés pour la composition automatique de services Web. Le planificateur SHOP2 [WPS+03, WSH+03] a été proposé par WU et al. en utilisant des descriptions de services de type DAML-S. SHOP2 est un planificateur à base d'un réseau hiérarchique de tâches<fnref n="6" /> (*Hierarchical Task Network* (HTN). Les auteurs

<footnote n="6">6. La planification hiérarchique (Hierarchical Task Network, HTN) utilise un langage similaire au langage de la planification classique. En effet, chaque état du monde est représenté par un ensemble de prédicats instanciés et chaque action correspond à une transition déterministe entre deux états. Cependant la planification hiérarchique diffère de la planification classique sur la façon de planifier [NIK+03]. Dans un planificateur HTN, l'objectif n'est pas d'atteindre un ensemble de buts (exemple : porte ouverte) mais de résoudre un ensemble de tâches (exemple : ouvrir porte). Les entrées du planificateur sont, comme en</footnote>
affirment que le planificateur hiérarchique HTN est plus efficace que d'autres langages de planification comme Golog qui a été précédemment cité.

D'après les auteurs, le principe de décomposition d'une tâche en sous-tâches dans la planification hiérarchique est très similaire au concept de décomposition de processus composites dans OWL-S. Afin de rendre leur proposition réalisable, les auteurs font deux hypothèses concernant le modèle de processus :

1. Les processus atomiques ont, soit des sorties, soit des effets, mais pas les deux en même temps.

2. Les structures de contrôle Split et Split et Join ne sont pas utilisées dans les processus composites

En 2002, SIRIN et al. ont présenté une première méthode de composition semi-automatique. En 2004, SIRIN et PARSIA [SP04] sont allés plus loin en intégrant un raisonneur sur les langages de descriptions dans le planificateur SHOP2. La planification HTN est très puissante pour les domaines où la connaissance est complète et détaillée, ce qui n'est pas le cas des services Web selon [KG05].

### 4.2.4 Composition de Services à base de la synthèse de programmes

La synthèse de programmes est une méthode de génie logiciel qui génère automatiquement des programmes. Il existe trois différentes approches pour la synthèse de programmes :

- transformationnelle,

- inductive et

- déductive.

Nous nous focalisons sur la facette déductive de la synthèse qui est basée sur l'observation que les preuves sont équivalentes au programme en raison du fait que chaque preuve peut être interprétée comme un pas de calcul. L'idée centrale est la transformation de la synthèse de programmes en une approche de preuve de théorèmes. L'idée d'une homologie entre les théorèmes et leurs spécifications, d'une part et les preuves et programmes constructifs, d'autre part a été détaillée dans le travail de de MANNA et WALDIN-GER datant de 1992 [MW92]. Tenant compte de certaines analogies, il est possible de voir les méthodes de composition de services Web utilisant des programmes de déduction de la synthèse de programmes comme des cas particuliers de l'usage de l'approche planification de l'IA. Mais la génération du processus de composition est fortement reliée aux théories de la preuve. Le processus général de composition à base de synthèse de programmes est schématisé par la figure 4.4.

Le processus général de composition de services Web utilisant la synthèse de programmes est décrit comme suit : premièrement, les descriptions des services Web existants sont traduites en axiomes logiques et les exigences en matière de composition spécifiées

<footnote>planification classique, un ensemble d'opérateurs, mais également, un ensemble de méthodes. Une méthode décrit la manière de décomposer une tâche en un ensemble de sous-tâches. Le principe de la planification HTN est de décomposer les tâches non primitives en sous-tâches de plus en plus petites, jusqu'à obtenir des tâches primitives qui peuvent être résolues en utilisant les opérateurs de planification.</footnote>
<figure><img src="image_35.png" /><figcaption>FIGURE 4.4 – Processus général de composition à base de synthèse de programmes</figcaption></figure>

sous la forme de séquents logiques à prouver. Deuxièmement, un prouveur de théorèmes est utilisé pour déterminer quels séquents peuvent être prouvés à l'aide des axiomes disponibles. Si la réponse est positive, la dernière étape consiste alors à construire la description du processus de composition à partir de la preuve complète.

**WALDINGER** dans [Wal01] élabore une idée selon laquelle la synthèse de services peut être réalisée comme une preuve de théorème. L'approche est basée sur la déduction automatique et la synthèse de programmes dont les bases théoriques ont été jetées dans un travail antérieur présenté dans [MW92].

Initialement les services disponibles et les exigences de l'usager sont décrits dans une logique du premier ordre en relation avec la logique classique avant que les preuves constructives soient générées par le prouveur de théorèmes pour que finalement, les descriptions du service composite soient extraites d'un certain nombre de preuves particulières. **LÄMMERMANN** [Lam02] utilise le programme de synthèse structurale (Structural Synthesis of Program SSP) pour automatiser la composition de services. SSP est une approche déductive pour la synthèse des programmes à partir de spécifications. Les spécifications des services considèrent les propriétés structurales, i.e. l'information entrée/sortie. SSP utilise des variables propositionnelles comme identifieurs pour les paramètres d'entrée/sortie et une logique propositionnelle intuitionniste pour résoudre le problème de composition.

La composition est basée sur les propriétés des programmes de preuve de la logique intuitionniste ce qui permet de transformer un programme de composition de services en un programme de recherche de preuve. L'auteur utilise aussi l'avantage des disjonctions de la logique classique pour décrire les exceptions qui peuvent être rejetées durant l'invocation du service.
### 4.3 Approches de composition orientées Qualité de Service

Le concept de QoS (Qualité de service) recouvre un large domaine de propriétés inhérentes au domaine de la transmission de données. Plusieurs travaux pour définir la QoS sont à l'origine d'une proposition de standardisation de l'ISO.

La référence normative est le << Quality of Service Framework >> publiée en 1998 par l'ISO dans [ISO98]. D'après cette référence, les concepts fondamentaux suivants structurent la QoS :

1. Caractéristiques de QoS : un aspect quantifiable de QoS, qui est défini indépendamment des moyens par lesquels il est représenté ou contrôlé.

2. Etablissement de la QoS : l'utilisation de mécanismes pour créer les conditions pour l'activation d'un système afin que les caractéristiques de QoS désirées soient atteintes.

3. Mécanisme de QoS : un mécanisme spécifique, pouvant utiliser des paramètres de QoS ou des informations de contexte, potentiellement en coordination avec d'autres mécanismes de QoS, dans le but de permettre l'établissement, le monitoring, la maintenance, le contrôle et la demande de QoS.

Dans la suite de cette section, nous étudions successivement ces concepts dans le cadre des services Web.

#### 4.3.1 Caractéristiques de QoS des Services Web

Dans le cadre des services Web, le W3C a identifié un ensemble de caractéristiques de QoS pertinentes pour le domaine des services Web [W3C03] :

- La performance représente la vitesse avec laquelle un service Web répond à une requête. Cette qualité peut être mesurée en termes de débit, temps de réponse, latence, temps d'exécution, temps de transaction, etc.

- La confiance qualité d'un service à exécuter certaines fonctions sous certaines conditions et dans un intervalle de temps donné. Il s'agit d'une mesure de la capacité d'un service à maintenir sa qualité (généralement le nombre de coupures de service par jour, semaine, mois). La confiance est également associée à la garantie de l'ordre et de la bonne livraison des messages

- Le passage à l'échelle (scalability) permet de quantifier le nombre de requêtes auxquelles le service peut faire face dans un intervalle de temps donné.

- La Capacité indique le nombre de requêtes que le service est capable de traiter simultanément.

- La robustesse est la capacité à fonctionner alors que les données en entrée provoquent des conflits ou sont incomplètes.

- Le traitement des exceptions : de nombreuse situations ne peuvent être prédites à l'avance ce qui implique de supporter les exceptions de façon adaptée.

- La Précision indique le taux d'erreurs générées par le service.

- L'intégrité est une propriété garantissant que l'intégrité des données et des transactions est bien respectée, afin de ne pas aboutir à une situation inconsistante.

- L'accessibilité est la capacité à répondre à des requêtes.
- La disponibilité du service devrait être prêt pour une consommation immédiate lors d'une invocation. La disponibilité est souvent associée au temps de réparation (ou TTR pour Time to Repair).

- L'interopérabilité est capacité à pouvoir communiquer quels que soient la plate-forme et les langages utilisés. En ce qui concerne les services Web, c'est la normalisation et l'extensibilité de SOAP et des métadonnées qu'il contient qui permet de garantir l'operability.

- La sécurité des communications entre services Web (Authentification, Confidentialité, Intégrité, Non répudiation). De multiples normes sont à mettre en relation avec la sécurité, dont principalement WS-Security, WS-Trust, WS-SecureConv, WS-Federation, Contrats de service

Etablir et s'assurer de la QoS d'un composant comme le service Web constitue un enjeu crucial puisque ceci permet d'établir une relation de confiance entre le fournisseur d'un service et un client en attente d'une certaine fiabilité. Cependant, contrairement aux spécifications bien établies dans le domaine fonctionnel des services Web (telles que WSDL, SOAP ou UDDI), il n'existe pas de standards officiellement reconnus par la communauté en ce qui concerne la description et l'établissement de propriétés de QoS. Pour autant, plusieurs travaux visent à apporter des réponses à cette lacune par le biais des contrats de service (en anglais : SLA pour Service Level Agreement) dont l'objectif est de permettre la réalisation d'un accord entre consommateur et fournisseur de service portant sur le niveau de QoS que doit fournir le service. Plus spécifiquement, un SLA consiste en un document généré à l'issue d'un protocole de négociation (plus ou moins complexe) entre le consommateur et le fournisseur de service, et qui permet de définir les offres et exigences de ces deux rôles. Les spécifications de ce document doivent être vérifiées à l'exécution via un mécanisme de monitoring. Le cycle de vie du SLA prévoit ensuite différentes possibilités : soit une spécification du SLA est mise en défaut (violation d'un terme) et un mécanisme correctif (prévu ou non dans le SLA) doit être mis en oeuvre, soit le SLA arrive à son terme (dans le cas où un intervalle temporel est spécifié), soit une partie (consommateur ou fournisseur de service) décide de mettre fin à la relation client-service.

### 4.3.2 Framework à base de broker

Nous allons considérer comme référence aux frameworks basés sur un broker (Broker based Framework) le travail de YU Tao et LIN Kwei-Jay à l'Université de Californie Irvine (UCI) développé dans deux papiers publiés en 2005 [YL05a, YL05b], même si des travaux antérieurs avaient initiés de tels frameworks à l'instar de [PSL03]. Dans ce travail, les deux auteurs présentent une architecture à base d'un broker appelée Qbroker pour l'intégration et l'adaptation dynamique de services Web. A l'instar d'autres approches, ils proposent une modélisation de la QoS ainsi que des algorithmes de sélection de services basés sur les caractéristiques globales de la composition. Le broker exploite les informations contenues dans les contrats SLA des services et analyse les rapports de la QoS du service à l'exécution afin de vérifier si un contrat SLA est violé ou non. Dans ce cas, le broker est en charge de trouver un autre service qui satisfait la QoS globale. L'algorithme de sélection ne peut supporter qu'une seule contrainte de QoS et un seul point d'échec. La figure 4.5 illustre l'architecture globale du framework.
<figure><img src="image_36.png" /><figcaption>FIGURE 4.5 – Architecture globale du framework à base de broker</figcaption></figure>
Dans cette architecture, la motivation principale pour la conception du broker est d'intégrer la logique de sélection des services. Ainsi, la logique de composition et celle de demandeur de service sont clairement séparées. Les brokers sont ensuite vus comme des services maintenus de façon autonome et gérés par un acteur indépendant (à la manière d'un intermédiaire comme une agence de voyage). Par la suite les brokers peuvent être amenés à travailler ensemble pour répondre à la requête d'un client. Après chaque transaction avec le client, l'utilisateur du service doit rapporter les performances de QdS du service pour que le broker puisse mettre à jour les données de QdS de chaque service. L'architecture du broker, exhibée dans la figure ci-dessus, est constituée de quatre composants :

1. **Le gestionnaire d'information (Service Information Manager)** garde en mémoire un ensemble de services Web candidats dans un annuaire constitué de deux tables (pour les informations fournies par le service et les données statistiques relatives à la QdS). La table service permet de stocker la description fonctionnelle des services (identifiant, URL, opération, données d'entrée/sortie, description) et les données du SLA (capacité, temps de réponse, disponibilité, fiabilité). La table des données statistiques enregistre les données transmises par les clients ayant utilisé les services (stabilité du service, disponibilité, etc.). En fonction de ces informations statistiques agrégées, les valeurs de QdS des services sont mises à jour dans la table service.

2. **Le gestionnaire de composition (Composition Manager)** maintient le registre de processus qui contient les plans de processus. Ces plans de processus correspondent aux services et à leurs connexions, formant un chemin d'exécution. Ce composant traite également les requêtes de recherche de services pour générer un plan d'exécution. Les plans d'exécution consistent en des processus abstraits. Ils sont formés à partir des plans de processus choisis par un utilisateur.

3. **Le gestionnaire de sélection (Selection Manager)** retrouve les services pour le plan d'exécution généré par le gestionnaire de composition (Composition Manager). La sélection s'effectue sur la base des exigences de QdS de l'utilisateur. L'algorithme utilise une technique de résolution par contraintes sur le graphe de la composition afin de vérifier que la QdS globale (après agrégation) respecte bien les contraintes exigées par l'utilisateur. Pour optimiser la QdS globale obtenue, une fonction-objectif (appelée aussi fonction d'utilité est définie. Cette fonction consiste en une somme pondérée de paramètres de QdS. Plus sa valeur est élevée, plus la QdS globale est élevée. Des algorithmes d'optimisation sont proposés (comme nous l'expliciterons plus loin) pour le problème de résolution par contraintes de sorte à générer un ensemble de chemins satisfaisants où un épisode de chemin peut comporter un opérateur OR-SPLIT portant sur deux services équivalents l'un pouvant servir de secours dans le cas où l'autre n'est pas accessible.

4. **Le gestionnaire d'adaptation (Adaptation Manager)** : Le résultat de la sélection étant renvoyé au moteur d'exécution de la composition, la composition peut être instanciée. Dans ce modèle d'architecture, c'est au moteur d'exécution d'observer la QdS des services impliqués dans la composition. Si les SLA ne sont pas violés, alors la QdS des services est renvoyée à l'Adaptation Manager. Au cas où un SLA est violé, alors le gestionnaire d'adaptation (Adaptation Manager) doit renvoyer un des nouveaux chemins d'exécution pré-calculés au moteur d'exécution et demande au gestionnaire de sélection (Selection Manager) de recalculer un ensemble de plans
<table><caption>TABLE 4.1 – Agrégation des paramètres QoS dans un patron de composition</caption><thead><tr><th>Propriété QoS</th><th>Sequence</th><th>And</th><th>XOR</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>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>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>min(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>min(re<sub>i</sub>)</td><td>re<sup>k</sup></td></tr></tbody></table>

de rechange. La table des statistiques est également mise à jour pour tenir compte de la violation du SLA.

Bien que ce travail ait été limité sur de nombreux points (une seule propriété peut être contrainte globalement et une seule erreur est traitée à la fois), il propose une séparation très nette entre les rôles de concepteur de composition et de sélecteur de services. Le broker et le moteur BPEL (dans le cas des processus d'affaires) sont clairement découpés et aucune donnée confidentielle ne transite par le broker puisque celui-ci n'agit pas comme un proxy, contrairement à la plupart des architectures des plateformes concurrentes. Ceci permet au gestionnaire du broker de servir de multiples clients et même de travailler en partenariat avec d'autres gestionnaires de broker. Par ailleurs, ce travail réutilise certaines informations des SLA et maintient à jour une base de données statistiques portant sur la QoS des services, ce qui apporte plus de fiabilité qu'une simple relation client-fournisseur de service. Enfin, dans des conditions idéales, l'adaptation **dynamique** ne coûte rien puisque les chemins de rechange sont préparés à l'avance et donc il n'y a pas de surcharge lorsqu'un service viole son SLA. En revanche, du fait de l'indépendance des rôles, le broker n'a pas de perception de la QoS à l'exécution et c'est donc au moteur BPEL d'implémenter la logique de monitoring et de surveillance de la disponibilité. Il est donc de la responsabilité du client (la composition de services) de s'assurer de la QoS fournie. Cela nécessite en outre de modifier le moteur BPEL et donc de le rendre spécifique à l'utilisation du broker. Le point qui nous intéresse dans ce framework est celui relatif à la sélection de services atomiques en vue de constituer un ensemble de chemins possibles constituant des services composites vérifiant les exigences de QoS de bout en bout. Mais avant d'étudier les algorithmes et les heuristiques de sélection, nous allons préciser les patrons de composition possibles pour générer les graphes de composition, les classes de caractéristiques et attributs de la QoS et la constitution de la fonction d'utilité. Le passage des requêtes de l'usager à la sélection de services QoS au service composite complexe au niveau de **Qbroker** est illustré dans la figure 4.6.

Les auteurs considèrent les six patrons de composition (le patron *sequantiel*, l'opérateur *ANDSplit* et *ANDJoin*, l'opérateur *XOR Split* et *XORJoin*) et l'opérateur *Loop*) qui sont illustrés dans la figure 4.7. L'agrégation des attributs de la QoS pour quatre des six classes de patrons susmentionnés est explicitée dans la table 4.1. Nous allons étudier sur un exemple illustré dans la figure 4.8, la composition d'un service avec les patrons susmentionnés.

Considérons le service composite représenté par la figure 4.8 où le service $S_2$ est suivi soit par $S_4$ soit par $S_5$ avec, respectivement, les probabilités $p_1$ et $p_2$. Le service $S_6$ peut être exécuté au plus K fois. Supposons que $t_i$ et $c_i$ représentent, respectivement, le temps de réponse et le coût du service atomique $S_i$, le réponse totale T et le coût total C du
<figure><img src="image_37.png" /><figcaption>FIGURE 4.6 – Composition orientée QoS de services Web</figcaption></figure>

<figure><img src="image_38.png" /><figcaption>FIGURE 4.7 – Les six patrons de composition</figcaption></figure>
<figure><img src="image_39.png" /><figcaption>FIGURE 4.8 – Un exemple de service Composite</figcaption></figure>

service composite sont données par les formules ci-après :

$$T = t_1 + \max(t_2 + p_1 \times t_4 + p_2 \times t_5, t_3 + K \times t_6) + t_7$$

$$C = c + c_2 + p_1 \times c_4 + p_2 \times c_5 + c_3 + K \times c_6 + c_7.$$

En général la valeur des paramètres QdS pour les critères Qds de chaque service atomique est soit une valeur moyenne ($q_{avg}$) soit une valeur du pire des cas ($q_{max}$). Afin de poser le problème de la sélection, nous allons adopter les notations suivantes. Nous supposons que l'on dispose d'un univers de services Web noté $\mathcal{S}$ défini comme l'union d'un nombre de classes abstraites de services : $\mathcal{S} = \cup_i S_i$, i = 1,...,n.

Chaque classe abstraite de services $S_i$ (comme la classe des agences de voyage, celle des compagnies aériennes, celle de l'alignement multiple de séquences, celle de la construction d'arbres phylogénétiques) peut être utilisée pour décrire un ensemble de services fonctionnellement équivalents comme par exemple *Agence Cook, Tunisair, BLAST, ClustalW, Phylip*, etc. Un service atomique de la classe $S_i$ est noté $s_{ij}$ et décrit par un vecteur d'attributs QdS; le vecteur des m attributs QdS exigés pour un service composite est noté $Q_c$ et s'écrit comme suit : $Q_c = [Q_{1c}... Q_{mc}]$.

A chaque service candidat $v$ à la composition est affectée une fonction d'utilité notée $\mathcal{F}_v$ qui est définie comme un ensemble de paramètres QdS. La finalité de la fonction d'utilité est de choisir les services atomiques qui vérifient les contraintes mais qui fournissent la meilleure valeur à la valeur de la fonction d'utilité en réponse aux exigences en la matière de l'usager - client. Dans le cas où nous disposons de $x$ attributs 'positifs' (ceux dont la maximisation est recherchée comme le critère de la disponibilité) et $y$ attributs 'négatifs' (ceux dont la minimisation est recherchée comme le critère coût) les $W_\alpha$ et $W_\beta$ sont les poids de chaque attribut QdS de deux classes d'attributs positifs et négatifs avec la somme de tous les poids est égale à 1. La fonction d'utilité d'un service s'écrit donc sous la forme suivante :

$$\mathcal{F}_{ij} = \sum_{\alpha=1}^{x} w_{\alpha} * \left( \frac{q_{ij}^{\alpha} - \mu^{\alpha}}{\sigma^{\alpha}} \right) + \sum_{\beta=1}^{y} w_{\beta} * \left( 1 - \frac{q_{ij}^{\beta} - \mu^{\beta}}{\sigma^{\beta}} \right)$$

$w_\alpha$ et $w_\beta$ désignent les poids des attributs QdS ($0 < w_\alpha$ et $w_\beta < 1$), $\sum_{\alpha=1}^x w_\alpha + \sum_{\beta=1}^y w_\beta = 1$. $\mu$ et $\sigma$ désignent respectivement l'écart type et la variance des valeurs des attributs QdS pour chaque classe de services.
### 4.3.2.1 Les contraintes QdS globales

Les contraintes QdS représentent les exigences à vérifier par le service composite en termes de QdS de bout en bout. Cette vérification peut être exprimée en termes de maximisation ou de minimisation d'une fonction d'utilité. Pour la première classe les attributs positifs seront gardés tels quels alors que les attributs négatifs doivent être multipliés par -1. On procède inversement dans le cas d'une minimisation, les attributs positifs devant être multipliés par -1. Soit un service composite abstrait noté $SC_{abs}$ défini par une requête de composition donnée et soit $C' = [c'_1 \dots c'_m]$ où $m$ est le nombre d'attributs choisis dans la requête parmi les $r$ solutions possibles, un vecteur de contraintes globales sur le service composite $SC_{abs}$.

Soit $SC$ une instanciation de $SC_{abs}$ dans laquelle un service Web concret est choisi comme candidat à la composition dans chaque classe de services $S_i$ de l'univers $\mathbb{S}$. On dira que la sélection $SC$ est admissible ssi :

$$q'(SC) \leq C' \text{ pour } \forall c'_k \in C' \quad k = 1, \dots, m.$$

Autrement dit, un $SC$ est admissible si toutes les contraintes globales sont satisfaites.

Une fonction d'utilité globale est considérée en vue de permettre de trier et de classer les services candidats. Une sélection est dite *optimale* (nous dirons plutôt *la plus satisfaisante*) pour une requête de composition abstraite de services Web atomiques est un vecteur de contraintes QdS globales si elle maximise (resp. minimise) la valeur de l'utilité globale $\mathcal{F}'(SC_{opt}) = \maxi (\text{resp. min}) \mathcal{F}(SC_i)$. Pour une requête de composition de $n$ classes de services et $l$ services atomiques par classe il y a $l^n$ combinaisons possibles à examiner pour identifier le service composite le plus satisfaisant. C'est donc un problème d'optimisation qui est NP-complet.

### 4.3.3 Algorithmes de sélection de composition de services avec des contraintes QdS

Plusieurs algorithmes ont été proposés dans la littérature pour la sélection de composition de services avec différentes structures de composition et diverses contraintes de QdS. Une taxonomie de ces solutions a été produite dont la première classe de ces approches vise à déterminer une composition optimale (i. e. composition à QdS élevée) utilisant des algorithmes de force brute comme le GP (*Global Planning*) dans [ZBN$^{+04}$] ou **BBLP**, **MCSP**, **WS-IP** dans [YZL07]. Dans [YZL07], deux classes de problèmes de sélection selon que le service composite est constitué d'une suite séquentielle de services atomiques ou qu'il est constitué par une suite de services atomiques reliés par un ou plusieurs patrons de composition parmi les six susmentionnés. Pour la classe de composition séquentielle, l'algorithme proposant des solutions exactes est le **MMKP** (pour **Multidimension Multichoice Knapsack Problem**) qui se base sur la méthode de résolution du problème du sac à dos multi-choix multicritère dans [0, 1]. Ce problème est réputé faire partie des problèmes NP-complets. La majorité des algorithmes pour identifier les solutions optimales pour le problème MMKP sont basés sur la méthode *Branch-and-Bound* qui est une méthode de programmation linéaire. **KHAN** [KKD$^{+98}$] a proposé un tel algorithme BBLP pour MMKP qui cherche la solution optimale itérativement.
Le temps de calcul de **BBLP** croissant exponentiellement avec la taille du problème, ainsi, pour des problèmes de sélection il n’est pas du tout recommandé pour la sélection des services Web composites. YU et al. ont proposé en 2007 une heuristique dénommée **WS-HEU** (heuristique HEU pour les services Web) en vue de trouver une solution sous-optimale au problème MMKP [YZL07]. L’heuristique WS-HEU est, en fait, une adaptation de l’heuristique HEU proposée en 2001 par S. KHAN et al. [AMSK01]. Les tests rapportés dans [YZL07] indiquent que la meilleure solution est trouvée par WS-HEU dès le premier test dans 98% des cas en consommant la moitié du temps de calcul de l’heuristique HEU. Pour *n* classes de services avec *l* candidats à la composition dans chaque classe et *m* contraintes QoS, la complexité temporelle de WS-HEU est $O(n^2 (l - 1)^2 m)$ qui est donc polynomiale (tout comme HEU).

La seconde classe de composition concerne les structures générales de workflows (disposant de tâches séquentielles, conditionnelles et parallèles) modélisées sous la forme d'un graphe acyclique direct (DAG). Une fois le graphe de composition obtenu entre le service source $v_s$ et le service destination $v_d$ comme le montre la figure suivante.

<figure><img src="image_40.png" /></figure>

Chaque noeud étant affecté d'un ensemble de valeurs d'attributs QoS, et une fonction d'utilité atomique. Le problème consiste à identifier le chemin optimisant la fonction utilité globale et respectant les attributs globaux de QoS spécifiés par l'usager-client et résolu exactement par le biais de l'algorithme **MCSP** (Maximal Constraint Satisfaction Problem). Là aussi une solution sous-optimale est obtenue grâce à MCSP-K qui est l'algorithme **MCSP** dans lequel la fonction de relaxation est modifiée. Pour le cas où les structures des flots ne sont exclusivement séquentielles, ce qui est le cas dans la réalité, les algorithmes proposés tant au niveau des modèles combinatoires que dans le modèle des graphes sont comme suit : **MMKP** (Multidimension Multichoice Knapsack Problem) pour le modèle combinatoire et **MCOP** (Multiconstraint Optimal Path : chemin optimal multicontraint) pour le modèle à base de graphe comme proposé dans [XB05].

L'algorithme **MCOP** étant comme **MMKP** NP-complet, les auteurs de [YZL07] ont proposé une heuristique dénommée *Wflow* qui donne une solution quasi-optimale en un temps polynomial. L'idée principale de l'heuristique *Wflow* est de décomposer les workflows en une multiplicité de chemins d'exécution. La complexité temporelle est polynomiale tout comme celle de **WS-HEU** soit en $O(n^2 (l - 1)^2 m)$. Pour les modèles en graphe, MCOP étant NP-complet, les auteurs de [YZL07] ont proposé une amélioration en suggérant l'heuristique MCOP-K qui est plus rapide que l'algorithme MCOP et consommant moins d'espace. Les performances demeurent, selon les tests effectués, proches de
l'optimum dans 95% des cas. Il est à signaler que l'heuristique MCOP-K avait été proposée en 2006 par Tao YU dans sa thèse de doctorat à l'Université Irvine [Yu06].

D'autres travaux avaient adressé le problème de la sélection avant et après les travaux de [YZL07]. C'est ainsi que ZENG et al ont utilisé la méthode de planification globale (Global Planning) dans [ZBD+03] afin d'obtenir les meilleurs composants d'un service composite en utilisant des techniques de programmation linéaire mixte.

ZENG et al. dans [ZBN+04] adoptent une telle sélection par optimisation locale puisque la sélection du service Web devant exécuter une tâche donnée dans un service composite est effectuée au dernier moment et sans tenir compte des autres tâches impliquées dans le service composite. Quand une tâche doit être exécutée, le système récolte les QdS des services Web qui sont candidats pour l'exécution de ladite tâche. Après quoi, un vecteur de qualité est affecté à chaque service candidat et c'est sur la base de ce vecteur que le système choisit un des services candidats en faisant appliquer une méthode de décision multicritère (MCDM pour Multiple Criteria Decision Making). Le processus de sélection est basé sur la pondération assignée par l'usager (le client) à chaque critère et un ensemble de contraintes sur les attributs qualitatifs. Ces contraintes sont exprimées sur les tâches individuelles et non sur une de leurs combinaisons.

ARDAGNA et PERNICI ont proposé en 2005 [AP05] et en 2007 [AP07] un algorithme de programmation linéaire étendu aux contraintes locales. D'autres approches présentent des heuristiques basées sur des méthodes évolutionnaires (Algorithmes génétiques) proposées dans [ZSC06, CLC07, GCC07, KZ07, VRB08].

Plus récemment ALRIFAI et al. ont présenté en 2008 dans [ARDN08] et en 2009 dans [AR09] une nouvelle approche combinant des techniques d'optimisation locales et globales. Cette approche démarre du niveau global pour résoudre le problème de la sélection au niveau local. Elle procède en décomposant les contraintes globales de QdS (celles imposées par le client-usager à la totalité de l compositions) en un ensemble de contraintes locales (celles imposées aux sous-tâches comme partie de la composition). Pour ce faire, les auteurs proposent des techniques mixant la programmation linéaire et la programmation en nombres entiers ; techniques dites MILP (Mixed Integer Linear Programming) afin de trouver la meilleure décomposition des contraintes de QdS.

### 4.3.3.1 Evaluation et Couverture de la QdS dans les plateformes existantes

Dans sa thèse, Fabien BALIGANDA [Bal08] a comparé les performances de 10 plateformes existantes pour la gestion de la QdS dans les compositions de services. Les principales plateformes sont les suivantes :

eFlow [CIJ+00] est une plateforme développée par la société HP pour spécifier, établir et observer la QdS de services composites, tout en fournissant également un certain nombre de fonctionnalités telles que la gestion des événements, des exceptions, des transactions ou de la sécurité [CIJ+00, CS01]. Etant une approche relativement ancienne, eFlow cherche à fournir aux utilisateurs un moyen de spécifier aisément des services composites à partir de services atomiques, à l'instar de l'approche BPEL. Avec eFlow, une composition de services est modélisée sous la forme d'un graphe qui définit l'ordre d'exécution de noeuds. Les arcs du graphe supportent des prédicats sur les variables du processus pour évaluer
les transitions entre nœuds du graphe.

**AgFlow** est le résultat des travaux de Zeng et al. [ZBD+03, ZBN+04] qui ont cherché à apporter des réponses à plusieurs challenges fondamentaux liés à la composition orientée QdS. Tout d'abord, à effectuer une étude de plusieurs caractéristiques de QdS chez les services Web. Ensuite, à poser le problème de la sélection des services Web appropriés pour permettre à un utilisateur d'obtenir certaines propriétés de QdS dans sa composition de services comme minimiser le prix et maximiser la réputation des services. Finalement, ce travail souligne l'intérêt d'une approche dynamique pour la prise en compte des changements de QdS inhérents à la variabilité du Web et des applications. Les contributions qui en découlent consistent en un modèle multi-dimensionnel capturant les propriétés de QdS et exhibant des méthodes pour attacher des valeurs à ces propriétés dans le cadre de services atomiques et composites. Deux approches (locale et globale) pour la sélection de services dans les compositions sont ensuite détaillées et un moteur d'exécution, «Ag-Flow», qui réagit aux changements en planifiant de nouveau les services à l'exécution est présenté.

**ORBWork** est fruit des travaux de [CMSA02, CMSA04] qui se sont fixent pour tâche de permettre de déduire et de gérer la QdS des workflows de services Web. Pour cela, un modèle prédictif de QdS basé sur la QdS de tâches atomiques a été élaboré, ainsi qu'une implémentation, ORBWork, basée sur un moteur d'exécution de workflow.

La plateforme **WS-Binder** est présentée dans [CPE+06, DPEV+06] s'intéresse aux problématiques de recherche statique et dynamique de services dans les compositions. Ce travail réutilise un certain nombre de contributions faites par les travaux précédents (notamment la modélisation de la QdS et les formules d'agrégation), améliore certaines propositions (découpage du workflow pour réduire l'espace de recherche à l'ensemble des services n'ayant pas encore été invoqués), et propose des contributions originales dont un algorithme modulable pour la sélection de service, un modèle de déclenchement de nouveau la planification et la gestion de métriques spécifiques à un domaine. Ce travail propose une plateforme (WS-Binder) qui contient l'implémentation de ces propositions et qui travaille en parallèle du moteur d'exécution BPEL.

La plateforme **Qbroker** est un basée sur un broker est le résultat des travaux de Tao YU [YL05a, YL05b], présente une architecture de brokering pour l'intégration et l'adaptation dynamique des services Web dans les compositions de services. A l'instar d'autres approches, elle propose une modélisation de la QdS ainsi que des algorithmes de sélection de services basés sur les caractéristiques globales de la composition.

Le tableau de la figure 4.10 montre des caractéristiques de QdS considérées par les différentes plateformes susmentionnées. Ce tableau synthétise les évaluations de différentes plateformes sous les 5 critères suivants : Réutilisation : (du BPEL, des contrats SLA (Service Level Agreement) et des WS-Policy), Séparation des préoccupations (SdP) : (isolation des spécifications, intrusivité des plateformes), Couverture : (plage de caractéristiques de QdS, mécanismes de QdS, granularité), Dynamicité et Expressivité (richesse de l'interface, déclarativité). SdP désigne la séparation des deux préoccupations qui sont la préoccupation de la gestion de la QdS et la préoccupation de la gestion de la composition. L'intrusivité désigne le degré d'intrusion les mécanismes de gestion de la QdS dans la plateforme mettant en exécution la composition. C'est **eFlow** qui offre une plus grande ouverture, à cet
<table><thead><tr><th rowspan="2"></th><th colspan="2">Réutilisation</th><th colspan="2">SdP</th><th colspan="3">Couverture</th><th colspan="2">Dynam.</th><th colspan="2">Expressivité</th></tr><tr><th>BPEL</th><th>SLA</th><th>Isol.</th><th>Intrus.</th><th>Chara.</th><th>Méca.</th><th>Gran.</th><th>Rich.</th><th>Decl.</th><th>Rich.</th><th>Decl.</th></tr></thead><tbody><tr><td>AO4BPEL</td><td>+</td><td>-</td><td>+</td><td>±</td><td>-</td><td>±</td><td>±</td><td>±</td><td>-</td><td>+</td><td>+</td></tr><tr><td>DYNAMO</td><td>+</td><td>±</td><td>+</td><td>-</td><td>±</td><td>±</td><td>+</td><td>±</td><td>+</td><td>+</td><td>+</td></tr><tr><td>MASC</td><td>-</td><td>±</td><td>+</td><td>-</td><td>±</td><td>-</td><td>±</td><td>±</td><td>±</td><td>-</td><td>-</td></tr><tr><td>TRAP/BPEL</td><td>+</td><td>-</td><td>+</td><td>+</td><td>±</td><td>-</td><td>-</td><td>±</td><td>-</td><td>+</td><td>+</td></tr><tr><td>eFlow</td><td>-</td><td>-</td><td>-</td><td>-</td><td>+</td><td>±</td><td>-</td><td>+</td><td>-</td><td>+</td><td>+</td></tr><tr><td>AgFlow</td><td>-</td><td>+</td><td>-</td><td>-</td><td>+</td><td>±</td><td>+</td><td>+</td><td>±</td><td>-</td><td>-</td></tr><tr><td>ORBWork</td><td>+</td><td>-</td><td>+</td><td>+</td><td>+</td><td>-</td><td>+</td><td>+</td><td>±</td><td>-</td><td>-</td></tr><tr><td>WS-Binder</td><td>+</td><td>+</td><td>+</td><td>+</td><td>+</td><td>±</td><td>+</td><td>+</td><td>±</td><td>+</td><td>+</td></tr><tr><td>Optimizing QoS</td><td>±</td><td>±</td><td>-</td><td>-</td><td>-</td><td>-</td><td>+</td><td>±</td><td>-</td><td>-</td><td>-</td></tr><tr><td>broker</td><td>+</td><td>+</td><td>-</td><td>-</td><td>±</td><td>±</td><td>+</td><td>±</td><td>-</td><td>-</td><td>-</td></tr></tbody></table>

FIGURE 4.9 – synthèse des évaluations des plateformes [Bal08]. Dans ce tableau, les cases vides représentent des fonctionnalités n'ayant pas été prises en compte par le système. Dans les autres cas, les travaux ont été jugés selon une notation comportant trois niveaux croissants : "-", "±", "+".

égard, grâce à son langage de requête **XQL**. Très peu de plateformes considèrent les caractéristiques de sécurité. La gestion de la QdS recouvre un ensemble de domaines qui sont adressés de manière inégale par les différentes plateformes. Les plateformes **WS-Binder**, **AgFlow** et **Qbroker** permettent également de gérer les SLA (négociation, violation).

Dans un rapport technique plus récent datant de février 2010 et ayant pour auteurs **Moreno MARZOLLA** et **Raffaela MIRANDOLA** [MM10], il a été procédé à un comparatif des plateformes adressant la question de la QdS des services Web, nous en extrayons les tableaux 4.2 and 4.3. De cette évaluation, il est possible de tirer quelques enseignements. Pour ce qui est des attributs QdS, trois plateformes utilisent de multiples QdS, les autres utilisent entre 1 et 6 attributs. Pour ce qui est du point de vue, la plupart des plateformes utilisent le point de vue du consommateur, quatre seulement utilisent le double point de vue Fournisseur/Consommateur, et une seule le point de vue fournisseur. Dans la colonne niveau de développement Les auteurs différencient les approches Design Time. Enfin, en ce qui les modèles d'enrichissement des QdS : cinq plateformes utilisent des méthodes d'optimisation, trois plateformes utilisent des modèles parmi lesquelles deux utilisent les algorithmes génétiques ; les trois autres sont basées broker et ont été présentées en détails dans ce chapitre (voir supra).

## 4.4 Conclusion

L'état de l'art présenté dans ce chapitre couvre toutes les dimensions de la composition de services Web que cette composition soit manuelle, semi-automatique ou automatique; qu'elle soit statique ou dynamique; qu'elle se base sur des wokflows ou sur des graphes de composition; qu'elle soit basée sur des propriétés fonctionnelles ou non fonctionnelles.
<table><caption>TABLE 4.2 – Synthèse des évaluations des Approches de Composition des services orienté QdS selon [MM10] (1)</caption><thead><tr><td>Approche</td><td>Critères QdS</td><td>Point de vue</td><td>Niveau de développement</td><td>modèles d'enrichissement des QdS</td></tr></thead><tbody><tr><td>Cardoso et al. [CMSA04]</td><td>Temps de réponse, coût et fiabilité</td><td>Consommateur</td><td>Design Time</td><td>Modèles</td></tr><tr><td>Maximilien et al. [MS04a, MS04b]</td><td>Réputation et Confiance</td><td>Consommateur</td><td>Design Time, Run Time</td><td>Ontologie</td></tr><tr><td>Vu et al. [VHA05]</td><td>Temps de réponse, Réputation et Confiance</td><td>Consommateur</td><td>Design Time, Run Time</td><td>Ontologie</td></tr><tr><td>Casati et al. [CCDS04]</td><td>Temps de réponse</td><td>Consommateur</td><td>Run Time</td><td>Fouille des données mesurées</td></tr><tr><td>Zeng et al. [ZBN+04]</td><td>Prix, Disponibilité, fiabilité et Réputation</td><td>Consommateur</td><td>Design Time</td><td>Modèle d'optimisation</td></tr><tr><td>Ardagna et al. [AP05]</td><td>Temps de réponse, coût et Réputation</td><td>Consommateur</td><td>Design Time, Run Time</td><td>Modèle d'optimisation</td></tr><tr><td>Cardellini et al. [CCGM06]</td><td>Temps de réponse, coût et Réputation</td><td>Consommateur</td><td>Design Time</td><td>Modèle d'optimisation</td></tr><tr><td>Canfora et al. [CPE+06]</td><td>Temps de réponse, coût, Disponibilité et fiabilité</td><td>Consommateur</td><td>Design Time</td><td>Modèles (Algorithmes génétiques)</td></tr><tr><td>Claro et al. [CAKH05]</td><td>Temps de réponse, coût, Disponibilité et fiabilité</td><td>Consommateur</td><td>Design Time</td><td>Modèles (Algorithmes génétiques)</td></tr></tbody></table>
<table><caption>TABLE 4.3 – Synthèse des évaluations des Approches de Composition des services orienté QdS selon [MM10] (2)</caption><thead><tr><td>Approche</td><td>Critères QdS</td><td>Point de vue</td><td>Niveau de développement</td><td>modèles d'enrichissement des QdS</td></tr></thead><tbody><tr><td>Yu and Lin [YL05b]</td><td>Multiple QdS</td><td>Consommateur</td><td>Design Time</td><td>Modèle d'optimisation</td></tr><tr><td>Yu and Lin [YL05a]</td><td>Temps de réponse</td><td>Consommateur</td><td>Run Time</td><td>Framework basé sur broker</td></tr><tr><td>Patel [PSL03]</td><td>Multiple QdS</td><td>Consommateur</td><td>Run Time</td><td>Découverte, Sélection et Monitoring de services Web</td></tr><tr><td>Serhani et al. [SDHS05]</td><td>Temps de réponse, Temps de latence, Disponibilité, Réputation et Prix</td><td>Consommateur</td><td>Run Time</td><td>Framework basé sur broker</td></tr><tr><td>Dong and Yu [DY06]</td><td>Temps de réponse, Fiableté et coût</td><td>Consommateur</td><td>Design Time</td><td>Modèle d'optimisation</td></tr><tr><td>Rosenberg et al. [RPD06]</td><td>Temps de latence, Temps de réponse, Disponibilité et Précision</td><td>Consommateur</td><td>Run Time</td><td>Mesures</td></tr><tr><td>Schmid et al. [Sch06]</td><td>Temps de latence</td><td>Consommateur</td><td>Run Time</td><td>Mesures</td></tr><tr><td>Shercliff et al. [SSGF06]</td><td>Multiple QdS</td><td>Fournisseur</td><td>Design Time et Run Time</td><td>Suivi et Modèles</td></tr><tr><td>Yu and Lin [YL04]</td><td>Multiple QdS</td><td>Fournisseur et Consommateur</td><td>Run Time</td><td>Framework basé sur Broker</td></tr></tbody></table>
Nous avons examiné les classes de composition automatique, même si elles se fondent sur
le formel, la logique, les preuves de théorèmes, la planification avec ses variantes, la logique
linéaire ou le calcul situationnel, aucune classe ne semble disposer de plus d'avantages que
les autres.

Pour notre part, nous allons nous inspirer des méthodes logiques et notamment déductives,
qui fera l'objet du chapitre 7 pour proposer notre approche de composition de services Web.

Par ailleurs, Les méthodes de sélection de services composites à base de QdS qui ont été
proposées au cours des cinq dernières années, sont nombreuses et diversifiées. Les solutions
'optimales' ne peuvent être obtenues qu'en faisant appel à des algorithmes conçus pour
des problèmes d'optimisation réputés NP-complets. En faisant appel à la programmation
linéaire ou à la programmation en nombres entiers, à la programmation dynamique ou au
problème du sac à dos, au problème de la recherche d'un chemin optimal ou à la CSP,
la composition abstraite peut sembler séduisante mais la composition concrète est loin
d'être implémentable en raison de la complexité temporelle de ces algorithmes qui est
exponentielle. Il a fallu recourir à des heuristiques pour rendre ces approches praticables
dans des cas réels où le nombre de classes de services est élevé et où la cardinalité de
chaque classe est élevée. Pour avoir une complexité temporelle polynomiale, il avait fallu
se contenter de solutions sous-optimales. Pour le méta-framework BioMed, nous allons
considérer des requêtes étendues de composition en ce sens qu'elles portent sur deux volets :
le premier centré sur les propriétés fonctionnelles alors que le second est centré sur des
propriétés non fonctionnelles (attributs de QdS). Dans le cas où BioMed ne découvre pas
de service atomique répondant au mieux à la requête, c'est le moteur de composition qui
est sollicitée.

Cette seconde partie de ce mémoire aura pour finalité de présenter une nouvelle ap-
proche de médiation de ressources Web opérant à différents niveaux : une médiation de
services Web, une médiation ontologique et une médiation de données. La médiation de
services repose sur la strate inférentielle de BIOMED permettant d'exploiter les connais-
sances ontologiques afin d'offrir des mécanismes flexibles de découverte et de composition.
La médiation ontologique repose sur une méta-carte ontologique conçue afin de représenter
le double engagement sémantique et ontologique reflétant une conceptualisation partagée
du domaine ciblé. La médiation de données se base sur le modèle d'alignement sémantique
afin d'offrir un modèle pivot de descriptions canoniques explicitant la sémantique d'un
service Web.

La seconde partie comprend les trois chapitres suivants :

Dans le chapitre 5, nous présentons le méta-framework BIOMED et ses différents ni-
veaux de stratification. Nous présentons les trois composantes clés de ce méta-framework
à savoir : le modèle d'alignement (normalisation) sémantique des descriptions de services
Web, une méta-carte ontologique permettant d'offrir une sémantique unifiée et un modèle
inférentiel permettant de formaliser une large typologie de raisonnement déductif.

Le chapitre 6 présente l'approche de découverte du méta-framework BIOMED basée
sur le raisonnement déductif afin d'inférer les solutions satisfaisant les contraintes fonc-
tionnelles d'une requête. Un mécanisme de classement est mis en place en considérant
l'ensemble des solutions sélectionnées par le moteur de raisonnement pour déceler les
bonnes voire meilleures solutions en combinant deux techniques celle de l'opérateur skyline
[BKS01] et celle du top-k [IBS08].

Le chapitre 7 sera consacré à la présentation de l'approche de composition du méta-
framework BIOMED permettant de déduire dans un premier temps par le biais des tech-
niques de raisonnement l'ensemble des plans de composition comprenant un ensemble de
services vérifiant les critères de composabilité fonctionnelle des service composants (com-
posabilité exacte ou rapprochée) et dans un second temps de sélectionner parmi les plans
de composition identifiés lors de la première phase, les plans qui vérifient les critères QdS.
La seconde phase sera résolue par deux approches possibles : la première identifique à celle
adoptée dans le chapitre 6 et la seconde adoptant une heuristique différente *non Pareto*.
Deuxième partie

Proposition, Contributions et
Expérimentations
<figure><img src="image_41.png" /></figure>
# Chapitre 5

## Un Méta-Framework stratifié de médiation de Services Web sémantiquement hétérogènes

### Sommaire

<table><tr><td>5.1 Cadre Conceptuel du Méta-Framework</td><td>102</td></tr><tr><td>5.1.1 Le niveau ressource</td><td>103</td></tr><tr><td>5.1.2 Le niveau description</td><td>104</td></tr><tr><td>5.1.3 Le niveau ontologique</td><td>105</td></tr><tr><td>5.1.4 Le niveau inférentiel</td><td>108</td></tr><tr><td>5.1.5 Le niveau processus</td><td>108</td></tr><tr><td>5.2 Un Modèle unifié pour la description de SW</td><td>109</td></tr><tr><td>5.3 Méta-Carte Ontologique</td><td>114</td></tr><tr><td>5.3.1 Le cadre de référence ontologique</td><td>117</td></tr><tr><td>5.3.2 Ontologies et représentation des connaissances</td><td>118</td></tr><tr><td>5.3.3 Le modèle conceptuel de BIOMED</td><td>118</td></tr><tr><td>5.4 Annotations sémantiques pour la sémantisation de SW</td><td>121</td></tr><tr><td>5.5 Une sémantique axiomatique comme fondement du modèle inférentiel</td><td>123</td></tr><tr><td>5.5.1 La relaxation assertionnelle (au niveau des instances)</td><td>124</td></tr><tr><td>5.5.2 La relaxation par généralisation et par spécialisation</td><td>125</td></tr><tr><td>5.5.3 La relaxation fonctionnelle</td><td>126</td></tr><tr><td>5.5.4 La relaxation fonctionnelle inverse</td><td>127</td></tr><tr><td>5.6 Conclusion</td><td>128</td></tr></table>

Le présent chapitre est consacré à la présentation du méta-framework de médiation sémantique proposé dans le cadre de cette thèse que nous nommons BIOMED pour *Bioinfor-matic Mediation Framework*. Le chapitre s'organise comme suit, la section 5.1 présente le cadre conceptuel et les objectifs du méta-framework proposé. Le modèle unifié de descriptions canoniques de services est présenté dans la section 5.2. La section 5.3 présente la méta-carte ontologique que nous proposons afin de pallier l'hétérogénéité des ontologies
existantes dans le domaine visé et pour assurer les engagements sémantique et ontologique. La section 5.4 discute l'annotation sémantique des descriptions de services Web. Enfin, dans la section 5.5, nous explicitons les mécanismes inférentiels que nous proposons afin d'exploiter les descriptions unifiées et les annotations sémantiques permettant ainsi de relaxer les propriétés des services et d'élargir leur portée et leur couverture sémantique.

### 5.1 Cadre Conceptuel du Méta-Framework

La médiation sémantique de services a pour objectif d'exploiter la sémantique explicite des services afin d'en faciliter la découverte, la sélection et la composition en *workflow* pour des utilisateurs finals. La sémantisation des descriptions de services représente une phase nécessaire dont l'objectif est d'expliciter la sémantique d'un service et de générer sa description sémantisée. Une description sémantisée comprend un ensemble de *primitives描述性* permettant de décrire explicitement les propriétés pertinentes d'un service associées à un ensemble d'annotations sémantiques décrivant le *lien* entre les primitives descriptiones et les concepts d'une ontologie du domaine. Ainsi, les annotations sémantiques permettent d'instancier les primitives descriptives à l'aide de concepts, relations sémantiques ou instances décrits dans une ontologie. Elles ont pour objectif d'exprimer formellement la sémantique du service afin d'améliorer sa découverte et sa composition et donc sa réutilisation.

Toutefois, différents conflits d'hétérogénéité sémantique peuvent surgir. Nous distinguons une double hétérogénéité sémantique au niveau des descriptions sémantisées de services :

1. L'hétérogénéité des primitives descriptives liée au framework adopté pour déclarer la sémantique du service;

2. L'hétérogénéité des annotations sémantiques qui peuvent être définies par le biais d'ontologies diverses.

En effet, les services peuvent faire appel à différentes ontologies du domaine comme les descriptions peuvent être décrites à l'aide de primitives appartenant à différents framworks de services Web sémantiques. Pour ce faire, nous proposons un méta-framework stratifié permettant de décrire, d'exploiter et de raisonner sur des services Web. Afin de pallier l'hétérogénéité des primitives descriptives, le méta-framework BIOMED repose sur un modèle d'alignement sémantique visant à générer des descriptions canoniques de services Web, ce modèle offre un ensemble de primitives sémantiques résultant de l'alignement des méta-modèles sous-jacents aux ontologies OWL-S et WSMO et celui des annotations SAWSDL. Ces primitives permettent d'expliciter les propriétés fonctionnelles et non fonctionnelles d'un service Web.

Afin de réconcilier les ontologies du domaine bioinformatique, nous avons proposé une méta-carte ontologique reflétant une sémantique consensuelle du domaine spécifiant les objets du domaine qui peuvent être associés à chaque concept de la méta-carte, conformément à sa signification formelle. Cette signification est induite par d'une part une *sémantique référentielle* établissant le lien entre l'intension et les extensions du concept impliquant notamment des relations d'hyperonomie/hyponymie, d'holonymie/méronymie et d'autre
part une sémantique différentielle entre les extensions du concept impliquant un arc sémantique allant de la synonymie à l'antonymie. La méta-carte ontologique est utilisée pour la génération des annotations sémantiques de services Web comme elle représente le soubassement du modèle inférentiel de Biomed. Le méta-framework illustré dans la figure 5.2 comporte cinq niveaux de conceptualisation : le niveau ressource, le niveau description, le niveau ontologique, le niveau inférentiel et le niveau processus. Nous détaillons dans ce qui suit ces cinq niveaux de stratification.

### 5.1.1 Le niveau ressource

Le niveau ressource comprend un ensemble de ressources Web accessibles par le biais d'interfaces de services Web. Dans le domaine bioinformatique, les services Web sont conçus pour standardiser la façon d'accéder à divers types de ressources comprenant des sources de données génomiques telles que GenBank<fnref n="1" /> ou protéiques telles que Swiss-Prot<fnref n="2" /> ou de maladies génétiques telles que OMIM<fnref n="3" /> mais également des outils tels que BLAST<fnref n="4" />. Les ressources bioinformatiques sont caractérisées par une forte hétérogénéité qui s'illustre à différents niveaux :

- **le niveau syntactique** : les modèles de données sont différents selon les sources : on retrouve le modèle relationnel (par exemple dans *Ensembl*<fnref n="5" />), le modèle XML (tel que dans la source UniProt<fnref n="6" />) ou encore les fichier balisés (tels que ceux de *SwissProt* et *GenBank*). La technologie de services Web permet de masquer le niveau d'hétérogénéité syntactique. Les services dans le domaine bioinformatique sont en grande partie des services orientés données (en opposition aux services orientés fonctionnalités) du fait qu'ils encapsulent de gigantesques sources de données afin de masquer la structure de ces sources et leur contenu informationnel en mettant en vigueur les politiques de sécurité associées.

- **le niveau conceptuel** : nous distinguons deux types d'hétérogénéité conceptuelle, la diversité des focus et de niveau de granularité. En bioinformatique, chaque source se focalise sur une entité conceptuelle du domaine. Certaines se focalisent sur la protéine comme entité centrale, d'autres sources se focalisent sur les gènes ou les maladies comme entité centrale, d'autres s'intéressent aux marqueurs de séquences exprimées alors que certains se focalisent sur les interactions entre protéines. Le niveau de granularité peut aussi varier selon les sources, celles qui se concentrent sur le génome humain et ceux qui s'intéressent à différents génomes de plusieurs espèces.

- **le niveau sémantique** : l'hétérogénéité sémantique s'illustre au niveau des instances des sources et des annotations sémantiques qu'elles contiennent. En l'occurrence,

<footnote n="1">1. http://www.ncbi.nlm.nih.gov/Genbank/</footnote>

<footnote n="2">2. http://www.ebi.ac.uk/uniprot/</footnote>

<footnote n="3">3. http://www.ncbi.nlm.nih.gov/omim/</footnote>

<footnote n="4">4. BLAST (acronyme de Basic Local Alignment Search Tool) est une méthode de recherche heuristique utilisée en bioinformatique permettant de trouver les régions similaires entre deux ou plusieurs séquences de nucléotides ou d'acides aminés. Ce service permet de retrouver rapidement dans des bases de données, les séquences ayant des zones de similitude avec une séquence donnée (spécifiée comme entrée par l'utilisateur). La méthode BLAST a été implémentée National Center for Biotechnology Information (NCBI), cette implémentation est accessible à l'adresse http://blast.ncbi.nlm.nih.gov/Blast.cgi</footnote>

<footnote n="5">5. http://www.ensembl.org/index.html</footnote>

<footnote n="6">6. http://www.uniprot.org/</footnote>
différents noms et symboles existent pour le même gène ou pour la même protéine. De plus, les sources décrivent une même entité du domaine selon des perspectives différentes, ceci peut être relative par exemple à l'expertise du bioinformaticien.

Durant les 20 dernières années, les ressources de données biologiques disponibles sur le Web se sont multipliées. Leur croissance est en forte progression depuis 10 ans. La *Databases Issue* de la revue Nucleic Acids Research (NAR), qui liste chaque année les sources les plus importantes du Web dans le domaine bioinformatique, recense plus de 1230 ressources en 2010, soit 58 ressources plus que l'année précédente et 168 ressources de plus qu'en 2009. Au total, le nombre de ressources a été multiplié par trois durant les dix dernières années. En pratique, ces ressources forment un réseau fortement connecté de noeuds inter-reliés par des références croisées qui permettent de faciliter la navigation à l'utilisateur. En effet, une entrée dans Swiss-Prot consistant en une protéine fera référence au gène lié par le biais d'un lien hypertexte pointant vers l'entrée relative au gène dans la ressource GenBank qui fera à son tour référence à la maladie associée à la mutation de ce gène dans la ressource OMIM. De plus, ces ressources sont sémantiquement annotées avec des concepts de différents vocabulaires contrôlés tels que Gene Ontology (GO) ou Mesh ou de nomenclatures telles que SNOMED.

L'avènement des services Web a révolutionné les modes d'accès à ces ressources et a permis de masquer les problèmes d'hétérogénéité syntactique inhérents aux ressources bioinformatiques et cela en offrant une plate-forme d'interopérabilité basée sur les services. Cependant, de nouveaux problèmes et défis ont vu le jour en termes de découverte et de sélection de services dans un environnement ouvert tel que le Web et face aux attentes diversifiés de scientifiques de plus en plus exigeants. D'autant plus que ces derniers ont constamment besoin de comparer les résultats générés à partir de plusieurs ressources et outils voire même les orchestrer afin de répondre à une requête complexe. Ainsi, le besoin en découverte et composition de services dans le domaine bioinformatique devient de plus en plus pressant afin de faire face à l'évolution du nombre de services Web et afin de guider les scientifiques à découvrir et composer les services Web les plus appropriés à leur besoin.

### 5.1.2 Le niveau description

La description d'un service correspond à la spécification de ses capacités en termes de fonctionnalités exprimée dans un langage formel et interoperable afin qu'elle soit exploitée par des agents humains et/ou artificiels. Une description peut être syntaxique telles qu'une description WSDL ou sémantisée si elle comprend des annotations faisant référence à une ontologie du domaine. Une description, quelle soit syntaxique ou sémantisée, est définie par le biais d'un ensemble de primitives que nous nommons *primitives descriptives*. A titre d'exemple, les primitives descriptives du langage WSDL constituent l'ensemble des mots-clés du langage tels que *operation*, *message*, *porttype*, etc. Une description sémantisée d'un service Web est définie par le biais d'un ensemble de primitives descriptives associées à un ensemble d'annotations sémantiques faisant référence à des concepts, relations ou instances ontologiques. Plusieurs frameworks de descriptions sémantiques ont été étudiées dans le chapitre 3 du présent mémoire et qui sont principalement : OWL-S, WSMO, SAWSDL. Ces frameworks offrent chacun de son côté des primitives descriptives permettant de générer
des descriptions sémantisées de SW qui sont hétérogènes entre elles. Cette hétérogénéité rend difficile l'élaboration d'une approche générique de découverte et de composition de services.

Pour ce faire, nous proposons au niveau description du méta-framework BIOMED un modèle unifié de descriptions sémantisées de services Web. Ce modèle offre un ensemble de primitives descriptives qualifiées de canoniques ayant comme objectif d'unifier les descriptions des frameworks existants de services Web sémantiques et les aligner afin de converger vers une sémantique unifiée représentative des aspects fonctionnels et non fonctionnels d'un service atomique (élémentaire ou non décomposable). Le modèle unifié permet de déclarer la signature fonctionnelle d'un service atomique en termes d'entrées, de sorties, préconditions et postconditions et un ensemble de propriétés non fonctionnelles décrivant la qualité du service. Nous avons omis de considérer les primitives permettant de décrire le comportement interne d'un service pour deux raisons, la première est liée au fait que les services du domaine bioinformatique sont en grande partie des services atomiques avec des interfaces (signatures fonctionnelles) riches vu la complexité des schémas des sources qu'ils encapsulent, et la seconde est liée à notre besoin de faire émerger une **sémantique minimale et suffisante** pour décrire canoniquement un service, le découvrir et le composer éventuellement avec d'autres services.

### 5.1.3 Le niveau ontologique

Au niveau ontologique du méta-framework BIOMED, un référentiel normalisé de services bioinformatiques est construit manuellement en adoptant le modèle pivot de descriptions canoniques du modèle unifié et en se basant sur une représentation sémantique permettant d'expliciter la sémantique des services Web.

La diversité des ontologies existantes dans le domaine bioinformatique comme le montrent des portails dédiés tels que OBO<sup>7</sup> (Open Biological and Biomedical Ontologies) foundation et le BioPortal<sup>8</sup> montre le besoin d'une représentation sémantique partagée consensuelle vérifiant un double engagement sémantique et ontologique [Bac00]. En effet, de la richesse et la complexité des connaissances du domaine cible et de la co-existence de plusieurs théories, facettes, points de vue dans ce même domaine émerge le besoin d'une sémantique partagée pourvue d'un ensemble de primitives sémantiques flexibles au sein d'une architecture modulaire reliant les composants d'une ontologie ou de différentes ontologies. D'autant plus que l'étude des ontologies proposées dans le domaine bioinformatique et biomédical montre leur inadéquation au besoin de médiation, de réconciliation et d'interopérabilité sémantique.

Ainsi, nous proposons de concevoir une méta-carte ontologique représentant la sémantique du réseau formé par les ontologies du domaine bioinformatique et nous la situons à un niveau intermédiaire entre une ontologie fondationnelle<sup>9</sup> telles que DOLCE, SUMO ou GFO et les ontologies du domaine. La conception de la méta-carte aura à répondre à un certain nombre de besoins qui sont décrit comme suit :

<footnote n="7">7. http://www.obofoundry.org/</footnote>

<footnote n="8">8. http://bioportal.bioontology.org/</footnote>

<footnote n="9">9. L'annexe A de ce mémoire présente un état de l'art des ontologies fondationnelles tout en les comparant.</footnote>
- **Fondements des primitives** : Les primitives de classes et de relations utilisées dans une la méta-carte doivent être fondées sur un ensemble de principes reflétant la motivation cognitive (comprenant l'intersubjectivité et la plus large capacité de réutilisation). L'appui d'une ontologie fondationnelle DOLCE permet de modéliser les méta-propriétés cognitives qui seront héritées par les concepts définis au niveau de la méta-carte.

- **Couverture Sémantique** : La méta-carte ontologique devrait assurer la couverture de toutes les entités du domaine (couverture extensionnelle) tout en garantissant la couverture de tous les types d'entités du domaine (couverture intensionnelle).

- **Précision de la modélisation** : La méta-carte doit tenter de représenter tous les modèles possibles du domaine d'intérêt et couvrir les tâches devant être accomplis, c'est dans ce sens qu'elle est multi-facette.

- **Modularité légère et forte** : dans le but de moduler l'espace du domaine conceptuel autant que possible, la méta-carte doit permettre d'organiser les théories du domaine soit dans des ontologies différentes soit dans des descriptions et situations différentes.

- **Scalabilité** : Les langages expressifs devraient représenter les détails des significations en conformité avec le domaine et les tâches qui y sont accomplies. Les ontologies expressives peuvent être utilisées comme ontologies référentielles ou comme aide et support à des services sophistiqués. Comme ontologies référentielles elles doivent supporter la scalabilité en vue d'aider computationnellement des services ardus comme l'extraction d'information (ou de connaissances) à partir d'entrepôts assez larges ou à partir du Web comme dans le cas du Web Sémantique.

- **Consistance Logique** : Les ontologies doivent être exprimées dans un langage formel disposant d'une sémantique formelle explicite à l'instar de la logique de premier ordre (LPO) de KIF, d'une Logique de Description (DL), de OWL etc.

Le choix d'utiliser une ontologie fondationnelle comme soubassement pour la conception de la méta-carte ontologique est justifié par les trois principaux arguments suivants, comme signalé par OBERLE et ses collègues dans [OAH+07] et qui font que l'ontologie fondationnelle :

- Peut servir comme base de modélisation en fournissant un point de départ pour construire de nouvelles ontologies. Au lieu de modéliser à partir de zéro, l'utilisation des ontologies fondationnelles fournit aux concepteurs un ensemble d'entités ontologiques prédéfinies qui sont réutilisables pour les ontologies qu'ils veulent construire ;

- Peut être choisie pour sa clarté conceptuelle car fournissant un point de référence pour une comparaison rigoureuse entre plusieurs approches ontologiques possibles, et un cadre de travail pour analyser, harmoniser, et intégrer des ontologies existantes ;

- Peut offrir des modèles de conception d'ontologie : idéalement, une ontologie fondationnelle définit et propose des modèles de conception d'ontologies pour des besoins de modélisation récurrents, tels que la localisation dans le temps et l'espace.

La méta-carte ainsi conçue comprend un ensemble de concepts "génériques" du domaine que nous nommons *hyper-concepts* interconnectés par un ensemble de relations sémantiques. Chaque hyper-concept est relié à une ou plusieurs ontologies décrivant l'ex-
<figure><img src="image_42.png" /><figcaption>FIGURE 5.1 – Illustration du niveau ontologique du méta-Framework BioMed</figcaption></figure>

tension de l'hyper-concept<fnref n="10" /> ou son intension<fnref n="11" />. En l'occurrence, l'ontologie Gene Ontology (GO) décrit les fonctions d'un gène au niveau extensionnel, la PO (Protein Ontology) offre une description unifiée du concept Protéine donc l'intension du concept associé (protéine) comme l'illustre la figure 5.1. La Sequence Ontology offre une description unifiée du concept séquence en spécifiant ses propriétés selon plusieurs points de vue : la structure (exon, intron, promoteur), la longueur, le type (nucléotidique ou acides aminés), le génome, les variations chromosomiques<fnref n="12" />.

**Définition 1 (Méta-carte Ontologique)** Etant donné un ensemble d'ontologies du domaine O={o₁,...,o_n}, la méta-carte ontologique d'un domaine D notée C=(V,E) est un graphe direct orienté composé d'un ensemble de noeuds V désignant les concepts du domaine reliées par un ensemble d'arcs E désignant des relations sémantiques. Une carte sémantique C est munie d'une fonction de mapping M : V → O qui permet d'associer à chaque concept c de l'ensemble des concepts V, une ontologie o décrivant l'extension du concept c.

<footnote n="10">10. l'ensemble d'instances du hyper-concept</footnote>

<footnote n="11">11. les caractéristiques spécifiques du concept</footnote>

<footnote n="12">12. Ces concepts sont définis dans le glossaire de la bioinformatique présenté en fin du rapport.</footnote>
### 5.1.4 Le niveau inférentiel

Le niveau inférentiel permet de modéliser l'ensemble des connaissances inférentielles du domaine des services. A cet effet, nous proposons une axiomatique pour formaliser ce type de connaissances. Cette axiomatique comprend différents schémas d'axiomes formalisant différent types de raisonnement qui sont réalisés à différent niveaux de conceptualisation de BIOMED. Nous distinguons trois niveaux de raisonnement : (a) au niveau ontologique ayant pour objectif d'exploiter les connaissances ontologiques, (b) au niveau description ayant pour objectif d'exploiter les descriptions sémantisées de SW et (c) au niveau assertionnel ayant pour objectif de raisonner sur les instances des services (instances de paramètres).

Le niveau inférentiel comprend un moteur d'inférence qui se base sur un raisonnement déductif. Ainsi, le moteur d'inférence implémente trois types de schémas d'axiomes qui sont décrits comme suit :

1. les axiomes du niveau **ontologique** permettent d'exploiter les connaissances de la carte ontologique et se déclinent en axiomes portant sur les concepts tels que le lien *is-A* ou la propriété de *disjonction de concepts* et des axiomes portant sur les relations sémantiques telles que les propriétés algébriques des relations (transitivité, réflexivité, anti-réflexivité, symétrie, anti-symétrie).

2. les axiomes du niveau **service** permettent de raisonner au niveau des descriptions unifiées des instances de services afin d'inférer de nouvelles descriptions sémantiques décrivant les services. Les axiomes du niveau service reposent sur les axiomes du niveau ontologique et du niveau assertionnel.

3. les axiomes du niveau **assertionnel** permettent de raisonner au niveau des instances et d'inférer par exemple le concept spécifique/général auquel une instance appartient.

Enfin, la sémantique axiomatique qui fait l'objet de la sous-section 5.5 permet de formaliser l'ensemble des connaissances inférentielles du domaine, les trois niveaux de raisonnement permettent d'enrichir la couverte sémantique des descriptions des services Web, ce qui permettra un appariement flexible entre les contraintes des clients et les descriptions de services.

### 5.1.5 Le niveau processus

Le niveau processus correspond aux différents processus pouvant être réalisés dans une architecture orienté service à savoir principalement ceux de la découverte et de la composition de services Web.

Le processus de découverte dans BIOMED repose sur le moteur de raisonnement déductif pour sélectionner les services Web atomiques qui répondent fonctionnellement et non fonctionnellement à une requête de découverte. Nous montrons que le raisonnement déductif permet d'élargir considérablement l'espace de recherche (search space) des services candidats afin d'apparier au mieux les contraintes de la requête. Contrairement aux approches existantes de découverte de services qui proposent des solutions de découverte exclusive-ment basées soit sur les propriétés fonctionnelles soit sur les propriétés non fonctionnelles d'un service et non pas les deux à la fois, l'approche de découverte proposée ici sélectionne les services en se basant sur les deux familles de propriétés. Etant donné que le nombre
de services candidats à une requête peut être élevé dans certains cas, nous avons adopté une heuristique de sélection des meilleurs services combinant les techniques basées sur l'opérateur *skyline* et les techniques de ranking *top-k*, ce qui permet de déterminer les meilleurs (top-k) services en se basant sur les valeurs des propriétés non fonctionnelles. L'approche de découverte est originale du fait qu'elle permet de combiner des techniques de raisonnement et de classement (ranking). L'approche de découverte proposée est présentée en détails dans le chapitre 6.

D'un autre côté, l'approche de composition se base sur le moteur de raisonnement pour déduire des chemins (possibles) constitués d'un ensemble de services atomiques vérifiant les critères de composabilité. En effet, une requête utilisateur est interprétée en premier lieu en tant que requête de découverte, si aucun service atomique ne répond aux spécifications de la requête alors le moteur de composition la prend en charge pour définir un graphe de composition définissant au moins un plan de composition de services satisfaisant la requête. Le moteur de raisonnement déductif permet de déduire un ensemble de services fonctionnellement satisfaisant la requête. Dans une seconde phase, l'approche de composition permettra de classer les plans de composition entre eux afin d'identifier les plus satisfaisants. L'approche de composition proposée sera présentée dans le chapitre 7.

## 5.2 Un Modèle unifié pour la description de SW

Nous proposons dans cette section un modèle de descriptions canoniques pour la représentation de services Web sémantisés. Ce modèle consiste en une vue unifiée des descriptions sémantiques de SW afin de pallier l'hétérogénéité des frameworks existantes à savoir OWL-S (Ontology Web Service), WSMO (Web Service Modeling Ontology) et le langage SAWSDL (Semantic Annotations for WSDL). Il ne s'agit pas de proposer un nouveau modèle pour la description sémantique de services Web mais de faire converger les modèles des propositions citées dessus vers un ensemble de descriptions canoniques qui capture une sémantique minimale et suffisante à l'automatisation des processus de découverte et de composition de SW. Il est important de considérer les trois dimensions suivantes dans la conception d'une description d'un service Web :

- Le niveau d'expressivité des descriptions. Entre une description en langage naturel et une formalisation en logique du premier ordre pour décrire un service, il s'agit de trouver un compromis entre une représentation formelle et riche sémantiquement pour garantir l'automatisation des tâches de découverte et de composition de services Web.

- La portée ou la couverture des descriptions et leur complétude. Il s'agit de trouver l'ensemble des propriétés canoniques nécessaires et suffisantes à la découverte d'un service Web. S'agit-il du même ensemble de propriétés canoniques lors d'un processus de composition ?

- L'usage de la description pour implémenter des scénarios d'expérimentation des Services Web sémantisées dans le monde réel.

En premier lieu, nous notons une hétérogénéité des labellisations au niveau des constructeurs ou primitives de description des frameworks. En effet, pour désigner l'interface du service, OWL-S prévoit une sous ontologie nommée *Ontology Profile*, le terme profil désigne
<figure><img src="image_43.png" /><figcaption>FIGURE 5.2 – Différents niveaux de stratification du méta-framework BIOMED</figcaption></figure>
l'interface du service. WSMO explicite l'objectif (Goal) et la capacité (capability) du service comme connotation de l'interface d'un SW. SAWSDL se base sur les mêmes constructeurs que le langage WSDL en rajoutant des annotations faisant référence à des concepts ontologiques (reference annotation).

De plus, les langages de formalisation de ces descriptions sont eux-mêmes hétérogènes, OWL-S se base sur le langage OWL (Ontology Web Language) pour être compatible avec l'infrastructure du Web sémantique, WSMO se base sur un langage logique du premier ordre WSML (Web Service Modelling Language) pour pouvoir raisonner sur les descriptions et SAWSDL consiste en une simple extension du langage WSDL pour garantir une compatibilité avec l'infrastructure actuelle des SW. L'usage des frameworks existants dans le monde est très limité, peu de travaux présentent des scénarios d'expérimentation des trois frameworks dans le monde réel et leur usage reste purement académique.

Le modèle canonique de BIOMED, illustré par la figure 5.5, s'appuie sur le schéma RDF-S (RDF Schema) pour décrire les différentes propriétés des services Web. RDF-S est le langage de description de ressources sur le Web permettant de déclarer des taxonomies de classes et de propriétés. Au niveau du modèle unifié des descriptions de services, ce dernier est décrit par un ensemble de primitives descriptives permettant d'expliciter sa signature fonctionnelle et un ensemble de propriétés non fonctionnelles décrivant sa qualité. Nous nommons les descriptions générées par le modèle unifié, **descriptions canoniques**.

En effet, un premier sous-ensemble de primitives descriptives permet de déclarer les propriétés fonctionnelles du service comprenant la liste des entrées, des sorties, de paramètres, de préconditions (les conditions devant être vérifiées par les entrées) et les postconditions (les conditions devant être vérifiées par les sorties du service). Ces propriétés fonctionnelles sont décrites d'une manière hétérogène au niveau des frameworks OWL-S et WSMO. Nous prévoyons l'existence de wrappers pour traduire les descriptions de services en OWL-S et WSMO vers notre modèle de description canonique. L'ensemble de mappings entre les primitives OWL-S, WSMO et le modèle de description BIOMED est illustré par les figures 5.3 et 5.4.

Le second sous-ensemble de primitives permet de décrire les propriétés non fonctionnelles (PNF) décrivant la qualité d'un service. Nous distinguons deux types de propriétés QoS, celles qui sont indépendantes du domaine du service et qui peuvent être adoptées quel que soit le domaine et celles qui sont spécifiques au domaine et variant d'un domaine à l'autre. Par exemple, le critère débit exprimé en bit par seconde est significatif dans le contexte d'un service de vidéo à la demande, par contre, dans le contexte de services en e-commerce, il serait primordial de considérer le critère sécurité.

Les PNF indépendantes du domaine correspondent à celles fréquemment utilisées dans le domaine de la Qualité de Service (en anglais, Quality of Service QoS) [Ran03, KKL03] et incluent : le temps de réponse, le débit, la disponibilité, la fiabilité.

- Le temps de réponse (*Response Time*) est le temps mis entre l'envoi de la requête par le client et la réception du résultat envoyé par le service Web. L'unité de mesure du temps de réponse est la milliseconde (ms).

- Le débit (*Throughput*) est mesuré par le nombre total d'invocations possibles d'un service Web dans un laps de temps donné. L'unité de mesure du débit est le nombre d'appels réussis par seconde.
<figure><img src="image_44.png" /><figcaption>FIGURE 5.3 – Mappings entre le modèle unifié de BiOMED et le méta-modèle de l'ontologie de profil OWL-S</figcaption></figure>
<figure><img src="image_45.png" /><figcaption>FIGURE 5.4 – Mappings entre le modèle unifié BIOMED et le méta-modèle du framework WSMO</figcaption></figure>
- la disponibilité (*availability*) exprimé en pourcentage, permet de mesurer la probabilité que le service soit opérationnel à un instant t. Ce critère est le rapport du nombre de fois de disponibilité du service par rapport au nombre total d'invocations du service dans un laps de temps.

- La fiabilité (*reliability*) est le rapport du nombre de messages d'erreur sur le nombre total de messages. Ce critère est mesuré en pourcentage.

D'un autre côté, nous avons identifié deux critères QdS spécifiques au domaine bioinformatique. Les deux critères non fonctionnels sont : le *degré de confiance* et la *compléture*. Ces deux critères ont été déjà considérés dans les travaux de thèse de Sarah Cohen Boulakia intitulé *"Intégration de données biologiques : Sélection de sources centrée sur l'utilisateur"* [Bou05]. Le degré de confiance reflète le degré de précision (sûreté) des informations fournies par un service. Un biologiste aurait plus confiance dans le service *SwissProt* ayant un degré de confiance de dix sur dix du fait que la source contient des informations protéiques vérifiées à la main (curated) par des experts du domaine. La compléture reflète la capacité d'une service à fournir le maximum d'instances d'une entité spécifiques.

Le service eFetchGeneService<fnref n="13" /> a un niveau de compléture maximum (10), alors que le service OMIM<fnref n="14" /> n'a qu'un niveau de compléture de 4 car la ressource OMIM ne contient qu'une partie des gènes séquencés ceux pouvant être associés aux maladies humaines.

Pour ce qui est des propriétés non fonctionnelles, notons qu'elles sont représentées de façon hétérogène au niveau des frameworks OWL-S et WSMO et sont inexistantes dans SAWSDL. Le framework OWL-S se limite à une description textuelle du service, de la catégorie du service et des informations sur le fournisseur comme propriétés non fonctionnelles comme il n'intègre pas des descriptions sur la qualité du service. Au niveau WSMO, il existe deux types de propriétés non fonctionnelles, le premier type appelé *core properties* relève des méta-données Dublin Core<fnref n="15" />, et le second type est spécifique à l'aspect qualité du service Web. Cependant, WSMO ne prévoit pas l'ajout de propriétés QdS relatives au domaine du service comme c'est le cas du dans le modèle unifié BIOMED. Le modèle de description canonique est illustré dans la figure 5.5.

## 5.3 Méta-Carte Ontologique

Dans l'exercice qui est le nôtre, nous nous proposons d'utiliser les ontologies sous la forme d'artéfacts sémantiques construits à partir de plusieurs ontologies de domaine, et une ontologie fondationnelle et reposant sur l'explicitation d'une sémantique formelle. Une telle sémantique constitue le fondement des langages utilisés pour la spécification des tâches et des domaines d'intérêt. Ainsi, quand un langage dispose d'une sémantique formelle, la représentation du contenu exprimé dans ce langage est une théorie formelle. C'est dans ce sens que les ontologies, sont en dernier ressort, des théories formelles sous des formes appropriées.

<footnote n="13">13. eFetchGene est un service Web permettant d'interroger la base génomique Entrez Gene de NCBI, la description du service est accessible à l'adresse http://www.ncbi.nlm.nih.gov/entrez/eutils/soap/v2.0/efetch_gene.wsdl</footnote>

<footnote n="14">14. http://xml.nig.ac.jp/wsdl/OMIM.wsdl</footnote>

<footnote n="15">15. http://dublincore.org/</footnote>
<figure><img src="image_46.png" /><figcaption>FIGURE 5.5 – Modèle RDF-S de descriptions canoniques</figcaption></figure>
En utilisant différentes ontologies apparaissent les interrelations quand ces ontologies sont utilisées pour découvrir et/ou composer des services. Il en résulte une architecture conceptuelle intégrant les théories et leurs interliens. A cet égard, le Web Sémantique est l'exemple le plus illustratif. L'alignement d'ontologies est un problème très complexe et il le serait plus dans le contexte bioinformatique dans lequel les ontologies ont une couverture sémantique réduite et présentent des incohérences dans leur structure et leur définition des entités, notamment parce qu'elles n'ont pas été fondées sur des principes ontologiques clairs. Nous pensons que l'alignement de ces ontologies sera d'autant plus compréhensible si les ontologies s'adossaient sur des ontologies fondationnelles. En effet, les ontologies fondationnelles ont pour objectif de faciliter et de favoriser l'interopérabilité entre des ontologies, de domaine ou d'application. Elles fournissent une axiomatisation logique rigoureuse explicitant les engagements ontologiques, rendant possible le raisonnement sur les entités et la mise en correspondance des ontologies. Ainsi, l'approche suivie pour la construction d'une méta-carte ontologique consiste à stratifier le niveau ontologique en différentes sous-ontologies situées à différents niveaux d'abstraction selon leur couverture, leur granularité sémantique et leur niveau de formalisation. Schématiquement, nous distinguons trois niveaux d'abstraction :

- Au niveau le plus abstrait, des ontologies fondationnelles telles que DOLCE, SUMO ou GFO apportent un ensemble de concepts et de relations abstraits censés permettre de structurer, par spécialisation, la conceptualisation de n'importe quel domaine;

- à un niveau médian, une méta-carte ontologique a pour objectif de représenter une sémantique partagée par le biais d'un ensemble de primitives conceptuelles reflétant un consensus local (régional) au niveau d'une communauté de pratique;

- Enfin, au niveau le plus spécifique, les primitives conceptuelles de la méta-carte sont à leur tour spécialisées pour définir des concepts plus concrets.

Le besoin d'un niveau médian est la conséquence du fait que les concepts apportés par une ontologie fondationnelle sont abstraits et ne sont pas directement instanciables. Cependant, les ontologies fondationnelles offrent des catégories de haut niveau permettant de catégoriser les concepts du domaine visé et de représenter formellement leur sémantique inhérente. En s'appuyant sur les travaux de recherche élaborés par [Isa05, Tem08, Cho09], notre choix s'est porté sur l'ontologie DOLCE. Cette décision est motivée par trois facteurs majeurs :

Le premier facteur est lié à l'axiomatisation de DOLCE qui est riche et bien documentée, ainsi que son fondement sur des principes de structuration explicites. De plus, elle est basée sur la méthodologie OntoClean [GW02, GW04], fournissant ainsi un guide précieux pour structurer des ontologies d'application, particulièrement en ce qui concerne les relations taxonomiques.

Le second argument en faveur de DOLCE est la disponibilité de nombreuses extensions sous forme d'ontologies noyaux de plusieurs domaines, qui ont considérablement servi à maintenir une structure et une méthodologie cohérentes dans la construction des ontologies.

Le troisième argument est lié aux principes de base retenus dans DOLCE, que nous considérons particulièrement pertinents dans le contexte de cette thèse. Le choix délibéré du "biais cognitif" (i.e. dépendant fortement des perceptions humaines et des conventions
sociales) peut s'avérer pertinent pour la modélisation d'artefacts humains, tels que les concepts mathématiques ou dans notre cas, les services en général et les services Web en particulier. Particulièrement, la distinction entre les "endurants" physiques et les "endurants" non physiques nous semble très importante dans le domaine biologique.

Tout d'abord, nous présentons notre cadre de référence DOLCE et ensuite la méta-
carte ontologique proposée au niveau ontologique du méta-framework BioMEd.

5.3.1 Le cadre de référence ontologique

DOLCE (*Descriptive Ontology for Linguistic and Cognitive Engineering*) fait partie
de la bibliothèque Wonder Web des ontologies fondationnelles (WFOL pour *WonderWeb
Foundational Ontologies Library*). DOLCE est proposée comme le premier module de ces
bibliothèques, servant de module de référence. Elle a été conçue pour permettre de com-
parer et rendre explicites les relations et les hypothèses fondamentales des futurs modules
de ces bibliothèques.

Comme son acronyme le reflète, DOLCE a un biais cognitif clair, dans le sens où elle
vise à appréhender les catégories ontologiques fondamentales du langage naturel et du bon
sens humain. DOLCE embrasse une approche descriptive multiplicative, et possède une
axiomatisation riche et rigoureuse. Tous les concepts de DOLCE sont considérés comme
des propriétés rigides, selon la méthodologie OntoClean qui souligne l'importance de se
concentrer d'abord sur ces propriétés [GW02, GW04]. DOLCE est une ontologie fonda-
tionnelle de "particuliers", dans le sens où son domaine du discours ne concerne que les
particuliers. Les universels sont uniquement utilisés pour organiser et classifier ces parti-
culiers, partitionné en quatre sous-domaines :

- Les Endurants sont des entités "endurantes dans le temps". Parmi les Endurants sont distingués les *Physical Objects* et les *Non-Physical Objects*, les premiers étant les seuls à posséder des qualités spatiales directes. Le domaine des Non-Physical Objects recouvre le domaine des entités sociales (ex. : la communauté des chercheurs en biologie moléculaire) et des entités cognitives parmi lesquelles figurent les Concepts (ex. : la notion d'ontologie) réifiant des types d'instances.

- Les Perdurants (PD) sont des entités se déroulant dans le temps. Parmi les Perdurants sont distingués, suivant un principe de cumulativité, les *Statives* et les *Events*. Parmi ces derniers, suivant qu'ils sont atomiques ou non, les *Achievements* sont distingués des *Accomplishments*.

- Endurants et Perdurants ont des *Qualities*, que nous percevons et/ou mesurons (ex. : poids, durée, couleur). Ces Qualities prennent une valeur (*Quale*) dans des régions de valeurs qui sont des *Abstracts*.

On notera également la principale relation entre Endurants et Perdurants, la relation
ternaire de participation temporelle signifiant que : *un endurant participe à un perdurant
durant un intervalle de temps*.
### 5.3.2 Ontologies et représentation des connaissances

Le problème posé par la représentation des connaissances est de formaliser dans un langage formel de représentation les connaissances permettant de traiter le problème à résoudre. Traditionnellement, un langage formel se définit à partir d'un alphabet comprenant des symboles de variables, des symboles de fonction et des symboles de prédicat et des symboles d'opérateurs logiques (connecteurs), des quantificateurs, etc. Ces symboles sont des primitives à partir desquelles toutes les formules bien formées du langage sont construites selon des règles de construction syntaxique définies par le langage lui-même. Cependant, il ne suffit pas de préciser comment construire les formules du langage, il faut en outre préciser quelle signification ou sémantique elles peuvent recevoir, pour leur associer des connaissances du domaine. C'est pourquoi un langage formel se doit d'être pourvu d'une sémantique formelle précisant quelles significations associer aux formules en fonction des significations des symboles qu'elles contiennent et de la manière dont ils sont assemblés. A ce point, il est nécessaire de distinguer les primitives logiques des primitives non logiques.

Si les primitives logiques ont leur sémantique spécifiée par le langage formel lui-même, c'est qu'ils possèdent une signification indépendante du domaine. C'est en quelque sorte une sémantique intégrée dans le langage formel. Par exemple, parmi les primitives logiques du langage OWL (Ontology Web Language) nous distinguons : *owl :class*, *owl :property*, *owl :allvaluesfrom*, *owl :maxcardinality*, etc. Par contre les primitives non logiques possèdent une signification dépendante du domaine : non spécifiée par le langage formel, elle doit être explicitement déterminée en fonction du domaine. Les primitives non logiques du domaine biologique incluent gène, protéine, métabolisme, structure tertiaire d'une protéine, domaine fonctionnel, etc.

C'est ainsi, la sémantique des connecteurs logiques et de la composition des symboles de fonction avec les symboles de variables est propre au langage formel et ne dépend pas de ce que les symboles représentent et donc du domaine concerné. Par exemple, la sémantique formelle associée au langage spécifie les tables de vérité des connecteurs une fois pour toutes. C'est dans ce sens, que nous adoptons la définition de B. Bachimont selon laquelle définir une ontologie pour la représentation des connaissances, c'est définir, pour un domaine et un problème donnés, la signature fonctionnelle et relationnelle d'un langage formel de représentation et la sémantique associée. Ce n'est qu'une fois l'ontologie définie qu'il est possible d'associer une sémantique dans le domaine aux constructions syntaxiques du langage. Il n'est possible de représenter des connaissances, c'est-à-dire d'exprimer dans un langage formel les connaissances du domaine, que si les formules et les primitives non logiques qu'elles contiennent sont pourvues d'une sémantique qui permette de savoir quelle connaissance est assumée par cette formule.

### 5.3.3 Le modèle conceptuel de BioMed

La conception de la méta-carte ontologique s'effectue selon les trois étapes suivantes : une première étape d'engagement sémantique permettant de définir une sémantique référentielle en fixant l'interprétation des termes (des unités linguistiques) ; une deuxième étape permet le passage au niveau formel et ce par le biais de l'engagement ontologique qui permet d'as-
socier à un concept sémantique une extension d'objets et enfin la troisième étape permet l'opérationnalisation de la méta-carte obtenue. Ainsi, La méta-carte sera constituée d'un ensemble de primitives sémantiques (conceptuelles) normalisées et formellement définies. Nous explicitons et illustrons par des exemples les trois étapes pré-citées.

### 5.3.3.1 L'engagement (la normalisation) sémantique

La première étape a pour objectif d'aboutir à un consensus sémantique portant sur la signification (interprétation) des termes (unités linguistiques, labels) utilisés dans le domaine pour dénoter les concepts. Dans cette étape, il s'agit de recenser les concepts clés du domaine visé et leurs différentes connotations. En effet, dans la modélisation ontologique, on cherche à construire des primitives conceptuelles dont le sens ne dépend pas des autres primitives et ne dépendent pas du contexte. La détermination de signifiés non contextuels correspond à la phase de la normalisation sémantique qui consiste à choisir parmi les signifiés possibles que peut recevoir une unité linguistique dans un contexte donné, celle qui doit être à chaque fois associée. Cela revient en fait à choisir un contexte de référence dans lequel les termes peuvent être interprétés sans ambiguïté. On retrouve ainsi les conditions d'une sémantique pour laquelle les unités signifient toujours la même chose quels que soient les énoncés qui les contiennent. Ce qui n'est donc pas vrai d'un point de vue linguistique doit être imposé par la normalisation sémantique qui porte sur le choix d'un contexte de référence, celui de la tâche ou du problème qui motive l'élaboration d'une représentation formelle des connaissances. Le point de vue de la tâche permet au modélisateur de fixer quelle doit être la signification de l'unité linguistique considérée. Ainsi, il est nécessaire de normaliser les significations des concepts pour ne retenir, pour chacun d'eux, qu'une seule signification, i.e., qu'une seule interprétation possible dans un monde possible. C'est ainsi que l'engagement sémantique vise à résoudre les problèmes de conceptualisation liés à la polysémie lexicale dans le sens où un terme possède plusieurs interprétations selon le contexte d'usage. Nous illustrons la polysémie lexicale dans l'exemple 1.

**Exemple 2** Le concept gène a été perçu de différents points de vue (polysémie lexicale) :

1. Un gène est un fragment d'ADN (aspect structurale) comprenant une partie promotrice suivie d'une alternance de régions d'exons (séquences codantes) et d'introns (séquences non codantes) comme le modélise l'ontologie Sequence Ontology;

2. Un gène est composé des acides nucléotidiques : Adénine, Cytosine, Guanine et Thymine (composition biochimique);

3. Un gène possède une fonction biologique induite par la protéine (ou les protéines qu'ils encodent) comme le modélisent l'ontologie Gene Ontology;

4. Un gène est localisé sur un chromosome.

À la fin de l'étape de l'engagement sémantique, nous obtenons un ensemble de primitives conceptuelles valable dans la seule région du monde modélisée où les concepts retenus correspondent bien à ceux de l'ontologie qui sont par définition décontextualisées. Ainsi, le sens d'un libellé est principalement défini selon deux types de sémantiques :
- Une sémantique référentielle qui établit le lien entre l'intension et l'extension d'un concept impliquant notamment des relations d'hyperonymie/hyponymie et d'holonymie/méronymie;

- sémantique différentielle qui associe à chaque unité linguistique les unités voisines (celles qui sont utilisées en même temps qu'elle dans les contextes d'usage) pour la définir par les identités et différences qu'elle entretient avec ses voisines au niveau extensionnel.

**Exemple 3** *En l'occurrence, les ADN (DNA) et les ARN (RNA) sont des acides nucléiques composé de nucléotides comprenant trois types de molécules (sémantique référentielle):*

*Nucleotide hasComponent (Heterocyclic Base AND Phosphate AND 5-Carbon Sugar)*

Les ADN et les ARN se distinguent par la nature du sucre contenu dans leurs nucléotides. Au niveau de l'ADN, le sucre (5-carbon sugar) est le désoxyribose alors qu'au niveau de l'ARN, il s'agit du ribosome (sémantique différentielle).

Ainsi, la sémantique différentielle permet de décrire les unités entre elles par les identités qui les unissent et les différences qui les distinguent. Toutes les unités se déterminent à partir d'une unité générique ultime, une unité racine, à laquelle elles appartiennent toutes. Par ailleurs, toutes les unités se déterminent d'une part par l'unité générique à laquelle elles appartiennent et d'autre part par les différences qui les distinguent. Cela signifie que le réseau des unités est un réseau d'héritage de propriétés où les unités filles héritent des sèmes d'une unité générique mère. Enfin, l'engagement sémantique dégage une ontologie (ici, une méta-carte ontologique) valable seulement localement (régionalement) dans le cadre d'un domaine et d'une tâche.

### 5.3.3.2 L'engagement ontologique

Cette étape correspond à la définition d'une sémantique formelle. La sémantique formelle ne considère plus des notions sémantiques (concepts sémantiques) mais des extensions, c'est-à-dire l'ensemble des objets qui vérifient des propriétés définies en intension dans l'étape précédente, propriétés ayant une définition formelle à ce niveau. En effet, les concepts sémantiques s'inter-définissent par identités et différences. L'identité correspond au fait qu'une notion est comprise dans une autre : l'insuline est une protéine ayant une activité hormonale (fonction biologique), de ce fait, elle est une hormone. Les concepts hormone et protéine ne sont pas disjoints (au niveau extensionnel), l'insuline hérite les caractéristiques de protéine (macromolécule) et celle d'hormone (activité hormonale). Cela implique que l'on retrouve dans les relations unissant les concepts formels les relations d'héritage des concepts sémantiques, mais nécessairement pas les exclusions. La structure des concepts formels n'est plus obligatoirement un arbre, mais plus généralement une structure de treillis. Cela se comprend d'ailleurs facilement pour la raison suivante : si la sémantique des concepts est référentielle, les relations entre les concepts sont des relations entre ensemble. La structure des concepts formels doit correspondre à la structure algébrique des ensembles, c'est-à-dire un treillis. La formalisation des relations se définit
<figure><img src="image_47.png" /><figcaption>FIGURE 5.6 – La méta-carte ontologique</figcaption></figure>

alors facilement : une relation se définit comme un sous-ensemble du produit cartésien des extensions des concepts composant sa signature.

L'engagement ontologique élaboré pour la conception de la méta-carte émane du sou-
bassement la théorie de l'ontologie fondationnelle DOLCE qui nous permet de qualifier la
nature intrinsèque des concepts modélisés en les rattachant à des méta-catégories.

## 5.4 Annotations sémantiques pour la sémantisation de SW

L'enrichissement sémantique de descriptions de services Web a pour objectif de faciliter
la découverte des services pertinents (en réponse à un besoin utilisateur) et l'explicitation
de leurs paramètres (fonctionnels) et de leurs profils d'usage. Deux étapes primordiales
de cet enrichissement sémantique sont la définition d'un modèle (sémantique) de des-
cription de services Web et l'annotation sémantique proprement dite. La définition d'un
modèle de description, tel que le modèle d'unification proposé dans la section 2, fournit
les primitives conceptuelles (nommées descriptives au niveau du modèle d'unification) per-
mettant de représenter abstraitement un service Web. L'annotation sémantique consiste
à instancier les primitives conceptuelles du modèle unifié de descriptions en termes de
concepts, relations et instances définis formellement au niveau de la méta-carte ontolo-
gique. Nous nommons l'artéfact résultant du processus d'annotation sémantique, dans
le contexte des services Web, une *description sémantisée*. En l'occurrence, le terme
courant en littérature est celui de *description sémantique* reflète plutôt le modèle de des-
cription qui a pour objectif de capturer les éléments ou attributs décrivant la sémantique d'un service tels que ceux de sa signature fonctionnelle, sa catégorie, ou son domaine.

Nous explicitons brièvement dans cette section le *quoi* et le *comment* du processus d'annotation sémantique en général et celui de l'annotation sémantique de SW en particulier. Nous présentons quelques définitions de base portant sur l'annotation sémantique. L'annotation sémantique est définie par [KPT+04] comme *la génération de métadonnées spécifiques et d'un schéma d'utilisation, ayant pour but de rendre possible de nouvelles méthodes d'accès à l'information et d'améliorer les méthodes existantes*. Il s'agit d'assigner à des entités dans un texte (dans le cas d'un ressource textuelle) un lien vers leur description sémantique. Cette définition est selon nous incomplète puisqu'elle omet de préciser que ces métadonnées sont générées sur la base d'une ontologie du domaine si on parle précisément d'annotation sémantique. Ainsi, Florence Amardeilh définit l'annotation sémantique comme *une représentation formelle d'un contenu, exprimée à l'aide de concepts, relations et instances décrits dans une ontologie*, et liée à la ressource originelle [ALM05]. L'aspect formel sous entend que les annotations sont formalisées dans un langage formel pour être exploitées par des agents logiciels.

Enfin, Jérôme Euzenat distingue le processus d'annotation de l'artéfact résultant du processus d'annotation. Il introduit une terminologie relative à l'annotation sémantique de documents. Les définitions qui suivent sont extraites de la référence [Euz05] qui définit le processus d'annotation comme étant le processus permettant de rattacher du sens à un ensemble de symboles (texte, image, vidéo) grâce à un ensemble d'assertions. Une assertion peut être *générique* ou *individuelle*, elle est générique si elle s'applique à plusieurs individus et individuelle si elle s'applique à un individu particulier dans un domaine d'interprétation. Un *schéma* est un ensemble d'assertions génériques qui décrit des entités génériques pour exprimer le contenu. Une *description* est un ensemble d'assertions individuelles. La *connaissance de contexte* est un ensemble d'assertions qui peuvent être schématiques ou descriptives. Une ontologie est un ensemble d'assertions qui décrit les concepts impliqués dans le domaine. L'ontologie étant de la connaissance commune utilisée pour comprendre le contenu, elle fait évidemment partie de la connaissance de contexte. Cependant, Euzenat distingue l'ontologie, composée en partie de connaissance générique, et le reste de la connaissance de contexte qui contient exclusivement des descriptions individuelles. Le contenu d'un document est le sens du document envisagé sous l'angle le plus général. Lorsque le contenu est exprimé dans un langage formel et attaché au document, il est appelé **annotation**.

Dans le contexte de notre travail, nous nommons schéma d'annotation un ensemble d'assertions génériques décrivant les propriétés sémantiques d'un service Web. En l'occurrence, le modèle RDF-S de descriptions canoniques de SW présenté en section 2 est un exemple de schéma d'annotation. Ainsi, l'annotation sémantique de services Web permet de décrire le lien entre les primitives d'un schéma d'annotation et un ensemble de connaissances formalisées dans une ontologie. Le résultat du processus d'annotation sémantique est une description sémantisée d'un SW comportant un ensemble d'assertions qui expriment **la sémantique explicite et formelle du service**. En d'autres termes, si $O$ est une ontologie, $\mathcal{K}$ l'ensemble des connaissances du contexte, $D$ est la description sémantisée du service, $\mathcal{I}_S$ est la sémantique d'un service $S$ et $\models$ est la conséquence logique, alors
$$ \mathcal{O} \cup \mathcal{K} \cup \mathcal{D} \models \mathcal{I}_S. $$

Cette sémantique est explicite si elle est exprimée par le biais d'un ensemble d'assertions dans un langage déclaratif. Elle est formelle si elle est exprimée sur la base d'un schéma d'annotation. Il est important de disposer d'annotations formelles pour pourvoir les réutiliser dans des mécanismes inférentiels. Au niveau du méta-framework BIOMED, le schéma d'annotation est formalisé par le modèle RDF-S de la description unifiée de SW. Sur la base de ce schéma d'annotation, les descriptions sémantisées sont réifiées en un ensemble de triplets RDF, constituant un graphe que nous nommons *graphe de services annotés*.

**Définition 2 (Graphe de services annotés)** *Un graphe de services est un graphe orienté biparti $G=(V,E)$ tel que les noeuds dans $V$ sont soit des services soit des concepts ontologiques. Les arcs dans $E$ désignent les relations entre les services et les concepts ontologiques, tels que, si $C$ est les hyper-concepts de la méta-carte ontologique et $S$ est un service alors :*

- $(S, \text{hasInputType}, C)$ indique que $S$ a pour entrée un paramètre de type sémantique le concept $C$,

- $(S, \text{hasOutput}, C)$ indique que $S$ a pour sortie un paramètre de type sémantique le concept $C$.

Un exemple de graphe de services annotés est illustré dans la figure 5.7. Enfin, la qualité et la pertinence des annotations dépendent étroitement de la couverture sémantique et de la pertinence de l'ontologie choisie pour annoter le service. Dans notre cas, la couverture sémantique est assez large dès lors que la méta-carte ontologique offre une pertinence élevée et révèle les différentes facettes tant au niveau intensionnel qu'extensionnel.

## 5.5 Une sémantique axiomatique comme fondement du modèle inférentiel

Le raisonnement déductif est une composante essentielle du modèle conceptuel du méta-framework BIOMED. Le moteur de raisonnement proposé permet d'effectuer différents types de raisonnement dans l'objectif de raisonner à la fois sur les connaissances ontologiques de la méta-carte ontologique, les connaissances descriptives et les annotations sémantiques. A chaque typologie de raisonnement, nous définissons un ensemble d'axiomes constituant dans leur ensemble la sémantique axiomatique sur laquelle repose le moteur de raisonnement, nous distinguons les axiomes suivants :

- **Axiomes ontologiques** : les axiomes du niveau ontologique permettent de raisonner au niveau ontologique afin d'inférer de nouvelles connaissances en exploitant par exemple certains propriétés algébriques des relations telles que la transitivité, ou déterminer la clôture transitive d'un concept à partir d'une hiérarchie de concepts.

- **Axiomes des services** : ces axiomes permettent de déduire de nouvelles propriétés des services Web en exploitant à la fois les connaissances du domaine (explicites à partir de la méta-carte ontologique ou implicites sous forme d'axiomes ontologiques) et les annotations sémantiques des services Web. Ces axiomes vont enrichir la couverture sémantique des propriétés des services (par exemple, on associera à un service
<figure><img src="image_48.png" /><figcaption>FIGURE 5.7 – Graphe de services annotés</figcaption></figure>

qui accepte en entrée un paramètre de type concept C₁, une annotation comprenant l'arbre ontologique du concept C₁ obtenu par calcul de la clôture transitive du concept).

- **Axiomes des instances** définissent des axiomes pour le concept spécifique/général auquel une instance appartient.

Selon que les annotations sémantiques sont créées en termes d'instances de concepts, de concepts, ou de relations sémantiques nous définissons cinq groupes d'axiomes relatifs à la *relaxation assertionnelle*, la *relaxation par généralisation et la relaxation par spécialisation*, la *relaxation fonctionnelle et la relaxation fonctionnelle inverse*. Cette axiomatique permet d'élargir (enrichir) les descriptions sémantisées de SW en inférant de nouvelles propriétés sémantiques d'où le terme de relaxation. Nous explicitons dans ce qui suit chaque groupes d'axiomes en les illustrant par des exemples.

### 5.5.1 La relaxation assertionnelle (au niveau des instances)

La relaxation assertionnelle permet de déduire le type sémantique pouvant être accepté en entrée ou renvoyé comme sortie par un service Web. Cette relaxation peut être effectuée aux différents niveaux de stratification du méta-framework BIOMED, en effet, les applications existants entre le niveau ressource comprenant les instances des services, le niveau description comprenant les descriptions unifiées et le niveau ontologique comprenant les types sémantiques (les hyper-concepts et leurs instances) du domaine. Cette relaxation assertionnelle est réifiée par les deux axiomes suivants :

$$ \begin{array}{l} [(I, rdf : type, c_1), (s, rdf : type, isService), (s, hasInput, I)] \\ [(s, InputType, c_1)] \end{array} \quad (A1) $$
<figure><img src="image_49.png" /><figcaption>FIGURE 5.8 – Arbre Ontologique du concept *Genomic Sequence*</figcaption></figure>

$$ \frac{[(O,df :type,c_2),(s,df :type,isService),(s,hasOutput,O)]}{[(s,OutputType,c_2)]} \quad (A2) $$

L'axiome (A1) permet de déduire le type sémantique accepté en entrée par un service alors que l'axiome (A2) permet de déduire le type sémantique d'une sortie d'un service.

### 5.5.2 La relaxation par généralisation et par spécialisation

La relaxation par spécialisation et par généralisation permet de déduire de nouvelles propriétés sémantiques du service en exploitant les connaissances d'un arbre ontologique défini comme suit.

**Définition 3 (Arbre Ontologique)** *Un arbre ontologique est un ensemble de concepts A muni d'une relation d'ordre partiel ≤ vérifiant les trois propriétés suivantes :*

- $\forall c \in A, c \leq c$ (réflexivité)

- $\forall c_1, c_2, c_3 \in A, \text{ si } c_1 \leq c_2 \text{ et } c_2 \leq c_3 \text{ alors } c_1 \leq c_3 \text{ (transitivité)}$

- $\forall c_1, c_2 \in A, \text{ si } c_1 \leq c_2 \text{ et } c_2 \leq c_1 \text{ alors } c_1 = c_2 \text{ (antisymétrie)}$

En d'autre termes, un arbre ontologique permet de catégoriser les concepts d'un domaine sous forme d'une hiérarchie de concepts. La figure 5.8 illustre l'arbre ontologique de l'hyper-concept *séquence génomique* de la méta-carte ontologique.

Le principe de la relaxation par spécialisation est défini par la règle d'annotation suivante : si *S* est un service Web qui accepte en entrée un paramètre I annoté sémantiquement par un concept *C*, alors I sera annoté par tous les sous-concepts subsumant *C* dans l'arbre ontologique. La relaxation par spécialisation permet d'étendre la portée sémantique d'une propriété d'un service pour inclure tous les concepts spécifiques d'un super-concept annotant un paramètre. La relaxation par spécialisation est définie formellement par les deux axiomes suivants :
$$ \frac{[(s, rdf : type, isService), (s, hasInput, I), (I, rdf : type, c), (c_1, rdfs : subClassOf, c)]}{[(s, InputType, c_1)]} \quad (A3) $$

$$ \frac{[(s, rdf : type, isService), (s, hasOutput, O), (O, rdf : type, c), (c_2, rdfs : subClassOf, c)]}{[(s, OutputType, c_2)]} \quad (A4) $$

Le haut d'un axiome définit les conditions devant être vérifiées (prémisses) et le bas de l'axiome définit la conclusion ou l'annotation à réaliser.

D'un autre côté, la relaxation par généralisation se base sur le constat suivant : si *S* est un service Web qui retourne en sortie un paramètre *O* annoté sémantiquement par un concept *C*, alors *O* sera annoté sémantiquement par tous les super-concepts de *C* dans l'arbre ontologique. Les axiomes (A5) et (A6) permettent de calculer la fermeture transitive d'un concept et d'inférer de nouvelles annotations sémantiques enrichissant la description sémantisée d'un service Web. La relaxation par généralisation est décrite formellement en utilisant les axiomes suivants :

$$ \frac{[(s, rdf : type, isService), (s, hasInput, I), (I, rdf : type, c_1), (c_1, rdfs : subClassOf, c)]}{[(s, InputType, c)]} \quad (A5) $$

$$ \frac{[(s, rdf : type, isService), (s, hasOutput, O), (O, rdf : type, c_2), (c_2, rdfs : subClassOf, c)]}{[(s, OutputType, c)]} \quad (A6) $$

Nous illustrons dans l'exemple suivant les relaxations par généralisation et par spécialisation.

**Exemple 4** *Blastn* est un service Web pour l'alignement multiple de séquences nucléotidiques. L'alignement multiple de séquences permet de retrouver des régions de similarité entre des séquences biologiques. Le graphe de service annoté est illustré par la figure 5.9 montrant les annotations sémantiques du service *Blastn*.

Une relaxation par spécialisation permet d'élargir la portée sémantique du paramètre en entrée "Nucleotide sequence" en annotant le paramètre $I_1$ par les sous-concepts DNA sequence, RNA et mRNA. D'un autre côté, une relaxation par généralisation permet d'annoter le paramètre en sortie $O_1$ avec les super-concepts du concept "Nucleotide sequence" à savoir le concept "Genomic Sequence".

### 5.5.3 La relaxation fonctionnelle

La relaxation fonctionnelle permet de déduire de nouvelles annotations sémantiques en se basant les propriétés fonctionnelles d'un concept. Une propriété fonctionnelle se définit comme suit : si *P* est une propriété fonctionnelle entre deux concepts $C_1$ et $C_2$, alors pour chaque instance du concept $C_1$, il existe une et une seule instance de $C_2$. Ainsi, l'axiome de la relaxation fonctionnelle se définit comme suit : si *S* est un service qui accepte en entrée un paramètre *I* annoté sémantiquement par un concept $C_1$ alors le paramètre *I* sera annoté par tous les concepts reliés à $C_1$ par une propriété fonctionnelle *P*. Les axiomes (A7) et (A8) formalisent la relaxation fonctionnelle :

$$ \frac{[(s, rdf : type, isService), (s, hasInput, I), (I, rdf : type, c_1), (c_1, p, c_2), (p, rdf : type, isFunctionalProperty)]}{[(s, hasInputType, c_2)]} \quad (A5) $$

$$ \frac{[(s, rdf : type, isService), (s, hasOutput, O), (O, rdf : type, c_1), (c_1, p, c_2), (p, rdf : type, isFunctionalProperty)]}{[(s, hasOutputType, c_2)]} \quad (A6) $$
<figure><img src="image_50.png" /><figcaption>FIGURE 5.9 – Graphe annoté du service Blastn</figcaption></figure>

**Exemple 5** WSInterProScan<sup>16</sup> est un service Web prend en entrée une séquence protéique (AminoAcid Sequence) pour retourner l'identifiant de la protéine correspondante à la séquence en entrée, ainsi que la fonction de la protéine et sa structure tertiaire (3D structure). Les annotations sémantiques du service WSInterProScan est illustré par le graphe de la figure 5.10. Au niveau ontologique, La fonction d'une protéine renseigne sur le domaine fonctionnel de la protéine et la famille de la protéine, d'où les propriétés fonctionnelles "hasFunctionalDomain" entre "Protein Function" et "Functional Domain" et "hasProteinFamily" entre "Protein Function" et "Protein Family". La relaxation fonctionnelle permet d'annoter respectivement le paramètre de sortie Output<sub>1</sub> par les concepts "Functional Domain" et "Protein Family". par toutes les propriétés fonctionnelles d'un concept annotant.

### 5.5.4 La relaxation fonctionnelle inverse

D'un autre côté, une propriété inversement fonctionnelle est définie comme suit : si P est une propriété inversement fonctionnelle entre deux concepts $C_1$ et $C_2$ alors pour chaque instance de $C_2$, il correspondra une et une seule instance de $C_2$. Par conséquent, l'axiome de la relaxation fonctionnelle inverse est définie comme suit : si S est un service qui accepte en entrée un concept $C_2$ alors S accepte en entrée tous les concepts reliés par une relation inversement fonctionnelle à $C_2$ (ce qui correspond au domaine des relations dont le co-domaine est le concept $C_2$). La relaxation inversement fonctionnelle s'applique aussi bien aux entrées et aux sorties d'un service et se réifie en les axiomes (A7) et (A8) formalisant ainsi la relaxation inversement fonctionnelle.

[(s, rdf :type, isService), (s, hasInput, I), (I, rdf :type, c2), (c1, p, c2), (p, rdf :type, isInverseFunctionalProperty)]]
[(s, hasInputType, c1)]

<footnote n="16">16. Le service Web WSInterproscan permet d'interroger la base InterPro. Cette base de données fédère un grand nombre de banques de données sur les domaines protéiques (PROSITE, PRINTS, Pfam, ProDom, SMART et d'autres).</footnote>
<figure><img src="image_51.png" /><figcaption>FIGURE 5.10 – Illustration de la relaxation fonctionnelle</figcaption></figure>

(A7)

[(s,rdf:type,isService),(s,hasOutput,O),(O,rdf:type,c2),(c1,p,c2),(p,rdf:type,isInverseFunctionalProperty)]]
[(s,hasOutputType,c1)]

(A8)

**Exemple 6** Pour prédire la fonction d'un gène, les protocoles scientifiques en bioinformatique se basent sur la séquence ADN correspondant au gène. "hasDNASquence" est une relation fonctionnelle inverse entre un gène et sa séquence ADN, ceci signifie qu'à une instance de séquence ADN correspond un et un seul gène. Ainsi, un service qui accepte une séquence ADN, acceptera le gène relié (par relaxation fonctionnelle inverse), de plus, toutes les propriétés fonctionnelles du gène telles que son nom (GeneName), son symbole (GeneSymbol) ou son identifiant (GeneID) seront déduits comme de nouvelles propriétés sémantiques du service comme illustrées dans la figure 5.11.

## 5.6 Conclusion

Nous avons proposé dans ce chapitre un méta-framework stratifié pour la médiation de services Web sémantiquement hétérogènes dénommé BIOMED. Ce méta-framework intègre un modèle unifié pour la description et l'annotation sémantique de SW. Le modèle d'alignement sémantique de BIOMED permet de normaliser la sémantique des services Web par le biais d'un ensemble de primitives canoniques descriptives. Il s'agit à ce niveau de réconcilier les descriptions émanant des trois principaux frameworks de descriptions sémantiques de SW ; à savoir OWL-S, WSMO, SAWSDL. La construction d'un référentiel de descriptions sémantisées de services Web est réalisée sur la base de ce modèle d'alignement. Les descriptions sont annotées sémantiquement en se basant sur la méta-carte
<figure><img src="image_52.png" /><figcaption>FIGURE 5.11 – Illustration de la relaxation fonctionnelle et fonctionnelle inverse</figcaption></figure>

ontologique du domaine bioinformatique. Le modèle inférentiel de BIOMED se base sur une sémantique axiomatique formalisant une large typologie de raisonnement permettant d'inférer de nouvelles annotations sémantiques élargissant ainsi la couverture sémantique des descriptions sémantisées contenues dans le référentiel. Nous montrons dans le chapitre suivant comment les techniques de raisonnement déductif permettent une médiation sémantique entre les descriptions sémantisées des services et la sémantique des besoins en services des utilisateurs exprimée par le biais de requêtes.
# Chapitre 6

## La découverte de Services Web
dans BioMed

### Sommaire

<table><tr><td>6.1</td><td>Introduction</td><td>131</td></tr><tr><td>6.2</td><td>Formalisation du problème de découverte</td><td>132</td></tr><tr><td>6.2.1</td><td>Appariement fonctionnel</td><td>133</td></tr><tr><td>6.2.2</td><td>Appariement fonctionnel et non fonctionnel</td><td>137</td></tr><tr><td>6.3</td><td>La solution BioMed pour la découverte de services Web</td><td>138</td></tr><tr><td>6.3.1</td><td>Phase de l'appariement fonctionnel</td><td>139</td></tr><tr><td>6.3.2</td><td>Phase de sélection et de classement des services</td><td>140</td></tr><tr><td>6.4</td><td>Opérationnalisation du méta-framework BioMed</td><td>143</td></tr><tr><td>6.4.1</td><td>Fondements de base</td><td>143</td></tr><tr><td>6.4.2</td><td>Le méta-service Web déductif dans BIOMED</td><td>145</td></tr><tr><td>6.4.3</td><td>Sémantique formelle</td><td>147</td></tr><tr><td>6.5</td><td>Découverte de services Web en bioinformatique</td><td>148</td></tr><tr><td>6.5.1</td><td>Le projet BioMoby</td><td>148</td></tr><tr><td>6.5.2</td><td>Un scénario de découverte dans BioMoby</td><td>150</td></tr><tr><td>6.6</td><td>Expérimentations et Résultats</td><td>153</td></tr><tr><td>6.6.1</td><td>Catalogue de ressources</td><td>154</td></tr><tr><td>6.6.2</td><td>L'implémentation du méta-service Web déductif dans BIOMED</td><td>157</td></tr><tr><td>6.6.3</td><td>Résultats des expérimentations</td><td>163</td></tr><tr><td>6.7</td><td>Conclusion</td><td>167</td></tr></table>

### 6.1 Introduction

Nous présentons dans ce chapitre une approche originale pour la découverte de services Web combinant à la fois les propriétés fonctionnelles et non fonctionnelles comme critères de sélection. Cette phase de sélection repose sur le moteur inférentiel conçu dans le cadre du méta-framework BIOMED et qui permet de déduire l'ensemble des solutions qui satisfont fonctionnellement et non fonctionnellement les contraintes d'une requête de découverte.
Le modèle inférentiel repose sur la sémantique axiomatique présentée dans le chapitre 5 permettant d’élargir la couverture sémantique des annotations des services et ce par biais de techniques de relaxation permettent de déduire un appariement vérifiant *au mieux* les contraintes d’une requête de découverte. Une phase de classement (ranking) complète la phase de sélection des solutions possibles et permet de classer l’espace des solutions possibles sur la base de leurs propriétés non fonctionnelles. Les expérimentations menées dans le cadre de l’évaluation de l’approche de découverte montre l’impact des techniques de raisonnement sur la taille de l’espace des solutions possibles d’une requête et l’intérêt des techniques de ranking pour déceler les meilleures solutions de l’espace en termes de propriétés QdS [GVRA09, GVRA10].

L’opérationnalisation du méta-framewok BIOMED se base sur l’implémentation d’un méta-service Web déductif qui repose sur une base déductive de données [ALVR07, ALV08a]. Nous explicitons cette opérationnalisation dans la section 6.4.

## 6.2 Formalisation du problème de découverte

Cette section a pour objectif de définir formellement le problème de découverte de services tel qu’abordé dans l’approche BIOMED. Nous nous reposons sur des descriptions unifiées de services Web afin de proposer une approche de découverte adaptée aux trois frameworks de descriptions sémantiques ciblés. Nous rappelons qu’une solution de découverte se base sur un algorithme de "matchmaking" pour déduire un appariement sémantique entre une description de service Web et une requête de découverte exprimant le besoin de l’utilisateur en termes de propriétés fonctionnelles des services. Les critères de sélection de services retenus dans l’approche de découverte proposée sont sur le plan fonctionnel, les entrées, les sorties et au plan non fonctionnel, les critères QdS. Les entrées et les sorties sont annotées sémantiquement et les propriétés non fonctionnelles décrivent la qualité du service. La définition 4 explicite la description canonique d’un service Web adoptée au niveau de l’approche de découverte proposée.

**Définition 4 (Description canonique d'un service Web)** *Un service Web S est défini par un tuplet S=<func, QdS> où func désigne un ensemble de propriétés fonctionnelles, en l'occurrence, l'ensemble des entrées typées I nécessaires à l'exécution du service S et l'ensemble des sorties typées O retournées par S après exécution, et QdS est un ensemble de propriétés non fonctionnelles, chaque propriété QdS est représentée par un triplet (p,v,u), où p est un paramètre QdS, v est la valeur du paramètre QdS et u est l'unité dans laquelle la valeur du paramètre est exprimée.*

La signature fonctionnelle du service notée *func* est annotée sémantiquement en termes de concepts ontologiques. L’exemple 7 illustre la description canonique d’un service Web.

**Exemple 7** *Soit $S_1$ un service Web qui reçoit en entrée un paramètre nommé $E_0$ désignant l'identifiant d'un gène (GeneID) et qui retourne en sortie trois paramètres $E_1, E_2$ et $E_3$ annotés respectivement avec les concepts AAsequence (séquence aminoacide), ProteinID (identifiant d'une proteine) et 3Dstructure (Structure 3D d'une protéine). Ce service permet aux scientifiques d'explorer l'ensemble des protéines (identifiants, séquences et struc-
tures tertiaires) codées par un gène dont l'identifiant est spécifié en entrée. Les descriptions QdS du service S₁ sont les suivantes : un temps de réponse de 4 secondes, une Disponibilité de 98 pour cent et un Débit de données de 15 invocations par seconde.

Alors, la description canonique du service S₁=(func, QdS) est définie comme suit :

- func = (I= {E₀: GeneID}, O={E₁: ASequence, E₂: ProteinID, E₃: 3Dstructure})

- QdS = { (temps de réponse, 4, secondes), (Disponibilité, 98, pourcentage), (Débit de données, 15, invocations par seconde)}

Les descriptions canoniques sont déclarées en RDF-S au niveau du référentiel de services construit dans le contexte du méta-framework BIOMED. chaque service Web est déclaré par un triplet RDF-S comme suit (s, **rdf**:type, isService). Les paramètres en entrée et en sortie sont déclarés respectivement par les triplets (s,hasInput, i) et (s, hasOutput, o), leurs types sémantiques sont déclarés par (p, **rdf**:type, c) où p est un paramètre en entrée ou en sortie d'un service s. p peut être une collection de concepts, nous disposons de trois types de collections, (p, **rdf**:bag, c), (p, **rdf**:alt, c) et (p, **rdf**:seq, c). Les prédicats (s, **hasQdSParameter**, p), (s, **hasValue**, v) et (p, **hasUnit**, u) permettent de définir respectivement un paramètre QdS d'un service, sa valeur et son unité de mesure. Le graphe RDF de services Web sémantisés est défini comme suit.

**Définition 5 (Graphe RDF de services Web sémantisés)** Soit *U* un ensemble d'URI (de services Web, de paramètres, de concepts ontologiques, de propriétés ontologiques, de types de données et d'ontologies), *L* un ensemble infini de littéraux, Un graphe RDF de services Web sémantisés est constitué d'un ensemble de triplets RDF (*v*₁, *v*₂, *v*₃) ∈ *U* × (*rdf*:type, *rdf*:bag, *rdf*:seq, *rdf*:alt, *hasInput*, *hasOutput*, *hasQdSParameter*, *hasValue*, *hasUnit*) × (*U* ∪ *L*) tel que *v*₁ est le sujet, *v*₂ est le prédicat et *v*₃ est l'objet. Un graphe de services Web sémantisés ne comprend pas de noeud blanc.

Une requête de découverte permet d'exprimer le besoin de l'utilisateur, elle permet de spécifier un ensemble de contraintes fonctionnelles et/ou non fonctionnelles. La requête de découverte spécifie un ensemble de contraintes fonctionnelles en restreignant les types sémantiques acceptés et retournés par un service ou un ensemble de contraintes non fonctionnelles portant sur les valeurs des paramètres QdS. Nous explicitons dans ce qui suit les notions d'appariement fonctionnel et d'appariement non fonctionnel d'une requête de découverte.

### 6.2.1 Appariement fonctionnel

La définition 6 définit la notion de requête de découverte de sorte qu'elle exprime uniquement des contraintes fonctionnelles restreignant les types sémantiques en entrée ou en sortie.

**Définition 6 (Requête de découverte)** Une requête de découverte est un tuplet $Q=\langle I, -O \rangle$, où *I* est un ensemble de paramètres typés désignant les entrées de la requête *Q* et *O* est un ensemble de paramètres typés désignant les sorties de la requête *Q*.

Il est primordial de disposer d'un langage de requête destiné à interroger les graphes RDF(S) et qui pourrait être adopté pour exprimer les requêtes de découverte dans le méta-
framework BIOMED. Plusieurs langages d'interrogation de ressources RDF(S) existent tels que le langage RQL (RDF Query Language) [KAC+02], le langage TRIPLE<fnref n="1" /> [SD02], ou plus récemment le langage SPARQL<fnref n="2" /> (SPARQL Protocol and RDF Query Language) [PS08]. Nous adoptons ce dernier pour exprimer les requêtes de découverte dans BIOMED, la raison de ce choix est qu'il est le langage de référence pour l'interrogation des annotations RDF selon la recommandation du W3C<fnref n="3" />.

Les requêtes SPARQL sont définies à partir de patrons de graphes qui sont fondamentalement des graphes RDF avec des variables (noeuds blancs).

**Exemple 8** *Un exemple de requête de découverte exprimée en SPARQL se présente comme suit :*

```sparql
PREFIX rdf : <http://www.w3.org/1999/02/22-rdf-syntax-ns>
SELECT DISTINCT fiS
WHERE {
    fiS      rdf:type      isService
    fiS      hasInput      p1
    p1      rdf:type GeneId
    fiS      hasOutput     o1
    o1      rdf:type ProteinId
    fiS      hasOutput     o2
    o2      rdf:type Sequence
}
```

La sémantique formelle des graphes RDF est décrite en détails dans [Hay04] et est traitée de la perspective de la logique du premier ordre en se basant sur la notion de modèle, d'interprétation et d'implication logique (Théorie des modèles<fnref n="4" />). Un graphe RDF est un ensemble de triplets (s,p,o), tel que s est un sujet, p est un prédicat (propriété qui met en évidence une relation entre s et o) et o est un objet. Nous définissons l'interprétation

<footnote n="1">1. http://triple.semanticweb.org/</footnote>

<footnote n="2">2. http://www.w3.org/TR/rdf-sparql-query/</footnote>

<footnote n="3">3. http://www.w3.org/</footnote>

<footnote n="4">4. La théorie des modèles est une branche de la logique mathématique. Elle a été formulée d'une façon complète et cohérente d'abord par Alfred Tarski qui a appelé sa théorie la sémantique du calcul des prédicats et cela pour deux raisons : (1) Elle donne une définition de la vérité et de la conséquence logique, indépendante de ce que donnent les démonstrations en logique, (2) Elle donne une réponse partielle à la question de la signification du langage, parce que les mots ont du sens s'ils permettent de faire des phrases vraies dans un monde possible. Selon Tarski, Un modèle sert d'abord de structure pour valider une théorie logique ou mathématique. Il existe deux notions de « consistance » ou de « cohérence » d'une théorie, a priori différentes, mais équivalentes en logique classique du premier ordre, d'après le théorème de complétude de Gödel : (a) un notion sémantique : une théorie est satisfaisable s'il existe un modèle dans lequel elle est vraie, (b) une notion syntaxique : une théorie est non contradictoire si on ne peut en dériver à la fois une formule et sa négation. Un système de déduction est dit « correct » si l'existence d'un modèle donne la certitude de travailler sur une théorie qui ne débouchera pas sur une contradiction. L'intérêt est que pour montrer la cohérence ou consistance d'une théorie, il est souvent plus facile d'en déterminer un modèle que de montrer qu'on ne peut dériver de contradiction.</footnote>

<footnote>La sémantique formelle du langage RDF basée sur la théorie des modèles rend possible la définition de règles d'inférences valides. Une autre façon de définir la sémantique du langage RDF est de donner une traduction de la syntaxe RDF vers une logique formelle liée à une théorie des modèles. Cette approche dénommée « sémantique axiomatique » a été suggérée dans cette thèse.</footnote>
<figure><img src="image_53.png" /><figcaption>FIGURE 6.1 – Exemples de graphes de requête et de service</figcaption></figure>

Il d'un graphe RDF de services Web sémantisés consiste en : (1) un ensemble non vide *Res* d'URI de services Web, de variables (paramètres), de concepts ontologiques, de propriétés et d'ontologies, (2) un sous ensemble de littéraux *Lit* ⊆ *Res* (3) un ensemble de propriétés *Prop* ⊆ *Res* × *Res* et une fonction de mapping $U \to Res \times Prop$ et $L \to Lit$.

La définition de l'appariement fonctionnel se base sur un matching structurel exact entre le graphe d'une requête et celui d'un service en se basant sur la notion d'isomorphisme de graphes.

**Définition 7 (Appariement fonctionnel exact)** *Etant donnés les graphes RDF d'une requête de découverte Q et d'un service Web S, notés respectivement $G_Q$ et $G_S$, Il existe un appariement fonctionnel exact entre G et S si et seulement si il existe un isomorphisme entre le graphe de la requête $G_Q$ et le graphe du service $G_S$. Un isomorphisme est une application bijective $\pi$ des termes de $G_Q$ dans les termes de $G_S$ de sorte que pour chaque triplet $(s,p,o) \in G_Q$, il existe $(\pi(s), p, \pi(o))$ qui est un triplet de $G_S$.*

Un isomorphisme implique l'existence d'un appariement exact entre le graphe de la requête et le graphe d'un service au niveau structurel. Ainsi, le service $S_1$ dont le graphe RDF est illustré dans la figure 6.1.(a) n'est pas une solution exacte de la requête Q dont le graphe RDF est illustré par la figure 6.1.(b).

Cependant, il existe un appariement approximatif entre le service $S_1$ et la requête Q puisque le service Web accepte les mêmes entrées (compatibilité des types sémantiques) que la requête Q et retourne en sortie l'identifiant d'une protéine (ProteinID) et l'instance d'une séquence d'acides aminés notée *AAsequence* qui est un sous-type de *séquence*.

L'intérêt des techniques de raisonnement présentées dans cette thèse et plus précisément au niveau du modèle inférentiel du méta-framework BIOMED est de reposer sur le principe de la relaxation de paramètres afin de déduire différents degrés d'approximation d'appariement fonctionnel entre une requête de découverte et une description sémantisée d'un SW en reposant sur l'ensemble des connaissances ontologiques fourni par la méta-carte ontologique. En l'occurrence, une relaxation par généralisation permet de mettre en évidence la sémantique référentielle d'un ensemble d'objet en leur associant une intension, ainsi, il est possible de déduire que le service $S_1$ a comme sortie le concept "séquence" comme le montre la figure 6.2.

Nous distinguons cinq niveaux d'appariement fonctionnel entre une requête de découverte et une description sémantisée d'un service Web : le *matching exact*, le *matching fonction-
<figure><img src="image_54.png" /><figcaption>FIGURE 6.2 – Graphe annoté du service $S_1$</figcaption></figure>

nel, le matching en plugin et le matching en subsomption que nous définissons comme suit :

1. **Le matching exact** entre une requête de découverte $Q$ et un service $S$, noté $Q \equiv S$, illustre le cas où pour chaque entrée typée $i$ de l'ensemble $I_Q$ des entrées d'une requête $Q$ (respectivement une sortie typée $o$ de l'ensemble $O_Q$ des sorties), il correspond une entrée $i'$ (respectivement une sortie $o'$) du service $S$ ayant le même type sémantique que $i$, i.e., le même concept ontologique annotant. Formellement, le matching exact est défini comme suit :

$$ \forall (i:C) \in I_Q, \exists (i':C') \in I_S \text{ tel que } (i:C) \text{ sémantiquement équivalent à } (i':C') $$

2. **Le matching fonctionnel** entre une requête de découverte $Q$ et un service $S$, noté $Q \Rightarrow S$, illustre le cas où pour chaque entrée typée $i$ de l'ensemble $I_Q$ des entrées (respectivement une sortie typée $o$ de l'ensemble $O_Q$ des sorties) d'une requête $Q$, il correspond une entrée $i'$ (respectivement une sortie $o'$) du service $S$ qui soit :

- de même type sémantique que le concept annotant $i$ (respectivement $o$),

- ou de type sémantique une propriété fonctionnelle du concept annotant $i$ (respectivement $o$),

- ou de type sémantique une propriété fonctionnelle inverse du concept annotant $i$ (respectivement $o$),

3. **Le matching en plugin** entre une requête $Q$ et un service $S$, noté $Q \subseteq S$, illustre le cas où :

- pour chaque entrée typée $i$ de l'ensemble des entrées $I_Q$ d'une requête $Q$, il correspond une entrée $i'$ du service $S$ qui soit de même type sémantique que le concept annotant $i$ ou un sous-concept du concept annotant $i$, et

- pour chaque sortie typée $o$ dans l'ensemble des sorties $O_Q$ d'une requête $Q$, il correspond une sortie $o'$ du service $S$ qui soit de type sémantique que le concept annotant $o$ ou un super concept du concept annotant $o$.

4. **Le matching en subsomption** entre une requête $Q$ et un service $S$, noté $S \subseteq Q$, correspond au cas où :
- pour chaque entrée typée *i* de l'ensemble des entrées *I*<sub>Q</sub> d'une requête *Q*, il correspond une entrée *o* du service *S* qui soit de type sémantique que le concept annotant de *i* ou un super concept du concept annotant de *i*.

- pour chaque sortie typée *o* dans l'ensemble des sorties *O*<sub>Q</sub> d'une requête *Q*, il correspond une sortie *o'* du service *S* qui soit de type sémantique que le concept annotant de *o* un sous-concept du concept annotant de *o*.

Nous illustrons les trois types de matching approximatif (plug-in, subsomption, fonctionnel) avec l'exemple suivant.

**Exemple 9** Nous reprenons la requête de l'exemple 8 exprimant le besoin d'un scientifique de services lui permettant d'étudier les protéines codées par le gène TP53. La spécification de la requête est la suivante :

- $Q=(I,O)$ tel que $I = \{ i_1 : geneId \}$ et $O=\{ o_1 : ProteinId, o_2 : AAsequence \}$
  Soit $S_1, S_2$ et $S_3$ trois SW ayant respectivement les descriptions fonctionnelles $F_{S_1}, F_{S_2}, F_{S_3}$ déclarées comme suit :

- $Func_{S_1}=(I,O)$ tel que $I=\{E_0:geneId\}$ et $O=\{E_1:ProteinId, E_2:Sequence\}$,

- $Func_{S_2}=(I,O)$ tel que $I=\{E_0:DNAsequence\}$ et $O=\{E_1:ProteinId, E_2:AASequence\}$,

- $Func_{S_3}=(I,O)$ tel que $I=\{E_0:geneId\}$ et $O=\{E_1:AAsequence\}$.

Aucun service ne matche exactement avec la requête *Q*. Cependant, les matchings approximatifs suivants peuvent être déduits par relaxation des propriétés fonctionnelles des services $S_1, S_2$ et $S_3$ :

- Un matching en plugin entre *Q* et $S_1$, $Q \subseteq S_1$,

- Un matching fonctionnel entre *Q* et $S_2$, $Q \Rightarrow S_2$,

- Un matching en subsomption entre *Q* et $S_3$, $S_3 \Rightarrow Q$.

Nous retenons seulement les services $S_1$ et $S_2$ comme solutions possibles à la requête *Q* étant donné que $S_3$ satisfait partiellement la requête en renvoyant seulement un sous-ensemble de l'ensemble des sorties *Q*.

Un mécanisme de classement de l'ensemble des solutions d'une requête se basera sur
le type d'appariement établi et se définit comme suit :

exact > fonctionnel > plug-in > subsomption > échec

En pratique, le nombre de services pouvant satisfaire fonctionnellement une requête de
découverte peut se révéler très élevé. Les techniques de relaxation permettent d'élargir la
couverture sémantique des descriptions sémantisées des services induisant l'élargissement
de l'espace de solutions d'une requête de découverte. Les contraintes non fonctionnelles
permettent d'exprimer les attentes des utilisateurs en termes de qualité de service. L'ex-
tension de la requête de découverte par l'ajout de contraintes non fonctionnelles aura pour
impact de restraindre l'espace de solutions aux services satisfaisant à la fois les contraintes
fonctionnelles et non fonctionnelles.

### 6.2.2 Appariement fonctionnel et non fonctionnel

La requête de découverte étendue contenant à la fois des contraintes fonctionnelles et non fonctionnelles, est définie comme suit :
**Définition 8 (Requête de découverte étendue)** Une requête de découverte étendue $Q$ est définie par un tuplet $Q=<F,NF>$, où $F$ est l'ensemble de propriétés fonctionnelles et $NF$ est un ensemble de propriétés non fonctionnelles.

- Les propriétés fonctionnelles $F$ d'une requête $Q$ sont représentées par un tuplet $(I,O)$ où $I$ est un ensemble de paramètres typéss désignant les entrées de la requête $Q$ et $O$ est un ensemble de paramètres typés désignant les sorties de la requête $Q$.

- Les propriétés non fonctionnelles $NF$ d'une requête $Q$ sont représentées par 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$.

**Exemple 10** Nous proposons d'étendre la requête de découverte exprimée dans l'exemple 8 par un ensemble de contraintes non fonctionnelles exprimées comme suit : un temps de réponse inférieur ou égal à 5 secondes et une disponibilité plus grande ou égale à 95. La requête $Q$ est exprimée comme suit :

$$Q=(F,NF)$$

- $F=(I,O)$

- $I = \{ E_0 : GeneID \}$

- $O = \{ E_1 : sequence, E_2 : ProteinID \}$

- $NF = \{(P,C,V,U)\}$

- $NF = \{(\text{temps de réponse}, \leq, 5, \text{secondes}), (\text{Disponibilité}, \geq, 95, \text{pourcentage})\}$

Un service $S=(func, QdS)$ satisfait les contraintes non fonctionnelles d'une requête $Q=(F,NF)$ ssi pour chaque quadruplet $(P,C,U,V) \in NF$, il existe un triplet $(p,v,u) \in QdS$, tels que :

- $P$ et $p$ sont équivalents

- l'expression $v C V$ est valide avec $C \in \{> , <, \geq, \leq, =, \neq\}$

- les deux paramètres sont exprimés dans la même unité.

Une nouvelle approche de découverte proposée dans le cadre du méta-framework BIO-MED est présentée dans la section suivante permettant de sélectionner les services qui satisfont fonctionnellement et non fonctionnellement une requête de découverte.

## 6.3 La solution BioMed pour la découverte de services Web

La solution de découverte proposée permet de déduire un espace de solutions $\mathcal{S}$ pour une requête $Q$ comprenant l'ensemble les meilleurs services qui satisfont fonctionnellement et non fonctionnellement une requête de découverte et cela en deux phases : une **phase d'appariement fonctionnel** permettant de sélectionner les solutions exactes et approchées d'une requête de découverte et une **phase de sélection et de classement** pour classer l'ensemble des solutions sélectionnées en termes de l'ensemble des attributs $QdS$ spécifié dans la requête étendue. La phase d'appariement fonctionnel repose sur le
moteur de raisonnement qui exploite les descriptions sémantisées des services Web et l'ensemble des connaissances ontologiques du domaine pour inférer les propriétés implicites des services en se basant sur la sémantique axiomatique (inférentielle). Une phase de classement est proposée afin de retourner à l'utilisateur l'ensemble des k-meilleurs services en termes de leurs propriétés non fonctionnelles.

La section 6.3.1 présente les techniques de relaxation proposées dans la phase de raisonnement. Ensuite, la section 6.3.2 explicite l'approche de classement proposée.

### 6.3.1 Phase de l'appariement fonctionnel

Au niveau de la phase de raisonnement, les différents types de relaxation exécutés sont les suivants :

- La relaxation par spécialisation des paramètres en entrée d'un service S est définie comme suit :

- ♣ si *I* est un paramètre en entrée d'un service *S* et *I* est annoté par un concept *C* alors *I* est annoté par tous les sous-concepts de *C*.

- La relaxation par généralisation des paramètres en sortie d'un service est définie comme suit :

- ♣ si *O* est un paramètre en sortie d'un service *S* et *O* est annoté avec le concept *C* alors *O* est annoté par tous les super-concepts de *C*.

- La relaxation fonctionnelle et fonctionnelle inverse des paramètres en entrée d'un service sont définies comme suit :

- ♣ si *I* est un paramètre en entrée d'un service *S* et *I* est annoté par le concept $C_1$ et *P* est une propriété fonctionnelle de $C_1$ vers $C_2$ alors *I* est annoté par le concept $C_2$

- ♣ si *I* est un paramètre en entrée d'un service *S* et *I* est annoté par le concept $C_2$ et *P* est une propriété fonctionnelle inverse de $C_1$ vers $C_2$ alors *I* est annoté par le concept $C_1$.

- La relaxation fonctionnelle et fonctionnelle inverse des paramètres en sortie d'un service sont définies comme suit :

- ♣ si *O* est un paramètre en sortie d'un service *S* et *O* est annoté par un concept C1 et *P* est une propriété fonctionnelle de C1 vers C2 alors *O* est annoté par le concept C2

- ♣ si *O* est un paramètre en sortie d'un service *S* et *O* est annoté avec le concept C2 et *P* est une propriété fonctionnelle inverse de C1 vers C2 alors *O* est annoté par le concept C1.

L'algorithme suivant permet de déduire l'ensemble des solutions satisfaisant une requête au niveau fonctionnel. La phase de raisonnement est opérationnalisée par un méta-service Web déductif modélisé par deux composantes : une composante extensionnelle comprenant l'ensemble des connaissances ontologiques et les annotations sémantiques des services Web et une composante intensionnelle comprenant un ensemble de règles logiques implémentant l'algorithme de l'appariement fonctionnel.
**Algorithme : Appariement fonctionnel**

**Inputs** : $G_O$ : graphe ontologique,

$G_S$ : graphe de services,

A : l'ensemble des axiomes du modèle inférentiel,

$G_Q$ : graphe de requête de découverte

**Outputs** : S : ensemble de services

**Début**

– Générer le graphe minimal $G'_S$ par application de chaque axiome $A_i \in A$ au
graphe initial $G_S$ de sorte que :

pour chaque $s \in G_S$ faire

pour chaque $c \in Input(s)$ faire

$Input(s) \leftarrow Input(s) \cup subclasses(c, G_O) \cup functionalProperties(c, G_O) \cup inverseFunctionalProperties(c, G_O)$

fin Pour

pour chaque $c' \in Output(s)$ faire

$Output(s) \leftarrow Output(s) \cup superclasses(c', G_O) \cup functionalProperties(c', G_O) \cup inverseFunctionalProperties(c', G_O)$

fin Pour

fin pour

– Normaliser $G'_S$ en fusionnant tous les noeuds se référant à un même concepts.

– Calculer les homophismes entre Q et $G'_S$ ainsi obtenu.

**Fin**

### 6.3.2 Phase de sélection et de classement des services

La seconde phase de l'approche de découverte proposée consiste à classer l'ensemble
des services retenus par le moteur inférentiel et vérifiant les contraintes non fonctionnelles
de la requête étendue afin de retourner à l'utilisateur les meilleurs services en terme de
qualité de service. La solution proposée combine deux approches connues dans le contexte
des bases des données à savoir celle se basant sur l'opérateur de *skyline* [BKS01] et celle
de l'algorithme *top-k* [IBS08]. Pour introduire l'approche de classement proposée, nous
introduisons deux notions fondamentales à la compréhension de l'approche à savoir la
dominance et le *skyline*.

**Définition 9 (Dominance)** Etant donné un ensemble points S dans un espace multidimensionnel D de dimension n, un tuple $t_i$ domine un tuple $t_j$ dans D, si et seulement si $\forall d_x \in D, t_i(d_x) \ge t_j(d_x)$ et $\exists d_y \in D, t_i(d_y) > t_j(d_y)$.

**Définition 10 (Skyline)** Etant donné un ensemble points S dans un espace multidimensionnel D de dimension n, un tuple $t_i$ est un objet skyline dans D si et seulement si aucun autre tuple $\forall t_j (\ne t_i) \in S$ ne domine $t_i$ dans D. SKY(D) désigne l'ensemble des objets skyline de S dans D.

Ainsi, la technique de skyline consiste en la constitution d'un ensemble de dominance *a la Pareto* (Voir Annexe B). Dans le contexte de la découverte de services, un skyline de
<table><caption>TABLE 6.1 – Skyline de trois services</caption><thead><tr><td>Service</td><td>Disponibilité</td><td>Temps de réponse</td></tr></thead><tbody><tr><td>NCBIBlastService</td><td>98 %</td><td>4 secondes</td></tr><tr><td>runBlat</td><td>97 %</td><td>2 secondes</td></tr><tr><td>WSFASTA</td><td>96 %</td><td>1 seconde</td></tr></tbody></table>

services désigne l'ensemble des services qui ne sont dominés par aucun autre service dans un espace multidimensionnel comprenant tous les critères QdS d'une requête de découverte; ces critères sont supposés être de même poids.

**Exemple 11** Supposons qu'un scientifique recherche un service pour l'alignement multiple de séquences nucléotidiques vérifiant les contraintes non fonctionnelles suivantes : Disponibilité au minimum supérieur à 98 % et un temps de réponse inférieur à 5 secondes. Les trois services Web NCBIBlastService<fnref n="5" />, runBlat<fnref n="6" /> et WSFASTA<fnref n="7" /> sont des outils d'alignement multiple de séquences et donc satisfont fonctionnellement et non fonctionnellement le besoin de l'utilisateur comme le montre leurs descriptions non fonctionnelles décrites dans la Table

De plus, nous supposons que l'utilisateur est intéressé par le meilleur service entre les trois services sélectionnés. Du point de vue disponibilité, runBlat est meilleur WSFASTA et NCBIBlastService sont meilleurs que runBlat. Cependant, en considérant la propriété temps de réponse, WSFATA est meilleur que runBlat et runBlat est meilleur que NCBIBlastService. Etant donné qu'aucun service n'est meilleur que tous les autres pour toutes les propriétés non fonctionnelles, ces services sont incomparables, i.e., ils forment ainsi un skyline de services induits par les propriétés QdS considérés dans la requête de découverte. Il est important de disposer de techniques de classement pour choisir les meilleurs solutions d'un skyline, sachant que ce genre de problème toutes les propriétés QdS sont d'égale importance.

La composante de découverte dans BIOMED repose sur l'algorithme WTKSF (Web Top-k Skyline Frequency) proposé dans [GVRA09, GVRA10]. Cet algorithme permet d'identifier les top-k services d'un skyline en calculant le nombre de fois qu'un service apparaît dans les différents sous-espaces dans l'espace multi-dimensionnel induits par les n dimensions. Etant donné un espace multi-dimensionnel de dimension n, il existe $2^n$-1 sous espaces non vides de propriétés QdS (critères). En l'occurrence, étant donné un critère multidimensionnel comprenant quatre paramètres QdS : la disponibilité (noté A pour Availability), le débit (noté T pour Throughput), la fiabilité (noté R pour reliability) et la documentation (noté D). L'ensemble des sous-espaces de l'espace multi-dimensionnel forment la structure d'un treillis comme l'illustre la figure 6.3.

La métrique de fréquence skyline permettant de mesurer la qualité d'un service est définie comme suit : SFM (Skyline Frequency Metric) = $\frac{\sum_{q_i \in m} s(q_i)}{2^d - 1}$. La métrique SFM permet de calculer le nombre d'occurrences du service dans les sous-espaces de l'espace multi-

<footnote n="5">5. http://www.ebi.ac.uk/Tools/webservices/wsdl/WSNCBIBlast.wsdlfikjkj</footnote>

<footnote n="6">6. http://biomoby.org/services/wsdl/inb.bsc.es/runBlat</footnote>

<footnote n="7">7. http://www.ebi.ac.uk/Tools/webservices/wsdl/WSFasta.wsdl</footnote>
<figure><img src="image_55.png" /><figcaption>FIGURE 6.3 – Ensemble des sous-espaces multi-dimensionnels</figcaption></figure>

dimensionnel. L’algorithme proposé détermine les top-k services satisfaisant une requête de découverte étendue ayant les meilleures valeurs dans la plus grande partie des critères QdS de la requête. L’algorithme WTKSF, est une version améliorée de l’algorithme TKSI (Top-k SkyIndex) présenté dans [GV09]. WTKSF diffère de l’algorithme TKSI du fait qu’il repose sur une heuristique pour guider la recherche des meilleurs services. WTKSF présuppose que l’ensemble des services sélectionnés est trié dans d listes ordonnées, d étant le nombre de paramètre QdS d’une requête étendue. L’algorithme se base sur l’heuristique suivante pour décider si un service $S_i$ est meilleur qu’un service $S_j$ :

- $S_i$ est un point extrême ayant les meilleures valeurs dans au minimum $\frac{d}{2}$ paramètres QdS de la requête. Un service est un point extrême dans une dimension $m$, s’il possède la meilleure valeur de cette dimension.

- Il n’existe pas de service $S_k$ meilleur que le service $S_i$ dans $(d-l)$ dimensions, où $l$ est le nombre de dimensions dans lesquelles $S_j$ est un point extrême.

- Il existe un service $S_l$ meilleur que le service $S_j$ dans $(d-l)$ dimensions, où $l$ est le nombre de dimensions dans lesquelles $S_i$ est un point extrême.

Dans le cas où les deux services ne vérifient pas l’heuristique proposée, l’algorithme WTKSF calcule la valeur de la métrique SFM pour les services $S_i$ et $S_j$ afin de décider lequel des deux services est meilleur. L’algorithme s’arrête quand $k$ services sont déterminés. Ainsi, le skyline des services est incrémentalement construit, et la métrique SFM est calculée seulement pour un nombre réduit de services.

Le problème de découverte des meilleurs services en terme de QdS est défini comme suit dans l’approche BIOMED :

**Définition 11 (Problème de découverte des Top-k Skyline Services)** *Etant donné une requête de découverte étendue $Q=(F,NF)$, un ensemble de services $SW = \{S_1, S_2, ..., S_n\}$ et la métrique de fréquence skyline SFM, le problème de découverte des top-k skyline services est de trouver l'ensemble $SW'$, tel que*

$$ - SW' \subseteq SW, $$
- Pour chaque service $s \in SW'$, s satisfait les contraintes fonctionnelles et non fonctionnelles de la requête $Q$,

- Il existe au plus *k* services dans *SW*'ayant les meilleures valeurs de la fonction *SFM*, ces *k* services existent dans le skyline induit par les propriétés non fonctionnelles

Nous proposons dans ce qui suit une opérationnalisation du méta-framework BIOMED comme méta-service Web déductif permettant de représenter à la fois la sémantique descriptive des services Web, la sémantique référentielle et différentielle explicitée par la méta-carte ontologique et la sémantique axiomatique émanant du modèle inférentiel.

# 6.4 Opérationnalisation du méta-framework BioMed

Dans cette section, nous présentons le cadre opérationnel du méta-framework BIOMED comme un méta-service Web déductif comprenant deux méta-composantes :

- Une méta-composante extensionnelle comprenant un ensemble de méta-prédicats extensionnels désignant un ensemble de primitives sémantiques de déclaration de connaissances,

- Une méta-composante intensionnelle comprenant un ensemble de méta-prédicats intensionnels désignant un ensemble d'axiomes.

## 6.4.1 Fondements de base

Nous considérons l'alphabet d'un langage logique sans symboles de fonctions composé de trois ensembles : VAR, CONST et PRED dénotant respectivement des ensembles de variables, de constantes et de prédicats. VAR, CONST et PRED sont de plus deux à deux disjoints et l'ensemble VAR est infini dénombrable, alors que les ensembles CONST et PRED sont finis. Un terme est défini comme étant une constante ou une variable. Un atome $p(t_1, ..., t_n)$ est formé par un symbole de prédicat $p$ d'arité $n$ et une liste d'arguments $(t_1, ..., t_n)$ où chaque $t_i$ $(1 \le i \le n)$ est un terme. Nous utilisons aussi la notation $p(\bar{t})$ pour représenter l'atome $p(t_1, ..., t_n)$. Un littéral est un atome $p(t_1, ..., t_n)$ (littéral positif) ou sa négation *not* $p(t_1, ..., t_n)$ (littéral négatif). Un littéral clos contient seulement des constantes parmi ses arguments. Un fait est un littéral positif clos.

Sur la base d'un tel langage logique, une théorie ontologique peut être exprimée pour décrire les connaissances spécifiques d'un domaine ainsi que l'ensemble des axiomes permettant d'inférer de nouvelles connaissances. Nous introduisons la définition d'une base de connaissances ontologiques.

**Définition 12 (Base de Connaissances Ontologiques)** *Une base de connaissances ontologiques KB d'une ontologie O est un tuple $KB = (\mathcal{F}, \mathcal{I})$, tel que $\mathcal{F}$ est un ensemble de faits représentant les connaissances explicites de l'ontologie à savoir les concepts, les propriétés des concepts, les relations sémantiques (taxonomiques ou non) entre concepts ainsi que les instances, et $\mathcal{I}$ est un ensemble d'axiomes permettant d'inférer de nouveaux faits.*

Nous nous sommes inspirés des travaux de [RRV08] formalisant les ontologies comme une base de données déductive [RU93] nommée par les auteurs *Deductive Ontology Data-
<table><caption>TABLE 6.2 – Méta-prédicats Extensionnels et Intensionnels du formalisme DOB</caption><thead><tr><th>PREDICATS EXTENSIONNELS</th><th>DESCRIPTION</th></tr></thead><tbody><tr><td>isOntology(0)</td><td>An ontology has an Uri 0</td></tr><tr><td>isImpOntology(01,02)</td><td>Ontology 01 imports ontology 02</td></tr><tr><td>isClass(C,0)</td><td>C is a class in ontology 0</td></tr><tr><td>isOProperty(P,D,R)</td><td>P is an object property with domain D and range R</td></tr><tr><td>isDProperty(P,D)</td><td>P is a data property with domain D</td></tr><tr><td>isTransitive(P)</td><td>P is a transitive property</td></tr><tr><td>isSymmetric(P)</td><td>P is a symmetric property</td></tr><tr><td>subClassOf(C1,C2)</td><td>C1 is subclass of C2</td></tr><tr><td>subPropertyOf(P1,P2)</td><td>P1 is subproperty of P2</td></tr><tr><td>AllValuesFrom(C,P,D)</td><td>C has property P with all values in D</td></tr><tr><td>maxCardinality(C,P,N)</td><td>C has property P with maximum cardinality N</td></tr><tr><td>isIndividual(I,C)</td><td>I is an individual belonging to class C</td></tr><tr><td>isStatement(I,P,J)</td><td>I is an individual that has property P with value J</td></tr><tr><th>PREDICATS INTENSIONNELS</th><th>DESCRIPTION</th></tr><tr><td>areSubClasses(C1,C2)</td><td>C1 are the direct and indirect subclasses of C2</td></tr><tr><td>areImpOntologies(01,02)</td><td>01 import the ontologies 02 directly and indirectly</td></tr><tr><td>areSubProperties(P1,P2)</td><td>P1 are the direct and indirect subproperties of P2</td></tr><tr><td>areClasses(C,0)</td><td>C are all the classes of an ontology and its imported ontologies 0</td></tr><tr><td>areStatements(S,P,O)</td><td>(S,P,O) are the statements for inverse, transitive or symmetric P</td></tr><tr><td>areIndividuals(I,C)</td><td>I are the individuals of a class and all of its direct and indirect superclasses C I are the individuals that participate in a property and belong to its domain or range C, or are values of a property with all values in C</td></tr></tbody></table>

base (DOB). Comme toute base déductive, une DOB comprend une base extensionnelle (EDB : extensional DataBase) et une base intensionnelle (IDB : Intensional DataBase). La base extensionnelle d'une DOB est conçue de sorte qu'elle comprend toutes les connaissances explicites d'une ontologie par le biais d'un ensemble de méta-prédicats extensionnels correspondant aux primitives de déclaration de connaissances dans un langage ontologique. La base intentionnelle correspond aux différents axiomes permettant de raisonner sur les connaissances de la base extensionnelle. Comme langage de représentation d'ontologies, les auteurs ont considéré le langage OWL (Ontology Web Language). La table 6.2 illustre la traduction d'un sous-ensemble des constructeurs du langage de définition d'ontologies OWL vers le formalisme DOB.

L'exemple 12 illustre la traduction d'un fragment de l'ontologie Galen<fnref n="8" /> en une DOB.

<footnote n="8">8. http://www.co-ode.org/galen/</footnote>
<table><caption>TABLE 6.3 – Fragment de l'ontologie GALEN traduite en DOB</caption><tr><td>isOntology('galen.owl')</td></tr><tr><td>isClass('factkb :Abdomen','galen.owl')</td></tr><tr><td>isClass('factkb :AbdominalAorta','galen.owl')</td></tr><tr><td>isFunctional('factkb :hasAbnormalityStatus')</td></tr><tr><td>isProperty('factkb :actsOn','Ontologies :galen.owl')</td></tr><tr><td>isTransitive('factkb :hasCause')</td></tr><tr><td>someValuesFrom('factkb :AdhesivePericarditis','factkb :hasOutcome','factkb :Adhesion')</td></tr><tr><td>subClassOf('factkb :AdductorMagnus','factkb :NAMEDMuscle')</td></tr><tr><td>subClassOf('factkb :AdductorTubercle','factkb :Eminence')</td></tr><tr><td>subPropertyOf('factkb :hasLayer','factkb :StructuralPartitiveAttribute')</td></tr><tr><td>subPropertyOf('factkb :hasLeftRightSelector','factkb :hasPositionalSelector')</td></tr></table>

**Exemple 12** Un fragment de l'ontologie Galen traduit en DOB est illustré dans la Table 6.3. Les méta-prédicats extensionnels sont les suivants : `isClass`, `isFunctional`, `isProperty`, `isTransitive`, `someValuesFrom`, `subclassOf`, `subpropertyOf`. Ces méta-prédicats extensionnels permettent de déclarer respectivement des concepts, des propriétés, des propriétés fonctionnelles, des propriétés transitives, des restrictions de valeurs, des sous-classes et des sous-propriétés.

Les prédicats intensionnels du formalisme DOB représentent l'ensemble des axiomes ontologiques du modèle inférentiel.

## 6.4.2 Le méta-service Web déductif dans BioMed

Nous nous proposons d'étendre le formalisme DOB pour représenter la dimension inférentielle du méta-framework BIOMED. La formalisation proposée s'inspire de la représentation classique des bases de connaissances où on regroupe un ensemble de faits du monde réel et un ensemble de règles ce qui nous permet de raisonner sur ces faits.

**Définition 13 (Méta-service Web Déductif)** Un méta-service Web déductif est un couple (EB,IB) comprenant :

- une base extensionnelle notée ESB (Extensional Service Base) composée d'un ensemble de méta-prédicats extensionnels EP permettent de représenter des descriptions sémantisées de SW et des connaissances ontologiques du domaine,

- une base intensionnelle notée ISB (Intensional Service Base) composée d'un ensemble de méta-prédicats intensionnels IP représentant l'ensemble des axiomes du modèle de raisonnement.

**Définition 14 (Méta-prédicat extensionnel)** Un méta-prédicat extensionnel de la forme $ep(t_1,...,t_n)$ est un littéral positif clos tel que $ep$ est le symbole du méta-prédicat extensionnel faisant référence à une primitive sémantique.

Les méta-prédicats extensionnels permettent d'exprimer la sémantique extensionnelle d'un service dans une forme déclarative. Nous distinguons deux types de méta-prédicats exten-
<table><caption>TABLE 6.4 – Méta-prédicats extensionnels du méta-service Web déductif BIOMED</caption><thead><tr><td>Méta-Prédicat Extensionnel</td><td>Description</td></tr></thead><tbody><tr><td>isService(S)</td><td>S est le nom du service Web</td></tr><tr><td>hasDescription(S,Desc)</td><td>Desc est la description du service S</td></tr><tr><td>hasInput(S,I)</td><td>le service S a comme entrée la variable I</td></tr><tr><td>hasOutput(S,O)</td><td>le service S a comme sortie la variable O</td></tr><tr><td>hasParameter(S,P)</td><td>le service S a comme paramètre la variable P</td></tr><tr><td>isTypeOf(X,C,O)</td><td>la variable X est de type le concept C de l'ontologie O</td></tr><tr><td>hasPrecondition(S,Pre)</td><td>Pre est une précondition du service S</td></tr><tr><td>hasEffect(S,Eff)</td><td>Eff est un effet du service S</td></tr><tr><td>hasQdSParameter(S,QdSName)</td><td>QdSName est un paramètre QdS décrivant le service S</td></tr><tr><td>hasQdSValue(S,QdSName,V)</td><td>le paramètre QdSName du service S possède la valeur V</td></tr><tr><td>isQdSParameter(QdSName)</td><td>QdSName est le nom d'un paramètre QdS</td></tr><tr><td>isQdSUnit(QdSName,U)</td><td>Le paramètre QdSName est exprimé dans l'unité U</td></tr></tbody></table>

sionnels : ceux qui représentent des primitives de représentation de connaissances d'un langage de définition d'ontologie tels que OWL ou pour notre cas RDF-S (Table 6.2) et ceux qui représentent des primitives descriptives pour la déclaration des propriétés sémantiques de services tels que ceux du notre modèle unifié de descriptions canonique présenté précédemment. La Table 6.4 illustre un ensemble de méta-prédicat pour expliciter la sémantique extensionnelle d'un service.

**Définition 15 (Méta-prédicat intensionnel)** *Un méta-prédicat intensionnel est défini par le biais d'une règle R de la forme : $H(\bar{X}) \leftarrow \exists \bar{Y} B(\bar{X}, \bar{Y})$, où H est la tête de R, B son corps, $\bar{X}$ et $\bar{Y}$ sont respectivement des variables distinctes et non distinctes. Le symbole H désigne le symbole du méta-prédicat intensionnel et B est la conjonction d'un nombre fini de littéraux positifs.*

Nous distinguons les méta-prédicats intensionnels qui correspondent aux axiomes du niveau ontologique (tels que l'axiome de la clôture transitive) des méta-prédicats intensionnels qui correspondent aux axiomes du niveau service. En l'occurrence, au niveau service, deux méta-prédicats intensionnels **InputType** et **OutputType** sont définis comme formalisation logique des axiomes du modèle inférentiel présenté dans le chapitre 5. La table 6.5 comprend la définition de ces deux méta-prédicats intensionnels.

**Définition 16 (Requête de découverte)** *Une requête de découverte (étendue ou non) s'exprime comme une requête conjonctive de la forme : $Q(\bar{X}) \leftarrow \exists \bar{Y} G(\bar{X}, \bar{Y})$, où $\bar{X}$ et $\bar{Y}$ sont respectivement des variables distinctes et non distinctes. $G(\bar{X}, \bar{Y})$ est la conjonction d'un ensemble de méta-prédicats extensionnels et/ou intensionnels.*

Selon que la requête exprime des contraintes fonctionnelles et/ou fonctionnelles, le corps de la requête conjonctive correspond à la conjonction des prédicats **InputType**, **OutputType**, **hasInput**, **hasOutput** pour exprimer des contraintes fonctionnelles et les prédicats **hasQoS** et **hasQoSValue** pour exprimer des contraintes non fonctionnelles.
<table><caption>TABLE 6.5 – Méta-Prédicats Intensionnels du Méta-Service Déductif BIOMED</caption><thead><tr><th colspan="2">Relaxation Assertionnelle</th></tr></thead><tbody><tr><td>InputType(S,C)</td><td>:-hasInput(S,X),isTypeOf(X,C,O).</td></tr><tr><td>OutputType(S,C)</td><td>:-hasOutput(S,X),isTypeOf(X,C,O).</td></tr><tr><td colspan="2">Relaxation par spécialisation</td></tr><tr><td>InputType(S,C)</td><td>:-hasInput(S,X),isTypeOf(X,C,O), areSubClasses(C<sub>1</sub>,C)</td></tr><tr><td colspan="2">Relaxation par généralisation</td></tr><tr><td>OutputType(S,C<sub>1</sub>)</td><td>:-hasOutput(S,X),isTypeOf(X,C,O),areSubClasses(C<sub>1</sub>,C).</td></tr><tr><td colspan="2">Relaxation fonctionnelle</td></tr><tr><td>InputType(S,C<sub>1</sub>)</td><td>:-hasInput(S,X),isTypeOf(X,C,O),isOProperty(P,C,C<sub>1</sub>), isFunctionalProperty(P).</td></tr><tr><td>OutputType(S,C<sub>1</sub>)</td><td>:-hasOutput(S,X),isTypeOf(X,C,O), isDProperty(C,C<sub>1</sub>), isFunctionalProperty(C<sub>1</sub>).</td></tr><tr><td colspan="2">Relaxation fonctionnelle Inverse</td></tr><tr><td>InputType(S,C<sub>1</sub>)</td><td>:-hasInput(S,X),isTypeOf(X,C,O),isOProperty(P,C,C<sub>1</sub>), isInverseFunctionalProperty(P).</td></tr><tr><td>OutputType(S,C<sub>1</sub>)</td><td>:-hasOutput(S,X),isTypeOf(X,C,O), isDProperty(C,C<sub>1</sub>), isFunctionalProperty(C<sub>1</sub>).</td></tr></tbody></table>

### 6.4.3 Sémantique formelle

La sémantique du méta-service Web déductif se base sur celle des bases de données déductives qui est définie comme suit.

**Définition 17 (Valuation)** *Etant donné un ensemble de variables V et un ensemble de constantes C, un mapping ou une valuation $\gamma$ est une fonction $\gamma: V \to C$.*

**Définition 18 (Instanciation valide)** *Etant donné un méta-service Web déductif S, un ensemble de constantes C dans S, un ensemble de variables V, un prédicat R, et une interprétation I de S qui correspond au modèle minimal [AHV95], une valuation $\gamma$ est une instanciation valide de R si et seulement si $\gamma(R)$ est évaluée à vrai dans I.*

**Définition 19 (Interpretation)** *Une Interpretation $I = (\Delta^I, \mathcal{P}^I, .^I)$ consiste en :*

- Un domaine d'interprétation non vide $\Delta^I$ correspond à l'union des ensemble de URIs d'ontologies, des classes, des services, des paramètres, des associations sémantiques, des types de données et des instances de classes. Ces ensembles sont disjoints deux à deux.

- L'ensemble d'interprétations $\mathcal{P}^I$ des prédicats extensionnels EP et des prédicats intensionnels IP.

- Une fonction d'interprétation $.^I$ qui fait correspondre à chaque prédicat n-aire $p^I \in \mathcal{P}^I$ une relation n-aire $\prod_{i=1}^n \Delta^I$.

Pour un prédicat extensionnel EP $p(t_1, ..., t_n)$ et une interprétation $I$, $I \models p(t_1, ..., t_n)$, i.e., $I$ satisfait $p$, si et seulement $(t_1, ..., t_n) \in p^I$.
Pour un prédicat intensionnel IP de la forme $R:H(\bar{X}) \leftarrow \exists \bar{Y} B(\bar{X}, \bar{Y})$ et une interprétation $I, I \models R$, i.e., $I$ satisfait $R$, si et seulement si, chaque fois que $I$ satisfait un prédicat appartenant au corps $B$, elle satisfait également la tête $H$.

**Définition 20 (Modèle)** *Etant donné un méta-service Web déductif S et une interprétation I, $I \models S$ si et seulement I modélise chaque prédicat EP et IP dans S.*

**Définition 21 (Satisfiabilité)** *Etant donné $q : Q(X) : -\exists Y G(X, Y)$ une requête de découverte, S un méta-service déductif, une instanciation de $X$, $\phi(X)$, satisfait $q$, si et seulement si il existe une instanciation de $Y$, $\phi(Y)$, telle que l'évaluation $G(X, Y)[\phi(X), \phi(Y)]$ appartient au modèle minimal de S.*

Fort de ces fondements théoriques, nous allons appliquer cet ensemble de concepts et l'axiomatique pour illustrer l'originalité du processus de découverte du méta-framework BIOMED.

## 6.5 Découverte de services Web en bioinformatique

Nous présentons dans cette section une étude de cas menée dans le cadre de cette thèse pour illustrer l'intérêt des contributions proposées. Nous nous intéressons au problème de découverte de services dans le domaine bioinformatique, au sein duquel, les services Web constituent des interfaces à des sources de données scientifiques hétérogènes et diverses. En effet, dans ce domaine, les expérimentations "in silico" adoptent de plus en plus la technologie des services Web pour implémenter des flots de données (workflows) répondant à une question scientifique complexe. Cependant, la découverte et la composition de services constitue un vrai challenge du fait que le nombre de ressources biologiques disponibles sur le Web a nettement augmenté ces dix dernières années. Comme cela a été mentionné au paravant dans ce mémoire, la Databases Issue de la revue Nucleic Acids Research (NAR) recense plus de 1230 ressources en 2010.

**Grimoires** et **BioMoby** central repository constituent tous les deux les plus importants annuaires de services Web sémantiques dans le domaine bioinformatique. Grimoires [MPP+04] est un annuaire de services Web basé sur la technologie UDDI et proposant des extensions permettant d'annoter sémantiquement les entités UDDI afin de faciliter la découverte de services. Selon [LA10], BioMoby est un annuaire de services Web dédié à la communauté bioinformatique comptant aujourd'hui 1673 services publiés par plus de 100 fournisseurs différents. Nous illustrons la problématique de découverte de service dans l'annuaire BioMoby par un ensemble de questions biologiques (requêtes de découverte). Nous étudions la pertinence des résultats du processus de découverte en comparant l'espace et la qualité des solutions obtenues avec et sans usage du raisonneur BioMed.

### 6.5.1 Le projet BioMoby

Initié en 2001, BioMoby [WL02] est un projet de recherche qui vise à proposer une plate-forme d'interopérabilité pour la publication et la découverte de services Web dans le domaine bioinformatique. Auparavant, la découverte de services Web était associée à
<figure><img src="image_56.png" /><figcaption>FIGURE 6.4 – Fragment de la hiérarchie *Service Type* dans BioMoby</figcaption></figure>

des systèmes de workflows tels que *Taverna* [OGA+06] ou *Kepler* [LAB+06]. Dans ce type de systèmes, les services Web sont découverts sur la base du format syntaxique de leurs entrées et sorties plutôt qu’en se basant sur la classe du service ou sa qualité.

Pour décrire la sémantique d'un service Web, BioMoby repose sur deux types d'hiérarchies :
une hiérarchie définissant les catégories de service (*Service Type Ontology*) et une hiérarchie
de types de données (*datatype ontology*). La première permet de spécifier la tâche du ser-
vice Web alors que la seconde permet de définir le type des entrées et des sorties d'un
service Web.

Ainsi, la publication de ressources dans BioMoby est réalisée en deux étapes :

- La première étape consiste à classer la ressource dans la hiérarchie de catégories de services Web définie par l'ontologie de type de service selon la tâche réalisée par le service (figure 6.4), Le fournisseur de service peut classer son service par rapport à une catégorie existante ou créer une nouvelle catégorie. Cinq catégories primitives sont définies pour classifier les ressources bioinformatiques : *Analyse* (Analysis), *Parsing*, *Enregistrement* (Registration), *Recherche* (Retrieval) et *Résolution* (resolution). L'analyse présenté dans [LA10] permet de révéler de nombreuses inconsistencies au niveau de l'ontologie de types de services à cause de la liberté donnée au fournisseur qui ont la possibilité de rajouter de nouvelles catégories. La figure 6.5 illustre un exemple d'inconsistance au niveau de la hiérarchie de types de services. Le service *NCBI_Blast* est créé comme une catégorie de services (sous-catégorie de la