Gate DBMS

3 Databases (243)
ER‐model. Relational model:Relational algebra, Tuple calculus, SQL. Integrity constraints, Normal forms. File organization,
Indexing (e.g., B and B+ trees). Transactions and concurrency control.
Mark Distribution in Previous GATE

Year 2021-1 2021-2 2020 2019 2018 2017-1 2017-2 2016-1 2016-2 Minimum Average Maximum
1 Mark Count 2 1 2 2 2 2 2 3 2 1 2 3
2 Marks Count 3 3 3 3 2 3 3 1 2 1 2.5 3
Total Marks 8 7 8 8 6 8 8 5 6 6 7.1 8
3.1 B Tree (28) top☝
3.1.1 B Tree: GATE CSE 1989 | Question: 12a top☝ ☛ https://gateoverflow.in/91199
The below figure shows a B+ tree where only key values are indicated in the records. Each block can hold upto three records.
A record with a key value 34 is inserted into the B+ tree. Obtain the modified B+ tree after insertion.
descriptive gate1989 databases b-tree
Answer ☟
Consider B+ - tree of order d shown in figure. (A B+ - tree of order d contains between d and 2d keys in each node)
Draw the resulting B+ - tree after 100 is inserted in the figure below.
gate1994 databases b-tree normal descriptive
Answer ☟
3.1.3 B Tree: GATE CSE 1994 | Question: 14b top☝ ☛ https://gateoverflow.in/360163
For a B+ - tree of order d with n leaf nodes, the number of nodes accessed during a search is O(_).
Answer ☟
3.1.4 B Tree: GATE CSE 1997 | Question: 19 top☝ ☛ https://gateoverflow.in/2279
A B+ - tree of order d is a tree in which each internal node has between d and 2d key values. An internal node with M key
values has M + 1 children. The root (if it is an internal node) has between 1 and 2d key values. The distance of a node from the
root is the length of the path from the root to the node. All leaves are at the same distance from the root. The height of the tree is the
distance of a leaf from the root.
+
© Copyright GATE Overflow. Some rights reserved.

A. What is the total number of key values in the internal nodes of a B+ -tree with l leaves (l ≥ 2)?
B. What is the maximum number of internal nodes in a B+ - tree of order 4 with 52 leaves?
C. What is the minimum number of leaves in a B+ -tree of order d and height h(h ≥ 1) ?
Answer ☟
3.1.5 B Tree: GATE CSE 1999 | Question: 1.25 top☝ ☛ https://gateoverflow.in/1478
Which of the following is correct?
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.
gate1999 databases b-tree normal
Answer ☟
Consider a B-tree with degree m, that is, the number of children, c, of any internal node (except the root) is such that
m ≤ c ≤ 2m − 1 . Derive the maximum and minimum number of records in the leaf nodes for such a B-tree with height
h, h ≥ 1.( Assume that the root of a tree is at height 0).
Answer ☟
3.1.7 B Tree: GATE CSE 2000 | Question: 1.22, UGCNET-June2012-II: 11 top☝ ☛ https://gateoverflow.in/646
B+ -trees are preferred to binary trees in databases because
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
gate2000-cse databases b-tree normal ugcnetjune2012ii
Answer ☟
(a) Suppose you are given an empty B+ tree where each node (leaf and internal) can store up to 5 key values. Suppose values
1, 2, … 10 are inserted, in order, into the tree. Show the tree pictorially
i. after 6 insertions, and

ii. after all 10 insertions
Do NOT show intermediate stages.

(b) Suppose instead of splitting a node when it is full, we try to move a value to the left sibling. If there is no left sibling, or the
left sibling is full, we split the node. Show the tree after values 1, 2, … , 9 have been inserted. Assume, as in (a) that each node can
hold up to $54 keys.
(c) In general, suppose a B+ tree node can hold a maximum of m keys,and you insert a long sequence of keys in increasing
order. Then what approximately is the average number of keys in each leaf level node.
i. in the normal case, and

ii. with the insertion as in (b).

gate2000-cse databases b-tree normal descriptive
Answer ☟
We wish to construct a B+ tree with fan-out (the number of pointers per node) equal to 3 for the following set of key values:
80, 50, 10, 70, 30, 100, 90
Assume that the tree is initially empty and the values are added in the order given.
a. Show the tree after insertion of 10, after insertion of 30, and after insertion of 90. Intermediate trees need not be shown.
b. The key values 30 and 10 are now deleted from the tree in that order show the tree after each deletion.
Answer ☟
a. The following table refers to search items for a key in B-trees and B+ trees.
B-tree B+ -tree
Successful search Unsuccessful search Successful search Unsuccessful search
X1 X2 X3 X4
A successful search means that the key exists in the database and unsuccessful means that it is not present in the database.
Each of the entries X1 , X2 , X3 and X4 can have a value of either Constant or Variable. Constant means that the search time
is the same, independent of the specific key value, where variable means that it is dependent on the specific key value chosen
for the search.
Give the correct values for the entries X1 , X2 , X3 and X4 (for example X1 = Constant,
X2 = Constant , X3 = Constant, X4 = Constant)
b. Relation R(A, B) has the following view defined on it:
CREATE VIEW V AS
(SELECT R1.A,R2.B
FROM R AS R1, R as R2
WHERE R1.B=R2.A)
i. The current contents of relation R are shown below. What are the contents of the view V ?
A B
1 2
2 3
2 4
4 5
6 7
6 8
9 10
ii. The tuples (2, 11) and (11, 6) are now inserted into R. What are the additional tuples that are inserted in V ?
Answer ☟
A B+ - tree index is to be built on the Name attribute of the relation STUDENT. Assume that all the student names are of
length 8 bytes, disk blocks are of size 512 bytes, and index pointers are of size 4 bytes. Given the scenario, what would be the best
choice of the degree (i.e. number of pointers per node) of the B+ - tree?
16

A. 16
B. 42
C. 43
D. 44
gate2002-cse databases b-tree normal ugcnetjune2012ii
Answer ☟
Consider the following 2 − 3 − 4 tree (i.e., B-tree with a minimum degree of two) in which each data item is a letter. The
usual alphabetical ordering of letters is used in constructing the tree.
What is the result of inserting G in the above tree?
A.
B.
C.
D. None of the above
gate2003-cse databases b-tree normal
Answer ☟
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?
A. 24
B. 25
C. 26
D. 27
Answer ☟
Which of the following is a key factor for preferring B+ -trees to binary search trees for indexing database relations?
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 form disks is in blocks
Answer ☟
3.1.15 B Tree: GATE CSE 2007 | Question: 63, ISRO2016-59 top☝ ☛ https://gateoverflow.in/1261
The order of a leaf node in a 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
gate2007-cse databases b-tree normal isro2016
Answer ☟
A B-tree of order 4 is built from scratch by 10 successive insertions. What is the maximum number of node splitting
operations that may take place?
A. 3
B. 4
C. 5
D. 6
Answer ☟
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
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
Answer ☟
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?
A. 1
B. 2
C. 3
D. 4

gate2010-cse databases b-tree easy
Answer ☟
3.1.19 B Tree: GATE CSE 2015 Set 2 | Question: 6 top☝ ☛ https://gateoverflow.in/8052
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 ______.
gate2015-cse-set2 databases b-tree normal numerical-answers
Answer ☟
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 ______.
gate2015-cse-set3 databases b-tree normal numerical-answers
Answer ☟
B+ Trees are considered BALANCED because.
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.
gate2016-cse-set2 databases b-tree normal
Answer ☟
In a B+ Tree , if the search-key value is 8 bytes long , the block size is 512 bytes and the pointer size is 2 B , then the
maximum order of the B+ Tree is ____
gate2017-cse-set2 databases b-tree numerical-answers normal
Answer ☟
Which one of the following statements is NOT correct about the B+ tree data structure used for creating an index of a

relational database table?
A. B+ Tree is a height-balanced tree

B. Non-leaf nodes have pointers to data records
C. Key values in each node are kept in sorted order
D. Each leaf node has a pointer to the next leaf node
gate2019-cse databases b-tree
Answer ☟
3.1.24 B Tree: GATE IT 2004 | Question: 79 top☝ ☛ https://gateoverflow.in/3723
Consider a table T in a relational database with a key field K . A B-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 PD 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
A. 20
B. 22
C. 23
D. 32
gate2004-it databases b-tree normal
Answer ☟
3.1.25 B Tree: GATE IT 2005 | Question: 23, ISRO2017-67 top☝ ☛ https://gateoverflow.in/3768
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
A. 5
B. 4
C. 3
D. 2
gate2005-it databases b-tree normal isro2017
Answer ☟
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
A. 23
B. 24
C. 34
D. 44
Answer ☟
Consider the B+ tree in the adjoining figure, where each node has at most two keys and three links.

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?
A. 1
B. 2
C. 3
D. 4
Answer ☟
Consider the B+ tree in the adjoining figure, where each node has at most two keys and three links.
Keys K15 and then K25 are inserted into this tree in that order. 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

(disregarding the links) is present in the tree.
iii. The root node remains unchanged (disregarding the links).
Which one of the following options is true?

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
Answer ☟
Answers: B Tree

B+ tree Reference.
In a B+ tree only the leaf nodes have a pointer to actual data (record pointers) whereas internal nodes points to index blocks.
In the given question we have
M : Number of pointers in internal nodes = 3.

L : Number of data items in a leaf node = 3.
Further we can see that right biasing is used while splitting a node (same key value moving to the right, in a B+ tree all
internal key values will be present in leaf node as only the leaf node actually points to the data record)
To insert 34 we’ll first place it in the sorted order among the leaf nodes.
Now, we see that the block (being the leaf node the pointers here are record pointers) having 34 is overflowing and so we’ll split
it and move the center element to the parent block. There might be a confusion as to whether 34 or 50 should move up, but if we
see the question it is following right biasing (same key value is going to the right) and so 50 must move up.
Now, we have an overflow in the internal node as the maximum capacity of an internal node is 3 block pointers but we are
having 4 here. So we must again split and move 50 upwards.
Now we have an overflow in the root node and so we must again split and move 120 upwards making a new root.
Now all the B+ tree requirements are satisfied and so the insertion algorithm terminates.
References
 0 votes -- Arjun Suresh (332k points)

For the given B+ tree, d = 2 ⟹ 2d = 4. Also right biasing is followed as 69 is to the right of 69 in the parent node.
We’ll insert 100 in the sorted position among the leaf nodes.

2d + 1 5
This causes an overflow and so the node will split into 2 by moving the element at position ⌈ ⌉ = ⌈ ⌉ = 3, which is
2 2
100. Thus we get.
This again causes an overflow at the root node and 69 needs to be moved up forming a new root. Here, 69 is not a record pointer
(only leaf nodes in B+ tree contains record pointers) and so we need not replicate it while moving up.
Now all the property of B+ tree is satisfied and the insertion algorithm terminates.
 31 votes -- Bikram (58.4k points)
3.1.3 B Tree: GATE CSE 1994 | Question: 14b top☝ ☛ https://gateoverflow.in/360163

For n leaves we have n − 1 keys in the internal node. (see 'part a' of this question)
Total keys in internal nodes = n − 1, each node can have keys between d and 2d.
For n − 1 keys there will be minimum ⌈ ⌉ internal nodes, and maximum ⌈ ⌉

n−1 n−1
2d d
internal nodes.
To calculate Big-Omega I am taking maximum everywhere.

If every node contains d + 1 pointers (d keys) then height will be maximum, because number of nodes to be accommodated are
fixed (⌈ d ⌉) .
n−1
If height is h then equation becomes
1 + (d + 1) + (d + 1)2 + (d + 1)3 + … + (d + 1)h−1 = n−1

d
(d+1)h−1 n−1
⟹ (d+1)−1
= d
h
⟹ (d + 1) = n
⟹ h = log(d+1) n
This is the maximum height possible or says the maximum number of levels possible.
Now using h traverse we can get to the leaf node :
O(h) O( n) = O( d n)

Answer is O(h) i.e., O(log(d+1) n) = O(logd n)
References
 50 votes -- Sachin Mittal (15.8k points)

Let us understand specification of B+ tree first
For a non-root node
Minimum number of keys = d ⟹ minimum number of children = d + 1

Maximum number of keys = 2d ⟹ maximum number of children = 2d + 1
For a root node
Minimum number of keys = 1 so, minimum number of children = 2

Maximum number of keys = 2d so, maximum number of children = 2d + 1
Now, coming to our actual question

Part (A). For a given no of leaf node (L ≥ 2) what will be the total no of keys in internal nodes?
Will solve this in three ways:
1. Assuming maximum nodes at each level
Height #nodes #keys

0 1 2d
1 2d + 1 2d(2d + 1)
⋮ ⋮ ⋮
h h
h (2d + 1) 2d[(2d + 1) ]
h
No. of leaf nodes = (2d + 1) = L
Total no. of keys in internal nodes = 2d + 2d(2d + 1) +2d(2d + 1)2 + … + 2d(2d + 1)
h−1
h
= (2d + 1) − 1 = L − 1
2. Assuming minimum nodes at each level
Height #nodes #keys

0 1 1
1 2 2d
⋮ ⋮ ⋮
h−1 h−1
h 2(d + 1) 2d[(d + 1) ]
h−1
So, no. of leaf nodes = 2(d + 1) =L
h−2
Total no of keys in internal nodes = 1 + 2d + 2d(d + 1) + … + 2d(d + 1)
h−1
= 2(d + 1) −1 = L−1
3. Whenever there is an overflow in a leaf node (or whenever no of leaf node increases by one), then we move a key in the
internal node (or we can say, no of internal keys increases by one).
Now, let's start with the base case. Only 2 leaf nodes (as given L ≥ 2 ). So, no. of keys in root node = 1 or L − 1.
Once there is an overflow in a single leaf node then no of leaf nodes now would become 3 and at the same the time we will have
one more key in our root node.
Part (B) Maximum number of internal nodes in a B+ tree of order 4 with 52 leaves?
Using Bulk loading approach, here we will use minimum fill factor (d = 4 hence, min keys = d = 4 and min children/block
pointer = d + 1 = 5)
So, we have 52 leaves so and need total 52 block pointers and one node should have minimum 5 block pointers.
So, for 52 leaves we require ⌊52/5⌋ = 10 nodes
⌊10/5⌋ = 2

For 11 block pointers we require ⌊10/5⌋ = 2 nodes
For 2 block pointers we require 1 node "it is root node"
So, max no of internal nodes= 10 + 2 + 1 = 13 nodes
Part (C) Minimum number of leaves in a B+ tree of order d and height h(h ≥ 1) ?
By part (A) "assuming minimum nodes at each level" case
Minimum no. of leaves = 2(d + 1)h−1
 42 votes -- saurabh rai (9k points)
3.1.5 B Tree: GATE CSE 1999 | Question: 1.25 top☝ ☛ https://gateoverflow.in/1478

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 http://home.iitj.ac.in/~ramana/ch10-storage-2.pdf
D. False. Height depends on number of record and also max no of keys in each node (order of tree)
Correct Answer: B
References
 49 votes -- srestha (85.2k points)

Given a B tree :
max children at a node : 2m − 1 ⟹ max keys : 2m − 2

min children at a node : m ⟹ min keys : m − 1
At Root node : min keys : 1 ⟹ min children : 2

Here, leaf level is at level h (because root is at level 0)
Now, we have to find
1. Minimum keys at leaf level(complete bottommost level, not just a node ) -

For this, we have to consider minimum everywhere.
Firstly we will count the minimum possible nodes at the leaf level.
At Root Node (level 0) : It can have minimum 2 child (mean 2 nodes minimum for next level)
At level 1: It has 2 nodes, each can have a minimum of m child (so, this gives 2 ∗ m minimum possible nodes at
next level )
At level 2 : min 2 ∗ m2 Child and so on.
At level (h − 1) : 2 ∗ (m)h−1 child (these are min number of leaf nodes possible )
At level h(leaf level) : 2 ∗ (m)h−1 nodes each having minimum (m − 1) keys. So, this gives the answer as
2 ∗ (m)h−1 ∗ (m − 1) minimum keys possible at leaf level.
2. Maximum keys at leaf level(complete bottommost level, not just a node ) -

For this, we have to count max everywhere.
At root (level 0) : max child possible 2m − 1 (nodes for next level)
At level 1 : 2m − 1 nodes give (2m − 1)2 child
At level (h − 1) : (2m − 1)h child (these are maximum possible nodes at leaf level)
At level h (leaf level) : (2m − 1)h nodes each having a maximum of (2m − 2) keys. Giving a total of -
(2m − 1)h ∗ (2m − 2) maximum keys at leaf level.
 43 votes -- Himanshu Agarwal (12.4k points)


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.
http://stackoverflow.com/questions/15485220/advantage-of-b-trees-over-bsts
References
A.i)
A.ii)

B)

The next 2 insertions weren’t asked in the question but will help you to understand part C of this question.
C. Insert a LONG SEQUENCE of keys in INCREASING ORDER
i. In normal case: Insertion always will be done at the rightmost leaf node, and all nodes will have exact
m+1
⌊ 2 ⌋ keys expect this rightmost leaf ( no of keys can vary from
m+1
⌊ 2 ⌋ to m for rightmost leaf).
For a long sequence, we can say the average is approximately

m+1
⌊ 2 ⌋ (This is the answer).
(There are two possible answers for this part, I left it on the reader to find out the second one)
Because all nodes will have
m+1
⌊ 2 ⌋ keys except 1 rightmost node.
we can also find the exact average in this case:

Let there are n keys in total ( inserted in increasing order),
No of leaf nodes will be exactly ⌊ n

⌋
⌊ ⌋
m+1
2
n
Average number of keys in leaf would be: ⎢ ⎥
⎢ ⎥
⎢ ⎥
⎢ n
⎥
⎣ ⌊ ⌋⎦
m+1
2

ii. With insertion as in (B): In this case, we can observe until the left sibling is full, we are shifting a key to the left leaf. As
we insert more and more keys all leaf nodes are filled except the rightmost two leaves, the rightmost 2 leaves can have any
number of in
m+1
⌊ 2 ⌋ to m each.
For a long sequence, we can say the average is approximately

m. ( Same reasoning as case i )
we can find the actual average in this case as well,
Let there are n keys in total ( inserted in increasing order),
n
Number of leaf nodes in this case will be ⌈ m ⌉,
n
so average number of keys would be: n
⌈m ⌉
 4 votes -- Nikhil Dhama (2.5k points)
(a) B+ tree insertion: 80, 50, 10, 70, 30, 100, 90

Order of B+ = p = 3
Overflow: When number of key values exceed p − 1 = 3 − 1 = 2
Tree after insertion of 10 :
(b)
p
Underflow: if leaf node contain ⌈ 2 ⌉ − 1 = 2 − 1 = 1 key values.
Deletion of key-value 30 :

Deletion of key-value 10 :
Here when we delete the key-value 10 then underflow happened, so we can merge this node with the right sibling.
When we merge two nodes then the parent node one value needs to come down i.e. 50 here.
Now if we try to bring 50 down then that node will again suffer from underflow as it will become empty.
so we will try to merge this node it with its right sibling i.e. the node which contains 70
Again, When we merge two nodes(nodes in the 2nd level that contain 50 and 70) then one value of the parent node (i.e. node
having 50, 70 ) needs to come down
So we will bring 70 down and merge it with 50 since bringing 70 down will not cause underflow as 80 is present in the parent
node.
 3 votes -- Lakshman Patel (65.7k points)

For A)
X1 = Variable (Key can be found @ Internal nodes at various levels)

X2 = Constant
X3 = Variable, We need to just check where key is present/absent, not to access Data. (A successful search means that the key

exists in the database and unsuccessful means that it is not present in the database.) So Variable
X4 = Constant
For Part B) i) Write down two copies of the same table for comparison side by side. Just map B of first to A of the second copy.
Those matching tuples take A of first table & B of seconds.
Content of View A
A B
1 3
1 4
2 5
For Part B) ii)
Additional tuples getting inserted:
A B
11 7
11 8
2 6
1 11
 30 votes -- Akash Kanase (36k points)

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 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.

http://www.cburch.com/cs/340/reading/btree/index.html
References
 49 votes -- Rajarshi Sarkar (27.9k points)

(B) is the correct answer.
Once we add G, the leaf node becomes B G H I , since we can have only 3 keys. the node has to split at G or H , and G or H
will be added to parent node.
Since P is the parent node in options 1 and 2, its evident the 3rd element i.e. H should be selected for splitting (because after
adding any key from the leftmost child node, P becomes the 3rd element in the node)
Now parent node becomes H L P U , select P as for splitting, and you get option B.
Hence, answer is B.
 22 votes -- ryan sequeira (3k points)


Answer: C
14(p − 1) + 6p ≤ 512
20p − 14 ≤ 512
20p ≤ 526
Therefore, p = 26 .

Answer: D
A. Cannot compare both the trees solely on basis of this.

B. Both trees are BST.
C. False. High fanout in B+ ensures that it takes more memory than BST.
D. True. Records are stored in disk blocks.
3.1.15 B Tree: GATE CSE 2007 | Question: 63, ISRO2016-59 top☝ ☛ https://gateoverflow.in/1261

The answer is option A.
Bp + P(Rp + Key) ≤ BlockSize
⟹ 1 × 6 + n(7 + 9) ≤ 1024
⟹ n ≤ 63.625.
So, 63 is the answer.
 62 votes -- Gate Keeda (15.9k points)

Total 5 splitting will occur during 10 successive insertions
Let's take 10 successive key values as {1, 2, 3, … 10} which can cause maximum possible splits.

 60 votes -- Prateek kumar (6.7k points)

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
3. after inserting 2 (there will be an internal node split and a leaf node split)
Correct Answer: C
 63 votes -- Vikrant Singh (11.2k points)

Answer: B
Order = 5+1 = 6
6
Minimum children in a non root node = ⌈ Order
2 ⌉=⌈ 2 ⌉=3
Keys = Minimum children in a non root node - 1 = 2

whichever way you go from the root to leaves, you'll always end up counting 5 nodes.
 60 votes -- Amar Vashishth (25.2k points)

(n − 1)12 + n × 8 ≤ 1024
n ≤ 51
In non leaf node number of keys = n − 1
= 51 − 1 = 50
 63 votes -- ppm (543 points)


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.
 41 votes -- ukn (543 points)

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 can not exceed 512 bytes .
2(p) + 8(p − 1) ≤ 512
⟹ p ≤ 52
Therefore, maximum order must be 52.

Properties of B+ trees:
1. B+ tree is height balance tree.
2. Key value is in sorted order.
3. Leaf node has pointer to next leaf node.
4. Non leaf node has pointer to a node (leaf or non leaf) and not pointer to data record.
Option B is not correct.

 26 votes -- Digvijay (44.9k points)

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.

 42 votes -- Sandeep_Uniyal (6.5k points)
3.1.25 B Tree: GATE IT 2005 | Question: 23, ISRO2017-67 top☝ ☛ https://gateoverflow.in/3768

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.
Correct Answer: A
 79 votes -- Manu Thakur (34k points)

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.
 35 votes -- jayendra (6.7k points)

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, 1 (Ans).
 55 votes -- Himanshu Agarwal (12.4k points)
Now merge 40 in upper level.

Now redistribute:
So, the answer is A.
 39 votes -- srestha (85.2k points)
3.2 Candidate Keys (5) top☝
3.2.1 Candidate Keys: GATE CSE 1994 | Question: 3.7 top☝ ☛ https://gateoverflow.in/2493
An instance of a relational scheme R(A, B, C) has distinct values for attribute A. Can you conclude that A is a candidate key
for R?
gate1994 databases easy database-normalization candidate-keys descriptive
Answer ☟
3.2.2 Candidate Keys: GATE CSE 2011 | Question: 12 top☝ ☛ https://gateoverflow.in/2114
Consider a relational table with a single record for each registered student with the following attributes:
1. Registration_Num: Unique registration number for each registered student

