Tehnologia Data Warehouse. Metode de Analiza Factoriala

Tehnologia Data Warehouse

Capitolul l Introducere

In lumea anilor 2000, o dată cu fenomenul de globalizare și continua creștere economică, nevoia de a asigura un management performant se manifestă din ce în ce mai intens. Dinamismul evoluției economiei, crescut și el în ultima vreme cere din partea companiilor să se adapteze rapid la orice schimbare; în plus, dimensiunile afacerilor au crescut, la fel ca și dimensiunile pieței. Pentru a lua deciziile optime, conducerile companiilor au nevoie de date despre evoluția afacerii în trecut pe baza cărora să se poată face prognoze de calitate pe termen scurt, mediu sau lung. Competiția e neiertătoare și fiecare pas greșit costă. Dictonul folosit de economiști pentru a exprima această realitate este foarte sugestiv : "what you don't know can hurt you" (ceea ce nu știi, te poate costa). Rezultatul este o permanentă și acută foame de informații, problemă pentru a cărei rezolvare e nevoie de prelucrarea unui volum mare de date din surse diferite și adesea neomegene.

Vechile sisteme de gestiune a bazelor de date, proiectate pentru procesarea tranzacțiilor curente (OLTP), nu mai pot face față și acestor noi cerințe, pe de o parte pentru că nu rețin în baza de date informații cu caracter istoric, strict necesare în procesul de luare a deciziilor manageriale, dar inutile în derularea operațiunilor curente și pe de altă parte pentru că sunt optimizate pentru prelucrarea unor cantități relativ mici de informație, în timp ce procesul de analiză a unei afaceri implică necesitatea unei viziuni globale asupra întregii activități, ceea ce nu se poate obține decât prin consultarea unui volum mare de date.

Pentru a rezolva toate aceste probleme se construiește, conform principiului că între structura unei entități și funcțiile pe care le îndeplinește există întotdeauna o relație strânsă, o noua bază de date, altfel structurată decât clasicele sisteme OLTP. Volumul mare de informații pe care trebuie să le conțină această bază de date i-a adus denumirea de depozit de date, in engleză "data warehouse", de unde și numele acestei tehnologii. Evident, în aceasta bază de date trebuie puse toate informațiile cu caracter istoric relevante în analiza economică.

In domeniile în care relația cu publicul este foarte importantă, cum ar fi comerțul, data warehouse se dovedește a fi un instrument important pentru fidelizarea clienților. Supermarket-urile în special încearcă să țină în baza lor de date informații despre clienții lor cu scopul de a avea o relație strânsă cu ei. Clientul este întâmpinat cu un salut familiar și i se cunosc preferințele, ceea ce îl face să revină cu plăcere în magazinul respectiv. Studiul pieței și al comportamentului clientului este în aceste cazuri foarte important, de

el depinzând în mare măsură succesul afacerii. Lucrul direct cu foarte mulți clienți face ca metodele statistice de exploatare a depozitului de date să aibă o importanță crescută. In acest caz, dimensiunile bazei de date sunt foarte mari, chiar dacă nu este vorba despre o companie mare.

Dar lumea afacerilor nu este singurul loc în care această tehnologie își găsește aplicații. In fond, oriunde e nevoie de un management performant, care trebuie să bazeze pe criterii științifice, data warehouse își poate aduce aportul. Astfel, în Statele Unite, fiscul a construit un astfel de depozit de date și astfel le poate oferi foarte rapid contribuabililor informații despre situația impozitelor pe care le mai au de plătit. Acesta nu este singurul avantaj pe care 1-a adus această investiție. Analizând modul în care cetățenii își plătesc taxele, contabilii pot determina mai ușor eventualele fraude. Detecția fraudelor e o problemă care nu preocupă doar pe colectorii de impozite, ci și pe conducerile marilor corporații. Studiind datele angajaților care au comis ilegalități în dauna companiei se pot găsi modele de comportament caracteristice celor predispus! să facă la fel și astfel pot fi prevenite noi pagube.

In fine, trebuie să precizăm și care este eficiența economică a acestei tehnologii. In unele cazuri s-a înregistrat pe termen mediu un profit de circa patru dolari petru fiecare dolar investit într-un data warehouse. Sigur, câștigul nu este peste tot la fel de mare, dar pe măsură ce acesta tehnologie câștigă popularitate și fiecare companie își construiește propriul depozit de date, problema nu se mai pune în termeni de câștiguri, ci în termeni de limitarea pierderilor. Data warehouse devine din ce în ce mai mult un instrument necesar, iar cine nu-1 are pierde în fața concurenței. Pe termen lung, neutilizarea acestei tehnologii (sau a uneia echivalente) poate duce chiar la dispariția de pe scenă a companiilor care adoptă o asemenea politică managerială.

Capitolul 2

Construcția și structura unui data warehouse

Să analizăm în continuare principalele cerințe pe care trebuie să le îndeplinească un depozit de date și efectele pe care acestea le au asupra structurii sale.

La fel ca și în cazul sistemelor OLTP, există o foarte strânsă legătură între caracteristicile particulare ale afacerii și structura bazei de date, pentru simplul motiv că optimizarea performanțelor nu se poate face fără a ține cont de ele. In plus, data warehouse este utilizată în procesul de luare a deciziilor, deci interacțiunea sa cu personalul uman este mult mai intensă. Trebuie ca sistemul să răspundă rapid la întrebări care presupun prelucrarea unui volum mare de date și calculul unor funcții statistice relevante pentru mangementul afacerii respecive. Cum întrebările nu sunt tot tipul asemănătoare, iar personalul care trebuie să folosească baza de date nu este decăt rare ori pregătit în domeniul IT, se poate considera că pregătirea acestui personal face parte din construcția depozitului de date. In concluzie, data warehouse nu e în general un produs care să poată fi furnizat "la cheie" de către o firmă de specialitate, ci un proiect de dezvoltare al companiei beneficiare, proiect care va fi realizat în colaborare cu o firmă din domeniul IT.

Dezvoltarea unui astfel de proiect cere mult timp (în funcție de mărimea companiei și de resursele alocate, de la câteva luni până la perioade de timp ce se apropie de un an) și se lovește adesea de obstacole neprevăzute; de aceea multe companii dezvoltă mai întâi un proiect-pilot pentru a câștiga experiență. O altă alternativă des folosită este construcția unui depozit de date ceva mai mic, folosit de obicei doar de un departament, și care poartă numele de data mart.

2.1 Integrarea datelor

Prima problemă practică pe care o întâlnim în construirea unui depozit de date este eterogenitatea surselor de date. Unele companii au dorit să includă în depozit și date vechi de zece-cinsprezece ani, date care au fost memorate în formate vechi și pe dispozitive fizice considerate astăzi depășite. In plus, există și probleme de inconsistență (erori, date lipsă, etc.). Aceste probleme trebuie rezolvate în manieră specifică; spre exemplu, informația care lipsește va fi înlocuită de obicei cu o medie a valorilor vecine, pentru că nu trebuie să

influențeze parametrii statistici ai variabilelor pe care le caracterizează. Adunarea tuturor datelor poate deci să dureze destul de mult, în unele cazuri luni de zile. Achiziționarea de hardware nou, destinat special depozitului de date, pare a fi necesară, deși multe companii încearcă (în general fără succes) să folosească același hardware pe care au și vechile sisteme OLTP. Datorită dimensiunilor mari (și perspectivelor de a crește și mai mult) ale bazei de date se optează cel mai frecvent pentru o organizare distribuită. Pentru a îmbunătăți accesul la înregistrările din baza de date, copii ale dicționarului datelor sunt păstrate în fiecare din fragmentele sistemului, chiar dacă administrarea sa se face centralizat. Datorită cantității mari de informație care trebuie prelucrată, se optează de obicei pentru scrierea de programe care să facă toate prelucrările necesare înainte de introducerea în depozit. Se disting trei grupe principale de instrumente care trebuiesc proiectate și utilizate :

instrumente pentru migrări de date, transformări simple care au ca scop aducerea
tuturor datelor la același format, în general prin înlocuirea unor termeni echivalenți
cu un sinonim unic (de exemplu, clasă, categorie și grupă cu categorie)

instrumente de "periere" (scrubbing), care se folosesc în transformări specifice dome
niului, cum ar fi extragerea unor componente ale unei adrese

instrumente de audit, ceva mai complexe, folosite la scanarea datelor pentru a de
tecta diverse anomalii și relații între entități (sau violări de reguli sau relații deja
stabilite)

Odată construite, aceste instrumente vor fi utile și după terminarea construcției depozitului de date, la operațiunile de actualizare.

2.2 Principalele deosebiri dintre OLTP si OLAP

Până acum am pus în evidență numai probleme pe care un depozit de date trebuie să le rezolve în plus față de o bază de date OLTP. Există însă și reversul medaliei, adică mici avantaje pe care ni le oferă problema implementării unui data warehouse, avantaje pe care le putem specula atât pentru a eficientiza sistemul cât și pentru a ne simplifica munca. Pentru a pune în evidență aceste avantaje vom enumera câteva deosebiri între sarcinile pe care trebuie să le îndeplinească un sistem OLTP și cele pe care le va îndeplini un sistem OLAP (On Line Analithical Processing) :

• Cantitatea de date conținută :

OLTP – puține date, reprezentând valori curente

OLAP – multe date, o adevărată arhivă

• Cantitatea de date folosită la o tranzacție :

– OLTP – puține, adesea doar o înregistrare

6

– OLAP – multe date, adesea tabele întregi

• Timpul de răspuns :

OLTP – rapid, cel mult de ordinul secundelor

OLAP – până la câteva minute

• Actualizări ale datelor :

OLTP – frecvente, făcute de mai mulți utilizatori, de obicei simultan

OLAP – rare, făcute de un singur utilizator

• Număr de tranzacții :

OLTP – mare într-o unitate de timp

OLAP – relativ mic

Scrierile în baza de date în sistemele OLAP sunt completări cu date la zi. Nu este esențial să se scrie datele imediat ce au fost obținute, pentru că oricum nu vor influența mult analiza. De aici rezultă în primul rând că aceste scrieri se pot face într-o perioadă de timp în care baza de date nu este folosită, de exemplu în timpul nopții. Problema accesului concurent, de-a dreptul dificilă în cazul sistemelor OLTP, și a cărei rezolvare e mare consumatoare de resurse, este practic inexistentă în cazul OLAP. De aceea putem renunța fără probleme la menținerea unor jurnale complete ale tranzacțiilor și la măsurile de protejare a consistenței informației din baza de date (segmente roll-back). De asemenea, faptul că up-date-ul se face fără a modifica datele existente (operații de ștergere sunt extrem de rare pentru că nimeni nu are motive serioase de a modifica date de arhivă) simplifică metodele de organizare a fișierelor care conțin datele.

Din nefericire exploatarea acestor mici avantaje nu rezolvă principala problemă de care ne lovim, și anume viteza mică a sistemului, datorată în special faptului că se utilizează volume mari de date la fiecare tranzacție. Cum utilizatorii consideră inacceptabil să aștepte o jumătate de oră sau mai mult rezultatul unei cereri, ne vedem nevoiți să sacrificăm spațiu pe disc în scopul îmbunătățirii vitezei. Creșterea redundanței duce la creșterea costurilor hardware-ului folosit, dar odată cu progresul tehnic acest lucru nu mai este chiar așa de important, prețurile componentelor hard de stocare scăzând vertiginos în ultima vreme.

Se observă aici că modelul relațional nu mai este potrivit sistemelor OLAP. Normalizarea tabelelor, pas esențial în proiectarea unui sistem OLTP cu ajutorul modelului relațional, avea ca efect (și scop) reducerea redundanței. Un sistem puternic normalizat are însă dezavantajul că e nevoie de un număr mare de join-uri pentru a regăsi informația din tabele. Pentru baze de date foarte mari, cum e dLAP. De aceea putem renunța fără probleme la menținerea unor jurnale complete ale tranzacțiilor și la măsurile de protejare a consistenței informației din baza de date (segmente roll-back). De asemenea, faptul că up-date-ul se face fără a modifica datele existente (operații de ștergere sunt extrem de rare pentru că nimeni nu are motive serioase de a modifica date de arhivă) simplifică metodele de organizare a fișierelor care conțin datele.

Din nefericire exploatarea acestor mici avantaje nu rezolvă principala problemă de care ne lovim, și anume viteza mică a sistemului, datorată în special faptului că se utilizează volume mari de date la fiecare tranzacție. Cum utilizatorii consideră inacceptabil să aștepte o jumătate de oră sau mai mult rezultatul unei cereri, ne vedem nevoiți să sacrificăm spațiu pe disc în scopul îmbunătățirii vitezei. Creșterea redundanței duce la creșterea costurilor hardware-ului folosit, dar odată cu progresul tehnic acest lucru nu mai este chiar așa de important, prețurile componentelor hard de stocare scăzând vertiginos în ultima vreme.

Se observă aici că modelul relațional nu mai este potrivit sistemelor OLAP. Normalizarea tabelelor, pas esențial în proiectarea unui sistem OLTP cu ajutorul modelului relațional, avea ca efect (și scop) reducerea redundanței. Un sistem puternic normalizat are însă dezavantajul că e nevoie de un număr mare de join-uri pentru a regăsi informația din tabele. Pentru baze de date foarte mari, cum e depozitul de date, această reducere a vitezei este inacceptabilă și de aici rezultă că strategia de proiectare tradițională a unei baze de date relaționale nu e aplicabilă și pentru data warehouse.

Modelul relaținal nu este însă total depășit de situație. Totul depinde, așa cum am mai spus, de caracteristicile particulare ale datelor care trebuie incluse în depozit. Dacă

modelul relațional se potrivește bine situației, se poate adopta o organizare de tip entitate-relație, cu modificări, desigur. După normalizarea tabelelor (necesară pentru stabilirea cu claritate a structurii depozitului nostru de date) trebuie aplicată o operațiune de denormalizare, constând în recombinarea cu grijă a tabelelor care nu introduc redundanță mare, dar urmează a fi folosite la multe operații de tip join.

2.3 Modelul multidimensional

Modelul multidimensional constituie o alternativă de proiectare a structurii bazelor de date. Acest model răspunde mai bine cerințelor data warehouse decât clasicul model relațional. Conceptele fundamentale ale modelului multidimensional sunt faptele și dimensiunile. Faptele sunt elementele centrale, datele afacerii, iar dimensiunile sunt moduri de a privi informația. Exemplul clasic este reprezentarea vânzărilor unei companii. Fiecare tranzacție comercială reprezintă un fapt, iar locul unde s-a produs această tranzacție, momentul și tipul produsului vândut constituie dimensiunile. Sigur, acest model nu e aplicabil numai în tehnologia depozitelor de date, poate fi folosit și în proiectarea sistemelor OLTP. Producătorii SGBD-urilor de acest tip susțin chiar că pentru baze de date de dimensiuni medii, modelul multidimesional are perfomanțe superioare celui relațional.

Faptele pot fi memorate într-un tabel și dimensiunile în tabele separate, ceea ce face posibilă aplicarea modelului multidimensional și în SGBD-uri relaționale. Avantajele acestei abordări sunt ușurința în navigare prin baza de date și folosirea softului deja existent pentru manipularea datelor.

2.3.1 Schema stea

Dacă privim tabela faptelor (sau măsurilor) ca pe un centru al bazei de date, iar tabelele dimensiuni ca pe niște sateliți ai săi, reprezentarea grafică a arhitecturii modelului de organizare multidimensional capătă un aspect de stea. Tabelul central, al faptelor, va conține câte o cheie externă (la nivel de înregistrare, desigur) pentru fiecare tabel-satelit ce reprezintă o dimensiune a informației-fapt.

Schema este simplă și poate fi foarte eficientă cu condiția ca dimensiunile să fie alese corect, adică să reprezinte concepte naturale proprii afacerii pe care trebuie s-o deservească sistemul respectiv. De asemenea, munca analiștilor care vor exploata depozitul de date este ușurată fiindcă organizarea informației este în conformitate cu modelul intuitiv în care gândesc ei afacerea.

Această arhitectură are și un punct slab : implică ocuparea unui spațiu mare pentru stocarea datelor, aspect asupra căruia se va reveni mai târziu.

2.3.2 Agregarea în schema multidimensională

Multe din operațiile care se efectuează în procesul de luare a deciziilor sunt de natură statistică și implică sumari parțiale. Spre exemplu, în analiza vânzărilor unui anume tip de produs, cum ar fi siropul de tuse, poate fi util, dacă nu chiar necesar să se sumeze toate tranzacțiile din fiecare lună, pentru a se urmări evoluția cererii și a se putea prevedea

consumul în viitor. Nu ar fi de loc înțelept să se studieze fiecare vânzare în parte, pentru că acest lucru nu ar aduce nici un fel de informație nouă, dar o prognoză corectă nu poate fi făcută doar pe baza faptului că în lunile de iarnă îmbolnăvirile sunt mai frecvente, fiind nevoie de precizia pe care doar experiența, acumulată sub formă de date în depozit, o poate da.

Aceste sume parțiale (pot fi și alte funcții statistice, foarte frecvent medii) se pot face la diferite nivele (în cazul de mai sus la nivel de lună, sezon sau an). Rezultatele parțiale de acest tip se numesc agregări, iar nivelele respective nivele de agregare. Rezultă de aici o organizare naturală a dimensiunilor în ierarhii. Navigarea prin aceste ierarhii se poate face în două direcții, spre nivelul superior, operație cunoscută sub numele de roll-up sau spre nivelul inferior, adică drill-down. Ambele operații se dovedesc a fi foarte utile și frecvent folosite, ceea ce subliniază calitățile modelului multidimensional.

Iată și un exemplu de tabele de fapte și dimensiuni : a) tabela faptelor

b) tabela dimensiunii timp

In tabela dimensiune de mai sus se observă două tipuri de date, și anume înregistrări la nivel de tranzacție și înregistrări medii lunare. Sigur, mediile lunare pot fi calculate din înregistrările la nivel de de tranzacție, deci păstrarea lor în tabel introduce redundanță. Dar dacă baza de date va avea de răspuns frecvent la întrebări de tipul Care este graficul vânzărilor lunare ale produsului X în ultimii 5 ani ?, atunci viteza de răspuns ar putea crește semnificativ.

