DBMS GATE-PSUs-NET

Previous Year Question Practices

DBMS

for

GATE-PSUs-UGC NET
Computer Science & Information Technology

Siddharth S. Shukla
{BE (CSE), M.tech.(CTA), PhD*}

website: www.igate.guru

i-GATE, B-713, Street 22, Smriti Nagar, Bhilai- 490020, Contact 98271-62352,96440-14000
[1]
 DBMS GATE-PSUs-NET

Copyright©,i-gate publication

Edition 2020

All right reserved

No part of this book or parts thereof may be reproduced, stored in a retrieval system or transmitted in any
language or by any means, electronic, mechanical, photocopying, recording or otherwise without the prior
written permission of the publisher.

i-GATE, B-713, Street 22, Smriti Nagar, Bhilai- 490020, Contact 98271-62352,96440-14000
[2]
 DBMS GATE-PSUs-NET

TRANSACTION MANAGEMENT
Q.1 In multiuser database if two users wish to update the same record at the same time, they are
prevented from doing so by [NET June 2012]
(A) Jamming (B) Password (C) Documentation (D) Record lock

Q.2 A Transaction Manager is which of the following? [NET June 2012]

(A) Maintains a log of transactions (B) Maintains before and after database images
(C) Maintains appropriate concurrent control(D) All of the above

Q.3 The problem that occurs when one transaction updates a database item and then the transaction
fails for some reason is [NET June 2012]
(A) Temporary Select Problem (B) Temporary Modify Problem
(C) Dirty Read Problem (D) None of these

Q.4 Which of the following is scheme to deal with deadlock? [NET June 2012]
(A) Time out (B) Time in (C) Both A and B (D) None of the above

Q.5 Match the following: [NET June 2014]

LIST-I LIST-II
a. Timeout ordering protocol i. Wait for graph
b. Deadlock prevention ii. Roll back
c. Deadlock detection iii. Wait-die scheme
d. Deadlock recovery iv. Thomas Write Rule
(A) a–iv; b–iii; c–i; d–ii (B) a–iii; b–ii; c–iv; d–i
(C) a–ii; b–i; c–iv; d–iii (D) a–iii; b–i; c–iv; d–iii

Q.6 Which one of the following concurrency protocol ensure both conflict serializability and freedom
from deadlock? [NET June 2014]
I. 2-phase locking II. Time-phase ordering
(A) I only (B) II only (C) Both I and II (C) Neither I nor II

Q.7 Which of the following is correct? [NET Dec. 2014]

I. Two phase locking is an optimistic protocol.
II. Two phase locking is pessimistic protocol
III. Time stamping is an optimistic protocol.
IV. Time stamping is pessimistic protocol.
(A) I and III (B) II and IV (C) I and IV (D) II and III
Q.8 _________ rules used to limit the volume of log information that has to be handled and processed
in the event of system failure involving the loss of volatile information. [NET Dec. 2014]
(A) Write-ahead log (B) Check-pointing (C) Log buffer (D) Thomas

i-GATE, B-713, Street 22, Smriti Nagar, Bhilai- 490020, Contact 98271-62352,96440-14000
[3]
 DBMS GATE-PSUs-NET

Q.9 Consider following schedules involving two transactions: [NET Jan. 2017]
S1: r1(X); r1(Y); r2(X); r2(Y); w2(Y); w1(X)
S2: r1(X); r2(X); r2(Y); w2(Y); r1(Y); w1(X)
Which of the following statement is true?
(A) Both S1 and S2 are conflict serializable.
(B) S1 is conflict serializable and S2 is not conflict serializable.
(C) S1 is not conflict serializable and S2 is conflict serializable.
(D) Both S1 and S2 are not conflict serializable.

Q.10 Consider the following four schedules due to three transactions (indicated by the subscript) using
read and write on a data item X, denoted by r(X) and w(X) respectively. Which one of them is
conflict serializable? [NET Nov. 2017]
S1: r1(X); r2(X); w1(X); r3(X); w2(X)
S2: r2(X); r1(X); w2(X); r3(X); w1(X)
S3: r3(X); r2(X); r1(X); w2(X); w1(X)
S4: r2(X); w2(X); r3(X); r1(X); w1(X)
(A) S1 (B) S2 (C) S3 (D) S4

Q.11 Suppose a database schedule S involves transactions T1, ….Tn. Construct the precedence graph of
S with vertices representing the transactions and edges representing the conflicts. If S is
serializable, which one of the following orderings of the vertices of the precedence graph is
guaranteed to yield a serial schedule? [NET Nov. 2017]
(A) Topological order (B) Depth-first order
(C) Breadth-first order (D) Ascending order of transaction indices

ANSWER KEY
1. (D) 2. (D) 3. (B) 4. (A) 5. (A) 6. (B) 7. (B)
8. (B) 9. (C) 10. (D) 11. (A)

SOLUTION
Sol.1 (D) record lock

Sol.2 Transaction Managers is responsible for maintaining all activities regarding database transaction
like ensuring ACID properties, ensure serializability in concurrency control and database images
hence ans is D.

Sol.3 This problem is called dirty read and it is due to this incorrect result is obtained
Uncommitted Dependency (Dirty Read)
Uncommitted dependency occurs when a second transaction selects a row that is being updated by
another transaction. The second transaction is reading data that has not been committed yet and
may be changed by the transaction updating the row.
For example, an editor is making changes to an electronic document. During the changes, a
second editor takes a copy of the document that includes all the changes made so far, and

i-GATE, B-713, Street 22, Smriti Nagar, Bhilai- 490020, Contact 98271-62352,96440-14000
[4]
 DBMS GATE-PSUs-NET

distributes the document to the intended audience. The first editor then decides the changes made
so far are wrong and removes the edits and saves the document. The distributed document
contains edits that no longer exist, and should be treated as if they never existed. This problem
could be avoided if no one could read the changed document until the first editor determined that
the changes were final.

Sol.4 One of the strategy to avoid deadlock situation in Java Multithreading is using timeout. Suppose,
one thread has acquired lock on one resource and now waiting for lock on another resource. After
certain time period if it cannot acquire lock on resource 2 then it should stop waiting for lock on
resource 2. Also it should release lock on resource 1. Thus deadlocks will be avoided.
So ans. is A

Sol.5 Answer : A
LIST-I LIST-II
a. Timeout ordering protocol iv. Thomas Write Rule
b. Deadlock prevention iii. Wait-die scheme
c. Deadlock detection i. Wait for graph
d. Deadlock recovery ii. Roll back

Sol.6 In basic two phase locking there is a chance for deadlock

Conservative 2pl is deadlock free
Option B

Sol.7 Ans. will be D

Two phase locking is pessimistic protocol (assumes bad thing going to happen) since it applies
locks (for safety).
Time stamping is an optimistic protocol (assumes good thing going to happen) since it uses no
locking. If bad things (multiple writes etc) happen, they are handled later.

Sol.8 B is the ans. Check pointing

Check pointing is a technique to add fault tolerance into computing systems. It basically consists
of saving a snapshot of the application's state, so that it can restart from that point in case of
failure.
In computer science, write-ahead logging (WAL) is a family of techniques for providing atomicity
and durability (two of the ACID properties) in database systems. In a system using WAL, all
modifications are written to a log before they are applied. Usually both redo and undo information
is stored in the log.
In computer science, particularly the field of databases, the Thomas write rule is a rule in
timestamp-based concurrency control. It can be summarized as ignore outdated writes.
Log buffer is a small contiguous memory structure, to host in memory transaction logs per
database.

Sol.9 Ans. will be C

i-GATE, B-713, Street 22, Smriti Nagar, Bhilai- 490020, Contact 98271-62352,96440-14000
[5]
 DBMS GATE-PSUs-NET

conflict serializable means we can first run one Transaction then after it second without any
conflict
conflict occurs when data item is same and at least one operation is read
so for S1 : r1(X); r1(Y); r2(X); r2(Y); w2(Y); w1(X)
here w1(x) cannot be placed before r2(X) as data item is common(X) and one operation is write so
it is not conflict serializable
now for S2 : r1(X); r2(X); r2(Y); w2(Y); r1(Y); w1(X)
here r1(X) can be placed after w2(Y) as data item is different and before that only read operation
are there so it is conflict serializable as T2 can be executed before T1

Sol.10 (D) make precedence graph for all the options, for option (D) only graph will be acyclic, hence
(D) is CSS.

Sol.11 Topological Order.

For a schedule, we can check its serializability by drawing a precedence graph and find its
topological order, precedence graph of schedule must not contain any cycle to be conflict free.

i-GATE, B-713, Street 22, Smriti Nagar, Bhilai- 490020, Contact 98271-62352,96440-14000
[6]
 DBMS GATE-PSUs-NET

BASIC CONCEPTS OF DBMS

Q.1 Which level of abstraction describes what data are stored in the database? [NET June 2012]
(A) Physical level (B) View level (C) Abstraction level (D) Logical level

Q.2 Which level of abstraction describes how data are stored in the date base [NET Dec. 2012]
(A) Physical level (B) View level (C) Abstraction level (D) Logical level

Q.3 Which of the following is not a type of Database Management System? [NET June 2013]
(A) Hierarchical (B) Network (C) Relational (D) Sequential

Q.4 Manager‘s salary details are to be hidden from Employee table. This Technique is called as
(A) Conceptual level Datahiding (B) Physical level Datahiding [NET June 2013]
(C) External level Datahiding (D) Logical level Datahiding

Q.5 A Network Schema [NET June 2013]

(A) restricts to one to many relationship (B) Permits many to many relationship
(C) Stores Data in a Database (D) Stores Data in a Relation

Q.6 Manager‘s salary details are hidden from the employee. This is called as [NET June 2014]
(A) Conceptual level data hiding (B) Physical level data hiding
(C) External level data hiding (D) Local level data hiding

Q.7 Database application were directly built on top of file system to overcome the following
drawbacks of using file-systems: [NET June 2015]
(a) Data redundancy and inconsistency (b) Difficulty in accessing data
(c) Data isolation (d) Integrity problems
(A) a (B) a and d (C) a, b, and c (D) a, b, c, and d

Q.8 Integrity constraints ensure that changes made to the database by authorized users do not result
into loss of data consistency. Which of the following statement(s) is (are) true w.r.t. the examples
of integrity constraints? [NET Jan. 2017]
(I) An instructor Id. No. cannot be null, provided Instructor Id No. being primary key.
(II) No two citizens have same Adhar-Id.
(III) Budget of a company must be zero.
(A) (I), (II) and (III) are true. (B) (I) false, (II) and (III) are true.
(C) (I) and (II) are true; (III) false. (D) (I), (II) and (III) are false

Q.9 Which of the following is/are true with reference to ‗view‘ in DBMS? [NET Nov. 2017]
(a) A ‗view‘ is a special stored procedure executed when certain event occurs.
(b) A ‗view‘ is a virtual table, which occurs after executing a pre-compiled query.
Code:
(A) Only (a) is true (B) Only (b) is true
(C) Both (a) and (b) are true (D) Neither (a) nor (b) are true

i-GATE, B-713, Street 22, Smriti Nagar, Bhilai- 490020, Contact 98271-62352,96440-14000
[7]
 DBMS GATE-PSUs-NET

ANSWER KEY
1. (D) 2. (D) 3. (D) 4. (A) 5. (B) 6. (A) 7. (D)
8. (C) 9. (B)

SOLUTION
Sol.1 Ans. is D
logical level abstraction means (describes) -What data are stored in the database?
Physical level describes

Sol.3 Answer : Sequential

There are four structural types of database management systems:
Hierarchical databases.
Network databases.
Relational databases.
Object-oriented databases.
A hierarchical database model is a data model in which the data is organized into a tree-like
structure. The data is stored as records which are connected to one another through links. A record
is a collection of fields, with each field containing only one value.
The network model is a database model conceived as a flexible way of representing objects and
their relationships. Its distinguishing feature is that the schema, viewed as a graph in which object
types are nodes and relationship types are arcs, is not restricted to being a hierarchy or lattice.
A relational database is a collection of data items organized as a set of formally-described tables
from which data can be accessed or reassembled in many different ways without having to
reorganize the database tables. The relational database was invented by E. F. Code at IBM in
1970.

Sol.4 Answer: External level Data hiding

We have 3 form of Schema
Physical
Conceptual
External
External Data Level
In the relational model, the external schema also presents data as a set of relations. An external
schema specifies a view of the data in terms of the conceptual level. It is tailored to the needs of a
particular category of users. Portions of stored data should not be seen by some users and begins
to implement a level of security and simplifies the view for these users
Examples:
Students should not see faculty salaries.
Faculty should not see billing or payment data.

Sol.5 Answer: permits many to many relationship

i-GATE, B-713, Street 22, Smriti Nagar, Bhilai- 490020, Contact 98271-62352,96440-14000
[8]
 DBMS GATE-PSUs-NET

The network model is a database model conceived as a flexible way of representing objects and
their relationships. Its distinguishing feature is that the schema, viewed as a graph in which object
types are nodes and relationship types are arcs, is not restricted to being a hierarchy or lattice.

Sol.6 Provides a powerful and flexible security mechanism by hiding parts of the DB from certain users.
The user is not aware of the existence of any attributes that are missing from the view. It permits
users to access data in a way that is customized to their needs, so that the same data can be seen by
different users in different ways, at the same time.
Hence Option (c) External Level data hiding is the correct choice.

Sol.7 Ans. is D
Traditional file system has all mentioned drawbacks. Database applications built by using tables
are used to overcome them
e,g. Normalization and integrity constraints reduces redundancy and inconsistency select * from
Table provide easy access to data
References, joins etc removes data isolation primary and foreign key along with check predicate
solves integrity problems

Sol.8 Integrity means something like 'be right' and consistent. The data in a database must be right and
in good condition.
There are the domain integrity, the entity integrity, the referential integrity and the foreign key
integrity constraints.
Domain integrity means the definition of a valid set of values for an attribute. You define
- data type,
- length or size
- is null value allowed
- is the value unique or not
The entity integrity constraint states that primary keys can't be null. There must be a proper value
in the primary key field.
The referential integrity constraint is specified between two tables and it is used to maintain the
consistency among rows between the two tables.
An instructor Id. No. cannot be null, provided Instructor Id. No. being the primary key. - is valid
No two citizens have same Adhar-Id. - is valid but, the budget of a company must be zero, is not a
valid integrity constraint
So option 3

Sol.9 By definition, VIEW is a virtual table, through which a selective portion of the data from one or
more tables can be seen. A view does not contain data of its own.

i-GATE, B-713, Street 22, Smriti Nagar, Bhilai- 490020, Contact 98271-62352,96440-14000
[9]
 DBMS GATE-PSUs-NET

NORMALIZATION
Q.1 Consider a schema R(A, B, C, D) and functional dependencies A → B and C → D. Then the
decomposition of R into R1(A, B) and R2(C, D) is [NET June 2012]
(A) Dependency preserving but not lossless join
(B) Dependency preserving and lossless join
(C) Lossless join but not dependency preserving
(D) Lossless join

Q.2 Which of the following is true? [NET Dec. 2012]

(A) A relation in BCNF is always in 3NF (B) A relation in 3NF is always in BCNF
(C) BCNF and 3NF are same (D) A relation in BCNF is not in 3NF

Q.3 If a relation with a Schema R is decomposed into two relations R1 and R2 such that (R1 ∪ R2) = R1
then which one of the following is to be satisfied for a lossless joint decomposition (→ indicates
functional independency) [NET Dec. 2012]
(A) (R1 ∩ R2) → R1 or R1 ∩ R2 → R2 (B) R1 ∩ R2 → R1
(C) R1 ∩ R2 → R2 (D) (R1 ∩ R2) → R1 and R1 ∩ R2 → R2

Q.4 The third normal form is based on the concept of________. [NET Dec. 2012]
(A) Closure Dependency (B) Transitive Dependency
(C) Normal Dependency (D) Functional Dependency

Q.5 Which normal form is considered as adequate for usual database design? [NET June 2013]
(A) 2NF (B) 3NF (C) 4NF (D) 5NF

Q.6 Armstrong (1974) proposed systematic approach to derive functional dependencies. Match the
following w.r.t. functional dependencies: [NET Dec. 2013]
List-I List-II
a. Decomposition rule i. If X → Y and Z → W then {X, Z} → {Y, W}
b. Union rule ii. If X → Y and {Y, W} → Z then {X, W} → Z
c. Composition rule iii. If X → Y and X → Z then X → {Y, Z}
d. Pseudo transitivity rule iv. If X → {Y, Z} then X → Y and X → Z
(A) a – iii, b – ii, c – iv, d – i (B) a – i, b – iii, c – iv, d – ii
(C) a – ii, b – i, c – iii, d – iv (D) a – iv, b – iii, c – i, d – ii

Q.7 Which one of the following statements is FALSE? [NET June 2014]
(A) Any relation with two attributes is in BCNF
(B) A relation in which every key has only one attribute is in 2NF
(C) A prime attribute can be transitively dependent on a key in a 3NF relation
(D) A prime attribute can be transitively dependent on a key in a BCNF relation

i-GATE, B-713, Street 22, Smriti Nagar, Bhilai- 490020, Contact 98271-62352,96440-14000
[10]
 DBMS GATE-PSUs-NET

Q.8 Let R = {A, B, C, D, E, F} be a relation schema with the following dependencies C → F, E → A,

EC → D, A → B. Which of the following is a key for R? [NET June 2014]
(A) CD (B) EC (C) AE (D) AC

Q.9 Consider the following relational schemas for a library database: [NET June 2014]
Book (Title, Author, Catalog_no, Publisher, Year, Price) Collection (Title, Author, Catalog_no)
with the following functional dependencies:
I. Title, Author → Catalog_no
II. Catalog_no → Title, Author, Publisher, Year
III. Publisher, Title, Year → Price Assume (Author, Title) is the key for both schemas. Which one
of the following is true?
(A) Both Book and Collection are in BCNF (B) Both Book and Collection are in 3NF
(C) Book is in 2NF and Collection in 3NF (D) Both Book and Collection are in 2NF

Q.10 Let R = ABCDE is a relational scheme with functional dependency set F = {A → B, B → C,

AC → D}. The attribute closures of A and E are [NET Dec. 2014]
(A) ABCD, ϕ (B) ABCD, E (C) Φ, ϕ (D) ABC, E

Q.11 Which of the following is false? [NET Dec. 2014]

(A) Every binary relation is never be in BCNF
(B) Every BCNF relation is in 3NF
(C) 1NF, 2NF, 3NF and BCNF are based on functional dependencies
(D) Multi valued Dependency (MVD) is a special case of Join Dependency (JD)

Q.12 Which one of the following statements about normal forms is FALSE? [NET June 2015]
(A) Lossless, dependency-preserving decomposition into 3NF is always possible
(B) Lossless, dependency-preserving decomposition into BCNF is always possible
(C) Any relation with two attributes is in BCNF
(D) BCNF is stricter than 3NF

Q.13 The Relation [NET June 2015]

Vendor Order (V_no, V_ord_no, V_name, Qty_sup, unit_price) is in 2NF because:
(A) Non_key attribute V_name is dependent on V_no which is part of composite key
(B) Non_key attribute V_name is dependent on Qty_sup
(C) Key attribute Qty_sup is dependent on primary_key unit price
(D) Key attribute V_ord_no is dependent on primary_key unit price

Q.14 The relation schemas R1 and R2 form a Lossless join decomposition of R if and only if
1. R1 ∩ R2 ↠ (R1 − R2) 2. R1 → R2 3. R1 ∩ R2 ↠ (R2 − R1) 4. R2 → R1 ∩ R2
[NET June 2015]
(A) 1 and 2 happens (B) 1 and 4 happens (D) 1 and 3 happens (D) 2 and 3 happens

Q.15 A relation R = {A, B, C, D, E, F, G} is given with following set of functional dependencies:

i-GATE, B-713, Street 22, Smriti Nagar, Bhilai- 490020, Contact 98271-62352,96440-14000
[11]
 DBMS GATE-PSUs-NET

F = {AD → E, BE → F, B → C, AF → G}. Which of the following is a candidate key?

[NET Dec. 2015]
(A) A (B) AB (C) ABC (D) ABD

Q.16 Consider the following database table having A, B, C and D as its four attributes and four possible
candidate keys (I, II, III and IV) for this table: [NET June 2016]
A B C D
a1 b1 c1 d1
a2 b3 c3 d1
a1 b2 c1 d2
I: (B) II: (B, C) III: (A, D) IV: (C, D)
If different symbols stand for different values in the table (e.g. d1 is definitely not equal to d2) then
which of the above could not be the candidate key for the database table?
(A) I and III only (B) III and IV only (C) II only (D) I only

Q.17 Which of the following statements is true? [NET July 2016]

D1: The decomposition of the schema R(A, B, C) into R1(A, B) and R2(A, C) is always lossless
D2: The decomposition of the schema R(A, B, C, D, E) having AD → B, C → DE, B → AE, and
AE → C, into R1(A, B, D) and R2(A, C, D, E) is lossless
(A) Both D1 and D2 (B) Neither D1 nor D2 (C) Only D1 (D) Only D2

Q.18 Consider a schema R(MNPQ) and functional dependencies M→N, P→Q. Then the decomposition
of R into R1(MN) and R2(PQ) is _______ [NET Jan. 2017]
(A) Dependency preserving but not lossless join
(B) Dependency preserving and lossless join
(C) Lossless join but not dependency preserving
(D) Neither dependency preserving nor lossless join

Q.19 Which one is correct w.r.t. RDBMS? [NET Jan. 2017]

(A) primary key ⊆ super key ⊆ candidate key
(B) primary key ⊆ candidate key ⊆ super key
(C) super key ⊆ candidate key ⊆ primary key
(D) super key ⊆ primary key ⊆ candidate key

Q.20 For a database relation R(A, B, C, D) where the domains of A, B, C and D include only atomic
values, only the following functional dependencies and those that can be inferred from them are :
A→C
B→D
The relation R is in _______. [NET Jan. 2017]
(A) First normal form but not in second normal form.
(B) Both in first normal form as well as in second normal form.

i-GATE, B-713, Street 22, Smriti Nagar, Bhilai- 490020, Contact 98271-62352,96440-14000
[12]
 DBMS GATE-PSUs-NET

(C) Second normal form but not in third normal form.

(D) Both in second normal form as well as in third normal form.

Q.21 Let pk(R) denotes primary key of the relation R. A many to one relationship that exists between
two relations R1 and R2 can be expressed as follows: [NET Jan. 2017]
(A) pk(R2) → pk(R1) (B) pk(R1) → pk(R2) (C) pk(R2) → R1 ∩ R2(D) pk(R1) → R1 ∩ R2

Q.22 In RDBMS, different classes of relations are created using_________ technique to prevent
modification anomalies. [NET Nov. 2017]
(A) Functional Dependencies (B) Data integrity
(C) Referential integrity (D) Normal Forms

Q.23 If every non-key attribute is functionally dependent on the primary key, then the relation is
in_________. [NET Nov. 2017]
(A) First normal form (B) Second normal form
(C) Third normal form (D) Fourth normal form

Q.24 Consider a relation R (A, B, C, D, E, F, G, H), where each attribute is atomic, and the following
functional dependencies exist. [NET Nov. 2017]
CH → G
A → BC
B → CFH
E→A
F → EG
The relation R is __________ .
(A) In 1NF but not in 2NF (B) In 2NF but not in 3NF
(C) In 3NF but not in BCNF (D) In BCNF

Q.25 Given two relations R1 (A, B) and R2 (C, D) the result of the following query –
Select distinct A, B [NET Nov. 2017]
From R1, R2
Is guaranteed to be same as R1 provided one of the following condition is satisfied.
(A) R1 has no duplicates and R2 is empty (B) R2 has no duplicates and R1 is empty
(C) Both R1 and R2 have no duplicates (D) R2 has no duplicates and R1 is non empty.

Q.26 Consider a schema R(A, B, C, D) and following functional dependencies.

A→B [NET Nov. 2017]
B→C
C→D
D→B
Then decomposition of R into R1 (A, B), R2(B, C) and R3(B, D) is __________ .
(A) Dependency preserving and lossless join
(B) Lossless join but not dependency preserving

i-GATE, B-713, Street 22, Smriti Nagar, Bhilai- 490020, Contact 98271-62352,96440-14000
[13]
 DBMS GATE-PSUs-NET

(C) Dependency preserving but not lossless join

(D) Not dependency preserving and not lossless join

Q.27 For a database relation R(a, b, c, d), where the domains a, b, c, d include only atomic values, only
the following functional dependencies and those that can be inferred from them hold
a → c, b → d
This relation is [NET July 2018]
(A) First normal form but not in second normal form
(B) Second normal form but not in first normal form
(C) Third normal form
(D) BCNF

ANSWER KEY
1. (C) 2. (A) 3. (A) 4. (B) 5. (B) 6. (D) 7. (D)
8. (B) 9. (C) 10. (B) 11. (A) 12. (D) 13. (A) 14. (C)
15. (D) 16. (C) 17. (D) 18. (A) 19. (B) 20. (A) 21. (C)
22. (D) 23. (B) 24. (A) 25. (B) 26. (A) 27. (A)

SOLUTION
Sol.1 Answer is C.
Here, no common attribute in R1 and R2, therefore lossy join will be there, and both the
dependencies are preserved in composed relations so, dependency preserving.

Sol.2 Ans. (A)

1NF ⊂ 2NF ⊂ 3NF ⊂ BCNF
So, A is always true

Sol.3 A is the ans.

Let R(A, B, C) and B is the key
Let R1 = (A, B) and R2 = (B) So R1 U R2 = R1
Definition of lossless D: says that if the intersection of two relation has a common attribute and
that is a key in any of the relation then it is lossless
now R1 ∩ R2 = B and B --> R1(because B is the key) so lossless and it can also be stated that
R1 ∩ R2 = B. and B-> R2 So lossless
Therefore if we have any one of the above then it is lossless
So A is the ans.

Sol.4 The third normal form (3NF) is a normal form used in database normalization Code's definition
states that a table is in 3NF if and only if both of the following conditions hold:
 The relation R (table) is in seconded normal form (2NF)
 Every non-prime attribute of R is non-transitively dependent on every key of R.
A non-prime attribute of R is an attribute that does not belong to any candidate key of R.
A transitive dependency is a functional dependency in which

i-GATE, B-713, Street 22, Smriti Nagar, Bhilai- 490020, Contact 98271-62352,96440-14000
[14]
 DBMS GATE-PSUs-NET

X → Z (X determines Z) indirectly, by virtue of X → Y and Y → Z (where it is not the case

that Y → X).
Hence, Option (B) Transitive Dependency.

Sol.5 3NF will be adequate for normal relational database design since 3NF tables are free of insertion,
update, and deletion anomalies.

Sol.6 D. a-iv, b-iii, c-i, d-ii

Decomposition rule : If x -> yz then x -> y , x -> z
Union rule : If x -> y , x -> z then x -> yz
Composition rule: if x -> y and z -> w then xz -> yw
Pseudo transitivity rule : If x -> y and yw -> z then xw -> z [y replace by x].
X → Z then

Sol.7 Any relation with two attributes is in BCNF => This is true. It is trivial
A relation in which every key has only one attribute is in 2NF => This is true. As it is not possible
to have Partial Functional Dependency
A prime attribute can be transitively dependent on a key in a 3NF relation => This is true. As
For 3NF to be violated we have something like Key => Non Key, Non Key => Non key 3NF
definition say x -> y, either x should be key or y should be prime attribute. Then we can have
something like Key => Non Key, Non key => Prime Attribute, resulting in Transitive FD on
Prime Attribute, still in 3NF.
LHS must be always key, so No Transitive dependency is allowed. So answer => D

Sol.8 {CD}+ = {CDF}

{EC}+ = {ABCDEF}
{AE}+ = {ABE}
{AC}+ = {ABCF}
Hence, Option (B) EC is the correct choice.

Sol.9 Answer: Book is in 2NF and Collection in 3NF.

Title, Author --> Catalog_no
Catalog_no --> Title, Author, Publisher, Year
Publishe, Title, Year} --> Price
Title, Author --> Catalog_no
Keys: Author, Title
Now, let's see Book Title, Author, Catalog_no, Publisher, Year, Price
[Title, Author]+ --> Title, Author, Catalog_no, Publisher, Year, Price
[Catalog_no]+--> Title, Author, Publisher, Year, Price, Catalog_no
So candidate keys are: Catalog_no, {Title, Author}
This dependencies, {Publisher, Title, Year} --> Price has Transitive Dependency.
Book is in 2NF.
If we consider collection

i-GATE, B-713, Street 22, Smriti Nagar, Bhilai- 490020, Contact 98271-62352,96440-14000
[15]
 DBMS GATE-PSUs-NET

There is no partial dependency. Here it is in 2NF

There is no Transitive dependency. Here it is in 3NF as well as in BCNF.

Sol.10 {A}+ = {A , B , C , D}
{E}+ = {E}
Hence, Option (B) ABCD, E.

Sol.11 Every binary relation (a relation with only 2 attributes) is always in BCNF. Because If both
attributes form the primary key, the relation is in BCNF. If one of the attributes is a primary key,
the other must be determined by it and thus the relation is in BCNF.
Hence, Option (A) Every binary relation is never be in BCNF.

Sol.12 option (D)

It is true . If there are only 2 attributes then relation is always in BCNF.
let R(A B) possible cases are:
(1) {A->B} here A is C and key so BCNF
(2) {B->A} here B is C and key so BCNF
(3) {A->B B->A} here A and B both are C and key so BCNF
(4) no non-trivial FD's here AB is C and key so BCNF

Sol.13 The Relation

Vendor Order (V_no, V_ord_no, V_name, Qty_sup, unit_price) is in 2NF because:
Non_key attribute V_name is dependent on V_no which is part of composite key.
For more information on Normal forms
Option (A) is correct.

