CAS CS 460

Introduction to Database Systems


Syllabus    Assignments    Labs    Announcements

Class at a glance

Class: M/W 4:30-5:45pm, EPC 207
Instructor: Manos Athanassoulis 

Teaching Assistant: Dimitris Staratzis
Dimitris Office Hours: M 1:30–2:30pm/Th 4:30–5:30pm

Office: MCS 106
Manos Office Hours: M/W 3-4:15pm

Discussion on Piazza /Notes /Gradescope
Labs: Tue 9:30am/10:20am, FAB341 / 12:30pm, FCB 104

Announcements



Class Schedule

Here you can find the tentative schedule of the class (which might change as the semester progresses). The textbook we use is also referred to as the "cow book" (see more details in the syllabus).

The slides will be uploaded here after each class, but they cannot be used as a replacement of the lectures, and will not be sufficient on their own. Some lectures might deviate from the textbook (in presentation, order, and content). Hence, attendance during the lecturing and during the class discussion is mandatory and an integral part of the class.

Class : Introduction

In our first class we introduce the concept of database systems, which store data and offer a declarative interface to access the data. We introduce the basic building blocks of database systems that are used to offer the expressive and efficient declarative interface to the data, and we discuss the aspects of everyday life, business operation, and scientific discovery for which database systems play a crucial role.

Readings

Class : Database Systems Architectures

In this class we discuss the fundamental components that comprise a database system. We will see the commonalities and the differences of the main database system architectures and we will discuss why we have several different ones. We will go over the key characteristics of relational systems (row-stores and column-stores), and we will introduce different designs like key-value stores and graph stores. Finally, we will introduce the class projects and we will discuss in detail course logistics.

Readings

  • Slides
  • "The Design and Implementation of Modern Column-Oriented Database Systems", Chapters 1, 2, 3
  • "Architecture of a Database System", Chapter 1

Class : ER Model

In this class we discuss the process of conceptually design our database. We will discuss how we can take specific requirements and transform them to a conceptual database schema using the Entity-Relationship Model (ER-Model). We will cover this process with examples.

Readings

Class : Relational Model

In this class we introduce the Relational Model, the most widely used model by vendors, institutions, and organizations to represent and store data. We connect this discussion with ER Model and we show how to build the relational model of an application when starting from the ER Model. This serves as a first get-to-know to SQL focusing on the DDL commands.

Readings

Class : Relational Algebra

In this class we introduce Relational Algebra, a query language used to express the implementation of queries. Relational Algebra is applied directly on relational data and can describe multiple ways of implementing the same "logical" query. We discuss the fundamental operations, their properties and the operations we can define using them (compound operations).

Readings

  • Slides
  • Textbook, Chapter 4.1, 4.2

Class : Functional Dependencies

In this class we introduce redundancy as one of the main problems in a relational schema. We introduce Functional Dependencies (FD) as generalized keys in order to help us identify a bad schema. We discuss how to reason for FD.

Readings

  • Slides
  • Textbook, Chapter 19.1-19.3

Class : Decomposition & Schema Normalization

In this class we use functional dependencies to identify bad schemata and to propose how to decompose relations to avoid problems from redundancy. We further discuss how to get good decompositions, that is, having lossless-joins and being (functional) dependency preserving. We discuss several normal forms that we can achieve with a varying degree of "how much" we decompose.

Readings

  • Slides
  • Textbook, Chapter 19.4-19.7

Class : SQL I

In this class we first introduce the basic constructs of an SQL query and then we continue thoroughly over several examples for SQL queries, slowly building increasingly complex queries. We discuss the basic SQL query, union-compatible operations, nested queries, aggregate operators, and the GROUP BY and HAVING keywords.

Readings

  • Slides
  • Textbook, Chapter 5.1-5.5

Class : SQL II

Continued.

Readings

  • Slides
  • Textbook, Chapter 5.1-5.5

Class : File Organization & Introduction to Indexing

In this class we introduce the main concepts needs to start working with the internals of database systems. We lay the groundwork needed for the memory hierarchy, file organization, page organization, and indexing.

Readings

Class : Storage Layer

In this class we dive into the details of the storage hierarchy. We discuss in detail the tradeoffs between different levels of the hierarchy. We provide details for the internals of hard disks and flash disks. We further discuss the specifics of buffer management and, specifically, of buffer replacement policies.

Readings

Class : Indexing with B+ Trees