Se naște acum o întrebare naturală : Câte nivele de agregare să păstrăm în tabelul-dimensiune ?

Distingem două soluții extreme : să reținem în tabel toate nivelele posibile, soluție care ar optimiza viteza cu prețul unui consum mare de spațiu pe disc (dimensiunile bazei de date pot crește de câteva ori) sau să nu reținem nici un nivel, soluție care ar reduce la minimum spațiul ocupat, dar cu consecințe dezastruoase în ceea ce privește viteza de operare. In plus, toate datele agregate trebuiesc calculate în momentul introducerii de date în depozit. La prima populare a depozitului cu date, adică la construcția sa, acest fapt nu constituie un impediment, deoarece construcția durează oricum destul de mult, dar up-datările ulterioare nu mai au la dispoziție la fel de mult timp, pentru că baza de date nu poate fi menținută mult în stare de inoperabilitate.

Evident, nici una din aceste soluții nu este suficient de bună pentru a putea fi aplicată practic. Optimul este pe undeva pe la mijloc, dar unde ? Din nefericire nu s-a găsit până la ora actuală un algoritm care să rezolve automat această problemă. De cele mai mult ori răspunsul de află la cei care vor folosi efectiv depoztul da date fiindcă ei știu cel mai bine care sunt întrebările la care va trebui să răspundă sistemul. Acesta e principiul motiv pentru care dezvoltarea unui asemenea sistem trebuie să fie făcută în colaborare cu beneficiarii. Oportunitatea sau inoportunitatea unei anume agregări poate fi decisă în funcție de raportul dintre spațiul suplimentar pe care îl cere și creșterea de viteză pe care o aduce. Pentru a evalua acest raport nu dispunem de nici o unitate de măsură, dar avem totuși un criteriu calitativ care ne pernițe să diferențiem agregările utile de cele proaste, și anume densitatea datelor. Daca un nivel al unei ierarhii (numit uneori element al dimensunii) totalizează informații dintr-un număr mare de linii al unui alt nivel din ierarhia sa, atunci agregarea pe nivelul respectiv e pe de o parte consumatoare de spațiu puțin și pe de altă parte un factor bun de îmbunătățire a vitezei, deci o agregare recomandabilă. Reciproc, dacă un nivel ierarhic totalizează un număr mic de linii ale nivelului inferior, agregarea respectivă nici nu aduce un spor de viteză demn de considerat, nici nu ocupă un spațiu suficient de mic pentru ca să nu deranjeze.

Problema care a rămas nerezolvată este timpul mare necesar actualizării tabelelor cu multe nivele de agregare; din consideretele arătate mai sus, vom avea cel mai frecvent agregări care totalizează un mare număr de linii, deci necesită un volum mare de calcul pentru actualizare atunci când liniile de care depind sunt modificate. Rezolvarea acestei probleme este adesea dificilă, mai ales dacă suntem în cazul unui depozit de date foarte mare. E posibil ca fereastra de timp disponibilă pentru up-date, de obicei o noapte, să nu fie suficientă. Ținând cont de particularitățile datelor se pot găsi metode de actualizare a tabelelor dimensionale fără a le reconstrui de zero; dacă e posibil, se recurge la două tipuri de up-date : unul implicând un volum de date mai mic, și care se poate face într-o noapte, și unul mai complex, cu un volum de date mai mare, care să fie făcut automat în week-end. De asemenea, dacă arhitectura bazei de date este distribuită se vor face scrieri în paralel. Dacă unele componente cer un timp mult peste media pentru up-date și structura bazei permite, se pot up-data componente diferite la momente diferite, fără a afecta pe utilizatori.

2.3.3 Normalizare parțială; schema fulg

Păstrarea datelor în tabele nenormalizate prezintă avantajele unui acces rapid și al simplității modelului de organizare al informației. Există, bineînțeles, și un mare dezavantaj : spațiul prea mare ocupat pe disc. Când acest spațiu este prea mare, costurile devin insuportabile și atunci trebuie făcute niște compromisuri.

De obicei se preferă menținerea tabelelor de fapte în formă nenormalizată, dar se normalizează tabelele-dimensiuni. Se câștigă astfel spațiu pe disc, dar cu prețul creșterii complexității organizării datelor. Navigarea este din acest motiv îngreuiată, iar instrumentele folosite pentru formularea cererilor complexe devin greu de proiectat și de utilizat. De aici rezultă că e de preferat să nu se elimine toate anomaliile, ci numai cele care introduc redundanță mare în baza de date. Găsirea modelului optim nu e întotdeauna simplă, dar efortul depus va fi pe deplin recompensat de rezultate.

10

In general, fiecare tabel – dimensiune va conține cheia primului nivel de agregare, iar fiecare nivel de agregare va conține cheia nivelului imediat următor în ierarhie. Schema obținută astfel are un aspect de fulg de zăpadă, de unde își primește și numele. Dacă există mai multe tabele de fapte care partajează aceleași dimensiuni, lucru întâlnit frecvent în depozitele de date mari, modelul fulg devine prin extensie o constelație de fapte. Sigur, schema devine ceva mai complicată, dar exploatarea relațiilor dintre fapte poate aduce îmbunătățiri ale performanței sistemului.

Micșorarea tabelelor dimensionale este un câștig nu numai din punct de vedere al spațiului necesar pentru stocarea informației, ci și din punct de vedere al vitezei de răspuns; și acest fapt trebuie avut în vedere la stabilirea arhitecturii depozitului de date.

O analiză atentă a acestei scheme de organizare a datelor arată faptul că ea oferă un sprijin natural pentru ierarhiile dimensionale, ceea ce constituie un argument în plus pentru utilizarea sa.

Deși din punct de vedere practic este superioară schemei stea, schema fulg nu rezolvă însă toate problemele legate de viteza de răspuns a sistemului. Nevoia de instrumente care să sporească rapiditatea calculului rămâne stringentă. Principalele instrumente folosite pentru îmbunătățirea vitezei sunt indecșii și view-urile materializate.

2.3.4 Stocarea datelor în vectori multidimensionali

Până acum am vorbit despre implementarea modelului multidimensional într-un sistem de gestiune a bazelor de date relațional ( soluție cunoscută și sub numele de ROLAP – Relațional On Line Analithical Processing). Aceasta nu este însă singura opțiune; datele pot fi stocate în structuri de date speciale, și anume vectorii multidimensionali, soluție denumită generic MOLAP (Multidimensional On Line Analithical Processing).

înainte de a descrie efectiv reprezentarea datelor sub formă de vectori multidimensionali vom da o descriere formală a modelului multidimensional. Deși din punct de vedere conceptual acest model pare a fi destul de simplu, descrierile matematice sunt ceva mai complicate dacât algebra relațională. Interesul crescut care se manifestă în ultima vreme pentru aceste baze de date (reamintesc, producători de asemenea sisteme susțin că performanțele lor sunt superioare SGBD-urilor relaționale, pentru baze de date de dimensiuni medii) a dus la apariția mai multor modele matematice pentru ele. Ne vom opri asupra unuia din ele, cunoscut sub numele de model MD, propus de Cabibbo și Torlone.

Pentru a fixa ideile, reluăm în termeni mai preciși principalele concepte de lucru :

Definiția l Numim fapte sau măsuri datele principale pe care le urmărim.

Faptele sunt deci în general date numerice care caracterizează tranzacțiile. Cele mai întâlnite exemple sunt vânzările unei companii, stocurile dintr-un depozit, etc.

Definiția 2 Dimensiunile sunt modurile naturale de a privi informația reprezentată de fapte.

Exemple tipice de dimensiuni sunt timpul, zona geografică, tipul produsului vândut.

11

Definiția 3 Elementele dimensiunii sunt date care reprezintă fiecare câte un nivel al unei ierarhii.

Fiecare nivel corespunde unei agregări. De remarcat că o dimensiune poate fi împărțită în mai multe feluri în ierarhii. De exemplu, dimesiunea geografică poate fi împărțită în următoarele moduri

oraș < județ < țară

oraș < zonă < regiune istorică (Ardeal, Moldova, etc)

Definiția 4 Atributele dimensiunii sunt valori atomice sau compuse care caracterizează dimensiunea.

Atributele permit caracterizarea datelor neierarhice. Un exemplu de atribut pentru dimensiunea produs este managerul de marcă.

O formalizare matematică a modelului multidimensional

Pentru a formaliza aceste concepte, fixăm întâi două mulțimi numărabile și disjuncte, de nume și de valori. Pentru fiecare nivel alegem un nume. Fie N mulțimea de nume asociată nivelelor. Fiecărui nivel îi vom asocia o mulțime numărabilă de valori, numită domeniu, și pe care o notăm cu DO M(1), VI E N De notat că domeniile a două nivele distincte sunt disjuncte, adică / ^ l' => DOM(l) n DOM(l') = $

Definiția 5 Numim dimensiune MD o mulțime parțial ordonată de nivele

L C N împreună cu o familie de funcții roll-up care include câte o funcție R — UP^ :

DOM(li] —> DO M (li] pentru orice pereche (li, 12) e L x L cu li -< li.

Dacă li, li G L cu li -< li spunem că l\ este deasupra lui li. Funcțiie roll-up definesc, bineînțeles, operațiile de roll-up de la un nivel la altul. Vom numi atomică o dimensiune cu un singur nivel. Se poate identifica, pentru comoditate, o dimensiune atomică cu singurul său nivel.

Definiția 6 Se numește schemă MD un triplet de forma (D, F, A), unde

D este o mulțime finită de dimensiuni

F este o mulțime finită de f-tabele de forma f [Ai : li < di >,…, An : ln < dn >
] : iq < do >, unde f este un nume, Ai cu O < l < n sunt și ele nume, distincte,
numite atribute ale lui f, iar li cu l < i < n sunt nivele ale dimensiunilor di

A este o mulțime finită d descrieri ale nivelelor, de forma 6(1) : l', unde l și l' sunt
nivele, iar S este un nume ce reprezintă descrierea lui l.

Definiția 7 Dacă S = (D, F, A) este o schemă MD, numim coordonată simbolică asupra unei f-tabele f [Ai : li < di >,…, An : /„ < dn >] : iq < do > în F o funcție care asociază fiecărui atribut Ai(l < i < n) o valoare din DO M (li).

12

O instanță asupra lui / este o funcție parțială care duce coordonatele simbolice ale lui / în valori din DOM(10). O instanță asupra unei descrieri a unui nivel 6(1) : l' în A este o funcție parțială de la DO M (l) la DO M (l'). Coordonatele în care este definită instanța se numesc măsuri.

Din acest model rezultă o posibilitate de reprezentare a informațiilor în baza de date. Coordonatele simbolice vor juca un rol asemănător cu tuplurile din modelul relațional. Datele se vor memora sub formă de vectori multidimensionali care vor conține măsuri, implementând practic instanțe asupra f-tabelelor. Pentru claritate vom considera un mic exemplu : vânzarea unei perechi de pantofi în magazinul din orașul Giurgiu pe data de 11.03.2002. Intr-un SGBD relațional, acest fapt s-ar reprezenta sub forma unui tuplu de forma (pantofi,Giurgiu,11.03.2002,15$) într-o tabelă. Același lucru, dar cu ajutorul vectorilor multidimensionali se va reprezenta astfel :

In locul tabelei se va defini un vector tridimensional (o dimesiune pentru tipul produsului, una pentru locul tranzacției și una pentru dată) și se va memora pur si simplu valoarea 15$ pe coordonatele corespunzătoare datei, produsului și locului respective. Se evidențiază două probleme :

vectorii au dimensiuni prea mari pentru a încăpea în memorie

doar o mică parte din celulele vectorilor sunt în general ocupate, la restul trebuind
să li se asocieze o valoare NULL

Partiționarea vectorilor

Pentru rezolvarea primei probleme vectorii multidimensionali trebuiesc divizați. Tehnica standard de memorare a tablourilor în ordinea crescătoare a coordonatelor liniilor sau coloanelor nu este suficientă. Să considerăm de exemplu cazul unui vector bidimensional, cu dimensiunile produs și dată, dimensiunea produs jucând rolul liniei, iar data pe al coloanei, stocat în ordinea crescă toare a liniilor. Accesarea tabelului în ordinea liniilor (după produs) este eficientă, deoarece fiecare pagină de disc citită va conține mai multe produse. Dacă însă încercăm să accesăm după coloane (după dată), va trebui să citim câte o pagină de disc pentru fiecare dată, dacă dimensiunea produs este mare, ceea ce este de așteptat în cazul data warehouse. Rezultă că dimeniunile vectorilor trebuie tratate uniform. Un mod de partiționare eficient a fost dat de Sarawagi și prevede împărțirea vectorilor n-dimensionali în subvectori n-dimensionali care să ocupe fiecare câte un bloc de disc. In funcție de situație se vor stabili rapoartele dintre mărimile diferitelor dimensiuni ale vectorilor.

Compresia vectorilor împrăștiați

A doua problemă se rezolvă, cum era de așteptat, prin comprimarea vectorilor (eventual după ce au fost deja partiționați). Pentru ca acest lucru să fie eficient, nu vor fi supuși procesului de comprimare toți vectorii, ci doar cei care au o densitate mică de date. Vectorii care au mai mult de 40% din celule ocupate se numesc vectori denși și nu vor fi comprimați; (proporția de numai 40% arată cât de slabă este în general popularea vectorilor multudimensionali) ceilalți se numesc vectori împrăștiați. Se poate utiliza compresia

13

chunk-offset. Pentru fiecare celulă nevidă se memorează o pereche (deplasament, date). Funcționează direct pentru vectorii partiționați (chunk = partiție) și se pare că este mai eficient decât algoritmii standard de arhivare (cum ar fi LZW). Deoarece reprezentările partițiilor vor avea lungimi variabile, e necesar să memorăm la începutul fișierului sub formă de metadate lungimea fiecărui subvector.

2.4 Indecși

Cantitatea mare de informație pe care trebuie să o păstreze și să o manevreze un depozit de date este principala sursă de dificultăți în proiectarea, întreținerea și utilizarea sa. Timpul de răspuns la diversele interogări complexe la care este supus sistemul crește uneori la valori inacceptabile. In acest context, utilizarea indecșilor pentru optimizarea vitezei devine un instrument important asupra căruia merită să aruncăm o privire.

Păstrarea în tabele a datelor la diferite nivele de agregare aduce un plus de viteză, dar metoda are limitările ei. Spre exemplu, să considerăm un lanț de magazine care înregistrează vânzările într-un data warehouse. Intr-un tabel-fapt se vor introduce valorile tranzacțiilor. Să presupunem că avem tabelele-dimensiuni Magazine (reprezintă locul unde a avut loc vânzarea), Timp (data tranzacției) și Tip_produs (ce produs a fost vândut).

Păstrând suficiente date agregate se poate răspunde foarte repede la întrebări de forma "Câte produse de valoare mai mare de 100$ s-au vândut în medie în ultimele 6 luni ?". Un responsabil cu marketing-ul ar putea pune și întrebări de forma " Câte sticle de Coca-Cola s-au vândut în medie în ultimii doi ani în zile în care temperatura a depășit 30°C ?". Temperatura nici măcar nu este o dimensiune în modelul bazei de date; e evident că nu vor exista date agregate după temperatură în depozit (nici n-ar fi util, decât dacă magazinele ar fi specializate pe distribuția de răcoritoare).

Numărul de dimensiuni care pot fi memorate este evident limitat, dar întrebările pe care le poate pune un manager sunt foarte variate și mai devreme sau mai târziu se va ajunge și la o situație de tipul celei de mai sus, când datele precalculate nu mai sunt disponibile. In acele cazuri rezultatul cererilor va trebui calculat din datele de la nivelul atomic și utilizarea unor indecși poate compensa, dacă nu total cel puțin parțial, pierderea de viteză datorată lucrului cu tabele mari.

In general, indecșii au umătorul dezavantaj: la fiecare operațiune DML trebuiesc actualizați. In sistemele OLTP, unde scrierile, modificările și ștergerile datelor din tabele sunt frecvente un număr mare de indecși poate avea un efect negativ asupra performanței. In cazul OLAP introducerile de date în depozit se fac însă periodic, de obicei noaptea, timp în care baza de date este indisponibilă, iar ștergerile și modificările sunt practic inexistente și deci acest dezavantaj se estompează. Desigur există și reversul medaliei, actualizarea indecșilor în timpul up-date-ului ducând la creșterea ferestrei de timp în care baza de date este indisponibilă. Dacă volumul de date care se introduce în depozit într-o ședință este mare, folosirea excesivă a indecșilor poate duce la depășirea timpului limitat pe care îl avem la dispoziție pentru up-date.

Plusul de viteză pe care îl aduce utilizarea indecșilor în timp ce baza de date este operațională este însă un argument puternic în favoarea utilizării lor.

14

2.4.1 Indecșii în sistemele OLTP

Pentru implementearea indecșilor în sistemele tradiționale s-a ales în marea majoritate a cazurilor utilizarea arborilor echilibrați (5+-trees). Frunzele acestor arbori conțin câte o secvență de intrări pentru valorile-cheie ale indexului. Fiecare valoare-cheie reflectă conținutul unei coloane indexate (sau a mai multora) și fiecare intrare a unei valori-cheie păstrează adresele unor linii într-o tabelă, linii ce conțin valoarea respectivă. Toate liniile tabelei indexate sunt referențiate o singură dată în arbore. In general, adresa unei linii este numită Row-ID, (prescurtat RID) și deci fiecare intrare a unei valori-cheie conține o listă de RID-uri. Numărul de valori aflate la nivelul frunză al arborelui este destul de mare; e posibil ca o listă de RID-uri să ocupe prea multă memorie sau chiar să nu încapă în RAM. Din acest motiv se recurge la compresia listelor.

O slăbiciune a arborilor echilibrați este faptul că pot fi afectați negativ de accesul concurent. Dacă mai multe procese accesează simultan același arbore, acesta poate fi ușor compromis. Cea mai simplă soluție pentru rezolvarea problemei mai sus menționate este serializarea accesului, dar asta poate avea efecte nefavorabile asupra vitezei de operare. Gray a introdus un mecanism de rezervare (locking), mecanism care a fost rafinat pe parcurs și care rezolvă și această problemă.

