Database Management System Implementation
Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: THEend8_
CSE 510 - Database Management System Implementation
Phase II
1 Goal
The version of the MiniBase I have distributed to you implements various modules of a relational database management
system. Our goal this semester is to use these modules of MiniBase as building blocks for implementing a Bigtable-like
DBMS.
Please consider the following papers as a starting point of your reading in the area:
Fay Chang, Jeffrey Dean, Sanjay Ghemawat, Wilson C. Hsieh, Deborah
A. Wallach, Mike Burrows, Tushar Chandra, Andrew Fikes, Robert
E. Gruber. Bigtable: A Distributed Storage System for Structured
Data.7th USENIX Symposium on Operating Systems Design and
Implementation (OSDI), {USENIX} (2006), pp. 205-218.
2 Project Description
The following is the list of tasks that you need to perform for this phase of the project. Note that getting these working
may involve other changes to various modules not described below.
• Create a new package called BigT, with three classes
– BigT.bigt, which creates and maintains all the relevant heapfiles (and index files of your choice to organize
the data),
– BigT.Map Minibase stores data in the form of tuples. Bigtable on the other hand stores data in the form of
maps
(row : string, column : string, time : int)→ string.
Therefore, the first task to extendMinibase with a new map construct. The map construct will be similar to the
tuple, but with a fixed structure; a tuple can have any arbitrary length (as long as it is bounded by max size)
and any arbitrary fields, but a map will have 4 fixed fields:
∗ RowLabel:attrString
∗ ColumnLabel:attrString
∗ TimeStamp:attrInteger
∗ Value:attrString
1
Spring 2023
Due Date: Midnight, March 19th
– BigT.Stream This supports the getNext() interface which will retrieve maps from the big table in some
specified order.
These classes will provide the following constructors and methods:
– BigT.bigt:
∗ bigt(java.lang.String name, int type): Initialize the big table. type is an integer be-
tween 1 and 5 and the different types will correspond to different clustering and indexing strategies you
will use for the bigtable.
∗ void deleteBigt(): Delete the bigtable from the database.
∗ int getMapCnt(): Return number of maps in the bigtable.
∗ int getRowCnt(): Return number of distinct row labels in the bigtable.
∗ int getColumnCnt(): Return number of distinct column labels in the bigtable.
∗ MID insertMap(byte[] mapPtr) Insert map into the big table, return its Mid. The
insertMap() method ensures that there are at most three maps with the same row and column la-
bels, but different timestamps, in the bigtable. When a fourth is inserted, the one with the oldest label is
dropped from the big table.
∗ Stream openStream(int orderType, java.lang.String rowFilter,
java.lang.String columnFilter, java.lang.String valueFilter): Initialize a
stream of maps where row label matching rowFilter, column label matching columnFilter, and
value label matching valueFilter. If any of the filter are null strings, then that filter is not considered
(e.g., if rowFilter is null, then all row labels are OK). If orderType is
· 1, then results are first ordered in row label, then column label, then time stamp
· 2, then results are first ordered in column label, then row label, then time stamp
· 3, then results are first ordered in row label, then time stamp
· 4, then results are first ordered in column label, then time stamp
· 6, then results are ordered in time stamp
– BigT.Map: You will need to create a class BigT.Map, similar to heap.Tuple but having a fixed structure
(and thus a fixed header) as described above. Thus, the constructor and get/set methods associated with the
BigT.Map should be adapted as appropriate:
∗ Map(): Class constructor create a new map with the appropriate size.
∗ Map(byte[] amap, int offset): Construct a map from a byte array.
∗ Map(Map fromMap): Construct a map from another map through copy.
∗ java.lang.String getRowLabel(): Returns the row label.
∗ java.lang.String getColumnLabel(): Returns the column label.
∗ int getTimeStamp(): Returns the timestamp.
∗ java.lang.String getValue(): Returns the value.
∗ Map setRowLabel(java.lang.String val): Set the row label.