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
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.
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.
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.
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.
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.
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).
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.
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.
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.
Continued.
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.
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.
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.
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.
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.
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.
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.
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).
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.
In this class we continue the discussion about the implementation of relational operators. In particular we discuss Nested Loop Joins and Sort-Merge Joins.
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.
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.
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.
In this class we present an overview of the transactional part of a database system.
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.
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.
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.
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.