CSL771: Database Implementations



This is the course page for CSL771: Database Implementations, for Semester I, 2011-2012, being taught by S. K. Gupta (skg AT cse.iitd.ac.in) at the Department of Computer Science and Engineering, IIT Delhi.

Updates | Assignments | Prerequisites | Grading Policy | Reference Books

Class timings

  • Tuesday, 11:00-12:00
  • Thursday, 11:00-12:00
  • Friday, 11:00-12:00

Teaching Assistants

Updates

  • Slides covered by Dr. Maya Ramanath : Download Here
  • Assignment IV statement is up!
  • Assignment III statement is up!
  • Assignment II statement is up!
  • You have to show your assignments working on GCL machines.
  • Submissions will be done via Moodle. Make sure you are enrolled for CSL771.
  • Assignment I statement is up!
  • All mails to the course instructor MUST have CSL771 as the subject.

Programming Assignments

Assignment 4 
 Groups of Two! 
For the problem statement, refer to the following PDF.


Assignment 3 
For the problem statement, refer to the following PDF and LaTeX files.


Assignment 2 

Implement and perform time analysis on the following variants of join algorithms:
1. Tuple-based
2. Block-based
3. Sort-based
4. Index-based 


This assignment is an extension to the in-class discussion on join algorithms. Note that many research papers are available for these algorithms. Students are advised to do a comprehensive survey of these, and mention them concisely in a report which carries substantial weightage.

For index-based join, demonstrate using the btree implemented in the previous assignment.
Compare the performance of different implementations with different sizes of data sets and Show results using comparative graphs for each dataset.
Typical sizes of relation data set (10^2, 10^3, 10^4, 10^5)

Also submit a document containing the explanation of algorithm employed in the above four cases, and explaining the resulting graphs obtained.

Submission Checklist
* Code performing Time Analysis
* Comparative Analysis Graphs
* Report surveying the available algorithms, and explaining your choice
Assignment 1 

Remarks
   1. Download sample.csv here
   2. Submission Deadline: August 17,2011 11:59PM	
   3. You are free to choose between C/C++/Java
   4. The assignment can be done in groups of TWO.
   5. Many useful animated illustrations and code-snippets are available on the web.You are free to consult them.
   6. Your code must be entirely your own. Submission must contain a statement of originality stating all your references.


Implement a B-Tree supporting operations on student records having the following format:

Records - (Name,Entry,Phone,CGPA)
	Name - Alphabet String
	Entry - YYYYDDXXX (Y represents the year and DD is code for the department)
	Phone - Integer String
	CGPA - F.FF (Floating Point String)

Routines Supported
A.  Insert sample.csv - Insert Bulk Records into the B-Tree
B.  Delete DD - DD is alphabet code for the department
C.  Update sample.csv - sample file containing updated records
D.  FindTopper YYYY - Return Student with Highest CGPA for an year
E.  Dump - It must create a csv in the same format with an ordered list of elements

Choose a suitable ordering criteria for the records which enables speedup!

Bonus Points - Depict the top levels in the B-Tree visually.

Sample Input 
	Order of the B-Tree(k) - integer
	sample.csv - input file containing records


Submission Checklist
    Along with the code,
    	* 1-page Documentation mentioning all functions in your code
    	* A write-up explaining your implementation of the above routines
    	* Statement of Originality

Prerequisites

Students interested in registering for the course must have completed a basic course in Database Systems.

Grading Policy (Tentative)

Minor I - 15%; Minor II - 20%; Major - 35%; Programming assignments - 20%; Surprise Quizzes - 10%

Reference Books

  • Database Systems: The Complete Book, by Hector Garcia-Molina, Jeff Ullman, and Jennifer Widom
  • File Organization for Database Design, Gio Wiederhold