Conflict and View Serializability in DBMS – Practice Question

Question:

Which of the following are true?

• A: All view serializable schedules are conflict serializable as well.
• B: All conflict serializable schedules are view serializable as well.
• C: If a schedule is view serializable, then it is serializable.
• D: All serial schedules are conflict serializable and view serializable.

Options:

1. A, B, D
2. B only
3. D only
4. None of the above

Correct Answer:

Option 4: None of the above

Solution:

1. Conflict Serializable and View Serializable:
– All conflict serializable schedules are also view serializable.
– However, not all view serializable schedules are conflict serializable, as view serializability is broader.

2. Serial Schedules:
– All serial schedules are trivially conflict serializable and view serializable because they lack conflicts.

3. View Serializability and Serializability:
– If a schedule is view serializable, it must also be serializable, as view serializability ensures execution matches some serial schedule.

Reasoning: Options A, B, C, and D are individually valid statements but do not collectively satisfy the requirements of the question. Thus, “None of the above” is the correct answer.

Binary Relations, Candidate Keys, and Normal Forms – Practice Question

Question:

Which statement is incorrect among the following?

• A: Every Binary Relation (a relation with only 2 attributes) is always in BCNF.
• B: If a Relation has only singleton candidate keys, then the relation is always in 2NF.
• C: If all attributes of a relation are prime attributes, then the relation is always in BCNF.

Options:

1. A
2. B
3. C
4. None of the above

Correct Answer:

Option 3: C

Solution:

1. Binary Relation (A):
– A binary relation, having only two attributes, always satisfies the conditions of BCNF because either one attribute determines the other, or both form a candidate key.

2. Singleton Candidate Keys (B):
– A relation with singleton candidate keys is always in 2NF, as partial dependencies cannot exist when the candidate key is a single attribute.

3. All Prime Attributes (C):
– If all attributes are prime, the relation is always in 3NF because there are no transitive or partial dependencies. However, it may not satisfy BCNF, as BCNF requires that all determinants must be superkeys. For example, in a relation \( R(A, B, C) \) with functional dependencies \( AB \to C \) and \( C \to B \), it is in 3NF but not BCNF.

Conclusion: Statement C is incorrect because being “all prime attributes” ensures 3NF but not necessarily BCNF.

Functional and Multivalued Dependencies in DBMS – Practice Question

Question:

Consider a relation R with five attributes ABCDE. For each of the following instances of R, the FD = {BC → D} and the MVD = {BC →→ D}:

• I: For {}, does not violate either dependency.
• II: For {(a,2,3,4,5), (2,a,3,5,5)}, FD is violated but MVD is not violated.
• III: For {(a,2,3,4,5), (2,a,3,7,5), (a,2,3,4,6)}, both FD and MVD are violated.
• IV: For {(a,2,3,4,5), (a,2,3,6,5), (a,2,3,4,6)}, FD does not hold, and MVD is not violated.

Which of the above statements is true?

Options:

1. I and III
2. II, III, and IV
3. I, III, and IV
4. All of the above

Correct Answer:

Option D: All of the above

Solution:

1. Case I (Empty Relation):
– The relation is empty, so there are no tuples to violate FD or MVD.
Result: No violation.

2. Case II:
– FD BC → D is violated because D values differ for BC = 3.
– MVD BC →→ D is not violated because it allows independent values of D.

3. Case III:
– Both FD BC → D and MVD BC →→ D are violated because D values conflict.

4. Case IV:
– FD BC → D does not hold (values conflict for BC = 3), but MVD BC →→ D is not violated.

Conclusion: All statements are correct. Hence, the correct option is “All of the above.”

Conflict Serializability and Schedules in DBMS – Practice Question

Question:

Which of the following statements is false?

• A: Every cascadeless schedule is recoverable.
• B: Serializability ensures correctness of a schedule.
• C: A conflict serializable schedule is always equivalent to one and only one single serial schedule.
• D: None of these.

Correct Answer:

Option C: A conflict serializable schedule is always equivalent to one and only one single serial schedule.

Solution:

1. Statement A:
– This is true. Cascadeless schedules ensure transactions only read committed data, inherently making them recoverable by preventing cascading aborts.

2. Statement B:
– This is true. Serializability ensures that a schedule is equivalent to a serial execution, preserving consistency and isolation.

3. Statement C:
– This is false. Conflict serializability allows for multiple equivalent serial schedules. The linear ordering of transactions corresponds to the topological sorting of the serialization graph, which may yield multiple valid orders.

Conclusion: Statement C is incorrect, making it the correct answer to this question.

Understanding BCNF and Functional Dependencies in DBMS

Question:

