Horizon Portail d'Information

Ressources numériques

Recherche rapide

Recherche avancée

Recherche alphabétique

Modifier la recherche

Dieng , Cheikh Tidiane , 1979-....

Laurent , Dominique , 19..-.... , professeur d'informatique

Goethals , Bart

Petit , Jean-Marc , 1968-....

Crémilleux , Bruno

Sall , Oumar , 19..-....

Université de Cergy-Pontoise , 1991-2019

Université de Saint-Louis , Sénégal

École doctorale Sciences et ingénierie , Cergy-Pontoise, Val d'Oise

Equipes Traitement de l'Information et Systèmes , Cergy-Pontoise, Val d'Oise

Etude et implantation de l'extraction de requetes frequentes dans les bases de donnees multidimensionnelles , Cheikh Tidiane Dieng ; sous la direction de Dominique Laurent

Thèse soutenue en co-tutelle

Titre provenant de l'écran-titre

Thèse soumise à l'embargo de l'auteur jusqu'au 19 juillet 2021

Ecole(s) Doctorale(s) : École doctorale Sciences et ingénierie (Cergy-Pontoise, Val d'Oise)

Partenaire(s) de recherche : Equipes Traitement de l'Information et Systèmes (Cergy-Pontoise) (Laboratoire)

Autre(s) contribution(s) : Dominique Laurent, Bruno Crémilleux, Oumar Sall, Tao-Yuan Jen (Membre(s) du jury) ; Bart Goethals, Jean-Marc Petit (Rapporteur(s))

Thèse de doctorat STIC (sciences et technologies de l'information et de la communication) Cergy-Pontoise 2011

Thèse de doctorat STIC (sciences et technologies de l'information et de la communication) Université de Saint-Louis (Sénégal) 2011

Au cours de ces dernières années, le problème de la recherche de requêtes fréquentes dans les bases de données est un problème qui a suscité de nombreuses recherches. En effet, beaucoup de motifs intéressants comme les règles d'association, des dépendances fonctionnelles exactes ou approximatives, des dépendances fonctionnelles conditionnelles exactes ou approximatives peuvent être découverts simplement, contrairement au méthodes classiques qui requièrent plusieurs transformations de la base pour extraire de tels motifs.Cependant, le problème de la recherche de requêtes fréquentes dans les bases de données relationnelles est un problème difficile car, d'une part l'espace de recherche est très grand (puisque égal à l'ensemble de toutes les requêtes pouvant être posées sur une base de données), et d'autre part, savoir si deux requêtes sont équivalentes (donc engendrant les calculs de support redondants) est un problème NP-Complet.Dans cette thèse, nous portons notre attention sur les requêtes de type projection-selection-jointure, et nous supposons que la base de données est définie selon un schéma étoile. Sous ces hypothèses, nous définissons une relation de pré-ordre (≼) entre les requêtes et nous montrons que :1. La mesure de support est anti-monotone par rapport à ≼, et2. En définissant, q ≡ q′ si et seulement si q ≼ q′ et q′ ≼ q, alors toutes les requêtes d'une même classe d'équivalence ont même support.Les principales contributions de cette thèse sont, d'une part d'étudier formellement les propriétés du pré-ordre et de la relation d'équivalence ci-dessus, et d'autre part, de proposer un algorithme par niveau de type Apriori pour rechercher l'ensemble des requêtes fréquentes d'une base de données définie sur un schéma étoile. De plus, cet algorithme a été implémenté et les expérimentations que nous avons réalisées montrent que, selon notre approche, le temps de calcul des requêtes fréquentes dans une base de données définie sur un schéma étoile reste acceptable, y compris dans le cas de grandes tables de faits.

The problem of mining frequent queries in a database has motivated many research efforts during the last two decades. This is so because many interesting patterns, such as association rules, exact or approximative functional dependencies and exact or approximative conditional functional dependencies can be easily retrieved, which is not possible using standard techniques.However, the problem mining frequent queries in a relational database is not easy because, on the one hand, the size of the search space is huge (because encompassing all possible queries that can be addressed to a given database), and on the other hand, testing whether two queries are equivalent (which entails redundant support computations) is NP-Complete.In this thesis, we focus on projection-selection-join queries, assuming that the database is defined over a star schema. In this setting, we define a pre-ordering (≼) between queries and we prove the following basic properties:1. The support measure is anti-monotonic with respect to ≼, and2. Defining q ≡ q′ if and only if q ≼ q′ and q′ ≼ q, all equivalent queries have the same support.The main contributions of the thesis are, on the one hand to formally sudy properties of the pre-ordering and the equivalence relation mentioned above, and on the other hand, to prose a levewise, Apriori like algorithm for the computation of all frequent queries in a relational database defined over a star schema. Moreover, this algorithm has been implemented and the reported experiments show that, in our approach, runtime is acceptable, even in the case of large fact tables.

Configuration requise : un logiciel capable de lire un fichier au format : PDF

(Accès au texte intégral) http://www.theses.fr/2011CERG0530/document

http://biblioweb.u-cergy.fr/theses/

Bases de données

Thèses et écrits académiques

Pour toute question, contactez la bibliothèque

Horizon Information Portal 3.25_france_v1m© 2001-2019 SirsiDynix Tous droits réservés.

Horizon Portail d'Information