Sol.14 Ans. is C
e.g. R1 = (a, b, c, d) R2 = (c, d, e, f)
R1 – R2 = (a, b), R2 – R1 = (e, f)
R1 ∩ R2 = c, d
c, d is common to both relation, now to be lossless c, d must be a super key in at least one of the
relation R1 and R2 acc to option C it is super key in both relation so it is lossless.

Sol.15 Given Relation is R = ABCDEFG

Take options
1. A = A
2. AB = ABC
3. ABC = ABC
4. ABD = ABDEFCG (ABCDEFG)
Hence answer would be (D) ABD will be the candidate keys.

Sol.16 Ans. is C
1:(B)

i-GATE, B-713, Street 22, Smriti Nagar, Bhilai- 490020, Contact 98271-62352,96440-14000
[16]
 DBMS GATE-PSUs-NET

2: (B, C)
3: (A, D)
4: (C, D)
1 is definitely candidate key
2 BC cannot be candidate key because it is Superset of candidate key(B) that why it is super key
3 AD is candidate key it is minimal super key
4 CD is also candidate key it is also minimal super key

Sol.17 Only D2. Since AD is key and it present in both the tables.
Not D1.
Since in D1 FD's not given...
If we take B -> A and C->A then it is lossy since no common attributes contain key from one of
the table.

Sol.18 R(MNPQ) and functional dependencies M → N, P → Q. Then the decomposition of R into

R1(MN) and R2(PQ) here clearly the dependencies are preserved but they are not lossless as both
R1 and R2 cannot be formed back again as they do not have a common attribute which is a key so
answer is A.

Sol.19 Superkey - An attribute or set of attributes that uniquely defined a tuple within a relation.
However, a superkey may contain additional attributes that are not necessary for unique
identification.
Candidate key - A superkey such that no proper subset is a superkey within the relation. So,
basically has two properties: Each candidate key uniquely identifies tuple in the relation; & no
proper subset of the composite key has the uniqueness property.
Primary key - The candidate key chosen to identify tuples uniquely within the relation.
So option B

Sol.20 A relation is in first normal form if every attribute in that relation is single valued attribute. It is in
1NF.
{A, B} are prime attributes and {C, D} are non-prime attribute.
A+ = {A, C}
B+ = {B, D}
{A, B}+ = {A, B, C, D} so AB is the key.
But A+ = {A, C}
B+ = {B, D} makes it partial dependency.
So, this relation is not in 2NF.
So, option (A) is correct.

Sol.21 Ans. will be (B) pk(R1) → pk(R2)

Consider the following case
A many-to-one relationship set exists between entity sets students and course (a relation r with
primary key roll_no)

i-GATE, B-713, Street 22, Smriti Nagar, Bhilai- 490020, Contact 98271-62352,96440-14000
[17]
 DBMS GATE-PSUs-NET

let it is decomposed in 2 relations r1(student with pk roll_no) and r2 (course with pk course name)
Roll_no can uniquely identify course name but course name cannot uniquely identify roll_no
So the functional dependency pk(student) → pk(course) indicates a many-to-one relationship
between r1 and r2

Sol.22 Ans. (D)

Normal forms
Explanation: Functional dependency is a constraint that describes the relationship between
attributes in a relation.
Data integrity refers to the accuracy and consistency of data stored in a database, data warehouse,
data mart or other construct.
Referential integrity is a relational database concept, which states that table relationships must
always be consistent.
Normalization is a process of organizing the data in database to avoid data redundancy, insertion
anomaly, update anomaly & deletion anomaly. 1NF, 2NF, 3NF and BCNF are types of normal
forms.
So, option (D) is correct.

Sol.23 Conditions for various normal forms:

1 NF – A relation R is in first normal form (1NF) if and only if all underlying domains contain
atomic values only.
2 NF – A relation R is in second normal form (2NF) if and only if it is in 1NF and every non-key
attribute is fully dependent on the primary key.
3 NF – A relation R is in third normal form (3NF) if and only if it is in 2NF and every non-key
attribute is non-transitively dependent on the primary key.
BCNF – A relation R is in Boyce-Code normal form (BCNF) if and only if every determinant is a
candidate key.
Example:
Relation R(XYZ) with functional dependencies {X -> Y, Y -> Z, X -> Z}.
This relation is in 2NF but not in 3NF because of every non-key attribute is transitively dependent
on the primary key. Here {X} will be candidate key.
So, option (B) is correct.

Sol.24 Firstly find the candidate keys for given relation R. These are :AD, BD, ED, FD
Now after finding candidate keys, check the relation for BCNF, 3NF and 2NF
For BCNF, every determinant must be super key. But this is not followed by any FD, so relation is
not in BCNF.
For 3NF, if there is X -> Y dependency then Y must be prime attribute, which is satisfied by given
FDs (like CH -> G, G is not prime) , so relation is not in 3NF.
For 2NF, there must not be any partial dependency, but A -> BC is partial dependency, so relation
is not in 2NF.
According to given question, all values are atomic so relation is in 1NF.
Correct option is A.

i-GATE, B-713, Street 22, Smriti Nagar, Bhilai- 490020, Contact 98271-62352,96440-14000
[18]
 DBMS GATE-PSUs-NET

Sol.25 Select A, B
From R1, R2:
In this query first we will take cartesian product of R1, R2 (R2 must be non empty)for this 0- R2
then select distinct A, B from cartesian product of R1, R2 (for A, B being distinct there should not
any duplicate A, B).
And
Select A, B
From R2
For this query A, B → No duplicate A, B.
By combining condition for both query we will get the right condition.
So, option (B) is correct.

Sol.26 The given relation R(A, B, C, D) and FD‘s of R = {A → B, B → C, C → D, D → B}

So, we have the following results from the FD set of R:
A → B, C, D
B → C, D
C → D, B
D → B, C
1. Dependency Preservation :
We say that in any decomposition {R1, R2 ... Rn} of R, Dependency is Preserved when {F1 ∪ F2 ∪
F3.... ∪ Fn} covers F where F is the FD set of R and Fn is the FD set of Rn.
So, here in given question, F1 = {A → B}

Sol.27 Candidate Key is ab

Since all a, b, c, d are atomic so the relation is in 1 NF
Checking the FDs:
a→c (Prime derives Non-Prime)
b→d (Prime derives Non-Prime)
Since, there are partial dependencies it is not in 2NF
(A) Answer 1NF but not 2NF

i-GATE, B-713, Street 22, Smriti Nagar, Bhilai- 490020, Contact 98271-62352,96440-14000
[19]
 DBMS GATE-PSUs-NET

SQL & RELATIONAL ALZEBRA

Q.1 In DML, RECONNCT command cannot be used with [NET Dec. 2012]
(A) OPTIONAL Set (B) FIXED Set (C) MANDATOR Set (D) All of the above

Q.2 Given a Relation POSITION (Posting-No, Skill), then the query to retrieve all distinct pairs of
posting-nos. requiring skill is [NET Dec. 2012]
(A) Select p.posting-No, p.posting-No from position p where p.skill = p.skill and p.posting-No <
p.posting-No
(B) Select p1.posting-No, p2.posting-No from position p1, position p2 where p1.skill = p2.skill
(C) Select p1.posting-No, p2.posting-No from position p1, position p2 where p1.skill = p2.skill and
p1.posting.No < p2.posting-No
(D) Select p1.posting-No, p2.posting-No from position p1, position p2 where p1.skill = p2.skill and
p1.posting.No = p2.posting-No

Q.3 Referential integrity is directly related to [NET Dec. 2012]

(A) Relation key (B) Foreign key (C) Primary key (D) Candidate key

Q.4 If D1, D2,… Dn are domains in a relational model, then the relation is a table, which is a subset of
(A) D1 + D2 + ⋯ + Dn (B) D1 × D2 × ⋯× Dn [NET June 2013]
(C) D1 ∪ D2 ∪⋯ ∪ Dn (D) D1 − D2 −⋯− Dn

Q.5 The ―PROJECT‖ operator of a relational algebra creates a new table that has always
(A) More columns than columns in original table [NET June 2013]
(B) More rows than original table
(C) Same number of rows as the original table
(D) Same number of columns as the original table

Q.6 The employee information of an organization is stored in a relation:

Employee (name, sex, salary, deptname). [NET June 2013]
Consider the following SQL query:
Select deptname from Employee
where sex = ‗M‘0
group by deptname
having avg (salary) > {select avg (salary) from Employee}
Output of the given query corresponds to
(A) Average salary of employee more than average salary of the organization
(B) Average salary of employee less than average salary of the organization
(C) Average salary of employee equal to average salary of the organization
(D) Average salary of male employees in a department is more than average salary of the
organization

i-GATE, B-713, Street 22, Smriti Nagar, Bhilai- 490020, Contact 98271-62352,96440-14000
[20]
 DBMS GATE-PSUs-NET

Q.7 The student marks should not be greater than 100. This is [NET Dec. 2013]
(A) Integrity constraint (B) Referential constraint
(C) Over-defined constraint (D) Feasible constraint

Q.8 Data Integrity control uses_________. [NET Dec. 2013]

(A) Upper and lower limits on numeric data (B) Passwords to prohibit unauthorized access to files
(C) Data dictionary to keep the data (D) Data dictionary to find last access data

Q.9 Consider the following schemas: [NET Dec. 2013]

Branch = (Branch-name, Assets, Branch-city)
Customer = (Customer-name, Bank name, Customer-city)
Borrow = (Branch-name, loan number, customer account-number)
Deposit = (Branch-name, Account-number, Customer-name, Balance)
Using relational Algebra, the Query that finds customers who have balance more than 10,000
is_____
(A) πcustomer−name(σbalance>10000(Deposit) (B) σcustomer−name(σbalance>10000(Deposit)
(C) πcustomer−name(σbalance>10000(Borrow) (D) σcustomer−name(πbalance>10000(Borrow)

Q.10 Find the false statement: [NET Dec. 2013]

(A) The relationship construct known as the weak relationship type was defined by Dey, Storey &
Barron (1999)
(B) A weak relationship occurs when two relationship types are linked by either Event- Precedent
sequence or Condition- precedent sequence.
(C) Conceptual model is not accurate representation of ―Universe of interest‖.
(D) Ternary, Quaternary and Quintary relationships are shown through a series of application
scenario‘s and vignette‘s.

Q.11 Consider the table student (stuid, name, course, marks). Which one of the following two queries is
correct to find the highest marks student in course 5? [NET Dec. 2013]
Q.1. Select S.stuid from student S where not exists (select * from student e where e course = '5'
and e marks  s marks)
Q.2. Select s.stu.id from student S where s.marks > any (select distinct marks from student S
where s.course = 5)
(A) Q.1 (B) Q.2 (C) Both Q.1 and Q.2 (D) Neither Q.1 nor Q.2

Q.12 Match the following: [NET June 2014]

List-I List-II
a. DDL i. LOCK TABLE
b. DML ii. COMMIT
c. TCL iii. Natural Difference
d. BINARY Operation iv. REVOKE
(A) a–ii; b–i; c–iii; d–iv (B) a–i; b–ii; c–iv; d–iii

i-GATE, B-713, Street 22, Smriti Nagar, Bhilai- 490020, Contact 98271-62352,96440-14000
[21]
 DBMS GATE-PSUs-NET

(C) a–ii; b–iii; c–i; d–iv (D) a–iv; b–i; c–ii; d–iii

Q.13 Division operation is ideally suited to handle queries of the type: [NET Dec. 2014]
(A) Customers who have no account in any of the branches in Delhi.
(B) Customers who have an account at all branches in Delhi.
(C) Customers who have an account in atleast one branch in Delhi.
(D) Customers who have only joint account in any one branch in Delhi

Q.14 Which of the following is true? [NET Dec. 2014]

I. Implementation of self-join is possible in SQL with table alias.
II. Outer-join operation is basic operation in relational algebra.
III. Natural join and outer join operations are equivalent.
(A) I and II are correct (B) II and III are correct
(C) Only III is correct. (D) Only I is correct.

Q.15 Drop Table cannot be used to drop a Table referenced by ____ constraint [NET June 2015]
(a) Primary key (b) Sub key (c) Super key (d) Foreign key
(A) a (B) a, b and c (C) d (D) a and d

Q.16 The STUDENT information in a university stored in the relation STUDENT (Name, Sex, Marks,
DEPT_Name). Consider the following SQL Query: [NET June 2015]
SELECT DEPT_Name from STUDENT where SEX = 'M' group by DEPT_Name having
avg(Marks) > SELECT avg(Marks) from STUDENT. It returns the name of the department for
which
(A) The average marks of Male students is more than the average marks of students in the
department
(B) The average marks of Male students is more than the average marks of students in the
university
(C) The average marks of students is more than the average marks of male students in the
university
(D) The average marks of Male students is more than the average marks of male students in the
university

Q.17 Consider the following database table: [NET Dec. 2015]

Create table test(
one integer,
two integer,
primary key(one),
unique(two),
check(one >= 1 and <= 10),
check (two >= 1 and <= 5)
);
How many data records/tuples atmost can this table contain?
(A) 5 (B) 10 (B) 15 (D) 50

i-GATE, B-713, Street 22, Smriti Nagar, Bhilai- 490020, Contact 98271-62352,96440-14000
[22]
 DBMS GATE-PSUs-NET

Q.18 Suppose ORACLE relation R(A, B) currently has tuples {(1, 2), (1, 3), (3, 4)} and relation S(B, C)
currently has {(2, 5), (4, 6), (7, 8)}.Consider the following two SQL queries SQ1 and SQ2:
SQ1: Select * From R Full Join S On R.B = S.B; [NET Dec. 2015]
SQ2: Select * From R Inner Join S On R.B = S.B;
The numbers of tuples in the result of the SQL query SQ1 and the SQL query SQ2 are given by:
(A) 2 and 6 respectively (B) 6 and 2 respectively
(C) 2 and 4 respectively (D) 4 and 2 respectively

Q.19 Consider the following three SQL queries (Assume the data in the people table):
(a) Select Name from people where Age > 21; [NET Dec. 2015]
(b) Select Name from people where Height > 180;
(c) Select Name from people where (Age > 21) or (Height > 180);
If the SQL queries a and b above, return 10 rows and 7 rows in the result set respectively, then
what is one possible number of rows returned by the SQL query c?
(A) 3 (B) 7 (C) 10 (D) 21

Q.20 Consider the following three tables R, S and T. In this question, all the join operations are natural
joins (⋈). (π) is the projection operation of a relation: [NET Dec. 2015]

Possible answer tables for this question are also given as below:

Which is the resulting table of πA, B (R⋈T) ⋈ πB, C (S⋈T)?

(A) (a) (B) (b) (C) (c) (D) (d)

Q.21 Consider a "CUSTOMERS" database table having a column "CITY" filled with all the names of
Indian cities (in capital letters). The SQL statement that finds all cities that have "GAR"
somewhere in its name, is: [NET Dec. 2015]
(A) Select * from customers where city = '%GAR%';
(B) Select * from customers where city = '$GAR$';

i-GATE, B-713, Street 22, Smriti Nagar, Bhilai- 490020, Contact 98271-62352,96440-14000
[23]
 DBMS GATE-PSUs-NET

(C) Select * from customers where city like '%GAR%';

(D) Select * from customers where city as '%GAR';

Q.22 In RDBMS, the constraint that no key attribute (column) may be NULL is referred to as:
(A) Referential integrity (B) Multi-valued dependency [NET July 2016]
(C) Entity integrity (D) Functional dependency

Q.23 Which of the following statement(s) is/are FALSE in the context of Relational DBMS?
I. Views in a database system are important because they help with access control by allowing
users to see only a particular subset of the data in the database
II. E-R diagrams are useful to logically model concepts
III. An update anomaly is when it is not possible to store information unless some other, unrelated
information is stored as well
IV. SQL is a procedural language [NET July 2016]
(A) I and IV only (B) III and IV only (C) I, II and III only (D II, III and IV only

Q.24 In a relational database model, NULL values can be used for all but which one of the following?
(A) To allow duplicate tuples in the table by filling the primary key column(s) with NULL
(B) To avoid confusion with actual legitimate data values like 0 (zero) or integer columns and "
(the empty string) for string columns
(C) To leave columns in a tuple marked as "unknown" when the actual value is unknown
(D) To fill a column in a tuple when that column does not really "exist" for that particular tuple
[NET July 2016]

Q.25 Consider the following two comments C1 and C2 on the relation R from an SQL database:
C1: drop table R; [NET July 2016]
C2: delete from R
Which of the following statement is TRUE?
I. Both C1 and C2 delete the schema R
II. C2 retains relation R, but deletes all tuples in R
III. C1 deletes not only all tuples of R, but also the schema for R
(A) I only (B) I and II only (C) II and III only (D) I, II and III only

Q.26 In distributed databases, location transparency allows for database users, programmers and
administrators to treat the data as if it is at one location, A SQL query with location transparency
needs to specify [NET July 2016]
(A) Inheritances (B) Fragments (C) Locations (D) Local formats
Q.27 Consider the relations R(A, B) and S(B, C) and the following four relational algebra queries over
R and S: [NET July 2016]
I. ΠA, B (R ⨝ S) II. R ⨝ ΠB(S)
III. R ∩ (ΠA(R) × ΠB(S)) IV. ΠA, R. B (R × S) where R⋅B refers to the column B in table R
One can determine that:

i-GATE, B-713, Street 22, Smriti Nagar, Bhilai- 490020, Contact 98271-62352,96440-14000
[24]
 DBMS GATE-PSUs-NET

(A) I, III and IV are the same query (B) II, III and IV are the same query
(C) I, II and IV are the same query (D) I, II and III are the same query

Q.28 Consider the following ORACLE relations: [NET July 2016]

R(A, B, C) = {<1, 2, 3>, <1, 2, 0>, <1, 3, 1>, <6, 2, 3>, <1, 4, 2>, <3, 1, 4>}
S(B, C, D) = {<2, 3, 7>, <1, 4, 5>, <1, 2, 3>, <2, 3, 4>, <3, 1, 4>}
Consider the following two SQL queries SQ1 and SQ2:
SQ1; SELECT R.B, AVG(S.B)
FROM R, S
WHERE R.A = S.C AND S.D < 7
GROUP BY R.B
SQ2: SELECT DISTINCT S.B, MIN(S.C)
FROM S
GROUP BY S.B
HAVING COUNT (DISTINCT S.D) > 1;
If M is the number of tuples returned by SQ1 and If N is the number of tuples returned by SQ2
then
(A) M = 4, N = 2 (B) M = 5, N = 3 (C) M = 2, N = 2 (D) M = 3, N = 3

Q.29 Consider the following relation: [NET Jan. 2017]

Works(emp_name, company_name, salary)
Here, emp_name is primary key.
Consider the following SQL query:
Select emp_name
From works T
where salary > (select avg (salary)
from works S
where T.company_name = S.company_name)
The above query is for following:
(A) Find the highest paid employee who earns more than the average salary of all employees of
his company
(B) Find the highest paid employee who earns more than the average salary of all employees of all
the companies
(C) Find all employees who earn more than the average salary of all employees of all the
companies
(D) Find all employees who earn more than the average salary of all employees of their company

Q.30 In SQL,_______ is an Aggregate function. [NET Nov. 2017]

(A) SELECT (B) CREATE (C) AVG (D) MODIFY

Q.31 ________ SQL command changes one or more fields in a record. [NET Nov. 2017]
(A) LOOK-UP (B) INSERT (C) MODIFY (D) CHANGE

i-GATE, B-713, Street 22, Smriti Nagar, Bhilai- 490020, Contact 98271-62352,96440-14000
[25]
 DBMS GATE-PSUs-NET

Q.32 In RDBMS, which type of Join returns all rows that satisfy the join condition?
(A) Inner Join (B) Outer Join (C) Semi Join (D) Anti Join
[NET July 2018]

Q.33 The relation book (title, price) which contains the titles and prices of different books. Assuming
that no two books have the same price, what does the following SQL query list?
select title [NET July 2018]
from book as B
where (select count(*)
from book as T
where T.price > B.price) < 5
(A) Titles of the four most expensive books
(B) Title of the fifth most inexpensive book
(C) Title of the fifth most expensive bookTitles of the five most expensive books
(D) Titles of the five most expensive books

ANSWER KEY
1. (B) 2. (C) 3. (B) 4. (B) 5. (C) 6. (D) 7. (A)
8. (D) 9. (A) 10. (B) 11. (D) 12. (D) 13. (B) 14. (D)
15. (C) 16. (B) 17. (C) 18. (D) 19. (C) 20. (D) 21. (C)
22. (C) 23. (B) 24. (A) 25. (C) 26. (B) 27. (D) 28. (A)
29. (D) 30. (C) 31. (C) 32. (B) 33. (C)

SOLUTION
Sol.1 FIXED Set

Sol.3 Referential integrity is a database concept that ensures that relationships between tables remain
consistent. When one table has a foreign key to another table, the concept of referential integrity
states that you may not add a record to the table that contains the foreign key unless there is a
corresponding record in the linked table. It also includes the techniques known as cascading
update and cascading delete, which ensure that changes made to the linked table are reflected in
the primary table.
Hence, Option (B) Foreign key.

Sol.4 Ans. is B
Mathematical Relations
Given sets D1, D2, …, Dn, not necessarily distinct.
The Cartesian product D1 x D2 x…x Dn is the set of all (ordered) n-tuples such that d1∈D1, d2 ∈
D2, …, dn ∈ Dn
A mathematical relation on D1, D2, …, Dn is a subset of the Cartesian product D1 x D2 x…x Dn. ƒ
D1, D2, …, Dn are the domains of the relation. n is the degree of the relation.
The number of n-tuples in a given relation is the cardinality of that relation; the cardinality of
a relation is always finite.

i-GATE, B-713, Street 22, Smriti Nagar, Bhilai- 490020, Contact 98271-62352,96440-14000
[26]
 DBMS GATE-PSUs-NET

Sol.5 The Projection operator is also a unary operator. Whereas the selection operator chooses a subset
of the rows of the relation, the projection operator chooses a subset of the columns. The Projection
operation on a table, simply forms another table by copying specified columns, from the original
table. Symbol of projection is π. Given a employee table having the columns(Emp-id, name,
salary).
To select only the name of employee:- πname(employee)
To know only the salary :- πsalary(employee)
Selection operation:
It yields a horizontal subset of a given relation that is the subset of row should be selected with in
the given relation for which a particular condition is satisfied. Sign of selection is σ. To see the
details of those employees whose salary is greater than 10000, the selection operation will be
used.
σsalary>10000(employee).
So, looking at the options given for the answer, the PROJECT operator cannot create a table
having more columns than the original table. Same number of columns also ruled out. More rows
than the original table is also not correct. So, it will be same number of rows as the original table,
but less number of columns than the original table. So, the correct answer is C.

Sol.6 Answer : D
Select deptname it says we are selecting Department. from Employee
Both above put together says we are selecting Dept name just by considering employee Table
where sex = ‗M‘
It says we are selecting Male Employee.
group by dept name having avg (salary) it says we are grouping all the male employee in a
Department whose avg salary is something > {select avg (salary) from Employee}
This Last Comparison says we have selected something which is greater then the right side of
comparison Operator
So what we have selected is Average salary of male employees in a department is more than
average salary of the organization

Sol.7 Integrity constraint is meant for "integrity" of data and mark <= 100 is part of it. By English
meaning D option can be right but in Database, is there something like "Feasible Constraint"?
Integrity Constraint is not meant to avoid data loss.

Sol.8 Ans. should be B

(A) is defined by integrity constraints
(C) and (D) is not related to data integrity control

Sol.9 πcustomer-name(σblance >10000(Deposit))

we have to apply projection and use table Deposit.
A is ans.

i-GATE, B-713, Street 22, Smriti Nagar, Bhilai- 490020, Contact 98271-62352,96440-14000
[27]
 DBMS GATE-PSUs-NET

Sol.11 Q.1. Select S.stuid from student S where not exist (select * from student e where e course = '5' and
e marks ≥ s marks) = false
Select S.stuid from student S where not exist (select * from student e where e course = '5' and e
marks > s marks) = correct
Q.2. select S.stuid From student S where s.marks > any (select distinct marks from student S
where s.course = 5) = false
select S.stuid From student S where s.marks > All (select distinct marks from student S where
s.course = 5) = correct
Ans. is D

Sol.13 Option (B) Customers who have an account at all branch in Delhi.
What division does :-
Division identify the attribute values from relation that are found to be paired with all of the
values from the other relation.
Here (B) is suitable option for this.

Sol.14 Ans. is D only 1 is correct self join is implemented in a single table by alias names
rest 2 are incorrect

Sol.15 Foreign key should be answer because this key is used only to create the referential integrity
constraint so we cannot drop the table.

Sol.16 The average marks of Male students is more than the average marks of students in the university
B is ans.

Sol.17 Check (one >= 1 and <= 10), check (two >= 1 and <= 5).
Here second constraint will decide the no of tuples (record). Or we can say that the common
condition will dominate.
i.e. check(two >= 1 and <= 5) 5 tuples.
So, option (A) is correct.

Sol.18 Inner join gives the record of two tables based on = condition
here R.B = S.B holds for 2 records when B = 2 and B = 4 hence its result w hence 2
for SQ2 Full Join or full outer join gives the result of left outer join(all rows of left table whether
there is match or not) + right outer join (all rows of right table whether there is match or not with
the left) now both table has 3 records but there are 2 match and 2 mismatch
hence SQ1 will give 4 records
So ans. is choice D

Sol.19 When set a and set b all rows are distinct ans. would be = 10 + 7 = 17
When set b is subset of set a than
10 + 7 – 7 = 10
Only these two options are preferable.

i-GATE, B-713, Street 22, Smriti Nagar, Bhilai- 490020, Contact 98271-62352,96440-14000
[28]
 DBMS GATE-PSUs-NET

Sol.20 (A) option is option return all possible results after natural join but it does not involve the table t
during natural join so false
In (B) option record 5 6 4 and record 1 2 2 not possible in result so false
In (C) option record 5 2 4 and record 1 6 2 not possible after natural join of table.
In (D) option it contain partial result after joining all three table So D option should be answer

Sol.22 Question says no key attribute may be null this property is applied in case of primary key which
shows the property of entity integrity so C option should be answer

Sol.23 Ans. should be D

II, III and IV are false (update anomaly is concerned with related information and SQL is not
procedure oriented PL/SQL is)

Sol.24 Ans. will be A

Null values cannot be used in primary key (Entity constraint)

Sol.25 Option C answer

Drop command remove all tuples of the relation as well as schema also
Delete command in SQL removes tuples from the relation but retain the schema of table in
database.

Sol.26 Answer B
In SQL query with location transparency the end user must specify the database fragment name
but does not need to specify where those fragments are located.
Fragmentation transparency is the highest level of transparency. The end user or programmer does
not need to know that a database is partitioned. Therefore, neither fragment names nor fragment
locations are specified prior to data access.
Local mapping transparency exists when the end user or programmer must specify both the
fragment names and their locations.

Sol.27 Let us take an example as R = {(10, 1), (20, 2)} and S = {(2, 30), (3, 40)}
I) R⟗S = {(20, 2, 30)}. So πA, B R⟗S = {(20, 2)}
II) πB (S) = {(2), (3)}. So R⟗πB (S) = {(20, 2)}
III) πA (R) X πB (S) = {10, 20} X {2, 3} = {(10, 2), (10, 3),(20, 2), (20, 3)}
R ∩ πA (R) X πB (S) = {(20, 2)}
IV) R X S = {(10, 1, 2, 30), (10, 1, 3, 40), (20, 2, 2, 30), (20, 2, 3, 40)}
πA, R. B R X S = {(10, 2), (10, 3), (20, 2), (20, 3)}

Sol.28 ANS : M = 4 , N = 2
output after R x S in SQ1
R.A R.B R.C S.B S.C S.D
1 2 3 3 1 4
1 2 0 3 1 4

i-GATE, B-713, Street 22, Smriti Nagar, Bhilai- 490020, Contact 98271-62352,96440-14000
[29]
 DBMS GATE-PSUs-NET

1 3 1 3 1 4
1 4 2 3 1 4
3 1 4 2 3 7
3 1 4 2 3 4
final output of SQ1 :
R.B AVG(S.B)
2 3
3 3
4 3
1 2
SQ2 output:
S.B MIN(S.C)
1 2
2 3

Sol.29 Option (D)

It does not select the highest paid employee, as MAX is not used. It just selects employee names
who ears more than the avg salary of all employee of their company only.
T.company_name = S. Company_name. So employee from all companies will not be considered.

Sol.30 An aggregate function allows yj3ou to perform a calculation on a set of values to return a single
scalar value. AVG, COUNT, MIN, MAX, SUM are aggregate functions.
In SQL SELECT is used to choose a column from a database table.
CREATE is used to create a DB table. AVG is a aggregate function. MODIFY is used to modify
DB table content. So, option (C) is correct.

Sol.31 Option C: modify is the answer.

Sol.32 Outer Join returns all rows that satisfy condition from both the participating relations. An outer
join extends the result of a simple join. An outer join returns all rows that satisfy the join
condition and also returns some or all of those rows from one table for which no rows from the
other satisfy the join condition.

Sol.33 Answer: D
The outer query selects all titles from book table. For every selected book, the sub query returns
count of those books which are more expensive than the selected book. The where clause of outer
query will be true for 5 most expensive book. For example count (*) will be 0 for the most
expensive book and count(*) will be 1 for second most expensive book.

i-GATE, B-713, Street 22, Smriti Nagar, Bhilai- 490020, Contact 98271-62352,96440-14000
[30]
 DBMS GATE-PSUs-NET

ENTITY RELATIONSHIP DIAGRAM

Q.1 An E-R model includes [NET Dec. 2013]
(I) An ER diagram portraying entity types.
(II) Attributes for each entity type.
(III) Relationships among entity types.
(IV) Semantic integrity constrains that reflects the business rules about data not captured in the ER
diagram
(A) I, II, III and IV (B) I and IV (C) I, II and IV (D) I and III

Q.2 Consider the following ER diagram: [NET Dec. 2013]

The minimum number of tables required to represent M, N, P, R1, R2 is

(A) 2 (B) 3 (C) 4 (D) 5

Q.3 Specialization Lattice stands for [NET June 2014]

(A) An entity type can participate as a subclass in only one specialization
(B) An entity type can participate as a subclass in more than one specialization
(C) An entity type that can participate in one specialization
(D) An entity type that can participate in one generalization

Q.4 What kind of mechanism is to be taken into account for converting a weak entity set into strong
entity set in entity-relationship diagram [NET Dec. 2014]
(A) Generalization (B) Aggregation (C) Specialization (D) Adding suitable attributes

Q.5 For a weak entity set to be meaningful, it must be associated with another entity set in
combination with some of their attribute values, is called as: [NET June 2014]
(A) Neighbour Set (B) Strong Entity Set (C) Owner Entity Set (D) Weak Set

Q.6 Which of the following statements is false about weak entity set? [NET June 2015]
(A) Weak entities can be deleted automatically when their strong entity is deleted
(B) Weak entity set avoids the data duplication and consequent possible inconsistencies caused by
duplicating the key of the string entity
(C) A weak entity set has no primary keys unless attributes of the strong entity set on which it
depends are included
(D) Tuples in a weak entity set are not partitioned according to their relationship with tuples in a
strong entity set

Q.7 Which of the following provides the best description of an entity type? [NET Dec. 2015]
(A) A specific concrete object with a defined set of processes (e.g. Jatin with diabetes)
(B) A value given to a particular attribute (e.g. height - 230 cm)

i-GATE, B-713, Street 22, Smriti Nagar, Bhilai- 490020, Contact 98271-62352,96440-14000
[31]
 DBMS GATE-PSUs-NET

(C) A thing that we wish to collect data about zero or more, possibly real world examples of it
may exist
(D) A template for a group of things with the same set of characteristics that may exist in the real
world

Q.8 Let M and N be two entities in a E-R diagram with simple single value attributes. R1 and R2
are two relationship between M and N, where as R1 is one-to-many and R2 is many-to-many.
The minimum number of tables required to represent M, N, R1 and R2 in the relational model
are_______. [NET Jan. 2017]
(A) 4 (B) 6 (C) 7 (D) 3

Q.9 Relations produced from E-R Model will always be in ________. [NET July 2018]
(A) 1 NF (B) 2 NF (C) 3 NF (D) 4 NF

Q.10 A many-to-one relationship exists between entity sets r1 and r2. How will it be represented using
functional dependencies if Pk(r) denotes the primary key attribute of relation r?
(A) Pk(r1) → Pk(r2) (B) Pk(r2) → Pk(r1) [NET July 2018]
(C) Pk(r2) → Pk(r1) and Pk(r1) → Pk(r2) (D) Pk(r2) → Pk(r1) or Pk(r1) → Pk(r2)

Q.11 Let R1 (a, b, c) and R2 (x, y, z) be two relations in which a is the foreign key of R1 that refers to
the primary key of R2. Consider following four options. [NET July 2018]
(a) Insert into R1 (b) Insert into R2 (c) Delete from R1 (d) Delete from R2
Which of the following is correct about the referential integrity constraint with respect to above?
(A) Operations (a) and (b) will cause violation.(B) Operations (b) and (c) will cause violation.
(C) Operations (c) and (d) will cause violation.(D) Operations (d) and (a) will cause violation.

ANSWER KEY
1. (A) 2. (B) 3. (B) 4. (B) 5. (C) 6. (D) 7. (D)
8. (D) 9. (C) 10. (A) 11. (D)

SOLUTION
Sol.1 Ans. is A E-R Model Includes all four

Sol.2 Answer is B, i.e. 3 minimum tables.

M, P are strong entities hence they must be represented by separate tables.
Many-to-one and one-to-many relationship sets that are total on the many-side can be represented
by adding an extra attribute to the ―many‖ side, containing the primary key of the ―one‖ side.
(This way no extra table will be needed for Relationship sets)
M table is modified to include primary key of P side (i.e. P1). N is weak entity, and is modified to
include primary key of P (i.e. P1). Therefore there would be Minimum of 3 tables with schema
given below:
M (M1, M2, M3, P1)
P (P1, P2)

i-GATE, B-713, Street 22, Smriti Nagar, Bhilai- 490020, Contact 98271-62352,96440-14000
[32]
 DBMS GATE-PSUs-NET

N (P1, N1, N2)

Sol.3 Answer: An entity type can participate as a subclass in more than one specialization.

Sol.4 We can convert weak entity set to strong entity set by adding primary keys of strong entity to the
weak entity. This approach causes redundancy storing the primary keys more than once.
Existence of weak entity set depends on Existence of strong entity set, Hence if strong entity set is
deleted, weak entity set is also get deleted. Thus if database contains a entity set that depends on
another entity set, then it is necessary to mark such as weak entity set.
Hence, Option (D) adding suitable attribute.

Sol.5 Every weak entity must be associated with an identifying entity; that is, the weak entity set is said
to be existence dependent on the identifying entity set. The identifying entity set is said to own the
weak entity set that it identifies. It is also called as owner entity set.

Sol.6 We have weak entities for several reasons:

 We want to avoid the data duplication and consequent possible inconsistencies caused by
duplicating the key of the strong entity.
 Weak entities react the logical structure of an entity being dependent on another entity.
 Weak entities can be deleted automatically when their strong entity is deleted.
 Weak entities can be stored physically with their strong entities.
D is incorrect statement. So the choice will be D.

Sol.7 It is D
It is collection of entity having common attribute. As in Student table each row is an entity and
have common attributes.
So STUDENT is an entity type which contains entities having attributes id, name and Age.
Also each entity type in a database is described by a name and a list of attribute. So we may say a
table is an entity type
Each template contains the following information:
 A unique name. (Required.)
 An entity key defined by one or more properties. (Required.)
 Data in the form of properties. (Optional.)
 Navigation properties that allow for navigation from one end of an association to the other end.
(Optional)

Sol.8 Ans. is option D i.e. 3 relations

Two tables are created for entities M and N and third table is created for relationships R2 (many to
many) for R1 no need of separate table (one to many)
 1-m relationships
The primary key from the `one side' is placed as a foreign key in the `many side'.
 m-n relationships

i-GATE, B-713, Street 22, Smriti Nagar, Bhilai- 490020, Contact 98271-62352,96440-14000
[33]
 DBMS GATE-PSUs-NET

A new relation is created with the primary keys from each entity forming a composite key.
 1-1 relationships
Depending on the optionality of the relationship, the entities are either combined or the
primary key of one entity type is placed as a foreign key in the other relation.

Sol.10 A many to one relationship set exists between entity sets Employee and Department.
Let two relations R1(employee with pk empId)
R2(Department with pk DId)
Here, empId can uniquely identify DId but DId cannot uniquely identify the empId.
Hence, pk(R1) -> pk(R2)

Sol.11 Let x is the primary key in R2(x, y, z)

Insert into R1 – Can cause violation because if we want to insert any value into a of R1, which is
not in x of R2.
Insert into R2 – Cannot cause violation
Delete from R1 – Cannot cause violation.
Delete from R2 – Can cause violation if we delete any value of x in R2, then the value referred
by a in R1 should also be deleted.
Hence, option (D) is correct.

i-GATE, B-713, Street 22, Smriti Nagar, Bhilai- 490020, Contact 98271-62352,96440-14000
[34]
 DBMS GATE-PSUs-NET

FILE STRUCTURE & INDEXING

Q.1 GO BOTTOM and SKIP-3 commands are given one after another in a database file of 30 records.
It shifts the control to [NET Dec. 2013]
th th rd th
(A) 28 record (B) 27 record (C) 3 record (D) 4 record

Q.2 A clustering index is created when _______. [NET June 2014]

(A) Primary key is declared and ordered (B) No key ordered
(C) Foreign key ordered (D) There is no key and no order

Q.3 A data which improves the performance and accessibility of the database are called:
(A) Indexes (B) User Data [NET Dec. 2015]
(C) Application Metadata (D) Data Dictionary

Q.4 The order of a leaf node in a B+ tree is the maximum number of children it can have. Suppose that
block size is 1kilobytes, the child pointer takes 7 bytes long and search field value takes 14 bytes
long. The order of the leaf node is ________. [NET Jan. 2017]
(A) 16 (B) 63 (C) 64 (D) 65

Q.5 In a Hierarchical database, a hashing function is used to locate the ________. [NET July 2018]
(A) Collision (B) Root (C) Foreign Key (D) Records

Q.6 Database system that is store each relation in a separate operating system file may use the
operating systems, authorization scheme, instead of defining a special scheme themselves.
In this case which of the following is false [NET July 2018]
(A) The administrator enjoy more control on the grant option
(B) It is difficult to differentiate among the update, delete and insert authorizations
(C) Cannot store more than one relation in a file
(D) Operation on the database are speeded up as the authorization procedure is carried out at the
operating system level

ANSWER KEY
1. (A) 2. (C) 3. (A) 4. (*) 5. (B) 6. (A)

SOLUTION
Sol.1 Go bottom will take u to the last record (i.e. 30th record) now skip 1 will take u to 29th skip 2 to
28th and skip 3 to 27th record hence ans. is B

Sol.2 A clustering index = (non key attribute + ordered)

so C is the answer

Sol.3 Answer A

i-GATE, B-713, Street 22, Smriti Nagar, Bhilai- 490020, Contact 98271-62352,96440-14000
[35]
 DBMS GATE-PSUs-NET

Indexes are special lookup tables that the database search engine can use to speed up data
retrieval. Simply put, an index is a pointer to data in a table. An index in a database is very similar
to an index in the back of a book.

Sol.4 Key size = 14 bytes (given)

Child pointer = 7 bytes (given)
We assume the order of B+ tree to be ‗n‘.
Block size >= (n – 1) * key size + n * child pointer
512 >= (n – 1) * 14 + n * 7
512 >= 14 * n – 14 + 7 * n
n <= (1024 + 14) / 20
n <= 1038 / 21
n <= 49.42
So, option (A) is correct.

i-GATE, B-713, Street 22, Smriti Nagar, Bhilai- 490020, Contact 98271-62352,96440-14000
[36]
 DBMS GATE-PSUs-NET

MISSCELLANEOUS
Q.1 Match the following: [NET Dec. 2013]
List-I List-II
a. Secondary Index i. Functional Dependency
b. Non-procedural Query language ii. B-Tree
c. Closure of set of attributes iii. Relational Algebraic Operation
d. Natural JOIN iv. Domain Calculus
(A) a-i, b-ii, c-iv, d-iii (B) a-ii, b-i, c-iv, d-iii
(C) a-i, b-iii, c-iv, d-ii (D) a-ii, b-iv, c-i, d-iii

Q.2 Location transparency allows: [NET Dec. 2014]

I. Users to treat the data as if it is done at one location.
II. Programmers to treat the data as if it is at one location.
III. Managers to treat the data as if it is at one location.
Which one of the following is correct?
(A) I, II and III (B) I and II only (C) II and III only (D) II only

Q.3 Consider the following statements: [NET Dec. 2014]

I. Re-construction operation used in mixed fragmentation satisfies commutative rule.
II. Re-construction operation used in vertical fragmentation satisfies commutative rule
Which of the following is correct?
(A) I (B) II
(C) Both are correct (D) None of the statements are correct

Q.4 Match the following database terms to their functions: [NET Dec. 2015]
List - I List – II
a. Normalization i. Enforces match of primary key to foreign key
b. Data Dictionary ii. Reduces data redundancy in a database
c. Referential Integrity iii. Defines view(s) of the database for particular user(s)
d. External Schema iv. Contains metadata describing database structure
(A) a-iv, b-iii, c-i, d-ii (B) a-ii, b-iv, c-i, d-iii
(C) a-ii, b-iv, c-iii, d-i (D) a-iv, b-iii, c-ii, d-i

Q.5 Semi-join strategies are techniques for query processing in distributed database system.
Which of the following is a semi-join technique? [NET June 2016]
(A) Only the joining attributes are sent from one site to another and then all of the rows are
returned.
(B) All of the attributes are sent from one site to another and then only the required rows are
returned.

i-GATE, B-713, Street 22, Smriti Nagar, Bhilai- 490020, Contact 98271-62352,96440-14000
[37]
 DBMS GATE-PSUs-NET

(C) Only the joining attributes are sent from one site to another and then only the required rows
are returned.
(D) All of the attributes are sent from one site to another and then only the required rows are
returned.

Q.6 An attribute A of datatype varchar (20) has value ‗Ram‘ and the attribute B of datatype char (20)
has value ‗Sita‘ in oracle. The attribute A has _______ memory spaces and B has _______
memory spaces. [NET Jan. 2017]
(A) 20, 20 (B) 3, 20 (C) 3, 4 (D) 20, 4

Q.7 Match the following with respect to RDBMS: [NET Nov. 2017]
a) Entity integrity (i) Enforces some specific business rule that do not fall into entity or
domain
b) Domain integrity (ii) Rows can‘t be deleted which are used by other records
c) Referential integrity (iii) Enforces valid entries for a column
d) User defined integrity (iv) No duplicate rows in a table
Code:
(A) a–iii, b–iv, c–i, d–ii (B) a–iv, b–iii, c–ii, d–i
(C) a–iv, b–ii, c–iii, d–i (D) a–ii, b–iii, c–iv, d–i

