I need help completing a java B+ tree assignment



Get Help With a similar task to - I need help completing a java B+ tree assignment

Login to view and/or buy answers.. or post an answer
Additional Instructions:

Assignment 3 COS 212 Department of Computer Science Deadline: 29 May 2020 at 23:00 Objectives: • Implement a B+-Tree. • Use the B+-Tree in a simplistic database table implementation. General instructions: • This assignment should be completed individually, no group effort is allowed. • Be ready to upload your assignment well before the deadline, as no extension will be granted. • You may not import any of Java’s built-in data structures. Doing so will result in a mark of zero. If you require additional data structures, you will have to implement them yourself. • If your code does not compile you will be awarded a mark of zero. Only the output of your program will be considered for marks, but your code may be inspected for the presence or absence of certain prescribed features. • All submissions will be checked for plagiarism. • Read the entire assignment before you start coding. • You will be afforded three upload opportunities. Plagiarism: The Department of Computer Science considers plagiarism as a serious offence. Disciplinary action will be taken against students who commit plagiarism. Plagiarism includes copying someone else’s work without consent, copying a friend’s work (even with consent) and copying material (such as text or program code) from the Internet. Copying will not be tolerated in this course. For a formal definition of plagiarism, the student is referred to http://www.library.up.ac.za/plagiarism/index.htm (from the main page of the University of Pretoria site, follow the Library quick link, and then choose the Plagiarism option under the Services menu). If you have any form of question regarding this, please ask one of the lecturers, to avoid any misunderstanding. Also note that the OOP principle of code re-use does not mean that you should copy and adapt code to suit your solution. 1 After completing this assignment: Upon successful completion of this assignment you will have implemented a B+-Tree. You will also have implemented your own simplistic database table that manipulates its data using your B+-Tree based database indexes. Task 1 Consider the STUDENT database table in Table 1. The first column is a unique internal identifier given by the database to each record in a table. This column is hidden from all general database activity. All other columns in this table represent user data that is visible. This particular table contains student information consisting of student number, name and surname. The student number has been designated a primary key index since it is unique at a university. To speed up searching for students by surname, another index has been created for the surname column. PrimKey SecKey RowID StudentID Name Surname 1 16230943 Lerato Molefe 2 17248830 Isabel Muller 3 16094340 John Botha 4 17012340 Michael Evans Table 1: A STUDENT database table Database indexes are generally implemented using B+-Trees. B+-Trees represent an efficient way to store indexes in memory and provide a fast and constant way to search for records stored on disk. The two indexes of Table 1 can be stored in two B+-Trees. The first tree would use the student numbers as keys, while the second one would use the surnames. In both trees, the row id would be the value that is stored in the leaf nodes. Your task is to implement a B+-Tree that can be used to store both the indexes that are defined in the STUDENT table in Table 1. Download the archive assignment3CodeTask1.zip. This provides a functional B+-Tree class and partially implemented B+-Tree node subclasses to use. You will have to complete the BPTreeNode class by implementing the insert, search, delete and values methods. The classes BPTreeInnerNode and BPTreeLeafNode inherit from the BPTreeNode parent class and will contain type specific functionality. You should use your own helper functions to assist in implementing the insert, search, delete and values methods as per the specification documented in the code. However, you may not modify any of the given members, methods or method signatures. You are also provided with the file Main.java, which will test some code functionality. It also provides an example of how the indexes of Table 1 could be defined and used. You are encouraged to write your own test code in this file. Test your code thoroughly using this file before submitting it for marking. Search Searching can be performed either sequentially via the linked leaf nodes or by tree traversal. The value associated with the given key should be returned. If the given key is not found, null should be returned. 2 Deletion Deletion will always take place at the leaf node level. A possible corresponding separator key in the parent internal node should not be removed during deletion. Only a future node merge can lead to the separator key removal. Underflow If a node underflows, first check if the left sibling has enough keys to share. If it doesn’t, check if the right sibling can share keys. If neither of the siblings have enough keys to share, then the underflowing node merges with its sibling (left sibling if possible, otherwise right sibling). Merging Merging of nodes will require the update of the separator keys in the parent internal node. Firstly, old separator keys will need to be removed. Secondly, a new separator key may need to be added for the newly merged node. Example You can use the B+-Tree visualiser (https://www.cs.usfca.edu/~galles/visualization/BPlusTree. html) to get a visual demonstration as to how the insertion and deletion strategies should work. Un- fortunately, the visualiser does not leave the separator key in an internal node once the key has been deleted from the leaf node. You should not follow this strategy in your implementation, but stick to the strategy used in the textbook. Task 2 Now consider a simplistic implementation of a database table that makes use of the B+-Tree imple- mentation created in task 1. A Table class stores its row data in an array of records. A Record class is used for that purpose and it stores an array of values and returns them as a string. Another array in the Table class stores the table columns that are used in the records. The Table class also stores an array of indexes that apply to specific record columns. An Index class is used for that purpose which contains the B+-Tree and some other information. Your task is to implement a database table that can be used to store both the data and indexes that are defined in the STUDENT table in Table 1. This database table should also support the manipulation of its data using its available indexes with the standard SQL methods select, insert and delete. Download the archive assignment3CodeTask2.zip. This provides a partially implemented Table class and functional helper classes to use. You will have to complete the Table class by implementing the SQL insert, search and delete methods, as well as the index create and print methods as per the specification documented in the code. To standardise output for marking purposes, an Error class has also been provided that contains standard messages that should be used as documented in the code. To compile the provided code, you need to add your completed files from task 1. You should use your own helper functions to assist in implementing the insert, search and delete SQL query methods as well as the index create and print methods. However, you may not modify any of the given members, methods or method signatures. You are also provided with the file Main.java, which will test some code functionality. It provides an example of how the data and indexes from Table 1 could be defined and used. You are encouraged to write your own test code in this file. Test your code thoroughly using this file before submitting it for marking. 3 Duplicates Since the B+-Tree search method only returns a single value, returning or removing multiple rows using the index is not possible without modification. Therefore, the select and delete methods only need to return or delete the first matching record found. Matching The select and delete methods only need to make provision for exact matches of the where clause. Special syntax that allows partial matches normally found in SQL does not need to be supported. Sizing The Table class constructor makes provision for an initial number of records and indexes. You may assume testing will stay within these limits and your insert() and createIndex() methods do not need to support increasing the initial array size when full. The B+-Trees used to store the index data should be of order 4. Submission instructions You need to create your own makefile and submit it along with your Java code. Your code should be compiled with the following command: javac *.java Your makefile should also include a run rule which will execute your code if typed on the command line as in make run. For your submission, you need to place all your source files including your makefile in a zip or tar/gzip archive (you need to compress your tar archive) named uXXXXXXXX.zip or uXXXXXXXX.tar.gz where XXXXXXXX is your student/staff number. There should be no folders/subfolders in your archive. Submit your code for marking under the appropriate links (Assignment 3: Task X ) before the deadline. Separate upload links are provided for the two tasks. Each link grants 3 uploads. Since every upload is a marking opportunity, do not use it to test your code. 4

