 |
Description  |
|
|
BACKGROUND OF THE INVENTION
This invention relates to programs that synchronize databases.
There are many situations in which it is important for a user to be able to
synchronize databases among computers. For instance, many users have
handheld computers, which typically weigh less than a pound, fit in a
pocket, and provide some combination of personal information management
functions, database functions, word processing functions, and spreadsheet
functions. Many users of handheld computers also own desktop computers
used for applications that manage databases similar to the databases
carried in handheld computers. Typically the user adds data to the two
computers independently, e.g., one enters data into the handheld computer
when out at a customer site but enters data into the desktop computer when
in the office. In such cases, the user normally would at some point want
to synchronize the databases on the handheld and desktop databases, i.e.,
automatically review changes made to the databases on the two computers,
and revise the data in both databases so that both have the same and most
current data.
Databases are collections of data organized as data records, each composed
of a number of data fields. For example, in an address database, a very
simple data record might be "John, Smith, Smith Co.", where "John" is the
information content of a FIRSTNAME field, "Smith" is the information
content of a LASTNAME field, and "Smith Co." is the information content of
a COMPANYNAME field.
Databases are managed by two broad classes of programs, database managers
and special-purpose application programs (both referred to herein as
database programs). A database manager is a program for managing general
databases, that is, databases in which the structure of the data records
can be specified at creation time by the user. Other databases are managed
by special-purpose application programs, e.g., a telephone directory
program of a handheld computer. Unlike the record structures of general
databases, the record structures of these special-purpose databases
typically are not specified by the user.
There are generally two ways in which software can specify a record in
these databases. One or more of the fields of a record can be designated
as a key, with particular records being specified by the contents of the
key (e.g., the above-mentioned address database might use the LASTNAME
field as a key, so that records could be specified by the contents of that
field). Records can also be specified using unique identification numbers
("unique IDs"), assigned by the database program at the time the record is
created.
There are known techniques for synchronizing databases, but they generally
depend on the databases having been specially designed to facilitate
synchronization. For example, MICROSOFT.TM. Schedule+ permits multiple
Schedule+ databases to be synchronized, but this is only possible because
Schedule+ was specially designed with synchronization in mind. Similarly,
directory databases built in conformance with the CCITT X.500
international standard can be synchronized by virtue of conforming to this
standard. One way in which synchronization is achieved in such products is
by the use of unique IDs assigned when a record is created. During
synchronization, the software is able to use the unique IDs to compare the
contents of corresponding data records in the two databases (e.g.,
corresponding data records for the same dinner appointment can be compared
even if the date, time, or description for the appointment has been
changed in one or both databases).
Another feature available for synchronizing databases specially designed
for synchronization are not-yet-synchronized flags, which are set whenever
a record is changed (e.g., when a dinner appointment is moved to a new
date and time). If the software finds a discrepancy during
synchronization, the program then checks each record's
not-yet-synchronized flag and, if one flag is set and the other is not,
the data in the record with the set flag prevails because it is assumed to
be newer. If both flags are set, the data transfer program resorts to
using a trump rule (e.g., handheld always prevails over desktop) or
interacting with the user because the program does not have enough
information to choose one over the other. After synchronization all of the
flags are reset.
Also available when databases have been specially designed for
synchronization is a time-and-date-of-last-modification stamp for every
record stored in the databases. Assuming sufficiently accurate
synchronization of the time-and-date clocks of the computers running the
databases, the synchronization program can always determine, even if both
of the corresponding items have been changed since last synchronization,
which change is the most recent, and assume that the more recent record
prevails. But such time and date stamping of records will typically be
impracticable owing to the scarcity of memory and file space, especially
on a handheld computer.
With databases not specially designed for synchronization, there has not
heretofore been any practical technique for synchronization. It has been
necessary to use either (1) brute force replacement of all of the records
of one database with all of the records of the other (e.g., using software
such as LapLink) or (2) a reconciliation technique developed by
IntelliLink Corp., of Nashua, N.H. (described in U.S. patent application
Ser. No. 07/867,167, now U.S. Pat. No. 5,392,390 filed on Apr. 10, 1992;
incorporated by reference).
IntelliLink's reconciliation technique uses key fields (e.g., the date and
time of appointments in a calendar database) to establish a correspondence
between records of the two databases, and then examines the records for
differences (e.g., a different appointment description for the same date
and time). The differences are reconciled either by invoking one or more
trump rules (e.g., handheld always prevails over desktop) or by
interacting with the user (e.g., by displaying the relevant mismatching
information and asking the user to choose).
An advantage of the reconciliation technique is its ability to handle
disparate databases (e.g., databases with different data structures,
designed for use with different application software and on different
computer platforms). To do its job, the IntelliLink reconciliation
technique does not require the presence of special
synchronization-enabling features such as unique IDs, not-yet-synchronized
flags, or time-and-date-of-last-modification stamps. It can work with
databases of radically different design, by first translating the
differently structured databases into a common intermediate format, and
then using key fields to establish correspondence between records. Yet
despite those advantages, and the fact that the reconciliation technique
was a huge improvement over the brute force replacement technique that
existed before it, reconciliation still falls short of real
synchronization.
One difficulty with the existing reconciliation technique is that unless a
trump rule such as "handheld always prevails over desktop" is employed,
the user is interrogated every time there is a data mismatch, and that
interrogation necessarily takes up a lot of time.
In addition, the reconciliation technique does not handle data deletions
well, because it inherently assumes that if an item on one computer is
empty and its corresponding item on the other computer is not, the empty
item should be updated with the non-empty item. This means, e.g., that
when a user deletes an appointment from a calendar database on one
computer, that appointment could be restored during reconciliation,
defeating the user's attempt to delete it.
SUMMARY OF THE INVENTION
The invention makes possible synchronization of disparate databases,
overcoming the shortcomings of the prior reconciliation technique. It does
so by providing a status file which allows the synchronization program to
determine if data records in one or more databases have been changed or
deleted since the last synchronization, or whether new data records have
been added.
Preferably, the status file contains the data present in the two databases
after the most recent synchronization. Corresponding sets of records are
chosen from each of the two databases and from the status file, and a
comparison is made of the information content of the records. Based on
that comparison, updating decisions are made for each set of records, for
example, decisions are made whether to select the information content of
one database record over the information content of the other, and finally
the selected information is written to the status file as well as the
databases.
The invention makes it possible to synchronize databases of radically
different design, operating on different computer platforms. E.g., a
calendar database proprietary to a particular handheld computer or
personal digital assistant (PDA) can now be synchronized with a calendar
database running on a user's desktop (e.g., LOTUS Organizer.TM., or
MICROSOFT.TM. Schedule+).
With the invention, it becomes quite practical for a person to use both a
PDA and a desktop calendar database in a group scheduling environment,
i.e., one in which calendar databases are interconnected between users so
that appointments may be added and deleted automatically. Now if an
appointment is added or deleted on one database, for example, the user's
desktop, the synchronization process of the invention can recognize that
such has occurred and automatically update the other during a
synchronization.
Synchronization of disparate databases can be performed with much less user
interaction than was necessary with the prior reconciliation technique.
E.g., by applying a rule that newer database changes prevail over older
changes, in connection with a preferred decision matrix, the user can
allow synchronization to occur with minimal or no interaction.
The invention permits databases that were specially designed for
synchronization to be synchronized with databases that were not so
designed. Embodiments of the invention can work with databases that
provide time-and-date-of-last-modification stamps, not-yet-synchronized
flags, or unique IDs, but also with databases that provide no such stamps,
flags, or IDs.
The invention also provides a backup function for information in a database
because the status file can be used to reconstruct a complete, earlier
version of the database.
The invention may be used to synchronize two or more databases on the same
computer or on different computers.
Other features and advantages of the invention will be apparent from the
following description of preferred embodiments, and from the claims.
BRIEF DESCRIPTION OF THE DRAWINGS
FIG. 1 illustrates both a handheld and a desktop computer, and shows,
diagrammatically, a database and data records for each.
FIG. 2 shows a handheld database, status file, desktop database, and
temporary workspace of a preferred embodiment of the invention.
FIG. 3 is a flowchart of the preferred embodiment.
FIGS. 4-6 are three sections of a flowchart showing the preferred
embodiment in more detail.
DESCRIPTION OF THE PREFERRED EMBODIMENTS
Shown in FIG. 1 are two computers on which disparate databases reside, a
database 7 in a handheld computer 1 and a database 11 in a desktop
computer 3. Synchronization depends on knowledge of: (1) how records 5 in
one database 7 correspond to records 9 in the other 11 and (2) the history
of updates in each database. For correspondence, the synchronization
program relies on the basic translation and mapping capabilities of the
prior IntelliLink reconciliation technique (e.g., as described in U.S.
patent application Ser. No. 07/867,167, now U.S. Pat. No. 5,392,390 filed
on Apr. 10, 1992, referred to earlier).
The synchronization program is typically run repeatedly over time. E.g.,
the user may choose to run synchronization daily, weekly, or on an
irregular "as needed" basis.
When conflicts are detected during synchronization (i.e., differences in
the content of key fields), they may be resolved automatically or
interactively, depending on user preference. The user may select among
different automatic rules, including:
1. Always propagate deletions even if that means deleting a recently
changed item.
2. Let handheld changes override desktop changes.
3. Let desktop changes override handheld changes.
4. Keep both versions and no longer attempt to reconcile them.
5. Leave the conflict unresolved.
If a conflict is to be resolved interactively, the user is presented with a
dialog box that allows the user to select one of these rules.
Since it is possible that a user may enter the same new information into
both the handheld and the desktop computer, the synchronization program
checks for this possibility in order to avoid duplication of data. The
program compares all new desktop records with all new handheld records,
and, when matches are found, the matches | | |
