## 2 Preliminaries
### Sensor Network and Database  
We consider a sensor network that consists of a set of sensor nodes. Each node is a battery-powered small computer with limited processing capability and memory capacity. It is equipped with one or more sensing devices and a radio for wireless communication. A node can directly communicate with other nodes within its wireless range. For multi-hop communication with other nodes beyond the wireless range of a node, the nodes form a network. The power in a node is also a limited resource. The power consumption in a node is dominated by data transmission. It is orders of magnitude more costly than processing on a node [1]. Power conservation (or energy-efficiency) is one of the most important requirements when a sensor network performs a task. The longevity of a sensor network depends on it. A sensor network is often ad-hoc and unstable, and each node has limited knowledge of other nodes and how they are connected. Finally, we assume that a sensor network is connected to the _base station_ which is not resource constrained. In WSNs, the data acquired by a sensor node at an instant in time is the readings of one or more sensors on the node (e.g., temperature, humidity, _etc._) These readings can be modeled as a relational tuple that has one attribute per sensor. Each attribute is called a _sensor attribute_ and the resulting tuple  
Figure 1: _Cont._  
is called a _sensor tuple_. Besides sensor attributes, a sensor tuple is often modeled as having _auxiliary attributes_ such as node ID, geographic coordinates of the node, and the timestamp of the sensor readings. The _stream_ of sensor tuples in WSNs can be modeled as a relation. It is called a _sensor relation_. Logically, it has at most one sensor tuple per node per instant in time. Physically, it is horizontally partitioned across the sensor nodes in WSNs. A composite of the node ID and timestamp attributes could be designated as a primary key of a sensor relation. The sensor nodes could be heterogeneous, having different sets of sensing devices. In a sensor tuple produced in a node without a particular sensing device, the corresponding sensor attribute is set to NULL. Depending on the degree of heterogeneity, different groups of sensor nodes could be modeled as separate sensor relations, one per group. Views of a sensor relation can also be defined as in relational databases. A query joining sensor readings can be declaratively expressed against the sensor relations in SQL-like syntax as shown in the previous section and in Figure 1. The sensor relations and/or its views are listed in the FROM clause as join operand relations. For example, in the query expressions in Figure 1(b,d,e), the sensor relations are directly queried. In the query expressions in Figure 1(a,c,f), views of the sensor relation are queried. The join predicates of interest are specified in the WHERE clause often with selection predicates. Each predicate is either on the sensor attributes or on the auxiliary attributes. In the query expression in Figure 1(d), for example, there are five predicate conditions in the WHERE clause: The first one (B\({}_{1}\)._light_\(<\)\(\delta\)) is a selection predicate on a sensor attribute _light_. The second one (B\({}_{2}\)._num_\(>\) B\({}_{1}\)._num_) is a join predicate on a sensor attribute _num_ (_i.e._, number). The remaining three (B\({}_{1}\)._loc_\(=\) B\({}_{2}\)._loc_; B\({}_{1}\)._time_\(<\) B\({}_{2}\)._time_; B\({}_{2}\)._time_\(<\) B\({}_{1}\)._time_\(+\)\(h\)) are join predicates on auxiliary attributes _loc_ (_i.e._, geographic location of a sensor node) and _time_ (_i.e._, timestamp of a sensor tuple). The predicates on sensor attributes are the ordinary ones used in the conventional database queries. The predicates on auxiliary attributes add spatial as well as temporal characteristics to the join queries in WSNs. Since a join is expressed declaratively, its implementation strategy needs to be devised.