2. UID: Unique identity number, unique at the national level for each citizen
3. BankAccount_Num: Unique account number at the bank. A student can have multiple accounts or joint accounts. This
attribute stores the primary account number.
4. Name: Name of the student
5. Hostel_Room: Room number of the hostel
Which of the following options is INCORRECT?
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 super key such that S ∩ UID is NULL then S ∪ UID is also a superkey
gate2011-cse databases normal candidate-keys
Answer ☟
3.2.3 Candidate Keys: GATE CSE 2014 Set 2 | Question: 21 top☝ ☛ https://gateoverflow.in/1978
The maximum number of superkeys for the relation schema R(E, F, G, H) with E as the key is _____.
gate2014-cse-set2 databases numerical-answers easy candidate-keys
Answer ☟

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______.
gate2014-cse-set2 databases numerical-answers easy candidate-keys
Answer ☟
A prime attribute of a relation scheme R is an attribute that appears

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
gate2014-cse-set3 databases easy candidate-keys
Answer ☟
Answers: Candidate Keys
3.2.1 Candidate Keys: GATE CSE 1994 | Question: 3.7 top☝ ☛ https://gateoverflow.in/2493

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 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.
 58 votes -- Sourav Roy (2.9k points)
3.2.2 Candidate Keys: GATE CSE 2011 | Question: 12 top☝ ☛ https://gateoverflow.in/2114

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 can not identify
each student uniquely with BankAccount_Num.
 56 votes -- Pranay Datta (7.8k points)

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
EF
⎨ ⎬
EG
⎪ ⎪
EH
⎩
⎪ ⎭
⎪
EFG
EFH
EGH
EFGH
 50 votes -- Sankaranarayanan P.N (8.5k points)

Should not eqaul 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.
 43 votes -- Aravind (2.8k points)

Answer (B).
The attributes of a candidate key are called the prime attributes. Suppose ABC is one candidate key of a Relation
R(ABCDEFGH). Then the attributes A, B and C all are prime attributes. Similarly if ABD is also another candidate key in
the same relation R, then D is also a prime attribute. And conversely, an attribute that does not occur in ANY candidate key is
called a non-prime attribute.
 18 votes -- Divya Bharti (8.8k points)
3.3 Conflict Serializable (3) top☝
3.3.1 Conflict Serializable: GATE CSE 2017 Set 2 | Question: 44 top☝ ☛ https://gateoverflow.in/118640
Two transactions T1 and T2 are given as
T1 : r1 (X)w1 (X)r1 (Y )w1 (Y )
T2 : r2 (Y )w2 (Y )r2 (Z)w2 (Z)
where ri (V ) denotes a read operation by transaction Ti on a variable V and wi (V ) denotes a write operation by transaction Ti on
a variable V . The total number of conflict serializable schedules that can be formed by T1 and T2 is ______
gate2017-cse-set2 databases transaction-and-concurrency numerical-answers conflict-serializable

Answer ☟
Let ri (z) and wi (z) denote read and write operations respectively on a data item z by a transaction Ti . Consider the following
two schedules.
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 one of the following options is correct?
A. S1 is conflict serializable, and S2 is not conflict serializable

B. S1 is not conflict serializable, and S2 is conflict serializable
C. Both S1 and S2 are conflict serializable
D. Niether S1 nor S2 is conflict serializable
gate2021-cse-set1 databases transaction-and-concurrency conflict-serializable
Answer ☟
Let S be the following schedule of operations of three transactions T1 , T2 and T3 in a relational database system:
R2 (Y ), R1 (X), R3 (Z), R1 (Y )W1 (X), R2 (Z), W2 (Y ), R3 (X), W3 (Z)
Consider the statements P and Q below:
P : S is conflict-serializable.
Q: If T3 commits before T1 finishes, then S is recoverable.
Which one of the following choices is correct?

A. Both P and Q are true
B. P is true and Q is false
C. P is false and Q is true
D. Both P and Q are false
gate2021-cse-set2 databases transaction-and-concurrency conflict-serializable
Answer ☟
Answers: Conflict Serializable

There is only one way to have (conflict) serializable schedule as T 1 → T 2, because last operation of T 1 and first
operation of T 2 conflicts each other.
Now See How many schedules are conflict serializable to T 2 → T 1.
I am writing T 1−
R(A) W(A) R(B) W(B)

If you notice, I wrote T 1 with space in between operation.
Now See T 2 from right, if we see T 2 from right, then tell me first operation of T 2 that conflicts with any operation of T 1.
W(C) and R(C) do not have any conflict with any operation, but W(B) has.
Pick W(B) and see, at how many places it can be there.
Case1: W(B) R(A) W(A) R(B) W(B)

Case2: R(A) W(B) W(A) R(B) W(B)
Case3: R(A) W(A) W(B) R(B) W(B)
Pick each case and see,how many positions other operation of T 2 can take.

Case1: W(B) R(A) W(A) R(B) W(B)
How many positions W(C) and R(C) can take ?
(note that these W(C) and R(C) cant come before W(B) )
that is 5C1 + 5C2 = 15 (either both can take same space or two different spaces)
Now see, for each of these 15 positions, how many can R(B) take ?
Obliviously R(B) cant come before W(B) therefore one position.
15 × 1 = 15 total possible schedules from case 1.
Case2: R(A) W(B) W(A) R(B) W(B)
that is 4C1 + 4C2 = 10 (either both can take same space or two different spaces)
Only 2 positions, because it has to come before W(B) .
Case3: R(A) W(A) W(B) R(B) W(B)
that is 3C1 + 3C2 = 6
Only 3 positions, because it has to come before W(B) .
total schedules that are conflict serializable as T 2 → T 1 = 15 + 20 + 18 = 53.
total schedules that are conflict serializable as T 1 → T 2 = 1.
total schedules that are conflict serializable as either T 2 → T 1 or T 1 → T 2 = 53 + 1 = 54 .


T1 T2
r1 (x)
r1 (y)
r2 (x)
r2 (y)
w2 (y)
w1 (x)
Here r1 (y) and w2 (y) are conflicting pairs, giving T1 → T2 and r2 (x) and w1 (x) giving T2 → T1 , so the schedule is not
conflict serializable.

T1 T2
r1 (x)
r2 (x)
r2 (y)
w2 (y)
r1 (y)
w1 (x)
Here r2 (x) and w2 (x) are conflicting pairs giving T2 → T1 , and w2 (y) and r1 (y) also giving T2 → T1 , therefore this schedule
is conflict serializable.
Correct Option B
 1 votes -- zxy123 (2.8k points)

T1 T2 T3
R(Y )
R(X)
R(Z)
R(Y )
W (X)
R(Z)
W (Y )
R(X)
W (Z)
T1 → T2 due to R1 (Y ) being before W2 (Y )

T1 → T3 due to W1 (X) being before R3 (X)
T2 → T3 due to R2 (Z) is being W3 (Z) in the schedule.
There are no other conflicts and the discovered conflicts are not forming the cycle.
Therefore, the given schedule is Conflict Serializable.
Statement Q : If T3 commits, before T1 finishes, then S is recoverable.
' Schedule S is recoverable, if Tj creating the dirty read by reading the written data by Ti and Tj commits after Ti
commits.
By the above definition, Q is wrong.

Option B is correct.
 3 votes -- Shaik Masthan (50.4k points)
3.4 Data Independence (1) top☝
3.4.1 Data Independence: GATE CSE 1994 | Question: 3.11 top☝ ☛ https://gateoverflow.in/2497
State True or False with reason
Logical data independence is easier to achieve than physical data independence.
gate1994 databases normal data-independence true-false
Answer ☟
Answers: Data Independence

3.4.1 Data Independence: GATE CSE 1994 | Question: 3.11 top☝ ☛ https://gateoverflow.in/2497

This is False.
Generally, physical data independence exists in most databases and file environments where physical details are hidden from the
user and applications remain unaware of these details. On the other hand, logical data independence is harder to achieve because
of a much stricter requirement - it allows structural and constraint changes without affecting application programs.
3.5 Database Normalization (49) top☝
3.5.1 Database Normalization: GATE CSE 1987 | Question: 2n top☝ ☛ https://gateoverflow.in/80609
State whether the following statements are TRUE or FALSE:
A relation r with schema (X, Y ) satisfies the function dependency X → Y , The tuples ⟨1, 2⟩ and ⟨2, 2⟩ can both be in r
simultaneously.
gate1987 databases database-normalization true-false
Answer ☟
3.5.2 Database Normalization: GATE CSE 1988 | Question: 12i top☝ ☛ https://gateoverflow.in/94398
What are the three axioms of functional dependency for the relational databases given by Armstrong.
gate1988 normal descriptive databases database-normalization
Answer ☟
3.5.3 Database Normalization: GATE CSE 1988 | Question: 12iia top☝ ☛ https://gateoverflow.in/94399
Using Armstrong’s axioms of functional dependency derive the following rules:
{x → y, x → z} ∣= x → yz
(Note: x → y denotes y is functionally dependent on x, z ⊆ y denotes z is subset of y, and ∣= means derives).
gate1988 easy descriptive databases database-normalization
Answer ☟
3.5.4 Database Normalization: GATE CSE 1988 | Question: 12iib top☝ ☛ https://gateoverflow.in/94618
{x → y, wy → z} ∣= xw → z
Answer ☟
3.5.5 Database Normalization: GATE CSE 1988 | Question: 12iic top☝ ☛ https://gateoverflow.in/94619
{x → y, z ⊂ y} ∣= x → z

Answer ☟
3.5.6 Database Normalization: GATE CSE 1990 | Question: 2-iv top☝ ☛ https://gateoverflow.in/83977
Match the pairs in the following questions:
(a) Secondary index (p) Function dependency

(b) Non-procedural query language (q) B-tree
(c) Closure of a set of attributes (r) Domain calculus
(d) Natural join (s) Relational algebraic operations
gate1990 match-the-following database-normalization databases
Answer ☟
3.5.7 Database Normalization: GATE CSE 1990 | Question: 3-ii top☝ ☛ https://gateoverflow.in/84054
Indicate which of the following statements are true:

A relational database which is in 3NF may still have undesirable data redundancy because there may exist:
A. Transitive functional dependencies

B. Non-trivial functional dependencies involving prime attributes on the right-side.
C. Non-trivial functional dependencies involving prime attributes only on the left-side.
D. Non-trivial functional dependencies involving only prime attributes.
gate1990 normal databases database-normalization multiple-selects
Answer ☟
3.5.8 Database Normalization: GATE CSE 1994 | Question: 3.6 top☝ ☛ https://gateoverflow.in/2492
State True or False with reason
There is always a decomposition into Boyce-Codd normal form (BCNF) that is lossless and dependency preserving.
gate1994 databases database-normalization easy true-false
Answer ☟
3.5.9 Database Normalization: GATE CSE 1995 | Question: 26 top☝ ☛ https://gateoverflow.in/2665
Consider the relation scheme R(A, B, C) with the following functional dependencies:
A, B → C,
C→A
A. Show that the scheme R is in 3NF but not in BCNF .

B. Determine the minimal keys of relation R.
gate1995 databases database-normalization normal descriptive
Answer ☟
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

A. in first normal form but not in second normal form
B. in second normal form but not in first normal form
C. in third normal form
D. none of the above
gate1997 databases database-normalization normal
Answer ☟
Which normal form is considered adequate for normal relational database design?
A. 2NF
B. 5NF
C. 4NF
D. 3NF
gate1998 databases database-normalization easy
Answer ☟
Consider the following database relations containing the attributes
Book_id
Subject_Category_of_book
Name_of_Author
Nationality_of_Author
With Book_id as the primary key.
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?
gate1998 databases database-normalization normal descriptive
Answer ☟
Let R = (A, B, C, D, E, F) be a relation scheme with the following dependencies C → F, E → A, EC → D, A → B .

Which one of the following is a key for R?
A. CD
B. EC
C. AE
D. AC
gate1999 databases database-normalization easy
Answer ☟
3.5.14 Database Normalization: GATE CSE 1999 | Question: 2.7, UGCNET-June2014-III: 25 top☝ ☛ https://gateoverflow.in/1485
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
C. in 3NF but not in 2NF
D. in both 2NF and 3NF

gate1999 databases database-normalization normal ugcnetjune2014iii
Answer ☟
Given the following relation instance.
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
gate2000-cse databases database-normalization easy
Answer ☟
R(A, B, C, D) is a relation. Which of the following does not have a lossless join, dependency preserving BCNF
decomposition?
A. A → B, B → CD
B. A → B, B → C, C → D
C. AB → C, C → AD
D. A → BCD
gate2001-cse databases database-normalization normal
Answer ☟
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 of relations is
A. Zero
B. More than zero but less than that of an equivalent 3NF decomposition
C. Proportional to the size of F+
D. Indeterminate
Answer ☟
For relation R=(L, M, N, O, P), the following dependencies hold:

M → O, NO → P, P → L and L → MN
R is decomposed into R1 = (L, M, N, P) and R2 = (M, O).
A. Is the above decomposition a lossless-join decomposition? Explain.

B. Is the above decomposition dependency-preserving? If not, list all the dependencies that are not preserved.
C. What is the highest normal form satisfied by the above decomposition?

gate2002-cse databases database-normalization normal descriptive
Answer ☟
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).
A. Dependency-preservation
B. Lossless-join
C. BCNF definition
D. 3NF definition
Answer ☟
From the following instance of a relation schema 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

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
gate2002-cse databases database-normalization
Answer ☟
Consider the following functional dependencies in a database.
Date_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. in none of the above
Answer ☟
The relation scheme Student Performance (name, courseNo, rollNo, grade) has the following functional dependencies:

name, courseNo, → grade
rollNo, courseNo → grade
name → rollNo
rollNo → name
The highest normal form of this relation scheme is

A. 2NF
B. 3NF
C. BCNF
D. 4NF
Answer ☟
3.5.23 Database Normalization: GATE CSE 2005 | Question: 29, UGCNET-June2015-III: 9 top☝ ☛ https://gateoverflow.in/1365
Which one of the following statements about normal forms is FALSE?
A. BCNF is stricter than 3NF

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 is in BCNF
gate2005-cse databases database-normalization easy ugcnetjune2015iii
Answer ☟
Consider a relation scheme 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 keys R?
A. AE, BE
B. AE, BE, DE
C. AEH, BEH, BCH
D. AEH, BEH, DEH
Answer ☟
The following functional dependencies are given:
AB → CD, AF → D, DE → F, C → G, F → E, G → A
Which one of the following options is false?
A. {CF}∗ = {ACDEFG}
B. {BG}∗ = {ABCDG}
C. {AF}∗ = {ACDEFG}
D. {AB}∗ = {ABCDG}
Answer ☟
3.5.26 Database Normalization: GATE CSE 2007 | Question: 62, UGCNET-June2014-II: 47 top☝ ☛ https://gateoverflow.in/1260
Which one of the following statements is FALSE ?

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 3 NF relation
D. A prime attribute can be transitively dependent on a key in a BCNF relation
gate2007-cse databases database-normalization normal ugcnetjune2014ii
Answer ☟
Consider the following relational schemes for a library database:

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 schemes. Which of the following statements is true?
A. Both Book and Collection are in BCNF

B. Both Book and Collection are in 3NF only
C. Book is in 2NF and Collection in 3NF
D. Both Book and Collection are in 2NF only
Answer ☟
Consider the following relational schema:

Suppliers(sid:integer , sname:string, city:string, street:string)
−−−−−−−−
Parts(pid:integer , pname:string, color:string)
−−−−−−−−−
Catalog(sid:integer, pid:integer , cost:real)
−−−−−−−−−−−−−−−−−−
Assume that, in the suppliers 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
gate2009-cse databases sql database-normalization normal
Answer ☟
Which of the following is TRUE?
A. Every relation in 3NF is also in BCNF

B. A relation R is in 3NF if every non-prime attribute of R is fully functionally 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

gate2012-cse databases easy database-normalization
Answer ☟
Relation R has eight attributes ABCDEFGH . Fields of R contain only atomic values. F =
{CH→G, A→BC, B→CFH, E→A, F→EG} is a set of functional dependencies (FDs) so that F + is exactly the set of FDs
that hold for R.
How many candidate keys does the relation R have?
A. 3
B. 4
C. 5
D. 6
Answer ☟
Relation R has eight attributes ABCDEFGH . Fields of R contain only atomic values. F =
{CH → G, A → BC, B → CFH, E → A, F → EG} is a set of functional dependencies (FDs) so that F + is exactly the set of
FDs that hold for R.
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 .
Answer ☟
3.5.32 Database Normalization: GATE CSE 2014 Set 1 | Question: 21 top☝ ☛ https://gateoverflow.in/1788
Consider the relation scheme R = (E, F, G, H, I, J, K, L, M, N) 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?
A. {E, F}
B. {E, F, H}
C. {E, F, H, K, L}
D. {E}
gate2014-cse-set1 databases database-normalization normal
Answer ☟
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?
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.

Answer ☟
Consider the relation X(P, Q, R, S, T , U) with the following set of functional dependencies
F = { {P, R} → {S, T }, {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}
gate2015-cse-set3 databases database-normalization easy
Answer ☟
Which of the following is NOT a superkey in a relational schema with attributes

V , W, X, Y , Z and primary key
V Y?
A. V XY Z
B. V WXZ
C. V WXY
D. V WXY Z
gate2016-cse-set1 databases database-normalization easy
Answer ☟
A database of research articles in a journal uses the following schema.

(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
Answer ☟

The following functional dependencies hold true for the relational schema R {V , W, X, Y , Z} :
V→W
VW → X
Y → VX
Y→Z
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
Answer ☟
Consider the following four relational schemas. For each schema , all non-trivial functional dependencies are listed, The
bolded 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)
rollno, courseid, → marks, grade
marks → grade
Schema IV: Registration (rollno, courseid, credit)
rollno, courseid → credit
courseid → credit
Which one of the relational schemas above is in 3NF but not in BCNF?
A. Schema I
B. Schema II
C. Schema III
D. Schema IV

Answer ☟
Let the set of functional dependencies F = {QR → S, R → P, S → Q} hold on a relation schema X = (PQRS) . X is
not in BCNF. Suppose X is decomposed into two schemas Y and Z , where Y = (PR) and Z = (QRS) .
Consider the two statements given below.
I. Both Y and Z are in BCNF

II. Decomposition of X into Y and Z is dependency preserving and lossless
Which of the above statements is/are correct?

A. Both I and II
B. I only
C. II only
D. Neither I nor II
Answer ☟
Consider a relational table R that is in 3NF , but not in BCNF. Which one of the following statements is TRUE?
A. R has a nontrivial functional dependency X → A , where X is not a superkey and A is a prime attribute.
B. R has a nontrivial functional dependency X → A , where X is not a superkey and A is a non-prime attribute and X
is not a proper subset of any key.
C. R has a nontrivial functional dependency X → A , where X is not a superkey and A is a non-prime attribute and X
is a proper subset of some key
D. A cell in R holds a set instead of an atomic value.
Answer ☟
Consider the relation R(P, Q, S, T , X, Y , Z, W) with the following functional dependencies.
PQ → X; P → Y X; Q → Y; Y → ZW
Consider the decomposition of the relation R into the constituent relations according to the following two decomposition schemes.
D1 : R = [(P, QS, T ); (P, T , X); (Q, Y ); (Y , Z, W)]

D2 : R = [(P, Q, S); (T , X); (Q, Y ); (Y , Z, W)]
Which one of the following options is correct?
A. D1 is a lossless decomposition, but D2 is a lossy decomposition

B. D1 is a lossy decomposition, but D2 is a lossless decomposition
C. Both D1 and D2 are lossless decompositions
D. Both D1 and D2 are lossy decompositions
gate2021-cse-set1 databases database-normalization
Answer ☟
Suppose the following functional dependencies hold on a relation U with attributes P, Q, R, S , and T :

P → QR
RS → T $
Which of the following functional dependencies can be inferred from the above functional dependencies?
A. PS → T
B. R→T
C. P→R
D. PS → Q
gate2021-cse-set2 multiple-selects databases database-normalization
Answer ☟
3.5.43 Database Normalization: GATE IT 2004 | Question: 75 top☝ ☛ https://gateoverflow.in/3719
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
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 and 1NF
gate2004-it databases database-normalization normal
Answer ☟
A table has fields 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

A. 1 NF
B. 2 NF
C. 3 NF
D. None of these
gate2005-it databases database-normalization easy
Answer ☟
In a schema with attributes A, B, C, D and E following set of functional dependencies are given
A→B
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
Answer ☟

Consider a relation R with five attributes V , W, X, Y , and Z. The following functional dependencies hold:
V Y → W, WX → Z, and ZY → V .
Which of the following is a candidate key for R?
A. V XZ
B. V XY
C. V WXY
D. V WXY Z
Answer ☟
Let R(A, B, C, D) be a relational schema with the following functional dependencies :

A → B, B → C , C → D and D → B. The decomposition of R into (A, B), (B, C), (B, D)
A. gives a lossless join, and is dependency preserving

B. gives 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
Answer ☟
Let R(A, B, C, D, E, P, G) be a relational schema in which the following functional dependencies are known to hold:
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
Answer ☟
3.5.49 Database Normalization: GATE2001-1.23, UGCNET-June2012-III: 18 top☝ ☛ https://gateoverflow.in/716
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
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
gate1998 databases ugcnetjune2012iii database-normalization
Answer ☟
Answers: Database Normalization
3.5.1 Database Normalization: GATE CSE 1987 | Question: 2n top☝ ☛ https://gateoverflow.in/80609

True is answer.
X → Y says when X repeats, Y will be also repeat. Since, X is not repeated, Y may or may not repeat.

X Y
1 2
2 2
 30 votes -- Prashant Singh (47.2k points)
3.5.2 Database Normalization: GATE CSE 1988 | Question: 12i top☝ ☛ https://gateoverflow.in/94398

1. AXIOM OF REFLEXIVITY
If Y ⊆ X then X → Y
2. AXIOM OF AUGMENTATION
If X → Y then XZ → Y Z for any Z
3. AXIOM OF TRANSITIVITY
If X → Y and Y → Z then X → Z
 12 votes -- Aashish (1.8k points)
3.5.3 Database Normalization: GATE CSE 1988 | Question: 12iia top☝ ☛ https://gateoverflow.in/94399

x → z (Given)
⟹ xx → zx (Axiom of augmentation) → (I)
Also x → y (Given)
⟹ xz → yz (Axiom of augmentation) → (II)
Using (I) and (II) we get
xx → yz (Axiom of transitivity)
⟹ x → yz
 9 votes -- Satbir Singh (21k points)
3.5.4 Database Normalization: GATE CSE 1988 | Question: 12iib top☝ ☛ https://gateoverflow.in/94618

x → y (Given)
⟹ xw → yw ( using axiom of augmentation A → B ⟹ AX → BX )
also yw → z (Given)
⟹ xw → z (using Axiom of transitivity (A → B and B → C) ⟹ A → C )

3.5.5 Database Normalization: GATE CSE 1988 | Question: 12iic top☝ ☛ https://gateoverflow.in/94619

∵ z ⊂ y , Trivially y → z . Now by transitivity, x → y, y → z ⟹ x → z
 6 votes -- Arkaprava Paul (1.9k points)
3.5.6 Database Normalization: GATE CSE 1990 | Question: 2-iv top☝ ☛ https://gateoverflow.in/83977

Secondary index ⇒ B-tree

Non-procedural query language ⇒ Domain calculus
Closure of a set of attributes ⇒ Function dependency
Natural join ⇒ Relational algebraic operations
(a) Secondary index (q) B-tree

(b) Non-procedural query language (r) Domain calculus
(c) Closure of a set of attributes (p) Function dependency
(d) Natural join (s) Relational algebraic operations
 10 votes -- Pankaj Kumar (7.8k points)
3.5.7 Database Normalization: GATE CSE 1990 | Question: 3-ii top☝ ☛ https://gateoverflow.in/84054
A . Transitive functional dependency. Therefore it is not in 3NF
B. 3NF because right side is prime attribute
C. Not in 3NF because let us suppose ABC is a candidate key ( you can assume any candidate key with any no of attribute) .
now consider AB -> non-prime attribute which shows it is not in 3NF
D. involving only prime attribute so the Right side should definitely contain only prime attribute. therefore it is in 3NF
so B, D is the answer
Edited on 24th Nov 2020 by Gurdeep saini
 10 votes -- Gurdeep (6.8k points)

False
BCNF decomposition can always be lossless, but it may not be always possible to get a dependency preserving BCNF
decomposition.

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 .

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

3NF ,
because we can always have a 3NF decomposition which is dependency preserving and lossless (not possible for any higher
forms).

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)

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.
3.5.14 Database Normalization: GATE CSE 1999 | Question: 2.7, UGCNET-June2014-III: 25 top☝ ☛ https://gateoverflow.in/1485

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 ST U,
there will be a FD U → S as well.


