## 3 Overview of Join Processing in WSNs
### Components of Join Implementation  
An implementation of a join in WSNs consists of several components. Some of the major ones that are common to most of the techniques surveyed in this paper are described below. **Routing Protocol. ** Throughout join processing from query dissemination to the delivery of the final join result, a routing protocol is required. Among others, the tuples and/or joining attribute values need to be shipped and/or replaced inside the network with a routing protocol to execute join operators. For this purpose, the standard _tree routing_ protocol presented in [25] is widely employed. Figure 3(a) shows a set of sensor nodes in a region, \(R\), of the sensor network and Figure 3(b) an example of a routing tree constructed for them with the node at the center as the root. When all the nodes of the sensor network participates in the query, a routing tree covering all the sensor nodes is constructed with the base station as the root (Figure 3(c)). For an inter-region join \(R\Join S\), a routing tree per region could be constructed. Figure 3(d) shows the two routing trees for regions \(R\) and \(S\). The location routing protocol such as GPSR [27] is also widely employed when routing data to the sensor node nearest to given geographic coordinates. It is usually used in combination with geographic hashing [28]. **Figure 3.** (**a**) A region, \(R\), of the sensor network that consists of sensor nodes, where each small circle denotes a sensor node; (**b**) A routing tree constructed for region \(R\), where the sensor node at the center (_i.e._, a dark circle) is chosen as the root; (**c**) A routing tree constructed for all the sensor nodes of the network with the base station as the root; (**d**) Join initiation for an inter-region join \(R\Join S\). **Query dissemination. ** The _query sink_ where a join query is submitted is either the base station or a node inside the network. The query message is supposed to be delivered to every node of the network. For an inter-region join \(R\Join S\), however, the query message can be routed to the _center_ coordinates of region \(R\) (\(S\)) using a location routing protocol like GPSR. The query is received at the sensor node \(c_{R}\) (\(c_{S}\)) nearest to the center coordinates of region \(R\) (\(S\)). In region \(R\) (\(S\)), a routing tree whose root is \(c_{R}\) (\(c_{S}\)) is constructed (Figure 3(d)) using the standard method of [25] while the query is disseminated in the region. **Join initiation. ** After a node receives a join query, it might need to participate in the process of join initiation. For an inter-region join, first the relevant information could be gathered through the routing tree of each region, and then collected at a sensor node \(c_{T}\) where a join processing strategy is dynamically generated. \(c_{T}\) could be a midpoint node between the two roots [5, 12] or a node in the designated region where the join is to be conducted [3, 4]. The strategy is notified back to the two roots,and this completes join initiation. Figure 3(d) shows the node \(c_{T}\) and the two routing trees for regions \(R\) and \(S\). The selection of the _join node_ where the join is to be conducted for an inter-region join is also a function of join initiation. If the memory space of one node is not sufficient for the join, a set of nodes are selected. They form a _join region_. The location of a join region could be computed in the query sink [3, 4, 8, 11]. Join initiation for other types of join queries was investigated in [22, 23]. In the technique called _Pair-wise Join_ that will be described in Section 4.2, _multiple_ routing trees are employed for finding out the optimal path between a pair of nodes that participate in the join and the optimal join node on it. **Filtering. ** As described in Section 2.3, in the conventional distributed databases, the semijoin and its variants are employed to filter out non-joinable tuples before the final join is conducted. They reduce the amount of data to be transmitted [9, 14].