N-Catch : un modèle d’entrepôt de données sur le cycle de l’azote dans un bassin versant

Télécharger le fichier pdf d’un mémoire de fin d’études

Entrepôts de données : concepts et définitions

Au cours de ces dernières années, les entrepôts de données ont joué un rôle essen-tiel dans le domaine de l’informatique décisionnelle en soutenant et en améliorant les processus décisionnels des organisations. « Un entrepôt de données est une collection de données thématiques, intégrées, non volatiles, historisées et exclusivement destinées aux processus d’aide à la décision » [Inm92]. L’évolution des technologies a conduit à conserver les données pour assurer le suivi des activités. L’intérêt de l’utilisation d’un entrepôt de données est : (i) de fournir un accès facile et rapide à ce gros volume de données accumulées au fil du temps à partir de diverses sources de données et dans divers formats (bases de données traditionnelles, fichiers xml, fichiers excel,..etc.) et (ii) d’analyser ces données pour prendre des décisions stratégiques et tactiques. Leurs uti-lisateurs, des décideurs, sont donc peu nombreux et s’intéressent non pas au détail des données mais à des tendances générales, selon tel ou tel critère.

Modèle multidimensionnel

La modélisation multidimensionnelle est la base des entrepôts de données et de l’analyse multidimensionnelle. Une dimension est un axe d’analyse du sujet étudié. Un modèle multidimensionnel fournit un support pour une analyse reposant sur plusieurs dimensions. Les données sont organisées de sorte à mettre en valeur le sujet étudié (i.e. analysé) et les diﬀérents axes d’analyse. Ces sujets d’analyses, nommés faits, peuvent représenter par exemple : les ventes d’un produit, la quantité de pesticides ou d’azote ap-pliquée par les agriculteurs. Un fait consiste en un ensemble de mesures correspondant à des informations sur le sujet analysé. Dans la suite de ce chapitre, tous les exemples et illustrations porteront sur le domaine d’application de l’agro-hydrologie, et plus pré-cisément sur l’analyse de l’impact des pratiques agricoles sur la pollution nitrique.

Modèle multidimensionnel hiérarchique

L’objectif d’un entrepôt de données est de permettre aux utilisateurs de formuler des requêtes complexes et d’eﬀectuer des analyses sur des données agrégées afin d’en dé-gager des propriétés implicites. Chaque dimension peut être associée à une ou plusieurs hiérarchies utilisées pour aﬃcher les données multidimensionnelles à plusieurs niveaux de granularité. Les valeurs des mesures associées à un niveau de granularité plus gros-sier sont obtenues en synthétisant des valeurs de mesures de plus bas niveau. On dit alors que les valeurs sont agrégées. Une fonction d’agrégation (e.x. somme, moyenne, maximum, etc.) est associée à chaque mesure définie dans le modèle multidimensionnel hiérarchique.
Exemple 2 Nous décrivons dans la Figure.1.2 deux diﬀérentes hiérarchies possibles sur la dimension Localisation. La première décrit une hiérarchie stricte (basée sur un ordre total) : chaque parcelle appartient à un bassin versant, qui à son tour appartient à une région, elle même située dans un pays, et la deuxième décrit une hiérarchie non-stricte (basée sur un ordre partiel) : chaque maille appartient à une parcelle et à un bassin versant (il n’existe pas de relation hiérarchique entre parcelle et bassin versant, car une parcelle peut appartenir à plusieurs bassins versants en même temps), qui à leur tour appartiennent à une région.

R-OLAP : Relational OLAP

