1. Homepage
  2. Programming
  3. CS660 Graduate Introduction to Database Systems - Programming Assignment 1: Heapfiles / Catalog / Tuple descriptor

CS660 Graduate Introduction to Database Systems - Programming Assignment 1: Heapfiles / Catalog / Tuple descriptor

Engage in a Conversation
BUCS660Introduction to Database SystemsHeapfilesCatalogTuple descriptorC++

Programming Assignment 1

In this assignment, we will implement implement a file that can store and retrieve tuples from disk. Each page of the file will store some metadata (header) and the data (tuples). Each Tuple is a collection of fixed length fields (i.e. INT, DOUBLE, CHAR(64)). CourseNana.COM

TupleDesc

The TupleDesc class represents the schema of a tuple. The schema of a tuple is a list of field types and names. CourseNana.COM

TupleDesc::TupleDesc

The constructor for TupleDesc creates a new schema with the given field types and names. It is up to you to decide what other computations you want to do here. CourseNana.COM

TupleDesc::compatible

This method checks if a tuple is compatible with the schema (i.e. all fields have the expected type). CourseNana.COM

TupleDesc::offset_of

This method returns the offset of a field in a tuple. CourseNana.COM

TupleDesc::index_of

This method returns the index of a field in a tuple. CourseNana.COM

TupleDesc::length

This method returns the length of a tuple (total number of bytes). CourseNana.COM

TupleDesc::size

This method returns the number of fields in a tuple. CourseNana.COM

TupleDesc::deserialize

This method deserializes a tuple from a byte array (read the contents of a byte array to create a Tuple object). CourseNana.COM

TupleDesc::serialize

This method serializes a tuple to a byte array (write the contents of a Tuple object to a byte array). CourseNana.COM

TupleDesc::merge

This method merges two TupleDesc. This will be useful later when we will need to join two tables. The fields of the new TupleDesc will be the fields of the first TupleDesc followed by the fields of the second TupleDesc. CourseNana.COM

DbFile

This is the base class for all database files. It provides the basic functionality for reading and writing pages to and from disk. CourseNana.COM

DbFile::DbFile

The constructor for DbFile opens the file with the given file name. If the file does not exist, it is created a new file with the given file name. The constructor counts the number of pages in the file and stores the number of pages in the numPages field. A file should always have one page when it is created (even if it is empty). CourseNana.COM

DbFile::~DbFile

The destructor for DbFile closes the file. CourseNana.COM

DbFile::readPage

The readPage method reads the page with the given page number from the file. CourseNana.COM

DbFile::writePage

The writePage method writes the page with the given page number to the file. CourseNana.COM

HeapFile

A HeapFile stores tuples in no particular order. The file is divided into pages and each page stores a fixed number of tuples along with a header that indicates which tuples are populated. CourseNana.COM

HeapFile::insertTuple

The insertTuple method inserts a tuple into the last page of the file. If there is no space in the last page, a new page is created. CourseNana.COM

HeapFile::deleteTuple

