## 3 Overview of Join Processing in WSNs
### Join Types  
A join query in WSNs is often characterized by its selection/join predicates on the _auxiliary_ attributes. The auxiliary attributes such as the location of a sensor node and the timestamp of the sensor readings represent the spatio-temporal dimension of the sensor readings. The spatio-temporal predicates on these attributes are important factors of a join query that affect its implementation. **Spatial predicates. ** For a join query \(R\bowtie S\), let \(\mathbb{R}\) (S) denote the set of sensor nodes which produce the tuple stream of \(R\) (S). Table 1 summarizes notations in the paper. A spatial predicate in a join query is the one on the attribute _location_ (_i.e._, geographic coordinates) of the sensor nodes. It restricts the sensor nodes that are to participate in the query. Spatial predicates can be specified as selection predicates or as join predicates. An example of the former is the predicate \"S\({}_{1}\)._location_**IN** Region_Specification(R\({}_{1}\))\" in the WHERE clause of the query in Figure 1(b). An example of the latter is the predicate \"distance(S\({}_{1}\).location, S\({}_{2}\).location) < \(\delta\)\" in the WHERE clause of the query in Figure 1(e). For a join query \(R\bowtie S\), only selection spatial predicates on \(R\) (and/or on \(S\)) can be specified. Queries in Figure 1(a-c) are of such type. Since there is no join spatial predicate, \(\mathbb{R}\) and \(\mathbb{S}\) can be easily identified assuming that each node knows its location. Since \(\mathbb{R}\) (S) covers a fixed _region_ of the network denoted as \(R\) (\(S\)), such type of join is an _inter-region join_. An instance of an inter-region join is shown in Figure 2. In an inter-region join \(R\bowtie S\), it is typical that regions \(R\) and \(S\) do not overlap \begin{table}
\begin{tabular}{l c} \hline \hline
**Symbol** & **Description** \\ \hline \(R\), \(S\) & Join operand relations for a join query \(R\bowtie S\) \\ \(\mathbb{R}\) (S) & A set of sensor nodes which produce the sensor tuple stream of \(R\) (S). Each node in \(\mathbb{R}\) \\  & (S) satisfies the predicates on geographic location of the nodes specified in the query. \\ \(R\) (\(S\)) & A region of the sensor network that consists of the nodes in \(\mathbb{R}\) (S) \\ \(\mathrm{w}_{R}\) (\(\mathrm{w}_{S}\)) & A time-based window of \(R\) (\(S\)). It is either fixed or sliding. \\ \(\overline{\mathrm{w}}_{R}\) (\(\overline{\mathrm{w}}_{S}\)) & A time-based _fixed_ window of \(R\) (\(S\)) \\ \(\overline{\mathrm{w}}_{R}\) (\(\overline{\mathrm{w}}_{S}\)) & A time-based _sliding_ window of \(R\) (\(S\)) \\ \hline \hline \end{tabular}
\end{table} 
Table 1: Notation. with each other as shown in Figure 2. An important property of an inter-region join is that a node that has received an inter-region join query can determine if it is to participate in the query without communicating with other nodes. The processing of an inter-region join has received so far the most attention in the literature [2, 3, 4, 5, 8, 11, 12, 20, 21], and several techniques that are suitable for such a join type have been proposed. If a join query specifies _join_ spatial predicates, they not just restrict the sensor nodes that are to participate in the query but also restrict _pairing_ among the sensor nodes for the join. Queries in Figure 1(d,e) are of such type. In general, a node that has received this type of query cannot determine if it is to participate in the query without communicating with other nodes. This could make in-network join implementation more difficult compared to an inter-region join. This type of join query was investigated in [6, 7, 22, 23, 24]. **Temporal predicates. ** Since a sensor relation is an _unbounded_ stream of sensor tuples, a full evaluation of a join between two sensor relations is neither possible nor practical.