L’implémentation R-OLAP ( « Relational OLAP » ou OLAP relationnelle) utilise une base de données relationnelle, pour le stockage des données et des agrégations destinées à l’analyse. La majorité des fonctions nécessaires à l’utilisation d’OLAP sont donc gérées par un système de gestion de bases de données relationnelle (SGBDR). Le langage de requête (i.e. SQL) est expressif, et son interprétation est optimisée pour un temps de réponse minimal. La base de données relationnelle doit être structurée suivant un schéma spécifique afin de faciliter les processus d’analyse par le SGBDR. En eﬀet, seuls certains schémas, décrits par les auteurs de [IBM98], peuvent être adaptés aux concepts OLAP. Le schéma en étoile est le plus connu, il consiste en une table de fait centrale et un ensemble de tables de dimensions représentées visuellement par une étoile (e.g. 1.1). En revanche, le schéma en constellation fusionne plusieurs schémas en étoile en utilisant des dimensions communes, il comprend donc plusieurs tables de faits et des dimensions communes ou spécifiques. Enfin, le schéma en flocon dérive du schéma en étoile : la table de fait est maintenue, tandis que les dimensions sont divisés en plusieurs tables en fonction de leurs hiérarchies. Le modèle en flocon est préconisé lorsque les tables de dimensions contiennent un très grand volume de données. Pour conclure, l’utilisation des SGBDR permet à l’implémentation R-OLAP de traiter un volume considérable de données. Cependant, l’implémentation R-OLAP se retrouve limitée aux fonctionnalités du langage SQL, et peut présenter des temps de calculs assez longs, étant donné qu’elle est plus adaptée à des processus transactionnels.

M-OLAP : Multidimensionnal OLAP

L’implémentation M-OLAP (« Multidimensional OLAP » ou OLAP multidimension-nel) utilise une base de données multidimensionnelle pour le stockage des données. Cette base de données multidimensionnelle possède une structure optimisée pour l’analyse, souvent nommée cube ou hypercube. M-OLAP utilise son propre système de gestion de bases de données, sous forme de matrices (i.e. tableaux). Toutes les fonctions spécifiques à l’OLAP sont mises en oeuvre nativement dans le système M-OLAP. Cette implémen-tation est généralement plus performante que R-OLAP pour plusieurs raisons. Tout d’abord, l’accès aux données par l’indexation multidimensionnelle est très peu coûteux. En eﬀet, les données sont organisées de manière à être directement exploitables par les outils d’analyse. Ensuite, les techniques de compression permettent de réduire au minimum l’espace de stockage additionnel requis. Ce qui permet à l’implémentation M-OLAP d’occuper moins de place sur le disque que l’implémentation R-OLAP pour laquelle les agrégations sont stockées dans la base de données relationnelle. Cependant, M-OLAP présente des limites majeures sur le plan du passage à l’échelle. En eﬀet, l’im-plémentation M-OLAP est très performante pour les données à faible dimensionnalité. Toutefois, en présence de gros volumes de données à forte dimensionnalité, la main-tenance de la structure et les requêtes d’analyse deviennent trop coûteuses. C’est de ce constat qu’à émergé une nouvelle implémentation combinant R-OLAP et M-OLAP, appelé Hybrid OLAP.

H-OLAP : Hybrid OLAP

L’implémentation H-OLAP (« Hybrid OLAP » ou OLAP hybride) constitue un croise-ment entre les deux implémentations présentées précédemment. Au sein de cette implé-mentation, un serveur H-OLAP accède à deux bases de données diﬀérentes. La première, multidimensionnelle, contient les données agrégées. La seconde, relationnelle, contient les données détaillées. L’implémentation H-OLAP hérite des caractéristiques des implé-mentations R-OLAP et M-OLAP selon le type de données manipulées par les requêtes, R-OLAP dans le cas de données détaillées et M-OLAP dans le cas de données agrégées. Cette implémentation devient particulièrement intéressante lorsque la majeure partie des requêtes manipulent des données agrégées (l’accès au données dans M-OLAP est peu coûteux) et que les données détaillées représentent un volume important (les SGBDR permettent de traiter un volume considérable de données).

Opérateurs de navigation