In this class we dive into the details of indexing. We discuss in detail the internals of the most popular tree index in database management systems, the B+ Tree. We describe the search algorithm, the insert algorithm, and the delete algorithm. We further discuss aspects of key compression and bulk loading, two important performance optimizations.

Readings

  • Slides
  • Textbook, Chapter 10.1, 10.3-10.8

Class : External Sorting

In this class we discuss the problem of sorting in the context of database systems. Sorting is a virtually ubiquitous operation in data management, and frequently we have to sort data that do not fit in memory. To that end external sorting algorithms are developed (that minimize number of disk accesses as opposed to number of comparisons). We discuss different sorting paradigms including external sorting and sorting with B+ Trees.

Readings

Class : Log-structured Merge Trees

In this class we introduce an alternative indexing and storage organization named Log-Structured Merge Trees (LSM-Trees). We discuss in detail the internals of LSM-Trees. We describe the ingestion and the search routines, as well as, how to update and delete.

Readings

Review

This is a review class. We will go over open questions in previous subjects and also discuss subtle details on exercises, mostly on the ones that have not been part of the Homework assignments.

Readings

Midterm 1

You can bring with you two pages of any notes you want. No more material will be available. No laptops, tablets or phones are allowed.

Class : Hash-based Indexing

In this class we discuss the different approaches for hash-based indexing. We first introduce static hashing, which has the problem of long chains of overflow pages. Then we discuss two different ways to address this problem with dynamic hashing: extendible hashing which used a directory and has no chains, and linear hashing which uses multiple different hash functions and allows overflows pages which are split (and re-hashed frequently).

Readings

Class : Query Processing with Relational Operators

In this class we discuss the implementation of relational operators. We start by discussing the implementations of selections and projections. And then we will continue discussing the implementations of joins: nested loop joins, sort-merge joins, and hash joins.

Readings

Class : Joins I: Nested-Loop Joins and Sort-Merge Joins

In this class we continue the discussion about the implementation of relational operators. In particular we discuss Nested Loop Joins and Sort-Merge Joins.

Readings

  • Textbook, Chapter 14.4.1-14.4.2

Class : Joins II: Hash Joins & the remaining relational operators

In this class we continue the discussion about the implementation of relational operators. In particular we discuss Hash Joins, General Joins, Union/Intersection, and Aggregates.

Readings

  • Textbook, Chapter 14.4.3-14.4.4, 14.6-14.7

Class : Query Optimization

In this class we put together all the knowledge about the SQL operators evaluation costs in order to understand how to choose how to implement a whole SQL query. We discuss the basic properties needed for query rewriting, pruning the decision search space, and the interesting orders.

Readings

Class : Guest Lecture by Stella Pantela

In this lecture we talk about Vertica, one of the leading Big Data Analytics DBMs and how Vertica deals with the handling of metadata, which is data about the data that a database stores, including table names, projection information, encoding, min, max values and many more. How does the database store, maintain and modify that metadata in a safe and efficient way? What does the metadata handling have to do with the Add Column Operation?
Bio: Stella is a senior distributed systems software engineer at Vertica, chair of the Vertica DataGals and a member of the Vertica patent committee. At Vertica, Stella builds powerful infrastructure used by big data analytics companies including Uber, Etsy, Wayfair, Philps. Her focus is on improving the distributed systems protocols for more efficient maintenance and transfer of metadata in both the cloud and enterprise environments. Stella’s work has been featured at SIGMOD and North East Database Day. Before Vertica, Stella completed her B.A. with Honors in Computer Science at Harvard University in 2015, where she also conducted research in the area of column stores with Professor Stratos Idreos. In her free time she maintains a blog on distributed systems and technology at stylianipantela.com.

Class : Overview of Transaction Management

In this class we present an overview of the transactional part of a database system.

Readings

Class : Concurrency Control

In this class we discuss in detail how Concurrency Control can achieve Consistency and Isolation. We discuss two-phase locking (2PL), serializability, recoverability, and deadlocks.

Readings

  • Slides
  • Textbook, Chapter 17.1-17.5

Class : Concurrency Control (cont.)

Class : Recovery

In this class we discuss in detail how the system can achieve Atomicity and Durability, and also ensure crash recovery. We cover in detail the Write-Ahead Logging (WAL) Protocol.

Readings

Class : NoSQL Systems and Topics in Databases

In the last class of the semester we will discuss about NoSQL systems and active research directions in data management, and current opportunities and needs in the data management industry.

Readings

Class : Midterm 2

You can bring with you two pages (in one sheet) of any notes you want. No more material will be available. No laptops, tablets or phones are allowed.