LNMIIT/B. Tech.

/CSE/CORE/2022-23/ODD/CSE227/ET

The LNM Institute of Information Technology

Department: CSE
Information and Database Management Systems (CSE227)
Exam Type: ENDTERM

Time: 180 minutes Date: 07/12/2022 Max. Marks:80

Total Questions Total Marks CO1 CO2 CO3 CO4

11 80 Q3 - 7 Q1 – 3, Q2 – 4 Q5 – 8, Q6 - 8 Q7-12, Q8- 6
Q4 - 10 Q9- 8, Q10- 7
Q11- 7
CO weightage 7/80 = 9% 17/80 = 21% 16/80 = 20% 40/80 = 50%

Instructions to Candidate
i. There are 11 questions. All questions are compulsory.
ii. Answers without proper explanation will be given zero marks.
iii. All answers should be given in order of sequence of questions.

1. Consider a database that includes two relations Student and Program.

Student Program

Roll_no F_name L_name Prog_code Prog_code P_name

900 Alicia Smith 0001 0001 DSA

901 Alan Smith 0002 0002 IDBMS

902 Alicia Bush 0001

903 John Smith 0001

What relational algebra expression will return the following result? (3 Marks)

F_name L_name Program

Alicia Smith DSA

John Smith DSA

R F_name, Lname, Program (P F_name, Lname, P_name (S Prog_code=0001 AND L_name=’Smith’ (Student ⋈ Program)))

R-Rename, S – Select, P - Projection

2. Suppose relations R and S have n tuples and m tuples, respectively, where m<=n and m,n are positive integers. Give
the minimum and maximum number of tuples in the following operations with complete justification.
(2*2=4 Marks)
a) R U S
Minimum: n (when all tuples of S also exist in R),
Maximum: m+n (add all tuples from both relation)
LNMIIT/B. Tech./CSE/CORE/2022-23/ODD/CSE227/ET

b) R * S
Minimum: 0
Maximum: m*n (if no matching key constraint, it will be cross product)

3. Consider the ER schema for a ship-tracking database to track transport ships and their locations for shipping
authorities. Map this schema into a relational schema and specify all primary and foreign keys. The following
sample representation MUST be used. Suppose there are two tables T1 and T2. They should be represented as:
(7 marks)
T1 (a1, a2, a3, a4)
PRIMARY KEY (a1)
T2 (b1, b2, a1, b3, b4)
PRIMARY KEY (b1, b2)
FOREIGN KEY (a1) REFERENCES T1(a1)

SHIP(Sname, Owner, Type, Pname)

Primary Key(Sname)

Foreign Key (Type) References Ship_Type(Type)

Foreign Key (Pname) References Port(Pname)

SHIP_TYPE(Type,Tonnage,Hull)

Primary Key(Type)

PORT(Pname, Sname)

Primary Key(Pname, Sname)

Foreign Key (Sname) References Ship(Sname)

LNMIIT/B. Tech./CSE/CORE/2022-23/ODD/CSE227/ET

SHIP_MOVEMENT(Date, Time, Sname, Longitude, Latitude)

Primary Key(Date, Time, Sname)

Foreign Key (Sname) References Ship(Sname)

4. Consider the following relational schema:

