Time stamping of database records

Details Time stamping of database records Time stamping of database records

2001-08-24

2004-06-22

Mizrahi, Diane D. (Department: 2175)

Data processing: database and file management or data structures

Database design

Data structure types

C707S793000, C707S793000

Reexamination Certificate

active

06754657

ABSTRACT:

FIELD OF THE INVENTION
The present invention concerns temporal databases and, more particularly, relates to time stamping of data items associated with a transaction.
BACKGROUND ART
A conventional database relation contains sets of records. Insertions, updates and deletions occur over time. It is frequently important to retain a perfect record of past database states. In many applications, such as financial, banking, insurance and medical applications it is desirable to maintain a database that can access not only the current set of records, but also a set of records that was current at a specified time. For example, the practice in financial applications is for accountants to correct errors, not by using an eraser, but by posting compensating transactions to the books. A bank must be able to determine the balance of a customer's account as of a certain day. In medical applications, the basis on which decisions were made are documented to guard against malpractice lawsuits.
A database having transaction time support allows not only the current state of the database to be accessed, but also previous states of the database to be accessed. A transaction time supported database provides accountability or traceability of the database records, which is important in databases used in financial, insurance, medical and other applications.
A transaction time relation consists of a set of data items, which may be thought of as a set of records. A start time d.TT
and an end time d.TT
are maintained by the system for each data item d. The start time d.TT
and the end time d.TT
define the time interval (d.TT
, d.TT
) during which each data item d was part of the current database state. This is a semi-open interval that includes d.TT
but excludes d.TT
, ensuring that a data item never has more than one value at any time. The start time d.TT
records the time when the data item d became part of the current state of the database and the end time d.TT
records when the data item d ceased to be part of the current state of the database.
A transaction that inserts the data item d sets the start time d, also referred to a write timestamp, TT
to the current time t
current
. The insertion sets the end time d.TT
to a variable now that is continuously updated to the current time. The data item having a start time d.TT
and an end time d.TT
set to the variable now is a current data item d within the database. The data item d remains a current data item until the data item d is explicitly deleted by a delete or update transaction. A transaction that deletes the data item d sets the end time d.TT
to the current time t
current
, indicating that the data item d ceased to be current at the transaction time t
current
. Update transactions are typically implemented as deletions of the original data item d to be updated followed by an insertion of the updated data item d.
A common query in a database having transaction time support is termed a time slice. A time slice asks for the set of data items that were current at some past time t. The time slice query is answered by finding each data item d having a start time d.TT
on or before the past time t requested and an end time d.TT
that was on or after the time t requested. The time slice at time t returns the state of the database that was current at the past time t.
When user specified transactions are supported, it is necessary to use the same timestamp value for all statements in the same transaction. It would be possible for a time slice to return an inconsistent database state if the same timestamp is not used for all statements in a single transaction. Using the same timestamp for all statements of a transaction makes all actions of a transaction conceptually take place at the same time. However, the SQL standard currently allows different statements in the same transaction to use separate timestamp values.
The specific choice of the time that is used for timestamping the data items of a transaction is essential to ensuring that any previous database state that can be retrieved via a time slice at a past time t is indeed the database state that was current at the past time t. If the transaction timestamp order does not agree with the serialization order of the transactions, it is possible that the time slice will return a database state that never existed as a current database state.
In the SQL database language, a query or modification can reference the current time, t
current
. The current time can be stored as an attribute in the database or used to query the database. For example, the current time t
current
can be used to retrieve the state of the database that was current ten minutes ago. Referencing the current time t
current
in a query can force the database management system to choose this time before a transaction commits. Choosing the current time before the transaction commits exposes the transaction to the risk that it will subsequently be discovered that the transaction timestamp given to the transaction and the timestamp values given to other transactions are not ordered in a way that is consistent with a valid transaction serialization order. Table 1 is a schedule of two transactions T
1
and T
2
that choose the current time as the transaction timestamp early in the transaction.
TIME
T
1
T
2
1
fix t
current
2
w((x,10,[1, now)))
3
fix t
current
4
w((y,31,[3, now)))
5
Commit
6
7
r((y,31,[3, now)))
8
w((z,14,[1, now)))
9
commit
Referring to Table 1, at Time 1 the timestamp for transaction T
1
timestamp is fixed at 1. At Time 2, transaction T
1
writes data item x and sets the start time for the data item x to 1 (the transaction's timestamp) and sets the end time for data item x to the continuously updating variable now, since the data item x is current. At Time 3, the transaction T
2
timestamp is fixed at 3. At Time 4, transaction T
2
writes the data item y and sets the start time for data item y to 3 (the transaction's timestamp) and sets the end time for y to the variable now, since the data item y is current. At Time 5, transaction T
2
commits. At Time 7, transaction T
1
reads the data item y. At Time 8, transaction T
1
, writes data item z and sets the start time for data item z to 1, transaction T
1
's timestamp. The end time for data item d
3
is set to the variable now, since the data item d
3
is current.
Table 1 illustrates that a time slice may not produce an accurate representation of the database at a given time t if the transaction timestamp order does not agree with serialization order. The transaction timestamp order shown in Table 1 is transaction T
1
, which fixes its timestamp at time 1, followed by transaction
2
, which fixes its timestamp at Time 3. However, there is a read-write conflict between transaction T
1
and transaction T
2
. Transaction T
1
reads data item y that is written by transaction T
2
. This read-write conflict puts transaction T
2
before transaction T
1
in any serializable schedule involving these two transactions, since data item y is written by transaction T
2
before data item y is read by transaction T
1
. As a result, the transaction timestamp order does not agree with the serialization order of the two transactions.
For simplicity of exposition, we elide the writes done to delete old versions when updates occurs. A read-write conflict on data item y between transactions T
1
and T
2
puts T
2
before T
1
in any serializable schedule involving these two transactions. In addition, T
1
chose its t
curren
value at Time 1, in preparation for the write statement at Time 2, while T
2
chose its t
curren
value at Time 3. Note also that this schedule is allowed by two-phase locking. This results in serialization order being different from timestamp order, and causes two potential problems. First, a timeslice for <y,z> for Time 2, issued at Time 6, returns <y=y
0
,z=z
0
> since T
2
has a time later than Time 2 and T
1
has not yet committed or even accessed z yet. However, the same timeslice (i.e., for Time 2), instead issued at Tim

Affiliated with

Also associated with

Rating

Time stamping of database records does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Time stamping of database records, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Time stamping of database records will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3310931