ECS 165A: Database Systems

Instructor: Mohammad Sadoghi
E-mail: [email protected]
Office: Kemper 3055
Office Hours: Thursdays 3:30-5:30pm

Teaching Fellow:Parsoa Khorsand Rahim Zadeh
Email:[email protected]
Office: Kemper 47
Office Hours: Wednesdays 11am-1pm

Teaching Fellow: Sajjad Rahnama
Email: [email protected]
Office:Academic Surge 2050
Office Hours: Mondays 10am-12pm

Lecture
            Time: Tue/Thu 1:40-3:00pm
            Location: Giedt 1002

Discussions Sessions
           A1 Time: Wed 8:00-8:50am; Location: Cruess Hall 107
           A2 Time: Mon 12:10-1:00pm; Location: Olson Hall 147
           A3 Time: Wed 4:10-5:00pm; Location: Wellman Hall 1


Overview

This is an innovative data management course that provides an introduction to the design and development of fundamental concepts in relational database management systems (DBMS). You will learn the theory and design behind database systems, the issues that affect their functionality and performance, and most importantly, what it takes to effectively utilize modern databases in practice.

The course has completely been redesigned, all students are expected to work in a group of five on an exciting, open-ended, data-oriented, quarter-long project, in a sense, operating and simulating startup environments. Needless to say, this rewarding experience is accompanied by a significant development effort (in Python) that spans hands-on experience on concepts such as memory and disk management, synchronization and concurrency, logging and recovery, and query optimization and evaluation, to name a few. To materialize these objectives, together this quarter, we will be building simplified L-Store [Paper, Slides] from scratch, an Hybrid Transactional and Analytical Processing (HTAP) database.

The course work is complementary to the classical well-formed, prescriptive model of assignments/projects that are indeed effective and invaluable in practice. Instead by design, the project is intended to be open-ended, namely, minimal instructions and requirements will be provided, as such it rewards and values research & development, taking risks, above all, it is aimed to foster and tap into the creativity of each individual.

The quarter-long project is broken into a set of three milestones, primarily all milestones will be graded orally (additionally we may employ autograder), where the progress is presented by all five group members, and each group member must be ready to answer questions about any aspect of the project; the latter is the utmost importance to ensure comprehensive learning experience and fair division of work among all members. Furthermore, in each milestone, a bonus of up to 20% can be gained to further encourage taking a risk, going the extra mile, and to just be curious & creative. Part of the bonus is reserved for fastest and the most optimized implementation of L-Store in class, e.g., how many read/write operations per second (adjusted based on the number of cores, CPU clock frequency, amount of memory, cache size, and other hardware metrics to ensure comparable results).

A fact of life, when there is group work, whether at school or in society, there are occasional conflicts; and it is crucial to learn how to resolve our differences and be receptive, open, and kind to one another. In kindness and reflection, we shall aim to resolve all conflicts. It is the group responsibility to handle all internal affairs, and only when absolutely necessary involving the instructor. But note, only under very rare exceptional circumstances, a group re-structuring would be granted because once the group is formed, at least for 10 weeks, we must learn how to work with each other in harmony.

For each group, it is recommended that each member lead one aspect of the project while contributing and learning about other parts; roughly, the main components are (1) memory management (e.g., bufferpool), (2) disk management (e.g., persistence and logging), (3) in-memory indexing (e.g., hashing or tree), (4) data access methods (e.g., APIs and query language), (5) multi-threading and synchronization (e.g., data structures latching), (6) transaction and concurrency (e.g., record-level locking), and (7) testing and benchmarking (correctness verification and performance measurements).

As for the lectures, the list of topics covered would include but not limited to:

  • DBMS Concepts and Architecture
  • Storage and Indexing
  • Query Languages (Relational Algebra and SQL)
  • Query Evaluation and Optimization
  • Concurrency Control and Recovery
  • Database Design, the E-R Model, Normalization, and Tuning
  • Database Security, Blockchain

Syllabus

Textbooks:

Required:
  • "Database Management Systems" (referred to as DB), 3rd Edition. Raghu Ramakrishnan and J. Gehrke. McGraw Hill, 2003, ISBN 0-07-246563-8.
  • "Transaction Processing on Modern Hardware" (referred to as TP), 1st Edition. Mohammad Sadoghi and Spyros Blanas. [Free online access when accessed within the UC Davis network]
  • Additionally, a list of research papers will be added later as part of the optional reading for the enthusiastic students.
Optional:
  • "Readings in Database Systems", 4th Edition. Joseph M. Hellerstein, Michael Stonebraker. 2005
  • "The Elements of Style", 4th Edition. William Strunk Jr. and E. B. White. 1999
  • "Style: Toward Clarity and Grace". Joseph M. Williams. 1995

Workload:

The key component of the course is the quarter-long group project that is broken into a set of three main milestones. All milestones will be graded orally (unless specified otherwise), where the progress is presented by all group members, and each group member must be ready to answer questions about any aspect of the project; the latter is the utmost importance to ensure comprehensive learning experience and fair division of work among all members. Therefore, for each milestone, a portion of the grade is devoted to the presented project as a whole on which all members receive the same grade (70% of the grade), but the remaining portion is individualized (30% of the grade), so for each milestone, not all group members may receive the same grade. For each milestone, a bonus of up to 20% can be rewarded.

The presentation for the oral evaluation is limited to at most 12 minutes per team, the time is strictly enforced. The breakdown of 15 minutes is as follows:
  • The milestone overview: the design and solution, what was accomplished and how? (8 minutes)
  • Q/A: Questions about various aspects of the project (4 minutes)
  • Demo: A live demonstration of the code, which includes adding, modifying, and querying the data (3 minutes)