ANSWER KEY
1. (D) 2. (A) 3. (C) 4. (B) 5. (C) 6. (B) 7. (B)

SOLUTION
Sol.1 It is easy to observe that
B-tree has secondary index
Natural join is Relational Algebraic Operation
Closure of set of attributes is related to Functional Dependency
Non-procedural Query language is related to Domain Calculus
Hence ans. is D
Primary index:
A primary index is an index on a set of fields that includes the unique primary key for the field
and is guaranteed not to contain duplicates. E.g. Employee ID can be Example of it.
Secondary index:
A Secondary index is an index that is not a primary index and may have duplicates. eg. Employee
name can be example of it. Because Employee name can have similar values.

Sol.2 In distributed databases, Location transparency allows:

I. Users to treat the data as if it is done at one location.
II. Programmers to treat the data as if it is at one location.
III. Managers to treat the data as if it is at one location.
All statement are correct.
So, option (A) is correct.

i-GATE, B-713, Street 22, Smriti Nagar, Bhilai- 490020, Contact 98271-62352,96440-14000
[38]
 DBMS GATE-PSUs-NET

Sol.3 D
All reconstructions need two operations
* Join
* Union
because the operations above are commutative, the reconstructions are commutative too.

Sol.4 Normalization - Reduces data redundancy in a database

Data Dictionary - Contains metadata describing database structure
Referential Integrity - Enforces match of primary key to foreign key
External Schema - Defines view(s) of the database for particular user(s)

Sol.5 Semi-join strategies are techniques for query processing in distributed database system. In which
only the joining attributes are sent from one site to another and then only the required rows are
returned.
So, option (C) is correct.

Sol.6 varchar will acquire the exact memory of attribute and it varies from tuple to tuple while char will
acquire memory space which is define at the time of table creation it is fixed: varchar(20) ‗Ram‘
will take 3 and ‗Sita‘ will take 20 character space in memory.
So, option (B) is correct.

Sol.7 Entity integrity is used to provide primary key mechanism hence there should be no duplicate
rows in table. (a-iv)
Domain integrity specifies that all columns in a relational database must be declared upon a
defined domain .(b-iii)
Referential integrity means we cannot delete records in master table before deleting the records
from the child table. (c-ii)
Answer should be option B.

i-GATE, B-713, Street 22, Smriti Nagar, Bhilai- 490020, Contact 98271-62352,96440-14000
[39]
 DBMS GATE-PSUs-NET

GATE Previous Year’s Questions

DEPENDENCIES AND NORMALIZATION
Q.1 State True or False with reason [GATE 1994]
There is always a decomposition into Boyce-Code normal form (BCNF) that is lossless and
dependency preserving.

Q.2 (a) Consider the relation scheme R(A, B, C) with the following functional dependencies:
A, B → C
C→A
Show that the scheme R is in 3NF but not in Beyce-Code BCNF
(b) Determine the minimal keys of relation R [GATE 1995]

Q.3 Let R(a, b, c) and S(d, e, f) be two relations in which d is the foreign key of S that refers to the
primary key of R. Consider the following four operations R and S [GATE 1997]
I. Insert into R II. Insert into S III. Delete from R IV. Delete from S
Which of the following can cause violation of the referential integrity constraint above?
(A) Both I and IV (B) Both II and III (C) All of these (D) None of these

Q.4 Which normal form is considered as adequate for normal usual relational database design?
(A) 2NF (B) 3NF (C) 4NF (D) 5NF
[GATE 1997]

Q.5 There are five records in a database. [GATE 1998]

Name Age Occupation Category
Rama 27 CON A
Abdul 22 ENG A
Jennifer 28 DOC B
Maya 32 SER D
Dev 24 MUS C

There is an index file associated with this and it contains the values 1, 3, 2, 5 and 4. Which one of
the fields is the index built from?
(A) Age (B) Name (C) Occupation (D) Category

Q.6 Consider the following database relations containing the attributes [GATE 1998]
 Book_id
 Subject_Category_of_book
 Name_of_Author
 Nationality_of_Author
With Book_id as the primary key.

i-GATE, B-713, Street 22, Smriti Nagar, Bhilai- 490020, Contact 98271-62352,96440-14000
[40]
 DBMS GATE-PSUs-NET

(a) What is the highest normal form satisfied by this relation?

(b) Suppose the attributes Book_title and Author_address are added to the relation, and the
primary key is changed to {Name_of_Author, Book_title}, what will be the highest normal
form satisfied by the relation?

Q.7 Let R = (A, B, C, D, E, F) be a relation schema with the following dependencies C  F, E  A,

EC  D, A  B. which of the following is a key for R? [GATE 1999]
(A) CD (B) EC (C) AE (D) AC

Q.8 Consider the schema R = (S, T, U, V) and the dependencies S → T, T → U, U → V and V → S.

Let R = (R1 and R2) be a decomposition such that R1 ∩ R2 ≠ ϕ. The decomposition is
(A) Not in 2NF (B) In 2NF but not 3NF [GATE 1999]
(C) In 3NF but not in 2NF (D) In both 2NF and 3NF

Q.9 Given the following relation instance. [GATE 2010]

X Y Z
1 4 2
1 5 3
1 6 3
3 2 2
Which of the following functional dependencies are satisfied by the instance?
(A) XY→Z and Z→Y (B) YZ→X and Y→Z
(C) YZ→X and X→Z (D) XZ→Y and Y→X

Q.10 Consider a schema R(A, B, C, D) and functional dependencies A → B and C → D. Then the
decomposition of R into R1(A, B) and R2(C, D) is [GATE 2001]
(A) Dependency preserving and lossless join
(B) Lossless join but not dependency preserving
(C) Dependency preserving but not lossless join
(D) Not dependency preserving and not lossless join

Q.11 R(A, B, C, D) is a relation. Which of the following does not have a lossless join, dependency
preserving BCNF decomposition? [GATE 2001]
(A) A → B, B → CD (B) A → B, B → C, C → D
(C) AB → C, C → AD (D) A → BCD

Q.12 Relation R with an associated set of functional dependencies, F is decomposed into BCNF. The
redundancy (arising out of functional dependencies) in the resulting set relations is.
(A) Zero [GATE 2002]
(B) More than zero but less than that of an equivalent 3NF decomposition
(C) Proportional to the size of F+
(D) Indeterminate

i-GATE, B-713, Street 22, Smriti Nagar, Bhilai- 490020, Contact 98271-62352,96440-14000
[41]
 DBMS GATE-PSUs-NET

Q.13 Relation R is decomposed using a set of functional dependencies, F and relation S is decomposed
using another set of functional dependencies G. One decomposition is definitely BCNF, the other
is definitely 3NF, but it is not known which is which. To make a guaranteed identification, which
one of the following tests should be used on the decompositions? (Assume that the closures of F
and G are available). [GATE 2002]
(A) Dependency-preservation (B) Lossless-join
(C) BCNF definition (D) 3NF definition

Q.14 From the following instance of a relation scheme R (A, B, C), we can conclude that:

A B C
1 1 1
1 1 0
2 3 2
2 3 2

(A) A functionally determines B and B functionally determines C [GATE 2002]

(B) A functionally determines B and B does not functionally determine C
(C) B does not functionally determine C
(D) A does not functionally determine B and B does not functionally determine C

Q.15 Consider the following functional dependencies in a database: [GATE 2003]

Data_of_Birth → Age
Age → Eligibility
Name → Roll_number
Roll_number → Name
Course_number → Course_name
Course_number → Instructor
(Roll_number, Course_number) → Grade
The relation (Roll_number, Name, Date_of_birth, Age) is:
(A) In second normal form but not in third normal form
(B) In third normal form but not in BCNF
(C) In BCNF
(D) None of the above

Q.16 Consider the following relation schema pertaining to a student database:

Student (rollno, name, address) [GATE 2004]
Enroll (rollno, courseno, coursename)
where the primary keys are shown underlined. The number of tuples in the Student and Enroll
tables are 120 and 8 respectively. What are the maximum and minimum number of tuples that can
be present in (Student * Enroll), where ‗*‘ denotes natural join?
(A) 8, 8 (B) 120, 8 (C) 960, 8 (D) 960, 120

i-GATE, B-713, Street 22, Smriti Nagar, Bhilai- 490020, Contact 98271-62352,96440-14000
[42]
 DBMS GATE-PSUs-NET

Q.17 The relation scheme Student Performance (name, courseNo, rollNo, grade) has the following
functional dependencies: [GATE 2004]
name, courseNo → grade
rollNo, courseNo → grade
name → rollNo
rollNo → name
The highest normal form of this relation scheme is
(A) 2 NF (B) 3 NF (C) BCNF (D) 4 NF

Q.18 A relation Empdtl is defined with attributes empcode (unique), name, street, city, state and
pincode. For any pincode, there is only one city and state. Also, for any given street, city and state,
there is just one pincode. In normalization terms, Empdtl is a relation in [GATE 2004]
(A) 1NF only (B) 2NF and hence also in 1NF
(C) 3NF and hence also in 2NF and 1NF (D) BCNF and hence also in 3NF, 2NF an 1NF

Q.19 A table has field F1, F2, F3, F4, F5 with the following functional dependencies
F1  F3, F2  F4, (F1, F2)  F5
In terms of Normalization, this table is in [GATE 2005]
(A) 1NF (B) 2NF (C) 3NF (D) None of these

Q.20 Which one of the following statements about normal forms is FALSE? [GATE 2005]
(A) BCNF is stricter than 3 NF
(B) Lossless, dependency preserving decomposition into 3NF is always possible
(C) Lossless, dependency preserving decomposition into BCNF is always possible
(D) Any relation with two attributes in BCNF

Q.21 Consider a relation schema R = (A, B, C, D, E, H) on which the following functional

dependencies hold {A  B, BC  D, E  C, D  A}. What are the candidate key of R?
(A) AE, BE (B) AE, BE, DE (C) AEH, BEH, BCH (D) AEH, BEH, DEH
[GATE 2005]
Q.22 In a schema with attributes A, B, C, D and E following set of functional dependencies are given
AB [GATE 2005]
AC
CD  E
BD
EA
Which of the following functional dependencies is NOT implied by the above set
(A) CD  AC (B) BD  CD (C) BC  CD (D) AC  BC

Q.23 Consider the relation r1(P, Q, R) and r2(R, S, T) with primary keys P and R respectively. The
relation r1 contains 2000 tuple and r2 contains 2500 tuples. The maximum size of the joint r1 >< r2
is [GATE 2006]

i-GATE, B-713, Street 22, Smriti Nagar, Bhilai- 490020, Contact 98271-62352,96440-14000
[43]
 DBMS GATE-PSUs-NET

(A) 2000 (B) 2500 (C) 4500 (D) 5000

Q.24 Consider a relation R with five attribute V, W, X, Y and Z. The following functional dependencies
hold: [GATE 2006]
VY  W, WX  Z and ZY  V. Which of the following is a candidate key of R?
(A) VXZ (B) VXY (C) VWXY (D) VWXYZ

Q.25 The following functional dependencies are given: [GATE 2006]

AB  CD, AF  D, DE  F, C  G, F  E, G  A.
Which one of the following is false?
(A) {CF}+ = {ACDEFG} (B) {BG}+ = {ABCDG}
(C) {AF}+ = {ACDEFG} (D) {AB}+ = {ACDFG}

Q.26 Which one of the following statements is FALSE? [GATE 2007]

(A) Any relation with two attributes is in BCNF
(B) A relation in which every key has only one attribute is in 2 NF
(C) A prime attributes can be transitively dependent on a key in 3NF relation
(D) A prime attributes can be transitively dependent on a key in a BCNF relation

Q.27 Consider the following implications relating to functional and multi-valued dependencies given
below, which may or may not be correct.
(i) If A   B and A   C then A  BC
(ii) If A  B and A  C then A   BC
(iii) If A   BC and A  B then A  C
(iv) If A  BC and A  B then A   C
Exactly how many of the above implications are valid? [GATE 2007]
(A) 0 (B) 1 (C) 2 (D) 3

Q.28 Let R(A, B, C, D) be a relations schema with the following functional dependencies:
A  B, B  C, C  D and D  B. [GATE 2008]
The decomposition of R into (A, B), (B, C), (B, D)
(A) Givens a lossless join, and is dependency preserving
(B) Given a lossless join, but is not dependency preserving
(C) Does not give a lossless join, but is dependency preserving
(D) Does not give a lossless join, and is not dependency preserving

Q.29 Let R(A, B, C, D, E, P, G) be a relational schema in which the following functional dependencies
are known to hold: [GATE 2008]
AB  CD, DE  P, C  E, P  C and B  G
The relational schema R is
(A) In BCNF (B) In 3NF, but not in BCNF
(C) In 2NF, but not in 3NF (D) Not in 2NF

i-GATE, B-713, Street 22, Smriti Nagar, Bhilai- 490020, Contact 98271-62352,96440-14000
[44]
 DBMS GATE-PSUs-NET

Q.30 The following functional dependencies hold for relations R(A, B, C) and S(B, D, E):
BA [GATE 2010]
AC
The relation R contains 200 tuples and the relation S contains 100 tuples. What is the maximum
number of tuples possible in the natural join R >< S?
(A) 100 (B) 200 (C) 300 (D) 2000

Q.31 Consider a relation table with a single record from each registered student with the following
attributes.
1. Registration_Num: Unique registration number of each registered student
2. UID: Unique identity number, unique at the national level for each citizen
3. BankAccpunt_Num: Uniqie account number at the bank. A student can have multiple account
or joint accounts. This attributes stores the primary account number
4. Name: Name of the student
5. Hostel_Room: Room number of the hostel
Which of the following option as in INCORRECT? [GATE 2011]
(A) BankAccount_Num is a candidate key
(B) Registration_Num can be a primary key
(C) UID is a candidate key if all students are from the same country
(D) If S is a superkey such that S  UID is NULL the S  UID is also a superkey

Q.32 Which of the following is TRUE? [GATE 2012]

(A) Every relation in 3NF is also in BCNF
(B) A relation R is in 3NF if every non-prime attributes of R is fully functional dependent on
every key of R
(C) Every relation in BCNF is also in 3NF
(D) No relation can be in both BCNF and 3NF

Linked Answer Question 33 and 34:

Relation R has eight attributes ABCDEFGH. Fields of R contains only atomic values.
F = {CH  G, A  BC, B  CFH, E  A, F  FG} is a set of functional dependencies (FDs) so
that F is exactly the set of FDs that hold for R.
Q.33 How many candidate keys does the relation R have? [GATE 2013]
(A) 3 (B) 4 (C) 5 (D) 6

Q.34 The relation R is [GATE 2013]

