Teaching Fellow: Parsoa Khorsand Rahim Zadeh
Teaching Fellow: Sajjad Rahnama
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
- "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.
- "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)
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) -- now 70% of your grade due to the final cancelation
- 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 March 6 (8:00am-4:00pm)
- Milestone 3: Multi-threaded, In-memory & Durable L-Store (Due on March 10); Oral Eval on March 13 (8:00am-4:00pm) Submission extended till March 15
- (Extra-credit of up to 20% can be earned in each milestone)
- In-class Midterm: 10% (Feb 20, 2020) -- now 20% of your grade due to the final cancelation
- Final Exam: 20% (Mar 19, 2020 at 8:00am) -- cancelled due to coronavirus
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.
List of Topics (tentative):
- 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)
- Relational Algebra (DB.Chapter 4)
- SQL: Queries, Programming, and Triggers (DB.Chapter 5)
- Optional Advanced Topics: Hive (Paper, Slides by Facebook & Cloudera)
- Optional Advanced Topics: SparkSQL (Paper, Slides by UC, Berkeley, AMPlab & databricks)
- Disks and Files (DB.Chapter 8)
- File Organization and Indexing (DB.Chapter 9)
- Lineage-based Storage Architecture (L-Store: Paper, Slides)
- Tree-Structured Indexes (TP.Chapter 6, DB.Chapter 9, and Intuitive and Simple Visual)
- Hash-Based Indexes (TP.Chapter 6 & DB.Chapter 10)
- Database Design & Index Selection (DB.Chapter 20a, Chapter 20b)
- Optional Advanced Topics: Latch-free, In-memory Indexes (TP.Chapter 6 & Bw-Tree: Paper, Slides)
- Optional Advanced Topics: In-memory, High-dimensional Indexes
- Transaction Properties (TP.Chapter 2 & DB.Chapter 16)
- Concurrency Control (DB.Chapter 17 & TP.Chapters 3-5)
- Optional Advanced Topics: Crash Recovery (DB.Chapter 20)
- Optional Advanced Topics: In-memory Databases (TP.Chapter 3 & Microsoft Hekaton: Paper)
- Optional Advanced Topics: Multi-version Optimistic Concurrency Control (TP.Chapter 3 & 2VCC: Paper)
- Optional Advanced Topics: Deterministic Concurrency Control (TP.Chapter 5 & QueCC: Paper)
- Optional Advanced Topics: Distributed Non-blocking Transactions (EasyCommit: Paper, Slides)
- Optional Advanced Topics: Distributed Deterministic Transactions (TP.Chapter 4 & Calvin: Paper, Distributed Workflow: Paper)
- Optional Advanced Topics: Avoiding Distributed Coordination Using Partitioning & Replication (TP.Chapter 6 & Schism: Paper)
- External Sorting (DB.Chapter 11)
- Evaluation of Relational Operators (DB.Chapter 12a [Join], DB.Chapter 12b [Selection, Projection, etc.])
- Relational Query Optimization (DB.Chapters 13 & 14)
- Optional Advanced Topics: Materialized Views (Survey Paper, Slides)
- Optional Advanced Topics: Index Maintenance (Indirection: Paper)
- Optional Advanced Topics: Resilient Distributed Datasets (RDDs: Paper, Slides)
- 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]
- Introduction to Relational Databases (DB.Chapter 1)
- Relational Algebra (DB.Chapter 4) (Individual Pre-milestone Assignment is due on January 19)
- Storage and Indexing (DB.Chapter 8)
- 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]
- Concurrency Protocols in L-Store (TP.Chapters 3.1.3, 3.4, 5.2.1) [Slides]
- L-Store Concurrency: QueCC - A Queue-oriented, Control-free Concurrency Architecture (TP.Chapters 5.1.6) [Paper, Slides]
- L-Store Concurrency: QueCC - A Queue-oriented, Control-free Concurrency Architecture (TP.Chapters 5.1.6) [Paper, Slides] (Midterm Preparation/Review)
- In-class Midterm
- Due to unforeseen circumstances, the class is canceled (Milestone 2 is due)
- Due to unforeseen circumstances, the class is canceled
- Concurrency Control: Optimistic and Timestamp CC (DB.Chapter 17 & TP.Chapters 3-5) (Milestone 3 is due) -- Extended till March 15
February 26, 2020: The Milestone #2 Presentation will be on March 6, 2020
February 5, 2020: Milestone #2 is out. It is due on Tuesday, February 25 through Canvas. There will be a 10% penalty for each late day. After two late days, the assignment will not be accepted.
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.
Course materials/grades will be made available on your Canvas account.