Quelles sont les caractéristiques d'un entrepôt de données ?
Caractéristiques de la conception d'entrepôts de données
Une conception d'entrepôt de données utilise un thème particulier.
Il fournit des informations sur un sujet plutôt que sur les opérations d'une entreprise.
Ces thèmes peuvent être liés aux ventes, à la publicité, au marketing, etc.Quels sont les différents types de données en informatique ?
Les données peuvent être divisées en 2 grandes catégories.
Catégoriques et quantitatives.
Les données catégories peuvent être subdivisées en données nominales et ordinales.
Les données quantitatives peuvent être discrète ou continue et sont aussi appelées données numériques.Comment fonctionne un entrepôt de données ?
Les entrepôts de données utilisent un serveur de base de données pour extraire les données des bases de données d'une entreprise et disposent de fonctionnalités supplémentaires pour la modélisation des données, la gestion du cycle de vie des données, l'intégration des sources de données, etc.
- Un entrepôt de données est conçu spécialement pour analyser des données, ce qui implique la lecture de grandes quantités de données dans le but de comprendre les relations et les tendances entre ces données.
Entrepôt de Données et Fouille de Données Un Modèle Binaire et
Développement dune nouvelle technique de compression pour les
MEMOIRE DE MASTER DEVELOPPEMENT ET EVALUATION DES
21st Century Learning and the 4Cs
The 4 Cs
Demonstrating Competency in the 21st Century Skills (4 Cs)
Content and Language Integrated Learning: The Four Cs of CLIL
The 4 Cs to 21st Century Skills
Table 34: Best Practices of the Four Cs
L'informatique des entrep^otsde donneesDaniel LemireSEMAINE6Compression dans les bases de donnees6.1.
Presentation de la semaineNous avons deja vu a la semaine precedente le codage par plage, et ler^ole important que cette technique de compression joue dans la con-struction de certains index, comme les index bitmaps.
Il existe cepen-dant plusieurs techniques de compression qui sont importantes dans lesentrep^ots de donnees.La compression procure plusieurs beneces.
D'abord, elle permetde stocker plus d'information sur des disques. Mais ce n'est pas lafonction la plus importante en ce qui nous concerne.La compressionpermet aussi de passer plus de donnees du disque aux microprocesseurs.En eet, des donnees compressees se chargent souvent plus rapidementen memoire.
De plus, la compression permet de conserver plus dedonnees en memoire.Nous verrons cette semaine plusieurs techniques de compressionpopulaires.6.2.
Theorie de l'informationEtant donne un chier, jusqu'a quel point pouvons-nous le compresser?Intuitivement, plus un document contient d'information, plus il seradicile de le compresser.
En eet, un chier qui ne contiendrait qu'uneseule lettre (a) repetee des milliers de fois ne contiendrait pas beaucoupd'information et serait donc facile a compresser (par codage par plage).12DANIEL LEMIRE, ENTREP^OTS DE DONNEESExemple 1.J'ai un texte de 3 mots,et
Je choisisd'abord de representer le premier mot sous la forme binaire<00>, lesecond sous la forme<10>et le dernier sous la forme<11>.
LasequenceShannon savait qu'il etait possible d'^etre encore plus ecace.En eet, il a represente le premier mot avec un seul bit :<0>.
Lasequence
Ilfut le premier a proposer une mesure d'entropie pour l'information:c'est-a-dire une limite fondamentale a la compression des donnees.A lire :http://fr.wikipedia.org/wiki/Theorie_de_l'informationConsiderons une cha^ne dencaracteres ou le caracterexappara^tf(x) fois.
La probabilite de selectionner ce caractere, au hasard, estdonc dep(x) =f(x)=n. La quantite d'information associee au caracterexest delogp(x)1.L'entropie de Shannon de la cha^ne de caracteresest dePxp(x)logp(x) ou la somme est sur l'ensemble des caracteres.La quantite d'information dans le texte est dePxnp(x)logp(x).Cette quantite d'information est un seuil minimal: la plupart des tech-niques de compression statistiques (basees sur la frequence des carac-teres) ne permettent pas d'utiliser moins dePxnp(x)logp(x) bits.Exemple 2.Prenons un texte de 2 mots, l'un ayant une frequence de500 et l'autre, de 250, pour un total de 750(n= 750).
Nous avonsalorsp(1) = 500=750 = 2=3etp(2) = 250=750 = 1=3.La quantited'information du premier mot est delog2(2=3)0;58et la quantited'information du second mot est delog2(1=3)1;58.
Pour coder letexte, il faut donc au moins((2=3)log2(2=3)(1=3)log2(1=3))750688bits, soit environ 86 octets.
Vous pouvez tester ce resultat engenerant un texte de seulement 2 mots qui comporte les frequences pre-scrites.
Vous constaterez que, quels que soient vos eorts de compres-sion avec zip ou avec un autre outil, vous n'arriverez pas, sans tricher,a un chier qui fait moins de 688 bits.
1) En informatique, le logarithme est toujours en base deux.LECTURE 6. COMPRESSION DANS LES BASES DE DONNEES36.3.Compression statistiqueIl y a plusieurs techniques de compression statistiques qui sont util-isees dans les entrep^ots de donnees tel que le codage de Human etla compression Lempel-Ziv-Welch [18].
Ces techniques compressentecacement les donnees, surtout lorsque certains caracteres, ou cer-tains cha^nes de caracteres sont frequemment repetees.
Par contre,elles sont relativement lentes bien qu'il existe des strategies permettantd'accelerer la decompression [15].A lire :http://fr.wikipedia.org/wiki/Codage_de_HuffmanA lire :http://fr.wikipedia.org/wiki/Lempel-Ziv-Welch6.4.
Codage des dierencesLe codage des dierences compresse les donnees en stockant les dif-ferences entre les valeurs successives plut^ot que les valeurs elle-m^emes.Si les valeurs sont triees, ou partiellement triees (par block), ce mode decompression peut ^etre tres ecice.
Elle s'applique pour plusieurs typesde donnees, incluant m^eme les nombres a virgule ottante [6, 11, 9, 4].On l'utilise dans les bases de donnees orientees-colonnes [14, 8, 7, 10].Formellement, le code fonctionne comme suit.
Nous voulons coderune liste d'entiersx1;x2;:::dansf0;1;2;:::;N1g. La premierevaleur est toujours stockee sans compression. Ensuite, on stocke lesvaleursxi+1ximodN2pouri= 1;2;:::. On s'attend a ce que laplupart du temp, cette dierence soit petite. Il se trouve qu'on peutstocker en memoire de petits entiers en utilisant peu de bits [17, 19,16, 1].La technique la plus simple est le codage a octet variable [12,3, 17, 20] : on stocke les premiers 7 bits de la valeur, puis on utiliseun bit supplementaire pour indiquer si un octet supplementaire seranecessaire pour le stockage, et ainsi de suite.6.5.
Codage des cha^nes frequentesIl existe une strategie de compression remarquablement simple qui estsouvent tres ecace.
Le codage des longues cha^nes repetees [2] est util-ise par Google [5] et dans le systeme de bases de donnees IBM DB2.
Leprincipe est fort simple : on traverse l'ensemble de la base de donnees,et on cherche de longues cha^nes de caracteres repetees.
On construitalors un dictionnaire de ces cha^nes, et chaque fois qu'on en rencontreune dans une table, on la remplace par un identiant correspondant ala cha^nes en question.
2) On peut aussi stocker la valeurxixi+1ouest le ou exclusif.4) DANIEL LEMIRE, ENTREP^OTS DE DONNEESExemple 3.Prenons la cha^ne de caracteresaaabbbacdbacdbacd-babbbb.
On decouvre la cha^ne de caracteresbacd.On lui associedonc un identiant, par exemple l'entier 1, et on substitue cet identi-ant dans la cha^ne originale:aaabb111babbbb.6.6.
Compression des prexesIl se produit souvent que, dans une sequence de valeurs, plusieursprexes sont recurrents.
Prenons par exemple la sequenceaaabb,aaabcc,aaaccc.La compression des prexes calcule d'abord unecha^ne de caracteres qui permettra d'identier des prexes.
Dans cecas particulier, prenons la cha^neaaabcc.On prend alors chaquecha^ne de caracteres dans notre sequence et on la compare avec cettecha^ne de reference.
D'abord on constate que la cha^neaaabbreutiliseles 4 premiers caracteres de la cha^ne de reference: on peut donc lastocker comme etant4b.
La cha^neaaabccest indentique a la cha^nede reference: il n'y a donc rien a stocker.La derniere cha^ne,aaaccc,peut ^etre codee comme etant3ccc.A consulter :http://msdn.microsoft.com/en-us/library/cc280464.aspx6.7.
Questions d'approfondissement(a)Le si teT witterp ermeta uxu tilisateursd ep ublierd esm essagesde 140 caracteres ou moins.
Est-ce que la compression Lempel-Ziv-Welch est appropriee dans ce cas?(b)S oitl esn ombresd e0 a2 321.
En utilisant 32 bits par nombre,combien faut-il d'octets pour les stocker? En utilisant le codagedes dierences, quel est le taux de compression?6.8.
Reponses suggerees(a)La compression Lempel-Ziv-Welch ne compresse queles cha^nes de caracteres susamment longues.
Mal-heureusement, elle risque d'^etre inecace sur des cha^nesde 140 caracteres.(b)Il faut 2324 = 234octets pour stocker la liste sanscompression.
Avec le codage des dierences, chaque dif-ference est de 1, ce qui ne requiert qu'un seul octet. Letaux de compression est donc de 1:4.BIBLIOGRAPHIE1.V. N. An ha ndA.M oat.In vertedi ndexco mpressionu singw ord-aligned binary codes.Information Retrieval, 8(1):151{166, 2005.2.J.
B entleya ndD .M cIlroy.Da taco mpressionwi thl ongr epeatedstrings.Information Sciences, 135(1-2):1{11, 2001.3.B .Bh attacharjee,L .L im,T.
Mal kemus,G. Mi haila,K. R oss,S. Lau, C. McArthur, Z. Toth, and R. Sherkat. Ecient indexcompression in DB2 LUW. InVLDB'09, pages 1462{1473, SanJose, CA, USA, 2009. VLDB Endowment.4.M.Bu rtscheran dP .R atanaworabhan.Hi ght hroughputco mpres-sion of double-precision oating-point data.
InDCC'07, pages 293{302, 2007.5.F .Ch ang,J. De an,S .Gh emawat,W. C. Hsi eh,D. A. W allach,M. Burrows, T. Chandra, A. Fikes, and R. E. Gruber. Bigtable:A distributed storage system for structured data.ACM Trans.Comput. Syst., 26(2):1{26, 2008.6.V.En gelson,D .F ritzson,a ndP .F ritzson.L osslessc ompressiono fhigh-volume numerical data from simulations.
InDCC'00, pages574{586, 2000.7.A. L .Ho llowaya ndD .J. D eWitt.Rea d-optimizedd atabases,i ndepth. InVLDB'08, pages 502{513, San Jose, CA, USA, 2008.VLDB Endowment.8.A. L .Ho lloway,V. R aman,G .S wart,a ndD. J. D eWitt.Ho wto barter bits for chronons: Compression and bandwidth trade osfor database scans. InSIGMOD'07, pages 389{400, New York,NY, USA, 2007. ACM.9.P .L indstroman dM.Isen burg.F astan de cientco mpressiono foating-point data.IEEE Transactions on Visualization and Com-puter Graphics, 12(5):1245{1250, 2006.56DANIEL LEMIRE, ENTREP^OTS DE DONNEES10.V.
R amanan dG.S wart.Ho wt ow ringa t abled ry:En tropycompression of relations and querying of compressed relations.
InVLDB'06, pages 858{869, 2006.11.P .Ra tanaworabhan,J. Ke, an dM. Bu rtscher.F astl osslessco m-pression of scientic oating-point data. InDCC'06, pages 133{142, 2006.12.F .S choler,H. Wi lliams,J. Yi annis,a ndJ. Z obel.C ompressionof inverted indexes for fast query evaluation. InSIGIR'02, pages222{229, New York, NY, USA, 2002. ACM.13.C. E. S hannon.A m athematicalt heoryo fc ommunications.BellSyst. Tech. J, 1948.14.M. S tonebraker,D .J. Ab adi,A. Ba tkin,X. Ch en,M. Ch erniack,M. Ferreira, E. Lau, A. Lin, S. Madden, E. O'Neil, P. O'Neil,A. Rasin, N. Tran, and S. Zdonik. C-Store: a column-orientedDBMS. InVLDB '05, pages 553{564, San Jose, CA, USA, 2005.VLDB Endowment.15.T. A. W elch.A t echniquefo rh igh-performanced ataco mpression.Computer, 17(6):8{19, 1984.16.H. Y an,S .D ing,an dT. S uel.I nvertedi ndexcom pressiona ndquery processing with optimized document ordering. InWWW'09, pages 401{410, 2009.17.J. Z hang,X. L ong,an dT. S uel.P erformanceo fco mpressedi n-verted list caching in search engines. InWWW '08, pages 387{396,2008.18.J. Zi van dA.L empel.C ompressiono fi ndividualse quencesv iavariable-rate coding.IEEE Transactions on Information Theory,24(5):530{536, 1978.19.J. Z obela ndA.
Mo at.In verted lesfo rt exts earchen gines.ACMComputing Surveys, 38(2):6, 2006.20.M. Zu kowski,S .Hem an,N.
Nes, a ndP .Bo ncz.S uper-scalarRAM- CPU cache compression. InICDE '06, Washington, DC, USA,2006. IEEE Computer Society.