a. Example for using normal transaction undo mechanism : Consider a bank account S with balance $200. Let two transactions individually deposit $20 in the account. Thus, the final balance should be $240. Now, when the transactions are executed in sequence T 1 , T 2 the log records would be as follows: < T 1 , S, 200, 220 > < T 2 , S, 220, 240 > Now, transaction T 1 needs to be undone...

Question

Want to see the full answer?

Answer 1

Expert Solution & Answer

Chapter 19, Problem 11PE

Explanation of Solution

a.

Example for using normal transaction undo mechanism:

Consider a bank account S with balance $200.

Let two transactions individually deposit $20 in the account. Thus, the final balance should be $240.

Now, when the transactions are executed in sequence T₁, T₂ the log records would be as follows:
< T₁, S, 200, 220 >

< T₂, S, 220, 240 >

Now, transaction T₁ needs to be undone...

Explanation of Solution

b.

Implementing point-in-time recovery using database dumps:

To modify the recovery algorithm from section 19.4 to implement point in time recovery using database dumps;

Identify the latest archival dump (say D) before the start of the erroneous transaction (say Te) that is < Te, start>.

Restore the database using this dump D.

Now, perform a redo of all log records starting from the dump till the transaction committed that is < Te, commit >.

Let S be the set of those transactions which were active at the commit time of Te.

Rollback all transactions in the set S including Te...

Explanation of Solution

c.

Re-executing non-erroneous transactions logically:

To understand the reason the later non-erroneous transactions cannot be re-executed logically using log records, consider again the example from part (a);

Let both the transactions be undone and the balance be reverted back to $200.

Now, if T₂ needs to be redone while using the log record < T₂, ...

Expert Solution & Answer

Want to see the full answer?

Check out a sample textbook solution

See solution

Students have asked these similar questions

Design a dynamic programming algorithm for the Longest Alternating Subsequence problem described below: Input: A sequence of n integers Output: The length of the longest subsequence where the numbers alternate between being larger and smaller than their predecessor The algorithm must take O(n²) time. You must also write and explain the recurrence. Example 1: Input: [3, 5, 4, 1, 3, 6, 5, 7, 3, 4] Output: 8 ([3, 5, 4, 6, 5, 7, 3, 4]) Example 2: Input: [4,7,2,5,8, 3, 8, 0, 4, 7, 8] Output: 8 ([4, 7, 2, 5, 3, 8, 0,4]) (Take your time with this for the subproblem for this one)

Design a dynamic programming algorithm for the Coin-change problem described below: Input: An amount of money C and a set of n possible coin values with an unlimited supply of each kind of coin. Output: The smallest number of coins that add up to C exactly, or output that no such set exists. The algorithm must take O(n C) time. You must also write and explain the recurrence. Example 1: Input: C24, Coin values = = [1, 5, 10, 25, 50] Output: 6 (since 24 = 10+ 10+1+1 +1 + 1) Example 2: Input: C = 86, Coin values = [1, 5, 6, 23, 35, 46, 50] Output: 2 (since 86 = 46+35+5)

Design a dynamic programming algorithm for the Longest Common Subsequence problem de- scribed below Input: Two strings x = x1x2 xm and y = Y1Y2... Yn Output: The length of the longest subsequence that is common to both x and y. . The algorithm must take O(m n) time. You must also write and explain the recurrence. (I want the largest k such that there are 1 ≤ i₁ < ... < ik ≤ m and 1 ≤ j₁ < ... < jk ≤ n such that Xi₁ Xi2 Xik = Yj1Yj2 ··· Yjk) Example 1: Input: x = 'abcdefghijklmnopqrst' and y = 'ygrhnodsh ftw' Output: 6 ('ghnost' is the longest common subsequence to both strings) Example 2: Input: x = 'ahshku' and y = ‘asu' Output: 3 ('asu' is the longest common subsequence to both strings)

Answer 2

Expert Solution & Answer

Chapter 19, Problem 11PE

Explanation of Solution

a.

Example for using normal transaction undo mechanism:

Consider a bank account S with balance $200.

Let two transactions individually deposit $20 in the account. Thus, the final balance should be $240.