(b) is answer.
If A → B then for each same value of A, B value should be same. If all the A values are distinct the FD hold irrespective of the
B values.
Since all Y values are distinct FDs with Y , Y X and Y Z on LHS hold. So, option B is correct.
In option A, Z → Y is violated as for same Z value we have different Y values.

Similarly in C, X → Z is violated and in D, XZ → Y is violated.

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.
References
(C) is the answer. Because of AB → C and C → A, we cannot have A, B and C together in any BCNF relation- in relation ABC,
C is not a super key and C→ A exists violating BCNF condition. So, we cannot preserve AB → C dependency in any
decomposition of ABCD.
For (A) we can have AB, BCD, A and B the respective keys
For (B) we can have AB, BC, CD, A, B and C the respective keys
For (D) we can have ABCD, A is key

Answer is A.

If a relation schema is in BCNF then all redundancy based on functional dependency has been removed, although other types of
redundancy may still exist. A relational schema R is in Boyce–Codd normal form if and only if for every one of its dependencies
X → Y, at least one of the following conditions hold:
X → Y is a trivial functional dependency (Y ⊆ X)

X is a super key for schema R
http://en.wikipedia.org/wiki/Boyce%E2%80%93Codd_normal_form
References
 60 votes -- Priya_das (603 points)

A. Yes as R1 ∩ R2 = M and M → O
B. NO
From the Dependencies obtained from R1 and R2 , we CANNOT infer NO → P
Mistake That CAN be made: Here we CANNOT apply Pseudo Transitivity Rule using M → O & MN → P to obtain
NO → P because the rule says :if M → O and NO → P then NM → P or MN → P , But here we have M → O
and MN → P ... SO we CANNOT apply the rule here to obtain NO → P from it.
C. BCNF
R1 keys : P, L, MN hence BCNF
R2 key : M hence BCNF
 54 votes -- Danish (3.4k points)

A. False . BCNF may or may not satisfy Dependency preservation, 3NF always does. But we can't make any guaranteed
decision, regarding BCNF if it satisfies Dependency preservation
B. False . Both are lossless.
C. True. Using this we can always decide between BCNF & 3NF .
D. False . Every BCNF relation is also 3NF trivially.
Answer -> C ( & Only C ).
A. dependency preservation.
in 3NF Dependency always preserved but in BCNF it may or may not be preserved.
For a particular set of FDs it may not differentiate BCNF and 3NF.
B.Lossless join always possible in both BCNF as well as 3NF.
D. 3NF definition also unable to differentiate BCNF & 3NF bcoz every BCNF is trivially 3NF.
C. every 3NF which is not BCNF fails BCNF Definition so it may used to differentiate which is BCNF & which is 3NF ..

Answer is C .
Generally Normalization is done on the schema itself.

From the relational instance given, we may strike out FD s 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.

There are three FDs that are valid from the above set of FDs for the given relation :
1. Date_of_Birth → Age
2. Name → Roll_number
3. 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 in 1NF only.
Option (D).
 58 votes -- Danish (3.4k points)

Here candidate keys are,
name, courseNo
rollNo, courseNo
That makes name, rollNo, and courseNo prime attributes (part of some candidate key)
Functional dependencies 3 and 4 are not partial FDs.
If a relation schema is not in 2NF, then for some FD x → y, x should be a proper subset of some candidate key and y should
be a non-prime attribute.
FD s 3 and 4 are not violating 2NF, because the RHS are prime attributes.
For a relation to be in 3NF, for every FD, x → y, x should be a super key or y is a prime attribute. For FD s 3 and
4, LHS are not super keys, but RHS are prime attributes. So, they are not violating 3NF.
For a relation to be in BCNF , for every FD, x → y, x should be super key. This is clearly violated for FD s 3 and 4 and so the
relation scheme is not in BCNF and hence not in 4NF also.
Correct option: B.
 36 votes -- rameshbabu (2.6k points)
3.5.23 Database Normalization: GATE CSE 2005 | Question: 29, UGCNET-June2015-III: 9 top☝ ☛ https://gateoverflow.in/1365

Option C is the only FALSE statement.
We can always have a lossless decomposition into BCNF but not always we can have a lossless and dependency preserving
decomposition. But this is always possible in the case of 3NF.
Option A is true as the requirement of BCNF required a relation schema to be in 3NF. Actually 3NF allows transitive
dependency for prime attributes whereas BCNF does not.
Option D is true as shown below.

Assume the two attributes to be A and B.
Now, we can have three cases:
1. Either A or B is the candidate key but not both. i.e., A → B or B → A. No other FD is possible and LHS of all FDs are
superkeys and so BCNF requirement is satisfied.
2. Both A and B are candidate keys. i.e., A → B and B → A. Like in above case BCNF requirement is satisfied.
3. Neither A → B nor B → A and so AB is the key. So, no other FD is possible and this case also satisfies BCNF
requirement.
Thus any relation with 2 attributes is guaranteed to be in BCNF.

Ref: https://gatecse.in/demystifying-database-normalization/
References

(d) AEH, BEH, DEH
using the given functional dependencies and looking at the dependent attributes, E and H are not dependent on any. So, they must
be part of any candidate key. So, only option is D. If we see the FD's, adding A, B or D to EH do form candidate keys.

{AF}*= {AFDE} .
Hence, option C is wrong.
3.5.26 Database Normalization: GATE CSE 2007 | Question: 62, UGCNET-June2014-II: 47 top☝ ☛ https://gateoverflow.in/1260

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 need
something like Key ⇒ Non Key, Non Key ⇒ Non key. 3NF definition says that for functional dependency 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.
Answer is D.

Answer: C
It is given that {Author, Title} is the key for both schemas.
The given dependencies are :
{Title, Author} → Catalog_no

Catalog_no → {Title, Author, Publisher, Year}

Catalog_no → {Title, Author, Publisher, Year}
{Publisher, Title, Year} → {Price}
First, let's take schema Collection (Title, Author, Catalog_no) :
{Title, Author} → Catalog_no
{Title, Author} is a candidate key and hence super key also and by definition of BCNF this is in BCNF .
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}

But in the given set of dependencies we have {Publisher, Title, Year} → Price, which has a Transitive Dependency. So,
Book is not in 3NF but is in 2NF.
 45 votes -- worst_engineer (2.8k points)

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:
' "each supplier and each street within a city has unique name"
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 .
http://db.grussell.org/section009.html
Correct Answer: A
References

(C) Every relation in BCNF is also in 3NF. Straight from definition of BCNF.

Here, we can see that D is not part of any F D′ s , hence D must be part of the candidate key.
Now D+ ={D}.
Hence, we have to add A, B, C, E, F, G, H to D and check which of them are Candidate keys of size 2.

We can proceed as:
AD+= {A,B,C,D,E,F,G,H}
Similarly we see BD+ , ED+ and FD+ also gives us all the attributes. Hence, AD,BD,ED,FD are definitely the candidate keys.
But CD+, GD+ and HD+ doesnnt give all the attributes hence, CD, GD and HD are not candidate keys.
Now we need to check the candidate keys of size 3. Since AD, BD, ED, FD are all candidate keys hence we can't find
candidate keys by adding elements to them as they will give us superkeys as they are already minimal. Hence, we have to
proceed with CD , GD and HD.
Also, we can't add any of A, B, E, F to CD , GD, HD as they will again give us superset of AD, BD, ED, FD .
Hence, we can only add among C, G, H to CD, GD, HD.
Adding C to GD and HD we get GCD, HCD . Taking closure and we will see they are not candidate keys.
Adding H to GD we get GHD which is also not a candidate key.(no more options with 3 attributes possible)
Now we need to check for candidate keys with 4 attributes. Since, only remaining options are CGH and we have to add D only
possible key of size 4 is CGHD whose closure also doesn't give us all of the attributes in the relation (All possible options
covered)
Hence, no of candidate keys are 4 : AD,BD,ED,FD.
Correct Answer: B
 32 votes -- Indranil Maji (537 points)

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 .
Correct Answer: A
 42 votes -- Manoj Kumar (26.7k points)

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.
Correct Answer: B

(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. We can not derive AB → E from the 1st set

Option C is correct because {P, S} → {S}
X∩Y =∅ {S} {P, 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.
 54 votes -- Anoop Sonkar (4.1k points)

Any superset of a key is also a superkey from definition of a superkey.
So, answer is B.
' a superkey can be defined as a set of attributes of a relation schema upon which all attributes of the schema are
functionally dependent
References
 39 votes -- Abhilash Panicker (7.6k points)

The actual design is in 1NF coz 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.
 48 votes -- Bharani Viswas (611 points)

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.
 52 votes -- sriv_shubham (2.8k points)

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.
 25 votes -- Baljit kaur (1k points)


Y is in BCNF because binary attribute.
Z is not in BCNF because S → Q is in Z and S is not Super key.
Dependency Preserving:
QR → S in Z
R → P is in Y
S → Q is in Z
So it is dependency preserving.
Lossless:
Y ∩ Z = R which is is key of Y .
Lossless it is.
Only 2nd is correct.
So Option C is the answer


In 3NF where functional dependency is of type X → Y
X can be the super key or Y can be the prime attribute
Whereas in BCNF where functional dependency is of type X → Y
X should be super key (BCNF is more strict compared to 3NF)
Option (C) says it has a partial dependency ( not even 2NF) .

Option (D) multiple values in a cell. i.e not atomice ( not even 1NF) .
Option (B) says X is not a super key and Y is not a prime attribute. Therefore not 3NF.
Ans (A): Says X is not a super key but Y is a prime attribute. Satisfies one of the conditions of the 3NF formal definition. As X
is not a Super Key it is not in BCNF .
 15 votes -- Srinivas_Reddy_Kotla (775 points)

Decomposition removes redundancy from the database. it is lossless if it’s possible to reconstruct the table from the
given set of decomposition tables using natural join.
Decomposition of a relation R into R1 , R2 is a lossless-join decomposition if at least one of the following functional
dependencies are in F + :
1. ((R1 ∩ R2 ) → (R1 − R2 )) is in F + or
2. ((R1 ∩ R2 ) → (R2 − R1 ) is in F +
Decomposition is lossless iff R1 ⋈ R2 = R
D1 : R = [r1 (PQST ), r2 (PT X), r3 (QY ), r4 (Y ZW)]

⟹ r1 ∩ r2 = (PT )+ = PT Y XZW which is superkey, we can combine them.
So new table is x1 = (PQST X)
+
In the same way; r3 ∩ r4 = Y = Y ZW
which is SK, and so we can merge them.
Thus x2 = (QY ZW)
Now x1 ∩ x2 = Q+ = QY ZW which is SK.
So we can get original table (PQST XY ZW)
So given decomposition D1 is lossless join decomposition.
Similarly we can check for D2
2 : R = [ 1 (PQS), 2 (T X), 3 (QY ), 4 (Y ZW)]

D2 : R = [r1 (PQS), r2 (T X), r3 (QY ), r4 (Y ZW)]
⟹ r3 ∩ r4 = Y + = Y ZW , is Sk we can merge them.
So new table will be x1 = (QY ZW)
Similarly x1 ∩ r1 = Q+ = QY ZW is also Sk,we can combine them.new table will be x2 = (PQSY ZW)
Now x2 ∩ r2 is not superkey. no common attribute is present between them. We can try any other order of combining the
relations and none of them will satisfy the lossless decomposition condition. Hence it is lossy decomposition.
∴ decomposition D2 is lossy decomposition.
Option A is correct.
Ref: lossless-join-and-dependency-preserving-decomposition
References
 3 votes -- Hira (14.1k points)

Option A: (PS)+ = P, Q, R, S, T so PS → T holds.
Option B: (R)+ = R so R → T doesn’t hold.
Option C: (P )+ = P, Q, R so P → R holds.
Option D: (PS)+ = P, Q, R, S, T so PS → Q holds


It is in 2nf - for 2NF all non prime attribute should be fully functionally dependent on key. Here key is empcode and
contains only one attribute hence no partial dependency. But there is transitive dependency in this (pincode -> city, state). So it is
not in 3NF .
answer: B

Answer is A 1NF
Key is {F1 , F2 }
F1 → F3 , F2 → F4 are partial dependencies (a proper subset of candidate key determining a non-key attribute) thus violating
2 NF requirement.
 35 votes -- K Rajashekar (997 points)

Answer is (B).
Apply membership test for all the given Functional Dependencies.
1. CD → AC
C D+ = CDEAB

2. BD → CD
BD+ = BD
i.e. BD cannot derive CD and hence is not implied.

Similarly do for rest two.

As we can see attributes X and Y do not appear in the RHS of any FD and so they need to be part of any
super/candidate key. So, candidate keys are: V XY , WXY , ZXY as these three can determine any other attribute where as a
proper subset of any of them cannot determine all other attributes.
V XZ is not a super key as Y is not there where as V WXY and V WXY Z are super keys but since their proper subsets are also
super keys they are not candidate keys.
Answer is B.
 27 votes -- Pooja Palod (24.1k points)

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) .
(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).
http://www.sztaki.hu/~fodroczi/dbs/dep-pres-own.pdf
References

Answer: D
Here AB is the candidate key and B->G is a partial dependency. So, R is not in 2NF .
3.5.49 Database Normalization: GATE2001-1.23, UGCNET-June2012-III: 18 top☝ ☛ https://gateoverflow.in/716

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.

A decomposition {R1, R2} is a lossless-join decomposition if R1 ∩ R2 → R1 (R1 should be key) or R1 ∩ R2 →
R2 (R2 should be key) but (A,B) ∩ (C,D) = ∅ so lossy join
FD:1 A→B
FD:2 C→D
R1(A,B) have all attributes of FD1 and R2(C,D) have all attributes of FD2 so ,dependency preserved decompostion
Reference : - question no. 8.1 Korth http://codex.cs.yale.edu/avi/db-book/db6/practice-exer-dir/8s.pdf
References
 12 votes -- Rishi yadav (9k points)
3.6 Er Diagram (10) top☝
3.6.1 Er Diagram: GATE CSE 2005 | Question: 75 top☝ ☛ https://gateoverflow.in/1398
Let E1 and E2 be two entities in an E/R diagram with simple-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?
A. 2
B. 3
C. 4
D. 5
gate2005-cse databases er-diagram normal
Answer ☟
Consider the following ER diagram
The minimum number of tables needed to represent M , N , P , R1, R2 is

A. 2
B. 3
C. 4
D. 5
Answer ☟
Consider the following ER diagram

The minimum number of tables needed to represent M , N , P , R1, R2 is
Which of the following is a correct attribute set for one of the tables for the minimum number of tables needed to represent M , N ,
P , R1, R2?
A. M1, M2, M3, P1
B. M1, P1, N1, N2
C. M1, P1, N1
D. M1, P1
Answer ☟
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

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
gate2012-cse databases normal er-diagram
Answer ☟
3.6.5 Er Diagram: GATE CSE 2015 Set 1 | Question: 41 top☝ ☛ https://gateoverflow.in/8309
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-singled attributes a11 and a12 of which a11 is the key attribute. E2 has two singled-valued attributes a21 and a22 of
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
relation are in 3NF is________________.
gate2015-cse-set1 databases er-diagram normal numerical-answers
Answer ☟
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 one of the following conditions, can the relational table for R be merged with that of A?
A. Relationship R is one-to-many and the participation of A in R is total

B. Relationship R is one-to-many and the participation of A in R is partial
C. Relationship R is many-to-one and the participation of A in R is total
D. Relationship R is many-to-one and the participation of A in R is partial
gate2017-cse-set2 databases er-diagram normal
Answer ☟

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.
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 ☟
Which one of the following is used to represent the supporting many-one relationships of a weak entity set in an entity-
relationship diagram?
A. Diamonds with double/bold border
B. Rectangles with double/bold border
C. Ovals with double/bold border
D. Ovals that contain underlined identifiers
gate2020-cse databases er-diagram
Answer ☟
3.6.9 Er Diagram: GATE IT 2004 | Question: 73 top☝ ☛ https://gateoverflow.in/3717
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
A. 2
B. 3
C. 5
D. 4
gate2004-it databases er-diagram normal
Answer ☟
Consider the entities 'hotel room', and 'person' with a many to many relationship 'lodging' as shown below:
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
gate2005-it databases er-diagram easy
Answer ☟
Answers: Er Diagram

We need a separate table for many-to-many relation.
one-to-many relation doesn't need a separate table and can be handled using a foreign key.
So, answer is B - 3 tables.
Reference: MIT notes.

References

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, answers is B.
References

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} .
P(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, answers is A.
References

(C) is incorrect as a relational table requires that, in a row, an attribute can have exactly one value or NULL value.

Answer is 4. 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.
Reference: MIT notes
References

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.
 36 votes -- Arnabi Bej (5.8k points)

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.
 37 votes -- Aakanchha (471 points)

Answer : A
Weak entity set is represented by Rectangles with double/bold border.

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 T 2 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
T 1 : {A11, A12, A13}− key is A11

T 2 : {A21, A22, A11}− key is A21
T 3 : {A21, A23}− {A21, A23}

T 3 : {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.
Correct Answer: B

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.
Correct Answer: C
3.7 Indexing (11) top☝
3.7.1 Indexing: GATE CSE 1989 | Question: 4-xiv top☝ ☛ https://gateoverflow.in/88228
For secondary key processing which of the following file organizations is preferred? Give a one line justification:
A. Indexed sequential file organization.
B. Two-way linked list.
C. Inverted file organization.
D. Sequential file organization.
gate1989 normal databases indexing descriptive
Answer ☟
3.7.2 Indexing: GATE CSE 1990 | Question: 10b top☝ ☛ https://gateoverflow.in/85691
One giga bytes of data are to be organized as an indexed-sequential file with a uniform blocking factor 8. Assuming a block
size of 1 Kilo bytes and a block refrencing pointer size of 32 bits, find out the number of levels of indexing that would be required
and the size of the index at each level. Determine also the size of the master index. The referencing capability (fanout ratio) per
block of index storage may be considered to be 32.
gate1990 databases indexing descriptive
Answer ☟
3.7.3 Indexing: GATE CSE 1993 | Question: 14 top☝ ☛ https://gateoverflow.in/2311
An ISAM (indexed sequential) file consists of records of size 64 bytes each, including key field of size 14 bytes. An address
of a disk block takes 2 bytes. If the disk block size is 512 bytes and there are 16K records, compute the size of the data and index
areas in terms of number blocks. How many levels of tree do you have for the index?
gate1993 databases indexing normal descriptive
Answer ☟
3.7.4 Indexing: GATE CSE 1998 | Question: 1.35 top☝ ☛ https://gateoverflow.in/1672
There are five records in a database.
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
gate1998 databases indexing normal
Answer ☟
3.7.5 Indexing: GATE CSE 2008 | Question: 16, ISRO2016-60 top☝ ☛ https://gateoverflow.in/414
A clustering index is defined on the fields which are of type

A. non-key and ordering
B. non-key and non-ordering
C. key and ordering
D. key and non-ordering
gate2008-cse easy databases indexing isro2016
Answer ☟
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
A. 8 and 0
B. 128 and 6
C. 256 and 4
D. 512 and 5
gate2008-cse databases indexing normal
Answer ☟
Consider a relational table r with sufficient number of records, having attributes A1 , A2 , … , An and let 1 ≤ p ≤ n . Two
queries Q1 and Q2 are given below.
Q1 : πA1 ,…,Ap (σAp =c (r)) where c is a constant

Q2 : πA1 ,…,Ap (σc1 ≤Ap ≤c2 (r)) where c1 and c2 are constants.
The database can be configured to do ordered indexing on Ap or hashing on Ap . Which of the following statements is TRUE?
A. Ordered indexing will always outperform hashing for both queries

B. Hashing will always outperform ordered indexing for both queries
C. Hashing will outperform ordered indexing on Q1 , but not on Q2
D. Hashing will outperform ordered indexing on Q2 , but not on Q1
Answer ☟
An index is clustered, if
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
Answer ☟
3.7.9 Indexing: GATE CSE 2015 Set 1 | Question: 24 top☝ ☛ https://gateoverflow.in/8222
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
A. Dense
B. Sparse
C. Clustered
D. Unclustered
gate2015-cse-set1 databases indexing easy
Answer ☟
Consider a database implemented using B+ tree for file indexing and installed on a disk drive with block size of 4 KB . The
size of search key is 12 bytes and the size of tree/disk pointer is 8 bytes. Assume that the database has one million records. Also
assume that no node of the B+ tree and no records are present initially in main memory. Consider that each record fits into one disk
block. The minimum number of disk accesses required to retrieve any record in the database is _______
gate2020-cse numerical-answers databases b-tree indexing
Answer ☟
A data file consisting of 1, 50, 000 student-records is stored on a hard disk with block size of 4096 bytes. The data file is
sorted on the primary key RollNo . The size of a record pointer for this disk is 7 bytes. Each student-record has a candidate key
attribute called ANum of size 12 bytes. Suppose an index file with records consisting of two fields, ANum value and the record
pointer the corresponding student record, is built and stored on the same disk. Assume that the records of data file and index file are
not split across disk blocks. The number of blocks in the index file is ________
gate2021-cse-set2 numerical-answers databases indexing
Answer ☟
Answers: Indexing
3.7.1 Indexing: GATE CSE 1989 | Question: 4-xiv top☝ ☛ https://gateoverflow.in/88228
Inverted File organization
Because of the following reasons
An index for each secondary key.
· An index entry for each distinct value of the secondary key.
It exhibits better inquiry performance

 4 votes -- Neeraj7375 (1.1k points)
3.7.2 Indexing: GATE CSE 1990 | Question: 10b top☝ ☛ https://gateoverflow.in/85691

First we can understand the terms given in the question:
Uniform blocking factor = 8

This is the no. of records which can be held in a data block.
This information is required for DENSE index which is mandatory when the index is unclustered - data records not ordered by
the search key (there is an index entry for each record) as compared to fully sparse (which has an index entry for each data
block). Since in the question we do not have any information about "record pointer size" we can assume that the index is sparse.
(Solution considering dense index is given at end)
Block size = 1 KB
This is the size of data block (file block containing records) as well as index block (file block containing index entries). Since file
size is given as 1 giga bytes, we get no. of data blocks = 11 GB
KB
= 1 M = 220
Block referencing pointer size = 32 bits = 4 B
This is the pointer size required to point to a block.
The referencing capability (fanout ratio) per block of index storage may be considered to be 32.
This means that an index block can refer to 32 blocks (either data or index blocks). i.e., even though we have 1024 bytes in a
block, and each block pointer size is 4 bytes, it can refer to only 32 blocks. This might be due to large search key size which
must be present for each index entry.
Now, coming to the solution:
No. of entries in first level index (which indexes to the data blocks) (in case of page tables in virtual memory, this will be the
total no. of entries in last level page table) = no. of data blocks (assuming sparse index) = 220
220
No. of index blocks in level 1 = 32 = 215 as each index block can refer to 32 blocks (given fanout) which means size of level 1
index = 215 × 1 KB = 32 MB
215
Since the fanout is 32, no. of index blocks in second level = = 210 .
32
Size of second level index = 210 × 1 KB = 1 MB
10
No. of index blocks in third level = 232 = 32 .
Size of third level index = 32 × 1 KB = 32 KB
32
No. of index blocks in fourth level = 32 = 1 and it occupies 1 KB. Since only 1 index block is there we do not need further
level of indexing.
Searching starts in the last level (this will be level 1 page table in case of virtual memory in OS).
Master Index -- not sure exactly what this means but I assume this is the complete index whose size will be
32 MB + 1 MB + 32 KB + 1 KB = 33.033 MB
Now assuming dense index.

Block pointer size = 32 bits . Since, we have 8 records in a block, we need at least 3 more extra bits for a record pointer. So, we
need to assume 5 bytes for a record pointer. As fanout is given in the question it is not changing when the record pointer size
block size
changes. If fanout was not given, we could have calculated it as search_key_size+record pointer size
1 GB
Here, we need an index entry for each record. So, we need = 1 KB
× 8 = 8 M = 223 entries in first level index.
23
No. of index blocks in first level = 232 = 218
Size of first level index = 218 × 1 KB = 256MB
18
No. of index blocks in second level = 232 = 213
Size of second level index = 213 × 1 KB = 8MB
13
No. of index blocks in third level = 232 = 28
Size of third level index = 28 × 1 KB = 256KB
8
2
No. of index blocks in fourth level = 32 =8
Size of fourth level index = 8 × 1 KB = 8KB
8
No. of index blocks in fifth level = ⌈ 32 ⌉=1
Size of fifth level index = 1 × 1 KB = 1 KB
Master Index size = 256 MB + 8 MB + 256 KB + 8 KB + 1 KB = 264.265 MB


Answer: 3
Size of each index entry = 14 + 2 = 16 B
Block size
Blocking factor of record file = Record size
= 512 B/64 B = 8
Block size
Blocking factor of index file = Index entry size
= 512 B/16 B = 32
No. of Records
No. of Blocks needed for data file = Blocking factor of record file
= 16 K/8 = 2 K
No. of first level index entries = No. of Data Blocks needed for data file = 2 K
No. of first level index blocks = ⌈ No. of first level index entries
Blocking factor of index file
⌉ = ⌈ 2K
32 ⌉ = 64
No. of second level index entries = No. of first level index blocks = 64
No. of second level index blocks = ⌈ No.Blocking

of second level index entries
factor of index file
⌉ = ⌈ 64
32 ⌉ = 2
No. of third level index entries = No. of second level index blocks = 2
No. of third level index blocks = ⌈ No. of third level index entries
Blocking factor of index file
2
⌉ = ⌈ 32 ⌉=1
3.7.4 Indexing: GATE CSE 1998 | Question: 1.35 top☝ ☛ https://gateoverflow.in/1672

Indexing will be on Occupation field because Occupation field lexicographically sorted will give the sequence
1, 3, 2, 5, 4 .
Correct Answer: C
3.7.5 Indexing: GATE CSE 2008 | Question: 16, ISRO2016-60 top☝ ☛ https://gateoverflow.in/414

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.
Reference -> Database Systems book BY Navathe, 6th Edition, 18.1 Types of Single- Level Ordered Indexes Page no. 632.
Answer should be A.

Content of an index will be <key, block pointer> and so will have size 6 + 10 = 16.
In the first level, there will be an entry for each record of the file. So,total size of first-level index
= 16384 * 16
No. of blocks in the first-level = Size of first-level index / block size

= 16384 * 16 / 1024
= 16 * 16 = 256
In the second-level there will be an entry for each block in the first level. So, total number of entries = 256 and total size of

second-level index
= No. of entries * size of an entry

= 256 * 16
No. of blocks in second-level index = Size of second-level index / block size

= 256 * 16 / 1024
=4
Correct Answer: C
 72 votes -- gatecse (63.3k points)

(C) Hashing works well on the 'equal' queries, while ordered indexing works well better on range queries too. For ex
consider B+ Tree, once you have searched a key in B+ tree , you can find range of values via the block pointers pointing to
another block of values on the leaf node level.
 64 votes -- Prateeksha Keshari (1.7k points)

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).
Video:
Video:
 29 votes -- prashant singh (337 points)

Clustered- this is the definition of clustered indexing and for the same reason a table can have only one clustered index.
http://www.ece.rutgers.edu/~yyzhang/spring03/notes/7-B+tree.ppt
Correct Answer: C
References


Given,
1. Search Key: 12 bytes

2. Tree Pointer: 8 bytes
3. Block Size: 4096 bytes
4. Number of database records: 106
Since it's a B+ tree, an internal node only has search key values and tree pointers. Let p be the order of an internal node. Hence,
p(8) + (p − 1)(12) ≤ 4096
which gives p ≤ 205.4 .
Therefore p = 205
Now,
Level Nodes Keys Pointers

1 1 204 205
2 205 204 × 205 2052
3 2052 204 × 2052 2053
Level 3 alone has approximately 8.5 × 106 entries. So we can be sure that a 3-level B+ tree is sufficient to index 106 records.
So to access any record (in the worst case), we need 3 block access to search for the record in the index along with 1 more access
to actually access the record.
Hence, 4 accesses are required.
 34 votes -- Debasish Das (1.5k points)

ANS = 698 .
Index is being built on attribute “ANum” which is Candidate Key, but Given that file is Sorted on Primary Key “Roll No”.
This indicates that The Index must a Secondary Index, (data records not being physically ordered as per the index making a
dense record necessary) so “THERE SHOULD EXIST AN INDEX RECORD FOR EVERY RECORD of Original ‘Student
Table’ ”.
=> Also this Line: “Assume that Records of data file and index file are not split across disc blocks”.
This indicates UNSPANNED STRATEGY.
With This Knowledge, let’s see the Data given.
→ Record Size in Index = 12 + 7 = 19 B (‘ANum’ key size + Record pointer Size), and Block Size = 4096 B
→ So number of Index records in 1 Block = ⌊ 4096
19 ⌋ = 215 records in 1 block (Remember again, unspanned strategy).
Total Number of records 1, 50, 000

→ So number of blocks in the Index file = =⌈ ⌉ = 698.
Records per block 215
(Recall that this is Secondary Index)
 4 votes -- Amcodes (745 points)
3.8 Joins (7) top☝
3.8.1 Joins: GATE CSE 2004 | Question: 14 top☝ ☛ https://gateoverflow.in/1011
Consider the following relation schema pertaining to a students database:
Students (rollno, name, address)

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
960, 8

C. 960, 8
D. 960, 120
gate2004-cse databases easy joins natural-join
Answer ☟
Consider the following relations A, B and C :

B
A
ID Name Age C
ID Name Age
15 Shreya 24 ID Phone Area
12 Arun 60
25 Hari 40 10 2200 02
15 Shreya 24
98 Rohit 20 99 2100 01
99 Rohit 11
99 Rohit 11
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<15 C
A. 7
B. 4
C. 5
D. 9
gate2012-cse databases joins normal
Answer ☟
3.8.3 Joins: GATE CSE 2014 Set 2 | Question: 30 top☝ ☛ https://gateoverflow.in/1989
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 intermediate results. Assuming size(r(R)) < size(s(S)), the
join will have fewer number of disk block accesses if
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 .
gate2014-cse-set2 databases normal joins
Answer ☟
3.8.4 Joins: GATE IT 2005 | Question: 82a top☝ ☛ https://gateoverflow.in/3847
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.
If Nested-loop join algorithm is employed to perform the join, with the most appropriate choice of table to be used in outer loop, the
number of block accesses required for reading the data are
A. 800000
B. 40080
C. 32020
D. 100
gate2005-it databases normal joins
Answer ☟

3.8.5 Joins: GATE IT 2005 | Question: 82b top☝ ☛ https://gateoverflow.in/3848
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.
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
A. 0
B. 30400
C. 38400
D. 798400
gate2005-it databases normal joins
Answer ☟
3.8.6 Joins: GATE IT 2006 | Question: 14 top☝ ☛ https://gateoverflow.in/3553
Consider the relations r1 (P, Q, R) and r2 (R, S, T) with primary keys P and R respectively. The relation r1 contains 2000
tuples and r2 contains 2500 tuples. The maximum size of the join r1 ⋈ r2 is :
A. 2000
B. 2500
C. 4500
D. 5000
gate2006-it databases joins natural-join normal
Answer ☟
Consider the following relation schemas :
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)

B. П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))
gate2007-it databases joins relational-algebra normal
Answer ☟
Answers: Joins

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.

