28:6
•
B. Carminati et al.
As introduced in Section 2, we adopt the data-flow paradigm to model
queries. Therefore, we present the query model by introducing the set of sup-
ported operators, that is, supported nodes in the query graph. In particular,
the core query model supports the well-know relational operators, like selec-
tion and projection, plus additional operators defined to handle window-based
operations. Moreover, it contains two further operators, useful for modeling a
query as a graph, that is, the IN and OUT operators.
In the following text, we provide a description of the supported operators.
In particular, each operator has an associated set of parameters, conveying
the information needed to evaluate the operator (e.g., the predicates to be
evaluated in case of a selection operator). In addition to their descriptions,
with some operators, we also associate an algebraic expression.
Input: IN operator. The IN operator models the streams entering in the query.
As such, the IN operator has no entering edges and only one exiting stream. The
IN operator has two associated parameters: Name, containing the name of the
input stream, and ATTs, storing the name of the attributes of the input stream.
Output: OUT operator. This operator generates the stream resulting from the
evaluation of the query. It has only one entering edge and has no exiting edges,
since it is assumed that all incoming tuples are passed directly to some external
application, like in real DSMSs. The OUT operator has an associated parameter,
called Name, containing the name of the resulting stream.
Projection: π operator. The projection operator performs the projection of
streams according to selected attributes. We define the projection of a stream
S over a set of attributes {A
1
,...,A
n
}∈ Att(S) as a stream S’ consisting of
all tuples of S from which attributes not belonging to {A
1
,...,A
n
} have been
pruned. In a query graph, the projection operator π has a unique entering edge,
representing the stream over which the projection is performed, and generates
a unique exiting edge, that is, the stream resulting from the projection. The π
operator has a parameter ATTs, containing the set of attributes {A
1
,...,A
n
} to
be extracted. The expression corresponding to the projection of a stream S over
a set of attributes {A
1
,...,A
n
}∈ Att(S) is π(A
1
,...,A
n
)(S).
Selection: σ operator. This operator selects specific tuples within a stream.
More formally, given a stream S and a predicate P over attributes in Att(S),we
define the selection of S with respect to P as a stream S’ consisting of all and only
those tuples in S that satisfy predicate P. Thus, the selection operator σ has a
unique entering edge and a unique exiting edge, that is, the stream containing
only the input tuples satisfying the selection predicate. The selection predicate
is contained into the σ parameter EXPs, and it is expressed through an SQL-like
syntax. The corresponding expression is σ (P)(S).
Example 3.1. Throughout this article, we consider examples from
the military domain. We assume that the streams are used to monitor
positions and health conditions of platoon’s soldiers. Hereafter, we con-
sider two data streams, Position and Health, with the following schemas:
Position(ts,SID,Platoon,Pos), Health (ts,SID,Platoon,Heart,BPressure),
ACM Transactions on Information and System Security, Vol. 13, No. 3, Article 28, Publication date: July 2010.