代做COMP7104、代写Database Systems、代写Java，Python，c/c++编程语言

日期：2020-10-04 11:06

COMP7104 – DASC7104 2019-2020 – Advance Database Systems

Homework 2 – Indexing and Relational Algebra

Note: the pictures are slightly simplified, they do no show any record pointer

for the leaf nodes.

For drawing B+ trees you could use tools such as the following:

https://www.cs.usfca.edu/~galles/visualization/BPlusTree.html

https://projects.calebevans.me/b-sketcher/

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)