Given relations A, B and C :
B
A
ID Name Age C
ID Name Age
15 Shreya 24 ID Phone Area
12 Arun 60
25 Hari 40 10 2200 02
15 Shreya 24
98 Rohit 20 99 2100 01
99 Rohit 11
99 Rohit 11
This is an example of theta join and we know: R ⋈θ S = σθ (R × S)
∴ (A ∪ B) ⋈A.Id>40∨C.Id<15 C = (A.Id>40 ((A ∪ B) × C)) ∪ (C.Id<15 ((A ∪ B) × C))
To make the query more efficient we can perform the select operation before the cross product.
∴ (A ∪ B) ⋈A.Id>40∨C.Id<15 C = (A.Id>40 (A ∪ B) × C) ∪ ((A ∪ B) ×C.Id<15 C)
Now calculate A ∪ B :
ID Name Age
12 Arun 60
15 Shreya 24
25 Hari 40
98 Rohit 20
99 Rohit 11
Please note that union is a set operation and duplicates will not be included by default.
First perform cross-product (A.Id>40 (A ∪ B) × C) , i.e., Multiply each row of A.Id>40 (A ∪ B) with each row of C :
ID Name Age C.ID Phone Area

98 Rohit 20 10 2200 02
98 Rohit 20 99 2100 01
99 Rohit 11 10 2200 02
99 Rohit 11 99 2100 01
Now perform cross-product ((A ∪ B) ×C.Id<15 C) , i.e., Multiply each row of (A ∪ B) with each row of C.Id<15 C :

12 Arun 60 10 2200 02
15 Shreya 24 10 2200 02
25 Hari 40 10 2200 02
Now take the union: (A.Id>40 (A ∪ B) × C) ∪ ((A ∪ B) ×C.Id<15 C)
We will get:

12 Arun 60 10 2200 02
15 Shreya 24 10 2200 02
25 Hari 40 10 2200 02
98 Rohit 20 10 2200 02
98 Rohit 20 99 2100 01
99 Rohit 11 10 2200 02
99 Rohit 11 99 2100 01
which has 7 Tuples, hence answer is A.

 8 votes -- Sourabh Gupta (4k points)
50. 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
Correct Answer: A
3.8.3 Joins: GATE CSE 2014 Set 2 | Question: 30 top☝ ☛ https://gateoverflow.in/1989

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 ques, |R| < |S|
(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
So, answer is A.
 20 votes -- Anurag Semwal (6.7k points)
3.8.4 Joins: GATE IT 2005 | Question: 82a top☝ ☛ https://gateoverflow.in/3847

We just have to think which table would be in the outer loop. To minimize block accesses, we have to put that table
outside having fewer records because for each outer record, one block access inside will be required.

Therefore, putting 2nd table outside,
for every 400 records

80 block accesses in the first table
= 32000
20 block accesses of the outer table.
So, the answer comes out to be 32000 + 20 = 32020

Correct Answer: C.
 84 votes -- Vishesh Bajpai (383 points)
Reference: http://en.wikipedia.org/wiki/Nested_loop_join
As per this reference this algorithm will involve nr ∗ bs + br block transfers
T1 can be either R or T2
If R is T1 then total number of block accesses is 2000 × 20 + 80 = 40080

If R is T2 then total number of block accesses is 400 × 80 + 20 = 32020
So, better is the second case (32020) Hence, I go for option C.

References
3.8.5 Joins: GATE IT 2005 | Question: 82b top☝ ☛ https://gateoverflow.in/3848

In Nested loop join for each tuple in first table we scan through all the tuples in second table.
Here we will take table T 2 as the outer table in nested loop join algorithm. The number of block accesses then will be
20 + (400 × 80) = 32020
In block nested loop join we keep 1 block of T 1 in memory and 1 block of T 2 in memory and do join on tuples.

For every block in T1 we need to load all blocks of T2. So number of block accesses is 80*20 + 20 = 1620
So, the difference is 32020 − 1620 = 30400
(B) 30400
 65 votes -- Omesh Pandita (1.9k points)

The common attribute is R and it is the primary key in the second relation. So R value should be distinct (primary key
implies unique) for 2500 rows. Hence when we do join, maximum possible number of tuples is 2000.
Correct option is A.

It should be A. As in B we are doing a join between two massive table whereas in A we are doing join between relatively
smaller table and larger one 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 depositer table with the selection condition.
Options C and D are invalid as there is no b-city column in a-Schema.
Lets see in detail. Let there be 100 different branches. Say about 10% of accounts are below 0. Also, let there be 10, 000
accounts in a branch amounting to 1, 000, 000 total accounts. A customer can have multiple accounts, so let there be on average
2 accounts per customer. So, this amounts to 2, 000, 000 total entries in depositor table. Lets assume these assumptions are true
for all the branches. So, now lets evaluate options A and B.
1. All the accounts in Agra branch, filter by positive balance, and then depositor details of them. So,
Get branch name from branch table after processing 100 records
Filter 10, 000 accounts after processing 1, 000, 000 accounts belonging to Agra
Filter 1000 accounts after processing 10,000 accounts for positive balance
Get 500 depositor details after processing 2, 000, 000 entries for the given 1000 accounts (assuming 1 customer having 2
accounts). So, totally this amounts to 2, 000, 000, 000 record processing.
So totally ≈ 2 billion records needs processing.
2. All the positive balance accounts are found first, and then those in Agra are found.
Filter 100, 000 accounts after processing 1, 000, 000 accounts having positive balance
Find the deposito details of these accounts. So, 100, 000*2, 000, 000 records need processing and this is a much larger
value than for query A. Even if we reduce the percentage of positive balance (10 we assumed) the record processing of
query A will also get reduced by same rate. So, overall query A is much better than query B.
 59 votes -- Shaun Patel (6.1k points)
3.9 Multivalued Dependency 4nf (1) top☝

3.9.1 Multivalued Dependency 4nf: GATE IT 2007 | Question: 67 top☝ ☛ https://gateoverflow.in/3512
Consider the following implications relating to functional and multivalued 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?

A. 0
B. 1
C. 2
D. 3
gate2007-it databases database-normalization multivalued-dependency-4nf normal
Answer ☟
Answers: Multivalued Dependency 4nf
3.9.1 Multivalued Dependency 4nf: GATE IT 2007 | Question: 67 top☝ ☛ https://gateoverflow.in/3512

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.
Correct Answer: C
3.10 Natural Join (3) top☝
3.10.1 Natural Join: GATE CSE 2005 | Question: 30 top☝ ☛ https://gateoverflow.in/1366
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?
A. s ⊂ r
B. r ∪ s = r
C. r ⊂ s
D. r ∗ s = s
gate2005-cse databases relational-algebra natural-join normal
Answer ☟
The following functional dependencies hold for relations R(A, B, C) and S(B, D, E).
B→A
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

gate2010-cse databases normal natural-join database-normalization
Answer ☟
3.10.3 Natural Join: GATE CSE 2015 Set 2 | Question: 32 top☝ ☛ https://gateoverflow.in/8151
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?
A. R contains a, b, e, f, g but not c, d .
B. R contains all 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 .
gate2015-cse-set2 databases normal natural-join
Answer ☟
Answers: Natural Join

Answer is C r ⊂ s.
s = r1 * r2
r r1 r2 A B C D
A B C D A B C A D 1 2 3 3
1 2 3 3 1 2 3 1 3 1 2 3 4
1 5 3 4 1 5 3 1 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.

(A) 100.
Natural join will combine tuples with same value of the common rows(if there are two common rows then both values must be
equal to get into the resultant set). So by this definition we can get at the max only 100 common values.
3.10.3 Natural Join: GATE CSE 2015 Set 2 | Question: 32 top☝ ☛ https://gateoverflow.in/8151

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.

3.11 Referential Integrity (4) top☝
3.11.1 Referential Integrity: GATE CSE 1997 | Question: 6.10, ISRO2016-54 top☝ ☛ https://gateoverflow.in/2266
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
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
gate1997 databases referential-integrity easy isro2016
Answer ☟
3.11.2 Referential Integrity: GATE CSE 2005 | Question: 76 top☝ ☛ https://gateoverflow.in/1399
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.
A C
2 4
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)
gate2005-cse databases referential-integrity normal
Answer ☟

3.11.3 Referential Integrity: GATE CSE 2017 Set 2 | Question: 19 top☝ ☛ https://gateoverflow.in/118236
Consider the following tables T 1 and T 2.

T1
T2
P Q
R S
2 2
2 2
3 8
8 3
7 3
3 2
5 8
9 7
6 9
5 7
8 5
7 2
9 8
In table T 1 P is the primary key and Q is the foreign key referencing R in table T 2 with on-delete cascade and on-update cascade.
In table T 2, R is the primary key and S is the foreign key referencing P in table T 1 with on-delete set NULL and on-update
cascade. In order to delete record ⟨3, 8⟩ from the table T 1, the number of additional records that need to be deleted from table T 1 is
_______
gate2017-cse-set2 databases numerical-answers referential-integrity normal
Answer ☟
Consider the following statements S1 and S2 about the relational data model:
S1: A relation scheme can have at most one foreign key.

S2: A foreign key in a relation scheme R cannot be used to refer to tuples of R.
Which one of the following choices is correct?

A. Both S1 and S2 are true
B. S1 is true and S2 is false
C. S1 is false and S2 is true
D. Both S1 and S2 are false
gate2021-cse-set2 databases referential-integrity
Answer ☟
Answers: Referential Integrity
3.11.1 Referential Integrity: GATE CSE 1997 | Question: 6.10, ISRO2016-54 top☝ ☛ https://gateoverflow.in/2266

R S
a (PK) b c d (FK referring to PK of R) e f
1 2
2 1
Insert into R cannot cause any violation.

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 cannot cause any violation.
Delete from R can cause violation if any tuple is deleted, and as a result a value in 'a' gets deleted which is referenced to
by 'd' in S.
Correct Answer: B
3.11.2 Referential Integrity: GATE CSE 2005 | Question: 76 top☝ ☛ https://gateoverflow.in/1399

(C)
(2, 4) (5, 2) (7, 2)

Since deleting (2, 4) , since 2 is a primary key, you have to delete its foreign key occurence i.e (5, 2) and (7, 2)
Since we are delting 5, and 7 we have delete it foreign key occurence i.e (9, 5) .
There is no foreign key occurence for 9.

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.
 74 votes -- Prateek Kumar (1.1k points)

Both S1 and S2 are FALSE.
In a relation scheme multiple foreign attributes can be present referring to primary keys of other relation schemes. A typical
example is an EXAM_RESULTS(sid,eid,marks) scheme where sid and eid are foreign keys referring to the primary keys in
STUDENT and EXAM schemes respectively.
S2 is FALSE because a foreign key can refer to the same scheme (self-referencing foreign key). A typical example is an
EMPLOYEE(eid, mid, …) scheme where mid is the Manager ID referring to the primary key eid of the same scheme.
3.12 Relational Algebra (26) top☝
3.12.1 Relational Algebra: GATE CSE 1992 | Question: 13b top☝ ☛ https://gateoverflow.in/43581
Suppose we have a database consisting of the following three relations:
FREQUENTS (CUSTOMER, HOTEL)

SERVES (HOTEL, SNACKS)
LIKES (CUSTOMER, SNACKS)
The first indicates the hotels each customer visits, the second tells which snacks each hotel serves and last indicates which snacks
are liked by each customer. Express the following query in relational algebra:
Print the hotels the serve the snack that customer Rama likes.
gate1992 databases relational-algebra normal descriptive
Answer ☟
3.12.2 Relational Algebra: GATE CSE 1994 | Question: 13 top☝ ☛ https://gateoverflow.in/2509
COURSES (cno, cname)

STUDENTS (rollno, sname, age, year)
REGISTERED_FOR (cno, rollno)
The underlined attributes indicate the primary keys for the relations. The ‘year’ attribute for the STUDENTS relation indicates the
year in which the student is currently studying (First year, Second year etc.)
A. Write a relational algebra query to print the roll number of students who have registered for cno 322.
B. Write a SQL query to print the age and year of the youngest student in each year.
gate1994 databases relational-algebra sql normal descriptive

Answer ☟
3.12.3 Relational Algebra: GATE CSE 1994 | Question: 3.8 top☝ ☛ https://gateoverflow.in/2494
Give a relational algebra expression using only the minimum number of operators from (∪, −) which is equivalent to R ∩ S.
Answer ☟
Consider the relation scheme.
AUTHOR (ANAME, INSTITUTION, ACITY, AGE)

PUBLISHER (PNAME, PCITY)
BOOK (TITLE, ANAME, PNAME)
Express the following queries using (one or more of) SELECT, PROJECT, JOIN and DIVIDE operations.
A. Get the names of all publishers.

B. Get values of all attributes of all authors who have published a book for the publisher with PNAME=’TECHNICAL
PUBLISHERS’.
C. Get the names of all authors who have published a book for any publisher located in Madras
Answer ☟
A library relational database system uses the following schema
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))
gate1996 databases relational-algebra descriptive
Answer ☟
3.12.6 Relational Algebra: GATE CSE 1997 | Question: 76-a top☝ ☛ https://gateoverflow.in/19838
Consider the following relational database schema:
EMP (eno name, age)

PROJ (pno name)
INVOLVED (eno, pno)
EMP contains information about employees. PROJ about projects and involved about which employees involved in which projects.
The underlined attributes are the primary keys for the respective relations.
What is the relational algebra expression containing one or more of {σ, π, ×, ρ, −} which is equivalent to SQL query.
select eno from EMP|INVOLVED where EMP.eno=INVOLVED.eno and INVOLVED.pno=3
gate1997 databases sql relational-algebra descriptive
Answer ☟

Given two union compatible relations R1 (A, B) and R2 (C, D), what is the result of the operation R1 ⋈A=C∧B=D R2 ?
A. R1 ∪ R2
B. R1 × R2
C. R1 – R2
D. R1 ∩ R2
gate1998 normal relational-algebra
Answer ☟
Consider the following relational database schemes:
COURSES (Cno, Name)

