## 3 Overview of Join Processing in WSNs
### Join Types
For a sensor relation \(R\), let \(\mathrm{w}_{R}\) denote a _time-based_ window [19] of \(R\) (in this section, we mention only the time-based window because we assume that temporal predicates are specified on the timestamp attribute. The description of the join types associated with temporal predicates in this section can be extended to incorporate the tuple-based window as well. \(\mathrm{w}_{R}\) is a subset of \(R\) restricted by a time interval. A join query \(R\bowtie S\) in WSNs is required to specify \(\mathrm{w}_{R}\) and \(\mathrm{w}_{S}\) so that each tuple of \(R\) (\(S\)) may be joined with \(\mathrm{w}_{S}\left(\mathrm{w}_{R}\right)\) instead of with \(S\left(R\right)\). Selection predicates or join predicates on the _timestamp_ of the sensor readings can specify such a window as described below. Three types of windows can be specified: _fixed, sliding_, and _jumping_. The time interval of a _fixed_ window is specified by _selection_ predicates on timestamps. For a join \(R\bowtie S\) to be executed as a _one-shot_ query, a pair of fixed windows \(\widetilde{\mathrm{w}}_{R}\) and \(\widetilde{\mathrm{w}}_{S}\) are specified such that the join result is \(\widetilde{\mathrm{w}}_{R}\bowtie\widetilde{\mathrm{w}}_{S}\). The time interval [\(t_{l}\), \(t_{2}\)] associated with \(\widetilde{\mathrm{w}}_{R}\) (or \(\widetilde{\mathrm{w}}_{S}\)) is specified such that \(t_{l}{\leq}\,t_{2}\,{\leq}\,t\), where \(t\) is the point of query submission in time. The queries in Figure 1(a,b) is for such a one-shot join [2, 3, 4]. Note that \(\widetilde{\mathrm{w}}_{R}\) and \(\widetilde{\mathrm{w}}_{S}\) are _static_ (_i.e._, stored) rather than _streaming_ in such a one-shot join. Fixed windows can be used for a _continuous_ join as well if their time intervals are the future ones. The example query in Figure 1(c) is for such a continuous join [5], where each window contains the tuples that are to be produced in the next 30 minutes. Thus, the windows in such a continuous join are streaming ones, and the window size (_i.e._, 30 minutes) is the _lifetime_ of the query. Figure 2: Inter-region join \(R\bowtie S\), where each small circle denotes a sensor node. The time interval of a _sliding_ window is specified by _join_ predicates on timestamps. For a join \(R\Join S\) to be executed as a continuous query, a pair of sliding windows \(\widehat{\ww}_{R}\) and \(\widehat{\ww}_{S}\) are specified such that the join is modeled as a _time-based sliding window join_[19]. This model of continuous join in WSNs has received much attention in the literature [6; 8; 11; 20; 22; 23]. A special case of a sliding window join is when one of \(\widehat{\ww}_{R}\)and \(\widehat{\ww}_{S}\) is not specified. For a continuous join \(R\Join S\) where a tuple of \(R\) (e.g., representing an event \(e_{r}\)) is joined only with the future tuples of \(S\) (e.g., representing future events \(e_{s}\) related to \(e_{r}\)) but not with the past tuples of \(S\), only one sliding window \(\widehat{\ww}_{R}\) needs to be specified. When a tuple of \(S\) is produced, it is joined with \(\widehat{\ww}_{R}\). However, it is not kept because no window of \(S\) is maintained. When a tuple of \(R\) is produced, it is not joined with \(S\) at the moment but kept in \(\widehat{\ww}_{R}\). The example query in Figure 1(d) is for such a continuous join [6]. For a join \(R\Join S\) modeled as a time-based sliding window join, the window \(\widehat{\ww}_{R}\) (\(\widehat{\ww}_{S}\)) is already a stored subset of \(R\) (\(S\)) when it is scanned for a join with a tuple of \(S\) (\(R\)) just produced. However, we regard \(\widehat{\ww}_{R}\) and \(\widehat{\ww}_{S}\) as streaming because they are sliding continuously. In the context of _acquisitional_ query processing in TinyDB [25], a one-shot join query can be expressed _without_ temporal predicates. In the query in Figure 1(e), for example, no temporal predicate is specified in the WHERE clause. It is a one-shot join query \(R\Join S\) as declared by the ONCE clause [26].