Database synchronizer

Abstract

A database synchronizer facilitates computing systems which have client-side and server-side applications that share data in similar database structures, but which do not maintain a continuous connection to a single shared data source. In general, a database synchronizer is used to share data among many nodes on the computing system. The database synchronizer is used to synchronize the data in a central database for a particular client with the data on that client's intermittently-connected computer. Updates performed by either client or server are propagated to the other side when a connection is established and eventually from the server to other clients in the system.

We claim: 
     
       1. A computing system for sharing data between a plurality of computers, the computing system comprising: a first computer having a first database which includes a first collection of data representable as a first plurality of rows and a first plurality of columns;   a second computer having a second database which includes a second collection of data including data replicated from the first database, the second collection of data representable as a second plurality of rows and a second plurality of columns;   an ordered list of common columns in the first plurality of columns and the second plurality of columns; and   a database synchronizer for synchronizing the first collection and the second collection at an arbitrary time, the database synchronizer using the ordered list to identify the location of data in the collections.   
     
     
       2. The computing system of claim 1 wherein the first database and the second database are heterogeneous. 
     
     
       3. The computing system of claim 1 wherein the ordered list defines a subset of the first and second collections. 
     
     
       4. The computing system of claim 1 further comprising: a first catalog including the ordered list and stored on the first computer; and   a second catalog including the ordered list and stored on the second computer.   
     
     
       5. The computing system of claim 1 wherein the database synchronizer temporarily establishes a communication link between the second computer and the first computer to transfer modification information. 
     
     
       6. The computing system of claim 5 further comprising a first update log stored on the first computer, the first update log including a history of modifications to data common between the first collection and the second collection. 
     
     
       7. The computing system of claim 1 wherein data is identified by the database synchronizer by a key value to represent a selected row of the collections and a common index into the ordered list to represent a selected column in the selected row. 
     
     
       8. The computing system of claim 1 wherein the first computer is a server computer sharing data in the first collection with a plurality of client computers and the second computer is a client computer. 
     
     
       9. The computing system of claim 1 wherein the database synchronizer uses row and column filtering of the data to limit the data synchronized between the computers. 
     
     
       10. The computing system of claim 1 further comprising a before-image collection of data on the second computer, the before-image collection having before-image data stored therein, the before-image data having values representing the state of the second collection at a time of last synchronization with the first collection. 
     
     
       11. The computing system of claim 1 further comprising a second update log stored on the second computer, the second update log including a history of modifications of data common between the second collection and the first collection. 
     
     
       12. The computing system of claim 1 wherein the first database is a relational database and the second database includes data accessible as tabular data. 
     
     
       13. A method of sharing data between a plurality of computers, comprising the steps of: at a first computer, storing a collection of data in a first database wherein the data is representable as a first plurality of rows and a first plurality of columns;   replicating data from the first database to a second database at a second computer, wherein the data is stored into a second collection of data representable as a second plurality of rows and a second plurality of columns;   generating an ordered list of common columns in the first plurality of columns and the second plurality of columns; and   synchronizing the first collection and the second collection at an arbitrary time using the ordered list to identify the location of data in the collections.   
     
     
       14. The method of claim 13 wherein the first database and the second database are heterogeneous. 
     
     
       15. The method of claim 13 wherein the step of generating the ordered list comprises defining a subset of the first and second collections. 
     
     
       16. The method of claim 13 further comprising the steps of: deriving a first catalog from the ordered list and storing the first catalog on the first computer; and   deriving a second catalog from the ordered list and storing the second catalog on the second computer.   
     
     
       17. The method of claim 13 wherein the step of synchronizing comprises: temporarily establishing a communication link between the second computer and the first computer; and   transferring modification information over the communication link.   
     
     
       18. The method of claim 17 further comprising the step of storing a first update log on the first computer, the first update log including a history of modifications to the columns of the first collection in the ordered list. 
     
     
       19. The method of claim 13 wherein the step of synchronizing comprises identifying data by a key value to represent a selected row of the collections and by a common index into the ordered list to represent a selected column in the selected row. 
     
     
       20. The method of claim 13 wherein the first computer is a server computer sharing data in the first collection with a plurality of client computers and the second computer is a client computer. 
     
     
       21. The method of claim 13 wherein the step of synchronizing comprises limiting the synchronizing of data between the computers using row and column filtering of the data. 
     
     
       22. The method of claim 13 further comprising the step of storing a before-image collection of data on the second computer, the before-image collection having before-image data stored therein, the before-image data having values representing the state of the second collection at a time of last synchronization with the first collection. 
     
     
       23. The method of claim 13 further comprising the step of storing a second update log on the second computer, the second update log including a history of modifications to the columns of the second collection in the shared list. 
     
     
       24. The method of claim 13 wherein the first database is a relational database and the second database includes data accessible as tabular data. 
     
     
       25. A method for synchronizing a plurality of tabular databases, each database maintained on a respective computer for storing a respective array of data fields arranged in rows and columns, comprising the steps of: creating a table correspondence which defines selected columns of a first table on a first computer as being common columns in the respective tables stored on the first computer and at least one other computer, each selected column of the first table corresponding to a respective replica column of a second table on a second computer;   defining a first catalog on the first computer from the table correspondence, the first catalog including an ordered list of the selected columns of the first table;   defining a second catalog on the second computer from the table correspondence, the second catalog including an ordered list of the replica columns of the second table, the list of replica columns in the second catalog ordered to match the order of the list of selected columns in the first catalog;   for a modified row of one of the tables, determining at least one column having modified data therein;   at the respective computer, encoding the at least one modified column of the modified row into a column indicator derived from the ordered list of replica columns in the respective catalog;   at the respective computer, building a modification message including the column indicator; and   transmitting the modification message to propagate the modified row from the respective computer to the other computer.   
     
     
       26. The method of claim 25 wherein the step of determining comprises constructing before values of data fields stored in the second table from a set of logged modification operations and comparing the before values with respective current values. 
     
     
       27. The method of claim 25 wherein the step of determining comprises detecting at least one difference between current values of data fields stored in the second table with before values of respective data fields stored in a before-image of the second table, the before values representing a time of last synchronization between the first and second tables. 
     
     
       28. The method of claim 27 wherein the before-image excludes a data field stored in the second table which is not updatable in the second table. 
     
     
       29. The method of claim 25 further comprising the step of validating a last synchronization of the first and second tables using before values of the data fields, the before values representing the values of data fields in the second table at a time of the last synchronization. 
     
     
       30. The method of claim 25 wherein the table correspondence defines a first subset of the first table and a second subset of the second table. 
     
     
       31. The method of claim 25 wherein the step of encoding comprises determining a respective index into the respective catalog for each modified column. 
     
     
       32. The method of claim 31 wherein the column indicator is a bitmapped value encoding the respective indices of a plurality of modified columns. 
     
     
       33. The method of claim 31 wherein the step of encoding comprises dynamically selecting an encoding technique based on the resulting size of the column indicator. 
     
     
       34. The method of claim 25 wherein the step of transmitting the update message comprises establishing a temporary communication link between the first and second computers prior to transmitting the modification message. 
     
     
       35. The method of claim 25 further comprising the steps of: receiving the modification message at the first computer; and   updating a corresponding row in the first table from the modification message.   
     
     
       36. The method of claim 25 wherein the step of determining comprises detecting at least one difference between current values of data fields stored in the first table and deduced current values of data fields stored in the second table. 
     
     
       37. The method of claim 36 wherein the step of detecting comprises deducing the current values of data fields stored in the second table from an update log having stored therein a history of modifications to the first table maintained on the first computer. 
     
     
       38. The method of claim 25 further comprising the steps of: receiving the modification message at the second computer; and   updating a corresponding row in the second table from the update message.   
     
     
       39. The method of claim 25 wherein the first and second databases are heterogenous. 
     
     
       40. The method of claim 25 wherein at least one of the tabular databases is a relational database. 
     
     
       41. A database synchronizer for synchronizing a plurality of tabular databases, each database maintained on a respective computer for storing an array of data fields arranged in rows and columns, the database synchronizer comprising: a table correspondence which defines selected columns of a first table on a first computer as being common columns in the respective tables stored in the first computer and at least one other computer, each selected column of the first table corresponding to a respective replica column of a second table on a second computer;   a first catalog derived from the table correspondence and stored on the first computer, the first catalog including an ordered list of the selected columns of the first table;   a second catalog derived from the table correspondence and stored on the second computer, the second catalog including an ordered list of the replica columns of the second table, the list of replica columns in the second catalog ordered to match the order of the list of selected columns in the first catalog;   for a modified row of one of the tables, at least one column having modified data therein;   at the respective computer, a column indicator having encoded therein the at least one modified column of the modified row, the column indicator derived from the ordered list of columns in the respective catalog;   at the respective computer, a modification message which includes the column indicator; and   a transmission link for transmitting the modification message to propagate the modified row from the respective computer to another computer.   
     
     
       42. The database synchronizer of claim 41 further comprising a set of logged modification operations for data fields of the second table. 
     
     
       43. The database synchronizer of claim 41 further comprising a before-image of the second table having before values of the data fields of the second table, the before values representing a time of last synchronization between the first and second tables. 
     
     
       44. The database synchronizer of claim 43 wherein the before-image excludes a data field stored in the second table which is not updatable in the second table. 
     
     
       45. The database synchronizer of claim 41 wherein the table correspondence defines a first subset of the first table and a second subset of the second table. 
     
     
       46. The database synchronizer of claim 41 wherein the column indicator comprises a respective index into the respective catalog for each modified column. 
     
     
       47. The database synchronizer of claim 46 wherein the column indicator is a bitmapped value encoding the respective indices of a plurality of modified columns. 
     
     
       48. The database synchronizer of claim 46 wherein the column indicator is encoded by an encoding technique based on the resulting size of the column indicator. 
     
     
       49. The database synchronizer of claim 41 wherein the communication link is temporary. 
     
     
       50. The database synchronizer of claim 41 further comprising a corresponding row in the first table updated from data in the modification message. 
     
     
       51. The database synchronizer of claim 41 further comprising: an update log having stored therein a history of modifications to the first table maintained on the first computer; and   before values of the data fields of the second table deduced from the update log.   
     
     
       52. The database synchronizer of claim 41 further comprising a corresponding row in the second table updated from data in the modification message. 
     
     
       53. The database synchronizer of claim 41 wherein the first and second databases are heterogenous. 
     
     
       54. The database synchronizer of claim 41 wherein at least one of the tabular databases is a relational database.