Această structură pare a fi foarte potrivită pentru sistemele OLTP, inserția și ștergerea fiind eficiente.

2.4.2 Indecșii în sistemele OLAP

Reducerea accesării tabelelor de bază este o modalitate eficientă de a crește viteza de răspuns a bazelor de date de tip data warehouse. Folosirea unor tehnici bazate pe utilizarea indecșilor poate fi o soluție pentru rezolvarea rapidă a cererilor pentru care nu avem la dispoziție agregări precalculate. Spre exemplu, pentru rezolvarea unei cereri în care intervin condiții multiple se poate folosi intersecția indecșilor. Reuniunea indecșilor se dovedește de asemenea o operație utilă.

Reprezentarea indecșilor în forma de mai sus nu este însă cea mai potrivită pentru sistemele OLAP.

Indecși bitmap

Pentru a eficientiza operațiile cu indecși, cum ar fi reuniunea și intersecția s-au construit reprezentări sub formă de bitmap pentru listele de RID-uri din frunze. Au apărut pentru prima oară în anii '60, la un produs al "Computer Corporation of America" (numit "Model 204") și au primit numele de indecși bitmap, deși nu sunt în realitate un tip aparte de indecși, ci numai un mod diferit de reprezentare a indecșilor deja descriși mai sus. Diferența constă în înlocuirea listelor de RID-uri cu hărți de biți (bitmaps).

Hărțile de biți sunt mai eficiente din punct de vedere al spațiului ocupat decât listele de RID-uri dacă numărul valorilor-cheie este mic. Chiar dacă numărul valorilor este mare, ei pot fi folosiți cu succes comprimând eventual bitmap-urile.

Construcția unui index bitmap se face dând în prima fază fiecărei linii un identificator în intervalul [l, M], adică un număr de ordine. Dacă în tabel avem n linii nu este neapărat

15

necesar ca n = M, deoarece se obișnuiește să se aloce un număr fix de linii p pentru fiecare pagină de disc, ceea ce îmbunătățește viteza de căutare. Deci pentru a regăsi o linie cu numărul de ordine j se va accesa pagina j/p și locația j°/0p (folosind notația din limbajul C). La alegerea lui p trebuie să ținem cont de faptul că nu toate liniile vor avea mereu aceeași lungime și am putea ajunge în imposibilitatea de a pune același număr de linii pe fiecare pagină de disc. O consecință a acestui fapt este posibilitatea ca unele valori ale numerelor de ordine să nu aibă un corespondent în tabel. Vom numi aceste numere poziții invalide.

Un bitmap B este definit pentru tabel ca un vector de M biți. Dacă P este o proprietate care ne interesează, putem memora în bitmap care din linii au prorietatea P pur și simplu setând l bitul corespunzător (prin intermediul numărului de ordine) și lăsând O pe ceilalți.

In consecință, un index bitmap pe o coloană C cu valorile posibile v\,… ,Vk va fi un arbore echilibrat în care nodurile vor avea aceste valori-cheie, la fel ca la un index clasic, și în loc de listele de RID-uri vor avea bitmap-uri asociate proprietăților C = v^ VI < i < k.

Dacă numărul de biți cu valoarea l dintr-un bitmap este relativ mare, vom spune că bitmap-ul este dens. Spre exemplu, dacă mulțimea valorilor-cheie are puține elemente, proporția biților care vor avea valoarea l va fi mare; în cazul particular al indexării după valori binare (cum ar fi sexul unei persoane) poate să ajungă la 50%.

In general, dacă numărul valorilor-cheie este mult mai mic decât numărul de linii folosirea acestei soluții pentru reprezentarea indecșilor este mai bună din punct de vedere al spațiului ocupat pe disc decât soluția listelor de RID-uri. Dacă totuși spațiul ocupat este prea mare, se poate recurge la comprimarea bitmap-urilor sau chiar la convertirea lor în liste de RID-uri.

Avantajele indecșilor bitmap

Principalul avantaj al reprezentării indecșilor cu ajutorul bitmap-urilor provine din faptul că operațiile pe biți, de pildă AND sau OR, sunt executate de CPU cu viteză foarte mare. Bitmap-urile pot fi tratate ca niște tablouri de întregi și calculul unei astfel de operații se poate face simplu, parcurgând aceste tablouri : for(long i=0; i<length(Bl) ; i++)

B3[i] = Bl [i] B2[i];

unde length(B) este lungimea tabloului-bitmap (aceeași pentru B1,B2 și rezultatul B3) iar operatorul calculat este OR. Operația AND se calculează la fel; probleme apar la calculul operației de negare, din cauza biților care nu corespund unor linii (pozițiile invalide). Dacă inițial acești biți sunt setați O și nu pun nici un fel de probleme la calculul conjuncției și disjuncției, (pentru simplul motiv că O AND O = O și O OR O = 0),prin negare bit cu bit aceste zerouri se vor transforma în l, indicând astfel existența unor linii invalide. Este necesar deci un pas în plus prin care să se elimine biții problemă. O soluție în acest sens este memorarea unui bitmap care să aibă l pe biții corespunzători pozițiilor valide și O pentru pozițile invalide, după care se va face "și" logic bit cu bit între rezultatul negării și acest bitmap, rezultatul obținut fiind cel final.

In cererile SQL se găsesc de obicei filtre logice (în clauza where) alcătuite din mai multe predicate care pot fi calculate cu ajutorul operațiilor logice fundamentale. Rezultatul acestor filtre este apoi supus la diverse grupări (în clauza group by) și în final se calculează

16

agregările care dau rezultatul util (cont, sum, avg etc). Calculul predicatelor din filtrele logice se face, cum era de așteptat, foarte eficient cu ajutorul indecșilor bitmap dacă aceștia sunt disponibili. In plus, bitmap-urile se dovedesc utile și la calculul agregărilor; un exemplu edificator este calculul funcției statistice count. Valoarea acestei funcții se obține pur și simplu numărând biții setați l dintr-un bitmap, ceea ce este evident o operațiune foarte rapidă.

Segmentarea indecșilor bitmap

Pentru a optimiza accesul la informația din indecși se utilizează spargerea bitmap-urilor în fragmente de lungime fixată, care încap pe o pagină de disc. Corespunzător fragmentelor, tabelele sunt împărțite în segmente, fiecare segment conținând un număr egal de linii. In consecință, convertirea bitmap-urilor în liste de RID-uri și reciproc este ușurată, RID-urile fiind mai scurte pentru că trebuie să indice offset-ul unei linii în cadrul unui segment. Adresa segmentului va fi memorată la începutul fiecărei liste de RID-uri, economisind astfel spațiu.

Un al doilea avantaj al segmentării este reducerea numărului de operații I/O. Intrările arborelui pentru o valoare-cheie sunt liste de pointeri la bitmap-uri sau la liste de RID-uri grupate pe fragmente. Dacă un fragment nu are însă linii corespunzătoare, nu se va memora nici un pointer. La calculul unor predicate lipsa pointerilor pentru un segment la unul din indecși arată că fragmentul respectiv trebuie ignorat și la ceilalți indecși care participă la calcul, economisind astfel citirea sa.

Indecși proiectivi

Dacă valorile dintr-o coloană C a unui tabel sunt de lungime fixă și avem frecvent nevoie de ele, putem să le extragem și să le memorăm în ordinea în care apar în tabel liniile din care fac parte. Fiind în general mult mai mici decât o linie întreagă, valorile respective vor încape în număr mare pe pagina de disc. Dacă n este numărul de ordine al unei linii, putem calcula ușor locația valorii coloanei C de pe linia respectivă; numărul paginii de disc este p=n/k iar deplasamentul în pagină este d=n°/0k, unde k este numărul de valori care încap pe o pagină de disc (am folosit notațiile operatorilor din limbajul C). Reciproc, fiind dată o valoare(prin adresă, adică precizând numărul paginii și deplasamentul în pagină), se poate găsi foarte ușor numărul de ordine al liniei corespunzătoare din tabel n=p*k+d.

Structura simplă descrisă mai sus se numește index proiectiv sau de proiecție (pro-jection index). Eficiența acestui tip de index este mare dacă dimensiunea unei linii din tabelă este mult mai mare decât a tipului valorii coloanei C. A fost utilizat pe scară largă pentru prima dată în sistemul SYSBASE IQ, producătorii numindu-1 "Fast Projection Index".

Indecși Bit-Sliced

Indecșii Bit-Sliced sunt utili la calculul unor agregări; ei conțin mulțimi de segmente de bitmap-uri (bitmap slices). Intuitiv, ei sunt un fel de indecși proiectivi pe o singură coloană. Practic, dacă valorile unui index proiectiv se pot scrie pe N biți, un index Bit-

17

Sliced va conține bitmap-uri cu biții de pe ordinul fc, l < k < N. Pentru claritate, să luăm un exemplu:

Fie C o coloană dintr-un tabel, astfel încât valorile de pe accesată coloană sunt reprezentate pe N biți. Pentru a n-a linie din tabel și i < N definim

„, ., f l, dacă bitul i al valorii de pe linia n este f
D(n,i) = < u, ,

v ' ' 10, altfel

Putem acum defini Bi ca fiind un bitmap ce conține toți biții D(n, i], i = f ..n, iar indexul bit-sliced pe coloana C ca fiind mulțimea tuturor bitmap-urilor Bi, i = l..n. Practic acest index conține aceeași informație pe care o conține și indexul proiectiv pe C, dar altfel organizată. Se impune în plus restricția ca să nu se memoreze bitmap-uri care conțin numai zerouri, dar asta nu e foarte important din punct de vedere practic, deoarece astfel de bitmap-uri pot fi identificate ușor la crearea indexului. Fiecare bitmap Bi se numește bit-slice al coloanei C.

Pentru o coloană C dată, este evident că un index de oricare din cele trei tipuri descrise mai sus se poate obține dintr-un index de un alt tip. In algoritmi însă, eficiența lor este diferită.

Compararea indecșilor

Vom considera în continuare câteva exemple de situații practice în care se pot utiliza indecșii și vom compara performațele lor.

f .Calculul sumei pe o coloană Fie cererea : SELECT SUM(C) FROM T WHERE condiție

Se consideră strategii de rezolvare a cererii bazate pe cele trei tipuri de indecși descriși anterior și pe citirea directă a tabelei T. Este evident că soluția accesării directe a liniilor tabelei este cea mai costisitoare din punctul de vedere al operațiilor I/O. Dacă rezultatul filtrării logice făcută de condiția pusă în clauza WHERE se prezintă sub forma unui set de linii dispersate în toată tabela, numărul paginilor de disc ce vor trebui accesate va fi foarte mare, ceea ce va încetini considerabil viteza de răspuns. Nici din punct de vedere al costului în operații CPU această strategie nu este bună; pentru calculul adresei unei valori de interes în tabelă sunt necesare câteva zeci de instrucțiuni. In concluzie, soluția bazată pe acces direct nu este preferabilă și trebuie evitată pe cât posibil.

Folosirea unui index proiecție pe coloana C rezolvă în mare parte problemele întâlnite strategia bazată pe acces direct. Mai multe valori consecutive sunt plasate pe o aceeași pagină de disc; dacă rezultatul filtrului logic se prezintă sub forma unui șir de numere de ordine ale liniilor în tabel, calculul adreselor valorilor corespunzătoare în index se face foarte ușor, după cum am arătat mai sus. Chiar dacă valorile care trebuiesc sumate provin de pe linii dispersate pe mai multe pagini de disc, gruparea și segmentarea indexului vor avea ca efect scăderea drastică a numărului de pagini ce trebuie accesate. Folosirea indexului duce deci la reducerea atât a costului I/O, cât și a costului CPU al operațiunii. Timpul de răspuns este de câteva ori mai bun decât la metoda anterioară.

18

Calculul sumei pe baza unui index clasic (cu listă de valori) se face parcurgând toate valorile-cheie și determinând câte linii din tabela corespund fiecărei valori. E suficient sa se înmulțească apoi valorile cu numerele de apariții și sa se adune rezultatele. Este deci necesar să se parcurgă listele de RID-uri sau bitmap-urile (după caz) din fiecare nod al arborelui; se remarcă faptul că reprezentarea sub formă de bitmap-uri a listelor de valori face numărarea foarte rapidă, mai ales dacă bitmap-urile sunt suficient de mici pentru a încăpea în RAM. Parcurgerea listelor de RID-uri sau a bitmap-urilor este costisitoare din punct de vedere al operațiilor CPU, mai ales dacă numărul de linii al tabelei este mare. Metoda este totuși mai bună decât calculul direct.

In cazul indecșilor bit-sliced calculul se face analog cu cazul indecșilor bitmap. Iată un algoritm în pseudocod stil C : SUM = 0; for(int i=0; i<N; i++)

SUM += 2** COUNT(5; & Bf}; return SUM;

unde N este numărul de biți pe care se reprezintă tipul de date al coloanei C, ei sunt "feliile" de bitmap-uri definite de indexul bit-slice iar B f este un bitmap în care biții corespunzători numerelor de ordine ale liniilor care ies din filtrul logic.

O estimare a costurilor totale (în operații) pentru cele patru strategii pentru un rezultat al filtrului logic de două milioane de linii se alfa în tabelul următor :

Pe baza acestui tabel putem compara performanțele celor patru strategii de rezolvare a cererii date. Având în vedere că în general costul unei operații I/O este mult mai mare decât al unei operații CPU (din punct de vedere al timpului consumat, evident), putem trage concluzia că indecșii bit-slice sunt de preferat în situații de acest fel.

2. Eficiența calcului unor alte agregări

Vom considera agregări calculabile prin metoda "divide et impera", i.e. calculul lor se poate face pe submulțimi disjuncte, rezultatul final obținându-se din rezultatele parțiale. De exemplu, maximul unei mulțimi se poate determina ca maximul dintre maximele a două submulțimi disjuncte (și a căror reuniune să fie egală cu mulțimea inițială). Astfel de agregări sunt COUNT, SUM, AVG, MIN, MAX, mediana și generalizarea ei, ( mediana este o valoarea cu proprietatea că cel puțin jumătate din elementele mulțimii pe care se calculează sunt mai mici sau egale cu ea și cel puțin jumătate sunt mai mari sau egale). Alt tip de agregări, cu produse de coloane (de exemplu dispersia), admite metode de calcul asemănătoare. Pentru calculul funcției COUNT nu e nevoie de indecși (dacă facem COUNT pe rezultatul unui filtru logic; altfel, adică dacă se iau în calcul toate valorile de pe o coloană, indecșii pot fi folositori, așa cum am arătat mai sus). Calculul agregărilor de tip SUM a fost deja prezentat, iar media (AVG) se reduce la COUNT și

19

SUM (prin definiție, AVG = SUM/COUNT). Eficiența utilizării indecșilor pentru celelate funcții diferă de la caz la caz:

Concluzie

Din acest tabel rezultă că nu avem la dispoziție o "rețetă" care să ne spună ce tip de index să construim. Studiul atent al problemei particulare pe care vrem să o rezolvăm este strict necesar, mai ales atunci când există și alte soluții înafară de indexare.

Indecși join

Un tip de index foarte folosit în sistemele de tip OLAP, indexul join este un index care memorează relațiile dintre tabele; mai precis, un index join este un index care păstrează relațiile dintre cheile externe ale unor tabele și cheile primare corespunzătoare.

Spre exemplu, indexul star join este definit pentru o schemă stea ca un index care concatenează valori ale coloanelor (sau codificări ordinale ale acestora) din diferite tabele dimensionale și conțin liste de RID-uri în tabela fapt pentru fiecare valoare concatenată. Acest index are o slăbiciune importantă : dacă avem multe coloane folosite pentru constrângeri în mai multe tabele dimensionale, pentru a obține toate combinațiile utile de constrângeri trebuie să creem un număr foarte mare de astfel de indecși.

Indexul join bitmap rezolvă această problemă. In esență este un index pe o tabelă T bazat pe o singură coloană a unei tabele S, unde T și S sunt supuse de obicei la operații de join de un anumit tip (fixat). Avantajul acestui tip index față de cel descris mai sus este că indecșii de acest fel se pot combina. Nu mai este deci nevoie de un număr mare de indecși pentru toate posibilitățile de combinare a tabelelor.

Pentru reprezentarea indecșilor join se poate alege oricare din soluțiile consacrate : indecși proiectivi, bit-sliced sau B-arbori (B-trees). Se va adopta în fiecare caz particular soluția care dă cele mai mari performanțe.

Calculul grupărilor cu ajutorul indecșilor join

Fie F, di, D2,…, Dn tabele-fapt, respectiv dimensiuni într-o schemă stea. Pentru execuția unei cereri, liniile întoarse de filtrul logic din clauza WHERE (notăm cu R tabela formată de aceste linii) vor fi grupate după atributele de grupare; pentru fiecare linie din R se va alege grupul din care face parte și asta se poate face mai repede cu ajutorul indecșilor proiectivi definiți pe coloanele atributelor de grupare. Se pot citi apoi valorile

20

ce trebuie agregate (eventual tot din indecși proiecție, cu toate implicațiile descrise mai sus) și în fine se face calculul funcției obiectiv.

Dacă nu avem la dispoziție destulă memorie RAM pentru toate operațiile de mai sus, se poate utiliza un derivat al algoritmului prezentat asemănător cu calculul unui join pe baza unei tabele de dispersie. Vor fi necesare mai multe treceri pentru a calcula porțiuni care să încapă în memorie.

Și indecșii clasici (cu bitmap-uri sau cu liste de RID-uri) pot fi folosiți cu succes pentru acest calcul. Spre exemplu, pentru o grupare după două atribute A și B ale dimensiunilor di și D2, un algoritm bazat pe indecși bitmap este următorul : Pentru fiecare intrare v\ în indexul pe coloana A a lui di

Pentru fiecare intrare v% din indexul pe coloana B a lui D2 Bg = BVl AND BV2 AND Br Evaluează funcția obiectiv pe Bg, unde Br este bitmap-ul asociat relației R.

