Time stamping of database records

• US 6,754,657 B2
• Filed: 08/24/2001
• Issued: 06/22/2004
• Est. Priority Date: 08/24/2001
• Status: Active Grant

• Current Assignee: ServiceNow Incorporated
• Original Assignee: Microsoft Corporation
• Inventors: Lomet, David Bruce
• Primary Examiner(s): Mizrahi, Diane D.
• Application Number:
  US09/939,180
• Publication Number:
  US 20030055807A1
• Time in Patent Office: 1,033 Days
• Field of Search: 707/8, 707/103.R, 707/201, 707/204, 707/203, 707/2, 707/4, 718/101, 709/213, 717/100, 714/6, 345/619
• US Class Current: 1/1
• CPC Class Codes: G06F 16/2322 using timestamps
• CPC Class Codes: G06F 16/2477 Temporal data queries
• CPC Class Codes: Y10S 707/99938 Concurrency, e.g. lock management in shared database
• CPC Class Codes: Y10S 707/99952 Coherency, e.g. same view to multiple users
• CPC Class Codes: Y10S 707/99953 Recoverability

Abstract

A method of assigning timestamps to data items processed by a transaction. The method sets initial upper and lower limits for a transaction timestamp that will be applied to data items processed by the transaction if the transaction does not abort. The upper and lower limits are incrementally updated as data items are processed and time intervals are requested by the transaction. The lower limit is incrementally updated as data items are processed to ensure that write-write, read-write and write-read conflicts are avoided. A transaction timestamp is selected that is greater than the lower limit, but less than the upper limit.

Claims

1. For use with a temporal database, a method of processing multiple transactions that read and write data in the database, comprising:

a) setting a transaction timestamp lower limit when a data item is read to the larger of a time the data item was written and a current timestamp lower limit;

b) setting the transaction timestamp lower limit when a data item is written to the largest of a time the data item was previously written, a time the data item was last read, and the current timestamp lower limit;

c) setting the transaction timestamp lower limit when a time interval is requested by a transaction to the larger of the current lower limit and a start of a time interval requested;

d) setting a transaction timestamp upper limit when a time interval is requested by a transaction to the smaller of a current upper limit and a end of the time interval requested; and

e) assigning a transaction timestamp to a value between said transaction timestamp lower limit and said transaction timestamp upper limit.

2. The method of claim 1 further comprising aborting a transaction when the timestamp lower limit is greater than or equal to the timestamp upper limit.

3. The method of claim 1 further comprising restricting write access to a data item when the data item is being read by a transaction and restricting read and write access to a data item when the data item is being written by the transaction.

4. The method of claim 1 further comprising determining whether a time interval has been requested by the transaction and setting the timestamp upper limit to a finite value only when a time interval has been requested by the transaction.

5. The method of claim 1 further comprising storing a list of all data items read by a transaction, storing a list of all data items inserted by a transaction, and storing a list of all data items deleted by a transaction.

6. The method of claim 5 further comprising comparing the transaction timestamp to the time each data item read by the transaction was last written and aborting the transaction when the transaction timestamp is less than the time the transaction was last written.

7. The method of claim 5 further comprising comparing the transaction timestamp to the time each data item written by the transaction was last written and aborting the transaction when the transaction timestamp is less than the time the transaction was last written.

8. The method of claim 5 further comprising comparing the transaction timestamp to the time each data item written by the transaction was last read and aborting the transaction when the transaction timestamp is less than the time the transaction was last read.

9. The method of claim 5 further comprising storing last read values for data items in a hash table, comparing a last read value in the hash table associated with each data item written by the transaction with the transaction timestamp and aborting the transaction when a last read value associated with a data item written is greater than the transaction timestamp.

10. The method of claim 1 further comprising storing last read values in a hash table and accessing the hash table to assign a conservative time a data item was last read to set the lower transaction limit when a data item is written.

11. The method of claim 1 wherein read timestamps are assigned to corresponding sets of data items by applying a hash function to data items.

12. For use with a temporal database, a method of processing multiple transactions that read and write data in the database, comprising:

a) determining whether a time interval has been requested by a transaction;

b) setting a transaction timestamp lower limit when a data item is read to the larger of a time the data item was last written and a previous timestamp lower limit;

c) setting the transaction timestamp lower limit when a data item is written to the largest of a time the data item was previously written, a time the data item was last read, and the previous timestamp lower limit;

