Contribution to the inductive database framework
Contribution au cadre des bases de données inductives
Résumé
The success of database technologies has lead to an always increasing mass of collected information in different application fields. Knowledge Discovery in Databases (KDD) aims at going further in the querying processes on such data so as to find in these data some hidden knowledge materialized under the form of patterns. The Inductive Database (IDB) concept is a generalization of the database concept which integrates patterns and data in a common framework. A KDD process can thus be seen as an extended querying process on an IDB. This PhD. Thesis is about the formalization and the evaluation of KDD scenarios in the IDB framework. We first show how to use an abstract language for IDBs to formally describe extraction processes that can be performed by the user. We thus obtain a prototypical scenario, i. E. A theoritical object made of a sequence of inductive queries and on which it is possible to reason. Such a kind of scenario is useful to formalize processes when transfering expertise between final users and KDD experts. Another application of the concept of scenario is the evaluation on a common basis of different implementations of IDBs, similarly to existing benchmarks for databases. An evaluation scenario has the same form than a prototypical scenario, but it focuses more on algorithmic issues and optimization techniques for sequences of inductive queries. When computing an execution plan for such a scenario, the IDB system should analyze the properties of queries composing it, by discovering dependencies between them or conjunctions of constraints for which it is useful to have efficient extraction tools. Finally, we present an evaluation scenario in the field of bioinformatics, and we show how to solve it by using techniques developed in our group or especially designed for the need of this scenario.
Le succès des techniques de bases de données permet de collecter une quantité toujours plus grande d'informations dans différents domaines. L'ECD (Extraction de Connaissance dans les Données) se donne pour but d'aller plus loin dans le processus d'interrogation des données pour y découvrir, sous forme de motifs, de la connaissance cachée. La notion de base de données inductive (BDI) généralise le concept de base de données en intégrant données et motifs dans un cadre commun. Un processus d'ECD peut alors être vu comme un processus d'interrogation étendu sur une BDI. Cette thèse s'intéresse `a la formalisation et `a l'évaluation des scénarios d'extraction dans le cadre des BDI. Nous montrons d'abord comment utiliser un langage abstrait pour les BDI pour décrire de manière formelle des processus d'extraction réalisables par l'utilisateur. Nous obtenons ainsi un scénario prototypique, i. E. Un objet théorique composé d'une séquence de requêtes inductives, sur lequel il est possible de raisonner. Un tel scénario sert avant tout `a formaliser des traitements pour le transfert d'expertise entre utilisateurs et spécialistes en ECD. Une autre application du concept de scénario est l'évaluation sur une base commune de différentes implémentations de BDI, dans la lignée des benchmarks existants pour les bases de données. Un scénario d'évaluation a le même aspect qu'un scénario prototypique, mais on s'intéresse ici aux problèmes algorithmiques et d'optimisation de séquences de requêtes inductives. Lors du calcul du plan d'exécution d'un tel scénario, le système devra analyser les propriétés des requêtes qui le composent, en découvrant des dépendances entre celles-ci ou des conjonctions de contraintes pour lesquelles nous souhaitons disposer d'outils d'extraction efficaces. Enfin, nous présentons un scénario d'évaluation en bioinformatique et nous montrons comment le résoudre en utilisant des techniques préexistantes dans l'équipe ou développées pour les besoins de ce scénario.