CSI 508. Database Systems – Fall 2020
Programming Assignment I
In this part, you need to implement the following methods (your code needs to pass all of the
5 tests in SlottedPageTest):
• add(Object o): adds the specified object o in a SlottedPage when this method is invoked
on that SlottedPage. This method must first save the object o in the free space of the
SlottedPage by calling the save(Object o) method. This save(Object o) method returns
an int value indicating the location at which the object o is saved in the SlottedPage. That
int value must be stored at the right header entry of the SlottedPage so that the saved
object o can be accessed in the future. For example, assume that object “123” is saved at
location 2038 in the byte array of an empty SlottedPage. Then, the first 4 bytes of the
byte array (i.e., the beginning of the header) must store an int value 1 to indicate that there
is only one entry in the header (in response to the addition of object “123”). The next 4
bytes of the byte array (i.e., the 0th entry in the header) must store 2038 (i.e., the location
at which “123” is saved). When an additional object “456” is saved at location 2028 in the
byte array, the first 4 bytes of the header must store 2 (to indicate that there are two entries
in the header) and the 1st entry (i.e., the entry after the 0th entry) in the header must store
2028 (i.e., the location at which “456” is saved). To find the number of entries that the
SlottedPage currently has, use the entryCount() method. To set the number of entries in
the header to an int value, use the setEntryCount(int count) method. To save location l
at the ith entry in the header, call saveLocation(i, l).
• get(int index): returns the object at the specified index in a SlottedPage when this
method is invoked on that SlottedPage. For example, get(0) returns the object at index 0
(i.e., the object whose location is stored at the 0th entry in the header) and get(1) returns the
object at index 1. This method must first find the location of the object at the specified index
by calling the getLocation(int index) method. This getLocation(int index) method
returns the int value stored at the header entry specified by index (i.e., the index-th header
entry). If that location is -1, meaning that the object was removed from the SlottedPage,
the get(int index) method needs to return null. Otherwise, get(int index) needs to
obtain the object by calling the toObject(byte b, int offset) method (with offset
set to the return value of getLocation(int index)) and then return that obtained object.
If the given index cannot match any of the entries in the SlottedPage (e.g., get(-1)), the
method needs to throw an IndexOutOfBoundsException.
• remove(int index): removes the object at the specified index from a SlottedPage when this
method is invoked on that SlottedPage. This method must save -1 at the appropriate entry
in the header. This method must also return the object removed (i.e., the object previously
stored at the specified index). This method must NOT change the first 4 bytes in the header
of the SlottedPage. These 4 bytes represent the number of entries in the header (including
those containing -1 indicating object removal), not the number of objects remaining in the
• iterator(): returns an iterator over the objects (excluding those removed) stored in a
SlottedPage when this method is invoked on that SlottedPage. To find the number of
entries in the current SlottedPage, use entryCount(). To get the object at each index, call
get(int index). Note that get(int index) returns null if there is currently no object at
the specified index due to the deletion of the previous object. Feel free to add an auxiliary
class or data structure for this iterator() method.
• compact(): reorganizes the SlottedPage on which the method is invoked (in order to maximize the free space of that SlottedPage). This method is used by the save(Object o)
method when the object to save cannot fit into the current free space of the SlottedPage.
This method needs to move objects at the end of the SlottedPage in a manner that eliminates
the space previously wasted by the objects removed from the SlottedPage.
Please make sure that your code passes all of the tests in SlottedPageTest.
Part 2. The Basic Storage Manager Implementation (40 points)
In this part, you need to implement, in FileManager.java, a basic storage manager that
maintains a series of data objects in each data file without buffering (i.e., by directly reading/writing
SlottedPages from/to data files). The methods to complete are as follows (your code needs to
pass all of the 4 tests in FileManagerTest):
• put(int fileID, Long location, Object o): puts object o at location location in the
file specified by fileID. Here, location has a long-type value, whose first half (4 bytes
corresponding to an integer) represents the ID of the page (e.g., page 0, page 1, etc.) and
the second half represents the index within the page. For example, put(10, 0x00000001L,
o) stores object o in page 0 of the file whose ID is 10 (i.e., the first disk block in the file)
at index 1 within the page. On the other hand, put(10, 0x00010000L, o) stores object o
in page 1 of the file whose ID is 10 (i.e., the second disk block in the file) at index 0 within
the page. Given a long-type argument location, use first(location) to get the ID of the
page and second(location) to get the index within the page. After finding an appropriate
page p, call put(int index, Object o) on p to put the object in that page and then call
the updated(p, fileID) method of FileManager to indicate that the page p is updated
(then the updated(p, fileID) method of FileManager automatically writes the page to
the appropriate data file). If the location argument has an inappropriate value (e.g., its first
half refers to page -1), then put(int fileID, Long location, Object o) needs to throw
• get(int fileID, Long location): returns the object at location location in the file specified by fileID.
• remove(int fileID, Long location): removes the object at location location from the
file specified by fileID.
• iterator(int fileID): returns an iterator over all objects stored in the the file specified
by fileID. This method needs to use page(int fileID, int pageID) of FileManager and
iterator() of SlottedPage. Make sure this method efficiently uses the memory (e.g., does
NOT put all of the objects in the memory first thereby incurring high space overhead and
then return an iterator over these objects).
Please verify your code using the tests in FileManagerTest.
Part 3. Buffer Management (10 points)
The FileManager class implemented in Part 2 directly accesses data files (i.e., no buffering),
causing disk seeks frequently. In this part, you need to implement the BufferedFileManager class
so that it extends the functionalities of FileManager in a manner that benefits from buffering
(i.e., frequently used pages are kept in memory, thereby enabling fast read and write operations).
Furthermore, you need to implement a page eviction policy for the cases where there are too many
pages to keep in the main memory. The choice of eviction policy is up to you. It is not necessary
to do something sophisticated. Describe your policy in the document that you submit.
When BufferedFileManager is implemented correctly, BufferedFileManagerTest will produce some output as follows (the exact number of reads and writes may vary depending on the
buffering strategy; however, there should in general be less reads and writes as the buffer size
本网站支持淘宝 支付宝 微信支付 paypal等等交易。如果不放心可以用淘宝交易！
E-mail: [email protected] 微信:itcsdx