R1 1

Information about R1 1

Published on September 11, 2007

Author: Arundel0

Source: authorstream.com

Content

Safety Guarantee of Continuous Join Queries over Punctuated Data Streams:  Safety Guarantee of Continuous Join Queries over Punctuated Data Streams Hua-Gang Li *, Songting Chen, Junichi Tatemura Divykant Agrawal, K. Selcuk Candan and Wang-Pin Hsiung NEC Laboratories America * University of California, Santa Barbara Stream Query Processing:  Stream Query Processing Continuous Queries Stream Query Engine Streaming Data Streaming Data Online transaction management Network analysis Sensor network monitoring … Motivating Example:  Motivating Example Window approach However, window size may be hard to determine Exploiting stream constraints Uniqueness, sorted input, etc Punctuations Punctuation:  Punctuation Punctuation A predicate that must be evaluated to false for every element following the punctuation Representation [Tucker et al. TKDE 2003] A special tuple (*, c, *, *) E.g., Item(sellerid,itemid,name,initialprice) A punctuation 'no more item with itemid = 1' is denoted as (*, 1, *, *) State of the Art:  State of the Art Semantic modeling of punctuations [Tucker et al. TKDE 2003] Punctuation-aware query optimization Binary join [Ding et al. EDBT 2004] Group By [Li et al. SIGMOD 2005] Generation of useful punctuations, i.e., heartbeats, from time domain [Srivastava et al. PODS 2004] However, one fundamental problem is not addressed Whether a query can benefit from available punctuations, refer to as 'safety checking' problem Outline:  Outline Formulate safety checking problem for continuous join queries Sound and complete safety condition for simple punctuations Sounds and complete safety condition for complex punctuations Conclusion and future work Punctuation Scheme:  Punctuation Scheme Punctuation scheme Describe the types of punctuation instances that a data stream can have at runtime Can be viewed as metadata of punctuation instances Representation Simple punctuation schemes: e.g., Item(sellerid, itemid, name, initialprice). punctuation scheme (–,+,–,–), instance (*, 1, *, *) Complex punctation schemes: e.g., Bid(bidderid, itemid, increase). punctuation scheme (+,+,–), instance (1, 1, *) Determined by application semantics Safety Checking Problem:  Safety Checking Problem Given a continuous join query Q (CJQ) and a set of punctuation schemes, Determine If Q still requires unbounded memory consumption no matter what punctuation instances (described by the punctuation schemes) may occur For example: Unsafe if we only have following two punctuation schemes Item(sellerid,itemid,name,initialprice) (–, +, –, –) Bid(bidderid,itemid,increase) (+, +, –) Safety .vs. Runtime memory consumption Unsafe query always requires infinite runtime memory However, safe query does not guarantee low runtime memory consumption Concepts:  Join State Refer to the space used for storing the inputs of each join operator Purgeability Purgeability of a join state for every tuple t, there exists a finite set of punctuation instances such that t will not produce any join results with any new tuples Purgeability of a join operator Safe Execution Plan Every join operator involved is purgeable Safe CJQ There exists at least one safe execution plan Concepts … … √ Purging for Binary Join Operator:  Purging for Binary Join Operator Purge S2 is similar. Hence we need punctuation schemes S1 (–, +), S2 (+, –) A CJQ with no Safe Binary Join Plan:  A CJQ with no Safe Binary Join Plan S1.A = S3.A Punctuation Schemes S1 (A–, B+), S2 (B–, C+), S3 (C–, A+) CJQ Unsafe Plan Purging for M-Way Join Operator:  Purging for M-Way Join Operator Chained Purge Strategy:  Chained Purge Strategy There is a punctuation propagation effect for M-way join operator! Punctuation Graph (simple punctuation scheme):  Punctuation Graph (simple punctuation scheme) Capture such punctuation propagation effect Purgeability of a Join Operator:  THEOREM 1. The join state S is purgeable iff there exists a path from S to every other node Si in the punctuation graph COROLLARY 1. A join operator is purgeable iff its punctuation graph is a strongly connected graph. Purgeability of a Join Operator S S1 S2 S3 … … S’ Safety for CJQ:  Safety for CJQ Safe CJQ requires at least one safe execution plan However, the number of execution plans is exponential THEOREM 2. A CJQ is safe iff its M-join plan is safe → If M-join plan is unsafe, no other safe plan exists → Linear safety checking for simple punctuation schemes Handling Complex Punctuation Schemes:  Handling Complex Punctuation Schemes S3: (+,+) cannot purge either S1 or S2, but can purge S1 S2 S3 (A, C) Generalized Punctuation Graph:  Generalized Punctuation Graph Intermediate result Purge of raw data stream Purge of intermediate result CJQ Safety under Complex Punctuations Schemes:  CJQ Safety under Complex Punctuations Schemes Intuition: intermediate results have to be purgeable as well Transformed Punctuation Graph 1. Identify strongly connected sub-graph, merge them into a single merged node 2. Take the generalized punctuation edges of merged node into account, continue Step 1 THEOREM 3. A CJQ is safe iff transformed punctuation graph ends up in a single merged node Polynomial safety checking for complex punctuation schemes Conclusion & Future Work:  Conclusion andamp; Future Work Formulate the safety checking problem for CJQ Sound and complete safety conditions Based on novel punctuation graph Linear for simple punctuation schemes Polynomial for complex punctuation schemes Future work Optimization of Chained Purge Strategy for M-join M-join purge .vs. a tree binary-join purge Optimization of CJQ Purge plan .vs. join plan Adaptive purge plan Generation of Punctuations Slide21: 

Related presentations


Other presentations created by Arundel0

Black Holes powerpoint
07. 10. 2007
0 views

Black Holes powerpoint

Physics Presentation
16. 10. 2007
0 views

Physics Presentation

Bangladesh
12. 10. 2007
0 views

Bangladesh

Afrodite Sevasti
13. 10. 2007
0 views

Afrodite Sevasti

Industrial Revolution
22. 10. 2007
0 views

Industrial Revolution

American Imperialism
22. 10. 2007
0 views

American Imperialism

i2 icfa sep05
11. 09. 2007
0 views

i2 icfa sep05

Deok Ryong Yoon
11. 09. 2007
0 views

Deok Ryong Yoon

i DMSS
11. 09. 2007
0 views

i DMSS

FinnishChemicalsinfo rmation
15. 10. 2007
0 views

FinnishChemicalsinfo rmation

A Nieto Nuez
26. 11. 2007
0 views

A Nieto Nuez

bio435 660 chap8 pt2
07. 12. 2007
0 views

bio435 660 chap8 pt2

mini3
11. 12. 2007
0 views

mini3

lecture 29
25. 10. 2007
0 views

lecture 29

slidepres
29. 10. 2007
0 views

slidepres

research methods schultz
07. 10. 2007
0 views

research methods schultz

RA2002
24. 10. 2007
0 views

RA2002

Physics with RICH detectors
15. 11. 2007
0 views

Physics with RICH detectors

Chap 03
17. 11. 2007
0 views

Chap 03

hogg
03. 01. 2008
0 views

hogg

genrepatrickgilmour
15. 10. 2007
0 views

genrepatrickgilmour

Rabies 2
19. 11. 2007
0 views

Rabies 2

weight control program se
04. 01. 2008
0 views

weight control program se

Water Everywhere
02. 01. 2008
0 views

Water Everywhere

feb17 cacci Soo Young
11. 09. 2007
0 views

feb17 cacci Soo Young

Chang Kyung Sup
11. 09. 2007
0 views

Chang Kyung Sup

AD2002
05. 01. 2008
0 views

AD2002

athans99
16. 02. 2008
0 views

athans99

Neologismen in STAR WARS
19. 02. 2008
0 views

Neologismen in STAR WARS

F02
20. 02. 2008
0 views

F02

2006 National Traffic 101
30. 10. 2007
0 views

2006 National Traffic 101

younginvestigators
27. 02. 2008
0 views

younginvestigators

capacity
29. 02. 2008
0 views

capacity

