CUBE - Operátor relační agregace

transcript

David Hoksza

Aplikace pro analýzu dat

Formulace dotazu Extrakce dat Vizualizace výsledků Analýza výsledků

Spread Sheet

Size vs Speed

Access Time (seconds)10-9 10-6 10-3 10 0 10 3

Secondary

Nearline Tape Offline

OnlineTape

Price vs Speed

Access Time (seconds)10-9 10-6 10-3 10 0 10 3

MainSecondary

Nearline Tape

OfflineTape

OnlineTape

Size(B) $/MB

Visualize

ExtractAnalyze &Formulate

Modelování n-dimenzionálního problému plochými tabulkami

Čas Šířka Délka Výška Teplota Tlak96/6/1:1500 37:58:33N 122:45:28W 102 21 1009. . . . . .. . . . . .. . . . . .96/6/7:1500 34:16:18N 27:05:55W 10 21 1024

Počasí

Dimenzionální redukce (agregace) ve vizualizačních nástrojích

Histogramy Křížové tabulky Součty, podsoučty, …

Dimenzionální redukce v SQL

Agregační funkce– COUNT()– SUM ()– MIN()– MAX()– AVG()

Operátor GROUP BY

Příklady agregace

SELECT AVG(Tepl) FROM Pocasi;

SELECT COUNT(DISTINCT Cas) FROM Pocasi;

SELECT Cas, Vyska, AVG(Tepl)

FROM Pocasi

GROUP BY Cas, Vyska;

Problémy GROUP BY

Histogramy Roll-up součty, drill-down podsoučty Křížové tabulky

GROUP BY a histogramy

SELECT Den, stat, MAX(Tepl) FROM Pocasi GROUP BY Den(Cas) AS Den,

Stát(Sirka, Delka) AS stat;

SELECT Den, stat, MAX(Tepl)FROM ( SELECT Den(Cas) AS Den,

Stat(Sirka, Delka) AS stat,

Tepl FROM Pocasi ) AS foo

GROUP BY Den, stat;

Řešení roll up

Model Rok Barva

Prodeje by Model by

Rok by Barva

Prodeje by Model by

Prodeje by Model

Chevy 1994 cerna 50

bila 40

1995 cerna 85

bila 115

Roll Up prodejů podle modelu, roku, barvy

není relační

Řešení roll up

Model Rok Barva

Prodeje by Model by

Rok by Barva

Prodeje by Model by

Prodeje by Model

Chevy 1994 cerna 50 90 290

Chevy 1994 bila 40 90 290

Chevy 1995 cerna 85 200 290

Chevy 1995 bila 115 200 290

Roll Up prodejů podle modelu, roku, barvy

2N agregačních sloupců

Řešení roll up – hodnota ALL(1)

Přetížení hodnot sloupce => přidání ALL SELECT Model, ‘ALL’, ‘ALL’, SUM(Prodeje)

FROM Prodeje WHERE

Model = 'Chevy' GROUP BY Model UNION SELECT Model, Rok, ‘ALL’, SUM(Prodeje) FROM Prodeje

WHERE Model = 'Chevy' GROUP BY

Model,Rok UNION SELECT Model, Rok, Barva, SUM(Prodeje)

FROM Prodeje WHERE

Model = 'Chevy'GROUP BY Model, Rok, Barva;

Model Rok Barva Jednotky

Chevy 1994 cerna 50

Chevy 1994 bila 40Chevy 1994 ALL 90Chevy 1995 cerna 85Chevy 1995 bila 115Chevy 1995 ALL 200Chevy ALL ALL 290

Řešení roll up – hodnota ALL(2)

Symetrická agregace:UNION

SELECT Model, ALL, Barva, SUM(Prodeje)

FROM Prodeje

WHERE Model = 'Chevy'

GROUP BY Model, Barva;

Model Rok Barva Jednotky

Chevy ALL cerna 135

Chevy ALL bila 155

Křížové tabulky (1)

cross-tabulation, cross tab

Předchozí jsou relační formou křížové tabulky

Obvyklá reprezentace v reportech

Křížové tabulky (2)

Chevy 1994 1995 total (ALL)

cerna 50 85 135

bila 40 115 155 total (ALL) 90 200 290

Ford 1994 1995 total (ALL)

cerna 50 85 135

bila 10 75 85 total (ALL) 60 160 220

Problémy

Složitý SQL zápis (6D dotaz => 64 UNION) Optimalizace

Dimenze CUBE

REDWHITEBLUE

By Color

By Make & Color

By Make & Year

By Color & Year

By MakeBy Year

The Data Cube and The Sub-Space Aggregates

REDWHITEBLUE

Chevy Ford

By Make

By Color

Cross TabRED

WHITEBLUE

By Color

Group By (with total)Sum

Aggregate

Celkové a dílčí agregace CUBE

