Présentation



Les applications telles que les bibliothèques numériques, les systèmes de médiation ou les architectures à base de services Web produisent des masses de données générant un grand nombre de modèles destinés a être stockés dans l'objectif d'être accessibles pour des utilisateurs (clients) exprimant un besoin spécifique, traduit totalement ou en partie à l'aide d'une requête.

Ces modèles, décrivant des objets complexes tels que les documents, les processus métiers ou les ontologies relatives à des domaines de connaissances, sont de ce fait hétérogènes et riches du point de vue sémantique.

Actuellement, la plupart des applications utilisant de tels modèles, se basent sur une représentation sous forme de diagrammes ou graphes dont l'accès se décline par un processus d'appariement qui s'appuie uniquement sur des propriétés de structures (ou topologiques).

Or, la représentation sous forme de graphes ne peut capturer toute la sémantique du modèle qu'elle représente, qui est issue des applications métiers visées ; il est alors nécessaire d'y adjoindre une représentation complémentaire dans un autre formalisme, ce qui rend l'appariement complexe et imprécis.


Ce projet place l'appariement des graphes au centre de la problématique de l'accès aux modèles en se fixant trois objectifs majeurs.

- Le premier consiste à proposer des modèles qui exploitent de manière conjointe les différentes représentations des objets, par exemple topologiques et sémantiques ainsi que des outils d'appariement qui les supportent.

- Le second objectif porte sur le traitement de requêtes non exhaustives, n'exprimant qu'une partie des besoins de l'utilisateur puisque souvent, la caractérisation des modèles cibles ne lui est pas totalement connue. On s'oriente alors vers la mise en œuvre d'un appariement imprécis par opposition aux appariements exacts basés sur l'hypothèse d'exhaustivité de la requête de l'utilisateur.

- Enfin, notre troisième objectif concerne la réduction de la complexité des algorithmes d'appariement de graphes, qui sont NP-complet dans le cas général.


Notre souci est alors d'identifier les sous-classes de graphes correspondant aux modèles étudiés dans le cadre du projet et pour lesquels on appliquerait des algorithmes, déjà existants, de complexité polynomiale, ou alors de nouveaux algorithmes.

La confrontation entre la théorie des graphes et les applications permettrait ainsi d'une part, d'apporter de nouvelles solutions pour le problème d'appariement de graphes, et, d'autre part, de proposer des solutions efficaces pour le problème principal du projet, qui est en l'occurrence l'accès à des modèles complexes.