Mise en oeuvre de techniques d'optimisation de requetes pour l'enumeration de motifs interessants dans les grandes bases de données

Abstract

Le développement de méthodes et de techniques pour les problèmes data mining et le succès des bases de données grâce à la simplicité des langages déclaratifs comme SQL et des techniques d'optimisation, ont emmené à la proposition de langages requêtes pour exprimer di érentes tâches data mining. Ces derniers s'avèrent très spéci ques, c'est une couche syntaxique autour d'un algorithme data mining. Dans ce mémoire, nous avons proposé une approche déclarative pour répondre à des requêtes data mining. Nous avons proposé un langage déclaratif pour exprimer des requêtes pour une classe particulière de problèmes d'extraction de motifs, dits "Représentables par des ensembles". Nous avons utilisé la logique DML pour exprimer les requêtes utilisateur et étudier leurs formes logiques. La logique DML permet de d'identi er deux propriétés importantes pour l'optimisation des requêtes : monotonie / anti-monotonie, ce sont les deux propriétés qu'exploitent les algorithmes génériques de la librairie iZi. Nous avons étendu également DML avec une classe importante de contraintes, dites succinctes ayant un pouvoir d'élagage de l'espace de recherche important. Une fois les formes logiques sont étudiées, un algorithme d'évaluation de la librairie iZi est choisi et un plan physique est généré pour répondre à une requête data mining.