## 4 Techniques of In-Network Join Processing
### Techniques with Filtering of Non-Joinable Tuples
The tuple IDs that have survived in \(T\) after \(R[A]\bowtie_{A\theta B}S[B]\) are returned back to regions \(R\) and \(S\), fully reducing relations \(R\) and \(S\). In [4], the cost formulas for _Local Semijoin_ and _Mediated Semijoin_ were developed assuming that the size of regions \(R\) and \(S\) is small. According to those formulas, the _optimal_ location of \(T\) in _Mediated Semijoin_ is shown to be that of either \(R\) or \(S\). In _Local Semijoin_, data routing is carried out by GPSR protocol. It guarantees data delivery as long as a route exists and discovers new routes automatically when a node fails. In this sense, _Local Semijoin_ can adapt to node failures as the underlying routing protocol does. _INJECT._ Min _et al_. [21] proposed _INJECT_ (In-Network Join strategy using Cost based optimization in Tree routing sensor networks) to answer a continuous join query. For a theta-join \(R\bowtie S\) which is to be executed periodically, _INJECT_ performs cost-based optimization, selecting the optimal strategy for each execution. Each execution is against static relations \(R\) and \(S\) with the routing  
Figure 8: Non-joinable tuple filtering and final join for \(R\bowtie S\) using a distributed variant of a semijoin, where \(v\)-tuple denotes a tuple of \(R\) or \(S\) whose joining attribute value is \(v\). tree covering all the nodes of the network with the base station as the root. In _INJECT_, both semijoin results, \(R\rtimes S\) and \(R\ltimes S\), are obtained inside the network. They are sent to the base station for the final join. Beside the external join, _INJECT_ considers various join strategies including _PartitionJoin_, _SynopsisJoin_, and _fullSynopsisJoin_. Before each execution of the query, _INJECT_ estimates the communication cost of each strategy using a cost model. The optimal one is chosen and notified into the network. The cost formulas are derived using such statistics as the selectivity of a selection predicate and the semijoin selectivity. At first, these statistics are unknown. The external join is employed in the learning phases in which these statistics are collected. The basic idea of _PartitionJoin_ is as follows: Let us consider an equi-join \(R\bowtie_{A=A}S\), for example. Regions \(R\) and \(S\) and their common path to the base station in the routing tree is shown in Figure 9(a). \(T_{R}\) and \(T_{S}\) respectively denote the subtree of region \(R\) and \(S\). A straightforward way to obtain the semijoin result \(R\rtimes S\) at node \(r_{S}\) (the root of \(T_{S}\)) is to collect \(R[A]\) at node \(r_{R}\) (the root of \(T_{R}\)), forward it to \(r_{S}\) via \(c_{T}\), and to filter out non-joinable tuples of \(S\) in \(T_{S}\) by injecting \(R[A]\) into \(T_{S}\) as shown in Figure 9(a). _PartitionJoin_ optimizes this process as follows: \(R[A]\) is collected at node \(r_{R}\). It is forwarded to \(r_{S}\) via \(c_{T}\). Non-joinable tuples of \(S\) in \(T_{S}\) are filtered out by _selectively_ forwarding \(R[A]\) into \(T_{S}\). In other words, \(R[A]\) is _not_ forwarded to every node of \(T_{S}\). For example, suppose that there are two subtrees of \(r_{S}\) (Figure 9(b)) and that \(R[A]\) is forwarded to the subtree whose root is \(n_{I}\) (denoted as \(T(n_{I})\)), whereas it is not to \(T(n_{2})\). Then, all the tuples of \(S\) in \(T(n_{2})\) are supposed to be sent to \(r_{S}\) where they are semijoined with \(R[A]\). The reason why \(R[A]\) is not forwarded to \(T(n_{2})\) is that the cost of forwarding \(R[A]\) to \(T(n_{2})\) would be higher than the benefit of reducing the set of \(S\) tuples in \(T(n_{2})\). For the subtree to which \(R[A]\) is forwarded (e.g., \(T(n_{I})\)), such _selective forwarding_ is _recursively_ applied. Figure 9(c) shows the three subtrees of \(T(n_{I})\). \(R[A]\) is forwarded to \(T(m_{I})\) and \(T(m_{2})\), but _not_ to \(T(m_{3})\). In [21], [PERSON] _et al_. proposed a dynamic programming algorithm that obtains the optimal selective forwarding of \(R[A]\) to \(T_{S}\). Figure 9: Semijoin \(R\rtimes S\) in _INJECT_.