CUBE tvoří tabulku se všemi dimenzemi

celková agregace funkcí f():

ALL, ALL, ….., ALL, f(*)

Dílčí agregace (vyšší dimenze)

…, ALL, …ALL, …, f(*)

Příklad (1)

SALES Model Year Color Sales Chevy 1990 red 5 Chevy 1990 white 87 Chevy 1990 blue 62 Chevy 1991 red 54 Chevy 1991 white 95 Chevy 1991 blue 49 Chevy 1992 red 31 Chevy 1992 white 54 Chevy 1992 blue 71 Ford 1990 red 64 Ford 1990 white 62 Ford 1990 blue 63 Ford 1991 red 52 Ford 1991 white 9 Ford 1991 blue 55 Ford 1992 red 27 Ford 1992 white 62 Ford 1992 blue 39

DATA CUBE Model Year Color Sales ALL ALL ALL 942 chevy ALL ALL 510 ford ALL ALL 432 ALL 1990 ALL 343 ALL 1991 ALL 314 ALL 1992 ALL 285 ALL ALL red 165 ALL ALL white 273 ALL ALL blue 339 chevy 1990 ALL 154 chevy 1991 ALL 199 chevy 1992 ALL 157 ford 1990 ALL 189 ford 1991 ALL 116 ford 1992 ALL 128 chevy ALL red 91 chevy ALL white 236 chevy ALL blue 183 ford ALL red 144 ford ALL white 133 ford ALL blue 156 ALL 1990 red 69 ALL 1990 white 149 ALL 1990 blue 125 ALL 1991 red 107 ALL 1991 white 104 ALL 1991 blue 104 ALL 1992 red 59 ALL 1992 white 116 ALL 1992 blue 110

SELECT Model, Rok, Barva, SUM(prodeje) as ProdejeFROM ProdejeWHERE Model in (‘Ford’, ‘Chevy’) AND Rok BETWEEN 1900 AND 1992GROUP BY CUBE Model, Rok, Barva

Příklad (2)

SELECT Den, stat, MAX(Tepl)

FROM Pocasi

GROUP BY CUBE

Den(Cas) AS Den,

Zeme(Sirka, Delka) AS stat;

Sémantika CUBE

Provádění CUBE:– Klasický GROUP BY přes <select list>– Postupná záměna za ALL => superagregáty

Operátor ROLLUP

CUBE může být být moc– Chci pouze roll-up nebo drill-down– Funkční závislosti atributů

=> vznik operátoru ROLLUP Produkuje pouze superagregáty:

(v1 , v2 , …., vn , f()),(v1 , v2 , …., ALL, f()),....(v1 , ALL, …., ALL, f()),(ALL, ALL, …., ALL, f()).

Výhody ROLLUP

Rychlejší Výhodné pro kumulativní agregáty (přirozeně

lineární množina výsledků)

Algebra pro operátory GROUP, CUBE, ROLLUP

CUBE od GROUP BY je CUBE CUBE od ROLLUP je CUBE ROLLUP od GROUP BY je ROLLUP Tedy:

CUBE(ROLLUP) = CUBEROLLUP(GROUP BY) = ROLLUP

Použití:GROUP BY <select list>

ROLLUP <select list>CUBE <select list>

Příklad složení

SELECT Manufacturer, Rok , Mesic, Den, Barva, Model

SUM(cena) AS Vynos

FROM Prodeje

GROUP BY Manufacturer,

ROLLUP Rok(Cas) AS Rok ,

Mesic(Cas) AS Mesic,

Den(Cas) AS Den,

CUBE Barva, Model;

Manufacturer Year, Mo, Day

Syntaxe

Současná:GROUP BY {<column jmeno> [collate clause], …}

Rozšířená:GROUP BY <aggregation list>

<aggregation list> ::=

