## 4 Techniques of In-Network Join Processing
### Summary and Assessment
\begin{table}
\begin{tabular}{c c c c c c c c c c c} \hline \hline
**Techniques** & **Join** & **Query Type** & **Join Operand** & **Non-Joinable** & **Involvement of** & **Adapted Join** & **Routing** & **Optimization and** \\  & **Pred.** & **Supported1** & **Relations2** & **Tuple Filtering3** & **Base Station4** & **Implementation** & **Protocol** & **Other Features** \\ \hline \hline \multirow{2}{*}{_Local Semijoin_[4] & theta & O & static & full reduction of & & NO & semijoin & GPSR & always outperforms _Medicated Semijoin_[4] \\  & & & & & partial or full & & & & _Medicated Semijoin_[4] \\ \multirow{2}{*}{_INJECT_[21]} & theta & C, P, L & static & reduction of both & NO & semijoin, & tree & & cost-based optimization \\  & & & & relations & & Bloomjoin & routing & & \\ \multirow{2}{*}{_Two-Phase SelfJoin_} & theta & C & stream & full reduction of & & & & & query decomposition \\  & & & & one relation & & & & & assuming a highly \\  & & & & one relation & & & & routing & selective selection \\ \multirow{2}{*}{_SENS-Join_[7]} & & & & partial to full & & & & & & \\  & & & & reduction of both & YES & semijoin & tree & \(n\)-dimensional join filter \\  & & & & relations 4 [FOOTNOTE:4]Footnote 4: C = continuous, O = one-shot, P = periodic, L = long-running.2 per window. 2 using a semijoin (or its variants) or a join filter. * other than in the final join. 5 The join method at the join node \(N\) is orthogonal to the proposed framework. Under the memory constraints at \(N\), any centralized join implementation can be used. * where partial to full depending on the resolution of join filter. 7 a hypothetical distributed join method whereby only the joinable tuples of each site are sent to the final join site. \\ \hline \hline \end{tabular}
\end{table} 
Table 2: _Cont._  
**Protocol-oriented implementation. ** A crucial challenge is to carefully design a protocol-oriented join implementation under the resource constraints of the sensor nodes. The state-of-the-art has well addressed this requirement. Examples of detailed description of protocol-oriented join implementations can be found in [2, 3]. In [21], the lower bounds of memory space of a sensor node required in executing the semijoin strategies are shown. However, the full details of implementation are often missing in the state-of-the-art techniques. Some examples are as follows: In [2], the size of the region \(T\) where the filtering of non-joinable attribute values through geographic hashing is to be conducted is computed based on the available memory of a sensor node. However, a skewed value distribution that might cause memory overflow in a node in \(T\) is not considered. In [11], the available memory of a sensor node is considered in arranging the optimal join region, which can be obtained after the initial execution of the join at the query sink to which all the tuples are collected. If the query sink is a node inside the network, its memory space matters but such an issue is not addressed. In [8], the overflow at a node to which a tuple is routed through geographic hashing is addressed. But the details are not given. **Fault-tolerance. ** This requirement has received the least attention in the state-of-the-art. Though failure handling is addressed in several techniques, only a simple form of failure is treated in each technique. In [4, 6, 7, 11, 22], the successful transmission of data in spite of a node or link failure is considered. It is achieved through the handling of failures by their underlying routing protocols. In [8], the replication of sliding windows is considered. As for other techniques where failure handling is not addressed, the aforementioned failure handling could be incorporated to them. However, more critical forms of failures (e.g., a partial or total loss of the join nodes) have not been addressed in the state-of-the-art.