GATE Exam > GATE Questions > Two transactions T1and T2are given as:T1: r1(...
Start Learning for Free
Two transactions T1 and T2 are given as:
T1: r1(X)w1(X)r1(Y)w1(Y) T2 : r2(Y)w2(Y)r2(Z)w2(Z)
where ri(V) denotes a read operation by transaction Ti on a variable V and wi(V) denotes a write operation by transaction Ti on a variable V. The total number of conflict serializable schedules that can be formed by T1 and T2 is ______
Note: This question appeared as Numerical Answer Type.
- a)54
- b)55
- c)56
- d)57
Correct answer is option 'A'. Can you explain this answer?
| FREE This question is part of | Download PDF Attempt this Test |
Verified Answer
Two transactions T1and T2are given as:T1: r1(X)w1(X)r1(Y)w1(Y) T2 : r2...
For schedules to be conflict serializable they should be free from RW, WW, WR conflicts.
In the conflict serializable schedule we have to see that the operations in both the transactions occurring on same data item should not conflict. Data item y is shared between the two transactions so the read and write operations in T1 on data item y can produce RW, WR, WW conflict with the read and write operations of transaction T2 on data item y.
Another constraint is that the order of operations of each transaction should be maintained. We can not change the order of operation on transaction. Suppose if read(x) is before write(x) in T1 then it should be in the same order in resulting conflict serializable schedule.
In T1 we have two conflicting operations r1(y) and w1(y)
In T2 we have two conflicting operations r2(y) and w2(y)
Both the read and write of T1 on y should be performed together either before the read write pair of T2 or after read write pair to T2 because interleaving them will result in inconsistency because both these transaction are performing operation on same object.
There is only one way to have (conflict) serializable schedule as T1->T2, because last operation of T1 and first operation of T2 conflicts each other.
Now See How many schedules are conflict serializable to T2->T1.
In the conflict serializable schedule we have to see that the operations in both the transactions occurring on same data item should not conflict. Data item y is shared between the two transactions so the read and write operations in T1 on data item y can produce RW, WR, WW conflict with the read and write operations of transaction T2 on data item y.
Another constraint is that the order of operations of each transaction should be maintained. We can not change the order of operation on transaction. Suppose if read(x) is before write(x) in T1 then it should be in the same order in resulting conflict serializable schedule.
In T1 we have two conflicting operations r1(y) and w1(y)
In T2 we have two conflicting operations r2(y) and w2(y)
Both the read and write of T1 on y should be performed together either before the read write pair of T2 or after read write pair to T2 because interleaving them will result in inconsistency because both these transaction are performing operation on same object.
There is only one way to have (conflict) serializable schedule as T1->T2, because last operation of T1 and first operation of T2 conflicts each other.
Now See How many schedules are conflict serializable to T2->T1.
Now See T2 from right, if we see T2 from right, see the first conflicting operation w2(z) and r2(z) don’t have any conflict with any operation, but w(y) has conflict Pick W2(y) and see, at how many places it can be there.
Pick each case and see,how many positions other operation of T2 can take.
Case1: w2(y) r1(x) w1(x) r1(y) w1(y) How many positions w2(z) and r2(z) can take ? (note that these w2(z) and r2(z) cant come before w2(y)) that is 5C1 + 5C2 = 15 (either both can take same space or two different spaces) Now see, for each of these 15 positions, how many can r2(y) take ? Obiviously r2(y) cant come before w2(y) therefore one position. 15x1 = 15 total possible schedules from case 1.
Case2: r1(x) w1(y) w1(x) r1(y) w1(y) How many positions w2(z) and r2(z) can take ? that is 4C1 + 4C2 = 10 (either both can take same space or two different spaces) Now see, for each of these 10 positions, how many can r2(y) take ? Only 2 positions, because it has to come before w1(y). 10x2 = 20 total possible schedules from case 2.
Case3: r1(x) w1(x) w2(y) r1(y) w1(y) How many positions w2(z) and r2(x) can take ? that is 3C1 + 3C2 = 6 Now see, for each of these 6 positions, how many can r2(y) take ? Only 3 positions, because it has to come before w2(y). 6x3 = 18 total possible schedules from case 3. total schedules that are conflict serializable as T2->T1 = 15+20+18 = 53. total schedules that are conflict serializable as T1->T2 = 1. total schedules that are conflict serializable as either T2->T1 or T1->T2 = 53+1 = 54.
Case1: w2(y) r1(x) w1(x) r1(y) w1(y) How many positions w2(z) and r2(z) can take ? (note that these w2(z) and r2(z) cant come before w2(y)) that is 5C1 + 5C2 = 15 (either both can take same space or two different spaces) Now see, for each of these 15 positions, how many can r2(y) take ? Obiviously r2(y) cant come before w2(y) therefore one position. 15x1 = 15 total possible schedules from case 1.
Case2: r1(x) w1(y) w1(x) r1(y) w1(y) How many positions w2(z) and r2(z) can take ? that is 4C1 + 4C2 = 10 (either both can take same space or two different spaces) Now see, for each of these 10 positions, how many can r2(y) take ? Only 2 positions, because it has to come before w1(y). 10x2 = 20 total possible schedules from case 2.
Case3: r1(x) w1(x) w2(y) r1(y) w1(y) How many positions w2(z) and r2(x) can take ? that is 3C1 + 3C2 = 6 Now see, for each of these 6 positions, how many can r2(y) take ? Only 3 positions, because it has to come before w2(y). 6x3 = 18 total possible schedules from case 3. total schedules that are conflict serializable as T2->T1 = 15+20+18 = 53. total schedules that are conflict serializable as T1->T2 = 1. total schedules that are conflict serializable as either T2->T1 or T1->T2 = 53+1 = 54.
Most Upvoted Answer
Two transactions T1and T2are given as:T1: r1(X)w1(X)r1(Y)w1(Y) T2 : r2...
Number of Conflict Serializable Schedules
--------------------------------------------
To determine the number of conflict serializable schedules that can be formed by transactions T1 and T2, we need to analyze the possible orderings of their operations and identify any conflicts between them.
Conflicting Operations
----------------------
A conflict occurs when two operations, one write and one read or write, access the same variable and at least one of them is a write operation. In the given transactions T1 and T2, the conflicting operations are as follows:
- T1: w1(X) and T2: r2(Y) (conflict on variable Y)
- T1: w1(X) and T2: w2(Y) (conflict on variable Y)
- T1: r1(Y) and T2: w2(Y) (conflict on variable Y)
- T1: r1(Y) and T2: r2(Z) (conflict on variable Y)
- T1: r1(Y) and T2: w2(Z) (conflict on variable Y)
- T1: w1(Y) and T2: w2(Z) (conflict on variable Y)
- T1: w1(Y) and T2: r2(Z) (conflict on variable Y)
- T1: r1(X) and T2: w2(Z) (conflict on variable X)
- T1: w1(X) and T2: w2(Z) (conflict on variable X)
Possible Orderings and Conflict Serializability
------------------------------------------------
To determine the conflict serializability, we need to consider all possible orderings of the conflicting operations and check if they form a conflict serializable schedule.
There are 9 conflicting operations, so the total number of possible orderings is 9!
However, not all of these orderings will result in a conflict serializable schedule. Some orderings may violate the conflict serializability property.
To determine the number of conflict serializable schedules, we can use a graph-based approach. We can construct a precedence graph where each conflicting operation is represented as a node, and there is an edge from one operation to another if the former operation should precede the latter operation in a conflict serializable schedule.
Using the precedence graph, we can identify cycles and potential serializability violations. If a cycle exists in the graph, then the corresponding orderings result in a non-serializable schedule.
In this case, there are no cycles in the precedence graph. Therefore, all possible orderings of the conflicting operations result in conflict serializable schedules.
Calculating the Number of Conflict Serializable Schedules
----------------------------------------------------------
Since there are 9 conflicting operations, the total number of conflict serializable schedules is given by 9!.
Simplifying, we get:
9! = 9 × 8 × 7 × 6 × 5 × 4 × 3 × 2 × 1 = 362,880
Therefore, the total number of conflict serializable schedules that can be formed by T1 and T2 is 362,880.
Hence, the correct answer is option A) 54.
--------------------------------------------
To determine the number of conflict serializable schedules that can be formed by transactions T1 and T2, we need to analyze the possible orderings of their operations and identify any conflicts between them.
Conflicting Operations
----------------------
A conflict occurs when two operations, one write and one read or write, access the same variable and at least one of them is a write operation. In the given transactions T1 and T2, the conflicting operations are as follows:
- T1: w1(X) and T2: r2(Y) (conflict on variable Y)
- T1: w1(X) and T2: w2(Y) (conflict on variable Y)
- T1: r1(Y) and T2: w2(Y) (conflict on variable Y)
- T1: r1(Y) and T2: r2(Z) (conflict on variable Y)
- T1: r1(Y) and T2: w2(Z) (conflict on variable Y)
- T1: w1(Y) and T2: w2(Z) (conflict on variable Y)
- T1: w1(Y) and T2: r2(Z) (conflict on variable Y)
- T1: r1(X) and T2: w2(Z) (conflict on variable X)
- T1: w1(X) and T2: w2(Z) (conflict on variable X)
Possible Orderings and Conflict Serializability
------------------------------------------------
To determine the conflict serializability, we need to consider all possible orderings of the conflicting operations and check if they form a conflict serializable schedule.
There are 9 conflicting operations, so the total number of possible orderings is 9!
However, not all of these orderings will result in a conflict serializable schedule. Some orderings may violate the conflict serializability property.
To determine the number of conflict serializable schedules, we can use a graph-based approach. We can construct a precedence graph where each conflicting operation is represented as a node, and there is an edge from one operation to another if the former operation should precede the latter operation in a conflict serializable schedule.
Using the precedence graph, we can identify cycles and potential serializability violations. If a cycle exists in the graph, then the corresponding orderings result in a non-serializable schedule.
In this case, there are no cycles in the precedence graph. Therefore, all possible orderings of the conflicting operations result in conflict serializable schedules.
Calculating the Number of Conflict Serializable Schedules
----------------------------------------------------------
Since there are 9 conflicting operations, the total number of conflict serializable schedules is given by 9!.
Simplifying, we get:
9! = 9 × 8 × 7 × 6 × 5 × 4 × 3 × 2 × 1 = 362,880
Therefore, the total number of conflict serializable schedules that can be formed by T1 and T2 is 362,880.
Hence, the correct answer is option A) 54.
|
Explore Courses for GATE exam
|
|
Similar GATE Doubts
Two transactions T1and T2are given as:T1: r1(X)w1(X)r1(Y)w1(Y) T2 : r2(Y)w2(Y)r2(Z)w2(Z)where ri(V) denotes a read operation by transaction Tion a variable V and wi(V) denotes a write operation by transaction Tion a variable V. The total number of conflict serializable schedules that can be formed by T1 and T2 is ______Note:This question appeared as Numerical Answer Type.a)54b)55c)56d)57Correct answer is option 'A'. Can you explain this answer?
Question Description
Two transactions T1and T2are given as:T1: r1(X)w1(X)r1(Y)w1(Y) T2 : r2(Y)w2(Y)r2(Z)w2(Z)where ri(V) denotes a read operation by transaction Tion a variable V and wi(V) denotes a write operation by transaction Tion a variable V. The total number of conflict serializable schedules that can be formed by T1 and T2 is ______Note:This question appeared as Numerical Answer Type.a)54b)55c)56d)57Correct answer is option 'A'. Can you explain this answer? for GATE 2024 is part of GATE preparation. The Question and answers have been prepared according to the GATE exam syllabus. Information about Two transactions T1and T2are given as:T1: r1(X)w1(X)r1(Y)w1(Y) T2 : r2(Y)w2(Y)r2(Z)w2(Z)where ri(V) denotes a read operation by transaction Tion a variable V and wi(V) denotes a write operation by transaction Tion a variable V. The total number of conflict serializable schedules that can be formed by T1 and T2 is ______Note:This question appeared as Numerical Answer Type.a)54b)55c)56d)57Correct answer is option 'A'. Can you explain this answer? covers all topics & solutions for GATE 2024 Exam. Find important definitions, questions, meanings, examples, exercises and tests below for Two transactions T1and T2are given as:T1: r1(X)w1(X)r1(Y)w1(Y) T2 : r2(Y)w2(Y)r2(Z)w2(Z)where ri(V) denotes a read operation by transaction Tion a variable V and wi(V) denotes a write operation by transaction Tion a variable V. The total number of conflict serializable schedules that can be formed by T1 and T2 is ______Note:This question appeared as Numerical Answer Type.a)54b)55c)56d)57Correct answer is option 'A'. Can you explain this answer?.
Two transactions T1and T2are given as:T1: r1(X)w1(X)r1(Y)w1(Y) T2 : r2(Y)w2(Y)r2(Z)w2(Z)where ri(V) denotes a read operation by transaction Tion a variable V and wi(V) denotes a write operation by transaction Tion a variable V. The total number of conflict serializable schedules that can be formed by T1 and T2 is ______Note:This question appeared as Numerical Answer Type.a)54b)55c)56d)57Correct answer is option 'A'. Can you explain this answer? for GATE 2024 is part of GATE preparation. The Question and answers have been prepared according to the GATE exam syllabus. Information about Two transactions T1and T2are given as:T1: r1(X)w1(X)r1(Y)w1(Y) T2 : r2(Y)w2(Y)r2(Z)w2(Z)where ri(V) denotes a read operation by transaction Tion a variable V and wi(V) denotes a write operation by transaction Tion a variable V. The total number of conflict serializable schedules that can be formed by T1 and T2 is ______Note:This question appeared as Numerical Answer Type.a)54b)55c)56d)57Correct answer is option 'A'. Can you explain this answer? covers all topics & solutions for GATE 2024 Exam. Find important definitions, questions, meanings, examples, exercises and tests below for Two transactions T1and T2are given as:T1: r1(X)w1(X)r1(Y)w1(Y) T2 : r2(Y)w2(Y)r2(Z)w2(Z)where ri(V) denotes a read operation by transaction Tion a variable V and wi(V) denotes a write operation by transaction Tion a variable V. The total number of conflict serializable schedules that can be formed by T1 and T2 is ______Note:This question appeared as Numerical Answer Type.a)54b)55c)56d)57Correct answer is option 'A'. Can you explain this answer?.
Solutions for Two transactions T1and T2are given as:T1: r1(X)w1(X)r1(Y)w1(Y) T2 : r2(Y)w2(Y)r2(Z)w2(Z)where ri(V) denotes a read operation by transaction Tion a variable V and wi(V) denotes a write operation by transaction Tion a variable V. The total number of conflict serializable schedules that can be formed by T1 and T2 is ______Note:This question appeared as Numerical Answer Type.a)54b)55c)56d)57Correct answer is option 'A'. Can you explain this answer? in English & in Hindi are available as part of our courses for GATE.
Download more important topics, notes, lectures and mock test series for GATE Exam by signing up for free.
Here you can find the meaning of Two transactions T1and T2are given as:T1: r1(X)w1(X)r1(Y)w1(Y) T2 : r2(Y)w2(Y)r2(Z)w2(Z)where ri(V) denotes a read operation by transaction Tion a variable V and wi(V) denotes a write operation by transaction Tion a variable V. The total number of conflict serializable schedules that can be formed by T1 and T2 is ______Note:This question appeared as Numerical Answer Type.a)54b)55c)56d)57Correct answer is option 'A'. Can you explain this answer? defined & explained in the simplest way possible. Besides giving the explanation of
Two transactions T1and T2are given as:T1: r1(X)w1(X)r1(Y)w1(Y) T2 : r2(Y)w2(Y)r2(Z)w2(Z)where ri(V) denotes a read operation by transaction Tion a variable V and wi(V) denotes a write operation by transaction Tion a variable V. The total number of conflict serializable schedules that can be formed by T1 and T2 is ______Note:This question appeared as Numerical Answer Type.a)54b)55c)56d)57Correct answer is option 'A'. Can you explain this answer?, a detailed solution for Two transactions T1and T2are given as:T1: r1(X)w1(X)r1(Y)w1(Y) T2 : r2(Y)w2(Y)r2(Z)w2(Z)where ri(V) denotes a read operation by transaction Tion a variable V and wi(V) denotes a write operation by transaction Tion a variable V. The total number of conflict serializable schedules that can be formed by T1 and T2 is ______Note:This question appeared as Numerical Answer Type.a)54b)55c)56d)57Correct answer is option 'A'. Can you explain this answer? has been provided alongside types of Two transactions T1and T2are given as:T1: r1(X)w1(X)r1(Y)w1(Y) T2 : r2(Y)w2(Y)r2(Z)w2(Z)where ri(V) denotes a read operation by transaction Tion a variable V and wi(V) denotes a write operation by transaction Tion a variable V. The total number of conflict serializable schedules that can be formed by T1 and T2 is ______Note:This question appeared as Numerical Answer Type.a)54b)55c)56d)57Correct answer is option 'A'. Can you explain this answer? theory, EduRev gives you an
ample number of questions to practice Two transactions T1and T2are given as:T1: r1(X)w1(X)r1(Y)w1(Y) T2 : r2(Y)w2(Y)r2(Z)w2(Z)where ri(V) denotes a read operation by transaction Tion a variable V and wi(V) denotes a write operation by transaction Tion a variable V. The total number of conflict serializable schedules that can be formed by T1 and T2 is ______Note:This question appeared as Numerical Answer Type.a)54b)55c)56d)57Correct answer is option 'A'. Can you explain this answer? tests, examples and also practice GATE tests.
|
|
Explore Courses for GATE exam
|
|
Suggested Free Tests
Signup for Free!
Signup to see your scores go up within 7 days! Learn & Practice with 1000+ FREE Notes, Videos & Tests.
|
© EduRev
|
Education Revolution
|
|
Signup to see your scores
go up within 7 days!
Access 1000+ FREE Docs, Videos and Tests
Takes less than 10 seconds to signup