EPL446: Advanced Database Systems
by Demetris Zeinalipour
Department of Computer Science
University of Cyprus

Quick Links

WebMail
CS Courses

EPL446: Schedule

 

Week

 Description PDF
1 Syllabus & Introduction to Advanced Database Management Systems (Chapter 1, Ramakrishnan & Gehrke 3ED)

Course Objectives  and Syllabus, Overview of the Minibase system,  Review of basic definitions :  Data Models, Levels of Abstractions, Data Independence, Introduction to problems addressed in EPL446: Query Optimization, Transactions, Concurrency Control, Detailed Course Outline		 Syllabus

Lecture 1
  Overview of Storage and Indexing (Chapters 8.1-8.3, Ramakrishnan & Gehrke 3ED):

DBMS Layer 1: Data on External Storage, Storage Mediums & Storage Hierarchy, DBMS Layer 2: Disk Space Manager (DSM),  DBMS Layer 3:Buffer Manager (BM),  DBMS Layer 4: Alternative File Organizations & Indexes (Access Methods), B+ Tree Index Overview, Structure of Data Entry k*, Hash-Based Index Overview, Clustered vs. Unclustered Indexes,  Primary vs. Secondary Indexes

Lecture 2
2
 Overview of Storage and Indexing (Chapters 8.4-8.5, exclude 8.4.5-8.4.6Ramakrishnan & Gehrke 3ED):

Finish Lecture 2: 2.20-2.28

Comparison of File Organizations (System and Cost Model, Assumptions), I/O cost analysis (Heap Files, Sorted Files and Clustered B+Tree Index File), Indexes and Performance Tuning (Understanding the Workload, Index Specification in SQL, Index-Only Plans,Index Selection Guidelines)


Lecture 3

Storing Data: Disks and Files(Chapters 9.1-9.7, Ramakrishnan & Gehrke 3ED):

Finish Lecture 3: 3.11-3.17

Disks (Components, Accessing a Block, Arranging Pages), RAID (Basic Concepts, Levels: 0 to 5 and 0+1), Disk Space Manager, Buffer Manager: Definitions (Pin/Unpin, Dirty-bit),  Replacement Policies (LRU, MRU, clock), Sequential Flooding, Buffer in OS, File, Page and Record Formats: File Structure (Linked-List/Directory-based), Page Structure with Fixed/Variable-length records, Record Structure (Fixed-length/Variable-length), System Catalog.

Assignment #1 - Announcement

Lecture 4

Ex1
3  Tree-based Indexing: ISAM (Chapters 10.1-10.2, Ramakrishnan & Gehrke 3ED):

Finish Lecture 4.15-4.37

Introduction to Tree Indexes, Structure of Nodes in Trees, Binary Search over Sorted Files, Binary vs. N-ary Search Trees, ISAM: Indexed Sequential Access Method (Outline, Search, Insert, Delete, Examples)

Lecture 5

Tree-based Indexing: B+Trees (Chapters 10.3-10.8, Ramakrishnan & Gehrke 3ED):

Introduction to B+ Trees, B+Tree Functions: Search / Insert / Delete (Algorithms & Examples), B+ Trees in Practice: i) Prefix-Key Compression and ii) Bulk Loading B+Trees 		Lecture 6
  4 Hash-based Indexing (Chapters 11.1-11.4, Ramakrishnan & Gehrke 3ED):

Static Hashing, Dynamic Hashing (Extendible Hashing, Linear Hashing), Extendible vs Linear Hashing

Lecture 7

Overview of Query Evaluation (Chapters 12.1-12.2,12.4-12.5, Ramakrishnan & Gehrke 3ED):

Finish Lecture 7.16-7.25 (Linear Hashing)

Revision of the Relational Model and Relational Operators, Overview of Query Evaluation, Introduction to Query Optimization, Alternative Plans: Motivation with Examples

Assignment #1 - Due Date (to be delivered on Wednesday noon in the Lab and electronically through Moodle)

Assignment #2 - Announcement

Lecture 8

Ex2
5 External Sorting (Chapters 13.1-13.5, Ramakrishnan & Gehrke 3ED):  

Introduction (When a DBMS sorts data), Simple Two-Way Merge-Sort, External Merge-Sort, Double Bufferun Using B+Tree for Sorting.Tentative: Minimizing I/O cost versus number of I/Os, 		 Lecture 9
  Evaluating Relational Operators (Chapters 12.3,14.1,14.3,14.5, Ramakrishnan & Gehrke 3ED):

Introduction to Algorithms for Relational Operators, The Selection Operation (No Index/Unsorted Data, No Index/Sorted Data, B+Tree Index, Hash Index), General Selection Conditions (Conjunctive Normal Form & Index Matching, Selections with No Disjunctions, Selections with Disjunctions, The Project Operation (using Sorting, using Hashing, Sorting vs. Hashing)		 Lecture 10
6 Evaluating Relational Operators (Chapters 14.4 - exclude Hash Join, Ramakrishnan & Gehrke 3ED)

Simple Nested Loops Join (Tuple-at-a-time, Page-at-a-time), Block-Nested Loop Join (M-size, M-size with Hashtable, (B-2)-size, Index-Nested Loops Join, Sort-Merge Join, Sort-Merge Join Refinement (Combining merge phase of sorting with merge phase of joining), Sort-Merge-Join Implementation Details

Lecture 11
  Typical Relational Query Optimizer (Chapter 12.6,15.1-15.4, Ramakrishnan & Gehrke 3ED):

What a Typical Optimizer Does (Alternative Plans Considered, Left-Deep Plans, Estimating the Cost of a Plan), Translating SQL Queries into Algebra, Estimating the Cost of a Plan, Relational Algebra Equivalences, Enumeration of Alternative Plans (Single-Relation Queries, Multiple-Relation Queries).

Assignment #2 - Due Date (to be delivered on Wednesday noon in the Lab and electronically through Moodle)		 Lecture 12
7
 MIDTERM - Friday 5/3/09
This is a closed book exam: no books, notebooks, notes, etc. allowed

Overview of Transaction Management & Concurrency Control (Chapters 16.1-16.3 and 16.6, Ramakrishnan & Gehrke 3ED)
* Supplementary Material:  Chapters 17.1-17.3 and 17.6 from Elmasri, Navathe 5ed

16.0) Introduction to Transactions, 16.1) The ACID (Atomicity-Consistency-Isolation-Durability) Properties, 16.2) Transactions and Schedules, 16.3) Concurrent Executions of Transactions and Problems, 16.6) Transaction Support in SQL

