Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: THEend8_
Homework 2 – Indexing and Relational Algebra
Note: the pictures are slightly simplified, they do no show any record pointer
for the leaf nodes.
1. Assume we have the following B+-tree of order 1. Each node in the index
must have either 1 or 2 keys (i.e, 2 or 3 pointers), and the leaves can hold
up to 2 entries.
a) What is the height of this tree after the following sequence of insertions:
26, 27, 28, 29, 30? Note that the current tree height is 2.
b) What is the maximum number of keys one can insert into the tree above
without changing its height?
c) What is the minimum number of keys one can insert to change the
height of the tree above?
d) Unrelated to the index tree above, assume you bulk-loaded the keys 1 to
60 into a B+ tree with fill-factor 0.75 and order d = 2. How many leaf nodes
would there be?
2. Suppose we have an Alternative 2 unclustered index on the attribute pair
(assignment_id, student_id) with a height of 2 (one must traverse 3 index
pages to reach a leaf page).
Here is the schema:
CREATE TABLE Submissions (
record_id integer UNIQUE,
assignment_id integer,
student_id integer,
time_submitted integer,
grade_received byte,
comment text,
regrade_request text,
PRIMARY KEY(assignment_id, student_id) );
CREATE INDEX SubmissionLookupIndex ON Submissions (assignment_id,
student_id);
Assume the table and its associated data takes up 12 MB (note:
1MB=1024KB) on disk and that page size is 64 KB. (This excludes the index
pages, but includes extra space allocated for future insertions, therefore
pages are assumed 2/3 full).
Assume also you know the size of each attribute type: integer 4B, text: 32B,
byte: 1B. Page pointers (page Ids) are 2B long, row Ids are 4B long.
a) How many records do we have in the Submissions table?
b) We want to scan all the records in Submissions. How many I/Os will this
operation take?
c) The following instruction is executed:
UPDATE Submissions
SET grade_received=85
WHERE assignment_id=20 AND student_id=12345;
How many I/Os will this operation take?
d) In the worst case, how many I/Os does it take to perform an equality
search on attribute grade_received?
3. Consider the B+ tree index of order d = 2 shown below.
a) Show the index resulting from inserting a data entry with key 9 into this
index.
b) Show the index resulting from inserting a data entry with key 3 into the
original index. How many page reads and page writes are necessary for this
insertion?
c) Show the index resulting from deleting the data entry with key 8 from the
original index, assuming that the left sibling is checked for possible
redistribution.
d) Show the index resulting from deleting the data entry with key 8 from the
original index, assuming that the right sibling is checked for possible
redistribution.
e) Show the index resulting from starting with the original index, inserting a
data entry with key 46 and then deleting the data entry with key 52.
f) Show the index resulting from deleting the data entry with key 91 from the
original index.
4. Relational Algebra. Consider the following schema:
Movie(movieId: integer , title: string , directorId:integer)
MovieDirector(directorId:integer , dname:string)
MovieClient(clientId:integer, cname:string)
Seen(movieID: integer , clientID:integer)
Liked(movieID: integer , clientID: integer)
The primary key fields are underlined, and the domain of each field is listed
after the field name. For example, movieId is the primary key for the Movie
table, movieId and clientId together form the primary key for Seen, etc.
Describe in plain English (without using words such as join, project, select,
etc) what the following relation algebra expressions (execution plans)
compute (if they compute something…):
The following relational operators are used:
? : natural join (with equality condition on all common attributes)
π : projection
σ : selection
– : set difference.
a) πtitle(πDirectorId (σdname=”John Wu”MovieDirector) ? Movie)
b) πtitle,dname(πDirectorId (σdname=”John Wu”MovieDirector) ? Movie)
c) πtitle (Seen – Liked)
d) πClientId(MovieClient) – πClientId(πMovieId (Movie) x πClientId (MovieClient) –
Seen)
e) πClientId(Liked ? Seen)