Querying Probabilistic OLAP data cubes with hierarchies: models and algorithms

Abstract

On-Line Analytical Processing assumes that every fact occupies a single, fully determined position in the multidimensional space, but large-scale data increasingly violates this premise. This thesis develops the theory of OLAP over data with imprecise dimensions and uncertain measures, relaxing the point-fact assumption so that a fact becomes a region of cells. Two formal accounts of the resulting ambiguity are developed: a probabilistic account via possible-worlds semantics induced by allocation, and a fuzzy account via graded membership and hesitation margins. The treatment covers consistency, faithfulness, and correlation-preservation, together with domain integrity constraints and hierarchy irregularities. A final part analyses the algorithms and their complexity: EM-based allocation, top-k query processing, incremental OLAP, and probabilistic inverse ranking, all unified by replacing exponential world sets with compact linear summaries of weighted claims.***

Le Traitement Analytique En Ligne (OLAP) suppose que chaque fait occupe une position unique et entièrement déterminée dans l’espace multidimensionnel, mais les données à grande échelle violent de plus en plus cette hypothèse. Cette thèse développe la théorie de l’OLAP sur des données aux dimensions imprécises et aux mesures incertaines, en relâchant l’hypothèse de fait ponctuel. Deux comptes formels de l’ambiguïté résultante sont développés : un compte probabiliste via la sémantique des mondes possibles induite par l’allocation, et un compte flou via l’adhésion graduée et les marges d’hésitation. Le traitement couvre la cohérence, la fidélité et la préservation des corrélations, ainsi que les contraintes d’intégrité de domaine et les irrégularités hiérarchiques. Une dernière partie analyse les algorithmes et leur complexité, notamment l’allocation EM, requêtes Top-k, OLAP incrémental et classement inverse probabiliste, tous unifiés par le remplacement des ensembles exponentiels de mondes par des résumés linéaires compacts.