Assignment #3 - Announcement		 Lecture 13
Ex3
8 Overview of Transaction Management & Concurrency Control (Chapters 17.4-17.5, Elmasri & Navathe, 5ED)
* Supplementary Material: Chapters 16.2-16.3 and 17.1 from Ramakrishnan & Gehrke, 3ED

16.2) Transactions and Schedules  (Serial, Complete Schedules), Serializability (Conflicting Actions, Conflict Equivalence, Conflict Serializability, Testing for Serializability using Precedence Graphs, View Equivalence and View Serializability),  16.3) Concurrent Execution of Transaction, 17.1) Recoverability (Recoverable Schedule, Cascadeless schedule, Strict Schedules)

Lecture 14
  Concurrency Control with Locking (Chapter 18.1, Elmasri & Navathe, 5ED):
* Supplementary Material: Chapters 17.1-17.4 from Ramakrishnan & Gehrke, 3ED

Introduction to DBMS Concurrency Control, Concurrency Control with Locking, Locks and Types of Locks, Implementing Locks in a DBMS, Conversion of Locks (Upgrade/Downgrade), CC with Locking Techniques (Conservative 2PL, Basic 2PL, Strict 2PL, Rigorous 2PL), Deadlocks and Starvation

Lecture 15
9 Concurrency Control with Timestamps (Chapters 18.2-18.4, Elmasri & Navathe, 5ED):
* Supplementary Material: Chapter 17.6 from Ramakrishnan & Gehrke, 3ED

Timestamp based CC: Definitions, Basic Timestamp Ordering (TO) Algorithm  and Examples, Strict Timestamp Ordering, Multiversion Concurrency Control,
Optimistic Concurrency Control

Lecture 16
  Crash Recovery (Chapters 17,  Garcia-Molina, Ullman, Widom, 2ED):

Definitions, Purpose, Failure Reasons, ACID Properties and Responsibilities, Undo Logging and Recovery, Checkpointing and Nonquiescent Checkpointing

Assignment #3 - Due Date (to be delivered on Wednesday noon in the Lab and electronically through Moodle)

 Lecture 17
10 Crash Recovery (Chapters 17,  Garcia-Molina, Ullman, Widom, 2ED):

Redo Logging and Recovery, Redo-Undo Logging and Recovery, ARIES Algorithm		 Lecture 18
 
National Holiday: March, 25th
 ---
11 Introduction to Distributed Databases (Chapters 25.1-25.4,  Elmasri & Navathe, 5ED):
* Supplementary Material: Chapters 22.6-22.10 from Ramakrishnan & Gehrke, 3ED

Introduction to Distributed Databases, Types of Distributed Databases, Homogeneous, Heterogeneous (Federated, MultiDBs), Distributed Databases Architectures (Client Server, Collaboration Server, Middleware),  Data Fragmentation & Replication (Horizontal, Vertical and Mixed Fragmentation. Synchronous vs. Asynchronous Replication)
Lecture 19
 
National Holiday: April 1st
 ---
12 Introduction to Distributed Databases (Chapters 25.1-25.4,  Elmasri & Navathe, 5ED):
* Supplementary Material: Chapters 22.6-22.10 from Ramakrishnan & Gehrke, 3ED

 Distributed Catalog Management. Distributed Query Processing (Centralized, Ship-to-one-site, Semi-join, Bloom-join)

Assignment #4 - Announcement		 Lecture 20

Ex4


Introduction to Semi-Structured (XML) Data  (Chapter 27,  Elmasri & Navathe, 5ED):
* Supplementary Material: Chapters 27.6-27.7 from Ramakrishnan & Gehrke, 3ED

Introduction, Structured, Semi structured, and Unstructured Data, XML Hierarchical (Tree) Data Model, XML Documents, DTD, 
 Lecture 21
13 Introduction to Semi-Structured (XML) Data  (Chapter 27,  Elmasri & Navathe, 5ED):
* Supplementary Material: Chapters 27.6-27.7 from Ramakrishnan & Gehrke, 3ED

XML Schema, Overview of XML Documents and Databases, Overview of XML Querying (XPath and XQuery)
Lecture 22
   Student Presentations

Assignment #4 - Due Date (to be delivered on Wednesday noon in the Lab and electronically through Moodle)
Presentations
Website


FINAL EXAM s

Day: TBA
Time: TBA
Place: ×ÙÄ01-xxx, New University Campus

This is a closed book exam: no books, notebooks, notes, etc. allowed
 
 

 

Copyright © Department of Computer Science, University of Cyprus