2.2
Analisi dettagliata del sistema PIM
In questa sezione vogliamo fare un’analisi approfondita di PIM [18], la me- todologia prima accennata che `e stata usata come base su cui proporre la nostra nuova tecnica. Essa, infatti, a nostro parere, propone idee buone e innovative, ma con alcuni punti miglirabili.
Di seguito, in figura 2.1, mostriamo l’architettura del sistema, utile a capirne il funzionamento spiegato successivamente.
Figura 2.1: PIM - Architettura
Esso accede al workload del DBMS ed estrae, per ogni query, i relativi dati nella forma <SQL expression, execution plan, costs, datetime> che saranno usati per la ricerca automatica degli indici. Fatt`o ci`o li inserisce nel “Local Metabase” (LM), un database interno al sistema e strutturato per i suoi scopi. Dopo aver decomposto il valore di datetime in giorno (1-31) e
mese (1-12) vengono selezionate le query time-expensive. Una query si dice time-expensive se:
1. RTq > t, dove RTq `e il tempo di risposta di q e t `e un parametro
costante (9000s);
2. Fq < k, dove Fq`e il numero di esecuzioni di q diviso per il periodo di
osservazione (in mesi) e k `e un parametro costante (5. q `e eseguita tra una e quattro volte al mese in media);
3. c’`e almeno una struttura di indici i tale per cui Bi,q> ECCi dove ECCi
`e il costo stimato per la creazione della struttura i e Bi,q`e il beneficio
dato dalla presenza della struttura di indici i durante l’esecuzione della query q rispetto all’esecuzione della stessa senza quella struttura. Per ogni teQuery viene trovato l’indice pi`u appropriato e salvato (as esempio, con la tecnica degli “Hypothetical Execution Plan”, dopo aver ottenuto il piano di esecuzione reale da parte del DBMS per la query in questione, lo analizza e cerca le operazioni che non fanno uso di indici per rimpiazzarle con altre equivalenti che, per`o, usano gli stessi.) Fatto ci`o, per ogni teQuery si accede alla storia delle esecuzioni per trovare la distribuzione statistica che meglio la rappresenta. A questo punto viene scelto il modello di predizione pi`u adatto tra regressione lineare, MLP (Multi Layer Perceptron) e RBF (Radial Basis Function). Per ogni modello di predizione vengono valutate diverse istanze caratterizzate da paramentri differenti. Per implementare, istruire e validare le due reti neurali (MLP e RBF) viene usato Weka, mentre per la regressione lineare viene usato un tool Java. Il risultato di questa operazione `e il miglior modello di predizione (con la configurazione associata) per ogni teQuery. Per scegliere la migliore istanza del modello di predizione per ogni query vengono usati il coefficiente di correlazione (compreso tra -1,
2.2. ANALISI DETTAGLIATA DEL SISTEMA PIM 19 negativamente correlati, e +1, positivamente correlati)
r = n
∑
xy− (∑x)(∑y)
√
[n∑x2− (∑x)2][n∑y2− (∑y)2]
e la radice dell’errore quadratico medio (RMSE, Root Mean Square Error) che `e la misura della differenza tra i valori predetti da un modello e i valori effettivamente osservati. Dopo aver trovato il moglior modello per ogni que- ry q, PIM lo usa per prevedere la prossima esecuzione di una determinata query ed inviare una richiesta di creazione degli indici in Iq al DDL Gene-
rator.
L’approccio che proponiamo in questo lavoro riprende gran parte dei concet- ti di PIM: anch’esso vuole essere un tool proattivo che possa implementare gli indici prima che la teQuery venga eseguita, anch’esso calcola le strutture indici pi`u appropriate per le teQuery in questione e le salva per implemen- tarle quando si predice che una delle suddette query stia per essere eseguita. La parte in cui si differenzia sostanzialmente da PIM `e la predizione della prossima esecuzione della teQuery in questione: PIM, come gi`a detto, ana- lizza la distribuzione dei tempi di esecuzione di una determinata teQuery e, attraverso tool esterni, trova la distribuzione statistica che meglio la rap- presenta. A questo punto viene scelto il modello di predizione pi`u adatto tra regressione lineare, MLP (Multi Layer Perceptron) e RBF (Radial Basis Function) che sar`a poi usato per prevedere quando la query sar`a eseguita nuovamente. Facendo ci`o, per`o, si prevede il momento dell’esecuzione di una determinata query basandosi solo sulla storia delle esecuzioni passate della stessa: il nostro approccio, invece, propone di considerare il “contesto” in cui la query si trova, quindi anche l’esecuzione di altre operazioni prima di essa. L’obiettivo `e quello di poter sapere, osservando le operazioni esegui- te sulla base di dati, se e tra quanto una determinata query sar`a eseguita,
in modo da potersi preparare implementando gli indici adatti per una sua migliore esecuzione. Per fare ci`o si `e pensato di applicare tecniche di Data Mining, in modo da poter istruire il tool osservando la storia passata dell’in- tero database e non solo delle occorrenze di una determinata query in modo da renderlo in grado di fare predizioni.
In un primo tempo, l’idea `e stata quella di applicare le regole di associa- zione per prevedere l’esecuzione di una teQuery basandosi sull’esecuzione di altre query. Le regole di associazione [26] sono una tecnica di Data Mining usata per scoprire relazioni di correlazione tra i dati in grandi insiemi di transazioni. Il problema che `e sorto `e che esse guardano ai dati all’interno di una transazione senza distinzione di ordine. Nel nostro dominio applica- tivo, per`o, poich´e deve essere predetta l’esecuzione di una query basandosi sull’esecuzione di altre, l’ordine in cui esse avvengono risulta essere fonda- mentale. Per questo motivo si `e deciso di utilizzare la tecnica del Sequential Pattern Mining (spiegata in modo preciso nel Capitolo 3) che consente di trovare, in un insieme di dati, sequenze ricorrenti che, in quanti tali, tengono in considerazione l’ordine degli elementi che le compongono.
Capitolo 3
Stato dell’arte sul Sequential
Pattern Mining
“Knowledge is what we get when an observer, preferably a scientifically trained observer, provides us with a copy of reality that we can all recognize.”
Christopher Lasch Il Sequential Pattern Mining (SPM) [22] `e una tecnica di Data Mining che permette di estrarre sequenze di elementi che si ripetono “spesso” nell’in- sieme di valori in ingresso. Esso tiene in considerazione l’ordine all’interno della transazione al contrario delle regole di associazione che non lo fanno, poich´e cercano semplicemente nell’insieme degli elementi disponibili. Esso `e utilizzato nella organizzazione d’impresa, nell’area della biologia e nel web mining per analizzare log distribuiti su pi`u server. Nel nostro caso, poich`e il log di operazioni di un database relazionale `e una sequenza temporale, per noi `e importante poter considerare l’ordine di queste ultime in modo da co- noscere cosa `e avvenuto prima dell’esecuzione della query in considerazione. Per questo motivo il SPM risulta essere la tecnica pi`u adatta.
Per chiarire il concetto di “spesso”, intoduciamo la definizione di supporto. Questa pu`o essere espressa in due modi:
• Supporto Relativo: indica il numero minimo di sequenze dei dati in
ingresso in cui deve essere presenta un pattern perch`e possa essere considerato frequente;
• Supporto Assoluto: indica la percentuale minima (compresa tra 0 e 1)
di sequenze dei dati in ingresso in cui deve essere presenta un pattern perch`e possa essere considerato frequente
Numerosi algoritmi sono stati presentati partendo dai pi`u datati che si basavano sulla propriet`a dell’algoritmo Apriori [23].
3.1
Notazione
Una sequenza `e una lista ordinata di eventi < e1e2. . . eI>. Date due sequen-
ze α =< x1x2. . . xn> e β =< y1y2. . . ym>, allora α `e detta sotto-sequenza
di β, ovvero α⊆ β, se esistono degli interi 1 ≤ j1 < j2 < . . . < jn ≤ m tali
che x1 ⊆ yj1, x2 ⊆ yj2, . . . , e xn ⊆ yjn. Se α e β contegono le seguenti se-
quenze α = < (xy), t > e β = < (xyz), (zt) >, allora β `e una super-sequenza di α. SID Sequenza 10 <l(lmn)(ln)o(nq)> 20 <(lo)n(mn)(lp)> 30 <(pq)(lm)(oq)nm> 40 <pr(lq)nmo>
Tabella 3.1: Sequenze di ingresso
Si considerino i dati in Tabella 3.1. Essi sono una piccola parte di un da- tabase di sequenze in cui ogni riga `e composta da un ID (SID `e l’acronimo
3.1. NOTAZIONE 23 di Sequence ID, cio`e ID della sequenza) che `e chiave primaria e da una se- quenza composta da un insieme di elementi. Ogni elemento pu`o contenere un item o un insieme di item (messi tra parentesi tonde). Gli item in un elemento non sono ordinati e sono elencati in ordine alfabetico. Per esem- pio, riferendoci ai dati della Tabella 3.1, <l(mn)on> `e una sottosequenza di <l(lmn)(ln)o(nq)>. Se la soglia di supporto minimo `e pari a 2, allora
<(lm)n> `e un sequential pattern valido. (Esempio da [24]).
In questo contesto possono essere individuate tre categorie di pattern:
• Pattern Periodici: questo modello `e usato per prevedere l’occorrenza
di alcuni eventi nel futuro. Esso, in una sequenza in ingresso come <x y z x y z x y z>, trova il pattern <x y z>. Essendo molto restrittivo viene introdotta la nozione di Pattern Periodico Parizale in cui i pat- tern trovati sono nella forma <x*y> dove * `e un insieme di item di dimensione qualunque.
• Pattern Statisticamente Significativi: vengono usati due indici, sup-
porto e confidenza, per valutare i pattern. Quelli pi`u rari rischiano di andare persi ed esiste il problema di identificare la posizione del- l’occorrenza di un pattern. Per informazioni pi`u dettagliate, numerosi lavori sono stati presentati in [25].
• Pattern Aprrossimati: i due approcci precedenti tengono in conside-
razione soltanto la corrispondenza perfetta dei pattern, mentre qui si considera un pattern approssimato che `e una sequenza di simboli le cui occorrenze in una sequenza appaiono con un valore maggiore di una determinata soglia.
Risulta utile, inoltre, definire una distinzione tra due tipologie di log su cui gli algoritmi possono essere applicati:
• Log Statici: l’algortimo usa come ingresso un insieme di dati e, alla
successiva esecuzione, usa dati completamente nuovi, dimenticandosi di quelli gi`a usati.
• Log Dinamici: l’algortimo usa come ingresso un insieme di dati e, alla
successiva esecuzione, usa lo stesso insieme della precedente esecuzione a cui aggiunge i nuovi dati.
Il problema di trovare pattern frequenti, quindi, corrisponde ad avere a di- sposizione uno stream di dati ed essere in grado di individuare delle sottose- quenze di lunghezza finita che ricorrono nello stream in maniera frequente, ovvero il cui supporto supera una soglia predefinita chiamata “supporto minimo”.