/ 00576

Sri Lanka Institute of Information Technology

B.Sc. Honours Degree in Information Technology

-.
Specialized in Software Engineering

Final Examination
Year 3, Semester 2 (2023)

SE3060 -Database Systems

Duration: 2 hours

EE
November 2023

Instructions to Candidates:

• This paper is preceded by a lo-minute reading period. The supervisor will

indicate when answering may commence.
• This paper has 4 questions.
• Answer all questions in the booklet given.
• The total marks for the paper is 100.
• This paper contains 6 pages, including the cover page.
• Electronic devices capable of storing and retrieving text, including
calculators and mobile phones are not allowed.
 00576

Question I - Transactions and Concurrenc Control 25 marks

(a) List the properties ofa transaction. Briefly explain each of them.
(4 marks)

(b) Compare why serializable schedules are more important for database systems than the
serial schedule.

(3 marks)

(c) "The strict Two-Phase Locking (S2PL) protocol significantly reduces the occunence of
cascading aborts and unrecoverable schedules, enhancing concurrency control in
database systems". Do you agree with this? Provide reasonable justiflcation for your
decision.

(4 marks)
'`~
(d) Consider the following part of the transaction schedule.
T1 T2 T3 T4
SA
RA
S(C)
R(C)
X(C)wait

X®)
W)
X@)wait

XWD

X@)wait

X(A)wait

Assume that Transaction Ti is higher priority than transaction T,+I(i.e. transaction T| has
higherprioritythanT2;T2hashigherprioritythanT3;andT3hashigherprioritythanT4).

Review the provided transaction schedule and analyse the reasons for the delay in
completing these transactions. Assume that the strict two-phase locking protocol
has been used to enable concurrency.

(3 marks)
Draw a Wait-For-Graph for the given schedule and check for deadlock.

(2 marks)
Draw the schedule again considering deadlock prevention algorithm: Wound-wait
approach.

(4 marks)
Page 2 of 6
 ::::)lJf3ri6

EE
Describe the steps involved in executing each of the following operations according to
the Sj.mp/e Tree I ocAz.ng cz/gorz.r¢m, in tens of the order in which nodes are locked,
unlocked, read and written. Be specific about what type of locks are obtained and
released. .
i. Search23.
ii. Delete43.
iii. Insert44.
(5 marks)

Question 2 -Indexin£ Techniques 25 marks

(a) Briefly explain three file organization techniques used in database systems to store and
manage data efficiently.
(4' marks)
`-
(b) Given that indexes can speed up queries, why don't we just create as many indexes as
we like?
(3 marks)

(c) How is a clustered B+ tree index different from an un-clustered one?

(3 marks)

(d) Consider the following B+ tree of order 2:

root

Page 3 of 6
 00576

Illustrate the 8+ tree after deleting 32. Consider left sibling for redistribution of data
entries.
(5 marks)

(e) Construct an Extendible Hashed File for the following.marks received by a group of
students in a course. The hashing function will consider the last 2 digits of the binary
representation.

marks
(5 marks)

(I) Provide three reasons to justify why most commercial databases support 8+ tree
indexes.
(5 marks)

EE
uestion 3 - Query Optimization 25 marks

(a) What is the justification for using I/0 costs as the main measure to compare different
algorithms for evaluating relational operators?
(2 marks)

a) Briefly explain why it is often advantageous to do selections before joins in a query

plan. How do early projections help during the query execution?
(3 marks)

(c) Consider the following relation:

Emp (etd: integer, ename: string, age: integer, salary: float)

On this table, there is a c/#s/ered a+ tree index on ez.d and an "#c/#s/ered a+ tree index
On age . EE'

i. The data records are stored in a heap file. In what order' are the data records of Emp
table stored and why?
(2 marks)

ii. Consider the following query:

Select ename, salary

From emp
Where age>2©;

If 95% of tuples satisfy the selection condition, what would be the best access path
for processing this query? Justify your answer.
(5 marks)

Page 4 of 6
 •r!J#F;n6

iii. Consider the following query:

Select age, avg(salary)

From emp
Group by age;

Would a clustered index on <age, salary> be useful? Explain briefly.

(6 marks)

(d) Therelation Emp (eid: integer, ename:string, age: integer, salary: float)
contains 4,000 pages. There are 10 buffer pages. The attribute ez.d takes up 10 bytes,
e#ame 20 bytes, clge 2 bytes and sc!/crry 8 bytes. A clustered 8+ tree on <age, salary>
is the only index available. In estimating the cost of query plans, ignore the cost of
whting the final result.

Consider the following query:

`- Select age, avg(salary)
From emp
Where salary>40©0©
Group by age;
Assume that I 0% of the tuples satisfy the selection condition. Describe the best plan and
show an estimation of its cost.
(7 marks)

uestion 4 - Big data 25 marks

(a) Discuss two real world exanples where NoSQL databases can be applied.
(5 marks)

a) Consider the following structure of books collection and whte answers for the following
questions.
`~
book id : ``8001'' ,
titl= : "MongoDB: The Definitive Guide" ,
author : ``Kristina Chodorow"
pages : 432 ,
langruage : ``English" ,
year : 2013 ,
publisher : {
name : ``O'Reilly Media'' ,
founded : 1980
location : ``CA"

i. Write a MongoDB query to display the fields boot id, /j.//e, cr24/¢or and};ea;. for all
the documents in the books collection.
(2 marks)

Page 5 of 6
 005r`',7t:,

ii. Write a MongoDB query to display all the books which are published in the English
language.
(2 marks)

iii. Write a MongoDB query to find the books that have pages, more than 100 but less
than 500.
(2 marks)

iv. Write a MongoDB update statement to change the publication year of the book with
`book id' `8001' from 2013 to 2015.

(4 marks)

(c) Compare single field indexes and multikey indexes in MongoDB.

(5 marks)

(d) Briefly, explain four modules of the Hadoop framework. `-

(5 marks)

- End of the Question Paper -

EE

Page 6 of 6