Homework 3 (Solution)
Database Systems
CS 355 / CE 373
Fall 2024
Note: All questions are worth 20 points each.
Question 1
(20 points)
(C) [5 points] Develop a cascadeless concurrent schedule for the following three transactions:
1
Solution:
(A)
T1 T2
T3
T4
(B) It is conflict-serializable because the precedence graph is acyclic. One possible equivalent
serial order:
[T2, T1, T3, T4]
(C) A possible cascadeless concurrent schedule for T1, T2, and T3 is given below:
T1 T2 T3
read(X)
Read(Y)
Y=X+5
Write(Y)
Read(X)
X = X-5
Write(X)
Read(A)
A=A+5
Write(A)
commit
Read(Y)
Read(A)
A = A+5
Y=Y+5
Write(A)
commit
Write(Y)
commit
2
Question 2
(20 points)
The compatibility function between S-mode and X-mode locks is given below:
Consider the following execution schedule of transactions T1 and T2.
T1 T2 T3
Lock-X(A)
Read(A)
A:=A+20
Write(A)
Unlock-X(A)
Lock-S(A)
Lock-S(B)
Read(A)
Lock-X(C)
Read(C)
C:=C-50
Write(C)
Unlock-X(C)
Read(B)
Display(A+B)
Unlock-S(A)
Unlock-S(B)
Lock-X(B)
Read(B)
B:=B-20
Write(B)
Unlock-X(B)
a)
a) Will the above execution schedule be allowed by the concurrency-control manager of the
DBMS (i.e. will all the locking requests be granted by the concurrency-control manager
immediately)?
b) Is this execution schedule serializable?
c) Rewrite transactions T1,T2, and T3 with appropriate lock and unlock instructions that are
consistent with two-phase locking protocol.
Justify your answer?
3
Solution:
A) Yes. It will be allowed as it is consistent with the compatibility function.
Concurrency control manager will grant all the locking requests immediately.
B) However, even with the use of locking (but the violation of two-phase locking
protocol), this execution schedule is not serializable. It can be shown to be non-
serializable by using the precedence graph.
C) Under two-phase locking protocol:
T1 T2 T3
Lock-X(A) Lock-S(A) Lock-X(C)
Read(A) Lock-S(B) Read(C)
A:=A+20 Read(A) C:=C-50
Write(A) Read(B) Write(C)
Lock-X(B) Display(A+B) Unlock-X(C)
Read(B) Unlock-S(A)
B:=B-20 Unlock-S(B)
Write(B)
Unlock-X(A)
Unlock-X(B)
a)
4
Question 3
(20 points)
Consider the following table from the University Database:
In a typical university, this table may contain several thousand records.
(a) One of the most frequent operations on this table is to find the grade of a student in a
particular course, given his/her ID. To speed up search, an index has to be built on this
table:
(i) Given the above frequent operation of finding the student’s grade in a course given
the student ID, what is the most appropriate attribute on which to build the index.
Justify your answer.
(ii) Based on the attribute identified in part (i), you are supposed to build an index on
this table. Answer the following questions about the index with appropriate
reasoning. Should the built index be:
1. Dense or sparse?
2. Clustered or non-clustered?
3. Single-level or multi-level?
(b) It has been observed that queries filtering records based on course codes are experiencing
poor performance.
(i) Which attribute should be utilized to create an index and enhance the efficiency of
these queries?
(ii) Based on the attribute identified in part (1), you are supposed to build an index on
this table. Answer the following questions about the index
1. Dense or sparse?
2. Clustered or non-clustered?
5
Solution:
(a) There is no single answer specially for (ii). The following is a reasonable solution:
(i) We will use the student ID attribute to construct the index.
(ii) The index on the student ID should be
1. Dense if there are a manageable number of student records (typically
thousands). However, if the number of student records crosses millions (this can
happen if 100,000 students have taken 10 courses each), then creating a sparse
index might be a better option.
2. Since the student IDs are sorted, obviously it should be a clustered index.
3. A single level index might be appropriate for a manageable number of
student records. However, if the student records crosses millions, a multi-level
index might be more efficient for search and retrieval purposes.
(b)
i) An index should be crated on course_id (or course code) attribute.
ii) Since database file is not sorted by course_id, the index will be non-clustered.
Therefore, it will have to be dense as well (since sparse, non-clustered is not an option.)
6
Question 4
(20 points)
Consider the following 3 different databases:
(a) The Stock Exchange Database of a city is a large database (several million records) that
keeps track buying and selling of shares. On the days when the stock exchange is open
(Monday to Friday, 9am to 5pm), there is a frequent buying and selling of stocks,
typically within seconds. The stock exchange is closed over the weekend.
(b) A university library database system is a medium sized database (thousands of records)
that keeps track of books loaned, books returned and student readers. Everyday some
students loan books as well as return books resulting in a few transactions, typically <
100. The library is open (Monday to Friday, 9am to 5pm) and closed over the weekends.
(c) A public messages database system is a small sized database (hundreds of records) which
stores public messages (such as ‘Stop Smoking’, ‘Give way to emergency vehicles’, etc.)
to be broadcast to the general public on Radio, TV and the Internet. The database is
mostly read-only with a review and update of the messages once every month.
Suggest database backup strategies for each of the above database systems consisting of full,
differential, and incremental backups or any combination of these on an hourly, daily, or
weekly basis. Justify your answers based on storage space, backup time, and restoration
time.
Solution:
Note: There can be several backup strategies, each with its own rationale, so the following is
a suggested strategy. If your students state another strategy with a reasonable explanation,
consider giving them partial grade.
(a) For the stock exchange database, an hourly incremental backup, a daily differential backup
and a weekly full backup will be a reasonable strategy. This is because there are several
transactions happening every hour, hence the need for incremental backups. Likewise
differential backups are needed to backup the data of each day, as they require more time
to backup than an incremental backup but are easier to restore. The Stock Exchange is
closed over the weekend, so a weekly full backup might be more feasible. From a
restoration perspective, differential backups can be used to restore the database if a crash
happens during off hours. Incremental backups might be used if the database crashes
during working hours, however the restoration will be very inefficient.
(b) For the library database either a differential (or incremental) backup every day, followed
by full backup every week is a reasonable strategy. In case of a crash on a working day,
differential backups might be used to restore the data upto that day.
(c) For the messages database, an initial full backup is sufficient. This can be followed by a
monthly full backup.
7
Question 5
(20 points)
Consider the following records inserted in a MongoDB collection to answer the below-given
queries:
2 {
3 "title": "The Great Gatsby",
4 "author": ["F. Scott Fitzgerald"],
5 "genre": "Fiction",
6 "publicationYear": 1925, 7 "copiesAvailable": 5,
8 "checkedOutBy": [
9 { "memberId": "1001", "dueDate": ISODate("2023-12-15") },
10 { "memberId": "1002", "dueDate": ISODate("2023-11-30") }
11 ]
12 },
13 {
14 "title": "Good Omens",
15 "author": ["Terry Pratchett", "Neil Gaiman"],
16 "genre": "Horror",
17 "publicationYear": 1990,
18 "copiesAvailable": 2,
19 "checkedOutBy": [
20 { "memberId": "1001", "dueDate": ISODate("2023-12-15") },
21 { "memberId": "1002", "dueDate": ISODate("2023-11-30") }
22 ]
23 },
24 {
25 "title": "The Talisman",
26 "author": ["Stephen King", "Peter Straub"],
27 "genre": "Fantasy",
28 "publicationYear": 1984,
29 "copiesAvailable": 1,
30 "checkedOutBy": [
8
31 { "memberId": "1007", "dueDate": ISODate("2023-12-18") },
32 ]
33 },
34 {
35 "title": "Neverwhere",
36 "author": ["Neil Gaiman", "Lenny Henry"],
37 "genre": "Fantasy",
38 "publicationYear": 1996,
(a) Write a query to return the titles and authors of all the books in the database
[Link]({},{title: 1, author: 1}
(b) Write a query that returns all books that were published after 1900.
[Link]({publicationYear: {$gt: 1900}})
(c) Write a query to display all titles and authors of books having the Fantasy genre
[Link]({genre:”Fantasy”},{title:1, author: 1})
(d) Write a query that returns all books that are checked out by at least one member
[Link]({"checkedOutBy" : {$exists:true}});
(e) Write a query to get all the books checked out by member 1001.
[Link]({"[Link]":"1001"});