PRE_REQ(Cno, Pre_Cno)
COMPLETED (Student_no, Cno)
COURSES gives the number and name of all the available courses.
PRE_REQ gives the information about which courses are pre-requisites for a given course.
COMPLETED indicates what courses have been completed by students
Express the following using relational algebra:
List all the courses for which a student with Student_no 2310 has completed all the pre-requisites.
Answer ☟
3.12.9 Relational Algebra: GATE CSE 1999 | Question: 1.18, ISRO2016-53 top☝ ☛ https://gateoverflow.in/1471
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
A. m + n and 0
B. mn and 0
C. m + n and |m − n|
D. mn and m + n
gate1999 databases relational-algebra easy isro2016
Answer ☟
Given the relations
employee (name, salary, 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
gate2000-cse databases relational-algebra easy isro2016
Answer ☟

Suppose the adjacency relation of vertices in a graph is represented in a table Adj (X, Y ). Which of the following queries
cannot be expressed by a relational algebra expression of constant length?
A. List all vertices adjacent to a given vertex

B. List all vertices which have self loops
C. List all vertices which belong to cycles of less than three vertices
D. List all vertices reachable from a given vertex
gate2001-cse databases relational-algebra normal
Answer ☟
Let r and s be two relations over the relation schemes R and S respectively, and let A be an attribute in R. The relational
algebra expression σA=a (r ⋈ s) is always equal to
A. σA=a (r)
B. r
C. σA=a (r) ⋈ s
gate2001-cse databases relational-algebra
Answer ☟
A university placement center maintains a relational database of companies that interview students on campus and make job
offers to those successful in the interview. The schema of the database is given below:
COMPANY(−cname
−−−−, clocation) STUDENT(−
srollno
−−−−−, sname, sdegree)
INTERVIEW(cname, srollno , idate) OFFER(cname, srollno , osalary)
−−−−−−−−−−− −−−−−−−−−−−
The COMPANY relation gives the name and location of the company. The STUDENT relation gives the student’s roll number,
name and the degree program for which the student is registered in the university. The INTERVIEW relation gives the date on
which a student is interviewed by a company. The OFFER relation gives the salary offered to a student who is successful in a
company’s interview. The key for each relation is indicated by the underlined attributes
a. Write a relational algebra expressions (using only the operators ⋈, σ, π, ∪, − ) for the following queries.
i. List the rollnumbers and names of students who attended at least one interview but did not receive any job offer.
ii. List the rollnumbers and names of students who went for interviews and received job offers from every company
with which they interviewed.
b. Write an SQL query to list, for each degree program in which more than five students were offered jobs, the name of the
degree and the average offered salary of students in this degree program.
gate2002-cse databases normal descriptive relational-algebra sql
Answer ☟
Consider the following SQL query

Select distinct a1 , a2 , … , an
from r1 , r2 , … , rm
where P
For an arbitrary predicate P, this query is equivalent to which of the following relational algebra expressions?
A. Πa1 ,a2 ,…an σp (r1 × r2 × ⋯ × rm )
p ( 1 ⋈ 2 ⋈⋯⋈ m)

B. Πa1 ,a2 ,…an σp (r1 ⋈ r2 ⋈ ⋯ ⋈ rm )
C. Πa1 ,a2 ,…an σp (r1 ∪ r2 ∪ ⋯ ∪ rm )
D. Πa1 ,a2 ,…an σp (r1 ∩ r2 ∩ ⋯ ∩ rm )
Answer ☟
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).
π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 student
D. names of girl students with more marks than all the boy students
Answer ☟
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) what 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?
π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.
Answer ☟
Let R and S be two relations with the following schema

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

Answer ☟
Suppose R1 (− −, B) and R2 (−
A −, D) are two relation schemas. Let r1 and r2 be the corresponding relation instances. B is a
C
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?
A. ∏B (r1 ) − ∏C (r2 ) = ∅
B. ∏C (r2 ) − ∏B (r1 ) = ∅
C. ∏B (r1 ) = ∏C (r2 )
D. ∏B (r1 ) − ∏C (r2 ) ≠ ∅
Answer ☟
3.12.19 Relational Algebra: GATE CSE 2014 Set 3 | Question: 21 top☝ ☛ https://gateoverflow.in/2055
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 ?
A. πA1 (σ(F1∧F2) (r))

B. πA1 (σ(F1∨F2) (r))
C. πA2 (σ(F1∧F2) (r))
D. πA2 (σ(F1∨F2) (r))
gate2014-cse-set3 databases relational-algebra easy
Answer ☟
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.
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.
C. some of his/her dependents.
D. all of his/her dependents.
gate2014-cse-set3 databases relational-algebra normal
Answer ☟
SELECT operation in SQL is equivalent to
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
gate2015-cse-set1 databases sql relational-algebra easy

Answer ☟
Consider a database that has the relation schema CR(StudentName, CourseName). An instance of the schema CR is as given
below.
StudentName CourseName
SA CA
SA CB
SA CC
SB CB
SB CC
SC CA
SC CB
SC CC
SD CA
SD CB
SD CC
SD CD
SE CD
SE CA
SE CB
SF CA
SF CB
SF CC
The following query is made on the database.
T 1 ← πCourseName (σStudentName=SA (CR))

T 2 ← CR ÷ T 1
The number of rows in T 2 is ______________ .
gate2017-cse-set1 databases relational-algebra normal numerical-answers
Answer ☟
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?
A. σB<5 (r ⋈ s)
B. σB<5 (r LOJ s)
C. r LOJ (σB<5 (s))
D. σB<5 (r) LOJ s
Answer ☟
Consider the following relations P(X, Y , Z), Q(X, Y , T ) and R(Y , V ) .
Table: Q

Table: P Table: Q Table: R
X Y Z X Y T Y V
X1 Y1 Z1 X2 Y1 2 Y1 V1
X1 Y1 Z2 X1 Y2 5 Y3 V2
X2 Y2 Z2 X1 Y1 6 Y2 V3
X2 Y4 Z4 X3 Y3 1 Y2 V2
How many tuples will be returned by the following relational algebra query?
Πx (σ(P.Y=R.Y∧R.V=V2)) (P × R))– Πx (σ(Q.Y=R.Y∧Q.T>2)) (Q × R))
Answer: ________
gate2019-cse numerical-answers databases relational-algebra
Answer ☟
The following relation records the age of 500 employees of a company, where empNo (indicating the employee number) is
the key:
empAge(empNo , age)
−−−−−−
Consider the following relational algebra expression:
ΠempNo (empAge ⋈(age>age1) ρempNo1,age1 (empAge))
What does the above expression generate?
A. Employee numbers of only those employees whose age is the maximum

B. Employee numbers of only those employees whose age is more than the age of exactly one other employee
C. Employee numbers of all employees whose age is not the minimum
D. Employee numbers of all employees whose age is the minimum
gate2021-cse-set1 databases relational-algebra
Answer ☟
3.12.26 Relational Algebra: GATE IT 2005 | Question: 68 top☝ ☛ https://gateoverflow.in/3831
A table 'student' with schema (roll, name, hostel, marks), and another table 'hobby' with schema (roll, hobbyname) contains
records as shown below:
Table: hobby
Roll Hobby Name
Table: student
1798 chess
Roll Name Hostel Marks
1798 music
1798 Manoj Rathor 7 95
2154 music
2154 Soumic Banerjee 5 68
2369 swimming
2369 Gumma Reddy 7 86
2581 cricket
2581 Pradeep pendse 6 92
2643 chess
2643 Suhas Kulkarni 5 78
2643 hockey
2711 Nitin Kadam 8 72
2711 volleyball
2872 Kiran Vora 5 92
2872 football
2926 Manoj Kunkalikar 5 94
2926 cricket
2959 Hemant Karkhanis 7 88
2959 photography
3125 Rajesh Doshi 5 82
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))
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
gate2005-it databases sql relational-algebra normal
Answer ☟
Answers: Relational Algebra
3.12.1 Relational Algebra: GATE CSE 1992 | Question: 13b top☝ ☛ https://gateoverflow.in/43581

OPTIMIZED ANSWER
Πhotel ((σcustomer=‘‘Rama" (LIKES) ) ⋈ SERV ES )
 35 votes -- Shubham Pandey (5k points)

A. πrollno (σcno. =322 (REGISTERED_FOR))
B. SELECT year, min(age) FROM STUDENTS GROUP BY year
In the second question we have to find the year and youngest student from that year. So, we have to apply MIN aggregate
function on each year (group by year).
 31 votes -- SAKET NANDAN (4.2k points)

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.

A. πpname(publishers)
B. πauthers.∗ (σbook.pname="TECHNICAL PUBLISHERS" (book) ⋈ authors)
C. πbook.aname(σpublishers.pcity="Madras" (publishers) ⋈ book)

 24 votes -- Sheshang M. Ajwalia (2.6k points)

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
3.12.6 Relational Algebra: GATE CSE 1997 | Question: 76-a top☝ ☛ https://gateoverflow.in/19838

πeno (σEMP.eno=INVOLVED.eno∧INVOLVED.pno=3 (EMP × INVOLVED))

This question is an example of Theta Join,
r ⋈θ s = σθ (r × s)
The join here will be selecting only those tuples where A = C and B = D, meaning it is the intersection. D option.

T1 will have all the available course numbers
T2 will have all the course numbers completed by student2310
T3 will have the combination of all the courses and the courses completed by student2310
PRE_REQ − T3 (set minus operation) will return us all the entries of PRE_REQ which are not there in T3 ,
Suppose ⟨C1 , C5 ⟩ is a particular tuple of (PRE-REQ − T3 ),
Now what does it imply? ⟹ It implies that C5 is one of the prerequisite course for C1 which has not been completed by C5 .
Proof: If student2310 would have completed C5 then definitely ⟨C1 , C5 ⟩ should have been there in T3 (remember T3 is
the combination of all the courses and the courses completed by student2310) and in that case (PRE_REQ − T3 ) can not have
⟨C1 , C5 ⟩ as a tuple.
So, for any such ⟨C1 , C5 ⟩ tuple, (⟨C1 , any course id ⟩) of PRE_REQ − T3 , C1 should not be printed as output (Since there is
some prerequisite course for C1 which student2310 has not completed).
Now, suppose we have not got any tuple as a result of (PRE_REQ − T3 ) where C2 is there under cno attribute (⟨C2 , any
course id⟩), what does it imply? ⟹ It implies that student2310 has completed all the prerequisite courses C2 .
Hence, in order to get the final result we need to project cno from (PRE_REQ − T3 ) and subtract it from T1 .
T1 ← πcno (COURSES)
T2 ← ρT2 (std2310completedcourses) (πcno (σstudent_no=2310 (COMPLETED)))
T3 ← T1 × T2
T4 ← ρT4 (cno, pre_cno) (PRE_REQ − T3 )
Result ← T1 − πcno (T4 )
 21 votes -- Sourav Basu (2.7k points)

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.

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_name depart)
(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.=x depart)
(c) We cannot generate relational algebra of aggregate functions using basic operations. We need extended operations here.
Option (c).
 43 votes -- Mithlesh Upadhyay (4.3k points)

The answer is D.
A. This is a simple select query.

B. This is the simple query we need to check X = Y in the where clause.
C. Cycle < 3 . Means cycles of lengths 1 and 2. The cycle of length 1 is easy., the same as self-loop. The cycle of length 2 is
also not too hard to compute. Though it'll be a bit more complex, will need to do like (X, Y ) & (Y , X) both present and
X! = Y . We can do this with a constant length (not depending on the number of tuples) RA query.
D. This is the hardest part. Here we need to find closure of vertices. This will need a kind of loop. If the graph is like a
skewed tree, our query must loop for O(N) times. We can't do this with a constant length query here.
Answer: D.

Answer is C.
C is just the better form of query, more execution friendly because requires less memory while joining. query, given in question
takes more time and memory while joining.
(I will write only useful attributes in relation which are required)

Ex: INTERVIEW
company name student roll
A 1

B 1
C 1
A 2
B 2
A 3
OFFER
company name student roll
A 1
B 1
C 1
A 2
So the student with rolls 1,2,3 interviewed. Student 1 did sit for all companies, got the job in all companies A,B,C.
Student 2 sat for A,B, got job in A only. Student 3 sat for A, did not get.
a) Part i) :
1
2
3
minus
1
2
equals to
∏scrollno (Interview) - ∏scrollno( Offer)
You got the required student's roll numbers but to print their names, store that in Temp and join with Student table.
∏ scrollno,sname ( Temp ⋈ Student)
a) Part ii) : Those who got interviewed (includes those who got jobs in all,some,none)
Now interviewed - offer = those who did not get jobs or got in some.
B 2
A 3
Now again subtract whatever you got from all students of the interview again
1
2
3
minus
2
3
equals to
But note that it is not an intersection. You may think.... A-(A-B) so intersection.
But it is not... We are doing A-B on all tuples.
But the next subtraction is done on a particular attribute. (It became distinct since we focused on it only)
∏scrollno (Interview) - ∏scrollno( Interview - Offer)
You got the required student's roll numbers but to print their names, store that in Temp and join with Student table.
∏ scrollno,sname ( Temp ⋈ Student)
b) select s.sdegree,AVG(o.osalary) from Student s,Offer o where s.srollno=o.srollno having count(distinct s.srollno)>5 group by

s.sdegree;
 40 votes -- Ahwan Mishra (10.2k points)

select distinct in SQL is equivalent to project and by default relation 1, relation 2 in SQL corresponds to cross-product.
So, option A.

OPTION : (D)
The given query states the following conditions:
Sex = F∧
x = M∧ → (1)
Marks ≤ m
Let the relation be Student(Name, Sex, Marks)
Name Sex Marks

S1 F 30
S2 F 10
S3 M 20
Student(Name, Sex, Marks) Relation is renamed as Student(n, x, m).

Taking the cross product of the relations
No. Name Sex Marks n x m