Let R(A, B, C, D, E) be a relation in BCNF. Suppose CDE is the only key in relation R. Which of the following dependencies is guaranteed to hold in R?

• A: BCD → A
• B: ABC → D
• C: ACDE → B
• D: CD → B

Correct Answer:

Option C: ACDE → B

Solution:

1. BCNF Criteria:
– A relation is in BCNF if for every functional dependency X → Y, X must be a superkey.

2. Key of Relation:
– The key of the relation R is CDE, meaning any functional dependency must include CDE or a superkey on the left-hand side.

3. Option Analysis:
– A: BCD → A — Invalid. BCD is not a superkey.
– B: ABC → D — Invalid. ABC is not a superkey.
– C: ACDE → B — Valid. ACDE is a superkey since it contains CDE.
– D: CD → B — Invalid. CD is not a superkey.

Conclusion: Only Option C satisfies the BCNF condition.

Counting Redundant Functional Dependencies in DBMS

Question:

What is the number of redundant FDs possible for the given set of FD A → B, B → C, C → D for relation R(ABCD)?

Correct Answer:

168

Solution:

1. Total FDs for Relation:
– For relation R(ABCD), the total number of FDs is given by \( 2^4 = 16 \).

2. Non-redundant FDs:
– Minimal set of FDs: \( A → B, B → C, C → D \), which are 3 in total.

3. Redundant FDs:
– Total redundant FDs = Total possible FDs – Minimal FDs = 168.

Conclusion: The number of redundant FDs for \( R(ABCD) \): 168.

Finding Minimal Cover of Functional Dependencies in DBMS

Question:

FD’s of relation Contracts are given as {C → CSJDPQV, JP → C, SD → P, J → S}. Choose the correct minimal cover of the given FD’s from the options below:

• A: C → QV, C → JD, JP → C, SD → P, J → S
• B: C → QDV, JP → C, SD → P, J → S
• C: C → JDQV, J → C, SD → P, J → S
• D: C → JDQV, JP → C, SD → P, J → S

Correct Answer:

Option D: C → JDQV, JP → C, SD → P, J → S

Solution:

1. Given FD’s:
C → CSJDPQV, JP → C, SD → P, J → S

2. Decomposition of C → CSJDPQV:
– Decompose into individual dependencies: C → C, C → S, C → J, C → D, C → P, C → Q, C → V.
– Remove trivial dependency C → C.

3. Eliminating Redundancies:
– C → P is implied by C → SD and SD → P.
– C → S is implied by C → J and J → S.
– Remaining minimal FDs: C → JDQV, JP → C, SD → P, J → S.

4. Verifying Against Options:
– Option D represents the minimal cover: C → JDQV, JP → C, SD → P, J → S.

Conclusion: The correct answer is Option D.

Conflict Serializability in DBMS – Transaction Scheduling

Question:

Consider the following schedule with four transactions:

Here:

• R(A, B, C): Read operations on A, B, C.
• W(A, B, C): Write operations on A, B, C.
• C: Commit operation.

Timestamp	T1	T2	T3	T4
1	W(A)
2		R(A)
3		R(B)	R(B)
4	W(C)			R(C)
5			W(C)
7	W(A)
8				W(B)
9	C	C	C	C

If we add R(B) between timestamp 7 and 8 to make it non-conflict serializable, what place would it be?

• A: T3
• B: T2
• C: T1
• D: It will remain conflict serializable

Correct Answer:

Option D: It will remain conflict serializable

Solution:

1. Conflict Serializability:
– Checks if the schedule can be transformed into a serial schedule by swapping non-conflicting operations.
– Conflicts arise due to write-read, read-write, or write-write conflicts.

2. Current Schedule Analysis:
– The given schedule is conflict serializable, as no conflicting operations violate serializability.

3. Adding R(B) Between Timestamps 7 and 8:
– Adding R(B) does not introduce additional conflicts. The schedule remains conflict serializable.

Conclusion: Adding R(B) does not affect conflict serializability. The schedule remains conflict serializable.

Calculating Schedules in DBMS – Transaction Operations

Question:

Given 3 transactions T1, T2, and T3, which have (2,2), (3,2), (4,2) read and write operations respectively, the number of schedules possible using these three transactions is:

• A: 1260
• B: 630630
• C: 6
• D: 63000

Correct Answer:

Option B: 630630

Solution:

1. Formula for Number of Schedules:
– The number of possible schedules is given by:
\[
\frac{(n_1 + n_2 + n_3)!}{n_1! \cdot n_2! \cdot n_3!}
\]
– Where \( n_1, n_2, n_3 \) are the total operations (read + write) for each transaction.