La vocation de l’OLAP est de réaliser une analyse interactive et multidimensionnelle des données de l’entrepôt de données. On parle de navigation dans les données et d’ana-lyse exploratoire. Cette analyse en ligne agrège les données pour pouvoir les explorer et les visualiser. L’OLAP dispose d’un ensemble d’opérateurs de navigation qui vont lui permettre de visualiser les informations contenues dans le cube, de sélectionner un sous-cube, de modifier l’ensemble des dimensions à prendre en compte ou de changer leur granularité. Comme mentionné précédemment, ces opérateurs de navigation sont géné-ralement décomposés en trois catégories : opérateurs de structuration (Rotate, Switch, Push, Pull ), de sélection (Slice, Dice) et d’agrégation (Roll-up, Drill-down). Dans cette partie, nous décrivons rapidement les opérateurs les plus utilisés dans la littérature et qui représentent un intérêt pour la suite de notre travail.

Opérateurs de sélection : Slice et Dice

L’opérateur Slice (littéralement, trancher), permet de sélectionner un sous ensemble du cube, selon une ou plusieurs valeurs d’une dimension particulière. Slice est un opéra-teur de sélection portant sur les valeurs d’une seule dimension. La Figure.1.5 montre un exemple de Slice : à partir du cube « Rendement Agricole » initial, on sélectionne un sous-ensemble de ce cube tel que la « Localisation » soit « France » ou « USA ». L’opérateur Dice permet de faire une projection du cube. L’application de Dice équivaut à l’application de l’opérateur Slice à plusieurs dimensions. La Figure.1.6 montre un exemple de Dice : à partir du cube « Rendement Agricole » initial, on sélectionne un sous-ensemble de ce cube tel que la « Localisation » soit « France » ou « USA », et que la « Date » soit « 2009 » ou « 2011 ». Slice ne peut produire que des tranches du cube, du fait qu’une sélection n’est possible que sur une dimension, alors que Dice peut produire des sous-cubes arbitraires.

Couplage fouille de données symboliques et analyse en ligne

Les premières tentatives d’extension des outils OLAP avec des méthodes de fouille de données remontent à 1997 avec les travaux de Han [Han97]. Ces travaux ont abouti à la création du système DBMiner. Ce système est fondé sur une approche M-OLAP. Les données sont stockées dans des structures multidimensionnelles, et plusieurs modules d’analyse sont proposés. Ces modules correspondent à des opérateurs OLAP auxquels on a ajouté des extensions permettant de simuler diverses techniques de fouille de don-nées. Cependant, les références relatives à DBMiner décrivent plutôt le côté fonctionnel de ce dernier et ne donnent pas assez d’information sur les procédés employés et la méthodologie théorique suivie.
Par la suite, divers travaux se ont intéressés à l’exploration automatique des cubes de données avec des algorithmes d’extraction de règles d’association [MHC97, GC98, IKA02]. Les diﬀérents auteurs (Kamber, Imieliski, Goil, Choudhary, …) exploitent la

Couplage fouille de données statistiques et analyse en ligne