1 S1 F 30 S1 F 30
2 S1 F 30 S2 F 10
3 S1 F 30 S3 M 20
4 S2 F 10 S1 F 30
5 S2 F 10 S2 F 10
6 S2 F 10 S3 M 20
7 S3 M 20 S1 F 30
8 S3 M 20 S2 M 10
9 S3 M 20 S3 M 30
Selecting the tuple (row#6 from the above table), which satisfies the condition (1) and PROJECTING Πname ⟹ S2
S1
Πname(σsex=F (Student)) =
S2
Hence, the query:
⎡ student ⋈ σx,x,m (student) ⎤

⎢ ⎥
Πname [ σsex=F (student) ] − Πname ⎢ ⎥
sex = F∧
⎢
⎢ ⎥
⎥
x = M∧
⎣ marks ≤ m ⎦
S1
– S2 = S1
S2
Let us take another relation data of Student(Name, Sex, Marks)

Name Sex Marks
S1 M 100 > highest marks of M student
S2 F 50 > highest marks of F student
S3 M 40
S4 F 30
Taking the cross product
No. Name Sex Marks n x m

1 S1 M 100 S1 M 100
2 S1 M 100 S2 F 50
3 S1 M 100 S3 M 40
4 S1 M 100 S4 F 30
5 S2 F 50 S1 M 100
6 S2 F 50 S2 F 50
7 S2 F 50 S3 F 40
8 S2 F 50 S4 F 30
9 S3 M 100 S1 M 100
10 S3 M 100 S2 F 50
11 S3 M 100 S3 M 40
12 S3 M 100 S4 F 30
13 S4 F 30 S1 M 100
14 S4 F 30 S2 F 50
15 S4 F 30 S3 M 40
16 S4 F 30 S4 F 30
Consider the row numbers 5, 13, 15 from the above table,
S2
⟹ Female students who scored less than equal to some Male students.
S4
S2
Πname[σsex=F (Student)] =
S4
Hence, the result of the query will be:
S2 S2
− = {}
S4 S4
From the above relational data of table Student(Name, Sex, Marks)
(D) is the correct option
In short,
{≥ All boys} =∣ universal ∣ − ∣< some M∣
{> All boys} =∣ universal ∣ − ∣≤ some M∣
{≥ some boys} =∣ universal ∣ − ∣< all M∣
 126 votes -- Akhil Nadh PC (16.5k points)
ENROLL

ENROLL
−−−−−−−−
STUDENTINFO
1 C1
−−−−−−−−−−−−−−
1 A M 1 C2
2 A F 2 C1
3 A F 2 C2
3 C2
πcourceId (σsex=“female" (studInfo)) × πcourseId (enroll)
2 C1
2 C1
2 C2
⟹ ∗ =
3 C1
3 C2
3 C2
(πstudId (σsex=“female" (studInfo)) × πcourseId (enroll)) − enroll)
⟹ 3 C1
πcourceId ((πstudId (σsex=“female" (studInfo)) × πcourseId (enroll)) − enroll)
⟹ C1
C1 is a course id in which not all girl students enrolled.

i.e. a proper subset of girls students appeared.
Hence (B) is the correct answer.
Ans is b,
First it does a cross join between female students id and all course ids, then subtract the entries which are already present in
enroll table.
Remaining are the courseids which are NOT done by at least one female student

(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 "⟩}
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 "⟩}


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.

(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.

(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.

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.
 46 votes -- Anoop Sonkar (4.1k points)

ANS) 4
1. CA
T1 WILL GIVE :- 2. CB
3. CC

1. SA
2. SC
T2 = CR ÷ T1 = All the tuples in CR which are matched with every tuple in T1 :
3. SD
4. SF
//SB IS NOT MATCHED WITH CA, SE IS NOT MATCHED WITH CC
 54 votes -- jatin saini (4.2k points)

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.

R ⋅ V = V 2 , there are two tuples which have Y parameter as Y 3 and Y 2.
P ⋅ Y = R ⋅ Y , there are no coincide with Y 3, and there is one tuple coincide with Y 2 which have X parameter as X2 .
ΠX (σ(P.Y=R.Y Λ R.V=V2) (P × R)) = {X2 }
Q ⋅ T > 2 , there are two tuples which have Y parameter as Y 1 and Y 2 which have X parameter as X1
(there is no need of checking R in this query part !)
ΠX (σ(Q.Y=R.Y Λ Q.T>2) (Q × R)) = {X1 }
ΠX (σ(P.Y=R.Y Λ R.V=V2) (P × R)) − ΠX (σ(Q.Y=R.Y Λ Q.T>2) (Q × R)) = {X2 } − {X1 } = {X2 }
Number of Tuples = 1

Correct Answer: C
Whenever a Database Problem intimidating like the above one(maybe it’s just me) appears, it’s often worth to Dissect the
statements for Individual components and build up your arguments from there rather than attempting it head-on by some random
example/argument only to get swayed by your hidden biases and choose the wrong answer.
Couple of Basic Ideas:

ρr1(x,y,…) is the rename operation here, it’s used to change the name of the empAge′ s attributes empNo, age to
empNo1, age1 to resolve potential conflicts that can arise while referring the relations’(the table) attributes(column) when
using relations that might share a common attribute name.
⋈<cond> is a combination of σ and × where we take the Cross Product at First between the two relations and apply the tuple
select condition supplied to ⋈ by using σ . So ⋈ equals σ<cond> (A × B)
Π<attr> is a Column Select Operation in naive words, it’s supplied with attributes that needs to be selected.
A Relation contains only unique tuples unlike in conventional SQL Databases.
Now,
1. First the ρ operator renames the RHS relation to empNo1, age1 .
2. We take the cross product of both the relations, each tuple in A(unmodified relation empAge) will be combined with every
tuple in B(renamed relation empAge).
3. We filter the tuples according to the condition age > age1 which implies those tuples whose age values in A that are

greater than at least one of B are selected. Since A are B are the same here only those values which aren’t the minimum
are selected in A are selected(>).
4. We find out the set of unique empNo by using Projection(Π)(Note: empNo derived from LHS side of ⋈ the original
relation A that we were talking about).
Since the empNo is derived from relation A(LHS) whose age attribute is greater than the relation’s minimum implies
employees from A are selected whose age isn’t the minimum hence, Option C is true.
Also, if empNo1 was chosen instead of empNo then it would list all the employee numbers whose age isn’t the maximum.
 1 votes -- Cringe is my middle name... (885 points)
3.12.26 Relational Algebra: GATE IT 2005 | Question: 68 top☝ ☛ https://gateoverflow.in/3831

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
2959 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.
3.13 Relational Calculus (14) top☝
3.13.1 Relational Calculus: GATE CSE 1993 | Question: 23 top☝ ☛ https://gateoverflow.in/2320
The following relations are used to store data about students, courses, enrollment of students in courses and teachers of
courses. Attributes for primary key in each relation are marked by ‘*’.
Students (rollno*, sname, saddr)
courses (cno*, cname)
enroll(rollno*, cno*, grade)
teach(tno*, tname, cao*)
(cno is course number cname is course name, tno is teacher number, tname is teacher name, sname is student name, etc.)
Write a SQL query for retrieving roll number and name of students who got A grade in at least one course taught by teacher names
Ramesh for the above relational database.
gate1993 databases sql relational-calculus normal descriptive
Answer ☟
The following relations are used to store data about students, courses, enrollment of students in courses and teachers of
courses. Attributes for primary key in each relation are marked by ‘*’.
students(rollno*, sname, saddr)

courses(cno*, cname)
enroll(rollno*, cno*, grade)

(cno is course number, cname is course name, tno is teacher number, tname is teacher name, sname is student name, etc.)
For the relational database given above, the following functional dependencies hold:
rollno → sname, saddr

cno → cname
tno → tname
rollno, cno → grade
a. Is the database in 3rd normal form (3NF)?

b. If yes, prove that it is in 3NF. If not, normalize the relations so that they are in 3NF (without proving).
gate1993 databases sql relational-calculus normal descriptive
Answer ☟
3.13.3 Relational Calculus: GATE CSE 1998 | Question: 2.19 top☝ ☛ https://gateoverflow.in/1692
Which of the following query transformations (i.e., replacing the l.h.s. expression by the r.h.s expression) is incorrect? R 1 and
R2 are relations, C1 and C2 are selection conditions and A1 and A2 are attributes of R1.
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 ))
gate1998 databases relational-calculus normal
Answer ☟
The relational algebra expression equivalent to the following tuple calculus expression:
{t ∣ t ∈ r ∧ (t[A] = 10 ∧ t[B] = 20)} is
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)
gate1999 databases relational-calculus normal
Answer ☟
Which of the rational calculus expression is not safe?
A. {t ∣ ∃u ∈ R1 (t[A] = u[A]) ∧ ¬∃s ∈ R2 (t[A] = s[A])}

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])}
gate2001-cse relational-calculus normal databases
Answer ☟

With regards to the expressive power of the formal relational query languages, which of the following statements is true?
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
gate2002-cse databases relational-calculus normal
Answer ☟
Let R1 (− −, B, C) and R2 (−
A −, E) be two relation schema, where the primary keys are shown underlined, and let C be a
D
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 )
C. ΠD (r1 ⋈C≠D r2 )
D. ΠC (r1 ⋈C=D r2 )
gate2004-cse databases relational-calculus easy
Answer ☟
Consider the relation employee(name, sex, supervisorName) with name as the key, supervisorName gives the name of the
supervisor of the employee under consideration. What does the following Tuple Relational Calculus query produce?
{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.
Answer ☟
Which of the following tuple relational calculus expression(s) is/are equivalent to ∀t ∈ r (P (t)) ?
I. ¬∃t ∈ r (P (t))
II. ∃t ∉ r (P (t))
III. ¬∃t ∈ r (¬P (t))
IV. ∃t ∉ r (¬P (t))
A. I only
B. II only
C. III only
D. III and IV only
Answer ☟

Let R and S be relational schemes such that R = {a, b, c} and S = {c}. Now consider the following queries on the database:
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
gate2009-cse databases relational-calculus difficult
Answer ☟
Consider the following relational schema.
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”
I. SELECT DISTINCT S.sname FROM Students as S, Registration

as R WHERE
R.rollno=S.rollno AND R.courseno=107 AND R.percent >90
II. ∏sname(σcourseno=107∧percent>90 (Registration ⋈ Students))

III. {T ∣ ∃S ∈ Students, ∃R ∈ Registration(S. rollno = R. rollno
∧R. courseno = 107 ∧ R. percent > 90 ∧ T . sname = S. sname)}
IV. {⟨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. II, III and IV only
gate2013-cse databases sql relational-calculus normal
Answer ☟
3.13.12 Relational Calculus: GATE IT 2006 | Question: 15 top☝ ☛ https://gateoverflow.in/3554
Which of the following relational query languages have the same expressive power?
I. Relational algebra
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
gate2006-it databases relational-algebra relational-calculus easy
Answer ☟

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 ?
A. 50
B. 100
C. 150
D. 200
gate2007-it databases relational-calculus probability normal
Answer ☟
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)
−−−−−−−−−−−−−−−
Consider the following tuple relational calculus query.
{t ∣ ∃E ∈ Enrolment t = E. school-id ∧ |{x ∣ x ∈ Enrolment ∧ x. school-id = t ∧ (∃B ∈ ExamResult B. erollno = x. erollno ∧

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
gate2008-it databases relational-calculus normal
Answer ☟
Answers: Relational Calculus
select student.rollno, student.sname
From student natural join enroll on student.rollno=enroll.rollno
Where enroll.grade='A' AND enroll.cno in (select cno from teach where tname='Ramesh')

In table teach we have Primary Key (which is automatically a candidate key as well) as (tno, coa). We have the
functional dependency tno → tname which is a partial functional dependency (a proper subset of candidate key determining a
non-key attribute) which violates 2NF requirement and hence 3NF too. So the relational database is not in 3NF.
To make it in 3NF we have to break teach table into (tno*, coa*) and (tno*, tname).
 9 votes -- Tarun kushwaha (1.7k points)

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.

 44 votes -- Shaun Patel (6.1k points)

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).

Answer: C.
It returns tuples not belonging to R1 (which is infinitely many). So, it is not safe.
Reference: http://nptel.ac.in/courses/IIT-MADRAS/Intro_to_Database_Systems_Design/pdf/3.1_Tuple_Relational_Calculus.pdf
References

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.

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.
 25 votes -- Vicky Bajoria (4.1k points)

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]
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.)
Hence, option C.

Only III is correct.
The given statement means for all tuples from r, P is true. III means there does not exist a tuple in r where P is not true. Both are
equivalent.
IV is not correct as it as saying that there exist a tuple, not in r for which P is not true, which is not what the given expression
means.

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
s
Arj TY 12
c
Arj TY 14
12
Cell TR 13
14
Tom TW 12
Ben TE 14
1. will give ⟨Arj, T Y ⟩.

2. will give ⟨Arj, T Y ⟩.
3. will not return any tuple as the c value 13, is not in s.
4. will give ⟨Arj, T Y ⟩, ⟨Arj, T Y ⟩, ⟨T om, T W⟩, ⟨Ben, T E⟩.
http://pages.cs.wisc.edu/~dbbook/openAccess/firstEdition/slides/pdfslides/mod3l1.pdf
Correct Answer: A
References


Answer: A
Four queries given in SQL, RA, TRC and DRC in four statements respectively retrieve the required information.

Answer: D
All are equivalent in expressive power.


σA≤100 (r)
r has 1000 tuples
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

5 = 1000/5 = 200
Correct Answer: D
 35 votes -- Abhinav Rana (723 points)

t ∣ ∃E ∈ Enrolment t = E. school-id
Returns school-ids from Enrolment table SUCH THAT
|{x ∣ x ∈ Enrolment ∧ x. school-id = t ∧ (∃B ∈ ExamResult B. erollno = x. erollno ∧ B. examname = x. examname ∧

the number of student enrolments from the school for exams with marks > 35 divides
|{x ∣ x ∈ Enrolment ∧ x. school-id = t}|
total number of student enrolments from the school
∗100 > 35
percentage of student enrolments with mark > 35 is > 35
Since to pass an exam > 35 mark is needed, this means selecting the school-ids where the pass percentage of students across all
the exams taken together is > 35.
Correct Answer: C.
3.14 Safe Query (1) top☝
3.14.1 Safe Query: GATE CSE 2017 Set 1 | Question: 41 top☝ ☛ https://gateoverflow.in/118324
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
gate2017-cse-set1 databases relational-calculus safe-query normal
Answer ☟
Answers: Safe Query
3.14.1 Safe Query: GATE CSE 2017 Set 1 | Question: 41 top☝ ☛ https://gateoverflow.in/118324

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) 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. bcz 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.
reference:http://www.cs.sfu.ca/CourseCentral/354/zaiane/material/notes/Chapter3/node14.html
http://people.cs.pitt.edu/~chang/156/10calculus.html
http://www.cs.princeton.edu/courses/archive/fall13/cos597D/notes/relational_calc.pdf
References
 47 votes -- 2018 (5.5k points)
3.15 Sql (51) top☝
3.15.1 Sql: GATE CSE 1988 | Question: 12iii top☝ ☛ https://gateoverflow.in/94625
Describe the relational algebraic expression giving the relation returned by the following SQL query.
Select SNAME
from S
Where SNOin
(select SNO
from SP
where PNOin
(select PNO
from P
Where COLOUR='BLUE'))
gate1988 normal descriptive databases sql

Answer ☟
3.15.2 Sql: GATE CSE 1988 | Question: 12iv top☝ ☛ https://gateoverflow.in/94626
Select SNAME
from S
Where SNOin
(select SNO
from SP
where PNOin
(select PNO
from P
What relations are being used in the above SQL query? Given at least two attributes of each of these relations.
gate1988 normal descriptive databases sql
Answer ☟
3.15.3 Sql: GATE CSE 1990 | Question: 10-a top☝ ☛ https://gateoverflow.in/85686
Consider the following relational database:
employees (eno, ename, address, basic-salary)

projects (pno, pname, nos-of-staffs-allotted)
working (pno, eno, pjob)
The queries regarding data in the above database are formulated below in SQL. Describe in ENGLISH sentences the two queries
that have been posted:
i. SELECT ename
FROM employees
WHERE eno IN
(SELECT eno
FROM working
GROUP BY eno
HAVING COUNT(*)=
(SELECT COUNT(*)
FROM projects))
ii. SELECT pname

FROM projects
WHERE pno IN
(SELECT pno
FROM projects
MINUS
SELECT DISTINCT pno
FROM working);
gate1990 descriptive databases sql
Answer ☟
3.15.4 Sql: GATE CSE 1991 | Question: 12,b top☝ ☛ https://gateoverflow.in/42998
Suppose a database consist of the following relations:

SUPPLIER (SCODE,SNAME,CITY).
PART (PCODE,PNAME,PDESC,CITY).
PROJECTS (PRCODE,PRNAME,PRCITY).
SPPR (SCODE,PCODE,PRCODE,QTY).
Write algebraic solution to the following :
i. Get SCODE values for suppliers who supply to both projects PR1 and PR2.
ii. Get PRCODE values for projects supplied by at least one supplier not in the same city.
sql gate1991 normal databases descriptive
Answer ☟

Suppose a database consist of the following relations:

SUPPLIER (SCODE,SNAME,CITY).
PART (PCODE,PNAME,PDESC,CITY).
PROJECTS (PRCODE,PRNAME,PRCITY).
SPPR (SCODE,PCODE,PRCODE,QTY).
Write SQL programs corresponding to the following queries:
i. Print PCODE values for parts supplied to any project in DEHLI by a supplier in DELHI.
ii. Print all triples <CITY, PCODE, CITY> such that a supplier in first city supplies the specified part to a project in the second
city, but do not print the triples in which the two CITY values are same.
gate1991 databases sql normal descriptive
Answer ☟
3.15.6 Sql: GATE CSE 1997 | Question: 76-b top☝ ☛ https://gateoverflow.in/203570
Consider the following relational database schema:
EMP (eno name, age)

PROJ (pno name)
INVOLVED (eno, pno)
EMP contains information about employees. PROJ about projects and involved about which employees involved in which projects.
The underlined attributes are the primary keys for the respective relations.
State in English (in not more than 15 words)
What the following relational algebra expressions are designed to determine
i. Πeno (INVOLVED) − Πeno ((Πeno (INVOLVED) × Πpno (PROJ)) − INVOLVED)

ii. Πage(EMP) − Πage(σE.age<Emp.age ((ρE(EMP) × EMP))
(Note: ρE(EMP) conceptually makes a copy of EMP and names it E (ρ is called the rename operator))
gate1997 databases sql descriptive normal
Answer ☟
Suppose we have a database consisting of the following three relations.
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.
gate1998 databases sql descriptive
Answer ☟
3.15.8 Sql: GATE CSE 1999 | Question: 2.25 top☝ ☛ https://gateoverflow.in/1502
Which of the following is/are correct?
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

gate1999 databases sql easy
Answer ☟
Consider the set of relations
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.
gate1999 databases sql easy descriptive
Answer ☟
Consider the set of relations
EMP (Employee-no. Dept-no, Employee-name, Salary)

DEPT (Dept-no. Dept-name, Location)
Write an SQL query to:

Calculate, for each department number, the number of employees with a salary greater than Rs. 1,00,000
gate1999 databases sql descriptive easy
Answer ☟
Given relations r(w, x) and s(y, z) the result of

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
gate2000-cse databases sql
Answer ☟
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?
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
gate2000-cse databases sql normal

Answer ☟
3.15.13 Sql: GATE CSE 2000 | Question: 22 top☝ ☛ https://gateoverflow.in/693
Consider a bank database with only one relation

transaction (transno, acctno, date, amount)
The amount attribute value is positive for deposits and negative for withdrawals.
a. Define an SQL view TP containing the information

(acctno,T1.date,T2.amount)
for every pair of transaction T1,T2 and such that T1 and T2 are transaction on the same account and the date of T2 is ≤ the
date of T1.
b. Using only the above view TP, write a query to find for each account the minimum balance it ever reached (not including the
0 balance when the account is created). Assume there is at most one transaction per day on each account and
each account has at least one transaction since it was created. To simplify your query, break it up into 2 steps by defining an
intermediate view V.
gate2000-cse databases sql normal descriptive
Answer ☟
Consider a relation geq which represents "greater than or equal to", that is, (x, y) ∈ geq only if y ≥ x .
create table geq
(
ib integer not null,
ub integer not null,
primary key ib,
foreign key (ub) references geq on delete cascade
);
Which of the following is possible if tuple (x,y) is deleted?

A. A tuple (z,w) with z > y is deleted
B. A tuple (z,w) with z > x is deleted
C. A tuple (z,w) with w < x is deleted
D. The deletion of (x,y) is prohibited
Answer ☟
Consider a relation examinee (regno, name, score), where regno is the primary key to score is a real number.
Write a relational algebra using (Π, σ, ρ, ×) to find the list of names which appear more than once in examinee.
Answer ☟
Write an SQL query to list the regno of examinees who have a score greater than the average score.
Answer ☟
3.15.17 Sql: GATE CSE 2001 | Question: 21-c top☝ ☛ https://gateoverflow.in/203573
appears (regno, centr_code)

Suppose the relation appears (regno, centr_code) specifies the center where an examinee appears. Write an SQL query to list the
centr_code having an examinee of score greater than 80.
Answer ☟
Consider the set of relations shown below and the SQL query that follows.
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
gate2003-cse databases sql easy
Answer ☟
The employee information in a company is stored in the relation
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
Answer ☟
3.15.20 Sql: GATE CSE 2005 | Question: 77, ISRO2016-55 top☝ ☛ https://gateoverflow.in/1400
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?
select title
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 book
D. Titles of the five most expensive books
gate2005-cse databases sql easy isro2016
Answer ☟
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.
Query1:
select A.customer, count(B.customer)
from account A, account B
where A.balance <=B.balance
group by A.customer
Query2:
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 Query1 and Query2.
1. Query1 will produce the same row set as Query2 for some but not all databases.
2. Both Query1 and Query 2 are a correct implementation of the specification
3. Query1 is a correct implementation of the specification but Query 2 is not
4. Neither Query1 nor Query2 is a correct implementation of the specification
5. Assigning rank with a pure relational query takes less time than scanning in decreasing balance order assigning ranks using
ODBC.
Which two of the above statements are correct?

A. 2 and 5
B. 1 and 3
C. 1 and 4
D. 3 and 5
Answer ☟
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.
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 Query 1 and Query2 return
different row sets
C. There exist databases for which Query3 returns strictly fewer rows than Query 2
D. There exist databases for which Query4 will encounter an integrity violation at runtime
Answer ☟
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”
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 = 5000, Plan 1 executes faster than Plan 2 for all databases
D. For x = 9000, Plan I executes slower than Plan 2 for all databases
Answer ☟
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 table?
Select e.empId
From employee e
Q1 : Where not exists
(Select * From employee s Where s.department = "5" and s.salary >= e.salary)

Select e.empId
From employee e
Q2 : 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
gate2007-cse databases sql normal verbal-aptitude
Answer ☟

Suppliers(sid:integer , sname:string, city:string, street:string)
−−−−−−−−
Parts(pid:integer , pname:string, color:string)
−−−−−−−−−
Catalog(sid:integer, pid:integer , cost:real)
−−−−−−−−−−−−−−−−−−
Consider the following relational query on the above database:
SELECT S.sname
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.
Answer ☟
A relational schema for a train reservation database is given below.
passenger(pid, pname, age)

reservation(pid, class, tid)
Reservation
Passenger
pid class tid
pid pname Age 0 AC 8200
0 Sachine 65 1 AC 8201
1 Rahul 66 2 SC 8201
2 Sourav 67 5 AC 8203
3 Anil 69 1 SC 8204
3 AC 8202

What pids are returned by the following SQL query for the above instance of the tables?
SELECT pid
FROM Reservation
WHERE class='AC' AND
EXISTS (SELECT *
FROM Passenger
WHERE age>65 AND
Passenger.pid=Reservation.pid)
A. 1, 0
B. 1, 2
C. 1, 3
D. 1, 5
Answer ☟
Consider a database table T containing two columns X and Y each of type integer . After the creation of the table, 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?
SELECT Y FROM T WHERE X=7;
A. 127
B. 255
C. 129
D. 257
Answer ☟
Database table by name Loan_Records is given below.
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 S
NATURAL JOIN
(SELECT Bank_Manager, Loan_Amount FROM Loan_Records) AS T
);
A. 3
B. 9
C. 5
D. 6
Answer ☟
Which of the following statements are TRUE about an SQL query?

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
gate2012-cse databases easy sql ambiguous
Answer ☟
Consider the following relations A, B and C :
B
A
C
Id Name Age
Id Name Age
15 Shreya 24 Id Phone Area
12 Arun 60
25 Hari 40 10 2200 02
15 Shreya 24
98 Rohit 20 99 2100 01
99 Rohit 11
99 Rohit 11
How many tuples does the result of the following SQL query contain?
SELECT A.Id
FROM A
WHERE A.Age > ALL (SELECT B.Age
FROM B
WHERE B.Name = ‘Arun’)
A. 4
B. 3
C. 0
D. 1
Answer ☟
3.15.31 Sql: GATE CSE 2014 Set 1 | Question: 22 top☝ ☛ https://gateoverflow.in/1789
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?

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
gate2014-cse-set1 databases normal sql
Answer ☟
Given the following schema:

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.
gate2014-cse-set1 databases sql normal
Answer ☟
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:
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
Answer ☟

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.
gate2014-cse-set3 databases sql easy
Answer ☟
Consider the following relation:
Performance

Performance
Student
Roll_No Course Marks
−−−−−−−− −−−−−−−
1 Math 80
Roll_No Student_Name
−−−−−−−− 1 English 70
1 Raj
2 Math 75
2 Rohit
3 English 80
3 Raj
2 Physics 65
3 Math 80
Consider the following SQL query.

SELECT S.Student_Name, Sum(P. Marks)
FROM Student S, Performance P
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_________________.
gate2015-cse-set1 databases sql normal numerical-answers
Answer ☟
Consider the following relation

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)
Answer ☟
Consider the following database table named water_schemes:

Water_schemes
scheme_no district_name capacity
1 Ajmer 20
1 Bikaner 10
2 Bikaner 10
3 Bikaner 20
1 Churu 10
2 Churu 20
1 Dungargarh 10
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
gate2016-cse-set2 databases sql normal numerical-answers
Answer ☟
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:
EMP
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
12 XYL AD
13 XYM AE
SELECT 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 _____________ .
gate2017-cse-set1 databases sql numerical-answers
Answer ☟
Consider the following database table named top_scorer .
top_scorer

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 Muller Germany 10
Rahn 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 ______
Answer ☟
Consider the following two tables and four queries in SQL.

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
gate2018-cse databases sql easy
Answer ☟
A relational database contains two tables Student and Performance as shown below:
Table: Performance

Table: Performance
Table: student
Roll_no Subject_code Marks
Roll_no Student_name
1 A 86
1 Amit
1 B 95
2 Priya
1 C 90
3 Vinit
2 A 89
4 Rohan
2 C 92
5 Smita
3 C 80
The primary key of the Student table is Roll_no. For the performance table, the columns Roll_no. and Subject_code together form
the primary key. Consider the SQL query given below:
SELECT S.Student_name, sum(P.Marks)
FROM Student S, Performance P
WHERE P.Marks >84
GROUP BY S.Student_name;
The number of rows returned by the above SQL query is ________
gate2019-cse numerical-answers databases sql
Answer ☟
Consider a relational database containing the following schemas.

Catalogue
sno
−−
− −pno cost
−−
S1 P1 150 Parts
S1 P2 50 Suppliers pno pname part_spec

−−−
S1 P3 100 sno
−−
− sname location P1 Table Wood
S2 P4 200 S1 M/s Royal furniture Delhi P2 Chair Wood
S2 P5 250 S2 M/s Balaji furniture Bangalore P3 Table Steel
S3 P1 250 S3 M/s Premium furniture Chennai P4 Almirah Steel
S3 P2 150 P5 Almirah Wood
S3 P5 300
S3 P4 250
The primary key of each table is indicated by underlining the constituent fields.
SELECT s.sno, s.sname
FROM Suppliers s, Catalogue c
WHERE s.sno=c.sno AND
cost > (SELECT AVG (cost)
FROM Catalogue
WHERE pno = ‘P4’
GROUP BY pno) ;
The number of rows returned by the above SQL query is

A. 4
B. 5
C. 0
D. 2
gate2020-cse databases sql
Answer ☟
A relation r(A, B) in a relational database has 1200 tuples. The attribute A has integer values ranging from 6 to 20, and the
attribute B has integer values ranging from 1 to 20. Assume that the attributes A and B are independently distributed.
The estimated number of tuples in the output of σ(A>10)∨(B=18) (r) is ____________.

Answer ☟
The relation scheme given below is used to store information about the employees of a company, where empId is the key and
deptId indicates the department to which the employee is assigned. Each employee is assigned to exactly one department.
emp(empId , name, gender, salary, deptId)

−−−−−
Consider the following SQL query:
select deptId, count(*)
from emp
where gender = “female” and salary > (select avg(salary)from emp)
group by deptId;
The above query gives, for each department in the company, the number of female employees whose salary is greater than the
average salary of
A. employees in the department
B. employees in the company
C. female employees in the department
D. female employees in the company
gate2021-cse-set2 databases sql easy
Answer ☟
3.15.45 Sql: GATE IT 2004 | Question: 74 top☝ ☛ https://gateoverflow.in/3718
A relational database contains two tables student and department in which student table 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')
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
gate2004-it databases sql normal
Answer ☟
A table T1 in a relational database has the following rows and columns:
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?
18.75

A. 18.75
B. 20
C. 25
D. Null
Answer ☟
Consider two tables in a relational database with columns and rows as follows:
Table: 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?
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
Answer ☟
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.
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
Answer ☟
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 ∕ 06
29 Salman 1 33 22 102 10 ∕ 10 ∕ 06
31 Boris 8 55 22 103 08 ∕ 10 ∕ 06
32 Amoldt 8 25 22 104 07 ∕ 10 ∕ 06
58 Schumacher 10 35 31 102 10 ∕ 11 ∕ 16
64 Sachin 7 35 31 103 06 ∕ 11 ∕ 16
71 Senna 10 16 31 104 12 ∕ 11 ∕ 16
74 Sachin 9 35 64 101 05 ∕ 09 ∕ 06
85 Rahul 3 25 64 102 08 ∕ 09 ∕ 06
95 Ralph 3 53 74 103 08 ∕ 09 ∕ 06
C: Cars relation
Cid Cname colour

101 Renault blue
102 Renault red
103 Ferrari green
104 Jaguar red
What is the output of the following SQL query?

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
where R.cid = C.cid and C.colour = 'green'
)
A. Karthikeyan, Boris
B. Sachin, Salman
C. Karthikeyan, Boris, Sachin
D. Schumacher, Senna
Answer ☟
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.

did dname rating age did Cid day
22 Karthikeyan 7 25 22 101 10 − 10 − 06
29 Salman 1 33 22 102 10 − 10 − 06
31 Boris 8 55 22 103 08 − 10 − 06
32 Amoldt 8 25 22 104 07 − 10 − 06
58 Schumacher 10 35 31 102 10 − 11 − 16
64 Sachin 7 35 31 103 06 − 11 − 16
71 Senna 10 16 31 104 12 − 11 − 16
74 Sachin 9 35 64 101 05 − 09 − 06
85 Rahul 3 25 64 102 08 − 09 − 06
95 Ralph 3 53 74 103 08 − 09 − 06
C: Cars relation
Cid Cname colour
101 Renault blue
102 Renault red
103 Ferrari green
104 Jaguar red
select D.dname
from Drivers D
where D.did in (
select R.did
intersect
select R.did
)
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
D. 100 − 104
Answer ☟
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)
−−−−−−−−−−−−−−−
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
Answer ☟
Answers: Sql
3.15.1 Sql: GATE CSE 1988 | Question: 12iii top☝ ☛ https://gateoverflow.in/94625
select PNO from P Where COLOUR='BLUE';
This can be written as: πpno (σcolour=′Blue′ (P))

Store this in T1.
∴ T 1 ← πpno (σcolour=′Blue′ (P))
Then
select SNO from SP
where PNOin (select PNO from P
T 2 ← πsno (σpno=T1 (SP))

Similary
Select SNAME from S
Where SNOin (select SNO from SP
where PNOin (select PNO from P
Where COLOUR='BLUE'));
Result ← πsname (σsno=T2 (S))
3.15.2 Sql: GATE CSE 1988 | Question: 12iv top☝ ☛ https://gateoverflow.in/94626

There are 3 relations here:
S(SNAME, SNO)
SP(SNO, PNO)
P(PNO, COLOUR)
 9 votes -- Akash Dinkar (27.9k points)

1.SELECT ename
FROM employees
WHERE eno IN
(SELECT eno
FROM working
GROUP BY eno
HAVING COUNT (*)=
(SELECT COUNT (*)
FROM projects));

This will return : Employee name who is working for all projects.
(ii)
SELECT pname
FROM projects
WHERE pno IN
(SELECT pno
FROM projects
MINUS
SELECT DISTINCT pno
FROM working);
This will return : Project name for which no employee is working.
3.15.4 Sql: GATE CSE 1991 | Question: 12,b top☝ ☛ https://gateoverflow.in/42998
SCODE values for suppliers who supply to both projects PR1 and PR2 -
Πscode,prcode (SPPR) ÷ Πprcode (σprname=pr1∨prname=pr2 (PROJECT S))
PRCODE values for projects supplied by at least one supplier not in the same city -
Πprcode (σcity<>prcity((SUPPLIER ∗ SPPR) ∗ PROJECT S))
* is natural join.
 8 votes -- Ashish verma (7.2k points)

i. Print PCODE values for parts supplied to any project in DELHI by a supplier in DELHI
Select SP.PCODE
From SPPR SP, Projects PR, Supplier SU
Where SP.PRcode = PR.PRcode
and SU.Scode = SP.Scode
and PR.PRcity = "DELHI"
and SU.city = "DELHI";
ii. Print all triples <CITTY, PCODE, CITY>

Select SU.city, SP.Pcode,PR.PRcity
from Supplier SU, Projects PR, SPPR SP
Where SU.Scode = SP.Scode
And PR.PRcode = SP.PRcode
And SU.city <> PR.PRcity;

i. Πeno (INV OLV ED) −Πeno ((Πeno (INV OLV ED) × Πpno (PROJ) − INV OLV ED)
Πeno (INV OLV ED)− All employees involved in projects → (A)
Πeno ((Πeno (INV OLV ED) × Πpno (PROJ) − INV OLV ED)− gives all employee who are not involved in at
least one project. → (B)
A − B = employee No. of employees involved on the all project. (Division Operator)
ii. Πage(EMP) − Πage(σEage<EMP.age (ρE(EMP) × EMP))

Πage(EMP)− Age of all employees → (C)
Πage(σEage<EMP.age (ρE(EMP) × EMP))− Employees who have age less than at least one other employee
→ (D)
C − D = Maximum of all ages of employees.


SELECT DISTINCT A.student FROM
FREQUENTS A, SERVES B, LIKES C
WHERE
A.parlor=B.parlor
AND
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));

(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.

(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
SELECT Dept-no, count(Employee-no) as total_employees

FROM EMP
WHERE Salary > 100000
GROUP BY Dept-no
 4 votes -- balraj_allam (95 points)

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 can not have
duplicates. If S is empty RXS becomes empty, so S must be non empty. This is true.

B. Here, assume that S is empty. (No duplicates.) Then R X 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.

Answer is option C.
Value at hand Option A Option B Option C

6 × × × × ✓ ✓
5 ✓ ✓ ✓ ✓ × ×
NULL × × × × × ✓
a.
Create view TP(T1.acctno, T1.date, T2.amount)
as (Select T1.acctno, T1.date, T2.amount
from Transaction T1, Transaction T2
where T1.acctno = T2.acctno
and T2.date <= T1.date);
b.
i.
Create view V(acctno, date, balance)
as (select acctno, date, sum(amount)
from TP
group by acctno, date);
ii.
select acctno, min(balance)
from V
group by acctno;

Answer: C
The table can be depicted as:
ib(PK) ub(FK)
z w=u
u v=x
x y
If (x, y) is deleted then from the above table:
v ≤ y ( as v = x)
u < v ≤ y, u! = v ( as v = x and ib is the Primary Key)
w < v ≤ y ( as w = u)
z < w < v ≤ y, z! = w ( as w = u and ib is the Primary Key)
As, it can be seen that w < v or w < x ( as v = x) so C is the answer.


πexm1.name (σ(exm1.regno≠examinee.regno)∧(emp1.name=emp2.name) )(ρexm1 (examinee) × examinee)
 16 votes -- Tauhin Gangwar (6.7k points)

There are many ways to write a query, all of which will perform the same task. One way is:
SELECT regno
FROM examinee
WHERE score > (SELECT AVG(score)
FROM examinee )
Here, the inner query is returning the average of the scores. And outer query selects those regno that have a score greater than
this average.
 11 votes -- Rishabh Gupta (12.5k points)
3.15.17 Sql: GATE CSE 2001 | Question: 21-c top☝ ☛ https://gateoverflow.in/203573
SELECT DISTINCT centr_code

FROM appears
WHERE regno IN (SELECT regno
FROM examinee
WHERE score > 80)

C. Names of the students who have got an A grade in at least one of the courses taught by Korth.

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.
3.15.20 Sql: GATE CSE 2005 | Question: 77, ISRO2016-55 top☝ ☛ https://gateoverflow.in/1400

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.

Both Query1 and Query2 are not correct implementations because: Assume that we have a table with n customers having
the 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 the same reason
Query1 is wrong though it is true if we assume the 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, the 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
where A.balance < B.balance
) from account A

Query1 and Query3 : output will be the same
and Query2 and Query4 : output will be same
I have run these queries on the online compiler, this what i get
BEGIN TRANSACTION;
-- /* Create a table called NAMES */

-- CREATE TABLE E(Id integer);
-- CREATE TABLE P(Id integer);
--
-- /* Create few records in this table */
-- INSERT INTO E VALUES(1);
--
-- INSERT INTO P VALUES(1);
COMMIT;
/* Display all the records from the table */

-- SELECT * FROM E;
-- select "------";
-- SELECT * FROM P;
-- select "------";
select "Query 1:";
select E.id from E
where E.id in (select P.id from P);
select "Query 2:";

select id from P
where id in (select id from E);
select "Query 3:";
select E.id from E e, P p

where e.id = p.id;
select "Query 4:";

select id from P
where exists (select * from E where E.id = P.id);
/* output */
Query 1:
1
1
3
3
Query 2:
1
3
Query 3:
1
1
3
3
Query 4:
1
3
So, answer should be B.
Answer should be (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
But, in case of plan 2 its in the nested loop so it need to check every time and will take more time to execute .
 27 votes -- Pranay Datta (7.8k points)


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. See here: http://sqlfiddle.com/#!9/9acce/1
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. See here: http://sqlfiddle.com/#!9/9acce/2
According the question the answer should be 1 for the above table.
PS: The question implies that the required employee must not be from department 5.
References

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.

(C) 1, 3
The inner query gives passenger_id with age above 65 i.e., 1, 2, 3

The outer query chooses the class as AC, which are 1 and 3


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
Correct Answer: A

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

Suresh Ramgopala 5000.00
After that count (*) will count total tuples present in this table so here it is 5.
 41 votes -- neha pawar (3.3k points)

GATE 2012 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."
This shows that P is indeed correct.
Also see "having clause section"

http://www.contrib.andrew.cmu.edu/~shadow/sql/sql1992.txt
http://searchsqlserver.techtarget.com/answer/ISO-ANSI-SQL-and-the-GROUP-BY-clause
The above link says that all columns used in group by must be present in select clause as per SQL-92 standard but later standards
doesn't enforce it. I tried this on MySQL and it works. It is allowed in MSSQL also- see below link.
From Microsoft (obviously applicable only to MS-SQL)

http://msdn.microsoft.com/en-us/library/ms177673.aspx
' Expressions in the GROUP BY clause can contain columns of the tables, derived tables or views in the FROM
clause. The columns are not required to appear in the SELECT clause <select> list. Each table or view column in any
nonaggregate expression in the <select> list must be included in the GROUP BY list:

So, as per standard it is not allowed, but in most current DBMS it is allowed. And there is no reason why this shouldn't be
allowed. So, ideally 'S' is more correct than 'R' or both are debatable and marks should have been given to all.
References

<cond> ALL evaluates to TRUE if inner query returns no tuples. So, Number of tuples returned will be number of tuples
in A = 3 .
Reference: http://dcx.sap.com/1200/en/dbusage/all-test-quantified-subquery.html
Correct Answer: B
References

(D)Both are false
S1: Foreign key constraint means a lot of constraints it has to be a primary key(which intrun 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).

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 can not :(
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='AA'
group by d1.dept_name;
will give output.

C)
Consider the following instances of R and S
R S
A B C A X Z
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)
A B C
1 2 3
1 2 3
7 8 9
7 8 9
For Option,
A) since multiplicity of tuples is disturbed
select R.* from R, S where R.a=S.a
∴ 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
 76 votes -- Kalpish Singhal (1.6k points)
So, an employee whose ALL customers gives him GOOD rating is chosen;
All such employees are chosen.
Answer = option D

For answering there is no need to execute the query, we can directly answer this as 2
How?
' Group by Student_Names
It means all name that are same should be kept in one row.
There are 3 names. But in that there is a duplicate with Raj being repeated ⟹ Raj produces one row and Rohit produces one
row ⟹ Total 2 rows.
For better understanding, I'll just analyze the whole query

1st statement which is executed from the query is From Clause : From Student S, Performance P
⟹ cross product of those two tables will be

S.RollNo S.Student_name P.Roll_no P.Course P.marks
1 Raj 1 Maths 80
1 Raj 1 English 70
1 Raj 2 Maths 75
1 Raj 3 English 80
1 Raj 2 Physics 65
1 Raj 3 Maths 80
2 Rohit 1 Maths 80
2 Rohit 1 English 70
2 Rohit 2 Maths 75
2 Rohit 3 English 80
2 Rohit 2 Physics 65
2 Rohit 3 Maths 80
3 Raj 1 Maths 80
3 Raj 1 English 70
3 Raj 2 Maths 75
3 Raj 1 English 80
3 Raj 2 Physics 65
3 Raj 3 Maths 80
2nd statement which is executed from the query is Where Clause : Where S.Roll_no = P.Roll_no
⟹ delete those rows which does not satisfy the WHERE condition. Then the result will be

1 Raj 1 Maths 80
1 Raj 1 English 70
2 Rohit 2 Maths 75
2 Rohit 2 Physics 65
3 Raj 3 English 80
1 Raj 3 Maths 80
3rd statement which is executed from the query is Group by Clause : Group by S.Student_Name
⟹ Merge those rows which are having same name, then result will be

{1, 1, 3, 3} Raj {1, 1, 3, 3} {Maths, English} {80, 70, 80, 80}
2 Rohit 2 {Maths, Physics} {75, 65}
Note that, this can't be used as final result as it violates 1NF (multiple values in each tuple for S.Roll_no, P.Roll_no, P.Course
and P.marks)
4th statement which is executed from the query is Select Clause : Select S.Student_Name, SUM(P.marks)
⟹ Delete un-necessary columns and calculate the aggregate functions, then result will be
S.Student_name P.marks
Raj 310
Rohit 140
 70 votes -- naresh1845 (1.1k points)

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.

1st query will return the following:
Table Name : Total (name, capacity)
name capacity
Ajmer 20
Bikaner 40
Churu 30
Dungargarh 10
2nd Query will return, Total_avg (capacity) 25
Since sum of capacity = 100/4 = 25
3rd query will be final and it's tuples will be considered as output, where name of district and its total capacity should be more
than or equal to 25
name
Bikaner
Churu
Hence, 2 tuples returned.
 75 votes -- Shashank Chavan (2.4k points)

The inner query will return
DeptName Num
AA 4
AB 3
AC 3
AD 2
AE 1
Now AVG(EC.Num) will find the average of Num values in the above-returned query, which is
(4 + 3 + 3 + 2 + 1) ÷ 5 = 2.6
So according to me, the answer should be 2.6.

 43 votes -- sriv_shubham (2.8k points)

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.

 48 votes -- tvkkk (1.1k points)

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.
 20 votes -- Baljit kaur (1k points)

Group by Student_name ⟹ number of distinct values of Student_name
in the instance of the relation all rows have distinct name then it should results 5 tuples !

The given query is a nested subquery but not co-related subquery (inner query is independent of the outer and so can be
executed independently)
SELECT AVG (cost) FROM Catalogue WHERE pno= 'P4' GROUP BY pno
sno
− pno −
−− − cost
−−− −−−
S1 P1 150
S1 P2 50
S1 P3 100
S2 P4 200
S2 P5 250
S3 P1 250
S3 P2 150
S3 P5 300
S3 P4 250
First, we will select the tuples with pno = ‘P4’ and then group by pno (so just one group) and then find the average cost.
sno
− pno −
−− − cost
−−− −−−
S2 P4 200
S3 P4 250
200+250
So average cost = 2 = 225
∴ the inner query will return 225
Now the given SQL query would become

SELECT s.sno,s.sname FROM Supplier s , Catalogue c WHERE s.sno=c.sno AND cost> 225
So here we need to do cross product of supplier table s and Catalogue table c and from the cross product we will select those
rows where s. sno = c. sno AND cost > 225
Since it is given that cost > 225 so we do not need to consider rows from the Catalogue table having cost ≤ 225 while doing
cross product. Hence from the Catalogue table only the row numbers 5, 6, 8, 9 need to be taken while doing the cross product.
After doing cross product we’ll get,

s.sno s.name s.location c.sno c.pno c.cost
S1 M/s Royal furniture Delhi S2 P5 250
S2 M/s Balaji furniture Bangalore S2 P5 250
S3 M/s Premium furniture Chennai S2 P5 250
Now after doing cross product only 4 tuples will be selected from the table due to the condition s. sno = c. sno
s.sno s.name s.location c.sno c.pno c.cost

∴ Option A. 4 is the correct answer

P(A > 10) = 10 2
15 = 3
1
P(B = 18) = 20
2 1 1
P(A > 10 ∧ B = 18) = 3 × 20 = 30
P(A > 10 ∨ B = 18) = P(A > 10) + P(B = 18)– P(A > 10 ∧ B = 18)
2 1 1 40+3–2 41
= 3 + 20 – 30 = 60 = 60
41
Estimated number of tuples = 60 × 1200 = 820
The above answer is TRUE for SQL SELECT but not for Relational Algebra as by theory relational algebra operates on a set
which means all the elements must be distinct. Since we have 15 distinct possible values for A and 20 distinct possible values for
B, in strict relational algebra we’ll get
41
Estimated number of tuples = 60 × (15 × 20) = 205.
Official Answer: 205 OR 820.

It’s a nested query but not Co-related query.
Evaluate the innermost query first.
select avg(salary)
from emp
It is given that emp represent employees of a company.

So, Option B is the correct answer.


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.

Update on null gives null. Now, avg function ignores null values. So, here avg will be (15 + 25 + 35)/3 = 25.
http://msdn.microsoft.com/en-us/library/ms177677.aspx
Correct Answer: C
References

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.
 40 votes -- neha pawar (3.3k points)

Answer is D) supply two or more items
The whole query returns the distinct list of suppliers who supply two or more items.
 32 votes -- Bran Stark (339 points)

For color = "Red", did = {22, 22, 31, 31, 64}
For color = "Green", did = {22, 31, 74}
Intersection of Red and Green will give did = {22, 31} which is Karthikeyan and Boris
Answer: A


select D.dname
from Drivers D
where D.did in (
select R.did
intersect
select R.did
)
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.
Correct Answer: B.

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
http://weblogs.sqlteam.com/jeffs/archive/2007/07/20/but-why-must-that-column-be-contained-in-an-aggregate.aspx
References
 63 votes -- erravi90 (131 points)
3.16 Timestamp Ordering (1) top☝
3.16.1 Timestamp Ordering: GATE CSE 2017 Set 1 | Question: 42 top☝ ☛ https://gateoverflow.in/118325
In a database system, unique timestamps are assigned to each transaction using Lamport's logical clock. Let T S(T1 ) and
T S(T2 ) be the timestamps of transactions T1 and T2 respectively. Besides, T1 holds a lock on the resource R, and T2 has requested
a conflicting lock on the same resource R. The following algorithm is used to prevent deadlocks in the database system assuming
that a killed transaction is restarted with the same timestamp.
if T S(T2 ) < T S(T1 ) then
T1 is killed
else T2 waits.

Assume any transaction 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.
gate2017-cse-set1 databases timestamp-ordering deadlock normal
Answer ☟
Answers: Timestamp Ordering
3.16.1 Timestamp Ordering: GATE CSE 2017 Set 1 | Question: 42 top☝ ☛ https://gateoverflow.in/118325
' In a database system, unique timestamps are assigned to each transaction using Lamport's logical clock
Since Unique Timestamps are assigned, so there is no question of two transaction having same timestamp.
Moreover, there is nothing mentioned about the size of the counter by which it can be determined that whether there will be case
of timestamp wrap around or not.
So, there will be no timestamp wrap around.
In Lamport's logical clock Timestamps are assigned in increasing order of enumeration.
So, Ti<Tj if Transaction Ti came into system before Tj.
The above scheme given is nothing but " Wound-Wait " Scheme in which younger transaction is killed by older transaction that
came into system before this younger transaction came.[1][2]
So, this is a part of Basic Time-Stamp Ordering in Concurrency Control.
And Basic Time Stamp ordering protocol is deadlock free and not starvation free, in general.
Here in this question according to given condition, the database system is both deadlock free and starvation free as well , as it is
Wound wait scheme and in case of wound wait it avoid starvation, because in Wound Wait scheme we restart a transaction
that has been aborted, with it's same original Timestamp . If it restart with a new Timestamp then there is a possibility of
Starvation ( as larger TimeStamp transaction is aborted here and new Transaction which is coming next have always
greater TimeStamp than previous one ). But that is Not the case here.
Reference:
[1] http://www.cs.colostate.edu/~cs551/CourseNotes/Deadlock/WaitWoundDie.html
[2] http://stackoverflow.com/questions/32794142/what-is-the-difference-between-wait-die-and-wound-wait
Hence, answer is (A).
PS: The Wound-wait scheme means :
The newer transactions are killed when an older transaction make a request for a lock being held by the
newer transactions .
Here the algorithm says TS(T2) < TS(T1) means T2 is older transaction ( as TS of T2 is less than TS of T1 ..means T2
come first then T1 come and TS is assign in increasing order ) , so newer one is T1 and also question says T1 holds
a lock on the resource R, and T2 has requested a conflicting lock on the same resource R.
So T1 is killed as per Wound-wait scheme .
Reference :
http://www.mathcs.emory.edu/~cheung/Courses/554/Syllabus/8-recv+serial/deadlock-compare.html
----------
' timestamps are assigned to each transaction using Lamport's logical clock.
This line means timestamps are assigns in increasing order .

We can divide the answer into 3 parts:
Part 1: Is it Wound wait scheme?
Yes, given algorithm:
If T S(T 2) < T S(T 1) , then
T 1 is killed
else, T 2 waits.
comes under wound wait scheme..as here old transaction is always survive and older transaction wounds newer transaction when
both want to apply lock on same resource ..
Part 2 : Wound Wait avoid Starvation
Yes, How?
as newer one is die and restart with same timestamp and older one is survive always so after execute older transaction that newer
one can definitely execute and new transactions which are coming can die and restart again ( previous newer became older that
time).
Part 3 : Does Starvation freedom implies Deadlock freedom?
Yes, here no starvation means also No deadlock possibility.
In one line - wound wait -> no starvation -> no deadlock -> option A.
EDIT
Another way to think about Deadlock and starvation
Deadlock is prevented because we are violating NO-Preemption Condition for the deadlock to happen.
How starvation free? Here Bounded waiting for transactions is ensured.HOW?
Consider "n" transactions T1 , T2 . . . . Tn having their timestamps order as T S(T1 ) < T S(T2 ) <. . . . . T S(Tn ) (Timestamps are
unique)
Consider for k, 1 < k ≤ n a transaction Tk , this transaction Tk can be atmost preempted by Transaction sets T1 , T2 . . . . . . Tk−1
and it is also given "Any transaction that is not killed eventually terminates". Means Eventually a time would come when, all
transactions Tj having T S(Tj ) < T S(Tk ) will terminate and Tk would get chance without preemption.And this J would lie in
range 1 ≤ j ≤ k − 1 . Bounded waiting ensured.
References
 111 votes -- Ayush Upadhyaya (28.4k points)
3.17 Transaction And Concurrency (28) top☝
3.17.1 Transaction And Concurrency: GATE CSE 1999 | Question: 2.6 top☝ ☛ https://gateoverflow.in/1484
For the schedule given below, which of the following is correct:
Read A

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
gate1999 databases transaction-and-concurrency normal
Answer ☟
3.17.2 Transaction And Concurrency: GATE CSE 2003 | Question: 29, ISRO2009-73 top☝ ☛ https://gateoverflow.in/919
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
gate2003-cse databases transaction-and-concurrency easy isro2009
Answer ☟
3.17.3 Transaction And Concurrency: GATE CSE 2003 | Question: 87 top☝ ☛ https://gateoverflow.in/970
Consider three data items D1, D2, and D3, and the following execution schedule of transactions T 1, T 2, and T 3. In the
diagram, R(D) and W(D) denote the actions reading and writing the data item D respectively.
T1 T2 T3
R(D3);
R(D2);
W(D2);
R(D2);
R(D3);
R(D1);
W(D1);
W(D2);
W(D3);
R(D1);
R(D2);
W(D2);
W(D1);
Which of the following statements is correct?

A. The schedule is serializable as T 2; T 3; T 1
B. The schedule is serializable as T 2; T 1; T 3
C. The schedule is serializable as T 3; T 2; T 1
D. The schedule is not serializable
gate2003-cse databases transaction-and-concurrency normal
Answer ☟
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
2. T1 B old = 12000 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
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
gate2006-cse databases transaction-and-concurrency normal isro2015
Answer ☟
Consider the following schedules involving two transactions. Which one of the following statements is TRUE?
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.
Answer ☟
Consider two transactions T1 and T2 , and four schedules S1 , S2 , S3 , S4 , of T1 and T2 as given below:
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
Answer ☟
Which of the following concurrency control protocols ensure both conflict serializability and freedom from deadlock?
I. 2-phase locking
II. Time-stamp ordering
A. I only
B. II only
C. Both I and II
D. Neither I nor II
Answer ☟
Consider the following schedule for transactions T 1, T 2 and T 3 :
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
Answer ☟
Consider the following transactions with data items P and Q initialized to zero:

T1 read (P);
read (Q);
if P = 0 then Q := Q + 1;
write (Q)
T2 read (Q);
read (P);
if Q = 0 then P := P + 1;
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
Answer ☟
3.17.10 Transaction And Concurrency: GATE CSE 2014 Set 1 | Question: 29 top☝ ☛ https://gateoverflow.in/1796
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?
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);
gate2014-cse-set1 databases transaction-and-concurrency normal
Answer ☟
Consider the following schedule S of transactions T 1, T 2, T 3, T 4 :
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
Answer ☟
Consider the transactions T 1, T 2, and T 3 and the schedules S1 and S2 given below.
T 1 : r1(X); r1(Z); w1(X); w1(Z)

T 2 : r2(Y ); r2(Z); w2(Z)
T 3 : 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.
Answer ☟
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)
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
gate2015-cse-set2 databases transaction-and-concurrency easy
Answer ☟
Consider a simple checkpointing 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?
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

