COMP7104代写、Database Systems代做、Python/c++编程设计调试、代写Java

日期：2019-04-14 09:33

COMP7104 – DASC7104 2018-2019 – Advance Database Systems

Homework 2 – Indexing and Relational Algebra

Indices (B+ Trees)

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 maximum number of insertions we can perform without changing the height of this

tree? Illustrate it by giving such an insertion pattern.

b) What is the minimum number of keys we can insert in order to trigger a change in the height

of this tree? Illustrate it by giving such an insertion pattern.

2. Suppose we have an Alternative 2 unclustered index on the attribute pair (assignment_id,

student_id) with a depth of 3 (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 on disk and that page size is 64 KB.

(This includes extra space allocated for future insertions; pages are 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) We want to scan all the records in Submissions. How many I/Os will this operation take ?

b) The following instruction is executed:

UPDATE Students

SET grade_received=85

WHERE assignment_id=20 AND student_id=12345;

How many I/Os will this operation take?

c) 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 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 tree, assuming

that the right sibling is checked for possible redistribution.

e) Show the index resulting from starting with the original tree, 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 tree.

4. Relational Algebra. Consider the following schema:

Suppliers(sid: integer , sname: string , address: string )

Parts(pid: integer , pname: string , color: string )

Catalog(sid: integer , pid: integer , cost: real )

The key fields are underlined, and the domain of each field is listed after the field name. Therefore

sid is the key for Suppliers, pid is the key for Parts, and sid and pid together form the key for

Catalog. The Catalog relation lists the prices charged for parts by Suppliers.

Describe in plain English (without using words such as join, project, select, etc) what the

following RA queries compute:

a) πsname (πsid ((σcolor=redParts) (σcost<100Catalog ))Suppliers)

b) πsname (πsid ((σcolor=redParts) (σcost<100Catalog )Suppliers))

c) (πsname ((σcolor=redParts) (σcost<100Catalog )Suppliers)) ∩

(πsname ((σcolor=greenParts) (σcost<100Catalog )Suppliers))

d) (πsid((σcolor=redParts) (σcost<100Catalog)Suppliers)) ∩

(πsid((σcolor=greenParts) (σcost<100Catalog)Suppliers))

e) πsname ((πsid,sname ((σcolor=redParts) (σcost<100Catalog )Suppliers )) ∩

(πsid,sname ((σcolor=greenParts)(σcost<100Catalog)Suppliers)))