Source: http://www.google.com/patents/US5287501?dq=U.S.+Patent+
Timestamp: 2013-12-09 14:15:27
Document Index: 280301337

Matched Legal Cases: ['arts 64', 'arts 64', 'art 64', 'art 64', 'art 104', 'art 104', 'art 64', 'art 122', 'art-122', 'art 122', 'art 122', 'art 122', 'art 122', 'art 122', 'art 64', 'art 122', 'art 122', 'art 122']

Patent US5287501 - Multilevel transaction recovery in a database system which loss parent ... - Google PatentsSearch Images Maps Play YouTube News Gmail Drive More »Advanced Patent Search | Sign inAdvanced Patent SearchPatentsWhen a subtransaction (46) of a higher-level transaction (50) commits during the operation of a database (10), the database enters into its operation log a record (FIG. 6 ) that acts both as a commit record for the subtransaction (46) and as an update record for the higher-level transaction and includes...http://www.google.com/patents/US5287501?utm_source=gb-gplus-sharePatent US5287501 - Multilevel transaction recovery in a database system which loss parent transaction undo operation upon commit of child transactionPublication numberUS5287501 APublication typeGrantApplication numberUS 07/728,661Publication dateFeb 15, 1994Filing dateJul 11, 1991Priority dateJul 11, 1991Fee statusPaidAlso published asDE69222169D1, DE69222169T2, EP0595925A1, EP0595925B1, WO1993001549A1Publication number07728661, 728661, US 5287501 A, US 5287501A, US-A-5287501, US5287501 A, US5287501AInventorsDavid B. LometOriginal AssigneeDigital Equipment CorporationPatent Citations (8), Non-Patent Citations (10), Referenced by (87), Classifications (11), Legal Events (5) External Links: USPTO, USPTO Assignment, EspacenetMultilevel transaction recovery in a database system which loss parent transaction undo operation upon commit of child transactionUS 5287501 AAbstract When a subtransaction (46) of a higher-level transaction (50) commits during the operation of a database (10), the database enters into its operation log a record (FIG. 6 ) that acts both as a commit record for the subtransaction (46) and as an update record for the higher-level transaction and includes a field (74) that identifies a higher-level "undo" transaction whereby the subtransaction can be undone without individually undoing its constituent operations. By logging operations in this manner, the database can handle multi-level recovery with very few restrictions on the timing of its updates and log entries.
A subroutine comprising a group of such operations is not inherently atomic or serializable, but it can be made so through the use of locks whose object resources are data blocks. A transaction is such a serializable subroutine. The concept of layers or levels enters the picture if a transaction itself comprises a plurality of transactions. In such a nested organization, not only is the transaction serializable with respect to other transactions, but its constituent "subtransactions" are serializable with respect to each other. The transactions can thus be seen to have a layered structure in which a transaction at one (lower) level comprising operations at that lower level can be thought of as an operation at the next-higher level, i.e., at the level of a transaction of which the lower-level transaction is a part. A plurality of lowest-level ("L.sub.0 ") operations that constitute an L.sub.0 transaction form an L.sub.1 operation, which can in turn be part of an L.sub.1 transaction that constitutes an L.sub.2 operation.
Different levels typically deal with different levels of abstraction. At L.sub.0, for instance, a transaction may be to subtract an amount from a record in a block explicitly specified by an argument of one transaction and add that amount to a corresponding record in another block similarly specified. The transaction designer--i.e., the implementor of the higher-level database software--should make such a transaction atomic if, for instance, it represents shifting money from one bank account to another, because the bank's books are "inconsistent" when they are in the state in which one part of the transaction has been performed without the other. Therefore, no transaction should be able to "see" the blocks involved until the L.sub.0 transaction is complete.
We will now consider a simple sequence of operations that illustrates the relationship between successive levels by showing the relationship between bottom-level (L.sub.0) operations and transactions and those at the next higher level (L.sub.1). FIG. 5 depicts this sequence.
The boxes in FIG. 5 represent operations. In particular, their horizontal positions represent the times at which the operations are logged and thus their order within the serially organized operation log 31; boxes further to the right represent records added later to the log. Arrows represent pointers such as the previous-operation field 34 of FIG. 4. Horizontally aligned boxes represent records of operations in the same transaction, i.e., records having the same contents in their transaction-ID fields, so FIG. 5 represents four transactions. Transactions 45, 46, and 48 are L.sub.0 transactions, while transaction 50 is an L.sub.1 transaction of which transactions 46 and 48 ar constituent operations. (Transaction 45 is an undo operation for the L.sub.1 operation that consists of transaction 46.)
The sequence of FIG. 5 begins with a request by a user--the "user" at this level typically being an L.sub.2 transaction--that the L.sub.1 transaction 50 be performed. The processor 14 begins the transaction and logs the L.sub.1 operation's start with an L.sub.1 start record 52, which represents no actual change of the data but is used in recovery, as will be explained below in connection with another start record. An L.sub.1 start record includes fields corresponding to the length, transaction-ID, and type fields 32, 36, and 38 of FIG. 4. Since the L.sub.1 transaction 50 is also an L.sub.2 operation, it will access one or more L.sub.2 resources. As it proceeds, therefore, it precedes each such access with a check of the lock table for a lock on the L.sub.2 resource to be accessed and continues only after any lock on that resource has been lifted. We will assume in the remaining discussion that no locks are present at any level except those acquired by the operations of the illustrated sequence.
The L.sub.1 transaction 50 then begins its first operation, namely, the L.sub.1 operation consisting of the L.sub.0 transaction 48. L.sub.0 transaction 48 commences by logging a start record 54 and making any necessary lock-table checks. L.sub.0 transaction 48 then proceeds with its first Lo operation by checking the lock table for the disk block to which that operation is directed. Under our assumption, that block is not already locked, so the operation continues with acquisition of its own lock, access of (typically the cache copy of) the object disk block, and logging of an update record 56.
Meanwhile, having commanded the start of its first L.sub.1 operation, the L.sub.1 transaction 50 commands the start of its second L.sub.1 operation, namely, L.sub.0 transaction 46. This transaction starts as transaction 48 did, and its initial stages are reflected in the operation log by a start record 58 and an update record 60. These follow each other in the log and are in turn followed by another update record 62, which represents an update in the first L.sub.0 transaction 48. All of these records are either update records and thus have the format depicted in FIG. 4 or are start records having a subset of the FIG. 4 fields.
According to the present invention, however, the next record 64 follows a format that is considerably different, as is suggested by its FIG. 5 representation's having two parts 64a and 64b that straddle two levels. This record is both the commit record for the L.sub.0 transaction 46 and what can be thought of as an update record for the L.sub.1 operation 46. It is an L.sub.1 update record in the sense that it indicates that updates for all of the constituent L.sub.0 operations of the L.sub.1 operation 46 have now been completed.
The two parts 64a and 64b relate to different levels. For example, the first type field 72a indicates an update of the results of the L.sub.1 operation 46, while the second type field 72b indicates that the L.sub.0 transaction 46 has committed. Similarly, the previous-record field 68a of the first part is, as the corresponding arrow 68a of FIG. 5 indicates, a pointer to the record 52 for the last L.sub.1 operation of the same L.sub.1 transaction 50, while the second previous-record field 68b is a pointer to the record 60 for the last L.sub.0 operation of the same L.sub.0 transaction 46. Also, while the first transaction-ID field 70a contains the ID of the L.sub.1 transaction 50 of which now-committed L.sub.0 transaction 46 is a constituent L.sub. operation, the second transaction-ID field 70b contains the ID of the L.sub.0 transaction 46 whose commitment it is the purpose of record part 64b to record.
This is what happens upon the event that record 64 reflects; i.e., the lock table receives a lock record directed to each L.sub.1 resource to which operation 46 is directed, and it loses the (more-restrictive) L.sub.0 lock acquired at the beginning of the operation that update record 60 documents. With locks maintained only at the L.sub.1 level, undo recovery will have to be performed at that level, and field 74 contains the data and routine-identifying information for that L.sub.1 operation. Undo field 74 is thus like undo field 42 except that it refers to a higher-level undo operation. Although L.sub.0 transaction (L.sub.1 operation) 46 is depicted as comprising only one loggable event other than its start and commitment, an L.sub.1 or higher operations may in general be complicated enough to have as its object more than one L.sub.1 resource, and part of the operation may be to identify those resources according to certain criteria. For this reason, the L.sub.1 update record 64a of FIG. 6 is not shown as having a resource-ID field separate from the transaction-undo field 74, which may identify a routine for identifying object resources not explicitly identified in the record.
Transaction 46 has now committed, but transaction 48 has not, and it proceeds with an L.sub.0 operation documented by a further update record 75. Before transaction 48 can commit, however, a processor crash occurs that FIG. 5 represents with a jagged line 76. That is, the database has been left in a state in which transactions 48 and 50 are both "active": they have both started but not committed. To provide the required atomicity, therefore, a recovery process must occur before ordinary database operation resumes.
One type of redo operation that one might use in implementing the present invention scans forward from a point in the log indicated by a conventionally established checkpoint, reading each L.sub.0 update record's resource field and then checking the disk data block designated thereby for the contents of its log-sequence-number ("LSN") field. This field indicates how recently that data block was durably updated. As was stated above, the log-writing routine assigns log sequence numbers to log records in a monotonically increasing sequence. That routine therefore always has available a next-record pointer representing the location of the next log record to be written. When the persistent data store 18 is updated by replacing disk-block contents with those of the corresponding modified ("dirty") volatile-cache blocks, a copy of the then-current next-record pointer is placed in the disk block's LSN field. Therefore, if the LSN field of a block in the disk data store 18 has an LSN higher than that of the log record that designates that block, the disk block has been updated since the operation reflected in the log record, and that operation does not have to be redone. Otherwise, it is redone and the results are written into the designated disk data block along with the LSN of the next record in the redo scan.
When the redo procedure has ended, the undo procedure begins. Since all undo operations for a given level are based on the assumption that no transactions at any lower level remain active, the backward process must be performed for each level individually, beginning with the bottom level. Consequently, as the bottom-level undo process proceeds backward through the log record, it performs undo operations only for log records that represent L.sub.0 operations. At the same time, however, it may also copy every other, higher-level log record into a level log, typically compiled in the RAM so as to expedite subsequent undo passes, dedicated to the level to which that log record's operation is directed.
In any event, the undo phase of the recovery procedure begins with the last L.sub.0 operation to occur, i.e., with the first L.sub.0 operation encountered in a backward scan of the log. Update record 75's transaction-ID field identifies L.sub.0 transaction 48, for which the redo procedure has not encountered a commit record. That operation's transaction therefore is still active, so its operations must be undone to preserve atomicity. The undo operation identified by record 75's undo field is accordingly performed, and a compensation log record 80 documents that undo operation. FIG. 7 depicts a typical compensation log record in pertinent detail.
Like the record of FIG. 4, that of FIG. 7 includes length and type fields 81 and 82, which have the same purposes as the corresponding fields 32 and 38 of FIG. 4. A transaction-ID field 84 identifies the transaction that contains the operation undone by the "inverse operation" that the compensation log record documents. A previous-operation field 86 similarly contains the LSN of the record for the previous operation in that transaction. Like the corresponding field 34 in the FIG. 4 L.sub.0 update record, field 86 is intended primarily to save time in aborting individual transactions in response to a user command rather than in crash recovery, in which all log records must be accessed.
It is to prevent this duplication that a CLR's record-type field in the illustrated embodiment distinguishes it from an ordinary update record; in response to the record-type field's identifying a record as a CLR, the undo process can refrain from performing an undo operation in response to that record. The exemplary record of FIG. 7 therefore does not include an undo field. It does need a redo field 88, though, because of the write-ahead-logging protocol. Field 88 is called a "redo" field because, like field 44, it contains the information used in the redo process to re-execute the (undo) operation that its record 80 documents. Although the thus-identified routine is thus a "redo" of the CLR-represented operation, it is an "undo" of the transaction for which the CLR-represented operation compensates; i.e., redo field 88's contents are the same as those of record 75's undo field. Since record 80 documents an operation at the L.sub.0 level, the identification of its object resources is depicted as occurring in a field 89 separate from the redo field 88.
Having performed the undo operation identified by record 75's undo field and logged by record 80, the undo scan proceeds to record 64, which was described in connection with FIG. 6 as being both an L.sub.0 commit record and an L.sub.1 update record. As an L.sub.0 commit record, it requires no undo operation, and as an L.sub.1 update record, it requires undoing during the L.sub.1 undo pass, not during the current, L.sub.0 undo pass. It is therefore copied into the L.sub.1 level log without the addition of any record to the operation log 31.
The next L.sub.0 update record 62 corresponds to an operation in uncommitted transaction 48, so its operation is undone in an operation recorded in the next CLR 92.
Belonging to a transaction 46 pronounced committed by previously encountered commit record 64b, the operations represented by the next two records 60 and 58 that the recovery procedure encounters are not undone and thus cause no additions to the operation log 31. This is true even though transactions 46's commit record 64b is part of a double record whose other part 64a designates an L.sub. transaction 50 the absence of whose commit record has identified it as active. The reason for this is that the presence of an undo field 74 in record 64 identifies the L.sub.1 operation consisting of L.sub.0 transaction 46 as being one for which an L.sub.1 undo operation is available (and, consequently, for which the locks of its constituent operations were released when transaction 46 committed). Any undoing of transaction 46 will therefore occur by way of an L.sub.1 operation, not by individually undoing its constituent operations.
An undo operation documented by CLR 94 compensates for the operation that the next-encountered record 56 represents, and the recovery operation then adds to the operation log a normal commit record 96 in response to start record 54 so that a further crash will not cause the operations of transaction 48 to be undone again. (In practice, the type field of record 96 would usually distinguish it from commit records for forward transactions--i.e., record 96 would actually be an "abort" record--so as to enable a housekeeping routine to strip the log of the records of aborted transactions that have already been rolled back. For present purposes, however, an abort record is simply a commit record.) Finally, the L.sub.0 undo process identifies start record 52 as belonging to the L.sub.1 level because, for instance, its transaction-ID field specifies a transaction that the process has previously identified as being at level L.sub.1, so it copies that record into the L.sub.1 level log without adding to the operation log. This completes the L.sub.0 undo pass for the forward operations whose records FIG. 5 depicts.
The recovery process then embarks upon the next, L.sub.1 undo pass. If the level logs mentioned above are implemented, the backward scan for this level begins in the RAM-resident L.sub.1 level log, although it may have to finish up in the operation log 31 if the L.sub.0 pass ended without copying all necessary L.sub.1 -related records into the L.sub.1 level log. The first-encountered L.sub.1 operation record 64 in that log represents an L.sub.1 operation in an L.sub.1 transaction 50 for which the recovery process has not encountered a commit record. (Preferably, only such uncommitted-transaction operations are copied into the level logs.) This operation must therefore be undone by performing the L.sub.1 undo operation that record 64's undo field 74 identifies.
For reasons similar to those discussed in connection with L.sub.0 CLRs 80, 92, and 94, it is preferable for a subsequent crash not to cause the field-74-identified L.sub.1 undo operation to be undone itself, so the undo process at level L.sub.1 (and higher levels) in one sense follows the same rules against redoing CLR-represented operations that it does at L.sub.0.
But a complication arises from the fact that an L.sub.1 undo operation is an L.sub.0 transaction, which typically consists of a plurality of constituent L.sub.0 operations. For a variety of reasons, it would greatly complicate recovery if preventing the undoing of the field-74-identified L.sub.1 undo operation were accomplished by preventing its constituent L.sub.0 operations from being undone. For example, it would add another layer of complexity for the recovery process invoked by an abort of that L.sub.0 undo transaction to (1) respond to a record of one of that transaction's constituent operations by searching for record 64 so as to determine what transaction to resume and (2) count the already-logged update records of that transaction's constituent operations to determine where to resume it. In most cases, moreover, the crash would have lost too much prior-state information for even these efforts to reveal where to resume the transaction.
When the recovery process depicted in FIG. 5 encounters the L.sub.1 update record 64 depicted in FIG. 6 in its (backward) L.sub.1 undo pass, it begins the field-74-identified L.sub.1 compensation operation--i.e., the L.sub.0 compensation transaction--by storing start record 98 in the operation log 31 and performing that compensation transaction's operations, recording them with normal L.sub.0 update records 100 and 102. It then notes the transaction's completion with a compensation/commit log record 104.
FIG. 8 depicts log record 104. Its format is the same as that of update/commit record 64 of FIG. 6, but in the illustrated embodiment, the record-type field 106a of the L.sub.1 record part 104a identifies it as a CLR rather than a forward update record. If transaction 45 has committed, therefore, CLR record part 104a will be present and prevent the recovery operation from responding to record 64a by performing again the L.sub.1 undo operation that L.sub.0 transaction 45 has already performed.
FIG. 9 depicts a forward sequence essentially the same as that of FIG. 5 with the exception that transaction 46' in FIG. 9 is one for which the transaction designer has decided to implement flat recovery rather than multi-level recovery. For records logged before the crash, therefore, FIG. 9 uses primed versions of the reference numerals for corresponding records in FIG. 5. Database operations that occur before the crash 76' in FIG. 9 are essentially the same as those before the crash 76 of FIG. 5, with two exceptions. The first exception is that, since the recovery is not to occur at multiple levels, the fact that L.sub.1 transaction 50' is still active causes the locks acquired during its subtransaction 46' to be retained even after transaction 46' commits. (The locks' transaction IDs are, however, changed to that of transaction 50'.) That is, transaction 50' "inherits" the locks of its committed constituent operation, transaction 46'.
The other exception is that log record 64' differs from the record depicted in FIG. 6 in that it does not have a field, corresponding to field 74, that identifies a higher-level undo operation; since flat recover is to be implemented, undo recovery occurs only at the bottom level, so record 64 requires no special L.sub.1 undo information, as will now be explained.
When a crash occurs, operations are redone in the manner previously described, and the undo procedure then starts. This is a flat recovery operation: the entire undo procedure occurs in one pass and at the L.sub.0 level. An undo operation recorded by CLR 112 is the same as the operation recorded by CLR 80 of FIG. 5; it compensates for the operation recorded by update record 75'.
Having dealt with record 75', the undo pass proceeds to the next log record 64'. Here the flat recovery method for a nested transaction differs from the multi-level recovery. In the multi-level recovery, the undo procedure encountered a record of the type depicted in FIG. 6, i.e., one that identified a higher-level undo operation. The recovery procedure responded to such a record by placing it in the L.sub.1 level log and thereby holding compensation for its L.sub.1 operation in abeyance until the next, L.sub.1 undo pass. In the L.sub.0 pass, the recovery treated that record simply as a commit record, i.e., as representing a transaction that had already been committed and so did not need to be redone.
Unlike record 64, however, record 64' identifies no higher-level undo procedure by which the higher-level operation can be undone, and the recovery procedure concludes that, if the higher-level operation must be undone, the undo operation must be performed at the lower level, namely, by re-opening its constituent L.sub.0 operations. So when it reaches an update/commit record like record 64', which identifies an uncommitted higher-level transaction but no higher-level undo operation, the recovery operation does not copy it into a higher-level log. Instead, its undo pass responds to the commit-record part 64b' by adding to the operation log 31 a two-level compensation/reopen log record 114. The format of compensation/start log record 114 is similar to that of compensation/commit log record 104 depicted in FIG. 8 except that record 114 additionally includes a next-undo field represented by line 115 in FIG. 9. This field's purpose will be explained shortly.
The part of the FIG. 11 sequence before the start of the L.sub.1 recovery pass is exactly the same as that of the FIG. 5 sequence, and the reference numerals for the records in that part of the sequence are primed versions of those for corresponding records in FIG. 5. In particular, transaction 46" is like transaction 46 in that it is intended for multi-level recovery. The difference occurs when the L.sub.1 recovery pass in the FIG. 11 sequence encounters double record 64a" in the L.sub.1 level log. Rather than logging the compensation transaction's start with a regular start record like record 98 of FIG. 5, the recovery procedure in this embodiment logs it with a double compensation/start record 122. It then logs the remainder of the compensation transaction 45" with ordinary update records 124 and 126 and, instead of a double record like record 104 of FIG. 5, a single (abort-type) commit record 128.
If an abort occurs in a recovery process in which compensation transaction 45" has already committed, the subsequent recovery operation operates just as it does in the FIG. 5 embodiment when transaction 45 has committed. If transaction 45" aborts, however, the process is more complicated than recovery from a transaction-45 abort because the L.sub.1 CLR 122a of FIG. 11 has already been written when compensation transaction 45" aborts, while L.sub.1 CLR 104a of FIG. 5 has not when transaction 45 aborts.
The significance of record part 122a's being a CLR is that, if it is encountered in recovery from a subsequent crash that aborts the transaction to which its operation belongs, it does not trigger an L.sub.1 undo operation, for reasons previously discussed in connection With the L.sub.0 CLRs. As was also mentioned above, however, the constituent operations of the L.sub.0 transaction that it represents may nonetheless be undone if that transaction was itself aborted.
Specifically, if the part-122a-represented L.sub.0 compensation transaction aborts, commit record 128 will not be present in the operation log 31. The L.sub.0 undo pass of the recovery operation that occurs after the abort therefore will reach, say, update record 124 without having encountered a commit record for the transaction that record 124 identifies, so the undo procedure will perform the L.sub.0 undo operation that record 124 identifies and add a corresponding L.sub.0 CLR to the operation log 31, as it would for a normal forward L.sub.0 operation; indeed, in this scheme, log record 124's operation is a normal forward L.sub.0 operation. Thus, the L.sub.0 undo pass does initially undo the constituent operations of the L.sub.0 compensation transaction--i.e., of the L.sub.1 undo operation--that record part 122a records.
But its response to its subsequent encounter with record part 122b reinstates that compensation transaction and thus justifies the fact that record part 122a remains in the (durable) operation log and will consequently occupy the L.sub.1 level log. Specifically, unlike the record-type field contents of ordinary start record 54", to which the L.sub.0 undo process responds by simply adding a (typically abort-type) commit record 96" to the operation log 31 to indicate that the roll-back of its transaction had completed, those of start record part 122b distinguish it as the start record of a compensation transaction, which cannot remain rolled back. The transaction-redo field 130 identifies the L.sub.1 redo operation for the L.sub.1 operation that the L.sub.1 CLR part 122a represents, i.e., the L.sub.1 undo operation for the L.sub.1 operation that update record part 64a" represents. When the L.sub.0 undo pass encounters record 122, it interrupts its L.sub.0 compensation operations to perform the indicated L.sub.1 redo operation. Record part 122a thus correctly indicates that the record-64a"-represented L.sub.1 operation has been undone and should not be undone again.
The recovery procedure's treatment of the transaction identified in part 122b of double record 122 does not depend on whether the L.sub.1 transaction 50" identified in the other part 122a is active; indeed, commit record 128's absence, which is what permits the recovery procedure to react to start record 122b, does not occur when that transaction is not active. But record 122 is still a two-part record, as opposed to two single records, in the sense that one part must always be written with the other: since a subsequent undo-recovery procedure that encounters CLR 122a will refrain from responding to an encounter with record 64a" by undoing the operation that record 64a" represents, the operation log on which such a second recovery procedure operates must be guaranteed to include record 122b, whose presence insures that the record-64a"-represented transaction is undone if its undo operation had not previously committed. Conversely, if a second recovery operation encounters start-compensation-transaction record 122b and has thus guaranteed that the record-64a"-represented transaction has been undone, it must also encounter CLR 122a to prevent that transaction from being undone a second time.
Patent CitationsCited PatentFiling datePublication dateApplicantTitleUS4648031 *Jun 21, 1982Mar 3, 1987International Business Machines CorporationMethod and apparatus for restarting a computing systemUS4819159 *Aug 29, 1986Apr 4, 1989Tolerant Systems, Inc.Distributed multiprocess transaction processing system and methodUS4868744 *Mar 3, 1986Sep 19, 1989International Business Machines CorporationMethod for restarting a long-running, fault-tolerant operation in a transaction-oriented data base system without burdening the system logUS4945474 *Apr 8, 1988Jul 31, 1990Internatinal Business Machines CorporationMethod for restoring a database after I/O error employing write-ahead logging protocolsUS5043866 *Apr 8, 1988Aug 27, 1991International Business Machines CorporationSoft checkpointing system using log sequence numbers derived from stored data pages and log records for database recoveryUS5095421 *Aug 17, 1989Mar 10, 1992International Business Machines CorporationTransaction processing facility within an operating system environmentUS5155678 *Oct 29, 1985Oct 13, 1992International Business Machines CorporationData availability in restartable data base systemEP0425415A2 *Sep 21, 1990May 2, 1991International Business Machines CorporationProcess and apparatus for preserving data integrity of a database* Cited by examinerNon-Patent CitationsReference1Pu, Calton and Noe, Jerre D., "Design and Implementation of Nested Transactions in Eden", IEEE, 1987.2 *Pu, Calton and Noe, Jerre D., Design and Implementation of Nested Transactions in Eden , IEEE, 1987.3Rothermel, K. and Mohan, C., "ARIES/NT: A Recovery Method Based on Write-Ahead Logging for Nested Transactions", Proceedings of the Fifteenth International Conference on Very Large Data Bases, Amsterdam, 1989.4 *Rothermel, K. and Mohan, C., ARIES/NT: A Recovery Method Based on Write Ahead Logging for Nested Transactions , Proceedings of the Fifteenth International Conference on Very Large Data Bases, Amsterdam, 1989.5Shin, Dong C. and Moon, Song C., "An Efficient Log-Based Crash Recovery Scheme for Nested Transactions", Microprocessing and Microprogramming, vol. 31, Nos. 1-5, Apr. 1991, pp. 99-104.6 *Shin, Dong C. and Moon, Song C., An Efficient Log Based Crash Recovery Scheme for Nested Transactions , Microprocessing and Microprogramming, vol. 31, Nos. 1 5, Apr. 1991, pp. 99 104.7 *Tripathi, Anand R. and Wang, Pong Sheng, An Object Oriented Design Model for Reliable Distributed Systems , Proc. 3rd Symposium on Reliability in Distributed Software and Database Systems (Clearwater Beach, Oct. 17 19, 1983).8Tripathi, Anand R. and Wang, Pong-Sheng, "An Object-Oriented Design Model for Reliable Distributed Systems", Proc. 3rd Symposium on Reliability in Distributed Software and Database Systems (Clearwater Beach, Oct. 17-19, 1983).9Weikum, Gerhard; Hasse, Christof; Broessier, Peter; Muth, Peter, "Multi-Level Recovery", Proc. 9th Symposium on Principles of Database Systems (1990).10 *Weikum, Gerhard; Hasse, Christof; Broessier, Peter; Muth, Peter, Multi Level Recovery , Proc. 9th Symposium on Principles of Database Systems (1990).* Cited by examinerReferenced byCiting PatentFiling datePublication dateApplicantTitleUS5469562 *Jun 26, 1992Nov 21, 1995Digital Equipment CorporationDurable atomic storage update managerUS5481699 *Mar 23, 1995Jan 2, 1996Digital Equipment CorporationDurable atomic storage update managerUS5485607 *Feb 5, 1993Jan 16, 1996Digital Equipment CorporationConcurrency-control method and apparatus in a database management system utilizing key-valued lockingUS5561798 *Jun 7, 1995Oct 1, 1996International Business Machines CorporationComputer program product and program storage device for improving data recovery performanceUS5581750 *Mar 15, 1993Dec 3, 1996International Business Machines CorporationSystem and method for improving data recovery performanceUS5659747 *Apr 22, 1993Aug 19, 1997Microsoft CorporationMultiple level undo/redo mechanismUS5680621 *Jun 7, 1995Oct 21, 1997International Business Machines CorporationSystem and method for domained incremental changes storage and retrievalUS5768582 *Jun 7, 1995Jun 16, 1998International Business Machines CorporationComputer program product for domained incremental changes storage and retrievalUS5794242 *Apr 8, 1997Aug 11, 1998Digital Equipment CorporationTemporally and spatially organized databaseUS5802536 *Oct 14, 1997Sep 1, 1998Sony CorporationInformation search and display apparatusUS5832203 *Jan 23, 1995Nov 3, 1998Tandem Computers IncorporatedMethod for providing recovery from a failure in a system utilizing distributed auditUS5832516 *Jan 21, 1997Nov 3, 1998Oracle CorporationCaching data in recoverable objectsUS5850535 *Oct 12, 1995Dec 15, 1998Computervision CorporationRoll-back during regeneration on a computer-aided design systemUS5870763 *Mar 10, 1997Feb 9, 1999Microsoft CorporationDatabase computer system with application recovery and dependency handling read cacheUS5878206 *Mar 25, 1997Mar 2, 1999Hewlett-Packard CompanyCommit scope control in hierarchical information processesUS5893128 *Mar 1, 1994Apr 6, 1999Nauckhoff; SvenDistributed work flow managementUS5900000 *Mar 5, 1998May 4, 1999International Business Machines CorporationSystem, method, and computer program product for providing and incremental retrieval adaptorUS5903898 *Jun 4, 1996May 11, 1999Oracle CorporationMethod and apparatus for user selectable loggingUS5933838 *Apr 4, 1997Aug 3, 1999Microsoft CorporationDatabase computer system with application recovery and recovery log sequence numbers to optimize recoveryUS5937388 *Mar 21, 1997Aug 10, 1999Hewlett-Packard CompanySystem and method for performing scalable distribution of process flow activities in a distributed workflow management systemUS5966713 *Dec 15, 1997Oct 12, 1999Telefonaktiebolaget Lm EricssonMethod for determining the contents of a restoration logUS6014673 *May 13, 1997Jan 11, 2000Hewlett-Packard CompanySimultaneous use of database and durable store in work flow and process flow systemsUS6018746 *Dec 23, 1997Jan 25, 2000Unisys CorporationSystem and method for managing recovery information in a transaction processing systemUS6070008 *Mar 5, 1998May 30, 2000International Business Machines CorporationSystem, method, and computer program product for providing an incremental storage adaptorUS6094660 *Nov 21, 1997Jul 25, 2000Telefonaktiebolaget Lm EricssonCustomer administrative system management of redundant database network elements in a telecommunications systemUS6151607 *Apr 28, 1999Nov 21, 2000Microsoft CorporationDatabase computer system with application recovery and dependency handling write cacheUS6182086 *Mar 2, 1998Jan 30, 2001Microsoft CorporationClient-server computer system with application recovery of server applications and client applicationsUS6216126 *May 27, 1998Apr 10, 2001Telefonaktiebolaget Lm EricssonMethod for transaction within a distributed databaseUS6321234 *Nov 8, 1996Nov 20, 2001Sybase, Inc.Database server system with improved methods for logging transactionsUS6421677 *Jul 19, 1999Jul 16, 2002International Business Machines CorporationExtension of data definition language (DDL) capabilities for relational databases for applications issuing DDL statementsUS6453322 *Jul 19, 1999Sep 17, 2002International Business Machines CorporationExtension of data definition language (DDL) capabilities for relational databases for applications issuing multiple units of workUS6490594May 8, 2000Dec 3, 2002Microsoft CorporationDatabase computer system with application recovery and dependency handling write cacheUS6578159 *Nov 18, 1999Jun 10, 2003Hitachi, Ltd.Transaction processing method and apparatusUS6587962 *Oct 20, 1999Jul 1, 2003Hewlett-Packard Development Company, L.P.Write request protection upon failure in a multi-computer systemUS6630946 *Nov 10, 1999Oct 7, 2003Symantec CorporationMethods for automatically locating data-containing windows in frozen applications program and saving contentsUS6631480Nov 10, 1999Oct 7, 2003Symantec CorporationMethods and systems for protecting data from potential corruption by a crashed computer programUS6662310Nov 10, 1999Dec 9, 2003Symantec CorporationMethods for automatically locating url-containing or other data-containing windows in frozen browser or other application program, saving contents, and relaunching application program with link to saved dataUS6671686Nov 2, 2001Dec 30, 2003Guy PardonDecentralized, distributed internet data managementUS6738832Jun 29, 2001May 18, 2004International Business Machines CorporationMethods and apparatus in a logging system for the adaptive logger replacement in order to receive pre-boot informationUS6904411 *Feb 26, 2002Jun 7, 2005N�gine, LLCMulti-processing financial transaction processing systemUS6925523 *Mar 3, 2003Aug 2, 2005Agilent Technologies, Inc.Managing monotonically increasing counter values to minimize impact on non-volatile storageUS6978279Mar 15, 1999Dec 20, 2005Microsoft CorporationDatabase computer system using logical logging to extend recoveryUS6983395 *May 23, 2001Jan 3, 2006Hewlett-Packard Development Company, L.P.Multi-agent cooperative transaction method and systemUS6990466 *Aug 8, 2000Jan 24, 2006International Business Machines CorporationMethod and system for integrating core banking business processesUS7107294 *Jan 7, 2004Sep 12, 2006International Business Machines CorporationMethod and apparatus for interrupting updates to a database to provide read-only accessUS7117479Oct 1, 2001Oct 3, 2006Sun Microsystems, Inc.Language-sensitive whitespace adjustment in a software engineering toolUS7130971Mar 30, 2004Oct 31, 2006Hitachi, Ltd.Assuring genuineness of data stored on a storage deviceUS7146364 *Nov 3, 2000Dec 5, 2006International Business Machines CorporationMethod and system for recovering data in a plurality of systemsUS7162593Jan 5, 2006Jan 9, 2007Hitachi, Ltd.Assuring genuineness of data stored on a storage deviceUS7237147 *Aug 27, 2003Jun 26, 2007Oracle International CorporationMethod and apparatus for making available data that was locked by a dead transaction before rolling back the entire dead transactionUS7239581Aug 24, 2004Jul 3, 2007Symantec Operating CorporationSystems and methods for synchronizing the internal clocks of a plurality of processor modulesUS7272666Feb 13, 2004Sep 18, 2007Symantec Operating CorporationStorage management deviceUS7287133Aug 24, 2004Oct 23, 2007Symantec Operating CorporationSystems and methods for providing a modification history for a location within a data storeUS7296008Aug 24, 2004Nov 13, 2007Symantec Operating CorporationGeneration and use of a time map for accessing a prior image of a storage deviceUS7386834 *Jun 28, 2002Jun 10, 2008Sun Microsystems, Inc.Undo/redo technique for token-oriented representation of program codeUS7409587Aug 24, 2004Aug 5, 2008Symantec Operating CorporationRecovering from storage transaction failures using checkpointsUS7509351Oct 7, 2005Mar 24, 2009Microsoft CorporationLogical logging to extend recoveryUS7536583Oct 13, 2006May 19, 2009Symantec Operating CorporationTechnique for timeline compression in a data storeUS7539746 *Dec 19, 2001May 26, 2009Emc CorporationHighly available transaction failure detection and recovery for electronic commerce transactionsUS7555618Dec 5, 2006Jun 30, 2009Hitachi, Ltd.Assuring genuineness of data stored on a storage deviceUS7577806Sep 23, 2003Aug 18, 2009Symantec Operating CorporationSystems and methods for time dependent data storage and recoveryUS7577807Aug 24, 2004Aug 18, 2009Symantec Operating CorporationMethods and devices for restoring a portion of a data storeUS7584337Feb 13, 2004Sep 1, 2009Symantec Operating CorporationMethod and system for obtaining data stored in a data storeUS7631120Aug 24, 2004Dec 8, 2009Symantec Operating CorporationMethods and apparatus for optimally selecting a storage buffer for the storage of dataUS7725667Mar 12, 2004May 25, 2010Symantec Operating CorporationMethod for identifying the time at which data was written to a data storeUS7725760Aug 24, 2004May 25, 2010Symantec Operating CorporationData storage systemUS7730222Aug 24, 2004Jun 1, 2010Symantec Operating SystemProcessing storage-related I/O requests using binary tree data structuresUS7730286 *Dec 30, 2005Jun 1, 2010Intel CorporationSoftware assisted nested hardware transactionsUS7739385 *Jun 16, 2003Jun 15, 2010Cisco Technology, Inc.Explicit locking of resources in devices accessible on a networkUS7827362Aug 24, 2004Nov 2, 2010Symantec CorporationSystems, apparatus, and methods for processing I/O requestsUS7904428Aug 24, 2004Mar 8, 2011Symantec CorporationMethods and apparatus for recording write requests directed to a data storeUS7904434 *Apr 14, 2008Mar 8, 2011Oracle International CorporationFramework for handling business transactionsUS7917708May 22, 2009Mar 29, 2011Hitachi, Ltd.Assuring genuineness of data stored on a storage deviceUS7953698Aug 3, 2006May 31, 2011Sybase, Inc.Replication system with methodology for replicating stored procedure callsUS7966298 *Apr 30, 2008Jun 21, 2011Unisys CorporationRecord-level locking and page-level recovery in a database management systemUS7991748Feb 17, 2004Aug 2, 2011Symantec CorporationVirtual data store creation and useUS8005805Dec 29, 2003Aug 23, 2011Guy PardonDecentralized, distributed internet data managementUS8074027Dec 4, 2006Dec 6, 2011Microsoft CorporationMulti-level read caching for multiplexed transactional loggingUS8078582Apr 6, 2009Dec 13, 2011Microsoft CorporationData change ordering in multi-log based replicationUS8255367 *May 31, 2010Aug 28, 2012Fujitsu LimitedFile management apparatus, method, and programUS8271436 *Oct 2, 2006Sep 18, 2012Mimosa Systems, Inc.Retro-fitting synthetic full copies of dataUS8463761Aug 23, 2011Jun 11, 2013Guy PardonDecentralized, distributed internet data managementUS8521973Sep 28, 2007Aug 27, 2013Symantec Operating CorporationSystems and methods for providing a modification history for a location within a data storeUS8554733 *Jun 15, 2005Oct 8, 2013Hitachi Ltd.Disaster recovery method, disaster recovery system, remote copy method and storage systemUS20100312753 *May 31, 2010Dec 9, 2010Fujitsu LimitedFile management apparatus, method, and programUSRE38270 *Aug 18, 1999Oct 7, 2003Microsoft CorporationMultiple level undo/redo mechanismEP0806015A1 *Jan 22, 1996Nov 12, 1997Tandem Computers IncorporatedSystem for maintenance of database integrity* Cited by examinerClassifications U.S. Classification707/648, 714/19, 714/E11.13, 707/999.202, 707/674International ClassificationG06F11/14Cooperative ClassificationY10S707/99953, H05K999/99, G06F11/1471, G06F2201/87European ClassificationG06F11/14A12Legal EventsDateCodeEventDescriptionAug 15, 2005FPAYFee paymentYear of fee payment: 12Nov 3, 2003ASAssignmentOwner name: HEWLETT-PACKARD DEVELOPMENT COMPANY, L.P., TEXASFree format text: CHANGE OF NAME;ASSIGNOR:COMPAQ INFORMANTION TECHNOLOGIES GROUP LP;REEL/FRAME:014102/0224Effective date: 20021001Owner name: HEWLETT-PACKARD DEVELOPMENT COMPANY, L.P. 20555 SHFree format text: CHANGE OF NAME;ASSIGNOR:COMPAQ INFORMANTION TECHNOLOGIES GROUP LP /AR;REEL/FRAME:014102/0224Jan 9, 2002ASAssignmentOwner name: COMPAQ INFORMATION TECHNOLOGIES GROUP, L.P., TEXASFree format text: ASSIGNMENT OF ASSIGNORS INTEREST;ASSIGNORS:DIGITAL EQUIPMENT CORPORATION;COMPAQ COMPUTER CORPORATION;REEL/FRAME:012447/0903;SIGNING DATES FROM 19991209 TO 20010620Owner name: COMPAQ INFORMATION TECHNOLOGIES GROUP, L.P. 20555Jul 26, 2001FPAYFee paymentYear of fee payment: 8Aug 14, 1997FPAYFee paymentYear of fee payment: 4RotateOriginal ImageGoogle Home - Sitemap - USPTO Bulk Downloads - Privacy Policy - Terms of Service - About Google Patents - Send FeedbackData provided by IFI CLAIMS Patent Services©2012 Google