Pattern Matching

In analiza datelor este importantă recunoaşterea unor "şabloane" în succesiunea de înregistrări furnizate de o instrucţiune select. Astfel de facilităţi se regăsesc în instrucţiunea select din Oracle 12c prin clauza MATCH_RECOGNIZE.

Exemple de şabloane:

valoarea unei expresii numerice (de exemplu preţul unui produs) are o evoluţie de tip "V" (dacă se reprezintă grafic, pentru o succesiune de zile, există o succesiune descrescătoare de valori, urmată de o succesiune crescătoare de valori))
valoarea unei expresii numerice are o evoluţie de tip W
perioada în care valoarea unei expresii numerice are o evoluţie descrescătoare într-un interval de cel puţin 15 zile
să se determine dacă un telefon A a apelat un telefon B, urmat de un apel de la B la C, urmat de un apel de la C la A, toate aceste apeluri să fie făcute într-un interval de maximum 10 minute
să se determine dacă dintr-un anumit cont într-un interval de 5 minute s-a extras o sumă mică, după care se face extragerea unei sume mari
se cer date despre conturile din care s-au făcut extrageri din cel puţin trei ţări diferite într-un interval de maximum 10 ore

Clauza MATCH_RECOGNIZE se foloseşte astfel:

select ... 
FROM sursa_date MATCH_RECOGNIZE (
   [PARTITION BY coloana[, coloana]...]
   [ORDER BY coloana[, coloana]...]
   [MEASURES expresie AS alias[, expresie AS alias]...]
   [{ONE ROW PER MATCH | ALL ROWS PER MATCH}]
   [AFTER MATCH {SKIP TO NEXT ROW | SKIP PAST LAST ROW | 
                 SKIP TO FIRST variabila | SKIP TO LAST variabila | 
                 SKIP TO variabila}]
   PATTERN (sablon) 
   [SUBSET variabila = (variabila[ , variabila]...) 
           [, variabila = (variabila[ , variabila]...)] ...
   DEFINE variabila AS conditie [, variabila AS conditie] ...
   ) alias
...

Explicaţii:

prin sursa_date MATCH_RECOGNIZE (...) se precizează o mulţime de date, care sunt din sursa de date, la care se adaugă date noi construite în clauza MATCH_RECOGNIZE
clauza PARTITION BY precizează o partiţie a înregistrărilor din sursa de date. Fără această clauză, toată sursa formează o partiţie. Sabloanele care se definesc sunt căutate într-o partiţie.
înregistrările dintr-o partiţie sunt ordonate cu clauza ORDER BY
clauza DEFINE defineşte o listă de variabile utile la definirea şablonului şi la extragerea de date. O variabilă are un nume şi o condiţie de definire şi va face "referire" la înregistrările (din sursa de date) care verifică această condiţie asociată. La precizarea condiţiei se pot folosi:
- expresii cu coloane din înregistrările sursei de date. Denumirea unei coloane din înregistrările ce verifică definiţia unei variabile se poate califica prin numele variabilei.
- funcţiile: PREV, NEXT, FIRST, LAST - care precizează precedenta, următoarea, prima, ultima înregistrare din partiţie care verifică şi condiţia din variabila folosită ca argument. Funcţiile pot avea un al doilea argument nenul, care precizează o deplasare faţă de înregistrarea curentă (deplasarea cu valoarea 1 este valoarea implicită).
  Exemplu:
```
DEFINE A AS A.PRET < PREV(A.PRET), B AS B.PRET > PREV(B.PRET), C AS PRET = 100
```
  A va face referire la înregistrările unde preţul scade (faţă de înregistrarea precedentă), B face referire la înregistrările la care preţul creşte, iar cu variabila C se face referire la înregistrările unde preţul este o valoare concretă.
- la definirea unei variabile se poate folosi altă variabilă.
  Exemplu:
```
DEFINE A AS PRET > 100, B AS B.PRET > A.PRET
```
  A face referire la înregistrările cu preţul mai mare decât 100.
  B foloseşte preţul dintr-o linie curentă. Condiţia de la definirea lui B foloseşte valoarea A.PRET, unde A precizează ultima înregistrare asociată la A.
- în condiţia de definire a unei variabile se pot folosi şi funcţii de agregare.
  Exemplu:
```
DEFINE A AS PRET > 100, B AS B.PRET > AVG(A.PRET)
```
  La definirea variabilei B se foloseşte valoarea medie a unor valori pentru toate înregistrările referite de variabila A.
clauza SUBSET defineşte variabile care fac referire la înregistrările precizate de variabilele din listă (reuniune de înregistrări)
clauza PATTERN defineşte, sub forma unei expresii regulare, un şablon care se verifică de o succesiune de înregistrări. In şablon se pot folosi variabile definite în clauza DEFINE (precizează înregistrări ce verifică definiţia) şi variabile fără definiţie asociată (corespund la o înregistrare oarecare din sursa de date). In clauza PATTERN pot apare construcţiile:
- concatenare de şabloane: succesiunea de înregistrări verifică succesiunea de şabloane.
  Pentru PATTERN(A B) se caută o înregistrare care verifică şablonul (condiţia) definită de A, urmată de o înregistrare care verifică şablonul (condiţia) definită de B.
- un şablon urmat de o construcţie cere precizează un anumit număr de repetări ale şablonului:
  - * - zero sau mai multe repetări
  - + - una sau mai multe repetări
  - ? - zero sau una repetări
  - {m} - m repetări, (n>0)
  - {m,} - m sau mai multe repetări
  - {m,n} - între m şi n repetări (0 <= n <= m, 0 < m)
  - {,n} - între 0 şi n repetări (m>0)
- şabloane alternative: apare caracterul "|" între şabloane
- gruparea unei succesiuni de şabloane: includerea acestora între "(" şi ")"
- PERMUTE (sablon [, sablon] ...): se verifică o permutare a şabloanelor din listă
- excluderea unui şablon (succesiunea de înregistrări nu verifică un şablon) se precizează prin includerea acestuia între "{-" şi "-}"
- caracterul "^" precizează poziţia din faţa primei înregistrări, iar "$" precizează poziţia de după ultima înregistrare
pentru succesiunea de înregistrări care verifică şablonul se pot genera unele date. Această generare se face pentru întreaga succesiune de înregistrări care verifică şablonul (ONE ROW PER MATCH), sau pentru fiecare înregistrare din succesiune (ALL ROWS PER MATCH)
clauza MEASURES precizează datele care se generează. La crearea acestor date se pot folosi următoarele construcţii:
- coloanele din sursa de date - dacă apare clauza ALL ROWS PER MATCH
- funcţia MATCH_NUMBER() precizează numărul grupului de înregistrări care verifică şablonul (aceste grupuri se indexează începând cu 1)
- funcţia CLASSIFIER precizează:
  - dacă apare ONE ROW PER MATCH: numele variabilei pentru care ultima înregistrarea este inclusă în şablon
  - dacă apare ALL ROWS PER MATCH: numele variabilei pentru care înregistrarea curentă este inclusă în şablon
- o coloană calificată de un nume de variabilă (de exemplu A.PRET):
  - dacă apare ONE ROW PER MATCH: valoarea din ultima înregistrare care este inclusă în şablon
  - dacă apare ALL ROWS PER MATCH: valoarea din înregistrarea curentă
  - dacă apare în funcţiile de agregare şi ONE ROW PER MATCH: determinarea valorii funcţiei de agregare pentru o mulţime de valori (luând toate înregistrările care verifică şablonul)
  - dacă apare în funcţiile de agregare şi ALL ROWS PER MATCH:
    - atunci când se ajunge la linia curentă se pot lua înregistrările parcurse şi funcţia de agregare să se calculeze pentru aceste înregistrări - atunci în faţa funcţiei de agregare apare RUNNING
    - atunci când se ajunge la linia curentă se pot lua toate înregistrările incluse în grup şi funcţia de agregare să se calculeze pentru toate aceste înregistrări - atunci în faţa funcţiei de agregare apare FINAL
  - funcţiile PREV, NEXT, FIRST, LAST
clauza AFTER MATCH determină poziţia din care se reia căutarea unei noi potriviri a şablonului. Valorile posibile sunt:
- SKIP TO NEXT ROW: următoarea înregistrare după prima înregistrare din grupul ce verifică şablonul
- SKIP PAST LAST ROW, valoarea implicită: următoarea înregistrare după ultima înregistrare din grupul ce verifică şablonul
- SKIP TO FIRST variabila: prima înregistrare din grupul ce verifică şablonul care este asociată variabilei precizată
- SKIP TO LAST variabila: ultima înregistrare din grupul ce verifică şablonul care este asociată variabilei precizată
- SKIP TO variabila: la fel ca SKIP TO LAST variabila

Exemple: Considerăm tabelele care memorează ratele de schimb medii zilnice şi lunare pentru euro, definite astfel:

CREATE TABLE cursz (
zi number(2), luna number(2), an number(4), valoare number(6,4), moneda char(3)
);

CREATE TABLE cursl (
luna number(2), an number(4), valoare number(6,4), moneda char(3)
);

Datele se pot prelua de la adresa: Bază de date interactivă, iar instrucţiunile insert se află la adresele cursz.txt, cursl.txt.

Probleme:

Succesiunea de trei sau mai multe luni de scădere a ratei de schimb lunare euro/lei

with curse as (select luna,an,valoare from cursl where moneda='eur')
SELECT *
FROM curse MATCH_RECOGNIZE (
     ORDER BY an,luna
     MEASURES strt.an as start_an, strt.luna as start_luna,
              strt.valoare as euro_inc,LAST(scade.valoare) as euro_sf,
              count(*) as nr_luni,
              strt.valoare-LAST(scade.valoare) as dif
     ONE ROW PER MATCH
     PATTERN (strt scade{3,})
     DEFINE
        scade AS scade.valoare < PREV(scade.valoare)
     ) a
ORDER BY a.start_an,a.start_luna;

Sablonul care se verifică este format dintr-o înregistrare curentă urmată de cel puţin trei înregistrări ce verifică definiţia variabilei scade.
Se extrag date pentru grupul de înregistrări ce verifică şablonul.
Datele obţinute:

  START_AN START_LUNA   EURO_INC    EURO_SF    NR_LUNI        DIF
---------- ---------- ---------- ---------- ---------- ----------
      2005          1     3.8178     3.5057          8     0.3121 
      2005         12     3.6589     3.4911          5     0.1678 
      2006          7     3.5723     3.1337         13     0.4386 
      2008          5     3.6594     3.5268          4     0.1326 
      2009          2     4.2839     4.1689          4      0.115 
      2009         11     4.2881     4.0879          5     0.2002 
      2010         11     4.2931     4.0992          6     0.1939 
      2012         10     4.5583     4.3793          4      0.179 
      2014          3     4.4931     4.3951          4      0.098

Problema precedentă pentru toate monedele cu date în tabelul cursl:

SELECT *
FROM cursl MATCH_RECOGNIZE (
     PARTITION BY moneda
     ORDER BY an,luna
     MEASURES strt.an as start_an, strt.luna as start_luna,
              strt.valoare as valoare_inc,LAST(scade.valoare) as valoare_sf,
              count(*) as nr_luni,
              strt.valoare-LAST(scade.valoare) as dif
     ONE ROW PER MATCH
     PATTERN (strt scade{3,})
     DEFINE
        scade AS scade.valoare < PREV(scade.valoare)
     ) a
ORDER BY moneda, a.start_an,a.start_luna;

Determinarea şabloanelor de tip V, unde fiecare perioadă (de scădere sau creştere) are cel puţin trei luni
Sabloane posibile (din SQL for Pattern Matching):

SELECT *
FROM cursl MATCH_RECOGNIZE (
     PARTITION BY moneda
     ORDER BY an,luna
     MEASURES strt.an as start_an, strt.luna as start_luna,
              LAST(scade.an) as an_min,LAST(scade.luna) as luna_min,
              count(scade.*)+1 as nr_scade,
              LAST(creste.an) as an_sf,LAST(creste.luna) as luna_sf,
              count(creste.*) as nr_creste,
              count(*) as nr_luni
     ONE ROW PER MATCH
     AFTER MATCH SKIP TO LAST creste
     PATTERN (strt scade{3,} creste{3,})
     DEFINE
        scade AS scade.valoare < PREV(scade.valoare),
        creste AS creste.valoare > PREV(creste.valoare)
     ) a
ORDER BY moneda,a.start_an,a.start_luna;

Datele care se obţin:

MONEDA   START_AN START_LUNA     AN_MIN   LUNA_MIN   NR_SCADE      AN_SF    LUNA_SF  NR_CRESTE    NR_LUNI
------ ---------- ---------- ---------- ---------- ---------- ---------- ---------- ---------- ----------
eur          2005          1       2005          8          8       2005         12          4         12 
eur          2005         12       2006          4          5       2006          7          3          8 
eur          2006          7       2007          7         13       2008          1          6         19
eur          2008          5       2008          8          4       2009          2          6         10 
eur          2009          2       2009          5          4       2009         11          6         10 
eur          2009         11       2010          3          5       2010          7          4          9 
eur          2010         11       2011          4          6       2011         11          7         13 
usd          2009          2       2009         11         10       2010          6          7         17 
usd          2010         12       2011          4          5       2011          7          3          8 
usd          2014          1       2014          5          5       2015          2          9         14

Determinarea şabloanelor de tip V, unde fiecare perioadă (de scădere sau creştere) are cel puţin 5 luni, iar datele se generează pentru fiecare înregistrare

SELECT moneda,an,luna,num_grup,var_sablon,
       nr_zi_scade,nr_zi_creste,nr_luni_grup,valoare,dif_in_grup
FROM cursl MATCH_RECOGNIZE (
     PARTITION BY  moneda
     ORDER BY an,luna
     MEASURES MATCH_NUMBER() AS num_grup,
              CLASSIFIER() AS var_sablon,
              RUNNING count(scade.*)+1 as nr_zi_scade,
              count(creste.*) as nr_zi_creste,
              FINAL count(*) as nr_luni_grup,
              valoare - strt.valoare AS dif_in_grup
     ALL ROWS PER MATCH
     PATTERN (strt scade{5,} creste{5,})
     DEFINE
        scade AS scade.valoare < PREV(scade.valoare),
        creste AS creste.valoare > PREV(creste.valoare)
     ) a
ORDER BY moneda,an,luna;

Datele care se obţin:

MONEDA         AN       LUNA   NUM_GRUP VAR_SABLON NR_ZI_SCADE NR_ZI_CRESTE NR_LUNI_GRUP    VALOARE DIF_IN_GRUP
------ ---------- ---------- ---------- ---------- ----------- ------------ ------------ ---------- -----------
eur          2006          7          1 STRT                1            0           19     3.5723           0 
eur          2006          8          1 SCADE               2            0           19     3.5277     -0.0446 
eur          2006          9          1 SCADE               3            0           19      3.527     -0.0453 
eur          2006         10          1 SCADE               4            0           19     3.5192     -0.0531 
eur          2006         11          1 SCADE               5            0           19     3.4954     -0.0769 
eur          2006         12          1 SCADE               6            0           19     3.4141     -0.1582 
eur          2007          1          1 SCADE               7            0           19     3.3937     -0.1786 
eur          2007          2          1 SCADE               8            0           19     3.3824     -0.1899 
eur          2007          3          1 SCADE               9            0           19     3.3694     -0.2029 
eur          2007          4          1 SCADE              10            0           19     3.3349     -0.2374 
eur          2007          5          1 SCADE              11            0           19      3.285     -0.2873 
eur          2007          6          1 SCADE              12            0           19     3.2264     -0.3459 
eur          2007          7          1 SCADE              13            0           19     3.1337     -0.4386 
eur          2007          8          1 CRESTE             13            1           19     3.2237     -0.3486 
eur          2007          9          1 CRESTE             13            2           19     3.3466     -0.2257 
eur          2007         10          1 CRESTE             13            3           19     3.3525     -0.2198 
eur          2007         11          1 CRESTE             13            4           19     3.4707     -0.1016 
eur          2007         12          1 CRESTE             13            5           19     3.5289     -0.0434 
eur          2008          1          1 CRESTE             13            6           19      3.693      0.1207 
eur          2010         11          2 STRT                1            0           13     4.2931           0 
eur          2010         12          2 SCADE               2            0           13     4.2925     -0.0006 
eur          2011          1          2 SCADE               3            0           13     4.2622     -0.0309 
eur          2011          2          2 SCADE               4            0           13     4.2472     -0.0459 
eur          2011          3          2 SCADE               5            0           13     4.1646     -0.1285 
eur          2011          4          2 SCADE               6            0           13     4.0992     -0.1939 
eur          2011          5          2 CRESTE              6            1           13      4.112     -0.1811 
eur          2011          6          2 CRESTE              6            2           13     4.1929     -0.1002 
eur          2011          7          2 CRESTE              6            3           13     4.2405     -0.0526 
eur          2011          8          2 CRESTE              6            4           13     4.2501      -0.043 
eur          2011          9          2 CRESTE              6            5           13      4.282     -0.0111 
eur          2011         10          2 CRESTE              6            6           13     4.3238      0.0307 
eur          2011         11          2 CRESTE              6            7           13     4.3536      0.0605 
usd          2009          2          1 STRT                1            0           17      3.348           0 
usd          2009          3          1 SCADE               2            0           17     3.2851     -0.0629 
usd          2009          4          1 SCADE               3            0           17     3.1777     -0.1703 
usd          2009          5          1 SCADE               4            0           17     3.0554     -0.2926 
usd          2009          6          1 SCADE               5            0           17     3.0035     -0.3445 
usd          2009          7          1 SCADE               6            0           17      2.994      -0.354 
usd          2009          8          1 SCADE               7            0           17     2.9576     -0.3904 
usd          2009          9          1 SCADE               8            0           17      2.911      -0.437 
usd          2009         10          1 SCADE               9            0           17     2.8904     -0.4576 
usd          2009         11          1 SCADE              10            0           17     2.8741     -0.4739 
usd          2009         12          1 CRESTE             10            1           17     2.8952     -0.4528 
usd          2010          1          1 CRESTE             10            2           17     2.8998     -0.4482 
usd          2010          2          1 CRESTE             10            3           17     3.0071     -0.3409 
usd          2010          3          1 CRESTE             10            4           17     3.0113     -0.3367 
usd          2010          4          1 CRESTE             10            5           17     3.0758     -0.2722 
usd          2010          5          1 CRESTE             10            6           17     3.3207     -0.0273 
usd          2010          6          1 CRESTE             10            7           17       3.47       0.122

Determinarea şabloanelor de tip W, unde fiecare perioadă (de scădere sau creştere) are cel puţin 3 luni, iar datele se generează pentru fiecare înregistrare

SELECT moneda,an,luna,num_grup,var_sablon,
       nr_zi_scade,nr_zi_creste,nr_luni_grup,valoare,dif_in_grup
FROM cursl MATCH_RECOGNIZE (
     PARTITION BY  moneda
     ORDER BY an,luna
     MEASURES MATCH_NUMBER() AS num_grup,
              CLASSIFIER() AS var_sablon,
              RUNNING count(scade.*)+1 as nr_zi_scade,
              count(creste.*) as nr_zi_creste,
              FINAL count(*) as nr_luni_grup,
              valoare - strt.valoare AS dif_in_grup
     ALL ROWS PER MATCH
     AFTER MATCH SKIP TO LAST creste
     PATTERN (strt scade{3,} creste{3,} scade{3,} creste{3,})
     DEFINE
        scade AS scade.valoare < PREV(scade.valoare),
        creste AS creste.valoare > PREV(creste.valoare)
     ) a
ORDER BY moneda,an,luna;

S-a marcat partea din instrucţiune care se modifică faţă de interogarea precedentă.

Se cer perioadele în care valoarea ratei schimbă valorile de 3.5, sau 4, sau 4.5

SELECT moneda,an,luna,valoare,num_grup,var_sablon
FROM cursl MATCH_RECOGNIZE (
     PARTITION BY moneda
     ORDER BY an,luna
     MEASURES MATCH_NUMBER() AS num_grup,
              CLASSIFIER() AS var_sablon
     ALL ROWS PER MATCH
     AFTER MATCH SKIP TO NEXT ROW
     PATTERN (PERMUTE(sub3_5, peste3_5) | PERMUTE(sub4, peste4) | PERMUTE(sub4_5, peste4_5))
     DEFINE
        sub3_5   AS sub3_5.valoare < 3.5,
        peste3_5 AS peste3_5.valoare > 3.5,
        sub4     AS sub4.valoare < 4,
        peste4   AS peste4.valoare > 4,
        sub4_5   AS sub4_5.valoare < 4.5,
        peste4_5 AS peste4_5.valoare > 4.5
     ) a
ORDER BY moneda,an,luna;

Datele care se obţin sunt:

MONEDA         AN       LUNA    VALOARE   NUM_GRUP VAR_SABLON                   
------ ---------- ---------- ---------- ---------- ------------------------------
eur          2006          3     3.5074          1 PESTE3_5                       
eur          2006          4     3.4911          1 SUB3_5                         
eur          2006          4     3.4911          2 SUB3_5                         
eur          2006          5     3.5071          2 PESTE3_5                       
eur          2006         10     3.5192          3 PESTE3_5                       
eur          2006         11     3.4954          3 SUB3_5                         
eur          2007         11     3.4707          4 SUB3_5                         
eur          2007         12     3.5289          4 PESTE3_5                       
eur          2008         12     3.9153          5 SUB4                           
eur          2009          1     4.2327          5 PESTE4                         
eur          2012          6     4.4603          6 SUB4_5                         
eur          2012          7     4.5484          6 PESTE4_5                       
eur          2012         11     4.5255          7 PESTE4_5                       
eur          2012         12     4.4895          7 SUB4_5                         
eur          2013         12     4.4633          8 SUB4_5                         
eur          2014          1     4.5219          8 PESTE4_5                       
eur          2014          1     4.5219          9 PESTE4_5                       
eur          2014          2     4.4906          9 SUB4_5                         
usd          2012          5     3.4703          1 SUB3_5                         
usd          2012          6      3.557          1 PESTE3_5                       
usd          2012         11     3.5289          2 PESTE3_5                       
usd          2012         12      3.424          2 SUB3_5                         
usd          2014         10     3.4835          3 SUB3_5                         
usd          2014         11     3.5507          3 PESTE3_5

Bibliografie: