2004 03 06 DEWS2004 in
1. 2. Continuous Query 3. 4.
GPS HTML, XML RFID
DB DB
Web URL TS URL Load Description 7 /echo.cgi 0.41 CGI Prog. RDB TS Load Mem 1 0.38 8688k 6 0.41 7808k TS URL IP 5 /top.html 7 /echo.cgi Location Description /test.shml URL SSI page /echo.cgi CGI Prog. Web z Web
DBMS
STREAM: Stanford Continuous Queries over Data Streams, Proc. SIGMOD2000. Query Processing, Resource Management, and Approximation in a Data Stream Management System, Proc. CIDR 2003. TelegraphCQ: Berkely TelegraphCQ: Continuous Dataflow Processing for an Uncertain World, Proc. CIDR 2003. PSoup: a system for streaming queries over streaming data, VLDB Journal 2003. Aurora: Brown, MIT Aurora: a new model and architecture for data stream management, VLDB Journal 2003.
NiagaraCQ: Wisconsin NiagaraCQ: A Scalable Continuous Query System for Internet Databases, SIGMOD 2000. Design and Evaluation of Alternative Selection Placement Strategies in Optimizing Continuous Queries, ICDE 2002. Gigascope: AT&T Gigascope: A Stream Databases for Network Applications, Proc. SIGMOD 2003. PeerCQ: Georgia Tech. PeerCQ: A Decentralized and Self-Configuring Peer-to- Peer Information Monitoring System, ICDCS 2003.
1. 2. Continuous Query 3. 4.
Continuous Query XML SQL[CQL, GSQL ] GUI[Aurora] (Change-based) (Timer-based)
CQL: Continuous Query Language Stanford STREAM The CQL Continuous Query Language: Semantic Foundations and Query Execution, TR. SQL 3(Time-based,Tuple-based, Partitioned)
Time-based Window Tuple-based Window Partitioned Window
CQL Web Web Access(TS, URL, IP) Status(TS, Load, Mem) URLURLs(Location, Description) Select Access.URL, Status.Load, URLs.Description From Access[NOW], Status[Range 5Minute], URLs Where Access.URL=URLs.Location AND Status.Load >= 0.40
DB
1. 2. Continuous Query 3. 4.
DBMS IO Hash Join Select * From R1, R2, R3 Where R1.a1 = R2.a1 AND R2.a2=R3.a2 Nested loop Join R1 R2 R3 index 10 20 1000000
DBMS Eddy
Rate-Based Query Optimization for Streaming Information Sources, Viglas SIGMOD 2002. 0.5 tuple/sec 5 tuple/sec 1 = 50 tuple/sec 2 = 500 tuple/sec Processed: 5 Transmitted: 0.5 Delay: 0 a b 2 1 1, 2 0.1 Processed: 5 Transmitted: 5 Delay: 0 Processed: 50 Transmitted: 5 Delay: 450 1 500 tuple/sec 2 Processed: 500 Transmitted: 50 Delay: 0
Eddy Eddy Eddies: Continuously Adaptive Query Processing, SIGMOD 2000. Eddy
Load Shedding Load Shedding: Random tuple drops [STREAM, Aurora] Semantic load shedding [Aurora] QoS
AuroraQoS Delay-based Drop-based Value-based 1 1 1 QoS QoS QoS 0 δ Delay delay 0 100 % messages 0 delivered Output value Delay-based Drop-based Random tuple drops 100% Value-based Semantic load shedding QoS 0
1. 2. Continuous Query 3. 4.
(Multiple Query Optimization) Continuous query
NiagaraCQ Q Q2 Q Q2 Q Q2 split S1.a2=300 S1.a2=200 S1.a2=300 split S1.a2=200 split Constant table Q1 = 300 Q2 = 200 S1.a1 =S2.a1 S1.a1 =S2.a1 S1.a1= S2.a1 S1.a1 =S2.a1 S1 S2 S1 S2 S1 S2 S1 S2
[, DEWS2003] Q1: 12 Q2: S1 Q2 8 Q1 Q2 S1 S2 0 S2 S1 12 0
[, DEWS2003]
Load Shedding STREAM Random TelegraphCQ eddy Aurora Random Semantic NiagaraCQ,
DBMS DataWarehouse DBMS DataWarehouse Linear road benchmark http://www-db.stanford.edu/stream/cql-benchmark.html