d) assigning a transaction timestamp to a value that is greater than the timestamp lower limit when it is determined that a time interval has not been requested by the transaction;

e) setting a transaction timestamp upper limit corresponding to an end of the time interval requested by a transaction;

f) setting a transaction timestamp lower limit which is the larger of the current timestamp lower limit and a start of the interval requested by a transaction; and

,

g) assigning a transaction timestamp a value that is greater than the timestamp lower limit and less than or equal to the timestamp upper limit when it is determined that a time interval has been requested by the transaction.

13. The method of claim 12 wherein the time interval requested by the transaction is the result of a SQL CURRENTTIME request.

14. The method of claim 12 further comprising aborting a transaction when the timestamp lower limit is greater than or equal to the timestamp upper limit.

15. The method of claim 12 further comprising restricting write access to a data item when the data item is being read by a transaction and restricting read and write access to a data item when the data item is being written by the transaction.

16. The method of claim 15 further comprising comparing the transaction timestamp to the time each data item written by the transaction was last read and aborting the transaction when the transaction timestamp is less than the time the transaction was last read.

17. The method of claim 12 further comprising storing a list of all data items read by a transaction and storing a list of all data items written by a transaction.

18. The method of claim 17 further comprising comparing the transaction timestamp to the time each data item read by the transaction was last written and aborting the transaction when the transaction timestamp is less than the time the transaction was last written.

19. The method of claim 17 further comprising comparing the transaction timestamp to the time each data item written by the transaction was last written and aborting the transaction when the transaction timestamp is less than the time the transaction was last written.

20. The method of claim 17 further comprising storing last read values for data items in a hash table, comparing a last read value in the hash table associated with each data item written by the transaction with the transaction timestamp and aborting the transaction when a last read value associated with a data item written is greater than the transaction timestamp.

21. The method of claim 12 further comprising storing last read values in a hash table and accessing the hash table to assign a conservative time a data item was last read to set the lower transaction limit when a data item is written.

22. For use with a temporal database, a method of processing multiple transactions that read and write data in the database, comprising:

a) assigning read timestamps to corresponding sets of data items;

b) setting a transaction timestamp lower limit when a data item is read to the larger of a time the data item was written and a previous timestamp lower limit;

c) setting the transaction timestamp lower limit when a data item is written to the largest of a time the data item was previously written, a read timestamp assigned to a set of data items corresponding to the data item being written, and the previous timestamp lower limit;

d) setting a transaction timestamp to a value that is greater than the timestamp lower limit.

23. The method of claim 22 wherein the read timestamps are assigned to corresponding sets of data items by applying a hash function to data items.

24. The method of claim 22 further comprising restricting write access to a data item when the data item is being read by a transaction and restricting read and write access to a data item when the data item is being written by the transaction.

25. The method of claim 22 further comprising determining whether a time interval has been requested by the transaction and setting a timestamp upper limit when a time interval has been requested by the transaction.

26. The method of claim 22 further comprising storing a list of all data items read by a transaction and storing a list of all data items written by a transaction.

27. The method of claim 26 further comprising comparing the transaction timestamp to the time each data item read by the transaction was last written and aborting the transaction when the transaction timestamp is less than the time the transaction was last written.

28. The method of claim 26 further comprising comparing the transaction timestamp to the time each data item written by the transaction was last written and aborting the transaction when the transaction timestamp is less than the time the transaction was last written.

29. The method of claim 26 further comprising comparing the transaction timestamp to the time each data item written by the transaction was last read and aborting the transaction when the transaction timestamp is less than the time the transaction was last read.

30. The method of claim 26 further comprising storing read timestamps for data items in a hash table, comparing the read timestamps in the hash table associated with each data item written by the transaction to the transaction timestamp and aborting the transaction when a last read value associated with a data item written is greater than the transaction timestamp.

31. The method of claim 22 further comprising storing the read timestamps in a hash table and accessing the hash table to assign a conservative time a data item was last read to set the lower transaction limit when a data item is written by the transaction.

32. For use with a temporal database, a method of processing multiple transactions that read and write data in the database, comprising:

a) storing read times in entries of a table that correspond to sets of data items;

b) assigning a transaction timestamp to a transaction;

c) storing a list of all data items read by the transaction;

d) accessing entries in said table that correspond to each data item read by said transaction; and

