## 4 Techniques of In-Network Join Processing
### Techniques with Filtering of Non-Joinable Tuples
(**a**) Relevant portion of the routing tree for an inter-region join \(R\bowtie S\) and the shipping of \(R[A]\) for performing semijoin \(R\rtimes S\); (**b**) Selective forwarding of \(R[A]\) in _PartitionJoin_; (**c**) Recursive application of selective forwarding of \(R[A]\) in _PartitionJoin_. _SynopsisJoin_ and _fullSynopsisJoin_ are the same as _PartitionJoin_ except that a Bloom filter [31] of the joining attribute is forwarded as a synopsis instead of the values of the joining attribute. Since a Bloom filter is much smaller, the cost of the semijoin is decreased while the benefit could be increased. _SynopsisJoin_ and _fullSynopsisJoin_ are regarded as efficient adaptations of the conventional Bloomjoin [33] or hash-semijoin [34,35] to WSNs. The in-network strategies of _INJECT_ can be employed only in the case that each of the nodes \(r_{R}\), \(c_{T}\), \(r_{S}\) in Figure 9(a) is equipped with the memory whose capacity is sufficient enough to buffer the data it is supposed to receive and hold. For example, with _SynopsisJoin_, \(r_{S}\) should be able to store \(R[A]\) as well as \(R\rtimes S\). _Two-Phase Self-Join (TPSJ)_. In [6], [PERSON] _et al_. proposed _TPSJ_ to answer a continuous join query. It executes a theta-join query \(q\) of the form:  
\[(\sigma_{P}\,R)\bowtie_{A\theta B\,\wedge\,T(h)}R \tag{3}\]  
where \(P\) is a selection predicate on the sensor relation, and _T(h)_ is a temporal predicate to specify a time-based sliding window [19] where \(h\) is the window size. The semantics of \(q\) is defined as follows: Let \(R_{1}=\sigma_{P}\,R\). \(R_{1}\) is a set of tuples produced at the same time instance, say, at \(t\) throughout the sensor network. Then,  
\[q=R_{1}\bowtie_{A\theta B\,\wedge\,T_{2}(t,h)}R, \tag{4}\]  
where the temporal predicate \(T_{2}(t,h)\) restricts \(R\) to those tuples produced in the time interval [\(t\), \(t\)+\(h\)]. The join predicate \(A\theta B\) is checked between the tuples of \(R_{1}\) and those of \(R\) satisfying \(T_{2}(t,h)\). The join processing proceeds in two phases after \(q\) is rewritten at the base station by _decomposing_\(q\) into two subqueries \(q_{1}\) and \(q_{2}\), where \(q_{1}=\sigma_{P}\,R\) and \(q_{2}=R_{1}\bowtie_{A\theta B\,\wedge\,T_{2}(t,h)}R\):  
* **Phase 1. **\(q_{1}\) is injected into the network, \(R_{1}\) is obtained and sent to the base station. Note that \(R_{1}\) received at the base station satisfies selection predicate \(P\) but has _not_ been checked for join predicate \(A\theta B\). * **Phase 2. ** The base station broadcasts \(q_{2}\) and \(R_{1}\) to the network. At each node \(N\), the semijoin \(R_{1}\rtimes_{A\theta B}R^{N}\) is carried out, where \(R^{N}\) is the subset of \(R\) produced at \(N\) in the time interval [\(t\), \(t\)+\(h\)]. This process fully reduces the sliding window of \(R\) (to be exact, \(\sigma_{T_{2}(t,h)}\,R\)) to \(R_{2}\). \(R_{2}\) is sent to the base station where \(R_{1}\bowtie_{A\theta B}R_{2}\) is conducted to obtain the final join result. _TPSJ_ is devised to detect events in monitoring applications. With a selection predicate, the candidate sensor readings (_i.e._, \(R_{1}\)) that represent the event of interest are collected first. Then, \(R_{1}\) triggers the checking of the subsequent readings to see if they are correlated with \(R_{1}\). _TPSJ_ would be effective when the selection predicate \(P\) is highly selective, because all the tuples of \(R_{1}\) are sent to the base station in the first phase. In _TPSJ_, node failures are handled by restructuring the routing tree. When a node fails to hear from its parent for some period of time, it chooses a new parent. For proper restructuring, each node maintains information on its neighbor nodes such as the number of messages that it has received from a neighbor and the number of hops that a neighbor is away from the root. Each node also periodically broadcasts a message to its neighbors to inform them that it is active. **SENS-Join. ** In [7], [PERSON] _et al_.