BASES DE DONNÉES

Responsable

• Dominique LAURENT Professeur

Membres de l'equipe

Chercheurs Permanents

• Tuyêt Trâm DANG NGOC Maître de Conférences
• Tao Yuan JEN ATER

Doctorants

• Yeow Wei CHOONG, partiellement financé par l'Ambassade de France en Malaisie
• Tianxiao LIU, financement CIFRE
• Virginie SANS, financement CIFRE
• Oumar SY, co-tutelle avec l'Université Gaston Berger (Saint-Louis, Sénégal), boursier de l'Alliance Française

• Entrepôts de données,
• Extraction de connaissances dans les bases de données,
• Données semi structurées (XML).

Extraction de règles d'association dans les bases de données

Ces recherches sont centrées sur l'extraction de règles d'association dans les bases de données relationnelles. La plupart des approches de découverte de règles d'association dans les bases de données traitent le problème pour une requête d'extraction donnée, alors que l'expérience montre qu'un ou plusieurs utilisateurs peuvent poser plusieurs requêtes sur la même base.

Dans ce cadre, nous avons introduit la notion de contexte d'extraction permettant l'expression des requêtes d'extraction et nous avons défini un ensemble d'opérateurs, basés sur l'algèbre relationnelle, permettant de combiner des contextes d'extraction entre eux. Nous avons de plus montré comment le stockage des réponses à des tâches déjà calculées permet d'optimiser les calculs des réponses à de nouvelles tâches d'extraction dont les contextes sont définis par combinaison des contextes. Ces travaux ont donné lieu au développement d'un prototype, appelé IncMiner, à partir duquel l'efficacité de notre approche a pu être mise en évidence.

Un autre aspect important de ces travaux concerne le stockage des réponses aux requêtes, nécessaire à notre approche itérative. Dans ce cadre, nous avons étendu la notion de représentation condensée (définie traditionnellement pour une requête) à un ensemble de requêtes conjonctives. Nos premiers résultats concernent le cas traditionnel d'extractions effectuées sur une table unique ; leur extension au cas général d'extractions effectuées à partir de plusieurs tables et leur intégration au prototype IncMiner sont en cours.

Ces travaux ont fait l'objet d'une thèse soutenue en décembre dernier à l'Université de Tours et sont actuellement poursuivis en collaboration avec le Laboratoire d'Informatique (LI) de Tours et le LRI de l'Université Paris 11.

Prédiction de valeurs manquantes dans les bases de données

La présence de valeurs manquantes dans les bases de données a suscité de nombreuses recherches dans le domaine de la découverte des connaissances, notamment en ce qui concerne la prédiction. Cependant, à notre connaissance, aucune de ces approches n'utilise les règles d'association pour la prédiction des valeurs manquantes. Nous montrons comment adapter les différents concepts et algorithmes par niveau liés aux règles d'association afin d'obtenir des règles fréquentes de confiance 1, permettant la prédiction de valeurs manquantes dans une table relationnelle. La particularité des règles extraites dans notre approche est que leurs conséquents se présentent sous la forme d'intervalles ou d'ensembles de valeurs, selon que le domaine de l'attribut sur lequel les valeurs sont prédites est soit continu soit discret. De plus, dans le cas d'un attribut continu, contrairement aux méthodes connues, notre approche ne nécessite pas de discrétiser le domaine de l'attribut avant le processus d'extraction.

Ces travaux font en partie l'objet de la thèse de Oumar Sy au LICP et sont menés en collaboration avec l'Université de Londres (Birkbeck College).

Extraction de requêtes fréquentes dans les schémas en étoile

De manière générale, l'extraction de toutes les requêtes fréquentes dans une base de données relationnelle est impossible à cause du nombre trop important de requêtes à tester. Nos travaux visent à montrer que si l'on se restreint à un type particulier de bases de bases de données, alors une telle extraction est réaliste, car elle peut être effectuée en utilisant des algorithmes par niveau du type Apriori, largement utilisés dans le domaine du data mining. Le type de bases de données que nous considérons dans ce travail correspond dans la pratique aux entrepôts de données. Un entrepôt de données peut être vu comme une base de données dont l'information, généralement volumineuse, est organisée de façon à en faciliter l'analyse. Cette organisation de l'information, connue sous le nom de schéma en étoile, permet la prise en compte de contraintes classiques de clés et clés étrangères dans le processus d'extraction des requêtes fréquentes à des fins d'optimisation.

Ces travaux font en partie l'objet de la thèse de Oumar Sy au LICP, sont menés en collaboration avec le LRI de l'Université Paris 11.

Représentations des données multi-dimensionnelles

Dans ce travail, nous étudions le problème de la représentation de données multi-dimensionnelles. Les techniques OLAP (On-Line Analytical Processing) permettent de présenter de telles données selon différentes dimensions et selon des degrés de granularité différents. Le concept de base est appelé cube de données (ou plus simplement cube). Un cube peut être vu comme un ensemble de cellules, chacune d'elle représentant une association entre un élément de chaque dimension (un tel élément est appelé membre), d'une part et un contenu de cellule (appelé mesure), d'autre part.

Il apparaît que les opérations de base liées à ce modèle permettent de manipuler les cubes essentiellement selon des critères définis sur les dimensions, et non sur les mesures. Or, en pratique, il peut également être souhaitable d'afficher (ou de représenter) un cube de données selon des critères définis sur les mesures. Nous étudions le problème du calcul des représentations dans deux directions : la première consiste à mettre en oeuvre des algorithmes permettant de tester l'existence de ces représentations et éventuellement de les calculer. Néanmoins, au vu de la complexité de tels algorithmes dans le cas général, nous étudions une approche approximative, en utilisant notamment des techniques d'algorithmes génétiques.