Enrichissement de l’analyse OLAP 31 structure multidimensionnelle du cube, avec ses agrégats pré-calculés, qu’ils considèrent comme un contexte favorable pour la recherche de règles. En eﬀet, le support et la confiance des règles peuvent être calculés directement à partir des fréquences obtenues avec la fonction d’agrégation COUNT pour le calcul des agrégats. Ils évitent ainsi de parcourir plusieurs fois toutes les données. Ainsi, selon cette approche, des opérateurs OLAP sont utilisés comme outils pour extraire et calculer les diﬀérents critères d’une règle à diﬀérents niveaux de granularité des dimensions du cube de données.
Plus récemment, l’auteur de [Lou11] a proposé un nouvel opérateur AROX (Asso-ciation Rules Operator for eXplanation) pour expliquer des phénomènes observés dans le cube à l’aide de règles d’association. En eﬀet, l’opérateur AROX se base sur une recherche guidée de règles d’association. Afin d’adapter le support et la confiance d’une règle au contexte OLAP, l’auteur propose une nouvelle définition du support et de la confiance en y associant les mesures quantitatives du cube de données. Ainsi, contrai-rement à toutes les autres approches, une règle d’association n’est plus évaluée selon le nombre d’occurrences des faits qu’elle supporte mais selon les mesures des faits qu’elle supporte. Par exemple, un agriculteur est plus intéressé d’analyser ses cultures en fonc-tion de leur rendement plutôt qu’en fonction de la surface qu’elles occupent.
D’autres études [PLL 10, NQN04, WK06, PHP 01] se sont intéressées à l’extraction de motifs fréquents dans le contexte de données multidimensionnelles et hiérarchiques. Les auteurs de [NQN04] Naouali et al. proposent d’extraire des motifs fréquents à partir de la table de fait d’un cube de données, où donc chaque motif représente un fait au sens OLAP. Selon les auteurs, les motifs fréquents permettent de mettre en évidence des liens sémantiques traduisant des relations intéressantes entre les cellules du cube étudié. Ces liens sont alors basés sur les ensembles fréquents que se partagent les cel-lules du cube. Les auteurs de [PLL 10, PHP 01] se sont intéressés quant à eux à la combinaison de plusieurs dimensions d’analyse et à la prise en compte des hiérarchies lors du processus d’extraction de motifs séquentiels multidimensionnels. Ceci afin de permettre une extraction de connaissances plus complète et dont l’utilisation dans le contexte OLAP peut être envisageable.
D’autres tentatives d’extension des capacités de l’OLAP ont émergé [SAM98, YGJ 06, CRST06, Lou11] avec la volonté d’étendre l’OLAP à la prédiction en ligne (i.e. analyse de type What If Analysis). Dans ce contexte, le couplage entre l’OLAP et la fouille de données permet de prédire la valeur de la mesure pour des faits inexistants ou des faits avec une valeur manquante. L’objectif est de permettre à l’utilisateur d’analyser les données du passé mais aussi d’anticiper les événements du futur. La plupart de ces travaux, utilisent comme méthode de prédiction un modèle de régression (linéaire, log-linéaire, logistique, …).
D’autres études [MRBB04, BF09b] ont tenté de relâcher la contrainte du schéma fixe de l’entrepôt en permettant la modification de la structure hiérarchique d’une dimension. Ces travaux se basent sur des méthodes de classifications pour définir de nouvelles hié-rarchies basées sur des relations sémantiques. Les auteurs de [MRBB04] ont proposé un nouvel opérateur OLAP, baptisé OpAC (Operator for Aggregation by Clustering), basé sur une méthode CAH (Classification Ascendante Hiérarchique). L’opérateur OpAC consiste en l’agrégation sémantique des valeurs d’une dimension d’un cube de données en se basant sur la technique CAH. Les opérateurs OLAP classiques agrègent les valeurs d’une dimension selon des liens hiérarchiques prédéfinis. En revanche, OpAC permet de créer de nouveaux agrégats qui reflètent des fait réels en exploitant les mesures contenues dans le cube de données.
Les auteurs de [BF09b] ont quant à eux proposé un nouvel opérateur d’agrégation RoK (Roll-up with K-means) en utilisant la méthode de classification automatique des k-means, qui permet de rechercher des structures naturelles dans les données. L’opé-rateur RoK permet de créer un nouveau niveau de granularité dans une hiérarchie de dimension en se basant sur les K-means. Il s’agit de trouver un bon regroupement des instances d’un niveau d’analyse existant choisi par l’utilisateur, à partir duquel un nouveau niveau d’analyse peut être créé. Cette approche enrichit l’analyse multidimen-sionnelle en oﬀrant de nouveaux angles de vues intéressants sur les faits pouvant être explorés par l’utilisateur.
Afin d’assister l’utilisateur dans sa tâche d’exploration des cubes de données, cer-tains travaux [SAM98, Lou11, LB12, Sar01] ont proposé des méthodes basées sur des modèles statistiques et notamment d’analyse factorielle pour le guider vers les régions intéressantes du cube et pour réorganiser intelligemment les dimensions du cube. Dans [SAM98], Sarawagi et al. proposent un outil d’identification des régions remarquables dans les cubes de données. Ils proposent une exploration guidée par la découverte (Discovery-Driven). Leur idée consiste à intégrer un module statistique de régression multidimensionnelle dans un serveur OLAP en vue de guider l’utilisateur pour détec-ter des valeurs outliers à diﬀérents niveaux hiérarchiques d’un cube de données. Une amélioration de ces travaux a été proposée dans [Sar01]. Cette amélioration concerne une meilleure automatisation de l’analyse par l’emploi de la programmation dynamique. Cette automatisation est garantie par un nouvel opérateur, appelé iDiﬀ, qui détecte les régions outliers et explore les raisons de la présence de ces régions dans un cube de données.
Plus récemment de nouveaux opérateurs (VOCoDa et ORCA) [Lou11, LB12, BMBLR07, MBR06] ont été proposés pour l’analyse en ligne de données complexes (données multi-sources, multi-formats et multi-structures). Ces deux opérateurs se basent sur des mé-thodes factorielles (AFC et ACM) pour la visualisation des faits dans un cube et la détection de régions intéressantes en réorganisant les dimensions du cube.

