Patent ID: 7065537

Claim:
A method of logging and recovery in a transaction-processing system having a main memory for storing a database, wherein the database comprises a plurality of objects, any of which is denoted by b hereafter, one or more persistent backup storage devices for storing a copy of the database in the main memory, and one or more persistent log storage devices for storing log records, the logging method comprising: generating a differential log record using Δ t =b t−1 ⊕ b t where Δ t is the differential log record generated for the t-th update on a database object b, ⊕ is the bit-wise exclusive-OR (XOR) operation, b t−1 is the image of the database before the t-th update occurs, and b t is the image of the database after the t-th update occurs; and the recovery method comprising: redoing updates of committed transactions using b s+p =b s ⊕ Δ (1) ⊕ Δ (2) . . . ⊕ Δ (p) , where b s is the image of a database object b after s number of updates are reflected, b s+p is the image of b rolled forward from b s by p number of updates involved in committed transactions, ⊕ is the bit-wise XOR operation, and where the sequence of the differential log records applied, Δ (1) through Δ (p) , is any possible arrangement of the set of sequentially-generated differential log records {Δ s−1 , . . . , Δ s+p+1 , Δ s+p }in the order independent from the order of log creation, and undoing updates of uncommitted transactions using b s−q =b s ⊕ Δ (1) ⊕ Δ (2) . . . ⊕ Δ (q) , where b s is the image of a database object b after s number of updates are reflected, b s−q is the image of b rolled backward from b s by q number of updates involved in uncommitted transactions, ⊕ is the bit-wise XOR operation, and where the sequence of the differential log records applied, Δ (1) through Δ (q), is any possible arrangement of the set of sequentially-generated differential log records {Δ s−q+1 , Δ s−q+2 , . . . , Δ s } in the order independent from the order of log creation.