Funzione di aggregazione

Nella gestione dei database, una funzione di aggregazione o funzione aggregata è una funzione in cui i valori di più righe sono sintetizzati in un unico valore sommativo.

Le funzioni di aggregazione comuni includono:

• media aritmetica
• conteggio
• massimo
• minimo
• moda
• campo di variazione
• somma
• Nanmean (ignora i valori NaN, cioè "nil" o "null")
• Stddev (abbreviazione di standard deviation, scarto quadratico medio)

Formalmente, una funzione aggregata prende come input un insieme, un multiinsieme o una lista da qualche dominio di input I e genera un elemento di un dominio di output O. I domini di input e output possono essere gli stessi, come per SUM, o possono essere diversi, come nel caso della funzione COUNT.

Le funzioni di aggregazione si trovano comunemente in numerosi linguaggi di programmazione, nei fogli di calcolo e nell'algebra relazionale.

La funzione listagg, come definita nello standard SQL:2016, aggrega i dati da più righe in una singola stringa concatenata.

Funzioni di aggregazione scomponibili

Le funzioni di aggregazione presentano un collo di botiglia, perché in potenza richiedono di avere tutti i valori di input contemporaneamente. Nel calcolo distribuito, è auspicabile suddividere tali calcoli in parti più piccole e distribuire il lavoro, solitamente calcolando in parallelo tramite un algoritmo divide et impera.

Alcune funzioni di aggregazione possono essere calcolate scomponendo il problema in sottoproblemi più semplici: si calcolano gli agregati dei sottoinsiemi e poi l'aggregto finale: ne sono un esempio le funzioni COUNT, MAX, MIN e SUM. In altri casi, l'aggregato può essere calcolato mediante dei numeri ausiliari relativi ai sottoinsiemi, aggregando questi numeri ausiliari e infine calcolando il numero complessivo alla fine: ad esempio, la funzione AVERAGE tiene traccia delle somme parziali (sottoinsiemi) mediante un numero ausiliario che indica il numero di termini conteggiati, per il quale la somma si divide alla fine; la funzione RANGE tiene traccia dei massimi e minimi calcolati sui sottoinsiemi parziali, per poi calcolare la differenza finale di questi due valori.

In altri casi l'aggregato non può essere calcolato senza analizzare l'intero insieme in un'unica volta, sebbene in alcuni casi si possano distribuire approssimazioni. Gli esempi includono le funzioni DISTINCT COUNT, MEDIAN e MODE.

Tali funzioni sono chiamate funzioni di aggregazione scomponibili o funzioni aggregate scomponibili. Le più semplici possono essere chiamate funzioni di aggregazione auto-scomponibili, che sono definite come quelle funzioni f tali che esiste un operatore di unione $\diamond$ tale che:

$f(X\uplus Y)=f(X)\diamond f(Y)$,

dove $\diamond$ è l'unione di un multiinsieme (omomorfismo monoide).

Ad esempio, per la funzione SUM:

$\operatorname {SUM} ({x})=x$, per un singleton;

$\operatorname {SUM} (X\uplus Y)=\operatorname {SUM} (X)+\operatorname {SUM} (Y)$, significando che l'unione $\diamond$ è semplicemente additiva.

COUNT:

$\operatorname {COUNT} ({x})=1$,

$\operatorname {COUNT} (X\uplus Y)=\operatorname {COUNT} (X)+\operatorname {COUNT} (Y)$.

MAX:

$\operatorname {MAX} ({x})=x$,

$\operatorname {MAX} (X\uplus Y)=\max {\bigl (}\operatorname {MAX} (X),\operatorname {MAX} (Y){\bigr )}$.

MIN:

${\textstyle \operatorname {MIN} ({x})=x}$,

$\operatorname {MIN} (X\uplus Y)=\min {\bigl (}\operatorname {MIN} (X),\operatorname {MIN} (Y){\bigr )}$.

Si noti che le funzioni di aggregazione autoscomponibili possono essere combinate (formalmente, calcolando il prodotto) mentre si applicano separatamente: ad esempio, si possono calcolare sia SUM che e COUNT in simultanea, tracciando due numeri.

Più in generale, si può definire una funzione di aggregazione scomponibile f come quella che può essere espressa come composizione di una funzione finale g e una funzione di aggregazione autoscomponibile h, $f=g\circ h,f(X)=g(h(X))$ (ad esempio: AVERAGE=SUM/COUNT, e RANGE=MAX−MIN).

Nel framework software di MapReduce, questi passaggi sono noti come InitialReduce (valore su record singolo/set singleton), Combine (unione binaria su due aggregazioni) e FinalReduce (funzione finale su valori ausiliari).