The deleteTuple method deletes the tuple point to by the provided iterator by marking the tuple as deleted in the header of the page. The tuple does not have to be overwritten but it is good practice to erase its data (remember that the whole page will be written to disk so the overhead of erasing the tuple's data is minimal). CourseNana.COM

HeapFile::getTuple

The getTuple method returns a tuple that corresponds to the provided iterator. The tuple is deserialized from the page. CourseNana.COM

HeapFile::next

The next method advances the iterator to the next populated tuple. This tuple may be in a subsequent page. If there are no more tuples, the iterator is set to the end of the file. CourseNana.COM

HeapFile::begin

The begin method returns an iterator to the first populated tuple in the file. This might not be in the first page of the file. CourseNana.COM

HeapFile::end

The end method returns an iterator to the end of the file. CourseNana.COM

HeapPage

The HeapPage class represents a page in a HeapFile. It is a wrapper of the Page type, meaning that it does not store any data itself, but it provides an interface to read and write to and from the page. Specifically, it provides access to the header the data and the capacity of the page. CourseNana.COM

HeapPage::HeapPage

The constructor for HeapPage initializes the capacity of the page and points the header and data to the correct offsets in the page buffer. CourseNana.COM

Given a page of $P$ bytes and tuples of length $T$ bytes a heap page can store $C$ tuples. For each tuple we will need one extra bit to indicate whether tuple is used. CourseNana.COM

$C = \lfloor \frac{P 8}{T 8 + 1} \rfloor$ CourseNana.COM

Let's have a look at an example: a page of $4096$ bytes ($4096 8$ bits) can store $31$ tuples of $132$ bytes ($132 8 + 1$ header bit). Which means that $4$ bytes will be left unused ($4096 - 31 * 132 = 4$). CourseNana.COM

The header bits will be grouped together in the first bytes of the page, followed by any unused bytes (padding). CourseNana.COM

The data will be stored in the remaining bytes of the page. CourseNana.COM

To summarize: CourseNana.COM

  • The header points to the beginning of the page (zero offset in the page buffer).
  • The header is followed by any unused bytes (padding).
  • The data begin after the padding (at offset $P - T * C$).

HeapPage::begin

The begin method returns the index to the first populated tuple in the page. This might not be in the first slot of the page. If there are no populated tuples, return an index which indicates the end of the page. CourseNana.COM

HeapPage::end

The end method returns the index to the end of the page (capacity). CourseNana.COM

HeapPage::insertTuple

The insertTuple method inserts a tuple into the first available slot of the page. CourseNana.COM

HeapPage::deleteTuple

The deleteTuple method deletes the tuple pointed to by the provided index by marking the tuple as deleted in the header of the page. CourseNana.COM

HeapPage::getTuple

The getTuple method returns a tuple that corresponds to the provided index. CourseNana.COM

HeapPage::next

The next method advances the index to the next populated tuple. If there are no more tuples, the index is set to the end of the page. CourseNana.COM

HeapPage::empty

The empty method checks if the page is empty (i.e. no populated tuples). CourseNana.COM

Questions

  1. Deleting tuples from a HeapFile might lead to having empty pages. How can we avoid having empty pages in a file? What is the cost of the solution you propose? CourseNana.COM

  2. In this assignment we have fixed size fields. How can we support variable size fields (e.g. VARCHAR)? CourseNana.COM

Grading

  • 60% of your grade will be based on whether your code passes the tests when we run it. These tests will be a superset of the tests we have provided. Before handing in your code, you should make sure your code produces no errors. CourseNana.COM

  • For testing, we will use ctest with our version of the tests. This means you cannot change the format of binary files. You should also not change our API. You should test that your code compiles the unmodified tests. Try to add code only where we have indicated. CourseNana.COM

  • 30% of your grade will be based on your answer to the technical questions posted above. You must follow instructions posted above to submit your answers. CourseNana.COM

  • 10% of your grade will be based on the quality of your writeup and our subjective evaluation of your code. CourseNana.COM

We hope you enjoy hacking on this assignment! CourseNana.COM

Get in Touch with Our Experts

WeChat (微信) WeChat (微信)
Whatsapp WhatsApp
BU代写,CS660代写,Introduction to Database Systems代写,Heapfiles代写,Catalog代写,Tuple descriptor代写,C++代写,BU代编,CS660代编,Introduction to Database Systems代编,Heapfiles代编,Catalog代编,Tuple descriptor代编,C++代编,BU代考,CS660代考,Introduction to Database Systems代考,Heapfiles代考,Catalog代考,Tuple descriptor代考,C++代考,BUhelp,CS660help,Introduction to Database Systemshelp,Heapfileshelp,Cataloghelp,Tuple descriptorhelp,C++help,BU作业代写,CS660作业代写,Introduction to Database Systems作业代写,Heapfiles作业代写,Catalog作业代写,Tuple descriptor作业代写,C++作业代写,BU编程代写,CS660编程代写,Introduction to Database Systems编程代写,Heapfiles编程代写,Catalog编程代写,Tuple descriptor编程代写,C++编程代写,BUprogramming help,CS660programming help,Introduction to Database Systemsprogramming help,Heapfilesprogramming help,Catalogprogramming help,Tuple descriptorprogramming help,C++programming help,BUassignment help,CS660assignment help,Introduction to Database Systemsassignment help,Heapfilesassignment help,Catalogassignment help,Tuple descriptorassignment help,C++assignment help,BUsolution,CS660solution,Introduction to Database Systemssolution,Heapfilessolution,Catalogsolution,Tuple descriptorsolution,C++solution,