Acest algoritm poate fi generalizat fără dificultăți pentru grupări pe mai multe atribute și se bazează pe capacitatea de combinare a indecșilor bitmap. Poate fi ineficient dacă sunt multe grupuri și liniile din aceste grupuri sunt împrăștiate în toată tabela F, dar poate fi îmbunătățit semnificativ prin segmentare.

2.5 View-uri

Definiția generală

Intr-un SGBD relațional există, pe lângă tabelele propriu-zise, și niște tabele logice, numite view-uri("vederi"). Sunt stocate sub în dicționarul datelor sub forma cererilor SQL care le definesc. Construcția acestor tabele se face din mai multe motive; exemple clasice sunt securitatea (utilizatorii vor avea drepturi de citire numai asupra unei părți din tabel) sau comoditate (cererea care definește view-ul poate fi dificil de scris pentru un nespecialist, spre exemplu dacă trebuie să implementeze operatorul SQL DIFFERENCE). Funcționare acestor tabele logice este simplă : ori de câte ori se execută o cerere asupra view-ului, motorul de analiză SQL combină cererea respectivă cu cererea care definește view-ul și execută rezultatul.

2.5.1 Materializarea view-urilor

In sistemele OLAP rolul view-urilor este mai important, ele contribuind și la creșterea vitezei de răspuns. Nu se mai folosește exclusiv metoda de stocare de la sistemele OLTP; se preferă "materializarea" tabelelor logice, adică scrierea lor efectivă ca tabele fizice. Astfel se introduce evident redundanță în baza de date dar se câștigă viteză. Sigur, nu este obligatoriu să se materializeze toate view-urile; se pot utiliza și vederi ne materializate. O altă problemă ridicată de această implementare a view-urilor este up-date-ul. Dacă view-urile nematerializate se modifică automat odată cu modificarea tabelelor de bază, din motive lesne de înțeles, cele materializate nu mai au această proprietate. Cum materializarea se face tocmai pentru a evita repetarea unor calcule intense, e limpede că

21

soluția reconstruirii de la zero a view-urilor la fiecare up-date al bazei de date nu este satisfăcătoare. Trebuiesc rezolvate deci două probleme :

Câte view-uri să materializăm și care sunt acestea ?

Cum facem up-date-ui acestor view-uri ?

Răspunsurile acestor întrebări depind în mare măsură de caracteristicile particulare ale depozitului. Vom studia în continuare modalități de rezolvare a problemelor de mai sus.

Pentru problema alegerii celor mai bune view-uri pentru materializare nu avem la dispoziție prea multe criterii clare; evident că se va încerca materializarea celor frecvent utilizate; deasemenea se va încerca simultan pe cât posibil materializarea acelor view-uri care sunt greu de calculat. Dar mulțimea tuturor view-urilor cu aceste caracteristici este destul de mare și în plus coincide în mare parte cu mulțimea view-urilor utile, deci aplicarea doar a acestor două criterii nu rezolvă problema.

La ora actuală se folosește materializarea unor view-uri cu structură simplă, de obicei join-uri ale tabelei-fapt cu un subset al dimensiunilor, eventual cu câteva agregări. Practica a dovedit că algoritmi de tip greedy pentru căutarea view-urilor care trebuie materializate dau rezultate satisfăcătoare. Experiența rămâne un factor important și trebuie să luăm în considerație și renunțarea la unele view-uri materializate și înlocuirea lor cu altele noi pe măsură ce utilizarea sistemului arată care sunt slăbiciunile sale.

2.5.2 Problema MVC – Multiple View Consistency

Materializarea view-urilor într-un data warehouse aduce două probleme de consistență a informației:

Informația dintr-un view trebuie să fie sincronizată cu cea din tabelele pe baza
cărora a fost definit; această problemă a fost deja menționată anterior

View-urile trebuie sincronizate între ele astfel încât rezultatele operațiilor de tip join
cu view-uri să fie corecte. Această problemă este numită problema MVC (multiple
view consistency)

In cele ce urmează ne vom ocupa de problema MVC. Sistemele de tip data warehouse se folosesc de obicei la procesul de luare a deciziilor, și din acest motiv up-date-ul se face în perioade de inactivitate, iar problema MVC este practic inexistentă. Consistența informației din view-uri este asigurată de programele de up-date care nu acționează simultan cu utilizatorii.

Există însă și excepții de la regula generală. Depozitele de date folosite pentru păstrarea unei relații familiare cu clientul (customer retention, în limbajul economic) nu-și pot permite să se oprească pentru up-date la fel ca cele folosite numai pentru OLAP.

Exemplu de problemă de tip MVC

Fie .R, S1, și T relații (tabele) din baza de date, iar Vi, V-2 view-uri definite de relațiile Vi = R ix S și V-2 = S \x\ T. In momentul inițial S este nu conține nici o înregistrare,

22

iar R și T conțin câte o înregistrare. La introducerea unui tuplu în S trebuie făcute și modificările corespuzătoare în Vi și V^. In tabelul următor se prezintă evoluția tabelelor și view-urilor în timpul operației de up-date.

La momentul ti se introduce tuplul (2,3) în S1, iar modificările view-urilor se fac ulterior, una după alta. La sfârșit (momentul t3) conținutul view-urilor este corect, dar la momentul t-2 numai unul din ele (Vi) reflectă realitatea din tabele. Cele două view-uri nu sunt sincronizate și rezolvarea unei interogări pe baza lor duce la rezultate eronate. Spre exemplu, dacă se calculează joinul R ix S ix T pe baza view-urilor materializate Vi și V2, nu se obține rezultatul corect. Executarea a up-date-ului după strategia de mai sus în paralel cu alte operații asupra view-urilor nu este posibilă. Procesul care se ocupă de inserarea tuplurilor în tabele și up-data-rea corespunzătoare a view-urilor nu poate fi întrerupt în orice moment pentru efectuarea unei interogări, pentru că este posibil ca în momentul întreruperii să avem o situație de tip £2, în care view-urile nu sunt sincronizate.

Dacă utilizarea depozitului de date o cere (ca în exemplul de mai sus), trebuie să găsim o modalitate de a permite realizarea operațiunilor în paralel fără a risca obținerea de rezultate false. Utilizarea unei structuri de date suplimentare, care să indice care din viwe-uri sunt sincronizate poate fi o soluție acceptabilă. Procesul de up-date nu va putea fi întrerupt pentru o interogare decât dacă view-urile care sunt implicate sunt sincronizate. De asemenea, este necesar ca procesul care se ocupă de up-date să fie astfel conceput încât să sincronizeze cât mai repede view-urile frecvent folosite, dându-le prioritate în fața celor mai puțin utilizate.

2.6 Structura unui Data Warehouse

Suntem acum în măsură să tragem o concluzie privind structura generală a unui Data Warehouse. O bază de date de acest tip se compune din cinci diviziuni funcționale :

Sursa

Putem cosidera ca făcând parte din această diviziune toate procesele care oferă datele ce se transferă în depozitul de date. De obicei aceste surse sunt bazele de date operaționale de tip OLTP ale companiei, dar există o tendință din ce în ce mai vizibilă de a integra și date externe. Spre exemplu, un responsabil cu vânzările într-o companie care produce automobile ar putea dori să afle răspunsul la întrebări de tipul " De unde se poate cumpăra cea mai ieftină mașină de marca X pe o regiune de lOOkm în jurul orașului Y ?". Sigur, aceasta este o întrebare legitimă și foarte naturală, dar nu e nevoie de un data warehouse pentru a-i răspunde. Dacă însă managerul pune întrebarea la fel de naturală "Care este venitul mediu al potențialilor clienți din această zonă ?", atunci e nevoie de multe date

23

pentru a răspunde, mai ales dacă se dorește și o cât mai bună previziune asupra acestor venituri în viitor. Se poate lua deci în considetație achiziționarea de date externe companiei. Identificarea cu acuratețe a tuturor acestor procese are loc bineînțeles în timpul construcției depozitului. Practica a arătat că munca aceasta consumă aproximativ trei sferturi din timpul scurs de la începutul proiectului și până când baza de date devine funcțională. Odată cu stabilirea surselor, trebuie rezolvate și problemele de incompatibilitate, eliminarea informației inutile sau incorecte, probleme tratate în secțiunea dedicată integrării datelor.

încărcarea

Odată sursele de date identificate, trebuie să ne ocupăm de migrarea lor spre baza noastră de date. Procesele legate de acest pas al dezvoltării proiectului sunt extragerea, curățarea, transformarea și încărcarea datelor în baza de date. Trebuie luată în considerare presiunea pe care o exercităm asupra sitemelor care oferă datele; dacă sistemele OLTP care fac toate operațiunile curente ale companiei sunt suprasolicitate pentru că trebuie să îndeplinească pe lângă sarcinile lor obișnuite și alimentarea cu date a depozitului, e necesar să intervenim fie prin restructurarea sistemelor-sursă fie prin reproiectarea programelor care se ocupă cu transferul datelor spre depozit. Altfel putem ajunge în situația neplăcută în care atât sistemele-sursă cât și depozitul de date se comportă prost, obstrucționându-se reciproc.

Stocarea

Trebuie să ne ocupăm, firește, și de structura fizică și logică a bazei de date. O metodă foarte eficientă (dar și costisitoare) de creștere a performanței este utilizarea arhitecturilor paralele. Pentru aceasta, trebuie să organizăm depozitul sub forma unui grup de baze de date interconectate, de obicei data mart-uri utilizate de câte un departament. Pentru data mart-uri se utilizează de obicei stocarea datelor în vectori multidimensionali, organizare care să convină în special departamentului respectiv. Pentru integrarea acestor baze de date într-un depozit global se pare că cel mai potrivit sistem de gestiune este cel relațional. In cadrul fiecărui data mart trebuie să alegem structura fizică a fișierelor care vor conține datele, nivelele de agregare precalculate, organizarea metadatelor și compatibilitatea lor cu metadatele din depozitul central. In plus, trebuie să alegem și arhitectura sistemelor de calcul care vor fi utilizate, astfel ca efortul de procesare să fie repartizat corect pe servere de aplicații spre a putea obține performanțe rezonabile.

Ultima problemă pe care o avem de rezolvat este repartizarea datelor către data mart-urile independente pentru a le conserva consistența în timpul up-date-ului.

In timpul proiectării structurii fizice (și logice) a depozitului se va urmări cu grijă păstrarea unei flexibilități care să permită atât modificări minore ale depozitului în urma observațiilor privind funcționarea sa, cât și conservarea performanțelor odată cu creșterea volumului de date din depozit, lucru care se va întâmpla negreșit în timp.

24

Interogarea

Interogarea unei baze de date în general este procesul prin care se accesează informația utilă păstrată în ea, deci un proces în care parametrii performanței sunt timpul de răspuns și corectitudinea informației extrase. Data Warehouse nu face excepție de la această regulă. Trebuie să pună la dispoziția utilizatorului informații de bună calitate și în timp util pentru a facilita luarea deciziilor și evaluarea sănătății companiei și a perspectivelor de dezvoltare. Datorită volumului mare de date și de calcule necesare pentru a găsi răspunsurile la întrebările pe care le pun managerii, tehnicile de interogare a unui depozit de date sunt ceva mai complicate decât în cazul unei baze de date obișnuite. Prezența în baza de date a informației agregate face ca optimizarea strategiei de execuție a unei cereri să se complice și ea. In plus, utilizatorii sunt adesea nespecialiști, deci trebuie să acceseze baza da date prin intermediul unor instrumente performante care să mascheze pe cât posibil interacțiunea directă cu sistemul. Aceste instrumente includ generatoare de rapoarte, programe de vizualizare grafică a rezultatelor, etc. Se numesc instrumente sau unelte front-end. Proiectarea acestor aplicații constituie un pas esențial în dezvoltarea proiectului.

Metadatele

Gestionarea unui volum mare de date este imposibilă fără o evidență precisă. De acest aspect se ocupă, ca în orice bază de date, sistemul. Metadatele sunt date despre date; fără ele nu se poate desfășura nici unul din procesele descrise mai sus. Putem considera metadate și informațiile despre performanțele sistemului și monitorizarea acestuia. Sigur, gestiunea metadatelor nu pune probleme la fel de dificile ca gestiunea datelor propriu-zise, dar importanța lor ne îndreptățește să le considerăm o diviziune funcțională a unui data warehouse.

25

Capitolul 3

Interogarea unui depozit de date

Interogarea a fost menționată ca o diviziune fundamentală a unui data warehouse. Există câteva particularități ale manipulării informației într-un data warehouse asupra cărora merită să aruncăm o privire mai atentă. In primul rând, pentru ca o bază de date să poată fi interogată trebuie să existe un limbaj în care să se formuleze cererile. Construcția unui astfel de limbaj este dificilă, dar și mai dificilă este impunerea lui. Fiind folosit de mai toate SGBD-urile clasice, SQL a câștigat cu timpul o popularitate care îl face foarte greu de înlocuit cu orice altceva, nu din rațiuni de performanță, ci pur și simplu din cauza inerției utilizatorilor. Din nefericire însă, SQL nu este perfect adaptat pentru procesarea analitică. Vom evidenția în continuare câteva probleme pe care le aduce utilizarea SQL-ului în contextul OLAP.

3.1 Probleme legate de cererile tipice OLAP

Principala caracteristică a cererilor la care trebuie să răspundă un depozit de date este, bineînțeles, agregarea. Dacă agregarea se face doar după un atribut, SQL este suficient întrucât oferă posibilitatea de grupare și calculul principalelor funcții statistice la nivel de grup. Situația se schimbă atunci când sunt necesare grupări multiple. Sigur, SQL este suficient pentru a exprima și astfel de cereri, în fond putând descrie orice cerere, dar formularea cererilor cu grupări și agregări multiple cere din partea utilizatorului un efort mai mare. Din acest motiv este utilă extinderea standardului SQL cu noi operatori pentru a facilita formularea acestor cereri. Pentru claritate, vom analiza mai întâi niște exemple de cereri mai dificil de formulat. Vom lucra pe o relație având structura :

Vânzări(Cod_sale,Preț,Cod_prod,Cod_comis,Cod_reg,Cantitate,Data) și care înregistrează vânzările unor comis-voiaj ori pe o perioadă de un an.

Exemplificare

Analizăm patru exemple de cereri tipice pentru tranzacțiile OLAP:

1. Pentru fiecare comis-voiajor se cere cantitatea celei mai mari vânzări și regiunea în care a fost făcută.

26

Pentru ficare comis-voiaj or se cere cantitatea medie a vânzărilor produselor cu co
durile 100 și 200.

Pentru ficare comis-voiajor se cere numărul de vânzări din prima, respectiv din a
doua jumătate a anului, al căror volum(cantitate) a depășit cantitatea medie pe an.

Pentru cei care au vândut în timpul verii mai mult de un sfert din valoarea vânzărilor
lor anuale se cere valoarea celei mai mari vânzări și regiunea în care a fost efectuată
(valoare = pret*cantitate).

Interogarea l se poate exprima în SQL astfel :

SELECT a.Cod_comis, a.Cantitate, a.Cod_reg FROM (SELECT Cod_comis, max(Cantitate) FROM Vânzări

GROUP BY Cod_comis) v, Vânzări a WHERE a.Cod_comis = v.Cod_comis;

sau echivalent :

CREATE VIEW v AS

SELECT Cod_comis, max(Cantitate)

FROM Vânzări

GROUP BY Cod_comis;

SELECT a.Cod_comis, a.Cantitate, a.Cod_reg FROM Vânzări a, v WHERE a.Cod_comis = v.Cod_comis;

Destul de greoi, deși este vorba de o cerere relativ simplă pe o bază de date și ea foarte simplă. A doua cerere este o exemplificare a problemei "conflictului valoare-atribut" (datele dintr-o relație corespund metadatelor din alta):

CREATE VIEW U AS

SELECT Cod_comis, avg(Cantitate) avgC

FROM Vânzări

WHERE Cod_prod = 100

GROUP BY Cod_comis;

CREATE VIEW V AS

SELECT Cod_comis, avg(Cantitate) avgC

FROM Vânzări

WHERE Cod_prod = 200

GROUP BY Cod_comis;

SELECT V.Cod_comis, V.avgC, U.avgC FROM V, U WHERE V.Cod_comis = U.Cod_comis;

27

Soluția fără crearea celor două view-uri este mai greu inteligibilă; considerăm că în cazul sistemelor OLAP măsurile de securitate sunt mai relaxate, întrucât nu se fac operațiuni DML decât în condiții stabilite; în consecință utilizatorii vor avea întotdeauna dreptul de a crea astfel de view-uri.

Problema 3 subliniază dificultatea exprimării în SQL standard a cererilor în care se utilizează nivele de agregare diferite ale aceleiași grupări. O exprimare în SQL a acestei cereri este :

CREATE VIEW V AS

SELECT Cod_comis, avg(Cantitate) avgC

FROM Vânzări

GROUP BY Cod_comis;

CREATE VIEW UI AS SELECT a.Cod_comis, countO) nr FROM Vânzări a, V WHERE a.Cod_comis = V.Cod_comis AND a.cantitate > avgC AND Data < '2007-07-01' GROUP BY a.Cod_comis;

CREATE VIEW U2 AS SELECT a.Cod_comis, count(*) nr FROM Vânzări a, V WHERE a.Cod_comis = V.Cod_comis AND a.cantitate > avgC AND Data >= '2007-07-01' GROUP BY a.Cod_comis;

SELECT Ul.Cod_comis, Ul.nr, U2.nr FROM UI, U2 WHERE Ul.Cod.comis = U2.Cod_comis;

Se observă deja că e necesar să se scrie multe linii pentru a exprima această cerere. La fel se întâmplă și în cazul ultimei probleme :

CREATE VIEW V AS

SELECT Cod_comis, sum(Pret*Cantitate) val

FROM Vânzări

GROUP BY Cod_comis;

CREATE VIEW U AS SELECT *

FROM Vânzări

WHERE Data > '2002-06-01'

AND Data < '2002-09-01';

28

CREATE VIEW X AS

SELECT Cod_comis, sum(Pret*Cantitate) val, max(Pret*Cantitate) maxval

FROM U

GROUP BY Cod_comis;

SELECT V.Cod_comis, U.Cod_reg, FROM V, U, X WHERE V.Cod_comis = U.Cod_comis