Algorithmes de recherche dans des sous-espaces

Comme nous l’avons vu dans la section précédente, de nombreux travaux récents se sont penchés sur le problème de l’extraction des points skyline en proposant des mé-thodes de calcul eﬃcaces. Cependant, lorsque le nombre de dimensions est trop impor-tant, les requêtes skyline commencent à perdre leur pouvoir discriminant en renvoyant une grande partie des données. Cela dit, est-il vraiment pertinent de prendre en considé-ration l’ensemble des dimensions à chaque nouvelle requête skyline ? La réponse est non. En eﬀet, il a été constaté, que suivant leurs centres d’intérêts, les utilisateurs pouvaient être amenés à poser des requêtes sur diﬀérents sous-ensembles de l’espace de dimensions et non sur la totalité. À partir de cette observation, divers travaux se sont alors intéressés à l’extraction de points skyline dans des sous-espaces de dimensions. Dans un scénario général, les requêtes skyline classiques peuvent être directement adaptées dans des sous-espaces. Cependant, lorsqu’il s’agit de calculer les skyline sur diﬀérents sous-espaces, aucun des algorithmes existants ne sait exploiter à son avantage les liens qui peuvent exister entre les diﬀérents skyline de ces diﬀérents sous-espaces. De plus la connaissance de ces liens peut être très intéressante non seulement pour économiser les temps de cal-cul mais aussi pour un décideur qui souhaite comprendre les raisons pour lesquelles un point donné devient dominant ou à l’inverse dominé. Diverses études se sont alors focali-sées sur ce problème [PJET05, RPK10, HGSW08, TD06, LOTW06, JTEH07, TXP08]. Dans ce qui suit nous décrivons un ensemble d’algorithmes spécifiquement développés pour l’extraction de points skyline dans des sous-espaces.
L’algorithme Skyline Cube (SKY CU BE) L’algorithme SKY CU BE a été indé-pendamment proposé par les auteurs de [PJET05, YLL 05]. À l’image du cube de don-nées dans les entrepôts de données, le SKY CU BE consiste en l’ensemble des skyline sur tous les sous-ensembles possibles. En d’autres termes, on peut dire que le SKY CU BE est au skyline ce que le cube de données est au GROU P -BY : une généralisation mul-tidimensionnelle. Le calcul d’un skyline étant généralement aussi coûteux que le calcul d’un GROU P -BY , la structure utilisée par l’algorithme SKY CU BE a les mêmes in-convénients que le cube de données. En eﬀet, si on souhaite répondre rapidement à toutes les requêtes posées sur la structure de SKY CU BE, il faut envisager là aussi une pré-matérialisation de ce cube. Deux diﬀérentes implémentations du SKY CU BE ont été proposées :
– The Bottom-Up Skycube algorithm (BU S) : L’idée de base de l’algorithme BU S est de calculer chaque cuboïde (i.e un sous ensemble du cube de données) du SKY CU BE niveau par niveau et de bas en haut, en prenant en compte la pro-priété suivante : un cuboïde père contient l’union de ses fils. Lorsque l’on calcule un cuboïde, on sait donc qu’un point présent dans un des fils sera forcément sky-line. Cette propriété a le double avantage de réduire l’entrée pour le calcul d’un cuboïde et de diminuer le nombre de tests de dominance eﬀectués.
– The Top-Down Skycube algorithm (T DS) : À l’inverse de BU S, l’algorithme T DS permet de calculer chaque cuboïde du SKY CU BE niveau par niveau et de haut en bas. Il calcule d’abord le cuboïde de tout l’espace de dimensions, ensuite chaque cuboïde fils peut être obtenu en appliquant un algorithme de calcul de skyline classique sur le cuboïde père. Cela permet de diminuer le nombre de tests de dominance en réduisant l’ensemble en entrée.
Cependant, ces deux algorithmes partagent certains inconvénients. En eﬀet, pour construire un SKY CU BE, les deux méthodes doivent énumérer et rechercher les points skyline associés à tous les sous-espaces possibles et non vides (i.e. 2n 1, avec n le nombre de dimensions l’espace). Cela conduit naturellement à de mauvaises performances sur des ensembles de données à dimensionnalité élevée. Par exemple, pour un ensemble de données associé à 30 dimensions, il existe 230 1 sous-espaces non vides.
Pei et al. [JAWCXH07] ont proposé Stellar, une méthode de calcul du SKYCUBE qui évite de rechercher l’ensemble skyline dans chaque sous-espace. En utilisant les notions de Groupe Skyline et de Sous-espace décisif, Stellar garantit qu’en conservant uniquement les groupes skyline et les sous-espaces décisifs associés, il est possible de retrouver tous les points skyline. Cette représentation est donc sans perte d’information et plus réduite que le SKY CU BE.
L’algorithme Orion [RPK10] est à notre connaissance l’approche la plus récente pour le calcul et l’optimisation du SKYCUBE. Il propose une représentation concise du SKY-CUBE. Il réduit considérablement les tests de dominance dans un sous-espace donné en identifiant les points skyline qui peuvent être dérivés à partir de skyline d’autres sous-espaces. En eﬀet, l’algorithme identifie deux types de points skyline : (i) des sky-line pouvant être entièrement déduits à partir d’une seule règle d’inférence et (ii) des skyline ayant besoin de règles de dérivation avancées ou, éventuellement de tests de dominance. L’algorithme, en se basant sur les connexions de Galois, réduit également le nombre de sous-espaces à explorer. En eﬀet, un opérateur de fermeture ainsi que son dual ont été définis pour le SKYCUBE. Un de ces opérateurs est ensuite utilisé pour construire une représentation concise du SKYCUBE. Avec un parcours en pro-fondeur, l’algorithme Orion permet de calculer de manière optimale les sous-espaces clos et d’élaguer eﬃcacement l’espace de recherche. Les expérimentations présentées dans [RPK10] montrent que les performances de l’algorithme Orion surpasse les perfor-mances de Stellar. En eﬀet, contrairement à Orion, Stellar ne tire pas profit de toutes les propriétés ni de toutes les relations entre les points skyline projetées sur diﬀérents sous-espaces. Ces relations peuvent aider à déduire directement les skyline sans test de dominance.
L’algorithme SU BSKY Proposé par les auteurs de [YXJ06], l’algorithme SUBSKY permet le calcul de requêtes skyline dans des sous-espaces arbitraires. SUBSKY conver-tit les données multidimensionnelles en valeurs à une dimension qui sont indexées dans un B-T ree. Deux diﬀérentes implémentations de l’algorithme ont été développées : Ba-sic SUBSKY pour les données uniformément distribuées et General SUBSKY pour les données distribuées de manière aléatoire. Les données sont classifiées dans un B-T ree sur la base de leur distance à un point repère, qui est identifié pour chaque cluster. Étant donné que la puissance d’élagage de cette méthode repose sur le choix des points repères, SUBSKY n’est pas adapté pour les données dynamiques, où la distribution des données peut changer au fil du temps. En outre, la capacité d’élagage de SUBSKY se détériore rapidement lorsque le nombre de dimensions augmente, ce qui le rend inapproprié pour le calcul de skyline dans des sous-espaces arbitraires à forte dimensionnalité.