D'autre part, dans ce même domaine, nous nous intéressons au calcul de blocs homogènes (contenant la même valeur de mesure) dans une représentation donnée d'un cube donné. Pour des raisons d'efficacité, nous proposons une méthode approximative, selon laquelle les blocs sont presque homogènes, ce qui implique des recouvrements possibles entre différents blocs. Dans notre approche, le calcul des blocs est effectué en utilisant un algorithme par niveau (du même type que les algorithmes permettant l'extraction de requêtes fréquentes) et les recouvrements de blocs sont pris en compte par l'utilisation de la logique floue dans l'expression des règles décrivant ces blocs.

Ces travaux font l'objet de la thèse de Yeow Wei Choong au LICP et sont menés en collaboration avec le LI de l'Université de Tours, le LIRMM de l'Université Montpellier II et le HELP Institute de Kuala Lumpur (Malaisie).

Maintenance de vues matérialisées et données semi-structurées

Vu l'accroissement constant des données disponibles sur le web, la problématique de l'intégration de ces données dans des entrepôts de données spécifiques fait actuellement l'objet de nombreuses recherches. Un entrepôt de données semi-structurées peut être vu comme une ou plusieurs vues matérialisées qui sont évaluées à partir de certains sites appelés sources. Nous nous intéressons ici au problème de savoir comment un tel entrepôt doit être maintenu à jour lorsque les sources sont elles-mêmes modifiées. Ce problème, dans le cadre des bases de données relationnelles a donné lieu à de nombreuses recherches, y compris par le Directeur de l'équipe en collaboration avec le LRI et l'Université de Münster (Allemagne). Néanmoins, dans le cadre des données semi-structurées réparties sur le web, deux difficultés supplémentaires apparaissent : (i) les sources sont totalement indépendantes de l'entrepôt et donc ne communiquent aucune information sur leurs modifications et (ii) les transmissions de données entre l'entrepôt et les sources doivent être optimisées.

Ce travail est mené dans le cadre d'une architecture typique dans le domaine de l'intégration d'information, à savoir : chaque source est associée à un extracteur (wrapper) et les extracteurs communiquent avec un intégrateur dont le rôle est de traduire les données reçues des sources dans des formats différents en un format unique utilisable par les applications au niveau de l'entrepôt. Au terme d'une année de travail, les résultats obtenus dans ce cadre sont d'une part, la caractérisation des informations requises pour « récupérer », au niveau de l'intégrateur, les mises à jour ayant eu lieu sur les sources, et d'autre part, une étude systématique des différents cas de mise à jour possibles en fonction de la manière dont est défini l'entrepôt.

Ces travaux font l'objet de la thèse de Virginie Sans au LICP et sont menés en collaboration avec le PRISM de l'Université de Versailles Saint-Quentin-en-Yvelines.

Intégration de données hétérogènes avec XQuery

Les sources d'informations sur l'Internet sont nombreuses et très diversifiées. Afin de les présenter sous la forme d'une vue uniforme pour permettre leur interrogation, des architectures de médiation sont en général utilisées. Une architecture de médiation s'appuie sur le concept médiateur/adaptateur. Les adaptateurs se chargent de l'hétérogénéité des sources en faisant office de traducteurs vers un modèle commun. Le médiateur se charge de la distributivité des données en intégrant ces données. Le modèle commun que nous utilisons est XML et le langage permettant de l'interroger est XQuery. Nos études liées à XML se font dans les directions suivantes :

• La conception d'architectures de médiation optimisée dans un environnement pair-à-pair
• La définition d'une structure (nommée TGV) permettant de modéliser des requêtes XQuery afin de les optimiser et d'en tirer un plan d'exécution. Cette structure TGV doit tenir compte des capacités fonctionnelles des sources ainsi que de la distribution des données.
• La définition d'une algèbre (nommée XAlgèbre) pour la construction d'un plan d'exécution pour la résolution de requête XQuery sur des données distribuées.
• La définition et le calcul de modèles de coût par rapport à une requête XQuery.

Ces travaux font l'objet d'une thèse au PRiSM et sont menés en collaboration avec le laboratoire PRiSM de l'Université de Versailles-Saint-Quentin-en-Yvelines.

Données semi-structurées et XML

Les documents XML peuvent étant vus comme des arbres, et leur schéma étant vu comme une grammaire d'arbres, ou comme un automate d'arbres, la plupart des traitements des documents se ramènent à des calculs sur automates. Nos travaux dans ce domaine concernent les points suivants :

• La validation d'un document XML : un document XML, vu comme un arbre, doit être valide par rapport à un automate d'arbre défini à partir d'une DTD. Dans ce cadre, nous étudions les opérations de mises à jour d'un document XML.
• L'expression et l'exploitation des contraintes de clés et de clés étrangères dans les collections de documents XML.
• La définition et l'utilisation de schémas XML pour les processus d'extraction de connaissances afin de définir un cadre unificateur modélisant les différents types de motifs extraits et permettant ainsi l'interrogation de ces motifs.

Chacun de ces points fait l'objet d'une thèse au LI, et donc ces travaux sont menés en collaboration avec le LI de l'Université de Tours.