(A) In 1NF, but not in 2NF (B) In 2NF, but not in 3NF
(C) In 3NF, but not in BCNF (D) In BCNF
Q.35 Consider the relation scheme R = {E, F, G, H, I, J, K, L, M, M} and the set of functional
dependencies {{E, F}  {G}, {F}  {I, J}, {E, H}  {K, L}, {K}  {M}, {L}  {N} on R.
What is the key for R? [GATE 2014]
(A) {E, F} (B) {E, F, H} (C) {E, F, H, K, L} (D) {E}

i-GATE, B-713, Street 22, Smriti Nagar, Bhilai- 490020, Contact 98271-62352,96440-14000
[45]
 DBMS GATE-PSUs-NET

Q.36 Given the following statements:

S1: A foreign key declaration can always be replaced by an equivalent check assertion in SQL.
S2: Given the table R(a, b, c) where a and b together form the primary key, the following is a
valid table definition.
CREATE TABLE S (
a INTEGER,
d INTEGER,
e INTEGER,
PRIMARY KEY (d),
FOREIGN KEY (a) references R)
Which one of the following statements is CORRECT? [GATE 2014]
(A) S1 is TRUE and S2 is FALSE (B) Both S1 and S2 are TRUE
(C) S1 is FALSE and S2 is TRUE (D) Both S1 and S2 are FALSE

Q.37 Given the following two statements:

S1: Every table with two single-valued attributes is in 1NF, 2NF, 3NF and BCNF.
S2: AB → C, D → E, E → C is a minimal cover for the set of functional dependencies AB → C,
D → E, AB → E, E → C.
Which one of the following is CORRECT? [GATE 2014]
(A) S1 is TRUE and S2 is FALSE (B) Both S1 and S2 are TRUE
(C) S1 is FALSE and S2 is TRUE (D) Both S1 and S2 are FALSE

Q.38 The maximum number of superkeys for the relation schema R(E, F, G, H) with E as the key
is_____. [GATE 2014]

Q.39 Given an instance of the STUDENTS relation as shown as below

StudentID StudentName StudentEmail StudentAge CPI
2345 Shankar Shankar@math X 9.4
1287 Swati swati@ee 19 9.5
7853 Shankar Shankar@cse 19 9.4
9876 Swati swati@mech 18 9.3
8765 Ganesh ganesh@civil 19 8.7

For (StudentName, StudentAge) to be a key for this instance, the value X should NOT be equal
to______. [GATE 2014]

Q.40 A prime attribute of a relation scheme R is an attribute that appears [GATE 2014]
(A) In all candidate keys of R (B) In some candidate key of R
(C) In a foreign key of R (D) Only in the primary key of R

Q.41 Consider the relation X(P, Q, R, S, T, U) with the following set of functional dependencies
F={ [GATE 2015]
{P, R} → {S, T},

i-GATE, B-713, Street 22, Smriti Nagar, Bhilai- 490020, Contact 98271-62352,96440-14000
[46]
 DBMS GATE-PSUs-NET

{P, S, U} → {Q, R}
}
Which of the following is the trivial functional dependency in F+, where F+ is closure to F?
(A) {P, R} → {S, T} (B) {P, R} → {R, T} (C) {P, S} → {S} (D) {P, S, U} → {Q}

Q.42 Which of the following is NOT a superkey in a relational schema with attributes V, W, X, Y, Z
and primary key V Y? [GATE 2016]
(A) V X Y Z (B) V W X Z (C) V W X Y (D) V W X Y Z

Q.43 A database of research articles in a journal uses the following schema [GATE 2016]
(VOLUME, NUMBER, STARTPAGE, ENDPAGE, TITLE, YEAR, PRICE)
The primary key is (VOLUME, NUMBER, STARTPAGE, ENDPAGE) and the following
functional dependencies exist in the schema.
(VOLUME, NUMBER, STARTPAGE, ENDPAGE) →TITLE
(VOLUME, NUMBER) → YEAR
(VOLUME, NUMBER, STARTPAGE, ENDPAGE) →PRICE
The database is redesigned to use the following schemas
(VOLUME, NUMBER, STARTPAGE, ENDPAGE, TITLE, PRICE)(VOLUME,
NUMBER, YEAR)
Which is the weakest normal form that the new database satisfies, but the old one does not?
(A) 1NF (B) 2NF (C) 3NF (D) BCNF

Q.44 The following functional dependencies hold true for the relational schema R{V, W, X, Y, Z}
V → W; VW → X; Y → VX; Y → Z [GATE 2017]
Which of the following is irreducible equivalent for this set of functional dependencies?
(A) V → W; V → X; Y → V; Y → Z
(B) V → W; W → X; Y → V; Y → Z
(C) V → W; V →X; Y → V; Y → X; Y → Z
(D) V → W; W → X; Y → V; Y → X; Y → Z

Q.45 Consider the following four relational schemas. For each schema, all non-trivial functional
dependencies are listed, The underlined attributes are the respective primary keys.
Schema I: Registration(rollno, courses)
Field ‗courses‘ is a set-valued attribute containing the set of courses a student has registered for.
Non-trivial functional dependency
rollno → courses
Schema II: Registration (rollno, coursid, email)
Non-trivial functional dependencies:
rollno, courseid → email
email → rollno
Schema III: Registration (rollno, courseid, marks, grade)
Non-trivial functional dependencies:
rollno, courseid, → marks, grade

i-GATE, B-713, Street 22, Smriti Nagar, Bhilai- 490020, Contact 98271-62352,96440-14000
[47]
 DBMS GATE-PSUs-NET

marks → grade
Schema IV: Registration (rollno, courseid, credit)
Non-trivial functional dependencies:
rollno, courseid → credit
courseid → credit
Which one of the relational schemas above is in 3NF but not in BCNF? [GATE 2017]
(A) Schema I (B) Schema II (C) Schema III (D) Schema IV

ANSWER KEY
1. (False) 2. (*) 3. (D) 4. (D) 5. (C) 6. (*) 7. (B)
8. (D) 9. (B) 10. (C) 11. (C) 12. (A) 13. (C) 14. (B)
15. (D) 16. (A) 17. (B) 18. (B) 19. (A) 20. (C) 21. (D)
22. (B) 23. (A) 24. (B) 25. (C, D) 26. (D) 27. (C) 28. (C)
29. (D) 30. (A) 31 (A) 32. (C) 33. (B) 34. (A) 35. (B)
36. (D) 37. (A) 38. (8) 39. (19) 40. (B) 41. (C) 42. (B)
43. (B) 44. (A) 45. (B)

SOLUTION
Sol.1 False
BCNF decomposition can always be lossless, but it may not be always possible to get a
dependency preserving BCNF decomposition.

Sol.2 The Candidate Keys are AB and BC

None of the given functional dependencies are partial. So, the scheme qualifies for 2NF
There is no transitive dependency. So, the scheme qualifies for 3NF
All determinants are not Candidate Keys. So, the scheme do not qualify for BCNF

Sol.3
R
a Let(PK) b C
1
2

d(FK referring to PK of R) e F
2
1

 Insert into R cannot cause any violation.

i-GATE, B-713, Street 22, Smriti Nagar, Bhilai- 490020, Contact 98271-62352,96440-14000
[48]
 DBMS GATE-PSUs-NET

 Insert into S can cause violation if any value is inserted into d of S, which value is not in a of
R.
 Delete from S would cause no violation.
 Delete from R would cause violation if it any tuple is deleted, and as a result a value in a gets
deleted which is refereed to by d in S.

Sol.4 3NF will be adequate for normal relational database design since 3NF tables are free of insertion,
update, and deletion anomalies.

Sol.5 Indexing will be on Occupation field because Occupation field lexicographically sorted will give
the sequence 1, 3, 2, 5, 4.

Sol.6 Since Book_id is the key we have,

Book_id → Subject_Category_of_book
Book_id → Name_of_Author
Book_id → Nationality_of_Author
If we assume no other FD is there (this is not specified in the question), the relation is in BCNF as
the LHS of every FD is primary key which is also a super key.
a. 2NF
b. New set of FDs are
Book_id → Subject_Category_of_book
Book_id → Name_of_Author
Book_id → Nationality_of_Author
Book_id → Book_title
{Name_of_Author, Book_title} → Nationality_of_Author
{Name_of_Author, Book_title} → Author_address
{Name_of_Author, Book_title} → Book_id
One thing to notice here is only the primary key is being changed from Book_id to {Book_title,
Name_of_Author}, but Book_id is still a key as based on convention Book_id always determines
Book_title. Again if we assume no other FD, the relation is in BCNF as LHS of every FD is a
super key. But it is logical to assume the FD
Name_of_Author → Author_address
(won't be valid if two authors have same address and should have been explicit in the question)
and this FD is a partial FD on the candidate key {Name_of_Author, Book_title} as
Name_of_Author is a part of the key and Author_address is not a key attribute. So, this violates
2NF and relation is now just in 1NF. (Debatable if we can assume FDs)

Sol.7 Answer: B
EC is the key for R. Both E and C are not coming on the right hand side of any functional
dependency. So, both of them must be present in any key. Now, with EC and the given FDs, we
can derive all other attributes making EC a key.

i-GATE, B-713, Street 22, Smriti Nagar, Bhilai- 490020, Contact 98271-62352,96440-14000
[49]
 DBMS GATE-PSUs-NET

Sol.8 R1 ∩ R2 ≠ ϕ. This makes the decomposition lossless join, as all the attributes are keys, R1 ∩ R2
will be a key of the decomposed relations (lossless condition says the common attribute must be a
key in at least one of the decomposed relation). Now, even the original relation R is in 3NF
(even BCNF) as all the attributes are prime attributes (in fact each attribute is a candidate key).
Hence, any decomposition will also be in 3NF (even BCNF). Option D.
PS: Decomposition in 3NF means decomposed relations are in 3NF. But when we consider any
decomposed relation, we must also include any FD which are being implied by the original
relational schema. For example, in a decomposed relation STU, there will be a FD U→S as well.

Sol.9 (B) is answer.

If a−>b then for each same value of a, b should be same, We have to get the opposite of the define
i.e. if no values of a are same then b need be same.

Sol.10 Answer is C.
Here, no common attribute in R1 and R2, therefore lossy join will be there.
and both the dependencies are preserved in composed relations so, dependency preserving.

Sol.11 Taking up option A first:

We have, R(A, B, C, D) and the Functional Dependency set = {A→B, B→CD}.
Now we will try to decompose it such that the decomposition is a Lossless Join, Dependency
Preserving and new relations thus formed are in BCNF. We decomposed it to R1(A, B) and R2(B,
C, D). This decomposition satisfies all three properties we mentioned prior.
taking up option B : we have, R(A, B, C, D) and the Functional Dependency set = {A→B, B→C,
C→D}.
we decomposed it as R1(A, B), R2(B, C) and R3(C, D). This decomposition too satisfies all
properties as decomposition in option A.
taking up option D : we have, R(A, B, C, D) and the Functional Dependency set = {A→BCD}.
This set of FDs is equivalent to set = {A→B, A→C, A→D} on applying decomposition rule
which is derived from Armstrong's Axioms.
we decomposed it as R1(A, B), R2(A, C) and R3(A, D). This decomposition also satisfies all
properties as required.
taking up option C : we have, R(A, B, C, D) and the Functional Dependency set = {AB→C,
C→AD}.
we decompose it as R1(A, B, C) and R2(C, D). This preserves all dependencies and the join is
lossless too, but the relation R1 is not in BCNF. In R1 we keep ABC together otherwise
preserving {AB→C} will fail, but doing so also causes {C→A} to appear in R1. {C→A} violates
the condition for R1 to be in BCNF as C is not a superkey. Condition that all relations formed
after decomposition should be in BCNF is not satisfied here.
We need to identify the INCORRECT, Hence mark option C.

Sol.12 Answer is A.
If a relation schema is in BCNF then all redundancy based on functional dependency has been
normal form if and only if for every one of its dependencies X → Y, at least one of the following
conditions hold:

i-GATE, B-713, Street 22, Smriti Nagar, Bhilai- 490020, Contact 98271-62352,96440-14000
[50]
 DBMS GATE-PSUs-NET

 X → Y is a trivial functional dependency (Y ⊆ X)

 X is a super key for schema R

Sol.13 Answer is (C) since to identify BCNF we need BCNF definition. One relation which satisfies will
be in BCNF and other will be in 3NF.
1st is wrong because dependency may be preserved by both 3NF and BCNF.
2nd is wrong because both 3NF and BCNF decomposition can be lossless.
4th is wrong because 3NF and BCNF both are in 3NF also.

Sol.14 Answer is C
Generally Normalization is done on the schema itself
From the relational instance given, we may strike out FDs that do not hold. E.g. B does not
functionally determine C (This is true). But, we cannot say that A functionally determines B for
the entire relation itself. This is because that, A−>B holds for this instance, but in future there
might be some tuples added to the instance that may violate A−>B.
So, overall on the relation we cannot conclude that A−>B, from the relational instance which is
just a subset of an entire relation.

Sol.15 There are three FDs that are valid from the above set of FDs for the given relation:
Date_of_Birth → Age
Name → Roll_number
Roll_number → Name
Candidate keys for the above are : (Date_of_Birth, Name) and (Date_of_Birth, Roll_number)
Clearly there is partial dependency here (Date_of_Birth → Age) and Age is not a prime attribute.
So, it is only in 1NF.
Option (D).

Sol.16 Rollno in students is key, ans. students table has 120 tuples, In Enroll table rollno is FK
referencing to Students table. In natural join it'll return the records where the rollno value of enroll
matches with the rollno of students so, in both conditions min and max records will be resulted
(8, 8).
Hence A is the answer.
Hint: table which has non-key, no of records of that will be resulted.

Sol.17 For easy understanding let's say attributes (name, courseNo, rollNo, grade) be (A, B, C, D)
Then given FDs are as follows: AB->D, CB->D, A->C, C->A
Here there are two Candidate keys, AB and CB.
Now AB->D and CB->D satisfy BCNF as LHS is superkey in both. But, A->C and C->A, doesn't
satisfy BCNF. Hence we check for 3NF for these 2 FDs. As C and A on RHS of both the FDs are
prime attributes, they satisfy 3NF.
Hence for the whole relation the highest normal form is 3NF.

Sol.18 Given: Empdtl: empcode, name, street, city, state and pincode
There is transitive dependency in Table (pincode, there is only one city and state), so not in 3NF
All attributes are fully dependant on key, so in 2NF

i-GATE, B-713, Street 22, Smriti Nagar, Bhilai- 490020, Contact 98271-62352,96440-14000
[51]
 DBMS GATE-PSUs-NET

So answer is B

Sol.19 Answer is A 1NF Key is f1f2.

f1−>f3, f2−>f4 are partial dependencies.

Sol.20 It is not always possible to decompose a table in BCNF and preserve dependencies. For example,
a set of functional dependencies {AB –> C, C –> B} cannot be decomposed in BCNF.

Sol.22 Answer is (B).

Apply membership test for all the given Functional Dependencies.
CD → AC
CD+ = CDEAB
BD→CD
BD+ = BD
i.e. BD cannot derive CD and hence is not implied. Similarly do for rest two.
Sol.23 The common attribute is R and it is primary key in the second relation. Hence the R value is
distinct for 2500 rows. Hence when we join max possible number of tuples is 2000

Sol.24 As we can see attribute XY do not appear in RHS of any FD they need to be part of key.
Candidate keys are: VXY, WXY, ZXY.

Sol.25 {AF}* = {AFDE}.Hence, option C is wrong.

Sol.26 Any relation with two attributes is in BCNF => This is true. It is trivial
A relation in which every key has only one attribute is in 2NF => This is true. As it is not possible
to have Partial Functional Dependency. A prime attribute can be transitively dependent on a key
in a 3NF relation => This is true. As For 3NF to be violated we have something like Key => Non
Key, Non Key => Non key 3NF definition say x->y, either x should be key or y should be prime
attribute. Then we can have something like Key => Non Key, Non key => Prime Attribute,
resulting in Transitive FD on Prime Attribute, still in 3NF.
LHS must be always key, so No Transitive dependency is allowed. So answer => D

Sol.27 a. If A → → B and A → →C then A → BC. So FALSE

b. If A → B and A → C then A→ BC. So A →→BC TRUE.
c. If A → → BC and A → B here B is Subset of AB and (A intersection BC) is phi so A → B but
not A → C so FALSE (Coalescence rule)
d. If A → BC then A → C so A → → C TRUE
if A → B then A → → B holds but reverse not true.

Sol.28 Option A.
(A, B) (B, C) – common attribute is B and due to B → C, B is a key for (B, C) and hence ABC
can be losslessly decomposed into (A, B) and (B, C).

i-GATE, B-713, Street 22, Smriti Nagar, Bhilai- 490020, Contact 98271-62352,96440-14000
[52]
 DBMS GATE-PSUs-NET

(A, B, C) (B, D), common attribute is B and B → D is a FD (via B → C, C → D), and hence, B is
a key for (B, D). So, decomposition of (A, B, C, D) into (A, B, C) (B, D) is lossless.
Thus the given decomposition is lossless.
The given decomposition is also dependency preserving as the dependencies A → B is present
in (A, B), B → C is present in (B, C), D → B is present in (B, D) and C → D is indirectly present
via C → B in (B, C) and B → D in (B, D).

Sol.29 Answer: D, Here AB is the candidate key and B->G is a partial dependency. So, R is not in 2NF.

Sol.30 From the given set of functional dependencies, it can be observed that B is a candidate key of R.
So all 200 values of B must be unique in R. There is no functional dependency given for S. To get
the maximum number of tuples in output, there can be two possibilities for S.
1) All 100 values of B in S are same and there is an entry in R that matches with this value. In this
case, we get 100 tuples in output.
2) All 100 values of B in S are different and these values are present in R also. In this case also,
we get 100 tuples.

Sol.31 Answer is (A)

A relation is given (Registration_Num, UID, BankAccount_Num, Name, Hostel_Room).
Now, Registration_Num is unique for each student. So with this, we can identify each student.
Hence, this can be the primary key.
UID: It's an identification number for a person in a country. (Say you're in India and your UID is
0243. Someone in Pakistan may also have the same UID as 0243). So, if all students are from
India (that is, the same country) then their UID will be different and then UID will be a Candidate
key.
If S is a super key then S ∪ UID will be a Super key. e.g. R(A, B, C, D), If AB is a superkey
then ABC, ABCD are also superkey.
BankAccount_Num is not a candidate key, because a student can have multiple accounts or joint
accounts. We cannot identify each student uniquely with BankAccount_Num.

Sol.32 (C) Every relation in BCNF is also in 3NF. Straight from definition of BCNF.

Sol.33 A+ is ABCEFGH which is all attributes except D.

B+ is also ABCEFGH which is all attributes except D.
E+ is also ABCEFGH which is all attributes except D.
F+ is also ABCEFGH which is all attributes except D.
So there are total 4 candidate keys AD, BD, ED and FD

Sol.34 Here, candidate keys are AD, BD, ED and FD.

Partial dependency exists A→ BC, B→ CFH and F→ EG etc. In the following FDs.
For example partial dependency A→C exists in A→ BC and B→C and B→H in B→ CFH. etc.
So, given relation is in 1NF, but not in 2NF.

i-GATE, B-713, Street 22, Smriti Nagar, Bhilai- 490020, Contact 98271-62352,96440-14000
[53]
 DBMS GATE-PSUs-NET

Sol.35 Since E, F, H cannot be derived from anything else E, F, H should be there in key. Using
Find {EFH}+, it contains all the attributes of the relation.
Hence, it is key.

Sol.36 (D) Both are false

S1: Foreign key constraint means a lot of constraints it has to be a primary key (which in turn has
few constraints)
Alternate reason: Using a check condition we can have the same effect as Foreign key while
adding elements to the child table. But when we delete an element from the parent table the
referential integrity constraint is no longer valid. So, a check constraint cannot replace a foreign
key.
So, we cannot replace it with a single check.
S2: if a and b forms a primary key in R, a alone cannot form a foreign key. i.e. R(a, b, c) and S(a,
d, e) a of S references to a of R but a of R is not candidate key but a prime attribute since a, b
combine a key.
Foreign key definition: it should be a candidate key in some other table (in our case it is only a
prime attribute).

Sol.37 (A) S1 is TRUE and S2 is FALSE.

A relation with 2 attributes is always in BCNF. The two sets of functional dependencies are not
the same. Cannot derive AB→EAB→E from the 1st set

Sol.38 Super Key is any set of attributes that uniquely determines a tuple in a relation.
Since E is the only key, E should be present in any super key.
Excluding E, there are three attributes in the relation, namely F, G, H. Hence, if we add E to any
subset of those three attributes, then the resulting set is a super key. Number of subsets of {F, G,
H} is 8. Hence the answer is 8. The following are Super Keys:
E 
EE 
 
EG 
 
EH 
 
EFG 
EFH 
 
EGH 
EFGH 
 

Sol.39 Should not equal to 19

Since if it is equal the same key will have two different values for "StudentEmail" which cannot
be true by the definition of candidate/primary/super key.

Sol.40 Prime attribute is a constituent of a candidate key. it need not present in all candidate keys. Hence,
option B is correct.

i-GATE, B-713, Street 22, Smriti Nagar, Bhilai- 490020, Contact 98271-62352,96440-14000
[54]
 DBMS GATE-PSUs-NET

Sol.41 Option C is correct because {P, S} → {S}

For trivial FD, if X → Y then Y must be a subset of X and for non trivial FD X ∩ Y = ∅ and
here {S} is subset of {P, S}.
PS: Trivial means something which is always there. An attribute set always determines any of the
component attributes and this is always true irrespective of the relation instance. Hence, this FD
becomes trivial.

Sol.42 Here Primary Key is VY

If its SuperKey Any Key It Should Must Contains VY as Part of it
Option A VXYZ So VY is Part of it Correct
Option B VWXZ So No VY is Subset It Fails It Incorrect
Option C VWXY So VY is Part o f it Correct
Option D VWXYZ So VY is Part of it it Also Correct
Answer is B

Sol.43 The actual design is in 1NF because there are partial dependencies in the given FD set so the
original DB design is in 1NF but not 2NF
Now, the new design is removing all the partial dependencies so its in 2NF
So, the weakest form that the new schema satisfies that the old one couldn't is 2NF answer is B

Sol.44 In option B and option D there is a dependency W → X which is not implied by the question and
hence they are definitely wrong. Now in option (C) Y → X. can be removed as it can be implied
as Y → V, and V → X.
Hence, option (A) is correct.

Sol.45 Answer is (B).

rollno, courseid → email
(rollno, courseid is a super key, so it comes under 3NF as well as BCNF).
email → rollno
Here, email is not a key though but rollno comes under prime-attribute. Hence it's in 3NF but not
BCNF.

Gate Previous Year’s Questions

E-R MODELS
Q.1 It is desired to design an object-oriented employee record system for a company. Each employee
has a name, unique id and salary. Employees belong to different categories and their salary is
determined by their category. The functions to get Name, getld and compute salary are required.
Given the class hierarchy below, possible locations for these functions are:
i. getld is implemented in the superclass
ii. getld is implemented in the subclass
iii. getName is an abstract function in the superclass
iv. getName is implemented in the superclass

i-GATE, B-713, Street 22, Smriti Nagar, Bhilai- 490020, Contact 98271-62352,96440-14000
[55]
 DBMS GATE-PSUs-NET

v. getName is implemented in the subclass

vi. getSalary is an abstract function in the superclass
vii. getSalary is implemented in the superclass
viii. getSalary is implemented in the subclass

Choose the best design [GATE 2004]

(A) I, IV, VI, VIII (B) I, IV, VII (C) I, III, V, VI, VIII (D) II, V, VIII

Q.2 Consider the following entity relationship diagram (ERD), where two entities E1 and E2 have a
relation R of cardinality 1 : m.

The attributes of E1 are A11, A12 and A13 where A11 is the key attribute. The attributes of E2
are A21, A22 and A23 where A21 is the key attribute and A23 is a multi-valued attribute.
Relation R does not have any attribute. A relational database containing minimum number of
tables with each table satisfying the requirements of the third normal form (3NF) is designed from
the above ERD. The number of tables in the database is [GATE 2004]
(A) 2 (B) 3 (C) 5 (D) 4

Q.3 Consider the entities 'hotel room', and 'person' with a many to many relationship 'lodging' as
shown below: [GATE 2005]

If we wish to store information about the rent payment to be made by person (s) occupying
different hotel rooms, then this information should appear as an attribute of
(A) Person (B) Hotel Room (C) Lodging (D) None of these

Q.4 Let E1 and E2 be two entities in an E/R diagram with simple single-valued attributes. R1 and R2 are
two relationships between E1 and E2, where R1 is one-to-many and R2 is many-to-many. R1 and R2
do not have any attributes of their own. What is the minimum number of tables required to
represent this situation in the relational model? [GATE 2005]
(A) 2 (B) 3 (C) 4 (D) 5

Q.5 The following table has two attributes A and C where A is the primary key and C is the foreign
key referencing A with on-delete cascade. [GATE 2005]
A C
--------
2 4

i-GATE, B-713, Street 22, Smriti Nagar, Bhilai- 490020, Contact 98271-62352,96440-14000
[56]
 DBMS GATE-PSUs-NET

3 4
4 3
5 2
7 2
9 5
6 4
The set of all tuples that must be additionally deleted to preserve referential integrity when the
tuple (2, 4) is deleted is:
(A) (3, 4) and (6, 4) (B) (5, 2) and (7, 2)
(C) (5, 2), (7, 2) and (9, 5) (D) (3, 4), (4, 3) and (6, 4)

Common Data Question 6 & 7:

Consider the following ER diagram.

Q.6 The minimum number of table needed to represent M, N, P R1, R2 is [GATE 2008]
(A) 2 (B) 3 (C) 4 (D) 5

Q.7 Which of the following is a correct attribute set for one of the tables for the correct answer to the
above question [GATE 2008]
(A) {M1, M2, M3, P1} (B) {M1, P1, N1, N2}
(C) {M1, P1, N1} (D) {M1, P1}

Q.8 Given the basic ER and relational models, which of the following is INCORRECT?
(A) An attribute of an entity can have more than one value [GATE 2012]
(B) An attribute of an entity can be composite
(C) In a row of a relational table, an attribute can have more than one value
(D) In a row of a relational table, an attribute can have exactly one value or a NULL value
Q.9 Consider an Entity-Relationship (ER) model in which entity sets E1 and E2 are connected by an
m : n relationship R12, E1 and E3 are connected by a 1 : n (1 on the side of E1 and n on the side of
E3) relationship R13.E1 has two single-valued attributes a11 and a12 of which a11 is the key attribute.
E2 has two single-valued attributes a21 and a22 which a21 is the key attribute. E3 has two single-
valued attributes a31 and a32 of which a31 is the key attribute. The relationships do not have any
attributes.
If a relational model is derived from the above ER model, then the minimum number of relations
that would be generated if all the relations are in 3NF is ___________. [GATE 2015]

Q.10 An ER model of a database consists of entity types A and B. These are connected by a relationship
R which does not have its own attribute. Under which of the following conditions, can the
relational table for R be merged with that of A? [GATE 2017]

i-GATE, B-713, Street 22, Smriti Nagar, Bhilai- 490020, Contact 98271-62352,96440-14000
[57]
 DBMS GATE-PSUs-NET

(A) Relation R is one-to-many and the participation of A in R is total.

(B) Relation R is one-to-many and the participation of A in R is partial.
(C) Relation R is many-to-one and the participation of A in R is total.
(D) Relation R is many-to-one and the participation of A in R is partial.

Q.11 In an Entity-Relationship (ER) model, suppose R is a many-to-one relationship from entity set E1
to entity set E2. Assume that E1 and E2 participate totally in R and that the cardinality of E1 is
greater than the cardinality of E2. [GATE 2018]
Which one of the following is true about R?
(A) Every entity in E1 is associated with exactly one entity in E2
(B) Some entity in E1 is associated with more than one entity in E2
(C) Every entity in E2 is associated with exactly one entity in E1
(D) Every entity in E2 is associated with at most one entity in E1

ANSWER KEY
1. (A) 2. (B) 3. (C) 4. (D) 5. (C) 6. (B) 7. (A)
8. (C) 9. (4) 10. (C & D) 11. (A)
SOLUTION
Sol.1 Name and id are a property of every employee and independent of their category. So, these should
be implemented in superclass. Every employee has a salary but this is determined by their
category. So, getSalary must be a abstract function in superclass and implemented in subclass.

Sol.2 We need just two tables for 1NF

