Advancing 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) B) π SNAME (π SID (σ Color = Redparts) (σ COST <100Catalog C) π SNAME ((σ cost =redParts) (σcost<100Catalog)) ∩ (π SNAME ((σcolor=greenParts)) D) π SID ((σ COST <100Catalog) ∩ (π SID ((σ COST <100Catalog)) (σcost<100Catalog)) E) π SNAME (π SID, SNAME ((σcolor=redParts) (σcost<100Catalog)) ∩ (π SID, SNAME ((sigma color = greenParts) (sigma cost < 100 catalog) Suppliers))) WX: codehelp