State True or False with reason
There is always a decomposition into Boyce-Codd normal form (BCNF) that is lossless and dependency preserving.

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?

Give a relational algebra expression using only the minimum number of operators from (∪, −) which is equivalent to R ∩ S.

State True or False with reason
Logical data independence is easier to achieve than physical data independence

Consider the following relational schema:

 COURSES (cno, cname)
 STUDENTS (rollno, sname, age, year)
 REGISTERED FOR (cno, rollno) 

(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.

Consider B+ − tree of order d shown in figure? (A) B⁺ − tree of order d contains between d and 2d keys in each node. (a) Draw the resulting B⁺ − tree after inserted in the figure.

(b) For a B⁺ − tree of order d with n leaf nodes, the number of nodes accessed during a search is 0(-).

Consider a relational database containing the following schemas.

The primary key of each table is indicated by underlying 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

Which one of the following is used to represent the supporting many-one relationships of a weak entity set in an entity-relationship diagram?

Consider a schedule of transactions T₁ and T₂:

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?

Consider a relational table R that is in 3NF, but not in BCNF. Which one of the following statements is TRUE?

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 ______.

A library relational database system uses the following schema

USERS (User#, UserName, HomeTown)
BOOKS (Book#, BookTitle, AuthorName)
ISSUED (Book#, User#, Date) 

Explain in one English sentence, what each of the following relational algebra queries is designed to determine

(a) σ User #=6 (11 User #, Book Title ((USERS ISSUED) BOOKS))
(b) σ Author Name (BOOKS (σ Home Town) = Delhi (USERS ISSUED))) 

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

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

   (a) Insert into R            (b) Insert into S 
   (c) Delete from R            (d) Delete from S    

Which of the following can cause violation of the referential integrity constraint above?

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.

The output of executing the SQL query is ___________.

Consider a database that has the relation schema CR(StudentName, CourseName). An instance of the schema CR is as given below.

The following query is made on the database.

         T1 ← πCourseName(σStudentName='SA'(CR))
         T2 ← CR ÷ T1

The number of rows in T2 is ____________.

Given two union compatible relations R₁(A,B) and R₂(C,D), what is the result of the operation R₁A = CAB = DR₂?

Which normal form is considered adequate for normal relational database design?

There are 5 records in a database.

There is an index file associated with this and it contain the values 1, 3, 2, 5 and 4. Which one of the fields is the index built form?

Which of the following query transformations (i.e. replacing the l.h.s. expression by the r.h.s. expression) is incorrect? R₁ and R₂ are relations, C₁, C₂ are selection conditions and A₁, A₂ are attributes of R₁?

(a) 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 parlor serves.
(Assuming 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.

(b) In a computer system where the 'best-fit' algorithm is used for allocating 'jobs' to 'memory partitions', the following situation was encountered:

When will the 20K job complete? Note - This question was subjective type.

(a) Four jobs are waiting to be run. Their expected run times are 6, 3, 5 and x. In what order should they be run to minimize the average response time?

(b) Write a concurrent program using par begin - par end to represent the precedence graph shown below.

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?

Consider the following relational database schemes:

  COURSES(Cno, name)
  PRE-REQ(Cno, pre_Cno)
  COMPLETED(student_no, Cno) 

COURSES give the number and the name of all the available courses.
PRE-REQ gives the information about which course 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.

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

The relational algebra expression equivalent to the following tuple calculus expression:

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 of the following is a key of R?

Which of the following is correct?

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

Consider the circuit shown below. In a certain steady state, the line Y is at '1'. What are the possible values of A, B and C in this state?

Which of the following sets of component(s) is/are sufficient to implement any arbitrary Boolean function?

Which of the following is/are correct?

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.)

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 employee 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. 100,000.

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

Given the relations

   employee (name, salary, deptno) and
   department (deptno, deptname, address)  

Which of the following queries cannot be expressed using the basic relational algebra operations (σ, π, ×, ⋈, ∪, ∩, -)?

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?

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

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) 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 5 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).

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 transactions T1, T2 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 had atleast one transaction since it was created. To simply your query, break it up into 2 steps by defining an intermediate view V.