## 4 Techniques of In-Network Join Processing
### Techniques without Filtering of Non-Joinable Tuples  
In this section, we present a survey of the join implementations named _Distribute-Broadcast Join_[11], _Mediated Join_[3,4], _Distributed Index-Join_[8], _Distributed Hash-Join_[8], and _Pair-wise Join_[22,23]. They do not support non-joinable tuple filtering before the final join. They are focusing on other issues including adaptation of the conventional join implementations to WSNs, the optimal location of the join nodes, indexing, and the optimal join initiation. **Distribute-Broadcast Join. ** In [11], [PERSON] and [PERSON] considered an inter-region join \(R\bowtie S\) to be executed as a continuous join query. They considered two query models. First, \(R\) and \(S\) are assumed to be _static_ and the execution of such a static join is repeated. Second, \(R\) and \(S\) are _streaming_ and the join is modeled as a sliding window join. In the first model, join processing proceeds as follows: All the tuples of \(R\) are shipped and distributed uniformly in one or more nodes that are located in a designated region \(P\) of the network, which is called a _join region_. Then, the tuples of \(S\) are broadcast to \(P\). At each node of \(P\), join processing is performed and the matched tuple pairs are transmitted to the query sink. In such a protocol called _Distribute-Broadcast Join_ (shown in Figure 4(a)), \(R\) and \(S\) respectively play the role of the inner and the outer relation of a nested-loop join. In [11], the _optimal_ join region with which the total communication cost for _Distribute-Broadcast Join_ is minimized was investigated. If the join region is to be simply constructed as a _circular region_ around a point \(C\) in the network, the optimal location of \(C\) is determined such that the weighted sum of the distances from \(C\) to region \(R\), to region \(S\), and to the query sink \(Q\) is minimized, where the weights are the sizes of \(R\), \(S\), and \(R\bowtie S\). Such an optimal point \(C\) lies within the triangle formed by region \(R\), region \(S\), and the query sink \(Q\) (\(\Delta\)_RSQ_), and this particular join implementation is called _Centroid Join_. If the join regions including the ones in geometrically non-trivial shape (_i.e._, other than just a circular region) are considered as well, the optimal join region \(\mathcal{P}\) is computed based on the sizes of \(R\), \(S\), and \(R\bowtie S\) assuming that the network is _dense_ enough for a node to be found at any point in the network. \(\mathcal{P}\) is formed using three points \(C_{r}\), \(C_{s}\), and \(C_{q}\) which are related respectively to region \(R\), region \(S\), and the query sink \(Q\). They lie within the triangle \(\Delta\)_RSQ_. Figure 4(b,c) show two possible shapes of \(\mathcal{P}\). In Figure 4(b), \(\mathcal{P}\) is formed of two curved paths \(<\)\(C_{r}\), \(C_{q}\)\(>\) and \(<\)\(C_{s}\), \(C_{q}\)\(>\), a line segment \(\overline{C_{q}Q}\), and a circular region \(P_{O}\) of appropriate radius around \(Q\). In Figure 4(c), \(\mathcal{P}\) is formed of two curved paths \(<\)\(C_{r}\), \(C_{q}\)\(>\) and \(<\)\(C_{s}\), \(C_{q}\)\(>\), and only a _part_ of the line segment \(\overline{C_{q}Q}\) (without the circular region around \(Q\) of Figure 4(b)). In the case of not sufficiently dense networks, the join region \(P\) is defined based on the paths traversed by location routing protocols GPSR and TBF. TBF (trajectory-based forwarding) protocol [32] could be used in particular to traverse the curved paths \(<\)\(C_{r}\), \(C_{q}\)\(>\) and \(<\)\(C_{s}\), \(C_{q}\)\(>\) of the optimal join region \(\mathcal{P}\). For reasonably dense sensor networks, the actual join region \(P\) yielded would be close to the originally intended optimal join region \(\mathcal{P}\). Figure 4: **(a)** Distribute-Broadcast Join; **(b)** A possible shape of an optimal join region; **(c)** Another possible shape of an optimal join region.