This essay has been submitted by a student. This is not an example of the work written by our professional essay writers.
Abstract. Focus of my research survey is exploring all major reconciliation mechanisms that have been used to remove update conflicts in databases running in mobile environment. When wireless clients (Laptops, PDA, Smart phones) disconnected for a short period or when these clients are facing bandwidth problem because of their geographical location, at that time update to the databases from different mobile clients can cause database to be in inconsistent state when these mobile client are re-connected. To avoid this database inconsistency, different reconciliation mechanisms were developed.
Keywords: Mobile Server, mobile Client, Central Database
Computer science and Telecom have revolutionized the world with the advent of mobile devices because of their portability and low energy requirement. Mobile devices are using in all fields of life like in business, health care and communication. But with mobile devices we face new challenges in mobile databases; the major challenge is reconciliation of updates from mobile clients in database during their disconnection.
To understand the terminology of Reconciliation, we have to understand how Mobile database are different traditional database and why we need reconciliation. Traditional databases either client-server or distributed databases are link with each other on persistent unbreakable link, so every update to the database by user is done instantly and there is no conflict of data. But in mobile environment clients are wirelessly connected to the server. Client may disconnected to the server because of signal problem at some close places like elevator, out of range place like jungle or mountains and in fast moving objects like trains and buses.
What will happen if client system is disconnected from the main database and user put his request to the client system?
Every mobile client replicates partial data into its cache to fulfill user request even in disconnection mode. Users request is treated as transaction that is a small program. User transactions are committed at the server globally. If server is disconnected from the client the transaction are tentatively executed at the client but could be rollback at the server when connection with server reestablished and it is found that transaction is conflicting during reintegration with the main database
What happen if one user request change main database before disconnection and other user read the old data before updating of main database?
All concurrent transactions at multiple clients are globally committed at the server. Server first verify each transaction, weather it is conflicting or not and also weather it read dirty data or not, then commit the transaction.
Syed Abid Ali (07-9022) Under Assistant Professor Ayaz-ul-Hassan: Computer Department, National University of Computer and Emerging Sciences, Karachi Campus www.nu.edu.pk
- Mobile Sales Application:
- Shared calendar Application:
Big General item store like "Makro" having multiple branches all are connected wirelessly and Makro has also Mobile sales man for collecting customer orders and home delivery, each salesman is given palmtop or laptop to update customer order to the central database.
Mobile salesman S1 got customer requirement for 10 pamper, salesman S1 palmtop is not connected to the mobile server because of signal problem, salesman S1 check pamper quantity on palmtop cache that show it is 15, so salesman S1 take customer order and put a transaction in its palmtop. But meanwhile another salesman S2 sold 10 pampers and update central database with pamper quantity to 5. In such situation when first salesman S1 reconnects to the server then its transaction will rollback and its order have to be cancel. But in this way customer will be annoyed with the system, so we have to design such a reconciliation mechanism that minimize the concurrent update transaction from multiple clients.
We have three conference halls that user request to occupy for different conferences
Two clients make requests to a calendar program. One-client requests hall X at 3:00, and either hall Y or Z, also at 3:00. Meanwhile, other client requests either hall X or Y at 3:00. Combining the transactions in simple way does not work. For example running transaction 1 then transaction 2 will reserve hall X and Y for the first client, and the second client request is dropped. Running transaction 2 first has a similar problem. We should have such a reconciliation mechanism that fulfills both client requests.
Reconciliation is quite difficult because of:
- Conflict presence in data
- Alternative execution paths within the transaction
- Dependencies between transactions
Reconciliation should be in such a way that number of drops for clients transactions updates as minimum as possible.
To guaranty database consistency, number of reconciliation mechanisms has been developing. Some of them are:
- Three tier architecture
- Gold Rush
- Transaction-Level Result-Set Propagation (TLRSP) model
- Multiversion Reconciliation
2 SqlIceCube [1,2]
SqlIceCube is a reconciliation mechanism that extracts semantic relation from the concurrent update transactions and creates a global update schedule (serialized all concurrent updates) and drop those update that are logically not possible, but drop rate should be minimized. Alleviating programmers from most of the work (defining rules for serialization of update) usually involved in semantics-based reconciliation.
In this model, update operations are small programs that are written in a subset of PL/SQL. These programs are known as mobile transactions that are submitted by client applications to change (modify) the database.
SqlIceCube is a generic reconciliation engine that combines concurrently executed mobile transactions into a single execution schedule. While disconnected, mobile transactions may be tentatively executed against local replicas. During reconciliation, the mobile transactions programs are executed again, i.e., the transactions are replayed logically (as opposed to redoing physical writes).
Consider the example of figure 1, where two clients make requests to a calendar program. One-client requests hall X at 3:00, and either hall Y or Z, also at 3:00. Meanwhile, other client requests either hall X or Y at 3:00. Combining the transactions in simple way does not work. For example running transaction 1 then transaction 2 will reserve hall X and Y for the first client, and the second client request is dropped. Running transaction 2 first has a similar problem. Satisfying all three requests requires reordering them. Thus, reconciliation systems must be prepared to reorder updates. The system presented in this report automatically infers the semantic information needed for reconciliation.
In this model, reconciliation is executed in two steps:
- Extracting semantic information by statically analyzed each transaction. A set of semantic static relations is inferred using the extracted information for each pair of transactions.
- The basic reconciler finds a schedule that makes it possible to execute more transactions.
This model presents the following contributions:
- Drive semantics of the operations and data types
- Users intents (What user want to schedule transactions)
- Creation of optimal reconciliation schedule.
- Help programmers for not writing rules to reorder transactions for scheduling
Working of semantics-based reconciler
Concurrent mobile transaction (in multiple mobile clients) combine to create optimal schedule. The reconciler can create alternative schedules based on semantic static relations between among number of transactions.
Preconditions and commit and rollback statements specified in transactions are dynamic constraints. Static relations are inferred by preconditions.
Static relations among multiple mobile transactions are independent of database state. There two types of static relations are
- Log relations
- Data relations
Static log relations
These express users' intents and are defined as follow
Alternatives Specify that only one transaction must be committed from a set of alternatives. For example; when scheduling a conference, a client can specify two or more alternative conference halls or dates.
Strong predecessor-successor If predecessor transaction commit then successor transaction can execute, otherwise successor transaction cannot commit. For example, meeting is schedule in first transaction then second transaction for tea break is executed.
Weak predecessor-successor: Transaction for cancellation of all existent appointments for the day execute after the transaction for scheduling a new appointment for same day.
Parcel (All-or-nothing group of transactions) Bank transfer is a parcel having two transactions, one depositing money in destination account and the other withdrawing money from source account.
Weak predecessor-successor relations & alternatives together create a set of ordered alternatives. One transaction is executed is guarantee by "alternatives relations". Preferred transaction is executed is guarantee by weak-predecessor relation.
Relations between transactions that encode the semantics of operations are called Data Relations.
Commute If the result of executing two transactions is independent of the execution order then these transactions can commute. As an example, two transactions that change independent data items can commute.
Helps If the commit of transaction T(1) changes the database state in a favorable way for the completion of truncation T(2) then we said transaction T(1) helps the transaction T(2). As an example, a transaction that increases the quantity of a product improves the chance of accepting a new order request for the same product from the client.
Prejudices Opposite of help. As an example, a transaction that decreases the quantity of a product can minimize the acceptance of new order request for the same product from the client.
Makes possible If commit of transaction T(1) guaranty commit of transaction T(2) then we say T(1) make possible transaction T(2). As an example, removing all conferences in a given hall makes possible to schedule a new conference for that hall.
Makes impossible Opposite of Make possible. As an example, If T(1) set the price of a product to a value that violates the preconditions of an order request in T(2) then T(1) makes impossible to accept this T(2)requests.
Preferable execution order between pair of transactions is suggested by static relations (makes possible and makes impossible, commute, helps, prejudices,)
Merit of a transaction: The reconciler creates a schedule incrementally by iteratively selecting a transaction according to following define merit.
The merit of transaction T is higher as:
- It belongs to a parcel that includes a transaction already executed.
- The value of weak predecessors of T is lower
- The value of alternatives to T is lower,
- The value of transactions T makes impossible is lower
- The value of weak & strong successors of T is higher.
- The value of transactions T helps is higher.
- The no. of transactions T prejudices is lower.
Algorithm for creating a single schedule: The algorithm maintains
- Set of transactions that can be scheduled, trxs
- Set of (temporarily) impossible transactions badTrxs
- Summary of relations established among transactions.
Algorithm to create a single schedule from Nuno Preguic¸a, Marc Shapiro,J. Legatheaux Martins (2003) SqlIceCube: Automatic Semantics-based Reconciliation for Mobile Databases Technical report
Algorithm selects one transaction 'T' randomly among set of candidate transactions 'trxs' having highest merit. Then selected transaction 'T' is executed against the current database state. If the transaction ends in a commit statement, its mean it is executes successfully, so it is added to the current partial schedule and the value of the schedule is updated. All transactions in the impossible transactions 'badTrxs' set that are helped or made possible by this transaction are removed from impossible transactions badTrxs. All transactions that are temporarily made impossible by the execution of this transaction 'T' are added to badTrxs. All transactions that are definitely made impossible by this transaction 'T' are removed from the set of transaction 'trxs' to schedule. The executed transaction 'T' is also removed from 'trxs'. If the transaction 'T' ends in a rollback statement then execution fails, the transaction 'T' is added to the impossible transactions badTrxs. The summary of relations among transactions is updated in both cases. This incremental process continues until there is single transaction to be schedule that is not known to be impossible. The algorithm verifies parcel integrity at the end. If all parcel relations are respected then created schedule is valid. Otherwise, the algorithm signals an error and indicates the set of transactions that caused the problem.
Complexity of Algorithm:
For each transaction 'T' to be select algorithm consider all n transaction to check the merit of the transaction 'T'. So overall complexity of the algorithm is O(n2).
Within every transaction each path that ends in a commit statement, the following information is extracted:
Semantic read set is obtained from select statements.
Semantic write set is obtained from insert, update and delete statements.
Precondition set contains all conditions in the given execution path, like if instructions and loops.
If there is only one execution path leading to a commit statement then a single set of static information is extracted.
Mobile sales application:
Case 1: Let T(a) be an add transaction and T(c) be a cancel transaction acting on the same product. The system infers the following relations.
- T(a) and T(c) do not commute because T(a) reads the stock of product with id = 80 and T(c) writes it.
- T(c) helps T(a) because adding a positive value to the stock helps the stock to be bigger than some constant.
- No other relations exist.
Improving the chances of committing both transactions.
Case 2: Two mobile transactions adding a new order for the same product. Following information extracted
- Two transactions do not commute
- One transaction prejudices the other because subtracting a positive value from the stock reduces the chances of the stock being larger than some constant.
Case 3: Two mobile transactions canceling the same order. Following information extracted
- Two transactions do not commute
- One transaction makes impossible the other because setting the order state to cancelled makes the precondition expressed in the transaction false.
Case 4: Two mobile transactions acting on different products and orders. Following information extracted
Two transactions commute because they do not access the same data items.
Shared calendar Application:
Case 1: Any two transactions commute if they refer non-overlapping reservations
Case 2: Overlapping transactions do not commute because both accessing same data item. Following additional relations are inferred for such transactions.
Case 2a: For two transactions inserting a new reservation, each one makes prejudices (& impossible) the other, as the inserted record make the precondition false.
Case 2b:For two transactions canceling the same reservation, each one makes prejudices (& impossible) the other, as the delete statement guarantees that no record exists that satisfy the specified precondition.
Case 3: For two transactions, one inserting new reservation transaction T(a), other deleting reservation transaction T(c), two cases should be considered.
Case 3a: If both refer to the same reservation then T(a) helps (& makes possible) T(c) because the inserted record guarantees that the reservation exists. Also T(c) helps (& makes possible) T(a) because removing the reservation guarantees a new reservation.
Case 3b: If both refer to different reservations then T(c) helps (& makes possible) T(a) because removing the reservation guarantees scheduling new reservation. But T(a) does not helps (& makes possible) T(c) because inserting record does not satisfy the condition of the select statement
In Java, prototype of the SqlIceCube reconciliation system is implemented. Major components of this prototype are:
- Database system. hsqldb Java Database Engine is used. Implementing the checkpoint needed by the SqlIceCube reconciler by making a copy of the database files.
- PL/SQL interpreter, which executes mobile transactions on top of a generic SQL database.
- Module that extracts information from mobile transactions, it analyzes the abstract parse trees built by the PL/SQL parser.
- Module that infers relations using the extracted information.
- Generic semantics-based reconciler that creates and executes a schedule combining sets of mobile transactions.
Deployment In the context of conflict-avoidance
Using SqlIceCube reconciler with conflict-avoidance mechanism (that use Locks and reservation to guaranty no conflict will occur) can increase the number of transaction that can be executed.
This model includes a semantic inference module that extracts semantic information from the code of mobile transactions automatically that eliminate the overhead of writing long complex rules to expose the semantics of operations. The SqlIceCube reconciler use a heuristic search approach and creates near-optimal schedules.
3 Mobisnap 
Mobisnap is collaboration of conflict avoidance mechanism (reservations like locks and some other techniques) & conflict resolution strategy. It guaranty that update can be executed in the server without conflicts. Client has held enough reservation over database state that updates in the client cache are final and other client may not update that part of the database.
Mobisnap includes several types of reservation (like using Locks, Escrow techniques) to guarantee the result of mobile transaction.
Architecture of Mobisnap System
It is based on client/server architecture having middleware. Components are:
- Central Database (RDBMS)
- Mobile Server (Mobisnap Server)
- Mobile Client (Mobisnap Client)
Primary copy of all data items is in the central database. Static users can access central database directly without accessing the mobile server. Whereas mobile clients can be laptops or palmtop or mobile phone, that could be disconnected for longer period of time.
Mobile client cannot access central database directly. They communicate with central database by accessing mobile servers. Mobile clients copy partial database tables to their cache and perform update in their local cache according to user requirements given in small programs called transactions. If mobile client has enough reservations to prevent server to be updated by other clients in same time then changes made at client is conformed even when client is disconnected otherwise changes are tentative and confirmed when connection with the server is establish server verify that no conflict occur. If some conflict is dictated then changes made by the client are rollback.
This model use different reservation collectively to guaranty that update made some client are conformed and no conflict will occur at the client by some other client. Different types of reservation used by this model are:
- Value-change Reservation
- Slot Reservation
- Value-use Reservation
- Escrow Reservation
It provides the exclusive right for the modification of the state of an existing data item. As an example, the description of a specific seat in a train could be change by the user.
It gives exclusive right to user for insert, modify and remove rows. As an example, a user can schedule a conference in a given hall in some defined period.
So value change and slot reservation bring the primary copy of the date from the server to the client cache, but we have to be careful for application of these reservation because they prevent other transaction from modifying select part of the database.
User can use a given value despite the original value of the data. As an example Sales-man can guaranty a definite price for the order of some particular product whose value change rapidly.
Eescrow reservation partitions the resource and distributes each user the portioned resource to be use exclusively. As an example, Consider we have stock of 90 books to be sold to be sold on to branches of the book stall, so the users are two, but we have to maintain minimum stock of 10 books. We partition the stock into two parts i.e. stock of 50 books to be sold by user 1, maintaining minimum stock of 5 books and stock of 40 books to be sold by user 2, maintaining minimum stock of 5 books.
Example of transaction program from Nuno Preguic¸a, J. Legatheaux Martins, Miguel Cunha, Henrique Domingos (2003): Reservations for Conflict Avoidance in a Mobile Database System Departamento de Inform´atica FCT, Universidade Nova de Lisboa, Portugal
- -------- PRODUCT ORDER: name = "Pampers"; quantity = 20; highest price = 60.00 ------
- pd_price FLOAT;
- pd_stock INTEGER;
- SELECT price, stock INTO pd_price, pd_stock FROM products WHERE name = 'PAMPERS';
- IF pd_price = 60.00 AND pd_stock = 20 THEN -- checks availability of stock & acceptability of price
- UPDATE products SET stock = pd_stock - 20 WHERE name = 'PAMPERS';
- INSERT INTO orders VALUES (id,'Clt foo','PAMPERS',20,pd_price); -- unique-identifier is returns by the id
- NOTIFY( 'SMTP', 'firstname.lastname@example.org', 'Order accepted ...'); -- in server & in client
- COMMIT pd_price; -- returns the price & commit
- ROLLBACK; -- when customer's preferences is not satisfied then rollbacks & returns
- ON ROLLBACK NOTIFY( 'SMS', '00923332448226', 'Impossible order...'); -- on rollback user receive notification
Reservations that salesman obtained are shown in table-1 for the transaction of simple insertion of order shown in transaction program code. For each reservation following information is maintained:
- Unique identifier
- Reservation Type
- Reserved columns within the rows
- The condition;
- Reserved data item value
If-statement in line-7 is guaranty by the two reservations mention above. The escrow reservation guarantees that stock of the product is greater than required product. The value-use reservation guarantees that the price is acceptable.
4 Three-tier architecture 
Extended client-server architecture is mostly used in mobile databases that create some problems like scalability issue; less secure system and low system performance for traffic congestion around the server. Three-tier architecture is introduced in this paper to overcome the drawbacks of two-tier architecture for mobile databases. In this paper middle tier called Group Replica Server (GPS) is introduce to extend client-server architecture. According to certain criteria like data access or region mobile clients are group together, each group has been assign server called Group Replica Server (GPS) having its own cache having replica of data related to certain group. Reconciliation of conflicting transactions is performed in two phases first at Group Replica Server (GPS) and second (final) at the mobile server.
When any transaction from the user require to read or write data then data is first check in client cache, if not found then it is being check at Group Replica Server (GPS), if data is not found at GPS then a request is send to the server if client is connected to the server. Server then communicates with other GPS to find the requested data. Even if server is disconnected or down, users transactions are entertained at client cache and at local GPS.
This system is more secure as compare to extend client-server architecture because client cannot access server directly. Main server and Local GPS have there own firewalls.
Scalability issue is resolved because it is easy to add as many as GPS between Server and clients.
Performance will improve as client and server direct communication is reduced, most of the user requests are fulfill at client cache or at local GPS.
The framework should be implemented to measure the efficiency of the architecture.
Two phase reconciliation protocol and single-phase reconciliation protocol must be compare to check efficiency.
5 Gold Rush 
Gold Rush is not meant for all mobile application. Gold Rush is most appropriate for such system where clients are disconnected from server for most of the time. It is not suitable for stock trader application because vales of the data items are changing quickly & abruptly, disconnection for second can cause unrecoverable lose of data & unbearable lose of money. Gold Rush is suitable for such applications that have low degree of conflict.
Gold Rush is middleware, it support Java applications. Objects from central database are stored in the client cache when central server is connected to the client. When the server is disconnected from the client, users transactions are manipulated against objects in client cache. When client reconnection with the server, all user transactions are replay at the server. For each replay transaction at the server, Server checks for conflicts with other database update, if there is some conflict server notify about conflict to the client. Programmer has to explicitly program to resolve conflict. This model does not resolve conflict. Resolving conflict is future target of this model.
The Gold Rush is based on three-tier architecture consists of a back-end data store a back-end data store, mobile object server, and a back-end data store as shown in Figure. The mobile middleware resides partially on the server and client. Weather client is connected or not, same transaction API is presents to the client application. But client cannot query to the database in disconnected mode. Method call obtains service directly from the server in connected mode and invokes middleware transparently in disconnected mode and use locally available resources.
The Gold Rush middleware has the following major components as shown in Figure 5.
Database objects: Java object represents an instance of a database entity.
Object caching: A persistent local object for supporting disconnected transactions on database objects, It is store on the client.
Optimistic concurrency control transactions: Primarily, the client works on data objects in the mobile device in disconnection mode. Transactions are stored on the client side, when connection is established with the server then replayed to the server. Object may be locked with an optimistic read lock or with an optimistic write lock or left unlocked.
Communication: Communication between object server and database store is with the help of JDBC, whereas communication between mobile client and database store is with the help of RMI.
Some Issues with this model are:
Security issue is not address in current prototype, but it will be address in future prototype.
Conflict Resolution our current prototype can detect the conflict, but it cannot resolve, it must be programmed explicitly. Future versions of Gold Rush will include conflict-resolution strategies.
6 Transaction-Level Result-Set Propagation model 
In Transaction-Level Result-Set Propagation (TLRSP) model, mobile users are allowed to access local replicas of the database and submit local transactions when system is disconnected. Serilizability of the transactions is ensured by local database host (EDBMS). All transactions are in tentative mode not the committed ones. These locally committed transactions are sent to the fixed database server for conflict reconciliation and result set incorporation when the system is reconnected. This model makes it sure that order of the transactions at the server is same as it was submitted to the local host. Server (FDBS) ensures ACID properties & transaction serializability with the help of two-phase locking mechanism. Transactions that are committed at local host need to be verified before committed globally at server. It uses Incremental Refresh method for synchronization.
7 Multiversion Reconciliation [7,8]
It uses client server approach. Center server has the primary copy of the data items, while mobile clients have replica of server database. The system keep several version of each data item and provide snapshot isolation; client transaction can be reconciled against any of these versions. With snapshot isolation, multi-version transaction can commit if and only if data items in its write set were not overwritten after this transaction read them. A key concept in our algorithm is that conflict resolution and detection are decoupled. The responsibility for detecting conflicts lies with the server. This is done by performing serializability testing on locally committed transactions (against latest snapshot of the committed version) on reconciling clients. On the other hand, conflict resolution is the responsibility of the client. The client manages this by providing the conflict resolution and cost functions for each transaction. In the absence of these functions, the server assumes a default, which guarantees snapshot isolation to unmodified client transactions. It does not provide symmetric reconciliation and robust concurrency control mechanism.
Some Issues with this model are:
Non-symmetric Reconciliation: It only work in client- server mode, It does not work in per to per or distributed mode.
It does not support robust concurrency control mechanism: Each client transaction must reconcile by an atomic operation on the server. This consumes much time affecting system performance.
I find 'SqlIceCube' and 'Mobisnap' best conflict reconciliation and avoidance mechanisms. Both are latest and their prototypes that have been implemented are quite mature and further research is under process. Both together can design such a model where transaction drop rate because of conflict is negligible with utmost performance. Further more If client-server architecture is replaced with three-tier architecture explain in three-tier architechure  then performance will further enhance. Whereas other reconciliation mechanisms are old version, their next version is not available till now.
- Nuno Preguica, Marc Shapiro, J.Legatheaux Martins: Automating semantics-based reconciliation for mobile Databases Dep. Inform´atica, Universidade Nova de Lisboa, Microsoft Research Ltd.,Cambridge, UK (October 2003)
- Nuno Preguic¸a, Marc Shapiro,J. Legatheaux Martins: SqlIceCube: Automatic Semantics-based Reconciliation for Mobile Databases Technical report (2003)
- Nuno Preguic¸a, J. Legatheaux Martins, Miguel Cunha, Henrique Domingos: Reservations for Conflict Avoidance in a Mobile Database System Departamento de Inform´atica FCT, Universidade Nova de Lisboa, Portugal (2003)
- Md. Abdur Rahman, Souhail Abdala and Abdulmotaleb El Saddik: A Framework for Two Phase Reconciliation in Mobile Databases
- Maria A. Butrico, Henry Chang, Anthony Cocchi, Norman H. Cohen, Dennis G. Shea, Stephen E. Smith.:Gold Rush: Mobile Transaction Middleware with Java-Object Replication. IBM Thomas J. Watson Research Center,Yorktown Heights, NY 10598(June 1997)
- Zhiming Ding, Xiaofeng Meng, Shan Wang: A Novel Conflict Detection and Resolution Strategy Based on TLRSP in Relicated Mobile Database Systems. Institute of Computing Technology, Chinese Academy of Sciences, Beijing China.
- Phatak, S.H. and B.R. Badrinath ICDE: Multiversion Reconciliation of Mobile Databases, pp:582-589 (Year 1999)
- M Shamim Hossain and M. Anwar Hossain: A Snoptic Review of Reconciliation Algorithm for Mobile Databases. School of Science and Technology, Bangladesh Open University, Bangladesh