Transaction-time temporal databases and query languages provide a solid framework for analyzing the properties of queries over data streams. In this paper we focus on issues connected with the construction of space-bounded synopses that enable answering of continuous queries over unbounded data streams. We link the problem to the problem of query-driven data expiration in append-only temporal databases and study space bounds on synopses that are sufficient and necessary for query answering under duplicate semantics.
A considerable effort to understand many aspects
of query processing over streaming data—data that
is arriving in fragments over time—has been the
topic of research in the last several years, see e.g.,
[
The goal of this paper is to show that certain requirements, often rather desirable in such systems— such as the use of SQL-style duplicate semantics while maintaining reasonable bounds on the size of the summary data—are not possible to achieve. The paper then shows how acceptable results can be achieved by carefully limiting the expressive power of streaming query languages in which continuous queries are formulated.
As we desire to derive bounds as strong as
possible, we adopt a holistic approach to the construction
of synopses for continuous queries. Unlike other
approaches that construct synopses on a
per-physicaloperator basis (e.g., for the so called symmetric joins,
etc., [
Many of the techniques presented in this paper can be
traced to approaches designed to allow efficient data
expiration in transaction-time temporal databases
[
Note that the negative results presented in this
paper are based on information-theoretic properties of
queries and thus cannot be improved upon by more
sophisticated algorithms without resorting to
approximations. We also contrast these results with
similar results obtained for the set semantics of the same
languages where constant bounds in the length of the
stream can be obtained. In addition to the technical
results, the paper provides a strong parallel between
techniques developed for transaction-time temporal
databases [
The rest of the paper is organized as follows: Section 2 provides the basic definitions and shows the links between streaming queries and temporal databases. Section 3 shows that in general, duplicate semantics leads at least to a logarithmic lower bound on the size of the synopses, measured in the length of the data stream; it also identifies cases in which allowing duplicates in the data model leads to linear lower bounds on the size of the synopses needed to answer a continuous query. Section 4 shows fragments of query languages for which a logarithmic bound can be achieved. We conclude with identifying open issues in the area in Section 5. 2
We first review the relevant definitions in the area of
transaction-time temporal databases and link them to
querying data streams. The presentation in this
section is based on a chapter on data expiration [
We first formalize the notion of data stream as follows.
a relational schema. A data stream is a sequence
S = hS0, S1, . . . , St, . . .i where each St is a multiset of tuples conforming to σ that have arrived in S at time t. We call the multisets St states of S at t. We assume discrete integer-like time with time instants drawn from a linearly ordered set and allow multiple tuples to arrive at the same time instant. The data values forming the tuples belong to the domain of uninterpreted constants; the data domain is equipped with equality only. At any particular finite time t, we have access only to a finite prefix of S of the form
S(t) = hS0, S1, . . . , Sti We use T(t) and D(t) to denote the active temporal and data domains of a stream (prefix), respectively. Note that the active domains change with time as new data arrives on the stream. The active temporal domain T(t) is, in our setting, just the set {0, . . . , t}; the definition, however, allows to use timestamps from any linearly ordered set.
Without loss of generality, we present our results for a single data stream. However, the results immediately extend to multiple streams, e.g., by coding multiple streams by values of a distinguished attribute. This formalization shows that data stream is just a variant name for an append-only temporal database (often called a transaction-time temporal database). This observation allows us to use off-the shelf temporal query languages to query data streams. In this paper we use two-sorted first-order logic (2-FOL) to query such streams:
Let S be a data stream. The syntax of first-order streaming queries over S is given by the following grammar.
Q ::= | | |
S(t, x1, . . . , xk) xi = xj | ti < tj | ti = tj | ti > tj Q ∧ Q | ∃xi.Q | ∃ti.Q | ε Q
Q ∨ Q | Q ∧ ¬Q The ε Q subformula stands for duplicate elimination.
In addition, we assume that the queries are range restricted ; this is enforced by requiring the usual restrictions on the occurrences of equalities and inequalities and the variable-compatibility conditions for disjunctions (∨) and negations (∧¬). The semantics of the queries is defined using the usual Tarskian-style satisfaction relation extended to account for duplication; we write
S(t), θ, n |= Q to stand for “the substitution/tuple θ is an answer to Q with n duplicates, when evaluated over S(t), a prefix of S”. The full semantics of the above language is given in Figure 1. In particular, the semantics specifies how duplicates are handled in queries1. An answer to a query at time t is the multiset
StQ := {θ, . . . , θ | S(t), θ, n |= Q}.
| {z }
n Note that the value n must be unique for a given tuple θ, i.e., θ(x) functionally determines n. To simplify the definition, we assume that substitutions not present in an answer have 0 duplicates.
Again, the query language in Definition 2.2 is just a temporal query language when the stream is regarded as finite prefix of a database history. Note also, that
1We utilize a SQL-style definition of duplicates, i.e., a product for conjunctions, sum for disjunction (union) and existential quantification (projection), and difference for range-restricted negation (set difference).
S(t), θ, n |= S(t, x1, . . . , xk) if hθ(x1), . . . , θ(xk)i ∈ Sθ(t) duplicated n times S(t), θ, 1 |= xi = xj
S(t), θ, 1 |= ti < tj S(t), θ1 ◦ θ2, m · n |= Q1 ∧ Q2 S(t), θ, Pv∈D(t) nv |= ∃x.Q S(t), θ, Ps∈T(t) ns |= ∃t.Q
S(t), θ, 1 |= ε Q
S(t), θ, n + m |= Q1 ∨ Q2
S(t), θ, max(0, m − n) |= Q1 ∧ ¬Q2
if θ(xi) = θ(xj )
if θ(ti) < θ(tj )
if S(t), θ[v/x], nv |= Q
if S(t), θ[s/t], ns |= Q
if S(t), θ, n |= Q
if S(t), θ1, m |= Q1 and S(t), θ2, n |= Q2
if S(t), θ, m |= Q1 and S(t), θ, n |= Q2
if S(t), θ, m |= Q1 and S(t), θ, n |= Q2
the semantics is defined with respect to the finite
portion of the data stream; answering queries over all
potential extensions of a stream has been shown
undecidable for any reasonably powerful query language [
Q be a query without free temporal variables. An answer to a continuous query specified by Q is defined as a stream
SQ = hS0Q, S1Q, . . . , SiQ, . . .i where StQ is the answer to Q over the stream prefix S(t) as defined by the semantics in Figure 1. The restriction to queries without free temporal variables is needed to ensure that results of a query form a proper data stream. This arrangement allows for compositionally, possibility of view definitions, etc. Note also that the representation of duplicates in binary (i.e., using counts to represent the numbers of duplicates) is a more compact representation than explicitly duplicating the tuples. Thus all lower bounds derived in this paper also hold for the SQL-style representation in unary (i.e., by explicit replication of the tuples in question). 2.2
For continuous queries, it is often not feasible to store the whole data stream in computer storage. Therefore, streaming systems use summaries called synopses to remember the parts of the data stream that are necessary to generate subsequent answers to continuous queries.
query over S. A holistic synopsis for Q is a triple (∅, Δ, Γ) that satisfies the following property: QhS0, . . . , Sti = Γ(Δ(St, Δ(St−1, Δ(. . . Δ(S0, ∅)))) for any prefix hS0, . . . , Sti of S. In addition, we require that the triple (∅, Δ, Γ) can be effectively constructed from Q.
The first two components define the actual holistic
synopsis for Q as a self-maintainable materialized view
of S: the ∅ component tells us what the contents of
this view is in the beginning and the Δ component tells
us how to update the view when more data arrives in
S. The last component, Γ now generates the answers
to Q only accessing the information in the view. Note
that the definition does not specify what data model
the view uses nor what query languages are used for
the three components of the synopsis. Note that this
definition is essentially the same as the definition of a
data expiration operator for transaction-time temporal
databases [
Intuitively, we have replaced the complete prefix of
queries. Thus our aim is to minimize the size of the materialized view in terms of:
3. the size of Q.
The dependency on the length of the data stream is the most critical factor. Thus we call a synopsis bounded if it is bounded by a constant function in the length of the stream. We call a synopsis log-bounded if it is bounded by a function logarithmic in |T(t)|.
For streaming query languages that use set
semantics, results obtained for temporal databases can be
applied:
Proposition 2.5 ([
The above theorem shows that for queries under set semantics, bounded synopses exist for rather powerful query languages, in particular for the language introduced in Definition 2.2. The rest of the paper argues that bounded synopses do not exist when duplicate semantics is used for the same language and that logbounded synopses are the best we can hope for in various fragments of the first-order language under duplicate semantics. 3
Now we are ready to provide simple lower bounds that
show why the use of unrestricted duplicate semantics
for streaming queries may be expensive and, in
certain cases, not feasible at all. An Ω(log |T(t)|) lower
bound has been observed for queries with the counting
aggregate [
(∃t.S(t, a)) ∧ ¬(∃t.S(t, b)), that expresses the fact that there were more a’s than b’s in the stream S, for a and b distinct constants, yields such bound for queries with duplicates. It is easy to see using the pigeon-hole principle that a synopsis for this query needs Θ(log |T(t)|) bits.
However, it turns out that log-bounded synopses are not sufficient for first-order queries with duplicate semantics.
Theorem 3.1 There is a first-order query for which any synopsis is bounded from below by Ω(|T(t)|). Proof (sketch): Consider the query ε∃t1, t2.t1 < t2 ∧¬((∃x.S(t1, x)) ∧ ¬(∃x.S(t2, x))) ∧¬((∃x.S(t2, x)) ∧ ¬(∃x.S(t1, x))) The query expresses the condition two states of S contain the same number of tuples. Now consider a prefix of a data stream S(t) such that Si contains the value a duplicated mi times, mi 6= mj for 0 ≤ i 6= j ≤ t. To be able to answer the above query when the stream is extended by the state Sn+1 we need at least a set of values {m0, . . . , mt}. To represent this set we need at least
t X log(mi) ≥ t · log(min{m0, . . . , mt}) ∈ Ω(|T(t)|) i=0 bits.
The unfortunate consequence of this lower bound is that, in general, the best synopsis for first-order queries under duplicate semantics are essentially as big as the original data stream (and thus we may be better off just storing the stream itself).
We now investigate cases in which logarithmic bounds on the size of holistic synopses can be obtained. To this end, we need to restrict the streaming query languages. We consider two different fragments of first-order logic: 1. positive first-order queries, and 2. temporal logic queries.
In both cases our aim is to make the proof of Theorem 3.1 inapplicable. In the first case by disallowing negation and in the second by disallowing multiple temporal contexts to exist at the same time. 4.1
We start with the case of the past fragment of the firstorder temporal logic (FOTL), a logic based on implicit access to the temporal attribute of tuples using modal operators. This way the number of coexisting temporal contexts is limited while still commanding a sufficient expressive power2. The syntax of the language is defined as follows:
Let S be a data stream. The syntax of FOTL queries over S is given by the following grammar.
Q ::= | | |
S(x1, . . . , xk) | xi = xj Q ∧ Q | ∃xi.Q | ε Q Q ∨ Q | Q ∧ ¬Q
Q since Q | 5Q Note that formulas of FOTL do not use variables ranging over the temporal domain; handling of this aspect of the queries is encapsulated in the temporal operators since and 5 (previous time). Thus the semantics is now defined with respect to an evaluation point using a satisfaction relation
S(t), θ, s, n |= Q
which, similarly to Definition 2.2, states that the tuple
θ is an answer to Q at time s with n duplicates in S(t).
Note that the time point s may be different from t; this
allows referring to past states of the data stream S in
queries. The semantics of FOTL mimics that of 2-FOL
introduced in Figure 1: all the standard first-order
connectives and quantifiers are evaluated per state of
S (using the so-called snapshot semantics [
S(t), θ, ns2 , s2 |= Q2 for some s2 < s, ns2 > 0 and S(t), θ, ms1 , s1 |= Q1 for all s1 < s2 ≤ s, ms1 > 0 For the previous time operator, 5Q, the duplicate semantics is defined as follows:
S(t), θ, s, n |= 5Q if S(t), θ, s − 1, n |= Q and s > 0 An answer to a continuous query Q at time t is defined as the multiset {θ, . . . , θ | S(t), θ, t, n |= Q}. | {z }
n The two variants, since1 and since2, differ in the way they handle duplicates: since1 counts the maximal number of the answers θ satisfying Q1 since Q2 was true; since2 counts the number of times the tuple θ satisfies Q2 such that Q1 was true since then3.
Additional temporal connectives can be derived from the since and 5 operators; again, the handling of duplicates is the only concern here.
Example 4.2 The sometime in the past (3) connective can be defined as follows: 31Q = true since1 Q 32Q = true since2 Q The two variants differ again in how duplication of results is defined: in the first case it indicates how far in the past was the earliest Q has been and the second case how many times Q has been true in the past4. Again additional connectives can be defined by combining the above two. For example, should we wish to know how far in the past the latest Q was we can write (¬Q) since1 Q.
3Similar to the duplicate semantics for SQL, this is just a particular a way of choosing how many duplicates are in an answer to a particular query. The definitions above work correctly with the rest of the technical development in this paper. A comprehensive study of various possibilities to define duplication of tuples for temporal queries is beyond the scope of this paper. 4Assuming the constant true is not duplicated.
Note that one might be tempted to define the duplicate semantics or the sometime in the past (3) operator, e.g., as follows: S(t), θ, t, n |= 3Q if S(t), θ, s, n |= 3Q for some s < t. This definition would seemingly allow formulating the query “were there two time instants with the same number of elements in the stream? ”. However, it is important to see that such a definition is incompatible with the definition of duplicate semantics: it allows assigning two different duplicities to the same tuple— this is illegal under the duplicate semantics.
To define a synopsis for a given FOTL formula we use the following identities: Lemma 4.3 Let S be a data stream and Q1 and Q2 FOTL queries. Then
S(t), θ, s, n + m |= Q1 since1 Q2 if – S(t), θ, s − 1, n |= Q1 since1 Q2 and – S(t), θ, s, m |= Q1.
S(t), θ, s, m |= Q1 since1 Q2 – S(t), θ, s − 1, n |= Q2, – S(t), θ, s − 1, l 6|= Q1 since1 Q2, and – S(t), θ, s, m |= Q1.
S(t), θ, s, n + m |= Q1 since2 Q2 if – S(t), θ, s − 1, n |= Q1 since2 Q2, – S(t), θ, s − 1, m |= Q2, and – S(t), θ, s, l |= Q1.
S(t), θ, s, m |= Q1 since2 Q2 if – S(t), θ, s − 1, n 6|= Q1 since2 Q2, – S(t), θ, s − 1, m |= Q2, and – S(t), θ, s, l |= Q1.
S(t), θ, s, n |= Q1 since2 Q2 if – S(t), θ, s − 1, n |= Q1 since2 Q2, – S(t), θ, s − 1, m 6|= Q2, and – S(t), θ, s, l |= Q1.
Proof (sketch): Immediate from the definitions.
With the help of these identities we can modify the
approach to bounded checking of past FOTL constraints
[
The above upper bound matches the lower bound from Section 3 as the query “have there been more a values than b values in the stream S” can be formulated in FOTL using the formula
(32S(a)) ∧ ¬(32S(b)).
Thus the above technique is (worst-case) optimal up to a constant factor (w.r.t. |T(t)|).
Example 4.6 The auxiliary views for the query above are R32S(a)(n) and R32S(b)(n); note that both the views have single integer attribute as the original subqueries are closed formulas.
The Δ operator is defined as
R32S(a) := {n + m | S(t), m, t |= S(a), t
R(t), n, t − 1 |= R32S(a)} where the stream R is the stream generated for the auxiliary relations. Similar definition is used for
lations in this example are 0-ary—conceptually they contain the true tuple duplicated an appropriate number of times; the actual binary representations therefore contain just one integer value each.
The Γ part is then defined as R32S(a) ∧ ¬R32S(b). 4.2
Queries in FOTL provide a powerful way of querying
data streams. They also generalize the so called
windowed queries in a natural way. However, there is a
mismatch between streaming query languages that use
SQL-like syntax (with explicit access to the time
instant attributes [
In this section we therefore look on common sublanguages of 2-FOL, namely on conjunctive queries (CQ) and unions of conjunctive queries (UCQ). We show that, in these cases the technique developed for FOTL can be adopted to CQ and UCQ.
Definition 4.7 (Conjunctive Query) A conjunctive query is an expression of the form
∃t1, . . . , tk, y¯.S(t1, x¯1), ∧ . . . ∧ S(tk, x¯k) ∧ φ ∧ ψ where x¯i are vectors of data variables, ϕ is a conjunction of equalities over the data variables and ψ a ordering condition over the temporal variables. The query can be potentially prefixed by duplicate elimination. Note that we require the answers to CQ not to contain any free temporal variables in order for them to serve as continuous queries over data streams.
The construction of synopses for CQ proceeds in two steps: 1. First a given CQ is rewritten to an equivalent union of CQs, such that the condition ψ in each of the constructed queries imposes a linear order among the variables t1, . . . , tk. 2. Second, each of the above queries is translated to FOTL and then the synopsis construction for FOTL is used.
This approach is supported by the following two lemmas: Lemma 4.8 Let Q be a CQ of the form
∃t1, . . . , tk, y¯.S(t1, x¯1), ∧ . . . ∧ S(tk, x¯k) ∧ φ ∧ ψ. Then there is a finite set of CQ such that • the (duplicate preserving) disjunction of these CQ is equivalent to the original CQ and • the subformulas ψ in these queries impose a linear order on valuations of the variables t1, . . . , tk. Proof (sketch): Let Ψ be the set of all formulas that express linear orders over t1, . . . , tk consistent with ψ. This set is finite and due to the law of excluded middle, no two elements of Ψ can be made true by the same valuation. Thus the set of CQ {∃t1, . . . , tk, y¯.S(t1, x¯1), ∧ . . .∧S(tk, x¯k)∧φ∧ϕ | ϕ ∈ Ψ} fulfills the requirements of the Lemma.
Thus, for each two variables, we have ti < tj, ti = tj, or ti > tj. This allows us to construct a FOTL formula by using the 32 connective to simulate the inequalities. Hence the following Lemma: Lemma 4.9 Let Q be a CQ of the form
∃t1, . . . , tk, y¯.S(t1, x¯1), ∧ . . . ∧ S(tk, x¯k) ∧ φ ∧ ϕ. in which ϕ imposes a linear order on the temporal variables t1, . . . , tk. Then there is an equivalent formula in FOTL.
We replace the CQ by a FOTL Proof (sketch): query of the form ∃y¯.3(S(x¯i1 ) ∧ . . . ∧ S(x¯il )∧ 3(S(x¯j1 ) ∧ . . . ∧ S(x¯jl0 ) ∧ . . .
3(S(x¯k1 ) ∧ . . . ∧ S(x¯kl00 )∧) . . .)) where the subscripts i1, . . . , il refer to those conjuncts in the original query that are first in the linear ordering of temporal variables, j1, . . . , jl0 to the second, and k1, . . . , kl00 to the last, i.e., the linear order of the temporal variables was ti1 = . . . = til > tj1 = . . . = tjl0 > . . . > tk1 = . . . = tkl00 in ϕ.
We finish the construction by applying the approach to construction of bounded synopses introduces in Section 4.1. The use of this approach for UCQ is immediate. 5
In this paper we have shown that duplicate semantics causes a severe difficulties in constructing bounded synopses for processing continuous queries. Indeed, even simple queries may require a synopsis (linearly) proportional to the length of the original stream— which defeats the usefulness of such synopsis. We have also developed restricted fragments of streaming queries that allow logarithmically-bounded synopses to be used and shown how such synopses can be constructed. 5.1
There are many directions of research to pursue in this direction. Among these are:
In this paper we mainly considered the standard SQL-style approach of defining duplicate semantics of queries. However, beyond compatibility concerns, there is no principal reason why other numerical functions, such as the “min” and “max” functions, couldn’t be used to define the duplicate semantic for conjunctions and disjunctions, respectively. The main open question is whether a plausible duplicate semantics for first-order queries to which Theorem 3.1 doesn’t apply exists.
We have shown two sublanguages of 2-FOL queries for which log-bounded synopses can be constructed. However, it is not clear whether it is possible to syntactically characterize those 2-FOL queries (possibly up to query equivalence) for which log-bounded synopses exist.
Aggregates. Another question relates to the possibility of introducing aggregate functions into the query language—again, the best lower bounds we know today are logarithmic in the length of the stream. However, the techniques proposed in this paper cannot cope with aggregates mainly as aggregate functions introduce new domain elements.
tion of research is to study fragments of query languages for which the possible result semantics is viable.
Also, the focus of this paper was on developing techniques that allow precise answers to continuous queries to be computed. Another direction of research is to consider appropriate ways to approximate the answers and trade-offs between quality of the approximations and space needed for storing synopses. While there has been a large amount of work in this area, surveying the issues connected with approximate query answers is beyond the scope of this paper.