Le funzioni di aggregazione scomponibili sono importanti nell'OLAP in quanto consentono di calcolare le query di aggregazione su dei numeri precalcolati nel cubo OLAP anziché sull'intero insieme dei dati di base. Ad esempio, il supporto delle funzioni COUNT, MAX, MIN, e SUM in OLAP risulta agevole poiché questi possono essere calcolati per ogni cella del cubo OLAP e quindi riepilogati; invece, è difficile supportare MEDIAN, poiché deve essere calcolato separatamente per ogni vista sui dati.

Altre funzioni di aggregazione scomponibili

Per calcolare la media e la deviazione standard dai dati aggregati è necessario avere a disposizione per ogni gruppo: il totale dei valori (Σx i = SUM(x)), il numero dei valori (N=COUNT(x)) e il totale dei quadrati dei valori (Σx i 2 =SUM(x 2 )) di ciascun gruppo.

AVG:

$\operatorname {AVG} (X\uplus Y)={\bigl (}\operatorname {AVG} (X)*\operatorname {COUNT} (X)+\operatorname {AVG} (Y)*\operatorname {COUNT} (Y){\bigr )}/{\bigl (}\operatorname {COUNT} (X)+\operatorname {COUNT} (Y){\bigr )}$.

oppure

$\operatorname {AVG} (X\uplus Y)={\bigl (}\operatorname {SUM} (X)+\operatorname {SUM} (Y){\bigr )}/{\bigl (}\operatorname {COUNT} (X)+\operatorname {COUNT} (Y){\bigr )}$.

oppure, solo se COUNT(X)=COUNT(Y)

$\operatorname {AVG} (X\uplus Y)={\bigl (}\operatorname {AVG} (X)+\operatorname {AVG} (Y){\bigr )}/2$.

SUM(x2): La somma dei quadrati dei valori è importante per calcolare la Deviazione Standard dei gruppi:

$\operatorname {SUM} (X^{2}\uplus Y^{2})=\operatorname {SUM} (X^{2})+\operatorname {SUM} (Y^{2})$

STDDEV:
Per una popolazione finita con probabilità uguali in tutti i punti, abbiamo:

$\operatorname {STDDEV} (X)=s(x)={\sqrt {{\frac {1}{N}}\sum _{i=1}^{N}(x_{i}-{\overline {x}})^{2}}}={\sqrt {{\frac {1}{N}}\left(\sum _{i=1}^{N}x_{i}^{2}\right)-({\overline {x}})^{2}}}={\sqrt {\operatorname {SUM} (x^{2})/\operatorname {COUNT} (x)-\operatorname {AVG} (x)^{2}}}$

Ciò significa che la deviazione standard è pari alla radice quadrata della differenza tra la media dei quadrati dei valori e il quadrato del valore medio.

$\operatorname {STDDEV} (X\uplus Y)={\sqrt {\operatorname {SUM} (X^{2}\uplus Y^{2})/\operatorname {COUNT} (X\uplus Y)-\operatorname {AVG} (X\uplus Y)^{2}}}$.

$\operatorname {STDDEV} (X\uplus Y)={\sqrt {{\bigl (}\operatorname {SUM} (X^{2})+\operatorname {SUM} (Y^{2}){\bigr )}/{\bigl (}\operatorname {COUNT} (X)+\operatorname {COUNT} (Y){\bigr )}-{\bigl (}(\operatorname {SUM} (X)+\operatorname {SUM} (Y))/(\operatorname {COUNT} (X)+\operatorname {COUNT} (Y)){\bigr )}^{2}}}$.

Bibliografia

• Yuan Yu, Pradeep Kumar Gunda e Michael Isard, Distributed aggregation for data-parallel computing: interfaces and implementations, ACM SIGOPS 22nd symposium on Operating systems principles, Association for Computing Machinery, 2009, pp. 247–260, DOI:10.1145/1629575.1629600.
• Paulo Jesus, Carlos Baquero e Paulo Sérgio Almeida, A Survey of Distributed Data Aggregation Algorithms, 2011, arXiv:1110.0725.
• Chao Zhang, Symmetric and Asymmetric Aggregate Function in Massively Parallel Computing, su hal.archives-ouvertes.fr, 2017.

Ulteriori letture

• Michel Grabisch, Jean-Luc Marichal, Radko Mesiar e Endre Pap, Aggregation functions, Encyclopedia of Mathematics and its Applications, vol. 127, Cambridge, Cambridge University Press, 2009, ISBN 978-0-521-51926-7, Zbl 1196.00002.
• Oracle Aggregate Functions: MAX, MIN, COUNT, SUM, AVG Examples

Voci correlate

• Tabella di contingenza
• Drill-down
• Data mining
• Elaborazione dati
• Extract, transform, load
• Fold
• Cubo OLAP
• OLAP
• Tabella pivot
• Algebra relazionale

Collegamenti esterni

• Aggregate Functions (Transact-SQL)