Discussion et conclusion

Dans la première partie de cette section, nous avons étudié les meilleurs représentants des deux grandes familles d’algorithmes (avec et sans index) de calculs de skyline. Dans ce qui suit, nous présentons un tableau récapitulatif en prenant en compte les critères d’évaluation décrits précédemment. Les algorithmes de calcul de skyline dans des sous-espaces ne sont pas inclus dans cette comparaison, car ces méthodes se basent sur les algorithmes de calculs de skyline dans un espace complet pour extraire leur skyline. En eﬀet, les algorithmes SUBSKY et SKYCUBE calculent leur skyline avec les algorithmes D&C et BBS respectivement.
Nous constatons (cf. Table 2.3), que tous les algorithmes décrits précédemment res-pectent parfaitement les deux critères Correction et Complétude, en retournant le skyline exact. S’agissant du critère Eﬃcacité, nous remarquons que les algorithmes utilisant les index spatiaux sont plus eﬃcaces que les autres. Toutefois, ils deviennent peu eﬃcaces voire inexploitables dès que le nombre de dimensions dépasse 6. Incontestablement, le comportement progressif (i.e. critère Progressivité) implique un pré-traitement des don-nées en entrées, c’est à dire l’utilisation d’index (N N, BBS, Index et Bitmap) ou le tri des données (SF S et LESS). Ces pré-traitement peuvent être réutilisés par toutes les requêtes ultérieures de manière dynamique avec la structure correspondante. Concer-nant la gestion des mises à jour des données, les algorithmes N N et BBS utilisent des structures d’index dynamiques (R-Tree), pouvant être mises à jour de manière incré-
Requêtes skyline : concepts de base 51

