GATE Solved Paper 2017-19 - GATE 2019

21. Consider the following two statements about database transaction schedules:
I. Strict two-phase locking protocol generates conflict serializable schedules that are also recoverable.
II. Timestamp-ordering concurrency control protocol with Thomas’ Write Rule can generate view serializable schedules that are not conflict serializable.
Which of the above statements is/are TRUE?

  • Option : C
  • Explanation :
    I. Strict 2PL guaranteed conflict serializable because of 2PL condition and also strict recoverable.
    II. Thomas Write timestamp ordering ensures serializable. Thomas write rule timestamp ordering allowed to execute schedule which is view equal serial schedule based on timestamp ordering.
Cancel reply
Cancel reply

22. Let G be an undirected complete graph on 𝑛 vertices, where n > 2. Then, the number of different Hamiltonian cycles in G is equal to

  • Option : D
  • Explanation :
    In a complete graph we can traverse the n vertices in any order and return to the starting vertex and form a Hamiltonian cycle. The number of such cycles will be n!

    However, since circular rotations will have to ignored. Since for example K4 with vertices {1, 2, 3, 4}, the cycle 1-2-3-4 is same as 2-3-4-1 is same as 3-4-1-2 etc. we now get only (n – 1)! distinct Hamiltonian cycles. Further, the cycle 1-2-3-4 and 1-4-3-2 are also same (clockwise and anticlockwise).

    So ignoring this orientation also we finally get distinct Hamiltonian cycles.
Cancel reply
Cancel reply

23. Compute

  • Option : C
  • Explanation :
    form.
    So apply L’H rule
Cancel reply
Cancel reply

24. Which one of the following statements is NOT correct about the B+ tree data structure used for creating an index of a relational database table?

  • Option : B
  • Explanation :
    B+ tree non-leaf node has a pointer to data records is a false statement.
    B+ tree non-leaf node consists of only keys and tree pointers (node pointers).
    Below is the structure of B+ tree non leaf node
Cancel reply
Cancel reply

25. For Σ = {a, b}, let us consider the regular language L = {x |x = a2+3k or x = b10 + 12k, k ≥ 0}. Which one of the following can be a pumping length (the constant guaranteed by the pumping lemma) for L?

  • Option : B
  • Explanation :
    L = {a2 + 3k or b10 + 12k} for k ≥ 0
    = a2 (a3)* or b10 (b12)*
    = {a2, a5, a8, ..., b10, b22, b234 .....}
    The pumping length is p, than for any string w ∈ L with ⏐w⏐≥ p must have a repetition i.e. such a string must be breakable into w = xyz such that ⏐y⏐≥ 0 and y can be pumped indefinitely, which is same as saying xyz ∈ L ⇒ xy*z ∈ L.

    The minimum pumping length in this language is clearly 11, since b10 is a string which has no repetition number, so upto 10 no number can serve as a pumping length. Minimum pumping length is 11. Any number at or above minimum pumping length can serve as a pumping length. The only number at or above 11, in the choice given is 24. So correct answer is option (B)
Cancel reply
Cancel reply