Obr č.1 Datový sklad
Datový sklad
Datový sklad je systém, který udržuje a vyhodnocuje objemná data (100GB a více). Používá se tam, kde se provádí analýza velkého množství dat (včetně dat historických) z více pohledů a z různých měřítek (granularit). Vznikl jako nástroj pro zpracovávání "obchodních" dat. Umožňuje dimenzionálně modelovat tato data.
Dimenzionální model těchto dat si lze představit jako body v třírozměrném prostoru, jehož osy (dimenze) jsou: čas, geografická lokace a produkt. Dimenze je možné sledovat z různých pohledů (granularit). Např. čas: rok, měsíc, týden, čtvrtletí, den....
Dimenzionální model si lze představit jako kostku s třemi osami: každý bod (prvek) kostky obsahuje reálné číslo vyjadřující obrat dosažený v odpovídajícím obchodě (osa lokace) v odpovídajícím čase (osa časová) za určitý sortiment (osa produkt). Toto číslo bývá nazýváno fakt.
Dimenzionální model je názornější z hlediska relací dat, než model relační (relační tabulky a vztahy mezi nimi), kde si musí uživatel pamatovat vazby mezi tabulkami.
Oba modely (dimenzionální i relační) jsou schopné ukládat přesně stejná data a jsou schopné podporovat přesně stejné analýzy. Ale stejná data reprezentují rozdílně.
Na rozdíl od OLTP systémů (On Line Transaction Processing), do kterých se často zapisuje, jsou data v datových skladech pro uživatele přístupná pouze pro čtení. Zapisovat je smí pouze aktualizační systém, který data v nějakých časových intervalech aktualizuje. Nepřepisuje data, ale vytváří další tabulky. Datový sklad tedy uchovává historii dat. V datových skladech jsou data uložena v relačních nebo multidimenzionálních strukturách. Data jsou do datových skladů transformována z různých interních i externích datových zdrojů, např. z existujících OLTP systémů. Při transformaci je ošetřována duplicita a konzistence dat. Data jsou využívána k analýze z různých, hlavně globálních pohledů, z historie dat. Pro analýzu je tedy zajímavý jejich časový horizont, úhel pohledu a měřítko (granularita).
Datový sklad umožňuje se v granularitách nezávisle pohybovat a dotazovat. Odpovědi dostane rychle z předdefinovaných tabulek, které připraví OLAP (viz. obr.1). V datovém skladu je zajištěna konzistence používaných dat, protože do něj nikdo nemůže zapisovat. Předpřipravování tabulek OLAPem znázorňuje Star schéma (obr. 2).
Obr č.2 Star schéma
Data v tabulkách jsou uložena úsporně, zbytečné detaily jsou odstraněny agregací dat - průměrování, sumarizace, maximální hodnota apod. Agregace se provádí pro dané dimenze a granularity (pro každý měsíc, pro každý okres...). Při vyhodnocování dotazu pak datový sklad má většinu potřebných údajů předem připravenou a vyhodnocení se tím výrazně urychlí.
2.2. Prostorová indexace
Obecně lze označit prostorové dotazy za velice výpočetně složité a jejich vyhodnocení za časově náročné. Některé podpůrné mechanismy, typicky založené na prostorové indexaci, umožňují urychlovat vyhodnocení prostorových dotazů. Mezi indexační techniky často používané v komerčních systémech patří např.:
- čtyřstromy (quad-trees) vyžívané firmou Oracle v rozšiřujícím modulu Spatial Cartriadge,
- R-stromy (R- trees) implementované firmou Informix (dnes IBM) do rozšiřujícího modulu Spatial DataBlade.
První prototyp systému GOLAP používá R- stromy, proto jí nyní budeme věnovat detailněji.
R stromy a jejich varianty jsou prostorové datové struktury umožňující indexaci obecnějších objektů než jenom samostatných bodu. V principu, R stromy a jejich podobné modifikace R+stromy jsou stromy, jejichž listy obsahují ukazatele na datové objekty reprezentující prostorové objekty. Důležité je to, že uzly R stromu jsou implementovány jako stránky v externí paměti.
Samotná indexace prostorových objektu je dána jako dvojice <I,Id> (také nazývaná index records), kde I je minimální ohraničující hyperkostka (MBH) konkrétního prostorového objektu. Každá MBH je dána n-ticemi (I0, I1, ..., In), kde Ii je interval [ai, bi] udávající dolní a horní hranici v dimenzi i.
Nelistové uzly obsahuji záznamy (I, ukazatel). Ukazatel se odkazuje na takový podstrom, který obsahuje uzly odpovídající všem MBH pokrývajícím MBH I. R strom je dán dvojicí (m, m1), kde m je minimální počet hran vycházejících z uzlu, m1 je maximální počet těchto hran. Tedy MBH se konstruuje tak, že počet hran vedoucích z odpovídajícího uzlu je alespoň m1 a nejvýše m. MBH se mohou překrývat. Obr.3 ukazuje konstrukci R stromu (2,3). Jestliže počet prostorových objektu je E, hloubka m-árního R stromu je v nejhorším případě [logmE] -1. R stromy jsou dynamické datové struktury založené na stránkovém štěpení (v případě operace vkládání) a na stránkovém slučování (v případě operace mazání). Na rozdíl od B stromu není vyhledávání v R stromech sledováním jedné cesty, protože MBH se mohou překrývat. To znamená, ze může existovat několik možností, jak se dostat k uzlu hledaného objektu.
Pro optimalizaci R stromu lze používat mnoho heuristik. Základní tendencí je co nejvíc oddělit MBH.
Pro správu R stromu je velmi důležitá operace vkládání (INSERT), která ovlivňuje efektivnost stromu. Základní strategie vkládání je najít takový listový uzel, pro který vkládáním a indexováním záznamu bude vyvoláno minimum uzlů na cestě z listu do kořene stromu vyžadujících update. Efektivnost R stromu velmi ovlivňují metody spojování uzlů.
Procedura spojování řeší problém jak dělit neuspořádanou množinu index záznamů. Podstatné je minimalizovat pravděpodobnost, že oba uzly bude potřeba vyhodnocovat během vyhledávání. Proto by objem všech MBH odpovídajících dvěma uzlům po spojení měl být minimální. Složitost algoritmu s celkem optimálními výsledky je exponenciální. Prakticky je použitelný suboptimální algoritmus s lineární nebo kvadratickou složitostí.
Obr č.3 Konstrukce R stromu
3. Architektura systému GOLAP
Systém GOLAP obsahuje dvě části: indexátor prostoru a vyhodnocovač dotazů. Indexátor sestavuje R stromy s uloženými geografickými objekty. Listy stromu korespondují s jednotlivými geografickými objekty, nelistové stromy s odpovídajícími MBH. Indexátor využívá ETL proces a při tvorbě (aktualizaci) datového skladu doplňuje prostorový index jako novou dimenzi datového skladu.
Vyhodnocovač je uživatelské rozhranní umožňující vybírat analyzovanou plochu. Vybere množinu MBH a jednotlivé objekty pokrývající vybranou plochu. Pak zkonstruuje odpovídající dotaz pro OLAP a pošle ho systému OLAP.
4. Výsledky experimentů
Byly provedeny první serie experimentů. Výsledky porovnávání konvenčního OLAPu a GOLAPu potvrdily očekávání. Byly prováděny na počítači 2xPIII 866MHz, 256MB RAM s MS Windows 2000 a MS SQL Server 2000 s Analytical Services. Byly náhodně generovány dvě množiny geografických dat. V obou bylo 100000 objektů rodělených v síti (rastru) 10000x10000 bodů. Jedna z množin byla generována s rovnoměrným geografickým rozdělením a druhá s dvourozměrným normálním (Gaussovým) rozdělením.
Obr č.4 Rovnoměrné rozdělení GIS objektů
Druhým způsobem bylo simulováno realističtější rozdělení objektů v systému GIS. Generování dat začalo náhodným výběrem 100 center (měst). Potom bylo vygenerováno kolem každého z nich 1000 objektů s dvourozměrným normálním rozdělením.
Obr č.5 Gaussovo normální rozdělení GIS objektů
Multidimenzionální schéma použité pro experimenty bylo jednoduché. Obsahovalo jen jednu tabulku faktů a lokační (geografickou) dimenzi. Tabulka faktů obsahovala jeden fakt vyjadřující počet GIS objektů v příslušné ploše. Geografická dimenze byla konstruována s využitím indexace prostoru. Stupeň agregace je zaveden do každé geografické dimenze pro každou úroveň uzlů v R stromu. Předpočítaná agregovaná data mohou být uložena v datovém skladu pro každý uzel (tj. MBH) R stromu.
Možnosti prostorové analýzy konvenčního systému OLAP jsou omezeny jednoduchým filtrováním vyjadřovaným v SQL. Naproti tomu GOLAP umožňuje analyzovat plochy ohraničené obecným polygonem. Autoři, aby ukázaly použitelnost GOLAPu, vybrali pesimistickou strategii. Tzn. Experimentální analýzy byly provedeny spíše na obdélníkových plochách než na obecných.
Pro všechny plochy byly analyzovány množiny dat dvou velikostí. Menší o velikosti 1000x1000 bodů reprezentující 1% celé sítě. Větší o velikosti 5000x5000 bodů reprezentujících 25% celé sítě. Pro všechny množiny dat a všechny velikosti prohledávaných ploch bylo provedeno dvacet běhů. Prohledávaná plocha byla v různých pozicích (kolem center shluků v případě Gaussova rozdělení) v jednotlivých bězích. Průměr hodnot všech dvaceti běhů obou dob odezvy a počet GIS objektů prohledávané plochy jsou uvedeny v tabulce 1.
Obrázek 4 a 5 ukazují výsledky provedené vyhodnocovacím modulem. Černé obdélníky reprezentují MBH prostorového indexu, který plně pokrývá prohledávanou plochu. Černé body reprezentují GIS objekty, které jsou obsaženy v prohledávané ploše, ale MBH, která je pokrývají, v ní nejsou plně obsazena. Tyto černé obdélníky a body odpovídají agregacím vyhodnoceným OLAPovou částí systému GOLAP.
|
Velikost plochy [body] |
Množina dat |
Objekty |
GOLAP |
OLAP |
Zrychlení OLAP/GOLAP [%] |
|
|
R-strom objekty |
Prům. čas odezvy [s] |
Prům. čas odezvy [s] |
||||
|
1000x1000 |
Rovn. |
1223 |
427 |
3.50 |
13.78 |
393.7 |
|
Gauss |
1998 |
60 |
0.51 |
13.11 |
2570.6 |
|
|
5000x5000 |
Rovn. |
24852 |
2416 |
33.67 |
14.23 |
42.3 |
|
Gauss |
21705 |
647 |
8.49 |
15.43 |
181.7 |
|
Tabulka 1. Výsledky experimentů
V případě vyhodnocování OLAP systémem musí být vyhodnocovány všechny GIS objekty (tzn. černé i šedé body na obrázku). Poměr počtu černých obdélníků a bodů ke všem bodům určuje efektivnost OLAPu.
5. Závěr
V tomto příspěvku je popsáno rozšíření komerčního systému OLAP, které umožňuje vyhodnocovat dotazy na uživatelem zadávaných plochách. Bez rozšíření je komerční OLAP vhodný jen pro on-line analýzu předdefinovaných oblastí (např. administrativní regiony, apod.).
Řešení je založené na použití prostorové indexace v multidimenzionální struktuře a využití indexace při vyhodnocování složitých, prostorově-analytických dotazů. Vyvinutý prototyp byl nazván GOLAP. První série experimentů prokázaly, že navrhované řešení je použitelné. Podle jejich výsledků je GOLAP 2 až 25 krát rychlejší než OLAP.
Efektivita systému GOLAP závisí na počtu objektů v prohledávané ploše, čas odezvy systému OLAP na něm není podstatně závislý. Komerční OLAP vybírá data pro agregaci, která odpovídají prohledávané ploše tak, že každý objekt testuje, leží-li v prohledávané ploše. Naproti tomu GOLAP používá k výpočtu výsledku pouze potřebná data agregovaná podle prostorového indexu.
Z tabulky 1 je zřejmé, že jsou situace, kdy je OLAP rychlejší než GOLAP. Experimenty potvrzují hypotézu, že efektivita systému GOLAP odpovídá poměru T/S, kde S je počet GIS objektů v prohledávané ploše a T je celkový počet objektů. Další výzkum bude zaměřen na podrobnější analýzy a jejich závislosti. Budou hledány kritické hodnoty poměru počtu objektů, kdy komerční OLAP pracuje lépe než GOLAP. Předpokládáme, že v praxi při geografických analýzách nepřekračuje velikost prohledávané plochy 10% celé mapy.
Dalším námětem pro výzkum je optimalizace dotazů systému OLAP generovaných prostorovým indexem. Tato optimalizace pomůže posunout výše kritickou hodnotu poměru.
Literatura
- Guttman, A.: R-trees: a dynamic index structure for spatial indexing, Proc. of SIGMOD Int. Conf. on Management of Data, 1984
- Gavrila, D.M.: R-tree Index Optimization, CAR-TR-718, Comp. Vision Laboratory Center for Automation Research, University of Maryland, 1994
- Kouba Z., Matoušek K., Mikšovský P.: On Data Warehouse and GIS Integration, In: Proceedings of the 11. International Conference on Database and Expert Systems Applications (DEXA 2000), Ibrahim, M. and Küng, J. and Revell, N. (Eds.), Lecture Notes in Computer Science (LNCS 1873), Springer, Germany
- Kurz A.: Data Warehousing - Enabling Technology, (in German), MITP-Verlag GmBH, Bonn, 1999, ISBN 3-8266-4045-4
- Pokorný J.:Prostorové datové struktury a jejich použití k indexaci prostorových objektů, GIS Ostrava 2000, Technical University Ostrava, Ostrava, 2000