/** * Class for a B+ tree * Since the structures and behaviours between internal nodes and leaf nodes are different, * there are different classes for each kind of node. However, both classes share attributes in * a common parent node class. * @param <TKey> the data type of the key * @param <TValue> the data type of the value */ public class BPTree<TKey extends Comparable<TKey>, TValue> { private BPTreeNode<TKey, TValue> root; private int debug; public BPTree(int order) { this.root = new BPTreeLeafNode<TKey, TValue>(order); this.debug = 0; } public String debug() { String res = ""; if (root != null) { res = res + debug; } return res; } /** * Print all keys of the B+ tree */ public void print() { if (root != null) { root.print(root); System.out.println(); } } /** * Insert a new key and its associated value into the B+ tree. */ public void insert(TKey key, TValue value) { if (root != null) { root = root.insert(key, value); } } /** * Search a key value on the B+ tree and return its associated value. */ public TValue search(TKey key) { if (root != null) { debug++; return root.search(key); } else return null; } /** * Delete a key and its associated value from the B+ tree. */ public void delete(TKey key) { if (root != null) { root = root.delete(key); } } /** * Return all associated key values on the B+ tree in ascending key order. */ public TValue[] values() { if (root != null) { return root.values(); } else { return null; } } }

/** * A B+ tree internal node * @param <TKey> the data type of the key * @param <TValue> the data type of the value */ class BPTreeInnerNode<TKey extends Comparable<TKey>, TValue> extends BPTreeNode<TKey, TValue> { protected Object[] references; public BPTreeInnerNode(int order) { this.m = order; // The strategy used here first inserts and then checks for overflow. // Thus an extra space is required i.e. m instead of m-1/m+1 instead of m. // You can change this if needed. this.keys = new Object[m]; this.references = new Object[m + 1]; } @SuppressWarnings("unchecked") public BPTreeNode<TKey, TValue> getChild(int index) { return (BPTreeNode<TKey, TValue>)this.references[index]; } public void setChild(int index, BPTreeNode<TKey, TValue> child) { this.references[index] = child; if (child != null) child.setParent(this); } @Override public boolean isLeaf() { return false; } ////// You should not change any code above this line ////// ////// Implement functions below this line ////// }

/** * A B+ tree leaf node * @param <TKey> the data type of the key * @param <TValue> the data type of the value */ class BPTreeLeafNode<TKey extends Comparable<TKey>, TValue> extends BPTreeNode<TKey, TValue> { protected Object[] values; public BPTreeLeafNode(int order) { this.m = order; // The strategy used here first inserts and then checks for overflow. // Thus an extra space is required i.e. m instead of m-1. // You can change this if needed. this.keys = new Object[m]; this.values = new Object[m]; } @SuppressWarnings("unchecked") public TValue getValue(int index) { return (TValue)this.values[index]; } public void setValue(int index, TValue value) { this.values[index] = value; } @Override public boolean isLeaf() { return true; } ////// You should not change any code above this line ////// ////// Implement functions below this line ////// }

/** * A B+ tree generic node * Abstract class with common methods and data. Each kind of node implements this class. * @param <TKey> the data type of the key * @param <TValue> the data type of the value */ abstract class BPTreeNode<TKey extends Comparable<TKey>, TValue> { protected Object[] keys; protected int keyTally; protected int m; protected BPTreeNode<TKey, TValue> parentNode; protected BPTreeNode<TKey, TValue> leftSibling; protected BPTreeNode<TKey, TValue> rightSibling; protected static int level = 0; protected BPTreeNode() { this.keyTally = 0; this.parentNode = null; this.leftSibling = null; this.rightSibling = null; } public int getKeyCount() { return this.keyTally; } @SuppressWarnings("unchecked") public TKey getKey(int index) { return (TKey)this.keys[index]; } public void setKey(int index, TKey key) { this.keys[index] = key; } public BPTreeNode<TKey, TValue> getParent() { return this.parentNode; } public void setParent(BPTreeNode<TKey, TValue> parent) { this.parentNode = parent; } public abstract boolean isLeaf(); /** * Print all nodes in a subtree rooted with this node */ @SuppressWarnings("unchecked") public void print(BPTreeNode<TKey, TValue> node) { level++; if (node != null) { System.out.print("Level " + level + " "); node.printKeys(); System.out.println(); // If this node is not a leaf, then // print all the subtrees rooted with this node. if (!node.isLeaf()) { BPTreeInnerNode inner = (BPTreeInnerNode<TKey, TValue>)node; for (int j = 0; j < (node.m); j++) { this.print((BPTreeNode<TKey, TValue>)inner.references[j]); } } } level--; } /** * Print all the keys in this node */ protected void printKeys() { System.out.print("["); for (int i = 0; i < this.getKeyCount(); i++) { System.out.print(" " + this.keys[i]); } System.out.print("]"); } ////// You may not change any code above this line ////// ////// Implement the functions below this line ////// /** * Search a key on the B+ tree and return its associated value. If the given key * is not found, null should be returned. */ public TValue search(TKey key) { // Your code goes here } /** * Insert a new key and its associated value into the B+ tree. The root node of the * changed tree should be returned. */ public BPTreeNode<TKey, TValue> insert(TKey key, TValue value) { // Your code goes here } /** * Delete a key and its associated value from the B+ tree. The root node of the * changed tree should be returned. */ public BPTreeNode<TKey, TValue> delete(TKey key) { // Your code goes here } /** * Return all associated key values on the B+ tree in ascending key order. An array * of the key values should be returned. */ @SuppressWarnings("unchecked") public TValue[] values() { // Your code goes here } }

/** * Class for a error messages * Contains common error messages. */ public class Error { public final static String Err1 = "No records found"; public final static String Err2 = "No indexes found"; public final static String Err3 = "No suitable index found"; public final static String Err4 = "Record(s) not found"; }

/** * Class for a table index * Stores and manipulates all values from a table column in a B+ tree. */ public class Index { private String name; private String column; private BPTree index; public Index(String name, String column, BPTree index) { this.name = name; this.column = column; this.index = index; } public String getName() { return name; } public void setName(String name) { this.name = name; } public String getColumnName() { return column; } public void setColumnName(String column) { this.column = column; } public BPTree getIndex() { return index; } public void setIndex(BPTree index) { this.index = index; } }

/** * Class for a table row * Stores and manipulates all values for a row in a record. */ public class Record { private Object[] columns; private int columnCount; public Record(int count) { this.columnCount = count; this.columns = new Object[columnCount]; } public Object getColumn(int idx) { return columns[idx-1]; } public void setColumn(int idx, Object obj) { columns[idx-1] = obj; } public String getValues() { if (columns[0] != null) { String result = columns[0].toString(); for (int i = 1; i < columnCount; i++) { result = result + "," + columns[i].toString(); } return result; } else return ""; } }

/** * A simplistic database table class. Uses the record class to store row data and the index class to * maintain indexes for specific columns. * Class also implements basic SQL methods. Uses the error class for common error messages. */ public class Table { private String name; private String[] columns; private Record[] records; private Index[] indexes; private int rowId; private int recordCount; private int indexCount; public Table(String name, String[] columns) { this.rowId = 1; //start index in records array this.recordCount = 0; this.indexCount = 0; this.name = name; this.columns = columns; this.records = new Record[1000]; //initial size of table this.indexes = new Index[10]; //initial number of indexes } public String getName() { return name; } public void setName(String name) { this.name = name; } public int getRecordCount() { return this.recordCount; } public int getIndexCount() { return this.indexCount; } public String debug() { String result = ""; if (indexCount > 0) { for (int i = 0; i < indexCount; i++) { Index idx = indexes[i]; result = result + idx.getIndex().debug(); if ((i+1) < indexCount) result = result + " "; } } else { result = "No Indexes!"; } return result; } ////// You may not change any code above this line ////// ////// Implement the functions below this line ////// /** * Insert the given "rec" in this table. Every record needs to have a unique row id, which is never reused. * Should indexes be present, they need to be updated. */ //SQL: insert into table values (rec) @SuppressWarnings("unchecked") public void insert(Record rec) { // Your code goes here } /** * Represents the full delete SQL query. Depending on given parameters, different subqueries are called. */ //SQL: delete from table where column equals value public void delete(String column, Object value) { if (column == null && value == null) { this.delete(); } else { this.deletep(column, value); } } /** * Delete all the records in this table where the given "column" matches "value". Needs to use the index * for "column" and call the search method of the used B+ tree. If no index exists for "column", conventional * record iteration and search should be used. Deleted rows remain empty and the records array should not be * compacted. recordCount however should be updated. Should indexes be present, they need to be updated. */ //SQL: delete from table where column equals value @SuppressWarnings("unchecked") private void deletep(String column, Object value) { // Your code goes here } /** * Delete all the records in this table. recordCount and row id should be updated. Should also * reset all indexes if present. */ //SQL: delete from table private void delete() { // Your code goes here } /** * Represents full select SQL query. Depending on given parameters, different subqueries are called. */ //SQL: select * from table where column equals value order by ocolumn public void select(String column, Object value, String ocolumn) { if (column == null && value == null) { if (ocolumn != null) this.select(ocolumn); else this.select(); } else { this.select(column, value); } System.out.println(); } /** * Print all the records in this table where the given "column" matches "value". Should call the getValues * method of the record class. Needs to use the index for "column" and call the search method of the used * B+ tree. If no index exists for "column", conventional record iteration and search should be used. * If the table is empty, print error message 1. If no record matches, print error message 4. */ //SQL: select * from table where column equals value @SuppressWarnings("unchecked") private void select(String column, Object value) { // Your code goes here } /** * Print all the records in this table ordered by the given "ocolumn" in ascending order. Should call * the getValues method of the record class. Needs to use the index for ocolumn and call the values * method of the used B+ tree. If the table is empty, print error message 1. If no indexes are * present, print error message 2. If there is no index available for "ocolumn", print error message 3. */ //SQL: select * from table order by ocolumn private void select(String ocolumn) { // Your code goes here } /** * Print all the records in this table. Should call the getValues method of the record class. If * the table is empty print error message 1. */ //SQL: select * from table private void select() { // Your code goes here } /** * Create an index called "name" using the record values from "column" as keys and the row id as value. * The created B+ tree must match the data type of "column". Return true if successful and false if * column does not exist. */ public boolean createIndex(String name, String column) { // Your code goes here } /** * Print all the keys in the index "name". Should call the print method of the used B+ tree. */ public void printIndex(String name) { // Your code goes here } //Helper methods }

Related Questions

Similar orders to I need help completing a java B+ tree assignment
7
Views
0
Answers
Nested imbalanced design of expriment using Box-Adjusted wald-type test
I need to provide statistical analysis of a nested design non-balanced design of experiment. I am hoping to have the implementation in either R, SPSS, or both. I will need the answers to be provided as shown in the attached file (Project.docx), and also wo...
28
Views
0
Answers
CMPT 200 Coding Homework
Write a class called Fraction that can store a rational number (reminder: those numbers that can be expressed in the form a/b, where a and b are integers are rational numbers). For example, a variable with a value of ½ would be created using oneHalf ...
14
Views
0
Answers
Artificial Inteligence System Technique
This is a Master Degree course and I have attached example questions, there are 5 questions and only 3 need to be answered. We will get the actual questions on the day of the exam and they need to be completed within 2 hours, which means the expert has to ...
18
Views
0
Answers
Simulating Networks
Here are the details of first assignment for Computer Networks class. This is a pretty basic assignment with very little work but you will have to do initial setup for virtual box on your machine. Here are the details on how to do the setup: Download virt...