Related works
Data management in broadcast environments receives a lot of attention in these few years. However, there are only a few studies on transaction processing [8]. In [11], Datacycle architecture is introduced for high throughput database systems. The entire contents of the database are repetitively broadcast to the hosts over a high bandwidth network. It could be very expensive to use the serializability as the correctness criterion in the Datacycle architecture [8].
In [8], a new correctness criterion is proposed to allow read-only transactions to read current and consistent data in broadcast environments without contacting the server. However, the serializability is not maintained in their protocol. Two different read-only transactions may perceive the effects of update transactions in different serial orders. It may be hazardous to certain applications such as mobile stock trading where a buy/sell trade will be triggered to exploit the temporary pricing relationships among stocks. From the trader’s perspective, the inability of database management system to maintain the serializability may have important financial consequences [12]. For instance, if the users who submitted multiple read-only transactions communicate and compare their query results, they may be confused [13]. In [8], they proposed two protocols, F-Matrix and R-Matrix. Although the F-Matrix shows better performance, it suffers from high overheads in terms of expensive computation and high bandwidth requirement for additional control information.
In [4,6], multi-version data broadcast approaches are suggested to resolve the problem of reading inconsistent data values. In addition to the most updated version, all the previous versions within a time frame need to be broadcast as well. Another method to detect the non-serializability problem is to broadcast serialization graphs [4,6]. Each client maintains its local serialization graph to ensure that the schedules of all the committed transactions are serializable. The first drawback of this method is also the heavy overhead in broadcasting the serialization graphs since every data conflict at the database server has to be broadcast. Secondly, each client must listen to the transmission channel to maintain and update its serialization graph [5]. This leads to another serious problem, which can affect the correctness of this approach: the need to maintain the serialization graphs at the client mobile even when it is disconnected. The mobile network is unreliable and disconnection is frequent. When disconnection occurs, the mobile client cannot obtain new serialization information about its transaction, making it virtually impossible to ensure serializability of transaction execution.
In [3], UFO algorithm can maintain the serializability of update transactions at the database server and the read-only mobile transactions. This algorithm has been shown to be more efficient and has minimal impact on server, client and the broadcast schedule. However, update operations of mobile clients have not been taken into account. In this paper, we propose a mobile database system that uses a modified UFO algorithm, utilizes a rule-based approach for concurrency control among mobile and update transactions in the broadcast environment. Moreover, this system has an inference engine that makes deduction using forward chaining control flow to provide effective consistency checking during updates.
System architecture model
Figure 1 presents a general architecture of the mobile database system similar to that described in [14,15]. Architecture model consists of stationary and mobile components. Mobile component is the mobile client, which can connect fixed network via a wireless link. Stationary components could be fixed host or base stations. Fixed Host in a fixed network does not have capable of connecting to a mobile unit. Base stations are augmented with wireless interface to communicate with mobile computers, called Mobile Support Station (MSS). In the above architecture model, database servers residing on fixed host and MSS compose a distributed database system. Every database server possesses site autonomy and supports local transaction processing through Two-Phase Locking mechanism. As a part of the distributed database system, each MSS can also function as a mobile transaction coordinator, which receives transaction operations from mobile clients and coordinates their execution. A mobile client can move arbitrarily at any moment within a wireless cell or among different cells. When it is connected with the fixed network, it always communicates with the MSS supporting the cell where it is currently located. In addition, it can disconnect from the fixed network at any time. When it reconnects with the fixed network, it fetches back the results of previous operations and sends subsequent operations.
An important property of the data items in a mobile computing system is that their values can be highly dynamic and sensitive as they are used to maintain the useful information such as weather, highway conditions, traffic directions, news, stock quotes and the location of a moving object [10]. To maintain the freshness and validity of the data items, data items should be updated often by the generation of update transactions. It is assumed that the updates are generated by means of some external environment such as capture devices, and sensors. The broadcast server disseminates all the data items periodically in each broadcast cycle. The duration of a broadcast cycle may be fixed or variable depending on the adopted broadcast scheduling algorithm, which is also used for selecting data items to broadcast.
Update transactions consist of one to several write operations and its arrival rate can be very high. It is assumed that a well-formed concurrency control protocol, such as two phase locking [3], is used for concurrency control amongst the update transactions at the database server. Mobile clients issue mobile transactions to access data items at the database. It is assumed that each mobile transaction consists of a sequence of read operations and defined with a deadline. Moreover mobile transaction will become totally useless after its deadline and has to be aborted or restarted.
In our model, the broadcast process is modeled as a long read-only transaction, called broadcast transaction. The length of a broadcast transaction is defined based on the life span of a mobile transaction that is equal to the time required to broadcast its data items. Thus, the data item set of a broadcast transaction includes all the data items, which are broadcast during the period from (current time - life-span of a mobile transaction) to current time. The reason of choosing the life span of a mobile transaction to define the length of a broadcast transaction is that for normal cases a mobile transaction will be finished within its life span. Note that the broadcast transaction actually does not possess any characteristics of a transaction.
The following are the assumptions of the system model are summarized below:
- All update transactions are processed at the database servers.
- The arrival rate of update transactions is high and random.
- All mobile transactions are read-write.
- Each mobile transaction has a deadline, i.e., arrival time + life span. It is important to complete a mobile transaction before its deadline. Otherwise, it should be restarted.
- The broadcast process is modeled as a broadcast transaction.
Correctness of transactions in broadcast environments
Dissemination of data items to mobile transactions may be performed concurrently with the execution of update transactions. So it is possible that mobile transactions may read inconsistent data values due to uncontrolled interleaving of update and mobile transactions. Moreover, Mobile transaction should access updated value of data items. Thus, there are two fundamental requirements for disseminating data items to mobile transactions: Mutual consistency and Currency. Mutual consistency ensures that (a) the server maintains mutually consistent data and (b) clients can read mutually consistent data. Currency ensures that clients can access data that is current.
Mutual Consistency
Concurrency control amongst update transactions are to be done by a well-formed concurrency control protocol such as Two-Phase Locking [1], we have to consider the inconsistent problem of data conflicts between mobile transactions and update transactions. Our proposed protocol will concentrate on resolving this type of data conflicts to ensure that all mobile transactions will read consistent data values. In this paper, we adopt serializability as the correctness criterion of database consistency as it is widely accepted in the database community. If the serialization graph of a set of transactions is acyclic, then the schedule is serializable.