État de l’art : Analyse des bases de données multidimensionnelles

Analyse en ligne OLAP 

L’évolution permanente des technologies de l’information conduit de plus en plus d’acteurs (entreprises, recherche,…) à conserver leurs données et ainsi préserver la mémoire de leurs activités. Les données collectées par ces acteurs sont un atout puissant pour dégager des tendances passées, actuelles et surtout futures. À partir des gisements de données ainsi constitués, il est naturel de chercher à les exploiter au mieux. Apparus pour gérer de très gros volumes de données issues de sources hétérogènes, les entrepôt de données [Inm92], ou en anglais Data warehouses, constituent l’outil essentiel de collecte et de mise à disposition des données en vue de leur analyse. L’analyse de ces données fait appel à des traitement OLAP (On Line Analytical Processing), introduits par les auteurs
de [CCS93], qui se distinguent des processus OLTP (On-Line Transactional Processing) principalement par leur complexité et par le nombre de données. En effet, il ne s’agit pas de formuler des requêtes classiques, simples et fréquentes, sélectionnant généralement quelques dizaines de tuples (i.e. enregistrements), mais de procéder à des analyses nécessitant d’agréger, de visualiser et d’explorer de manière interactive les données. On parle de navigation dans les données et d’analyse exploratoire. Pour cela les données sont représentées dans une structure particulière appelée cube de données ou hypercube [GBLP96]. C’est le concept central pour l’analyse OLAP. Le cube de données est constitué de l’union des résultats des requêtes agrégatives Group-By sur toutes les combinaisons possibles des critères d’analyse (ce que l’on nommera par la suite : dimensions). Grâce au pré-calcul du cube, l’utilisateur peut avoir une réponse quasi instantanée à toutes les requêtes qui lui seront utiles. Pour ce faire, le modèle d’analyse OLAP fournit des opérateurs pour résumer les données sous forme d’agrégats (ou au contraire pour détailler les éléments agrégés) et d’opérateurs pour visualiser les informations contenues dans le cube de données. 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 le contexte de notre travail, nous nous intéressons particulièrement aux deux dernières catégories d’opérateurs.

Cependant, à l’inverse de la fouille de données, OLAP ne permet pas d’extraire automatiquement des connaissance (implicites ou explicites) à partir des données [Cha98]. En effet, une des limites de l’OLAP est de se restreindre à des aspects exploratoires et navigationnels. La fouille de données quant à elle, permet d’extraire des connaissances à partir des données et a une grande variété de méthodes avec des objectifs d’analyse différents. Ainsi une nouvelle problématique OLAP a fait son apparition. Dès la fin des années 90, plusieurs travaux [Cha98, Han97, SS01, Sar99, SAM98, GC01, CZC01] proposent d’associer les principes de l’OLAP aux méthodes de fouille de données pour enrichir l’analyse en ligne et ne plus la limiter à une simple exploration ou à une simple visualisation de données. Le couplage entre l’analyse en ligne et la fouille de données est alors désigné par les termes de OLAM (On-Line Analytical Mining) [Han97], OLAP Intelligence, Multidimensional Mining,…

Parallèlement à ces travaux, d’autres équipes de recherche se sont intéressées à l’association de l’OLAP avec des méthodes de recherche d’information. Les premiers travaux remontent au début des années 2000 [MLC00, PP03] et se sont particulièrement focalisés sur la combinaison de l’OLAP avec des techniques d’analyse de documents dans le cadre d’entrepôts de données textuelles. En effet, avec l’avènement des données complexes (données multi-format et/ou multi structure et/ou multi-source, …), l’analyse en ligne doit s’adapter à la nature spécifique de ces données tout en gardant l’esprit de l’OLAP. Ces travaux ouvrent de nouvelles pistes de recherche dans le contexte de l’enrichissement des possibilités de l’analyse OLAP et de l’intégration des connaissances de l’utilisateur dans le processus d’analyse. Nous portons une attention particulière à ces derniers travaux, car dans le contexte de notre étude, nous nous orientons vers une combinaison des principes de l’OLAP et de la recherche d’information et en particulier, de la recherche d’information multi-critères (requêtes skyline), permettant la visualisation et l’extraction de régions intéressantes dans un cube de données. Nous souhaitons, à travers cette approche, guider l’utilisateur vers les informations qui sont susceptibles de l’intéresser et lui permettre d’évaluer la pertinence de ces dernières afin de savoir si elles constituent ou non de nouvelles connaissances.

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

Au cours de ces dernières années, les entrepôts de données ont joué un rôle essentiel 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 dan 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 utilisateurs, 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 diffé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 appliqué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.

Exemple 1 Considérant le modèle multidimensionnel décrit par la Figure.1.1. Le fait Rendement Agricole est représentée par trois dimensions : culture (ici Id-Cult), date (ici Id-Dat) et localisation (ici Id-Loc), et une mesure : rendement de la culture (kg/ha) (ici Rendement-Culture).

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’effectuer 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 afficher les données multidimensionnelles à plusieurs niveaux de granularité. Les valeurs des mesures associées à un niveau de granularité plus grossier 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 diffé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.

Lors de l’analyse multidimensionnelle des données, les utilisateurs exploitent l’entrepôt de données en combinant les différentes dimensions et les différents niveaux de granularité des hiérarchies correspondantes. Pour sélectionner les données appropriées au niveau d’abstraction adéquat, les utilisateurs expriment et soumettent des requêtes à l’entrepôt de données. De telles requêtes sont particulièrement coûteuses car elles demandent le balayage d’important volumes de données. Cependant, ces requêtes s’inscrivent dans un processus d’aide à la décision et idéalement devraient être interactives. Pour concilier ces deux besoins contradictoires, i.e. répondre rapidement à des requêtes portant sur des données volumineuses, Gray et al. [GBLP96] ont introduit le concept de cube de données. C’est un concept central de l’analyse OLAP, pour pré-calculer et matérialiser tous les agrégats possibles. Ainsi, répondre à toute requête se réduit à une simple sélection de résultats préalablement stockés. Un cube de données (ou cube OLAP) est une abstraction des données permettant aux utilisateurs de visualiser des données agrégées selon un ensemble de dimensions hiérarchiques. Les cellules du cube de données contiennent les valeurs des mesures associées aux dimensions et aux niveaux de granularité sélectionnés.

Implémentations 

Une fois le concept d’OLAP et ses propriétés définies, plusieurs implémentations ont été réalisées. Ces implémentations reprennent toutes les concepts OLAP, et chacune est optimisée pour une utilisation particulière d’OLAP. Dans la littérature, ces différentes implémentations peuvent être regroupées en plusieurs catégories : R OLAP (Relational OLAP), M-OLAP (Multidimensionnal OLAP), H-OLAP (Hybrid OLAP), S-OLAP (Spatial OLAP), W-OLAP (Web-based OLAP) et RT-OLAP (Real Time OLAP). Dans ce qui suit, nous nous focaliserons sur les quatre implémentations les plus utilisées et les plus intéressantes pour nos travaux : R OLAP, M-OLAP, H-OLAP et S-OLAP (la partie sur S-OLAP sera développée ultérieurement dans le chapitre 3, section 3.5).

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 IP O-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
Conclusion

Télécharger le rapport complet