Lab 5: Heap File

  • Course: COSC 460 Databases Fall 2018
  • Instructor: Michael Hay
  • Assignment: Lab 5: Heap File
  • Due: Thu, Oct 11 at 11:59 PM
  • Starter code: lab5.zip

Introduction

In this lab, you are asked to implement a Heap File.

Environment setup

See previous labs.

Saving and accessing your files

See previous labs.

Assignment overview

Before starting this lab, you are strongly encouraged to review your notes from class and re-read the textbook (Cow book, especially Ch. 9.5).

One of the things that makes this lab interesting is that we are now starting to bring the pieces together into a functioning database. For example, your HeapFile implementation will sit on top of your BufferManager and it will read and write data onto SlottedPage objects. Those pages are transferred to/from disk using a DiskManager implementation that I provide. In addition, this lab introduces some new components, such as the Catalog, which maintains information about the tables stored in the database. By bringing different units of code together, one of the learning goals for this lab is that you further develop your conceptual understanding of database architecture.

This lab is challenging in ways that are different from earlier labs. First, you may need to spend more time exploring the code before you dive in and implement. Second, often what happens when you bring code together is that bugs surface in existing code, despite the fact that this code may have passed some earlier tests. Thus, if your HeapFile crashes on some test, do not assume the error is in HeapFile. The source of the bug may in fact be in your SlottedPage implementation, for instance.

Note: In the javadocs and various places, you may notice comments about acquiring locks. You will also see references to TransactionId objects. For now, you can simply ignore these comments and references. Later in the semester you will revise your HeapFile implementation so that it supports multiple users making concurrent database modifications.

Starter code

You are expected to modify these files:

  • HeapFile.java

You are expected to read, use, but not modify the remaining files.

Tasks

To implement HeapFile you have to support three basic operations:

  • Adding tuples: The insertTuple method in HeapFile is responsible for adding a tuple to a heap file. To add a new tuple to a HeapFile, you will have to find a page with an empty slot. If no such pages exist in the HeapFile, you need to allocate a new page.
  • Removing tuples: To remove a tuple, you will need to implement deleteTuple in HeapFile. This is as simple as locating the page on which the tuple resides and calling the delete method you implemented on SlottedPage. Remember that a tuple contains a RecordID which allows you to find the page on which it resides. (Make sure your SlottedPage implementation sets the RecordId to null upon deletion.)
  • Iteration over tuples: You will also need to implement the iterator() method, which should iterate through through the tuples of each page in the HeapFile. Your iterator must be (space and time) efficient! In particular, your implementation should consume a minimal amount of memory beyond what the Buffer Manager has allocated. A rough guideline: your HeapFile may have roughly 1 page worth of data in memory but not much more than that. An implementation that loads the entire table’s worth of data into memory will not receive any credit.

VERY IMPORTANT: Your HeapFile implementation must obtain data by calling the BufferManager. It should never interact directly with the DiskManager. Also, since some BufferManager methods return generic Page objects, you will need to cast them to SlottedPage objects in HeapFile.

  • Task 1 Answer the questions on the worksheet that will be provided in lab. You should be able to complete this during the 2 hour lab.
  • Task 2 Implement the various get methods in HeapFile. You should be able to pass the associated tests.
  • Task 3 Implement insertTuple. You may want to write a “helper” method that finds (or creates!) a page into which you can insert a record.
  • Task 4 Implement deleteTuple. This method should be much simpler than insertTuple.
  • Task 5 Implement the heap file iterator.

Milestone

The milestone for this lab will be to complete the above tasks and pass the tests described above.

Code Review

Please submit your work for labs 3, 4, and 5 for code review. There is a separate assignment in Gradescope called lab345codereview. Upload these four files:

  • SlottedPage.java
  • SlottedPageFormatter.java
  • BufferManagerImpl.java
  • HeapFile.java

Submission instructions

Upload your files to Gradescope.