e) updating the read time of each accessed entry of the table to the transaction timestamp when the transaction timestamp is greater than the read time stored in the entry of the table.

33. The method of claim 32 wherein sets of data items are assigned to each entry of the table by a hash function.

34. The method of claim 32 further comprising restricting write access to a data item when the data item is being read by a transaction and restricting read and write access to a data item when the data item is being written by the transaction.

35. For use with a temporal database, a method of processing multiple transactions that read and write data in the database, comprising:

a) restricting write access to a data item when the data item is being read by a transaction;

b) restricting read and write access to a data item when a data item is being written by the transaction;

c) determining whether a time interval has been requested by the transaction;

d) assigning read timestamps to corresponding sets of data items;

e) storing said read timestamps in a read timestamp table;

f) setting a transaction timestamp lower limit when a data item is read to the larger of a time the data item was written and a previous timestamp lower limit;

g) setting the transaction timestamp lower limit when a data item is written to the largest of a time the data item was previously written, a read timestamp stored in the read timestamp table corresponding to the data item being written, and the previous timestamp lower limit;

h) setting a transaction timestamp upper limit corresponding to an end of the time interval requested by the transaction when it is determined that a time interval has been requested by the transaction;

i) assigning the transaction timestamp a value between said transaction timestamp lower limit and said transaction timestamp upper limit;

j) storing in memory a list of each data item read by the transaction;

k) storing in memory a list of each data item inserted by the transaction;

l) storing in memory a list of each data item deleted by the transaction;

m) comparing the transaction timestamp to the time the data item was written for each read, inserted and deleted data item;

n) aborting the transaction when the time a data item written is greater than the transaction timestamp;

o) comparing the transaction timestamp to a value in the read timestamp table that corresponds to each inserted and deleted data item;

p) aborting the transaction when the value in the read timestamp table that corresponds to the inserted and deleted data items is greater than the transaction timestamp;

q) committing the transaction; and

r) setting the read timestamps in the read timestamp table for the corresponding sets of data items to the greater of the transaction timestamp and a previous read timestamp for each data item read.

36. The method of claim 35 wherein the read timestamps are stored in storage locations of a hash table and a hash function determines the read timestamp assigned to each set of data items.

37. The method of claim 36 wherein the hash table is accessed to set the transaction timestamp lower limit when a data item is written.

38. The method of claim 36 wherein the transaction timestamp is compared to a value in the hash table that corresponds to each inserted and deleted data item.

39. The method of claim 36 wherein the read timestamps stored in the hash table are set to the greater of the transaction timestamp and the previous read timestamp stored in the storage location for each data item read.

40. A method for use with a temporal database during execution of transactions over the database wherein a given transaction may both read and write data within the database comprising:

a) setting an initial transaction timestamp lower limit;

b) during a first phase of transaction execution, updating said lower limit based on reading and writing of data so that;

i) if data is being read, updating the time stamp lower limit to a time at least as large as the time the data was written, and

ii) if data is being written, updating the time stamp lower limit to a time at least as large as the time the data was previously written or updating the time stamp lower limit to a time as large as the time the data was read;

c) during a second phase of transaction execution, after a request for a current time is processed, evaluating said lower limit based on reading and writing of data so that;

i) if data is being read, and the lower limit is less than the time the data was last written aborting the transaction,

ii) if data is being written, and the lower limit is less than the time the data was previously written or the lower limit is less than the time the data was read, aborting the transaction; and

d) committing the transaction by finalizing the reading and writing of data to the database unless the transaction aborted during the second phase of transaction execution.

41. The method of claim 40 wherein the committing of the transaction assigns a read time stamp to data read by the transaction as the lower limit and wherein a write time stamp is assigned to the data written by the transaction is set to the lower limit.

42. The method of claim 41 wherein the read time stamp of data read by the transaction is stored in a memory wherein multiple database data records share a memory location for said read time stamps.

43. The method of claim 42 wherein a storage location for a read time stamp is determined by a function that maps multiple data records to a single memory location.

44. The method of claim 43 wherein the function is a hash function that points to a hash storage table.

45. The method of claim 44 wherein a hash table is set up for each data table of the temporal database and wherein the hash function determines a storage location within its hash table based upon a key value in the temporal database table.

46. The method of claim 40 wherein the request for current time is accompanied by establishing an upper limit and wherein the transaction aborts if thelower limit exceeds the upper limit.