• Persistent Data storage
• Relatively static records
• (Typically) no predefined notion of time
• Complex one-off queries

• Data arrives in real time
• Data is ordered (implicitly by arrival time or explicitly by timestamp)
• Too much data to store
• Data never stops coming
• Ongoing analysis of rapidly changing data

Application domains

• Network monitoring and traffic engineering
• Sensor networks, RFID tags
• Telecommunication call records
• Financial applications
• Web logs and click streams
• Manufacturing processes

• A potentially unbounded sequence of tuples
• Transactional data streams: log interaction between entities
• Credit card: purchases by consumers from merchants
• Telecommunications: phone calls by callers to dialed parties
• Web: accesses by clients of resources at servers
• Measurement data streams: monitor evolution of entity states
• Sensor networks: physical phenomena, road traffic
• IP network: traffic at router interfaces
• Earth climate: temperature, moisture, etc.

• One-time queries
• Run once to completion over the current dataset
• Continuous queries
• Issued once and then continuously evaluated over a data stream
• Notify me when the temperature drops below X
• tell me when prices of stock Y > 300

• Queries produce/refer to relations and streams
• Based on SQL, with the addition of:
• Streams as new data type
• Continuous instead of one-time semantics
• Windows on streams (derived from SQL-99)
• Sampling on streams (basic)

• Construct query plan based on relational operators, as in an RDBMS
• Selection 
• Projection
• Join
• Aggregation (group by)
• Combine plans form continuous queries (reduce redundancy)
• Stream tuples through the resulting network of operators

• Some full relation operators can work on a tuple at a time
• Count, sum, average, min, max (even with group by)
• (Order by, however, can't)

[image]

Intersection, difference, product, join

(Union, however, can be evaluated tuple-by-tuple)

• No output until entire input seen, but streams are unbounded
• Joins may need to join tuples that are aritrarily far apart

• Some relational operators can work directly on streams
• Selection, projection, union, some aggregates
• Some relational operators need to work on relations
• Join, product, difference, interseciton, other aggregates
• Stream-to-relation operators
• Windows
• Relation-to-stream operators
• Istream, Dstream, Rstream

• Mechanism for extracting a finite relation (synopsis) from an infinite stream
• Various window proposals for restricting operator scope.
• Windows absed on ordering attribute (e.g. last 5 minutes of tuples)
• Windows absed on tuple counts (e.g. last 1000 tuples)
• Windows based on explicit markers e.g. punctuations)
• Variants (e.g. partitioning tuples in a window)
• Various window behaviours
• Sliding, tumbling

• Consider a stream-based join operation
• a conventional join over a pair of windows on the input streams
• outputs a stream of tuples joined from the input streams

• DBMS deals with finite relations
• Query evaluation should produce all results for a given query
• DSMS deal with unbounded data streams
• May not be possible to return all results for a given query
• Trade-off between resource use and comlpeteness of result set
• Size of buffers used for windows is one example of a parameter that affects resource use and completeness
• Can further reduce resource by randomly sampling from streams

• Insert Stream (Istream)
• Whenever a tuple is inserted into the relation, emit it on the stream
• Delete Stream (Dstream)
• Whenever a tuple is deleted from the releation, emit it on the stream
• Relation Stream (Rstream)
• At every time instant, emit every tuple in the relation on the stream

SELECT Istream(*)

FROM S [rows unbounded] 

WHERE S.A > 10

S is converted into a relation (of unbounded size)

Resulting relation is converted back to a stream via Istream

SELECT *

FROM S

WHERE S.A > 10

S is a stream - query plan involves only selection, so window is now unnecessary

SELECT *

FROM S1 [rows 1000], S2[range 2 minutes]

WHERE S1.A > S2.A and S1.A > 10

Windows specified on streams:

• Tuple based sliding window - [rows 1000]
• Time-based sliding window - [range 2 minutes]

SELECT Rstream(S.A, R.B)

FROM S1 [now], R

WHERE S1.A = R.A

• Query probes a stored table R based on each tuple in streams S and streams the result
• [now] - time based sliding window containing tuples in the last time step

• Traditionally relation cardinalities used in query optimizer
• Minimize the size of intermediate results
• Problematic in a streaming environment
• All streams are unbounded = infinite size
• Need novel optimization objectives that are relevant when input sources are streams 
• Stream rate based (e.g. NiagaraCQ)
• Resource-based (e.g. STREAM)
• QoS based (e.g. Aurora)
• Solution: Continuous adaptive optimization