Answer ☟
Consider the partial Schedule S involving two transactions T 1 and T 2. 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) .
Schedule S
Time Instance Transaction ID
T1 T2
1 read(A)
2 write(A)
3 read(C)
4 write(C)
5 read(B)
6 write(B)
7 read(A)
8 commit
9 read(B)
Suppose that the transaction T 1 fails immediately after time instance 9. Which of the following statements is correct?
A. T 2 must be aborted and then both T 1 and T 2 must be re-started to ensure transaction atomicity
B. Schedule S is non-recoverable and cannot ensure transaction atomicity
C. Only T 2 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
Answer ☟
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
gate2016-cse-set1 databases transaction-and-concurrency easy
Answer ☟
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
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.
Answer ☟

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?
A. Topological order
B. Depth-first order
C. Breadth- first order
D. Ascending order of the transaction indices
Answer ☟
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
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.
Answer ☟
Consider the following two statements about database transaction schedules:
I. Strict two-phase locking protocol generates conflict serializable schedules that are also recoverable.
II. Timestamp-ordering concurrency control protocol with Thomas’ Write Rule can generate view serializable schedules that are
not conflict serializable
Which of the above statements is/are TRUE?

A. I only
B. II only
C. Both I and II
D. Neither I nor II
gate2019-cse databases transaction-and-concurrency
Answer ☟
Consider a schedule of transactions T1 and T2 :
T1 RA RC WD WB Commit
T2 RB WB RD WC Commit
Here, RX stands for “Read(X)” and WX stands for “Write(X)”. Which one of the following schedules is conflict equivalent to the
above schedule?
A.
B.

C.
D.
gate2020-cse databases transaction-and-concurrency
Answer ☟
Suppose a database system crashes again while recovering from a previous crash. Assume checkpointing is not done by the
database either during the transactions or during recovery.
Which of the following statements is/are correct?
A. The same undo and redo list will be used while recovering again
B. The system cannot recover any further
C. All the transactions that are already undone and redone will not be recovered again
D. The database will become inconsistent
gate2021-cse-set1 multiple-selects databases transaction-and-concurrency
Answer ☟
3.17.23 Transaction And Concurrency: GATE IT 2004 | Question: 21 top☝ ☛ https://gateoverflow.in/3662
Which level of locking provides the highest degree of concurrency in a relational database ?
A. Page
B. Table
C. Row
D. Page, table and row level locking allow the same degree of concurrency
gate2004-it databases normal transaction-and-concurrency
Answer ☟
Consider the following schedule S of transactions T 1 and T 2 :
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 T 1, T 2
B. S is serializable only as T 2, T 1
C. S is serializable both as T 1, T 2 and T 2, T 1