Now, when the transactions are executed in sequence T₁, T₂ the log records would be as follows:
< T₁, S, 200, 220 >

< T₂, S, 220, 240 >

Now, transaction T₁ needs to be undone...

Explanation of Solution

b.

Implementing point-in-time recovery using database dumps:

To modify the recovery algorithm from section 19.4 to implement point in time recovery using database dumps;

Identify the latest archival dump (say D) before the start of the erroneous transaction (say Te) that is < Te, start>.

Restore the database using this dump D.

Now, perform a redo of all log records starting from the dump till the transaction committed that is < Te, commit >.

Let S be the set of those transactions which were active at the commit time of Te.

Rollback all transactions in the set S including Te...

Explanation of Solution

c.

Re-executing non-erroneous transactions logically:

To understand the reason the later non-erroneous transactions cannot be re-executed logically using log records, consider again the example from part (a);

Let both the transactions be undone and the balance be reverted back to $200.

Now, if T₂ needs to be redone while using the log record < T₂, ...

Expert Solution & Answer

Want to see the full answer?

Check out a sample textbook solution

See solution

Answer 3

Expert Solution & Answer

Chapter 19, Problem 11PE

Explanation of Solution

a.

Example for using normal transaction undo mechanism:

Consider a bank account S with balance $200.

Let two transactions individually deposit $20 in the account. Thus, the final balance should be $240.

Now, when the transactions are executed in sequence T₁, T₂ the log records would be as follows:
< T₁, S, 200, 220 >

< T₂, S, 220, 240 >

Now, transaction T₁ needs to be undone...

Explanation of Solution

b.

Implementing point-in-time recovery using database dumps:

To modify the recovery algorithm from section 19.4 to implement point in time recovery using database dumps;

Identify the latest archival dump (say D) before the start of the erroneous transaction (say Te) that is < Te, start>.

Restore the database using this dump D.

Now, perform a redo of all log records starting from the dump till the transaction committed that is < Te, commit >.

Let S be the set of those transactions which were active at the commit time of Te.

Rollback all transactions in the set S including Te...

Explanation of Solution

c.

Re-executing non-erroneous transactions logically:

To understand the reason the later non-erroneous transactions cannot be re-executed logically using log records, consider again the example from part (a);

Let both the transactions be undone and the balance be reverted back to $200.

Now, if T₂ needs to be redone while using the log record < T₂, ...

Expert Solution & Answer

Want to see the full answer?

Check out a sample textbook solution

See solution

Answer 4

Expert Solution & Answer

Chapter 19, Problem 11PE

Explanation of Solution

a.

Example for using normal transaction undo mechanism:

Consider a bank account S with balance $200.

Let two transactions individually deposit $20 in the account. Thus, the final balance should be $240.

Now, when the transactions are executed in sequence T₁, T₂ the log records would be as follows:
< T₁, S, 200, 220 >

< T₂, S, 220, 240 >

Now, transaction T₁ needs to be undone...

Explanation of Solution

b.

Implementing point-in-time recovery using database dumps:

To modify the recovery algorithm from section 19.4 to implement point in time recovery using database dumps;

Identify the latest archival dump (say D) before the start of the erroneous transaction (say Te) that is < Te, start>.

Restore the database using this dump D.

Now, perform a redo of all log records starting from the dump till the transaction committed that is < Te, commit >.

Let S be the set of those transactions which were active at the commit time of Te.

Rollback all transactions in the set S including Te...

Explanation of Solution

c.

Re-executing non-erroneous transactions logically:

To understand the reason the later non-erroneous transactions cannot be re-executed logically using log records, consider again the example from part (a);

Let both the transactions be undone and the balance be reverted back to $200.

Now, if T₂ needs to be redone while using the log record < T₂, ...

Expert Solution & Answer

Want to see the full answer?

Check out a sample textbook solution

See solution

Answer 5

Expert Solution & Answer

Answer 6

Expert Solution & Answer

Answer 7

Chapter 19, Problem 11PE

Explanation of Solution

a.

Example for using normal transaction undo mechanism:

Consider a bank account S with balance $200.

Let two transactions individually deposit $20 in the account. Thus, the final balance should be $240.

Now, when the transactions are executed in sequence T₁, T₂ the log records would be as follows:
< T₁, S, 200, 220 >

