# Databases (Test 1)

## Gate Exam : Cs Computer Science And Information Technology

| Home | | Gate Exam | | Cs Computer Science And Information Technology | | Databases |

Databases
| Databases |
Topic: Databases Tag: CS GATE 2009
Q.1
What is the chromatic number of an n-vertex simple connected graph which does not contain any odd length cycle? Assume n ≥ 2
A. 2
B. 3
C. n - 1
D. n
Answer : Option A
Explaination / Solution:
No Explaination.

Workspace
Report
Q.2
The Gross Domestic Product (GDP) in Rupees grew at 7% during 2012-2013. For international comparison, the GDP is compared in US Dollars (USD) after conversion based on the market exchange rate. During the period 2012-2013 the exchange rate for the USD increased from Rs. 50/ USD to Rs. 60/ USD. India’s GDP in USD during the period 2012- 2013
A. increased by 5 %
B. decreased by 13%
C. decreased by 20%
D. decreased by 11%
Answer : Option D
Explaination / Solution:

Per 100 Rs final value 107 Rs
⇒ Per 100/50 Dollars final value 107/60
for 100 dollars____?
= ((100 × 50)/100) × (107/60) = 89.16
Decreased by 11%.

Workspace
Report
Topic: Databases Tag: CS GATE 2009
Q.3
Which of the following statement (s) is/are correct regarding Bellman-Ford shortest path algorithm? P. Always find a negative weighted cycle, if one exists. Q. Finds whether any negative weighted cycle is reachable from the source.
A. P only
B. Q only
C. Both P and Q
D. Neither P nor Q
Answer : Option B
Explaination / Solution:
No Explaination.

Workspace
Report
Q.4
What is the optimized version of the relation algebra expression  where A1, A2 are sets of attributes in with A⊂ Aand F1, F2 are Boolean expressions based on
A.
B.
C.
D.
Answer : Option A
Explaination / Solution:
No Explaination.

Workspace
Report
Q.5
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 keys of R.
D. only in the primary key of R.
Answer : Option B
Explaination / Solution:

A prime attribute or key attribute of a relation scheme R is an attribute that appears in any of the candidate key of R, remaining attributes are known as non-prime or non-key tribute

Workspace
Report
Q.6
Consider the transactions T1, T2, and T3 and the schedules S1 and S2 given below.
T1 : r1 (X) ; r1 (z) ; w1 (X) ; w1 (z)
T2 : r2 (X) ; r2 (z) ; w2 (z)
T3 : r3 (X) ; 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 : Option A
Explaination / Solution:

Precedence graph for S1 & S2 are as follows

∴Only S1 is conflict serializable.

Workspace
Report
Q.7
Consider the relational schema given below, where eId of the relation dependentis 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

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
Answer : Option D
Explaination / Solution:

Part A of the above given relational algebra query will give the set of empIds of those employees whose age is less than or equal to the age of some of his/her dependents. Now when set of empIds of all employees minus set of empIds obtained from part A is done, then we get the set of empIds of employees whose age is greater than that of all of his/her dependents.

Workspace
Report
Q.8
Consider the decision problem 2CNFSAT defined as follows:
{ φ | φ is a satisfiable propositional formula in CNF with at most two literal per clause}
For example,  is a Boolean formula and it is in 2CNFSAT.
The decision problem 2CNFSAT is
A. NP-Complete.
B. solvable in polynomial time by reduction to directed graph reachability.
C. solvable in constant time since any input instance is satisfiable.
D. NP-hard, but not NP-complete.
Answer : Option B
Explaination / Solution:

2 SAT is in P. This we can prove by reducing 2 SAT to directed graph reachability problem which is known to be in P.
Procedure for reducing 2 SAT to reachability problem:
1. Let ϕ be CNF with clauses of length 2 and let P be the set of propositional variables(literals) in ϕ
2. Build a graph G=(V,E) with V= P { p|p P} ∪ ¬ ∈ and (x, y E )∈ iff there is a clause in ϕ that is equivalent to x y → (all the clauses are converted to equivalent implications and the graph built is called as implication graph)
3. Observe that ϕ is unsatisfiable iff there is a p P ∈ such that there is both a path from p to to ¬p and from ¬p to p in G.
This condition can be tested by running the reachability algorithm several times.

Workspace
Report
Topic: Databases Tag: CS GATE 2009
Q.9
Let R and S be relational schemes such that R={a, b, c} and S={c}. Now consider the following queries on the database:

Where R.c = S.c
Which of the above queries are equivalent?
A. I and II
B. I and III
C. II and IV
D. III and IV
Answer : Option C
Explaination / Solution:
No Explaination.

Workspace
Report
Topic: Databases Tag: CS GATE 2009
Q.10
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)
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 blue parts
D. Find the names of all suppliers who have not supplied only blue part
Answer : Option A
Explaination / Solution:
No Explaination.

Workspace
Report