BTS statement on mesothelioma
11. 03. 2008
0 views

BTS statement on mesothelioma

04 ICG report
20. 03. 2008
0 views

04 ICG report

chapter13part2
07. 04. 2008
0 views

chapter13part2

mesmuses methodology
20. 06. 2007
0 views

mesmuses methodology

Mar02 Workshop Sakallah
20. 06. 2007
0 views

Mar02 Workshop Sakallah

manifesto pldi
20. 06. 2007
0 views

manifesto pldi

lisb overview
20. 06. 2007
0 views

lisb overview

Lesko June01
20. 06. 2007
0 views

Lesko June01

350LEC
09. 04. 2008
0 views

350LEC

bogota final
13. 04. 2008
0 views

bogota final

naccl workshop canada2003
20. 06. 2007
0 views

naccl workshop canada2003

Musy
20. 06. 2007
0 views

Musy

miniboone kektc6
20. 06. 2007
0 views

miniboone kektc6

millennium mix
20. 06. 2007
0 views

millennium mix

MICRO III Aula4
20. 06. 2007
0 views

MICRO III Aula4

MICRO III Aula10
20. 06. 2007
0 views

MICRO III Aula10

MICRO III Aula1
20. 06. 2007
0 views

MICRO III Aula1

morocco
24. 10. 2007
0 views

morocco

wordsplash11th1
14. 04. 2008
0 views

wordsplash11th1

Lucas Foods Case Analysis
16. 04. 2008
0 views

Lucas Foods Case Analysis

opening research data lifecycle
19. 06. 2007
0 views

opening research data lifecycle

Oersted
19. 06. 2007
0 views

Oersted

file45164
17. 04. 2008
0 views

file45164

gutierrez 2002
22. 04. 2008
0 views

gutierrez 2002

thickett
17. 10. 2007
0 views

thickett

rias uk
28. 04. 2008
0 views

rias uk

potomacroundtable Presentation
28. 12. 2007
0 views

potomacroundtable Presentation

how do i know wetland
03. 01. 2008
0 views

how do i know wetland

Oceans2005
07. 11. 2007
0 views

Oceans2005

wblocuniv
11. 09. 2007
0 views

wblocuniv

Secrets Presentation
07. 01. 2008
0 views

Secrets Presentation

Trinidad Tobago
14. 02. 2008
0 views

Trinidad Tobago

MICROIII Aula9
20. 06. 2007
0 views

MICROIII Aula9

MICRO III Aula8
20. 06. 2007
0 views

MICRO III Aula8

Micro III Aula13
20. 06. 2007
0 views

Micro III Aula13

MICRO III Aula11
20. 06. 2007
0 views

MICRO III Aula11

GKim
11. 09. 2007
0 views

GKim

OPSPanama
22. 10. 2007
0 views

OPSPanama

East Asia
25. 03. 2008
0 views

East Asia

NORDU net 2003P Villemoes Talk
19. 06. 2007
0 views

NORDU net 2003P Villemoes Talk

Nygren TPC symposium
19. 06. 2007
0 views

Nygren TPC symposium

M Barbi
20. 06. 2007
0 views

M Barbi

vaitkus
10. 10. 2007
0 views

vaitkus

fpgd040225
29. 10. 2007
0 views

fpgd040225

Future of PR Iran November 2005
24. 02. 2008
0 views

Future of PR Iran November 2005

boj
09. 10. 2007
0 views

boj

Lacroix
15. 11. 2007
0 views

Lacroix

longo2
03. 01. 2008
0 views

longo2

dd259
19. 10. 2007
0 views

dd259

America in World War II
04. 01. 2008
0 views

America in World War II

Digitization Projects
11. 09. 2007
0 views

Digitization Projects

Mikkel Olesen
20. 06. 2007
0 views

Mikkel Olesen

from powerful to personal week2
22. 11. 2007
0 views

from powerful to personal week2

young soo
11. 09. 2007
0 views

young soo

Clayton
22. 10. 2007
0 views

Clayton

PL Asia Slides
11. 09. 2007
0 views

PL Asia Slides