2. Total Operations:
– \( T_1: 2 + 2 = 4 \),
– \( T_2: 3 + 2 = 5 \),
– \( T_3: 4 + 2 = 6 \),
– Total operations: \( n_1 + n_2 + n_3 = 4 + 5 + 6 = 15 \).

3. Factorial Calculations:
– Total factorial: \( 15! = 1,307,674,368,000 \),
– Individual factorials:
\( 4! = 24, \quad 5! = 120, \quad 6! = 720 \).

4. Number of Schedules:
Substitute into the formula:
\[
\frac{15!}{4! \cdot 5! \cdot 6!} = \frac{1,307,674,368,000}{24 \cdot 120 \cdot 720} = 630630
\]

Conclusion: The total number of schedules possible is 630630.

Recoverability in DBMS – Analyzing Transaction Schedules

Question:

Given the schedule S:

S: r1(x), r2(z), w1(x), r3(x), r2(y), w2(y), w3(x), r3(y), r2(x)

For the schedule S, two orderings of commit operations are specified:

1. c1, c3, c2
2. c1, c2, c3

Which of these orderings ensures recoverability of schedule S?

• A: Only I
• B: Both I and II
• C: Only II
• D: None of these

Correct Answer:

Option D: None of these

Solution:

1. Definition of Recoverability:
– A schedule is recoverable if transactions read data written by other transactions only after the writing transactions commit.

2. Order Analysis:
– Order I (c1, c3, c2):
– T3 reads uncommitted data from T2 (r3(y) reads y written by w2(y)).
– T3 commits (c3) before T2 (c2), violating recoverability.

– Order II (c1, c2, c3):
– T2 reads uncommitted data from T3 (r2(x) reads x written by w3(x)).
– T2 commits (c2) before T3 (c3), violating recoverability.

Conclusion: Both orders fail to ensure recoverability due to dirty reads and incorrect commit sequences. Therefore, the correct answer is Option D: None of these.

DBMS Scheduling: Cascadeless and Recoverable Schedules

Question:

Consider the following schedule S:

S: r1(y), r2(z), w1(y), w1(y), r2(x), w2(x), w2(y), r1(x), c1, c2

Which of the following is true about S?

• A: S is cascadeless
• B: S is not cascadeless but recoverable
• C: S is not recoverable, but changing the order of commits to c2, c1 makes the schedule recoverable
• D: S is not recoverable, and changing the order of commits to c2, c1 does not make the schedule recoverable

Correct Answer:

Option D: S is not recoverable, and changing the order of commits to c2, c1 does not make the schedule recoverable

Solution:

1. Cascadelessness:
– A schedule is cascadeless if transactions read only committed data.
– In S, r1(x) reads x written by w2(x) before T2 commits, and r2(y) reads y written by w1(y) before T1 commits. Hence, S is not cascadeless.

2. Recoverability:
– A schedule is recoverable if a transaction reads data written by another transaction only after the writing transaction commits.
– In S, r1(x) reads uncommitted data from w2(x), and r2(y) reads uncommitted data from w1(y). This violates recoverability.

3. Impact of Changing Commit Order:
– Changing the commit order to c2, c1 does not resolve the dirty reads.
– r2(y) still reads uncommitted y from w1(y), and r1(x) still reads uncommitted x from w2(x). Hence, recoverability is not achieved.

Conclusion: S is not recoverable, and changing the commit order does not help. The correct answer is Option D.

Understanding Recoverability and Keys in DBMS

Question 13:

Consider a relation R that has 3 attributes ABC. It is decomposed into relations R1(AB) and R2(BC). If you are given the following instances of R1 and R2, which of the following is not true about the instances of R from which these are obtained?

Instances:

• R1 = {(5,1), (6,1)}
• R2 = {(1,8), (1,9)}

• Statement I: The instances of R from which the given instances of R1 and R2 were obtained must be a subset of the set of ABC tuples.
• Statement II: Attribute B is the key for R.

Options:

• A: Statement I
• B: Statement II
• C: Both Statement I and II
• D: Neither Statement I nor Statement II

Correct Answer:

Option B: Statement II

Solution:

– Statement I is true because the decomposition ensures the subset condition.
– Statement II is false because B cannot uniquely determine A and C.

Question 14:

For the given schedule S, which of the following statement(s) is (are) true?

S: r1(x), w1(x), r2(x), r1(y), w1(y), w2(x), r2(y), c1, c2;

Statements:

1. S is recoverable.
2. If the order of w1(x) and w2(x) are interchanged, then S will be a non-recoverable schedule.

Options:

• A: Only I
• B: Only II
• C: Both I and II
• D: None of the above

Correct Answer:

Option A: Only I

Solution:

– Statement I: S is recoverable as no dirty reads occur.
– Statement II: Interchanging write operations does not make the schedule non-recoverable.