AND V.Cod_comis = X.Cod_comis

AND X.val > V.val

AND X.maxval < X.val * 4;

Dacă structura bazei de date ar fi fost mai complicată, așa cum se întâmplă de obicei în realitate, cererile de mai sus ar fi devenit și mai lungi și mai greu de înțeles. De asemenea, astfel de cereri odată scrise nu vor fi folosite mereu la fel, datorită faptului că procesul de analiză la care este folosită baza de date este dinamic. Cererile vor trebui adaptate (sau rescrise), de unde rezultă că e nevoie de întreținerea lor, ori asta e un lucru dificil dacă ele nu sunt ușor de înțeles. In plus, se remarcă faptul că toate rezolvările problemelor de mai sus se fac prin mai multe parcurgeri ale tabelelor. Acest lucru, coroborat cu structura lor complicată induce o nouă problemă : motorul de analiză SQL nu va putea să le optimizeze (sau nu le va putea optimiza pe toate). Cum renunțarea la SQL nu este fezabilă din considerente mai sus descrise, e necesar un compromis, și anume extinderea limbajului SQL astfel încât să poată exprima clar și succint și astfel de cereri. Utilizatorii vor putea învăța relativ repede și ușor noile facilități ale limbajului, iar sintaxa va fi mai simplă și codul mai ușor de optimizat.

3.1.1 Extinderea SQL

Pentru a satisface toate criteriile de mai sus, e necesar ca modificările aduse sintaxei SQL să fie minime și în plus să se păstreze principiile generale de formulare a unei cereri. O soluție în acest sens este adăugarea unor clauze instrucțiunii SELECT care să permită exprimarea naturală a restricțiilor impuse variabilelor de grupare.

Modificări aduse sintaxei SQL

Clauzele FROM și WHERE nu vor fi modificate. In clauza GROUP BY se va opera doar o schimbare minoră, și anume se va permite specificarea variabilelor de grupare, de exemplu

GROUP BY Cantitate, Preț : C, P

C și P fiind variabile de grupare.

Se introduce o nouă clauză, SUCH THAT. Ea are rolul de a introduce restricții asupra variabilelor de grupare. Condiția care conține restricțiile respective poate fi complexă, formată eventual din mai multe subclauze conectate prin operatori logici (AND, NOT și OR). Clauza HAVING va conține alături de restricțiile obișnuite și agregări după unul sau

29

mai multe atribute. Se observă că din punctul de vedere al utilizatorului schimbările sunt foarte ușor de învățat (câteva ore par a fi arhisuficiente chiar și pentru un nespecialist). Pentru a demonstra și eficiența lor vom prezenta rezolvările cererilor de mai sus folosind sintaxa îmbogățită.

Rezolvările exemplelor în noul context

Soluție pentru prima cerere :

SELECT Cod_comis, Cantitate, Cod_regiune FROM Vânzări GROUP BY Cod_comis : C SUCH THAT C.Cantitate = max(Cantitate);

îmbunătățirea este evidentă. Iată și forma pe care o ia interogarea de la problema 2 :

SELECT Cod_comis, avg(A.Cantitate), avg(B.Cantitate) FROM Vânzări

GROUP BY Cod_comis : A, B SUCH THAT A.Cod_prod=100 AND B.Cod_prod=200;

Cererea de mai sus ilustrează modul de utilizare a variabilelor de grupare. Și în acest caz exprimarea este mult mai scurtă și mai ușor de înțeles. Problema 3 se rezolvă astfel :

SELECT Cod_comis, COUNT(A.*), COUNT(B.*) FORM Vânzări

GROUP BY Cod_comis : A, B SUCH THAT (A.Data < '2002-07-01'

AND A.Cantitate > avg(Cantitate)) AND (B.Data >= '2002-07-01'

AND B.Cantitate > avg(Cantitate));

In fine, problema 4 poate fi rezolvată cu următoarea cerere:

SELECT Pret*Cantitate, Cod_reg FROM Vânzări GROUP BY Cod_comis : A

SUCH THAT A.Data >= '2002-06-01' AND B.Data < '2002-09-01' HAVING sum(A.Pret * A.Cantitate) > 4*sum(Pret*Cantitate) AND A.Preț * A.Cantitate = max(A.Pret * A.Cantitate);

Odată cu aceste modificări nu putem spune însă că am rezolvat complet problema interogărilor specifice OLAP. Cererile se pot scrie acum mai ușor și mai natural, dar problema rezolvării lor eficiente rămâne. In secțiunea următoare se tratează un aspect specific implementării cererilor în OLAP, și anume calculul rezultatelor cererilor cu agregări multiple.

30

3.2 Calculul cubului de date

Așa cum am menționat în secțiunea dedicată agregărilor, menținerea tuturor nivelelor de agregare în baza de date este practic imposibilă. Cum procesul de analiză pe care trebuie să-1 sprijine sistemele OLAP necesită utilizarea tuturor acestor nivele, chiar dacă nu simultan, rezultă că viteza de calcul a diferitelor agregări rămâne o chestiune de primă importanță în domeniul data warehouse. In cazul agregărilor de date relativ la mai multe dimensiuni, operații foarte frecvent întâlnite în OLAP, datele stocate în nivelele de agregare ale dimensiunilor ajută mai puțin la creșterea vitezei, deci e nevoie de algoritmi performanți pentru ca analiza să se poată desfășura în condiții bune. Soluția stocării unor agregări precalculate e și ea binevenită (aproape indispensabilă).

S-au căutat diverse soluții pentru această problemă, atât în cazul reprezentării relaționale, cât și în cazul reprezentării datelor cu vectori multidimensionali.

3.2.1 Cazul relațional

Operatorul "Cub"

Operatorul de grupare implementat în SQL standard nu este suficient pentru a rezolva problema; în situațiile practice analiza cere adesea calcularea tuturor agregărilor, adică după toate combinările de atribute, sau măcar a unei submulțimi mari a acestei mulțimi. Operatorul " Cub", propus de Cray face tocmai acest calcul. Să luăm drept exemplu un model multidimensional cu numai trei dimensiuni, dar tipice, și anume produs, zonă și timp. Faptul va fi valoarea tranzacției. Atunci "Cubul" va calcula vânzările grupate după produs, zonă și timp; după zonă și timp; după produs și zonă; după produs și timp; numai după produs; numai după timp; numai după zonă, și în final vânzările totale. Acceptarea rapidă de către specialiști a utilității operatorului a făcut ca o variantă a acestuia să fie propusă pentru îmbogățirea standardului SQL.

S-au propus diverși algoritmi pentru implementarea "Cubului" în cadrul ROLAP, mulți fiind în fapt extensii ale algoritmilor clasici pentru calculul operatorului SQL de grupare. Pentru creșterea eficienței s-au urmărit trei idei principale :

Folosirea unor operații de grupare sau sortare a atributelor dimensiunii pentru a
"apropia" tuplurile între care există relații

Folosirea rezultatelor parțiale ale unor grupări efectuate pentru calculul unei sub-
agregări la sub-agregarea următoare, și în fine

Calculul unei agregări pe baza unei alte agregări gata făcute, în general mult mai
mici decât tabela de bază.

Cei mai cunoscuți algoritmi sunt PipeSort, PipeHash și Overlap. Vom descrie în continuare unul dintre ei, si anume Pipehash.

Algoritmul PipeHash

Vom defini mai întâi o latice de căutare, structură pe care algoritmul o primește la intrare.

31

Se numește latice de căutare pentru cubul de date un graf cu următoarele proprietăți:

nodurile reprezintă fiecare câte o grupare a cubului

între un nod i și un nod j există o muchie dacă și numai dacă j poate fi generat din
i (de unde i se numește părintele lui j) și j are exact cu un atribut mai puțin decât
i.

fiecare muchie m^ a laticei are asociate două costuri, și anume costul calculării lui
j din i când i nu este sortat, notat S(iriij), și costul calculării lui j din i când i este
sortat, notat A(iriij).

Observație : gradul exterior al fiecărui nod este egal cu cardinalul mulțimii atributelor grupării pe care o reprezintă. Nivelul k al laticei este mulțimea nodurilor de grad exterior k. Costurile S(rriij} și A(rriij} trebuie calculate în prealabil cu ajutorul unor proceduri statistice.

După cum sugerează și numele, algoritmul se bazează pe tabele de dispersie. Principala problemă care trebuie rezolvată este incapacitatea de a încărca în memorie tabelele de dispersie datorită dimensiunilor prohibitive. Algoritmul calculează un arbore MTS (Minimum spanning tree), subarbore al laticii cubului de date, pe care-1 utilizează la calculul efectiv al cubului. Proprietatea principală a acestui arbore este că pentru fiecare muchie (i, j), i este cel mai mic părinte al lui j. Se obțin optimizări ale vitezei prin procedee ca păstrarea rezultatelor parțiale într-un buffer-cache.

Descrierea algoritmului

Intrare : laticea de căutare

Pas l calculează aMTS = arborele MTS asociat laticii de căutare

Pas 2 lista_arbori <- aMTS

Pas 3 Cât timp lista_arbori 7^ $ execută :

scoate un arbore A din lista_arbori