< T₂, S, 220, 240 >

Now, transaction T₁ needs to be undone...

Explanation of Solution

b.

Implementing point-in-time recovery using database dumps:

To modify the recovery algorithm from section 19.4 to implement point in time recovery using database dumps;

Identify the latest archival dump (say D) before the start of the erroneous transaction (say Te) that is < Te, start>.

Restore the database using this dump D.

Now, perform a redo of all log records starting from the dump till the transaction committed that is < Te, commit >.

Let S be the set of those transactions which were active at the commit time of Te.

Rollback all transactions in the set S including Te...

Explanation of Solution

c.

Re-executing non-erroneous transactions logically:

To understand the reason the later non-erroneous transactions cannot be re-executed logically using log records, consider again the example from part (a);

Let both the transactions be undone and the balance be reverted back to $200.

Now, if T₂ needs to be redone while using the log record < T₂, ...

Answer 8

Chapter 19, Problem 11PE

Explanation of Solution

a.

Example for using normal transaction undo mechanism:

Consider a bank account S with balance $200.

Let two transactions individually deposit $20 in the account. Thus, the final balance should be $240.

Now, when the transactions are executed in sequence T₁, T₂ the log records would be as follows:
< T₁, S, 200, 220 >

< T₂, S, 220, 240 >

Now, transaction T₁ needs to be undone...

Answer 9

Chapter 19, Problem 11PE

Explanation of Solution

a.

Example for using normal transaction undo mechanism:

Consider a bank account S with balance $200.

Let two transactions individually deposit $20 in the account. Thus, the final balance should be $240.

Now, when the transactions are executed in sequence T₁, T₂ the log records would be as follows:
< T₁, S, 200, 220 >

< T₂, S, 220, 240 >

Now, transaction T₁ needs to be undone...

Answer 10

Explanation of Solution

b.

Implementing point-in-time recovery using database dumps:

To modify the recovery algorithm from section 19.4 to implement point in time recovery using database dumps;

Identify the latest archival dump (say D) before the start of the erroneous transaction (say Te) that is < Te, start>.

Restore the database using this dump D.

Now, perform a redo of all log records starting from the dump till the transaction committed that is < Te, commit >.

Let S be the set of those transactions which were active at the commit time of Te.

Rollback all transactions in the set S including Te...

Answer 11

Explanation of Solution

b.

Implementing point-in-time recovery using database dumps:

To modify the recovery algorithm from section 19.4 to implement point in time recovery using database dumps;

Identify the latest archival dump (say D) before the start of the erroneous transaction (say Te) that is < Te, start>.

Restore the database using this dump D.

Now, perform a redo of all log records starting from the dump till the transaction committed that is < Te, commit >.

Let S be the set of those transactions which were active at the commit time of Te.

Rollback all transactions in the set S including Te...

Answer 12

Explanation of Solution

c.

Re-executing non-erroneous transactions logically:

To understand the reason the later non-erroneous transactions cannot be re-executed logically using log records, consider again the example from part (a);

Let both the transactions be undone and the balance be reverted back to $200.

Now, if T₂ needs to be redone while using the log record < T₂, ...

Answer 13

Explanation of Solution

c.

Re-executing non-erroneous transactions logically:

To understand the reason the later non-erroneous transactions cannot be re-executed logically using log records, consider again the example from part (a);

Let both the transactions be undone and the balance be reverted back to $200.

Now, if T₂ needs to be redone while using the log record < T₂, ...

Answer 14

Expert Solution & Answer

Answer 15

Expert Solution & Answer

Answer 16

Want to see the full answer?

Check out a sample textbook solution

See solution

Answer 17

Ch. 19 - Prob. 1PE Ch. 19 - Prob. 2PE Ch. 19 - Prob. 3PE Ch. 19 - Prob. 4PE Ch. 19 - Prob. 5PE Ch. 19 - Prob. 6PE Ch. 19 - Prob. 7PE Ch. 19 - Prob. 8PE Ch. 19 - Prob. 9PE Ch. 19 - Prob. 10PE

Explanation of Solution

Explanation of Solution

Explanation of Solution

Want to see the full answer?

Chapter 19 Solutions