{(<column jmeno> | <expression>)

[ AS <correlation jmeno> ]

[ <collate clause> ]

Nová:GROUP BY [ <aggregation list> ]

[ ROLLUP <aggregation list> ]

[ CUBE <aggregation list> ]

Diskuse hodnoty ALL

Co je ALL?– Model.ALL = ALL(Model) = {Chevy, Ford}– Model.ALL = ALL(Rok) = {1990, 1991, 1992}– Model.ALL = ALL(Barva) = {red, white, blue} hnízděné relace

ALL reprezentuje množinu

Funkce ALL() vrací množinu, nebo NULL

Zjištění, zda je sloupec agregát

Přidání ALL do SQL

Nové klíčové slovo ALL [NOT] ALLOWED do definice sloupce a

systémového katalogu Interpretace operátorů jako množinových (=) Ostatní prvky domény => singltony

Problémy ALL

Tvoří speciální případy

Nutí pracovat s hodnotami jako s množinami

Lze vynechat

Nahrazení ALL

Místo ALL použít NULL Neimplementovat ALL() Implementovat GROUPING() pro rozlišení

mezi NULL a ALL

Nahrazení ALL - příklad

SELECT Model,Rok,Barva,SUM(prodeje),

GROUPING(Model),

GROUPING(Rok),

GROUPING(Barva)

FROM Prodeje

GROUP BY CUBE Model, Rok, Barva;

Dostaneme:

(NULL, NULL, NULL, 941, TRUE, TRUE, TRUE)

Místo

(ALL, ALL, ALL, 941)

Dekorace

Sloupce, které nejsou v GROUP BY, ale jsou na nich funkčně závislé

SELECT oddeleni.jmeno, sum(prodeje)

FROM prodeje JOIN oddeleni USING (oddeleni_cislo)

GROUP BY prodeje.oddeleni_cislo;

oddeleni.jmeno není v SQL92 povoleno

Dekorace – nový přístup

Je-li dekorace funkčně závislá na agregaci, pak je v SELECT listu povolena

Dekorace interagují s agregačními sloupci:

SELECT Den,stat,MAX(Tepl), kontitnent(stat) AS kontitnentFROM PocasiGROUP BY CUBE Den(Cas) AS Den, Zeme(Sirka, Delka) AS stat

den stat max(Tepl) kontinent

25.1.1995 USA 28 North America

ALL USA 37 North America

25.1.1995 ALL 41 NULLALL ALL 48 NULL

Schémata dimenzí

Ukládáno mnoho informacích o akci => dimenze

Schéma sněhové vločky (snowflake schema) Hvězdicové schéma (star schema)

Snowflake - příklad

Tabulky dimenzí mohou obsahovat i dekorace (např. další informace o kanceláři…)

Dimenze se mohou dále štěpit (např. týdny nezapadají do měsíců)

DivisionGroup

Channel Discount District

Region

Geography

WeekMonth

QuarterYear

Product Seller Buyer Units Price Office Date

Cust Type

Počítání CUBE a ROLLUP

Zobecnění GROUP BY => stejné techniky výpočtu

Počítaní agregátů na co nejnižší systémové úrovni Omezit přesuny dat Používat pole nebo hashování pro reprezentaci

agregačních sloupců v paměti Pro velké agregáty (řetězce) používat hashování

Definice a implementace agregačních funkcí

1. Inicializace agregační funkce 2. Volání agregace pro každou novou hodnotu 3. Získání výsledné hodnoty

Scratchpad

Možnost definovat cenu funkce =>

Prostor pro optimalizátor

2N - algoritmus

Alokování prostoru pro každou buňku kostky Pro každý nový (x1, …, xN, v) Iter(ukazatel, v)

– tzn. 2N krát (xi nebo ALL)

Final(&ukazatel) pro každý z Π(Ci+1) uzlů kostky

Kardinalita základní tabulky T => T*2N volání Iter() Lze zrychlit podle typu agregační funkce

Typy agregačních funkcí

Mějme 2-dimenzionální množinu hodnot {Xij|I=1,…I;j=1,…J}

Typy funkcí:– Distributivní– Algebraické– Holistické

Distributivní funkce

Agregační funkce F() je distributivní, existuje-li funkce G() tž.:F({Xi,j}) = G({F({Xi,j|I=1,…,I}) | j=1,…,J})

Př.: – MIN(), MAX(), SUM() ….. F=G– COUNT() … G=SUM()

Algebraické funkce

Agregační funkce F() je algebraická, existuje-li funkce G() vracející n-tici a funkce H() tž.:F({Xi,j}) = H({G({Xi,j|I=1,…,I}) | j=1,…,J})

Př.: Average(), MaxN(), MinN()

Holistické funkce

Agregační funkce F() je holistická, jestliže neexistuje konstanta omezující velikost subagregátu tj.:Neexistuje konstanta M charakterizující F({Xi,j|I=1,

…,I})

Př.: Median(), MostFrequent()

Počítání super-agregátů holistické funkce

Není znám efektivnější postup než 2N-algoritmus používající standardní techniky GROUP BY

Počítání super-agregátů distributivní funkce

Z N-té dimenze spočítáme (N-1)-tou dimenzi projekcí (agregací) jedné dimenze

Př.:CUBE(ALL,x2,…,xN) = F({CUBE(u,x2,…,xN)})

Distributivnost umožňuje agregaci agregátů

Počítání super-agregátů algebraické funkce

Spíše než subagregáty je nutno si pamatovat n-tice z vyšších dimenzí!

Shrnutí

Operátor CUBE generalizuje a sjednocuje:AgregátyGROUP BYHistogramyRoll-upyKřížové tabulky

CUBE je založen na ALL (označení sloupce přes který se agreguje)

Někdy se vyplatí pouze ROLLUP Jednoduše spočitatelné pro distributivní a algebraické

funkce

CUBE - Operátor relační agregace

Documents