Additionally, there will be a pre-milestone individual assignment, for which each student is expected to think about and explore all aspects of the project. In other words, each student for his/herself, need to think about what it is required to make a HTAP database and to document their finding in a few pages. Of course, it is highly recommended to search the web for tutorials and other useful materials. As for part this pre-milestone phase, (1) the group must be formed, namely, when each student submit their report, the name of their group members and their team name must be submitted; and (2) each student must decide which aspect of the project he/she wishes to lead based on the research. If you need help to form your group and look for partners, kindly contact the TAs. Note any group assignment by TAs will be random. Additionally, an online form will be made available to submit your team details.

The mid-term and final will cover materials from the project and lectures.

Grading:

The final grade will be based upon the following components (all submissions are due at midnight):
  • Individual Pre-milestone Assignment: 10% (Due on Jan 19, 2020)
  • Group Project (three milestones): 60% (20% for each milesone)

    • Milestone 1: Single-threaded, In-memory L-Store (Due on Feb 4); Oral Eval on Feb. 7 (8:00am-4:00pm)
    • Milestone 2: Single-threaded, In-memory & Durable L-Store (Due on Feb 25); Oral Eval on Feb. 28 (8:00am-4:00pm)
    • Milestone 3: Multi-threaded, In-memory & Durable L-Store (Due on March 10); Oral Eval on Mar. 13 (8:00am-4:00pm)
    • (Extra-credit of up to 20% can be earned in each milestone)
  • In-class Midterm: 10% (Feb 20, 2020)
  • Final Exam: 20% (Mar 19, 2020 at 8:00am)

Communication:

For communication with the instructor, please use email ([email protected]) and not Canvas. The instructor will not check/reply to Canvas messages.

For group communication (monitored by TAs) and other students, we will rely on Slack. Please contact the TAs to add you to our Slack channel: ECS165A Slack.

Course Policy:

In this class, we adopt the UC Davis Code of Academic Conduct available here.

In addition, late submission will result in a 10% penalty for each day late; at most an extension of up to two days may be granted. Students are strongly advised that any act of cheating will result in a score of 0 for the entire milestone (or the course) and offenses will be reported to the Office of the Dean of Students. You are encouraged to discuss problems and ideas but the final solution or code must be your own. In the event of a major campus emergency, course requirements, deadlines, and grading percentages are subject to changes that may be necessitated by a revised quarter calendar. If such unusual circumstances arise, students may determine any such changes by contacting the instructor.


Contents

List of Topics (tentative):

  1. Introduction to Database Systems
    • Database Management Systems (DB.Chapter 1)
    • The Relational Model (DB.Chapter 3)
    • Optional Advanced Topics: Overview of Modern Distributed Data Processing Systems (Hadoop, Spark)
  2. Database Query Languages
  3. Storage and Indexing
  4. Transaction Management
  5. Schema Design (tentative)
  6. Query Evaluation (tentative)
  7. Index & Storage Management (tentative)
    • Optional Advanced Topics: Index Maintenance (Indirection: Paper)
    • Optional Advanced Topics: Resilient Distributed Datasets (RDDs: Paper, Slides)
  8. Secure Transactions & Blockchain (tentative)
    • Optional Advanced Topics: Blockchain Landscape and AI Renaissance: The Bright Path Forward. [Tutorial: Part 1, Part 2]
    • Optional Advanced Topics: An In-Depth Look of BFT Consensus in Blockchain: Challenges and Opportunities. [Paper, Slides: System, Theory]
    • Optional Advanced Topics: Blockchain Transaction Processing. [Encyclopedia: Preprint]
    • Optional Advanced Topics: ResilientDB [Journey, Slides, Code]


Tentative Schedule

January 7, 2020:
  • Overview
January 9, 2020: January 14, 2020: January 16, 2020:
  • Relational Algebra (DB.Chapter 4)
  • (Individual Pre-milestone Assignment is due on January 19)
January 21, 2020: January 23, 2020:
  • Storing Data: Disks and Files (DB.Chapter 9)
  • L-Store - Lineage-based Storage Architecture (TP.Chapters 3.1.3, 3.4, 5.2.1) [Paper, Slides]
January 28, 2020:
  • L-Store - Lineage-based Storage Architecture (TP.Chapters 3.1.3, 3.4, 5.2.1) [Paper, Slides]
January 30, 2020:
  • Transaction Concepts & Properties
February 4, 2020:
  • Concurrency Controls: Part 1
  • (Milestone 1 is due)
February 6, 2020:
  • Concurrency Controls: Part 2
February 11, 2020:
  • L-Store MVCC Concurrency: Part 1
February 13, 2020:
  • L-Store MVCC Concurrency: Part 2
February 18, 2020:
  • TBA
February 20, 2020:
  • In-class Midterm
February 25, 2020:
  • Analytics: SQL Query Language
  • (Milestone 2 is due)
February 27, 2020:
  • Database Design & Index Selection: Part 1
March 3, 2020:
  • Database Design & Index Selection: Part 2
March 5, 2020:
  • Query Evaluation: Part 1
March 10, 2020:
  • Query Evaluation: Part 2
  • (Milestone 3 is due)
March 12, 2020:
  • TBA

Announcements

January 21, 2020: Milestone #1 is out. It is due on Tuesday, February 4 through Canvas. There will be a 10% penalty for each late day. After two late days, the assignment will not be accepted.

January 12, 2019: Pre-milestone Homework is out. It is due on Sunday, January 19 through Canvas. There will be a 10% penalty for each late day. After two late days, the assignment will not be accepted.

January 2, 2020: Welcome to ECS 165A. Kindly note that the lecture starts on January 7 and discussion sessions starts on the week of Jan. 13. Looking forward to an amazing quarter.

Handouts

Course materials/grades will be made available on your Canvas account.