Hf Platforma průmyslové spolupráce CZ.l.07/2.4.00/17.0041 Název Operátory pro zpracování proudů dat Popis a využití práce s operátory v jazyce Esper pro Java Benchmarking výuka: pokročilá Java Jazyk textu slovenský Autor (autoři) Tomáš Hrušo Oficiální stránka projektu: http://lasaris.fi.muni.cz/pps Dostupnost výukových materiálů a nástrojů online: http://lasaris.fi.muni.cz/pps/study-materials-and-tools Obsah 1 Spracúvanie dát........................................... 3 1.1 Udalosť/Event........................................ 3 1.1.1 Typ udalosti...................................... 4 1.1.2 Atribúty udalosti................................... 4 1.1.3 Udalosť ako objekt.................................. 4 1.2 Stavebné kamene pre spracúvanie udalostí........................ 5 1.2.1 Producenti udalostí.................................. 6 1.2.2 Konzumenti udalostí................................. 8 1.2.3 Agenti spracúvania udalostí ............................ 11 Filtrujúci agenti ................................... 12 Transformační agenti................................ 13 Detekční agenti.................................... 15 1.3 Sieť spracúvania udalostí.................................. 17 2 Spôsoby spracúvania udalostí.................................. 18 2.1 Systém pre správu databáz ................................. 19 2.2 Systém riadenia toku dát................................... 19 3 Kontexty............................................... 22 3.1 Temporálny kontext...................................... 22 3.1.1 Fixný interval..................................... 22 3.1.2 Kĺzajúci interval ................................... 24 3.2 Priestorový kontext...................................... 25 4 Príkazy................................................ 27 4.1 Agregačné operátory..................................... 28 4.1.1 COUNT........................................ 29 4.1.2 MIN.......................................... 30 4.1.3 MAX.......................................... 31 4.1.4 AVG.......................................... 32 4.1.5 SUM.......................................... 33 4.2 GROUP BY........................................... 34 4.3 JOIN.............................................. 37 4.4 SEQUENCE.......................................... 39 4.5 ORDERBY........................................... 42 4.6 First N............................................. 46 5 Záver................................................. 48 1 Úvod Hneď ako začala výpočtová technika pracovať rýchlejšie ako človek, dávali sa jej úlohy na spracúvanie veľkého množstva dát a mala reagovať určitým spôsobom, ktorý záleží od prijatých dát. Odvtedy vznikli rôzne reprezentácie dát a prístupy ku ich spracovaniu. V tejto práci budem pracovať s dátami reprezentovanými ako udalosti a porovnám ich s databázovým systémom. Hardvér už nie je taký drahý, ako býval. Firmy si môžu dovoliť najvýkonnejšie stroje. Čo sa týka úložného priestoru, tak vďaka virtuálizácii a ďalšiemu softvérovému vybaveniu môžeme teoreticky predpokladať, že máme neobmedzene miesta. Čo ma ale najviac v tejto práci zaujíma, je rýchlosť spracovania dát, takže odhliadneme od obmedzení v pamäti. „Spracovanie dát je činnosť, ktorú vykonáva napríklad počítač alebo človek pri manipulácii s dátami s cieľom ich transformácie v rámci zadanej úlohy" [7]. V tejto práci ma bude zaujímať samotný spôsob transformácie dát pomocou operátorov. Každý operátor je funkcia, ktorá mení vstup na výstup pomocou definovaných pravidiel. Existuje ich strašne veľa, tak som vybral niektoré, naviac používané. Kombináciou operátorov môžem prakticky z každého vstupu vytvoriť výstup aký chcem. Prvá kapitola sa bude venovať teoretickému základu návrhu udalosťami riadenej sieti [3]. Pozriem sa konkrétne na každú zložku osobitne a zadefinujem pojmy súvisiace so spracúvaním dát. V druhej kapitole porovnám systém riadenia toku dát(DSMS) a systém pre správu databáz (DBMS). Rozoberiem ich rozdiely a načrtnem ich využitie. V tretej kapitole sa pozriem na kontexty a ich použitie pri spracúvaní dát. Rozoberiem rôzne druhy kontextov, nie len časové ale aj priestorové. V štvrtej, poslednej kapitole popíšem formálne každý operátor, pridám príklady použitia a porovnám rýchlosť pri rôznych vstupných hodnotách. Cieľom tejto práce je premerať operátory v spracúvaní dát. Zistiť pri akých podmienkach je operátor rýchlejší a pri ktorých naopak veľmi pomalý. 2 Kapitola 1 Spracúvanie dát Spracúvanie dát je metóda sledovania a analyzovania toku udalostí/ dát. Na základe analýzy toku môžeme následne vytvoriť novú udalosť, ktorú bude spracúvať iný tok udalostí. Týmto postupom vytvoríme komplexné spracovanie dát (Complex event processing - CEP). CEP analyzuje viacero tokov súčasne a na základe tejto analýzy môže vytvoriť novú udalosť a poslať ju do jedného alebo viacerých tokov dát. Tento postup je veľmi efektívny pre analýzu napríklad logu užívateľov, ktorý sa snažili prihlásiť do nejakého systému za určenú dobu, tzv. offline spracúvanie ale aj pre aplikácie, ktoré pracujú v reálnom čase(online) ako napríklad aplikácia, ktorá skúma počasie v Českej republike. Má k dispozícii niekoľko meteorologických staníc v Brne, Prahe a Olomouci. Každá stanica odošle každú minútu aktuálne informácie o počasí, ale aby sa nepreťažila sieť, každá inú sekundu. Aplikácia spracúva informácie tak, že prijme všetky udalosti a vnútorne ich logicky rozdelí a rozošle každú ku svojmu spracúvaniu, napríklad teplotu pošle stanici A, ktorá spočíta priemernú hodnotu a vypíše ju užívateľovi. Čiže, každú minútu si aplikácia pozbiera informácie od meteorologických staníc (od každej má jeden vstupný tok) a spočíta výsledné hodnoty, ktoré pošle ku vypísaniu na obrazovku (t.j. na výstupný tok). 1.1 Udalosť/Event „Event je udalosť v rámci určitého systému alebo domény, je to niečo čo sa stalo, alebo sa uvažuje akoby sa stalo v tejto doméne. Slovo event sa tiež používa ako programovacia entita, ktorá reprezentuje udalosť vo výpočtovom systéme." [3] Inými slovami, je to popísateľná množina dát, ktorá vznikla na základe nejakej zmeny v systéme, napríklad vytvorenie nového užívateľa alebo niečo jednoduché ako tik časovača alebo klik-nutie myšou a ďalšie iné. Je to základná jednotka spracúvania udalostí podobná riadku v tabuľke databáze alebo objektu v OOP(objektovo orientovanom programovaní). Každý event musí obsahovať časové razítko jej vzniku. Je možné že jedna udalosť v systéme môže vyvolať viac ako jeden event v aplikácii. Napríklad zrušenie dovolenky môže vygenerovať udalosť na odvolanie rezervácie v hoteli odoslanej na recepciu, ďalej na zrušenie pôžičky auta poslanej danej požičovni áut a samozrejme udalosť pre uvoľnenie rezervácie v lietadle. Nemusí to byť reálna udalosť, ktorá sa stala v tomto svete, môže to byť udalosť, ktorá vzniká vo virtuálnej realite alebo nejakej simulácii. 3 1. Spracúvanie dát 1.1.1 Typ udalosti „Typ udalosti je špecifikácia pre množinu eventov, ktoré majú rovnaký sémantický zmysel a rovnakú štruktúru. Každý event je považovaný ako inštancia nejakého typu. "[3] Keď máme nejakú veľkú aplikáciu, tak niekedy potrebujeme spracúvať iba niektoré udalosti. Napríklad ich môžeme rozdeľovať pomocou ich typu. V spomínanej aplikácii na skúmanie a meranie počasia máme niekoľko typov udalostí. Prvá je od meteorologickej stanice, typu Informácie o počasí, keď príde táto udalosť, aplikácia ju rozloží na menšie udalosti napríklad typu Teplota alebo Tlak vzduchu, a podobne. 1.1.2 Atribúty udalosti „Atribút udalosti je komponenta štruktúry udalosti. Každý atribút má meno a dátový typ." [3] Atribúty pomáhajú zisťovať príčinu udalostí a obohacujú udalosť o dôležité informácie. Každý atribút má dátový typ. Napríklad v spomínanej aplikácii na meranie teploty, teplomery posielajú udalosť s atribútom, ktorý má názov teplota a je dátového typu číslo. 1.1.3 Udalosť ako objekt Definition element describing event type Header Pay load Open content Open content indicator Type description attributes Event type Identifier string Event composition true/false Temporal granularity milliseconoVsecondfminute... Header attribute indicators Occurrence time Event certainty Event annotation" Event Identity Detection time Event source Attribute name Data type Semantic role Relationships to other event types Member Generalization / Specialization Retraction Obr. 1.1: Definičný element typu udalosti sa skladá s atribútov, ktoré opisujú obsah hlavičky a nákladu eventu, a listom vzťahov tohoto typu a ostatných typov udalostí. [3] 4 1. Spracúvanie dát Obrázok 1.1 zobrazuje štruktúru definičného elementu. Ako môžeme vidieť, skladá sa z nasledujúcich informácií: Atribúty opisujúce typ Podľa týchto atribútov vie detekčný systém určiť presný typ udalosti a skontrolovať či splňuje atribúty daného typu. Identifikátor typu udalosti obsahuje reťazec znakov, číže názov typu. Kompozícia udalosti je pravdivostná hodnota či je daný typ kompozíciou iného alebo nie. Časové razítko a granularita udáva v akých jednotkách sa bude merať čas. V spomínanej aplikácii na skúmanie počasia by tu bola hodnota sekundy. Ukazovatele na atribúty v hlavičke Tieto atribúty slúžia na zistenie miesta a času vzniknutia udalosti, jej dôveryhodnosti, obsahuje taktiež volný text slúžiaci ako popis udalosti a jej unikátny identifikátor. Definície atribútov Tu sa už nenachádzajú metadáta, ale dáta, ktoré podrobnejšie opisujú aktuálny výskyt udalosti. Každý takýto atribút musí byť pomenovaný (nejaký reťazec znakov), musí mať dátový typ (číslo, reťazec, pravdivostná hodnota, binárne dáta, dátum, lokácia, ...) a musí mať sémantickú rolu (normálny, bežný atribút alebo odkaz na inú udalosť). Ukazovateľ na volný obsah S týmto ukazovateľom máme volnú ruku s formátováním dát. Obsahuje dáta, ktorým formát môže určiť entita, ktorá udalosť vytvorila. Vzťah s ostatnými typmi udalostí Určuje vzťah s inými typmi udalostí (ak vôbec nejaký existuje). Člen je vzťah hovoriaci že daná udalosť je člen inej zloženej udalosti. Generalizácia a špecifikácia je vzť ah určujúci čije tento typ zovšeobecnením alebo špecifikáciou iného typu udalosti. Stiahnutie je vzťah ku druhému typu keď su navzájom logicky opačné. Napríklad ako udalosť typu Zrušenie objednávky je opakom udalosti typu Zadanie objednávky. 1.2 Stavebné kamene pre spracúvanie udalostí Ako každý spôsob programovania, programovanie pomocou spracúvania udalostí je výnimočné. Samozrejme že sa dá simulovať v ostatných spôsoboch, napríklad v OOP (udalosť je objekt) alebo v databáze (udalosť je riadok tabuľky) ale táto architektúra programovania je založená na veľkej sieti rôznych objektov, spojenej kanálmi, ktoré prenášajú udalosti od jedného objektu ku druhému. Je veľmi jednoduché zmeniť funkčnosť vymenením jednej časti, časťou novou s rovnakým rozhraním. V tejto sekcii si postupne priblížime rôzne druhy týchto objektov a ich prepojení, stavebných kameňov pre spracúvanie dát. 5 1. Spracúvanie dát 1.2.1 Producenti udalostí „Producent udalostí je entita na kraji systému pracujúceho s udalosťami, ktorá vkladá udalosti do systému." [3] Obr. 1.2: Rôzne druhy producentov udalostí stretávajúce sa v aplikáciách na spracúvanie dát. [3] Producent je dôležitá súčasť systému. Bez neho by nevznikali žiadne udalosti, ktoré by sa dali ďalej spracúvať. V spomínanej aplikácii na spracúvanie počasia, sú meteorologické stanice producenti udalostí. Ale nemusí to byť vždy tak jednoduché. Napríklad ak sú dve udalosťami riadené siete navzájom prepojené, tak tá druhá vidí tú prvú ako producenta. Existujú stovky príkladov, čo by mohlo byť producentom udalostí. Ako môžeme vidieť na Obrázku 1.2 tak sa producenti dajú rozdeliť do troch skupín: 1. Hardware Hardwareový producenti sa používajú v strašne veľa odvetviach a základom je senzor. Ako napríklad senzor ktorý merá: • Teplotu • Vzduch • Vlhkosť • Tlak tekutiny • pH level Viac komplikovanejšie detektory využívajú viac senzorov naraz ako napríklad GPS lokátor, Siezmometer alebo policajný radar na meranie rýchlosti. Physical sensors Embedded sensors Detectors Cameras Microphones Application programs Verification and payment Location and presence Social communications Surveillance Simulated sensors Applications Instrumentation Adaptors Data feeds 6 1. Spracúvanie dát 2. Software Aj keď software je často sprevádzaný hardwareovým producentom, existujú aj iba soft-wareový producenti. Napríklad simulované senzory. Sú to klasické hardwareové senzory, ktoré sú simulované vo virtuálnej realite alebo nejakom simulátore. Ďalej aplikácie, ktoré generujú udalosti na základe zadaných parametrov. Alebo generátory udalostí, ktoré nie sú vygenerované aplikáciou ale nepriamo nejakou monitorujúcou aplikáciou. Alebo takzvané adaptory, nie sú to aplikácie čo si „vymýšlajú" nové udalosti ale pozorujú okolie (napríklad viac hardwareových producentov) a na základe toho generujú nové udalosti, alebo len premieňajú rozhranie udalostí aby vyhovovali požiadavkám siete. 3. Ľudská interakcia Každá udalosť vygenerovaná ľudskou interakciou je vždy sprevádzaná kúskom hardwaru a softwaru. Väčšinou to je klikanie v grafickom rozhraní aplikácie alebo iná interakcia s užívateľským rozhraním. Pekným príkladom je sociálna komunikácia ako napríklad Facebook alebo Twiter. Všeobecne sa všetci títo producenti dajú zapísať pomocou definičného elementu producenta udalostí. Ako môžeme vidieť na Obrázku 1.3, definičný element producenta udalostí sa skladá z nasledujúcich informácií: Detaily o producentovi Táto časť obsahuje informácie o producentovi. Identifikátor udáva meno producenta, ktoré môže byť odkazované z inej časti systému. Kategória udáva kategóriu producenta (napríklad meteorologická stanica). Nemá žiadny vplyv na spracovanie vygenerovaných udalostí, ale popisuje druh producenta. Typ definičného elementu obsahuje informáciu o definičnom elemente. Môže nadobudnúť jednu z hodnôt: abstraktný typ, trieda producentov alebo inštancia triedy producentov. Anotácia obsahuje užívateľské informácie o inštancii, triede alebo abstraktnom type. Je voliteľným atribútom. Fronta je logická hodnota indikujúca či producent má frontu alebo nie. Výstupné terminály Je to kolekcia výstupných terminálov kde pre každý jeden obsahuje tri informácie. Identifikátor sa používa na rozlíšenie výstupných terminálov v prípade že producent má viac ako jeden terminál. Typy udalostí sú kolekcia obsahujúca identifikátory typov udalostí, ktoré môže vyprodukovať cez daný výstupný terminál. Nie je to výhradná asociácia (viac výstupných terminálov môže produkovať rovnaký typ udalostí). Ciele sú list identifikátorov vstupných terminálov entít ktoré prijímajú udalosti z daného výstupného terminálu. Ak je producent abstraktný typ, môže mať aj nula cieľov. Viac výstupných terminálov môže mať rovnaký cieľ. Vzťahy s ostatnými producentmi Určuje vzťah ku ostatným producentom, môže sa jednať o zovšeobecnenie alebo o špeci- 7 1. Spracúvanie dát Building block describing event producer Icon: > Producer details Event producer identifier Event producer category Definition element type Annotation Query capability Output terminals Identifier Event types Targets Relationship to other producers Generalization / Specialization Obr. 1.3: Definičný element producenta udalostí obsahuje informácie o definičnom elemente samotnom, list výstupných terminálov, a list vzťahov ku ostatným definíciám producentov udalostí. [3] fikáciu. Napríklad typ Meteorologická stanica v Brne je špecifikáciou všeobecnejšieho typu Meteorologická stanica. 1.2.2 Konzumenti udalostí „Konzument udalostí je entita na kraji systému pracujúceho s udalosťami, ktorá prijíma udalosti zo systému." [3] Konzument je zložka systému bez ktorej by samotné spracúvanie nemalo žiaden zmysel. Je to komponenta, ktorá spracúva (napríklad zobrazuje) udalosti ktoré sieť vygeneruje. V spomínanej aplikácii na spracúvanie počasia, je monitor užívateľa konzument udalostí. Ale nie vždy to musí byť tak jednoduché. Napríklad keď sú dve udalosťami ovládané siete navzájom prepojené, tak prvá vidí tú druhú ako svojho konzumenta. Existuje veľa príkladov, čo by mohlo byť konzumentom udalostí. 8 1. Spracúvanie dát Physical actuators Industrial control Lighting systems HVAC Alarm systems Email, SMS, telephone Computer user interfaces News feeds Social networking Event logs Business applications Business processes State machines Home automation Obr. 1.4: Druhy konzumentov udalostí stretávajúce sa v aplikáciách na spracúvanie dát. [3] Ako môžeme vidieť na Obrázku 1.4 tak sa konzumenti dajú rozdeliť do troch skupín: 1. Hardware Hardwareový konzument je často označovaný ako aktivátor. Keď dostane udalosť, tak vykoná nejakú akciu v reálnom svete. Napríklad zamykanie a odomykanie dverí, kontrolovanie výhybiek vlaku, a ďalšie iné. 2. Ľudská interakcia Človek ako konzument udalostí potrebuje vizualizáciu dát, napríklad monitorom. Samotná vizualizácia je prevádzaná softwareom alebo hardwareom, ktorý vizualizáciu podporuje. Napríklad spomínaný monitor, aplikácia si navrhne užívateľské prostredie a na základe prichádzajúcich udalostí ho mení. Napríklad v aplikácii na skúmanie a meranie počasia, keď príde udalosť, ktorá ukazuje že v Brne prší, aplikácia zmení obrázok pri Brne na mrak s kvapkami. Ale ak následne príde informácia že v Olomouci svieti slnko, v sekcii pre Olomouc sa zmení obrázok na slnko. Výborným príkladom sú Ambient prístroje 1, tie reagujú na prichádzajúcu udalosť zmenou farby. 3. Software Softwareovým konzumentom udalostí je napríklad log aplikácie kde sa zapisujú výsledky alebo iné operácie, ktoré aplikácia vykonala. Môže sa hocikedy pozrieť na ľubovolný bod v čase a zistiť čo aplikácia vtedy vykonávala a podlá toho sa zachovať. Na základe udalosti môže nejaký systém zmeniť svoj stav. Napríklad webovej stránke, ktorá ponúka veľa webových aplikácií, príde udalosť o veľkej zátaži serveru, ktorú zanalyzuje a na základe toho zmení svoj stav na zaťažená a bude poskytovať iba 50% aplikácií. 1. http://www.ambientdevices.com/ 9 1. Spracúvanie dát Všeobecne sa všetci títo konzumenti dajú zapísať pomocou definičného elementu konzumenta udalostí. Building block describing event consumer Icon: Consumer details Event consumer identifier Event consumer category Definition element type Annotation Input terminals Identifier Event types Filters Sources Relationship to other consumers Generalization / Specialization Obr. 1.5: Definičný element konzument udalostí obsahuje detaily o definičnom elemente samotnom, list vstupných terminálov, a list vzťahov ku ostatným definíciám konzumentov udalostí. [3] Ako môžeme vidieť na Obrázku 1.5, definičný element konzumenta udalostí sa skladá z nasledujúcich informácií: Detaily o konzumentovi Táto časť obsahuje informácie o konzumentovi. Identifikátor udáva meno konzumenta, ktoré môže byť odkazované z inej časti systému. Kategória udáva kategóriu konzumenta (napríklad log). Nemá žiaden vplyv na spracovanie udalostí, ale popisuje druh konzumenta. Typ definičného elementu obsahuje informáciu o definičnom elemente. Môže nadobudnúť jednu z hodnôt: abstraktný typ, trieda konzumentov alebo inštancia triedy konzumentov. Anotácia obsahuje užívateľské informácie o inštancii, triede alebo abstraktnom type. Je voliteľným atribútom. Výstupné terminály Je to kolekcia vstupných terminálov kde pre každý jeden obsahuje štyri informácie. Identifikátor sa používa na rozlíšenie vstupných terminálov v prípade že konzument má viac 10 1. Spracúvanie dát ako jeden terminál. Typy udalostí sú list obsahujúci identifikátory typov udalostí, ktoré sú akceptované daným vstupným terminálom. Nie je to výhradná asociácia (viac vstupných terminálov môže akceptovať rovnaký typ udalostí). Filtre sú rozšírením a spresnením predchádzajúcej kolekcie. Špecifikujú aké udalosti môžu byť akceptované týmto vstupným terminálom. Zdroje sú list identifikátorov výstupných terminálov entít ktoré odosielajú udalosti do daného výstupného terminálu. Ak je konzument abstraktný typ, môže mať aj nula zdrojov. Vzťahy s ostatnými konzumentmi Určuje vzťah ku ostatným konzumentom, môže sa jednať o zovšeobecnenie alebo o špecifikáciu. Napríklad typ log záťaže systému je špecifikáciou všeobecnejšieho typu log. 1.2.3 Agenti spracúvania udalostí „Agent spracúvania udalostí je softwareový modul ktorý spracúva udalosti." [3] Agent spracúvania udalostí tvorí jadro udalosťami riadenej architektúry. Vykonáva 3 základné funkcie: filtrovanie, porovnávanie a odvodzovanie. Event processing agent í ■ iltc- Transformation I Pa'.tť i detect 1 I l Translate Aggregate Split 1 Compose Enrich Project Obr. 1.6: Typy agentov. Tento diagram ukazuje dedičnú hierarchiu, napríklad, Obohatenie a Projekcia sú špeciálne prípady Prekladania, ktoré je špeciálnym prípadom Transformácie. [3] V agentovi najskôr prebieha filtrovacia funkcia, ktorá zahodí všetky udalosti, ktoré nespĺňajú požadované vlastnosti. Potom nastane porovnávanie, ktoré hľadá zadaný vzor vo vstupných udalostiach, a nakoniec sa na výstupe predchádzajúceho kroku spustí funkcia na odvodenie finálnej verzie udalostí, ktoré sú vypustené výstupným terminálom ku ďalšiemu spracúvaniu. Ako uvidíme ďalej, nie každý typ agenta musí využívať všetky 3 funkcie. Všeobecne sa agenti dajú zapísať pomocou definičného elementu agenta spracúvania udalostí. Ako môžeme vidieť na Obrázku 1.7, definičný element agenta sa skladá z nasledujúcich informácií: 11 1. Spracúvanie dát Definition element describing event processing agent Icon !0 EPA general information EPAtdéfiiiflftr EPA lyp# Filtering function Filler expra safari Malching function Pattern signature Derivation function Derivation formulae Input terminals Identifier Event types Filers Snurces Output terminals Identifier Event types Targets Relationships Contact ire-ence Global slate references Obr. 1.7: Všeobecný definičný element agenta spracúvania udalostí. [3] Všeobecné informácie Táto časť obsahuje identifikátor, ktorý reprezentuje unikátne meno agenta, ktorého je to definičný element. Ďalej obsahuje typ agenta, tento atribút zaraďuje agenta do nejakej zo skupín na Obrázku 1.6. Vstupné/výstupné terminály Zoznam/list vstupných terminálov s rovnakým rozhraním ako 1.5. Zoznam/list výstupných terminálov s rovnakým rozhraním ako 1.3. Filtrujúci agenti Keď máme obrovskú aplikáciu obsahujúcu veľa producentov udalostí, tak sa môže stať že potrebujeme iba určitý druh udalostí. Ku tomuto výsledku sa môžeme dopracovať viacerými prostriedkami. Ako sme videli už v kapitole 1.2.2, tak sa dá filtrovať na vstupných termináloch pomo- 12 1. Spracúvanie dát cou listu typov udalostí, ktoré môžu byť prijaté. Podobne môžeme na vstupnom terminály zadať filtrovací výraz, ktorý ak sa vyhodnotí na PRAVDA, tak je udalosť prijatá, a ak sa vyhodnotí na NEPRAVDA, tak sa udalosť zahodí. Niekedy je ale vhodné spracúvať aj udalosti, ktoré neprejdú filtrovacím výrazom. Na to sa používajú špeciálny filtrovací agenti. Ako môžeme vidieť na obrázku 1.8, tento druh agentov má 3 výstupné terminály. Nielen že môžete spracúvať aj udalosti, ktoré neprejdú filtrovacím výrazom, ale môžete spracúvať aj udalosti na ktoré sa nedá aplikovať filtrovací výraz (napríklad sú iného typu, alebo niektorý z atribútov nie je definovaný, a podobne). Ďalší a posledný typ filtrovania spočíva v kontextoch, kedy spracúvame len niektoré udalosti podľa časového razítka alebo pozície. Ku kontextom sa dostanem neskôr. Transformační agenti Keď už máme odfiltrované nepotrebné udalosti, chceme s nimi pracovať. Môžeme použiť niekoľko techník, ktoré sú zobrazené na obrázku 1.9. Rozlišujeme dva druhy transformačných agentov, bez stavu a so stavom. Bez stavu sú takí, že každú udalosť spracúvajú rovnako (projekcia, obohatenie a preklad). Transformační agenti so stavom spočívajú v tom, že výstupná udalosť je odvodená z viacerých vstupných udalostí (kompozícia, agregácia a rozdelenie). Obohatenie/Enrich Tento transformačný agent obohatí vstupnú udalosť o nejakú doplňujúcu informáciu. Ako napríklad pri objednávke, ktorá obsahuje adresu, sa podľa adresy nájde meno osoby, ktorá tam býva a pridá sa ako nový atribút. Obr. 1.8: Filtrovací agent ukazujúci vstupný terminál a 3 výstupné. [3] 13 1. Spracúvanie dát Obr. 1.9: Šesť podtypov transformačného agenta ukazujúcich vstupné a výstupné terminály a typ transformácie. [3] Proj ekcia/Proj ect Opačný agent ako predchádzajúci. V tomto prípade nejakú informáciu zo vstupnej udalosti odoberáme. Ako napríklad nepotrebné identifikátory, čísla vo výslednom produkte. Preklad/Translate Je kombináciou predchádzajúcich dvoch. Môže odoberať aj pridávať nové atribúty do vstupnej udalosti. Výstupná udalosť sa vôbec nemusí podobať vstupnej. Tento agent môže slúžiť ako adaptér, ktorý prekladá z jedného rozhrania do druhého. Kompozícia/Compose Ako názov napovedá, tento agent komponuje, skladá viacero udalostí do jednej pomocou nejakého daného pravidla. Podobne ako operátor JOIN, ktorý rozoberiem neskôr. Rozdelenie/Split Tento agent je opak predchádzajúceho. Rozdeľuje udalosti podľa nejakého daného pravidla. Podobne ako v aplikácii na meranie počasia, ktorá rozdeľuje udalosť od meteorologickej stanice na menšie, ktoré rozposiela špeciálnym agentom na ďalšie spracúvanie. Podobne ako operátor GROUP BY, ktorý rozoberiem neskôr. Agregaci a/Aggregate Agent slúžiaci na prevádzanie agregačných funkcií ako počet, priemerná hodnota, atď. Ako v spomínanej aplikácii, kde počítame priemernú hodnotu teploty. 14 1. Spracúvanie dát Detekční agenti Detekční agenti sú dôvod, prečo sa používa udalosťami orientované programovanie. Nielen že môžeme filtrovať a transformovať udalosti, vďaka týmto agentom je možné eventy kombinovať a detegovať vzory. Pattern detect EPA Input terminal fíte r e* p na s sien r^S— Instance l-T selection Context expreEE on Relevance Altering Relevenr. event typ b e Pattern matching set * Matchiní Derivation Output n r? , .-■^ Derivation _I I expression _ Derivation fljtpjBaakn ^ Participant □vents Pattern s^tatua: "x^ Partám type Pattern parameters Relevant event types Pattern palctes Not-selected Obr. 1.10: Logická štruktúra detekčného agenta, ukazujúca tri logické časti s „podpisom vzoru",ktorý riadi proces detegovania vzoru. Trojuholníkové objekty reprezentujú inštancie udalosti. [3] Ako je vidieť na Obrázku 1.10, detekčný agent používa všetky tri zložky (filtrovaciu, porovnávaciu aj odvodzovaciu). Existujú dva druhy typov vzorov, základný a dimenzionálny. Základné vzory sú napríklad: All pattern Tento vzor obsahuje list typov udalostí. Ukladá si udalosti a pri každej prichádzajúcej skontroluje, či má už takú udalosť uloženú, ak nie „vyškrtne " si ju zo zoznamu, ak hej, čaká na ďalšie. Keď prijme všetky typy udalostí, splní vzor a vygeneruje výslednú udalosť. Any pattern Tento vzor funguje podobne ako predchádzajúci, akurát je spokojný ak mu príde aspoň jedna udalosť so zoznamu. 15 1. Spracúvanie dát Absence pattern Vzor, ktorý sa využíva najčastejšie ako časovač. Keď mu priradíme temporálny kontext, o ktorom bude reč neskôr, tak bude spokojný ak za daný čas nepríde ani jedna udalosť. Treshold patterns Sú to vzory, ktorým dáme číslo a názov atribútu. Prehľadávajú prichádzajúce udalosti a kontrolujú či napríklad počet udalostí sa nerovná tomu číslu(count pattern), alebo či hodnota nie je väčšia/menšia ako zadané číslo(value min/max/average pattern). Môžeme mu priradiť aj funkciu, ktorá niečo počíta s atribútmi a porovnáva s výslednou hodnotou. Subset selection pattern Tieto vzory pracujú s podmnožinami udalostí ako napríklad hľadajú určitý počet najväčších/ najmenších hodnôt(the relative n highest/lowest values pattern). Okrem týchto základných existujú ešte aj dimenzionálně, ktoré pracujú s časom, priestorom alebo ich kombináciou. Nasledujúce vzory su dimenzionálně: Sequence pattern Tento vzor deteguje sekvencie udalostí. Je spokojný ak prišla aspoň jedna udalosť z každého typu udalostí, ktoré má na zozname, a prišli v rovnakom poradí. Tento vzor budem brať ako operátor a rozoberiem ho neskôr. First/Last n pattern Tieto vzory redukujú veľký počet udalostí na n alebo menej udalostí. Ak ich je menej ako n, vybrané sú všetky. First n pattern deteguje prvých n udalostí a Last n pattern opačne posledných n udalostí. Trend patterns Tieto vzory pozorujú určitý atribút udalostí a porovnávajú ich medzi sebou. Napríklad Increasing pattern deteguje či každá nová udalosť má daný atribút väčší ako predchádzajúca. Decreasing pattern deteguje či je daný atribút vždy menší. Non-increasing/non-decreasing pattern detekujú nestúpanie/neklesanie atribútu. Spatial patterns Tieto vzory pracujú s GPS lokáciou udalosti. Kontrolujú vzdialenosť udalosti od určitého bodu(min/max/average pattern) alebo vzdialenosti všetkých udalostí po dvojiciach(rela-tive min/max/average pattern) Spatiotemporal patterns Ako posledný typ sú detekční agenti, ktorí pracujú s GPS lokáciou a časom zároveň. Pozorujú zmenu polohy udalosti s priebehom času a testujú zmenu jej smeru. Napríklad či stojí na mieste alebo sa pohybuje (ne)rovno. 16 1. Spracúvanie dát 1.3 Sieť spracúvania udalostí Skombinovaním predchádzajúcich stavebných kameňov, prepojených kanálmi vytvoríme sieť na spracúvanie udalostí. Od producentov sú do nej posielané udalosti, ktoré sieť pomocou rôznych agentov spracúva, transformuje a deteguje rôzne vzory. Nakoniec spracované udalosti pošle konzumentom. Ako vidíme na Obrázku 1.11 sieť môžeme reprezentovať grafickou notáciou, pospájaním stavebných kameňov šípkami v smere posielania udalostí. Na obrázku môžeme vidieť zatiaľ nespomenuté stavebné kamene ako kanál (Channel) a globálny stavový element (State). Kanál uľahčuje grafickú notáciu tým, že rozdeľuje M:N reláciu na M:l a 1:N relácie, čo sa ľahšie zakresľuje. Globálny stavový element slúži na zachovávanie informácií bez ohľadu na spracúvanú udalosť. Interne sa môže podobať klasickej relačnej databáze, ktorá mení svoj stav na základe prijatia rôznych udalostí. Napríklad môže mať uložený jazyk, v ktorom sa vykonáva spracúvanie udalostí a na základe tejto informácie sa môžu udalosti preposielať cez prekladového agenta. Ak užívateľ zmení jazyk, je globálnemu stavovému elementu zaslaná udalosť na zmenenie jazyku. Obr. 1.11: Ukážka siete spracúvania udalostí ukazujúca grafickú reprezentáciu a ilustruje niektoré vlastnosti siete. [3] Keďže sieť môže byť veľmi komplikovaná, môžeme ju rozdeliť na menšie časti, ktoré nakoniec spojíme do jednej veľkej. Pozrieme sa na ňu ako na obyčajného agenta, ktorý má počet vstupných terminálov rovnaký ako ma podsieť producentov a výstupných terminálov rovnako veľa, ako má podsieť konzumentov. Táto kapitola obsahuje základné teoretické základy spracúvania udalostí. Ďalej sa pozriem na spôsoby spracúvania dát/udalostí pomocou systému riadenia toku dát (DSMS) a systému pre správu databáz (DBMS). 17 Kapitola 2 Spôsoby spracúvania udalostí V tejto kapitole sa pozriem na základy spracúvania dát pomocou systému riadenia toku dát(DSMS) a systému pre správu databáz(DBMS). DSMS je rozšírením DBMS o dôležité koncepty pri spracovaní dát. Existujú tam kontinuálne dotazy, ktoré sa nevykonajú raz ako v databáze, ale existujú tam permanentne. Dalo by sa to simulovať v databáze pomocou spúšťačov(triggerov) pri vkladaní do tabuľky, ale nie je to rovnako výkonné. Spúšťač vždy pracuje s celou tabuľkou, naproti tomu, kontinuálny dotaz si zaznamenáva informácie postupne, a pracuje iba s dátami, ktoré práve potrebuje. Napríklad dotaz na spočítanie udalostí v priebehu minúty. Spúšť ač si pri každej novej udalosti vždy prepočíta celú tabuľku, plus musí odfiltrovať udalosti, ktoré nepatria do minútového intervalu, čo je časovo veľmi náročné. Kontinuálny dotaz pri každej novej udalosti pripočíta jednotku ku počítadlu a odčíta počet udalostí, ktoré sú staršie ako minúta(tie sa vyhodia ako už nepotrebné). Systém pre správu databáz Systém riadenia toku dát Perzistentně dáta Nestály dátový prúd Náhodný prístup Sekvenčný prístup Dotazy na jedno použitie Kontinuálne dotazy (Teoreticky) neobmedzené sekundárne úložisko Limitovaná hlavná pamäť Iba momentálny stav je relevantný Treba uvažovať ako je zoradený vstup Relatívne malá úroveň obnovovania Potencionálne extrémne veľká úroveň obnovovania Malinké alebo žiadne časové nároky Nároky v reálnom čase Predpokladajú sa presné údaje Predpokladajú sa zastaralé/nepresné údaje Plánované spracovanie dotazu Variabilné príchody dát a ich charakteristiky Tabuľka 2.1: Rozdiely medzi DBMS a DSMS[8] V Tabuľke 2.1 vidíme hlavné rozdiely medzi týmito dvoma systémami. Jeden som už trochu začal rozoberať, ale v priebehu kapitoly sa z oboch pohľadov pozriem na každý problém osobitne. 18 2. Spôsoby spracúvania udalostí 2.1 Systém pre správu databáz V databázovom systéme môžeme uchovávať udalosti ako riadky v tabuľke. Problém spočíva v tom, že databáza očakáva stále dáta, ktoré užívateľ uloží a potom ich opakovane číta a používa. Udalosti sú ale na jedno použitie. Reprezentujú okamih v čase, ktorý nastal na základe nejakej zmeny v systéme. Keď sa zmena spracuje, pokračuje sa ďalšou udalosťou. To nás privádza ku potrebe sekvenčného prístupu, ktorý databáza nemá. Pristupuje ku dátam náhodne, čo môže byť menej optimálne pri postupne prichádzajúcich udalostiach, ktoré sa spracúvajú sekvenčne. Náhodný prístup môže byť naopak efektívnejší pri veľkom okne s použitím konkrétneho operátora, ku tomu sa ale dostanem neskôr. Každá nová udalosť je spracúvaná alebo upravovaná (záleží na aplikácii). V databázovom systéme sa dá pracovať s každou novou udalosťou pomocou spúšťačov, ktoré pri každom vyvolaní, musia prejsť celú tabuľku, pretože spolu nezdieľajú žiadne dáta. Sú to dotazy na jedno použitie. Veľká výhoda databázového systému je v teoreticky neobmedzenej pamäti keďže nikdy dopredu nevieme, koľko udalostí bude potrebné uložiť pri ich spracúvaní. Ale s veľkým množstvom dát, prichádza časová náročnosť ich spracúvania. Databáza sa snaží optimalizovať dotazy, ktoré sú na ňu dotazované aby prebehli čo najrýchlejšie, ale všeobecne na databázový systém nie sú časové nároky vyhrotené do takých vysokých hodnôt ako potrebuje ku svojmu rýchlemu prevozu spracúvanie dát. To znamená ze dotaz by sa mal vyhodnotiť do príchodu nasledujúcej udalosti. Databázový systém nie je navrhnutý tak, aby sa staral o zoradenie vstupu, ktoré môže byť porušené pomalou linkou(udalosť, s časovým razítkom r sa dostane ku agentovi neskôr ako udalosť s časovým razítkom r + 1). Dôležitý je iba momentálny stav databázy nad ktorou sa spustí dotaz, ktorý si musí sám zabezpečiť zoradenie spracúvaných dát. Použitie databázového systéme slúži hlavne na uschovávanie trvalých, presných a nemenia-cich sa dát. Ak je nad dátami spustená nejaká procedúra, môže sa naplánovať, čo pri udalostiach neplatí, pretože nevieme kedy nastanú. Systému pre správu databáz chýbajú základné prvky spracúvania dát, ale stále sa dá použiť na túto činnosť. Každá operácia sa dá simulovať pomocou procedúr a spúšťačov. Schéma(atribúty) udalosti reprezentujú stĺpce v tabuľke, ktorá reprezentuje prúd udalostí. Obtiažne, ale nie nemožné, sú na simuláciu kontexty, ku ktorým sa dostanem v nasledujúcej kapitole, pretože sa musia zisťovať pri každej novej udalosti, čo môže byť časovo náročné. Teraz ešte na porovnanie rozoberiem systém určený pre spracúvanie udalostí, DSMS. 2.2 Systém riadenia toku dát Projektov na zdokonalenie spracúvania dát existuje niekoľko [2]. Ale všetky musia bojovať so základnými výzvami samotného spracúvania udalostí. Musia predpokladať nestály dátový prúd. Neexistuje možnosť predpovedať kedy udalosť nastane a dopredu sa na ňu nejako špecificky pripraviť. Môžu využívať informácie, že udalosti prichádzajú jedna za druhou a nastaviť spracúvanie na sekvenčné, čo môže výrazne zvýšiť výkon aplikácie. Dotazy musia byť natoľko rýchle aby zvládali veľmi rýchly prísun nových udalostí v reálnom čase. Z toho vyplýva že môže byť potrebná extrémne vysoká úroveň obnovovania. 19 2. Spôsoby spracúvania udalostí Ako som už spomenul v kapitole 2.1, udalosti nemusia vďaka rýchlosti siete prísť v presnom poradí. S týmto problémom sa dá vysporiadať rôznymi spôsobmi ako vzorkovaním(sampling), dávkovým spracovaním(batch processing) alebo pomocou kĺzajúcich okien(sliding windows). Tieto spôsoby rozoberiem neskôr v priebehu kapitoly ale ani jeden nemôže byť natvrdo implementovaný v jadre systému, pretože užívateľ ich nemusí chcieť vždy využiť. Pomalá linka, udalosti ktoré neprišli v správnom poradí, nespôsobujú rizikové problémy v samotnom spracúvaní, ale znižujú presnosť výsledných dát. Užívateľ môže využiť spomínaných systémov na spresnenie výsledku svojej aplikácie. Zoradenie udalostí nemusí byť iba pomocou časového razítka ich vzniku. Užívateľ môže definovať iné usporiadanie s ktorým sa systém musí nejako vysporiadať. Napríklad môže brať ako dôležitý čas príchodu udalosti ku agentovi, takže pomalé linky už nebudú spôsobovať problémy lebo z pohľadu agenta pôjdu po poradí. Jednou s najväčších výziev pri spracúvaní udalostí je uloženie potencionálne neobmedzeného dátového prúdu do limitovanej hlavnej pamäte. Pokiaľ dotaz, ktorý sa vyhodnocuje s príchodom každej novej udalosti, trvá veľmi dlho, ďalšie udalosti sa pomaly nahromadia a dátový prúd môže narásť do enormných rozmerov. Inak povedané, ak nové udalosti stále prichádzajú, aj keď staré ešte nie sú spracované, hodnota výpočtu na jednu udalosť musí byť malá, inak bude latencia výpočtu moc veľká a algoritmus nebude stíhať s dátovým prúdom. Preto sa zaujímame o algoritmy ktoré sú spokojné s hlavnou pamäťou a nepristupujú na disk. Týmto sa dostávame ku ďalšiemu problému, ktorým sú kontinuálne dotazy. Tento problém som už naznačil v úvode kapitoly a je výnimočný pre spracúvanie dát. S každou novou udalosťou sa prepočíta výsledná hodnota algoritmu. Keďže s rýchlo prichádzajúcimi udalosťami rastie ich počet, výpočtová hodnota algoritmu sa predlžuje a môže sa preplniť pamäť. Aby sme urýchlili beh algoritmu, môžeme aproximovať odpoveď a tým znížiť presnosť výsledku, ktorá je väčšinou dostačujúca. Existujú rôzne spôsoby aproximácie, ktoré teraz postupne vysvetlím. [2] Kĺzajúce okná Jedna z techník na aproximáciu výsledku je nepočítať výsledok zo všetkých dát ale iba z blízkej minulosti. V reálnych aplikáciách sa tento druh aproximácie využíva veľmi často, pretože zastaralé dáta sú menej dôležité ako nové a preto môžu byť zanedbané. Týmto prístupom nie len že zredukujeme čas behu algoritmu, keďže bude počítať z obmedzeného počtu dát, ale aj vyriešime problém neobmedzeného prúdu dát. SQL-podobné programovacie jazyky stačí rozšíriť a kľúčové slovo, ktoré vytvorí, spravuje a manipuluje s kĺzajúcim oknom. Napríklad v jazyku CQL [1], okno s veľkosťou 1 minúty, ktoré sa posúva po 10 sekundách vyzerá následovne: SELECT Istream Count(*) EROM C2XMessage [ Range 1 Minuté Slide 10 s~] WHERE Speed > 30.0 Ku kĺzajúcim a iným druhom okien sa vrátim v ďalšej kapitole. [2] 20 2. Spôsoby spracúvania udalostí Dávkové spracovanie Tento spôsob sa hodí ak je kontinuálny dotaz pomalý a pridanie novej udalosti do prúdu je rýchle. Spočíva v tom, že prichádzajúce udalosti su buffrované, postupne dané do menších dávok, ktoré sú následne spracované kontinuálnym dotazom. Pokiaľ je kontinuálny dotaz vykonávaný, nové udalosti sa odkladajú do ďalšej dávky. Tento spôsob je výhodný, pretože nespôsobuje veľké nepresnosti v odpovedi, ale odpoveď dostaneme v neskoršom čase. Preto sa využíva v aplikáciách, ktoré očakávajú presnosť výsledku ale nevyžadujú instantnú odpoveď. [2] Vzorkovanie Vzorkovanie sa využíva ak kontinuálny dotaz prebehne za krátku dobu, ale pridanie novej udalosti trvá dlhšie ako priemerná doba príchodu ďalšej udalosti. Je nemožné aby boli využité všetky dáta, pretože prichádzajú skôr ako môžu byť spracované. Preto musí algoritmus počítať iba s niektorými udalosťami, čoho výsledkom je aproximácia výslednej hodnoty. Tento prístup môže v niektorých prípadoch(hlavne ak kontinuálny dotaz obsahuje operátor JOIN) poskytnúť veľmi slabú presnosť. Na algoritme, ktorý by poskytoval presnejšiu odpoveď sa stále pracuje. [2] Ďalším problémom su blokujúce operátory, ktoré pre svoj výpočet musia poznať celý vstup. Napríklad operátor zoradenia alebo agregačné operátory ako SUM, COUNT, MIN, MAX alebo AVG. Keďže nie je možné aby operátor čakal na celý vstup pretože nemôže odhadnúť kedy je koniec, musí to systém pre spracúvanie dát nejako vyriešiť. Jedna možnosť je produkovať odpoveď po každej novej udalosti(ako to napríklad robí Esper). Celkovo je každá odpoveď aproximácia výslednej, čo je lepšie ako žiadna odpoveď. Ďalšou možnosťou je nahradzovať blokujúce operátory ich neblokujúcimi variantami, ktoré robia približne rovnakú činnosť. V tejto kapitole som sa pozrel na rozdiely medzi systémom na spracúvanie udalostí a systémom na správu databáz. Ďalej priblížim problematiku kontextov používaných pri spracúvaní dát. 21 Kapitola 3 Kontexty Niekedy potrebujeme rozlišovať podobné udalosti na základe nejakej hodnoty, napríklad času alebo miesta vzniku, alebo chceme počítať len s podmnožinou všetkých udalostí. Aby sme to nemuseli všetko písať ručne, stále dokola do agentov, boli vytvorené kontexty, ktoré sa využívajú najčastejšie. Môžeme mať aplikáciu, ktorá prijíma udalosti iba od 8 do 10 hodiny rannej. Takže jej nastavíme fixný temporálny kontext, ktorý trvá iba dané hodiny. Udalosti, ktoré prídu v iných hodinách budú ignorované, pretože nepatria do kontextu. Na Obrázku 3.1 vidíme rôzne druhy kontextov aj s ich parametrami. V tejto kapitole sa budem zaoberať temporálnymi a priestorovými kontextami. O stavovo a segmentovo orientovaných kontextoch je viac informácií v [3, kapitola 7]. 3.1 Temporálny kontext Existujú 4 typy temporálnych kontextov, kde každý pracuje s rozdelením času na ohraničené intervaly, ktorým sa taktiež hovorí okná(windows). Ako vidíme na Obrázku 3.2, tieto okná môžu byť disjunktné(neprekrývajúce sa), kontinuálne (nadväzujúce na seba) alebo sa môžu prelínať. Ich začiatok a koniec môže byť vyvolaný buď určitým časovým okamihom, alebo konkrétnou udalosťou. V tejto podkapitole sa budem zaoberať iba intervalmi, ktoré sa spúšťajú a končia časovým okamžikom, pretože intervaly, ktoré závisia na udalostiach pracujú analogicky. Obsahujú list typov udalostí, pri ktorých výskyte sa okno otvorí a list typov udalostí, pri ktorých(opakovanom, podľa nastavenia okna) výskyte sa okno zatvorí. Otvorenie nového okna záleží na počte udalostí, ktoré sa vyskytli v priebehu času kedy bolo okno otvorené. Pre spresnenie analógie medzi týmito dvoma druhmi intervalov, si môžeme predstaviť systém, kde sa vyskytne nová udalosť každú sekundu (sekunda je najmenšia časová jednotka, ktorú použijem), takže fixný časový interval veľkosti 2 minút bude rovnako veľký ako fixný interval udalostí, ktorý sa zatvorí po príchode 120 udalostí od jeho otvorenia. 3.1.1 Fixný interval Fixný časový interval reprezentuje určitú časovú dobu, podľa ktorej sú udalosti rozdeľované do odlišných skupín, ktoré sú individuálne spracúvané. Môže to byť konštantná doba, bez opakovania, alebo sa môže opakovať. Atribúty tohoto kontextu sú následovné: 22 3. Kontexty Temporal Spatial State one nted E nrt rty Rabvanl BtatflB Temporal ordering Segmentation oriented Attribute list Partrtjon identifier Partition expreeaori F ijte J interval Inlarval alert Interval enc Recurrence Tamporal OTDJsnhg Event interval InriHtcf event list Terminator evant Nat Expiration tŕne offeel Expiration eventccunt Context inrtatcir pclcy Temporal ordenng SIkIiiiu fined interval In^erv al p e^oc Interval duration interval size Tenporal ordering S lid i rig event interval Evantllal Inlarval aJze Event period Tenporal orderrig Fined location Spatial relation Locstton attribute Part Lůn ident hers Entity Entity distance locution Lacalbn attribute Entity attribute Entity identrtlflf Penrton idefYiiiEirs Minimum and maxMnum distances. Event distance location Inrjalor event lis! Mriinun and maximum distance Context iritis tor polty Localbn attribute Obr. 3.1: Rozdielne typy kontextov ukazujúce svoje parametre. Tento diagram tiež ukazuje základné dimenzie priradené ku typom, napríklad typ fixná lokácia je braná ako priestorový kontext. [3] Štart intervalu Reprezentuje časovú jednotku, kedy interval začne. Môže byť typu Dátum alebo Dátum-Cas. Ak je dátového typu Dátum, interval začne o polnoci daného dátumu. Koniec intervalu Reprezentuje časovú jednotku, kedy prvý interval skončí, alebo obsahuje dĺžku intervalu. Môže byť typu Dátum alebo DátumCas. Ak je dátového typu Dátum, interval skončí o polnoci daného dátumu. Rekurzia Reprezentuje ako často, a či vôbec, sa interval opakuje. Temporálne zoradenie Tento atribút určuje, ktorá časová stopa sa má použiť(či čas detegovania alebo výskytu). 23 3. Kontexty Fixed interval July2.3010 SPH 4- i ha uii 9 i .CC 10:00 £:O0 10:00 °-D 3300 10-JOO Event interval A o *-1 Fro m patienf's ad mittance to ~° patent's, release A + j days Within ľ days from an earthquake 4- 2 rKHjri 4-1 hours Sliding fixed interval ... B- + 1 ŕiDur á-- =□ 4-1 hour -e- 4-1 hour -e- -e- 4- 1 hour 4-1 hour -e Á A ÄAAÄAA A Sliding event ^ 3-9-9-© interval Every ? blood presiuie measurements Obr. 3.2: Rozdielne typy temporálnych kontextov s ich kontextovými segmentami. [3] Na Obrázku 3.2 vidíme 2 fixné časové intervaly. Prvý môže znázorňovať aukčnú aplikáciu, kde aukcia začne 2 Júla 2010 o 18 hodine a trvá 3 hodiny. Akceptujú sa iba udalosti v tomto intervale. Druhý interval môže reprezentovať aplikáciu, ktorá skenuje trh každý pracovný deň od 8 do 10 hodiny rannej. Taktiež sa to dá predstaviť ako polootvorený interval [ts, te) kde udalosť s časovým razítkom t patrí do intervalu ak ts < r < te. 3.1.2 Kĺzajúci interval Kĺzajúci časový interval reprezentuje, laicky povedané, pohybujúci sa fixný časový interval. Taktiež rozdeľuje udalosti do rozdielnych skupín, akurát tento interval sa môže aj prekrývať, takže jedna udalosť môže patriť do viacerých intervalov zároveň. Atribúty tohoto kontextu sú následovné: Perióda intervalu Reprezentuje časový úsek od otvorenia okna, po ktorom bude otvorené okno nové. Trvanie intervalu Časový úsek, za ktorý ostáva okno otvorené. Veľkosť intervalu Maximálny počet udalostí, ktorý ak je prekročený, okno sa zavrie aj keď ešte nevypršalo trvanie intervalu. 24 3. Kontexty Temporálne zoradenie Tento atribút určuje, ktorá časová stopa sa má použiť(či čas detegovania alebo výskytu). Ako je vidieť na Obrázku 3.2, prvý kĺzajúci interval trvá 2 hodiny, a nové okno je otvorené každú hodinu t.j. perioda = 1 hodina a trvanie = 2 hodiny. Tuje viditeľné že ak je perioda intervalu menšia ako jeho trvanie, intervaly sa prelínajú. Druhý príklad je príklad kontinuálneho intervalu kde sa perióda a trvanie rovnajú. Posledný, na obrázku neznázornený interval je keď je perióda väčšia ako trvanie. Vtedy nie je intervalmi pokrytá celá časová os. Rovnako ako pri fixnom časovom intervale sa to dá predstaviť ako polootvorený interval [Ts,Te) takže udalosť s časovým razítkom r patrí do intervalu ak Ts < r < Te. V programovacom jazyku Esper, s ktorým som pracoval, som sa stretol s implementáciou kĺzajúceho okno, ktorá spájala časové okno s oknom riadeným udalosťami. Funguje to tak, že s každou novou udalosťou sa ako keby zavrie fiktívne, dopredu neotvorené okno. To znamená že s každou novou udalosťou s časovým razítkom r sú v minútovom okne všetky udalostí, ktoré majú časové razítko väčšie alebo rovné r — 60 sec. 3.2 Priestorový kontext Priestorový kontext rozdeľuje udalosti podľa ich geografickej lokácie. Aby sme mohli zistiť kde udalosť vznikla, musí obsahovať atribúty reprezentujúce jej geografickú lokáciu, napríklad bod by obsahoval geografickú šírku a výšku. Miesto vzniku udalosti môže byť taktiež reprezentované názvom nejakej geografickej entity, napríklad názov mesta. Na správne určenie miesta a zaradenie do správneho kontextu potrebujeme externú databázu podľa ktorej sa atribúty preložia do geografických súradníc, takémuto postupu sa hovorí geoco-ding. Udalosť nemusí reprezentovať len bod v 2-D priestore, môže to byť aj priamka/úsečka, napríklad cesta, ktorá vytvorila udalosť zápcha. Môže to byť taktiež aj plocha, príde udalosť že vybuchla bomba a jej umiestnenie bude area výbuchu. Existujú 3 typy priestorového kontextu. Fixná lokácia(Fixed location), Vzdialenosť od entity (Entity distance location) a Vzdialenosť od udalosti(Event distance location). Každý jeden následne povrchne rozoberiem. Fixná lokácia Tento kontext využijeme ak nás zaujímajú udalosti len z nejakého miesta, napríklad chceme prijímať len udalosti, ktoré vznikli v Amerike. Existuje viac typov relácií, ktoré môže vzniknutá udalosť zdielať s definovanou a to: je obsiahnutá, obsahuje, presahuje, prelína sa, rovná sa alebo dotýka sa. Myslím že ich význam je zrejmý akurát dodám že je to brané z pohľadu entity, takže entita je obsiahnutá v udalosti, entita obsahuje udalosť, atd. Vzdialenosť od entity Tento kontext rozdeľuje udalosti podlá ich vzdialenosti od určitej entity. Teoreticky vytvára nekonečne veľa rozdelení, keďže vzdialenosť je jednotka dĺžky a každá dĺžka sa dá rozdeliť na nekonečne veľa častí, ale prakticky máme nejakú najmenšiu jednotku dĺžky, 25 3. Kontexty definujme si ju ako meter, tak potom vzdialenosť od entity veľkosti 1 km, rozdelí danú oblasť na 1000 rozdelení. Vzdialenosť od udalosti Tento kontext pracuje podobne ako Vzdialenosť od entity ale navyše má list udalostí, od ktorých sa vzdialenosť merá. Ak sa niekde vyskytne udalosť, ktorá sa nachádza na liste, tak sa vytvárajú rozdelenia na základe vzdialenosti od spomenutej udalosti. 26 Kapitola 4 Príkazy Už som spomenul celú teóriu spracúvania udalostí, teraz sa na to pozriem z viac praktickej časti. Budem hovoriť konkrétne o programovacom jazyku Esper, ktorého výkon a správanie operátorov som premeral. Esper je open-source softvér pod licenciou GNU General Public Licence(GPU) [6], ktorého syntax sa podobá, je rozšírením, SQL jazyka. Operátory pracujú podobne aj v ostatných programovacích jazykoch. Operátor v spracúvaní dát, je funkcia, ktorá zoberie žiadnu, jednu alebo viac udalostí na vstupe a vráti jednu alebo viac nových udalostí, číslo alebo iný dátový typ záležiac od operátora. Taktiež nemusí vrátiť nič. Operátory sú väčšinou úzko späté s kontextami, pretože dostávajú na vstup všetky udalosti, ktoré patria do daného kontextu, nie je to však podmienka. Aby som to spojil s teóriou, funkčnosť všetkých agentov sa dá zapísať pomocou príkazov, napríklad zo spomínaného Esperu. Pre lepšiu predstavu, filtrovací agent, ktorému sú posielané udalosti typu Prihlásenie užívateľa, odosiela ďalej iba udalosti, ktorých prihlásenie bolo neúspešné(a-tribút success je nepravda). Dotaz, ktorý vykonáva takúto úlohu môže vyzerať napríklad takto: INSERT INTO ďalejSpracúvanýPrúd SELECT * FROM prúdPriháseníUžívateľov WHERE success = false; Pri tomto dotaze som syntakticky využil iba kľúčové slová SQL jazyka. Ak by v databáze existovala tabuľka s názvom ďalejSpracúvanýPrúd a prúdPrihláseníUžívateľov tak by tento dotaz prešiel aj v databázovom systéme. Rozdiel je v tom, že v databáze by sa vykonal raz a skončil by, no v svete spracúvania dát je to kontinuálny dotaz, ktorý je priradený prúdu prúdPrihláseníUžívateľov. Takže pri každej novej udalosti v tomto prúde sa hneď vyhodnotí či ju poslať ďalej do prúdu ďalejSpracúvanýPrúd alebo zahodiť. Meranie časových hodnôt prebieha offline. Pomocou javovského Random 1 si vygenerujem náhodné listy udalosti(so semienkom 1, 2 a 3). Postupne tieto udalosti posielam agentovi na spracovanie. Agent obsahuje vždy jeden dotaz na konkrétny operátor. Z každého merania mám jednu časovú hodnotu v milisekundách, z ktorých vypočítam aritmetický priemer a výsledok zapíšem do tabuľky, z ktorej vykreslím graf pomocou online nástroju [10]. V tejto kapitole sa budem držať nasledujúcich označení. Pole, ktoré vygenerujem má značku EL a dĺžku n. Funkcia, ktorá vráti udalosť z pola môže byť buď EL(i), kde i je číslo(index, poradie udalosti v liste), alebo EL{E), kde E je udalosť, ktorú chceme z pola dostať na výstup. 1. http://docs.oracle.com/Javase/6/docs/api/java/util/Random.html 27 4. Príkazy Taktiež, niektoré operátory očakávajú na vstup atribút každej udalosti v EL, toto budem značiť ako EL(A). Udalosť má atribúty timestamp, ktorý je dátového typu long 2 a reprezentuje vznik udalosti, časové razítko, ďalej obsahuje atribút test, ktorý je taktiež dátového typu long a podlá tohoto atribútu sa bude testovať. Posledný atribút je D, ktorý je dátového typu reťazec(string), ale obsahuje len jedno písmeno, buď 1 alebo r. Tento atribút bol pridaný z dôvodu operátoru JOIN a rozhoduje do ktorého prúdu dát má byť udalosť poslaná. Takže udalosť budem formálne zapisovať ako E(t, t, d), kde r je časové razítko, t je hodnota atribútu test a d je hodnota atribútu D. Každý atribút dostanem funkciou E (A). Kontext, v ktorom bude operátor vyhodnocovaný, bude prevažne kĺzajúce okno, ktoré rozdelí vstup do m rôznych nedisjunktných častí. Generovanie udalostí prebieha tak, že každá 250-ta udalosť má o 1 ms väčší timestamp ako predchádzajúca, takže mám virtuálně prostredie kde sa za sekundu vytvoria 250 000 udalosti. Funkcia, ktorá toto pole generuje, dostane na vstup informácie počet udalostí, rozsah testu a semienko. Počet udalostí je zrejmé čo znamená, podlá semienka sa náhodne generuje a rozsah testu obsahuje číslo, ktoré reprezentuje maximálnu hodnotu atribútu test. Takže napríklad keby má hodnotu 6, atribút test obsahuje hodnoty z intervalu (0, 5). Atribút je vždy, pokiaľ nie je explicitne povedané inak, generovaný náhodne, pomocou spomínaného semienka. Atribút D, ktorý využijem iba pri operátore JOIN, sa generuje striedavo, t.j. každá párna udalosť má hodnotu „r" a každá nepárna hodnotu „1". Najviac vypovedajúca hodnota bude väčšinou pri počte udalostí 2 000 000, pretože je to jediné množstvo, ktoré je väčšie ako 10 sec okno. 4.1 Agregačné operátory Niekedy môže byť centrum záujmu jednoduchá matematická operácia, ktorá ako vstup dostane nejaký atribút viacerých logicky rovnakých udalostí, väčšinou číslo, a ako výsledok vráti číslo, ktoré je nejako odvodené zo vstupu. Príkladom môže byť funkcia MAX, ktorá zoberie na vstup nejaký číselný atribút udalostí a vráti najväčšiu nameranú hodnotu. Jedno z využití agregačných operátorov môže byť pri štatistických úlohách. Môže nás zaujímať priemerný počet prihlásených užívateľov za deň v hodinách. Tak vytvoríme kĺzajúce okno s periódou rovnou trvaniu intervalu, ktorá bude mať dĺžku 1 hodinu. Vždy keď sa okno uzavrie, spočítame počet prihlásení a pošleme túto informáciu ako udalosť ďalšiemu agentovi, ktorý z nich bude počítať priemernú hodnotu raz za deň. Môže to vyzerať následovne: INSERT INTO prúdPočtuPrihlásení SELECT COUNT(*) AS počet FROM prúdPriháseníUžívateľov . win : time_batch (1 hod ); SELECT AVG( počet) FROM prúdPočtuPrihlásení. win: time_batch (24 hod ); Syntax .win:time_batch(časový úsek) vytvorí spomínané kĺzajúce okno s rovnakým trvaním a periódou intervalu dĺžky časového úseku. Teraz sa presuniem konkrétnejšie na jednotlivé agregačné operátory postupne. 2. http://docs.oracle.com/Javase/tutorial/Java/nutsandbolts/datatypes.html 28 4. Príkazy 4.1.1 COUNT Jednoduchá operácia, ktorá reprezentuje funkciu, ktorá na vstupe očakáva E L a vráti jeho dĺžku n. Count 500 000 -*- 1 000 000 2 000 000 4400 4200 4000 3800 3600 3400 3200 3000 2800 2600 I 2400 ■ÍS 2200 I 2000 = 1800 1600 1400 1200 1000 800 600 400 200 0 3784.6 3514.6 2542 23Ě6.3 2252.6 1962.6 1865.6 velkosf time okna Obr. 4.1: Tento graf reprezentuje chovanie agregačného operátora COUNT pri rozdielnych veľkostiach veľkostí kĺzajúceho okna. Ako môžeme vidieť z grafu na Obrázku 4.1, zmena veľkosti okna žiadno výrazne nezmení rýchlosť výpočtu tohoto operátora. Všetky výraznejšie zmeny sú spôsobené nejakým prerušením procesu alebo iným vedľajším efektom. Je viditeľné menšie spomalenie pri 10 sec okne, ale to je pochopiteľné, keďže operátor dostáva naraz väčší vstup. Využitie tohoto operátora je veľmi rozsiahle. Existuje veľa aplikácií, ktoré na svoju prácu potrebujú mať vypočítaný počet niečoho, alebo dĺžku pola. Konkrétny príklad som spomenul už v úvode tento podkapitoly. 29 4. Príkazy 4.1.2 MIN Minimum je agregačný operátor, ktorý reprezentuje funkciu, ktorá na vstupe očakáva EL(A), ktoré sú typu číslo a vráti číselný atribút udalosti E (A), pre ktorý bude platiť že Vx G EL(A).E(A) < x. 500 000 -■- 1 000 000 2 000 000 Min 500 000 - sorted -■- 1 000 000 - sorted -■- 2 000 000 - sorted velkosť time okna Obr. 4.2: Tento graf reprezentuje chovanie agregačného operátora MIN pri rozdielnych veľkostiach veľkostí kĺzajúceho okna. Sorted(zoradené) znamená že atribút udalostí test je klesajúci. Ako môžeme vidieť z grafu na Obrázku 4.2, zmena veľkosti okna žiadno výrazne nezmení rýchlosť výpočtu tohoto operátora, až na zoradený vstup. Všetky výraznejšie zmeny sú spôsobené nejakým prerušením procesu alebo iným vedľajším efektom. Samozrejme že zoradený vstup sa bude so zväčšovaním okna spomaľovať pretože každá nová udalosť je nové minimum a všetko sa musí prepočítavať. Využitie tohoto operátora je si myslím celkom zrejmé. Napríklad chceme pozorovať cenu notebooku, tak prijímame udalosti, ktoré sú vyvolané zmenou ceny vybratého modelu. Nakoniec sa pozrieme kedy bol najlacnejší, kedy sa ho oplatilo kúpiť. 30 4. Príkazy 4.1.3 MAX Maximum je agregačný operátor, ktorý reprezentuje funkciu, ktorá na vstupe očakáva EL(A), ktoré sú typu číslo a vráti číselný atribút udalosti E (A), pre ktorý bude platiť že Vx G EL(A).E(A) > x. Max 500 000 1 000 000 2 000 000 500 000 - sorted 1 000 000 - sorted □ 2 000 000 - sorted 9000 8500 8000 7500 7000 6500 6000 5500 ' 5000 4500 4000 3500 3000 2500 2000 1500 1000 500 0 7728.6 60í «> kde horný riadok tabuľky sú udalosti, ktoré sú púšťané do ľavého prúdu a spodný riadok do pravého prúdu. Vstup pre každý príklad je rovnaký a to: a1 b3 a5 b7 b2 b4 ae a8 Prvý príklad je jednoduchý a typy obidvoch okien sú rovnaké a to keepall(). To znamená že sa udržujú všetky udalosti takže prakticky sa okno otvorí na začiatku spracúvania a zavrie na jeho konci. Vygenerovaný výsledok je: 1- {} 2. (a1,b2) 3. (b3, b2) 4. (a\b4),(b3,b4) 5. {a5, b2), {a5, b4) 6. (a1^6), (a3,a6), (a5,a6) 7. (b7,b2),(b7,b4),(b7,ae) 8. (a1, a8), (b3,a8),(a5,a8), (b7, a8) Druhý príklad ukazuje funkčnosť keď je last_event() typom obidvoch okien . To znamená že sa udržuje len posledná udalosť. Vygenerovaný výsledok je: 1- {} 2. (a1,b2) 3. (b3, b2) 4. {b3, b4) 5. (a5,b4) 6. (a5, a6) 7. (b7,ae) 8. (b7,a8) 38 4. Príkazy Tretí príklad ukazuje funkčnosť keď sú typy obidvoch okien length(2). To znamená že sa udržujú posledné 2 udalosti. Vygenerovaný výsledok je: 1- {} 2. (a1,b2) 3. (b\b2) 4. (a\&4),(&3,&4) 5. (a5, b2), (a5, b4) 6. {b3, a6), (a5, a6) 7. (&7,&4),(67,a6) 8. (a5, a8), (b7, a8) A posledný štvrtý príklad ukazuje funkčnosť keď sú typy obidvoch okien length_batch(2). To znamená že sa udržujú posledné 2 udalosti ale je to kľzajúce okno s rovnakou periódou a trvaním intervalu. Vygenerovaný výsledok je: 4. (a1, ft2), (63, ft2), (a1, Ď4), (63, 64) 7. (a5,b2),(a5,b4),(b7,b2),(b7,b4) 8. (a5, a6), (67, a6), (a5, a8), (67, a8) Z výsledkov vyplýva že operátor join v Esperi naozaj funguje ako karteziánsky súčin. Pri prvých troch príkladoch je vidieť že s príchodom každej novej udalosti sa najskôr pozrie či druhý prúd obsahuje nejaké udalosti. Ak nie, tak nič nespraví. Ak áno, vytvorí toľko nových udalostí, koľko je v druhom prúde udalostí. Trochu komplikovanejšie to je v štvrtom príklade, kde máme lengthjbatch okno. Tam sa operátor vykoná po zaplnení okna(v našom prípade 2 udalosti) a pozrie sa na posledné plné okno v druhom prúde a vytvorí x * y udalostí, kde x je počet udalostí v prvom prúde a y počet v druhom(v tomto prípade sú rovnaké, 2*2 = 4). Toto správanie je najlepšie vidieť príchodom 7. udalosti. Aj keď druhý prúd už zaplnil okno udalosťami 2 a 4, prišla aj udalosť 6(čiže sa otvorilo nové okno) tak výsledné spojené udalosti sú (5,2), (7,2),____Keď majú prúdy rôzne druhy okien, funguje každé samo za seba, rovnako ako v týchto príkladoch. Úplne rovnako to funguje aj pri časových oknách, akurát je rozdiel v timejbatch, pretože musí čakať na udalosť, ktorá nepatrí do daného okna aby ho mohla uzavrieť. Teraz prejdem ku výkonu tohoto operátora. Tento operátor je viac časovo náročný ako ostatné, plus je to blokujúci operátor, takže musí čakať na celý vstup aby mohol produkovať výsledok, a preto som musel zredukovať počet udalostí vytvorených za sekundu na 1000/sec, pretože potom by buď došla pamäť alebo by výpočet trval veľmi dlho. Z toho istého dôvodu mu na vstupe dávam iba 5 ciferné počty udalostí. Ako je vidieť na grafe na Obrázku 4.8 doba výpočtu rastie exponenciálne ku veľkosti okna. Je to logické, keďže JOIN spojuje každú udalosť z jedného prúdu s každou udalosťou druhého prúdu. 4.4 SEQUENCE Niekedy je potreba hľadať nejaké vzory v prúde dát, v tomto prípade sekvenciu. Sekvencia je postupnosť definovaných udalostí s definovaným poradím. Môžu sa líšiť typom alebo v hodnotách atribútov. Napríklad keď máme hocijaký systém s tlačítkom, ktoré vyvolá udalosť, môžeme 39 4. Príkazy Join 15 000 30 000 ■ 45 000 71641.3 503 46076 —J 367 i 163-"" 320 Í9>^ 24 81 219 1K7ŔK 151 53^-- 1 55 ^ i —1 i-- 9246"' „, 124 . i ---— ' 13.3 ■--- '6666.3-- _ . Ífl49.3 - - l j_____ velkosť time okna Obr. 4.8: Tento graf reprezentuje chovanie operátoru JOIN pri rozdielnych veľkostiach veľkostí kĺzajúceho okna. vytvoriť dotaz, ktorý deteguje či nebolo tlačítko stlačené 2 alebo viackrát za 3 sekundy. Ak sa tak stalo, akceptuje sa iba prvá udalosť (predpoklad že ostatné sú nechcené kliknutia). V Esperi nie je sekvencia implementovaná zvlášť ako operátor, ale dá sa modelovať pomocou všeobecnejšieho modelu detekovania vzorov. Keď detegujeme sekvenciu, zvyčajne nechceme aby nám systém odpovedal že ju našiel a ďalej nehľadal, preto je v Esperi kľúčové slovo every, ktoré zais-ťuje opakované hľadanie. Formálne, sekvencia je operátor, ktorý zoberie na vstup EL a na výstup posiela odpovede o nájdení požadovanej sekvencie. Posiela však iba kladné odpovede. Funkčnosť spomínaného kľúčového slova every spočíva v tom, že pri každom výskyte danej udalosti, vytvorí pre ňu sub-výraz, ktorý ďalej hľadá ďalší prvok sekvencie. Napríklad pri dotaze every (A -> B) pri výskyte druhej udalosti A sa vytvorí spomínaný sub-výraz a pri výskyte udalosti B sa zoberie najdlhšie aktívny sub-výraz a ukončí sa odpoveďou sekvencia sa našla [5]. Lepšie to je vidieť na príkladoch. 40 4. Príkazy V Esperi som sa zameral hlavne na funkčnosť kľúčového slova every, takže nasledujúce príklady sú vstup+dotaz/výsledok. Výsledná tabuľka bude vyzerať následovne, prvý stĺpec obsahuje dotaz na sekvenciu, ktorá sa hľadá a ostatné obsahujú číslo reprezentujúce počet sekvencií nájdených v danom vstupe. Vstup je postupnosť písmen(pre zjednodušenie budem vypisovať iba atribút test, ktorý je dátového typu reťazec). Prvý príklad je najjednoduchší, testuje či môže byť sekvencia prerušená inou udalosťou bez ovplyvnenia. Výsledok je jednoznačný a kladný. Vstup je [a, f, b, f, c], a pre každý dotaz bol výsledok práve jedna sekvencia. Druhý príklad je vstup [a, b, c, a, b, c, a, b, c, a, b, c]. Tretí príklad má vstup [a, a, a, a, b, b, b, b, c, c, c, c]. Dotaz 1. príklad 2. príklad 3. príklad a -> b 1 1 1 every(a -> b) 1 4 1 every a -> b 1 4 4 a -> every b 1 4 4 every a -> every b 1 10 16 a-> b-> c 1 1 1 every(a -> b -> c) 1 4 1 every a -> b -> c 1 4 4 a -> every b -> c 1 4 4 a -> b -> every c 1 4 4 every a -> every b -> c 1 10 16 a -> every b -> every c 1 10 16 every a -> b -> every c 1 10 16 every a -> every b -> every c 1 20 64 Z týchto výsledkov sa dá pekne vidieť ako to funguje na zadaných vstupoch. No v realite nie sú vstupy vždy takéto „pekné". Ďalší príklad, ktorý spomeniem berie na vstup mnou náhodne vymyslenú postupnosť a ukážem, ktoré udalosti sú zahrnuté v každej sekvencii. Vstup je následovný: [A1, B2, C3, B4, A5, De, C7, A8, F9, A10, A11, B12]. Číslo v exponente je len informačné, podľa neho budem rozlišovať udalosti. Formát následovného listu je «dotaz» nový riadok a očíslovaný list vo formáte «udalosť, pri ktorej sa našla sekvencia» | [«list sekvencií»]. • A -+ B 1. B2\[(A\B2)] • every (A —> B) 1. B2\[{A\B2)] 2. B12\[(A5,B12)} • every A —> B 1. B2\[(A\B2)] 2. B12\ [(A5, B12) , (A8, B12) , (A10, B12) , (A11, B12)] 41 4. Príkazy A —> everyB 1. B2\[(A\B2)] 2. B4\[{A\B4)] 3. B12\[(A\B12)] everyA —> everyB 3, 2, 1 £2| [(A1, B2)] B4\ [(A1, B4)] B12\ [(A1, B12) , (A5, B12) , (A8, B12) , (A10, £12) , (A11, B12)] Viac príkladov je na [5]. Teraz prejdem ku výkonu tohoto operátora. Premeral som hľadanie vzoru every(l->2->3) a every 1 -> every 2 -> every 3. Keďže sekvencia vytvára pre každú novú sek-venciu podvýraz, musel som taktiež zredukovať vstup pretože dochádzala pri testovaní pamäť. Na grafe na Obrázku 4.9 sú vidieť časové hodnoty pre vzor every(l->2->3). Tieto hodnoty výrazne klesajú, čo je logické keďže zväčšujem rôznosť atribútu test, čo znamená že je menšia pravdepodobnosť že sa vyskytne vo vstupe sekvencia (udalosti, ktoré neobsahujú v atribúte test čísla 1,2 alebo 3 sú ignorované). V grafe je aj konštantná hodnota pre nenáhodný vstup a to postupne 1,2,3,1,2,3,____Samozrejme že pre tento vstup je výpočet pomalší, pretože je tam tých sekvencií najviac. To isté platí aj pre vzor every l->every 2->every 3 zobrazený na grafe na Obrázku 4.10. Pri tomto meraní som musel znížiť počet vstupných udalostí až na 4 ciferné čísla, pretože tento vzor vytvára veľké množstvo podvýrazov, ktoré rýchlo zaplnili pamäť. 4.5 ORDER BY Udalosti máme zoradené podľa času príchodu, časového razítka. Lenže môže nastať situácia, kedy je potreba ich zoradiť pomocou nejakého iného atribútu, napríklad nejakej ceny a podobne. Aby to nebolo tak jednoduché, musíme ešte definovať počet udalostí, po ktorých to chceme zoraďovať. Je to celkom logické, keďže bez tejto informácie by sme sa snažili zoradiť celý potencionálne nekonečný prúd a to by nemuselo dopadnúť dobre. Syntax tohoto operátora je následovná: order by expression [asc I desc] [, expression [asc I desc]] [, ...] Ako je vidieť zo syntaxe, môžeme zoraďovať pomocou viacerých atribútov naraz. Ďalej si taktiež môžeme zadefinovať či chceme zoraďovať vzostupne (asc) alebo zostupne(desc), kde vzostupne je preddefinovaná hodnota. Formálne je to funkcia, ktorá zoberie EL a číslo n a vráti n-tice zoradených udalostí podľa definovaných atribútov. Môžeme zoraďovať aj pomocou viacerých atribútov. Potom to funguje ako pri alfabetickom zoraďovaní. Najskôr sa vstup zoradí pomocou prvého atribútu a kde sú rovnaké, rozhodne sa o ich poradí pomocou druhého atribútu, atď. 42 4. Príkazy Sequence everyfl ->2->3) 150 000 300 000 600 000 150 000 - sorted 300 000 - sorted 600 000 - sorted 6400 6200 6000 5800 5600 5400 5200 5000 4800 4600 4400 4200 4000 3800 & 3600 3 3400 ■Sá 3200 ä 3000 g 2800 2600 2400 2200 2000 1800 1600 1400 1200 1000 SOO 600 400 200 0 5612.6 561 2.6 5612.6 IBM f me t f; men ŕ ■ÍíiDj.O joj |aŕť»7 j3-1ŕ4 ĺ . ojoj i.o j&j-í ■ j-jo. k. 7491 1 1 ... 7.1 r 4 r £ľ "---_ 1504 6 ' —— 107 Q 6--—— iníí ŕ Ľ y ■1U J j .0 »■------ —i -----' rôznosť test atribútu 15 Obr. 4.9: Tento graf reprezentuje chovanie operátora SEQUENCE pri rozdielnych rôznych hodnotách atribútu test. Sorted(zoradené) znamená že atribút udalostí test má hodnoty postupne 1,2,3,1,2,3,... Esper na operátor ORDER BY kladie nasledujúce obmedzenie [4]: • Všetky agregačné funkcie, ktoré sa objavia v ORDER BY klauzule sa musia objaviť aj v SE-LECT výraze. Poďme sa teraz pozrieť na funkčnosť tohoto operátora v Esperi. Formát vstupu sa nezmení oproti minulým príkladom, to znamená že budem písať iba atribút test(ktorý je typu reťazec) a ako jeho horný index budem písať poradie(na rozlíšenie udalostí). Vstup pre prvý príklad je [a1, b2, c3, d4, e5, f6, g7, h8, i9, j^O] a vstup pre druhý príklad je presne opačný, t.j. [j1, i2, h3, g4, fJ, e6, d7, c8, b9, a10]. Pre obidva príklady je veľkosť buffru 3. 43 4. Príkazy 500 20000 19000 18000 17000 16000 15000 14000 13000 12000 T3 11000 J 10000 ■ _ ■g 9000 8000 7000 6000 5000 4000 3000 2000 1000 0 1 000 1 500 Sequence every 1 ->every 2->every 3 -■- 500 - sorted -•- 1 000 - sorted 1 500 - sorted niiAi i t 1 1 /4oU.J \ \ \ \ \ \ \ \ \ SÄ8Ä.3 57ř 7.3 5787.3 1 "--^^ \^ 1J - ' "----———^ľl""^-^! - rôznosť test atribútu 15 Obr. 4.10: Tento graf reprezentuje chovanie operátora SEQUENCE pri rozdielnych rôznych hodnotách atribútu test. Sorted(zoradené) znamená že atribút udalostí test má hodnoty postupne 1,2,3,1,2,3,... Výsledok prvého príkladu je následovný: prišla udalosť časové razítko test 1 a E3 2 b 3 c 4 d Ee 5 e 6 f 7 g E9 8 h 9 i 44 4. Príkazy Výsledok druhého príkladu je veľmi podobný: prišla udalosť časové razítko test 3 h E3 2 i 1 i 6 e Ee 5 f 4 g 9 b E9 8 c 7 d Z výsledkov je pekne vidieť že funkčnosť operátora odpovedá jeho definícii. Teraz sa presuniem na porovnanie výkonu operátora. Zmeral som ho na základe zmeny veľkosť buffru, ktorý ostáva zoradený. Dotaz vyzerá následovne: SELECT test, timestamp FROM Test.win:keepall() output every X events ORDER BY test; Order by 15000 14500 14000 13500 13000 12500 12000 11500 11000 10500 10000 9500 9000 8500 8000 7500 7000 6500 6000 5500 5000 4500 4000 3500 3000 2500 2000 1500 1000 500 D 13068.6 8741 « 872 6530.3 44 69________-—-" _______- _ ---------- 2447.6 232 0.6 ??sn3 Výpočet udalostí Obr. 4.11: Tento graf reprezentuje chovanie operátora ORDER BY pri rôznych hodnotách veľkosti buffru. Na grafe na Obrázku 4.11 je vidieť že pri väčšej veľkosti buffru je výkon operátora pomalší. To je jasné, keďže mu na vstupe príde viac udalostí, ktoré musí zoradiť. 45 4. Príkazy Z grafu na Obrázku 4.12 môžeme vydedukovať že Esper používa interne stromové uloženie, keďže až pri veľkosti okna 1 000 000 je výpočet náročnejší ako pri náhodnom vstupe. Očividne je vkladanie nových listov do stromu rýchlejšie ako vytvorenie nového stromu. Order by 19000 T- 18000 - 17000■- 16000 - 15000■- 14000 - 13000 - 12000 - 11000 - 10000 - i" 9000- i U 8000 - 7000 - 6000 - 5000 - 4000 - 3000 "• 2000 - 1000 - 0 - \00 166?n 3 /S 8483.3 _______ 8380.6 -—- ■-----___64f _.....^ -' ~ 41S 3073JÍ_____ liii.b 22i 0.3 2242.6 počet udalostí Obr. 4.12: Tento graf reprezentuje chovanie operátora ORDER BY pri rôznych hodnotách veľkosti buffru a vstupe zoradenom zostupne. 4.6 First N Tento operátor je v Esperi implementovaný ako okno. Správa sa to ako kontext, do ktorého patrí prvých n udalostí a ďalšie do neho nepatria. Tento operátor som už spomenul v 1.2.3 ako vzor pre detekčného agenta. Formálne je to funkcia, ktorá berie na vstup EL a číslo n a vracia ELV, ktorého dĺžka je n a obsah tvorí prvých n udalostí z E L. Ak veľkosť E L je menšia ako n, potom E L = ELV. Keďže funkčnosť tohoto operátora je úplne zrejmá. Teraz prejdem na funkčnosť implementácie pomocou Esperu. Uvediem 3 príklady, ktoré budú mať rovnaký vstup ale rôznu veľkosť bufferu. Vstup je [a1, b2, c3, d4, e5, /6, g7, h8, i9, jľ0]. Prvý riadok tabuľky budú veľkosti bufferu pre každý stĺpec. Udalosť je ďalej poslaná hneď pri jej príchode, takže budem písať dvojice (test, časové razítko). 46 4. Príkazy Výsledok ku danému vstupu je nasledovný: 5 10 20 (a,l) (a,l) (a,l) (b,2) (b,2) M (c,3) (c,3) (c,3) (d,4) (d,4) (d,4) (e,5) (e,5) (e,5) (f,6) (Í6) (g,7) (g,7) (h,8) (h,8) (i,9) (i,9) (p0) (po) Teraz prejdem ku rýchlosti tohoto operátora. Premeral som rýchlosť na základe zmeny veľkosť bufferu rovnako ako pri minulom operátore. Order by 14500 14000 13500 13000 12500 12000 11500 11000 10500 10000 9500 _ 9000 g 8500 g 8000 v; 7500 _j 7000 _ 6500 * 6000 5500 5000 4500 4000 3500 3000 2500 2000 1500 1000 500 0 13068.6 S741 f, R7? i- 6530.3 ______—-— _____—-—- 44 69 _ - " 2447.6 232 0.6 775*0 3 počet udalostí Obr. 4.13: Tento graf reprezentuje chovanie operátora FIRST N pri rozdielnych rôznych hodnotách veľkosti buffru. Na grafe na Obrázku 4.13 je pekne vidieť aj funkčnosť tohoto operátora. Pre 1 000 000 a 2 000 000 udalostí, keď je veľkosť bufferu 1 000 000, tak ich výkon je rovnaký(pre 2 000 000 by mal byť väčší, lebo ešte musí ignorovať ďalších milión udalostí ale to je chvíľka). 47 Kapitola 5 Záver Bakalárska práca zahrňuje základné pojmy z teórie spracúvania dát, snaží sa o zovšeobecnenie architektúry, ktorá má veľa rôznych implementácií. Porovnáva tento prístup so systémom pre správu databáz, kde ukazuje na rozdiely a podobnosti. Ďalej rozoberá dôležité, často používané operátory, vysvetľuje ako pracujú. Funkčnosť je prezentovaná na rôznych príkladoch kde je uvedený vstup a výstup. Je premeraná časová náročnosť každého operátora na rôznych vstupoch(rozdielna veľkosť okna, rôznorodosť testovaného atribútu, počet udalostí). Možným rozšírením tejto práce by mohlo byť rozpísanie viacerých operátorov alebo porovnanie správania a funkčnosti operátorov s iným programovacím jazykom pre spracúvanie dát ako napríklad Microsoft Streamlnsight1 alebo iným. 1. http:/ / technet.microsoft.com/en-us/library/ee362541.aspx 48 Literatúra [1] Arvind Arasu, Shivnath Babu, and Jennifer Widom. The cql continuous query language: Semantic foundations and query execution. ???, 2003. [2] Brian Babcock, Shivnath Babu, Mayur Datar, Rajeev Motwani, and Jennifer Widom. Models and issues in data stream systems. ???, 2002. [3] Opher Etzion and Peter Niblett. Event processing in action. Manning, c2011. [4] EsperTech Inc. Chapter 4. epl reference: Clauses. http://esper.codehaus.org/ esper-4 . 2 . 0/doc/ref erence/en/html/epl_clauses . html. [Online; navštívené 5.5.2014]. [5] EsperTech Inc. Chapter 6. epl reference: Patterns, http://esper.codehaus.org/ esper-4 .6.0/doc/reference/en-US/html/event_patterns .html. [Online; navštívené 8.5.2014]. [6] EsperTech Inc. Esper - license. http://esper.codehaus.org/about/license/ license . html. [Online; navštívené 26.4.2014]. [7] Wikipedia. Spracovanie dát — Wikipedia, the free encyclopedia, http : // sk . wikipedia . org/wiki/Spracovanie_d%C3%Alt, 2009. [Online; navštívené 04-November-2009]. [8] Wikipedia. Data stream management system — Wikipedia, the free encyclopedia, http s : //en . wikipedia . org/wiki/Data_stream_management_system, 2014. [Online; navštívené ll-May-2014]. [9] Wikipedia. Relational algebra — Wikipedia, the free encyclopedia. https://en. wikipedia . org/wiki/Relational_algebra#Natural_join, 2014. [Online; navštívené 07-May-2014]. [10] Zigomatic. Online charts I create and design your own charts and diagrams online, http : //www. onlinecharttool. com/. [Online; navštívené 29.4.2014]. 49