COMP7104 – DASC7104 2018-2019 – Advance Database Systems
Homework 2 – Indexing and Relational Algebra
Indices (B+ Trees)
- 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. - 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? - 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. - 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)))
WX：codehelp