Selectează-subarbore(A, A')

Calculează-subarbore(A')

Selectează-subarbore(A,A')

Dacă memoria disponibilă > memoria necesară calculului lui A atunci return A Altfel

/* Se alege s C S care va determina partiționarea lui A */ Fie S mulțimea atributelor rădăcinii lui A Fie Ps = numărul maxim de partiții ale rădăcinii lui A dacă se face partiționarea determinată de s

/* Deteminăm un subarbore As al lui A care are aceeași rădăcină și conține toate

grupările care conțin s */

32

Fie s C S astfel încât memoria ceruta de AS/PS sa fie mai mica decât memoria disponibila șterge As din A

se introduc arbori râmași în lista_arbori return As

Calculare-subarbore(A')

Fie M memoria disponibila;

Fie nrPărți memoria necesara lui A'*factor_de_siguranță;

se partiționează râdâcina lui A' în nrPărți

Pentru fiecare partiție

Se parcurge A' în lârgime și pentru fiecare nod n

Se calculează toți fiii lui n (cu o singura parcurgere)

Daca n se afla în cache se salveazâ pe disc și se eliberează memoria ocupata

de tabela sa de dispersie

Comentarii

Complexitatea acestui algoritm este exponențiala; practica a arâtat ca se comporta mai bine daca datele sunt compacte. Deși performanțele sale sunt net superioare abordârilor simpliste, în care grupârile se calculează independent, exista și soluții mai rapide.

3.2.2 Cazul multidimensional

Deși vectorii multidimensionali par la prima vedere o alegere proasta pentru modalitatea de stocare și manipulare a datelor, în principal datorita împrâștierii lor, proprietățile lor structurale îi fac o soluție foarte potrivită pentru implementarea modelului multidimensional. Calculul cubului de date este una din problemele la a cărei rezolvare folosirea vectorilor multidimensionali aduce un plus de performanță, demonstrând astfel viabilitatea lor. Vom prezenta în continuare un algoritm de calcul al cubului de date bazat pe vectori multidimensionali, elaborat de Y. Zhao, P.M. Deshpande și J.F. Naughton.

Varianta "naivă"

Vom descrie mai întâi, pentru un plus de claritate, o variantă simplificată a algoritmului, care nu evită calcule redundante și din a cărei rafinare rezultă algoritmul propriu-zis.

Fie V un vector tri-dimensional și A, B și C dimensiunile sale. Calculul agregării AB poate fi văzut ca o parcurgere a vectorului de-a lungul dimensiunii C cu un plan (reprezentat de produsul cartezian al dimensiunilor A și B). In practică, V va fi partiționat, deci nu vom putea parcurge tot planul AB deodată și va trebui să facem această operație pe fiecare partiție. Ne putem imagina o amplasare a partițiilor cubice în felul următor : așezăm partițiile una lângă alta astfel încât planele corespunzătoare dimensiunilor A și B să fie paralele, iar dreptele corespunzătoare dimensiunii C să fie în prelungire. Dacă fiecare partiție are dimensiunile de lungimi AP,BP,CP, parcurgem tot corpul geometric obținut

33

de-a lungul dimensiunii C cu dreptunghiuri de dimensiuni ACBC, trecând prin fiecare partiție. Putem calcula rezultate parțiale la trecerea prin fiecare partiție, stocându-le pe disc și calculând la sfârșit agregarea totala din toate rezultatele parțiale. In felul acesta, fiecare partiție este citita o singura data, deci numărul accesurilor de disc este minim, iar cantitatea de memorie utilizata este egala cu spațiul ocupat de o partiție. Cum partițiile sunt proiectate tocmai pentru a încăpea în memorie, nu avem probleme. Generalizarea pentru mai mult de trei dimensiuni nu pune nici un fel de probleme.

Calculul "cubului" presupune însă mai multe agregări. In cazul nostru, (vectorul V), trebuie sa calculam agregările AB, BC, AC, A, B, C și în final agregarea totala. Se observa ca putem privi mulțimea agregărilor de calculat ca pe o latice (termen întâlnit și la algoritmul PipeHash) cu ABC având fiii AB, AC și BC, AC având fiii A și C, etc. Un calcul eficient se poate face daca se ia un subarbore în aceasta latice și fiecare nod se va calcula din părintele sau din acest arbore. Determinarea arborelui optim era o problema în contextul ROLAP, pentru ca dimensiunile nodurilor nu erau cunoscute decât după calculul cubului și eram nevoiți sa folosim estimări mai mult sau mai puțin precise. Vectorii multidimensionali ne permit însă calculul exact al acestor valori și în plus cantitatea de memorie necesara pentru calculul unui fiu, deoarece cunoaștem dimensiunile vectorilor și ale partițiilor. Putem deci defini (și determina) arborele MST al laticii. Pentru fiecare nod n, părintele sau în arborele MST este un nod n\ de mărime minima din care se poate calcula n.

Descrierea algoritmului (varianta "naivă")

Intrare : laticea de căutare Pas l Calculează arborele MST pentru laticea de căutare

Pas 2 Calculează fiecare group-by Di{Di^..Dik din părintele D^D^^Di^^ de mărime minimă (din arborele MST). Se parcurge fiecare partiție a părintelui de-a lungul dimensiunii Di și se pune rezultatul fiecărei agregări într-o partiție a DilDi2..Dik; când o partiție e gata, se salvează pe disc, se eliberează memoria și se trece la următoarea. După parcurgerea DilDi2..Dik+1 partițiile produse formează chiar nodul ce trebuia calculat.

Algoritmul utilizează puțina memorie (nu încarcă decât o singura partiție odată), dar suferă din următorul motiv : unele date sunt citite de pe disc de mai multe ori, de unde rezulta pierderi de timp mari, pentru ca operațiile I/O sunt foarte lente. De exemplu, nodul ABC este parcurs o data pentru calculul fiului AB, o data pentru BC și încă o data pentru a calcula AC.

Din fericire, algoritmul admite îmbunătățiri consistente.

Varianta îmbunătățită (Mulți-Way Array Algoritm)

Eficientizarea algoritmului se bazează pe minimizarea numărului de citiri ale datelor de pe disc. (Amortizarea scanărilor) Se încearcă minimizarea spațiului de memorie folosit pentru a stoca în RAM cât mai multe date parțiale, pentru a nu mai fi nevoie de rescanâri.

34

Ordine dimensională

Un factor care poate influența pozitiv nevoia de memorie a algoritmului este ordinea logică în care privim dimensiunile. Dacă avem de-a face cu un vector multidimensional ale cărui dimensiuni sunt Di,D2,. . . Dn, putem alege să-1 parcurgem după o ordine O = (Dj1,Dj2, . . . , Djn). Acest lucru e independent de memorarea lui fizică, pentru că la partiționare dimesiunile sunt tratate uniform, deci nu e nevoie de nici o operație suplimentară.

Studiind modul de utilizare a memoriei s-a ajuns la următoarea regulă de alocare eficientă :

Dacă avem de calculat o agregare (D^,Dj2, . . . , -DJ„_1) a unui vector de dimensiuni (Di, D2, • • • , D n} citit în ordinea dimensională O = (Di, D2, • • • , Dn) și (D^, Dj2, . . . , -DJ„_1) conține un prefix al O = (Di,D2, . . . , Dn) de lungime p, < p < n — l, vom aloca spațiu pentru

i=l i=p+l

unități ale elementului vectorului, unde \Di\ este mărimea dimensiunii Di; iar \Ci\ este mărimea aceleiași dimensiuni, dar pentru partiție, deci mai mică în majoritatea cazurilor decât \Di .

Spre exemplu, calculul agregării BC (în cadrul exemplului de mai sus) e nevoie de |.Bc||Cc|w octeți, pentru AC de I^HC^ u octeți, iar pentru AB de |ylc||5c u octeți, unde u este numărul de octeți necesar pentru a memora un element al vectorului, iar Xc e mărimea dimensiunii X a vectorului (respectiv bucății de vector rezultată în urma partiționării) .

Memoria economisită va fi folosită la calculul mai multor agregări simultan, reducând astfel numărul de operații I/O și deci aducând un plus de viteză. Pentru a organiza calculele se folosește un arbore MST, la fel ca în algoritmul PipeHash.

Găsirea unui arbore MST

Arborele MST pentru un cub (Di,…,Dn) într-o ordine dimensională dată O = (Dj1, . . . ,Djn) este un arbore cu n + l nivele, rădăcina (Dj1, . . . ,Djn) fiind la nivelul n. Fiecare nod din arbore poate fi calculat din părinții săi. Calculul nu va fi însă la fel de eficient pentru fiecare dintre părinți; vom alege cel mai bun părinte pe baza regulii de mai sus privind necesarul de memorie. Pentru calculul nodului i se va folosi acel părinte care are proprietatea că necesarul de memorie pentru calculul lui i este minim. Pentru ca acest minim să se atingă, trebuie ca prefixul nodului părinte conținut în i să fie de lungime minimă. Dacă sunt mai multe altfel de noduri, se va alege cel mai mic termeni de spațiu ocupat.

Găsirea unui arbore MST nu rezolvă complet problema optimizării calculului cubului; asta deoarece nu toți arborii MST necesită la fel de multă memorie. Diferența între eficiența a doi arbori MST poate fi chiar foarte mare și depinde de ordinea dimensională aleasă.

35

Care e cel mai bun arbore MST ?

Pentru a răspunde la această întrebare vom determina mai întâi câtă memorie e necesară pentru calculul cubului folosind un arbore MST dat. Să presupunem că pentru fiecare partiție mărimea fiecărei dimensiuni este aceeași, notată cu c, adică \Ci = c, Vi. La nivelul n este rădăcina d! … Dn căreia îi alocăm cn unități de memorie; la următorul nivel avem nodurile Di..Dk..Dn, VI < k < n unde D& semnifică faptul că termenul respectiv lipsește. Fiecare nod conține un prefix al rădăcinii și lungimile acestor prefixe sunt evident de lungimi n — f, n — 2,…, 0. Conform regulii de mai sus privind alocarea memoriei, pentru acest nivel va fi nevoie de

71-1

ud

71-1

71-3

„71-1

unități de memorie. Generalizând, se obține pentru nivelul k un necesar de memorie de:

"n i a

Putem privi această expresie ca pe un polinom în c; observăm că ordinea în care am parcurs dimensiunile este determinantă pentru valoarea sa, deoarece coeficienții depind numai de această ordine. E relativ simplu de găsit ordinea dimensională optimă din punct de vedere al consumului de memorie; valoarea expresiei se minimizează dacă se minimizează coeficienții polinomului. In consecință, minimul se atinge pentru ordinea O = (Di,…, Dn) cu di < D-2 < • • • < \Dn\. Putem deci calcula necesarul de memorie pentru calculul unui arbore. Formula de calcul este însă prea complicată, fiind compusă din sumele de pe fiecare nivel. E naturală întrebarea "Care este o margine superioară pentru memoria necesară calculului cubului parcurgând un arbore dat ?". Chiar dacă această margine ar fi ceva mai mare decât necesarul real de memorie, ea ar putea fi utilizată cu succes din punct de vedere practic, pentru că oricum trebuie să rămână și o zonă de memorie de rezervă. Dacă notăm cu d media geometrică a mărimilor dimensiunilor di, …, Dn o margine superioară este cn + (d + l + c)n~l. Demonstrația acestui fapt este calculatorie. Pornind de la inecuațiile

Dl

n ia

i=k+l

< \D2

71-1

n ia

i=k+l

IA "-1 < IA

i=k+l

(evidente din relația de ordine dintre \Di\, ..\Dn\), obținem prin înmulțire

(H IA

\71-1

71-1

n

i=k+l

71-1

36

și aplicând apoi regula de calcul a memoriei pentru fiecare nivel, sumând și grupând termenii având aceeași putere a lui d, rezulta în final ceea ce trebuia demonstrat.

In final, utilizând toate rezultatele de mai sus se poate trece la scrierea efectiva a algoritmului. Daca T este un arbore și nu avem destula memorie pentru a-1 calcula, vom fi nevoiți sa nu-1 parcurgem în întregime ; unii subarbori vor fi calculați ulterior și se numesc arbori incompleți. Problema alegerii subarborilor care sa fie calculați pare a fi NP-completâ și se folosesc metode euristice pentru a o rezolva.

Descrierea algoritmului

Pas l Calculează T un MST pentru o ordinea dimensională optimă O

Pas 2 Inițializează lista arborilor de calculat cu T

Pas 3 Pentru fiecare arbore T' din lista aborilor de calculat

Pas 3.1 Creează subarborele de lucru W și subarborii incompleți Is

Pas 3.2 Alocă memorie subarborilor

Pas 3.3 Parcurge partițiile rădăcinii lui T' în ordinea O

Pas 3.3.1 calculează agregarea fiecărei partiții în grupările din W

Pas 3.3.2 generează rezultate intermediare pentru Is

Pas 3.3.3 scrie partițiile complete ale lui W pe disc

Pas 3.3.4 scrie rezultatele intermediare în partițiile lui Is

Pas 3.4 Pentru toți I

Pas 3.4.1 generează partițiile complete din părțile lui Is Pas 3.4.2 scrie partițiile complete pe disc Pas 3.4.3 Introduce I în lista arborilor de calculat

Importanța algoritmului

Așa cum am menționat anterior, eficiența algoritmului este superioara algoritmilor rezultați din generalizarea celor folosiți pentru calculul grupărilor în sistemele relaționale. Mai mult, acest algoritm poate fi utilizat și în sisteme relaționale, sigur, nu direct, ci prin încărcarea tabelelor în vectori multidimensionali și transformarea rezultatelor în tabele. Testele practice au demonstrat un fapt surprinzător : chiar daca sunt necesare operații suplimentare pentru cele doua transformări în și din vectori multidimensionali, algoritmul de mai sus rămâne mai eficient decât cei care folosesc tabelele în mod direct.

37

Capitolul 4

Exploatarea unui Data Warehouse -câteva elemente de data mining

4.1 Motivație

Cantitatea mare de date dintr-un data warehouse pune nu numai probleme legate de gestionare și accesare, ci și de interpretare. Mai concret, dacă sistemul nu face altceva decât să răspundă la diversele cereri formulate de utilizator pur și simplu afișând niște cifre, e posibil ca rezultatul să nu fie satisfăcător. Motivul este simplu: un "morman de cifre", chiar dacă este prezentat sub forma unui raport, se poate dovedi nefolositor dacă lipsesc instrumentele adecvate pentru analiza sa. In procesul de luare a deciziilor se folosesc desigur și datele numerice, dar centrul de interes se plasează în sfera legăturilor (corelațiilor) dintre faptele studiate. Aceste legături nu sunt însă ușor de observat, mai ales dacă datele sunt eterogene (adică prezintă aspecte esențial diferite ale afacerii, sub formă de măsurători asupra faptelor, exprimate în unități de măsură incomensurabile).

4.1.1 Statistică inferențială versus data mining

Statistica se ocupă de interpretarea datelor numerice și oferă mijloace de rezolvare a problemei de mai sus. Din nefericire însă aceste tehnici sunt limitate, pentru că se bazează pe teste statistice. Un test statistic este o metodă de a verifica o ipoteză. Spre exemplu, testul x2 poate fi folosit pentru a determina dacă două variabile aleatoare discrete sunt independente. Valorile trebuiesc puse într-un tabel de contingență și apoi se aplică pur și simplu o formulă de calcul. Răspunsul este confirmarea sau infirmarea ipotezei în funcție de valoarea rezultată din calculul efectuat, cu o marjă de eroare prestabilită. Se evidențiază aici câteva dezavantaje:

Deși formula e simplu de aplicat, matematica din spatele ei este destul de complicată;
dacă nu cunoaște bine și aceste detalii utilizatorul poate greși.

Testul funcționează doar pentru testarea unei ipoteze. Adaptarea lui pentru alte
ipoteze necesită cunoștințe avansate de statistică.

38

Chiar dacă avem la dispoziție un număr mare de teste pentru diferite ipoteze, e
posibil ca la un moment dat în analiză să fie nevoie de construirea unui nou test.

Pentru aplicarea unui test trebuie să formulăm problema în termeni matematici,
lucru care nu poate fi convenabil decât pentru o persoană cu pregătire matematică.

Raportul dintre cantitatea de muncă făcută de om și cea făcută de calculator nu
este foarte bun pentru că procesul nu este automatizat.

In fine, ipoteza pe care o testează un astfel de test trebuie formulată a priori de
analist. Intr-o situație practică există o multitudine de ipoteze care ar putea fi
testate. Intuiția analistului este solicitată la maxim, pentru că el trebuie să aleagă
ipotezele viabile și nu are la dispoziție nici un fel de algoritm pentru aceasta. Dacă în
plus avem de-a face cu o situație în care e adevărată o ipoteză complet neașteptată,
șansele ca acest fapt să fie descoperit sunt foarte mici. Avem aici o problemă
serioasă, pentru că tocmai descoperirea unor informații total noi (și deci neașteptate)
aduce cele mai mari beneficii.

Tehnicile de analiză pe care le vom descrie încearcă să surmonteze aceste dezavantaje. Metode de analiză de acest tip au apărut încă din anii '60, dar lipsa dispozitivelor de calcul avansate a făcut ca ele să nu poată fi utilizate. Aceste rezultate au fost obținute de statisticieni ca Benzecri sau Tuckey și domeniul a fost numit de aceștia statistică ex-ploratorie. Diferența între statistica exploratorie și ceea ce numim în mod clasic statistică este însă destul de mare și de aceea mulți preferă să utilizeze denumirea de data mining, denumire care va fi folosită și în această lucrare.

4.2 Formalizarea matematică a problemei. Terminologie

In cele ce urmează vom descrie câteva metode matematice care pot facilita interpretarea datelor numerice. Dacă aceste date se prezintă sub forma unui tabel, lucru foarte frecvent în cazul rapoartelor create de un SGBD, vom privi coloanele ca pe niște variabile, iar liniile ca pe indivizi. Noțiunile de individ și variabilă vor fi în centrul analizei și deci merită să aruncăm o privire asupra lor. Vom nota în general cu n numărul de indivizi (linii) și cu p numărul de variabile (coloane).

4.2.1 Indivizi

Indivizii pot fi văzuți ca vectori reali cu p componente. Fiecare individ este caracterizat de cele p variabile, valorile acestor variabile fiind deci componenetele vectorului-individ. Spațiul W se va numi spațiul indivizilor. Pentru a compara indivizii între ei trebuie aleasă o metrică pe acest spațiu. Metrica trebuie să fie compatibilă cu problema pe care o studiem, adică dacă doi indivizi sunt apropiați (distanța dintre ei este mică), atunci cei doi sunt asemănători. Reciproc, dacă cei doi sunt la mare distanță, ei trebuie să fie

39

esențial diferiți din punctul de vedere al analizei. Distața euclidiană este o bună alegere în multe cazuri, dar există și situații în care se vor prefera alte distanțe.

O calitate importantă a indivizilor este importanța lor. Spre exemplu, dacă indivizii sunt regiuni geografice și se studiază vânzările companiei în aceste regiuni, e posibil ca analistul să considere (din motive economice) că unele regiuni sunt mai importante, adică au un potențial mai mare pentru creșterea volumului tranzacțiilor. In acest caz, fiecărui individ i se va asocia un număr real subunitar numit pondere. Suma ponderilor tuturor indivizilor trebuie să fie egală cu 1. Ponderea fiecărui individ va fi proporțională cu importanța sa. Dacă însă indivizii au importanță egală, ponderile lor vor fi egale și vom considera că sunt neponderați, pentru că ponderea nu mai aduce în acest caz nici o informație utilă. Indivizii neponderați se mai numesc anonimi. Acest termen este moștenit, ca și termenul de individ de altfel, de la analiza sondajelor de opinie, unde păstrarea anonimatului celor intervievați împiedică atribuirea unor ponderi.

Motivul pentru care considerăm indivizii vectori în W este faptul că vectorii reali pot fi reprezentați grafic prin puncte. Mulțimea indivizilor pe care îi analizăm se va reprezenta printr-un nor de astfel de puncte. De aceea ne vom referi la această mulțime cu sintagma "norul de puncte-indivizi". Forma acestui nor poate releva informații noi despre faptele pe care le studiem, intrucât este determinată de relațiile dintre variabile. O noțiune importantă în studiul norului de indivizi este noțiunea de inerție.

Definiția 8 (Inerția)

Fie a e 1RP un punct oarecare. Atunci numim inerție a norului de puncte-indivizi față de punctul a numărul

n n

Ia, = Y^Pi(Gi ~ a)TM(ei ~ a) = ^Pi\\ei ~ a\\M,
i=l i=l

unde M este matricea simetrică și pozitiv definită care dă metrica aleasă pentru spațiul indivizilor, iar Ci este individul cu numărul de ordine i; pi este ponderea individului i.

Definiția 9 Inerția globală

Dacă g este centrul de greutate al norului (e vorba de noțiunea geometrică de centru de greutate), atunci inerția norului față de g se numește inerție globală și se notează cu

!„•

Inerția față de un punct satisface proprietatea:

Ia = I9+ \\9-a\\lf,

relație cunoscută sub numele de formula lui Huygens.

Tehnicile de analiză pe care le vom trata sunt bazate pe faptul că distanța dintre punctele-indivizi "ascunde" informație utilă. Din nefericire în marea majoritate a cazurilor (de fapt aproape întotdeauna) p este mai mare decât 3, și de aceea reprezentarea grafică nu poate fi vizualizată direct. Matematica oferă însă metode de reprezentare în plan a acestui nor, cu pierdere minimă de informație. Vom reveni la acest aspect în cele ce urmează.

40

4.2.2 Variabile

La fel ca și indivizii, variabilele pot fi văzute ca vectori reali de n componente. Spațiul ]Rn va fi numit spațiul variabilelor. Denumirea de variabilă vine din statistică; din punct de vedere statistic, coloanele tabelului sunt selecții de volum n asupra unor variabile aleatoare.

In general variabilele iau valori reale (procente, sume de bani, cantități de mărfuri, etc), dar există și cazuri în care valorile sunt discrete. Sigur, numerele naturale sunt în particular numere reale, dar dacă valorile posibile ale variabilei sunt puține nu o mai putem trata ca și cum ar lua valori reale. De exemplu, dacă indivizii sunt înregistrări ale datelor unor persoane putem avea o variabilă care indică sexul, deci cu numai două valori posibile. Variabilele care iau valori reale se vor numi continue, iar cele care iau valori naturale se vor numi variabile nominale. Valorile unei variabile nominale se numesc modalități.

Pentru studiul variabilelor se folosesc următoarele obiecte matematice:

Definiția 10 (Media)

Media de selecție a variabilei X j este

n

m(Xj) = X j = Y,Pixa,

i=l

unde pi este ponderea individului i, iar Xij este valoarea pe care o ia variabila j pentru individul i.

Definiția 11 (Dispersia)

Dispersia de selecție a variabilei X j este

cu aceleași semnificații pentru Pi și X j.

Definiția 12 (Covarianța de selecție)

Covarianța a două variabile X j și Xk este

n

cov(Xj,Xk) = vjk = ^2pi(Xij – Xj)(Xik – Xk)

Definiția 13 Coeficientul de corelație

Numim coeficient de corelație de selecție a două variabile numărul real

V' •

cor (X i, X j) = Tij =

Coeficientul de corelație dintre două variabile este un număr subunitar. Dacă valoarea sa este apropiată de -l, cele două variabile sunt puternic corelate negativ (creșterea uneia coincide cu descreșterea celeilalte), iar dacă e aproape de l, variabilele sunt corelate pozitiv. Dacă însă valoarea coeficientului este zero sau aproape zero, vom spune că variabilele sunt necorelate. Practic acest lucru va fi interpretat ca un indicator la faptului că variabilele sunt independente, deși din punct de vedere matematic necorelarea nu implică independență.

41

4.3 Metode de analiză factorială

Analiza factorială înseamnă studierea norului de puncte-indivizi prin proiecția pe un plan. Acest plan trebuie ales astfel încât deformarea norului (inevitabilă datorită proiecției) să fie minimă. Planul ales se va numi plan factorial principal. Astfel vom obține o imagine grafică a norului de puncte-indivizi, imagine care poate ajuta analiza. In plus, va trebui să putem caracteriza cantitativ eroarea introdusă de deformarea prin proiecție si să găsim cele mai bune metode de a interpreta graficul obținut.

4.3.1 Analiza în componente principale

Analiza în componente principale (A.C.P.) este o tehnică de analiză prin proiecție care funcționează atunci când variabilele sunt continue. Avem la dispoziție doi "nori" de puncte : indivizi și variabile. Principiul A.C.P. este reprezentarea acestor "nori" într-un spațiu de dimensiune mult mai mică (se presupune că dimensiunile n și p ale spațiilor indivizilor și respectiv variabilelor sunt prea mari pentru a se putea face o reprezentare grafică).

In general dimensiunea acestui spațiu este 2 (deci spațiul de proiecție este chiar planul factorial principal), dar dacă reprezentarea în plan nu este suficient de precisă se poate alege soluția reprezentării norului proiectat într-un spațiu tridimensional, graficul rezultat fiind reprezentabil pe calculator.

Reprezentarea grafică obținută va releva informații noi despre relațiile dintre indivizi și variabile. Spre exemplu, dacă norul de puncte-indivizi are o formă alungită, elipsoidală, atunci rezultă că există o corelație liniară între variabile. Dacă însă norul are forma aproape sferică, punctele fiind împrăștiate uniform în cadrul lui, atunci nu avem nici o corelație.

Corelație de-a lungul unei axe Necorelare (izotropie)

Figura 4.1: Formele norilor și interpretarea lor

Analiza norului de puncte-indivizi

Așa cum am menționat anterior, spațiul de proiecție trebuie ales astfel încât deformarea să fie minimă. Pentru a putea alege acest spațiu avem însă nevoie de o formulare precisă, matematică, a criteriului de mai sus. Ipoteza cu care lucrăm este că distanțele dintre indivizi "ascund" informații utile. De aceea vom căuta să minimizăm modificarea acestor distanțe. Este evident că oricare ar fi spațiul de proiecție ales, unele distanțe vor fi mult modificate prin proiecție, iar altele mai puțin. Trebuie să facem în așa fel încât

42

deformarea globală să fie cât mai mică. Vom alege deci spațiul de proiecție astfel încât suma pătratelor distanțelor dintre proiecții să fie maximă. Această alegere se justifică prin faptul că prin proiecție distanțele se micșorează, deci atunci când suma pătratelor este maximă, deformarea globală este minimă. Pentru a enunța acest principiu în termeni de inerție avem nevoie de următorul rezultat:

Lemă Inerția globală este media pătratelor distanțelor dintre indivizi.

i j

Demonstrație

Se aplică formula lui Huygens pentru fiecare individ și se sumează relațiile :

Pllei =PlIg+Pl\\ei -g||M

Pjen = Pnlg + Pnen ~ gM

rezultă :

&;4 = Y^Pilg + Y,Pi\\ei ~ 9\\2M =>• &;&jl|e; – ej\\lt = Ig + Ig = IIg

iii i j

(M este peste tot matricea care dă metrica)

In consecință, în termeni de inerție, criteriul de optim ia forma următoare : cel mai bun spațiu de proiecție este acela care maximizează inerția globală a norului de puncte-indivizi.

Notăm cu X tabelul de date, iar cu Y tabelul centrat (din fiecare variabilă se scade media sa empirică). Vom lucra pe tabelul centrat. Faptul că folosim tabelul centrat Y și nu pe cel inițial X nu schimbă rezultatul analizei. Acest artificiu are un singur efect, și anume mutarea centrului de greutate al norului de puncte-indivizi în originea spațiului. Astfel se simplifică semnificativ calculele.

V este matricea de covarianță (vij = cov(Xij X j)), iar M metrica. Cu aceste notații, rezolvarea problemei reprezentării optime a norului de puncte-indivizi este dată de următoarea teoremă :

Teorema l (Spațiul de proiecție)

Subspațiul de dimensiune q pe care se proiectează optim în sensul maximizării inerției globale este generat de primii q vectori proprii ai matricii A = V M din M.ptp(lR). Vectorii proprii sunt considerați în ordinea descrescătoare a valorilor proprii corespunzătoare ai > A2> … > A,.

Demonstrație

Fie Ti spațiul de proiecție optim și pi, … Pn proiecțiile punctelor-indivizi Ai,…An în

43

acest spațiu. Aplicând teorema lui Pitagora avem relațiile O Ai = OPi + AiPi , pentru Vi = L. n, de unde rezultă

n

] O Ai = y y OPi + y _, ^4i-Pj , unde O este originea spațiului.

i=l i=l i=l

Minimizarea deformărilor revine deci la minimizarea Y^PiAiPi , distanțele O Ai fiind constante.

Fie a E Rp un vector M-normat (i. e. aTMa = 1) și Aa dreapta determinată de a și origine (dreapta versor a lui a). Proiecția pe Aa a unui punct A^ notată Qi va avea proprietatea OQi = Y^Ma, unde Yi este vectorul cu p componante egal cu linia i din tabelul Y. Acest fapt rezultă imediat din definiția produsului scalar și ținând seama că tabelul Y este obținut prin centrarea lui X. In consecință, coordonatele Qi pe Aa sunt YTMa și deci

i2 = aTMYTDYMa = aTMVMa = aTMAa,

i=\

unde D este matricea ponderilor definită de relația D = diag(pi, . . . ,p„).

Dacă vrem să minimizăm deformarea proiecției pe o dreaptă de versor a, putem determina a ca soluție a problemei de programare pătratică

l max(aTMAa) \ aTMa = l

Rezolvăm această problemă cu metoda multiplicatorilor lui Lagrange :

O f*

C = aTMAa – X(aTMa – 1), — = O => 2MAa – 2\Ma = O => MAa = XMa (l)

CJd

înmulțim (1) la stânga cu aT și avem

aTMAa = XaTMa => A = aTMAa

M fiind matricea care dă metrica pe spațiul indivizilor, trebuie să fie pozitiv definită, deci inversabilă. Putem deci înmulți în relația (1) cu M"1, de unde obținem Aa = Aa, de unde rezultă că A este valoare proprie a matricii A. Fiind soluți a problemei de programare pătratică enunțate mai sus, A este în plus si valoarea proprie maximă. De aici rezultă că a este vectorul propriu al matricii A corespunzător valorii proprii maxime.

Căutarea celui de-al doilea generator al spațiului Ji se face după aceeași metodă. Trebuie să găsim a2 E W M-normat, M-perpendicular pe a și care să minimizeze funcția – Problema de programare pătratică are deci forma

v a^Ma = O Lagrange-anul este deci :

£ = a^MAa2 – 2\2(a^Ma2 – 1) –

44

și din condiția de anulare a derivatei avem :

r\ s*

—— = O => 2MAa2 – 2A2Ma2 – ri2Ma = O da-2

Prin înmulțire cu aT avem : 2MAa2 – 2\2aTMa2 – r)2aTMa = O, dar aTMa = l și MAa = \a => aTMA = XaTM.

De aici rezultă XaTMa2 — r] = O, și ținând cont de faptul că a j_m «2 =>• aTMa2 = O avem 772 = 0. Acum problema este asemănătoare cu prima, deci va avea același tip de soluție. A2 va fi cea de-a doua valoare proprie în ordinea mărimii. Repetând raționamentul de q ori și renotând a cu ai și A cu ai avem demonstrația completă.

Subspațiul Ji căutat va fi deci subspațiul generat de primii q vectori proprii ai matricii A.

Observație A se numește matricea inerției deoarece urma sa este egală cu inerția globală.

Definiția 14 (Axă principală)

Se numește axă principală de inerție un vector propriu a, M-normat, al matricii de inerție.

Definiția 15 (Factor principal)

Se numește factor principal asociat axei principale a j, notat Uj, vectorul din 1RP

Definiția 16 (Componentă principală)

Se numește componentă principală de ordin j vectorul din K1 definit de relația

Proprietate

Factorii principali u j sunt vectori proprii M"1 ortogonali ai matricii MV asociați valorilor proprii X j ale matricii de inerție.

Analiza nenormată

Dacă datele sunt omogene, adică măsurate cu aceelași unități de măsură, nu e nevoie de transformări ale tabelului înainte de reprezentarea grafică. In acest caz analiza se va numi nenormată, întrucât transformarea pe care o vom aplica pentru date eterogene va fi o normare a vectorilor variabile. Metrica M utilizată în acest caz va fi matricea identitate. Această metrică dă importanță egală tuturor variabilelor, indiferent de dispersia lor. Din acest motiv variabilele cu dispersia mare vor influența mai mult analiza decât cele cu dispersie mică.

45

Analiza normată

Datele pot fi însă destul de eterogene, și atunci este necesară o ponderare a variabilelor în funcție de dispersia lor empirică. O soluție la îndemână este împărțirea fiecărei variabile cu dispersia sa. Dacă ne gândim la unități de măsură, observăm că rezultatul acestei împărțiri nu depinde de unitatea de măsură a variabilei inițiale. De aici deducem că această operație produce și o adimensionalizare a datelor. Variabilele nou obținute vor avea toate dispersia egală cu l, deci ponderea lor în analiză va fi echilibrată. Lucrăm tot cu tabelul centrat Y, din aceleași motive ca la analiza nenormată.

Cum fiecare coloană din Y reprezintă o variabilă centrată, deci cu media nulă, rezultă că hi^hd este egală cu dispersia variabilei necentrate, unde D = diag(pi,… ,pn). In consecință, alegând metrica D pentru spațiul variabilelor, transformarea pe care o vom aplica tabelului pentru omogenizare va fi normarea vectorilor coloane. Operația poartă numele de reducere, iar tabelul rezultat se numește tabelul centrat redus și se notează cu Z.

In plus, din definiția coeficientului de corelație dintre două variabile rezultă o proprietate utilă a tabelului centrat redus : d2(Zj, Z&) = 2(1 —rjk), unde Zj, Z^ sunt coloanele j, respectiv k din Z iar Tjk este coeficientul de corelație dintre cele două variabile. Consecința practică este faptul că distanța dintre două variabile centrat-reduse poate fi interpretată exact așa cum ne spune intuiția :

Dacă două variabile sunt foarte apropiate, i.e. distanța dintre ele este mică, atunci
ele sunt puternic corelate pozitiv și deci creșterea sau descreșterea uneia va fi însoțită
de creșterea și respectiv descreșterea celeilalte;

Dacă dimpotrivă variabilele sunt foarte depărtate (i.e. distanța dintre ele ~ 4, adică
maxim), atunci ele vor fi corelate negativ (rjk ~ — 1) și deci creșterea uneia va fi
insoțită de descreșterea celeilalte;

Dacă distanța este medie (~ 2), atunci variația uneia nu va influența pe cealaltă,
corelația fiind aproximativ nulă.

Vectorii Z j vor avea toți norma egală cu l (evident, de vreme ce au fost normați) și deci într-o reprezentare grafică vor fi puncte pe cercul de rază 1. Vom folosi acest fapt la analizarea norului de puncte-variabile.

Analiza norului de puncte-variabile

Proiecția norului de puncte-variabile pe un subspațiu de dimensiune 2 sau 3 poate fi folosită pentru analiză. Se pune aceeași problemă a minimizării deformării, criteriul de optim fiind același. Rezolvarea este foarte asemănătoare (de fapt absolut analoagă) cu rezolvarea problemei proiecției norului de puncte-indivizi.

Se ajunge la un rezultat similar cu cel obținut pentru norul de puncte-indivizi. Subspațiul de proiecție va fi generat de vectorii proprii corespunzători primelor q valori proprii ale matricii YMYTD. Se demonstrează însă că valorile proprii obținute în urma acestui calcul sunt egale cu cele obținute pentru indivizi. Din punct de vedere practic, asta înseamnă că nu este nevoie să le mai calculăm încă o dată. In plus, dimensiunea matricii inerției

46

este p, iar dimensiunea matricii YMYTD este n, și cum în general p este mult mai mic decât n, se vor calcula mai ușor valorile proprii pentru matricea inerției.

Reprezentarea grafică a variabilelor se face puțin diferit de a indivizilor, pentru a sprijini interpretarea intuitivă a graficului. Dacă indivizii se vor reprezenta prin puncte, mici discuri sau pătrate, variabilele se vor reprezenta ca niște săgeți care pleacă din origine și care au vârful în punctul-variabilă. Variabilele vor fi astfel mai ușor comparate cu niște direcții, iar două variabile vor fi considerate asemănătoare, înrudite, dacă vor fi reprezentate prin direcții apropiate, ceea ce corespunde conceptului statistic de corelație.

Definiția 17 Se numește cerc de corelație principală subspațiul generat de vectorii corespunzători primilor q valori proprii ale matricii de inerție.

Dacă analiza este normată, variabilele vor fi reprezentate ca niște săgeți cu vârfurile pe cercul unitate. Unghiurile dintre aceste săgeți sunt ușor de comparat și de interpretat.

Putem alege și soluția reprezentării simultane pe același grafic a proiecțiilor celor doi nori. Trebuie însă menționat că în acest caz apropierea dintre un punct-individ și un punct-variabilă nu are nici o interpretare, întrucât cele două puncte fac parte din spații diferite. Direcțiile indicate de săgețile care reprezintă variabilele pot ajuta la interpretarea pozițiilor indivizilor în nor. Dacă doi indivizi sunt diametral opuși pe direcția indicată de o variabilă, atunci putem trage concluzia că variabila respectivă îi diferențiază puternic.

Calitatea analizei

Reprezentarea grafică într-un plan a norului de puncte-indivizi nu se poate face fără deformare. Tehnica pe care am folosit-o minimizează această deformare, dar se pune problema calității rezultatelor obținute. Cu alte cuvinte, am obținut un optim, dar cât de bun este acest optim ?

O altă întrebare este în ce condiții putem obține rezultate satisfăcătoare ? In plus, dacă suntem în situația de a nu putea folosi A.C.P. din cauza rezultatelor prea imprecise, ce concluzii putem trage din acest fapt ?

Mai trebuie remarcat că în cele de mai sus s-a ignorat posibilitatea ca matricea A să aibă mai puțin de q valori proprii. Având însă în vedere că de obicei q este 2, rareori 3, iar n și p (numărul de indivizi respectiv variabile) sunt în marea majoritate a cazurilor cel puțin de ordinul zecilor, putem presupune că nu ne vom lovi niciodată practic de această problemă.

In esență, A.C.P. revine la găsirea unui sistem de axe convenabil și la reprezentarea norului de puncte în acest sistem, făcând abstracție de ultimele p — q axe. In consecință, pentru ca analiza să nu fie compromisă, trebuie ca proiecția norului pe subspațiul generat de aceste axe să aibă un procent cât mai mic din inerția norului inițial. Acest criteriu se bazează și el pe ipoteza că informația este ascunsă în distanțele dintre indivizi.

Pentru a caracteriza calitativ analiza trebuie să găsim cât de importante sunt coordonatele punctelor pe o axă oarecare din punctul de vedere al inerției, adică ce procent din inerție se pierde prin neglijarea axei respective. Se poate verifica printr-un calcul rapid că acest procent este proporțional cu valoarea proprie \j corespunzătoare axei respective. Cu alte cuvinte, calitatea analizei este cu atât mai bună cu cât valorile proprii ai și A2

47

sunt mai mari în comparație cu celelalte. Cazul ideal este atunci când primele două valori proprii sunt mari, iar toate celelalte sunt aproape nule. Atunci graficul obținut prin A.C.P. conține aproape toată informația din norul inițial. La polul opus se situează cazul în care valorile proprii descresc liniar. Raportul dintre suma primelor două și suma totală este mic și analiza mai puțin precisă.

Se remarcă faptul ca prin A.C.P. se "aruncă" o parte din informația conținută de norul inițial. De aici rezultă că dacă datele de lucru inițiale au infomație redundantă, este posibil s-o "aruncăm" tocmai pe aceasta, realizând astfel o analiză precisă. A.C.P. elimină deci o redundanță, dacă aceasta există. Dacă nu, analiza nu va fi precisă, " aruncându-se" informație utilă. Redundanța pe care o poate elimina A.C.P. este o redundanță "ascunsă" în corelațiile dintre variabile. Cu cât variabilele sunt mai puțin corelate, cu atât șansele unei analize precise sunt mai mici. In consecință, atunci când A.C.P. nu dă rezultate, putem trage concluzia că variabilele pe care le studiem sunt puțin corelate.

Indivizi si variabile ilustrative

Pierderea de informație datorată proiecției, chiar dacă nu este mare, poate duce la unele confuzii. Nu putem ști cu siguranță dacă o relație găsită este rezultatul unui fapt obiectiv sau o iluzie dată de deformarea inerentă analizei. De aceea se preferă să nu se utilizeze toate datele disponibile pentru efectuarea analizei. Se va păstra nealterat un grup de indivizi (aleși aleator sau după un criteriu specific domeniului din care provin datele). Acest grup va servi ca eșantion de verificare a rezultatelor analizei. Rezultatele care se confirmă și pentru acești indivizi sunt rezultate în care putem avea încredere. Indivizii din acest eșantion se vor numi indivizi ilustrativi.

Aceeași tehnică se poate folosi și pentru variabile. Variabilele alese pentru testarea rezultatelor analizei se vor numi variabile ilustrative.

Dezavantajele ACP

Din cele de mai sus rezultă că analiza în componente principale nu suferă de neajunsurile statisticii clasice, inferențiale. Procesul de analiză poate fi în mare măsură automatizat, reducând la minim volumul de muncă al omului. Analistul nu trebuie să formuleze nici o ipoteză și nici nu are nevoie de cunoștințe avansate de matematică pentru a utiliza această metodă. Este suficient să cunoască noțiunile de medie, dispersie și corelație pentru a putea folosi un soft care face astfel de analize.

Partea proastă este că analiza nu poate releva decât corelații liniare între variabile. Corelațiile neliniare nu vor fi puse în evidență și pentru descoperirea lor vor trebui utilizate alte metode.

Deasemenea, în cazul unui volum mare de date, graficul poate deveni foarte aglomerat și greu de interpretat.

4.3.2 Analiza de corespondență simplă (ACS)

In cazul în care variabilele cu care lucrăm nu sunt continue, ACP nu mai poate fi folosită direct. Pentru analiza relațiilor dintre două variabile nominale se poate folosi

48

ACS. Efectuarea acestei analize revine la aplicarea unor transformări datelor, urmate de efectuarea unei ACP.

Primul pas este construirea unui tabel de contingență. Dacă X și Y sunt variabilele pe care le analizăm, iar X are n modalități și Y are p modalități, tabelul de contingență IC este o matrice cu n linii și p coloane, care conține pe poziția 2, j numărul de indivizi care au simultan modalitatea i a variabilei X și modalitatea j a variabilei Y .

Prin împărțirea tururor componentelor acestui tabel cu k = n x p se obține un nou tabel notat cu T și numit tabelul frecvențelor relative. Vom nota cu fi0 suma elementelor de pe linia i a tabelului T și cu f0j suma elementelor de pe coloana j a lui T .

Putem face acum o ACP pe acest tabel privind liniile ca pe niște indivizi și coloanele ca pe niște variabile.

Metrica pe care o vom folosi trebuie să fie însă compatibilă cu problema. Distanța euclidiană are dezavantajul că nu e stabilă la agregarea liniilor (coloanelor). Din modul de construcție al tabelului pe care se face analiza e natural ca la combinarea prin adunare pe componente a două coloane distanța dintre oricare două linii să nu se modifice, și analog și pentru tabelul transpus. Asta deoarece dacă hotărâm din motive independente de analiză să cumulăm două modalități ale unei variabile, analiza nu trebuie să se schimbe, întrucât relația dintre variabile nu este afectată.

O distanță care are proprietatea de stabilitate la agregarea liniilor/coloanelor este distanța x2. Prin definiție, distanța dintre două linii i și k este dată de relația:

p i

4.4 Exemplu de analiză ACP

Pentru a exemplifica această metodă de analiză vom face un mic studiu asupra calității vieții în România. Datele se prezintă sub forma unui tabel cu valori ale unor indicatori socio-economici la nivel de județ, tabel ce se găsește în anexa ??.

4.4.1 Prezentarea datelor

Indivizii sunt în număr de 43, reprezentând cele 41 de județe ale țării, municipiul București și media pe toată țara.

Pentru a nu aglomera graficele, vom folosi denumiri prescurtate atât pentru indivzi cât și pentru variabile. Pentru județe folosim prescurtările de la numerele de înmatriculare auto, iar pentru variabile câte o prescurtare specifică.

Avem 18 variabile, grupate natural:

• Variabile demografice :

Gradul de urbanizare a populației – reprezintă procentul din totalul populației care
trăiește în mediul urban; am folosit pentru această variabilă numele prescurtat Urb

Rata de creștere a populației – rata medie de creștere a populației in regiunea res
pectivă, prescurtat Grow

49

Tineri – reprezintă procentul din populație cu vârsta între O si 19 ani inclusiv,
prescurtat Yng

Vârstnici – procentul populației cu vârsta peste 65 ani, prescurtat Old

Fertilitate – rata fertilității; în fapt măsoară numărul de nașteri raportat la 1000 de
femei; prescurtarea folosita este Fert

Inactivi dependenți – numita și rata de dependența demografica, măsoară numărul
de persoane cu vârsta sub 15 ani sau peste 64 de ani raportat la suta de locuitori
ce au vârsta între aceste limite (potențialul forței de muncă active); prescurtarea
folosită în acest caz este Ddr

Variabile ce caracterizează starea economica atât a populației cât și a regiunii respective

Angajați – variabila ce reprezintă numărul de locuitori activi in câmpul muncii
raportat la numărul celor care au vârsta intre 15 si 64 de ani (procent) ; pentru
ușurință se prescurtează Empe

Inactivi – se mai numește și rata de dependență economică; reprezintă numărul de
locuitori inactivi (șomeri sau care nu sunt apți pentru muncă ) la 1000 de locuitori;
prescurtarea este Ecdr

Șomaj – reprezintă procentul celor apți de muncă dar inactivi; prescurtarea folosită
pentru această variabilă este Uepl

LS_primar – procentul locuitorilor care lucrează in sectorul primar al economiei
(procent din totalul celor care lucrează); prescurtat Empl

LS_secundar – procentul celor care lucrează în sectorul secundar al economiei; pre
scurtarea este Emp2

LS_terțiar – procentul lucratorilor din sectorul terțiar al economiei; prescurtat Emp3

Sal mediu – caracterizează salariul mediu al populației din județul respectiv; pre
scurtarea Sal pare să fie cea mai comodă

Taxe și impozite – un indicator foarte bun al stării ecomomiei regionale; reprezintă
venitul pe care statul îl obține din taxare și impozare în județul respectiv; unitatea
de măsură este mii de lei pe cap de locuitor. Se prescurtează Tax

Variabile ce caracterizează educația, cultura și sănătatea

Ch edu – valoarea cheltuielilor cu educația, măsurată în mii de lei pe cap de elev
(școlar la orice nivel). Se prescurtează Edu

Ch sănătate – valoarea cheltuielilor cu sănătatea, măsurată în mii de lei pe cap de
locuitor; prescurtarea folosită este Hexp

50

17. Ch Cult – valoarea cheltuielilor cu cultura, măsurată de asemenea in mii de lei pe
cap de locuitor, prescurtată Cuex

• Variabila care caracterizează rata infracționalității

18. Rata crim – rata criminalității, măsurată în numărul de infractori condamnați prin
sentință definitivă la 100000 de locuitori; prescurtată Crim

Se observă că datele sunt destul de eterogene, deci se va face o analiză normată. O altă remarcă este că datele nu sunt atomice. Analiza se face pe date agregate, fapt ce subliniază necesitatea de a calcula diverse agregări într-un data warehouse.

4.4.2 Rezultatele analizei

Pentru a genera graficele am folosit programul SPAD, versiunea 3.5. Vom prezenta în continuare graficele rezultate prin proiectarea celor doi nori pe planul factorial principal, mai întâi variabilele și apoi indivizii. Suma primelor două valori proprii este un pic mai mare decât jumătate din suma tuturor valorilor proprii, deci analiza nu este foarte precisă.

51

Facteur 2

Facteur 1

Figura 4.2: Reprezentarea grafică a variabilelor în planul factorial principal

Observăm că variabilele se grupează în mod natural (după corelație) în "buchete". Avem pe de o parte variabilele Angajați, Taxe și impozite, LS_tertiar, Sal mediu, LS_se-cundar, Pop urbană, Ch edu, Ch sănătate și Ch cult, care formează un "buchet" ce indică regiunile țării în care calitatea vieții este mai bună, și pe de altă parte "buchetul" format de LS_primar, populația inactivă, Fertilitate, Rata creșterii populației, Șomaj, Tineri, "buchet" care se situează în opoziție cu primul și caracterizează in special zonele rurale, slab dezvoltate și în care calitatea vieții este proastă.

52

05

(J W CC

OD >

d O

< CC

w

OD

i_ 15

00 00

m

0

kO

*

l

g

00

c

fN

g

(Li

-t—• U 05

53

Figura 4.3: Reprezentarea grafică a indivizilor în planul factorial principal

Județele sunt reprezentate prin discuri cu diametrul proporțional cu calitatea reprezentării lor. (Calitatea reprezentării este dată de valorile cosinusului pătrat al unghiului dintre vectorul-individ și planul factorial principal; cu cât un individ este mai aproape de planul factorial, cu atât va fi alterat mai puțin prin proiecție, deci un cosinus mare implică o reprezentare fidelă). Individul mediu este reprezentat printr-un cerc; se observă că el se află aproape de centrul norului de puncte proiecții ale indivizilor. O observație importantă este că nu toți indivizii sunt la fel de bine reprezentați; de fapt, calitatea reprezentării diferă destul de mult de la un individ la altul. Acest lucru era însă de așteptat; informația redundantă din date este puțină; în consecință prin reducerea numărului de variabile se pierde inevitabil o parte din informația utilă. Ipoteza ACP că distanțele dintre indivizi conțin informații despre aceștia se confirmă practic. Se observă gruparea pe grafic a județelor sărace (Vaslui, Suceava, Botoșani) în colțul din stânga-jos, într-o poziție diametral opusă față de individul mediu aflându-se capitala. Se știe că în București nivelul de trai este ceva mai ridicat decât în restul țării, iar graficul de mai sus confirmă acest lucru; Bucureștiul este plasat destul de departe de resul indivizilor. Aproape de București se găsesc județele Brașov, Cluj și Timiș, județe cu economie dezvoltată și cu o calitate a vieții peste medie.

Pentru cine cunoaște starea de fapt din țară, analiza de mai sus nu aduce nimic nou. Privite însă din perspectiva unei persoane care nu știe absolut nimic despre România, datele inițiale nu relevă toate aceste informații. Analiza se dovedește astfel utilă. Din grafice se pot deduce asemănările dintre județe și corelațile dintre diverși indicatori socio-economici.

4.5 Clasificare automată (cluster analises)

Metodele de analiză descrise mai sus realizează o reducere a numărului de variabile. Clasificarea înseamnă reducerea numărului de indivizi prin gruparea acestora în clase. Privind clasele rezultate ca pe niște noi indivizi, se poate aplica apoi ACP, depășind astfel unul din dezavantajele menționate pentru această metodă de analiză.

Clasificarea se va face tot pe baza distanțelor dintre indivizi, întrucât e natural să se grupeze în aceeași clasă indivizi asemănători. Nu se cunoaște însă anterior numărul de clase și având în vedere că numărul total de clasificări posibile este enorm chiar și pentru câteva zeci de indivizi, problema clasificării rămâne o problemă dificilă.

Există două abordări, fiecare cu avantajele și dezavantajele sale:

Metode neierarhice – se face o clasificare cu un număr prestabilit de clase. Deza
vantajul principal este că numărul de clase trebuie cunoscut anterior, iar avantajul
este că algoritmii prelucrează rapid un număr mare de indivizi.

Metode ierarhice – se generează un șir de clasificări din ce în ce mai fine. Evident
că numărul de clase nu trebui dat anterior, dar consumul de resurse de calcul este
mai mare.

Ambele abordări sunt influențate de distanța aleasă pentru spațiul indivizilor. Se folosesc cu succes atât distanța euclidiană cât și distanța dată de matricea M = în funcție de particularitățile problemei putând fi alese și altele.

54

4.5.1 Metode neierarhice

Fiind dat un număr natural fc, se încearcă împărțirea celor n indivizi în k clase cât mai omogene. Omogenitatea înseamnă că într-o clasă indivizii trebuie să fie cât mai asemănători. Din punct de vedere statistic, asta înseamnă că dispersia unei clase trebuie să fie cât mai mică. In termeni de inerție, o clasă este cu atât mai omogenă cu cât inerția norului de puncte-indivizi ce o alcătuiesc este mai mică.

Avem nevoie de un criteriu de optim pe care să-1 aplicăm pentru a găsi clasificarea cea mai bună. Vom extinde noțiunea de inerție de la indivizi și pentru clase, în scopul caracterizării clasificării în totalitatea ei.

Fie gi, #2) • • ••> 9k centrele de greutate ale celor k clase. Notăm cu Ci clasa i și cu pj ponderea individului j. Atunci inerția clasei i este definită de relația

Dacă fiecare clasă are o pondere pj, (în general proporțională cu cardinalul său), atunci

k definim inerția intraclasă Iw = IC Pili- Dacă g este centrul de greutate al întregului

i=l

k nor de indivizi, definim inerția interclase ib = Y, Pid?(di,g)- Notând cu / inerția totală

i=l

(globală) avem proprietatea / = Iw + I b (conform principiului lui Huygens). Cum / este constant în raport cu clasificarea aleasă, avem două criterii de optim echivalente, și anume minimizarea Iw și maxmimizarea /b.

Metoda centrilor mobili

Un algoritm de clasificare propus de Forgy este următorul:

Se aleg aleator k puncte distincte ci, C2, . . . , Ck din spațiul indivizilor. Punctele alese
se vor numi centri. I w * — oo

Se împarte grupul de indivizi în k clase, după următorul criteriu: individul j este
introdus în clasa i dacă distanța de la el la q este cea mai mică dintre distanțele de la
el la punctele ci, C2, . . . , Ck- In caz de egalitate repartizarea se va face aleator. Dacă
una din clasele obținute are cardinalul nul, se generează un nou centru (aleator) și
se reia procedeul.

Se calculează centrele de greutate gi, g2, • • • , 5% ale claselor obținute și inerția I'w.

Dacă numărul de pași depășește o valoare prestabilită sau diferența dintre inerția
obținută la pasul anterior (I'w) și Iw este mai mică decât un e dat, STOP. Altfel,
Iw * — I'w (inerția calculată la pasul 3), q < — gtfi și mergi la pasul 1.

Practica a arătat că algoritmul converge destul de repede și în general clasificările obținute sunt bune. Dezavantajul principal este că centrii inițiali sunt aleși aleator, rezultatul depinzând de această alegere.

55

4.5.2 Metode ierarhice

O ierarhie de clase este o mulțime total ordonată de partiții. Ordinea este naturală, fiecare partiție având clasele formate din reuniuni de clase ale partiției imediat inferioare conform relației de ordine. Astfel, cea mai mică partiție (în sensul relației de ordine a ierarhiei) are atâtea clase câți indivizi sunt în total, fiecare clasă conținând câte un individ. Cea mai mare partiție are o singură clasă care conține toți indivizii. Aceste două pățiții sunt însă inutile din punctul de vedere al analizei și le vom numi partiții triviale.

Cum numărul de clase din partiții scade odată cu creșterea nivelului în ierarhie, putem imagina o reprezentare a ierarhiei sub formă de arbore. Arborele rezultat se va numi arbore ierarhic. Construcția acestui arbore se face plasând pe fiecare nivel câte o partiție, în ordinea descrescătoare dictată de ierarhie. Nodurile arborelui sunt clasele partițiilor. Rădăcina este clasa partiției triviale cu o singură clasă. Fii unui nod sunt clasele care prin reuniune dau clasa din nodul respectiv.

Un exemplu de astfel de arbore este prezentat în figura 4.3.

Pentru a realiza o ierarhie (sau un arbore ierarhic) avem la dispoziție două strategii:

Top-down – se pornește de la clasificarea care asignează toți indivizii inei singure
clase și se încearcă obținerea de noi clasificări din ce în ce mai fine prin divizarea
claselor existente în subclase

Bottom-up – se pornește de la partiția care conține numărul maxim de clase (cu câte
un individ în fiecare clasă) și se obțin noi partiții prin fuziuni ale claselor existente

Prima alternativă are dezavantajul că nu se cunoaște numărul de subclase pentru fiecare împărțire a unei clase în subclase. Nici a doua variantă nu e mult mai bună, dar se pot utiliza tehnici de tip Greedy pentru determinarea unei clasificări mai puțin fine pornind de la o partiție dată. Un astfel de algoritm este metoda lui Ward. Criteriul de optim este gruparea claselor mai asemănătoare, la fel ca și la metodele neierarhice. In termeni de inerție, se va alege combinarea claselor pentru care inerția interclase scade cel mai puțin.

Proprietate (Ward)

Pierderea de inerție interclase prin reunirea claselor A și B este dată de relația:

unde px este ponderea clasei X iar gx centrul de greutate al clasei X. Generalizarea acestei formule poartă numele de Ierna Lance- Williams:

6(C {A B}} = (PA +

pa + P b + pc Pe baza acestei afirmații s-a construit următorul algoritm (Ward):

56

Metoda Ward de ierarhizare automată

1. Se calculează matricea A„ = (fc);1ii „ unde 6^ = p^] d2(ei, e,-)

'* V tJ'i'i3 — l,…ri *j Pi^Pj ^ •> '

In A„ se caută elementul de valoarea minimă, fie (i, j) poziția sa; se elimină linia
și coloana j iar linia și coloana i se renotează ij. Matricea nou formată se notează
A„_i

Coloana i j se calculează după formula Lance-Williams

-. (Pk + Pi)Sik + (P, + Pk)Sjk – PA,,

P, + P3 + Pk

4. Dacă n=l, STOP

Altfel se pune A„ <— A„_i, n = n — l și se merge la pasul 2

Discriminare

O problemă înrudită cu problema clasificării este problema discriminării. Fiind dat un grup de indivizi și o clasificare a sa, trebuie să determinăm în care din clase vom introduce un individ x care nu a participat la clasificare.

Există mai multe soluții pentru această problemă. Se poate determina care din centrele de greutate ale claselor e mai aproape de noul venit pentru ca apoi acesta să fie introdus în clasa cu centrul de greutate respectiv. O altă soluție, poate mai flexibilă, este folosirea unei rețele neuronale antrenată pe indivizii deja clasificați.

In final mai trebuie observat că ierarhia obținută depinde de distanța aleasă. In consecință, această distanță trebuie aleasă cu grijă pentru a obține rezultate utile. In unele cazuri se dovedește folositoare realizarea mai multor clasificări, după mai multe distanțe.

Există și cazuri în care nu avem la dispoziție o distanță veritabilă. Algoritmii vor trebui atunci adaptați pentru distanțe degenerate.

57

Capitolul 5

Concluzii și perspective

5.1 Inteligenta artificială si depozitele de date

Posibilitatea utilizării cu succes a unei rețele neuronale pentru clasificarea indivizilor, menționată în capitolul 4, atrage atenția asupra unui fapt până nu de multă vreme neglijat în practică : inteligența artificială poate să rezolve probleme dificile, crescând gradul de automatizare și extinzând funcționalitatea sistemului. Defectul major al tehnicilor produse de acest domeniu al informaticii este consumul mare de resurse. Explozia performanțelor hardware din ultimii ani (miile de megahertzi ai procesoarelor PC-urilor de azi păreau doar un vis frumos acum 3-4 ani) minimizează însă importanța acestei probleme.

In prezent depozitele de date sunt folosite în principal pentru asistarea personalului uman în luarea deciziilor. Aplicarea masivă a metodelor dezvoltate în cadrul generic numit inteligență artificială ar putea duce într-un viitor nu foarte depărtat la realizarea unor baze de date "inteligente", care să ia singure unele decizii.

Sigur, se poate pune și problema construcției unor sisteme complet independente, care să nu necesite intervenția personalului uman, dar având în vedere complexitatea problemelor pe care ar trebui să le rezolve aceste sisteme, putem considera că vor fi realizabile doar într-un viitor mai îndepărtat, dacă nu chiar niciodată.

In fine, trebuie să remarcăm că multe din încercările de a realiza o inteligență artificială se bazează pe imitarea raționamentelor umane sau a structurii fizice a creierului uman (rețele neuronale). Având în vedere faptul că un om nu poate raționa decât dacă este în posesia unei cantități foarte mare de informație (capacitatea de memorare creierului uman este foarte mare), putem trage concluzia că încercările de imitare a raționamentului uman nu vor avea succes decât dacă baza de cunoștințe va fi foarte mare. Tehnicile de gestionare a informațiilor dezvoltate pentru data warehouse pot fi utile, dacă nu chiar necesare într-o asemenea situație. Cu alte cuvinte, nu numai inteligența artificială își găsește aplicații în domeniul depozitelor de date, ci și reciproc, data warehouse poate avea aplicații în inteligența artificială.

58

5.2 Statistica si depozitele de date

Așa cum am remarcat în secțiunea dedicată analizei în componente principale, tehnicile de data mining prezentate în această lucrare nu sunt suficiente pentru a scoate la lumină toate informațiile utile dintr-o bază de date de mari dimensiuni.

Domeniul data mining este desigur mult mai larg, dar nu rezolvă în totalitate problema găsirii și interpretării datelor "ascunse". In consecință, utilizarea statisticii clasice rămâne o alternativă demnă de luat în considerație.

Peste tot în lume institutele naționale de statistică au zăcăminte de date mari, utilizate de guverne pentru luarea deciziilor economice sau pentru îmbunătățiri legislative. Procesul de trecere la societatea informațională va duce mai devreme sau mai târziu la organizarea acestor date în baze de date de tip data warehouse. Statistica oficială va deveni deci un domeniu în care tehnologia data warehouse va fi indispensabilă.

5.3 încheiere

Am urmărit pe parcursul acestei lucrări construcția și utilizarea unui sistem de tip OLAP, de la adunarea informațiilor din surse externe și până la prelucrarea și interpretarea datelor din el. Tehnologia este însă foarte nouă și se dezvoltă foarte rapid, urmând tendința generală a întregului domeniu IT din ultimii ani.

Explozia dezvoltării internetului în ultimii 5 ani va avea cu siguranță un impact puternic asupra direcțiilor de dezvoltate ale tuturor domeniilor informaticii, deci și asupra data warehouse. Exploatarea uriașelor resurse de informație de pe internet, în mare parte sub formă de text, reprezintă noua provocare la care trebuie să răspundă creatorii sistemelor OLAP. Viteza cu care evoluează tehnologiile informaționale face însă dificilă, dacă nu chiar imposibilă orice anticipare a direcției spre care se va îndrepta tehnologia data warehouse în viitor.

Un singur lucru este cert: într-o formă mai mult sau mai puțin asemănătoare cu cea pe care o știm astăzi, depozitele de date vor rămâne în uz pentru multă vreme.

59