CSCI6370 Database Management Fall 2008
Project 2:Perfomance Evaluation for Selection Algorithms
Due:October 07 2008
In the first project we implemented a Table which used a List to store the table data.In the second project we will extend the Table to improve the query execution time. You will do this by using an efficient way of looking up tuples on basis of primary keys.Build index using primary key only.You can assume that the primary key has only one attribute.It is not necessary to build indices on secondary keys.
How to improve query execution
Data structures like B+ trees, Linear Hash tables,Double hash tables optimize the search process.You can use either B+ Tree, B-Tree, Linear Hashing or Extendible Hashing.You will build one such data structure for your Table class.The select and insert operators will be supported. Your data structure would be implemented as a class that either implements the java.util.Map interface or java.util.AbstractMap interface.
public class MyMap extends AbstractMap implements Map, Cloneable, Serializable
{
//your implementation goes here
}
Methods like get(key),put(key,attrValues) can be used to look up for keys to avoid inserting duplicates, faster retrieval of tuples, etc.
The select and insert operators will be supported.They might need some modification so as to support the new data structure.
Note that you should implement the data structure on your own and using HashMap available in Java would not account for Linear Hashing/Extendible Hashing.
Perfomance Evaluation
Collect timing data (in milliseconds using System.currentTimeInMillis() vs. the number of tuples). Please do your performance test and analysis using "point queries" of selection, for the following
1. Point Queries using Primary Key 2. Point Queries on non-key attributes.
The point queries on primary key should be faster than those on non key attributes.
Plot your results in an excel sheet in the following pattern
| # of tuples | Point queries on primary key | Point query on non-key attributes |
| 500 | 0.1 | 0.5 |
| 1000 | 0.2 | 1.1 |
| 2000 | 0.71 | 1.4 |
| 3000 | 1.23 | 3.0 |
| 4000 | 3.1 | 5.2 |
Resources
TupleGenerator.java
TupleGenerator.groovy
Programming language
Java or Groovy is required for the project.
What to submit
Please submit the source code,readme file,excel sheet containing timing results.
The readme file should contain: your names, how to compile and run your code and
other specifications you want to make.
Please pack all your files in a zip package with the file
name: "project2" + last names of group members.
For example: project2_Shastri_Parate_McKnight.zip
How to submit
Mail your ".zip" file to the address csci6370fall08@gmail.com
Put "Project 2 submission" as the subject.