CSCI 4140辅导、讲解Database Systems、辅导Java/Python程序设计、辅导c++语言
- 首页 >> Algorithm 算法 CSCI 4140 Advanced Database Systems
Assignment 4 – Transaction Management
Write name and student ID below, then your write your answers directly into this document and submit the pdf version of the file while making sure that the name of your file is in the format “A4-B00XXXXXX-YourLastName-4140.pdf”, where “B00XXXXXX” is your student ID and “YourLastName” is your last name.
Write your answers directly in this doc.
First Name:
Last Name:
Student ID:
1.Consider the following histories/schedules:
H1 ={ R2(z); W1(x); W1(y); R3(x); R2(x); R1(z); R2(y); W3(x) }
H2 ={ W1(x); R3(x); W3(x); R2(x); W1(y); R2(y); R2(z); R1(z) }
H3 ={ W1(x); W1(y); R1(z); R3(x); W3(x); R2(x); R2(z); R2(y) }
H4 ={ R2(z); R2(y); W1(x); W1(y); R3(x) ; R1(z); R2(x); W3(x) }
Use the tables below for your answers for questions which ask if schedules are equivalent. Use answer “YES” and “NO” as indicated in the column dealing with “if two schedules are equivalent or not”. If you state that the schedules are not equivalent, then state the reason why (usually by providing evidence that two schedules do not satisfy one of the conditions for two schedules being equivalent). The first row is already filled with answers as an example.
(i) Which of the above histories are conflict equivalent? If they are not conflict equivalent, why not?
Pair of Histories Conflict Equivalent
(YES/NO and if NO then reason)
H1, H2 NO: (conflicting pair order (R2(x), W3(x)) in H1, (W3(x), R2(x)) in H2)
H1, H3
H1, H4
H2, H3
H2, H4
H3, H4
(ii) Which of the above histories are view equivalent? If they are not view equivalent, why not?
Pair of Histories View Equivalent
(YES/NO and if NO then reason
H1, H2 NO: (R2(x) sees write W1(x) in H1 & sees write W3(x) in H2)
H1, H3
H1, H4
H2, H3
H2, H4
H3, H4
(iii) Which of the above histories are conflict-serializable? For each conflict-serializable schedule also state to which serial schedules it is equivalent (i.e., list all serial schedules to which it is equivalent).
(iv) Which of the above histories are view-serializable? For each view-serializable schedule also state to which serial schedules it is equivalent (i.e., list all serial schedules to which it is equivalent).
2.Consider the Basic Time-stamp Ordering algorithm and also the following transactions that are attempting to access a DB item. For each case state the outcome (proceed with the operation or abort the transaction) and also show any changes to the DB item's time-stamps.
For each case below (i.e., for each and every row in the table below) assume that X has a read time-stamps of 60 and a write time-stamp of 50 – i.e., assume that the cases are independent of each other.
TS … Time Stamp
Transaction TS Operation on X (Read/Write) Result
(Abort / Proceed) New Read TS for X (if any) New Write TS for X (if any)
3.Consider the last paragraph on the page 379 of Dr. Ozsu’s book, which deals with the Basic Timestamp Ordering (TO) algorithm:
“Remember that in the case of strict 2PL algorithms, the releasing of locks is delayed further, until the commit or abort of a transaction. It is possible to develop a strict TO algorithm by using a similar scheme. For example, if Wi(x) is accepted and released to the data processor, the scheduler delays all Rj(x) and Wj(x) operations (for all Tj) until Ti terminates (commits or aborts).” Such an algorithm was presented in the class and is in the course presentation materials (see the file with a name “6-Transactions Equivalence Serializability – Ozsu.pdf” in the module Slides on Brightspace).
a.Consider a strict TO algorithm, also referred to as “Basic Timestamp Method with Prewrites,” as described above, presented in class, and reviewed again in the following text. Assume that a DB item X has a read time-stamp of 32 and a write time-stamp of 41. Consider also the following transactions that are attempting to access the DB item X. Notation used: a transaction, its timestamp, and its operation are denoted by an ordered pair, in which the first item is the transaction’s timestamp, while the second item is the transaction’s operation. For instance, (60, R) denotes a read by a transaction with a timestamp of 60. Furthermore, a write, by a transaction on a DB item x, is performed in two steps. During the transaction’s execution phase, its write to x is called a pre-write and any subsequent reads and writes on the DB item by other transactions are delayed (queued in the reverse order of their time-stamps) unless, of course, they are aborted. When the transaction is terminated successfully (i.e., committed), only then any writes by the transaction are performed (one could express it as the transaction’s pre-writes are transformed to writes). Upon a transaction’s commit, for each of the transaction’s pre-write, its write is issued. Consider the commitment of the transaction that has a pre-write queued on the data item x: a write is issued for the transaction on x and the pre-write that is queued in x’s queue is converted to a write. If that write is at the head of the x’s queue, it is executed and removed from the queue. If the item at the head of the queue is a read or a write, it is also executed and removed from the queues, and so on.
Notation for operations:
R … Read, P … Pre-write, and W … Write (signaling conversion of pre-writes to writes).
For each operation in the table below, show (in the table):
- whether the transaction is
- Aborted (by entering A),
- Delayed/Queued (enter Q), or
- Executed/Done (enter E)
- show a new value of the data item’s timestamp(s), if any, and
- show the content of the queue of delayed operations (reads, prewrites, writes for the DB item X).
Note that the effects on the DB item are cumulative. That is, the results of one operation affect the results of subsequent operations.
TS … Time Stamp Op … Operation
Trans-action’s
(TS, Op) Aborted/
Queued/
Performed
(A/Q/E) New
Read TS
for X
(if any) New
Write TS for X
(if any) Queue Content
Queue Front ……………………..…..Queue Back
Initial 30 40 Initially Empty
Now assume that the transaction with a timestamp of 60 has successfully finished its work and it that it has issued a commit request. As part of its commit process, a write operation on X is issued, i.e., (60, W) is issued on X. Briefly describe what happens next.
4.This question deals with the 2-Phase Commit (2-PC) protocol. Note that it does NOT deal with network partitioning.
a)Consider a failure of a site containing a participant. Upon the site-failure recovery, how does the recovery procedure determine the state of the participant just prior to the failure?
b)Consider a site failure containing a participant. How does the coordinator find out that a participant has failed?
c)Consider a participant (of a 2PC-protocol), a participant that has failed (site failure). After the failure is fixed, the recovery procedure determines the state of the transaction just prior to the failure. For each state of the transaction just prior to the failure, indicate in the table below whether the recovery procedure can locally terminate the transaction immediately (i.e., without consulting the coordinator) or whether it has to consult the coordinator before terminating the transaction. Enter only T or F (T for True and F for False) as answers.
Participant’s State
Initial Ready
Can abort the transaction immediately
Can commit the transaction immediately
Must consult the coordinator before terminating the transaction
d)Consider a situation in which a participant (of the 2PC-protocol) has failed. The coordinator has timed-out and faces the decision whether it can terminate the transaction and if so whether to abort it or commit it. This decision, of course, depends on its (coordinator’s) state. In the table below, indicate for each of the coordinator’s states whether the transaction can be aborted, committed, or whether the coordinator must wait for the participant’s repair (i.e., that the transaction is blocked until repair). Enter T or F (T for True and F for False) in each of the table entries under the Coordinator’s State.
Coordinator’s State
Initial Wait
Can abort the transaction immediately
Can commit the transaction immediately
Must wait for the participant’s repair
e)Consider the situation in which a site containing a coordinator and a participant has failed. The operational participants have timed-out waiting for instructions/messages from the coordinator, messages that are not arriving because the site, where the coordinator (and a participant as well) is located, is still not operational. Consider the following termination protocol. A new coordinator is elected such that it is located at a site of one of the operational participants - call this participant (at the site where the new coordinator is located) the local participant. The newly elected coordinator consults the state of the local participant. Depending on the state of the local participant, state in the table below whether the newly elected coordinator can safely terminate the transaction without considering the states of the other (non-local) operational participants. Safe termination means that if the newly elected coordinator leads the operational participants to transaction’s termination (commit or abort) – the termination will NOT be inconsistent with the transaction’s termination that could have been reached at the failed site by the coordinator and the participant just before the failure at the site.
Local Participant’s State
Initial Ready
Can abort the transaction immediately without considering the states of all of the operational participants (enter only T or F (T for True and F for False) as answers)
Can commit the transaction without considering the states of all of the operational participants (enter only T or F (T for True and F for False) as answers)
Is there a state in which the newly elected coordinator cannot proceed without considering the states of all of the operational participants? (Answer YES / NO)
If your answer is YES, which state is it? ______________
f)Consider a termination protocol for the situation as in the case above, i.e., when there is a failure of a site containing both the coordinator and a local participant. When the new coordinator is elected, it asks all operational participants to supply their states (and receives the state information from each of the operational participants). State in the table below whether or not the coordinator can safely terminate the transaction based on the answers from the operational participants.
Operational Participants’ States Enter one of:
Can Abort,
Can Commit,
Blocked (cannot safely commit or abort)
One operational participant is in Abort state, the rest are in Ready state
All operational participants are in the Ready state
One or more operational participants, but not all, are in the Commit state while the rest are in the Ready state
Assignment 4 – Transaction Management
Write name and student ID below, then your write your answers directly into this document and submit the pdf version of the file while making sure that the name of your file is in the format “A4-B00XXXXXX-YourLastName-4140.pdf”, where “B00XXXXXX” is your student ID and “YourLastName” is your last name.
Write your answers directly in this doc.
First Name:
Last Name:
Student ID:
1.Consider the following histories/schedules:
H1 ={ R2(z); W1(x); W1(y); R3(x); R2(x); R1(z); R2(y); W3(x) }
H2 ={ W1(x); R3(x); W3(x); R2(x); W1(y); R2(y); R2(z); R1(z) }
H3 ={ W1(x); W1(y); R1(z); R3(x); W3(x); R2(x); R2(z); R2(y) }
H4 ={ R2(z); R2(y); W1(x); W1(y); R3(x) ; R1(z); R2(x); W3(x) }
Use the tables below for your answers for questions which ask if schedules are equivalent. Use answer “YES” and “NO” as indicated in the column dealing with “if two schedules are equivalent or not”. If you state that the schedules are not equivalent, then state the reason why (usually by providing evidence that two schedules do not satisfy one of the conditions for two schedules being equivalent). The first row is already filled with answers as an example.
(i) Which of the above histories are conflict equivalent? If they are not conflict equivalent, why not?
Pair of Histories Conflict Equivalent
(YES/NO and if NO then reason)
H1, H2 NO: (conflicting pair order (R2(x), W3(x)) in H1, (W3(x), R2(x)) in H2)
H1, H3
H1, H4
H2, H3
H2, H4
H3, H4
(ii) Which of the above histories are view equivalent? If they are not view equivalent, why not?
Pair of Histories View Equivalent
(YES/NO and if NO then reason
H1, H2 NO: (R2(x) sees write W1(x) in H1 & sees write W3(x) in H2)
H1, H3
H1, H4
H2, H3
H2, H4
H3, H4
(iii) Which of the above histories are conflict-serializable? For each conflict-serializable schedule also state to which serial schedules it is equivalent (i.e., list all serial schedules to which it is equivalent).
(iv) Which of the above histories are view-serializable? For each view-serializable schedule also state to which serial schedules it is equivalent (i.e., list all serial schedules to which it is equivalent).
2.Consider the Basic Time-stamp Ordering algorithm and also the following transactions that are attempting to access a DB item. For each case state the outcome (proceed with the operation or abort the transaction) and also show any changes to the DB item's time-stamps.
For each case below (i.e., for each and every row in the table below) assume that X has a read time-stamps of 60 and a write time-stamp of 50 – i.e., assume that the cases are independent of each other.
TS … Time Stamp
Transaction TS Operation on X (Read/Write) Result
(Abort / Proceed) New Read TS for X (if any) New Write TS for X (if any)
3.Consider the last paragraph on the page 379 of Dr. Ozsu’s book, which deals with the Basic Timestamp Ordering (TO) algorithm:
“Remember that in the case of strict 2PL algorithms, the releasing of locks is delayed further, until the commit or abort of a transaction. It is possible to develop a strict TO algorithm by using a similar scheme. For example, if Wi(x) is accepted and released to the data processor, the scheduler delays all Rj(x) and Wj(x) operations (for all Tj) until Ti terminates (commits or aborts).” Such an algorithm was presented in the class and is in the course presentation materials (see the file with a name “6-Transactions Equivalence Serializability – Ozsu.pdf” in the module Slides on Brightspace).
a.Consider a strict TO algorithm, also referred to as “Basic Timestamp Method with Prewrites,” as described above, presented in class, and reviewed again in the following text. Assume that a DB item X has a read time-stamp of 32 and a write time-stamp of 41. Consider also the following transactions that are attempting to access the DB item X. Notation used: a transaction, its timestamp, and its operation are denoted by an ordered pair, in which the first item is the transaction’s timestamp, while the second item is the transaction’s operation. For instance, (60, R) denotes a read by a transaction with a timestamp of 60. Furthermore, a write, by a transaction on a DB item x, is performed in two steps. During the transaction’s execution phase, its write to x is called a pre-write and any subsequent reads and writes on the DB item by other transactions are delayed (queued in the reverse order of their time-stamps) unless, of course, they are aborted. When the transaction is terminated successfully (i.e., committed), only then any writes by the transaction are performed (one could express it as the transaction’s pre-writes are transformed to writes). Upon a transaction’s commit, for each of the transaction’s pre-write, its write is issued. Consider the commitment of the transaction that has a pre-write queued on the data item x: a write is issued for the transaction on x and the pre-write that is queued in x’s queue is converted to a write. If that write is at the head of the x’s queue, it is executed and removed from the queue. If the item at the head of the queue is a read or a write, it is also executed and removed from the queues, and so on.
Notation for operations:
R … Read, P … Pre-write, and W … Write (signaling conversion of pre-writes to writes).
For each operation in the table below, show (in the table):
- whether the transaction is
- Aborted (by entering A),
- Delayed/Queued (enter Q), or
- Executed/Done (enter E)
- show a new value of the data item’s timestamp(s), if any, and
- show the content of the queue of delayed operations (reads, prewrites, writes for the DB item X).
Note that the effects on the DB item are cumulative. That is, the results of one operation affect the results of subsequent operations.
TS … Time Stamp Op … Operation
Trans-action’s
(TS, Op) Aborted/
Queued/
Performed
(A/Q/E) New
Read TS
for X
(if any) New
Write TS for X
(if any) Queue Content
Queue Front ……………………..…..Queue Back
Initial 30 40 Initially Empty
Now assume that the transaction with a timestamp of 60 has successfully finished its work and it that it has issued a commit request. As part of its commit process, a write operation on X is issued, i.e., (60, W) is issued on X. Briefly describe what happens next.
4.This question deals with the 2-Phase Commit (2-PC) protocol. Note that it does NOT deal with network partitioning.
a)Consider a failure of a site containing a participant. Upon the site-failure recovery, how does the recovery procedure determine the state of the participant just prior to the failure?
b)Consider a site failure containing a participant. How does the coordinator find out that a participant has failed?
c)Consider a participant (of a 2PC-protocol), a participant that has failed (site failure). After the failure is fixed, the recovery procedure determines the state of the transaction just prior to the failure. For each state of the transaction just prior to the failure, indicate in the table below whether the recovery procedure can locally terminate the transaction immediately (i.e., without consulting the coordinator) or whether it has to consult the coordinator before terminating the transaction. Enter only T or F (T for True and F for False) as answers.
Participant’s State
Initial Ready
Can abort the transaction immediately
Can commit the transaction immediately
Must consult the coordinator before terminating the transaction
d)Consider a situation in which a participant (of the 2PC-protocol) has failed. The coordinator has timed-out and faces the decision whether it can terminate the transaction and if so whether to abort it or commit it. This decision, of course, depends on its (coordinator’s) state. In the table below, indicate for each of the coordinator’s states whether the transaction can be aborted, committed, or whether the coordinator must wait for the participant’s repair (i.e., that the transaction is blocked until repair). Enter T or F (T for True and F for False) in each of the table entries under the Coordinator’s State.
Coordinator’s State
Initial Wait
Can abort the transaction immediately
Can commit the transaction immediately
Must wait for the participant’s repair
e)Consider the situation in which a site containing a coordinator and a participant has failed. The operational participants have timed-out waiting for instructions/messages from the coordinator, messages that are not arriving because the site, where the coordinator (and a participant as well) is located, is still not operational. Consider the following termination protocol. A new coordinator is elected such that it is located at a site of one of the operational participants - call this participant (at the site where the new coordinator is located) the local participant. The newly elected coordinator consults the state of the local participant. Depending on the state of the local participant, state in the table below whether the newly elected coordinator can safely terminate the transaction without considering the states of the other (non-local) operational participants. Safe termination means that if the newly elected coordinator leads the operational participants to transaction’s termination (commit or abort) – the termination will NOT be inconsistent with the transaction’s termination that could have been reached at the failed site by the coordinator and the participant just before the failure at the site.
Local Participant’s State
Initial Ready
Can abort the transaction immediately without considering the states of all of the operational participants (enter only T or F (T for True and F for False) as answers)
Can commit the transaction without considering the states of all of the operational participants (enter only T or F (T for True and F for False) as answers)
Is there a state in which the newly elected coordinator cannot proceed without considering the states of all of the operational participants? (Answer YES / NO)
If your answer is YES, which state is it? ______________
f)Consider a termination protocol for the situation as in the case above, i.e., when there is a failure of a site containing both the coordinator and a local participant. When the new coordinator is elected, it asks all operational participants to supply their states (and receives the state information from each of the operational participants). State in the table below whether or not the coordinator can safely terminate the transaction based on the answers from the operational participants.
Operational Participants’ States Enter one of:
Can Abort,
Can Commit,
Blocked (cannot safely commit or abort)
One operational participant is in Abort state, the rest are in Ready state
All operational participants are in the Ready state
One or more operational participants, but not all, are in the Commit state while the rest are in the Ready state