Sale(clerk, store, city, date, item#, size, color)

// records that a clerk sold an item on a particular day
Item(item#, size, color, price)
// records prices and available sizes and colors for items

Make the following assumptions, and only these assumptions, about the real world being modelled:
i. Each clerk works in one store.
ii. Each store is in one city.
iii. A given item# always has the same price, regardless of size or color.
iv. Each item is available in one or more sizes and one or more colors, and each item is available in all
combinations of sizes and colors for that item.

Attempt the following problems:

a. Based on the assumptions above (and no others), specify an appropriate set of completely nontrivial
functional dependencies for relations Sale and Item.
b. Based on the assumptions above (and no others), specify all keys for relations Sale and Item.
c. Are relations Sale and Item in Boyce-Codd Normal Form (BCNF)? If not, decompose the relations so they
are in BCNF. (10 marks)

Ans:

(a)

FDs for Sale:

Clerk -> store ------- (1)

Store -> city ------- (2)

FD for Item

Item# -> price ------- (3)

(b)
LNMIIT/B. Tech./CSE/CORE/2022-23/ODD/CSE227/ET

Key for Sale:

(clerk, date, item#, size, color)

Key for Item:

(item#, size, color)

(c) (i)

Sale is not in BCNF as in both FDs LHS is not the candidate key (CK).

Take any one FD that violates the condition. Clerk -> store

(clerk)+ = {clerk, store, city}.

Therefore, decompositions are:

Sale1(clerk, store, city) and sale2(clerk, date, item#, size, color)

FDs (1) and (2) hold on Sale1. CK for Sale1 is (clerk). Therefore, FD (2) violates the condition of
Sale1. So the relation is not in BCNF.

Now take FD(2) that violates the BCNF condition of Sale1.

(store)+ = {city}.

Therefore, decompositions of Sale1 are:

Sale11(store, city) and sale12(clerk, store).

FD (1) holds on sale11 and FD (2) holds on sale12. Now both the relations are in BCNF because LHS is
a CK.

Sale2 is all key relation, so it is in BCNF.

The BCNF decompositions od Sale are Sale11, Sale12 and Sale2.

(c) ii

Item is not in BCNF.

FD (3) violates the condition of BCNF.

Decompositions are:

Item1(item#, price) and item2(item#, size, color)

Both the relations are now in BCNF.

5. Consider a disk with block size B = 512 bytes. A block pointer is P = 6 bytes long, and a record pointer is PR = 7
bytes long. A file has r = 30,000 EMPLOYEE records of fixed length. The record size is R = 115 bytes.
LNMIIT/B. Tech./CSE/CORE/2022-23/ODD/CSE227/ET

a. Calculate the blocking factor bfr and the number of file blocks b.
b. Suppose that the file is not ordered by the key field Ssn (9 bytes) and we want to construct a secondary
index on Ssn. Calculate
i. the index blocking factor bfri
ii. the number of first-level index entries and the number of first-level index blocks;
iii. the number of levels needed if we make it into a multilevel index;
iv. the total number of blocks required by the multilevel index; and
v. the number of block accesses needed to search for and retrieve a record from the file—given its
Ssn value—using the secondary index. (8 marks)

a. Bfr = floor(B/R) = floor(512/115) = 4

No. of file blocks = ceil(r/bfr) = ceil(30000/4) = 7500.
b. If the file is not ordered on ssn – secondary index will be created. The index will have one
entry for each ssn value. Since the data file has 30, 000 records, there will be 30, 000 index
entries. Each index record structure is 15 bytes.
i. Therefore, with bfri = 34,
ii. no. of first level blocks = ceil(30000/34) = 883.
iii. No. of second level blocks = 883/34 = 26 blocks.
No. of third level blocks = 26/34 = 1 block.
Therefore, total no. of levels = 3
iv. Total no. of blocks in the index = 883+26+1= 910 blocks.
v. The no. of block accesses (assuming that the block of outer index is in RAM) = (no.
of levels -1 ) + 1 block access to fetch the block with the record (in file) = 3 block
accesses.

6. For the B+ tree of order six in Figure 1, mention the min and max requirements at leaf and non-leaf nodes and show
the form of the tree after each of the following series of operations:

a. Insert 9
b. Insert 10
c. Insert 8
d. Delete 23
e. Delete 19 (8 marks)

7. Consider the below given schedule. Here R and W denotes the read and write operation on share data items X and
Y. Subscript 1, 2, 3 after the R and W represents the transaction number T1, T2, and T3.

Schedule: R1(X), R1(Y), W1(X), R2(Y), W3(Y), W1(X), C1, R2(Y), C2, C3
Find out the following for the given schedule:
i. Schedule is Serializable schedule or not. If yes, then what will be the number of equivalent serial
schedule?
ii. Schedule is Recoverable schedule or not?
iii. Schedule is Cascade less Rollback Recoverable schedule or not?
LNMIIT/B. Tech./CSE/CORE/2022-23/ODD/CSE227/ET

iv. Schedule is Strict Recoverable schedule or not? (12 marks)

8. Consider the below given transactions. Here R (READ) and W (WRITE) are the operations in the transaction.
T1, T2 represent the transaction number and X, Y are the shared data times.
T1: R(X), W(X), R(Y) C1
T2: R(X), W(X), R(Z) C2
Find out the following
i. Total number of recoverable schedule possible with transaction T1 and T2?
ii. Total number of irrecoverable schedule possible with transaction T1 and T2?
iii. Total number of schedules possible with transaction T1 and T2? (6 Marks)

9. Consider the below given schedule with the lock orders

T1: X(A), T2: S(A), T3: X(B), T4: S(C), T5:S(D), T5: X(B), T4: X(A), T3: S(C), T3: X(A), T1: S(D)
i. Draw the wait for graph for the given order of locks.
ii. Find whether the deadlock is present in the wait-for graph or not. Write the transactions which are
involved in the deadlock.
iii. If the last lock requested by T1 is an exclusive lock instead of shared lock on data item D, then what
will be its impact on the wait-for graph. Will it cause a deadlock? If yes, show using the updated wait-
for graph.
(8 Marks)

10. Consider the below given schedule

T2: R(A), T2: W(B), T3: W(A), T1: R(B), T4: R(B), T1: R(A), T1: W(C), T4: W(A)
i. Find out whether the given schedule can be executed using the [20, 10, 30, 40] time stamp order or not?
ii. Which transactions will be rolled back using the [20, 10, 30, 40] time stamp ordering.
iii. What will be the correct time stamp order to execute the given schedule? (7 Marks)

11. Consider a simple checkpointing protocol and the following set of operations in the log file.
(start, T4); (write, T4, x, 3, 2); (start, T1); (commit, T4); (write, T1, z, 7, 5);
(checkpoint, {_________});
(start, T2); (write, T2, x, 2, 9); (commit, T2); (start, T3); (write, T3, y, 2, 7); Crash
After the crash, if the system tries to recover
i. Which transactions will be there in the active list of the checkpoint.
ii. What will be the contents of the UNDO and REDO list.
iii. What will be the value of all shared data-items after the recovery. (7 Marks)