T1: {A11, A12, A13}
T2: {A21, A22, A23, A11}
A23 being multi-valued, A21, A23 becomes the key for T2 as we need to repeat multiple values
corresponding to the multi-valued attribute to make it 1NF. But, this causes partial FD A21 ->
A22 and makes the table not in 2NF. In order to make the table in 2NF, we have to create a
separate table for multi-valued attribute. Then we get
{T1: {A11, A12, A13} - key is A11
T2: {A21, A22, A11} - key is A21
T3: {A21, A23} - key is {A21, A23}
Here, all determinants of all FDs are keys and hence the relation is in BCNF and so 3NF also. So,
we need minimum 3 tables.

Sol.3 Since it is many to many, rent cannot be an attribute of room or person entities alone. If depending
on number of persons sharing a room the rent for each person for the room will be different.
Otherwise rent can be attribute of room. Hence i go for attribute of Lodging.

Sol.4 You need three tables:

For R1: Since it is one : many, you need just the tables for E1 and E2. E2 will have a foreign key
referencing E1. Thus multiple tuples in E2 will reference the same tuple in E1.
For R2: Since it is a many : many, you need the tables E1 and E2 as well as a 3rd table for the

i-GATE, B-713, Street 22, Smriti Nagar, Bhilai- 490020, Contact 98271-62352,96440-14000
[58]
 DBMS GATE-PSUs-NET

mappings as it can be shown in neither E1 nor E2. In the third table, say E3, there will be references
to both E1 and E2.
So, in all you need three tables.

Sol.5 (C)
Since deleting (2, 4), since 2 is a primary key, you have to delete its foreign key occurrence i.e. (5,
2) and (7, 2)
Since we are deleting 5 and 7 we have delete it foreign key occurrence i.e. (9, 5).
There is no foreign key occurrence for 9.

Sol.6 First strong entity types are made to tables. So, we get two tables M and P.
I assume R1 is 1 : 1 or 1 : n as that would minimize the number of tables as asked in question.
Now participation of M in R1 is total (indicated by double arrow) meaning every entity of M
participate in R1. Since R1 is not having an attribute, we can simple add the primary key of P to
the table M and add a foreign key reference to M. This handles R1 and we don't need an extra
table. So, M becomes M1, M2, M3, P1.
N here is a weak entity weakly related to P. So, we form a new table N, and includes the primary
key of P(P1) as foreign key reference. Now (P1, N1) becomes the primary key of N.
Thus we get 3 tables.
M: M1, M2, M3, P1 – M1 primary key, P1 references P
P: P1, P2 − P1 primary key
N: P1, N1, N2 − (P1, N1) primary key, P1 references P.
So, answer is B.

Sol.8 (C) is incorrect as a relational table requires that, in a row, an attribute can have exactly one value
or NULL value.

Sol.9 Answer is D. The relations are as shown:

⟨a11, a12⟩ for E1
⟨a21, a22⟩ for E2
⟨a31, a32, a11⟩ for E3 and E1 − E3 relationship
⟨a11, a21⟩ for m : n relationship E1 − E2
We cannot combine any relation here as it will give rise to partial functional dependency and thus
violate 3NF

Sol.10 The relation table for R should always be merged with the entity that has total participation and
relationship should be many to one.
Answer is C.

Sol.11 Since it is a many to one relationship from E1 to E2, therefore:

1. No entity in E1 can be related to more than one entity in E2. (hence B is incorrect)
2. An entity in E2 can be related to more than one entity in E1 (hence C and D are incorrect).
Option (A) is correct: Every entity in E1 is associated with exactly one entity in E2.

i-GATE, B-713, Street 22, Smriti Nagar, Bhilai- 490020, Contact 98271-62352,96440-14000
[59]
 DBMS GATE-PSUs-NET

GATE Previous Year’s Question

FILE STRUCTURE
Q.1 Which of the following is correct? [GATE 1999]
(A) B-trees are for storing data on disk and B+ trees are for main memory.
(B) Range queries are faster on B+ trees.
(C) B+ trees are for primary indexes and B+ trees are for secondary indexes.
(D) The height of a B+ tree is independent of the number of records.

Q.2 B+ trees are preferred to binary trees in databases because [GATE 2000]
(A) Disk capacities are greater than memory capacities
(B) Disk access is much slower than memory access
(C) Disk data transfer rates are much less than memory data transfer rates
(D) Disks are more reliable than memory

Q.3 AB+ tree index is to be built on the Name attribute of the relation STUDENT. Assume that all
student names are of length 8 bytes, disk block are size 512 bytes, and index pointers are of size 4
bytes. Given this scenario, what would be the best choice of the degree (i.e., the number of
pointers per node) of the B+ tree? [GATE 2002]
(A) 16 (B) 42 (C) 43 (D) 44

Q.4 The order of an internal node in a B+ tree index is the maximum number of children it can have.
Suppose that a child pointer takes 6 bytes, the search field value takes 14 bytes, and the block size
is 512 bytes. What is the order of the internal node? [GATE 2004]
(A) 24 (B) 25 (C) 26 (D) 27

Q.5 Consider a table T in a relational database with a key field K. AB-tree of order p is used as an
access structure on K, where p denotes the maximum number of tree pointers in a B-tree index
node. Assume that K is 10 bytes long; disk block size is 512 bytes; each data pointer P D is 8 bytes
long and each block pointer PB is 5 bytes long. In order for each B-tree node to fit in a single disk
block, the maximum value of p is [GATE 2004]
(A) 20 (B) 22 (C) 23 (D) 32

Q.6 Which one of the following is a key factor for preferring B+ trees to binary search trees for
indexing database relations? [GATE 2005]
(A) Database relations have a large number of records
(B) Database relations are sorted on the primary key
(C) B+ trees require less memory than binary search trees
(D) Data transfer from disks is in blocks

Q.7 A B-Tree used as an index for a large database table has four levels including the root node. If a
new key is inserted in this index, then the maximum number of nodes that could be newly created
in the process are [GATE 2005]
(A) 5 (B) 4 (C) 3 (D) 2
Linked Answer Questions 8 and 9:

i-GATE, B-713, Street 22, Smriti Nagar, Bhilai- 490020, Contact 98271-62352,96440-14000
[60]
 DBMS GATE-PSUs-NET

A database table T1 has 2000 records and occupies 80 disk blocks. Another table T2 has 400
records and occupies 20 disk blocks. These two tables have to be joined as per a specified join
condition that needs to be evaluated for every pair of records from these two tables. The memory
buffer space available can hold exactly one block of records for T1 and one block of records for
T2 simultaneously at any point in time. No index is available on either table.
Q.8 If, Nested-loop join algorithm is employed to perform the join, with the most appropriate choice
of the table of the used in outer loop, the number of block accesses required for reading the data
are [GATE 2005]
(A) 800000 (B) 40080 (C) 32020 (D) 100

Q.9 If, instead of Nested-loop join, Block nested-loop join is used, again with the most appropriate
choice of table in the outer loop, the reduction in number of block accesses required for reading
the data will be [GATE 2005]
(A) 0 (B) 30400 (C) 38400 (D) 798400

Q.10 In a database file structure, the search key field is 9 bytes long, the block size is 512 bytes, a
record pointer is 7 bytes and a block pointer is 6 bytes. The largest possible order of a non-leaf
node in a B+ tree implementing this file structure is [GATE 2006]
(A) 23 (B) 24 (C) 34 (D) 44

Q.11 The order of a leaf node in a tree B+ tree is the maximum number of (value, data record pointer)
pairs it can hold. Given that the block size is 1K bytes, data record pointer is 7 bytes long, the
value field is 9 bytes long and a block pointer is 6 bytes long, what is the order of the leaf node?
(A) 63 (B) 64 (C) 67 (D) 68
[GATE 2007]
Common Data Questions: 12 & 13
+
Consider the B tree in the adjoining figure, where each node has at most two keys and three links.

Q.12 Keys K15 and then K25 are inserted into this tree in that order. Exactly how many of the
following nodes (disregarding the links) will be present in the tree after the two insertions?

[GATE 2007]
(A) 1 (B) 2 (C) 3 (D) 4
+
Q.13 Now the key K50 is deleted from the B tree resulting after the two insertions made earlier.
Consider the following statements about the B+ tree resulting after this deletion.
(i) The height of the tree remains the same.
(ii) The node K20 (disregarding the links) is present in the tree.

i-GATE, B-713, Street 22, Smriti Nagar, Bhilai- 490020, Contact 98271-62352,96440-14000
[61]
 DBMS GATE-PSUs-NET

(iii) The root node remains unchanged (disregarding the links)

Which one of the following options is true? [GATE 2007]
(A) Statements (i) and (ii) are true (B) Statements (ii) and (iii) are true
(C) Statements (iii) and (i) are true (D) All the statements are false

Q.14 A clustering index is defined on the fields which are of type [GATE 2008]
(A) Non-key and ordering (B) Non-key and non-ordering
(C) Key and ordering (D) Key and non-ordering

Q.15 Consider a file of 16384 records. Each record is 32 bytes long and its key field is of size 6 bytes.
The file is ordered on a non-key field, and the file organization is unspanned. The file is stored in
a file system with block size 1024 bytes, and the size of a block pointer is 10 bytes. If the
secondary index is built on the key field of the file, and a multi-level index scheme is used to store
the secondary index, the number of first-level and second-level blocks in the multi-level index are
respectively [GATE 2008]
(A) 8 and 0 (B) 128 and 6 (C) 256 and 4 (D) 512 and 5

Q.16 The following key values are inserted into a B+ tree in which order of the internal nodes is 3, and
that of the leaf nodes is 2, in the sequence given below. The order of internal nodes is the
maximum number of tree pointers in each node, and the order of leaf nodes is the maximum
number of data items that can be stored in it. The B+ tree is initially empty
10, 3, 6, 8, 4, 2, 1 [GATE 2009]
The maximum number of times leaf nodes would get split up as a result of these insertions is
(A) 2 (B) 3 (C) 4 (D) 5

Q.17 Consider a B+ tree in which the maximum number of keys in a node is 5. What is the minimum
number of keys in any non-root node? [GATE 2010]
(A) 1 (B) 2 (C) 3 (D) 4

Q.18 A file is organized so that the ordering of the data records is the same as or close to the ordering of
data entries in some index. Than that index is called [GATE 2015]
(A) Dense (B) Sparse (C) Clustered (D) Unclustered

Q.19 With reference to the B+ tree index of order 1 shown below, the minimum number of nodes
(including the Root node) that must be fetched in order to satisfy the following query. "Get all
records with a search key greater than or equal to 7 and less than 15" is ______.

i-GATE, B-713, Street 22, Smriti Nagar, Bhilai- 490020, Contact 98271-62352,96440-14000
[62]
 DBMS GATE-PSUs-NET

[GATE 2015]

Q.20 Consider a B+ tree in which the search key is 12 byte long, block size is 1024 byte, recorder
pointer is 10 byte long and the block pointer is 8 byte long. The maximum number of keys that
can be accommodated in each non-leaf node of the tree is _________. [GATE 2015]

Q.21 B+ Trees are considered BALANCED because. [GATE 2016]

(A) The lengths of the paths from the root to all leaf nodes are all equal.
(B) The lengths of the paths from the root to all leaf nodes differ from each other by at most 1.
(C) The number of children of any two non-leaf sibling nodes differ by at most 1.
(D) The number of records in any two leaf nodes differ by at most 1.

Q.22 In a B+ Tree, if the search-key value is 8 bytes long, the block size is 512 bytes and the block
pointer size is 2 B, then the maximum order of the B+ Tree is ____ [GATE 2017]

ANSWER KEY
1. (B) 2. (B) 3. (C) 4. (C) 5. (C) 6. (D) 7. (A)
8. (C) 9. (B) 10. (C) 11. (A) 12. (A) 13. (A) 14. (A)
15. (C) 16. (A) 17. (B) 18. (C) 19. (5) 20. (20) 21. (A)
22. (52)
SOLUTION
Sol.1 Option B
(A) False. Both r stored in disk
(B) True. By searching leaf level linearly in B+ tree, we can say a node is present or not in B+ tree.
But for B tree we have to traverse the whole tree
(C) False. B tree and B+ tree uses dynamic multilevel indexes
(D) False. Height depends on number of record and also max no of keys in each node (order of
tree)

Sol.2 Answer is (B). The major advantage of B+ tree is in reducing the number of last level access
which would be from disk in case of large data size.

Sol.3 Answer: C
+
In a B tree we want en entire node content to be in a disk block. A node can contain up to p
pointers to child nodes and up to p – 1 key values for a B+ tree of order p. Here, key size is 8 bytes
and index pointer size is 4 bytes. Now a B+ tree has different structure for internal node and leaf

i-GATE, B-713, Street 22, Smriti Nagar, Bhilai- 490020, Contact 98271-62352,96440-14000
[63]
 DBMS GATE-PSUs-NET

nodes. While internal nodes can have upto p – 1 key values and p child pointers, leaf node will
have one sibling pointer in addition to maximum p – 1 keys and p – 1 record pointers. Since our
key is Name attribute which is not assumed to be unique it must be a secondary index and hence
the record pointer must be an index pointer to primary index. This will ensure size of a leaf node
is same as the size of a non-leaf node. Hence for a maximum sized node we can write
(8 + 4) (p − 1) + 4 ≤ 512
⟹ 12p ≤ 520
⟹ p = 43.

Sol.4 Answer: C
14(p − 1) + 6p ≤ 512
20p – 14 ≤ 512
20p ≤ 526
Therefore, p = 26

Sol.5 It is 23.
(p − 1)(key_ptr_size + record_ptr_size) + p. (block_ptr_size) ≤ 512
⟹ (p − 1) (10 + 8) + p × 5 ≤ 512
⟹ 23p ≤ 530
⟹ p ≤ 23.04
So, maximum value of p possible will be 23.

Sol.6 Answer: D
A. Cannot compare both the trees solely on basis of this.
B. Both trees are BST.
C. False. High fan out in B+ ensures that it takes more memory than BST.
D. True. Records are stored in disk blocks.
Sol.7 Suppose all nodes are completely full means every node has n − 1 keys. Tree has 4 levels if a new
key is inserted then at every level there will be created a new node, and in worst case root node
will also be broken into two parts, and we have 4 levels so, answer should be 5 because tree will
be increased with one more level.

Sol.8 Number of block access = nr * bs + br

where br and bs are number of blocks in relations R and S respectively, and nr is the number of
tuples in relation R.
We select the relation with small number of tuples as outer relation R. So, R is T2.
Number of block access = 400 * 80 + 20 = 32020
Thus, option (C) is correct.

Sol.9 Number of block access = nr * bs + br

where br and bs are number of blocks in relations R and S respectively, and nr is the number of
tuples in relation R.
We select the relation with small number of tuples as outer relation R. So, R is T2.

i-GATE, B-713, Street 22, Smriti Nagar, Bhilai- 490020, Contact 98271-62352,96440-14000
[64]
 DBMS GATE-PSUs-NET

Number of block access = 400 * 80 + 20 = 32020

The memory buffer space holds one block of records for T1 and one block of records for T2
simultaneously.
So, number of block accesses is 80 * 20 + 20 = 1620
So, Total number of block access = 32020 – 1620 = 30400

Sol.10 Answer is (C).

From the structure of B+ tree we can get this equation:
n × p + (n − 1) × k ≤ B (for non leaf node)
Here, n = order, p = tree/block/index pointer, B = size of block
I non leaf node no record pointer is there in B+ tree.
So, n × p + (n − 1)k ≤ B
n × 6 + (n − 1) × 9 ≤ 512
⟹ n ≤ 34.77
Largest possible value for n is 34.

Sol.11 The answer is option A.

Bp + P(Rp + Key) ≤ Block Size
1 × 6 + n(7 + 9) ≤ 1024
n ≤ 63.625.
So, 63 is the answer.

Sol.12 Option (A) is correct.

It is a B+ Tree.
After inserting K15 we get –

Now, we insert K25, which gives –

so, we see in the final tree only (K20, K25) is present. Hence A (Ans.)

Sol.13

i-GATE, B-713, Street 22, Smriti Nagar, Bhilai- 490020, Contact 98271-62352,96440-14000
[65]
 DBMS GATE-PSUs-NET

Now merge 40 in upper level.

Now redistribute:

So, answer is A.

Sol.14 There are several types of ordered indexes. A primary index is specified on the ordering key
field of an ordered file of records. Recall from Section 17.7 that an ordering key field is used
to physically order the file records on disk, and every record has a unique value for that field. If
the ordering field is not a key field- that is, if numerous records in the file can have the same value
for the ordering field— another type of index, called a clustering index, can be used. The data file
is called a clustered file in this latter case. Notice that a file can have at most one physical ordering
field, so it can have at most one primary index or one clustering index, but not both.
Answer should be A.

Q.15 Indexing mechanisms are used to optimize certain accesses to data (records) managed in files. For
example, the author catalog in a library is a type of index. An Index File consists of records
(called index entries) of the form
Search-key Pointer to Block

If even outer index is too large to fit in main memory, yet another level of index can be created,
and so on.

i-GATE, B-713, Street 22, Smriti Nagar, Bhilai- 490020, Contact 98271-62352,96440-14000
[66]
 DBMS GATE-PSUs-NET

Number of records in file = 16384

Record size = 32 bytes
Key Size = 6 bytes
Block Size on file system = 1024 bytes
Size of Block Pointer = 10 bytes
Size of a record or index Entry = 10 + 6 = 16
Number of blocks in first level = (Number of records in file) / (Disk Block Size)
= (16384 * 16) / (1024)
= 16 * 16
= 256
In second level, there will be 256 * 16 entries.
Number of blocks in second level = (Number of entries) / (Block Size)
= (256 * 16) / 1024
=4
Q.16 In this question they have asked only to count leaf node splits.
So, after discussing with my friends on Facebook, I found that you will get two different answers
depending on which convention you follow.
Convention 1: put the middle element in the left node, if you follow this you will get 4 as answer.
Convention 2: put the middle element in the right node, if you follow this you will get 3 as
answer.
4 splits:
1. after inserting 6
2. after inserting 4
3. after inserting 2 (there will be an internal node split and a leaf node split)
4. after inserting 1

Sol.17 Answer: B
Order = 5 + 1 = 6
 Order   6 
Minimum children in a non root node =   2
 2   2 

i-GATE, B-713, Street 22, Smriti Nagar, Bhilai- 490020, Contact 98271-62352,96440-14000
[67]
 DBMS GATE-PSUs-NET

Keys = Minimum children in a non root node – 1 = 2

Sol.18 Clustered- this is the definition of clustered indexing and for the same reason a table can have only
one clustered index.

Sol.20 (n − 1)12 + n ∗ 8 <= 1024

n <= 51
In non leaf node number of keys = n − 1
= 51 – 1 = 50

Sol.21 Option A: In B+ Tree all leaves are at same level.

In both B Tree and B+ trees, depth (length of root to leaf paths) of all leaf nodes is same. This is
made sure by the insertion and deletion operations. In these trees, we do insertions in a way that if
we have increase height of tree after insertion, we increase height from the root. This is different
from BST where height increases from leaf nodes. Similarly, if we have to decrease height after
deletion, we move the root one level down. This is also different from BST which shrinks from
the bottom. The above ways of insertion and deletion make sure that depth of every leaf node is
same.

Sol.22 Let order of B+ tree is p then maximum number of child pointers = p and maximum number of
keys = p − 1.
To accommodate all child pointers and search key, total size of these together cannot exceed 512
bytes.
2(p) + 8(p − 1) ≤ 512
⟹ p ≤ 52
Therefore, maximum order must be 52.

i-GATE, B-713, Street 22, Smriti Nagar, Bhilai- 490020, Contact 98271-62352,96440-14000
[68]
 DBMS GATE-PSUs-NET

GATE Previous Year’s Question

RELATION MODEL-RELATIONAL ALGEBRA AND TUPLE CALCULUS
Q.1 An instance of a relational scheme R(A, B, C) has distinct values for attributes A. Can you
conclude that A is a candidate key for R? [GATE 1994]

Q.2 Give a relational algebra expression using only the minimum number of operators from (∪, −) is
equivalent to R ∩ S. [GATE 1994]

Q.3 A library relational database system uses the following schema [GATE 1996]
USERS (User#, User Name, Home Town)
BOOKS (Book#, Book Title, Author Name)
ISSUED (Book#, User#, Date)
Explain in one English sentence, what each of the following relational algebra queries is designed
to determine
(a) σUser#=6(πUser#, Book Title((USERS⋈ISSUED)⋈BOOKS))
(b) πAuthor Name(BOOKS⋈(σHome Town=Delhi(USERS⋈ISSUED)))

Q.4 Which of the following query transformations (i.e., replacing the L.H.S. expression by the R.H.S.
expression) is incorrect? R1 and R2 are relations. C1, C2 are selection conditions and A1, A2 are
attributes of R1. [GATE 1998]
(A) σC1(σC2(R1)) → σC2(σC1(R1)) (B) σC1(πA1(R1)) → πA1(σC1(R1))
(C) σC1(R1 ∪ R2) → σC1(R1) ∪ σC1(R2) (D) πA1(σC1(R1)) → σC1(πA1 (R1))

Q.5 Consider the join of a relation R with a relation S. If R has m tuples and S has n tuples then the
maximum and minimum sizes of the join respectively are [GATE 1999]
(A) m + n and 0 (B) mn and 0 (C) m + n and |m − n| (D) mn and m + n

Q.6 The relational algebra expression equivalent to the following tuple calculus expression
{t ∣ t ∈ r ∧ (t[A] = 10 ∧ t[B] = 20)} is [GATE 1999]
(A) σ(A=10∨B=20)(r) (B) σ(A=10)(r) ∪ σ(B=20)(r)
(C) σ(A=10)(r) ∩ σ(B=20)(r) (D) σ(A=10)(r) − σ(B=20)(r)

Q.7 Given the relations [GATE 2000]

employee (name, salary, deptname, dept-no), and department (dept-no, dept-name, address),
Which of the following queries cannot be expressed using the basic relational algebra operations
(σ, π, ×, ⋈, ∪, ∩, −)?
(A) Department address of every employee
(B) Employees whose name is the same as their department name
(C) The sum of all employees salaries
(D) All employees of a given department

Q.8 Which of the rational calculus expression is not safe? [GATE 2001]
(A) {t ∣ ∃u ∈ R1(t[A] = u[A]) ∧ ¬∃s ∈ R2(t[A] = s[A])}

i-GATE, B-713, Street 22, Smriti Nagar, Bhilai- 490020, Contact 98271-62352,96440-14000
[69]
 DBMS GATE-PSUs-NET

(B) {t ∣ ∀u ∈ R1(u[A] = "x" ⇒ ∃s ∈ R2(t[A] = s[A] ∧ s[A] = u[A]))}

(C) {t ∣ ¬(t ∈ R1)}
(D) {t ∣ ∃u ∈ R1(t[A] = u[A]) ∧ ∃s ∈ R2(t[A] = s[A])}

Q.9 With regard to the expressive power of the formal relational query languages, which of the
following statements is true? [GATE 2002]
(A) Relational algebra is more powerful than relational calculus
(B) Relational algebra has the same power as relational calculus
(C) Relational algebra has the same power as safe relational calculus
(D) None of the above

Q.10 Let R1(A, B, C) and R2(D, E) be two relation schema, where the primary keys are shown
underlined, and let C be a foreign key in R1 referring to R2. Suppose there is no violation of the
above referential integrity constraint in the corresponding relation instances r1 and r2. Which of the
following relational algebra expressions would necessarily produce an empty relation?
(A) ΠD(r2) − ΠC(r1) (B) ΠC(r1) − ΠD(r2) [GATE 2004]
(C) ΠD(r1⋈C≠Dr2) – ΠC(r1) (D) ΠC(r1⋈C=Dr2)

Q.11 Consider the relation Student (name, sex, marks), where the primary key is shown underlined,
pertaining to students in a class that has at least one boy and one girl. What does the following
relational algebra expression produce? (Note:  is the rename operator). [GATE 2004]
πname{σsex=female(Student)} − πname(Student >< (sex=female∧x=male∧marks≤m)ρn, x, m(Student))
(A) Names of girl students with the highest marks
(B) Names of girl students with more marks than some boy student
(C) Names of girl students with marks not less than some boy students
(D) Names of girl students with more marks than all the boy students

Q.12 Let r be a relation instance with schema R = (A, B, C, D). We define r1 = πA,B,C(r) and r2 = πA,D(r).
Let S = r1 * r2 where ∗ denotes natural join. Given that the decomposition of r into r1 and r2 is
lossy, which one of the following is TRUE? [GATE 2005]
(A) s ⊂ r (B) r ∪ s = r (C) r ⊂ s (D) r * s = s

Q.13 A table ‗student‘ with schema (roll, name, hostel, marks), and another table ‗hobby‘ with schema
(roll, hobby name) contains records as shown below: [GATE 2005]
Table Student
ROLL NAME HOSTEL MARKS
1798 Manoj Rathod 7 95
2154 Soumic Banerjee 5 68
2369 Gumma Reddy 7 86
2581 Pradeep Pendse 6 92
2643 Suhas Kulkarni 5 78
2711 Nitin Kadam 8 72

i-GATE, B-713, Street 22, Smriti Nagar, Bhilai- 490020, Contact 98271-62352,96440-14000
[70]
 DBMS GATE-PSUs-NET

2872 Kiran Vora 5 92

2926 Manoj Kunkalikar 5 94
2959 Hemant Karkhanis 7 88
3125 Rajesh Doshi 5 82

Table Hobby
ROLL HOBBYNAME
1798 chess
1798 music
2154 music
2369 swimming
2581 cricket
2643 chess
2643 hockey
2711 volleyball
2872 football
2926 cricket
2959 photography
3125 music
3125 chess
The following SQL query is executed on the above tables:
select hostel
from student natural join hobby
where marks >= 75 and roll between 2000 and 3000; Relations S and H with the same schema as
those of these two tables respectively contain the same information as tuples. A new relation S′ is
obtained by the following relational algebra operation:
S′ = Πhostel((σs.roll=H.roll(σmarks>75 and roll>2000 and roll<3000(S)) × (H)) [GATE 2006]
The difference between the number of rows output by the SQL statement and the number of tuples
in S′ is
(A) 6 (B) 4 (C) 2 (D) 0

Q.14 Which of the following relational query languages have the same expressive power?
I. Relational algebra [GATE 2006]
II. Tuple relational calculus restricted to safe expressions
III. Domain relational calculus restricted to safe expressions
(A) II and III only (B) I and II only (C) I and III only (D) I, II and III

Q.15 Consider the relation enrolled (student, course) in which (student, course) is the primary key, and
the relation paid (student, amount) where student is the primary key. Assume no null values and
no foreign keys or integrity constraints. Assume that amounts 6000, 7000, 8000, 9000 and 10000
were each paid by 20% of the students. Consider these query plans (Plan 1 on left, Plan 2 on
right) to ―list all courses taken by students who have paid more than x‖ [GATE 2006]

i-GATE, B-713, Street 22, Smriti Nagar, Bhilai- 490020, Contact 98271-62352,96440-14000
[71]
 DBMS GATE-PSUs-NET

A disk seek takes 4ms, disk data transfer bandwidth is 300 MB/s and checking a tuple to see if
amount is greater than x takes 10µs. Which of the following statements is correct?
(A) Plan 1 and Plan 2 will not output identical row sets for all databases
(B) A course may be listed more than once in the output of Plan 1 for some databases
(C) For x = 5500, Plan 1 executes faster than Plan 2 for all databases
(D) For x = 9000, Plan 1 executes slower than Plan 2 for all databases

Q.16 Consider a selection of the form σA≤100(r), where r is a relation with 1000 tuples. Assume that the
attribute values for A among the tuples are uniformly distributed in the interval [0, 500]. Which
one of the following options is the best estimate of the number of tuples returned by the given
selection query? [GATE 2007]
(A) 50 (B) 100 (C) 150 (D) 200

Q.17 Consider the following relation schemas: [GATE 2007]

b-Schema = (b-name, b-city, assets)
a-Schema = (a-num, b-name, bal)
d-Schema = (c-name, a-number)
Let branch, account and depositor be respectively instances of the above schemas. Assume that
account and depositor relations are much bigger than the branch relation.
Consider the following query
Пc-name (σb-city = "Agra" ⋀ bal < 0 (branch ⋈ (account ⋈ depositor)
Which one of the following queries is the most efficient version of the above query?
(A) Пc-name (σbal < 0 (σb-city = "Agra" branch ⋈ account) ⋈ depositor)
(C) Пc-name (σb-city = "Agra" branch ⋈ (σbal < 0 account ⋈ depositor))
(C) Пc-name ((σb-city = "Agra" branch ⋈ σb-city = "Agra" ⋀ bal < 0 account) ⋈ depositor)
(D) Пc-name (σb-city = "Agra" branch ⋈ (σb-city = "Agra" ⋀ bal < 0 account ⋈ depositor))

Q.18 Information about a collection of students is given by the relation studinfo(studId, name, sex). The
relation enroll (studId, courseId) gives which student has enrolled for (or taken) that course(s).
Assume that every course is taken by at least one male and at least one female student. What does
the following relational algebra expression represent? [GATE 2007]

i-GATE, B-713, Street 22, Smriti Nagar, Bhilai- 490020, Contact 98271-62352,96440-14000
[72]
 DBMS GATE-PSUs-NET

πcourceId((πstudId(σsex="female"(studInfo)) × πcourseId(enroll)) − enroll)

(A) Courses in which all the female students are enrolled.
(B) Courses in which a proper subset of female students are enrolled.
(C) Courses in which only male students are enrolled.
(D) None of the above

Q.19 Consider the relation employee(name, sex, supervisorName) with name as the key, supervisor
Name gives the name of the supervisor of the employee under consideration. What does the
following Tuple Relational Calculus query produce? [GATE 2007]
{e.name ∣ employee(e) ∧ (∀x)[¬employee(x) ∨ x.supervisorName ≠ e.name ∨ x.sex = ‗‗male"]}
(A) Names of employees with a male supervisor.
(B) Names of employees with no immediate male subordinates.
(C) Names of employees with no immediate female subordinates.
(D) Names of employees with a female supervisor.

Q.20 Let R and S be two relations with the following schema [GATE 2008]
R(P, Q, R1, R2, R3)
S(P, Q, S1, S2)
Where {P, Q} is the key for both schemas. Which of the following queries are equivalent?
I. ΠP(R ⋈ S)
II. ΠP(R) ⋈ ΠP(S)
III. ΠP(ΠP,Q(R) ∩ ΠP,Q(S))
IV. ΠP(ΠP,Q(R) − (ΠP,Q(R) − ΠP,Q(S))
(A) Only I and II (B) Only I and III (C) Only I, II and III (D) Only I, III and IV

Q.21 Let R and S be relational schemes such that R = {a, b, c} and S = {c}. Now consider the following
queries on the database: [GATE 2009]
1. πR−S(r) − πR−S(πR−S(r) × S − πR−S,S(r))
2. {t ∣ t ∈ πR−S(r) ∧ ∀u ∈s (∃v ∈r(u = v[S] ∧ t = v[R − S]))}
3. {t ∣ t ∈ πR−S(r) ∧ ∀v ∈r (∃u ∈s (u = v[S] ∧ t = v[R − S]))}
4. Select R.a, R.b
from R, S
where R.c = S.c
Which of the above queries are equivalent?
(A) 1 and 2 (B) 1 and 3 (C) 2 and 4 (D) 3 and 4

Common Data Questions: 22 and 23

Consider the following relational schema: [GATE 2009]
Suppliers(sid:integer, sname:string, city:string, street:string)
Parts(pid:integer, pname:string, color:string)
Catalog (sid: integer, pid:integer. Cost:real)
Q.22 Consider the following relational query on the above database:
SELECT S.sname

i-GATE, B-713, Street 22, Smriti Nagar, Bhilai- 490020, Contact 98271-62352,96440-14000
[73]
 DBMS GATE-PSUs-NET

FROM Suppliers S
WHERE S.sid NOT IN (SELECT C.sid
FROM Catalog C
WHERE C.pid NOT IN (SELECT P.pid
FROM Parts P
WHERE P.color <> 'blue'))
Assume that relations corresponding to the above schema are not empty. Which one of the
following is the correct interpretation of the above query?
(A) Find the names of all suppliers who have supplied a non-blue part
(B) Find the names of all suppliers who have not supplied a non-blue part
(C) Find the names of all suppliers who have supplied only non-blue part
(D) Find the names of all suppliers who have not supplied only blue parts

Q.23 Assume that, in the supplier relation above, each supplier and each street within a city has unique
name, and (sname, city) forms a candidate key. No other functional dependencies are implied
other than those implied by primary and candidate keys. Which one of the following
is TRUE about the above schema?
(A) The schema is in BCNF (B) The schema is in 3NF but not in BCNF
(C) The schema is in 2NF but not in 3NF (D) The schema is not in 2NF

Q.24 Suppose R1(A, B) and R2(C, D) are two relation schemas. Let r1 and r2 be the corresponding
relation instances. B is a foreign key that refers to C in R2. If data in r1 and r2 satisfy referential
integrity constraints, which of the following is ALWAYS TRUE? [GATE 2012]
(A) ∏B(r1) − ∏C(r2) = ∅ (B) ∏C(r2) − ∏B(r1) = ∅
(B) ∏B(r1) = ∏C(r2) (D) ∏B(r1) − ∏C(r2) ≠ ∅

Q.25 Consider the following relational schema. [GATE 2013]

Students(rollno: integer, sname: string)
Courses(courseno: integer, cname: string)
Registration(rollno: integer, courseno: integer, percent: real)
Which of the following queries are equivalent to this query in English?
―Find the distinct names of all students who score more than 90% in the course numbered 107‖
1. SELECT DISTINCT S.sname
FROM Students as S, Registration as R
WHERE R.rollno = S.rollno AND R.courseno = 107 AND R.percent > 90
2. ∏sname(σcourseno = 107 ∧ percent > 90(Registration ⋈ Students))
3. {T ∣ ∃S ∈ Students, ∃R ∈ Registration(S.rollno = R.rollno ∧ R.courseno = 107 ∧ R.percent >
90 ∧ T.sname = S.sname)}
4. {⟨SN⟩ ∣ ∃SR∃RP(⟨SR, SN⟩ ∈ Students ∧ ⟨SR, 107, RP⟩ ∈ Registration ∧ RP > 90)
(A) I, II, III and IV (B) I, II and III only (C) I, II and IV only (D) I, III and IV only

Q.26 Consider a join (relation algebra) between relations r(R) and s(S) using the nested loop method.
There are 3 buffers each of size equal to disk block size, out of which one buffer is reserved for

i-GATE, B-713, Street 22, Smriti Nagar, Bhilai- 490020, Contact 98271-62352,96440-14000
[74]
 DBMS GATE-PSUs-NET

intermediate results. Assuming size(r(R)) < size(s(S)), the join will have fewer number of disk
block accesses if [GATE 2014]
(A) relation r(R) is in the outer loop
(B) relation s(S) is in the outer loop
(C) join selection factor between r(R) and s(S) is more than 0.5
(D) join selection factor between r(R) and s(S) is less than 0.5

Q.27 Consider the relational schema given below, where eId of the relation dependent is a foreign key
referring to empId of the relation employee. Assume that every employee has at least one
associated dependent in the dependent relation. [GATE 2014]
employee (empId, empName, empAge) dependent (depId, eId, depName, depAge)
Consider the following relational algebra query:
ΠempId(employee) − ΠempId(employee ⋈(empId=eID)∧(empAge≤depAge)dependent)
The above query evaluates to the set of empIds of employees whose age is greater than that of
(A) some dependent (B) all dependents
(B) some of his/her dependents (D) all of his/her dependents

Q.28 Consider two relations R1(A, B) with the tuples (1, 5), (3, 7) and R2(A, C) = (1, 7), (4, 9). Assume
that R(A, B, C) is the full natural outer join of R1 and R2. Consider the following tuples of the
form (A, B, C) a = (1, 5, null), b = (1, null, 7), c = (3, null, 9), d = (4, 7, null), e = (1, 5, 7), f = (3,
7, null), g = (4, null, 9). Which one of the following statements is correct? [GATE 2015]
(A) R contains a, b, e, f, g but not c, d (B) R contains all of a, b, c, d, e, f, g
(C) R contains e, f, g but not a, b (D) R contains e but not f, g

Q.29 Consider a database that has the relation schema CR(StudentName, CourseName). An instance of
the schema CR is as given below. [GATE 2017]
CR
Student name Course name
SA CA
SA CB
SA CC
SB CB
SB CC
SC CA
SC CC
SC CA
SD CA
SD CB
SD CC
SD CD
SE CA
SE CB

i-GATE, B-713, Street 22, Smriti Nagar, Bhilai- 490020, Contact 98271-62352,96440-14000
[75]
 DBMS GATE-PSUs-NET

SE CC
SF CA
SF CB
SF CC

The following query is made on the database.

T1 ← πCourseName(σStudentName = ‗SA‘(CR))
T2 ← CR ÷ T1
The number of rows in T2 is ______________ .

Q.30 Consider a database that has the relation schemas EMP(EmpId, EmpName, DeptId), and
DEPT(DeptName, DeptId). Note that the DeptId can be permitted to be NULL in the relation
EMP. Consider the following queries on the database expressed in tuple relational calculus.
I. {t | ∃u ∈ EMP(t[EmpName] = u[EmpName] ∧ ∀v ∈ DEPT(t[DeptId] ≠ v[DeptId]))}
II. {t | ∃u ∈ EMP(t[EmpName] = u[EmpName] ∧ ∃v ∈ DEPT(t[DeptId] ≠ v[DeptId]))}
III. {t | ∃u ∈ EMP(t[EmpName] = u[EmpName] ∧ ∃v ∈ DEPT(t[DeptId] = v[DeptId]))}
Which of the above queries are safe?
(A) I and II only (B) I and III only (C) II and III only (D) I, II and III

Q.31 Consider the relations r(A, B) and s(B, C), where s.B is a primary key and r.B is a foreign key
referencing s.B. Consider the query
Q : r ⋈ (σB<5(s))
Let LOJ denote the natural left outer-join operation. Assume that r and s contain no null values.
Which of the following is NOT equivalent to Q? [GATE 2018]
(A) σB<5(r ⋈ s) (B) σB<5(r LOJ s) (C) r LOJ (σB<5(s)) (D) σB<5(r) LOJ s

ANSWER KEY
1. (No) 2. (*) 3. (*) 4. (D) 5. (B) 6. (C) 7. (C)
8. (C) 9. (C) 10. (B) 11. (D) 12. (C) 13. (B) 14. (D)
15. (C) 16. (D) 17. (B) 18. (B) 19. (C) 20. (D) 21. (C)
22. (A) 23. (B) 24. (A) 25. (A) 26. (A) 27. (D) 28. (C)
29. (4) 30. (*) 31. (C)

SOLUTION
Sol.1 No.
A B C
1 5 6
2 4 7
3 4 5
Suppose this is the relational instance at any point of time.
Now we can see that A → BC holds for this instance, hence A+ = {A, B, C}. (For every unique
value of A, values of B and C are distinct. But FDs are defined on the schema and not on

i-GATE, B-713, Street 22, Smriti Nagar, Bhilai- 490020, Contact 98271-62352,96440-14000
[76]
 DBMS GATE-PSUs-NET

any instance. So, based on the state of any instance we cannot say what holds for schema (there
can be other instances too for R) At the best we can say that A → BC MAY hold for R.
PS: If we have a single instance where A → BC, is not holding, it is enough to say A → BC, does
not hold for the relation R.

Sol.2 R − (R − S)
There is no need to use Union operator here. Just because they say you can use operators from
(∪, −) we don't need to use both of them. Also they are saying that only the minimum number of
operators from (∪, −) which is equivalent to R∩S. My expression is Minimal.

Sol.3 a. Select the (user# and) titles of the books issued to User# 6
b. Select author names of the books issued to users whose home town is Delhi

Sol.4 (D) if the selection condition is on attribute A2, then we cannot replace it by RHS as there will not
be any attribute A2 due to projection of A1 only.

Sol.5 Answer is B.
mn
Case 1: if there is a common attribute between R and S, and every row of r matches with the each
row of s - i.e., it means, the join attribute has the same value in all the rows of both r and s,
Case 2: If there is no common attribute between R and S.
0 There is a common attribute between R and S and nothing matches- the join attribute in r and s
have no common value.

Sol.6 Answer: (C)

Tuple t should have two attributes A and B such that t.A = 10 and t.B = 20.
So, (Tuples having A = 10) ∩ (Tuples having B = 20) = (Tuples having A = 10 and B = 20).

Sol.7 Possible solutions, relational algebra:

(a) Join relation using attribute dpart_no.
 Πaddress(emp ⋈ depart) OR
 Πaddress(σemp.depart_no.= depart.depart_no.(emp × depart))
(B)
Πname(σemp.depart_no.=depart.depart_no.∧emp.name=depart.depart_name(emp × depart)) OR
Πname(emp⋈ emp.name=depart.depart_namedepart)
(D) Let the given department number be x
Πname(σemp.depart_no.=depart.depart_no.∧depart_no.=x(emp × depart)) OR
Πname(emp⋈ depart_no.=xdepart)
(C) We cannot generate relational algebra of aggregate functions using basic operations. We need
extended operations here.
Option (C).

Sol.8 It returns tuples not belonging to R1 (which is infinitely many). So, it is not safe.

i-GATE, B-713, Street 22, Smriti Nagar, Bhilai- 490020, Contact 98271-62352,96440-14000
[77]
 DBMS GATE-PSUs-NET

Sol.9 Answer: C
Relational algebra has the same power as safe relational calculus as:
 A query can be formulated in safe Relational Calculus if and only if it can be formulated in
Relational Algebra.

Sol.10 Answer is (B).

C in R1 is a foreign key referring to the primary key D in R2. So, every element of C must come
from some D element.

Sol.12 Answer is C r ⊂ s
r r1 r2 s = r1 * r2
A B C D A B C A B A B C D
1 2 3 3 1 2 3 1 3 1 2 3 3
1 5 3 4 1 5 3 1 4 1 2 3 4
1 5 3 4
1 5 3 4

All the rows of r are in s (marked bold). So, r ⊂ s

And one more result r * s = r.

Sol.13 SQL query will return:

Roll Hostel
2369 7
2581 6
2643 5
2643 5
Duplicate Row is present in
hobby Table
2872 5
2926 5
2956 7
Total 7 rows are selected.
In RA only distinct values of hostels are selected i.e. 5, 6, 7
SQL row count – RA row count =7 – 3 = 4
Answer is B.
Sol.14 Answer: D
All are equivalent in expressive power.

Sol.15 Option (C)

In all cases plan 1 is faster than plan 2 cause in plan 1 we are reducing the load by doing select
amount > x and then the loop

Sol.16 σA≤100(r)
r has 1000 tuples

i-GATE, B-713, Street 22, Smriti Nagar, Bhilai- 490020, Contact 98271-62352,96440-14000
[78]
 DBMS GATE-PSUs-NET

Values for A among the tuples are uniformly distributed in the interval [0, 500]. This can be split
to 5 mutually exclusive (non-overlapping) and exhaustive (no other intervals) intervals of same
width of 100 ([0 – 100], [101 – 200], [201 – 300], [301 – 400], [401 –500], 0 makes the first
interval larger - this must be a typo in question) and we can assume all of them have same number
of values due to Uniform distribution. So, number of tuples with A value in first interval should be
Total No. of tuples
 1000 / 5  200
5

Sol.17 For better record processing, We should always do select before join to avoid unnecessary tuples
being considered for join.(For an SQL query this is not strictly required as DBMS will rearrange
the query to make it efficient) and processing a smaller table gives more efficiency than the larger
one.
option (A): Пc-name (σbal < 0 (σb-city = ―Agra‖ branch ⋈ account) ⋈ depositor) here we are doing join
between relatively smaller table(branch) and larger one(account) and the output that this inner
table gives (which is smaller in comparison to joins that we are doing in B) is used for join with
depositor table with the selection condition.(same as given query).
option (B): Пc-name (σb-city = ―Agra‖ branch ⋈ (σbal < 0 account ⋈ depositor)) here we are doing a join
between two massive table account and depositor with selection condition(for balance less than
zero) and the output that this inner table gives is used for join with branch table(relatively smaller
table) with the selection condition (for city Agra). (same as given query) so option A and option B
both are same as given query but there is difference between record processing as the record
processing of option A will get reduced by some rate. (as filtered conditions are applied after the
join between one smaller and one larger table which will give relatively smaller table than the join
of two larger tables). So, overall option A is much better than option B.
option (C): Пc-name (σb-city = ―Agra‖ branch ⋈ σb-city = ―Agra‖ depositor) Incorrect as there is no b-city
column in a-Schema.
option (D): Пc-name (σb-city = ―Agra‖ branch ⋈ (σb-city = ―Agra‖ depositor)) Incorrect as there is no b-city
column in a-Schema.
⋀ bal < 0 account) ⋈
⋀ bal < 0 account ⋈
Note: don‘t miss this sentence ―account and depositor relations are much bigger than the branch
relation‖ because That makes A the best answer.

Sol.19 OR (∨) is commutative and associative, therefore i can rewrite given query as:
{e.name ∣ employee(e) ∧ (∀x) [¬employee(x) ∨ x.sex = ―male‖ ∨ x.supervisorName ≠ e.name]}
{e.name ∣ employee(e) ∧ (∀x)[¬(employee(x) ∧ x.sex ≠ ―male‖) ∨ x.supervisorName ≠ e.name]}
{e.name ∣ employee(e) ∧ (∀x)[(employee(x) ∧ x.sex ≠ ―male‖) ⇒ x.supervisorName ≠ e.name]}
{e.name ∣ employee(e) ∧ (∀x)[(employee(x) ∧ x.sex = ―female‖) ⇒ x.supervisorName ≠ e.name]}
It is clear now they are saying something about female employees, This query does not say
anything about male employees. Therefore Option A and B are out of consideration.
This query retrieves those e.name who satisfies this condition:
∀x[(employee(x) ∧ x.sex = "female") ⇒ x.supervisorName ≠ e.name]

i-GATE, B-713, Street 22, Smriti Nagar, Bhilai- 490020, Contact 98271-62352,96440-14000
[79]
 DBMS GATE-PSUs-NET

Means retrieves those e.name, who is not a supervisor of any female employees. i.e. it retrieves
name of employees with no female subordinate. (here "immediate" is obvious, as we are checking
first level supervisor.)

Sol.20 Option (D) i, iii, iv

(iv) is the expansion for natural join represented with other operators. Why ii is not equivalent?
Consider the following instances of R and S
R:{⟨‗‗1‖,‗‗abc‖,‗‗p1‖,‗‗p2‖,‗‗p3‖⟩, ⟨‗‗2‖,‗‗xyz‖,‗‗p1‖,‗‗p2‖,‗‗p3‖⟩}
S:{⟨‗‗1‖,‗‗abc‖,‗‗q1‖,‗‗q2‖⟩, ⟨‗‗2‖,‗‗def‖,‗‗q1‖,‗‗q2‖⟩}
Now, consider the given queries:
i. R ⋈ S gives
{⟨‗‗1‖, ‗‗abc‖, ‗‗p1‖,‗‗p2‖, ‗‗p3‖, ‗‗q1‖, ‗‗q2‖⟩}
Projecting P gives {⟨‗‗1‖⟩}
ii. πP(R) ⋈ πP(S) gives
{⟨‗‗1‖⟩⟨‗‗2‖⟩} ⋈ {⟨‗‗1‖⟩⟨‗‗2‖⟩} = {⟨‗‗1‖, ‗‗2‖⟩}
iii. ΠP(ΠP,Q(R) ∩ ΠP,Q(S)) gives
{⟨‗‗1‖, ‗‗abc‖⟩, ⟨‗‗2‖, ‗‗xyz‖⟩} ∩ {⟨‗‗1‖, ‗‗abc‖⟩, ⟨‗‗2‖, ‗‗def‘⟩} = {⟨‗‗1‖, ‗‗abc‖⟩}
Projecting P gives {⟨‗‗1‖⟩}
iv. ΠP(ΠP,Q(R) − (ΠP,Q(R) − ΠP,Q(S))) gives
{⟨‗‗1‖, ‗‗abc‖⟩, ⟨‗‗2‖, ‗‗xyz‖⟩} − ({⟨‗‗1‖, ‗‗abc‖⟩, ⟨‗‗2‖, ‗‗xyz‖⟩} − {⟨‗‗1‖, ‗‗abc‖⟩, ⟨‗‗2‖, ‗‗def‖⟩})
= {⟨‗‗1‖, ‗‗abc‖⟩, ⟨‗‗2‖, ‗‗xyz‖⟩} − {⟨‗‗2‖, ‗‗xyz‖⟩} = {⟨‗‗1‖, ‗‗abc‖⟩}
Projecting P gives {⟨‗‗1‖⟩}

Sol.21 1. πR−S(r) − πR−S(πR−S(r) × S − πR−S,S(r))

= πa,b(r) − πa,b(πa,b(r) × S − πR(r))
= (r/s)
2. Expanding logically the statement means to select t(a, b) from r such that for all tuples u in s,
there is a tuple v in r, such that u = v[S] and t = v[R − S]. This is just equivalent to (r/s)
3. Expanding logically the statement means that select t(a, b) from r such that for all tuples v in r,
there is a tuple u in s, such that u = v[S] and t = v[R − S]. This is equivalent to saying to
select (a, b) values from r, where the c value is in some tuple of s.
4. This selects (a, b) from all tuples from r which has an equivalent c value in s.
So, 1 and 2 are equivalent.
r
a b c
Arj TY 12 s
Arj TY 14 c
Cell TR 13 12
1. will give ⟨Arj, TY⟩.
Tom TW 12 14
2. will give ⟨Arj, TY⟩.
Ben TE 14
3. will not return any tuple as the c value 13, is
not in s.
4. will give ⟨Arj, TY⟩, ⟨Arj, TY⟩, ⟨Tom, TW⟩, ⟨Ben, TE⟩.

i-GATE, B-713, Street 22, Smriti Nagar, Bhilai- 490020, Contact 98271-62352,96440-14000
[80]
 DBMS GATE-PSUs-NET

Sol.22 SELECT P.pid FROM Parts P WHERE P.color <> ‘blue‘

Select all non blue parts
SELECT C.sid FROM Catalog C WHERE C.pid NOT IN
Selects all suppliers who have supplied a blue part
SELECT S.sname
FROM Suppliers S
WHERE S.sid NOT IN
Selects suppliers who have not supplied any blue parts. So, none of the options matches.
Option C is wrong as it does not select suppliers who have not supplied any parts which the given
query does.
Option A is wrong because it even selects those suppliers who have supplied blue and non-blue
parts and also does not include those suppliers who have not supplied any parts.

Sol.23 The non-trivial FDs are

1. (sname, city) → street
2. sid → street
3.(sname, city) → sid
4. sid → sname
5. sid → city
For all these, LHS is a super key and hence BCNF condition is satisfied. But we have some more
dependencies here:
This basically means each supplier in a city has unique name making (sname, city) determine sid
and hence making it a candidate key. Each street within a city also has a unique name and so
(street, city) is also a candidate key. Even then with all 3 candidate keys (for Suppliers schema),
for any FD, the LHS is a super key here, and hence the relation schema (for other two relations it
is straight forward) is in BCNF.

Sol.24 Answer is A.
Referential integrity means, all the values in foreign key should be present in primary key. r2(c) is
the super set of r1(b)
So, {subset - superset} is always empty set.

Sol.25 Answer: A
Four queries given in SQL, RA, TRC and DRC in four statements respectively retrieve the
required information.

Sol.26 In joining B and B+ using nested loop method, with A in outer loop two factors are involved.
i> No. of blocks containing all rows in A should be fetched
ii> No. of Rows A times no of Blocks containing all Rows of B (in worst case all rows of B are
matched with all rows of A).
In above question, |R| < |S|

i-GATE, B-713, Street 22, Smriti Nagar, Bhilai- 490020, Contact 98271-62352,96440-14000
[81]
 DBMS GATE-PSUs-NET

i> will be less when number of rows in outer table is less since less no of rows will take less no. of
blocks
ii> if we keep R in outer loop, no. of rows in R are less and no. of blocks in S are more If we
keep S in outer loop, no of rows in S are more and no. of blocks in R are less.
In ii> block accesses will be multiplication and will come same in both cases.
So, i> will determine no of block accesses

Sol.27 (D) all of his/her dependents.

The inner query selects the employees whose age is less than or equal to at least one of his
dependents. So, subtracting from the set of employees, gives employees whose age is greater than
all of his dependents.

Sol.28
A B
R1(A, B): 1 5
3 7

A C
R2(A, C): 1 7
4 9
Now, if we do full natural outer join:

A B C
1 5 7
3 7 NULL
4 NULL 9
So, option (C) is correct.

Sol.29 Explanation: Result of T1:

CA
CB
CC
Result of T2 = CR/T1
SA
SC
SD
SF
Total = 4

Sol.30 Answer is (D) before ∧ operation all three expressions are the same, i.e. return true if for each
tuple t we have finite no of tuple u in employee table for which they have same employee_name.

i-GATE, B-713, Street 22, Smriti Nagar, Bhilai- 490020, Contact 98271-62352,96440-14000
[82]
 DBMS GATE-PSUs-NET

(I) but in 2nd part, for each tuple v in department there may exist infinite no of tuple t for which
they may not be equal.
i.e. true for finite no of tuples ∧ true for infinite no of tuples, over all true for finite tuple.
(II) there may exist infinite no of tuple for which at least one tuple v belongs to department table
for which they may not be equal.
i.e. true for finite no of tuples ∧ true for infinite no of tuples, over all true for finite tuple.
(III) this one actually true for finite no of tuples, as there may exist only finite tuple which may be
equal to at least one tuple v in department. Because department table contain finite no of tuple all
tuple t which are same may not be more than all tuple v in department table in case of equality
operation.
i.e. true for finite ∧ true for finite tuple, over all true for finite tuple.
so all TRC query will return finite tuple which implies all are safe.

Sol.31 Option a, b, d will restrict all record with B < 5 but option C will include record with b >= 5 also,
so false.
C is answer.

i-GATE, B-713, Street 22, Smriti Nagar, Bhilai- 490020, Contact 98271-62352,96440-14000
[83]
 DBMS GATE-PSUs-NET

Gate Previous Year’s Question

STRUCTURED QUERY LANGUAGE (SQL)
Q.1 Suppose we have a database consisting of the following three relations. [GATE 1998]
FREQUENTS (student, parlor) giving the parlors each student visits.
SERVES (parlor, ice-cream) indicating what kind of ice-creams each parlor serves.
LIKES (student, ice-cream) indicating what ice-creams each student likes.
(Assume that each student likes at least one ice-cream and frequents at least one parlor)
Express the following in SQL:
Print the students that frequent at least one parlor that serves some ice-cream that they like.

Q.2 Which of the following is/are correct? [GATE 1999]

(A) An SQL query automatically eliminates duplicates
(B) An SQL query will not work if there are no indexes on the relations
(C) SQL permits attribute names to be repeated in the same relation
(D) None of the above

Q.3 Consider the set of relations [GATE 1999]

 EMP (Employee-no. Dept-no, Employee-name, Salary)
 DEPT (Dept-no. Dept-name, Location)
Write an SQL query to:
(a) Find all employees names who work in departments located at ‗Calcutta‘ and whose salary is
greater than Rs.50,000.
(b) Calculate, for each department number, the number of employees with a salary greater than Rs.
1,00,000.

Q.4 In SQL, relations can contain null values, and comparisons with null values are treated as
unknown. Suppose all comparisons with a null value are treated as false. Which of the following
pairs is not equivalent? [GATE 2000]
(A) x = 5, not(not(x = 5)) (B) x = 5, x > 4 and x < 6, where x is an integer
(C) x ≠ 5, not(x = 5) (D) None of the above

Q.5 Given relations r(w, x) and s(y, z) the result of [GATE 2000]
select distinct w, x
from r, s
is guaranteed to be same as r, provided.
(A) r has no duplicates and s is non-empty (B) r and s have no duplicates
(C) s has no duplicates and r is non-empty (D) r and s have the same number of tuples

Q.6 Consider the following SQL query [GATE 2003]

Select distinct a1,a2,…,an
from r1, r2,…, rm
where 

i-GATE, B-713, Street 22, Smriti Nagar, Bhilai- 490020, Contact 98271-62352,96440-14000
[84]
 DBMS GATE-PSUs-NET

For an arbitrary predicate P, this query is equivalent to which of the following relational algebra
expressions?
(A)   (r1× r2 ×⋯×rm) (B)   (r1 ⋈ r2 ⋈ ⋯⋈ rm)
a1 ,a 2 ,....,a n a1 ,a 2 ,....,a n

(C)   (r1 ∪ r2 ∪ ⋯∪ rm) (D)   (r1 ∩ r2 ∩ ⋯∩ rm)

a1 ,a 2 ,....,a n a1 ,a 2 ,....,a n

Q.7 Consider the set of relations shown below and the SQL query that follows. [GATE 2003]
Students: (Roll_number, Name, Date_of_birth)
Courses: (Course_number, Course_name, Instructor)
Grades: (Roll_number, Course_number, Grade)
Select distinct Name
from Students, Courses, Grades
where Students.Roll_number = Grades.Roll_number
and Courses.Instructor = 'Korth'
and Courses.Course_number = Grades.Course_number
and Grades.Grade = 'A'
Which of the following sets is computed by the above query?
(A) Names of students who have got an A grade in all courses taught by Korth
(B) Names of students who have got an A grade in all courses
(C) Names of students who have got an A grade in at least one of the courses taught by Korth
(D) None of the above

Q.8 The employee information in a company is stored in the relation [GATE 2004]
Employee (name, sex, salary, deptName)
Consider the following SQL query
Select deptName
From Employee
Where sex = ‗M‘
Group by deptName
Having avg(salary) >
(select avg (salary) from Employee)
It returns the names of the department in which
(A) The average salary is more than the average salary in the company
(B) The average salary of male employees is more than the average salary of all male employees
in the company
(C) The average salary of male employees is more than the average salary of employees in same
the department
(D) The average salary of male employees is more than the average salary in the company

Q.9 A relational database contains two tables student and department in which student tables has
columns roll_no, name and dept_id and department table has columns dept_id and dept_name.
The following insert statements were executed successfully to populate the empty tables:
Insert into department values (1, 'Mathematics') [GATE 2004]

i-GATE, B-713, Street 22, Smriti Nagar, Bhilai- 490020, Contact 98271-62352,96440-14000
[85]
 DBMS GATE-PSUs-NET

Insert into department values (2, 'Physics')

Insert into student values (l, 'Navin', 1)
Insert into student values (2, 'Mukesh', 2)
Insert into student values (3, 'Gita', 1)
How many rows and columns will be retrieved by the following SQL statement?
Select * from student, department
(A) 0 row and 4 columns (B) 3 rows and 4 columns
(C) 3 rows and 5 columns (D) 6 rows and 5 columns

Q.10 A table T1 in a relational database has the following rows and columns: [GATE 2004]
Roll no. marks
1 10
2 20
3 30
4 Null
The following sequence of SQL statements was successfully executed on table T1.
Update T1 set marks = marks + 5
Select avg(marks) from T1
What is the output of the select statement?
(A) 18.75 (B) 20 (C) 25 (D) Null

Q.11 Consider two tables in a relational database with columns and rows as follows:
Tables : Student Table : Department
ROLL_NO NAME DEPT_ID DEPT_ID DEPT_NAME
1 ABC 1 1 A
2 DEF 1 2 B
3 GHI 2 3 C
4 JKL 3
Roll_no is the primary key of the Student table, Dept_id is the primary key of the Department
table and Student.Dept_id is a foreign key from Department.Dept_id
What will happen if we try to execute the following two SQL statements? [GATE 2004]
(i) update Student set Dept_id = Null where Roll_on = 1
(ii) update Department set Dept_id = Null where Dept_id = 1
(A) Both i and ii will fail (B) i will fail but ii will succeed
(C) i will succeed but ii will fail (D) Both i and ii will succeed

Q.12 A company maintains records of sales made by its salespersons and pays them commission based
on each individual's total sales made in a year. This data is maintained in a table with following
schema: [GATE 2005]
salesinfo = (salespersonid, totalsales, commission)
In a certain year, due to better business results, the company decides to further reward its
salespersons by enhancing the commission paid to them as per the following formula:

i-GATE, B-713, Street 22, Smriti Nagar, Bhilai- 490020, Contact 98271-62352,96440-14000
[86]
 DBMS GATE-PSUs-NET

If commission < = 50000, enhance it by 2%

If 50000 < commission < = 100000, enhance it by 4%
If commission > 100000, enhance it by 6%
The IT staff has written three different SQL scripts to calculate enhancement for each slab, each of
these scripts is to run as a separate transaction as follows:
T1 Update salesinfo
Set commission = commission * 1.02
Where commission < = 50000;
T2 Update salesinfo
Set commission = commission * 1.04
Where commission > 50000 and commission is < = 100000;
T3 Update salesinfo
Set commission = commission * 1.06
Where commission > 100000;
Which of the following options of running these transactions will update the commission of all
salespersons correctly
(A) Execute T1 followed by T2 followed by T3
(B) Execute T2, followed by T3; T1 running concurrently throughout
(C) Execute T3 followed by T2; T1 running concurrently throughout
(D) Execute T3 followed by T2 followed by T1

Q.13 In an inventory management system implemented at a trading corporation, there are several tables
designed to hold all the information. Amongst these, the following two tables hold information on
which items are supplied by which suppliers, and which warehouse keeps which items along with
the stock-level of these items. [GATE2005]
Supply = (supplierid, itemcode)
Inventory = (itemcode, warehouse, stocklevel)
For a specific information required by the management, following SQL query has been written
Select distinct STMP.supplierid
From Supply as STMP
Where not unique (Select ITMP.supplierid
From Inventory, Supply as ITMP
Where STMP.supplierid = ITMP.supplierid
And ITMP.itemcode = Inventory.itemcode
And Inventory.warehouse = 'Nagpur');
For the warehouse at Nagpur, this query will find all suppliers who
(A) Do not supply any item (B) Supply exactly one item
(C) Supply one or more items (D) Supply two or more items

Q.14 The relation book (title, price) contains the titles and prices of different books. Assuming that no
two books have the same price, what does the following SQL query list? [GATE 2005]
select title
from book as B

i-GATE, B-713, Street 22, Smriti Nagar, Bhilai- 490020, Contact 98271-62352,96440-14000
[87]
 DBMS GATE-PSUs-NET

where (select count(*)

from book as T
where T.price > B.price) < 5
(A) Titles of the four most expensive books (B) Title of the fifth most inexpensive book
(C) Title of the fifth most expensive book (D) Titles of the five most expensive books

Common Data Question 15 to 16:

Q.15 Consider a database with three relation instances shown below. The primary keys for the Drivers
and Cars relation are did and cid respectively and the records are stored in ascending order of
these primary keys as given in the tables. No indexing is available in the database.

D: Drivers relation R: Reserves relation

did Dname rating age did cid day
22 Karthikeyan 7 25 22 101 10-10-2006
29 Salman 1 33 22 102 10-10-2006
31 Boris 8 55 22 103 08-10-2006
32 Amoldt 8 25 22 104 07-10-2006
58 Schumacher 10 35 31 102 10-11-2006
64 Sachin 7 35 31 103 06-11-2006
71 Senna 10 16 31 104 12-11-2006
74 Sachin 9 35 64 101 05-09-2006
85 Rahul 3 25 64 102 08-09-2006
95 Ralph 3 53 74 103 08-09-2006

C: Cars relation
cid cname colour
101 Renault blue
102 Renault red
103 Ferrari green
104 Jaguar red

Q.15 What is the output of the following SQL query [GATE 2006]
select D.dname
from Drivers D
where D.did in (
select R.did
from Cars C, Reserves R
where R.cid = C.cid and C.colour = 'red'
intersect
select R.did
from Cars C, Reserves R
where R.cid = C.cid and C.colour = 'green'

i-GATE, B-713, Street 22, Smriti Nagar, Bhilai- 490020, Contact 98271-62352,96440-14000
[88]
 DBMS GATE-PSUs-NET

)
(A) Karthikeyan, Boris (B) Sachin, Salman
(C) Karthikeyan, Boris, Sachin (D) Schumacher, Senna

Q.16 Let n be the number of comparisons performed when the above SQL query is optimally executed.
If linear search is used to locate a tuple in a relation using primary key, then n lies in the range
(A) 36−40 (B) 44−48 (C) 60−64 (C) 100−104
[GATE 2006]

Q.17 Consider the relation account (customer, balance) where the customer is a primary key and there
are no null values. We would like to rank customers according to decreasing balance. The
customer with the largest balance gets rank 1. Ties are not broke but ranks are skipped: if exactly
two customers have the largest balance they each get rank 1 and rank 2 is not assigned.
Query 1: Select A.customer, count(B.customer) from account A, account B where A.balance <=
B.balance group by A.customer
Query 2: Select A.customer, 1 + count(B.customer) from account A, account B where A.balance
< B.balance group by A.customer
Consider these statements about Query 1 and Query 2.
1. Query 1 will produce the same row set as Query 2 for some but not all databases.
2. Both Query 1 and Query 2 are a correct implementation of the specification
3. Query 1 is a correct implementation of the specification but Query 2 is not
4. Neither Query 1 nor Query 2 is a correct implementation of the specification
5. Assigning rank with a pure relational query takes less time than scanning in decreasing
balance order and assigning ranks using ODBC.
Which two of the above statements are correct? [GATE 2006]
(A) 2 and 5 (B) 1 and 3 (C) 1 and 4 (D) 3 and 5

Q.18 Consider the relation enrolled (student, course) in which (student, course) is the primary key, and
the relation paid (student, amount) where student is the primary key. Assume no null values and
no foreign keys or integrity constraints. [GATE 2006]
Given the following four queries:
Query1: select student from enrolled where student in (select student from paid)
Query2: select student from paid where student in (select student from enrolled)
Query3: select E.student from enrolled E, paid P where E.student = P.student
Query4: select student from paid where exists (select * from enrolled where enrolled.student =
paid.student)
Which one of the following statements is correct?
(A) All queries return identical row sets for any database
(B) Query2 and Query4 return identical row sets for all databases but there exist databases for
which Query1 and Query2 return different row sets
(C) There exist databases for which Query3 returns strictly fewer rows than Query2
(D) There exist databases for which Query4 will encounter an integrity violation at runtime

i-GATE, B-713, Street 22, Smriti Nagar, Bhilai- 490020, Contact 98271-62352,96440-14000
[89]
 DBMS GATE-PSUs-NET

Q.19 Consider the table employee(empId, name, department, salary) and the two queries Q1, Q2 below.
Assuming that department 5 has more than one employee, and we want to find the employees who
get higher salary than anyone in the department 5, which one of the statements is TRUE for any
arbitrary employee [GATE 2007]
Q1: Select e.empId
From employee e
Where not exists
(Select * From employee s Where s.department = "5" and s.salary >= e.salary)
Q2: Select e.empId
From employee e
Where e.salary > Any
(Select distinct salary From employee s Where s.department = "5")
(A) Q1 is the correct query
(B) Q2 is the correct query
(C) Both Q1 and Q2 produce the same answer
(D) Neither Q1 nor Q2 is the correct query

Common Data Question 20 & 21:

Consider the following relational schema:
Student (school-id, sch-roll-no, sname, saddress)
School (school-id, sch-name, sch-address, sch-phone)
Enrolment(school-id sch-roll-no, erollno, examname)
ExamResult(erollno, examname, marks)
Q.20 What does the following SQL query output?
SELECT sch-name, COUNT (*)
FROM School C, Enrolment E, ExamResult R
WHERE E.school-id = C.school-id
AND
E.examname = R.examname
AND E.erollno = R.erollno
AND
R.marks = 100 AND S.school-id IN (SELECT school-id
FROM student
GROUP BY school-id
HAVING COUNT (*) > 200)
GROUP By school-id
(A) For each school with more than 200 students appearing in exams, the name of the school and
the number of 100s scored by its students
(B) For each school with more than 200 students in it, the name of the school and the number of
100s scored by its students
(C) For each school with more than 200 students in it, the name of the school and the number of
its students scoring 100 in at least one exam
(D) Nothing; the query has a syntax error

i-GATE, B-713, Street 22, Smriti Nagar, Bhilai- 490020, Contact 98271-62352,96440-14000
[90]
 DBMS GATE-PSUs-NET

Q.21 Consider the following tuple relational calculus query. [GATE 2008]
{t | ∃E ∈ Enrolment t = E.school-id ∧ | {x | x ∈ Enrolment ∧ x.school-id = t ∧ (∃ B ∊ ExamResult
B.erollno = x.erollno ∧ B.examname = x.examname ∧ B.marks > 35)}| / | {x | x ∊
Enrolment ∧ x.school-id = t}| * 100 > 35}
If a student needs to score more than 35 marks to pass an exam, what does the query return?
(A) The empty set
(B) Schools with more than 35% of its students enrolled in some exam or the other
(C) Schools with a pass percentage above 35% over all exams taken together
(D) Schools with a pass percentage above 35% over each exam

Q.22 Consider a database table T containing two columns X and Y each of type integer. After the
creation of the table integer, one record (X = 1, Y = 1) is inserted in the table.
Let MX and MY denote the respective maximum values of X and Y among all records in the table
at any point in time. Using MX and MY, new records are inserted in the table 128 times with X
and Y values being MX + 1, 2 * MY + 1 respectively. It may be noted that each time after the
insertion, values of MX and MY change. What will be the output of the following SQL query after
the steps mentioned above are carried out? [GATE 2011]
SELECT Y FROM T WHERE X = 7;
(A) 127 (B) 255 (C) 129 (D) 257

Q.23 Database table by name Loan_Records is given below. [GATE 2011]

Borrower Bank_Manager Loan_Amount
Ramesh Sunderajan 10000.00
Suresh Ramgopal 5000.00
Mahesh Sunderajan 7000.00
What is the output of the following SQL query?
SELECT count(*)
FROM (
SELECT Borrower, Bank_Manager
FROM Loan_Records) AS SNATURAL JOIN
(SELECT Bank_Manager, Loan_Amount FROM Loan_Records) AS T
);
(A) 3 (B) 9 (C) 5 (D) 6
Q.24 Which of the following statements are TRUE about an SQL query? [GATE 2012]
P: An SQL query can contain a HAVING clause even if it does not have a GROUP BY clause
Q: An SQL query can contain a HAVING clause only if it has a GROUP BY clause
R: All attributes used in the GROUP BY clause must appear in the SELECT clause
S: Not all attributes used in the GROUP BY clause need to appear in the SELECT clause
(A) P and R
(B) P and S
(C) Q and R
(D) Q and S

i-GATE, B-713, Street 22, Smriti Nagar, Bhilai- 490020, Contact 98271-62352,96440-14000
[91]
 DBMS GATE-PSUs-NET

Common Data Questions: 25 & 26

Sol.25 Consider the following relations A, B and C: [GATE 2012]
A B C
Id Name Age Id Name Age Id Phone Age
12 Arun 60 15 Shreya 24 10 2200 2
15 Shreya 24 25 Hari 40 99 2100 1
99 Rohit 11 98 Rohit 20
99 Rohit 11
Q.25 How many tuples does the result of the following relational algebra expression contain? Assume
that the schema of A∪B is the same as that of A.
(A ∪ B) ⋈ A.Id>40∨C.Id<15C
(A) 7 (C) 4 (D) 5 (D) 9

Q.26 How many tuples does the result of the following SQL query contain? [GATE 2012]
SELECT A.Id
FROM A
WHERE A.Age > ALL (SELECT B.Age
FROM B
WHERE B.Name = ‗Arun‘)
(A) 4 (C) 3 (C) 0 (D) 1

Q.27 Given the following schema: [GATE 2014]

employees (emp-id, first-name, last-name, hire-date, dept-id, salary)
departments (dept-id, dept-name, manager-id, location-id)
You want to display the last names and hire dates of all latest hires in their respective departments
in the location ID 1700. You issue the following query:
SQL > SELECT last-name, hire-date
FROM employees
WHERE (dept-id, hire-date) IN
(SELECT dept-id, MAX (hire-date)
FROM employees JOIN departments USING (dept-id)
WHERE location-id = 1700
GROUP BY dept-id);
What is the outcome?
(A) It executes but does not give the correct result
(B) It executes and gives the correct result.
(C) It generates an error because of pairwise comparison.
(D) It generates an error because of the GROUP BY clause cannot be used with table joins in a
sub-query.

i-GATE, B-713, Street 22, Smriti Nagar, Bhilai- 490020, Contact 98271-62352,96440-14000
[92]
 DBMS GATE-PSUs-NET

Q.28 SQL allows duplicate tuples in relations, and correspondingly defines the multiplicity of tuples in
the result of joins. Which one of the following queries always gives the same answer as the nested
query shown below: [GATE 2014]
select * from R where a in (select S.a from S)
(A) Select R.* from R, S where R.a = S.a
(B) Select distinct R.* from R, S where R.a = S.a
(C) Select R.* from R,(select distinct a from S) as S1 where R.a = S1.a
(D) Select R.* from R,S where R.a = S.a and is unique R

Q.29 What is the optimized version of the relation algebra expression πA1(πA2(σF1(σF2(r)))), where A1,
A2 are sets of attributes in r with A1⊂A2 and F1, F2 are Boolean expressions based on the
attributes in r? [GATE 2014]
(A) πA1(σ(F1∧F2)(r)) (B) πA1(σ(F1∨F2)(r)) (C) πA2(σ(F1∧F2)(r)) (D) πA2(σ(F1∨F2)(r))

Q.30 Consider the following relational schema: [GATE 2014]

employee (empId, empName, empDept)
customer (custId, custName, salesRepId, rating)
salesRepId is a foreign key referring to empId of the employee relation. Assume that each
employee makes a sale to at least one customer. What does the following query return?
SELECT empName
FROM employee E
WHERE NOT EXISTS (SELECT custId
FROM customer C
WHERE C.salesRepId = E.empId
AND C.rating <> 'GOOD');
(A) Names of all the employees with at least one of their customers having a ‗GOOD‘ rating.
(B) Names of all the employees with at most one of their customers having a 'GOOD' rating.
(C) Names of all the employees with none of their customers having a 'GOOD' rating.
(D) Names of all the employees with all their customers having a 'GOOD' rating.

Q.31 Consider the following relation: [GATE 2014]

Student Performance
Roll_No Student_Name Roll_No Course Marks
1 Raj 1 Maths 80
2 Rohit 1 English 70
3 Raj 2 Maths 75
3 English 80
2 Physics 65
3 Maths 80

Consider the following SQL query.

SELECT S.Student_Name, Sum(P. Marks)
FROM Student S, Performance P

i-GATE, B-713, Street 22, Smriti Nagar, Bhilai- 490020, Contact 98271-62352,96440-14000
[93]
 DBMS GATE-PSUs-NET

WHERE S.Roll_No = P.Roll_No

GROUP BY S.STUDENT_Name
The numbers of rows that will be returned by the SQL query is_________________.

Q.32 SELECT operation in SQL is equivalent to [GATE 2015]

(A) The selection operation in relational algebra
(B) The selection operation in relational algebra, except that SELECT in SQL retains duplicates
(C) The projection operation in relational algebra
(D) The projection operation in relational algebra, except that SELECT in SQL retains duplicates

Q.33 Consider the following relation [GATE 2015]

Cinema(theater, address, capacity)
Which of the following options will be needed at the end of the SQL query
SELECT P1.address
FROM Cinema P1
such that it always finds the addresses of theaters with maximum capacity?
(A) WHERE P1.capacity >= All (select P2.capacity from Cinema P2)
(B) WHERE P1.capacity >= Any (select P2.capacity from Cinema P2)
(C) WHERE P1.capacity > All (select max(P2.capacity) from Cinema P2)
(D) WHERE P1.capacity > Any (select max(P2.capacity) from Cinema P2)

Q.34 Consider the following database table named water_schemes: [GATE 2016]

The number of tuples returned by the following SQL query is _________.

with total (name, capacity) as
select district_name, sum (capacity)
from water_schemes
group by district_name
with total_avg (capacity) as
select avg (capacity)
from total
select name
from total, total_avg
where total.capacity ≥ total_avg.capacity

i-GATE, B-713, Street 22, Smriti Nagar, Bhilai- 490020, Contact 98271-62352,96440-14000
[94]
 DBMS GATE-PSUs-NET

Q.35 Consider the following database table named top_scorer [GATE 2017]
top_scorer
player country goals
Klose Germany 16
Ronaldo Brazil 15
G Muller Germany 14
Fontaine France 13
Pele Brazil 12
Klinsmann Germany 11
Kocsis Hungary 11
Batistuta Argentina 10
Cubillas Peru 10
Lato Poland 10
Lineker England 10
T Mutter Germany 10
Rohan Germany 10

Consider the following SQL query:

SELECT ta.player FROM top_scorer AS ta
WHERE ta.goals >ALL (SELECT tb.goals
FROM top_scorer AS tb
WHERE tb.country = 'Spain')
AND ta.goals > ANY (SELECT tc.goals
FROM top_scorer AS tc
WHERE tc.country = 'Germany')
The number of tuples returned by the above SQL query is ______.

Q.36 Consider a database that has the relation schema EMP (EmpId, EmpName, and DeptName). An
instance of the schema EMP and a SQL query on it are given below: [GATE 2017]

EmpId EmpName DeptName

1 XYA AA
2 XYB AA
3 XYC AA
4 XYD AA
5 XYE AB
6 XYF AB
7 XYG AB
8 XYH AC
9 XYI AC
10 XYJ AC
11 XYK AD

i-GATE, B-713, Street 22, Smriti Nagar, Bhilai- 490020, Contact 98271-62352,96440-14000
[95]
 DBMS GATE-PSUs-NET

12 XYL AD
13 XYM AE

SELEXCT AVG(EC.Num)
FROM EC
WHERE (DeptName, Num) IN
(SELECT DeptName, COUNT(EmpId) AS EC(DeptName, Num))
FROM EMP
GROUP BY DeptName)
The output of executing the SQL query is _____________ .

Q.37 Consider the following two tables and four queries in SQL. [GATE 2018]
Book (isbn, bname), Stock(isbn, copies)
Query 1: SELECT B.isbn, S.copies
FROM Book B INNER JOIN Stock S
ON B.isbn = S.isbn;
Query 2: SELECT B.isbn, S.copies
FROM Book B LEFT OUTER JOIN Stock S
ON B.isbn = S.isbn;
Query 3: SELECT B.isbn, S,copies
FROM Book B RIGHT OUTER JOIN Stock S
ON B.isbn = S.isbn
Query 4: SELECT B.isbn, S.copies
FROM Book B FULL OUTER JOIN Stock S
ON B.isbn = S.isbn
Which one of the queries above is certain to have an output that is a superset of the outputs of the
other three queries?
(A) Query 1 (B) Query 2 (C) Query 3 (D) Query 4

ANSWER KEY
1. (*) 2. (D) 3. (*) 4. (C) 5. (A) 6. (A) 7. (C)
8. (D) 9. (D) 10. (C) 11. (C) 12. (D) 13. (D) 14. (D)
15. (A) 16. (C) 17. (C) 18. (B) 19. (B) 20. (B) 21. (C)
22. (A) 23. (C) 24. (D) 25. (A) 26. (B) 27. (B) 28. (C)
29. (A) 30. (D) 31. (2) 32. (D) 33. (A) 34. (*) 35. (7)
36. (2.6) 37. (D)

SOLUTION
Sol.1 SELECT DISTINCT A.student FROM
FREQUENTS A, SERVES B, LIKES C
WHERE
A.parlor = B.parlor
AND

i-GATE, B-713, Street 22, Smriti Nagar, Bhilai- 490020, Contact 98271-62352,96440-14000
[96]
 DBMS GATE-PSUs-NET

B.ice-cream = C.ice-cream
AND
A.student = C.student;
OR
SELECT DISTINCT A.student FROM FREQUENTS A
WHERE
parlor IN
(SELECT parlor FROM SERVES B
WHERE B.ice-cream IN
(SELECT ice-cream
FROM LIKES C
WHERE C.student = A.student));

Sol.2 (D)
SQL wont remove duplicates like relational algebra projection, we have to remove it explicitly by
distinct. If there are no indexes on the relation SQL will either chose one/more on its own or
simply work without any index. No index would just slow the query but it will surely work.
SQL does not permit 2 attributes to have same name in a relation.

Sol.3 (a)
select Employee-name
from EMP, DEPT
where Salary > 50000 and EMP.Dept-no = DEPT.Dept-no and Location = "Calcutta"
(b)
select Dept-no, count(*)
from EMP where salary > 100000
group by Dept-no

Sol.4 Option C
For all values smaller than 5, x < 5 will always be true but x = 5 will be false.

Sol.5 This question is about SQL, in SQL Relations are MULTISET, not SET. So, R or S can have
duplicated.
Answer: A.
(A) If R has duplicates, in that case, due to distinct keyword those duplicates will be eliminated in
final result. So, R cannot have duplicates. If S is empty R  S becomes empty, so S must be
non empty. This is true.
(B) Here, assume that S is empty. (No duplicates.) Then R  S will be empty. So this is false.
(C) Same argument as B.
(D) Assume that R has duplicates. Then Distinct keyword will remove duplicates. So, result of
query! = R, so This is false.

i-GATE, B-713, Street 22, Smriti Nagar, Bhilai- 490020, Contact 98271-62352,96440-14000
[97]
 DBMS GATE-PSUs-NET

Sol.6 select distinct in SQL is equivalent to project and by default relation 1, relation 2 in SQL
corresponds to cross-product. So, option A.

Sol.7 C. Names of the students who have got an A grade in at least one of the courses taught by Korth.

Sol.8 D is the answer.

The inner query is over all department and over both male and female employees while the outer
query is only for male employees.

Sol.9 Since, there is no specific joining condition specified, it will retrieve Cartesian product of the table
Number of rows = product of number of rows in each relation = 3 × 2 = 6
Number of columns = sum of number of columns =3 + 2 = 5
Answer: D.

Sol.10 Update on null gives null. Now, avg function ignores null values. So, here avg will be
(15 + 25 + 35)/3 = 25.

Sol.11 Answer is C
Here in (i) when we update in STUDENT table Dept_id = NULL it is fine as a foreign key can be
NULL. But in (ii) if we set in DEPARTMENT table dept id = NULL it is not possible as
PRIMARY KEY cannot be NULL. Instead of update to NULL, if we try DELETE, then also it is
not allowed as we have foreign key reference to it from STUDENT table with Dept_id = 1.
DELETE ON CASCADE clause is a way to avoid this issue which will delete all referenced
entries from the child table too but unless told we cannot assume this as this cause is not
universally applicable.

Sol.12 T3 followed by T2 followed by T1

If this sequence is not followed then it may happen that Officer of one slab get benefited twice.
Say an officer is having commission as 99,999, He must be get updated commission according to
T2.But then
99,999*1.04 = 1,03,998 and he again becomes eligible for next slab of commission.
T3 followed by T2 followed by T1 will be check all border cases like above. So Answer is D

Sol.13 Answer is (D) supply two or more items

The whole query returns the distinct list of suppliers who supply two or more items.

Sol.14 Answer: D
The outer query selects all titles from book table. For every selected book, the subquery returns
count of those books which are more expensive than the selected book. The where clause of outer
query will be true for 5 most expensive book. For example count (*) will be 0 for the most
expensive book and count(*) will be 1 for second most expensive book.

Sol.15 For color = "Red", did = {22, 22, 31, 31, 64}

i-GATE, B-713, Street 22, Smriti Nagar, Bhilai- 490020, Contact 98271-62352,96440-14000
[98]
 DBMS GATE-PSUs-NET

For color = "Green", did = {22, 31, 74}

Intersection of Red and Green will give did = {22, 31} which is Karthikeyan and Boris
Answer: A

Sol.16 select D.dname

from Drivers D
where D.did in (
select R.did
from Cars C, Reserves R
where R.cid = C.cid and C.colour = 'red'
intersect
select R.did
from Cars C, Reserves R
where R.cid = C.cid and C.colour = 'green'
)
select R. did from Cars C, Reserves R where R.cid = C.cid and C.colour = 'red'
So, first get 2 red cars by scanning 4 tuples of the cars relation. Now, for each of the two 'red' cars,
we scan all the 10 tuples of the 'Reserves' relation and thus we get 2 × 10 + 4 = 24 comparisons.
But this is not optimal. We can check in the reverse order for each tuple of the 'Reserves' relation
because 'cid' is a primary key (hence unique) of 'Cars' relation. Supposing our earlier selection
is ⟨102, 104⟩ then this requires 3 + 7 × 2 = 17 comparisons. Due to if(R.cid==102 || R.cid == 104)
If the order was ⟨104, 102⟩, then 2 + 8 × 2 = 18 comparisons. due to if(R.cid==104 || R.cid ==
102)
Thus, totally 21 to 22 comparisons and gives ⟨22, 31, 64⟩ as did.
Similarly for the 'green' car we get 4 + 10 = 14 comparisons. due to if(R.cid==103) and gives ⟨22,
31, 74⟩ as did.
Intersect requires 1 + 2 + 3 = 6 comparisons in the best case and 3 + 2 + 3 = 8 in the worst case
and this gives ⟨22, 31⟩.
Finally we have to locate the did 22 and did 31 from the driver table and did is the primary key.
As told in the question, we use linear search and for 22, we hit on the first try and for 31 we hit on
the third try. So, 1 + 3 = 4 comparisons.
Thus total no. of comparisons = (21 to 22) + 14 + (6 to 8) + 4 = 45 to 48.
Sol.17 Both Query1 and Query2 are not correct implementations because: Assume that we have a table
with n customers having same balance. In that case Query1 will give rank n to each customer. But
according to the question the rank assigned should be 1. And Query2 will return an empty result
set (as it will never return rank 1). So statement 4 is correct. For same reason Query 1 is wrong
though it is true if we assume relation set is empty. Statements 2 and 3 are false as 4 is TRUE.
Statement 5 is false as a single scan should be faster than a join query. So, best option should be
C, though 1 is not technically correct.
A correct query to achieve the task would be:
select A.customer, (
select 1 + count(*)
from account B

i-GATE, B-713, Street 22, Smriti Nagar, Bhilai- 490020, Contact 98271-62352,96440-14000
[99]
 DBMS GATE-PSUs-NET

where A.balance < B.balance

) from account A

Sol.18 Take an example:

Table enrolled
student course
abc c1
xyz c1
abc c2
pqr c1
Table paid
student amount
abc 20000
xyz 10000
rst 10000
Output of Query 1
abc
abc
xyz
Output of Query 2
abc
xyz
Output of Query 3
abc
xyz
Output of Query 4
abc
xyz
Query 1 and Query 3 may return repetitive student values as ―student‖ is not a key in relation
enrolled, however query 2 and query 4 always return same row sets.
So, option (B) is correct.
Sol.19 Answer: A
Create a table like this:
create table employee(empId int(50), name varchar(50), department int(50), salary int(50));
insert into employee values (1, 'a', 4, 90);
insert into employee values (2, 'b', 5, 30);
insert into employee values (3, 'c', 5, 50);
insert into employee values (4, 'd', 5, 80);
insert into employee values (8, 'f', 7, 10);
Q1 returns 1 for the above table.
Q2 returns empId of those employees who get salary more than the minimum salary offered in
department 5. It returns 1, 3, 4 for the above table.
According the question the answer should be 1 for the above table.

i-GATE, B-713, Street 22, Smriti Nagar, Bhilai- 490020, Contact 98271-62352,96440-14000
[100]
 DBMS GATE-PSUs-NET

PS: The question implies that the required employee must not be from department 5.

Sol.20 D:
If Select clause consist aggregate and non - aggregate columns. All non aggregate columns in the
Select clause must appear in Group By clause. But in this query Group by clause consists school-
id instead of school-name

Sol.21 {t | ∃ E ∊ Enrollment t = E.school-id  | {x | x ∊ Enrollment  x.school-id = t 

(∃ B ∊ ExamResult B.erollno = x.erollno  B.examname = x.examname  B.marks > 35)}
In this first query it is picking up tuple of the student who Enroll in some exam and who got >35
marks in that exam
{x | x ∊ Enrolment  x.school-id = t} | * 100 > 35}
in second part of the query t is tuples of first query and x is their enrollment and enrollment >35%
So, the query returns the tuples where 35% students enrolled and all of them got >35 marks in
some exam
(B) division will pick 35% enrollment of the student in some exams

Sol.22 X = 1, Y = 1
X = 2, Y = 2 × 1 + 1 = 3
X = 3, Y = 2 × 3 + 1 = 7
X = 4, Y = 2 × 7 + 1 = 15
X = 5, Y = 2 × 15 + 1 = 31
X = 6, Y = 2 × 31 + 1 = 63
X = 7, Y = 2 × 63 + 1 = 127

Sol.23 The answer is (C).

When we perform the natural join on S and T then result will be like this
Borrower Bank_Manager Loan_Amount
Ramesh Sunderajan 10000.00
Ramesh Sunderajan 7000.00
Suresh Ramgopal 5000.00
Mahesh Sunderajan 10000.00
Mahesh Sunderajan 7000.00
After that count (*) will count total tuples present in this table so here it is 5.

Sol.24 Answer key is (C) Q and R are true.

But correct answer should be B.
When group by is not present, having is applied to the whole table "A grouped table is a set of
groups derived during the evaluation of a <group by clause> or a <having clause>. A group is a
multiset of rows in which all values of the grouping column or columns are equal if a <group by
clause> is specified, or the group is the entire table if no <group by clause> is specified. A
grouped table may be considered as a collection of tables. Set functions may operate on the
individual tables within the grouped table."

i-GATE, B-713, Street 22, Smriti Nagar, Bhilai- 490020, Contact 98271-62352,96440-14000
[101]
 DBMS GATE-PSUs-NET

Sol.25 For C.ID = 10, all tuples from A∪B satisfies the join condition, hence 5 tuples (union of A and B
has only 5 tuples are 2 of them are repeating for Shreya and Rohit) will be returned. Now, for
C.ID = 99, A.ID = 99 and A.ID = 98 (for A.ID = 98, we need to assume A ∪ B, has the same
schema s A as told in the question) satisfies the condition A.ID > 40, and hence two tuples
are returned. So, number of tuples = 5 + 2 = 7.
The output will be:

Id Name Age Id Phone Area

12 Arun 60 10 2200 02
15 Shreya 24 10 2200 02
99 Rohit 11 10 2200 02
25 Hari 40 10 2200 02
98 Rohit 20 10 2200 02
99 Rohit 11 99 2100 01
98 Rohit 20 99 2100 01

Sol.26 <cond> ALL evaluates to TRUE if inner query returns no tuples. So, Number of tuples returned
will be number of tuples in A = 3.

Sol.27 SELECT dept-id, MAX(hire-date)

FROM employees JOIN departments USING(dept-id)
WHERE location-id = 1700
GROUP BY dept-id
This inner query will give the max hire date of each department whose location_id = 1700 and
outer query will give the last name and hire-date of all those employees who joined on max hire
date.
answer should come to (B) no errors.
And we can use group by and where together, who said we cannot :(
Example: create table departments(dept_id number, dept_name varchar2(25), location_id
number);
Query: select d1.dept_name,max(d1.location_id)
from departments d1, departments d2
where d1.dept_name = d2.dept_name
and d1.dept_name='A'
group by d1.dept_name;
will give output.

Sol.28 C
Consider the following instances of R and S
R S
A B C A X Z

i-GATE, B-713, Street 22, Smriti Nagar, Bhilai- 490020, Contact 98271-62352,96440-14000
[102]
 DBMS GATE-PSUs-NET

1 2 3 1 2 3
1 2 3 3 5 7
7 8 9 7 6 5
7 8 9 7 6 5

Now output of given query

select * from R where a in (select S.a from S)
∴ Output will be
A B C
1 2 3
1 2 3
7 8 9
7 8 9
7 8 9
7 8 9
(B)
select distinct R.* from R, S where R.a = S.a
∵ only Distinct R will be chosen in the end so, output will be
A B C
1 2 3
7 8 9

(C) ANSWER
select R.* from R,(select distinct a from S) as S1 where R.a = S1.a
Multiplicity of tuples is maintained.
∵ Multiplicity of duplicate tuples will be distributed when there is a match between R.a and S.a
and for that match S.a‘s value is repeated.
So, Output will be
A B C
1 2 3
1 2 3
7 8 9
7 8 9

Sol.29 (A) πA1(σ(F1∧F2)(r))

since A1 is subset of A2 will get only A1 attributes as it is in the outside, so we can remove
project A2. Two Selects with Boolean expression can be combined into one select with And of
two Boolean expressions.

i-GATE, B-713, Street 22, Smriti Nagar, Bhilai- 490020, Contact 98271-62352,96440-14000
[103]
 DBMS GATE-PSUs-NET

Sol.30 If any employee has received rating other than 'GOOD' from any of their customers, then there
will be some rows returned by the inner query; And NOT EXISTS will return false so those
employees won't be printed. Only those employees which have got rating 'GOOD' from all of their
customers will be printed.

Sol.31 Below is result of given query. Note that there are only two student names and query prints
sum(P.Marks) for every student.
Student_Name Marks
Raj 310
Rohit 140
Total 2 rows

Sol.32 Option D is correct because SELECT operation in SQL is equivalent to The projection operation
in relational algebra, except that SELECT in SQL retains duplicates but projection gives only
distinct.

Sol.33 A is the answer

B - Returns the addresses of all theaters.
C - Returns null set. max() returns a single value and there won't be any value > max.
D - Returns null set. Same reason as C. All and ANY works the same here as max returns a single
value.

Sol.34 First group by district name is performed and total capacities obtained as following
Ajmer 20
Bikaner 40
Charu 30
Dungargarh 10
Then average capacity is computed,
Average Capacity = (20 + 40 + 30 + 10)/4
= 100/4
= 25.
Finally districts with more than average are selected.
Bikaner is 40 which is greater than average (25)
Charu is 30 which is also greater than average (25).
Therefore answer is 2 tuples.

Sol.35 ALL (EMPTY SET) always returns TRUE. So first where condition is always satisfied.
Second where condition will return all those rows who have more goals than ANY German
player. Since, minimum goals by a German is 10, all the rows which are greater than 10 Goals will
be returned.
I.e. first 7 rows in the table.
Hence, answer: 7

i-GATE, B-713, Street 22, Smriti Nagar, Bhilai- 490020, Contact 98271-62352,96440-14000
[104]
 DBMS GATE-PSUs-NET

Sol.36 Output of Query will be:

DeptName Number
AA 4
AB 3
AC 3
AD 2
AE 1
4 + 3 + 3 + 2 + 1 = 13 / 5 = 2.6

Sol.37 Answer is D.
Since the full-outer join is nothing but a combination of inner-join and the remaining tuples of
both the tables that couldn't satisfy the common attributes' equality condition, and merging them
with "null" values.

i-GATE, B-713, Street 22, Smriti Nagar, Bhilai- 490020, Contact 98271-62352,96440-14000
[105]
 DBMS GATE-PSUs-NET

GATE Previous Year’s Questions

TRANSACTIONS & CONCURRENCY CONTROL
Q.1 For the schedule given below, which of the following is correct: [GATE 1999]
1 Read A
2 Read B
3 Write A
4 Read A
5 Write A
6 Write B
7 Read B
8 Write B
(A) This schedule is serializable and can occur in a scheme using 2PL protocol
(B) This schedule is serializable but cannot occur in a scheme using 2PL protocol
(C) This schedule is not serializable but can occur in a scheme using 2PL protocol
(D) This schedule is not serializable and cannot occur in a scheme using 2PL protocol

Q.2 Which of the following scenarios may lead to an irrecoverable error in a database system?
(A) A transaction writes a data item after it is read by an uncommitted transaction
(B) A transaction reads a data item after it is read by an uncommitted transaction
(C) A transaction reads a data item after it is written by a committed transaction
(D) A transaction reads a data item after it is written by an uncommitted transaction
[GATE 2003]

Q.3 Consider three data items D1, D2 and D3 and the following execution schedule of transactions T1,
T2 and T3. In the diagram, R(D) and W(D) denote the actions reading and writing the data item D
respectively. [GATE 2003]

Which of the following statements is correct?

(A) The schedule is serializable as T2; T3; T1(B) The schedule is serializable as T2; T1; T3
(C) The schedule is serializable as T3; T2; T1(D) The schedule is not serializable

Q.4 Which level of locking provides the highest degree of concurrency in a relational database?
(A) Page [GATE 2004]
(B) Table

i-GATE, B-713, Street 22, Smriti Nagar, Bhilai- 490020, Contact 98271-62352,96440-14000
[106]
 DBMS GATE-PSUs-NET

(C) Row
(D) Page, table and row level locking allow the same degree of concurrency

Q.5 Consider the following schedule S of transactions T1 and T2: [GATE 2004]
T1 T2
Read(A)
A = A – 10
Read (A)
Temp = 0.2*A
Write(A)
Read(B)
Write(A)
Read(B)
B = B + 10
Write(B)
B = B + Temp
Write (B)

Which of the following is TRUE about the schedule S?

(A) S is serializable only as T1, T2
(B) S is serializable only as T2, T1
(C) S is serializable both as T1, T2 and T2, T1
(D) S is not serializable either as T1, T2 or as T2, T1

Q.6 Amongst the ACID properties of a transaction, the 'Durability' property requires that the changes
made to the database by a successful transaction persist [GATE 2005]
(A) Except in case of an Operating System crash
(B) Except in case of a Disk crash
(C) Except in case of a power failure
(D) Always, even if there is a failure of any kind

Q.7 Consider the following log sequence of two transactions on a bank account, with initial balance
12000, that transfer 2000 to a mortgage payment and then apply a 5% interest.
1. T1: start [GATE 2006]
2. T1: B old = 1200, new = 10000
3. T1: M old = 0, new = 2000
4. T1: commit
5. T2: start
6. T2: B old = 10000 new = 10500
7. T2: commit
Suppose the database system crashes just before log record 7 is written. When the system is
restarted, which one statement is true of the recovery procedure?
(A) We must redo log record 6 to set B to 10500
(B) We must undo log record 6 to set B to 10000 and then redo log records 2 and 3

i-GATE, B-713, Street 22, Smriti Nagar, Bhilai- 490020, Contact 98271-62352,96440-14000
[107]
 DBMS GATE-PSUs-NET

(C) We need not redo log records 2 and 3 because transaction T1 has committed
(D) We can apply redo and undo operations in arbitrary order because they are idempotent

Q.8 Consider the following schedules involving two transactions. Which one of the following
statements is TRUE? [GATE 2007]
S1: r1(X); r1(Y); r2(X); r2(Y); w2(Y); w1(X)
S2: r1(X); r2(X); r2(Y); w2(Y); r1(Y); w1(X)
(A) Both S1 and S2 are conflict serializable.
(B) S1 is conflict serializable and S2 is not conflict serializable.
(C) S1 is not conflict serializable and S2 is conflict serializable.
(D) Both S1 and S2 are not conflict serializable.

Q.9 Consider the following two transactions: T1 and T2.

T1 : read (A); T2 : read (B);
read (B); read (A);
if A = 0 then B ← B + 1; if B ≠ 0 then A ← A – 1;
write (B); write (A);
Which of the following schemes, using shared and exclusive locks, satisfy the requirements for
strict two phase locking for the above transactions?
(A) S1 : S2 : (B) S1 : S2 :
lock S(A); lock S(B); lock X(A); lock X(B);
read (A); read (B); read (A); read (B);
lock S(B); lock S(A); lock X(B); lock X(A);
read (B); read (A); read (B); read (A);
if A = 0 if B ≠ 0 if A = 0 if B ≠ 0
then B ← B + 1; then A ← A – 1; then B ← B + 1; then A ← A – 1;
write (B); write (A); write (B); write (A);
commit; commit; unlock (A); unlock (A);
unlock (A); unlock (B); commit; commit;
unlock (B); unlock (A); unlock (B); unlock (A);
(C) S1 : S2 : (C) S1 : S2 :
lock S(A); lock S(B); lock S(A); lock S(B);
read (A); read (B); read (A); read (B);
lock X(B); lock X(A); lock X(B); lock X(A);
read (B); read (A); read (B); read (A);
if A = 0 if B ≠ 0 if A = 0 if B ≠ 0
then B ← B + 1; then A ← A – 1; then B ← B + 1; then A ← A – 1;
write (B); write (A); write (B); write (A);
unlock (A); unlock (B); unlock (A); unlock (A);
commit; commit; unlock (B); unlock (B);
unlock (B); unlock (A); commit; commit;

i-GATE, B-713, Street 22, Smriti Nagar, Bhilai- 490020, Contact 98271-62352,96440-14000
[108]
 DBMS GATE-PSUs-NET

Q.10 Consider the following three schedules of transactions T1, T2 and T3. [Notation: In the following
NYO represents the action Y (R for read, W for write) performed by transaction N on object O.]
S1: 2RA 2WA 3RC 2WB 3WA 3WC 1RA 1RB 1WA 1WB
S2: 3RC 2RA 2WA 2WB 3WB 1RA 1RB 1WA 1WB 3WC
S3: 2RA 3RC 3WA 2WA 2WB 3WC 1RA 1RB 1WA 1WB
Which of the following statements is TRUE? [GATE 2008]
(A) S1, S2 and S3 are all conflict equivalent to each other
(B) No two of S1, S2 and S3 are conflict equivalent to each other
(C) S2 is conflict equivalent to S3, but not to S1
(D) S1 is conflict equivalent to S2, but not to S3

Q.11 Consider two transactions T1 and T2, and four schedules S1, S2, S3, S4, of T1 and T2 as given
below: [GATE 2009]
T1: R1[x] W1[x] W1[y]
T2: R2[x] R2[y] W2[y]
S1: R1[x] R2[x] R2[y] W1[x] W1[y] W2[y]
S2: R1[x] R2[x] R2[y] W1[x] W2[y] W1[y]
S3: R1[x] W1[x] R2[x] W1[y] R2[y] W2[y]
S4: R2[x] R2[y] R1[x] W1[x] W1[y] W2[y]
Which of the above schedules are conflict-serializable?
(A) S1 and S2 (B) S2 and S3 (C) S3 only (D) S4 only

Q.12 Which of the following concurrency control protocols ensure both conflict serialzability and
freedom from deadlock? [GATE 2010]
I. 2-phase locking II. Time-stamp ordering
(A) I only (B) II only (C) Both I and II (D) Neither I nor II

Q.13 Consider the following schedule for transactions T1, T2 and T3: [GATE 2010]
T1 T2 T3
Read(X)
Read (Y)
Read (Y)
Write (Y)
Write (X)
Write (X)
Read (X)
Write (X)
Which one of the schedules below is the correct serialization of the above?
(A) T1→T3→T2 (B) T2→T1→T3 (C) T2→T3→T1 (D) T3→T1→T2

Q.14 Consider the following transactions with data items P and Q initialized to zero:
T1: read (P) ; T2: read (Q) ; [GATE 2012]
read (Q) ; read (P) ;

i-GATE, B-713, Street 22, Smriti Nagar, Bhilai- 490020, Contact 98271-62352,96440-14000
[109]
 DBMS GATE-PSUs-NET

if P = 0 then Q : = Q + 1 ; if Q = 0 then P : = P + 1 ;
write (Q) ; write (P) ;
Any non-serial interleaving of T1 and T2 for concurrent execution leads to
(A) a serializable schedule
(B) a schedule that is not conflict serializable
(C) a conflict serializable schedule
(D) a schedule for which a precedence graph cannot be drawn

Q.15 An index is clustered, if [GATE 2013]

(A) It is on a set of fields that form a candidate key
(B) It is on a set of fields that include the primary key
(C) The data records of the file are organized in the same order as the data entries of the index
(D) The data records of the file are organized not in the same order as the data entries of the index

Q.16 Consider the following four schedules due to three transactions (indicated by the subscript)
using read and write on a data item x, denoted by r(x) and w(x) respectively. Which one of them is
conflict serializable? [GATE 2014]
(A) r1(x); r2(x); w1(x); r3(x); w2(x); (B) r2(x); r1(x); w2(x); r3(x); w1(x);
(C) r3(x); r2(x); r1(x); w2(x); w1(x); (D) r2(x); w2(x); r3(x); r1(x); w1(x);

Q.17 Consider the following schedule S of transactions T1, T2, T3, T4: [GATE 2014]
T1 T2 T3 T4
Reads (X)
Writes (X)
Commit
Writes (X)
Commit
Writes (Y)
Reads (Z)
commit
Reads (X)
Reads (Y)
Commit

Which one of the following statements is CORRECT?

(A) S is conflict-serializable but not recoverable
(B) S is not conflict-serializable but is recoverable
(C) S is both conflict-serializable and recoverable
(D) S is neither conflict-serializable not is it recoverable

Q.18 Consider the transactions T1, T2 and T3 and the schedules S1and S2 given below.
T1: r1(X); r1(Z); w1(X); w1(Z) [GATE 2014]
T2: r2(Y); r2(Z); w2(Z)

i-GATE, B-713, Street 22, Smriti Nagar, Bhilai- 490020, Contact 98271-62352,96440-14000
[110]
 DBMS GATE-PSUs-NET

T3: r3(Y); r3(X); w3(Y)

S1: r1(X); r3(Y); r3(X); r2(Y); r2(Z); w3(Y); w2(Z); r1(Z); w1(X); w1(Z)
S2: r1(X); r3(Y); r2(Y); r3(X); r1(Z); r2(Z); w3(Y); w1(X); w2(Z); w1(Z)
Which one of the following statements about the schedules is TRUE?
(A) Only S1 is conflict-serializable (B) Only S2 is conflict-serializable
(C) Both S1 and S2 are conflict-serializable (D) Neither S1 nor S2 is conflict-serializable

Q.19 Consider the following transaction involving two bank accounts x and y.
read(x); x: = x – 50; write (x); read(y); y: = y + 50; write(y) [GATE 2015]
The constraint that the sum of the accounts x and y should remain constant is that of
(A) Atomicity (B) Consistency (C) Isolation (D) Durability

Q.20 Consider a simple check pointing protocol and the following set of operations in the log.
(start, T4); (write, T4, y, 2, 3); (start, T1); (commit, T4); (write, T1, z, 5, 7); (checkpoint);
(start, T2); (write, T2, x, 1, 9); (commit, T2); (start, T3); (write, T3, z, 7, 2);
If a crash happens now and the system tries to recover using both undo and redo operations, what
are the contents of the undo list and the redo list? [GATE 2015]
(A) Undo: T3, T1; Redo: T2 (B) Undo: T3, T1; Redo: T2, T4
(C) Undo: none; Redo: T2, T4, T3, T1 (D) Undo: T3, T1, T4; Redo: T2

Q.21 Consider the following partial Schedule S involving two transactions T1 and T2. Only
the read and the write operations have been shown. The read operation on data item P is denoted
by read(P) and write operation on data item P is denoted by write(P). [GATE 2015]

Suppose that the transaction T1 fails immediately after time instance 9. Which one of the
following statements is correct?
(A) T2 must be aborted and then both T1 and T2 must be re-started to ensure transaction atomicity
(B) Schedule S is non-recoverable and cannot ensure transaction atomicity
(C) Only T2 must be aborted and then re-started to ensure transaction atomicity
(D) Schedule S is recoverable and can ensure transaction atomicity and nothing else needs to be
done

Q.22 Consider the following directed graph: [GATE 2016]

i-GATE, B-713, Street 22, Smriti Nagar, Bhilai- 490020, Contact 98271-62352,96440-14000
[111]
 DBMS GATE-PSUs-NET

The number of different topological orderings of the vertices of the graph is _____________.

Q.23 Which one of the following is NOT a part of the ACID properties of database transactions?
(A) Atomicity (B) Consistency (C) Isolation (D) Deadlock-freedom
[GATE 2016]

Q.24 Consider the following two phase locking protocol. Suppose a transaction T accesses (for read or
write operations), a certain set of objects {O1,…,Ok}. This is done in the following manner:
Step 1. T acquires exclusive locks to O1, . . . , Ok in increasing order of their addresses.
Step 2. The required operations are performed.
Step 3. All locks are released.
This protocol will [GATE 2016]
(A) guarantee serializability and deadlock-freedom
(B) guarantee neither serializability nor deadlock-freedom
(C) guarantee serializability but not deadlock-freedom
(D) guarantee deadlock-freedom but not serializability

Q.25 Suppose a database schedule S involves transactions T1, ….Tn. Construct the precedence graph of
S with vertices representing the transactions and edges representing the conflicts. If S is
serializable, which one of the following orderings of the vertices of the precedence graph is
guaranteed to yield a serial schedule? [GATE 2016]
(A) Topological order (B) Depth-first order
(C) Breadth-first order (D) Ascending order of transaction indices

Q.26 Consider the following database schedule with two transactions T1 and T2.
S = r2(X); r1(X); r2(Y); w1(X); r1(Y); w2(X); a1; a2 [GATE 2017]
Where ri(Z) denotes a read operation by transaction Ti on a variable Z, wi(Z) denotes a write
operation by Ti on a variable Z and ai denotes an abort by transaction Ti.
Which one of the following statements about the above schedule is TRUE?
(A) S is non-recoverable (B) S is recoverable, but has a cascading abort
(C) S does not have a cascading abort (D) S is strict

Q.27 Consider the following tables T1 and T2.

T1 T2
P Q R S
2 2 2 2

i-GATE, B-713, Street 22, Smriti Nagar, Bhilai- 490020, Contact 98271-62352,96440-14000
[112]
 DBMS GATE-PSUs-NET

3 8 8 3
7 3 3 2
5 8 9 7
6 9 5 7
8 5 7 2
9 8

In table T1, P is the primary key and Q is the foreign key referencing R in table T2 with on-delete
cascade and on-update cascade. In table T2, R is the primary key and S is the foreign key
referencing P in table T1 with on-delete set NULL and on-update cascade. In order to delete
record ⟨3, 8⟩ from the table T1, the number of additional records that need to be deleted from
table T1 is _______ [GATE 2017]

Q.28 In a database system, unique time stamps are assigned to each transaction using Lamport‘s logical
clock. Let TS(T1) and TS(T2) be the time stamps of transactions T1 and T2 respectively. Besides,
T1 holds a lock on the resource R, and T1 has requested a conflicting lock on the same resource R.
The following algorithm is used to prevent deadlocks in the database assuming that a killed
transaction is restarted with the same timestamp. [GATE 2017]
if TS(T2) <TS(T1) then
T1 is killed
else T2 waits.
Assume any transactions that is not killed terminates eventually. Which of the following is TRUE
about the database system that uses the above algorithm to prevent deadlocks?
(A) The database system is both deadlock-free and starvation- free.
(B) The database system is deadlock- free, but not starvation-free.
(C) The database system is starvation-free but not deadlock- free.
(D) The database system is neither deadlock- free nor starvation-free.

ANSWER KEY
1. (D) 2. (D) 3. (D) 4. (C) 5. (D) 6. (D) 7. (C)
8. (C) 9. (C) 10. (D) 11. (B) 12. (B) 13. (A) 14. (B)
15. (C) 16. (D) 17. (C) 18. (A) 19. (B) 20. (A) 21. (B)
22. (6) 23. (D) 24. (A) 25. (A) 26. (C) 27. (0) 28. (A)
SOLUTION
Sol.1 Precedence graph of this given schedule is cyclic hence, this schedule is not CSS hence not
allowed by 2PL (contra positive)
This schedule is not even serializable because
if T1->T2 we'll lose Last Updated by T1 on item B
if T2->T1 we'll lose initial value of A read by T1
Hence (D) is correct choice

Sol.2 Option D

i-GATE, B-713, Street 22, Smriti Nagar, Bhilai- 490020, Contact 98271-62352,96440-14000
[113]
 DBMS GATE-PSUs-NET

(A) Here if transaction writing data commits, then transaction which read the data might get
phantom tuple/ Unrepeatable error. Though there is no irrecoverable error possible even in this
option.
(B) This is non issue. Both transaction reading data.
(C) This is non issue.
(D) This is dirty read. In case if transaction reading uncommitted data commits, irrecoverable error
occurs of uncommitted transaction fails. So (D) is answer

Sol.3 There is a cycle in precedence graph so schedule is not conflict serialisable.

Check View Serializability:
Checking View Serializability is NPC problem so proving by contradiction.
1. Initial Read
T2 read D2 value from initial database and T1 modify D2 so T2 should execute before T1.
i.e., T2→T1
2. Final write.
final write of D1 in given schedule done by T2 and T1 modify D1 i.e. W(D1).
that means T2 should execute after T1.
i.e., T1→T2
So, schedule not even View Serializable.
Not Serializable.

Sol.4 Row level locking provides more concurrency, because different transactions can access different
rows in a table / page at same time,

Sol.5 There is a cycle in the precedence graph - so the given schedule is not Conflict Serializable.
If a schedule is view serializable but not conflict serializable it MUST have one or more blind
writes. Here, there is no blind writes. So, the given schedule is not even view serializable.
Option D is the Answer.

Sol.6 Answer D. Irrespective of any failure the successful result of transaction should persist.
Suppose we book ticket 2 months in advance in irctc and transaction success. Then when we are
going to board the train on that time they tells because of system/disk/power crash they don‘t have
your seat information and you are not allowed in the seat. it is a serious problem. hence result
should persist irrespective of all crashes.
Sol.7 Answer should be B. Here we are not using checkpoints so, redo log records 2 and 3 and undo log
record 6.
Consider the following steps taken from the book 'Navathe':
PROCEDURE RIU_M
1. Use two lists of transactions maintained by the system: the committed transactions since the
last checkpoint and the active transactions
2. Undo all the write_item operations of the active(uncommitted) transaction, using the UNDO
procedure. The operations should be undone in the reverse order in which they were written
into the log.

i-GATE, B-713, Street 22, Smriti Nagar, Bhilai- 490020, Contact 98271-62352,96440-14000
[114]
 DBMS GATE-PSUs-NET

3. Redo all the write_item operations of the committed transactions from the log, in the order in
which they were written into the log.

Sol.8 For S1: it is not conflict serializable

for S2: it is conflict serializable

Answer is option C.

Sol.9 Answer is (C).

Many of you would point a DEADLOCK and I won't deny But see Question just asks for
requirement to follow Strict 2PL. Requirement are
1. Exclusive locks should be released after the commit.
2. No Locking can be done after the first Unlock and vice versa.
In 2PL deadlock may occur BUT it may be that it doesn't occur at all.
Consider that in option (C) if both execute in serial order without concurrency. Then that is
perfectly valid and YES it follows Strict 2PL.

Sol.10 Though answer is (D) but it seems that it's a miss printing in schedule (S3) because being conflict
equivalent there should same operations on same data items. First operation in schedule (S3)
should be 2RA. Furthermore, if it's 2RA in S3 then S3 is not even Conflict Serializable schedule.

Sol.11 The answer is B.

 S1 has a cycle from T1 → T2 and T2 → T1
 S2 It is uni-directional and has only T2 → T1
 S3 It is uni-directional and has only T1 → T2
 S4 same as S1
A schedule is conflict serializable if there is no cycle in the directed graph made by the schedules.
In the schedules we check for RW, WR, WW conflicts between the schedules and only these
conflicts contribute in the edges of the graph.

Sol.12 In basic two phase locking there is a chance for deadlock

Conservative 2PL is deadlock free
Option B.

i-GATE, B-713, Street 22, Smriti Nagar, Bhilai- 490020, Contact 98271-62352,96440-14000
[115]
 DBMS GATE-PSUs-NET

Sol.13 Answer is option A.

create precedence graph and apply Topological sort on it to obtain
T1 → T3 → T2

Sol.14 Answer is (B). Explanation: T1: r(P), r(Q), w(Q) T2: r(Q), r(P), w(P) now, consider any non serial
schedule for example, S: r1(P), r2(Q), r1(Q), r2(P), w1(Q), w2(P) now, draw a precedence graph
for this schedule. Here there is a conflict from T1−>T2 and there is a conflict from T2−>T1
therefore, the graph will contain a cycle. So we can say that the schedule is not conflict
serializable.

Sol.15 Answer is (C).

Index can be created using any column or combination of column which need not be unique.
So, A, B are not the answers.
Indexed column is used to sort rows of table. Whole data record of file is sorted using index
so, C is correct option. (Simple video explains this).

Sol.16 (D) make precedence graph for all the options, for option (D) only graph will be acyclic, hence
(D) is CSS.

Sol.17 Answer: S is both conflict serializable and recoverable.

Recoverable? Look if there are any dirty reads? Since there are no dirty read, it simply implies
schedule is recoverable (if there were dirty read, then we would have taken into consideration the
order in which transactions commit)
Conflict serializable? Draw the precedence graph (make edges if there is a conflict instruction
among Ti and Tj. But for the given schedule, no cycle exists in precedence graph, thus it's conflict
serializable.
Sol.18

S1 has no cycle hence, Conflict-Serializable

S2 has cycle hence NOT Conflict-Serializable
Answer is option A.

i-GATE, B-713, Street 22, Smriti Nagar, Bhilai- 490020, Contact 98271-62352,96440-14000
[116]
 DBMS GATE-PSUs-NET

Sol.19 Consistency
In the given transaction Atomicity guarantees that the said constraint is satisfied. But this
constraint is not part of Atomicity property. It is just that Atomicity implies Consistency here.

Sol.20
T1 T2 T3 T4
Start
w (y, 2, 3)
start
commit
w (z, 5, 7)
checkpoint checkpoint checkpoint checkpoint
start
w (x, 1, 9)
commit
start
w (z, 7, 2)
crash crash crash crash
Now from the table we can find that T1 and T3 has uncommitted write operation, so they must be
undone. Even though T2 has committed after writing, but it is after checkpoint. So, it needs to be
redone.
Answer is A.

Sol.21 The correct option is B.

Why A is not correct because it says abort transaction T2 and then redo all the operations.
But is there a guarantee that it will succeed this time?(no maybe again T1 will fail).
Now as to why b is correct because as the other answer points out it is by definition an
irrecoverable schedule now even if we start to undo the actions on by one (after t1 fails) in order
to ensure transaction atomicity. Still we cannot undo a committed transaction. Hence, this
schedule is unrecoverable by definition and also not atomic since it leaves the data base in an
inconsistent state.
Sol.22 Following are different 6 Topological Sortings
a-b-c-d-e-f
a-d-e-b-c-f
a-b-d-c-e-f
a-d-b-c-e-f
a-b-d-e-c-f
a-d-b-e-c-f

Sol.23 A - Atomicity
C - Consistency
I - Isolation

i-GATE, B-713, Street 22, Smriti Nagar, Bhilai- 490020, Contact 98271-62352,96440-14000
[117]
 DBMS GATE-PSUs-NET

D - Durability.
Answer (D)

Sol.24 Two Phase Locking protocol is conflict serializable. So this is a modified version of the basic 2PL
protocol, So serializabilty should be guaranteed. and we can get a serializable scheduling by
ordering based on Lock points(same as in basic 2PL)
Now in Step 1, exclusive locks are aquired to O1, O2, O3 ……. in increasing order of addresses.
since it is mentioned as exclusive lock, only one transaction can lock the object.
Due to acquiring of locks based on ordering of addresses, and locks aren't released until the
transaction completes its operation. We can prevent the circular wait condition, and hence making
it deadlock free.
So, the answer should be (A) guarantees serializability and deadlock freedom

Sol.25 Option A
Cycle in precedence graph tells that schedule is not conflict serializable. DFS and BFS traversal of
graph are possible even if graph contains cycle. And hence DFS and BFS are also possible for non
serializable graphs. But Topological sort of any cyclic graph is not possible. Thus topological sort
guarantees graph to be serializable. Option D is not valid because in a transaction with more
indices might have to come before lower one. Also two non- conflicting schedule can occur
simultaneously.

Sol.26

As we can see in figure,

 T2 overwrites a value that T1 writes
 T1 aborts: its ―remembered‖ values are restored.
 Cascading Abort could have raised if – > Abort of T1 required abort of T2 but as T2 is
already aborted , its not a cascade abort. Therefore, Option C
Option A – is not true because the given schedule is recoverable
Option B – is not true as it is recoverable and avoid cascading aborts;
Option D – is not true because T2 is also doing abort operation after T1 does, so NOT strict.

Sol.27 As Q refers to R so, deleting 8 from Q won't be an issue, however S refers P. But as the
relationship given is on delete set NULL, 3 will be deleted from T1 and the entry in T2 having 3
in column S will be set to NULL. So, no more deletions. Answer is 0.

i-GATE, B-713, Street 22, Smriti Nagar, Bhilai- 490020, Contact 98271-62352,96440-14000
[118]
 DBMS GATE-PSUs-NET

Sol.28 Given,
if TS(T2) < TS(T1) then
T1 is killed
else T2 waits.
T1 holds a lock on the resource R
T2 has requested a conflicting lock on the same resource R
According to algo, TS(T2) < TS(T1) then T1 is killed else T2 will wait. So in both cases neither
deadlock will happen nor starvation.
Therefore, option A is correct

i-GATE, B-713, Street 22, Smriti Nagar, Bhilai- 490020, Contact 98271-62352,96440-14000
[119]
 DBMS GATE-PSUs-NET

TIFR Previous Year’s Questions

SQL & RELATIONAL ALZEBRA
Q.1 In a relational database there are three relations: [TIFR 2010]
 Customers = C (C Name)
 Shops = S (S Name)
 Buys = B (C Name, S Name)
Then the Relational Algebra expression (Π is the projection operator).
C − ΠCName((C × S) − B)
returns the names of
(A) Customers who buy from at least one shop
(B) Customers who buy from at least two shops
(C) Customers who buy from all shops.
(D) Customers who do not buy anything at all
(E) None of the above

Q.2 In a relational database there are three relations: [TIFR 2010]

 Customers = C (C Name)
 Shops = S (S Name)
 Buys = B (C Name, S Name)
Which of the following relational algebra expression returns the names of shop that have no
customers at all?
[Here Π is the projection operator].
(A) ΠSNameB (B) S – B (C) S – ΠSNameB (D) S – ΠSName((C × S) – B)
(E) None of the above

ANSWER KEY
1. (C) 2. (C)

SOLUTION
Sol.1 It is division in relational algebra
Division = πAB(R)/πB(S) Results in 'A' values for which here should be 'B' in R for every 'B' of S.
πAB(R)/πB(S) = ΠA(R) − πA(πA(R) × S − R) Retrieve all A's who are related to every B
C − ΠCName((C × S) − B)
C × S gives the complete relation of each customer to every shop
(C × S) − B): gives the relation of the customer which is not related to every shop.
ΠCName((C × S) − B): gives the customer name who is not related to every shop.
C − ΠCName((C × S) − B): gives the customer who is related to every shop.
Option (C) Customers who buy from all shops.

i-GATE, B-713, Street 22, Smriti Nagar, Bhilai- 490020, Contact 98271-62352,96440-14000
[120]