Le rapport de stage ou le pfe est un document d’analyse, de synthèse et d’évaluation de votre apprentissage, c’est pour cela chatpfe.com propose le téléchargement des modèles complet de projet de fin d’étude, rapport de stage, mémoire, pfe, thèse, pour connaître la méthodologie à avoir et savoir comment construire les parties d’un projet de fin d’étude.

Table des matières

Introduction
I État de l’art : Analyse des bases de données multidimensionnelles
1 Analyse en ligne OLAP
1.1 Introduction
1.2 Entrepôts de données : concepts et définitions
1.2.1 Modèle multidimensionnel
1.2.2 Modèle multidimensionnel hiérarchique
1.2.3 Architecture d’un entrepôt de données
1.2.4 Implémentations
1.2.4.1 R-OLAP : Relational OLAP
1.2.4.2 M-OLAP : Multidimensionnal OLAP
1.2.4.3 H-OLAP : Hybrid OLAP
1.2.5 Opérateurs de navigation
1.2.5.1 Opérateurs de sélection : Slice et Dice
1.2.5.2 Opérateurs d’agrégation : Roll-up et Drill-down
1.2.6 Domaines d’application des entrepôts de données
1.3 Enrichissement de l’analyse OLAP
1.3.1 Couplage fouille de données et analyse en ligne
1.3.1.1 Couplage fouille de données symboliques et analyse en ligne
1.3.1.2 Couplage fouille de données statistiques et analyse en ligne
1.3.2 Couplage recherche d’information et analyse en ligne
1.3.3 Discussion et conclusion
2 Analyse multicritères dans les bases de données
2.1 Introduction
2.2 Requêtes skyline : concepts de base
2.2.1 Ordres de préférence et skyline
2.2.2 Propriétés des requêtes skyline
2.2.3 Algorithmes de calcul des skyline
2.2.3.1 Algorithmes de recherche dans un espace complet
2.2.3.2 Algorithmes de recherche dans des sous-espaces
2.2.4 Discussion et conclusion
II N-Catch : un modèle d’entrepôt de données sur le cycle de l’azote dans un bassin versant
3 Processus de construction de l’entrepôt de données N-Catch
3.1 Introduction et motivations
3.2 Les données
3.2.1 Le modèle TNT
3.2.2 Site d’étude
3.2.3 Protocole de simulation
3.3 Processus de construction de N-Catch
3.3.1 Modélisation et alimentation de N-Catch
3.3.2 Modélisation de N-Catch
3.3.2.1 Dimension spatiale
3.3.2.2 Dimension temporelle
3.3.2.3 Dimension agricole
3.3.2.4 Mesures : indicateurs agro-environnementaux
3.3.3 Alimentation de N-Catch
3.3.3.1 Extraction des données
3.3.3.2 Transformation et chargement des données
3.3.4 Implémentation de N-Catch
3.4 Utilisation de l’entrepôt de données N-Catch
3.4.1 Requêtes étudiées
3.4.2 Illustration de N-Catch
3.4.2.1 Dimension temporelle
3.4.2.2 Dimension spatiale
3.4.2.3 Dimension agricole
3.4.3 Discussion
3.5 Visualisation cartographique des données stockées dans N-Catch
3.5.1 Système d’information géographique (SIG)
3.5.2 Spatial-OLAP (S-OLAP )
3.5.3 Description des données spatiales
3.5.4 Couplage de N-Catch avec QGIS
3.5.4.1 Jointure de N-Catch avec les données spatiales
3.5.4.2 Exemples de requêtes
3.6 Conclusion
III Requêtes skyline dans un contexte multidimensionnel et hiérarchique
4 Calcul incrémental des requêtes skyline en présence de préférences dynamiques
4.1 Introduction et motivations
4.2 Skyline et préférences dynamiques
4.2.1 Algorithme IPO-T ree
4.3 Algorithme EC2Sky
4.3.1 Calcul incrémental des skyline : Théorème
4.3.2 Implémentation de EC2Sky
4.3.2.1 Les skyline associés aux dimensions statiques
4.3.2.2 Les skyline associés aux dimensions dynamiques
4.3.3 Structure de EC2Sky
4.3.4 Évaluation de requêtes
4.3.5 Évaluations expérimentales
4.4 Conclusion
5 Requêtes skyline hiérarchiques
5.1 Introduction et motivations
5.2 Requêtes skyline associées à des dimensions hiérarchiques
5.2.1 Formalisation des hiérarchies
5.2.2 Relations hiérarchiques entre préférences
5.2.3 Navigation dans la structure de spécialisation/généralisation
5.2.4 Algorithme HSky
5.2.4.1 Calcul des requêtes skyline hiérarchiques
5.2.4.2 Structure de HSky
5.2.4.3 Évaluation de requêtes
5.2.4.4 Évaluations expérimentales
5.3 Conclusion
IV Couplage de l’entrepôt N-Catch avec les requêtes skyline
6 Utilisation des algorithmes EC2Sky et HSky à partir de N-Catch
6.1 Introduction et motivations
6.2 Couplage de N-Catch avec les algorithmes EC2Sky et HSky
6.2.1 Requêtes étudiées
6.2.2 Illustration du couplage de N-Catch avec EC2Sky
6.2.3 Illustration du couplage de N-Catch avec HSky
6.3 Conclusion
Conclusion
Bibliographie