Home

Algèbre XOLAP - Université Lumière Lyon 2

1. Dennis Pedersen Karsten Riis and Torben Bach Pedersen A Powerful and SQL Compatible Data Model and Query Language for OLAP In 13 Australasian Database Conference ADC 02 Melbourne Australia Australian Computer Society 2002 Dennis Pedersen Karsten Riis and Torben Bach Pedersen Query optimization for OLAP XML federations In 5 International Workshop on Data Warehousing and OLAP DOLAP 02 McLean USA pages 57 64 ACM 2002 Stelios Paparizos Yuging Wu Laks V S Lakshmanan and H V Jagadish Tree Logical Classes for Efficient Evaluation of XQuery In SIGMOD International Conference on Management of Data SIGMOD 04 Paris France pages 71 82 ACM 2004 Liam Quin Extensible Markup Language XML http www w3 org XML World Wide Web Consortium W3C 2006 Franck Ravat Olivier Teste and Gilles Zurfluh Mod lisation multidimensionnelle des syst mes d cisionnels In 1 Journ es francophones Extraction et Gestion des Connaissances EGC 01 Nantes France pages 201 212 Herm s 2001 Franck Ravat Olivier Teste and Gilles Zurfluh Alg bre OLAP et langage graphique In 24 Congr s en Informatique des Organisation et Syst mes d Information de D cision INFORSID 06 Hammamet Tunisie pages 1039 1054 2006 Franck Ravat Olivier Teste and Gilles Zurfluh Constraint Based Multi Dimensional Databases pages 323 368 Database Modeling for Industrial Data Management Idea Group Publishing 2006 34 Sho
2. unnesting join expression dues la nature complexe des arbres XML En effet la jointure est d finie par des relations entre identifiants type de n ud contenu de s quences de n uds et non par des cl s comme en relationnel et la position des s quences dans l arbre L valuation d une jointure revient donc comparer des sous arbres Finalement les auteurs d finissent de nouvelles expressions qui permettent la construction de noeuds document element attribute and text node constructors Ces expressions permettent d ajouter de nouveaux n uds l arbre initial ou de cr er un nouvel arbre ou s quence 10 2 2 2 Alg bres sur les arbres de donn es XML La repr sentation des documents XML sous forme d arbres de donn es enracin s et ordonn s plus rarement non ordonn s est d fendue par de nombreux auteurs Dans cette repr sentation la racine du document devient le n ud racine de l arbre et ses l ments fils deviennent les n uds fils de cette racine et ainsi de suite pour le reste des l ments 2 2 2 1 Alg bre pour la recherche d information dans des fragments XML Selon Pradhan trouver un fragment int ressant dans un document XML revient identifier le sous arbre correspondant Pra06 Comme il est possible de parvenir n importe quel n ud en suivant diff rents chemins le fragment recherch doit tre compos d un ensemble de n uds reli s ensemble par le plus proche noeud parent commun Pradh
3. combiner les membres d une dimension aux mesures du cube c est dire faire passer ses membres comme contenu de cellules Ben07 Nous voyons dans la figure 10 comment Agrawal et al expriment la transformation d une dimension en mesure en associant la mesure Sales la dimension cible par l op ration Product La fonction de la transformation d une dimension en mesure affiche les faits d une fa on adapt e la d finition de l op ration elle m me sans modifier les valeurs des mesures Dans un contexte TAX il suffit alors de restructurer les sous arbres faits de mani re adapter la sortie au principe de la transformation d une dimension en mesure Ici et en nous inspirant du 20 travail d Agrawal et al nous associons pour chaque fait la dimension cibl e par l op ration la mesure Soit l exemple de la figure 11 illustrant une transformation de la dimension ville en mesure prix L dedans nous remarquons que le n ud repr sentant la mesure est d velopp de fa on contenir la fois prix et ville comme l ments fils au m me temps Pour r aliser ce but nous avons recours l op ration TAX copier et coller qui prend en entr e un mod le d arbre une liste de copie et une liste de sp cifications Le mod le d arbre permettant de transformer la dimension ville en mesure est disponible dans la figure 12 La liste de sp cifications indique que les arbres ins r s sont les descendants directs du n ud prix 4 da
4. ne se pose pas pour l alg bre pour l ECD car ses op rateurs sont utilis s exclusivement dans des algorithmes d ECD 2 2 5 5 R gles d optimisation Comme une seule requ te XML peut faire appel plusieurs op rateurs afin de calculer le r sultat attendu les r gles d optimisation d signent les r les que prennent ces op rateurs au sein de la requ te Le but d une optimisation est alors de r duire le nombre de r sultats interm diaires et par la suite le nombre d op rateurs utilis s Dans Niagara les deux op rateurs de projection follow unnesting follow et straight follow sont interchangeables Dans ce cas le m me traitement est effectu mais la fa on de repr senter les r sultats est diff rente Les op rateurs de XAL peuvent tre utilis s au sein d un algorithme d optimisation de XQuery propos par les auteurs de cette alg bre Chaque clause XQuery y est vue comme un ou plusieurs op rateurs XAL Dans le cadre de TAX la r gle d optimisation est plus claire avec la traduction des requ tes XQuery en expressions de l alg bre TLC Dans l alg bre de Fern ndez et al plusieurs op rateurs peuvent tre regroup s et g n ralis s dans une fonction qui repr sente elle m me un op rateur ind pendant Selon les auteurs ces fonctions peuvent rendre les requ tes plus modulaires et concises Zhang et al affirment de leur c t que la combinaison des fonctionnalit s de trois types d op rateurs relationnels XML
5. Les donn es XML sont traduites en relationnel avant leur utilisation au sein de ces architectures d int gration Pedersen et al pr conisent galement d int grer des donn es XML et relationnelles au sein d un m me syst me PRPO2b PP03 PPP04 De plus ils proposent une approche pour f d rer des sources de donn es XML avec des cubes OLAP existants Une f d ration se compose d un cube d une collection de documents XML et de liens entre le cube et les documents Un cube 16 multidimensionnel est d crit par son nom et ses tables de dimensions et de faits Chaque dimension est vue comme une hi rarchie de niveaux o chaque niveau est associ un groupe de valeurs dimensionnelles La table de faits est une relation contenant un attribut pour chaque dimension et un attribut pour chaque mesure Ce mod le de cube est associ une alg bre compos e de trois op rateurs L op rateur le plus fondamental dans une f d ration OLAP XML la d coration attache une nouvelle dimension un cube en se basant sur les valeurs des l ments XML li s La s lection sert filtrer les mesures L op rateur de projection g n ralis e generalized projection a pour r le l agr gation des mesures La projection est vue ici comme une op ration de s lection employant une clause de groupement group by Ces op rateurs sont mis en ceuvre sur les donn es OLAP XML l aide une extension de SQLM nomm e SQLXM qui permet d associer des requ
6. bre OLAP Nous les classons en deux familles selon les analogies qu ils pr sentent avec les concepts relationnels et multidimensionnels respectivement 2 1 Alg bres OLAP 2 1 1 Extensions des concepts relationnels 2 1 1 1 Alg bre pour les cubes de donn es Agrawal et al proposent un mod le pour les bases de donn es multidimensionnelles et les op rateurs alg briques li s AGS96 AGS97 Ils mod lisent les cubes multidimensionnels sous forme de rep res trois dimensions et proposent sur cette base une alg bre riche d op rateurs inspir s essentiellement du relationnel dont la sortie repr sente un nouveau cube Con us pour tre traduits en SQL ces op rateurs peuvent tre mis en uvre via un SGBD relationnel ou via un autre moteur supportant les donn es multidimensionnelles L op rateur push transforme une dimension en mesure L op ration r ciproque est assur e par pull L op rateur de destruction d une dimension supprime une dimension d un cube condition que cette derni re ne dispose que d une seule mesure La restriction limine d une dimension les attributs qui ne satisfont pas un pr dicat pr d fini Le principe relationnel de jointure est transcrit en reliant deux cubes via leurs dimensions communes tout en respectant une condition de jointure L op rateur fusion merge permet de r unir deux dimensions d un cube en une seule et de calculer les mesures r sultantes par l interm diaire d une fonction d agr gat
7. cole doctorale Informatique et Information pour la Soci t Master Recherche Informatique de Lyon Sp cialit ECD Extraction des Connaissances partir des Donn es Rapport de stage Alg bre XOLAP analyse en ligne multidimensionnelle des entrep ts de donn es XML Pr par au sein du Laboratoire ERIC Universit Lumi re Lyon 2 BERIC EQI IPE DE RECHERCHE EN INGENIERIE DES CONNAISSANCES R alis par Marouane HACHICHA marouane hachicha Q univ lyon2 fr Sous la direction de M J r me DARMONT M Hadj MAHBOUBI jerome darmont univ lyon2 fr hadj mahboubi Geric univ lyon2 fr 2006 2007 R sum Avec l av nement de XML comme standard de repr sentation de donn es d cisionnelles les entrep ts de donn es XML trouvent leur place dans le d veloppement de solutions d cisionnelles bas es sur le Web Dans ce contexte il devient n cessaire de permettre des analyses OLAP sur des cubes de donn es XML Pour cela des extensions du langage XQuery sont n cessaires Afin de d finir un cadre formel et de permettre l optimisation indispensable des requ tes d cisionnelles exprim es en XQuery la d finition d une alg bre est souhaitable Or les alg bres XML OLAP propos es dans la litt rature d pendent encore largement du mod le relationnel et ne pr sentent qu un nombre d op rateurs OLAP tr s limit En cons quence nous proposons dans ce travail une nouvelle alg bre XOLAP XML OLAP compl te
8. es utilis nous d finissons un sens de lecture standard des donn es XML multidimensionnelles selon les trois modes de repr sentation possibles fichiers XML multidimensionnels cubes XOLAP et arbres TAX multidimensionnels Le sens de lecture pour les deux premi res formes est de haut en bas la mesure est lue en dernier Pour les arbres le sens de lecture est de gauche droite Les axes repr sentant les dimensions suivent un sens de lecture adapt e de haut en bas puis de gauche droite Dans ce qui suit nous pr sentons les diff rents op rateurs de notre alg bre XOLAP Nous mettons en ceuvre chaque op rateur sur les donn es multidimensionnelles de la base ventes cit e dans la section pr c dente et mod lis e en arbres TAX Pour chaque op rateur nous donnons sa d finition originale dans l alg bre OLAP classique et nous l exprimons dans un contexte XOLAP via un ou plusieurs op rateurs TAX Pour cela nous nous sommes bas s essentiellement sur un ensemble de supports de cours sur l OLAP Sho97 Adi05 Van05 Ben07 Gar07 en plus de l alg bre TAX 3 3 2 Op rateurs 3 3 2 1 Op rateurs li s la structure e Rotation rotate La rotation rotate ou pivotement pivot Gar07 permute les dimensions d un cube en lui faisant subir une rotation autour d un de ses axes passant par le centre de deux faces oppos es de mani re pr senter un ensemble de faces diff rents dans le cube Une rotation est une op ration visue
9. issue de l extension de l alg bre XML TAX par des op rateurs OLAP Nous mettons cette contribution en pratique gr ce une interface permettant d exprimer les op rateurs de notre alg bre au sein du syst me de gestion de bases de donn es natif XML TIMBER Abstract With the rise of XML as a standard for representing business data XML data warehouses appear as suitable solutions for Web based decision support applications In this context it is necessary to allow OLAP analyses on XML data cubes Thus XQuery extensions are needed To help define a formal framework and allow much needed performance optimizations on analytical queries expressed in XQuery defining an algebra is desirable However XML OLAP algebras from the literature still largely rely on the relational model and only feature a very small number of OLAP operators Hence we propose in this work a new complete XOLAP XML OLAP algebra that is an extension of the TAX XML algebra by OLAP operators We have also implemented this proposal through an interface that help express our algebra s operators within the TIMBER XML native database management system Table des mati res 1 Introduction 2 Etat de l art 2 1 Alg bres OLAP 2 1 1 Extensions des concepts relationnels 2 1 1 1 Alg bre pour les cubes de donn es 2 1 1 2 Alg bres pour les cubes de donn es relationnels 2 1 1 3 Alg bre pour les cubes vus comme des ensembles de relations 2 1 1 4 Alg bres po
10. l ment de forage L exemple de la figure 29 illustre cela Le forage vers le bas n cessite des donn es suppl mentaires pour sa mise en ceuvre En d autres termes les donn es repr sent es en sortie sont suppos es connues par le manipulateur Dans l exemple pr sent pr c demment les arrondissements de chaque ville ainsi que les mesures correspondantes sont suppos s connues Bien qu il soit l op ration r ciproque du forage vers le haut nous n exprimons pas le forage vers le bas en utilisant le cheminement r ciproque des op rateurs utilis s Nous ne r alisons pas en effet une agr gation suivie d un groupement Gr ce la richesse de TAX nous pouvons utiliser un minimum d op rateurs pour assurer un forage vers le bas comme suit 1 Suppression de n uds La premi re op ration effectuer est de supprimer les arbres repr sentant les faits sous arbres d tailler afin de les substituer par les faits correspondants Une suppression de n uds prend en entr e dans TAX l arbre mod lisant l entrep t un mod le d arbre et une sp cification de suppression indiquant les n uds laguer de l arbre Dans notre exemple l entrep t repr sente la repr sentation en arbres TAX du cube XOLAP de la figure 29 Le mod le d arbre indique le format d arbres supprimer tout en indiquant obligatoirement l attribut l ment de la suppression figure 30 Le signe dans indique que le n ud vente doit tre supprim avec l e
11. lt produit gt Ecran lt produit gt lt annee gt 2006 lt annee gt lt prix gt 160 lt prix gt lt vente gt lt vente gt lt ville gt Paris lt ville gt lt produit gt Souris lt produit gt lt annee gt 2004 lt annee gt lt prix gt 80 lt prix gt lt vente gt lt vente gt lt ville gt Paris lt ville gt lt produit gt Souris lt produit gt lt annee gt 2006 lt annee gt lt prix gt 100 lt prix gt lt vente gt lt vente gt lt ville gt Paris lt ville gt lt produit gt Souris lt produit gt lt annee gt 2006 lt annee gt lt prix gt 100 lt prix gt lt vente gt lt vente gt lt ville gt Paris lt ville gt lt produit gt Clavier lt produit gt lt annee gt 2004 lt annee gt lt prix gt 100 lt prix gt lt vente gt lt vente gt lt ville gt Paris lt ville gt lt produit gt Clavier lt produit gt lt annee gt 2005 lt annee gt lt prix gt 105 lt prix gt lt vente gt lt vente gt lt ville gt Paris lt ville gt lt produit gt Clavier lt produit gt lt annee gt 2006 lt annee gt lt prix gt 107 lt prix gt lt vente gt lt ventes gt Figure 34 R sultat d un d coupage de l entrep t XML ventes en tranche avec XQuery 59 XOLAP Forage vers le haut Roll Up Mozilla Firefox Fichier Edition Affichage Historique Marque pages Outils X D E hitpilftz7 0 0 1 erojet XOLAP roluplforageverslehaut htm D marrage
12. qu un fait est compos d une ou plusieurs mesures valeurs num riques et des dimensions qui les d crivent Par cons quence les occurrences d un m me l ment du fichier XML multidimensionnel 18 mod lisent un fait Les sous l ments de chaque fait XML repr sentent alors ses dimensions et ses mesures Un exemple d un fait XML vente de l entrep t ventes est disponible dans la figure 1 Les fichiers XML multidimensionnelles sont mod lisables en cubes OLAP que nous appelons cubes XOLAP et en arbres TAX puisque ces derniers mod lisent tout fichier XML Les cubes XOLAP comme les cubes OLAP sont vus sous la forme de n axes o chaque axe mod lise une dimension dans un rep re n dimensionnel Chaque document XML multidimensionnel peut tre traduit la fois en arbre TAX et en cube XOLAP Nous pouvons aussi repr senter des donn es sous ces deux formes en fichiers XML multidimensionnels Une transformation des arbres TAX repr sentant des donn es XML multidimensionnelles en cubes XOLAP est donc possible et vice versa Comme nous choisissons d tendre TAX par des op rateurs OLAP nous adoptons le mod le de donn es utilis par Jagadish et al JLSTO1 les arbres TAX pour les donn es XML multidimensionnelles Dans un arbre TAX mod lisant un fichier XML multidimensionnel que nous appelons aussi un arbre TAX multidimensionnel chaque sous arbre repr sente un fait sous l ment Nous utilisons l exemple suivant dans le reste d
13. s la structure 3 3 2 2 Op rateurs ensemblistes 3 3 2 3 Op rateurs li s la granularit 3 4 Discussion 3 4 1 R gles d optimisation dans notre alg bre 3 4 Conformit entre notre alg bre XOLAP et l alg bre OLAP classique 3 5 Mise en pratique de notre alg bre XOLAP 3 5 1 Recours TIMBER 3 5 2 Mise en pratique de notre alg bre 3 5 2 1 Principe de l application 3 5 2 2 Op rateurs impl ment s 3 5 2 3 Op rateurs en cours d impl mentation 3 5 2 4 Limitations de XQuery rencontr es Conclusion Bibliographie Annexes 1 Introduction Les technologies d cisionnelles telles que les entrep ts de donn es et l analyse en ligne OLAP On Line Analytical Processing sont d sormais technologiquement matures Cependant leur complexit les rend peu attractives pour de nombreux utilisateurs potentiels et les diteurs de solutions d cisionnelles commencent d velopper des interfaces Web simples et conviviales Law06 De plus de nombreuses applications d cisionnelles n cessitent des sources de donn es externes l organisme qui les exploite Par exemple mener une veille concurrentielle au sein d une entreprise requiert l analyse de donn es uniquement disponibles aupr s de ses concurrentes Dans ce contexte le Web est une source de donn es extr mement riche On parle notamment de Web farming Hac99 En cons quence une nouvelle tendance l entreposage de donn es en ligne se d gage avec des approches telles que l entr
14. tach s d une facon adapt e la d finition du forage vers le haut Le groupement est r alis suivant toutes les combinaisons possibles des attributs des dimensions autres que celle du forage Le groupement prend en entr e les arbres issus de la s lection un mod le de groupement une fonction de groupement et une fonction d ordre de valeur d arbre Le mod le de groupement pr cise que cette op ration est assur e par les attributs de la dimension autres que celle du forage ann e dans notre cas Le mod le correspondant est disponible dans la figure 23 La fonction de groupement pr cise l ordre des l ments dans les sous arbres du r sultat La fonction d ordre indique l ordre que prennent ces sous arbres Dans notre exemple l ordre des sous arbres ainsi que de leurs n uds est bien l ordre d part La figure 24 montre un exemple de groupement des ventes par ville et produit Au total nous obtenons neufs arbres selon toutes les combinaisons des valeurs possibles ville produit Avant de passer l tape suivante il faut faire une s lection de tous les sous arbres selon un mod le qui prend comme racine fax group subroot 25 3 Jointure Pour chaque sous arbre fax group subroot exprimant un groupement nous r alisons une jointure TAX des trois sous arbres correspondants en un seul arbre selon le mod le de la figure 25 Le r sultat de jointure des arbres de la figure 24 est pr sent dans la figure 26 Il suffit ensuite de s l
15. uds repr sentant les futurs descendants du n ud ins r 2 2 2 3 Alg bre XAL Frasincar et al auteurs de l alg bre XAL XML Algebra adoptent galement la repr sentation des documents XML sous forme d arbres et plus g n ralement de graphes FHP02 XAL comprend trois familles d op rateurs Les op rateurs d extraction recherchent l information n cessaire dans les graphes XML et renvoient la collection de sommets correspondante La projection la s lection la distinction distinct la jointure le d sordonnancement unorder et le tri sort constituent l ensemble de ces op rateurs Ils s appliquent sur des graphes Les quatre premiers ne pr sentent pas de diff rence avec les op rateurs TAX En revanche le d sordonnancement permet de d sorganiser une collection en entr e tandis que le tri transforme une collection suivant un mod le donn Les m ta op rateurs contr lent l valuation des expressions Ce ne sont pas de v ritables op rateurs au sens de la cr ation ou de l extraction d l ments de donn es Ils sont plut t utilis s pour exprimer des r p titions au niveau des op rateurs ou des entr es Map applique une fonction pr d finie sur chaque l ment de la collection d entr e L effet de cette fonction se r v le dans la collection de sortie Kleene Star r p te une fonction ind finiment pour une collection d entr e donn e chaque it ration le r sultat est ajout en entr e de la fonction s
16. Derni res nouvelles R sultats de la reche Google lt 4 C Rechercher 9 PageRank A Orthographe A s abonner fed options amp Choisir les dimensions l ments de groupement multiple O Ville O Produit Ann e Prix Prix Choisir la dimension l ment de jointure C Ville O Produit Ann e Choisir la fonction d agr gation C Somme Sum CI Moyenne Avg G n rer la requ te XQuery SE demarrer E Zl rapp4 doc Wi liste de figu C AnnexeFIN i conclusion AdobeReader 3 Fermer sess Figure 35 Mise du forage vers le haut en pratique 60 ventes vente ville Paris ville lt pdt gt Ecran lt pdt gt lt temps gt Temps lt temps gt lt prix gt 385 lt prix gt lt vente gt lt vente gt lt ville gt Paris lt ville gt lt pdt gt Souris lt pdt gt lt temps gt Temps lt temps gt lt prix gt 270 lt prix gt lt vente gt lt vente gt lt ville gt Paris lt ville gt lt pdt gt Clavier lt pdt gt lt temps gt Temps lt temps gt lt prix gt 3 12 lt prix gt lt vente gt lt vente gt lt ville gt Lyon lt ville gt lt pdt gt Ecran lt pdt gt lt temps gt Temps lt temps gt lt prix gt 382 lt prix gt lt vente gt lt vente gt lt ville gt Lyon lt ville gt lt pdt gt Souris lt pdt gt lt temps gt Temps lt temps gt lt prix gt 29
17. Diego USA page 671 ACM 2003 Xin Zhang Bradford Pielech and Elke A Rundesnteiner Honey I shrunk the XQuery an XML algebra optimization approach In 4 International Workshop on Web Information and Data Management WIDM 02 McLean USA pages 15 22 ACM 2002 Ji Zhang Wei Wang Han Liu and Sheng Zhang X warehouse building query pattern driven data In 14 International Conference on World Wide Web WWW 05 Chiba Japan pages 896 897 ACM 2005 M Zhang and J T Yao XML Algebras for Data Mining In Data Mining and Knowledge Discovery Theory Tools and Technology VI Orlando USA volume 5433 of SPIE proceedings series pages 209 217 SPIE 2004 35 36 Annexes vente lt ville gt Paris lt ville gt lt produit gt Souris lt produit gt lt annee gt 2004 lt annee gt lt prix gt 70 lt prix gt lt vente gt Figure 1 Fait XML vente de l entrep t ventes vente lt vente gt pas ville Lyon ville2 Ecran produit Ecran produit c lt annee gt 2005 lt annee gt 2005 lt prix gt 150 lt prix gt lt vente gt ville produit annee prix Lyon Ecran 2005 150 Figure 2 Fait XML vente sous ses trois pr sentations fichier XML multidimensionnel cellule XOLAP et arbre TAX multidimensionnel Paris Lyon Nice Ecran Souris Clavier 2004 2005 2006 Figure 3 Structure du cube XOLAP repr sentant l entrep t de donn es XML ventes 37 Paris Lyon Nice 2004 2005 200
18. Miami USA pages 370 373 2005 C J Date and Hugh Darwen A Guide to SQL Standard 4th Edition Addison Wesley 1997 Alin Deutsch Mary Fern ndez Daniela Florescu Alon Levy and Dan Suciu XML QL A Query Language for XML http www w3 org TR NOTE xml ql World Wide Web Consortium W3C 1998 Anindya Datta and Helen Thomas The cube data model a conceptual model and algebra for on line analytical processing in data warehouses Decision Support Systems 27 3 289 301 1999 Flavius Frasincar Geert Jan Houben and Cristian Pau XAL an Algebra for XML Query Optimization In 13 Australasian Database Conference ADC 02 Melbourne Australia volume 5 of CRPIT Australian Computer Society 2002 Leonidas Fegaras David Levine Sujoe Bose and Vamsi Chaluvadi Query processing of streamed XML data In 11 International Conference on Information and Knowledge Management CIKM 02 McLean USA pages 126 133 ACM 2002 Mary F Fern ndez J r me Sim on and Philip Wadler An Algebra for XML Query In 20 Conference on Foundations of Software Technology and Theoretical Computer Science FSTTCS 00 New Delhi India volume 1974 of Lecture Notes in Computer Science pages 11 45 Springer 2000 Georges Gardarin Data warehouse Support de cours Universit de Versailles Saint Quentin en Y velines France 2007 Jim Gray Adam Bosworth Andrew Layman and Hamid Pirahesh Data Cube A Relational Aggregation Operator Generalizi
19. Michel Adiba Entrep ts de donn es Fouille de Donn es Support de cours Master SI Universit de Grenoble France 2004 2005 Rakesh Agrawal Ashish Gupta and Sunita Sarawagi Modeling Multidimensional Databases Technical report IBM Almaden Research Center San Jose USA 1996 Rakesh Agrawal Ashish Gupta and Sunita Sarawagi Modeling Multidimensional databases In 13 International Conference on Data Engineering ICDE 97 Birmingham UK pages 232 243 IEEE Computer Society 1997 Xavier Baril and Zohra Bellahs ne Designing and Managing an XML Warehouse pages 455 473 XML Data Management Native XML and XML enabled Database Systems Addison Wesley 2003 Vinayak R Borkar and Michael J Carey Extending XQuery for Grouping Duplicate Elimination and Outer Joins In XML 2004 Washington DC USA pages 1 11 November 2004 Kevin S Beyer Donald D Chamberlin Latha S Colby Fatma Ozcan Hamid Pirahesh and Yu Xu Extending XQuery for Analytics In ACM SIGMOD International Conference on Management of Data SIGMOD 05 Baltimore USA pages 503 514 ACM 2005 Scott Boag Don Chamberlin Mary F Fernandez Daniela Florescu Jonathan Robie and J r me Sim on XQuery 1 0 An XML Query Language http www w3 org TR xquery World Wide Web Consortium W3C 2007 David Belanger Kenneth Ward Church and Andrew Hume Virtual Data Warehousing Data Publishing and Call Detail In International Workshop on Databases in Telecommu
20. Native System for Querying XML In 2003 ACM SIGMOD International Conference on Management of Data SIGMOD 03 San Diego USA page 672 ACM 2003 Stelios Paparizos Shurug Al Khalifa H V Jagadish Andrew Nierman and Yuging Wu A physical algebra for XML Technical report University of Michigan USA 2002 Byung Kwon Park Hyoil Han and Il Yeol Song XML OLAP A Multidimensional Analysis Framework for XML Warehouses In 7 International Conference on Data Warehousing and Knowledge Discovery DaWaK 05 Copenhagen Denmark volume 3589 of Lecture Notes in Computer Science pages 32 42 Springer 2005 Jaroslav Pokorny XML Data Warehouse Modelling and Querying In 5 International Baltic Conference BalticDB amp IS 02 Tallin Estonia pages 267 280 Institute of Cybernetics at Tallin Technical University 2002 Dennis Pedersen and Torben Bach Pedersen Achieving adaptivity for OLAP XML federations In 6 International Workshop on Data Warehousing and OLAP DOLAP 03 New Orleans USA pages 25 32 ACM 2003 Dennis Pedersen Jesper Pedersen and Torben Bach Pedersen Integrating XML Data in the TARGIT OLAP System In 20 International Conference on Data Engineering ICDE 2004 Boston USA pages 778 781 IEEE Computer Society 2004 Sujeet Pradhan An Algebraic Query Model for Effective and Efficient Retrieval of XML Fragments In 32 International Conference on Very Large Data Bases VLDB 06 Seoul Korea pages 295 306 ACM 2006
21. Un type est un l ment incluant d autres l ments comme la racine d un document XML Une variable globale repr sente une instance du document XML Cette alg bre comprend de nombreux op rateurs dont le plus simple est la projection puisqu il suffit de pr ciser le chemin de l l ment recherch de fa on similaire XPath Le deuxi me op rateur l it ration consiste parcourir les l ments indiqu s dans le chemin employ via une boucle for It rer revient alors associer une projection au for Cette association constitue la base des quatre op rateurs suivants Une s lection est possible en associant une clause where une it ration L op rateur suivant la quantification vise s lectionner les l ments d un type quelconque ayant des sous l ments communs Pour joindre des l ments d un ou plusieurs documents jointure il suffit d imbriquer des boucles for Le nombre de boucles for utilis es correspond au nombre de sources types joindre en un seul l ment Le r sultat est donn selon l ordre d imbrication Une clause where peut tre employ e pour conditionner cette op ration Le quatri amp me op rateur suivant cette logique la restructuration regroupe diff rents l ments dans un seul document XML selon une ou plusieurs conditions Des clauses for et where sont employ es afin d atteindre cet objectif De plus la fonction distinct est utilis e pour viter les redondances comme dans le cas relatio
22. cf Section 3 3 1 N d signe le nombre d axes repr sentants le cube Dans notre cas trois forages vers le haut sont effectu s suivant les axes dimensions produit ann e et ville L agr gation choisie dans les trois forages est somme Le r sultat final des trois forages vers le haut est disponible dans la figure 32 2 2 Groupements agr gations et jointures Pour chaque r sultat du forage vers le haut nous r alisons un groupement pour tous les attributs des dimensions participant ce forage Par exemple pour le r sultat du forage vers le haut suivant l axe produit nous r alisons les groupements suivants deux groupements par ville un pour l ann e 2003 et l autre pour 2004 et deux autres groupements par ann e et par ville Paris et puis Lyon Dans les diff rents groupements nous conservons la m me fonction d agr gation somme ici Les r sultats des groupements sont explicit s dans la figure 32 3 Par exemple l arbre v2 repr sente le r sultat du groupement des produits Ecran par ville pour les ann es 2003 et 2004 Les autres arbres de v22 jusqu v32 suivent aussi cette logique La mesure du fait v21 400 est la somme de 210 et 190 les valeurs des mesures des arbres v9 et v10 respectivement ce qui d montre la validit de notre d marche jusqu ici Dans TAX pour chaque groupement l arbre mod le sp cifie les deux dimensions l ments du groupement Nous sommons ensuite pour chaque arbre r sultant du gro
23. d part Figure 32 2 Trois forages vers le haut sur notre cube initial 55 Paris Lyon E 210 190 cran vo v10 140 145 Souris vil v12 350 335 v23 v24 2003 2004 E 190 210 cran TS vid 130 155 Souris v15 v16 320 365 v27 v28 Paris Lyon 160 160 v19 v20 2004 190 175 350 335 v31 v32 v21 v9 v10 v22 v11 v12 v23 v9 v11 v24 v10 v12 v25 v13 v14 v26 v15 v16 v27 v13 v15 v28 v14 16 v29 v17 v18 v30 v19 v20 v31 v17 v19 v32 v18 v20 Figure 32 3 Diff rentes agr gations 56 685 350 335 Souris Figure 32 4 Diff rentes parties du cube final Figure 32 Construction de cube de donn es avec TAX 34 vente vente ville Paris ville lt annee gt 2004 lt annee gt lt produit gt Ecran lt produit gt lt produit gt Ecran lt produit gt lt annee gt 2004 lt annee gt lt ville gt Paris lt ville gt lt prix gt 125 lt prix gt lt prix gt 125 lt prix gt lt vente gt lt vente gt Figure 33 R sultat d une rotation d un fait XML vente avec XQuery 58 ventes vente lt ville gt Paris lt ville gt lt produit gt Ecran lt produit gt lt annee gt 2004 lt annee gt lt prix gt 125 lt prix gt lt vente gt lt vente gt lt ville gt Paris lt ville gt lt produit gt Ecran lt produit gt lt annee gt 2005 lt annee gt lt prix gt 100 lt prix gt lt vente gt lt vente gt lt ville gt Paris lt ville gt
24. d tachement d un d du cube avec TAX nous s lectionnons les sous arbres correspondants aux faits repr sentants le d extraire Nous exprimons cette op ration par une s lection TAX de tout sous arbre fait repr sentant une cellule Cette s lection prend en entr e l arbre base initial l arbre mod le de la figure 20 et une liste de s lections contenant le n ud vente pour conserver ses descendants Les clauses OR utilis es dans ce mod le n existent dans un aucun mod le de l alg bre TAX Pourtant Jagadish et al emploient une clause BEFORE dans un mod le de leur travail JLSTO1 D sormais ils ont pu utiliser une clause AFTER par exemple la place de BEFORE en inversant juste l ordre de param tres correspondants Si OR n est pas employ e au mod le de la figure 20 nous avons recours plusieurs mod les la fois l issue de la s lection nous obtenons les huit arbres quivalents aux huit cellules du d de la figure 19 Il reste alors les r unir sous une m me racine ventes avec une production TAX 22 3 3 2 3 Op rateurs li s la granularit Les op rateurs li s la granularit consid rent dans leur logique les hi rarchies des dimensions en repr sentant les donn es multidimensionnelles La granularit d une dimension d signe le nombre de niveaux hi rarchiques qu elle puisse repr sent e cette dimension Van05 e Forage vers le haut roll up Le forage vers le haut roll up repr sent
25. de donn es des documents XML classiquement un arbre plus g n ralement un graphe ainsi qu les enrichir de nouveaux op rateurs sp cifiquement adapt s au contexte XML si possible Les travaux existants qui tendent vers XOLAP cf Section 2 3 ne satisfont pas nos objectifs Ils privil gient en effet la traduction des cubes XML en relationnel et leur interrogation avec des extensions du langage SQL alors que nous tendons vers une solution native XML exploitant le langage XQuery pour l interrogation De plus ces travaux ne proposent en termes d alg bre qu un nombre d op rateurs tr s limit C est pourquoi nous d finissons une nouvelle alg bre XOLAP XML OLAP issue de l extension d une alg bre XML par les op rateurs OLAP classiques construction de cube cube rotation rotate permutation d une modalit dans une dimension switch forage vers le haut ou vers le bas roll up ou drill down s lection et projection sur un cube slice et dice transformation d une mesure en dimension ou d une dimension en mesure pull ou push L alg bre XML choisie est bien TAX cf Section 2 2 2 2 pour des raisons que nous expliquons dans la section suivante En deuxi me lieu nous essayons de mettre notre contribution en pratique gr ce une interface permettant d exprimer les op rateurs de notre alg bre en g n rant les requ tes XQuery correspondantes appel es aussi des requ tes XQuery d cisionnelles qui seront ex cut es au sein d
26. des op rateurs Les op rateurs traditionnels propos s sont l union la diff rence le produit cart sien le renommage la projection et la s lection Ces derniers fonctionnent de la m me fa on que leurs quivalents en alg bre relationnelle D autres op rateurs de restructuration sont propos s le groupement grouping la fusion merging l clatement spliting et la compression collapsing Le groupement et la fusion respectivement l clatement et la compression peuvent tre vus comme l inverse l un de l autre Le groupement permet de r unir dans un tableau les informations selon un certain attribut La fusion effectue l op ration r ciproque L clatement permet de transformer une table en plusieurs Par contre la compression fusionne un ensemble de tables en un seul Il est clair alors que groupement et fusion sont deux op rateurs qui manipulent essentiellement les donn es alors qu clatement et compression manipulent leur structure Gr ce l op rateur de transposition transposing il est possible d exprimer pour toute op ration sur les lignes d une matrice une op ration similaire sur ses colonnes Finalement afin d offrir une meilleure repr sentation des donn es la suppression des redondances clean up limine dans une table les valeurs nulles 2 1 2 2 Alg bre pour les informations r parties en niveaux Cabibbo et Torlone proposent un mod le logique des syst mes OLAP pour la conception des bases de do
27. est pas efficace et nous envisageons d optimiser ce processus dans des travaux futurs 29 4 Conclusion et perspectives Nous avons d fini dans ce m moire le cadre formel d une nouvelle alg bre XOLAP qui permet d ex cuter des requ tes analytiques OLAP sur des donn es multidimensionnelles stock es dans des documents XML Ces travaux se basent sur un tat de l art que nous avons voulu le plus exhaustif possible et qui traite des alg bres OLAP des alg bres XML et des premiers travaux concernant des approches XML OLAP Cette partie de notre m moire a fait l objet d une soumission d article survey la conf rence Bases de Donn es Avanc es BDA 2007 Afin de d finir notre alg bre XOLAP nous avons tendu l alg bre XML TAX par les op rateurs OLAP les plus couramment utilis s et cit s dans la litt rature cube rotate switch roll up drill down slice dice pull et push De plus ce travail nous a galement amen s formaliser des notions indispensables comme les fichiers XML multidimensionnels les cubes XOLAP et les arbres TAX multidimensionnels Finalement nous avons con u un prototype logiciel qui met en uvre nos op rateurs XOLAP et permet de g n rer le code XQuery correspondant Cette interface d interrogation s appuie actuellement sur le SGBD XML natif TIMBER qui impl mente l alg bre TAX et ses d riv es mais elle en est totalement ind pendante et pourrait fonctionner avec tout autre SGBD XML supportan
28. figure 6 e Changement de position des modalit s dans une dimension switch L op ration de changement de position des modalit s dans une dimension switch consiste interchanger les positions de deux ou plusieurs attributs au sein d une m me dimension De m me que la rotation cette op ration se caract rise par un effet visuel en r sultat puisque les valeurs des mesures ne changent pas avec le changement de position des faits correspondants Un exemple de changement de position des modalit s dans une dimension dans notre cube XOLAP initial est disponible dans la figure 7 Nous y permutons les attributs Nice et Lyon de la dimension ville En respectant le sens de lecture des donn es XOLAP que nous avons d fini et quelle que soit la forme de leur pr sentation multidimensionnelle nous pr sentons trois fragments de donn es XML inspir s du cube pr c dent et les arbres correspondants dans la figure 8 Pour r aliser un changement de position des modalit s dans une dimension en utilisant TAX il suffit de r ordonner les sous arbres de l arbre TAX multidimensionnel en sortie L op rateur de r ordonnancement TAX parait le mieux adapt pour atteindre cet objectif Le r ordonnancement prend en entr e la collection d arbres mod lisant les donn es un mod le d arbre une fonction de valeur d arbre et une liste de r ordonnancement Le mod le d arbre pr cise les noeuds r ordonner L ordre que prennent ces n uds est indiqu da
29. la projection consiste rechercher les entit s en entr e de l op rateur qui correspondent un mod le d fini en s lectionnant les attributs cit s dans la liste de projection La projection n existe pas dans l alg bre de Pradhan Par ailleurs nous soulignons l importance de certains op rateurs sp cifiques XML comme ceux propos s par Fern ndez et al qui s expriment par des chemins de type XPath par Novak et Zamulin qui sont li s aux expressions FLWOR de XQuery ou aussi par 15 Zhang et al ou encore copier et coller dans TAX sommet dans Niagara et les op rateurs de construction de XAL Les op rateurs pour l ECD sont galement originaux et agissent sur les arbres plut t que sur les donn es 2 2 5 4 Expressivit Puisque le but d une alg bre XML est de repr senter des requ tes utilisateurs gr ce ses op rateurs elle est jug e plus performante si elle peut tre exprim e dans divers langages de requ tes XML TAX sort du lot selon ce crit re car elle est support e par la plupart des langages de requ tes XML tels que XQuery ou XML QL DFF 98 Les op rateurs de Niagara sont exprim s en Quilt CRF00 XAL et les alg bres respectives de Pradhan Bose et al Zhang et al ainsi que le bin me Novak et Zamulin supportent les requ tes XQuery L alg bre de Fern ndez et al constitue un cas particulier puisqu elle est elle m me congue comme un langage de requ tes XML Finalement la question de l expressivit
30. le cas g n ral de toute op ration de projection dans l alg bre relationnelle comme dans l alg bre multidimensionnelle C est principalement pour toutes ces raisons que nous n avons pas adopt s lection ni m me projection pour nommer cette op ration Dans l exemple de la figure 16 nous voyons qu un d coupage de cube en tranches carte du r sultat l ensemble des tranches non vis es par l analyse Autrement dit un tel op rateur lague du r sultat l ensemble de faits en commun entre les attributs dimensionnels de l axe lequel appartient l attribut dimensionnel selon lequel se r alise la coupe sauf ce dernier et tous les autres attributs des autres axes Nous tendons TAX par l op rateur de d coupage en tranches de cubes en tranches comme suit L objectif est l extraction depuis l arbre initial des sous arbres correspondants l ensemble de tranches vis es par l op ration L arbre repr sentant le r sultat de d coupage de l arbre de la figure 16 en tranches est disponible dans la figure 17 Un d coupage de cube en tranches avec TAX est assur en s lectionnant tous les faits correspondants aux tranches conserver Ici la s lection TAX prend en entr e l arbre mod lisant la base un arbre mod le et une liste de param tres Puisque la coupe se r alise suivant un ou plusieurs attributs d une seule dimension il suffit de les indiquer dans l arbre mod le Par exemple pour atteindre le r sultat de la figure 17 l att
31. le serveur Les auteurs se basent sur un de leurs travaux pr alables une alg bre pour les donn es XML non fragment es stock es sur une seule machine FLBCO2 Son premier op rateur est l extraction qui retourne une liste de singletons dont l unique l ment contient l arbre XML entier La s lection la projection la fusion merging et la jointure suivent la m me logique que leurs quivalents en relationnel Deux op rateurs de parcours de chemins dans les documents XML nest et unnest sont aussi inspir s de l alg bre relationnelle La r duction reduce produit le r sultat final d une requ te utilisant des fonctions d agr gation count par exemple Ces trois derniers op rateurs fonctionnent sur la base de l op ration associative binaire 4 pour additionner les l ments d un ensemble et les r duire en un seul Dans la deuxi me alg bre propos e par les auteurs pour les donn es XML fragment es ces op rateurs sont repris et enrichis BFLCO3 L extraction consiste extraire les fragments partir du flux de donn es et les identifier via une variable de gamme L op rateur de s lection filtre les fragments dans le flux selon une condition La projection s lectionne les attributs partir d un n uplet du flux de donn es en entr e La fusion assure la r union des n uplets de deux flux d entr e en un seul sans liminer les doublons Une jointure est possible entre les fragments de deux flux de donn es diff r
32. lt annee gt 2005 lt annee gt lt prix gt 150 lt prix gt lt vente gt lt ventes gt lt ventes gt lt vente gt lt ville gt Paris lt ville gt lt produit gt Ecran lt produit gt lt annee gt 2005 lt annee gt lt prix gt 160 lt prix gt lt vente gt lt vente gt lt ville gt Lyon lt ville gt lt produit gt Ecran lt produit gt lt annee gt 2005 lt annee gt lt prix gt 150 lt prix gt lt vente gt lt vente gt lt ville gt Nice lt ville gt lt produit gt Ecran lt produit gt lt annee gt 2005 lt annee gt lt prix gt 140 lt prix gt lt vente gt lt ventes gt n ventes ville produit ann e prix ville produit ann e prix ville produit nn e prix Paris Ecran 2004 160 Lyon Ecran 2004 150 Nice Ecran 2004 140 ville produit ann e prix ville produit ann e prix ville produit ann e Prix Paris Ecran 2004 160 Nice Ecran 2004 140 Lyon Ecran 2004 150 Figure 8 Changement de position des modalit s dans une dimension sous les trois formes fichier XML multidimensionnel cellule XOLAP et arbre TAX multidimensionnel 40 xls i x2 x3 3 x4 4 x5 x6 x7 x8 x9 x10 x11 x12 x13 xl4 x15 x16 Arbre mod le 1 2 3 4 Liste de r ordonnancement f x1 ventes f x2 f x3 f x4 vente f x5 Paris f x9 Lyon f x13 Nice Diff rents valeurs que prend la fonction de valeur d arbre Figure 9 El ments en entr e du r
33. ordonnancement TAX pour r aliser un changement de positions des modalit s dans une dimension 41 Date lt Sales Product gt lt Sales gt ei dard 15 gt lt 10 gt Sales mar 4 15 p1 10 p3 2 lt 15 p2 gt 20 p4 gt feb 3 20 gt lt 15 gt 15 lt 20 gt product feb3 lt 0p1 gt lt 15p3 gt 7 feb 2 10 lt 15 gt feb 2 lt 10p2 gt lt 15 p3 gt jan 1 T 10 20 gt lt 25 gt jan 1 10 p1 gt lt 20 p3 gt lt 25 p4 gt Product pl p pi p4 pl p2 p3 p4 Product Figure 10 Transformation d une mesure en dimension dans l alg bre d Agrawal et al AGS96 AGS97 vente ville produit ann e Paris Souris 2003 prix ville 50 Paris Figure 11 Transformation d une mesure en dimension avec TAX 1 1 tag ventes 2 tag vente 3 tag 5 tag ville 3 content 5 content 4 tag 6 tag prix 4 content 6 content 3 4 5 6 Figure 12 Mod le d arbre pour l op ration TAX copier et coller 42 vente ville Lyon ville2 produit Ecran produit lt annee gt 2005 lt annee gt lt prix gt 150 lt prix gt lt vente gt Lyon Ecran Z 150 2005 vente AIS ville produit annee prix Lyon Ecran 2005 150 Lyon Ecran 2005 lt vente gt lt ville gt Lyon lt ville gt lt produit gt Ecran lt produit gt lt annee gt 2005 lt annee gt lt prix gt lt ville gt Lyon lt ville gt lt prix gt 150 lt prix gt lt prix gt lt v
34. relationnelle JL STO1 Pour d finir les arbres XML les auteurs s inspirent de DOM Document Object Model HWW06 et mod lisent chaque n ud par une paire attribut valeur partir d une racine unique chaque occurrence d un l ment fils repr sente un sous arbre s par La descente dans la hi rarchie utilise le m me principe Jagadish et al introduisent galement des mod les d arbres pattern trees que doivent suivre les arbres en sortie des requ tes d nomm s arbres t moins witness trees Dans TAX la s lection retourne un arbre t moin satisfaisant le pr dicat indiqu dans le mod le d arbre En entr e de cet op rateur nous trouvons l arbre mod lisant la base le mod le et une liste de param tres La sortie repr sente la correspondance entre la base et le mod le en tenant compte des l ments en param tres La projection est similaire la s lection dans le sens qu elle retourne les n uds non sp cifi s dans l ensemble d entr e Bien qu ils fonctionnent sur le m me principe projection et s lection sont deux op rateurs compl tement diff rents ind pendants et surtout non orthogonaux au contraire du cas relationnel les arbres n ont pas une structure faite de lignes et de colonnes Le produit prend en entr e deux collections d arbres C et D pour produire en sortie une juxtaposition des diff rentes paires de fragments possibles Comme dans le cas relationnel l ordre est tr s important ici car C D est d
35. ses axes dimension Dans notre alg bre nous r ordonnons les dimensions cibl es par cette op ration autour de l axe de rotation dans le fichier XML multidimensionnel final Pour atteindre ce but pratiquement l interface permet l analyste de choisir apr s la visualisation de son cube l axe la dimension de rotation Il ne reste pour l utilisateur qu cliquer sur un bouton Effectuer une rotation pour g n rer la requ te XQuery Un t l chargement suivi d une ex cution de cette requ te sur notre entrep t de donn es XML avec TIMBER g n re le fichier XML de la figure 33 e D coupage de cube en tranches slice Par principe le d coupage de cube en tranches d tache une ou plusieurs tranches d un cube suivant un ou plusieurs attributs d une m me dimension Dans l interface impl ment e ainsi que dans la requ te XQuery g n r e nous suivons cette logique Gr ce notre interface l utilisateur peut choisir les attributs sur lesquels effectuer la coupe La seule condition que nous imposons aux utilisateurs est que l ensemble des attributs s lectionn s doit appartenir une m me dimension La requ te XQuery g n r e partir de cette interface s lectionne les faits des fichiers XML multidimensionnels selon les attributs Le r sultat d une l ex cution de cette op ration qui d coupe ventes en tranches vente suivant la ville Paris est disponible dans la figure 34 e Forage vers le haut Roll up Un forag
36. un SGBD natif XML 3 2 Justification du choix de TAX Face au grand nombre d alg bres XML propos es dans la litt rature notre choix s est port sur TAX Notre motivation principale provient de la richesse de cette alg bre qui comprend sous ses formes logique et physique plus qu une vingtaine d op rateurs Cela nous offre une grande libert pour les combiner et exprimer les diff rents op rateurs OLAP que nous souhaitons mettre en ceuvre De plus l expressivit de TAX est largement reconnue puisque cette alg bre peut tre exprim e avec la majorit des langages de requ tes XML et notamment XQuery qui est le langage que nous ciblons pour des analyses OLAP Enfin TAX et son alg bre d riv e TLC fournissent un cadre d optimisation de requ tes que nous pourrons exploiter car la performance est un de nos principaux soucis pour des applications d cisionnelles int gralement bas es sur XML et XQuery 3 3 Alg bre XOLAP 3 3 1 Mod le de donn es Avant d exposer notre alg bre XOLAP et comme pour les alg bres tudi es dans l tat de l art nous commen ons par pr senter le mod le de donn es sous jacent qui est logiquement inspir de celui de TAX Nous nommons un fichier XML mod lisant des donn es multidimensionnelles connu aussi sous le nom d un entrep t de donn es XML un fichier XML multidimensionnel Normalement la mod lisation d une table de faits ou d un fait avec XML ne pose pas de probl me Nous rappelons
37. une cellule quivalente dans le cube de la figure 28 e Construction de cube cube Dans un premier travail Gray et al d finissent l op rateur cube de donn es data cube ou construction de cube cube comme un op rateur relationnel g n ralisant le groupement group by le produit de tables cross tab et le forage vers le haut roll up GBLP96 Un an plus tard ils assimilent cube de donn es data cube un op rateur d agr gation relationnel g n ralisant le groupement group by le produit des tables cross tab et les sous totaux sub totals GCB 97 Les sous totaux d signent en g n ral les agr gations utilis es dans le forage vers le haut c est dire les totaux ou le forage vers le bas ici nous utilisons les sous totaux Cube groupe les r sultats de diff rentes agr gations r alis es sur un cube en tenant compte de tous les niveaux de granularit possibles des donn es de ce cube L utilisation du produit des tables jointure permet d avoir un cube plus grand groupant les r sultats et les agr gations appliqu es Nous exprimons cube avec TAX gr ce l enchainement des op rateurs suivants Ces diff rentes tapes sont illustr es la figure 32 Le cube de donn es initial choisi dans cette partie est celui de la figure 32 1 1 Forage vers le haut En premier lieu nous r alisons N forages vers le haut TAX sur le cube de donn es exemple figure 32 2 selon le m me principe d crit pr c demment
38. une dimension dans ce dernier Le transfert change l emplacement d un attribut dans une dimension pour mieux visualiser les relations entre les attributs L union de deux cubes selon une ou plusieurs dimensions de jointure est possible s ils disposent de la m me structure Plusieurs op rations d agr gation sont possibles sans passer par des op rations de groupement L agr gation de cubes permet de r duire la taille d un cube en compressant les mesures relatives ses dimensions L op rateur rc join permet de joindre une relation avec une dimension d un cube Finalement la construction g n re un cube partir d une relation Les dimensions et les mesures concern es sont sp cifi es en entr e de l op rateur 2 1 1 3 Alg bre pour les cubes vus comme des ensembles de relations Avec pour objectif l analyse en ligne OLAP Gyssens et Lakshmanan mod lisent les bases de donn es multidimensionnelles en tables relationnelles GL97 Cette repr sentation conserve les noms des tables de faits et de leurs attributs pour les attributs dimensionnels comme pour les mesures Tr s proche de l alg bre relationnelle cette alg bre se compose de deux ensembles d op rateurs Le premier ensemble repose sur des op rateurs classiques repris de l alg bre relationnelle union intersection diff rence et produit cart sien et les op rateurs unaires de s lection de projection et de renommage Chacun de ces op rateurs est d fini de la m me fa on
39. 3 lt prix gt lt vente gt lt vente gt lt ville gt Lyon lt ville gt lt pdt gt Clavier lt pdt gt lt temps gt Temps lt temps gt lt prix gt 593 lt prix gt lt vente gt lt vente gt lt ville gt Nice lt ville gt lt pdt gt Ecran lt pdt gt lt temps gt Temps lt temps gt lt prix gt 615 lt prix gt lt vente gt lt vente gt lt ville gt Nice lt ville gt lt pdt gt Souris lt pdt gt lt temps gt Temps lt temps gt lt prix gt 345 lt prix gt lt vente gt lt vente gt lt ville gt Nice lt ville gt lt pdt gt Clavier lt pdt gt lt temps gt Temps lt temps gt lt prix gt 380 lt prix gt lt vente gt lt ventes gt Figure 36 R sultat d un forage vers le haut sur l entrep t XML ventes avec XQuery 61
40. 6 Ecran Souris Clavier Clavier 2004 Paris 2005 2006 Figure 4 Rotation du cube XOLAP ventes suivant la dimension produit Ville Ann e Ann e 77 pe Ville Produit Produit Figure 5 Rotation des axes repr sentant les dimensions de l entrep t XML ventes 38 vente vente ville Lyon ville2 lt annee gt 2005 lt annee gt lt produit gt Ecran lt produit gt lt produit gt Ecran lt produit gt lt annee gt 2005 lt annee gt lt ville gt Lyon lt ville gt lt prix gt 150 lt prix gt lt prix gt 150 lt prix gt lt vente gt lt vente gt Lyon 2005 Ecran 44 Ecran 150 A 150 2005 Lyon Vente Vente V P A M A P V M Lyon Ecran 2005 150 2005 Ecran Lyon 150 Figure 6 Exemple d une rotation d un fait XML sous les trois formes fichier XML multidimensionnel cellule XOLAP et arbre TAX multidimensionnel Paris Lyon Nice Paris Nice Lyon Ecran Souris Clavier Figure 7 Changement de position des modalit s dans une dimension dans le cube XOLAP ventes 39 ventes vente ville Paris ville2 produit Ecran produit lt annee gt 2005 lt annee gt lt prix gt 160 lt prix gt lt vente gt lt vente gt lt ville gt Nice lt ville gt lt produit gt Ecran lt produit gt lt annee gt 2005 lt annee gt lt prix gt 140 lt prix gt lt vente gt lt vente gt lt ville gt Lyon lt ville gt lt produit gt Ecran lt produit gt
41. 97 TD01 Van05 VBRO3 Ver06 Wik07 ZDW 03 ZPRO2 ZWLZ05 ZY04 Arie Shoshani OLAP and Statistical Databases Similarities and Differences In 16 ACM SIGACT SIGMOD SIGART Symposium on Principles of Database Systems PODS 97 Tucson USA pages 185 196 ACM 1997 Helen Thomas and Anindya Datta A Conceptual Model and Algebra for On Line Analytical Processing in Decision Support Databases Information Systems Research 12 1 83 102 2001 Christelle Vangenot Datawarehouse Support de cours D partement d informatique Laboratoire de bases de donn es Ecole polytechnique f d rale de Lausanne Suisse 2005 Boris Vrdoljak Marko Banek and Stefano Rizzi Designing Web Warehouses from XML Schemas In 5 International Conference on Data Warehousing and Knowledge Discovery DaWaK 03 Prague Czech Republic volume 2737 of Lecture Notes in Computer Science pages 89 98 Springer 2003 Boris Verhaegen Requ tes OLAP sur une base de donn es XML native Master s thesis Universit Libre de Bruxelles Belgique 2006 Wikip dia Hypercube OLAP Bhttp fr wikipedia org wiki Hypercube OLAP Wikip dia 2007 Xin Zhang Katica Dimitrova Ling Wang Maged El Sayed Brian Murphy Bradford Pielech Mukesh Mulchandani Luping Ding and Elke A Rundensteiner Rainbow Multi XQuery Optimization Using Materialized XML Views In 2003 ACM SIGMOD International Conference on Management of Data SIGMOD 03 San
42. AP pr sent e selon deux crit res Comme notre alg bre est une extension de TAX elle en a h rit le crit re de r gles d optimisation De plus chaque op rateur XOLAP respecte dans sa d finition celle de son quivalent en OLAP classique 3 4 1 R gles d optimisation dans notre alg bre TAX a montr sa fiabilit surtout en termes d adaptabilit toutes formes de donn es XML comme les donn es multidimensionnelles dans notre cas Le crit re qui a contribu la cr ation de nos op rateurs XOLAP est des r gles d optimisation offertes par TAX cf Section 2 2 5 5 Chaque op rateur XOLAP est constitu d une combinaison de plusieurs au moins deux op rateurs TAX En outre nous disposons de plusieurs possibilit s d exprimer un m me op rateur Par exemple en d finissant le forage vers le haut nous avons pu viter d employer le groupement TAX et ainsi la s mantique de la jointure Un recours d autres op rations TAX suppl mentaires est tr s probable dans ce dernier cas Pour le forage vers le haut comme pour le reste des op rateurs XOLAP nous avons voulu conserver le principe norme tout en l exprimant de la fa on la plus simple et la plus efficace 3 4 2 Conformit entre notre alg bre XOLAP et l alg bre OLAP classique Nous avons respect quelle que soit la mani re de sa mise en ceuvre avec TAX sa d finition habituelle dans le contexte OLAP classique En cons quence les d finitions des op rateurs
43. L alg bre logique ou alg bre physique Finalement il ne reste qu ex cuter la requ te et examiner son r sultat Pour cela nous avons concu une interface Web d taill e dans la partie suivante 3 5 2 Mise en pratique de notre alg bre Dans cette section nous donnons plus de d tails sur l interface Web qui permet d exploiter notre alg bre XOLAP en pratique Pour illustrer cette partie nous continuons d utilise notre exemple de donn es XML multidimensionnelles de ventes Faute de place nous ne pr sentons qu un exemple d op rateur de chaque famille structurel rotation ensemblistes d coupage de cube en tranches et li la granularit forage vers le haut 3 5 2 1 Principe de l application Notre interface permet en premier lieu de s lectionner l op ration XOLAP d sir e partir d une liste ou un menu contenant tous les op rateurs XOLAP de notre alg bre Ensuite il peut s lectionner les param tres caract risant l op ration pour g n rer la requ te XQuery correspondante Dans l tape suivante cette requ te est t l charg e upload et ex cut e travers l interface de TIMBER Notons toute fois que notre application est strictement ind pendante de TIMBER Nous pouvons la lier toute autre SGBD natif XML supportant XQuery 27 3 5 2 2 Op rateurs impl ment s e Rotation rotate Nous savons d j que la rotation permute les dimensions d un cube en lui faisant subir une rotation autour d un de
44. Soit une requ te XQuery exemple qui pour parvenir son r sultat op re une s lection une projection une agr gation un groupement puis se termine par la s lection des l ments vis s par l analyse TLC permet de traduire cette requ te XQuery en une suite d op rateurs L op rateur de filtrage filter prend en entr e en plus de la collection d arbres de donn es S un attribut de filtrage p un mode m et une tiquette LCLf se r f rant une classe logique En sortie il fournit les sous arbres de S qui correspondent aux n uds li s dans la classe logique et qui satisfont p Le mode m pr cise comment se fait le choix de l ensemble de ces noeuds La jointure prend en entr e deux ensembles d arbres S1 et S2 un arbre mod le annot apt et un pr dicat p L annotation utilis e ici est le signe une seule correspondance entre l arbre en entier et l arbre mod le L arbre t moin repr sente la jointure entre les deux ensembles de noeuds d crits par p L op rateur de s lection prend en entr e un ensemble d arbres S et un mod le apt La sortie est constitu e de l ensemble des arbres t moins compos s des n uds communs entre S et apt La projection prend en entr e un ensemble d arbres et la classe logique repr sentant les noeuds recherch s S ils ne peuvent pas tre reli s pour former un arbre la racine de l arbre en entr e est employ e pour assurer cette liaison L limination de doublons duplicate elimination prend en
45. XOLAP mis en uvre ind pendamment de TAX sont les m mes que celles de leurs quivalents en alg bre OLAP classique De plus nous avons donn le r sultat de chaque op rateur XOLAP sous forme de cubes XOLAP de m me structure que les cubes OLAP M me les deux op rateurs structuraux la transformation d une dimension en mesure et la transformation d une mesure en dimension peuvent 26 tre exprim s sous forme de cubes XOLAP car tout arbre TAX est traductible en cube XOLAP ce qui n existe dans aucune autre alg bre OLAP Tout au long de la pr sentation de l alg bre XOLAP nous avons commenc par la d finition g n rale de chaque op rateur dans le contexte OLAP classique Notons que les cours que nous avons utilis s ainsi que l ensemble des articles proposant des alg bres OLAP ne constituent pas des supports complets de l OLAP En effet certains op rateurs sont absents dans certains supports D autres sont munis de d finitions contradictoires d un document un autre comme le d coupage de cube en tranches slice et d tachement d un d du cube dice qui varient d un travail un autre cf Section 3 3 3 2 Les pr sentations des op rateurs OLAP dans les r f rences utilis es ne pr sentent pas le principe de leur fonctionnement tout en se limitant des d finitions simples qui obligent le lecteur faire un effort suppl mentaire pour les comprendre C est pourquoi nous avons voulu pr senter travers ce m moire e
46. ag produit amp 2 3 4 5 4 tag ann e amp 5 tag prix Figure 30 Mod le pour la suppression des arbres suppl mentaires dans le forage vers le bas TAX 1 1 tag vente amp Eu UN 2 tag arrondissement amp 3 tag produit amp 2 3 4 5 4 tag ann e amp 5 tag prix Arbre mod le Liste de copie vente Paris1 Souris 2004 90 vente Paris8 Souris 2004 90 vente Lyon2 Souris 2004 88 vente Lyon6 Souris 2004 88 vente Paris Clavier 2004 110 vente Paris8 Clavier 2004 110 vente Lyon2 Clavier 2004 106 vente Lyon6 Clavier 2004 106 vente Paris Souris 2005 100 vente Paris8 Souris 2005 100 vente Lyon2 Souris 2005 90 vente Lyon6 Souris 2005 90 vente Paris Clavier 2005 113 vente Paris8 Clavier 2005 113 vente Lyon2 Clavier 2005 110 vente Lyon6 Clavier 2005 110 Figure 31 El ments en entr e de copier et coller dans le forage vers le bas TAX 53 Notre cube de donn es se compose de huit cellules donc de huit sous arbres TAX de v v6 r unis sous la m me racine ventes Paris Lyon Paris Lyon Ecran 110 100 v5 v6 Souris 80 75 v7 v8 2004 Figure 32 1 cube initial 54 Paris Lyon Ecran Souris Paris Ecran En TAX cette manipulation cubique se traduit par une union des 12 sous arbres r sultants des trois forages vers le haut avec les 8 sous arbres de
47. amp 3 tag produit amp 3 content Ecran amp 4 tag ann e amp 2 3 4 5 5 tag prix Figure 18 Mod le d arbre pour une s lection TAX d coupant l arbre en tranches 46 Paris Lyon Nice FIGURE 19 D tachement d un d du cube XOLAP ventes 1 1 tag vente amp 2 tag ville amp 2 content Lyon OR Nice amp 3 tag produit amp 2 3 4 5 3 content Souris OR Clavier amp 4 tag ann e amp 4 content 2004 OR 2005 amp 5 tag prix Figure 20 Mod le d arbre pour une s lection TAX d coupant l arbre en tranches 47 Paris Lyon Nice Paris Lyon Nice Figure 21 Forage vers le haut suivant l axe ann e ou Temps sur le cube XOLAP ventes La fonction d agr gation utilis e ici est somme 48 ventes vente vente vente ville produit temps prix ville produit temps prix ville produit temps prix Paris Ecran Temps 350 Lyon Ecran Temps 344 Nice Ecran Temps 343 ville produit temps prix ville produit temps prix ville produit temps prix Paris Souris Temps 310 Lyon Souris Temps 300 Nice Souris Temps 301 ville produit temps prix ville produit temps prix ville produit temps prix Paris Clavier Temps 321 Lyon Clavier Temps 311 Nice Clavier Temps 297 Figure 22 Forage vers le haut avec TAX 49 1 1 tag vente 2 tag ville 3 tag produit 2 3 4 4 tag prix F
48. an propose une alg bre compos e de deux op rateurs la s lection et la jointure En d finissant un pr dicat contrainte une s lection consiste identifier tous les fragments satisfaisant ce pr dicat Une jointure de deux fragments f1 et f2 est possible si et seulement s ils contiennent ou sont gaux la condition de jointure un fragment f De plus il ne faut pas qu il existe un autre fragment f inclus et plus r duit que f f1 et f2 en m me temps En d autres termes la jointure se r alise sur le plus petit fragment commun entre les sous arbres joindre La jointure entre fragments utilise les propri t s alg briques suivantes l idempotence la commutativit l associativit et l absorption L alg bre offre aussi la possibilit de joindre un nombre infini de paires d ensembles de fragments F1 et F2 L op ration consiste appliquer le principe d crit ci dessus pour toute combinaison de paires possible Dans ce cas l auteur utilise les propri t s alg briques de commutativit d associativit de monotonie et de loi de distribution Cette plus puissante jointure de fragments powerset fragment join repr sente une extension de l op rateur de jointure dans laquelle un nombre arbitraire non nul de fragments de F1 et F2 sont joints 2 2 2 2 Alg bre logique TAX et alg bre physique d riv e Jagadish et al proposent une alg bre logique d arbres nomm e TAX Tree Algebra for XML qui est une extension de l alg bre
49. avons d termin trois crit res de comparaison qui sont g n ralement transversaux aux familles d alg bres que nous avons identifi es dans un premier temps extensions des concepts relationnels d une part et multidimensionnels d autre part Le mod le de donn es adopt les op rateurs offerts et la gestion de la granularit des donn es constituent l ensemble de ces crit res 2 1 3 1 Mod le de donn es Dans les travaux que nous venons de pr senter chaque alg bre est bas e sur un mod le de donn es sp cifique Bien que tous ces mod les partent du principe d analyser des faits OLAP selon plusieurs dimensions et mesures leur conception diff re d une alg bre l autre Nous retrouvons ici les deux grandes familles de mod les support es par les diff rentes alg bres La premi re famille adopte une extension du mod le relationnel o les auteurs mod lisent les donn es multidimensionnelles dans un format relationnel classique GLS96 LW96 GL97 Au contraire dans la deuxi me famille les concepts relationnels sont exclus de toute repr sentation des donn es AGS96 AGS97 CT97 CT98 TDO1 RTZ06a RTZO06b Par exemple dans leur travail Agrawal et al mod lisent les donn es en un espace de repr sentation multidimensionnel sous forme d axes de dimensions sans se r f rer aux tableaux Les autres auteurs ont aussi laiss de c t la repr sentation tabulaire des donn es l exception de Cabibbo et Torlone qui m
50. ble des valeurs utilis es dans le cube tandis que g symbolise la combinaison des domaines des noms des dimensions associ es ces valeurs Sur ce mod le l alg bre des auteurs propose neuf op rateurs d di s la manipulation OLAP Le premier op rateur restriction permet de limiter un ensemble des valeurs V pour obtenir en sortie un ensemble VO inclut ou gal V L op rateur agr gation permet d agr ger une mesure en groupant les attributs de la dimension correspondante Le produit cart sien relie deux cubes en unifiant les dimensions d une part et les mesures d autre part La jointure est un cas particulier du produit cart sien congue dans le but de relier deux cubes ayant une ou plusieurs dimensions communes Les deux op rateurs suivants n cessitent que les deux cubes en question soient union compatibles L union permet d unir deux cubes C est une op ration diff rente du produit cart sien puisqu il s agit d unifier les ensembles de valeurs de deux cubes en une seule valeur VO dans le cube r sultant La diff rence consiste soustraire l ensemble de valeurs correspondant au deuxi me cube du premier La partition classe les cellules d un cube dans des groupes significatifs Cette t che concerne certains types d agr gation Par exemple il est possible de grouper toutes les moyennes selon un pr dicat pr d fini Les deux derniers op rateurs pull et push peuvent tre class s comme des op rateurs de transformation Pull pe
51. consid rer comme une dimension Il suffit alors de r aliser une projection sur tous les sous arbres de l arbre de base L arbre mod le et la liste de projection en entr e de l op ration indiquent la nouvelle position que prenne la mesure parmi les dimensions qui permet sa transformation en dimension en sortie Un exemple de transformation d une mesure en dimension avec TAX est disponible dans la figure 15 Nous n avons pas proc d de la m me fa on pour la transformation d une dimension en mesure puisqu une mesure doit exprimer une valeur num rique Par contre il n est pas interdit qu une dimension exprime aussi une valeur num rique ce qui est le cas suite une transformation d une mesure en dimension En d autres termes une dimension peut tre repr sent e la fin de l arbre si cette derni re ne dispose pas de mesure Mais repr senter une mesure avec les dimensions nous pose dans un cas sp cial celui de la transformation d une mesure en dimension 3 3 2 2 Op rateurs ensemblistes Dans ce qui suit nous exprimons les deux op rateurs ensemblistes de l OLAP slice et dice dans un contexte XOLAP Connus g n ralement sous les noms de s lection et projection sur un cube respectivement nous adoptons d autres d nominations plus pr cises inspir es essentiellement de leurs principes d coupage de cube en tranches pour slice et d tachement d un d du cube pour dice Notre utilisation de ces nouveaux termes est justifi e dans
52. de Gestion de Bases de Donn es SGBD natifs XML bien qu en constant progr s pr sentent en effet des limitations en terme de performance et b n ficieraient grandement d une optimisation automatique des requ tes et particuli rement des requ tes d cisionnelles qui sont en g n ral tr s co teuses Ce m moire est organis comme suit Le chapitre 2 d taille sur l tat de l art sur les alg bres OLAP au d but les alg bres d interrogation de donn es XML et les alg bres XOLAP peu nombreuses qui visent permettre des analyses OLAP sur des cubes XML alg bres XOLAP Nous pr sentons dans le chapitre 3 notre propre alg bre XOLAP qui se r sume dans la mise en uvre des op rateurs OLAP classiques dans un contexte XML Pour cela nous tendons l alg bre XML TAX par des op rateurs OLAP Nous mettons ensuite cette extension en pratique via une application g n rant des requ tes XQuery d cisionnelles traduisant nos op rateurs Ces requ tes seront par la suite ex cut es dans le SGBD natif XML TIMBER Finalement nous pr sentons le bilan de nos travaux ainsi que ses perspectives dans le chapitre 4 2 tat de l art Malgr le d veloppement des syst mes d cisionnels les bases de donn es multidimensionnelles et la technologie OLAP souffrent d un manque de formalisation pr cise Nous nous int ressons dans ce chapitre aux travaux qui proposent des mod les pour les donn es multidimensionnelles supportant une alg
53. e production CAJKO1 Pour notre part nous choisissons de garder le principe de l association groupement agr gation pour r aliser un forage vers le haut avec TAX Groupement et agr gation consistent en deux op rations TAX compl tement distinctes mais nous pouvons n anmoins les combiner dans un m me contexte tout en respectant les principes de chacun L arbre correspondant au r sultat que nous voulons atteindre et qui mod lise le cube r sultant du forage de la figure 21 est disponible dans la figure 22 Il comporte neuf sous arbres qui repr sentent chacun un fait vente d crit par le lieu de vente et le produit vendu La dimension Temps combine toutes les valeurs que peut prendre une ann e La fonction d agr gation choisie dans notre exemple est la somme sum Chaque mesure repr sente alors la somme des ventes durant les trois ann es pour tout groupement ville produit possible en suivant le m me axe que dans le cube original Dans ce qui suit nous d montrons comment une suite d op rateurs TAX permet d aboutir par tapes un forage vers le haut 1 S lection Il faut en premier lieu extraire tous les sous arbres avec une s lection TAX avec un mod le et une liste de s lections conservant les structures et les contenus initiaux de tous les arbres de l entrep t Le but de cette s lection est de d tacher tous les arbres afin de les pr parer au processus suivant 2 Groupement Nous groupons ensuite les sous arbres d
54. e les donn es du cube un niveau de granularit sup rieur selon une dimension conform ment sa hi rarchie Le but est de passer d un niveau de granularit un autre niveau plus g n ral par exemple passer d une repr sentation multidimensionnelle des donn es suivant les villes une autre suivant les pays Ce passage n cessite l association d une fonction d agr gation somme moyenne etc l op ration de groupement Le but de cette association est d indiquer comment sont calcul es les valeurs du niveau sup rieur partir de celles du niveau inf rieur Techniquement un forage vers le haut consiste aplatir ou plier les diff rentes tranches du cube en une seule tout en suivant la direction de l axe repr sentant la dimension concern e par cette op ration Chaque cellule du r sultat final contient le r sultat de l agr gation des mesures correspondantes Un exemple du forage vers le haut sur notre cube XOLAP est pr sent dans la figure 21 o nous calculons le total des ventes sur toutes les ann es pour chaque groupement produit ville Dans un contexte relationnel une fonction d agr gation est souvent associ e un groupement L emploi du groupement pr cise les attributs vis s par l agr gation Dans TAX Jagadish et al s parent l agr gation du groupement dans TAX D autres approches optent pour cette id e et proposent une alg bre OLAP o le forage vers le haut est exprim en associant une jointure un
55. e notre travail Soit un fichier mod lisant un entrep t de donn es XML ventes Les mesures repr sentent les prix des produits vendus des diff rentes villes et diff rentes ann es Nous disposons alors de trois dimensions ville produit et ann e et une mesure prix mod lis s dans un l ment fait intitul vente Chacune des dimensions est caract ris e par trois modalit s Paris Lyon et Nice comme villes Ecran Souris et Clavier comme produits et 2004 2005 et 2006 comme ann es En liaison avec ce que nous avons dit pr c demment dans cette section chaque fait XML est mod lisable sous forme d arbre TAX et de cellule XOLAP figure 2 Supposons maintenant que ventes repr sente vingt sept faits vente Le fichier XML multidimensionnel est alors constitu d une racine principale ventes et de vingt sept occurrences de vente Chaque vente pr cise les dimensions et les mesures correspondantes La structure du cube XOLAP quivalent ce fichier XML est illustr e dans la figure 3 En outre l arbre TAX quivalent ce cube et au fichier XML est aussi constitu de vingt sept sous arbres vente r unis sous une seule racine ventes En cas d entrep t creux une ou plusieurs mesures absentes une cellule vide est repr sent e de la m me mani re dans le fichier XML comme sous forme d arbre TAX tout en en donnant une valeur nulle la mesure toujours pr sente avec les dimensions correspondantes Pour am liorer le mod le de donn
56. e vers le haut est assur par une combinaison des op rations de s lection groupement multiple jointure agr gation et mise jour des valeurs de n uds insertion de n uds Cet enchainement d op rations est traduit dans notre interface comme suit tout en tenant compte de la requ te XQuery que nous voulons g n rer Soit un exemple o les dimensions de groupement sont ville et produit la dimension de jointure est ann e l agr gation employ e est la somme et Temps repr sente la valeur du noeud ins r la place d ann e en r sultat puisque le forage vers le haut est assur suivant cet axe Lors de la mise en uvre du forage vers le haut en pratique nous nous sommes rendu compte que notre programme est plus souple si la jointure est r alis e suivant la dimension qui n a pas particip au groupement ann e dans notre exemple Cette solution tait cit e mais pas utilis e dans la d finition du forage vers le haut avec TAX Pourtant nous l avons soutenu dans la pratique pour des buts d optimisation de notre programme L interface impl ment e disponible en annexe figure 35 facilite la r alisation d un forage vers le haut gr ce au protocole suivant l En premier lieu l analyste choisit les dimensions de groupement Si nous disposons de n dimensions n dimensions sont alors les l ments de groupement multiple Ce sont toutes les dimensions sauf la dimension selon laquelle est assur le forage vers le haut ville et
57. ectionner depuis chaque r sultat de jointure l arbre vente en utilisant le mod le d arbre et la liste de s lections correspondants La jointure peut tre r alis e aussi selon les ann es l axe qui n a pas particip au groupement Pourtant nous n avons pas choisi cette solution et nous avons proc d comme d crit d j 4 Agr gation L op ration d agr gation prend en entr e une fonction d agr gation un mod le d arbre et un ensemble de sp cifications de mise jour La fonction d agr gation utilis e dans notre exemple est somme sum Le mod le d arbre doit conserver tous les n uds de l arbre d entr e avec en plus un nouveau n ud i supportant l agr gation calcul e La sp cification de mise jour pr cise comment se r alise l agr gation Ici un n ud i prend comme valeur la somme du reste de n uds mesures Un r sultat d agr gation sur le sous arbre vente de la figure 26 est pr sent e dans la figure 27 Dans les arbres r sultants la pr sence des n uds mesures autres que i est inutile Pour les laguer nous avons recours une projection Le mod le et la liste de projection correspondants ne sp cifient pas ces noeuds comme r sultat souhait 5 Insertion de n uds Nous employons l op ration d insertion de n uds pour ins rer dans chaque arbre un n ud repr sentant la dimension Temps qui agr ge les trois ann es l issue de cette insertion il reste associer les neufs arbres vente sous une s
58. elberg Germany pages 524 533 IEEE Computer Society 2001 3l CD99 C0190 CRF00 CT97 CT98 DBRA05 DD97 DFF 98 DT99 FHP02 FLBC02 FSW00 Gar07 GBLP96 GCB 97 James Clark and Steve DeRose XML Path Language XPath Version 1 0 http www w3 org TR xpath World Wide Web Consortium W3C 1999 Latha S Colby A recursive algebra for nested relations Information Systems 15 5 567 582 1990 Donald D Chamberlin Jonathan Robie and Daniela Florescu Quilt An XML Query Language for Heterogeneous Data Sources In 3 International Workshop on The World Wide Web and Databases WebDB 00 Dallas USA volume 1997 of Lecture Notes in Computer Science pages 1 25 Springer 2000 Luca Cabibbo and Riccardo Torlone Querying multidimensional databases In 6 International Workshop of Database Programming Languages DBPL 97 Estes Park USA volume 1369 of Lecture Notes in Computer Science pages 319 335 Springer 1997 Luca Cabibbo and Riccardo Torlone A logical approach to multidimensional databases In 6 International Conference on Extending Database Technology EDBT 98 Valencia Spain volume 1377 of Lecture Notes in Computer Science pages 183 197 Springer 1998 J r me Darmont Omar Boussaid Jean Christian Ralaivao and Kamel Aouiche An Architecture Framework for Complex Data Warehouses In 7 International Conference on Enterprise Information Systems ICEIS 05
59. ente gt Lyon Ecran 7 150 2005 Lyon i vente prix ville produit annee Ville prix Lyon 150 Figure 13 Transformation d une mesure en dimension avec toutes les repr sentations multidimensionnelles fichier XML cellule XOLAP et arbre TAX Pull 1st member of each element as the new dimension Sales 10 41 20 43 10 44 Product pl p2 p3 pl pe product Figure 14 Transformation d une dimension en mesure dans l alg bre d Agrawal et al AGS96 AGS97 vente vente ville produit ann e prix prix produit ann e ville Lyon Ecran 2005 150 150 Ecran 2005 Lyon Figure 15 Transformation d une dimension en mesure avec TAX 44 Figure 16 D coupage de cube XOLAP ventes en tranches suivant le produit Ecran 45 ventes vente vente vente ville produit ann e prix ville produit ann e prix ville produit ann e prix Paris Ecran 2004 140 Lyon Ecran 2004 120 Nice Ecran 2004 130 vente vente vente ville produit ann e prix ville produit ann e prix ville produit ann e prix Paris Ecran 2005 150 Lyon Ecran 2005 155 Nice Ecran 2005 135 vente vente vente ville produit ann e prix ville produit ann e prix ville produit ann e prix Paris Ecran 2006 150 Lyon Ecran 2006 155 Nice Ecran 2006 140 Figure 17 D coupage de l entrep t en tranches avec TAX 1 avec 1 tag vente amp 2 tag ville
60. entr e une collection d arbres un param tre Ci et la liste 13 des n uds de la classe logique sp cifi e nl Le param tre Ci limine les duplications au niveau des noms ou du contenu des noeuds Un ensemble de fonctions d agr gation est aussi d fini dans l alg bre TLC count max etc En entr e ces fonctions prennent l ensemble des arbres mod lisant la base la nature de l agr gation les noeuds concern s par l agr gation et les noeuds cibles cr er Les noeuds ajout s l issue de l agr gation doivent avoir les m mes parents que les noeuds initiaux Le dernier op rateur de TLC est la construction construct qui prend en entr e une collection d arbres S et un mod le annot de construction C L arbre C est un mod le annot normal mais qui permet en plus l tiquetage le renommage et le rassemblement jointure des arbres de donn es 2 2 3 2 Alg bre de requ tes pour les flux de donn es XML fragment es Partant du constat que l utilisation des donn es XML distribu es s accroit continuellement Bose et al proposent une alg bre de requ tes pour le langage XQuery qui op re sur des flux de donn es XML r partis sur le r seau BFLCO3 Apr s avoir rassembl diff rents fragments de donn es XML et les avoir repr sent s selon un mod le disponible sur un serveur l alg bre propos e s applique aux flux de donn es fragment es Les donn es XML en provenance du client sont mod lis es en arbres de donn es sur
61. ents selon un pr dicat de jointure Cet op rateur conserve la structure initiale des donn es Unnest permet de parcourir l arbre XML selon le chemin et le pr dicat indiqu s L op rateur inverse nest doit tre associ un groupement une ent te et un op rateur Si l un des trois n est pas compl tement valu l l ment correspondant n est pas analys Finalement la r duction s applique l ent te de chaque l ment et fusionne les r sultats en utilisant l op rateur 2 2 4 Alg bres XML pour ECD Zhang et Yao pr sentent une analyse des alg bres XML existantes dans une optique d extraction des connaissances partir des donn es XML ZY04 par exemple pour d couvrir des ph nom nes inconnus et utiliser des connaissances acquises partir de grandes volumes de donn es r gles d association typologies En conclusion de cette tude les auteurs pr conisent l emploi d une alg bre sp cifiquement adapt e En se basant sur une repr sentation des donn es XML en arbres cette alg bre peut se r sumer en cinq op rateurs d inclusion d arbres de sous arbres de r gions groupes d arbres d enfants ou de chemins 2 2 5 Discussion Dans cette section nous discutons des diff rentes alg bres XML en reprenant cinq crit res propos s par Zhang et Yao dans leur analyse des alg bres XML cf Section 2 2 4 le mod le de donn es sur lequel se base l alg bre l unit de base d information manipul e pa
62. eposage virtuel BCH99 ou l entreposage XML Pok02 BB03 HBHO3 VBRO3 PHS05 ZWLZO05 BMCAO6 Le langage XML eXtensible Markup Language Qui06 est en effet de plus en plus utilis comme standard pour repr senter des donn es d cisionnelles BCC 05 et se montre particuli rement adapt pour mod liser des donn es dites complexes DBRAOS5 issues de sources h t rog nes et notamment du Web Ainsi plusieurs travaux visent tendre le langage XQuery BCF 07 pour supporter des requ tes de type OLAP groupement agr gation etc BC04 BCC 05 Kay06 Ver06 Ces extensions devraient non seulement permettre d effectuer des analyses OLAP classiques mais aussi de prendre en compte dans l analyse en ligne des sp cificit s des donn es XML comme par exemple des hi rarchies multiples imbriqu es et incompl tes ragged hierarchies BCC 05 qui seraient tr s difficiles g rer dans un environnement relationnel Nous travaillons dans ce contexte concevoir une alg bre XML OLAP ou XOLAP permettant d ex cuter des requ tes OLAP sur des donn es XML natives Notre objectif pour d velopper un tel outil est triple 1 d finir un cadre formel actuellement inexistant dans le contexte XOLAP 2 soutenir les efforts les efforts visant tendre le langage XQuery pour permettre des analyses OLAP notamment avec des op rateurs sp cifiques XML 3 permettre l optimisation de requ tes OLAP exprim es en XQuery Les Syst mes
63. es d un arbre XML et permettent de pointer un ou plusieurs noeuds sp cifiques child descendent descendent or self parent ancestor ancestor or self self attribute Une expression l mentaire qui adopte une fonction de navigation est not e function name Node Seq Node Une expression FLWOR du langage XQuery peut ainsi tre d finie par la combinaison de plusieurs expressions l mentaires Les expressions de parcours path expressions sont exprim es dans les clauses for et let les expressions de s lection selection expressions dans la clause where les expressions d ordre ordering expressions dans la clause Order by et les expressions de construction du r sultat mapping expressions dans la clause return Une s lection selection expression consiste extraire une sous s quence autre expression en se basant sur un crit re de s lection Elle est not e s p o s repr sente une expression sequence et p la condition de s lection Cette condition peut tre exprim e par l valuation d un pr dicat predicate test ou par un test sur les noeuds point s par l expression kind test Cette fonctionnalit est sp cifique XML et n existe pas dans les mod les relationnels et orient s objet Une projection est d finie par des expressions orient es par des fonctions de navigation Elle consiste s lectionner diff rentes parties de l arbre XML Une jointure revient des expressions de d semboitement
64. eule racine ventes via une production TAX e Forage vers le bas drill down Le forage vers le bas est l op ration r ciproque du forage vers le haut Le forage vers le bas permet d obtenir des d tails sur la signification d un r sultat en affinant une dimension un niveau d agr gation inf rieur par exemple passer d une repr sentation multidimensionnelle des donn es suivant les pays une autre repr sentation suivant les villes D un point de vue technique si le forage vers le haut permet de plier un cube le forage vers le bas le d plie en d taillant les donn es suivant une ou plusieurs dimension Un exemple de forage vers le bas est illustr dans la figure 28 o les faits sont d taill s selon la dimension ville Le but est de d tailler les ventes par arrondissement pour tous les produits et pour toutes les ann es La fonction d agr ation choisie ici est la somme G n ralement nous pouvons choisir un autre type d agr gation moyenne par exemple En sommant les valeurs des ventes d un produit pour les arrondissements d une m me ville au cours d une ann e donn e nous devons obtenir la valeur de la vente dans le cube initial pour ces m mes dimensions Chaque fait doit passer dans le r sultat de sa mod lisation par un arbre un certain nombre d arbre selon les exigences du forage Pour chaque fait le nombre d arbres en sortie du forage vers le bas est multipli en le nombre de modalit s que prend la dimension
65. g tandis que fold est quivalent destroy dimension de Gyssens et al 2 1 3 3 Granularit des donn es La prise en compte de la granularit des donn es varie largement selon les alg bres OLAP Certaines ne consid rent d ailleurs pas du tout la granularit des donn es dans leurs diff rents op rateurs GLS96 GL97 vraisemblablement du fait que ces alg bres s inspirent trop directement du cas relationnel La prise en compte de la granularit des donn es est toujours accompagn e par une impl mentation des op rateurs de forage vers le haut et ou vers le bas roll up et ou drill down et parfois de l op rateur cube Agrawal et al expriment le forage vers le haut roll up en associant une fonction d agr gation comme somme l op rateur fusion de leur alg bre Ils expriment aussi le forage vers le bas drill down en effectuant l op ration r ciproque du forage vers le haut c est dire en remontant en arri re pour savoir comment sont r alis es l agr gation et la fusion des donn es Li et Wang pr sentent dans leur alg bre de groupement un op rateur de forage vers le haut roll qui se repose sur une op ration de groupement Les fonctions de forage vers le haut de Cabibbo et Torlone permettent galement d atteindre ce but mais les auteurs ne donnent malheureusement pas plus de d tails sur leur fonctionnement Bien que Datta et Thomas ne pr sentent pas d op rateurs de forage ni d agr gation ils affirme
66. iff rent de D C De plus une jointure peut tre assur e par un produit suivi d une s lection Les op rateurs ensemblistes union intersection et diff rence ne peuvent tre utilis s dans TAX qu en cas de similitude entre deux arbres Un certain isomorphisme doit exister entre les noeuds des arbres trait s afin de conserver leur ordre ainsi que les paires attribut valeur correspondantes Le groupement n est pas ignor dans ce travail mais contrairement au cas relationnel il est s par des op rations d agr gation Pour grouper des n uds group by prend en entr e un mod le d arbre une fonction de groupement pour identifier les arbres t moins dans la collection initiale selon ce mod le et une fonction d ordre pour une meilleure organisation du r sultat En sortie du groupement les doublons sont limin s Les op rateurs classiques d agr gation comme la somme le minimum le 11 maximum et le comptage sont sp cifi s dans TAX Ils prennent en entr e un mod le d arbre la nature de l agr gation r aliser et une sp cification de mise jour Cette derni re pr cise comment est calcul e l agr gation et comment elle est ins r e dans l arbre initial pour aboutir l arbre t moin selon le mod le d arbre en entr e D autres op rateurs TAX n ont pas d quivalent dans les travaux similaires Leur but principal est de mettre jour les arbres Le premier le renommage renaming consiste changer le nom ou la valeu
67. igure 23 Mod le pour le groupement utilis dans le forage le haut TAX Tax group root tax grouping list tax group subroot Vente ville produit ville produit prix ville produit prix ville produit prix Paris Ecran Paris Ecran 140 Paris Ecran 150 Paris Ecran 160 Figure 24 Groupement selon la ville Paris et le produit Ecran dans le forage vers le haut TAX 1 2 5 3 4 6 7 8 5 tag vente 3 content 6 content 4 content 7 content 3 tag 6 tag V 4 tag 7 tag P 8 tag M Figure 25 Mod le pour la jointure utilis dans le forage vers le haut TAX 50 Elements jointure ville produit ville produit prix prix prix Paris Ecran Paris Ecran 140 150 160 Figure 26 Jointure selon la ville Paris et le produit Ecran pour le forage vers le haut TAX vente ville produit prix prix prix sum prix Paris Ecran 140 150 160 450 Figure 27 Calcul d agr gation pour le forage vers le haut TAX 51 Paris Lyon Paris 1 Paris 8 Lyon 2 _ Lyon 6 Souris Figure 28 Forage vers le bas sur le cube XOLAP ventes PAS PAS ville produit ann e prix arrondissement produit ann e prix Paris Souris 2004 220 Paris1 Souris 2004 113 arrondissement produit ann e prix Paris8 Souris 2004 113 Figure 29 Forage vers le bas avec TAX 52 1 tag vente amp 1 2 tag ville amp NZD 2 content Paris OR 2 content Lyon amp 3 t
68. ion Les auteurs d finissent ensuite des op rateurs OLAP bas s sur cette alg bre Une projection sur un cube s effectue en fusionnant les dimensions non concern es par cette op ration en une seule puis en la d truisant L union est assur e en joignant les valeurs non nulles de deux cubes ayant le m me nombre de dimensions et utilisant les m mes types de donn es L intersection s effectue en joignant deux cubes dans les valeurs communes des dimensions La diff rence entre deux cubes C1 et C2 est assur e par une intersection entre eux suivie d une union du r sultat avec le premier cube C1 2 1 1 2 Alg bres pour les cubes de donn es relationnels Li et Wang formalisent un cube de donn es relationnel pour une analyse OLAP LW96 Deux alg bres sont propos es dans ce contexte une alg bre de groupement extension de l alg bre relationnelle et une alg bre multidimensionnelle pour manipuler les cubes multidimensionnels Nous ne nous int ressons dans ce qui suit qu la deuxi me Dans le mod le de donn es correspondant une dimension d un cube est d finie par son nom et une relation qui lui est associ e Le r le des relations est d assurer la correspondance entre les r f rences des cellules et les attributs correspondants Six op rateurs sont propos s chacun fournissant un nouveau cube en sortie Le premier op rateur ajout d une dimension permet de g n rer un nouveau cube C1 partir d un cube existant C en ins rant
69. ion and optimization techniques In ACM SIGMOD International Conference on Management of Data SIGMOD 96 Montreal Canada pages 228 239 ACM 1996 Chang Li and Xiaoyang Sean Wang A data model for supporting on line analytical processing In 5 International Conference on Information and Knowledge Management CIKM 96 Rockville USA pages 81 88 ACM 1996 Leonid Libkin and Limsoon Wong Query Languages for Bags and Aggregate Functions Journal of Computer and System Sciences 55 2 241 272 1997 Tapio Niemi Marko Niinim ki Jyrki Nummenmaa and Peter Thanisch Constructing an OLAP cube from distributed XML data In 5 International Workshop on Data Warehousing and OLAP DOLAP 02 McLean USA pages 22 27 ACM 2002 Leonid Novak and Alexandre V Zamulin An XML Algebra for XQuery In 10 East European Conference on Advances in Databases and Information Systems ADBIS 06 Thessaloniki Greece volume 4152 of Lecture Notes in Computer Science pages 33 OMG07 PAKC 03 PAKJ 02 PHS05 Pok02 PP03 PPP04 Pra06 PRP02a PRP02b PWLJ04 Qui06 RTZOI RTZ06a RTZ06b 4 21 Springer 2006 OMG Unified Modeling Language http www uml org Object Management Group OMG 2007 Stelios Paparizos Shurug Al Khalifa Adriane Chapman H V Jagadish Laks V S Lakshmanan Andrew Nierman Jignesh M Patel Divesh Srivastava Nuwee Wiwatwattana Yuging Wu and Cong Yu TIMBER A
70. la pr sentation de ces deux op rations e D coupage de cube en tranches slice Le d coupage de cube en tranches slice dissocie une ou plusieurs tranches d un cube de donn es multidimensionnel selon un ou plusieurs attributs d une seule dimension et ce pour tous les attributs dimensionnels correspondants Un cube peut d ailleurs tre vu comme un ensemble de tranches superpos es les unes sur les autres horizontalement ou les unes cot des autres encore verticalement Donc e d coupage de cube en tranches peut s effectuer dans l un de ces deux sens 21 mais pas dans les deux simultan ment Nous morcellerions alors le cube en cellules ou groupes de cellules ce qui n est pas le but ici Techniquement un d coupage de cube en tranches est assimil une projection sur un cube de donn es dans le sens de la r duction dimensionnelle et non dans celui de l alg bre relationnelle bien que les deux soient conceptuellement homologues Gar07 Wik07 Cette projection est plus claire en cas d extraction de toutes les tranches d un cube de mani re ce que l union des tranches r sultantes constitue le cube de d part Cette op ration nous rappelle l op ration SQL select from table qui d termine une projection via une s lection En r alit une projection peut tre vue comme une s lection dans SQL comme dans l OLAP Pourtant le raisonnement inverse de s lection projection est faux D ailleurs la s lection est
71. lle qui consiste d placer deux dimensions ou plus sans modifier les valeurs des mesures correspondantes D un point de vue technique une rotation consiste en une s lection de faces et non de membres Le r sultat d une rotation de notre cube XOLAP exemple autour de l axe produit figure 3 est disponible dans la figure 4 Une repr sentation axiale de ce m me exemple est illustr e dans la figure 5 19 Un exemple de rotation d un fait du fichier XML multidimensionnel suivant l axe produit est disponible dans la figure 6 Il s agit en fait d interchanger les positions des dimensions autres que la dimension ou l axe de rotation Pour exprimer une rotation avec TAX nous avons recours la s lection Une s lection TAX prend son entr e l arbre mod lisant l entrep t de donn es XML un arbre mod le et une liste de s lectionss Suivant le sens de lecture d fini pr c demment cf Section 3 3 1 l ordre des dimensions dans l arbre mod le doit correspondre l ordre des axes dans le r sultat La liste de s lectionss contient obligatoirement le noeud vente afin de garantir la pr servation de tous ses descendants pour l ensemble des occurrences en sortie de la s lection Dans une tape suivante il nous reste r unir tous les arbres s lectionn s sous une seule racine ventes via l op rateur TAX production Le r sultat de la rotation d un fait XML sous ses trois formes arbre fichier XML et cellule XOLAP est disponible dans la
72. mation pour Bose et al est un arbre enracin et ordonn o les trous et les remplisseurs sont pris en compte par certains op rateurs Les op rateurs de l alg bre de Fern ndez et al manipulent en entr e le contenu d un document XML ensemble de types et variables globales et fournissent en sortie un nouveau document XML Dans les travaux de Zhang et al il n existe pas d unit d information de base en raison de la diversit des op rateurs relationnels XML ou sp cifiques Finalement l entit principale manipul e dans le mod le de Novak et Zamulin est l expression s quence de noeuds 2 2 5 3 Op rateurs Certaines alg bres ne repr sentent que la traduction des op rateurs relationnels dans un contexte XML BFLCOS3 Pra06 La plupart des autres tendent les concepts relationnels par de nouveaux op rateurs qui diff rent d un travail un autre Dans l ensemble de ces travaux chaque op rateur est toujours d pendant du mod le de donn es Parmi les op rateurs inspir s du relationnel la s lection dans les alg bres XML permet de choisir une entit qualifi e parmi les entit s en entr e La projection en revanche ne suit pas les principes relationnels et diff re d une alg bre l autre En effet en alg bre relationnelle projeter limine du r sultat les champs non sp cifi s Dans XAL et Niagara l op rateur de projection est similaire au parcours d expressions de chemins dans XPath Dans TAX et ses d riv es
73. n cours d impl mentation Leur mise en uvre suit le m me principe une interface g n rant une requ te XQuery Des limitations de XQuery ont toute fois influenc notre travail 3 5 2 4 Limitations de XQuery rencontr es Pour impl menter plusieurs de nos op rateurs XOLAP comme switch cube et dice des probl mes li es aux limitations du langage XQuery nous ont rencontr Ce dernier touche l op rateur XOLAP switch pr cis ment et touche aux autres op rateurs cube et dice pour l instant Le changement de position des modalit s dans une dimension switch permet de permuter deux attributs d une m me dimension au sein d un cube XOLAP La requ te XQuery correspondante parcourt l l ment repr sentant la dimension cible un nombre de fois gal au nombre de modalit s interchanger Elle doit afficher les diff rentes valeurs de cette m me dimension dans l ordre d sir qui est galement indiqu aussi dans cette requ te Le probl me qui se pose ici est qu une requ te XQuery ne permet pas plus d un parcours d un seul l ment donn avec une boucle for Donc pour r aliser un changement de position des modalit s dans une dimension il nous faut combiner un ensemble de r sultats de plusieurs requ tes XQuery qui parcoure chacune la dimension cible une fois Une association des diff rents r sultats de toutes ces requ tes constitue le r sultat d sir Bien que nous atteignions notre but en suivant cette m thode elle n
74. n plus de l alg bre XOLAP les d finitions de chaque op rateur OLAP et surtout leur mode de fonctionnement d une fa on simple et technique Finalement comme nous l avons d j voqu cf Section 3 4 1 nous avons voulu conserver le principe norme de chaque op rateur m me dans le contexte XML Par exemple nous avons exprim le forage vers le haut en conservant le principe de l association groupement agr gation indispensable son fonctionnement 3 5 Mise en pratique de notre alg bre XOLAP ce stade nous avons mis en uvre de fa on th orique une alg bre XOLAP compl te en unissant les concepts XML et OLAP en un seul Afin de valider notre approche nous l avons impl ment au sein du SGBD natif XML TIMBER 3 5 1 Recours TIMBER Comme nous avons tendu TAX par des op rateurs OLAP nous avons de mettre en ceuvre les requ tes traduisant nos op rateurs XOLAP via le SGBD natif XML TIMBER PAKC 03 TIMBER constitue en effet la mise en ceuvre de TAX et de ses d riv es logique et physique En suivant les instructions du manuel d utilisateur mis en ligne JPCJ 06 nous avons exp riment quelques requ tes XML simples L interface TIMBER permet l utilisateur de saisir ou de t l charger partir d un fichier sa requ te XQuery 1 0 BCF 07 L analyste choisit ensuite un des trois modes d entr e pour sa requ te XQuery alg bre logique ou alg bre physique ainsi que le mode d affichage du r sultat XM
75. ndreas Bauer and Gunnar Harde XCube XML for data warehouses In ACM 6 International Workshop on Data Warehousing and OLAP DOLAP 03 New Orleans USA pages 33 40 2003 Philippe Le H garet Ray Whitmer and Lauren Wood Document Object Model DOM http www w3 org DOM World Wide Web Consortium W3C 2006 H V Jagadish Laks V S Lakshmanan Divesh Srivastava and Keith Thompson TAX A Tree Algebra for XML In 8 International Workshop on Database Programming Languages DBPL 01 Frascati Italy volume 2397 of Lecture Notes in Computer Science pages 149 164 Springer 2001 Mikael R Jensen Thomas H Moller and Torben B Pedersen Specifying OLAP cubes on XML data Journal of Intelligent Information Systems 17 2 3 255 280 2001 H V Jagadish Jignesh M Patel Adriane Chapman Magesh Jayapandian Yunyao Li Stelios Paparizos Nuwee Wiwatwattana Cong Yu Shurug Al Khalifa Andrew Nierman Keith Thompson Yuqing Wu Yi Yu Nick Koudas Laks V S Lakshmanan and Divesh Srivastava TIMBER http www eecs umich edu db timber University of Michigan USA 2006 Michael Kay Positional Grouping in XQuery In 3 International Workshop on XQuery Implementation Experience and Perspectives XIME P 06 Chicago USA June 2006 George Lawton Making business intelligence more useful Computer 39 9 14 16 2006 Leonid Libkin Rona Machlin and Limsoon Wong A query language for multidimensional arrays Design implementat
76. ng Group By Cross Tab and Roll Up In 12 International Conference on Data Engineering ICDE 96 New Orleans USA pages 152 159 IEEE Computer Society 1996 Jim Gray Surajit Chaudhuri Adam Bosworth Andrew Layman Don Reichart Murali Venkatrao Frank Pellow and Hamid Pirahesh Data Cube A Relational Aggregation Operator Generalizing Group By Cross Tab and Sub Totals Journal of Data Mining and Knowledge Discovery 1 1 29 53 1997 32 GL97 GLS96 GVD 01 Hac99 HBH03 HWW 06 JLSTO1 JMP01 JPCJ 06 Kay06 Law06 LMW96 LW96 LW97 NNNT02 NZ06 Marc Gyssens and Laks V S Lakshmanan A foundation for multi dimensional databases In 23 International Conference on Very Large Data Bases VLDB 97 Athens Greece pages 106 115 Morgan Kaufmann 1997 Marc Gyssens Laks V S Lakshmanan and Iyer N Subramanian Tables as a paradigm for querying and restructuring In 15 ACM SIGACT SIGMODSIGART Symposium on Principles of Database Systems PODS 96 Montreal Canada pages 93 103 ACM 1996 Leonidas Galanis Efstratios Viglas David J DeWitt Jeffrey F Naughton and David Maier Following the paths of XML Data An algebraic framework for XML query evaluation Technical report University of Wisconsin USA 2001 Richard D Hackathorn Web farming for the data warehouse The Morgan Kaufmann Series in Data Management Systems Morgan Kaufmann 1999 Wolfgang Hiimmer A
77. nications Edinburgh UK volume 1819 of Lecture Notes in Computer Science pages 106 117 Springer 1999 BDD Plateforme d entreposage XML de donn es complexes Rapport technique P le Bases de Donn es D cisionnelles BDD Laboratoire ERIC Universit Lumi re Lyon 2 France http bdd univ lyon2 fr page projets 2006 Fadila Bentayeb Syst mes d Informations D cisionnels Support de cours Master Recherche ECD Universit Lumi re Lyon 2 France 2006 2007 Sujoe Bose Leonidas Fegaras David Levine and Vamsi Chaluvadi A Query Algebra for Fragmented XML Stream Data In 9 International Workshop on Database Programming Languages DBPL 03 Potsdam Germany volume 2921 of Lecture Notes in Computer Science pages 195 215 Springer 2003 Omar Boussaid Riadh Ben Messaoud R my Choquet and St phane Anthoard X Warehousing An XML Based Approach for Warehousing Complex Data In 10 East European Conference on Advances in Databases and Information Systems ADBIS 06 Thessaloniki Greece volume 4152 of Lecture Notes in Computer Science pages 39 54 Springer 2006 Peter Buneman Shamim A Naqvi Val Tannen and Limsoon Wong Principles of Programming with Complex Objects and Collection Types Theoretical Computer Science 149 1 3 48 1995 Damianos Chatziantoniou Michael O Akinde Theodore Johnson and Samuel Kim The MD join An Operator for Complex OLAP In 17 International Conference on Data Engineering ICDE 01 Heid
78. nn es multidimensionnelles CT97 CT98 Dans ce mod le les dimensions sont repr sent es en hi rarchies suivant un ordre pr d fini exprim par une relation de forage vers le haut Une famille de fonctions appel es fonctions de forage vers le haut roll up functions compl te la d finition d une dimension Le sch ma d un mod le multidimensionnel consiste alors en un ensemble fini de dimensions et un ensemble fini de tables de faits Malgr l int r t de leur approche Cabibbo et Torlone se limitent la formalisation de cette famille de fonctions de forage vers le haut et ne proposent pas d autres op rateurs 2 1 2 3 Alg bre pour les tables multidimensionnelles Ravat et al proposent un mod le qui sert de support une alg bre et un langage graphique pour l analyse et la visualisation des donn es RTZ06a RTZ06b Leur alg bre int gre les op rateurs OLAP classiques compl t s par des op rateurs avanc s afin de faciliter l expression d analyses d cisionnelles complexes Le mod le repose sur une repr sentation multi faits o chaque fait est analys en fonction d axes d analyse dimensions multi vues multi hi rarchis es Les auteurs mod lisent un cube de donn es par une structure de visualisation proche des arbres d attributs sous la forme d un tableau double entr e hi rarchis appel table multidimensionnelle TM RTZ01 L alg bre propos e repose sur un op rateur de construction display qui produi
79. nnel En plus de ces six op rateurs les fonctions d agr gation suivantes sont inclues dans l alg bre la moyenne avg le comptage count le maximum max le minimum min et la somme sum Elles sont toujours associ es une condition de type where et tiennent compte des r p titions de types Finalement une nouvelle notion sp cifique cette alg bre est introduite les fonctions Leur d finition suit le m me principe que dans les langages de programmation classiques nom param tres et type de retour Le but est de g n raliser via une fonction une op ration donn e L utilisateur peut d finir un nombre illimit de fonctions et utiliser des fonctions r cursives 2 2 1 2 Alg bre XAT Zhang et al proposent une alg bre pour les langages de requ tes XML ZPRO2 Baptis e XAT XML Algebra Tree elle permet de mod liser les requ tes XQuery sous forme d arbres avant de les optimiser au sein du syst me Rainbow ZDW 03 Les auteurs soutiennent l id e de traduire les donn es XML en relationnel mais utilisent aussi ces deux paradigmes simultan ment En entr e de Rainbow les donn es sont stock es dans des documents XML avant d tre transf r es dans des SGBD relationnels XAT est essentiellement con ue pour am liorer les performances de Rainbow en optimisant les requ tes Elle pr sente trois cat gories d op rateurs op rateurs XML op rateurs SQL et op rateurs sp cifiques XAT Les op rateurs classiques p
80. ns la liste de r ordonnancement La fonction de valeur indique la valeur que prend chaque n ud participant dans l ordre g n ral Ces trois derniers l ments sont illustr s dans la figure 9 Comme notre but est d inter changer les villes Nice et Lyon Paris parait cart de l analyse Pourtant l attribut correspondant cette ville doit tre indiqu dans l arbre mod le pour que Paris apparaisse dans le r sultat m me s il conserve son emplacement En d autres termes r ordonner les attributs d une dimension consiste indiquer la fois l ordre des attributs concern s et non concern s puisque ces derniers participent l ordre final Nous passons maintenant deux autres op rateurs structuraux la transformation d une dimension en mesure push et la transformation d une mesure en dimension pull Dans les alg bres OLAP discut es dans l tat de l art cf Section 2 1 nous ne retrouvons pas les r sultats de ces deux op rations sous la forme de cubes OLAP mais mod lis s dans des tables multidimensionnelles Pourtant Agrawal et al exposent ces deux op rateurs sur leur mod le de donn es de rep res trois dimensions mod lisant les cubes de donn es AGS96 AGS97 Nous avons donc recours ce travail puisque nous soutenons l id e de repr senter les cubes en rep res n dimensionnels dans notre alg bre e Transformation d une dimension en mesure push La transformation d une dimension en mesure push consiste
81. ns le mod le La liste de copie d termine les diff rentes valeurs des n uds apparaissant en sortie En r sultat nous obtenons le r sultat de la figure 13 e Transformation d une mesure en dimension pull Pour exprimer l op ration r ciproque de la transformation d une dimension en mesure Agrawal et al expriment la transformation d une mesure en dimension en repr sentant suivant leur mod le l ensemble de mesures sur un axe pour la transformer en mesure AGS96 AGS97 En r alit Agrawal et al partent d une repr sentation du r sultat d une transformation d une dimension en mesure pour arriver l tat initial en permutant les emplacement de la mesure et la dimension y associ e comme le montre la figure 14 Nous ne suivons pas leur logique bien qu elle soit juste dans le sens o elle est adapt e leur mod le car nous devons suivre les exigences du n tre Nous exprimons alors la transformation d une mesure en dimension avec TAX comme suit Si nous adoptons la mani re d exprimer la transformation d une dimension en mesure et que nous associions la mesure une dimension comme nous avons associ une dimension une mesure nous commettrions une erreur En fait selon le mod le de nitre alg bre une mesure est toujours repr sent e si elle existe comme la derni re branche du sous arbre mod lisant le fait en allant de droite gauche Repr senter la mesure avec toutes les dimensions permet selon notre mod le de la
82. nsemble de ces fils Dans notre cas le r sultat final est un arbre vide ne contenant aucun sous arbre 24 puisque tous les faits sont substituer Le noeud racine ventes reste par cons quent sans descendant pour le moment 2 Copier et coller Les noeuds supprim s l tape pr c dente doivent tre substitu s par d autres Nous pourrions utiliser alors l op ration TAX insertion de n uds Cependant selon Jagadish et al il est recommand d employer l op rateur copier et coller en cas d insertion de n uds accompagn s de leurs descendants JL STO1 Dans notre exemple nous copions et collons la place de chaque arbre supprim deux arbres contenant chacun les informations sur les ventes pour les arrondissements correspondants Par exemple la place de l arbre des ventes des souris Paris en 2004 il s agit de copier et coller les deux arbres de la figure 29 mod lisant les ventes des souris dans les 1 et 8 arrondissements Copier et coller prend en entr e un mod le d arbre une liste de copie et une liste de sp cifications La liste de copie indique les diff rentes valeurs que prendront les noeuds apparaissant dans le mod le en sortie Ainsi la liste de sp cifications indique que les arbres ins r s sont les descendants directs du noeud ventes issu de l op ration pr c dente de suppression de noeuds Tous ces l ments sont disponibles dans la figure 31 la fin nous obtenons seize arbres qui poss dent chacun
83. nt que leur alg bre peut supporter ces op rations Enfin Ravat et al d veloppent des op rateurs de forage vers le haut et vers le bas roll up et drill down qui ne s loignent pas dans leur fonctionnement de leurs quivalents dans les autres alg bres 2 2 Alg bres XML Dans cette section nous tudions les alg bres XML pr sent es dans la litt rature Bien que la plupart puisent leur logique dans celle des op rateurs relationnels de nouveaux op rateurs sont apparus avec XML Nous classons dans les sections suivantes les alg bres XML en quatre familles selon la logique d impl mentation suivie 1 alg bres pour les langages de requ tes XML 2 alg bres sur les arbres de donn es XML 3 alg bres sur les arbres de donn es XML pour l valuation de XQuery 4 alg bres XML pour l Extraction des Connaissances partir des Donn es ECD 2 2 1 Alg bres pour les langages de requ tes XML 2 2 1 1 Alg bre pour les requ tes XML En s inspirant essentiellement des notions issues de multiples langages comme SQL DD97 XPath CD99 et NRA alg bre relationnelle d imbrication Col90 BNTW95 LMW96 LW97 Fern ndez et al ont soumis au W3C World Wide Web Consortium une alg bre pour les requ tes XML riche et facile utiliser FSWO00 Les documents et les sch mas XML y sont transform s en nouveaux sch mas adapt s l alg bre Deux notions importantes les caract risent les types et les variables globales
84. od lisent les donn es multidimensionnelles dans des tables mais ces derni res sont loin d tre relationnelles Pour conclure cette diversit de mod les provient du fait que les syst mes d aide la d cision reposant sur la technologie OLAP ont exist avant la d finition d un fondement th orique standard et reconnu par la communaut des bases de donn es 2 1 3 2 Op rateurs Outre les op rateurs OLAP classiques la rotation rotate la permutation d une modalit dans une dimension switch le forage vers le haut ou vers le bas roll up ou drill down la s lection et la projection sur un cube slice et dice la traduction des mesures en dimensions ou des dimensions en mesures pull ou push et l op rateur cube et les op rateurs inspir s du relationnel peu d op rateurs ont t propos s pour enrichir l analyse en ligne en g n ral Parmi ceux ci nous pouvons cependant citer la suppression des redondances dans l alg bre de Gyssens et al ou encore les op rateurs de restructuration unfold et fold de Gyssens et Lakshmanan L inconv nient de ces nouveaux op rateurs est qu ils sont totalement d pendants du mod le de donn es Leur utilisation dans le cadre d une autre alg bre OLAP n cessite une adaptation au mod le qui lui est associ e De plus nous pouvons galement noter que ces op rateurs ont des synonymes dans d autres alg bres Par exemple unfold est quivalent l op rateur add dimension de Li et Wan
85. produit dans notre exemple 2 L analyste s lectionne ensuite sa dimension de jointure ann e dans notre exemple 3 Une liste de fonctions d agr gation est disponible pour choisir celle utiliser dans le forage vers le haut somme dans notre exemple 4 Enfin il ne reste pour l utilisateur qu cliquer sur un bouton pour g n rer la requ te permettant d assurer l op ration XOLAP forage le haut Dans notre programme nous associons la requ te g n r e la fonction XQuery 1 0 de s quence distinct values Cette derni re joue m me r le que la fonction SQL distinct en liminant les valeurs identiques d un attribut Malheureusement TIMBER ne prend pas en charge la fonction 28 distinct values Nous avons essay d exprimer la requ te avec l alg bre physique mais c tait impossible m me en ayant recours l op rateur limination de doublons duplicate elimination Les d veloppeurs de TAX nous ont confirm ces probl mes Une modification du code source TIMBER nous a cependant permis d ex cuter la requ te quivalente en alg bre physique Malgr les contraintes li es TIMBER notons que notre requ te XQuery assure le forage vers le haut sur tout autre syst me supportant XQuery 1 0 avec toutes ses fonctions Nous avons utilis l diteur XML XMLSpy pour g n rer le r sultat d un forage vers le haut avec XQuery figure 36 3 5 2 3 Op rateurs en cours d impl mentation Nos autres op rateurs sont e
86. que dans le cas relationnel Le second ensemble d op rateurs propose deux op rateurs de restructuration unfold et fold qui permettent de remanier la structure d un cube Unfold ajoute une nouvelle dimension dans le sch ma relationnel d un cube R ciproquement l lagage d une dimension d un cube est assur par fold 2 1 1 4 Alg bres pour l analyse en ligne OLAP Datta et Thomas proposent un mod le de cube de donn es supportant une alg bre OLAP DT99 Ce mod le de cube respecte la sym trie entre les dimensions et les mesures comme la sym trie entre les agr gations de types forage vers le haut roll up et valeurs num riques somme moyenne etc ou encore entre les transformations convertir une dimension en mesure et vice versa Cette sym trie est l origine des op rateurs OLAP propos s par les auteurs Ces derniers d finissent un cube comme un quadruplet D M A f D et M d signent les dimensions et les mesures respectivement Chaque D ou M est d finie par un nom relatif un domaine pr d fini Les ensembles des noms des dimensions et des noms d attributs sont disjoints repr sente un groupe d attributs chacun tant d fini par son nom extrait du domaine de noms d attributs Enfin f repr sente une fonction de D vers A qui permet d tablir la correspondance entre les dimensions et les attributs Les auteurs mod lisent aussi un cube mat rialis dans l ensemble D M A f V g V repr sente l ensem
87. r des attributs associ s des noeuds sp cifiques de l arbre La liste de noms possibles est d finie en entr e de cet op rateur Le renommage TAX est analogue au renommage des attributs dans les tables relationnelles L op rateur de r ordonnancement reordering permet de modifier l ordre des descendants d un n ud donn ou encore le groupement de plusieurs n uds en un seul Le r ordonnancement prend en entr e une collection d arbres le mod le suivre et la liste des noeuds cibles Les auteurs ont galement enrichi leur travail par un op rateur copier et coller copy and paste qui permet de dupliquer de nouveaux n uds dans l arbre Une autre op ration de mise jour des arbres est galement propos e via la mise jour des valeurs value updates des attributs des n uds Ici les noeuds cibles sont d finis dans le mod le Une liste sp cifiant les noms possibles qui peuvent tre constants d riv s d autres noms ou encore d j existants est associ e au mod le en entr e de l op ration L alg bre est galement munie d un op rateur de suppression de n uds node deletion pour lequel une liste de noeuds supprimer doit tre d finie Le dernier op rateur est l insertion de neuds node insertion Lors de cette op ration certaines informations doivent tre fournies la position d insertion ainsi que l adaptabilit des noeuds associ s l objet ins r Le copier et coller peut tre utilis pour indiquer les n
88. r les op rateurs les op rateurs disponibles l expressivit de l alg bre et les r gles d optimisation possibles ZY 04 14 2 2 5 1 Mod le de donn es Le mod le de repr sentation des documents XML g n ralement adopt dans la litt rature est un arbre de donn es enracin ordonn et tiquet Il n existe pas pour autant de repr sentation standard Dans XAL chaque document XML est repr sent par un graphe enracin avec une relation partielle d ordre d finie entre ses diff rentes ar tes Niagara mod lise le document XML en un graphe enracin et orient en indiquant les l ments et les attributs correspondants ainsi que leur ordre par des num ros au niveau des sommets du graphe TAX et les alg bres qui en sont d riv es traitent les documents XML comme des for ts d arbres enracin s et tiquet s Le mod le de Pradhan n glige l ordre des noeuds du fragment recherch dans l arbre initial mais les relie avec le plus proche noeud parent commun et associe chaque n ud un ou plusieurs mots cl s utiles dans la recherche d information Une originalit des arbres de Bose et al est la pr sence de noeuds vides ou trous holes auxquels d autres sous arbres enracin s les remplisseurs fillers peuvent tre associ s dans le but de relier les fragments des documents XML Finalement Zhang et Yao exploitent aussi des mod les d arbres tiquet s dans leur alg bre sans plus de pr cision Finalement certains auteu
89. remier op rateur de Niagara source prend en entr e un ou plusieurs types de documents XML DTD XML DTD En sortie il fournit une collection d ensembles de singletons repr sentant les racines XML qui satisfont un crit re pr d fini Suivi follow a le m me r le que la projection dans TAX XAL et l alg bre relationnelle Il s lectionne les l ments de chaque collection suivant l expression de chemin d finie Homologue au concept de s lection dans les autres alg bres la s lection consiste ici filtrer les ensembles et conserver seulement ceux qui respectent un pr dicat bas sur les op rateurs gt lt etc De m me la jointure consiste rassembler deux collections sur la base d un pr dicat L union l intersection et le produit cart sien sont aussi d finis dans Niagara Appliqu s sur des collections ils conservent le principe alg brique d fini en relationnel Le groupement permet finalement de r unir les l ments correspondants aux chemins indiqu s en param tres L ordre de groupement est aussi exprim comme param tre d entr e Trois nouveaux op rateurs sont galement propos s La cr ation de sommet vertex prend en entr e l tiquette d une ar te et cr e le sommet correspondant en sortie L exposition expose permet de rechercher les l ments sp cifiques d une collection selon le chemin indiqu en param tre Enfin le renommage permet de modifier les l ments d une collection en changeant leur
90. ribut l ment selon lequel se r alise la coupe Ecran est associ la d finition de l arbre mod le comme le montre la figure 18 La liste de s lections doit contenir obligatoirement le n ud 7 1 tag vente pour garantir la conservation de tous ses l ments fils dans le r sultat l issue de cette s lection nous obtenons un ensemble d arbres vente s par s que nous r unissons tous sous une seule racine ventes via une production TAX e D tachement d un d du cube dice Le d tachement d un d du cube retire sous cube du cube de donn es multidimensionnel selon certains pr dicats d finis sur ses dimensions Certaines r f rences consid rent que le d tachement d un d du cube est une projection sur une ou plusieurs dimensions du cube Ben07 D autres la consid rent comme une s lection dans le sens de la r duction dimensionnelle pas dans le sens relationnel Gar07 Wik07 Pour notre part nous partons du principe g n ral de l op ration consistant s lectionner les mesures d un cube pour un certain nombre d attributs dimensionnels qui doit tre le m me pour tous les axes du cube De plus les cellules du d r sultant peuvent tre attach es ou non ensemble dans le cube original Adi05 Un exemple de d tachement d un d du cube est disponible dans la figure 19 dans lequel nous conservons de notre cube XOLAP exemple que les ventes des souris et des claviers Lyon et Nice en 2004 et 2005 Pour exprimer un
91. rmet de convertir les mesures en dimensions selon une fonction de transformation Push permet de r aliser l op ration inverse en utilisant aussi une autre fonction de transformation d di e Un second travail des m mes auteurs utilise ce mod le et propose une autre alg bre de neuf op rateurs TDO1 Sept d entre eux ne sont pas modifi s La restriction l agr gation l union et la diff rence ont conserv les m mes noms et principes Le produit cubique les extractions des dimensions et des mesures remplacent le produit cart sien pull et push respectivement Deux nouveaux op rateurs sont la projection m trique et le renommage La projection m trique r duit le nombre d attributs correspondant aux mesures prises en compte dans la repr sentation des donn es Le renommage permet de rebaptiser les l ments d un ensemble d attributs ou de caract ristiques mesures ou dimensions 2 1 2 Extensions des concepts multidimensionnels 2 1 2 1 Alg bre pour les matrices bidimensionnelles Gyssens et al proposent une alg bre pour les donn es multidimensionnelles mod lis es de facon tabulaire GLS96 Rang es dans des tableaux bidimensionnels les donn es peuvent tre des noms des valeurs num riques ou nulles En l absence d une structure fig e les tables peuvent prendre plusieurs formes tout en respectant l aspect multidimensionnel des donn es Les auteurs d finissent ensuite une alg bre tabulaire et tablissent une cat gorisation
92. rojection s lection etc sont exprim s en SQL Les op rateurs sp cifiques assurent les diff rentes phases d optimisation Les op rateurs XML d union d intersection de diff rence et d agr gation op rent sur les colonnes o sont stock es les donn es XML apr s leur transformation en relationnel L exposition expose permet de visualiser ces colonnes comme des fragments ou des documents XML l tiquetage tagger d tiqueter une liste de donn es selon un mod le et enfin la navigation navigate de parcourir les donn es XML contenues dans une colonne selon le chemin indiqu 2 2 1 3 Alg bre XML pour XQuery Novak et Zamulin proposent une alg bre pour XQuery qui se limite volontairement des structures de premier ordre NZ06 Cette alg bre est bas e sur des expressions et respecte un mod le signature de base de donn es XML sp cifi par les auteurs Une expression l mentaire est une s quence de n uds sequel de l arbre qui repr sente le document XML Elle est not e Seg Node 2Seq Node Cette s quence peut respecter l ordre des n uds dans l arbre document order ou non reverse order Une expression incorpore aussi des accesseurs de n uds node kind node name parent string value type children attributes et nilled Afin d orienter le parcours de ces expressions dans l arbre XML les auteurs d finissent et formalisent des fonctions de navigation parcours Ces fonctions repr sentent les diff rents ax
93. rs adoptent des repr sentations ad hoc Fern ndez et al mod lisent les documents XML sous forme de sch mas compos s de types et de variables globales Les for ts d finies dans ce mod le peuvent tre ordonn es ou non Les for ts non ordonn es sont exploit es pour les jointures par exemple Zhang et al repr sentent les requ tes XQuery en arbres au sein de l architecture Rainbow Selon les besoins d analyse certaines donn es XML conservent leur structure tandis que d autres sont traduites en relationnel Enfin Novak et Zamulin structurent les documents XML dans un mod le de base de donn es XML bas sur XPath 2 2 5 2 Unit de base de l information Par analogie avec les op rateurs relationnels qui op rent sur des collections de n uplets les op rateurs des alg bres XML agissent sur des collections d entit s Dans XAL et Niagara l entit de base est le sommet l ment ou attribut Dans ce cas un op rateur re oit en entr e et fournit en sortie une collection de sommets Par contre les op rateurs de TAX et de ses d riv es ainsi que l alg bre pour l ECD de Zhang et Yao prennent en entr e et produisent en sortie une collection d arbres De plus un arbre mod le et un arbre t moin accompagnent chaque op ration en entr e et en sortie respectivement Selon Pradhan l unit d information de base est le fragment qui repr sente une suite de n uds de l arbre repr sentant le document XML L unit de base de l infor
94. s tiquettes Les anciennes et les nouvelles tiquettes sont indiqu es en param tres 2 2 3 Alg bres sur les arbres de donn es XML pour l valuation de XQuery Les alg bres pr sent es dans les sections pr c dentes visent optimiser les langages de requ tes XML en g n ral Dans cette section nous pr sentons les alg bres sur les arbres XML qui sont con ues plus sp cifiquement pour l valuation du langage XQuery 2 2 3 1 Alg bre TLC Sur la base des notions introduites dans TAX Paparizos et al proposent une nouvelle alg bre pour les classes logiques d arbres nomm e TLC Tree Logical Class PWLJ04 Par d finition une classe logique contient l ensemble des n uds communs entre les arbres mod les et t moins Dans TLC les branches de l arbre mod le sont annot es par les signes ou Cette extension g n ralise le principe de correspondance matching entre les arbres mod les et les arbres en entr e Le signe indique qu une et une seule correspondance peut tre r alis e Le signe correspond z ro ou plusieurs correspondances En cas d utilisation de il est impossible d aller au del d une seule correspondance tandis que l emploi de autorise un nombre illimit de correspondances L alg bre TLC est con ue pour manipuler l h t rog n it au sein des requ tes XQuery partir d exemples r els les auteurs montrent qu une requ te XQuery peut tre vue comme une suite d op rations logiques
95. s de jointure La mesure contenue dans cette cellule repr sente le r sultat de l agr gation somme des ensembles de mesures du r sultat de jointure En fait le r sultat de cette agr gation est le m me quel que soit l axe choisi pour cette op ration Il suffit alors de sommer deux cellules en suivant un m me axe pour obtenir le bon r sultat Dans TAX obtenir l arbre quivalent cette cellule se fait en joignant une deuxi me fois chacun des deux arbres r sultants de la jointure selon chaque axe et en appliquant une agr gation de type somme sur chaque arbre Et puisque nous obtenons trois r sultats identiques dans les trois cas il ne reste qu grouper les trois arbres en un seul Comme le groupement limine les doublons du r sultat une seule mesure est conserv la fois dans le r sultat final alors Nous justifions le choix du groupement par le fait que l arbre correspondant cette derni re cellule est exprim selon les trois axes au m me temps tout en repr sentant le plus haut niveau d agr gation sur le cube Sur le cube OLAP de la figure 32 4 la cellule courante est celle qui repr sente la mesure 685 En achevant toutes les tapes de l expression de l op rateur de cube de donn es nous obtenons un arbre TAX contenant les 32 sous arbres issus de toute cette d marche Chaque sous arbre correspond une cellule de cube de donn es de la figure 32 4 3 4 Discussion Dans cette section nous discutons l alg bre XOL
96. sp cifiques au sein d un seul syst me permet d atteindre un tr s bon niveau d optimisation Finalement dans les algorithmes pour l ECD plusieurs op rateurs de l alg bre de Zhang et Yao peuvent tre employ s la fois 2 3 Alg bres XOLAP Dans cette section nous nous int ressons aux travaux qui abordent XML et OLAP dans un m me contexte Ces travaux ne pr sentent pas de v ritables alg bres XOLAP compl tes mais forment des tentatives int ressantes de d finition d un environnement XML OLAP et des notions associ es Jensen et al proposent un travail qui se r sume en trois points JMPO1 Ils pr sentent tout d abord une architecture d int gration des donn es XML et relationnelles Ils proposent ensuite une mod lisation multidimensionnelle des bases de donn es XML relationnelles OLAP avec UML OMG07 Enfin les auteurs illustrent les consid rations n cessaires prendre en compte pour concevoir des bases de donn es XML supportant des analyses OLAP En sortie du syst me d int gration propos les donn es sont pr sent es en relationnel et valu es avec OQL Dans la m me logique Niemi et al pr sentent une architecture d int gration de donn es XML et un mod le de base de donn es OLAP exploit s par un langage d di MDX NNNT02 Dans ces deux travaux les op rateurs OLAP sp cifiques XML sont absents puisque les donn es OLAP sont exploit es avec des langages de requ tes pour les donn es relationnelles
97. t XQuery Les perspectives qui s offrent nous sont de trois ordres Premi rement nous comptons poursuivre l impl mentation de notre proposition d alg bre XOLAP logique au niveau physique dans le cadre d une plateforme d entreposage XML de donn es complexes en cours de conception dans notre laboratoire BDD06 Notre objectif est de permettre travers une interface simple et accessible depuis le Web la construction et la manipulation de cubes XML Dans un second temps et en plus des op rateurs d finis nous comptons incorporer dans notre alg bre et notre prototype de nouveaux op rateurs sp cifiques au contexte XML Il nous para t par exemple particuli rement int ressant de pouvoir effectuer des op rations de forage roll up et drill down sur des hi rarchies de dimensions complexes telles que les ragged hierarchies mentionn es par Beyer et al BCC 05 L objectif de ce travail est de venir en support des extensions en cours du langage XQuery pour les applications d cisionnelles Pour terminer l efficacit du langage XQuery s tant av r e au cours de nos tests limit e pour ex cuter des requ tes d cisionnelles nous envisageons d exploiter notre alg bre XOLAP comme support de l optimisation automatique de requ tes OLAP exprim es en XQuery 30 Bibliographie Adi05 AGS96 AGS97 BB03 BC04 BCC 05 BCF 07 BCH99 BDD06 Ben07 BFLCO03 BMCA06 BNTW95 CAJKO1
98. t une TM partir d une base de donn es multidimensionnelle et sur un ensemble de onze op rateurs fondamentaux portant sur les TM et facilitant la manipulation OLAP Le premier op rateur la rotation permet de remplacer un axe d analyse par un autre ou de changer la hi rarchie sur un m me axe au sein d une TM Les forages vers le bas ou vers le haut drill down ou roll up autorisent la modification des diff rents niveaux de granularit utilis s pour visualiser les donn es au sein d une TM Les dimensions de la TM peuvent tre enrichies par des attributs suppl mentaires en employant l op rateur d imbrication nest La s lection restreint l ensemble des valeurs affich es des attributs dimensionnels et des mesures correspondantes L op rateur d organisation switch intervertit deux valeurs d un attribut d une dimension pour permettre l ordonnancement des valeurs affich es Le calcul d agr gats permet d ajouter dans une TM des calculs agr geant ses lignes et ou ses colonnes L op rateur de conversion d un param tre en mesure push transforme un param tre dimension en mesure au sein de la TM La conversion d une mesure en param tre pull transforme une mesure en param tre dimension Enfin les op rateurs d ajout addm et de suppression delm de mesures permettent de modifier l ensemble des mesures calcul es 2 1 3 Discussion Pour valuer les diff rentes alg bres OLAP pr sent es dans les sections pr c dentes nous
99. tes XPath aux requ tes SOLM SQLM est lui m me une extension de SQL pour le traitement des donn es multidimensionnelles PRPO2a L ensemble des travaux de Pedersen et al repr sente l heure actuelle la seule v ritable tentative de d finition d une alg bre permettant de r aliser une analyse en ligne OLAP sur des cubes XML Toutefois cette alg bre se caract rise par seulement deux op rateurs initiaux exprim s en SQL la s lection et la projection g n ralis e qui correspondent ce que nous connaissons sous le nom de slice et dice dans les alg bres OLAP classiques 17 3 Alg bre XOLAP propos e Dans ce chapitre nous pr sentons en d tail notre alg bre XOLAP mod le de donn es op rateurs et mise en pratique de l alg bre Nous pr sentons au pr alable la probl matique et l objectif de notre stage et nous justifions notre choix de l alg bre TAX pour atteindre nos objectifs Toutes les figures utilis es dans la pr sentation des op rateurs de notre alg bre sont disponibles en annexe 3 1 Probl matique et objectif de stage ce stade nous avons avec en point de mire la d finition d une alg bre XOLAP dress un tat de l art que nous esp rons le plus exhaustif possible au sujet des alg bres OLAP cf Section 2 1 et des alg bres XML cf Section 2 2 Les op rateurs OLAP existants tant d finis dans un contexte soit relationnel soit multidimensionnel il nous reste d sormais les adapter au mod le
100. uivante Par rapport Map Kleene Star inclut la collection d entr e en plus dans le r sultat Finalement les op rateurs de construction permettent de manipuler la structure des documents XML nouveaux sommets et ar tes La cr ation de sommet create vertex premier op rateur de construction pr sent ajoute un nouveau sommet n ud au graphe Le type et la valeur m me nulle des noeuds sont indiqu s en entr e de l op rateur L ajout de nouvelles ar tes est assur via l op rateur de cr ation d ar te create edge qui prend en entr e les noeuds p re et fils relier ainsi que le type et le nom de la nouvelle liaison et renvoie le sommet fils Pour terminer partant du besoin de copier des sommets et des ar tes dans le but d enrichir les graphes Frasincar et al d finissent un op rateur de copie d exemples copy examples Copier un sommet revient cr er un nouveau sommet avec le type et la valeur du sommet original Copier une ar te n cessite la copie de tous les noeuds parents et fils correspondants En cons quence copier un graphe complet en partant d un sommet donn consiste copier tous ses sous graphes ainsi que les graphes les reliant ce sommet 12 2 2 2 4 Alg bre Niagara Niagara est une alg bre pour langages de requ tes XML qui se base galement sur une mod lisation des documents XML en graphes GVD 01 Dans ce mod le les attributs sont mod lis s au niveau le plus bas de l arbre Le p
101. upement les deux mesures en une seule en ayant recours l op rateur d agr gation TAX Nous remarquons dans la figure 32 3 que quelques r sultats de groupements se r p tent Par exemple le couple d arbres v2 v22 est similaire v25 v26 Nous remarquons que ces deux combinaisons de sous arbres repr sentent une dimension commune produit L emplacement des 25 cellules correspondantes dans le cube final est alors effectu suivant cet axe In es est de m me pour les combinaisons v23 v24 v31 v32 l axe en commun ici est ville et v27 v28 v29 v30 l axe en commun ici est annee Sur le sch ma du cube il suffit de repr senter une des deux combinaisons pour chaque axe puisque les valeurs de mesures se r p tent chez la combinaison quivalente En faisant la correspondance des cellules avec les arbres de faits TAX il suffit de joindre via une jointure TAX les quatre arbres des deux ensembles selon leur axe commun entre eux Par exemple nous joignons les arbres v2 v22 v25 et v26 selon la dimension produit De m me pour v23 v24 v31 v32 jointure selon les villes et v27 v28 v29 v30 jointure selon les ann es La compl tion du cube de la figure 32 3 est illustr e dans la figure 32 4 En arrivant au r sultat de la figure 32 4 nous remarquons qu une seule cellule manque pour constituer le cube final En effet cette cellule correspond au point de contact entre les trois r sultat
102. ur l analyse en ligne OLAP Extensions des concepts multidimensionnels 2 1 2 1 Alg bre pour les matrices bidimensionnelles 2 1 2 2 Alg bre pour les informations r parties en niveaux 2 1 2 3 Alg bre pour les tables multidimensionnelles Discussion 2 1 3 1 Mod le de donn es 2 1 3 2 Op rateurs 2 1 3 3 Granularit des donn es 2 2 Alg bres XML 22 1 2 2 2 2 2 3 2 2 4 Didi Alg bres pour les langages de requ tes XML 2 2 1 1 Alg bre pour les requ tes XML 2 2 1 2 Alg bre XAT 2 2 1 3 Alg bre XML pour XQuery Alg bres sur les arbres de donn es XML 2 2 2 1 Alg bre pour la recherche d information dans des fragments XML 2 2 2 2 Alg bre logique TAX et alg bre physique d riv e 2 2 2 3 Alg bre XAL 2 2 24 Alg bre Niagara Alg bres sur les arbres de donn es XML pour l valuation de XQuery 2 2 3 1 Alg bre TLC 2 2 3 2 Alg bre de requ tes pour les flux de donn es XML fragment es Alg bres XML pour l ECD Discussion 2 2 5 1 Mod le de donn es 2 2 5 2 Unit de base de l information 2 2 53 Op rateurs 2 2 5 4 Expressivit 2 2 5 5 R gles d optimisation 2 3 Alg bres XOLAP 3 Alg bre XOLAP propos e 3 1 Probl matique et objectif du stage 33 ov V 00 0 00 00 1 1 01 0 O t Un Un tA 11 11 13 13 13 14 14 14 15 15 15 16 16 18 18 3 2 Justification du choix de TAX 3 3 Alg bre XOLAP 3 3 1 Mod le de donn es 3 3 2 Op rateurs 3 3 2 Op rateurs li

Algèbre XOLAP - Université Lumière Lyon 2

Contents

Download Pdf Manuals

Related Search

Related Contents

Alg&egrave;bre XOLAP - Universit&eacute; Lumi&egrave;re Lyon 2

Contents

Download Pdf Manuals

Related Search

Related Contents

Algèbre XOLAP - Université Lumière Lyon 2