Advanced Databases

Objectives and outcomes
Students are familiar with the principles and elements of modern database management systems. Upon completion of the course, students will understand the internal functionality of a database management system. They will be able to analyse basic algorithms for query evaluation and concurrency control. They will be able to implement or modify existing database management system modules and evaluate their performances.

Lectures
Physical architecture of a database management system. Memory space management. File management. Physical organisation of databases. In-memory databases. Tree-based indexing. Indexed Sequential Access Method (ISAM). Searching, inserting, deleting and duplicates. Key compression. Bulk loading B+ trees. Hash-based indexing. Static, extendible and linear hashing. Query evaluation. System catalogs. Algorithms for relational operations. External sorting. External Merge Sort. Use of B+ sorting trees. Evaluation of relational operators. Selection operations (without index – unsorted and sorted data, with index – index with B+ tree, hash index). CNF and index matching. Selections with disjunction. Projection operations. A Join operation. Set operations. Aggregation operations. Query optimization. Translating SQL queries into algebra. Equivalences of relational algebra (selections, projections, intersections and unions). Multiple relation queries. Nested subqueries. Cost-based and rule-based optimisations. Transaction management. ACID properties. Concurrent transactions. Lock-based concurrency control. Transaction support in SQL. Atomicity and rollback implementation. Implementation of distributed databases. Evaluation of parallel queries. Data partitioning. Non-relational and NoSQL databases. Deductive, temporal and spatial databases.

Practical classes
MySQL open-source database management system. Architecture analysis and experimental modification of the following modules: Connection Manager, Thread Manager, Connection Thread, User Authentication, Access Control, Parser, Command Dispatcher, Query Cache, Optimizer, Table Manager, Table Modification, Table Maintenance, Status Reporting, Abstracted Storage Engine Interface, Storage Engine Implementations (MyISAM, InnoDB, MEMORY, Berkeley DB), Logging, Replication Master, Replication Slave, Client/Server Protocol API.