D. S is not serializable either as T 1, T 2 or as T 2, T 1
gate2004-it databases transaction-and-concurrency normal
Answer ☟
Amongst the ACID properties of a transaction, the 'Durability' property requires that the changes made to the database by a
successful transaction persist
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
gate2005-it databases transaction-and-concurrency easy
Answer ☟
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:
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:
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
Where commission > 50000 and commission is < = 100000;
T3
Update salesinfo
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
Answer ☟
Consider the following two transactions: T 1 and T 2.
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?
S1 : lock S(A); S2 : lock S(B);

read (A); read (B);
lock S(B); lock S(A);
read (B); read (A);
If A = 0 If B ≠ 0
A.
then B ← B + 1; then A ← A − 1;
commit; commit;
unlock (A); unlock (B);
unlock (B); unlock (A);
S1 : lock X(A); S2 : lock X(B);
read (A); read (B);
lock X(B); lock X(A);
read (B); read (A);
If A = 0 If B ≠ 0
B.
then B ← B + 1; then A ← A − 1;
unlock (A); unlock (A);
commit; commit;
read (A); read (B);
read (B); read (A);
If A = 0 If B ≠ 0
C.
then B ← B + 1; then A ← A − 1;
unlock (A); unlock (B);
commit; commit;
read (A); read (B);
read (B); read (A);
If A = 0 If B ≠ 0
D.
then B ← B + 1; then A ← A − 1;
unlock (A); unlock (A);
commit; commit;
Answer ☟
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 3WA 1RA 1RB 1WA 1WB 3WC
(S3) 2RA 3RC 3WA 2WA 2WB 3WC 1RA 1RB 1WA 1WB
Which of the following statements is TRUE?
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
Answer ☟
Answers: Transaction And Concurrency
3.17.1 Transaction And Concurrency: GATE CSE 1999 | Question: 2.6 top☝ ☛ https://gateoverflow.in/1484
If we draw the precedence graph we get a loop,and hence the schedule is not conflict serializable.
There is no blind write too so ,there is no chance that view serializability can occur.
Now 2pl ensures CS.
Since possiblity of CS is ruled out at the onset,so schedule cannot occur in 2PL.
Ans d)

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

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
T 2 read D2 value from initial database and T 1 modify D2 so T 2 should execute before T 1.
i.e., T 2 → T 1
2. Final write.
final write of D1 in given schedule done by T 2 and T 1 modify D1 i.e. W(D1)..
that means T 2 should execute after T 1.
i.e., T 1 → T 2
So, schedule not even View Serializable.

Not Serializable.
Correct Answer: D


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.
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.
 105 votes -- Pooja Palod (24.1k points)

For S1 : it is not conflict serializable
For S2 : it is conflict serializable
Answer is option C.

The answer is B.
S1 has a cycle from T 1 → T 2 and T 2 → T 1.

S2-- It is uni-directional and has only T 2 → T 1.
S3-- It is uni-directional and has only T 1 → T 2.
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.

In basic two phase locking there is a chance for deadlock
Conservative 2pl is deadlock free
I go with B.


Answer is option A.
create precedence graph and apply Topological sort on it to obtain
T1 → T3 → T2
References

Answer is (B). Explanation: T 1 : r(P), r(Q), w(Q)T 2 : 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 T 1− > T 2 and there is a conflict from T 2− > T 1 therefore, the graph will contain a cycle. so we can say that
the schedule is not conflict serializable.

(D) make precedence graph for all the options, for option (D) only graph will be acyclic, hence (D) is CSS.

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.
Hope this helps.

 50 votes -- Ramandeep Singh (131 points)
Even though @Ramandeep Singh has answered this question, I'd like to add some additional points because in the comments and
discussion on this question, many students are having incorrect arguments which they think are correct.
The Mistake that most students are doing (in the comments to this question) is that they are Not making correct Precedence
Graph because they are not making conflict edges in the Precedence graph "from a committed transaction to a newly started
transaction"....which is completely wrong because if you do so then How will you make Precedence Graph for Serial Schedule??
Following all the definitions and concepts are directly (without modification) picked mostly from Navathe and some from the
following link : http://www.ict.griffith.edu.au/~rwt/uoe/1.1.ccc.html

Refer Navathe if you still have some doubt.
Transactions :
A transaction is effectively a sequence of read and write operations on atomic database items. A transaction may be incomplete
because the (database) system crashes, or because it is aborted by either the system or the user (or application). Complete
transactions are committed. Transactions must terminate by either aborting or committing.
Complete Schedule :
A schedule S of n transactions T 1, T 2, … , T n is said to be a complete schedule if the following conditions hold:
1. The operations in S are exactly those operations in T 1, T 2, … , T n , including a commit or abort operation as the last
operation for each transaction in the schedule.
2. For any pair of operations from the same transaction T i , their relative order of appearance in S is the same as their order of
appearance in T i . (i.e Operation order in/of every transaction must preserve.)
3. For any two conflicting operations, one of the two must occur before the other in the schedule.
Condition 1 simply states that all operations in the transactions must appear in the complete schedule. Since every transaction has
either committed or aborted, a complete schedule will not contain any active transactions at the end of the schedule.
In general, it is difficult to encounter complete schedules in a transaction processing system because new transactions are
continually being submitted to the system. Hence, it is useful to define the concept of the committed projection C(S) of a
schedule S .
Committed Projection of a schedule :

Committed Projection C(S) of a schedule S includes only the operations in S that belong to committed transactions—that is,
transactions T i whose commit operation Ci is in S .
Given a schedule S, the committed projection C(S) is the subset of S consisting of operations (r1(X), w2(Y ), etc) that are
part of transactions that have committed ( that is, r1(X) would be part of C(S) only if transaction 1's commit, c1, were also part
of S). This is sometimes useful in analyzing schedules when transactions are continuously being added.
A committed projection C(S) of a schedule S includes the operations in S only from the committed transactions. Let's take an
example :
Transactions:
T 1 : r1(X); w1(X); r1(Y ); w1(Y ); c1;

T 2 : r2(Y ); w2(Y ); a2;
T 3 : r3(X); w3(X);
S1 : r1(X); r2(Y ); w1(X); w2(Y ); r1(Y ); a2; w1(Y ); c1; r3(X); w3(X);
Then C(S1) =??

Well, C(S1) will be the same as T 1 because T 3 has No Commit/Abort operation as the last operation of the transaction and T 2
is Not committed. So, by the definition of Committed Transaction, C(S1) = T 1.
Now, as according to Navathe,

We can theoretically define a schedule S to be serializable if its committed projection
C(S) is equivalent to some serial schedule, since only committed transactions are guaranteed by the DBMS.
And It applies to both Conflict and View Serializability.
A schedule is serialisable if the effect of its committed projection (the restriction to its committed transactions) on any
consistent database is identical to that of some serial schedule of its committed transactions.
(Conflict) Serialisability theorem :
Given a schedule S , define the serialisation graph(Precedence Graph) SG(S) to have the committed transactions of S as its
nodes, and a directed edge from T 1 to T 2 if T 1 and T 2 contain conflicting operations O1 and O2 such that O1 precedes O2 in
S. Then S is serialisable if and only if SG(S) is acyclic.
http://www.ict.griffith.edu.au/~rwt/uoe/1.1.ccc.html
Now, coming to the given question :

The given schedule is Complete Schedule as all the transactions in the schedule are committed(or aborted). Moreover, the given
schedule is Committed Projection of itself as well because all the Transactions are committed. Now, as the above definition of
Conflict serializability suggests, we make Precedence graph for this schedule and in the precedence graph, the Nodes will be the
Transactions participating in the committed projection of the schedule(which is same as the given schedule ) ..
The precedence graph will be as following :

From the precedence graph we can see that Only One serial schedule is conflict equivalent to the given schedule which is
T 2, T 3, T 1, T 4, … No other schedule is conflict equivalent to the given schedule.
Only One serial schedule is conflict equivalent to the given schedule which is T 2, T 3, T 1, T 4, … This makes sense because T 2
is reading the initial value of data item X (directly from the database) But if we run either of T 3 or T 1 before T 2 then they will
write the data item X and T 2 will have to read the modified value of X. Hence, Only one Serial Schedule can be equivalent to
the given schedule and that is T 2, T 3, T 1, T 4.
The Mistake that most students are doing (in the comments to this question) is that they are Not making correct Precedence
Graph because they are not making conflict edges from a committed transaction to a new started transaction....which is
completely wrong because if you do so then How will you make Precedence Graph for Serial Schedule??
Serial Schedule (Definition as it is given in Navathe) : Formally, a schedule S is serial if, for every transaction T participating
in the schedule, all the operations of T are executed consecutively in the schedule; otherwise, the schedule is called nonserial.
Therefore, in a serial schedule, only one transaction at a time is active—the commit (or abort) of the active transaction initiates
execution of the next transaction. No interleaving occurs in a serial schedule.
S = R1 (X) W1 (X) C1 R2 (X) W2 (X) C2 R3 (X) W3 (X) C3
If you make precedence graph for this schedule, then you must get a acyclic precedence graph But those students who are not
putting conflict edges in the precedence graph "from a committed transaction to a newly started transaction" then you won't get
any edges in this graph and the graph will be empty graph, which you know is not correct.
Consider this schedule :
T1 T2 T3
Write(X)
Writes(Z)
Writes(X)
Commit
Writes(Y)
Reads(Y)
Writes(Z)
Writes(M)
Commit
Reads(M)
Commit
Try to find whether this schedule is Conflict Serializable Or Not??

If you do it correctly, It is Not conflict serializable because there is Cycle in the precedence graph of this schedule. But If you
don't put conflict edges in the precedence graph "from a committed transaction (T 1) to a newly started transaction (T 3)" then
you won't get edge T 1 → T 3 in the precedence graph and hence, you will incorrectly get the answer as Conflict serializable.
References

 45 votes -- Deepak Poonia (23.4k points)
S1 has no cycle hence, Conflict-Serializable

S2 has cycle hence NOT Conflict-Serializable
Answer is option A.

B. 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.
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 T 1 and T 3 has uncommitted write operation, so they must be undone. Even though T 2 has
committed after writing, but it is after checkpoint. So, it needs to be redone.
Answer is A.


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.
 66 votes -- Tamojit Chatterjee (1.9k points)

A - Atomicity
C - Consistency
I - Isolation
D - Durability.
Answer (D)

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

Topological Order.
 24 votes -- Sharathkumar Anbu (595 points)

Answer is C
T1 T2
R(x)
R(x)
R(y)
W(x)
R(y)
W(x)
a1
a2

(A): This is not possible, because we have no dirty read ! No dirty read ⟹ Recoverable
(B): This is not possible, because of no Dirty read ! No dirty read ⟹ No cascading aborts !
(D): This is not true, because we can see clearly in image that after W1(X) before T1 commit or aborts T2 does W2(x) !
C is only option remaining !

1. Strict 2PL allows only schedules whose precedence graph is acyclic i.e. schedule is Conflict Serial. In 2PL, transactions do
not release exclusive locks until the transaction has committed or aborted i.e. schedule is recoverable.
2. Time stamp ordering schedule with Thomas write rule generate View serial schedule with BLIND WRITE. Because of
BLIND WRITE it won't be Conflict Serial.
So, Option C - both are true

If you draw the dependency graph, you'll notice that there is a cycle. Hence Option (D) and Option (B) are straightaway
False.
Now in Option (C), there is a swapping operation of conflicting operations W1 (D) and R2 (D). Hence it's False as well.
Hence, Option(A) is the answer
 8 votes -- Debasish Das (1.5k points)

Answer: A
Ideation/Source of the content: Navathe 6th Edition, 22.1: Recovery Concepts
Explanation:
Support for option A and against option C: Since check-pointing is not used we have to depend on the system logs. Let's
suppose we have three transactions A, B and C. Also assume that transaction A and C commits before failure and B was started
but the system crashed before it can commit. So, in the first recovery process database will redo A and C as per the system logs.
Now consider that while redoing A successfully commits, the system crashed for the second time before the B can commit. So,
while recovering for the second time the same system logs will be used. However, it is should be noted that the system logs will
also have entry to redo transaction A since it was committed after the first failure. However, the undo/redo operations are
idempotent (they are the same no matter how many time they are executed).
Against option B: If the system crashes again same logic as above can be used for recovery.
Against option D: Inconsistency refers to situations (generally) when the value of a shared variable varies in two or more
transactions, but that doesn’t seem to happen here as no uncommitted transaction’s data is being read/written during the entire
recovery process.
Conclusion: So, the only option of selecting the same list for undo/redo seems to be correct.
 1 votes -- Abhishek Dutta (145 points)

Row level locking provides more concurrency, because different transactions can access different rows in a table / page
at same time,
Correct Answer: C


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.

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 dont 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.

Correct Answer : D
T 3 followed by T 2 followed by T 1 will be correct execution sequence:
other cases some people will get two times increment
eg. if we have T 1 followed by T 2
if initial commision is 49500
then he is belonging to < 50000
hence, 49500 ∗ 1.02 = 50490
now, he is eligible in second category
then, 50490*1.04 = 52509.6
so, he wil get increment two times. but he is eligible for only one slab of commision.

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.


Two schedules are conflict equivalent if we can derive one schedule by swapping the non-conflicting operations of the
other schedule.
S1
T1 T2 T3
R(A)
W(A)
R(C)
W(B)
W(A)
W(C)
R(A)
R(B)
W(A)
W(B)
Here, we can swap R(C) and W(B) since they are non-conflicting pair (since they are operating on different data items)
After swapping the schedule will become T 2 → T 3 → T 1
T1 T2 T3
R(A)
W(A)
W(B)
R(C)
W(A)
W(C)
R(A)
R(B)
W(A)
W(B)
S2
T1 T2 T3
R(C)
R(A)
W(A)
W(B)
W(A)
R(A)
R(B)
W(A)
W(B)
W(C)
Here, we can swap and write R(C) after performing T2 operations:- R(A), W(A) and W(B) since each of them form non-
conflicting pair with R(C) (since they are operating on different data items)
Also, we can swap W(C) and can execute it before all the T1 operations as each of the t1 operations are forming non-conflicting
pair with W(C) (since they are operating on different data items)
After swapping the schedule will become T 2 → T 3 → T 1

T1 T2 T3
R(A)
W(A)
W(B)
R(C)
W(A)
W(C)
R(A)
R(B)
W(A)
W(B)
S3
T1 T2 T3
R(A)
R(C)
W(A)
W(A)
W(B)
W(C)
R(A)
R(B)
W(A)
W(B)
Here, we can't swap the operations and make it as T 2 → T 3 → T 1 because of the conflicting pairs W(A)and W(A)
∴ Option D. S1 is conflict equivalent to S2, but not to S3 is the correct answer.
Answer Keys
3.1.1 N/A 3.1.2 N/A 3.1.3 N/A 3.1.4 N/A 3.1.5 B
3.1.6 N/A 3.1.7 B 3.1.8 N/A 3.1.9 N/A 3.1.10 N/A
3.1.11 C 3.1.12 B 3.1.13 C 3.1.14 D 3.1.15 A
3.1.16 C 3.1.17 C 3.1.18 B 3.1.19 5 3.1.20 50
3.1.21 A 3.1.22 52 3.1.23 B 3.1.24 C 3.1.25 A
3.1.26 C 3.1.27 A 3.1.28 A 3.2.1 N/A 3.2.2 A
3.2.3 8 3.2.4 19 3.2.5 B 3.3.1 54 3.3.2 B
3.3.3 B 3.4.1 False 3.5.1 True 3.5.2 N/A 3.5.3 N/A
3.5.4 N/A 3.5.5 N/A 3.5.6 N/A 3.5.7 B;D 3.5.8 False
3.5.9 N/A 3.5.10 A 3.5.11 D 3.5.12 N/A 3.5.13 B
3.5.14 D 3.5.15 B 3.5.16 C 3.5.17 A 3.5.18 N/A
3.5.19 C 3.5.20 C 3.5.21 D 3.5.22 B 3.5.23 C

3.5.24 D 3.5.25 C 3.5.26 D 3.5.27 C 3.5.28 A
3.5.29 C 3.5.30 B 3.5.31 A 3.5.32 B 3.5.33 A
3.5.34 C 3.5.35 B 3.5.36 B 3.5.37 A 3.5.38 B
3.5.39 C 3.5.40 A 3.5.41 A 3.5.42 A;C;D 3.5.43 B
3.5.44 A 3.5.45 B 3.5.46 B 3.5.47 A 3.5.48 D
3.5.49 A 3.6.1 B 3.6.2 B 3.6.3 A 3.6.4 C
3.6.5 4 3.6.6 C 3.6.7 A 3.6.8 A 3.6.9 B
3.6.10 C 3.7.1 N/A 3.7.2 N/A 3.7.3 3 3.7.4 C
3.7.5 A 3.7.6 C 3.7.7 C 3.7.8 C 3.7.9 C
3.7.10 4 3.7.11 698 : 698 3.8.1 A 3.8.2 A 3.8.3 A
3.8.4 C 3.8.5 B 3.8.6 A 3.8.7 A 3.9.1 C
3.10.1 C 3.10.2 A 3.10.3 C 3.11.1 B 3.11.2 C
3.11.3 0.00 3.11.4 D 3.12.1 N/A 3.12.2 N/A 3.12.3 N/A
3.12.4 N/A 3.12.5 N/A 3.12.6 N/A 3.12.7 D 3.12.8 N/A
3.12.9 B 3.12.10 C 3.12.11 D 3.12.12 C 3.12.13 N/A
3.12.14 A 3.12.15 D 3.12.16 B 3.12.17 D 3.12.18 A
3.12.19 A 3.12.20 D 3.12.21 D 3.12.22 4 3.12.23 C
3.12.24 1 3.12.25 C 3.12.26 B 3.13.1 N/A 3.13.2 N/A
3.13.3 D 3.13.4 C 3.13.5 C 3.13.6 C 3.13.7 B
3.13.8 C 3.13.9 C 3.13.10 A 3.13.11 A 3.13.12 D
3.13.13 D 3.13.14 C 3.14.1 D 3.15.1 N/A 3.15.2 N/A
3.15.3 N/A 3.15.4 N/A 3.15.5 N/A 3.15.6 N/A 3.15.7 N/A
3.15.8 D 3.15.9 N/A 3.15.10 N/A 3.15.11 A 3.15.12 C
3.15.13 N/A 3.15.14 C 3.15.15 N/A 3.15.16 N/A 3.15.17 N/A
3.15.18 C 3.15.19 D 3.15.20 D 3.15.21 C 3.15.22 B
3.15.23 C 3.15.24 A 3.15.25 X 3.15.26 C 3.15.27 A
3.15.28 C 3.15.29 C 3.15.30 B 3.15.31 D 3.15.32 B
3.15.33 C 3.15.34 D 3.15.35 2 3.15.36 A 3.15.37 2
3.15.38 2.6 3.15.39 7 3.15.40 D 3.15.41 5 3.15.42 A
3.15.43 819 : 820 ; 205 : 205 3.15.44 B 3.15.45 D 3.15.46 C 3.15.47 C
3.15.48 D 3.15.49 A 3.15.50 B 3.15.51 D 3.16.1 A
3.17.1 D 3.17.2 D 3.17.3 D 3.17.4 B 3.17.5 C
3.17.6 B 3.17.7 B 3.17.8 A 3.17.9 B 3.17.10 D
3.17.11 C 3.17.12 A 3.17.13 B 3.17.14 A 3.17.15 B
3.17.16 D 3.17.17 A 3.17.18 A 3.17.19 C 3.17.20 C
3.17.21 A 3.17.22 A 3.17.23 C 3.17.24 X 3.17.25 D

Gate DBMS

Uploaded by

Copyright:

Available Formats

Gate DBMS

Uploaded by

Document Information

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Gate DBMS

Uploaded by

Copyright:

Available Formats

3 Databases (243)

Mark Distribution in Previous GATE

3.1 B Tree (28) top☝

3.1.1 B Tree: GATE CSE 1989 | Question: 12a top☝ ☛ https://gateoverflow.in/91199

descriptive gate1989 databases b-tree

3.1.2 B Tree: GATE CSE 1994 | Question: 14a top☝ ☛ https://gateoverflow.in/2510

gate1994 databases b-tree normal descriptive

3.1.3 B Tree: GATE CSE 1994 | Question: 14b top☝ ☛ https://gateoverflow.in/360163

gate1994 databases b-tree normal descriptive

3.1.4 B Tree: GATE CSE 1997 | Question: 19 top☝ ☛ https://gateoverflow.in/2279

© Copyright GATE Overflow. Some rights reserved.

gate1997 databases b-tree normal descriptive

3.1.5 B Tree: GATE CSE 1999 | Question: 1.25 top☝ ☛ https://gateoverflow.in/1478

Which of the following is correct?

gate1999 databases b-tree normal

3.1.6 B Tree: GATE CSE 1999 | Question: 21 top☝ ☛ https://gateoverflow.in/1520

gate1999 databases b-tree normal descriptive

B+ -trees are preferred to binary trees in databases because

A. Disk capacities are greater than memory capacities

gate2000-cse databases b-tree normal ugcnetjune2012ii

3.1.8 B Tree: GATE CSE 2000 | Question: 21 top☝ ☛ https://gateoverflow.in/692

i. after 6 insertions, and

Do NOT show intermediate stages.

i. in the normal case, and

© Copyright GATE Overflow. Some rights reserved.

3.1.9 B Tree: GATE CSE 2001 | Question: 22 top☝ ☛ https://gateoverflow.in/763

gate2001-cse databases b-tree normal descriptive

3.1.10 B Tree: GATE CSE 2002 | Question: 17 top☝ ☛ https://gateoverflow.in/870

gate2002-cse databases b-tree normal descriptive

© Copyright GATE Overflow. Some rights reserved.

gate2002-cse databases b-tree normal ugcnetjune2012ii

3.1.12 B Tree: GATE CSE 2003 | Question: 65 top☝ ☛ https://gateoverflow.in/952

What is the result of inserting G in the above tree?

gate2003-cse databases b-tree normal

3.1.13 B Tree: GATE CSE 2004 | Question: 52 top☝ ☛ https://gateoverflow.in/1048

gate2004-cse databases b-tree normal

3.1.14 B Tree: GATE CSE 2005 | Question: 28 top☝ ☛ https://gateoverflow.in/1364

A. Database relations have a large number of records

© Copyright GATE Overflow. Some rights reserved.

gate2005-cse databases b-tree normal

gate2007-cse databases b-tree normal isro2016

3.1.16 B Tree: GATE CSE 2008 | Question: 41 top☝ ☛ https://gateoverflow.in/453

gate2008-cse databases b-tree normal

3.1.17 B Tree: GATE CSE 2009 | Question: 44 top☝ ☛ https://gateoverflow.in/1330

gate2009-cse databases b-tree normal

3.1.18 B Tree: GATE CSE 2010 | Question: 18 top☝ ☛ https://gateoverflow.in/2191

© Copyright GATE Overflow. Some rights reserved.

3.1.19 B Tree: GATE CSE 2015 Set 2 | Question: 6 top☝ ☛ https://gateoverflow.in/8052

gate2015-cse-set2 databases b-tree normal numerical-answers

3.1.20 B Tree: GATE CSE 2015 Set 3 | Question: 46 top☝ ☛ https://gateoverflow.in/8555

gate2015-cse-set3 databases b-tree normal numerical-answers

3.1.21 B Tree: GATE CSE 2016 Set 2 | Question: 21 top☝ ☛ https://gateoverflow.in/39569

B+ Trees are considered BALANCED because.

gate2016-cse-set2 databases b-tree normal

3.1.22 B Tree: GATE CSE 2017 Set 2 | Question: 49 top☝ ☛ https://gateoverflow.in/118561

gate2017-cse-set2 databases b-tree numerical-answers normal

3.1.23 B Tree: GATE CSE 2019 | Question: 14 top☝ ☛ https://gateoverflow.in/302834

© Copyright GATE Overflow. Some rights reserved.

A. B+ Tree is a height-balanced tree