Universitatea Babeş-Bolyai Cluj-Napoca
Facultatea de Matematică şi Informatică
Ciclul de studii: Masterat
Domeniul: Informatica
Programul de studii: Baze de date
Limba de predare: Engleză

SYLLABUS

I. General data
Code	Subject	
MIH1003	Implementation of Database Management Systems	

Semester	Hours: C+S+L	Category	Status	
2	2+0+2	speciality	compulsory	

II. Full status faculty members
Name and	Scientific	Didactic	Chair	Type of activity	
surname	title	title		C	S	L	
VARGA Viorica	Ph.D.	Assoc.Prof.	Computer Systems	*			

Associated faculty members
Name and	Scientific	Institution	Type of	Type of activity	
surname	title		position	C	S	L	

III. Course objectives
The course objective is the presentation of data storage in databases, buffer management, index techniques, query processing and the overview of query optimization in relational databases.
The students will be able to understand query processing in relational databases and to implement a simple Database Management System (DBMS).	

IV. Course contents
1. The structure of physical database, file organizations, the structure of the database catalog.
2.	Index techniques (ISAM, hash, tree indexes, etc.). 
3.	The implementation of the SQL commands.
4.	Algorithms for the implementation of relational algebra operations: selection, projection, join (nested loop, indexed nested loop, merge join), etc.
5.	The phases of query processing.
6.	The cost model for query processing evaluation, DBMS's statistics.
7.	Overview of query optimization. 
8.	Physical database design.
9.	Query processing and optimization in MS SQL Server.
10.	Query processing and optimization in Oracle.	

V. Bibliography
C. J. Date: An Introduction to Database Systems, 8th Edition, Addison-Wesley Higher Education, 2004.
S. Chaudhuri: An Overview of Query Optimization in Relational Systems, 1998 
H. Garcia-Molina, J. D. Ullman, J. Widom: Database System Implementation, Prentice Hall Upper Saddle River, New Jersey, 2000.
G. Graefe: Query Evaluation Techniques for Large Databases, ACM Computing Surveys, 25(2), 1993.
Y. Ioannidis: Query Optimization, ACM Computing Surveys, 1996
H.T. Ozsu, P. Valduriez, Principles of Distributed Database Systems, Prentice Hall, 1991.
R. RAMAKRISHNAN, J. GERKHE: Database Management Systems, McGraw-Hill Higher Education; 3 edition (2002).
A. Silberschatz, H. Korth, S. Sudarshan: Database System Concepts, McGraw-Hill, New York, 2006.
P. Selinger et al: Access Path Selection in a Relational Database Management System, ACM SIGMOD 1979, 23-34. 
J. D. Ullman, J. Widom: A First Course in Database Systems, Prentice Hall Upper Saddle River, New Jersey, 1997.
V. Varga, Interogarea bazelor de date distribuite, Casa Cărţii de Ştiinţă, Cluj-Napoca, 
2006. 	

VI. Thematic of didactic activities per weeks
Course 1. The structure of the physical database
-	The structure of the magnetic disc  
-	Optimization of Disk-Block Access
-	RAID (redundant arrays of independent disks)
Course 2. Buffer-replacement policies
- File organization: fixed-length records, variable-length records, sequential file, heap file, sorted file, multitable clustering file organization.
- data dictionary storage
Course 3. Ordered indices, dense and sparse indices and multilevel indices. Index Sequential Access Mechanism. Index update. Primary (clustering) and secondary (unclustering) indices.
Course 4. B+-tree index files. Structure of a B+-tree. Queries on B+-trees. Algorithm for update, delete in B+-tree. B+-tree file organization.
Course 5. B-tree index files. Static hashing, hash indices. Dynamic hashing: extendable hashing, algorithms for update and delete in hash files. Comparison of ordered indexing and hashing.
Course 6. Multiple-key access: using multiple single-key indices, indices on multiple keys, bitmaps indices.
Course 7. Overview of query processing. Measures of query cost. Basic algorithm for selection implementation. (linear search, binary search, using indices, selections involving comparison)
Course 8. Algorithms for external sorting.
Course 9. Algorithms for join implementation (nested-loop join, block nested-loop join, indexed nested-loop join, merge join, hash join, cost of algorithms).
Course 10. Algorithms for projection, set operations, outer join and aggregation implementation. Implementation of pipelining.  
Course 11. Overview of query optimization. Transformation of relational expressions, equivalence rules. Join ordering. Enumeration of equivalent expressions. Estimating statistics of expression results: selection size estimation, join size estimation, size estimation for other operations. Materialized view, it’s maintenance and using it in query optimization.
Course 12. Query processing and optimization in Oracle.
Course 13. Query processing and optimization in MS SQL Server.
Course 14. Physical database design.
Laboratory: Implementation of a complete single-user relational database management system. It involves a significant amount of coding. The project is highly structured, but there is enough slack in the specification so that creativity is both allowed and required. The basic project is divided into four parts: 
1.	The Record Management (RM) Component: implement a set of functions for managing unordered files of database records. 
2.	The Indexing (IX) Component: implement a facility for building indexes on records stored in unordered files. The indexing facility will be based on B+ trees or dynamic hashing. 
3.	The System Management (SM) Component: This part will implement various database and system utilities, including data definition commands, (including primary key and foreign key constraint), index definition commands and catalog management. The System Management component will rely on the Record Management and Indexing components from Parts 1 and 2. It also will use a command-line parser or a graphical user interface. 
4.	The Query Language (QL) Component: In this part students will implement a query language, which consists of user-level data manipulation commands, both queries and updates (SQL Select, Insert, Update, Delete can be used). The Query Language component will rely on the three components from Parts 1-3, and it will use the command-line parser or a graphical user interface. The queries have to be processed, using algorithms presented at the course.
Lab 1-3. Project part 1.
Lab 4-5. Project part 2.
Lab 6-7. Project part 3.
Lab 8-11. Project part 4.
Lab 12. Examples of optimized queries in Oracle.
Lab 13. Examples of optimized queries in MS-SQL Server.
Lab 14. Project presentation.	

VII. Didactic methods used
The course is explained using Power Point presentations, which permits more examples, conversations with students. The query processing and optimization examples in Oracle and MS SQL Server are presented on the running systems on the instructor’s laptop.	

VIII. Assessment
1. Laboratory 			60%  (50 % project) 
2. Course activity 		10 %
3. Exam 			30 %	

IX. Additional references
www.db-book.com; www.cs.wisc.edu/~dbbook; \\SCS\SQL-INFO\Documentation	

	Dean,							Chair head,
Prof. Tâmbulea Leon, Ph.D.			Prof. Boian Florin, Ph.D.

	Date,							Course responsible,
	26-September, 2009					Assoc.Prof. VARGA Viorica, Ph.D.