## 4 Techniques of In-Network Join Processing
### Techniques with Filtering of Non-Joinable Tuples  
In this section, we present a survey of the join implementations named _Synopsis Join_[2], _Local Semijoin_[4], _INJECT_[21], _TPSJ_[6], _SENS-Join_[7], _CJF_[24], _PEJA_[5], and _SRJA_[12]. Their common feature is in-network filtering of non-joinable tuples. _Synopsis Join_. In [2], [PERSON] _et al_. proposed _Synopsis Join_ to answer a one-shot join query. It executes an inter-region equi-join \(R\bowtie_{A=B}S\). A distributed variant of the semijoin is employed to fully reduce both \(R\) and \(S\). Let \(v\)-_tuple_ denote a tuple of \(R\) or \(S\) whose joining attribute value is \(v\). Then, \(v\)-tuples of \(R\) are to be joined with \(v\)-tuples of \(S\). The join proceeds as follows:  
Each joining attribute value \(v\) of the \(v\)-tuples is geographically hashed to be sent to a sensor node \(N_{v}\) located in a region \(T\) of the network, where the joinability of \(v\) is to be checked. The value \(v\) is sent as a part of the _synopsis_ of a local relation at the sensor node where the corresponding \(v\)-tuple is stored. In [2], a _histogram_ is used as an example of the synopsis, which stores \(<\!v\), the count of \(v\)-tuples\(>\) pairs with other auxiliary information such as location information on the nodes storing the corresponding \(v\)-tuples. The location of region \(T\) is determined such that the transmission cost for sending the synopses to be imposed on region \(R\) would get roughly equal to that on region \(S\). Thus, \(T\) is located between \(R\) and \(S\) but closer to the bigger region of the two. If \(v\) turns out a joinable value (that is, \(v\) is in both \(R[A]\) and \(S[B]\)), \(N_{v}\) notifies this to all the nodes of \(R\) and \(S\) storing the \(v\)-tuples. This notification is done with a location routing protocol like GPSR, for the location information of the \(v\)-tuples has been collected at \(N_{v}\). With this notification, \(R\) and \(S\) are fully reduced. For each joinable value \(v\) in \(R[A]\) or in \(S[B]\), the final join among the corresponding \(v\)-tuples is conducted at a designated sensor node \(N_{v\!f}\), to which the \(v\)-tuples of regions \(R\) and \(S\) are sent. The final join result is sent to the query sink \(Q\). The location of \(N_{v\!f}\) is included in the aforementioned notification message sent by \(N_{v}\). Since \(N_{v}\) has collected the location information of all the \(v\)-tuples of \(R\) and \(S\), it can designate \(N_{\forall}\) such that the communication cost of the remaining steps can be minimized [2]. Figure 8 depicts the process of _Synopsis Join_, focusing on the aspect of non-joinable tuple filtering and the final join. _Local Semijoin_. In [4], [PERSON] _et al_. proposed the _Local Semijoin_ to answer a one-shot join query. It executes an inter-region equi-join R \(\bowtie_{A=B}\) S. A variant of semijoin is employed to fully reduce both R and S. In region R, the values of R.A and the IDs of their corresponding tuples are collected at the root of the routing tree. The root sends them to region S. At each node N in region S, semijoin R[A] \(\rtimes_{A\theta_{R}}\mathrm{S_{N}}\) is conducted, where \(\mathrm{S_{N}}\) is the subset of S stored at N. This fully reduces S. For the matched values of R[A], their corresponding tuple IDs are sent back to region R, reducing R fully as well. The two regions send those tuples that have survived to the query sink for the final join. _Local Semijoin_ is a direct application of the conventional semijoin to WSNs except for the _backward_ reduction using the tuple IDs. In [4], however, it was shown that _Local Semijoin_ always outperforms _Mediated Semijoin_, an alternative implementation which might seem a more general one. In _Mediated Semijoin_, a join region \(T\) possibly other than the two regions \(R\) and \(S\) is arranged to which \(R[A]\) and \(S[B]\) are sent along with their tuple IDs.