Database Reference
In-Depth Information
out-of-order negative event. Applications can thus distinguish between
the types of tuples they receive.
If ordered output is needed, additional semantic information such as
K-Slack factor or punctuation is needed to “unblock” the on-hold can-
didate sequences from being output. Two techniques are introduced to
support this. A native approach [44, 45] on handling out-of-order event
stream uses K-Slack as a priori bound on the out-of-order in the input
streams. It buffers incoming events in the input queue for K time units
until the ordering can be guaranteed. The major drawback of K-slack is
the rigidity of the K parameter that cannot adapt to the variance in the
network latencies existing in a heterogeneous RFID reader network. For
example, one reasonable setting of K may be the maximum of the aver-
age latencies in the network. However, as the average latencies change,
K may become either too large (thereby buffering unneeded data and
introducing unnecessary ineciencies and delays for the processing), or
too small (thereby becoming inadequate for handling the out-of-order
processing of the arriving events and resulting in inaccurate results). It
also requires additional space and introduces more latency before allow-
ing events being evaluated.
Another solution proposed to handle out-of-order data arrival is apply-
ing punctuation, namely, assertions inserted directly in the data stream
confirming that, for instance, a certain value or time stamp will no
longer appear in the future input streams [47, 46]. Permanent valid
is achieved because results are only reported when they are known to
be final. Relative small memory consumption is achieved by employ-
ing purging as early as possible. To safely purge data, meta-knowledge
is needed to guarantee the nonoccurrence of future out-of-order data.
A general method for meta-knowledge in streaming is to interleave dy-
namic constraints into the data streams, sometimes called punctuation.
Based on this, a conservative method is proposed in [46]. It works under
the assumption that out-of-order data may be common, and it produces
output only when its correctness can be guaranteed. A partial order
guarantee (POG) model is proposed to guarantee the correctness. Such
techniques do require some services to be created first and appropriately
inserting such assertions. Using POGs provides a simple and highly
flexible solution. If the network latency were to fluctuate over time, it
could be naturally captured by adjusting the POG generation without
requiring any change of the query engine. Also, the query engine de-
sign can be agnostic to particularities of the domain or the environment.
While it is conceivable that POGs themselves can arrive out-of-order,
a punctuate operator could conservatively determine when POGs are
released into the stream based on acknowledged receival of the events
