Abstract:
A system and method for synchronizing records stored in differing formats in a shared data environment. One aspect of the invention involves distinguishing a record without regard to its format. Once a record is introduced into the environment, it is detected. A record tag, unique to the environment, is generated and associated with the record. When synchronizing, only those records with equivalent record tags are compared and updated.

Description:
FIELD OF THE INVENTION 
   This invention relates to synchronizing electronic data. Specifically, this invention is directed to a method and system for synchronizing electronic data stored in differing formats. 
   BACKGROUND OF THE INVENTION 
   In today&#39;s computer networks, sharing data among devices has become desirable if not essential. Not only does the shared data need to be replicated on each device, but the set of replicated data must be synchronized so that changes made to one replica are reflected in all the others. Synchronization enables many users to work with their own local copy of shared data but have the shared data updated as if they were working on a single, centralized database. For shared data applications where users are geographically widely distributed, replication and synchronization are often the most efficient methods for effectively utilizing shared data. 
   In addition to desktop computers, workstations, and servers, modern computing environments often include lightweight handheld computing devices that fit into a pocket, purse, or day planner. Modern computing environments range from private networks to the Internet. Although a wide range of application programs can be executed on handheld computers, shared data applications are particularly popular and well suited for these devices. Shared data applications include, among many others, electronic calendars and task lists, electronic mail organizers, and electronic address books. A device running one or more of these applications stores electronic data that is or can be replicated and shared with other devices. It is desirable, if not essential, then to at least periodically synchronize data stored on each device. For example, many calendaring applications allow devices to share data or records concerning each user&#39;s appointments. It is important that when a new appointment is added or an existing appointment is modified on one device that addition or change is reflected on all devices providing calendaring. 
   Where the shared data applications on each device use the same data formats, synchronization is a relatively simple process. However, modern computing environments tend to be more complex, often having devices from multiple manufacturers, each with differing data formats making it difficult to accurately synchronize shared data. For example, where the data for one appointment is stored in one format on one device and in a second format on the other, synchronization sometimes results in the duplication of the appointment on each device. 
   SUMMARY OF THE INVENTION 
   The present invention is directed to a system and method for synchronizing records stored in differing formats in a shared data environment. One aspect of the invention involves distinguishing a record without regard to its format. Once a record is introduced into the environment, it is detected. A record tag, unique to the environment, is generated and associated with the record. When synchronizing, only those records with equivalent record tags are compared and synchronized. 

   
     DESCRIPTION OF THE DRAWINGS 
       FIG. 1  is a schematic representation of a shared data environment having a personal computer, a PDA (Personal Digital Assistant) and a server. 
       FIG. 2  is a block diagram illustrating the logical components of a device from  FIG. 1 . 
       FIG. 3  is a block diagram further illustrating the data store of  FIG. 2 . 
       FIG. 4  is a block diagram further illustrating a group from  FIG. 3 . 
       FIG. 5  is a block diagram further illustrating the database of  FIG. 2 . 
       FIG. 6  is a block diagram illustrating a logical communication path between the components of two devices when synchronizing records. 
       FIG. 7  is a flow chart illustrating the identification of a record new to a shared data environment. 
       FIGS. 8 and 9  are flow charts each further illustrating the act of generating from  FIG. 7 . 
       FIG. 10  is a flow chart illustrating the identification of a data store new to a shared data environment. 
       FIG. 11  is a flow chart further illustrating the act of generating from  FIG. 10 . 
       FIG. 12  is a flow chart illustrating synchronization of two data stores. 
   

   DETAILED DESCRIPTION OF THE INVENTION 
   INTRODUCTION: In today&#39;s mobile computing environment electronic records are replicated and shared across many devices. These devices store the electronic records in any number of varying formats. It is expected that by associating each record with a unique record tag, embodiments of the present invention will allow shared records stored in differing formats to be synchronized more effectively and more efficiently. 
   Although the various embodiments of the invention disclosed herein will be described with reference to the shared data environment  10  shown schematically in  FIG. 1 , the invention is not limited to use with shared data environment  10 . The invention may be implemented in or used with any electronic system in which it is necessary or desirable to synchronize shared data. The following description and the drawings illustrate only a few exemplary embodiments of the invention. Other embodiments, forms, and details may be made without departing from the spirit and scope of the invention, which is expressed in the claims that follow this description. 
   Referring to  FIG. 1 , computing system  10  represents generally an environment in which a variety of electronic devices  12  are linked. Devices  12  represent electronic devices such as, but not limited to, servers, personal computer workstations, and personal digital assistants. Communication link  14  interconnects devices  12  representing generally a cable, wireless, or remote connection via a telecommunication link, an infrared link, a radio frequency link, or any other connector or system that provides electronic communication between devices  12 . Communication link  14  may represent an intranet, an Internet, or a combination of both. The path followed by link  14  between devices  12  in the schematic view of  FIG. 1  represents the logical communication path between these devices, not necessarily the physical path between the devices. Devices  12  can be connected at any point and the appropriate communication path established logically between the devices. While each device  12  is shown attached to shared data environment  10 , any device  12  may be removed and later reconnected to link  18 . This is expected to be the case for devices such as PDA&#39;a and laptop computers. 
   COMPONENTS: Referring to  FIG. 2 , each device includes shared data application  16  and data store  18 . Shared data application  16  represents generally an e-mail client, electronic calendar and task list, an electronic address book or any other application capable of sharing data. Data store  18  embodies a logical memory location for storing electronic records used by shared data application  16 . Each record contained in database  18  typically represents a discrete item of shared data such as an e-mail, an appointment, a task, or an address. While  FIG. 2  illustrates device  12  as containing one shared data application  16  and one data store  18 , device  12  can contain any number of shared data applications  16  and data stores  18 . Moreover, shared data application  16  and data store  18  need not be located on device  12 . They need only be accessible by device  12 . 
   Each device  12  also includes synchronization (sync) engine  20 , database  24  and tag generator  26 . Sync engine  20  represents generally programming capable of synchronizing records in two or more data stores  18 . When contained in given data store  18 , each record is stored in a format native to a corresponding shared data application  16 . Records in different data stores  18 , then can be stored in any number of formats. To synchronize records stored using differing formats, sync engine  20  also includes programming capable of retrieving a record stored in a given format, translating that record into a second format, and modifying or creating second record using the translation. Database  24  contains files for each record in data store  18 . The files identify each record within the shared data environment  10  while indicating the status of the record—that is whether the record is new, unchanged, or has been modified or deleted. Tag Generator  26 , described in more detail below, represents generally any programming capable of uniquely identifying a record within shared data environment  10 . 
     FIG. 3  provides an example of a data store  18 . Data store  18  includes groups  28 . Groups  28  embody logical memory locations for containing records of differing types. In the example of  FIG. 3 , data store  18  includes e-mail, calendar, task list, and address book groups  28 .  FIG. 4  provides illustrates the logical components of any given group  28 . As shown, group  28  includes three records  30 . Each record  30  includes data  32  associated with a local identifier  34 . Local identifiers  34  embody electronic data used to identify a particular record  30  within data store  18 . Local identifiers  34  are usually created by shared data application  16  when storing a record  30  in data store  18 . A local identifier  34  may be something as basic as a file name or other electronic data appended to or associated with a record  30 . 
     FIG. 5  provides an example of the logical components of database  24 . Here, database  24  includes data store tag  36  and files  38 . Data store tag  36  represents electronic data used to uniquely identify a particular data store  18  within shared data environment  10 . Each file  38  includes local identifier  34  record tag  40 , and record status  42 . Using local identifier  34 , other each logical components  40  and  42  of a given file  38  are associated with a particular record  30  within a given data store  18 . Record tag  40  represents electronic data uniquely identifying an associated record  30  within shared data environment  10 . Record status  42  represents electronic data indicating the status of a given record  30 . For example, when a record  30  is first introduced into a data store  18  its status is “new.” When a record  30  has been altered, its status is “modified.” Other record status indicators include “deleted” 0  and “unchanged.” 
   The block diagrams of  FIGS. 1–5  show the architecture, functionality, and operation of one implementation of the present invention. If embodied in software, each block may represent a module, segment, or portion of code that comprises one or more executable instructions to implement the specified logical function(s). If embodied in hardware, each block may represent a circuit or a number of interconnected circuits to implement the specified logical function(s). 
   Also, the invention can be embodied in any computer-readable medium for use by or in connection with an instruction execution system such as a computer/processor based system or other system that can fetch or obtain the logic from the computer-readable medium and execute the instructions contained therein. A “computer-readable medium” can be any medium that can contain, store, or maintain the programming of the present invention for use by or in connection with the instruction execution system. The computer readable medium can comprise any one of many physical media such as, for example, electronic, magnetic, optical, electromagnetic, infrared, or semiconductor media. More specific examples of a suitable computer-readable medium would include, but are not limited to, a portable magnetic computer diskette such as floppy diskettes or hard drives, a random access memory (RAM), a read-only memory (ROM), an erasable programmable read-only memory, or a portable compact disc. 
   OPERATION: The operation of sync engine  20  and tag generator  26  will now be described with reference to the block diagram of  FIG. 6  and the flow diagrams of  FIGS. 7–12 .  FIGS. 7–9  provide examples of the steps taken to uniquely identify a record  30  within shared data environment  10 , while  FIGS. 10 and 11  provide examples of uniquely identifying a data store within shared data environment  10 .  FIG. 12  provides an example of the steps taken to synchronize records  30  contained in two data stores  18  and  18 ′. 
   Beginning with  FIG. 6 , only one sync engine  20  is needed to synchronize records  30  across any number of devices.  FIG. 6  illustrates sync engine  20  in communication with databases  24  and  24 ′, tag generators  26  and  26 ′, data stores  18  and  18 ′ and shared data applications  16  and  16 ′. Referring also now to  FIG. 7 , one of the shared data applications,  16  in this case, creates and introduces a new record  30  in corresponding data store  18  (step  50 ). Alternatively, a data store  18  containing new records  30  could be introduced into shared data environment  10 . The corresponding tag generator  26  detects the record&#39;s introduction (step  52 ) and generates a record tag  40  unique to shared data environment  10  (step  54 ). Tag generator  26  then associates the generated record tag  40  with the detected record  30  updating the corresponding datastore  18  or  18 ′ with a file  38  for the new record  30  (step  56 ). 
     FIG. 8  illustrates one embodiment of the steps taken to generate a record tag  40  unique to shared data environment  10 . Communicating with each database  32 , tag generator  26  identifies the record tags  40  and  40 ′ associated with all other records  30  and  30 ′ in shared data environment  10  (step  54 A). Tag generator  26  then repeatedly generates a new tag comparing that tag to the other record tags  40  and  40 ′ until the new tag is found to be unique (steps  54 B and  540 ).  FIG. 9  provides an alternative example of steps taken to generate a tag in step  54 . Tag generator  26  acquires the local identifier  34  for the new record  30  (step  54 D) and the data store tag  36  for the data store  18  containing the new record  30  (step  54 E). Tag generator  26  then combines or concatenates the acquired data  32  and  36  creating a record tag  40  (step  54 F). The embodiment illustrated in  FIG. 9  has the benefit of not requiring tag generator  26  to be connected to shared data environment  10  when generating a record tag  40 . Because the data store tag  36  is unique to the environment  10 , a combination of the data store tag  36  and the local identifier  34  is also unique. Tag generator  26 , then, can create a record tag  40  unique to shared data environment  10  while being disconnected from the environment  10 . 
     FIG. 10  illustrates the steps taken to generate a data store tag  36 . Typically, a new data store  36  is introduced into shared data environment  10  when either a new device  12  containing a data store is connected to environment  10  or when created by a given shared data application  16  or  16 ′ (step  58 ). In either case, tag generator  26  in this example detects the introduction of the data store  18  into shared environment  10  (step  60 ) and generates a data store tag  36  unique to the shared data environment  10  (step  62 ). Tag generator  26  associates the new data store tag  36  with the new data store  18  (step  64 ). It is envisioned that tag generator  26  will accomplish step  64  by establishing a database  24  for the new data store  18 . As described above, the database  24  will contain the new data store tag  36  and a file  38  for each record  30  found in the new data store  18 . 
     FIG. 11  provides an example of the steps taken to generate a data store tag  36  in step  62  of  FIG. 10 . Communicating with each database  32  in shared data environment  10 , tag generator  26  then identifies the data store tags  36  and  36 ′ associated with all other data stores  18  and  18 ′ in shared data environment  10  (step  62 A). Tag generator  26  then repeatedly generates a new data store tag comparing that tag to the other data store tags  36  and  36 ′ until the new tag is found to be unique (steps  62 B and  62 C). 
     FIG. 12  illustrates the steps taken to synchronize the two data stores  18  and  18 ′ in  FIG. 6 . Sync engine  20  identifies data stores  18  and  18 ′ (step  66 ) and acquires the record tags  40  and  40 ′ from databases  32  and  32 ′ for each record  30  and  30 ′ contained in data stores  18  and  18 ′ (step  68 ). Sync engine  20  compares each record tag  40  or  40 ′ from one database  32  or  32 ′ with the record tags  40 ′ or  40  the other database  32 ′ or  32  until it finds a match (step  70 ). Upon finding a match, sync engine  20  acquires and compares the record status  42  and  42 ′ for each record  30  and  30 ′ associated with the matching record tags  40  and  40 ′ and updates the records  30  and  30 ′ accordingly (step  72 ). It is envisioned that record tags  40  and  40 ′ will be scalar—a programming term referring to a string of letters, numbers, and/or other alphanumeric characters. When comparing scalar record tags  40  and  40 ′, sync engine  20  performs a scalar comparison of the record tags  40  and  40 ′. In other words, sync engine  20  determines whether a first record tag is equivalent to a second. 
   The following describes how two records might be updated based upon the record status of each:
     Modifying one record  30  to match the second record  30 ′ if the record status  42  for the first record  30  is indicates that the first record  30  is new or unchanged and the record status  42 ′ record for the second record  30 ′ indicates that the second record  30 ′ has been modified. Modifying may also include restoring a deleted record  30  if the record status  42 ′ for the other record  30 ′ indicates that the record  30 ′ has been modified at a time after the first record  30  was deleted.   Deleting one record  30  if the record status  42  for that record  30  is new or unchanged and the record status  42 ′ for the second record  30 ′ indicates that the second record  30  has been deleted. Deleting in this case may include deleting a record  30  if the record status  42  for that record  30  indicates that the record  30  has been modified while the record status  42 ′ for the other record  30 ′ indicates that it has been deleted at a time after the first record  30  was modified; and   Modifying each record  30  and  30 ′ in light of the other if the record status  42  and  42 ′ for each indicates that each has been modified.
 
When a record  30  is new to shared data environment  10 , comparing the new record&#39;s record tag  40  with the record tags  40 ′ will not reveal a match. In this case sync engine  20  replicates the new record  30  in the other data store  18 ′ and updates the other database  24 ′ with a file  38 ′ for the new record  40 ′. When finished, each data store  18  and  18 ′ contain identical records  30  and  30 ′ associated with identical record tags  40  and  40 ′.
   

   Although the flowcharts of  FIGS. 7–12  show a specific order of execution, the order of execution may differ from that which is depicted. For example, the order of execution of two or more blocks may be scrambled relative to the order shown. Also, two or more blocks shown in succession in  FIGS. 7–12  may be executed concurrently or with partial concurrence. All such variations are within the scope of the present invention. The present invention has been shown and described with reference to the foregoing exemplary embodiments. It is to be understood, however, that other forms, details, and embodiments may be made without departing from the spirit and scope of the invention, which is defined in the following claims.