# Table of Contents - [Overview | CS186 Projects](#overview-cs186-projects) - [Submitting the Assignment | CS186 Projects](#submitting-the-assignment-cs186-projects) - [SQL vs. SQLite | CS186 Projects](#sql-vs-sqlite-cs186-projects) - [Project 1: SQL | CS186 Projects](#project-1-sql-cs186-projects) - [Testing | CS186 Projects](#testing-cs186-projects) - [Project 3: Joins and Query Optimization | CS186 Projects](#project-3-joins-and-query-optimization-cs186-projects) - [Getting Started | CS186 Projects](#getting-started-cs186-projects) - [Project 2: B+ Trees | CS186 Projects](#project-2-b-trees-cs186-projects) - [Testing | CS186 Projects](#testing-cs186-projects) - [Getting Started | CS186 Projects](#getting-started-cs186-projects) - [Submitting the Assignment | CS186 Projects](#submitting-the-assignment-cs186-projects) - [Submitting the Assignment | CS186 Projects](#submitting-the-assignment-cs186-projects) - [Your Tasks | CS186 Projects](#your-tasks-cs186-projects) - [Your Tasks | CS186 Projects](#your-tasks-cs186-projects) - [Part 2: Query Optimization | CS186 Projects](#part-2-query-optimization-cs186-projects) - [Part 0: Skeleton Code | CS186 Projects](#part-0-skeleton-code-cs186-projects) - [Submitting the Assignment | CS186 Projects](#submitting-the-assignment-cs186-projects) - [Testing | CS186 Projects](#testing-cs186-projects) - [Getting Started | CS186 Projects](#getting-started-cs186-projects) - [Part 1: Join Algorithms | CS186 Projects](#part-1-join-algorithms-cs186-projects) - [Task 2 Common Errors | CS186 Projects](#task-2-common-errors-cs186-projects) - [Task 1 Debugging | CS186 Projects](#task-1-debugging-cs186-projects) - [Project 4: Concurrency | CS186 Projects](#project-4-concurrency-cs186-projects) - [Part 0: Skeleton Code | CS186 Projects](#part-0-skeleton-code-cs186-projects) - [Development Container Setup | CS186 Projects](#development-container-setup-cs186-projects) - [Getting Started | CS186 Projects](#getting-started-cs186-projects) - [Getting Started | CS186 Projects](#getting-started-cs186-projects) - [Project 0: Setup | CS186 Projects](#project-0-setup-cs186-projects) - [Part 1: Queuing | CS186 Projects](#part-1-queuing-cs186-projects) - [Your Tasks | CS186 Projects](#your-tasks-cs186-projects) - [Submitting the Assignment | CS186 Projects](#submitting-the-assignment-cs186-projects) - [Testing | CS186 Projects](#testing-cs186-projects) - [Getting Started | CS186 Projects](#getting-started-cs186-projects) - [Project 5: Recovery | CS186 Projects](#project-5-recovery-cs186-projects) - [Your Tasks | CS186 Projects](#your-tasks-cs186-projects) - [Part 2: Multigranularity | CS186 Projects](#part-2-multigranularity-cs186-projects) - [Testing | CS186 Projects](#testing-cs186-projects) - [Submitting the Assignment | CS186 Projects](#submitting-the-assignment-cs186-projects) - [Project 6: NoSQL | CS186 Projects](#project-6-nosql-cs186-projects) - [Project 0: Setup | CS186 Projects](#project-0-setup-cs186-projects) - [Submitting the Assignment | CS186 Projects](#submitting-the-assignment-cs186-projects) - [Getting Started | CS186 Projects](#getting-started-cs186-projects) - [Adding a partner on GitHub | CS186 Projects](#adding-a-partner-on-github-cs186-projects) - [Miscellaneous | CS186 Projects](#miscellaneous-cs186-projects) - [Nested Loop Join Animations | CS186 Projects](#nested-loop-join-animations-cs186-projects) - [Your Tasks | CS186 Projects](#your-tasks-cs186-projects) - [Adding a partner on GitHub | CS186 Projects](#adding-a-partner-on-github-cs186-projects) --- # Overview | CS186 Projects ![](https://cs186.gitbook.io/project/~gitbook/image?url=https%3A%2F%2F678656433-files.gitbook.io%2F%7E%2Ffiles%2Fv0%2Fb%2Fgitbook-x-prod.appspot.com%2Fo%2Fspaces%252F-MFVQnrLlCBowpNWJo1E%252Fuploads%252Fgit-blob-35ab29e43032fa73e20aa5d368f8770023de93cf%252Fderpydb-small%2520%281%29%2520%285%29%2520%284%29%2520%281%29%2520%282%29%2520%285%29.jpg%3Falt%3Dmedia%26token%3De83dcdb6-1092-404c-90b0-26d7a07f1de1&width=768&dpr=4&quality=100&sign=f29c59a7&sv=2) The official unofficial mascot of the projects RookieDB is a bare-bones database implementation which supports executing simple transactions in series. In the assignments of this class you will be adding support for B+ tree indices, efficient join algorithms, query optimization, multigranularity locking to allow concurrent execution of transactions, and database recovery. For convenience, the staff will be maintaining a read-only public repo [here](https://github.com/berkeley-cs186/sp25-rookiedb/) containing the project skeleton. When starting projects remember to work off of the private repos provided to you through GitHub Classroom rather than the public one. [](https://cs186.gitbook.io/project/#code-overview) Code Overview ---------------------------------------------------------------------- As you will be working with this codebase for the rest of the semester, it is a good idea to get familiar with it. The code is located in the `src/main/java/edu/berkeley/cs186/database` directory, while the tests are located in the `src/test/java/edu/berkeley/cs186/database` directory. The following is a brief overview of each of the major sections of the codebase. ### [](https://cs186.gitbook.io/project/#cli) cli The `cli` directory contains all the logic for the database's command line interface. Running the main method of `CommandLineInterface.java` will create an instance of the database and create a simple text interface that you can send and review the results of queries in. **The inner workings of this section are beyond the scope of the class** (although you're free to look around), you'll just need to know how to run the Command Line Interface. #### [](https://cs186.gitbook.io/project/#cli-parser) cli/parser The subdirectory `cli/parser` contains a lot of scary looking code! Don't be intimidated, this is all automatically generated automatically from the file `RookieParser.jjt` in the root directory of the repo. The code here handles the logic to convert from user inputted queries (strings) into a tree of nodes representing the query (parse tree). #### [](https://cs186.gitbook.io/project/#cli-visitor) cli/visitor The subdirectory cli/visitor contains classes that help traverse the trees created from the parser and create objects that the database can work with directly. ### [](https://cs186.gitbook.io/project/#common) common The `common` directory contains bits of useful code and general interfaces that are not limited to any one part of the codebase. ### [](https://cs186.gitbook.io/project/#concurrency) concurrency The `concurrency` directory contains a skeleton for adding multigranularity locking to the database. You will be implementing this in Project 4. ### [](https://cs186.gitbook.io/project/#databox) databox Our database has, like most DBMS's, a type system distinct from that of the programming language used to implement the DBMS. (Our DBMS doesn't quite provide SQL types either, but it's modeled on a simplified version of SQL types). The `databox` directory contains classes which represents values stored in a database, as well as their types. The various `DataBox` classes represent values of certain types, whereas the `Type` class represents types used in the database. An example: Copy DataBox x = new IntDataBox(42); // The integer value '42'. Type t = Type.intType(); // The type 'int'. Type xsType = x.type(); // Get x's type, which is Type.intType(). int y = x.getInt(); // Get x's value: 42. String s = x.getString(); // An exception is thrown, since x is not a string. ### [](https://cs186.gitbook.io/project/#index) index The `index` directory contains a skeleton for implementing B+ tree indices. You will be implementing this in Project 2. ### [](https://cs186.gitbook.io/project/#memory) memory The `memory` directory contains classes for managing the loading of data into and out of memory (in other words, buffer management). The `BufferFrame` class represents a single buffer frame (page in the buffer pool) and supports pinning/unpinning and reading/writing to the buffer frame. All reads and writes require the frame be pinned (which is often done via the `requireValidFrame` method, which reloads data from disk if necessary, and then returns a pinned frame for the page). The `BufferManager` interface is the public interface for the buffer manager of our DBMS. The `BufferManagerImpl` class implements a buffer manager using a write-back buffer cache with configurable eviction policy. It is responsible for fetching pages (via the disk space manager) into buffer frames, and returns Page objects to allow for manipulation of data in memory. The `Page` class represents a single page. When data in the page is accessed or modified, it delegates reads/writes to the underlying buffer frame containing the page. The `EvictionPolicy` interface defines a few methods that determine how the buffer manager evicts pages from memory when necessary. Implementations of these include the `LRUEvictionPolicy` (for LRU) and `ClockEvictionPolicy` (for clock). ### [](https://cs186.gitbook.io/project/#io) io The `io` directory contains classes for managing data on-disk (in other words, disk space management). The `DiskSpaceManager` interface is the public interface for the disk space manager of our DBMS. The `DiskSpaceMangerImpl` class is the implementation of the disk space manager, which maps groups of pages (partitions) to OS-level files, assigns each page a virtual page number, and loads/writes these pages from/to disk. ### [](https://cs186.gitbook.io/project/#query) query The `query` directory contains classes for managing and manipulating queries. The various operator classes are query operators (pieces of a query), some of which you will be implementing in Project 3. The `QueryPlan` class represents a plan for executing a query (which we will be covering in more detail later in the semester). It currently executes the query as given (runs things in logical order, and performs joins in the order given), but you will be implementing a query optimizer in Project 3 to run the query in a more efficient manner. ### [](https://cs186.gitbook.io/project/#recovery) recovery The `recovery` directory contains a skeleton for implementing database recovery a la ARIES. You will be implementing this in Project 5. ### [](https://cs186.gitbook.io/project/#table) table The `table` directory contains classes representing entire tables and records. The `Table` class is, as the name suggests, a table in our database. See the comments at the top of this class for information on how table data is layed out on pages. The `Schema` class represents the _schema_ of a table (a list of column names and their types). The `Record` class represents a record of a table (a single row). Records are made up of multiple DataBoxes (one for each column of the table it belongs to). The `RecordId` class identifies a single record in a table. The `HeapFile` interface is the interface for a heap file that the `Table` class uses to find pages to write data to. The `PageDirectory` class is an implementation of `HeapFile` that uses a page directory. #### [](https://cs186.gitbook.io/project/#table-stats) **table/stats** The `table/stats` directory contains classes for keeping track of statistics of a table. These are used to compare the costs of different query plans, when you implement query optimization in Project 4. ### [](https://cs186.gitbook.io/project/#transaction.java) Transaction.java The `Transaction` interface is the _public_ interface of a transaction - it contains methods that users of the database use to query and manipulate data. This interface is partially implemented by the `AbstractTransaction` abstract class, and fully implemented in the `Database.Transaction` inner class. ### [](https://cs186.gitbook.io/project/#transactioncontext.java) TransactionContext.java The `TransactionContext` interface is the _internal_ interface of a transaction - it contains methods tied to the current transaction that internal methods (such as a table record fetch) may utilize. The current running transaction's transaction context is set at the beginning of a `Database.Transaction` call (and available through the static `getCurrentTransaction` method) and unset at the end of the call. This interface is partially implemented by the `AbstractTransactionContext` abstract class, and fully implemented in the `Database.TransactionContext` inner class. ### [](https://cs186.gitbook.io/project/#database.java) Database.java The `Database` class represents the entire database. It is the public interface of our database - users of our database can use it like a Java library. All work is done in transactions, so to use the database, a user would start a transaction with `Database#beginTransaction`, then call some of `Transaction`'s numerous methods to perform selects, inserts, and updates. For example: Copy Database db = new Database("database-dir"); try (Transaction t1 = db.beginTransaction()) { Schema s = new Schema() .add("id", Type.intType()) .add("firstName", Type.stringType(10)) .add("lastName", Type.stringType(10)); t1.createTable(s, "table1"); t1.insert("table1", 1, "Jane", "Doe"); t1.insert("table1", 2, "John", "Doe"); t1.commit(); } try (Transaction t2 = db.beginTransaction()) { // .query("table1") is how you run "SELECT * FROM table1" Iterator iter = t2.query("table1").execute(); System.out.println(iter.next()); // prints [1, John, Doe] System.out.println(iter.next()); // prints [2, Jane, Doe] t2.commit(); } db.close(); More complex queries can be found in [`src/test/java/edu/berkeley/cs186/database/TestDatabase.java`](https://github.com/berkeley-cs186/sp25-rookiedb/blob/master/src/test/java/edu/berkeley/cs186/database/TestDatabase.java) . [NextProject 0: Setup](https://cs186.gitbook.io/project/assignments/proj0) Last updated 10 months ago --- # Submitting the Assignment | CS186 Projects This project is due on **Thursday, 1/30/2025 at 11:59PM PST (GMT-8)**. [](https://cs186.gitbook.io/project/assignments/proj0/submitting#pushing-changes-to-github-classroom) Pushing changes to GitHub Classroom ---------------------------------------------------------------------------------------------------------------------------------------------- To submit a project, navigate to the cloned repo in a terminal and stage the files for your submission using `git add`. For example, in this project you would run: `git add src/main/java/edu/berkeley/cs186/database/databox/StringDataBox.java` to stage your change to `StringDataBox.java`. Once your changes are staged commit them with `git commit -m "Put your own informative commit message here"`. Finally use`git push` to push all of your changes to the remote GitHub repository created by GitHub Classroom. [](https://cs186.gitbook.io/project/assignments/proj0/submitting#submitting-to-gradescope) Submitting to Gradescope ------------------------------------------------------------------------------------------------------------------------ Once your changes are on GitHub go to the CS186 Gradescope and click on the project for which you want to submit your code. Select GitHub for the submission method (if it hasn't been selected already), and select the repository and branch with the code you want to upload and submit. If you have not done this before, then you will have to link your GitHub account to Gradescope using the "Connect to GitHub" button. If you are unable to find the appropriate repository, then you might need to go to [https://github.com/settings/applications](https://github.com/settings/applications) , click Gradescope, and grant access to the `cs186-student` organization. Note that you are only allowed to modify certain files for each assignment, and changes to other files you are not allowed to modify will be discarded when we run tests. You should make sure that all code you modify belongs to files with `TODO(proj0)` comments in them. A full list of files that you may modify for this project are as follows: * `databox/StringDataBox.java` Once you've submitted you should see a score of 1.0/1.0. If so, congratulations! You've finished your first assignment for CS 186. ### [](https://cs186.gitbook.io/project/assignments/proj0/submitting#submitting-via-upload) Submitting via upload If your GitHub account has access to many repos, the Gradescope UI might time out while trying to load which repos you have available. If this is the case for you, you can submit your code directly using via upload. You can zip up your source code with `zip -r submission.zip src/` and submit that directly to the autograder. [](https://cs186.gitbook.io/project/assignments/proj0/submitting#grading) Grading -------------------------------------------------------------------------------------- * 100% of your grade will be made up of one test released to you (the test that we provided in `database.databox.TestWelcome`) and the debugging exercise. * This project will be worth 0% of your overall grade, but failing to complete it may result in you being **administratively dropped from the class** [PreviousYour Tasks](https://cs186.gitbook.io/project/assignments/proj0/your-tasks) [NextProject 1: SQL](https://cs186.gitbook.io/project/assignments/proj1) Last updated 10 months ago --- # SQL vs. SQLite | CS186 Projects \[_Note: You can skip this section for now and come back to it while you're doing the tasks in Project 1._\] [](https://cs186.gitbook.io/project/assignments/proj1/sql-vs-sqlite#why-are-we-using-sqlite-in-this-class) Why Are We Using SQLite in This Class? ------------------------------------------------------------------------------------------------------------------------------------------------------ As you may have learned mostly SQL synax, it will not be the engine that we use for this project. Instead, we will use a more lightweight variant called SQLite. As noted on the docs of [SQLite](https://www.sqlite.org/whentouse.html) official website, _Client/server SQL database engines strive to implement a shared repository of enterprise data. They emphasize scalability, concurrency, centralization, and control. SQLite strives to provide local data storage for individual applications and devices._ As such, SQLite is very easy to set up and run, while a standard SQL engine requires setting up an entire server. Now, with downloading an app of several megabytes, you can quickly run SQL-like queries on any database you want! [](https://cs186.gitbook.io/project/assignments/proj1/sql-vs-sqlite#new-autograder) New Autograder ------------------------------------------------------------------------------------------------------- Starting this semester, we will be using a new autograder integrating [Cosette](https://cosette.cs.washington.edu/) to grade your work. The Cosette SQL Solver will check the equivalence of two SQL queries, and that implies if you are not writing in standard SQL syntax, but somehow SQLite engine understood it, Cosette will complain. And you will be deducted 5% of points for that question even if the output produced by your query matches the output of the official solution. [](https://cs186.gitbook.io/project/assignments/proj1/sql-vs-sqlite#sqlite-syntax-difference) SQLite Syntax Difference --------------------------------------------------------------------------------------------------------------------------- SQLite is a much more tolerant language than SQL, so a lot of queries that raise an error in SQL will be inferred and run successfully by SQLite. We do not wish that you utilize this tolerance to write "incorrect" queries. Next, we will go over some most common errors that students make and which Cosette Solver will complain about. Specifically: * There is support for `LEFT OUTER JOIN` but not `RIGHT OUTER` or `FULL OUTER`. * To get equivalent output to `RIGHT OUTER` you can reverse the order of the tables (i.e. `A RIGHT JOIN B` is the same as `B LEFT JOIN A`. * While it isn't required to complete this assignment, the equivalent to `FULL OUTER JOIN` can be done by `UNION`ing `RIGHT OUTER` and `LEFT OUTER` * There is no regex match (`~`) tilde operator. You can use `LIKE` instead. * There is no `ANY` or `ALL` operator. [](https://cs186.gitbook.io/project/assignments/proj1/sql-vs-sqlite#most-common-sql-errors) Most Common SQL Errors ----------------------------------------------------------------------------------------------------------------------- * Use the alias directly in `WHERE/HAVING` clause Copy SELECT birthyear, AGG(col1) AS foo, ... FROM 186_TAs GROUP BY birthyear HAVING foo > "bar" ... The problem here is that SELECT is applied after the TAs are "GROUP BY"ed and filtered by "HAVING". At the stage of "HAVING", the SQL engine doesn't understand the alias "foo" in the SELECT clause yet. * "==" Something that you may learn in the first day of a CS class includes that computers start at index 0, and "=" is the assignment operator rather than comparison. This convention will be broken in SQL world, where you should use "=" for direct comparison. * `(INNER | { LEFT | RIGHT | FULL } [OUTER]) JOIN` without a join condition In SQL, only `NATURAL JOIN` does not require a join condition as it automatically infers the common column names. It is the language's rule that you are required to give some condition with the `ON` clause. * `GROUP BY` without aggregate This is probably one of the most common mistakes made by using SQLite. Let's take a look at the following example, where we are trying to gain insight into the attendance rate of each student in 186, displayed with their sid, number of appearances in sections, along with their names. Copy SELECT s.sid, SUM(a.attendance) AS attend_rate, s.name FROM 186_students s INNER JOIN section_attendance a ON s.sid = a.sid GROUP BY s.sid ... In this SQL query, `s.sid` will be recognized without any issue, as it's the GROUP BY key; same for `SUM(a.attendance)`, as it is the Aggregate column. But how about `s.name`? It doesn't fall into either of the categories, so it is invalid to use it here. [](https://cs186.gitbook.io/project/assignments/proj1/sql-vs-sqlite#ok-so-sqlite-seems-untrustworthy) OK, so SQLite Seems Untrustworthy... ----------------------------------------------------------------------------------------------------------------------------------------------- Now, you may be very concerned that some code that gets executed in SQLite engine will fail the autograder check. Don't worry about that, as SQLite is a commercial use database engine, it is quite fault-tolerant, that is to say, it catches a lot of syntax issues. The ones mentioned above are just slightly more demanding syntax rules in SQL. So if your code passes the SQLite check, and it is following the rule taught in class, you should be good to go! [PreviousGetting Started](https://cs186.gitbook.io/project/assignments/proj1/getting-started) [NextYour Tasks](https://cs186.gitbook.io/project/assignments/proj1/your-tasks) Last updated 10 months ago --- # Project 1: SQL | CS186 Projects [Getting Started](https://cs186.gitbook.io/project/assignments/proj1/getting-started) [SQL vs. SQLite](https://cs186.gitbook.io/project/assignments/proj1/sql-vs-sqlite) [Your Tasks](https://cs186.gitbook.io/project/assignments/proj1/your-tasks) [Testing](https://cs186.gitbook.io/project/assignments/proj1/testing) [Submitting the Assignment](https://cs186.gitbook.io/project/assignments/proj1/submitting) [PreviousSubmitting the Assignment](https://cs186.gitbook.io/project/assignments/proj0/submitting) [NextGetting Started](https://cs186.gitbook.io/project/assignments/proj1/getting-started) Last updated 10 months ago --- # Testing | CS186 Projects We strongly encourage testing your code yourself. The given tests for this project are not comprehensive tests: it is possible to write incorrect code that passes them all but not get a full score due to hidden tests. You may consider testing anything that we specify in the comments or in this document that a method should do that you don't see a test already testing for, and any edge cases that you can think of. Think of what valid inputs might break your code and cause it not to perform as intended, and add a test to make sure things are working. We've put together a [video](https://drive.google.com/drive/folders/1VeqJHtAJ0fFcGvusLjXa-wyKzZ_TKb8L) to introduce you to the testing framework! To help you get started, here is one case that is _not_ in the given tests (and will be included in the hidden tests): everything should work properly even if we delete everything from the `BPlusTree`. For example, after everything is deleted and a new iterator is created, the new iterator should immediately return `false` for `hasNext`. (Note that we don't allow mutating the tree during a scan, so the behavior of an iterator created before everything was deleted is undefined, and can be handled however you like or not at all). To add a unit test, open up the appropriate test file (in `src/test/java/edu/berkeley/cs186/database/index`) and simply add a new method to the file with a `@Test` annotation. For example, Copy @Test public void testEverythingDeleted() { // your test code here } To test that your implementation throws a specific exception, you may use the following decorator: Copy @Test(expected = BPlusTreeException.class) public void testSomething() { // your test code here } Many test classes have some setup code done for you already: take a look at other tests in the file for an idea of how to write the test code. [PreviousYour Tasks](https://cs186.gitbook.io/project/assignments/proj2/your-tasks) [NextSubmitting the Assignment](https://cs186.gitbook.io/project/assignments/proj2/submission) Last updated 9 months ago --- # Project 3: Joins and Query Optimization | CS186 Projects [Getting Started](https://cs186.gitbook.io/project/assignments/proj3/getting-started) [Part 0: Skeleton Code](https://cs186.gitbook.io/project/assignments/proj3/skeleton-code) [Part 1: Join Algorithms](https://cs186.gitbook.io/project/assignments/proj3/part-1-join-algorithms) [Part 2: Query Optimization](https://cs186.gitbook.io/project/assignments/proj3/part-2-query-optimization) [Testing](https://cs186.gitbook.io/project/assignments/proj3/testing) [Submitting the Assignment](https://cs186.gitbook.io/project/assignments/proj3/submitting-the-assignment) [PreviousSubmitting the Assignment](https://cs186.gitbook.io/project/assignments/proj2/submission) [NextGetting Started](https://cs186.gitbook.io/project/assignments/proj3/getting-started) Last updated 9 months ago --- # Getting Started | CS186 Projects [](https://cs186.gitbook.io/project/assignments/proj1/getting-started#logistics) Logistics ----------------------------------------------------------------------------------------------- This project is due **Thursday, 2/6/2025 at 11:59PM PST (GMT-8)**. It is worth 5% of your overall grade in the class. **A gentle reminder that though our projects have tight release schedules, projects don't tend to take the entire time given to complete them :)** [](https://cs186.gitbook.io/project/assignments/proj1/getting-started#prerequisites) Prerequisites ------------------------------------------------------------------------------------------------------- You should watch the SQL I lecture before beginning this project. Later questions will require material from the SQL II lecture. [](https://cs186.gitbook.io/project/assignments/proj1/getting-started#academic-integrity-policy) Academic Integrity Policy ------------------------------------------------------------------------------------------------------------------------------- “_As a member of the UC Berkeley community, I act with honesty, integrity, and respect for others._” — UC Berkeley Honor Code **Read through the academic integrity guidelines** [**here**](https://cs186berkeley.net/integrityguidelines/) **.** We will be running plagiarism detection software on every submission against our own database of this semester's submissions, past submissions, and publicly hosted implementations on platforms such as GitHub and GitLab, followed by a thorough manual review process. Plagiarism on any assignment will result in a [non-reportable warning](https://conduct.berkeley.edu/wp-content/uploads/2024/01/Academic-Misconduct-Resource-Sheet-for-Students-UPDATED.pdf) and a grade penalty based on the severity of the infraction. As long as you follow the guidelines, there isn't anything to worry about here. While we do rely on software to find possible cases of academic dishonesty, every case is reviewed by multiple TAs who can filter out false positives. [](https://cs186.gitbook.io/project/assignments/proj1/getting-started#fetching-the-released-code) Fetching the released code --------------------------------------------------------------------------------------------------------------------------------- The GitHub Classroom link for this project is in the Project 1 release post on [Edstem](https://edstem.org/us/courses/70276/discussion/) . Once your private repo is set up clone the project 1 skeleton code onto your local machine. ### [](https://cs186.gitbook.io/project/assignments/proj1/getting-started#debugging-issues-with-github-classroom) Debugging Issues with GitHub Classroom Feel free to skip this section if you don't have any issues with GitHub Classroom. If you are having issues (i.e. the page froze or some error message appeared), first check if you have access to your repo at `https://github.com/cs186-student/sp25-proj1-username`, replacing `username` with your GitHub username. If you have access to your repo and the starter code is there, then you can proceed as usual. ### [](https://cs186.gitbook.io/project/assignments/proj1/getting-started#id-404-not-found) 404 Not Found If you're getting a 404 not found page when trying to access your repo, make sure you've set up your repo using the GitHub Classroom link in the Project 1 release post on [Edstem](https://edstem.org/us/courses/70276/discussion/) . If you don't have access to your repo at all after following these steps, feel free to contact the course staff on Edstem. [](https://cs186.gitbook.io/project/assignments/proj1/getting-started#required-software) Required Software --------------------------------------------------------------------------------------------------------------- ### [](https://cs186.gitbook.io/project/assignments/proj1/getting-started#sqlite3) SQLite3 Check if you already have sqlite3 instead by opening a terminal and running `sqlite3 --version`. Any version at 3.8.3 or higher should be fine. If you don't already have SQLite on your machine, the simplest way to start using it is to download a precompiled binary from the [SQLite website](http://www.sqlite.org/download.html) . #### [](https://cs186.gitbook.io/project/assignments/proj1/getting-started#windows) Windows 1. Visit the download page linked above and navigate to the section **Precompiled Binaries for Windows**. Click on the link **sqlite-tools-win32-x86-\*.zip** to download the binary. 2. Unzip the file. There should be a `sqlite3.exe` file in the directory after extraction. 3. Navigate to the folder containing the `sqlite3.exe` file and check that the version is at least 3.8.3: `cd path/to/sqlite_folder` `./sqlite3 --version` 4. Move the `sqlite3.exe` executable into your `sp25-proj1-yourname` directory (the same place as the `proj1.sql` file) #### [](https://cs186.gitbook.io/project/assignments/proj1/getting-started#macos-yosemite-10-10-el-capitan-10-11-sierra-10-12) macOS Yosemite (10.10), El Capitan (10.11), Sierra (10.12) SQLite comes pre-installed. Check that you have a version that's greater than 3.8.3 `sqlite3 --version` #### [](https://cs186.gitbook.io/project/assignments/proj1/getting-started#mac-os-x-mavericks-10-9-or-older) Mac OS X Mavericks (10.9) or older SQLite comes pre-installed, but it is the wrong version. 1. Visit the download page linked above and navigate to the section **Precompiled Binaries for Mac OS X (x86)**. Click on the link **sqlite-tools-osx-x86-\*.zip** to download the binary. 2. Unzip the file. There should be a `sqlite3` file in the directory after extraction. 3. Navigate to the folder containing the `sqlite3` file and check that the version is at least 3.8.3: `cd path/to/sqlite_folder` `./sqlite3 --version` 4. Move the `sqlite3` file into your `sp25-proj1-yourname` directory (the same place as the `proj1.sql` file) #### [](https://cs186.gitbook.io/project/assignments/proj1/getting-started#ubuntu) Ubuntu Install with `sudo apt install sqlite3` For other Linux distributions you'll need to find `sqlite3` on your appropriate package manager. Alternatively you can follow the Mac OS X (10.9) or older instructions substituting the Mac OS X binary for one from **Precompiled Binaries for Linux.** ### [](https://cs186.gitbook.io/project/assignments/proj1/getting-started#python) Python You'll need a copy of Python 3.5 or higher to run the tests for this project locally. You can check if you already have an existing copy by running `python3 --version` in a terminal. If you don't already have a working copy download and install one for your appropriate platform from [here](https://www.python.org/downloads/) . [](https://cs186.gitbook.io/project/assignments/proj1/getting-started#download-and-extract-the-data-set) Download and extract the data set ----------------------------------------------------------------------------------------------------------------------------------------------- Download the data set for this project from the course's Google Drive [here](https://drive.google.com/file/d/1fY-XKzt1sqiwEzUgQelmu7yw-1ZEpAU3/view?usp=sharing) . You should get a file called `lahman.db.zip`. Unzip the `lahman.db.zip` file inside your `sp25-proj1-yourname` directory. You should now have a `lahman.db` file in your `sp25-proj1-yourname` directory (the same place as the `proj1.sql` file) [](https://cs186.gitbook.io/project/assignments/proj1/getting-started#running-the-tests) Running the tests --------------------------------------------------------------------------------------------------------------- If you followed the instructions above you should now be able to test your code. Navigate to your project directory and try using `python3 test.py`. You should get output similar to the following: Copy FAIL q0 see diffs/q0.txt FAIL q1i see diffs/q1i.txt FAIL q1ii see diffs/q1ii.txt FAIL q1iii see diffs/q1iii.txt FAIL q1iv see diffs/q1iv.txt FAIL q2i see diffs/q2i.txt FAIL q2ii see diffs/q2ii.txt FAIL q2iii see diffs/q2iii.txt FAIL q3i see diffs/q3i.txt FAIL q3ii see diffs/q3ii.txt FAIL q3iii see diffs/q3iii.txt FAIL q4i see diffs/q4i.txt FAIL q4ii_bins_0_to_8 see diffs/q4ii_bins_0_to_8.txt FAIL q4ii_bin_9 see diffs/q4ii_bin_9.txt FAIL q4iii see diffs/q4iii.txt FAIL q4iv see diffs/q4iv.txt FAIL q4v see diffs/q4v.txt If so, move on to the next section to start the project. If you see `ERROR`instead of `FAIL` create a followup on Edstem with details from your `your_output/` folder. [PreviousProject 1: SQL](https://cs186.gitbook.io/project/assignments/proj1) [NextSQL vs. SQLite](https://cs186.gitbook.io/project/assignments/proj1/sql-vs-sqlite) Last updated 9 months ago --- # Project 2: B+ Trees | CS186 Projects [Getting Started](https://cs186.gitbook.io/project/assignments/proj2/getting-started) [Your Tasks](https://cs186.gitbook.io/project/assignments/proj2/your-tasks) [Testing](https://cs186.gitbook.io/project/assignments/proj2/testing) [Submitting the Assignment](https://cs186.gitbook.io/project/assignments/proj2/submission) [PreviousSubmitting the Assignment](https://cs186.gitbook.io/project/assignments/proj1/submitting) [NextGetting Started](https://cs186.gitbook.io/project/assignments/proj2/getting-started) Last updated 9 months ago --- # Testing | CS186 Projects You can run your answers through SQLite directly by running `sqlite3 lahman.db` to open the database and then entering `.read proj1.sql` Copy $ sqlite3 lahman.db SQLite version 3.33.0 2020-08-14 13:23:32 Enter ".help" for usage hints. sqlite> .read proj1.sql This can help you catch any syntax errors in your SQLite. To help debug your logic, we've provided output from each of the views you need to define in questions 1-4 for the data set you've been given. Your views should match ours, but note that your SQL queries should work on ANY data set. **We will test your queries on a (set of) different database(s), so it is** _**NOT**_ **sufficient to simply return these results in all cases!** Please also note that queries that join on extra, unnecessary tables will slow down queries and not receive full credit on the hidden tests. To run the test, from within the `sp25-proj1-yourname` directory: Copy $ python3 test.py $ python3 test.py -q 4ii # This would run tests for only q4ii Become familiar with the UNIX [diff](http://en.wikipedia.org/wiki/Diff) format, if you're not already, because our tests saves a simplified diff for any query executions that don't match in `diffs/`. As an example, the following output for `diffs/q1i.txt:`: Copy - 1|1|1 + Jumbo|Diaz|1984 + Walter|Young|1980 indicates that your output has an extra `1|1|1` (the `-` at the beginning means the expected output _doesn't_ include this line but your output has it) and is missing the lines `Jumbo|Diaz|1984` and `Walter|Young|1980` (the plus at the beginning means the expected output _does_ include those lines but your output is missing it). If there is neither a `+` nor `-` at the beginning then it means that the line is in both your output and the expected output (your output is correct for that line). If you care to look at the query outputs directly, ours are located in the `expected_output` directory. Your view output should be located in your solution's `your_output` directory once you run the tests. **Note:** For queries where we don't specify the order, it doesn't matter how you sort your results; we will reorder before comparing. Note, however, that our test query output is sorted for these cases, so if you're trying to compare yours and ours manually line-by-line, make sure you use the proper ORDER BY clause (you can determine this by looking in `test.py`). Different versions of SQLite handle floating points slightly differently so we also round certain floating point values in our own queries. A full list is specified here for convenience: Copy SELECT * FROM q0; SELECT * FROM q1i ORDER BY namefirst, namelast, birthyear; SELECT * FROM q1ii ORDER BY namefirst, namelast, birthyear; SELECT birthyear, ROUND(avgheight, 4), count FROM q1iii; SELECT birthyear, ROUND(avgheight, 4), count FROM q1iv; SELECT * FROM q2i; SELECT * FROM q2ii; SELECT * FROM q2iii; SELECT playerid, namefirst, namelast, yearid, ROUND(slg, 4) FROM q3i; SELECT playerid, namefirst, namelast, ROUND(lslg, 4) FROM q3ii; SELECT namefirst, namelast, ROUND(lslg, 4) FROM q3iii ORDER BY namefirst, namelast; SELECT yearid, min, max, ROUND(avg, 4) FROM q4i; SELECT * FROM q4ii WHERE binid <> 9; WITH max_salary AS (SELECT MAX(salary) AS salary FROM salaries) SELECT binid, low, ((CASE WHEN high >= salary THEN '' ELSE 'not ' END) || 'at least ' || salary) AS high, count FROM q4ii, max_salary WHERE binid = 9; SELECT yearid, mindiff, maxdiff, ROUND(avgdiff, 4) FROM q4iii; SELECT * FROM q4iv ORDER BY yearid, playerid; SELECT team, ROUND(diffAvg, 4) FROM q4v ORDER BY team; [PreviousYour Tasks](https://cs186.gitbook.io/project/assignments/proj1/your-tasks) [NextSubmitting the Assignment](https://cs186.gitbook.io/project/assignments/proj1/submitting) Last updated 10 months ago --- # Getting Started | CS186 Projects [](https://cs186.gitbook.io/project/assignments/proj2/getting-started#logistics) Logistics ----------------------------------------------------------------------------------------------- This project is due **Thursday, 2/20/2025 at 11:59PM PST (GMT-8)**. It is worth 6% of your overall grade in the class. The workload for the project is designed to be completed solo, but this semester we're allowing students to work on this project with a partner if you want to. Feel free to search for a partner [here](https://edstem.org/us/courses/70276/discussion/5999429) ! **A gentle reminder that though our projects have tight release schedules, projects don't tend to take the entire time given to complete them :)** [](https://cs186.gitbook.io/project/assignments/proj2/getting-started#prerequisites) Prerequisites ------------------------------------------------------------------------------------------------------- The disks, buffers, and files lecture covers reading from / writing to disks, the B+ tree lectures cover B+ tree operations. [](https://cs186.gitbook.io/project/assignments/proj2/getting-started#academic-integrity-policy) Academic Integrity Policy ------------------------------------------------------------------------------------------------------------------------------- “_As a member of the UC Berkeley community, I act with honesty, integrity, and respect for others._” — UC Berkeley Honor Code **Read through the academic integrity guidelines** [**here**](https://cs186berkeley.net/integrityguidelines/) **.** We will be running plagiarism detection software on every submission against our own database of this semester's submissions, past submissions, and publicly hosted implementations on platforms such as GitHub and GitLab, followed by a thorough manual review process. Plagiarism on any assignment will result in a [non-reportable warning](https://conduct.berkeley.edu/wp-content/uploads/2024/01/Academic-Misconduct-Resource-Sheet-for-Students-UPDATED.pdf) and a grade penalty based on the severity of the infraction. As long as you follow the guidelines, there isn't anything to worry about here. While we do rely on software to find possible cases of academic dishonesty, every case is reviewed by multiple TAs who can filter out false positives. [](https://cs186.gitbook.io/project/assignments/proj2/getting-started#fetching-the-released-code) Fetching the released code --------------------------------------------------------------------------------------------------------------------------------- The GitHub Classroom link for this project is in the Project 2 release post on [Edstem](https://edstem.org/us/courses/70276/discussion/) . You'll be working off a fresh copy of the RookieDB skeleton instead of reusing the one from Project 0. ### [](https://cs186.gitbook.io/project/assignments/proj2/getting-started#setting-up-your-local-development-environment) Setting up your local development environment If you're using IntelliJ, you can follow the instructions in [Project 0](https://cs186.gitbook.io/project/assignments/proj0/getting-started#setting-up-your-local-development-environment) to set up your local environment again. Once you have your environment set up, you can head to the next section [Your Tasks](https://cs186.gitbook.io/project/assignments/proj2/your-tasks) and begin working on the assignment. [](https://cs186.gitbook.io/project/assignments/proj2/getting-started#working-with-a-partner) Working with a partner ------------------------------------------------------------------------------------------------------------------------- Only one partner has to submit, but please make sure to add the other partner to the Gradescope submission. To share a newly created repository over GitHub, follow the instructions [here](https://cs186.gitbook.io/project/common/adding-a-partner-on-github) . [](https://cs186.gitbook.io/project/assignments/proj2/getting-started#debugging-issues-with-github-classroom) Debugging Issues with GitHub Classroom --------------------------------------------------------------------------------------------------------------------------------------------------------- Feel free to skip this section if you don't have any issues with GitHub Classroom. If you are having issues (i.e. the page froze or some error message appeared), first check that you have access to your repo at `https://github.com/cs186-student/sp25-proj2-username`, replacing `username` with your GitHub username (or your partner's username, if applicable). If you have access to your repo with the starter code present, then you can proceed as usual. #### [](https://cs186.gitbook.io/project/assignments/proj2/getting-started#id-404-not-found) 404 Not Found If you're getting a 404 not found page when trying to access your repo, make sure you've set up your repo using the GitHub Classroom link in the Project 2 release post on [Edstem](https://edstem.org/us/courses/70276/discussion/) . If you don't have access to your repo at all after following these steps, feel free to follow up on the Project 2 post on Edstem. [PreviousProject 2: B+ Trees](https://cs186.gitbook.io/project/assignments/proj2) [NextYour Tasks](https://cs186.gitbook.io/project/assignments/proj2/your-tasks) Last updated 9 months ago --- # Submitting the Assignment | CS186 Projects This project is due on **Thursday, 2/6/2025 at 11:59PM PST (GMT-8)**. Push your changes to your GitHub Classroom private repository and then submit through Gradescope. You may find it helpful to read through the Project 0 submission procedure again [here](https://cs186.gitbook.io/project/assignments/proj0/submitting) . Alternatively you can submit your `proj1.sql` file directly (make sure it is named `proj1.sql` or the autograder won't recognize it). A full list of files that you may modify are as follows: * `proj1.sql` [](https://cs186.gitbook.io/project/assignments/proj1/submitting#grading) Grading -------------------------------------------------------------------------------------- * 75% of your grade will be made up of tests released to you * 20% will be determined by hidden tests unreleased tests that we will run on your submission after the deadline * 5% will be determined by the correctness of your SQL syntax (see [`SQL vs. SQLite`](https://cs186.gitbook.io/project/assignments/proj1/sql-vs-sqlite#new-autograder) for more information) * This project will be worth 5% of your overall grade in the class [PreviousTesting](https://cs186.gitbook.io/project/assignments/proj1/testing) [NextProject 2: B+ Trees](https://cs186.gitbook.io/project/assignments/proj2) Last updated 10 months ago --- # Submitting the Assignment | CS186 Projects [](https://cs186.gitbook.io/project/assignments/proj2/submission#files) Files ---------------------------------------------------------------------------------- You may **not** modify the signature of any methods or classes that we provide to you, but you're free to add helper methods. You should make sure that all code you modify belongs to files with `TODO(proj2)` comments in them (e.g. don't add helper methods to DataBox). A full list of files that you may modify follows: * `src/main/java/edu/berkeley/cs186/database/index/BPlusTree.java` * `src/main/java/edu/berkeley/cs186/database/index/InnerNode.java` * `src/main/java/edu/berkeley/cs186/database/index/LeafNode.java` * `src/main/java/edu/berkeley/cs186/database/index/BPlusNode.java` (Optional) Make sure that your code does _not_ use any (non-final) static variables -- this may cause odd behavior when running with the autograder vs. in your IDE (tests run through the IDE often run with a new instance of Java for each test, so the static variables get reset, but multiple tests per Java instance may be run when using maven, where static variables _do not_ get reset). [](https://cs186.gitbook.io/project/assignments/proj2/submission#gradescope) Gradescope -------------------------------------------------------------------------------------------- Once all of your files are prepared in your repo you can submit to Gradescope through GitHub the same way you did for [Project 0](https://cs186.gitbook.io/project/assignments/proj0/submitting#pushing-changes-to-github-classroom) . [](https://cs186.gitbook.io/project/assignments/proj2/submission#submitting-via-upload) Submitting via upload ------------------------------------------------------------------------------------------------------------------ If your GitHub account has access to many repos, the Gradescope UI might time out while trying to load which repos you have available. If this is the case for you, you can submit your code directly using `via upload`: zip your source code with `python3 zip.py --assignment proj2` and submit that directly to the autograder. [](https://cs186.gitbook.io/project/assignments/proj2/submission#partners) Partners ---------------------------------------------------------------------------------------- Only one partner has to submit, but please make sure to add the other partner to the Gradescope submission. Slip minutes will be calculated individually. For example, if partner A has 10 slip minutes remaining and partner B has 20 slip minutes remaining and they submit 20 minutes late, partner A will be subject to the late penalty (1/3 off partner A's score) while partner B will have 0 remaining slip minutes and no late penalty applied to partner B's score. [](https://cs186.gitbook.io/project/assignments/proj2/submission#grade-breakdown) Grade breakdown ------------------------------------------------------------------------------------------------------ * 60% of your grade will be made up of tests released to you (the tests that we provided in `database.index.*`). * 40% of your grade will be made up of hidden, unreleased tests that we will run on your submission after the deadline. [PreviousTesting](https://cs186.gitbook.io/project/assignments/proj2/testing) [NextProject 3: Joins and Query Optimization](https://cs186.gitbook.io/project/assignments/proj3) Last updated 9 months ago --- # Your Tasks | CS186 Projects **In light of recent advancements in Generative AI, CS186 staff has developed a variety of techniques to detect usage of ChatGPT, Bard, Copilot, and other Generative AI tools. Students are cautioned to use such tools in accordance with our** [**Generative AI policy**](https://cs186berkeley.net/integrityguidelines/) **, as per the syllabus.** ![](https://cs186.gitbook.io/project/~gitbook/image?url=https%3A%2F%2F678656433-files.gitbook.io%2F%7E%2Ffiles%2Fv0%2Fb%2Fgitbook-legacy-files%2Fo%2Fassets%252F-MFVQnrLlCBowpNWJo1E%252F-MGv2sBScKfZ0PuPbu2f%252F-MGv2xZpFxxZXBGetCxm%252Fb_tree.jpg%3Falt%3Dmedia%26token%3Dec3fb0c7-14ac-4da6-acbb-35c3e8bb550b&width=768&dpr=4&quality=100&sign=386fd245&sv=2) Datarake In this project you'll be implementing B+ tree indices. Since you'll be diving into the codebase for the first time, we've provided an introduction to the skeleton code. [](https://cs186.gitbook.io/project/assignments/proj2/your-tasks#understanding-the-skeleton-code) Understanding the Skeleton Code -------------------------------------------------------------------------------------------------------------------------------------- ### [](https://cs186.gitbook.io/project/assignments/proj2/your-tasks#databox) DataBox Every modern database supports a variety of data types to use in records, and RookieDB is no exception. For consistency and convenience, most implementations choose to have their own internal representation of their data types built on top of the implementation language's defaults. In RookieDB, we represent them using data boxes. A data box can contain data of the following types: * `Boolean` (1 byte) * `Int` (4 bytes) * `Float` (4 bytes) * `Long` (8 bytes) * `String(N)` (N bytes) You'll be working with the abstract [`DataBox`](https://github.com/berkeley-cs186/sp25-rookiedb/blob/master/src/main/java/edu/berkeley/cs186/database/databox/DataBox.java) class, which implements `Comparable`. You may find it useful to review how the [Comparable interface](https://docs.oracle.com/javase/8/docs/api/java/lang/Comparable.html) works for this project. ### [](https://cs186.gitbook.io/project/assignments/proj2/your-tasks#recordid) RecordId A record in a table is uniquely identified by its page number (the number of the page on which it resides) and its entry number (the record's index on the page). These two numbers (`pageNum`, `entryNum`) comprise a [`RecordId`](https://github.com/berkeley-cs186/sp25-rookiedb/blob/master/src/main/java/edu/berkeley/cs186/database/table/RecordId.java) . For this project, we'll be using record IDs in our leaf nodes as pointers to records in the data pages. ### [](https://cs186.gitbook.io/project/assignments/proj2/your-tasks#index) Index The [`index`](https://github.com/berkeley-cs186/sp25-rookiedb/tree/master/src/test/java/edu/berkeley/cs186/database/index) directory contains a partial implementation of an Alternative 2 B+ tree, an implementation that you will complete in this project. Some of the important files in this directory are: * [`BPlusTree.java`](https://github.com/berkeley-cs186/sp25-rookiedb/blob/master/src/main/java/edu/berkeley/cs186/database/index/BPlusTree.java) - This file contains the class that manages the structure of the B+ tree. Every B+ tree maps keys of a type `DataBox` (a single value or "cell" in a table) to values of type `RecordId` (identifiers for records on data pages). An example of inserting and a retrieving records using keys can be found in the comments at [`BPlusTree.java line 130`](https://github.com/berkeley-cs186/sp25-rookiedb/blob/master/src/main/java/edu/berkeley/cs186/database/index/BPlusTree.java#L130) * [`BPlusNode.java`](https://github.com/berkeley-cs186/sp25-rookiedb/blob/master/src/main/java/edu/berkeley/cs186/database/index/BPlusNode.java) - A B+ node represents a node in the B+ tree, and contains similar methods to `BPlusTree` such as `get`, `put` and `delete`. `BPlusNode` is an abstract class and is implemented as either a `LeafNode` or an `InnerNode` * * [`LeafNode.java`](https://github.com/berkeley-cs186/sp25-rookiedb/blob/master/src/main/java/edu/berkeley/cs186/database/index/LeafNode.java) - A leaf node is a node with no descendants that contains pairs of keys and Record IDs that point to the relevant records in the table, as well a pointer to its right sibling. More details can be found [`LeafNode.java line 15`](https://github.com/berkeley-cs186/sp25-rookiedb/blob/master/src/main/java/edu/berkeley/cs186/database/index/LeafNode.java#L15) * [`InnerNode.java`](https://github.com/berkeley-cs186/sp25-rookiedb/blob/master/src/main/java/edu/berkeley/cs186/database/index/InnerNode.java) - An inner node is a node that stores keys and pointers (page numbers) to child nodes (which themselves may either be an inner node or a leaf node). More details can be found [`InnerNode.java line 15`](https://github.com/berkeley-cs186/sp25-rookiedb/blob/master/src/main/java/edu/berkeley/cs186/database/index/InnerNode.java#L15) * [`BPlusTreeMetadata.java`](https://github.com/berkeley-cs186/sp25-rookiedb/blob/master/src/main/java/edu/berkeley/cs186/database/index/BPlusTreeMetadata.java) \- This file contains a class that stores useful information such as the order and height of the tree. You can access instances of this class using the `this.metadata` instance variables available in all of the classes listed above. #### [](https://cs186.gitbook.io/project/assignments/proj2/your-tasks#implementation-details) Implementation Details You should read through all of the code in the [`index`](https://github.com/berkeley-cs186/sp25-rookiedb/tree/master/src/main/java/edu/berkeley/cs186/database/index) directory. Many comments contain critical information on how you must implement certain functions. For example, `BPlusNode::put` specifies how to redistribute entries after a split. You are responsible for reading these comments. Here are a few of the most notable points: * Generally, B+ trees **do** support duplicate keys. However, our implementation of B+ trees **does not** support duplicate keys. You will throw an exception whenever a duplicate key is inserted. But you **don't** have to do so for deleting an absent key. * Our implementation of B+ trees assumes that inner nodes and leaf nodes can be serialized on a single page. You **do not** have to support nodes that span multiple pages. * Our implementation of `delete` **does not** rebalance the tree. Thus, the invariant that all non-root leaf nodes in a B+ tree of order `d` contain between `d` and `2d` entries is broken. Note that actual B+ trees **do rebalance** after deletion, but we will **not** be implementing rebalancing trees in this project for the sake of simplicity. ### [](https://cs186.gitbook.io/project/assignments/proj2/your-tasks#lockcontext-objects) LockContext objects There are a few parts in this project where a method will take in objects of the type `LockContext`. You don't need to worry too much about these objects right now; they will become more relevant in Project 4. If there are any methods you wish to call that require these objects, use the ones passed in to the method you are implementing, or defined in the class of the method you are implementing (`this.lockContext` for `BPlusTree` and `this.treeContext` for `InnerNode` and `LeafNode`). ### [](https://cs186.gitbook.io/project/assignments/proj2/your-tasks#optional-less-than-t-greater-than-objects) Optional objects This part of the project makes extensive use of `Optional` objects. We recommend reading through the documentation [here](https://docs.oracle.com/javase/8/docs/api/java/util/Optional.html) to get a feel for them. In particular, we use `Optional`s for values that may not necessarily be present. For example, a call to `get` may not yield any value for a key that doesn't correspond to a record, in which case an `Optional.empty()` would be returned. If the key did correspond to a record, a populated `Optional.of(RecordId(pageNum, entryNum))` would be returned instead. ### [](https://cs186.gitbook.io/project/assignments/proj2/your-tasks#project-structure-diagram) Project Structure Diagram Here's a diagram that shows the structure of the project with color-coded components. You may find it helpful to refer back to this after you start working on the tasks. ![](https://cs186.gitbook.io/project/~gitbook/image?url=https%3A%2F%2F678656433-files.gitbook.io%2F%7E%2Ffiles%2Fv0%2Fb%2Fgitbook-legacy-files%2Fo%2Fassets%252F-MFVQnrLlCBowpNWJo1E%252Fsync%252Fb5164abe18f4d8a7a0174ce8119da13706554570.jpg%3Fgeneration%3D1599942738303255%26alt%3Dmedia&width=768&dpr=4&quality=100&sign=4fb0ffd3&sv=2) (Click on the image to zoom in) * Green boxes: functions that you need to implement * White boxes: next to each function, contains a quick summary of the important points that you need to consider for that function. **To find more detailed descriptions look at the comments of each method**. * Orange boxes: hints for each function which may point you to helper functions. [](https://cs186.gitbook.io/project/assignments/proj2/your-tasks#your-tasks) Your Tasks -------------------------------------------------------------------------------------------- Based on student feedback from previous semesters, we estimate that this project will take approximately 15-20 hours to complete. We have also included a star-based difficulty ranking per task, relative to the rest of the project, as a guide for pacing your work. _Please note that every student works at a different pace, and it's absolutely ok to spend more or less time on the project than the provided estimates!_ ### [](https://cs186.gitbook.io/project/assignments/proj2/your-tasks#task-1-leafnode-frombytes) Task 1: `LeafNode::fromBytes` _Difficulty: ★☆☆☆☆_ You should first implement the `fromBytes` in `LeafNode`. This method reads a `LeafNode` from a page. For information on how a leaf node is serialized, see `LeafNode::toBytes`. For an example on how to read a node from disk, see `InnerNode::fromBytes`. Your code should be similar to the inner node version but should account for the differences between how inner nodes and leaf nodes are serialized. You may find the documentation in [`ByteBuffer.java`](https://github.com/berkeley-cs186/sp25-rookiedb/blob/master/src/main/java/edu/berkeley/cs186/database/common/ByteBuffer.java#L5) helpful. Once you have implemented `fromBytes` you should be passing `TestLeafNode::testToAndFromBytes`. ### [](https://cs186.gitbook.io/project/assignments/proj2/your-tasks#task-2-get-getleftmostleaf-put-remove) Task 2: `get`, `getLeftmostLeaf`, `put`, `remove` _Difficulty: ★★★★★_ After implementing `fromBytes`, you will need to implement the following methods in `LeafNode`, `InnerNode`, and `BPlusTree`: * `get` * `getLeftmostLeaf` (`LeafNode` and `InnerNode` only) * `put` * `remove` For more information on what these methods should do refer to the comments in `BPlusTree` and `BPlusNode`. Each of these methods, although split into three different classes, can be viewed as one recursive action each - the `BPlusTree` method starts the call, the `InnerNode` method is the recursive case, and the `LeafNode` method is the base case. It's suggested that you work on one method at a time (over all three classes). We've provided a `sync()` method in `LeafNode` and `InnerNode`. The purpose of `sync()` is to ensure that representation of a node in our buffers is up-to-date with the representation of the node in program memory. **Do not forget to call** `**sync()**` **when implementing the two mutating methods** (`put` and `remove`); it's easy to forget. ### [](https://cs186.gitbook.io/project/assignments/proj2/your-tasks#task-3-scans) Task 3: Scans _Difficulty: ★★★☆☆_ You will need to implement the following methods in `BPlusTree`: * `scanAll` * `scanGreaterEqual` In order to implement these, you will have to complete the [`BPlusTreeIterator`](https://github.com/berkeley-cs186/sp25-rookiedb/blob/master/src/main/java/edu/berkeley/cs186/database/index/BPlusTree.java#L422) inner class in `BPlusTree.java`to complete these two methods. After completing this task, you should be passing `TestBPlusTree::testRandomPuts` Your implementation **does not** have to account for the tree being modified during a scan. For the time being you can think of this as there being a lock that prevents scanning and mutation from overlapping, and that the behavior of iterators created before a modification is undefined (you can handle any problems with these iterators however you like, or not at all). ### [](https://cs186.gitbook.io/project/assignments/proj2/your-tasks#task-4-bulk-load) Task 4: Bulk Load _Difficulty: ★★★☆☆_ Much like the methods from the Task 2 you'll need to implement `bulkLoad` within all three of `LeafNode`, `InnerNode`, and `BPlusTree`. Since bulk loading is a mutating operation you will need to call `sync()`. Be sure to read the instructions in [`BPluNode::bulkLoad`](https://github.com/berkeley-cs186/sp25-rookiedb/blob/master/src/main/java/edu/berkeley/cs186/database/index/BPlusNode.java#L162) carefully to ensure you split your nodes properly. We've provided a visualization of bulk loading for an order 2 tree with fill factor 0.75 ([powerpoint slides here](https://docs.google.com/presentation/d/1_ghdp60NV6XRHnutFAL20k2no6tr2PosXGokYtR8WwU/edit?usp=sharing) ): ![](https://cs186.gitbook.io/project/~gitbook/image?url=https%3A%2F%2F678656433-files.gitbook.io%2F%7E%2Ffiles%2Fv0%2Fb%2Fgitbook-x-prod.appspot.com%2Fo%2Fspaces%252F-MFVQnrLlCBowpNWJo1E%252Fuploads%252Fgit-blob-76b3592e0be17a7ee3aa0310295744d048fc8b0a%252Fvis%2520%281%29%2520%281%29%2520%282%29%2520%283%29%2520%283%29%2520%282%29%2520%285%29.gif%3Falt%3Dmedia%26token%3D2a21e1ea-abe5-455e-bda8-6a3688206f8a&width=768&dpr=4&quality=100&sign=3ca5dcba&sv=2) After this, you should pass all the Project 2 tests we have provided to you (and any you add yourselves)! These are all the provided tests in [`database.index.*`](https://github.com/berkeley-cs186/sp25-rookiedb/tree/master/src/test/java/edu/berkeley/cs186/database/index) . [](https://cs186.gitbook.io/project/assignments/proj2/your-tasks#debugging) Debugging ------------------------------------------------------------------------------------------ To help you debug we have implemented the `toDotPDFFile` method of `BPlusTree`. You can add a call to this method in a test to generate a PDF file of your B+ tree. For example, Copy BPlusTree tree = ... tree.toDotPDFFile("tree.pdf"); If you get `"Cannot run program "dot"`, you need to install [GraphViz](https://graphviz.gitlab.io/download/) . GraphViz is a software package that generates visualizations of network style graphs. [](https://cs186.gitbook.io/project/assignments/proj2/your-tasks#putting-it-all-together) Putting it all together ---------------------------------------------------------------------------------------------------------------------- Navigate to `CommandLineInterface.java` and run the code to start our CLI. This should open a new panel in IntelliJ at the bottom. Click on this panel. We've provided 3 demo tables (`Students`, `Courses`, `Enrollments`). Recall from Project 0 that we can run queries on this CLI. Let's try running the following query: Copy SELECT * FROM Students AS s WHERE s.sid = 1; After implemting our B+ Tree index in Project 2, we can now create indices on columns of tables! Let's try running the command below: Copy CREATE INDEX on Students(sid); This creates an index on the sid column of the `Students` table. Unfortuantely, we do not have enough demo data to actually observe much speedup. Theoretically, however, we can create indices on certain columns to speed up lookup queries. Let's run `exit` to terminate the CLI. [](https://cs186.gitbook.io/project/assignments/proj2/your-tasks#youre-done) You're done! ---------------------------------------------------------------------------------------------- Move on to the next sections for details on testing and on submitting the assignment. [PreviousGetting Started](https://cs186.gitbook.io/project/assignments/proj2/getting-started) [NextTesting](https://cs186.gitbook.io/project/assignments/proj2/testing) Last updated 9 months ago --- # Your Tasks | CS186 Projects ![](https://cs186.gitbook.io/project/~gitbook/image?url=https%3A%2F%2F678656433-files.gitbook.io%2F%7E%2Ffiles%2Fv0%2Fb%2Fgitbook-x-prod.appspot.com%2Fo%2Fspaces%252F-MFVQnrLlCBowpNWJo1E%252Fuploads%252Fgit-blob-de8dc7f3bdb52e98c8e1652bbab12708141ff1ac%252Fdatabaseball%2520%282%29%2520%283%29%2520%283%29%2520%283%29%2520%282%29%2520%288%29.jpg%3Falt%3Dmedia&width=768&dpr=4&quality=100&sign=60eb45dc&sv=2) Databaseball In this project we will be working with the commonly-used [Lahman baseball statistics database](http://seanlahman.com/) (our friends at the San Francisco Giants tell us they use it!) The database contains pitching, hitting, and fielding statistics for Major League Baseball from 1871 through 2019. It includes data from the two current leagues (American and National), four other "major" leagues (American Association, Union Association, Players League, and Federal League), and the National Association of 1871-1875. At this point you should be able to run SQLite and view the database using either `./sqlite3 -header lahman.db` (if in the previous section you downloaded a precompiled binary) or `sqlite3 -header lahman.db` otherwise. If you're using windows and you find that the previous command doesn't work, try running `winpty ./sqlite3 lahman.db`. Copy $ sqlite3 lahman.db SQLite version 3.33.0 2020-08-14 13:23:32 Enter ".help" for usage hints. sqlite> .tables Try running a few sample commands in the SQLite console and see what they do: Copy sqlite> .schema people Copy sqlite> SELECT playerid, namefirst, namelast FROM people; Copy sqlite> SELECT COUNT(*) FROM fielding; [](https://cs186.gitbook.io/project/assignments/proj1/your-tasks#understanding-the-schema) Understanding the Schema ------------------------------------------------------------------------------------------------------------------------ The database is comprised of the following main tables: Copy People - Player names, date of birth (DOB), and biographical info Batting - batting statistics Pitching - pitching statistics Fielding - fielding statistics It is supplemented by these tables: Copy AllStarFull - All-Star appearances HallofFame - Hall of Fame voting data Managers - managerial statistics Teams - yearly stats and standings BattingPost - post-season batting statistics PitchingPost - post-season pitching statistics TeamFranchises - franchise information FieldingOF - outfield position data FieldingPost- post-season fielding data FieldingOFsplit - LF/CF/RF splits ManagersHalf - split season data for managers TeamsHalf - split season data for teams Salaries - player salary data SeriesPost - post-season series information AwardsManagers - awards won by managers AwardsPlayers - awards won by players AwardsShareManagers - award voting for manager awards AwardsSharePlayers - award voting for player awards Appearances - details on the positions a player appeared at Schools - list of colleges that players attended CollegePlaying - list of players and the colleges they attended Parks - list of major league ballparks HomeGames - Number of homegames played by each team in each ballpark For more detailed information, see the [docs online](https://www.dropbox.com/scl/fi/9i2nhlskvfkqy7mbuqem7/readme2023.txt?rlkey=odnwx7ujztm0z4ob8dmggfcr0&e=1&dl=0) . [](https://cs186.gitbook.io/project/assignments/proj1/your-tasks#writing-queries) Writing Queries ------------------------------------------------------------------------------------------------------ We've provided a skeleton solution file, `proj1.sql`, to help you get started. In the file, you'll find a `CREATE VIEW` statement for each part of the first 4 questions below, specifying a particular view name (like `q2i`) and list of column names (like `playerid`, `lastname`). The view name and column names constitute the interface against which we will grade this assignment. In other words, _don't change or remove these names_. Your job is to fill out the view definitions in a way that populates the views with the right tuples. For example, consider Question 0: "What is the highest `era` ([earned run average](https://en.wikipedia.org/wiki/Earned_run_average) ) recorded in baseball history?". In the `proj1.sql` file we provide: Copy CREATE VIEW q0(era) AS SELECT 1 -- replace this line ; You would edit this with your answer, keeping the schema the same: Copy -- solution you provide CREATE VIEW q0(era) AS SELECT MAX(era) FROM pitching ; To complete the project, create a view for `q0` as above (via copy-paste), and for all of the following queries, which you will need to write yourself. You can confirm the test is now passing by running `python3 test.py -q 0` Copy > python3 test.py -q 0 PASS q0 More details on testing can be found in the [Testing](https://cs186.gitbook.io/project/assignments/proj1/testing) section. [](https://cs186.gitbook.io/project/assignments/proj1/your-tasks#your-tasks) Your Tasks -------------------------------------------------------------------------------------------- Based on student feedback from previous semesters, we estimate that this project will take approximately 5-10 hours to complete. We have also included a star-based difficulty ranking per task, relative to the rest of the project, as a guide for pacing your work. _Please note that every student works at a different pace, and it's absolutely ok to spend more or less time on the project than the provided estimates!_ ### [](https://cs186.gitbook.io/project/assignments/proj1/your-tasks#task-1-basics) Task 1: **Basics** _Difficulty: ★☆☆☆☆_ **i.** In the `people` table, find the `namefirst`, `namelast` and `birthyear` for all players with weight greater than 300 pounds. **ii.** Find the `namefirst`, `namelast` and `birthyear` of all players whose `namefirst` field contains a space. Order the results by `namefirst`, breaking ties with `namelast` both in ascending order **iii.** From the `people` table, group together players with the same `birthyear`, and report the `birthyear`, average `height`, and number of players for each `birthyear`. Order the results by `birthyear` in _ascending_ order. Note: Some birth years have no players; your answer can simply skip those years. In some other years, you may find that all the players have a `NULL` height value in the dataset (i.e. `height IS NULL`); your query should return `NULL` for the height in those years. **iv.** Following the results of part iii, now only include groups with an average height > `70`. Again order the results by `birthyear` in _ascending_ order. ### [](https://cs186.gitbook.io/project/assignments/proj1/your-tasks#task-2-hall-of-fame-schools) Task 2: **Hall of Fame Schools** _Difficulty: ★★☆☆☆_ **i.** Find the `namefirst`, `namelast`, `playerid` and `yearid` of all people who were successfully inducted into the Hall of Fame in _descending_ order of `yearid`. Break ties on `yearid` by `playerid` (ascending). **ii.** Find the people who were successfully inducted into the Hall of Fame and played in college at a school located in the state of California. For each person, return their `namefirst`, `namelast`, `playerid`, `schoolid`, and `yearid` in _descending_ order of `yearid`. Break ties on `yearid` by `schoolid, playerid` (ascending). For this question, `yearid` refers to the year of induction into the Hall of Fame. * Note: a player may appear in the results multiple times (once per year in a college in California). **iii.** Find the `playerid`, `namefirst`, `namelast` and `schoolid` of all people who were successfully inducted into the Hall of Fame -- whether or not they played in college. Return people in _descending_ order of `playerid`. Break ties on `playerid` by `schoolid` (ascending). (Note: `schoolid` should be `NULL` if they did not play in college.) ### [](https://cs186.gitbook.io/project/assignments/proj1/your-tasks#task-3-sabermetrics) Task 3: [**SaberMetrics**](https://en.wikipedia.org/wiki/Sabermetrics) _Difficulty: ★★★★☆_ **i.** Find the `playerid`, `namefirst`, `namelast`, `yearid` and single-year `slg` (Slugging Percentage) of the players with the 10 best annual Slugging Percentage recorded over all time. A player can appear multiple times in the output. For example, if Babe Ruth’s `slg` in 2000 and 2001 both landed in the top 10 best annual Slugging Percentage of all time, then we should include Babe Ruth twice in the output. For statistical significance, only include players with more than 50 at-bats in the season. Order the results by `slg` descending, and break ties by `yearid, playerid` (ascending). * Baseball note: Slugging Percentage is not provided in the database; it is computed according to a [simple formula](https://en.wikipedia.org/wiki/Slugging_percentage) you can calculate from the data in the database. * SQL note: You should compute `slg` properly as a floating point number---you'll need to figure out how to convince SQL to do this! * Data set note: The online documentation `batting` mentions two columns `2B` and `3B`. On your local copy of the data set these have been renamed `H2B` and `H3B` respectively (columns starting with numbers are tedious to write queries on). * Data set note: The column `H` o f the `batting` table represents all hits = (# singles) + (# doubles) + (# triples) + (# home runs), not just (# singles) so you’ll need to account for some double-counting * If a player played on multiple teams during the same season (for example `anderma02` in 2006) treat their time on each team separately for this calculation **ii.** Following the results from Part i, find the `playerid`, `namefirst`, `namelast` and `lslg` (Lifetime Slugging Percentage) for the players with the top 10 Lifetime Slugging Percentage. Lifetime Slugging Percentage (LSLG) uses the same formula as Slugging Percentage (SLG), but it uses the number of singles, doubles, triples, home runs, and at bats each player has over their entire career, rather than just over a single season. Note that the database only gives batting information broken down by year; you will need to convert to total information across all time (from the earliest date recorded up to the last date recorded) to compute `lslg`. Order the results by `lslg` (descending) and break ties by `playerid` (ascending) * Note: Make sure that you only include players with more than 50 at-bats across their lifetime. **iii.** Find the `namefirst`, `namelast` and Lifetime Slugging Percentage (`lslg`) of batters whose lifetime slugging percentage is higher than that of San Francisco favorite Willie Mays. You may include Willie Mays' `playerid` in your query (`mayswi01`), but you _may not_ include his slugging percentage -- you should calculate that as part of the query. (Test your query by replacing `mayswi01` with the playerid of another player -- it should work for that player as well! We may do the same in the autograder.) * Note: Make sure that you still only include players with more than 50 at-bats across their lifetime. _Just for fun_: For those of you who are baseball buffs, variants of the above queries can be used to find other more detailed SaberMetrics, like [Runs Created](https://en.wikipedia.org/wiki/Runs_created) or [Value Over Replacement Player](https://en.wikipedia.org/wiki/Value_over_replacement_player) . Wikipedia has a nice page on [baseball statistics](https://en.wikipedia.org/wiki/Baseball_statistics) ; most of these can be computed fairly directly in SQL. _Also just for fun_: SF Giants VP of Baseball Operations, [Yeshayah Goldfarb](https://www.mlb.com/giants/team/front-office/yeshaya-goldfarb) , suggested the following: > Using the Lahman database as your guide, make an argument for when MLBs “Steroid Era” started and ended. There are a number of different ways to explore this question using the data. (Please do not include your "just for fun" answers in your solution file! They will break the autograder.) ### [](https://cs186.gitbook.io/project/assignments/proj1/your-tasks#task-4-salaries) Task 4: **Salaries** _Difficulty: ★★★★★_ **i.** Find the `yearid`, min, max and average of all player salaries for each year recorded, ordered by `yearid` in _ascending_ order. **ii.** For salaries in 2016, compute a [histogram](https://en.wikipedia.org/wiki/Histogram) . Divide the salary range into 10 equal bins from min to max, with `binid`s 0 through 9, and count the salaries in each bin. Return the `binid`, `low` and `high` boundaries for each bin, as well as the number of salaries in each bin, with results sorted from smallest bin to largest. * Note: `binid` 0 corresponds to the lowest salaries, and `binid` 9 corresponds to the highest. The ranges are left-inclusive (i.e. `[low, high)`) -- so the `high` value is excluded. For example, if bin 2 has a `high` value of 100000, salaries of 100000 belong in bin 3, and bin 3 should have a `low` value of 100000.\ \ * Note: The `high` value for bin 9 may be inclusive).\ \ * Note: The test for this question is broken into two parts. Use `python3 test.py -q 4ii_bins_0_to_8` and `python3 test.py -q 4ii_bin_9` to run the tests\ \ * Hidden testing advice: we will be testing the case where a bin has zero player salaries in it. The correct behavior in this case is to display the correct `binid`, `low` and `high` with a `count` of zero, NOT just excluding the bin altogether.\ \ \ Some useful information:\ \ * In the lahman.db, you may find it helpful to use the provided helper table `binids`, which contains all the possible `binid`s. Get a feel of what the data looks like by running `SELECT * FROM binids;` in a sqlite terminal. We'll only be testing with these possible binids (there aren't any hidden tests using say, 100 bins) so using the hardcoded table is fine\ \ * If you want to take the [floor](https://en.wikipedia.org/wiki/Floor_and_ceiling_functions)\ of a positive float value you can do `CAST (some_value AS INT)`\ \ \ **iii.** Now let's compute the Year-over-Year change in min, max and average player salary. For each year with recorded salaries after the first, return the `yearid`, `mindiff`, `maxdiff`, and `avgdiff` with respect to the previous year. Order the output by `yearid` in _ascending_ order. (You should omit the very first year of recorded salaries from the result.)\ \ **iv.** In 2001, the max salary went up by over $6 million. Write a query to find the players that had the max salary in 2000 and 2001. Return the `playerid`, `namefirst`, `namelast`, `salary` and `yearid` for those two years. If multiple players tied for the max salary in a year, return all of them.\ \ * Note on notation: you are computing a relational variant of the [argmax](https://en.wikipedia.org/wiki/Arg_max)\ for each of those two years.\ \ \ **v.** Each team has at least 1 All Star and may have multiple. For each team in the year 2016, give the `teamid` and `diffAvg` (the difference between the team's highest paid all-star's salary and the team's lowest paid all-star's salary).\ \ * Note: Due to some discrepancies in the database, please draw your team names from the All-Star table (so use `allstarfull.teamid` in the SELECT statement for this).\ \ \ [](https://cs186.gitbook.io/project/assignments/proj1/your-tasks#youre-done)\ \ You're done!\ \ \ ----------------------------------------------------------------------------------------------\ \ Rerun `python3 test.py` to see if you're passing tests. If so, follow the instructions in the next section to submit your work.\ \ [PreviousSQL vs. SQLite](https://cs186.gitbook.io/project/assignments/proj1/sql-vs-sqlite)\ [NextTesting](https://cs186.gitbook.io/project/assignments/proj1/testing)\ \ Last updated 9 months ago --- # Part 2: Query Optimization | CS186 Projects ![](https://cs186.gitbook.io/project/~gitbook/image?url=https%3A%2F%2F678656433-files.gitbook.io%2F%7E%2Ffiles%2Fv0%2Fb%2Fgitbook-legacy-files%2Fo%2Fassets%252F-MFVQnrLlCBowpNWJo1E%252Fsync%252Fb196fa30aebce79b501f167603bba450ca564d5f.png%3Fgeneration%3D1601083825126557%26alt%3Dmedia&width=768&dpr=4&quality=100&sign=ef644cec&sv=2) Dataspace In this part, you will implement a piece of a relational query optimizer: Plan space search. [](https://cs186.gitbook.io/project/assignments/proj3/part-2-query-optimization#overview-plan-space-search) Overview: Plan Space Search -------------------------------------------------------------------------------------------------------------------------------------------- You will now search the plan space of some cost estimates. For our database, this is similar to System R: the set of all left-deep trees, avoiding Cartesian products where possible. Unlike System R, we do not consider interesting orders, and further, we completely disallow Cartesian products in all queries. To search the plan space, we will utilize the dynamic programming algorithm used in the Selinger optimizer. Before you begin, you should have a good idea of how the `QueryPlan` class is used (see the [Skeleton Code](https://cs186.gitbook.io/project/assignments/proj3/skeleton-code) section) and how query operators fit together. For example, to implement a simple query with a single selection predicate: Copy /** * SELECT * FROM myTableName WHERE stringAttr = 'CS 186' */ QueryOperator source = SequentialScanOperator(transaction, myTableName); QueryOperator select = SelectOperator(source, 'stringAttr', PredicateOperator.EQUALS, "CS 186"); int estimatedIOCost = select.estimateIOCost(); // estimate I/O cost Iterator iter = select.iterator(); // iterator over the results A tree of `QueryOperator` objects is formed when we have multiple tables joined together. The current implementation of `QueryPlan#execute`, which is called by the user to run the query, is to join all tables in the order given by the user: if the user says `SELECT * FROM t1 JOIN t2 ON .. JOIN t3 ON ..`, then it scans `t1`, then joins `t2`, then joins `t3`. This will perform poorly in many cases, so your task is to implement the dynamic programming algorithm to join the tables together in a better order. You will have to implement the `QueryPlan#execute` method. To do so, you will also have to implement two helper methods: `QueryPlan#minCostSingleAccess` (pass 1 of the dynamic programming algorithm) and `QueryPlan#minCostJoins` (pass i > 1). [](https://cs186.gitbook.io/project/assignments/proj3/part-2-query-optimization#visualizing-the-naive-query-optimizer) Visualizing the Naive Query Optimizer ----------------------------------------------------------------------------------------------------------------------------------------------------------------- This section is optional, but we recommend that you run through the steps. Our database supports an `EXPLAIN` command which outputs the query plan for a given query. Let's test out our current query optimizer! Navigate to `CommandLineInterface.java` and run the code to start our CLI. This should open a new panel in IntelliJ at the bottom. Click on this panel. We've provided 3 demo tables (Students, Courses, Enrollments). Let's try running the following query: Copy SELECT * FROM Students AS s INNER JOIN Enrollments AS e ON s.sid = e.sid; Let's display the query plan used to execute the above query by running the following command: Copy EXPLAIN SELECT * FROM Students AS s INNER JOIN Enrollments AS e ON s.sid = e.sid; An estimated 603 I/Os, a very costly query! Our current naive query optimizer joins the table in the order given and only uses SNLJs for joins, which can become very expensive. Let's try a more complex query. The following computes the distribution of majors in CS186. Copy SELECT c.name, s.major, COUNT(*) FROM Students AS s INNER JOIN Enrollments AS e ON s.sid = e.sid INNER JOIN Courses AS c ON e.cid = c.cid WHERE c.name = 'CS 186' GROUP BY s.major, c.name; Like before, let's inspect the query plan. Copy EXPLAIN SELECT c.name, s.major, COUNT(*) FROM Students AS s INNER JOIN Enrollments AS e ON s.sid = e.sid INNER JOIN Courses AS c ON e.cid = c.cid WHERE c.name = 'CS 186' GROUP BY s.major, c.name; This query also performs very poorly. Run `exit` to terminate the CLI. In the next few tasks, we'll implement an optimizer that will drastically improve the cost of our queries! [](https://cs186.gitbook.io/project/assignments/proj3/part-2-query-optimization#your-tasks) Your Tasks ----------------------------------------------------------------------------------------------------------- Note that you may **not** modify the signature of any methods or classes that we provide to you, but you're free to add helper methods. Also, you should only modify `query/QueryPlan.java` in this part. Based on student feedback from previous semesters, we estimate that this part of the project will take approximately 15-20 hours to complete. We have also included a star-based difficulty ranking per task, relative to the rest of the project, as a guide for pacing your work. _Please note that every student works at a different pace, and it's absolutely ok to spend more or less time on the project than the provided estimates!_ ### [](https://cs186.gitbook.io/project/assignments/proj3/part-2-query-optimization#task-5-single-table-access-selection-pass-1) Task 5: Single Table Access Selection (Pass 1) _Difficulty: ★★★☆☆_ Recall that the first part of the search algorithm involves finding the lowest estimated cost plans for accessing each table individually (pass i involves finding the best plans for sets of i tables, so pass 1 involves finding the best plans for sets of 1 table). This functionality should be implemented in the `QueryPlan#minCostSingleAccess` helper method, which takes a table and returns the optimal `QueryOperator` for scanning the table. In our database, we only consider two types of table scans: a sequential, full table scan (`SequentialScanOperator`) and an index scan (`IndexScanOperator`), which requires an index and filtering predicate on a column. You should first calculate the estimated I/O cost of a sequential scan, since this is always possible (it's the default option: we only move away from it in favor of index scans if the index scan is both possible and more efficient). Then, if there are any indices on any column of the table that we have a selection predicate on, you should calculate the estimated I/O cost of doing an index scan on that column. If any of these are more efficient than the sequential scan, take the best one. Finally, as part of a heuristic-based optimization covered in class, you should push down any selection predicates that involve solely the table (see `QueryPlan#addEligibleSelections`). This should leave you with a query operator beginning with a sequential or index scan operator, followed by zero or more `SelectOperator`s. After you have implemented `QueryPlan#minCostSingleAccess`, you should be passing all of the tests in `TestSingleAccess`. These tests do not involve any joins. ### [](https://cs186.gitbook.io/project/assignments/proj3/part-2-query-optimization#task-6-join-selection-pass-i-greater-than-1) **Task 6: Join Selection (Pass i > 1)** _Difficulty: ★★★★★_ Recall that for i > 1, pass i of the dynamic programming algorithm takes in optimal plans for joining together all possible sets of i - 1 tables (except those involving cartesian products), and returns optimal plans for joining together all possible sets of i tables (again excluding those with cartesian products). We represent the state between two passes as a mapping from sets of strings (table names) to the corresponding optimal `QueryOperator`. You will need to implement the logic for pass i (i > 1) of the search algorithm in the `QueryPlan#minCostJoins` helper method. This method should, given a mapping from sets of i - 1 tables to the optimal plan for joining together those i - 1 tables, return a mapping from sets of i tables to the optimal left-deep plan for joining all sets of i tables (except those with cartesian products). You should use the list of explicit join conditions added when the user calls the `QueryPlan#join` method to identify potential joins. After implementing this method you should be passing `TestOptimizationJoins#testMinCostJoins` **Note:** you should not add any selection predicates in this method. This is because in our database, we only allow two column predicates in the join condition, and a conjunction of single column predicates otherwise, so the only unprocessed selection predicates in pass i > 1 are the join conditions. _This is not generally the case!_ SQL queries can contain selection predicates that can _not_ be processed until multiple tables have been joined together, for example: Copy SELECT * FROM t1, t2, t3, t4 WHERE (t1.a = t2.b OR t2.b = t2.c) where the single predicate cannot be evaluated until after `t1`, `t2`, _and_ `t3` have been joined together. Therefore, a database that supports all of SQL would have to push down predicates after each pass of the search algorithm. ### [](https://cs186.gitbook.io/project/assignments/proj3/part-2-query-optimization#task-7-optimal-plan-selection) Task 7: Optimal Plan Selection _Difficulty: ★★★★☆_ Your final task is to write the outermost driver method of the optimizer, `QueryPlan#execute`, which should utilize the two helper methods you have implemented to find the best query plan. You will need to add the remaining group by and projection operators that are a part of the query, but have not yet been added to the query plan (see the private helper methods implemented for you in the `QueryPlan` class). **Note:** The tables in `QueryPlan` are kept in the variable `tableNames`. After this, you should pass all the tests we have provided to you in `database.query.*`. [](https://cs186.gitbook.io/project/assignments/proj3/part-2-query-optimization#visualizing-the-query-optimizer) Visualizing the Query Optimizer ----------------------------------------------------------------------------------------------------------------------------------------------------- This section is also optional, but we recommend that you run through the steps. Now that we've finished implementing a better query optimizer, let's visualize the results and compare it with the [naive query optimizer](https://cs186.gitbook.io/project/assignments/proj3/part-2-query-optimization#optional-visualizing-the-naive-query-optimizer) ! Navigate to `CommandLineInterface.java` and run the code to start our CLI. Let's try running the following two queries again: Copy EXPLAIN SELECT * FROM Students AS s INNER JOIN Enrollments AS e ON s.sid = e.sid; Copy EXPLAIN SELECT c.name, s.major, COUNT(*) FROM Students AS s INNER JOIN Enrollments AS e ON s.sid = e.sid INNER JOIN Courses AS c ON e.cid = c.cid WHERE c.name = 'CS 186' GROUP BY s.major, c.name; The outputted query plans are much better than before! Notice how we now push down selects and use more efficient joins. [](https://cs186.gitbook.io/project/assignments/proj3/part-2-query-optimization#submission) Submission ----------------------------------------------------------------------------------------------------------- Follow the submission instructions [here](https://cs186.gitbook.io/project/assignments/proj3/submitting-the-assignment) for the Project 3 Part 2 assignment on Gradescope. If you completed everything you should be passing all the tests in the following files: * `database.query.TestNestedLoopJoin` * `database.query.TestGraceHashJoin` * `database.query.TestSortOperator` * `database.query.TestSingleAccess` * `database.query.TestOptimizationJoins` * `database.query.TestBasicQuery` [PreviousTask 2 Common Errors](https://cs186.gitbook.io/project/assignments/proj3/part-1-join-algorithms/task-2-common-errors) [NextTesting](https://cs186.gitbook.io/project/assignments/proj3/testing) Last updated 9 months ago --- # Part 0: Skeleton Code | CS186 Projects ![](https://cs186.gitbook.io/project/~gitbook/image?url=https%3A%2F%2F678656433-files.gitbook.io%2F%7E%2Ffiles%2Fv0%2Fb%2Fgitbook-legacy-files%2Fo%2Fassets%252F-MFVQnrLlCBowpNWJo1E%252Fsync%252Fb52d8215f4001648f23f82a25c7ffeb00c38879a.png%3Fgeneration%3D1601083825234226%26alt%3Dmedia&width=768&dpr=4&quality=100&sign=eb495251&sv=2) To read, or not to read, that is the question In this project you'll be implementing some common join algorithms and a limited version of the Selinger optimizer. We've provided a brief introduction into the new parts of the code base you'll be working with. For **Part 1** we recommend you read through: * **common/iterator** - Details on backtracking iterators, which will be needed to implement joins * **Join Operators** - Details on the base class of the join operators you'll be implementing and some useful helper methods we've provided * **query/disk** - Details on some useful classes for implementing Grace Hash Join and External Sort For **Part 2** we recommend you read through: * **Scan and Special Operators** - These talk about additional operators that you'll use while creating query plans * **query/QueryPlan.java** - Gives a high level overview of a QueryPlan and some details on how to create and work with them [](https://cs186.gitbook.io/project/assignments/proj3/skeleton-code#common-iterator) common/iterator --------------------------------------------------------------------------------------------------------- The `common/iterator` directory contains an interface called a `BacktrackingIterator`. Iterators that implement this will be able to mark a point during iteration, and reset back to that mark. For example, here we have a backtracking iterator that just returns 1, 2, and 3, but can backtrack: Copy BackTrackingIterator iter = new BackTrackingIteratorImplementation(); iter.next(); // returns 1 iter.next(); // returns 2 iter.markPrev(); // marks the previously returned value, 2 iter.next(); // returns 3 iter.hasNext(); // returns false iter.reset(); // reset to the marked value (line 3) iter.hasNext(); // returns true iter.next(); // returns 2 iter.markNext(); // mark the value to be returned next, 3 iter.next(); // returns 3 iter.hasNext(); // returns false iter.reset(); // reset to the marked value (line 11) iter.hasNext(); // returns true iter.next(); // returns 3 `ArrayBacktrackingIterator` implements this interface. It takes in an array and returns a backtracking iterator over the values in that array. [](https://cs186.gitbook.io/project/assignments/proj3/skeleton-code#query-queryoperator.java) query/QueryOperator.java --------------------------------------------------------------------------------------------------------------------------- The `query` directory contains what are called query operators. A single query to the database may be expressed as a composition of these operators. All operators extend the `QueryOperator` class and implement the `Iterable` interface. The scan operators fetch data from a single table. The remaining operators take one or more input operators, transform or combine the input (e.g. projecting away columns, sorting, joining), and return a collection of records. ### [](https://cs186.gitbook.io/project/assignments/proj3/skeleton-code#join-operators) Join Operators [`JoinOperator.java`](https://github.com/berkeley-cs186/sp25-rookiedb/blob/master/src/main/java/edu/berkeley/cs186/database/query/JoinOperator.java) is the base class of all the join operators. **Reading this file and understanding the methods given to you can save you a lot of time on Part 1.** It provides methods you may need to deal with tables and the current transaction. You should not be dealing directly with `Table` objects nor `TransactionContext` objects while implementing join algorithms in Part 1 (aside from passing them into methods that require them). Subclasses of JoinOperator are all located in `query/join`. Some helper methods you might want to be aware of are located [here](https://github.com/berkeley-cs186/sp25-rookiedb/blob/master/src/main/java/edu/berkeley/cs186/database/query/JoinOperator.java#L167-L207) . ### [](https://cs186.gitbook.io/project/assignments/proj3/skeleton-code#scan-operators) Scan Operators The scan operators fetch data directly from a table. * [`SequentialScanOperator.java`](https://github.com/berkeley-cs186/sp25-rookiedb/blob/master/src/main/java/edu/berkeley/cs186/database/query/SequentialScanOperator.java) - Takes a table name provides an iterator over all the records of that table * [`IndexScanOperator.java`](https://github.com/berkeley-cs186/sp25-rookiedb/blob/master/src/main/java/edu/berkeley/cs186/database/query/IndexScanOperator.java) - Takes a table name, column name, a PredicateOperator (>, <, <=, >=, =) and a value. The column specified must have an index built on it for this operator to work. If so, the index scan will use take advantage of the index to yield records with columns satisfying the given predicate and value (e.g. `salaries.yearid >= 2000`) efficiently ### [](https://cs186.gitbook.io/project/assignments/proj3/skeleton-code#special-operators) Special Operators The remaining operators don't fall into a specific category, but rather perform some specific purpose. * [`SelectOperator.java`](https://github.com/berkeley-cs186/sp25-rookiedb/blob/master/src/main/java/edu/berkeley/cs186/database/query/SelectOperator.java) - Corresponds to the **σ** operator of relational algebra. This operator takes a column name, a PredicateOperator (>, <, <=, >=, =, !=) and a value. It will only yields records from the source operator for which the predicate is satisfied, for example (`yearid >= 2000`)[`ProjectOperator.java`](https://github.com/berkeley-cs186/sp25-rookiedb/blob/master/src/main/java/edu/berkeley/cs186/database/query/ProjectOperator.java) - Corresponds to the **π** operator of relational algebra. This operator takes a list of column names and filters out any columns that weren't listed. Can also compute aggregates, but that is out of scope for this project * [`SortOperator.java`](https://github.com/berkeley-cs186/sp25-rookiedb/blob/master/src/main/java/edu/berkeley/cs186/database/query/SortOperator.java) - Yields records from the source operator in sorted order. You'll be implementing this in Part 1 ### [](https://cs186.gitbook.io/project/assignments/proj3/skeleton-code#other-operators) Other Operators These operators are **out of scope** and directly relevant to the code you'll be writing in this project. * [`MaterializeOperator.java`](https://github.com/berkeley-cs186/sp25-rookiedb/blob/master/src/main/java/edu/berkeley/cs186/database/query/MaterializeOperator.java) - Materializes the source operator into a temporary table immediately, and then acts as a sequential scan over the temporary table. Mainly used in testing to control when IOs take place * [`GroupByOperator.java`](https://github.com/berkeley-cs186/sp25-rookiedb/blob/master/src/main/java/edu/berkeley/cs186/database/query/JoinOperator.java) - Out of scope for this project. This operator accepts a column name and yields the records of the source operator but with the records grouped by their value and each separated by a marker record. For example, if the source operator had singleton records `[0,1,2,1,2,0,1]` the group by operator might yield `[0,0,M,1,1,1,M,2,2]` where `M` is a marker record. [](https://cs186.gitbook.io/project/assignments/proj3/skeleton-code#query-disk) query/disk ----------------------------------------------------------------------------------------------- The classes in this directory are useful for implementing Grace Hash Join and External Sort, and correpond to the concept of "partitions" and "runs" used in those topics respectively. Both classes have an `add` method that can be used to insert a record into the partition/run. These classes will automatically buffer insertions and reads so that at most one page is needed in memory at a time. [](https://cs186.gitbook.io/project/assignments/proj3/skeleton-code#query-aggr) query/aggr ----------------------------------------------------------------------------------------------- The classes and functions in this directory implement aggregate functions, and are **not** necessary to complete the project (though you're free to browse through them if you're interested). [](https://cs186.gitbook.io/project/assignments/proj3/skeleton-code#query-queryplan.java) query/QueryPlan.java ------------------------------------------------------------------------------------------------------------------- ![](https://cs186.gitbook.io/project/~gitbook/image?url=https%3A%2F%2F678656433-files.gitbook.io%2F%7E%2Ffiles%2Fv0%2Fb%2Fgitbook-legacy-files%2Fo%2Fassets%252F-MFVQnrLlCBowpNWJo1E%252Fsync%252F5ab16076409c16b317372484e18415750cf839f8.png%3Fgeneration%3D1601083825540667%26alt%3Dmedia&width=768&dpr=4&quality=100&sign=af210cc0&sv=2) This is the _volcano model_, where the operators are layered atop one another, and each operator requests tuples from the input operator(s) as it needs to generate its next output tuple. Note that each operator only fetches tuples from its input operator(s) as needed, rather than all at once! A query plan is a composition of query operators, and it describes _how_ a query is executed. Recall that SQL is a _declarative_ language - the user does not specify _how_ a query is run, and only _what_ the query should return. Therefore, there are often many possible query plans for a given query. The [`QueryPlan`](https://github.com/berkeley-cs186/sp25-rookiedb/blob/master/src/main/java/edu/berkeley/cs186/database/query/QueryPlan.java) class represents a query. Users of the database create queries using the public methods (such as `join()`, `select()`, etc.) and then call `execute` to generate a query plan for the query and get back an iterator over the resulting data set (which is _not_ fully materialized: the iterator generates each tuple as requested). The current implementation of `execute` simply calls `executeNaive`, which joins tables in the order given; your task in Part 2 will be to generate better query plans. **SelectPredicate** SelectPredicate is a helper class inside of QueryPlan.java that stores information about that selection predicates that the user has applied, for example `someTable.col1 < 186`. A select predicate has four values that you can access: * `tableName`and `columnName` specify which column the predicate applies to * `operator` represents the type of operator being used (for example `<`, `<=`, `>`, etc...) * `value` is a DataBox containing a constant value that the column should be evaluated against (in the above example, `186` would be the value). All of the select predicates for the query are stored inside the selectPredicates instance variable. **JoinPredicate** JoinPredicate is a helper class inside of QueryPlan.java that stores information about the conditions on which tables are joined together, for example: `leftTable.leftColumn = rightTable.rightColumn`. All joins in RookieDB are equijoins. JoinPredicates have five values: * `joinTable`: the name of one of the table's being joined in. Only used for toString() * `leftTable`: the name of the table on the left side of the equality * `leftColumn`: the name of the column on the left side of the equality * `rightTable`: the name of the table on the right side of the equality * `rightColumn`: The name of the column on the right side of the equality All of the join predicates for the query are stored inside of the joinPredicates instance variable. ### [](https://cs186.gitbook.io/project/assignments/proj3/skeleton-code#interface-for-querying) Interface for querying You should read through the `Database.java` section of the [main overview](https://cs186.gitbook.io/project#database-java) and browse through examples in [`src/test/java/edu/berkeley/cs186/database/TestDatabase.java`](https://github.com/berkeley-cs186/sp25-rookiedb/blob/master/src/test/java/edu/berkeley/cs186/database/TestDatabase.java) to familiarize yourself with how queries are written in our database. After `execute()` has been called on a `QueryPlan` object, you can print the final query plan: Copy Iterator result = query.execute(); QueryOperator finalOperator = query.getFinalOperator(); System.out.println(finalOperator.toString()); Copy -> SNLJ on S.sid=E.sid (cost=6) -> Seq Scan on S (cost=3) -> Seq Scan on E (cost=3) [PreviousGetting Started](https://cs186.gitbook.io/project/assignments/proj3/getting-started) [NextPart 1: Join Algorithms](https://cs186.gitbook.io/project/assignments/proj3/part-1-join-algorithms) Last updated 9 months ago --- # Submitting the Assignment | CS186 Projects [](https://cs186.gitbook.io/project/assignments/proj3/submitting-the-assignment#files) Files ------------------------------------------------------------------------------------------------- You may **not** modify the signature of any methods or classes that we provide to you, but you're free to add helper methods. You should make sure that all code you modify belongs to files with `TODO(proj3)` comments in them (e.g. don't add helper methods to DataBox). A full list of files that you may modify follows: * `src/main/java/edu/berkeley/cs186/database/query/join/BNLJOperator.java` * `src/main/java/edu/berkeley/cs186/database/query/join/SortOperator.java` * `src/main/java/edu/berkeley/cs186/database/query/join/SortMergeOperator.java` * `src/main/java/edu/berkeley/cs186/database/query/join/GHJOperator.java` * `src/main/java/edu/berkeley/cs186/database/query/QueryPlan.java` (Part 2 only) Make sure that your code does _not_ use any static (non-final) variables - this may cause odd behavior when running with maven vs. in your IDE (tests run through the IDE often run with a new instance of Java for each test, so the static variables get reset, but multiple tests per Java instance may be run when using maven, where static variables _do not_ get reset). [](https://cs186.gitbook.io/project/assignments/proj3/submitting-the-assignment#gradescope) Gradescope ----------------------------------------------------------------------------------------------------------- Once all of your files are prepared in your repo you can submit to Gradescope through GitHub the same way you did for [Project 0](https://cs186.gitbook.io/project/assignments/proj0/submitting#pushing-changes-to-github-classroom) . [](https://cs186.gitbook.io/project/assignments/proj3/submitting-the-assignment#submitting-via-upload) Submitting via upload --------------------------------------------------------------------------------------------------------------------------------- If your GitHub account has access to many repos, the Gradescope UI might time out while trying to load which repos you have available. If this is the case for you, you can submit your code directly using via upload. You can zip up your source code with `python3 zip.py --assignment proj3` and submit that directly to the autograder. [](https://cs186.gitbook.io/project/assignments/proj3/submitting-the-assignment#partners) Partners ------------------------------------------------------------------------------------------------------- Only one partner has to submit, but please make sure to add the other partner to the Gradescope submission. Slip minutes will be calculated individually. For example, if partner A has 10 slip minutes remaining and partner B has 20 slip minutes remaining and they submit 20 minutes late, partner A will be subject to the late penalty (1/3 off partner A's score) while partner B will have 0 remaining slip minutes and no late penalty applied to partner B's score. [](https://cs186.gitbook.io/project/assignments/proj3/submitting-the-assignment#grade-breakdown) Grade breakdown --------------------------------------------------------------------------------------------------------------------- This project is worth 8% of your overall grade. * **30% of your score will come from your submission for Part 1**. We will only be running public Part 1 tests on your Part 1 submission. * **70% of your score will come from your final submission**. We will be running the hidden Part 1 tests, the public Part 2 tests, and the hidden Part 2 tests on your Part 2 submission. * 60% of your overall score will be made up of the tests released in this project (the tests that we provided in `database.query.*`). * 40% of your overall score will be made up of hidden, unreleased tests that we will run on your submission after the deadline. * The combined public and hidden tests from Part 1 are worth 50% * The combined public and hidden tests from Part 2 are worth 50%. [PreviousTesting](https://cs186.gitbook.io/project/assignments/proj3/testing) [NextProject 4: Concurrency](https://cs186.gitbook.io/project/assignments/proj4) Last updated 9 months ago --- # Testing | CS186 Projects We strongly encourage testing your code yourself. The given tests for this project are not comprehensive tests: it is possible to write incorrect code that passes them all (but not get full score). Things that you might consider testing for include: anything that we specify in the comments or in this document that a method should do that you don't see a test already testing for, and any edge cases that you can think of. Think of what valid inputs might break your code and cause it not to perform as intended, and add a test to make sure things are working. We will **not** be testing behavior on invalid inputs (`null` objects, negative buffer sizes or buffers too small to perform a join, invalid queries, etc...). You can handle these inputs however you want, or not at all. To help you get started, here is one case that is _not_ in the given tests (and will be included in the hidden tests): joining an empty table with another table should result in an iterator that returns no records (`hasNext()` should return false immediately). To add a unit test, open up the appropriate test file and simply add a new method to the file with a `@Test` annotation, for example: Copy @Test public void testEmptyBNLJ() { // your test code here } Many test classes have some setup code done for you already: take a look at other tests in the file for an idea of how to write the test code. For example, the SNLJ tests in TestNestedLoopJoin can be used as a template for your own BNLJ, Sort, and SMJ tests. [PreviousPart 2: Query Optimization](https://cs186.gitbook.io/project/assignments/proj3/part-2-query-optimization) [NextSubmitting the Assignment](https://cs186.gitbook.io/project/assignments/proj3/submitting-the-assignment) Last updated 9 months ago --- # Getting Started | CS186 Projects [](https://cs186.gitbook.io/project/assignments/proj3/getting-started#logistics) Logistics ----------------------------------------------------------------------------------------------- This project is worth 8% of your overall grade in the class. * Part 1 is due **Thursday, 3/6/2025 at 11:59PM PST (GMT-8)** and will be worth 30% of your score. Your score will be determined by public tests only. * Part 2 is due **Thursday, 3/13/2025 at 11:59PM PDT (GMT-7)** and will be worth the remaining 70% of your score. We'll be running the public tests for Part 2 and all hidden tests for both Part 1 and Part 2 on this submission. The workload for the project is designed to be completed solo, but this semester we're allowing students to work on this project with a partner if you want to. Your partner does not have to be the same one as you had for Project 2. Feel free to search for a partner on [this Edstem thread](https://edstem.org/us/courses/70276/discussion/5999429) ! **A gentle reminder that though our projects have tight release schedules, projects don't tend to take the entire time given to complete them :)** [](https://cs186.gitbook.io/project/assignments/proj3/getting-started#prerequisites) Prerequisites ------------------------------------------------------------------------------------------------------- You'll need to finish both Iterators & Joins lectures to finish Part 1. To finish Part 2 you'll need to watch up to the Query Optimization: Costs & Search lecture. [](https://cs186.gitbook.io/project/assignments/proj3/getting-started#academic-integrity-policy) Academic Integrity Policy ------------------------------------------------------------------------------------------------------------------------------- “_As a member of the UC Berkeley community, I act with honesty, integrity, and respect for others._” — UC Berkeley Honor Code **Read through the academic integrity guidelines** [**here**](https://cs186berkeley.net/integrityguidelines/) **.** We will be running plagiarism detection software on every submission against our own database of this semester's submissions, past submissions, and publicly hosted implementations on platforms such as GitHub and GitLab, followed by a thorough manual review process. Plagiarism on any assignment will result in a [non-reportable warning](https://conduct.berkeley.edu/wp-content/uploads/2024/01/Academic-Misconduct-Resource-Sheet-for-Students-UPDATED.pdf) and a grade penalty based on the severity of the infraction. As long as you follow the guidelines, there isn't anything to worry about here. While we do rely on software to find possible cases of academic dishonesty, every case is reviewed by multiple TAs who can filter out false positives. [](https://cs186.gitbook.io/project/assignments/proj3/getting-started#fetching-the-released-code) Fetching the released code --------------------------------------------------------------------------------------------------------------------------------- The GitHub Classroom link for this project is in the Project 3 release post on [Edstem](https://edstem.org/us/courses/70276/discussion/) . Once your private repo is set up clone the Project 3 skeleton code onto your local machine. ### [](https://cs186.gitbook.io/project/assignments/proj3/getting-started#setting-up-your-local-development-environment) Setting up your local development environment If you're using IntelliJ you can follow the instructions in [Project 0](https://cs186.gitbook.io/project/assignments/proj0/getting-started#setting-up-your-local-development-environment) to set up your local environment again. Once you have your environment set up you can head to the next section [Part 0](https://cs186.gitbook.io/project/assignments/proj3/skeleton-code) and begin working on the assignment. [](https://cs186.gitbook.io/project/assignments/proj3/getting-started#working-with-a-partner) Working with a partner ------------------------------------------------------------------------------------------------------------------------- Only one partner has to submit, but please make sure to add the other partner to the Gradescope submission. If you want to share code over GitHub you can follow the instructions [here](https://cs186.gitbook.io/project/common/adding-a-partner-on-github) . [](https://cs186.gitbook.io/project/assignments/proj3/getting-started#debugging-issues-with-github-classroom) Debugging Issues with GitHub Classroom --------------------------------------------------------------------------------------------------------------------------------------------------------- Feel free to skip this section if you don't have any issues with GitHub Classroom. If you are having issues (i.e. the page froze or some error message appeared), first check if you have access to your repo at `https://github.com/cs186-student/sp25-proj3-username`, replacing `username` with your GitHub username. If you have access to your repo and the starter code is there, then you can proceed as usual. ### [](https://cs186.gitbook.io/project/assignments/proj3/getting-started#id-404-not-found) 404 Not Found If you're getting a 404 not found page when trying to access your repo, make sure you've set up your repo using the GitHub Classroom link in the Project 3 release post on [Edstem](https://edstem.org/us/courses/70276/discussion/) . If you don't have access to your repo at all after following these steps, feel free to contact the course staff on Edstem. [PreviousProject 3: Joins and Query Optimization](https://cs186.gitbook.io/project/assignments/proj3) [NextPart 0: Skeleton Code](https://cs186.gitbook.io/project/assignments/proj3/skeleton-code) Last updated 9 months ago --- # Part 1: Join Algorithms | CS186 Projects ![](https://cs186.gitbook.io/project/~gitbook/image?url=https%3A%2F%2F678656433-files.gitbook.io%2F%7E%2Ffiles%2Fv0%2Fb%2Fgitbook-legacy-files%2Fo%2Fassets%252F-MFVQnrLlCBowpNWJo1E%252Fsync%252F2d099394d2b47cca1bfe4c9290db76e4a225c3ec.png%3Fgeneration%3D1601083825848627%26alt%3Dmedia&width=768&dpr=4&quality=100&sign=c9f81f31&sv=2) Datatape In this part, you will implement some join algorithms: block nested loop join, sort merge, and grace hash join. You can complete Task 1, Task 2 and Task 3 in **any order you want**. Task 4 is dependent on the completion of Task 3. Aside from when the comments tell you that you can do something in memory, everything else should be **streamed**. You should not hold more pages in memory at once than the given algorithm says you are allowed to. Doing otherwise may result in no credit. **Note on terminology**: in lecture, we sometimes use both block and page describe the unit of transfer between memory and disk. In the context of join algorithms, however, page refers to the unit of transfer between memory and disk, and block refers to a set of one or more pages. All uses of the word `block` in this part refer to this second definition (a set of pages). **Convenient assumptions**: * For all iterators that will be implemented in this project you can assume `hasNext()` will always be called before `next()`. * Any Record object provided through an argument or as an element of a list or iterator will never be `null`. * For testing purposes, we will **not** be testing behavior on invalid inputs (`null` objects, negative buffer sizes or buffers too small to perform a join, invalid queries, etc...). You can handle these inputs however you want, or not at all. * Your join operators, sort operator, and query plans do not need to account for underlying relations being mutated during their execution. [](https://cs186.gitbook.io/project/assignments/proj3/part-1-join-algorithms#your-tasks) Your Tasks -------------------------------------------------------------------------------------------------------- Based on student feedback from previous semesters, we estimate that this part of the project will take approximately 20-25 hours to complete. We have also included a star-based difficulty ranking per task, relative to the rest of the project, as a guide for pacing your work. _Please note that every student works at a different pace, and it's absolutely ok to spend more or less time on the project than the provided estimates!_ ### [](https://cs186.gitbook.io/project/assignments/proj3/part-1-join-algorithms#task-1-nested-loop-joins) Task 1: Nested Loop Joins _Difficulty: ★★☆☆☆_ #### [](https://cs186.gitbook.io/project/assignments/proj3/part-1-join-algorithms#simple-nested-loop-join-snlj) Simple Nested Loop Join (SNLJ) SNLJ has already been implemented for you in `SNLJOperator`. You should take a look at it to get a sense for how the pseudocode in lecture and section translate to code, but you should **not** copy it when writing your own join operators. Although each join algorithm should return the same data, the order differs between each join algorithm, as does the structure of the code. In particular, SNLJ does not need to explicitly manage pages of data (it only ever needs the next record of each table, and therefore can just use an iterator over all records in a table), whereas all the algorithms you will be implementing in this part must explicitly manage when pages of data are fetched from disk. #### [](https://cs186.gitbook.io/project/assignments/proj3/part-1-join-algorithms#page-nested-loop-join-pnlj) Page Nested Loop Join (PNLJ) PNLJ has already been implemented for you as a special case of BNLJ with B=3. Therefore, it will not function properly until BNLJ has been properly implemented. The test cases for both PNLJ and BNLJ in `TestNestedLoopJoin` depend on a properly implemented BNLJ. #### [](https://cs186.gitbook.io/project/assignments/proj3/part-1-join-algorithms#block-nested-loop-join-bnlj) Block Nested Loop Join (BNLJ) You should read through the given skeleton code in `BNLJOperator`. The `next` and `hasNext` methods of the iterator have already been filled out for you, but you will need to implement the `fetchNextRecord` method, which should do most of the heavy lifting of the BNLJ algorithm. There are also two suggested helper methods: `fetchNextLeftBlock`, which should fetch the next non-empty block of left table pages from `leftSourceIterator`, and `fetchNextRightPage`, which should fetch the next non-empty page of the right table (from `rightSourceIterator`). The `fetchNextRecord` method should, as its name suggests, fetches the next record of the join output. When implementing this method there are 4 important cases you should consider: * Case 1: The right page iterator has a value to yield * Case 2: The right page iterator doesn't have a value to yield but the left block iterator does * Case 3: Neither the right page nor left block iterators have values to yield, but there's more right pages * Case 4: Neither right page nor left block iterators have values nor are there more right pages, but there are still left blocks We've provided the following animation to give you a feel for how the blocks, pages, and records are traversed during the nested looping process. Identifying where each of these cases take place in the diagram may help guide on what to do in each case. ![](https://cs186.gitbook.io/project/~gitbook/image?url=https%3A%2F%2F678656433-files.gitbook.io%2F%7E%2Ffiles%2Fv0%2Fb%2Fgitbook-legacy-files%2Fo%2Fassets%252F-MFVQnrLlCBowpNWJo1E%252Fsync%252F00e507c4028d7e86c59c32bf3d626c5a76973935.gif%3Fgeneration%3D1601518326156231%26alt%3Dmedia&width=768&dpr=4&quality=100&sign=ddd88e0d&sv=2) Animations of SNLJ and PNLJ can be found [here](https://cs186.gitbook.io/project/common/misc/nested-loop-join-animations) . Loaded left records are highlighted in blue, while loaded orange records are highlighted in orange. The dark purple square represents which pair of records are being considered for the join, while light purple shows which pairs have already been considered. Once you have implemented `BNLJOperator`, all the tests in `TestNestedLoopJoin` should pass. ### [](https://cs186.gitbook.io/project/assignments/proj3/part-1-join-algorithms#task-2-hash-joins) Task 2: Hash Joins _Difficulty: ★★★☆☆_ #### [](https://cs186.gitbook.io/project/assignments/proj3/part-1-join-algorithms#simple-hash-join-shj) Simple Hash Join (SHJ) We've provided an implementation of Simple Hash Join which can be found in `SHJOperator.java`. Simple Hash Join performs a single pass of partitioning on only the left records before attempting to join. Read the code for SHJ carefully as it should give you a good idea of how to implement Grace Hash Join. #### [](https://cs186.gitbook.io/project/assignments/proj3/part-1-join-algorithms#grace-hash-join-ghj) Grace Hash Join (GHJ) Everything you will need to implement will be done in `GHJOperator.java`. You will need to implement the functions `partition`, `buildAndProbe`, and `run`. Additionally, you will have to provide some inputs in `getBreakSHJInputs` and `getBreakGHJInputs` which will be used to test that Simple Hash Join fails but Grace Hash Join passes (tested in `testBreakSHJButPassGHJ`) and that GHJ breaks (tested in `testGHJBreak`) respectively. The file `Partition.java` in the `query/disk` directory will be useful when working with partitions. Read through the file and get a good idea what methods you can use. Once you have implemented all the methods in `GHJOperator.java`, all tests in `TestGraceHashJoin.java` will pass. There will be **no hidden tests** for Grace Hash Join. Your grade for Grace Hash Join will come solely from the released public tests. ### [](https://cs186.gitbook.io/project/assignments/proj3/part-1-join-algorithms#task-3-external-sort) Task 3: External Sort _Difficulty: ★★★★★_ The first step in Sort Merge Join is to sort both input relations. Therefore, before you can work on implementing Sort Merge Join, you must first implement an external sorting algorithm. Recall that a "run" in the context of external mergesort is just a sequence of sorted records. This is represented in `SortOperator` by the `Run` class (located in `query/disk/Run.java`). As runs in external mergesort can span many pages (and eventually span the entirety of the table), the `Run` class does not keep all its data in memory. Rather, it creates a temporary table and writes all of its data to the temporary table (which is materialized to disk at the buffer manager's discretion). You will need to implement the `sortRun`, `mergeSortedRuns`, `mergePass`, and `sort` methods of `SortOperator`. * `sortRun(run)` should sort the passed in data using an in-memory sort (Pass 0 of external mergesort). * `mergeSortedRuns(runs)` should return a new run given a list of sorted runs. * `mergePass(runs)` should perform a single merge pass of external mergesort, given a list of all the sorted runs from the previous pass. * `sort()` should run external mergesort from start to finish, and return the final run with the sorted data Each of these methods may be tested independently, so you **must** implement each one as described. You may add additional helper methods as you see fit. Once you have implemented all four methods, all the tests in `TestSortOperator` should pass. ### [](https://cs186.gitbook.io/project/assignments/proj3/part-1-join-algorithms#task-4-sort-merge-join) Task 4: Sort Merge Join _Difficulty: ★★★☆☆_ Now that you have a working external sort, you can now implement Sort Merge Join (SMJ). For simplicity, your implementation of SMJ should _not_ utilize the optimization discussed in lecture in any case (where the final merge pass of sorting happens at the same time as the join). Therefore, you should use `SortOperator` to sort during the sort phase of SMJ. You will need to implement `fetchNextRecord()` in the `SortMergeIterator` inner class of `SortMergeOperator`. Your implementation of `SortMergeOperator` and your implementation of `SortOperator` may be tested independently. Remember that you may **not** add a new public method to `SortOperator` and call it from `SortMergeOperator`. Once you have implemented `SortMergeIterator`, all the tests in `TestSortMergeJoin` should pass. [](https://cs186.gitbook.io/project/assignments/proj3/part-1-join-algorithms#submission) Submission -------------------------------------------------------------------------------------------------------- Follow the submission instructions [here](https://cs186.gitbook.io/project/assignments/proj3/submitting-the-assignment) for the Project 3 Part 1 assignment on Gradescope. If you completed everything you should be passing all the tests in the following files: * `database.query.TestNestedLoopJoin` * `database.query.TestGraceHashJoin` * `database.query.TestSortOperator` * `database.query.TestSortMergeJoin` [PreviousPart 0: Skeleton Code](https://cs186.gitbook.io/project/assignments/proj3/skeleton-code) [NextTask 1 Debugging](https://cs186.gitbook.io/project/assignments/proj3/part-1-join-algorithms/task-1-debugging) Last updated 9 months ago --- # Task 2 Common Errors | CS186 Projects [](https://cs186.gitbook.io/project/assignments/proj3/part-1-join-algorithms/task-2-common-errors#index-out-of-bounds-error-while-partitioning) Index out of bounds error while partitioning ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- Hash codes can be negative. Make sure you handle that case. The hash codes can also be larger than the number of partitions, so make sure you handle that too. We recommend you look at [SHJOperator'](https://github.com/berkeley-cs186/sp25-rookiedb/blob/master/src/main/java/edu/berkeley/cs186/database/query/join/SHJOperator.java#L73-L76) s implementation to make sure you partition correctly with hash codes. [](https://cs186.gitbook.io/project/assignments/proj3/part-1-join-algorithms/task-2-common-errors#reached-the-max-number-of-passes-cap) Reached the max number of passes cap --------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- This means that you're doing recursive partitioning infinitely. The most likely cause of this is partitioning using the the same hash function every single time. Make sure to update your hash func calls so that the hash function is updated each time. If you're certain that you're doing both of those things, make sure your condition for recursive partitioning is correct. An off by one (for example `<=` vs `<` ) is enough to make it so you never reach the build and probe phase. [](https://cs186.gitbook.io/project/assignments/proj3/part-1-join-algorithms/task-2-common-errors#code-running-forever-recursion-depth-limit-exceeded-java.lang.outofmemoryerror) Code running forever/recursion depth limit exceeded/java.lang.OutOfMemoryError --------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- Make sure every time you make a recursive call to run that you increment the pass number. [](https://cs186.gitbook.io/project/assignments/proj3/part-1-join-algorithms/task-2-common-errors#assertionerror-expected-1674-actual-91) AssertionError: Expected: 1674 Actual: 91 ---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- Make sure when you recursively call run that you add all of the resulting records to your output. Additionally make sure that whenever you call buildAndProbe that you also add those records to your output. [PreviousTask 1 Debugging](https://cs186.gitbook.io/project/assignments/proj3/part-1-join-algorithms/task-1-debugging) [NextPart 2: Query Optimization](https://cs186.gitbook.io/project/assignments/proj3/part-2-query-optimization) Last updated 9 months ago --- # Task 1 Debugging | CS186 Projects We put together some extra tests with detailed error outputs that should give you some hints as to what might be go wrong with your BNLJ implementation. They're meant to be easier to reason about than the main BNLJ tests since each page only has 4 records instead of 400. **These tests are ungraded**. They're just meant to help you track down bugs in the nested loop join tests in `TestNestedLoopJoin`. [](https://cs186.gitbook.io/project/assignments/proj3/part-1-join-algorithms/task-1-debugging#overview) Overview --------------------------------------------------------------------------------------------------------------------- These tests are designed to give you visualizations that might hint as to where you're going wrong. **You should try to get the test cases working in order**, that is, start with the 1x1 PNLJ tests, followed by the 2x2 PNLJ tests, and then finally the 2x2 BNLJ tests. When you fail a test it should give you a detailed description of why you failed. Here's some example output from failing `testPNLJ1x1Full`: Copy edu.berkeley.cs186.database.query.QueryPlanException: == MISSING OR EXTRA RECORDS == +---------+ Left 0 | ? ? ? ? | Page 0 | x x x x | #1 0 | x x x x | 0 | x x x x | +---------+ 0 0 0 0 Right Page #1 You either excluded or included records when you shouldn't have. Key: - x means we expected this record to be included and you included it - + means we expected this record to be excluded and you included it - ? means we expected this record to be included and you excluded it - r means you included this record multiple times - a blank means we expected this record to be excluded and you excluded it In this example we expect every single record in the left table to be joined with every single table in the right table. The question marks on the top row of the box tell you that you're missing 4 records. A likely reason for why this is the case is that your join logic exits too early, before the last left record is ever compared against the right records. The exact cause of this particular problem is stopping iteration as soon as `!this.leftRecordIterator.hasNext()`, before considering the last left record against any right records. Here's a more complicated case that we see in office hours a lot in testPNLJ2x2Full : Copy edu.berkeley.cs186.database.query.QueryPlanException: == MISMATCH == +---------+---------+ Left 0 | | | Page 0 | | | #2 0 | | | 0 | | | +---------+---------+ Left 0 | x x x x | A | Page 0 | x x x x | | #1 0 | x x x x | | 0 | x x x x | E | +---------+---------+ 0 0 0 0 0 0 0 0 Right Right Page #1 Page #2 You had 1 or more mismatched records. The first mismatch was at record #17. The above shows the state of the join when the mismatch occurred. Key: - x means your join properly yielded this record at the right time - E was the record we expected you to yield - A was the record that you actually yielded This example found a record returned in the wrong order. To help you debug we give the position of where we expected the next record to be, and where it actually was. Can you spot the bug? We were expecting the first record on right page #2 to be compared with the first record in left page #1. It appears that leftRecord was still set to the last record on page #1. The mistake was that the leftRecord wasn't reset back to the first record in the left page. Many students will remember to call `leftIterator.reset()`, but forget to do `leftRecord = leftIterator.next()` afterwards, causing this issue. [](https://cs186.gitbook.io/project/assignments/proj3/part-1-join-algorithms/task-1-debugging#animations) Animations ------------------------------------------------------------------------------------------------------------------------- Here's some animations of how we expect each test format to be traversed. ### [](https://cs186.gitbook.io/project/assignments/proj3/part-1-join-algorithms/task-1-debugging#pnlj-1x1) PNLJ 1x1 ![](https://cs186.gitbook.io/project/~gitbook/image?url=https%3A%2F%2F678656433-files.gitbook.io%2F%7E%2Ffiles%2Fv0%2Fb%2Fgitbook-x-prod.appspot.com%2Fo%2Fspaces%252F-MFVQnrLlCBowpNWJo1E%252Fuploads%252Fgit-blob-f1106527564658f02b2741e2e5fb4c5c5ab2f450%252F1x1%2520%283%29%2520%282%29%2520%284%29.gif%3Falt%3Dmedia&width=768&dpr=4&quality=100&sign=a4d1a0bd&sv=2) ### [](https://cs186.gitbook.io/project/assignments/proj3/part-1-join-algorithms/task-1-debugging#pnlj-2x2) PNLJ 2x2 ![](https://cs186.gitbook.io/project/~gitbook/image?url=https%3A%2F%2F678656433-files.gitbook.io%2F%7E%2Ffiles%2Fv0%2Fb%2Fgitbook-x-prod.appspot.com%2Fo%2Fspaces%252F-MFVQnrLlCBowpNWJo1E%252Fuploads%252Fgit-blob-1ba4e1a3a9f99d0e3ddd43ad0d778d078076e717%252F2x2pnlj%2520%281%29%2520%281%29%2520%281%29.gif%3Falt%3Dmedia&width=768&dpr=4&quality=100&sign=edbaa21c&sv=2) ### [](https://cs186.gitbook.io/project/assignments/proj3/part-1-join-algorithms/task-1-debugging#bnlj-2x2-b-4) BNLJ 2x2 (B=4) ![](https://cs186.gitbook.io/project/~gitbook/image?url=https%3A%2F%2F678656433-files.gitbook.io%2F%7E%2Ffiles%2Fv0%2Fb%2Fgitbook-x-prod.appspot.com%2Fo%2Fspaces%252F-MFVQnrLlCBowpNWJo1E%252Fuploads%252Fgit-blob-1f533bb4157bbbcdf130d063dd9153022cfeab30%252F2x2bnlj%2520%284%29%2520%284%29%2520%282%29%2520%285%29.gif%3Falt%3Dmedia&width=768&dpr=4&quality=100&sign=f142a5b&sv=2) [](https://cs186.gitbook.io/project/assignments/proj3/part-1-join-algorithms/task-1-debugging#cases) Cases --------------------------------------------------------------------------------------------------------------- Here's examples of the cases mentioned in the spec look like in the PNLJ 2x2 cases (block size of 1). The dark purple square is the most recently considered record. The red arrow points to the next pair records that should be considered for the join. ![](https://cs186.gitbook.io/project/~gitbook/image?url=https%3A%2F%2F678656433-files.gitbook.io%2F%7E%2Ffiles%2Fv0%2Fb%2Fgitbook-x-prod.appspot.com%2Fo%2Fspaces%252F-MFVQnrLlCBowpNWJo1E%252Fuploads%252Fgit-blob-789697883f5e7f4e6c782c5259ed5dc635310d4f%252Fcases%2520%281%29%2520%281%29.png%3Falt%3Dmedia%26token%3D48bb4814-1be8-4de5-b6cc-f48f5462df6e&width=768&dpr=4&quality=100&sign=24f48eb0&sv=2) Try to think about what should be advanced and what should be reset in each case. As a reminder: * Case 1: The right page iterator has a value to yield * Case 2: The right page iterator doesn't have a value to yield but the left block iterator does * Case 3: Neither the right page nor left block iterators have values to yield, but there's more right pages * Case 4: Neither right page nor left block iterators have values nor are there more right pages, but there are still left blocks [](https://cs186.gitbook.io/project/assignments/proj3/part-1-join-algorithms/task-1-debugging#common-errors) Common Errors ------------------------------------------------------------------------------------------------------------------------------- ### [](https://cs186.gitbook.io/project/assignments/proj3/part-1-join-algorithms/task-1-debugging#pnlj-1x1-full) PNLJ 1x1 Full Copy == MISSING OR EXTRA RECORDS == +---------+ Left 0 | x ? x ? | Page 0 | x ? x ? | #1 0 | x ? x ? | 0 | x ? x ? | +---------+ 0 0 0 0 Right Page #1 You either excluded or included records when you shouldn't have. Key: - x means we expected this record to be included and you included it - + means we expected this record to be excluded and you included it - ? means we expected this record to be included and you excluded it - r means you included this record multiple times - a blank means we expected this record to be excluded and you excluded it The above case is likely happening because you're calling `rightRecordIterator.next()` more often than you should, and losing every other value. Make sure whenever you call `rightRecordIterator.next()` that you compare the result to the current left record and set it as the next record if there's a match. Copy == MISMATCH == +---------+ Left 0 | | Page 0 | | #1 0 | E | 0 | A x x x | +---------+ 0 0 0 0 Right Page #1 You had 1 or more mismatched records. The first mismatch was at record #5. The above shows the state of the join when the mismatch occurred. Key: - x means your join properly yielded this record at the right time - E was the record we expected you to yield - A was the record that you actually yielded The above case is mostly likely caused by failing to advance the left record in case 2. Remember that even if you call `leftRecordIterator.next()`, if you don't set the result to leftRecord then leftRecord won't get updated. Copy edu.berkeley.cs186.database.query.QueryPlanException: == MISSING OR EXTRA RECORDS == +---------+ Left 0 | ? ? ? ? | Page 0 | x x x x | #1 0 | x x x x | 0 | x x x x | +---------+ 0 0 0 0 Right Page #1 You either excluded or included records when you shouldn't have. Key: - x means we expected this record to be included and you included it - + means we expected this record to be excluded and you included it - ? means we expected this record to be included and you excluded it - r means you included this record multiple times - a blank means we expected this record to be excluded and you excluded it The above case likely caused by stopping iteration too early, specifically as soon as !leftRecordIterator.hasNext(). Remember that even if there isn't another left record, you still have to compare the current left record against every right record in the rightRecordIterator. Copy edu.berkeley.cs186.database.query.QueryPlanException: == MISMATCH == +---------+ Left 0 | | Page 0 | | #1 0 | A | 0 | x x x E | +---------+ 0 0 0 0 Right Page #1 You had 1 or more mismatched records. The first mismatch was at record #4. The above shows the state of the join when the mismatch occurred. Key: - x means your join properly yielded this record at the right time - E was the record we expected you to yield - A was the record that you actually yielded == MISSING OR EXTRA RECORDS == +---------+ Left 0 | x x x ? | Page 0 | x x x ? | #1 0 | x x x ? | 0 | x x x ? | +---------+ 0 0 0 0 Right Page #1 You either excluded or included records when you shouldn't have. Key: - x means we expected this record to be included and you included it - + means we expected this record to be excluded and you included it - ? means we expected this record to be included and you excluded it - r means you included this record multiple times - a blank means we expected this record to be excluded and you excluded it In the above case you're probably handling case 2 too early, before you ever compare the last right record to the current left record. Make sure that when you handle case 2 that you've already handled case 1 for the the last right record. ### [](https://cs186.gitbook.io/project/assignments/proj3/part-1-join-algorithms/task-1-debugging#pnlj-2x2-full) PNLJ 2x2 Full Copy == MISMATCH == +---------+---------+ Left 0 | | | Page 0 | | | #2 0 | | | 0 | | | +---------+---------+ Left 0 | x x x x | A | Page 0 | x x x x | | #1 0 | x x x x | | 0 | x x x x | E | +---------+---------+ 0 0 0 0 0 0 0 0 Right Right Page #1 Page #2 You had 1 or more mismatched records. The first mismatch was at record #17. The above shows the state of the join when the mismatch occurred. Key: - x means your join properly yielded this record at the right time - E was the record we expected you to yield - A was the record that you actually yielded In the above case you're probably not handling case 3 properly. In particular, make sure that when you run out of both left records and right records for a given left block and right page respectively that you call `leftIterator.reset()` AND assign `leftRecord` to the first record of the current page. Many students forget to reassign left record. Copy +---------+---------+ Left 0 | | | Page 0 | | | #2 0 | | A | 0 | E | | +---------+---------+ Left 0 | x x x x | x x x x | Page 0 | x x x x | x x x x | #1 0 | x x x x | x x x x | 0 | x x x x | x x x x | +---------+---------+ 0 0 0 0 0 0 0 0 Right Right Page #1 Page #2 You had 1 or more mismatched records. The first mismatch was at record #33. The above shows the state of the join when the mismatch occurred. Key: - x means your join properly yielded this record at the right time - E was the record we expected you to yield - A was the record that you actually yielded In the above case make sure that by the end of case 4 you've set rightRecordIterator to be an iterator over right page #1. Copy edu.berkeley.cs186.database.query.QueryPlanException: == MISMATCH == +---------+---------+ Left 0 | | | Page 0 | | | #2 0 | | | 0 | E | | +---------+---------+ Left 0 | A x x x | x x x x | Page 0 | x x x x | x x x x | #1 0 | x x x x | x x x x | 0 | x x x x | x x x x | +---------+---------+ 0 0 0 0 0 0 0 0 Right Right Page #1 Page #2 You had 1 or more mismatched records. The first mismatch was at record #33. The above shows the state of the join when the mismatch occurred. Key: - x means your join properly yielded this record at the right time - E was the record we expected you to yield - A was the record that you actually yielded In the above case make sure that by the end of case 4 you've set leftRecordIterator to be an iterator over left page #2. Copy == MISSING OR EXTRA RECORDS == +---------+---------+ Left 0 | ? ? ? ? | ? ? ? ? | Page 0 | ? ? ? ? | ? ? ? ? | #2 0 | ? ? ? ? | ? ? ? ? | 0 | ? ? ? ? | ? ? ? ? | +---------+---------+ Left 0 | x x x x | x x x x | Page 0 | x x x x | x x x x | #1 0 | x x x x | x x x x | 0 | x x x x | x x x x | +---------+---------+ 0 0 0 0 0 0 0 0 Right Right Page #1 Page #2 You either excluded or included records when you shouldn't have. Key: - x means we expected this record to be included and you included it - + means we expected this record to be excluded and you included it - ? means we expected this record to be included and you excluded it - r means you included this record multiple times - a blank means we expected this record to be excluded and you excluded it In the above case you're probably doing something wrong in case 4. In particular make sure that your code resets your right record iterator to be an iterator over the first page of the right relation. Remember that you'll need to reset your `rightIterator` to do this! Copy == MISSING OR EXTRA RECORDS == +---------+---------+ Left 0 | ? ? ? ? | ? ? ? ? | Page 0 | ? ? ? ? | ? ? ? ? | #2 0 | ? ? ? ? | ? ? ? ? | 0 | ? ? ? ? | ? ? ? ? | +---------+---------+ Left 0 | x x x x | ? ? ? ? | Page 0 | x x x x | ? ? ? ? | #1 0 | x x x x | ? ? ? ? | 0 | x x x x | ? ? ? ? | +---------+---------+ 0 0 0 0 0 0 0 0 Right Right Page #1 Page #2 You either excluded or included records when you shouldn't have. Key: - x means we expected this record to be included and you included it - + means we expected this record to be excluded and you included it - ? means we expected this record to be included and you excluded it - r means you included this record multiple times - a blank means we expected this record to be excluded and you excluded it In the above case you likely have a problem in your implementation of case 3, and your code is terminating too early. One possible cause of this is forgetting to mark the beginning of your leftRecordIterator in fetchNextLeftBlock. This could cause problems when you try to reset leftRecordIterator in your case 3, and causing you to throw a no such element exception earlier than you intend to. [PreviousPart 1: Join Algorithms](https://cs186.gitbook.io/project/assignments/proj3/part-1-join-algorithms) [NextTask 2 Common Errors](https://cs186.gitbook.io/project/assignments/proj3/part-1-join-algorithms/task-2-common-errors) Last updated 9 months ago --- # Project 4: Concurrency | CS186 Projects [Getting Started](https://cs186.gitbook.io/project/assignments/proj4/getting-started) [Part 0: Skeleton Code](https://cs186.gitbook.io/project/assignments/proj4/skeleton-code) [Part 1: Queuing](https://cs186.gitbook.io/project/assignments/proj4/part-1-lockmanager) [Part 2: Multigranularity](https://cs186.gitbook.io/project/assignments/proj4/part-2-lockcontext-and-lockutil) [Testing](https://cs186.gitbook.io/project/assignments/proj4/testing) [Submitting the Assignment](https://cs186.gitbook.io/project/assignments/proj4/submitting-the-assignment) [PreviousSubmitting the Assignment](https://cs186.gitbook.io/project/assignments/proj3/submitting-the-assignment) [NextGetting Started](https://cs186.gitbook.io/project/assignments/proj4/getting-started) Last updated 8 months ago --- # Part 0: Skeleton Code | CS186 Projects ![](https://cs186.gitbook.io/project/~gitbook/image?url=https%3A%2F%2F678656433-files.gitbook.io%2F%7E%2Ffiles%2Fv0%2Fb%2Fgitbook-legacy-files%2Fo%2Fassets%252F-MFVQnrLlCBowpNWJo1E%252Fsync%252F4d4d0d043a6f40300b10af06d455befc6fac9cb9.png%3Fgeneration%3D1602744722535589%26alt%3Dmedia&width=768&dpr=4&quality=100&sign=2319e34d&sv=2) Data x-ray Read through all of the code in the `concurrency` directory (including the classes that you are not touching - they may contain useful methods or information pertinent to the project). Many comments contain critical information on how you must implement certain functions. Try to understand how each class fits in: what is each class responsible for, what are all the methods you have to implement, and how does each one manipulate the internal state. Trying to code one method at a time without understanding how all the parts of the lock manager work often results in having to rewrite significant amounts of code. [](https://cs186.gitbook.io/project/assignments/proj4/skeleton-code#layers) Layers --------------------------------------------------------------------------------------- ![](https://cs186.gitbook.io/project/~gitbook/image?url=https%3A%2F%2F678656433-files.gitbook.io%2F%7E%2Ffiles%2Fv0%2Fb%2Fgitbook-legacy-files%2Fo%2Fassets%252F-MFVQnrLlCBowpNWJo1E%252Fsync%252F1f97f3bfda2c79b4bd4db9a17536655fed02c839.png%3Fgeneration%3D1602744722026673%26alt%3Dmedia&width=768&dpr=4&quality=100&sign=566b1aa4&sv=2) The skeleton code divides multigranularity locking into three layers. * The `LockManager` object manages all the locks, treating each resource as independent (it doesn't consider the resource hierarchy at all). This level is responsible queuing logic, blocking/unblocking transactions as necessary, and is the single source of authority on whether a transaction has a certain lock. If the `LockManager` says T1 has X(database), then T1 has X(database). * A collection of `LockContext` objects, which each represent a single lockable object (e.g. a page or a table) lies on top of the `LockManager`. The `LockContext` objects are connected according to the hierarchy (e.g. a `LockContext` for a table has the database context as its parent, and its pages' contexts as children). The `LockContext` objects all share a single `LockManager`, and each context enforces multigranularity constraints on its methods (e.g. an exception will be thrown if a transaction attempts to request X(table) without IX(database)). * A declarative layer lies on top of the collection of `LockContext` objects, and is responsible for acquiring all the intent locks needed for each S or X request that the database uses (e.g. if S(page) is requested, this layer would be responsible for requesting IS(database), IS(table) if necessary). In Part 1, you will be implementing the bottom layer (`LockManager`) and lock types. In Part 2, you will be implementing the middle and top layer (`LockContext` and `LockUtil`), and integrate your changes into the database. [PreviousGetting Started](https://cs186.gitbook.io/project/assignments/proj4/getting-started) [NextPart 1: Queuing](https://cs186.gitbook.io/project/assignments/proj4/part-1-lockmanager) Last updated 8 months ago --- # Development Container Setup | CS186 Projects [](https://cs186.gitbook.io/project/common/devcontainer-setup#development-container-setup) Development Container Setup --------------------------------------------------------------------------------------------------------------------------- A [development container](https://containers.dev/) is a [quasi-standard](https://github.com/devcontainers/spec) way to configure a development environment in a Docker container and install an agent that communicates with the IDE running on the host machine. The container can run locally or on a remote host. This configuration solution is an option for students who are unable to configure their local environment via the existing Maven and JDK setup infrastructure and/or need to build on a remote host due to system constraints. [](https://cs186.gitbook.io/project/common/devcontainer-setup#requirements) Requirements --------------------------------------------------------------------------------------------- ### [](https://cs186.gitbook.io/project/common/devcontainer-setup#docker) Docker Install [Docker](https://www.docker.com/) on the machine running the build container, i.e. your laptop or personal computer. We recommend that you run the build container on the host machine (a personal device); however, it is possible to run the container elsewhere, though course staff is unlikely to support alternate methods. ### [](https://cs186.gitbook.io/project/common/devcontainer-setup#ide) IDE We recommend using IntelliJ IDEA due to its debugging capabilities and are unlikely to support other IDEs. If you prefer a different IDE, see below for instructions to run a development container via Visual Studio Code (VS Code) or GitHub Codespaces. #### [](https://cs186.gitbook.io/project/common/devcontainer-setup#intellij-idea-ultimate) IntelliJ IDEA Ultimate _Note that this version is different from IntelliJ IDEA CE (Community Edition); however, both can remain installed and be used on your device simultaneously._ Development containers are currently supported only in the [Ultimate edition](https://www.jetbrains.com/idea/) of IntelliJ IDEA. You may obtain a free, non-commercial license [here](https://www.jetbrains.com/community/education/#students) on a new or existing JetBrains account using your university address (@berkeley.edu). Note that if you have an existing JetBrains account linked to a different email address, you may need to [link](https://sales.jetbrains.com/hc/en-gb/articles/7654171906706-Linking-multiple-email-addresses-to-your-JetBrains-Account) your personal email to your university email JetBrains account. #### [](https://cs186.gitbook.io/project/common/devcontainer-setup#other-ides) Other IDEs Install your preferred IDE. Note that course staff will only support IntelliJ IDEA Ultimate (recommended), VS Code, and GitHub Codespaces. [](https://cs186.gitbook.io/project/common/devcontainer-setup#creating-the-dev-container) Creating the Dev Container ------------------------------------------------------------------------------------------------------------------------- ### [](https://cs186.gitbook.io/project/common/devcontainer-setup#intellij-idea-ultimate-1) IntelliJ IDEA Ultimate IntelliJ is currently configured to use the [EAP](https://www.jetbrains.com/idea/nextversion/) (early access) version of its IDE to connect to the container by default. The EAP version is the beta version of the IDE that is both less stable and on a license which expires after 30-45 days. To disable this, go to `Settings > Advanced Settings` and uncheck the box "Always use the latest backend" (see [here](https://youtrack.jetbrains.com/articles/SUPPORT-A-551) for the article). ![](https://cs186.gitbook.io/project/~gitbook/image?url=https%3A%2F%2F678656433-files.gitbook.io%2F%7E%2Ffiles%2Fv0%2Fb%2Fgitbook-x-prod.appspot.com%2Fo%2Fspaces%252F-MFVQnrLlCBowpNWJo1E%252Fuploads%252Fgit-blob-e44fd03a4d2a15f5cbf810ec4cd60bc1b23d4b29%252Fdc-0.png%3Falt%3Dmedia&width=768&dpr=4&quality=100&sign=97398ade&sv=2) Screenshot - Uncheck "Always use the latest backend.".png Start the IDE and navigate to "Dev Containers": ![](https://cs186.gitbook.io/project/~gitbook/image?url=https%3A%2F%2F678656433-files.gitbook.io%2F%7E%2Ffiles%2Fv0%2Fb%2Fgitbook-x-prod.appspot.com%2Fo%2Fspaces%252F-MFVQnrLlCBowpNWJo1E%252Fuploads%252Fgit-blob-84484cc566607ddee640f15ff1f8f37ffcfd2d70%252Fdc-1.png%3Falt%3Dmedia&width=768&dpr=4&quality=100&sign=8718d29e&sv=2) Screenshot - Select Dev Containers Create a "New Dev Container": ![](https://cs186.gitbook.io/project/~gitbook/image?url=https%3A%2F%2F678656433-files.gitbook.io%2F%7E%2Ffiles%2Fv0%2Fb%2Fgitbook-x-prod.appspot.com%2Fo%2Fspaces%252F-MFVQnrLlCBowpNWJo1E%252Fuploads%252Fgit-blob-4fdf80595387ea00610b8d4079ed4b1993b85e0a%252Fdc-2.png%3Falt%3Dmedia&width=768&dpr=4&quality=100&sign=f0116d22&sv=2) Screenshot - Select New Dev Container Use the HTTPS address of the rookiedb repository for the relevant project. For example, a student with GitHub username `oski` working on Project 0 would use the repository address `https://github.com/cs186-student/sp25-proj0-oski.git`: ![](https://cs186.gitbook.io/project/~gitbook/image?url=https%3A%2F%2F678656433-files.gitbook.io%2F%7E%2Ffiles%2Fv0%2Fb%2Fgitbook-x-prod.appspot.com%2Fo%2Fspaces%252F-MFVQnrLlCBowpNWJo1E%252Fuploads%252Fgit-blob-769d098e24608da90ca62f0aaf326309dbce8dc9%252Fdc-6.png%3Falt%3Dmedia&width=768&dpr=4&quality=100&sign=d1cd5fe3&sv=2) Screenshot - Add Repository and Branch information Click "Build Container and Continue" and wait for Docker to download and build the image (this will take a few minutes). #### [](https://cs186.gitbook.io/project/common/devcontainer-setup#troubleshooting) Troubleshooting **GitHub Authentication** GitHub [deprecated password-based authentication](https://github.blog/security/application-security/token-authentication-requirements-for-git-operations/) in July 2020, which means that your password no longer works for command-line authentication. If asked to authenticate your GitHub account via IntelliJ, create a [Personal Access Token (PAT)](https://docs.github.com/en/authentication/keeping-your-account-and-data-secure/managing-your-personal-access-tokens#creating-a-personal-access-token-classic) , which you may use to set up each of your dev containers. Ensure that you save your token securely, as it cannot be accessed again via your account. **SSH Repository URL** If you're creating a dev container using the SSH URL instead of the HTTPS URL, you may need to run `ssh-add -k` locally to add your private SSH key to your device. You may run `ssh-add -l` to see the SSH keys currently on your device. ### [](https://cs186.gitbook.io/project/common/devcontainer-setup#visual-studio-code-vs-code-local) Visual Studio Code (VS Code) (local) Select ![Remote Explorer](https://cs186.gitbook.io/project/~gitbook/image?url=https%3A%2F%2F678656433-files.gitbook.io%2F%7E%2Ffiles%2Fv0%2Fb%2Fgitbook-x-prod.appspot.com%2Fo%2Fspaces%252F-MFVQnrLlCBowpNWJo1E%252Fuploads%252Fgit-blob-5978cb5ea5e3d59f3711fc14836bc45ec65bdeea%252Fdc-4.png%3Falt%3Dmedia&width=300&dpr=4&quality=100&sign=b8440293&sv=2) and click the ![plus icon](https://cs186.gitbook.io/project/~gitbook/image?url=https%3A%2F%2F678656433-files.gitbook.io%2F%7E%2Ffiles%2Fv0%2Fb%2Fgitbook-x-prod.appspot.com%2Fo%2Fspaces%252F-MFVQnrLlCBowpNWJo1E%252Fuploads%252Fgit-blob-9baa4345176eeb0c21f5c9b52d8210e05370fda0%252Fdc-5.png%3Falt%3Dmedia&width=300&dpr=4&quality=100&sign=ebc0e970&sv=2) to create a new dev container. Then select `Clone Repository in Container Volume` and follow prompts to clone the repository into the container. ### [](https://cs186.gitbook.io/project/common/devcontainer-setup#codespaces-vs-code-or-web-browser) Codespaces (VS Code or web browser) A [GitHub Codespace](https://github.com/features/codespaces) runs the build container in Azure, either in a browser or through the VS Code application. Either open VS Code or the web-based editor for the repository, `https://github.dev/cs186-student/sp25-projX-username`, by navigating through `github.dev` instead of `github.com`. Select ![Remote Explorer](https://cs186.gitbook.io/project/~gitbook/image?url=https%3A%2F%2F678656433-files.gitbook.io%2F%7E%2Ffiles%2Fv0%2Fb%2Fgitbook-x-prod.appspot.com%2Fo%2Fspaces%252F-MFVQnrLlCBowpNWJo1E%252Fuploads%252Fgit-blob-5978cb5ea5e3d59f3711fc14836bc45ec65bdeea%252Fdc-4.png%3Falt%3Dmedia&width=300&dpr=4&quality=100&sign=b8440293&sv=2) and click on "Create Codespace." Please consult the documentation for latest pricing information. GitHub currently provides 120 core-hours (60 hours in the least-capable image) per month to all users for free. If you elect to run in this or another remote configuration, course staff may be unable to provide support. [](https://cs186.gitbook.io/project/common/devcontainer-setup#undefined) ---------------------------------------------------------------------------- CS 186 Spring 2025 Authors: Chris Douglas, Janani Sriram [PreviousAdding a partner on GitHub](https://cs186.gitbook.io/project/common/adding-a-partner-on-github) [NextMiscellaneous](https://cs186.gitbook.io/project/common/misc) Last updated 9 months ago --- # Getting Started | CS186 Projects [](https://cs186.gitbook.io/project/assignments/proj4/getting-started#logistics) Logistics ----------------------------------------------------------------------------------------------- This project is worth 8% of your overall grade in the class. * Part 1 is due **Friday, 3/28/2025 at 11:59PM PDT (GMT-7)** and will be worth 20% of your score. Your score will be determined by public tests only. * Part 2 is due **Thursday, 4/3/2025 at 11:59PM PDT (GMT-7)** and will be worth the remaining 80% of your score. We'll be running the public tests for Part 2 and all hidden tests for both Part 1 and Part 2 on this submission. The workload for the project is designed to be completed solo, but this semester we're allowing students to work on this project with a partner if you want to. Your partner does not have to be the same as the one you had for previous assignments. Feel free to search for a partner on [this Edstem thread](https://edstem.org/us/courses/70276/discussion/5999429) ! **A gentle reminder that though our projects have tight release schedules, projects don't tend to take the entire time given to complete them :)** [](https://cs186.gitbook.io/project/assignments/proj4/getting-started#prerequisites) Prerequisites ------------------------------------------------------------------------------------------------------- You should watch both Transactions & Concurrency lectures before beginning this project. [](https://cs186.gitbook.io/project/assignments/proj4/getting-started#academic-integrity-policy) Academic Integrity Policy ------------------------------------------------------------------------------------------------------------------------------- “_As a member of the UC Berkeley community, I act with honesty, integrity, and respect for others._” — UC Berkeley Honor Code **Read through the academic integrity guidelines** [**here**](https://cs186berkeley.net/integrityguidelines/) **.** We will be running plagiarism detection software on every submission against our own database of this semester's submissions, past submissions, and publicly hosted implementations on platforms such as GitHub and GitLab, followed by a thorough manual review process. Plagiarism on any assignment will result in a [non-reportable warning](https://conduct.berkeley.edu/wp-content/uploads/2024/01/Academic-Misconduct-Resource-Sheet-for-Students-UPDATED.pdf) and a grade penalty based on the severity of the infraction. As long as you follow the guidelines, there isn't anything to worry about here. While we do rely on software to find possible cases of academic dishonesty, every case is reviewed by multiple TAs who can filter out false positives. [](https://cs186.gitbook.io/project/assignments/proj4/getting-started#additional-resources) Additional Resources --------------------------------------------------------------------------------------------------------------------- Debugging walkthrough video for project 4 task 2 can be found [here](https://drive.google.com/drive/folders/1UnpcSU-rG9VAHfsD5WXO8CfFuzEDbwH_?usp=sharing) . [](https://cs186.gitbook.io/project/assignments/proj4/getting-started#fetching-the-released-code) Fetching the released code --------------------------------------------------------------------------------------------------------------------------------- The GitHub Classroom link for this project is in the Project 4 release post on [Edstem](https://edstem.org/us/courses/70276/discussion/) . Once your private repo is set up clone the Project 4 skeleton code onto your local machine. ### [](https://cs186.gitbook.io/project/assignments/proj4/getting-started#setting-up-your-local-development-environment) Setting up your local development environment If you're using IntelliJ you can follow the instructions [in Project 0](https://cs186.gitbook.io/project/assignments/proj0/getting-started#setting-up-your-local-development-environment) in to set up your local environment again. Once you have your environment set up you can head to the next section [Part 0](https://cs186.gitbook.io/project/assignments/proj4/skeleton-code) and begin working on the assignment. [](https://cs186.gitbook.io/project/assignments/proj4/getting-started#working-with-a-partner) Working with a partner ------------------------------------------------------------------------------------------------------------------------- Only one partner has to submit, but please make sure to add the other partner to the Gradescope submission. If you want to share code over GitHub you can follow the instructions [here](https://cs186.gitbook.io/project/common/adding-a-partner-on-github) . [](https://cs186.gitbook.io/project/assignments/proj4/getting-started#debugging-issues-with-github-classroom) Debugging Issues with GitHub Classroom --------------------------------------------------------------------------------------------------------------------------------------------------------- Feel free to skip this section if you don't have any issues with GitHub Classroom. If you are having issues (i.e. the page froze or some error message appeared), first check if you have access to your repo at `https://github.com/cs186-student/sp25-proj4-username`, replacing `username` with your GitHub username. If you have access to your repo and the starter code is there, then you can proceed as usual. #### [](https://cs186.gitbook.io/project/assignments/proj4/getting-started#id-404-not-found) 404 Not Found If you're getting a 404 not found page when trying to access your repo, make sure you've set up your repo using the GitHub Classroom link in the Project 4 release post on [Edstem](https://edstem.org/us/courses/70276/discussion/) . If you don't have access to your repo at all after following these steps, feel free to contact the course staff on Edstem. [PreviousProject 4: Concurrency](https://cs186.gitbook.io/project/assignments/proj4) [NextPart 0: Skeleton Code](https://cs186.gitbook.io/project/assignments/proj4/skeleton-code) Last updated 8 months ago --- # Getting Started | CS186 Projects [](https://cs186.gitbook.io/project/assignments/proj0/getting-started#logistics) Logistics ----------------------------------------------------------------------------------------------- This assignment is due **Thursday, 1/30/2025 at 11:59PM PST (GMT-8)**. It is worth 0% of your overall grade, but failure to complete it may result in being **administratively dropped from the class**. [](https://cs186.gitbook.io/project/assignments/proj0/getting-started#prerequisites) Prerequisites ------------------------------------------------------------------------------------------------------- No lectures are required to work through this assignment. [](https://cs186.gitbook.io/project/assignments/proj0/getting-started#git-and-github) `git` and GitHub ----------------------------------------------------------------------------------------------------------- [git](https://en.wikipedia.org/wiki/Git) is a _version control_ system, that helps developers like you track different versions of your code, synchronize them across different machines, and collaborate with others. If you don't already have git on your machine you can follow the instructions [here](https://git-scm.com/book/en/v2/Getting-Started-Installing-Git) to install it. [GitHub](https://github.com/) is a site which supports this system, hosting it as a service. In order to get a copies of the skeleton code to work on during the semester you'll need to create an account. We will be using git and GitHub to pass out assignments in this course. If you don't know much about git, that isn't a problem: you will _need_ to use it only in very simple ways that we will show you in order to keep up with class assignments. If you'd like to use git for managing your own code versioning, there are many guides to using git online -- [this](http://git-scm.com/book/en/v1/Getting-Started) is a good one. ### [](https://cs186.gitbook.io/project/assignments/proj0/getting-started#fetching-the-released-code) Fetching the released code For each project, we will provide a GitHub Classroom link. Follow the link to create a GitHub repository with the starter code for the project you are working on. Use `git clone` to get a local copy of the newly created repository. For example, if your GitHub username is `oski` after being assigned your repo through GitHub Classroom you would run: `git clone https://github.com/cs186-student/sp25-proj0-oski` The GitHub Classroom link for this project is provided in the project release post on [Edstem](https://edstem.org/us/courses/70276/discussion/) . ### [](https://cs186.gitbook.io/project/assignments/proj0/getting-started#debugging-issues-with-github-classroom) Debugging Issues with GitHub Classroom Feel free to skip this section if you don't have any issues with GitHub Classroom. If you are having issues (i.e. the page froze or some error message appeared), first check if you have access to your repo at `https://github.com/cs186-student/sp25-proj0-username`, replacing `username` with your GitHub username. If you have access to your repo and the starter code is there, then you can proceed as usual. #### [](https://cs186.gitbook.io/project/assignments/proj0/getting-started#id-404-not-found) 404 Not Found If you're getting a 404 not found page when trying to access your repo, make sure you've set up your repo using the GitHub Classroom link in the Project 0 release post on [Edstem](https://edstem.org/us/courses/70276/discussion/) . If you don't have access to your repo at all after following these steps, feel free to contact the course staff on Edstem. [](https://cs186.gitbook.io/project/assignments/proj0/getting-started#setting-up-your-local-development-environment) Setting up your local development environment ----------------------------------------------------------------------------------------------------------------------------------------------------------------------- You are free to use any text editor or IDE to complete the assignments, but **we will build and test your code in a Docker container with Maven**. We recommend setting up a local development environment by installing Java 11 locally (the version our Docker container runs) and using an IDE such as IntelliJ. (_Please make sure you have at least Intellij 2019 version, some of the issues from previous semesters are from a too old Intellij_) [Java 11 downloads](https://www.oracle.com/java/technologies/downloads/#java11) (or alternatively, you're free to use [OpenJDK](https://openjdk.java.net/install/) ). You may find a local version of JDK version 11.0.23 [here](https://drive.google.com/file/d/1DZIXu-3u-A6Duo_nisQC2Z5OZToBbh6I/view?usp=drive_link) . To import the project into IntelliJ, click `Open`, and select the `pom.xml` file when importing. `pom.xml` is what stores the configuration and dependencies you need for the project. Once it is scanned, Maven will use the information in it to build the project for you! ![](https://cs186.gitbook.io/project/~gitbook/image?url=https%3A%2F%2F678656433-files.gitbook.io%2F%7E%2Ffiles%2Fv0%2Fb%2Fgitbook-x-prod.appspot.com%2Fo%2Fspaces%252F-MFVQnrLlCBowpNWJo1E%252Fuploads%252Fgit-blob-10e72377349689588802744fdf9cd2aef4e091ef%252Fintellijopen.jpg%3Falt%3Dmedia&width=768&dpr=4&quality=100&sign=7e832dac&sv=2) After hitting Open, navigate to the pom.xml file, open it, and then select "Open as Project" If launching IntelliJ takes you to an existing workspace instead of showing you the popup above you can open the project by navigating to `File -> New -> Project From Existing Sources` and then select the `pom.xml` file and click "OK". "Trust" the project if you are prompted. If you previously had used other versions of Java to build the project, you can change to Java 11 by `File -> Project Structure... -> Change Project SDK to the one you want to use`. ### [](https://cs186.gitbook.io/project/assignments/proj0/getting-started#alternate-development-environment-setup) Alternate development environment setup If the above setup instructions don't work, most often due to unresolvable Maven or JDK issues, you may use a development container; see [here](https://cs186.gitbook.io/project/common/devcontainer-setup) for instructions. Note that this option is only for students whose devices are incompatible with the above setup instructions. ### [](https://cs186.gitbook.io/project/assignments/proj0/getting-started#running-tests-in-intellij) Running tests in IntelliJ If you are using IntelliJ and wish to run the tests for a given assignment follow the instructions below. 1. Navigate to one of the test files for the project. For example, for Project 2 navigate to src/java/test/.../index/TestBPlusNode.java. 2. Navigate to one of the tests (as shown below). Click on the green arrow and run the test (it should fail). ![](https://cs186.gitbook.io/project/~gitbook/image?url=https%3A%2F%2F678656433-files.gitbook.io%2F%7E%2Ffiles%2Fv0%2Fb%2Fgitbook-x-prod.appspot.com%2Fo%2Fspaces%252F-MFVQnrLlCBowpNWJo1E%252Fuploads%252Fgit-blob-c3b6cf0dc800964a5084b628023da9cd050d42e5%252FScreen%2520Shot%25202022-01-17%2520at%252010.56.04%2520PM.png%3Falt%3Dmedia&width=768&dpr=4&quality=100&sign=26f27f7c&sv=2) If the green arrow does not appear or you're unable to run the test, follow the steps below. 1. Open up Run/Debug Configurations with Run > Edit Configurations. 2. Click the + button in the top left to create a new configuration, and choose JUnit from the dropdown. Fill in the configurations as shown below and click ok. Make sure to click Modify Options > Search for tests > In whole project. ![](https://cs186.gitbook.io/project/~gitbook/image?url=https%3A%2F%2F678656433-files.gitbook.io%2F%7E%2Ffiles%2Fv0%2Fb%2Fgitbook-x-prod.appspot.com%2Fo%2Fspaces%252F-MFVQnrLlCBowpNWJo1E%252Fuploads%252Fgit-blob-82fa7265153e0bf1704e2f075de793e54f2be632%252FScreen%2520Shot%25202022-01-17%2520at%252011.14.15%2520PM.png%3Falt%3Dmedia&width=768&dpr=4&quality=100&sign=2852353d&sv=2) Your interface may look different depending on your version of IntelliJ. You should now see Project 2 tests in the dropdown in the top right. You can run/debug this configuration to run all the Project 2 tests. _If for some reason you still cannot run the tests, it's likely that you had one of the steps above wrong. At this time, the best thing to do is to re-clone the project and go through the setting up again. Some students may try re-importing the_ `_pom.xml_` _file, but there could be some configuration being polluted, so the safest option is to re-clone the project and import the_ `_pom.xml_` _file again._ Once you have a copy of the released code, head to the next section "Your Tasks" and begin working on the assignment. [PreviousProject 0: Setup](https://cs186.gitbook.io/project/assignments/proj0) [NextYour Tasks](https://cs186.gitbook.io/project/assignments/proj0/your-tasks) Last updated 9 months ago --- # Project 0: Setup | CS186 Projects [Getting Started](https://cs186.gitbook.io/project/assignments/proj0/getting-started) [Your Tasks](https://cs186.gitbook.io/project/assignments/proj0/your-tasks) [Submitting the Assignment](https://cs186.gitbook.io/project/assignments/proj0/submitting) [PreviousOverview](https://cs186.gitbook.io/project) [NextGetting Started](https://cs186.gitbook.io/project/assignments/proj0/getting-started) Last updated 1 year ago --- # Part 1: Queuing | CS186 Projects ![](https://cs186.gitbook.io/project/~gitbook/image?url=https%3A%2F%2F678656433-files.gitbook.io%2F%7E%2Ffiles%2Fv0%2Fb%2Fgitbook-x-prod.appspot.com%2Fo%2Fspaces%252F-MFVQnrLlCBowpNWJo1E%252Fuploads%252Fgit-blob-dd341262e48f22f122b8410acac172c286eecfb0%252Fdatarace%2520%281%29%2520%281%29%2520%282%29%2520%282%29%2520%283%29%2520%283%29%2520%282%29%2520%285%29.png%3Falt%3Dmedia%26token%3Df573d82d-eda3-4f10-a526-343b40ddb4e0&width=768&dpr=4&quality=100&sign=72f6bae9&sv=2) Datarace In this part you will implement some helpers functions for lock types and the queuing system for locks. The `concurrency` directory contains a partial implementation of a lock manager (`LockManager.java`), which you will be completing. Note on terminology: in this project, "children" and "parent" refer to the resource(s) directly below/above a resource in the hierarchy. "Descendants" and "ancestors" are used when we wish to refer to all resource(s) below/above in the hierarchy. [](https://cs186.gitbook.io/project/assignments/proj4/part-1-lockmanager#your-tasks) Your Tasks ---------------------------------------------------------------------------------------------------- Based on student feedback from previous semesters, we estimate that this part of the project will take approximately 15-20 hours to complete. We have also included a star-based difficulty ranking per task, relative to the rest of the project, as a guide for pacing your work. _Please note that every student works at a different pace, and it's absolutely ok to spend more or less time on the project than the provided estimates!_ ### [](https://cs186.gitbook.io/project/assignments/proj4/part-1-lockmanager#task-1-locktype) Task 1: LockType _Difficulty: ★★☆☆☆_ Before you start implementing the queuing logic, you need to keep track of all the lock types supported, and how they interact with each other. The [`LockType`](https://github.com/berkeley-cs186/sp25-rookiedb/blob/master/src/main/java/edu/berkeley/cs186/database/concurrency/LockType.java) class contains methods reasoning about this, which will come in handy in the rest of the project. For the purposes of this project, a transaction with: * `S(A)` can read A and all descendants of A. * `X(A)` can read and write A and all descendants of A. * `IS(A)` can request shared and intent-shared locks on all children of A. * `IX(A)` can request any lock on all children of A. * `SIX(A)` can do anything that having `S(A)` or `IX(A)` lets it do, except requesting S, IS, or SIX\*\* locks on children of A, which would be redundant. \*\* This differs from how its presented in lecture, where SIX(A) allows a transaction to request SIX locks on children of A. We disallow this in the project since the S aspect of the SIX child would be redundant. You will need to implement the `compatible`, `canBeParentLock`, and `substitutable` methods: * [`compatible(A, B)`](https://github.com/berkeley-cs186/sp25-rookiedb/blob/master/src/main/java/edu/berkeley/cs186/database/concurrency/LockType.java#L14) checks if lock type A is compatible with lock type B -- can one transaction have lock A while another transaction has lock B on the same resource? For example, two transactions can have S locks on the same resource, so `compatible(S, S) = true`, but two transactions cannot have X locks on the same resource, so `compatible(X, X) = false`. * [`canBeParentLock(A, B)`](https://github.com/berkeley-cs186/sp25-rookiedb/blob/master/src/main/java/edu/berkeley/cs186/database/concurrency/LockType.java#L48) returns true if having A on a resource lets a transaction acquire a lock of type B on a child. For example, in order to get an S lock on a table, we must have (at the very least) an IS lock on the parent of table: the database. So `canBeParentLock(IS, S) = true`. * [`substitutable(substitute, required)`](https://github.com/berkeley-cs186/sp25-rookiedb/blob/master/src/main/java/edu/berkeley/cs186/database/concurrency/LockType.java#L61) checks if one lock type (`substitute`) can be used in place of another (`required`). This is only the case if a transaction having `substitute` can do everything that a transaction having `required` can do. Another way of looking at this is: let a transaction request the required lock. Can there be any problems if we secretly give it the substitute lock instead? For example, if a transaction requested an X lock, and we quietly gave it an S lock, there would be problems if the transaction tries to write to the resource. Therefore, `substitutable(S, X) = false`. Once you complete this task you should be passing all the tests in [`TestLockType.java`](https://github.com/berkeley-cs186/sp25-rookiedb/blob/master/src/test/java/edu/berkeley/cs186/database/concurrency/TestLockType.java) . ### [](https://cs186.gitbook.io/project/assignments/proj4/part-1-lockmanager#task-2-lockmanager) Task 2: LockManager _Difficulty: ★★★★☆_ **Note:** Your Part 1 submission will only need to pass the following tests from this task for full credit: * TestLockManager.testSimpleAcquireLock * TestLockManager.testSimpleAcquireLockFail * TestLockManager.testSimpleReleaseLock * TestLockManager.testReleaseUnheldLock * TestLockManager.testSimpleConflict The remaining tests will be tested in the Part 2 submission. The [`LockManager`](https://github.com/berkeley-cs186/sp25-rookiedb/blob/master/src/main/java/edu/berkeley/cs186/database/concurrency/LockManager.java) class handles locking for individual resources. We will add multigranularity constraints in Part 2. **Before you start coding**, you should understand what the lock manager does, what each method of the lock manager is responsible for, and how the internal state of the lock manager changes with each operation. The different methods of the lock manager are not independent: trying to implement one without consideration of the others will cause you to spend significantly more time on this project. There is a fair amount of logic shared between methods, and it may be worth spending a bit of time writing some helper methods. A simple example of a blocking acquire call is described at the bottom of this section -- you should understand it and be able to describe any other combination of calls before implementing any method. You will need to implement the following methods of `LockManager`: * [`acquireAndRelease`](https://github.com/berkeley-cs186/sp25-rookiedb/blob/master/src/main/java/edu/berkeley/cs186/database/concurrency/LockManager.java#L155) : this method atomically (from the user's perspective) acquires one lock and releases zero or more locks. This method has priority over any queued requests (it should proceed even if there is a queue, and it is placed in the front of the queue if it cannot proceed). * [`acquire`](https://github.com/berkeley-cs186/sp25-rookiedb/blob/master/src/main/java/edu/berkeley/cs186/database/concurrency/LockManager.java#L182) : this method is the standard `acquire` method of a lock manager. It allows a transaction to request one lock, and grants the request if there is no queue and the request is compatible with existing locks. Otherwise, it should queue the request (at the back) and block the transaction. We do not allow implicit lock upgrades, so requesting an X lock on a resource the transaction already has an S lock on is invalid. * [`release`](https://github.com/berkeley-cs186/sp25-rookiedb/blob/master/src/main/java/edu/berkeley/cs186/database/concurrency/LockManager.java#L207) : this method is the standard `release` method of a lock manager. It allows a transaction to release one lock that it holds. * [`promote`](https://github.com/berkeley-cs186/sp25-rookiedb/blob/master/src/main/java/edu/berkeley/cs186/database/concurrency/LockManager.java#L237) : this method allows a transaction to explicitly promote/upgrade a held lock. The lock the transaction holds on a resource is replaced with a stronger lock on the same resource. This method has priority over any queued requests (it should proceed even if there is a queue, and it is placed in the front of the queue if it cannot proceed). We do not allow promotions to SIX, those types of requests should go to `acquireAndRelease`. This is because during SIX lock upgrades, it is possible we might need to also release redundant locks, so we need to handle these upgrades with `acquireAndRelease`. * [`getLockType`](https://github.com/berkeley-cs186/sp25-rookiedb/blob/master/src/main/java/edu/berkeley/cs186/database/concurrency/LockManager.java#L255) : this is the main way to query the lock manager, and returns the type of lock that a transaction has on a specific resource., which was implemented in the previous step. The following helper methods may come in handy for this task: methods of the `ResourceEntry` class which you will implement, `getResourceEntry`, methods of the `LockType` class. #### [](https://cs186.gitbook.io/project/assignments/proj4/part-1-lockmanager#queues) Queues Whenever a request for a lock cannot be satisfied (either because it conflicts with locks other transactions already have on the resource, or because there's a queue of requests for locks on the resource and the operation does not have priority over the queue), it should be placed on the queue (at the back, unless otherwise specified) for the resource, and the transaction making the request should be blocked. The queue for each resource is processed independently of other queues, and must be processed after a lock on the resource is released, in the following manner: * The request at the front of the queue is considered, and if it doesn't conflict with any of the existing locks on the resource, it should be removed from the queue and: * the transaction that made the request should be given the lock * any locks that the request stated should be released are released * the transaction that made the request should be unblocked * The previous step should be repeated until the first request on the queue cannot be satisfied or the queue is empty. #### [](https://cs186.gitbook.io/project/assignments/proj4/part-1-lockmanager#synchronization) **Synchronization** `LockManager`'s methods have `synchronized` blocks to ensure that calls to `LockManager` are serial and that there is no interleaving of calls. You may want to read up on [synchronized methods](https://docs.oracle.com/javase/tutorial/essential/concurrency/syncmeth.html) and [synchronized statements](https://docs.oracle.com/javase/tutorial/essential/concurrency/locksync.html) in Java. You should make sure that all accesses (both queries and modifications) to lock manager state in a method is inside **one** synchronized block, for example: Copy // Correct, use a single synchronized block void acquire(...) { synchronized (this) { ResourceEntry entry = getResourceEntry(name); // fetch resource entry // do stuff entry.locks.add(...); // add to list of locks } } // Incorrect, multiple synchronized blocks void acquire(...) { synchronized (this) { ResourceEntry entry = getResourceEntry(name); // fetch resource entry } // first synchronized block ended: another call to LockManager can start here synchronized (this) { // do stuff entry.locks.add(...); // add to list of locks } } // Incorrect, doing work outside of the synchronized block void acquire(...) { ResourceEntry entry = getResourceEntry(name); // fetch resource entry // do stuff // other calls can run while the above code runs, which means we could // be using outdated lock manager state synchronized (this) { entry.locks.add(...); // add to list of locks } } Transactions block the entire thread when blocked, which means that you cannot block the transaction inside the `synchronized` block (this would prevent any other call to `LockManager` from running until the transaction is unblocked... which is never, since the `LockManager` is the one that unblocks the transaction). To block a transaction, call `Transaction#prepareBlock` **inside** the synchronized block, and then call `Transaction#block` **outside** the synchronized block. The `Transaction#prepareBlock` needs to be in the synchronized block to avoid a race condition where the transaction may be dequeued between the time it leaves the synchronized block and the time it actually blocks. If tests in `TestLockManager` are timing out, double-check that you are calling `prepareBlock` and `block` in the manner described above, and that you are not calling `prepareBlock` without `block`. (It could also just be a regular infinite loop, but checking that you're handling synchronization correctly is a good place to start). **Example** Consider the following calls (this is what `testSimpleConflict` tests): Copy // initialized elsewhere, T1 has transaction number 1, // T2 has transaction number 2 Transaction t1, t2; LockManager lockman = new LockManager(); ResourceName db = new ResourceName("database"); lockman.acquire(t1, db, LockType.X); // t1 requests X(db) lockman.acquire(t2, db, LockType.X); // t2 requests X(db) lockman.release(t1, db); // t1 releases X(db) In the first call, T1 requests an X lock on the database. There are no other locks on database, so we grant T1 the lock. We add X(db) to the list of locks T1 has (in `transactionLocks`), as well as to the locks held on the database (in `resourceLocks`). Our internal state now looks like: Copy transactionLocks: { 1 => [ X(db) ] } (transaction 1 has 1 lock: X(db)) resourceEntries: { db => { locks: [ {1, X(db)} ], queue: [] } } (there is 1 lock on db: an X lock by transaction 1, nothing on the queue) In the second call, T2 requests an X lock on the database. T1 already has an X lock on database, so T2 is not granted the lock. We add T2's request to the queue, and block T2. Our internal state now looks like: Copy transactionLocks: {1 => [X(db)]} (transaction 1 has 1 lock: X(db)) resourceEntries: {db => {locks: [{1, X(db)}], queue: [LockRequest(T2, X(db))]}} (there is 1 lock on db: an X lock by transaction 1, and 1 request on queue: a request for X by transaction 2) In the last call, T1 releases an X lock on the database. T2's request can now be processed, so we remove T2 from the queue, grant it the lock by updating `transactionLocks` and `resourceLocks`, and unblock it. Our internal state now looks like: Copy transactionLocks: { 2 => [ X(db) ] } (transaction 2 has 1 lock: X(db)) resourceEntries: { db => { locks: [ {2, X(db)} ], queue: [] } } (there is 1 lock on db: an X lock by transaction 2, nothing on the queue) [](https://cs186.gitbook.io/project/assignments/proj4/part-1-lockmanager#submission) Submission ---------------------------------------------------------------------------------------------------- After this, you should pass all the tests we have provided to you in [`database.concurrency.TestLockType`](https://github.com/berkeley-cs186/sp25-rookiedb/blob/master/src/test/java/edu/berkeley/cs186/database/concurrency/TestLockType.java) and [`database.concurrency.TestLockManager`](https://github.com/berkeley-cs186/sp25-rookiedb/blob/master/src/test/java/edu/berkeley/cs186/database/concurrency/TestLockManager.java) . Remember that for the Part 1 submission you only need to pass the first 5 tests of TestLockManager for full credit. Note that you may **not** modify the signature of any methods or classes that we provide to you, but you're free to add helper methods. Also, you should only modify code in the `concurrency` directory for this part. [PreviousPart 0: Skeleton Code](https://cs186.gitbook.io/project/assignments/proj4/skeleton-code) [NextPart 2: Multigranularity](https://cs186.gitbook.io/project/assignments/proj4/part-2-lockcontext-and-lockutil) Last updated 8 months ago --- # Your Tasks | CS186 Projects For this assignment you will get acquainted with running RookieDB's command line interface and make a small change to one file to get things working properly. [](https://cs186.gitbook.io/project/assignments/proj0/your-tasks#task-1-running-the-cli) Task 1: Running the CLI --------------------------------------------------------------------------------------------------------------------- Most databases provide a command line interface (CLI) to send and view the results of queries. To run the CLI in IntelliJ navigate to the file: `src/main/java/edu/berkeley/cs186/database/cli/CommandLineInterface` It's okay if you don't understand most of the code here right now, we just want to run it. Locate the arrow next to the class declaration click on it to start the CLI. _Note: If you see the warning_ Copy Required type: List Provided: List _It is because you are using a very new version of Java. If you find it concerning to see the red line in Intellij, follow the steps in the previous page to change the Java SDK_ ![](https://cs186.gitbook.io/project/~gitbook/image?url=https%3A%2F%2F678656433-files.gitbook.io%2F%7E%2Ffiles%2Fv0%2Fb%2Fgitbook-legacy-files%2Fo%2Fassets%252F-MFVQnrLlCBowpNWJo1E%252Fsync%252F5a4de4c7d0ddde02ad4bd05e3938198a93f3c469.png%3Fgeneration%3D1598272179258074%26alt%3Dmedia&width=768&dpr=4&quality=100&sign=da376aaa&sv=2) Click the arrow (circled in red above) to run the CLI This should open a new panel in IntelliJ resembling the following image: ![](https://cs186.gitbook.io/project/~gitbook/image?url=https%3A%2F%2F678656433-files.gitbook.io%2F%7E%2Ffiles%2Fv0%2Fb%2Fgitbook-x-prod.appspot.com%2Fo%2Fspaces%252F-MFVQnrLlCBowpNWJo1E%252Fuploads%252Fgit-blob-39d89c33aadc2526e0a5d9ceeb91c8e4c8252106%252Fimage%2520%2810%29%2520%281%29%2520%281%29.png%3Falt%3Dmedia&width=768&dpr=4&quality=100&sign=77237784&sv=2) Click on this panel and try typing in the following query and hitting enter: `SELECT * FROM Courses LIMIT 5;` You should get something similar to the following output: ![](https://cs186.gitbook.io/project/~gitbook/image?url=https%3A%2F%2F678656433-files.gitbook.io%2F%7E%2Ffiles%2Fv0%2Fb%2Fgitbook-legacy-files%2Fo%2Fassets%252F-MFVQnrLlCBowpNWJo1E%252Fsync%252Fb720005287f6253bac3bf8df4fc9be45f1ae035a.png%3Fgeneration%3D1598272178939307%26alt%3Dmedia&width=768&dpr=4&quality=100&sign=551d402e&sv=2) Hmm, that doesn't look quite right! Follow the instructions in the next task to get the proper output. To exit the CLI just type in `exit` and hit enter. [](https://cs186.gitbook.io/project/assignments/proj0/your-tasks#task-2-welcome-to-cs186) Task 2: Welcome to CS186! ------------------------------------------------------------------------------------------------------------------------ Open up `src/main/java/edu/berkeley/cs186/database/databox/StringDataBox.java`. It's okay if you do not understand most of the code right now. The `toString` method currently looks like: Copy @Override public String toString() { // TODO(proj0): replace the following line with `return s;` return "FIX ME"; } Follow the instructions in the `TODO(proj0)` comment to fix the return statement. Navigate to`src/test/java/edu/berkeley/cs186/database/databox/TestWelcome.java` and try running the test in the file, which should now be passing. Now you can run through Task 1 again to see what the proper output should be. (If you see anything highlighted in red in the test file, its likely that JUnit wasn't automatically added to the classpath. If this is the case, find the first failed import and hover over the portion marked in red. This should bring up a tooltip with the option "Add JUnit to classpath". Select this option. Afterwards, no errors should appear in the file.) [](https://cs186.gitbook.io/project/assignments/proj0/your-tasks#task-3-debugging-exercise) Task 3: Debugging Exercise --------------------------------------------------------------------------------------------------------------------------- In this course, a majority of the projects are written in Java and involve modifying a large codebase. Knowing how to effectively utilize the IntelliJ debugger will be important in identifying errors with your code. Let's cover the basics of using the IntelliJ debugger! As you follow along with the steps below, please submit your answers to this [Gradescope assignment](https://www.gradescope.com/courses/932632/assignments/5640417) . You must complete this for full credit. Let's start by navigating to src/test/java/.../index/TestBPlusNode.java. #### [](https://cs186.gitbook.io/project/assignments/proj0/your-tasks#breakpoints) Breakpoints Place a breakpoint as shown below. Breakpoints allow you to select locations in your code where you want the debugger to pause. ![](https://cs186.gitbook.io/project/~gitbook/image?url=https%3A%2F%2F678656433-files.gitbook.io%2F%7E%2Ffiles%2Fv0%2Fb%2Fgitbook-x-prod.appspot.com%2Fo%2Fspaces%252F-MFVQnrLlCBowpNWJo1E%252Fuploads%252Fgit-blob-cefaeedac3f3d354e1e551f58190f622a2e5a9b8%252FScreen%2520Shot%25202022-01-17%2520at%252011.41.55%2520PM.png%3Falt%3Dmedia&width=768&dpr=4&quality=100&sign=e2c4191e&sv=2) #### [](https://cs186.gitbook.io/project/assignments/proj0/your-tasks#running-the-debugger) Running the debugger Select the green arrow next to the function header for testFromBytes. In the dropdown menu, click debug. This will open a debugging console at the bottom. The code is currently paused at the line we placed a breakpoint on. ![](https://cs186.gitbook.io/project/~gitbook/image?url=https%3A%2F%2F678656433-files.gitbook.io%2F%7E%2Ffiles%2Fv0%2Fb%2Fgitbook-x-prod.appspot.com%2Fo%2Fspaces%252F-MFVQnrLlCBowpNWJo1E%252Fuploads%252Fgit-blob-011bd2fe36bc500c293199d90e311fc7e919728f%252FScreen%2520Shot%25202022-01-17%2520at%252011.39.45%2520PM.png%3Falt%3Dmedia&width=768&dpr=4&quality=100&sign=557ac103&sv=2) #### [](https://cs186.gitbook.io/project/assignments/proj0/your-tasks#inspecting-variables) Inspecting variables ![](https://cs186.gitbook.io/project/~gitbook/image?url=https%3A%2F%2F678656433-files.gitbook.io%2F%7E%2Ffiles%2Fv0%2Fb%2Fgitbook-x-prod.appspot.com%2Fo%2Fspaces%252F-MFVQnrLlCBowpNWJo1E%252Fuploads%252Fgit-blob-5005c51313e4c645a5920f74a21d3cfe74c049db%252FScreen%2520Shot%25202022-01-17%2520at%252011.56.14%2520PM%2520copy.jpg%3Falt%3Dmedia&width=768&dpr=4&quality=100&sign=a96a6fe1&sv=2) The debugger allows you to inspect relevant variables in the code Question 1: What is the current size of 'leafKeys'? #### [](https://cs186.gitbook.io/project/assignments/proj0/your-tasks#step-into) Step into Click on the button shown below to step into the LeafNode constructor. ![](https://cs186.gitbook.io/project/~gitbook/image?url=https%3A%2F%2F678656433-files.gitbook.io%2F%7E%2Ffiles%2Fv0%2Fb%2Fgitbook-x-prod.appspot.com%2Fo%2Fspaces%252F-MFVQnrLlCBowpNWJo1E%252Fuploads%252Fgit-blob-22816b4115593b7a5d39f94b7159e676dd6e5a21%252FScreen%2520Shot%25202022-01-18%2520at%252012.00.53%2520AM%2520copy.jpg%3Falt%3Dmedia&width=768&dpr=4&quality=100&sign=a0ec8afe&sv=2) #### [](https://cs186.gitbook.io/project/assignments/proj0/your-tasks#step-over) Step over Click on the button shown below to step forward one line. ![](https://cs186.gitbook.io/project/~gitbook/image?url=https%3A%2F%2F678656433-files.gitbook.io%2F%7E%2Ffiles%2Fv0%2Fb%2Fgitbook-x-prod.appspot.com%2Fo%2Fspaces%252F-MFVQnrLlCBowpNWJo1E%252Fuploads%252Fgit-blob-158acca96e636deb264f7fc10be4e94e8cb11edd%252FScreen%2520Shot%25202022-01-18%2520at%252012.00.53%2520AM%2520copy%25202.jpg%3Falt%3Dmedia&width=768&dpr=4&quality=100&sign=7396111b&sv=2) Question 2: What is the current size of 'rids'? #### [](https://cs186.gitbook.io/project/assignments/proj0/your-tasks#resume-execution) Resume execution This button allows you to resume execution of your program until it reaches another breakpoint. Don't worry if testFromBytes fails after resuming execution. You won't pass this test until project 2. ![](https://cs186.gitbook.io/project/~gitbook/image?url=https%3A%2F%2F678656433-files.gitbook.io%2F%7E%2Ffiles%2Fv0%2Fb%2Fgitbook-x-prod.appspot.com%2Fo%2Fspaces%252F-MFVQnrLlCBowpNWJo1E%252Fuploads%252Fgit-blob-f5150b86001e689409a26af728c10efb44530456%252FScreen%2520Shot%25202022-01-18%2520at%252012.00.53%2520AM.png%3Falt%3Dmedia&width=768&dpr=4&quality=100&sign=86ff1095&sv=2) [](https://cs186.gitbook.io/project/assignments/proj0/your-tasks#youre-done) You're done! ---------------------------------------------------------------------------------------------- Follow the instructions in the next section "Submitting the Assignment" to turn in your work. [PreviousGetting Started](https://cs186.gitbook.io/project/assignments/proj0/getting-started) [NextSubmitting the Assignment](https://cs186.gitbook.io/project/assignments/proj0/submitting) Last updated 10 months ago --- # Submitting the Assignment | CS186 Projects [](https://cs186.gitbook.io/project/assignments/proj4/submitting-the-assignment#files) Files ------------------------------------------------------------------------------------------------- You may **not** modify the signature of any methods or classes that we provide to you, but you're free to add helper methods. You should make sure that all code you modify belongs to files with `TODO(proj4_part1)` and `TODO(proj4_part2)` comments in them (e.g. don't add helper methods to DataBox). A full list of files that you may modify follows: * `src/main/java/edu/berkeley/cs186/database/concurrency/LockType.java` * `src/main/java/edu/berkeley/cs186/database/concurrency/LockManager.java` * `src/main/java/edu/berkeley/cs186/database/concurrency/LockContext.java` (Part 2 only) * `src/main/java/edu/berkeley/cs186/database/concurrency/LockUtil.java` (Part 2 only) * `src/main/java/edu/berkeley/cs186/database/table/Table.java` (Part 2 only) * `src/main/java/edu/berkeley/cs186/database/table/PageDirectory.java` (Part 2 only) * `src/main/java/edu/berkeley/cs186/database/memory/Page.java` (Part 2 only) * `src/main/java/edu/berkeley/cs186/database/Database.java` (Part 2 only) Make sure that your code does _not_ use any static (non-final) variables - this may cause odd behavior when running with maven vs. in your IDE (tests run through the IDE often run with a new instance of Java for each test, so the static variables get reset, but multiple tests per Java instance may be run when using maven, where static variables _do not_ get reset). [](https://cs186.gitbook.io/project/assignments/proj4/submitting-the-assignment#gradescope) Gradescope ----------------------------------------------------------------------------------------------------------- Once all of your files are prepared in your repo you can submit to Gradescope through GitHub the same way you did for [Project 0](https://cs186.gitbook.io/project/assignments/proj0/submitting#pushing-changes-to-github-classroom) . ### [](https://cs186.gitbook.io/project/assignments/proj4/submitting-the-assignment#submitting-via-upload) Submitting via upload If your GitHub account has access to many repos, the Gradescope UI might time out while trying to load which repos you have available. If this is the case for you, you can submit your code directly using via upload. You can zip up your source code with `python3 zip.py --assignment proj4` and submit that directly to the autograder. [](https://cs186.gitbook.io/project/assignments/proj4/submitting-the-assignment#partners) Partners ------------------------------------------------------------------------------------------------------- Only one partner has to submit, but please make sure to add the other partner to the Gradescope submission. Slip minutes will be calculated individually. For example, if partner A has 10 slip minutes remaining and partner B has 20 slip minutes remaining and they submit 20 minutes late, partner A will be subject to the late penalty (1/3 off partner A's score) while partner B will have 0 remaining slip minutes and no late penalty applied to partner B's score. [](https://cs186.gitbook.io/project/assignments/proj4/submitting-the-assignment#grading) Grading ----------------------------------------------------------------------------------------------------- * Your submission for Part 1 will be worth 20% of your Project 4 grade and will come entirely from the Part 1 public tests. * Your submission for Part 2 will be worth 80% of your Project 4 grade. * 5% for Part 1 hidden tests * 60% for Part 2 public tests * 15% for Part 2 hidden tests Your Part 2 submission will be used to run all hidden tests (and public Part 2 tests). If you do not have a submission for Part 2, you will receive a 0% on all hidden tests for Part 1 and 2. You may go back and make changes to Part 1 even after that part deadline has passed before submitting to Part 2. [PreviousTesting](https://cs186.gitbook.io/project/assignments/proj4/testing) [NextProject 5: Recovery](https://cs186.gitbook.io/project/assignments/proj5) Last updated 8 months ago --- # Testing | CS186 Projects We strongly encourage testing your code yourself, especially after each part (rather than all at the end). The given tests for this project (even more so than previous projects) are **not** comprehensive tests: it **is** possible to write incorrect code that passes them all. Things that you might consider testing for include: anything that we specify in the comments or in this document that a method should do that you don't see a test already testing for, and any edge cases that you can think of. Think of what valid inputs might break your code and cause it not to perform as intended, and add a test to make sure things are working. To help you get started, here is one case that is **not** in the given tests (and will be included in the hidden tests): if a transaction holds IX(database), IS(table), S(page) and promotes the database lock to a SIX lock via `LockContext#promote`, `numChildLocks` should be updated to be 0 for both the database and table contexts. To add a unit test, open up the appropriate test file (all test files are located in `src/test/java/edu/berkeley/cs186/database` or subdirectories of it), and simply add a new method to the test class, for example: Copy @Test public void testPromoteSIXSaturation() { // your test code here } Many test classes have some setup code done for you already: take a look at other tests in the file for an idea of how to write the test code. [PreviousPart 2: Multigranularity](https://cs186.gitbook.io/project/assignments/proj4/part-2-lockcontext-and-lockutil) [NextSubmitting the Assignment](https://cs186.gitbook.io/project/assignments/proj4/submitting-the-assignment) Last updated 8 months ago --- # Getting Started | CS186 Projects [](https://cs186.gitbook.io/project/assignments/proj5/getting-started#logistics) Logistics ----------------------------------------------------------------------------------------------- This project is due **Thursday, 4/24/2025 at 11:59PM PDT (GMT-7)**. It is worth 8% of your overall grade in the class. The workload for the project is designed to be completed solo, but this semester we're allowing students to work on this project with a partner if you want to. Feel free to search for a partner on [this Edstem thread](https://edstem.org/us/courses/70276/discussion/5999429) ! **A gentle reminder that though our projects have tight release schedules, projects don't tend to take the entire time given to complete them :)** [](https://cs186.gitbook.io/project/assignments/proj5/getting-started#prerequisites) Prerequisites ------------------------------------------------------------------------------------------------------- You should watch all the recovery lectures before starting this project. We also highly recommend reviewing the [recovery notes](https://cs186berkeley.net/resources/static/notes/n14-Recovery.pdf) . [](https://cs186.gitbook.io/project/assignments/proj5/getting-started#academic-integrity-policy) Academic Integrity Policy ------------------------------------------------------------------------------------------------------------------------------- “_As a member of the UC Berkeley community, I act with honesty, integrity, and respect for others._” — UC Berkeley Honor Code **Read through the academic integrity guidelines** [**here**](https://cs186berkeley.net/integrityguidelines/) **.** We will be running plagiarism detection software on every submission against our own database of this semester's submissions, past submissions, and publicly hosted implementations on platforms such as GitHub and GitLab, followed by a thorough manual review process. Plagiarism on any assignment will result in a [non-reportable warning](https://conduct.berkeley.edu/wp-content/uploads/2024/01/Academic-Misconduct-Resource-Sheet-for-Students-UPDATED.pdf) and a grade penalty based on the severity of the infraction. As long as you follow the guidelines, there isn't anything to worry about here. While we do rely on software to find possible cases of academic dishonesty, every case is reviewed by multiple TAs who can filter out false positives. [](https://cs186.gitbook.io/project/assignments/proj5/getting-started#fetching-the-released-code) Fetching the released code --------------------------------------------------------------------------------------------------------------------------------- The GitHub Classroom link for this project is in the Project 5 release post on [Edstem](https://edstem.org/us/courses/70276/discussion/) . Once your private repo is set up clone the Project 5 skeleton code onto your local machine. ### [](https://cs186.gitbook.io/project/assignments/proj5/getting-started#setting-up-your-local-development-environment) Setting up your local development environment If you're using IntelliJ you can follow the instructions [in Project 0](https://cs186.gitbook.io/project/assignments/proj0/getting-started#setting-up-your-local-development-environment) in to set up your local environment again. Once you have your environment set up you can head to the next section [Your Tasks](https://cs186.gitbook.io/project/assignments/proj5/your-tasks) and begin working on the assignment. [](https://cs186.gitbook.io/project/assignments/proj5/getting-started#working-with-a-partner) Working with a partner ------------------------------------------------------------------------------------------------------------------------- Only one partner has to submit, but please make sure to add the other partner to the Gradescope submission. If you want to share code over GitHub you can follow the instructions [here](https://cs186.gitbook.io/project/common/adding-a-partner-on-github) . [](https://cs186.gitbook.io/project/assignments/proj5/getting-started#debugging-issues-with-github-classroom) Debugging Issues with GitHub Classroom --------------------------------------------------------------------------------------------------------------------------------------------------------- Feel free to skip this section if you don't have any issues with GitHub Classroom. If you are having issues (i.e. the page froze or some error message appeared), first check if you have access to your repo at `https://github.com/cs186-student/sp25-proj5-username`, replacing `username` with your GitHub username. If you have access to your repo and the starter code is there, then you can proceed as usual. ### [](https://cs186.gitbook.io/project/assignments/proj5/getting-started#id-404-not-found) 404 Not Found If you're getting a 404 not found page when trying to access your repo, make sure you've set up your repo using the GitHub Classroom link in the Project 5 release post on [Edstem](https://edstem.org/us/courses/70276/discussion/) . If you don't have access to your repo at all after following these steps, feel free to contact the course staff on Edstem. [PreviousProject 5: Recovery](https://cs186.gitbook.io/project/assignments/proj5) [NextYour Tasks](https://cs186.gitbook.io/project/assignments/proj5/your-tasks) Last updated 7 months ago --- # Project 5: Recovery | CS186 Projects [Getting Started](https://cs186.gitbook.io/project/assignments/proj5/getting-started) [Your Tasks](https://cs186.gitbook.io/project/assignments/proj5/your-tasks) [Testing](https://cs186.gitbook.io/project/assignments/proj5/testing) [Submitting the Assignment](https://cs186.gitbook.io/project/assignments/proj5/submitting-the-assignment) [PreviousSubmitting the Assignment](https://cs186.gitbook.io/project/assignments/proj4/submitting-the-assignment) [NextGetting Started](https://cs186.gitbook.io/project/assignments/proj5/getting-started) Last updated 7 months ago --- # Your Tasks | CS186 Projects In this project you will implement write-ahead logging and support for savepoints, rollbacks, and ACID compliant restart recovery. If you haven't already, we recommend reading through the [recovery notes](https://cs186berkeley.net/resources/static/notes/n14-Recovery.pdf) and referencing them as needed while you work through this project. The tests for this project are all located in [`TestRecoveryManager.java`](https://github.com/berkeley-cs186/sp25-rookiedb/blob/master/src/test/java/edu/berkeley/cs186/database/recovery/TestRecoveryManager.java) . Based on student feedback from previous semesters, we estimate that this project will take approximately 25-35 hours to complete. We have also included a star-based difficulty ranking per task, relative to the rest of the project, as a guide for pacing your work. _Please note that every student works at a different pace, and it's absolutely ok to spend more or less time on the project than the provided estimates!_ [](https://cs186.gitbook.io/project/assignments/proj5/your-tasks#understanding-the-skeleton-code) Understanding the Skeleton Code -------------------------------------------------------------------------------------------------------------------------------------- This project will be centered around `ARIESRecoveryManager.java`, which implements the `RecoveryManager` interface. Recall that there are two distinct modes of operation: _forward processing_ where we perform logging and maintain some metadata such as the dirty page table and transaction table during normal operation of the database, and _restart recovery_ (a.k.a. crash recovery), which consists of the processes taken when the database starts up again. During normal operation, the rest of the database calls various methods of the recovery manager to indicate that certain operations (e.g. a page write or flush) have occurred. During a restart, the `restart` method is called, which should bring the database back to a valid state. Some files that will be useful to read through are: * [`RecoveryManager.java`](https://github.com/berkeley-cs186/sp25-rookiedb/blob/master/src/main/java/edu/berkeley/cs186/database/recovery/RecoveryManager.java) provides an overview of each of the methods you'll be implementing and when they're called * [`TransactionTableEntry.java`](https://github.com/berkeley-cs186/sp25-rookiedb/blob/master/src/main/java/edu/berkeley/cs186/database/recovery/TransactionTableEntry.java) represents an entry in our transaction table and tracks thing like the lastLSN and active savepoints. * [`LogManager.java`](https://github.com/berkeley-cs186/sp25-rookiedb/blob/master/src/main/java/edu/berkeley/cs186/database/recovery/LogManager.java) contains the implementation for the log manager, which provides an interface for appending, fetching, and flushing logs * [`LogRecord.java`](https://github.com/berkeley-cs186/sp25-rookiedb/blob/master/src/main/java/edu/berkeley/cs186/database/recovery/LogRecord.java) contains the super class for all of the different types of logs that we support. Every log has a type and an LSN. Certain subclasses of LogRecord optionally support extra methods. * The [`records/`](https://github.com/berkeley-cs186/sp25-rookiedb/tree/master/src/main/java/edu/berkeley/cs186/database/recovery/records) directory contains all the subclasses of LogRecord. It may seem a bit overwhelming at first but they'll be introduced as you progress through the project. #### [](https://cs186.gitbook.io/project/assignments/proj5/your-tasks#disk-space-manager) Disk Space Manager You will not need to directly use the disk space manager in this project (the various `LogRecord` subclasses will use it for you as needed), but it does help to understand how our disk space manager organizes data at a high level. The disk space manager is responsible for allocating pages, and our disk space manager divides pages into _partitions_. Page 40000000001, for example, is the 1st page (0-indexed) in partition 4. Partitions are explicitly allocated and freed (but can only be freed if there are no pages in them), and pages are always allocated under a partition. Partition 0 is reserved for storing the log, which is why in a couple of places, you will see checks comparing the partition number against 0. Every other partition contains either a table or a serialized B+ tree object. #### [](https://cs186.gitbook.io/project/assignments/proj5/your-tasks#functional-objects-in-java) Functional objects in Java The project uses functional objects/interfaces in several places, which you may not be familiar with. If you are not familiar with these in Java, you should look through [the official Java documentation](https://docs.oracle.com/javase/8/docs/api/java/util/function/package-summary.html) - they're how you pass around functions and lambdas in Java, and the list of interfaces in the above link are simply the types of possible functions. Each interface has a method to call the passed in function (for example, [the `Consumer` interface has the `accept` method](https://docs.oracle.com/javase/8/docs/api/java/util/function/Consumer.html#accept-T-) ). [](https://cs186.gitbook.io/project/assignments/proj5/your-tasks#forward-processing) Forward Processing ------------------------------------------------------------------------------------------------------------ ![](https://cs186.gitbook.io/project/~gitbook/image?url=https%3A%2F%2F678656433-files.gitbook.io%2F%7E%2Ffiles%2Fv0%2Fb%2Fgitbook-x-prod.appspot.com%2Fo%2Fspaces%252F-MFVQnrLlCBowpNWJo1E%252Fuploads%252Fgit-blob-d1d25127e374feec8a094bb44b68b58f407f0606%252Fproj5-db-happy%2520%281%29%2520%283%29%2520%284%29%2520%285%29%2520%285%29%2520%281%29.png%3Falt%3Dmedia&width=768&dpr=4&quality=100&sign=56171167&sv=2) When the database is undergoing normal operation - where transactions are running normally, reading and writing data - the job of the recovery manager is to maintain the log by adding log records and ensuring that the log is properly flushed when necessary so that we can recover from a crash at any time. A few components of forward processing are already implemented for you. #### [](https://cs186.gitbook.io/project/assignments/proj5/your-tasks#initialization) Initialization At the time the database is first created, before any transactions run, the recovery manager needs to first set the log up, which is done in the `initialize` method in `ARIESRecoveryManager.java`. We store the _master record_ as the very first log record in the log, at LSN 0 (recall that the master record stores the LSN of the begin checkpoint record of the most recent successful checkpoint).To simplify things when implementing the analysis phase of restart recovery, we also immediately perform a checkpoint, writing a begin and end checkpoint record in succession, and updating the master record. This has been implemented for you. ### [](https://cs186.gitbook.io/project/assignments/proj5/your-tasks#task-1-transaction-status) Task 1: Transaction Status _Difficulty: ★★★★☆_ Part of the recovery manager's job during forward processing is to maintain the status of running transactions, and log changes in transaction status. The recovery manager is notified of changes in transaction status through three methods: * `commit` is called when a transaction attempts to move into the `COMMITTING` state. * `abort` is called when a transaction attempts to move into the `ABORTING` state. * `end` is called when a transaction attempts to move into the `COMPLETE` state. In the three methods (`commit`, `abort`, `end`) that you need to implement, you will need to keep the transaction table up-to-date, set the status of the transaction accordingly, and write the appropriate log record to the log (check the `records/` directory for the types of logs you can create). During this task you should get into the habit of **updating the lastLSN** in the transaction table whenever you append a log for a transaction's operation. This includes status change records, update records, and CLRs. You'll also need to implement: * In `commit` the commit record needs to be flushed to disk before the commit call returns to ensure durability. * In `end` if the transaction ends in an abort, all changes must be rolled back before an EndTransaction record is written. Look at the docstring for `rollbackToLSN` for details on how to rollback, and think about what LSN you can pass into this function to completely rollback a transaction. Some helper functions you may find useful for this task: * `LogManager#fetchLogRecord` * `LogManager#appendToLog` * `LogManager#flushToLSN` * `Transaction#setStatus` * `LogRecord#isUndoable` * `LogRecord#undo` After completing this task you should pass `testAbort` and `testAbortingEnd`. You will need to complete Task 2: Logging before `testSimpleCommit` passes. ### [](https://cs186.gitbook.io/project/assignments/proj5/your-tasks#task-2-logging) Task 2: Logging _Difficulty: ★☆☆☆☆_ During normal operation several methods are called when certain events happen: * `logAllocPart`, `logFreePart`, `logAllocPage`, `logFreePage`: these are called by the disk space manager whenever someone tries to create or delete a partition or page, and should append the appropriate log record, and have been implemented for you. * `logPageWrite` is called by the buffer manager whenever someone tries to write to part of a page, and will be implemented by you. Your implementation should create and append an appropriate log record and update the transaction table and dirty page table accordingly. All of these methods should keep the tables maintained by the recovery manager up-to-date (the dirty page table and transaction table). After completing this task the following tests should be passing: `testEnd`, `testSimpleCommit`, `testSimpleLogPageWrite`. ### [](https://cs186.gitbook.io/project/assignments/proj5/your-tasks#task-3-savepoints) Task 3: Savepoints _Difficulty: ★★☆☆☆_ Recall from lecture that SQL has [savepoints](https://www.postgresql.org/docs/9.6/sql-savepoint.html) to allow for _partial rollback_: `SAVEPOINT pomelo` creates a savepoint named `pomelo` for the current running transaction, allowing a user to rollback all changes made after the savepoint by using `ROLLBACK TO SAVEPOINT pomelo`. The savepoint can be deleted with `RELEASE SAVEPOINT pomelo`. Write-ahead logging lets us implement savepoints. The recovery manager has three methods related to savepoints, which correspond to the three SQL statements for savepoints, and follow the semantics of the corresponding SQL statements: * `savepoint` creates a savepoint for the current transaction with the specified name. As with the `SAVEPOINT` statement in SQL, the name of the savepoint is scoped to the transaction: two different transactions may have their own savepoint called `pomelo`. * `releaseSavepoint` deletes a specific savepoint for the current transaction; it behaves the same as the `RELEASE SAVEPOINT` statement in SQL. * `rollbackToSavepoint` rolls the transaction back to the specified savepoint. All changes done after the savepoint should be undone, similarly to an aborting transaction, except the status of the transaction does not change; it behaves the same way as the `ROLLBACK TO SAVEPOINT` statement in SQL. See Transaction Status for more details on undoing changes. The skeleton code has provided most of the implementation of savepoints for you - all that is left is to implement the logic for undoing changes in `rollbackToSavepoint`. This is extremely similar to the undo logic in `end()`, so if you already implemented the `rollbackToLSN` method to complete Task 1 you should be able to reuse that helper here. After completing this task `testSimpleSavepoint` and `testNestedRollback` should be passing. ### [](https://cs186.gitbook.io/project/assignments/proj5/your-tasks#task-4-checkpoints) Task 4: Checkpoints _Difficulty: ★★★☆☆_ Recall from lecture that in ARIES, we periodically perform _fuzzy checkpoints_ which occur even while other transactions run, to minimize recovery time after a crash, without bringing the database to a halt during forward processing. The approach is outlined below. Note that part of the implementation is already provided to you; you are responsible for writing the end checkpoint records that are not covered by the given code. First, a begin checkpoint record is added to the log. Then, we write end checkpoint records, accounting for the fact that we may have to break up end checkpoint records due to too many DPT/Xact table entries. An end checkpoint record should be written even if all tables are empty, and multiple end checkpoint records should only be written if necessary. This is done as follows: * iterate through the dirtyPageTable and copy the entries. If at any point, copying the current record would cause the end checkpoint record to be too large, an end checkpoint record with the copied DPT entries should be appended to the log. * iterate through the transaction table, and copy the status/lastLSN, outputting end checkpoint records only as needed. * output one final end checkpoint. Finally, we must rewrite the master record with the LSN of the begin checkpoint record of the new successful checkpoint. As an example, if we had 200 DPT entries and 300 transaction table entries, we would output the following end checkpoint records in the following order: * EndCheckpoint with 200 DPT entries and 52 transaction table entries * EndCheckpoint with 240 transaction table entries * EndCheckpoint with 8 transaction table entries (If an end checkpoint has 200 DPT entries, a maximum of 52 table entries can fit in the remaining space. A maximum of 240 transaction table entries can fit in a single end checkpoint.) You may find the `EndCheckpoint.fitsInOneRecord` static method useful for this; it takes in two parameters: * the number of dirty page table entries stored in the record, * the number of transaction number/status/lastLSN entries stored in the record and returns whether the resulting record would fit in one page. For example, for the record: Copy EndCheckpoint{ dpt={1 => 30000, 2 => 33000, 3 => 34000}, txnTable={1 => (RUNNING, 33000), 2 => (RUNNING, 34000)} } the corresponding call is: Copy EndCheckpoint.fitsInOneRecord(3, 2); // # of dpt entries, # of txnTable entries [](https://cs186.gitbook.io/project/assignments/proj5/your-tasks#restart-recovery) Restart Recovery -------------------------------------------------------------------------------------------------------- ![](https://cs186.gitbook.io/project/~gitbook/image?url=https%3A%2F%2F678656433-files.gitbook.io%2F%7E%2Ffiles%2Fv0%2Fb%2Fgitbook-x-prod.appspot.com%2Fo%2Fspaces%252F-MFVQnrLlCBowpNWJo1E%252Fuploads%252Fgit-blob-a6e7a4050c6ac5ba113c5a9d675d9abef02211a8%252Fproj5-db-off-the-cliff%2520%283%29%2520%284%29%2520%281%29%2520%282%29%2520%284%29.png%3Falt%3Dmedia&width=768&dpr=4&quality=100&sign=9f5710d7&sv=2) When the database starts up again, it enters restart recovery. Recall from lecture that this involves three phases: analysis, redo, and undo. The `RecoveryManager` interface exposes a single method for restart recovery: the `restart` method, which is called when the database starts up. In order to test each phase in isolation, the skeleton has three package-private helper methods for restart recovery which you will need to implement: `restartAnalysis`, `restartRedo`, and `restartUndo`, which perform the analysis, redo, and undo phases respectively. In addition to the three phases of recovery, the `restart` method does two things: * between the redo and undo phases, any page in the dirty page table that isn't actually dirty (has changes in-memory that have not been flushed) should be removed from the dirty page table. These pages may be present in the DPT as a result of the analysis phase, if we are uncertain about whether a change has been flushed to disk successfully or not. * after the undo phase, recovery has finished. To avoid having to abort all the transactions again should we crash, we take a checkpoint. ### [](https://cs186.gitbook.io/project/assignments/proj5/your-tasks#task-5-analysis) Task 5: Analysis _Difficulty: ★★★★★_ This section concerns just the `restartAnalysis` method, which performs the analysis pass of restart recovery. **Master Record** To begin analysis, the master record needs to be fetched, in order to find the LSN of the checkpoint to start at (recall that in `initialize`, a checkpoint was written near the start of the log, so there is always a checkpoint to start at). **Scanning the Log** The goal of analysis is to reconstruct the dirty page table and transaction table from the log. The many types of log records encountered while scanning fall into three categories: log records for operations that a transaction does, checkpoint records, and log records for transaction status changes (commit/abort/end). (There is also the master record, but it should never come up while scanning the log). **Log Records for Transaction Operations** These are the records that involve a transaction, and therefore, we need to update the transaction table whenever we encounter one of these records. The following applies to any record with a non-empty result for `LogRecord#getTransNum()` * If the transaction is not in the transaction table, it should be added to the table (the `newTransaction` function object can be used to create a `Transaction` object, which can be passed to `startTransaction`). * The lastLSN of the transaction should be updated. **Log Records for Page Operations** The dirty page table will need to be updated for certain page-related log records: * UpdatePage/UndoUpdatePage both may dirty a page in memory, without flushing changes to disk. * FreePage/UndoAllocPage both make their changes visible on disk immediately, and can be seen as flushing the freed page to disk (remove page from DPT) * You don't need to do anything for AllocPage/UndoFreePage * If you're curious about how the data from before the page was freed is restored in this case, we work around this by always writing an update log records that go from \[old bytes\] -> \[zeroes\] right before freeing the page. After undoing the free page, undoing these updates would restore the old bytes (\[zeroes\] -> \[old\_bytes\]). **Log Records for Transaction Status Changes** These three types of log records (CommitTransaction/AbortTransaction/EndTransaction) all change the status of a transaction. When one of these records are encountered, the transaction table should be updated as described in the previous section. The status of the transaction should also be set to one of `COMMITTING`, `RECOVERY_ABORTING`, or `COMPLETE`. If the record is an EndTransaction record, the transaction should also be cleaned up before setting the status, and the entry should be removed from the transaction table. Additionally, you should add the ended transaction's transaction number into the `endedTransactions` set, which will be important for processing end checkpoint records. **Checkpoint Records** When a BeginCheckpoint record is encountered, no action is required. When an EndCheckpoint record is encountered, the tables stored in the record should be combined with the tables currently in memory: For each entry in the checkpoint's snapshot of the dirty page table: * The recLSN of a page in the checkpoint should always be used, even if we have a record in the dirty page table already, since the checkpoint is always more accurate than anything we can infer from just the log. For each entry in the checkpoint's snapshot of the transaction table: * Before updating a transaction table entry, check if the corresponding transaction is already in `endedTransactions`. If so, the transaction is already complete and the entry can be ignored, since any information it contains is no longer relevant. Otherwise: * If we don't have a corresponding entry for the transaction in our reconstruction of the transaction table, it should be added (the `newTransaction` function object can be used to create a `Transaction` object, which can be passed to `startTransaction`). * The lastLSN of a transaction in the checkpoint should be used if it is greater than or equal to the lastLSN of the transaction in the in-memory transaction table. Additionally, the status of transactions should be updated. Remember that checkpoints are fuzzy, meaning that they capture state from any time between the begin and end records. This means some of the transaction status's stored in the record may be out of date, e.g. the checkpoint may say a transaction is running when we already know that its aborting. Transactions will always advance through states in one of two ways: * running -> committing -> complete * running -> aborting -> complete You should only update a transaction's status if the status in the checkpoint is more "advanced" than the status in memory. Some examples: * if the checkpoint says a transaction is aborting and our in-memory table says its running, we should update the in-memory status to recovery aborting\* because its possible to transition from running to aborting. * if the checkpoint says a transaction is running and our in-memory table says its committing, we wouldn't update our in-memory table. There's no way for the status to change from committing to running in normal operation, and so the checkpoint status must be out-of-date. \* Make sure that you set to recovery aborting instead of aborting if the checkpoint says aborting **Ending Transactions** The transaction table at this point should have transactions that are in one of the following states: `RUNNING`, `COMMITTING`, or `RECOVERY_ABORTING`. * All transactions in the `COMMITTING` state should be ended (`cleanup()`, state set to `COMPLETE`, end transaction record written, and removed from the transaction table). * All transactions in the `RUNNING` state should be moved into the `RECOVERY_ABORTING` state, and an abort transaction record should be written. * Nothing needs to be done for transactions in the `RECOVERY_ABORTING` state. After completing this task you should be passing `testRestartAnalysis` and `testAnalysisCheckpoints`. ### [](https://cs186.gitbook.io/project/assignments/proj5/your-tasks#task-6-redo) Task 6: Redo _Difficulty: ★★★☆☆_ This section concerns just the `restartRedo` method, which performs the redo pass of restart recovery. Recall from lecture that the redo phase begins at the lowest recLSN in the dirty page table. Scanning from that point on, we redo a record if it is redoable and if it is either: * a partition-related record (AllocPart, UndoAllocPart, FreePart, UndoFreePart) * a record that allocates a page (AllocPage, UndoFreePage) * a record that modifies a page (UpdatePage, UndoUpdatePage, UndoAllocPage, FreePage) where all of the following hold: * the page is in the DPT * the record's LSN is greater than or equal to the DPT's recLSN for that page. * the pageLSN on the page itself is strictly less than the LSN of the record. In order to check the pageLSN of a page, you'll need to fetch it from the buffer manager. We recommend you use the following template: Copy Page page = bufferManager.fetchPage(new DummyLockContext(), pageNum); try { // Do anything that requires the page here } finally { page.unpin(); } The buffer manager always returns a pinned page which is why we use a try-finally block to ensure that the page is always unpinned once we're done using it. Note that we can use a dummy lock context here without worrying about isolation issues since no other operations can run at the same time as the redo phase. You may find [this method](https://github.com/berkeley-cs186/sp25-rookiedb/blob/master/src/main/java/edu/berkeley/cs186/database/memory/Page.java#L164-L169) of the Page class useful here. Be sure to account for the case where `restartRedo` is called on an empty log! After finishing this task you should be passing `testRestartRedo`. ### [](https://cs186.gitbook.io/project/assignments/proj5/your-tasks#task-7-undo) Task 7: Undo _Difficulty: ★★★★☆_ This section concerns just the `restartUndo` method, which performs the undo pass of restart recovery. Recall from lecture that during the undo phase we do not abort and undo the transactions one by one due to a large number of random I/Os incurred as a result. Instead, we repeatedly undo the log record (that needs to be undone) with the highest LSN until we are done, making only one pass through the log. The undo phase begins with the set of lastLSN of each of the aborting transactions (in the `RECOVERY_ABORTING` state). We repeatedly fetch the log record of the largest of these LSNs and: * if the record is undoable, we write the CLR out and undo it\* * replace the LSN in the set with the undoNextLSN of the record if it has one, or the prevLSN otherwise; * end the transaction if the LSN from the previous step is 0, removing it from the set and the transaction table. Refer to the Ending Transactions subsection of the Analysis task for a more comprehensive overview on what ending a transaction entails. \* The `undo` method of `LogRecord` does not actually undo changes - it instead returns the compensation log record. To actually undo changes, you will need to append the returned CLR and then call `redo` on it. After finishing this task you should be passing `testRestartUndo`, `testUndoCLR`, and `testUndoDPTAndFlush`. Additionally, if you've implemented all tasks correctly every test in `TestRecoveryManager.java` should now be passing. [](https://cs186.gitbook.io/project/assignments/proj5/your-tasks#important-differences-from-aries-as-presented-in-lecture) Important differences from ARIES as presented in lecture ---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- There are a few important differences between ARIES as presented in the lecture, and the implementation of the recovery manager that you need to do in this project, which are mostly implementation details. **On exams, you should use the simplified version of ARIES as described in lecture whenever this project and lecture diverge.** #### [](https://cs186.gitbook.io/project/assignments/proj5/your-tasks#forward-processing-1) Forward Processing Project Lecture 1 Log page/partition allocations/frees No such logging 2 End Checkpoint may have many records End Checkpoint is one record * We log page/partition allocations/frees. **Explanation:** This is just a quirk of how our disk space manager works, to ensure that it can be brought back to a consistent state after a crash. * A checkpoint may have many end\_checkpoint records, whereas in lecture, only a single end\_checkpoint record is used. **Explanation:** This is due to the fact that we need a single log record to fit in a page: we may have so many transactions/dirty pages that we cannot fit it all in one page. #### [](https://cs186.gitbook.io/project/assignments/proj5/your-tasks#restart-recovery-1) Restart Recovery Project Lecture 1 Clean up dirty page table after redoing changes Step does not exist 2 Checkpoint after undo Step does not exist 3 Process checkpoints upon reaching end\_checkpoint record (single pass) Load checkpoints before starting analysis (2 passes) 4 Process page/partition allocation/free records These entries do not exist * We clean out the dirty page table of all pages that are not dirty in the buffer manager, after redoing all changes, whereas in lecture, this step is omitted. **Explanation:** We would like the dirty page table to reflect pages that are actually dirty (because the only time they get removed is when the page is flushed, which may not ever happen if the already-flushed page is never modified again). We omit this step in lecture and exams out of simplicity. * We checkpoint after undo, whereas in lecture, this step is omitted. **Explanation:** This is a fairly unimportant step (it is not necessary for correctness - we have completely recovered after undo), but it is useful for performance reasons and a natural point to perform a checkpoint, and avoid a lot of work the next time we crash. * We do a single pass through the records, processing checkpoints upon reaching the end-checkpoint record, whereas in lecture we first create the checkpoint's table and then scan through the log **Explanation:** The two approaches are equivalent - they will result in the exact same tables after analysis, but it is both simpler and more efficient to process the end\_checkpoint records and add their information to the tables in memory as we reach them, especially since we have multiple end\_checkpoint records. * We process page/partition allocation/free records, and in some cases, remove the page from the dirty page table while doing so. **Explanation:** See explanation about these records under forward processing. In some cases (free page/undo alloc page), we remove a page from the dirty page table, and in others (alloc page/undo free page), we do not need to add the page to the dirty page table. This is because these operations all update on-disk data immediately. For example, allocating a page to the end of a partition will immediately increase the size of the file on disk backing that partition. [](https://cs186.gitbook.io/project/assignments/proj5/your-tasks#further-reading) Further Reading ------------------------------------------------------------------------------------------------------ If you enjoyed the material in this project and the previous project (Locking), we recommend reading through the ARIES paper ([link here](https://cs.stanford.edu/people/chrismre/cs345/rl/aries.pdf) )! Nothing in the ARIES paper is in-scope for the class (and where what we teach in class conflicts with the paper, material from this class takes precedence), but the paper (albeit long) is well-written and talks more about the context behind design decisions for both multigranularity locking and ARIES, as well as more details that come up in implementations. You should have enough background at this point in the course to read and understand it, so we recommend reading through it at your own pace if this portion of the course caught your interest. [PreviousGetting Started](https://cs186.gitbook.io/project/assignments/proj5/getting-started) [NextTesting](https://cs186.gitbook.io/project/assignments/proj5/testing) Last updated 7 months ago --- # Part 2: Multigranularity | CS186 Projects ![](https://cs186.gitbook.io/project/~gitbook/image?url=https%3A%2F%2F678656433-files.gitbook.io%2F%7E%2Ffiles%2Fv0%2Fb%2Fgitbook-x-prod.appspot.com%2Fo%2Fspaces%252F-MFVQnrLlCBowpNWJo1E%252Fuploads%252Fgit-blob-95c1471fc9fa1b4b53b1f18e8fafb489a1cad795%252Fdataphase%2520%281%29%2520%281%29%2520%282%29%2520%282%29%2520%283%29%2520%283%29%2520%281%29.png%3Falt%3Dmedia%26token%3Dcc39cbd7-d204-47f8-9f9f-c4975d9cc1b5&width=768&dpr=4&quality=100&sign=239009d6&sv=2) Dataphase **A working implementation of Part 1 is required for Part 2. If you have not yet finished** [**Part 1**](https://cs186.gitbook.io/project/assignments/proj4/part-1-lockmanager) **, you should do so before continuing.** In this part, you will implement the middle layer (`LockContext`) and the declarative layer (in `LockUtil`). The `concurrency` directory contains a partial implementation of a lock context (`LockContext`), which you must complete in this part of the project. [](https://cs186.gitbook.io/project/assignments/proj4/part-2-lockcontext-and-lockutil#your-tasks) Your Tasks ----------------------------------------------------------------------------------------------------------------- Based on student feedback from previous semesters, we estimate that this part of the project will take approximately 30-40 hours to complete. We have also included a star-based difficulty ranking per task, relative to the rest of the project, as a guide for pacing your work. _Please note that every student works at a different pace, and it's absolutely ok to spend more or less time on the project than the provided estimates!_ ### [](https://cs186.gitbook.io/project/assignments/proj4/part-2-lockcontext-and-lockutil#task-3-lockcontext) Task 3: LockContext _Difficulty: ★★★★★_ The [`LockContext`](https://github.com/berkeley-cs186/sp25-rookiedb/blob/master/src/main/java/edu/berkeley/cs186/database/concurrency/LockContext.java) class represents a single resource in the hierarchy; this is where all multigranularity operations (such as enforcing that you have the appropriate intent locks before acquiring or performing lock escalation) are implemented. You will need to implement the following methods of `LockContext`: * [`acquire`](https://github.com/berkeley-cs186/sp25-rookiedb/blob/master/src/main/java/edu/berkeley/cs186/database/concurrency/LockContext.java#L85-L95) : this method performs an acquire via the underlying `LockManager` after ensuring that all multigranularity constraints are met. For example, if the transaction has IS(database) and requests X(table), the appropriate exception must be thrown (see comments above method). If a transaction has a SIX lock, then it is redundant for the transaction to have an IS/S lock on any descendant resource. Therefore, in our implementation, we prohibit acquiring an IS/S lock if an ancestor has SIX, and consider this to be an invalid request. * [`release`](https://github.com/berkeley-cs186/sp25-rookiedb/blob/master/src/main/java/edu/berkeley/cs186/database/concurrency/LockContext.java#L103-L113) : this method performs a release via the underlying `LockManager` after ensuring that all multigranularity constraints will still be met after release. For example, if the transaction has X(table) and attempts to release IX(database), the appropriate exception must be thrown (see comments above method). * [`promote`](https://github.com/berkeley-cs186/sp25-rookiedb/blob/master/src/main/java/edu/berkeley/cs186/database/concurrency/LockContext.java#L121-L139) : this method performs a lock promotion via the underlying `LockManager` after ensuring that all multigranularity constraints are met. For example, if the transaction has IS(database) and requests a promotion from S(table) to X(table), the appropriate exception must be thrown (see comments above method). In the special case of promotion to SIX (from IS/IX/S), you should simultaneously release all descendant locks of type S/IS, since we disallow having IS/S locks on descendants when a SIX lock is held. You should also disallow promotion to a SIX lock if an ancestor has SIX, because this would be redundant. **Note**: this does still allow for SIX locks to be held under a SIX lock, in the case of promoting an ancestor to SIX while a descendant holds SIX. This is redundant, but fixing it is both messy (have to swap all descendant SIX locks with IX locks) and pointless (you still hold a lock on the descendant anyways), so we just leave it as is. * [`escalate`](https://github.com/berkeley-cs186/sp25-rookiedb/blob/master/src/main/java/edu/berkeley/cs186/database/concurrency/LockContext.java#L147-L179) : this method performs lock escalation up to the current level (see below for more details). Since interleaving of multiple `LockManager` calls by multiple transactions (running on different threads) is allowed, you must make sure to only use one mutating call to the `LockManager` and only request information about the current transaction from the `LockManager` (since information pertaining to any other transaction may change between the querying and the acquiring). * [`getExplicitLockType`](https://github.com/berkeley-cs186/sp25-rookiedb/blob/master/src/main/java/edu/berkeley/cs186/database/concurrency/LockContext.java#L186-L189) : this method returns the type of the lock explicitly held at the current level. For example, if a transaction has X(db), `dbContext.getExplicitLockType(transaction)` should return X, but `tableContext.getExplicitLockType(transaction)` should return NL (no lock explicitly held). * [`getEffectiveLockType`](https://github.com/berkeley-cs186/sp25-rookiedb/blob/master/src/main/java/edu/berkeley/cs186/database/concurrency/LockContext.java#L196-L201) : this method returns the type of the lock either implicitly or explicitly held at the current level. For example, if a transaction has X(db): * `dbContext.getEffectiveLockType(transaction)` should return X * `tableContext.getEffectiveLockType(transaction)` should _also_ return X (since we implicitly have an X lock on every table due to explicitly having an X lock on the entire database). Since an intent lock does _not_ implicitly grant lock-acquiring privileges to lower levels, if a transaction only has SIX(database), `tableContext.getEffectiveLockType(transaction)` should return S (not SIX), since the transaction implicitly has S on table via the SIX lock, but not the IX part of the SIX lock (which is only available at the database level). It is possible for the explicit lock type to be one type, and the effective lock type to be a different lock type, specifically if an ancestor has a SIX lock. The following helper methods may come in handy for this task: methods of `LockType` and `LockManager`, `ResourceName#parent` and `ResourceName#isDescendantOf`, `hasSIXAncestor` and `sisDescendants` which you will implement, `fromResourceName`. **Hierarchy** The `LockContext` objects all share a single underlying `LockManager` object. The `parentContext` method returns the parent of the current context (e.g. the lock context of the database is returned when `tableContext.parentContext()` is called), and the `childContext` method returns the child lock context with the name passed in (e.g. `tableContext.childContext(0L)` returns the context of page 0 of the table). There is exactly one `LockContext` for each resource: calling `childContext` with the same parameters multiple times returns the same object. The provided code already initializes this tree of lock contexts for you. For performance reasons, however, we do not create lock contexts for every page of a table immediately. Instead, we create them as the corresponding `Page` objects are created. #### [](https://cs186.gitbook.io/project/assignments/proj4/part-2-lockcontext-and-lockutil#escalation) Escalation Lock escalation is the process of going from many fine locks (locks at lower levels in the hierarchy) to a single coarser lock (lock at a higher level). For example, we can escalate many page locks a transaction holds into a single lock at the table level. We perform lock escalation through `LockContext#escalate`. A call to this method should be interpreted as a request to escalate all locks on descendants (these are the fine locks) into one lock on the context `escalate` was called with (the coarse lock). The fine locks may be any mix of intent and regular locks, but we limit the coarse lock to be either S or X. For example, if we have the following locks: IX(database), SIX(table), X(page 1), X(page 2), X(page 4), and call `tableContext.escalate(transaction)`, we should replace the page-level locks with a single lock on the table that encompasses them: ![](https://cs186.gitbook.io/project/~gitbook/image?url=https%3A%2F%2F678656433-files.gitbook.io%2F%7E%2Ffiles%2Fv0%2Fb%2Fgitbook-x-prod.appspot.com%2Fo%2Fspaces%252F-MFVQnrLlCBowpNWJo1E%252Fuploads%252Fgit-blob-c14d03dde76686cd7b9a90bb00695ccbad267160%252Fproj4-escalate1%2520%283%29%2520%283%29%2520%283%29%2520%281%29%2520%283%29.png%3Falt%3Dmedia&width=768&dpr=4&quality=100&sign=d5f083df&sv=2) Likewise, if we called `dbContext.escalate(transaction)`, we should replace the page-level locks and table-level locks with a single lock on the database that encompasses them: ![](https://cs186.gitbook.io/project/~gitbook/image?url=https%3A%2F%2F678656433-files.gitbook.io%2F%7E%2Ffiles%2Fv0%2Fb%2Fgitbook-x-prod.appspot.com%2Fo%2Fspaces%252F-MFVQnrLlCBowpNWJo1E%252Fuploads%252Fgit-blob-5ce4b3a0fe666867c554f74df85455942421c3bc%252Fproj4-escalate2%2520%281%29%2520%281%29%2520%282%29%2520%282%29%2520%283%29%2520%283%29.png%3Falt%3Dmedia%26token%3D8427ac3e-c038-4eaf-aa4b-667865f4963f&width=768&dpr=4&quality=100&sign=63a43cb4&sv=2) Note that escalating to an X lock always "works" in this regard: having a coarse X lock definitely encompasses having a bunch of finer locks. However, this introduces other complications: if the transaction previously held only finer S locks, it would not have the IX locks required to hold an X lock, and escalating to an X reduces the amount of concurrency allowed unnecessarily. We therefore require that `escalate` only escalate to the least permissive lock type (between either S or X) that still encompasses the replaced finer locks (so if we only had IS/S locks, we should escalate to S, not X). Also note that since we are only escalating to S or X, a transaction that only has IS(database) would escalate to S(database). Though a transaction that only has IS(database) technically has no locks at lower levels, the only point in keeping an intent lock at this level would be to acquire a normal lock at a lower level, and the point in escalating is to avoid having locks at a lower level. Therefore, we don't allow escalating to intent locks (IS/IX/SIX). ### [](https://cs186.gitbook.io/project/assignments/proj4/part-2-lockcontext-and-lockutil#task-4-lockutil) Task 4: LockUtil _Difficulty: ★★★★☆_ The LockContext class enforces multigranularity constraints for us, but it's a bit cumbersome to use in our database: wherever we want to request some locks, we have to handle requesting the appropriate intent locks, etc. To simplify integrating locking into our codebase (the second half of this part), we define the `ensureSufficientLockHeld` method. This method is used like a declarative statement. For example, let's say we have some code that reads an entire table. To add locking, we can do: Copy LockUtil.ensureSufficientLockHeld(tableContext, LockType.S); // any code that reads the table here After the `ensureSufficientLockHeld` line, we can assume that the current transaction (the transaction returned by `Transaction.getTransaction()`) has permission to read the resource represented by `tableContext`, as well as any children (all the pages). We can call it several times in a row: Copy LockUtil.ensureSufficientLockHeld(tableContext, LockType.S); LockUtil.ensureSufficientLockHeld(tableContext, LockType.S); // any code that reads the table here or write several statements in any order: Copy LockUtil.ensureSufficientLockHeld(pageContext, LockType.S); LockUtil.ensureSufficientLockHeld(tableContext, LockType.S); LockUtil.ensureSufficientLockHeld(pageContext, LockType.S); // any code that reads the table here and no errors should be thrown, and at the end of the calls, we should be able to read all of the table. Note that the caller does not care exactly which locks the transaction actually has: if we gave the transaction an X lock on the database, the transaction would indeed have permission to read all of the table. But this doesn't allow for much concurrency (and actually enforces a serial schedule if used with 2PL), so we additionally stipulate that `ensureSufficientLockHeld` should grant as little additional permission as possible: if an S lock suffices, we should have the transaction acquire an S lock, not an X lock, but if the transaction already has an X lock, we should leave it alone (`ensureSufficientLockHeld` should never reduce the permissions a transaction has; it should always let the transaction do at least as much as it used to, before the call). We suggest breaking up the logic of this method into two phases: ensuring that we have the appropriate locks on ancestors, and acquiring the lock on the resource. You will need to promote in some cases, and escalate in some cases (these cases are not mutually exclusive). ### [](https://cs186.gitbook.io/project/assignments/proj4/part-2-lockcontext-and-lockutil#task-5-two-phase-locking) Task 5: Two-Phase Locking _Difficulty: ★★☆☆☆_ At this point, you should have a working system to acquire and release locks on different resources in the database. In this task you'll add logic to acquire and release locks throughout the course of a transaction. _Tip: for all the files mentioned below, you can use IntelliJ's_ `_Ctrl/Cmd + Shift + N_` _to search for the file quickly! If you still couldn't find the file, click into the link that will launch you into the Github repo._ #### [](https://cs186.gitbook.io/project/assignments/proj4/part-2-lockcontext-and-lockutil#acquisition-phase) Acquisition Phase **Reads and Writes:** The simplest scheme for locking is to simply lock pages as we need them. As all reads and writes to pages are performed via the `Page.PageBuffer` class, it suffices to change only that. Modify the [`get`](https://github.com/berkeley-cs186/sp25-rookiedb/blob/master/src/main/java/edu/berkeley/cs186/database/memory/Page.java#L209) and [`put`](https://github.com/berkeley-cs186/sp25-rookiedb/blob/master/src/main/java/edu/berkeley/cs186/database/memory/Page.java#L225) methods of [`Page.PageBuffer`](https://github.com/berkeley-cs186/sp25-rookiedb/blob/master/src/main/java/edu/berkeley/cs186/database/memory/Page.java#L188) to lock the page (and acquire locks up the hierarchy as needed) with the least permissive lock types possible. **Scans**: If we know we'll be scanning multiple pages of a table, we're better off just getting a single lock on the table instance of many fine grained locks on the table's pages. Modify the ridIterator and recordIterator methods to acquire an appropriate lock on the table before doing a scan. **Write Optimization:** When we modify a page, we'll almost always end up reading it first (acquiring IS/S locks) and then write back our updates to it afterwards (promoting to IX/X locks). If we know ahead of time that we're going to modify a page, we can skip the IS/S locks altogether by just acquiring IX/X locks to begin with. Modify the following methods to request the appropriate lock upfront: * [`PageDirectory#getPageWithSpace`](https://github.com/berkeley-cs186/sp25-rookiedb/blob/master/src/main/java/edu/berkeley/cs186/database/table/PageDirectory.java#L107) * [`Table#updateRecord`](https://github.com/berkeley-cs186/sp25-rookiedb/blob/master/src/main/java/edu/berkeley/cs186/database/table/Table.java#L307) * [`Table#deleteRecord`](https://github.com/berkeley-cs186/sp25-rookiedb/blob/master/src/main/java/edu/berkeley/cs186/database/table/Table.java#L335) Note: no more tests will pass after doing this, see the next section for why. #### [](https://cs186.gitbook.io/project/assignments/proj4/part-2-lockcontext-and-lockutil#release-phase) Release Phase At this point, transactions should be acquiring lots of locks needed to do their queries, but no locks are ever released! We will be using Strict Two-Phase Locking in our database, which means that lock releases only happen when the transaction finishes, in the `cleanup` method. Modify the `close` method of `Database.TransactionContextImpl` to release all locks the transaction acquired. You should only use `LockContext#release` and not `LockManager#release` - `LockManager` will not verify multigranularity constraints, but other transactions at the same time assume that these constraints are met, so you do want these constraints to be maintained. Note that you can't just release the locks in any order! Think about in what order you are allowed to release the locks. You should pass the all the tests in [`TestDatabaseDeadlockPrecheck`](https://github.com/berkeley-cs186/sp25-rookiedb/blob/master/src/test/java/edu/berkeley/cs186/database/TestDatabaseDeadlockPrecheck.java) and [`TestDatabase2PL`](https://github.com/berkeley-cs186/sp25-rookiedb/blob/master/src/test/java/edu/berkeley/cs186/database/TestDatabase2PL.java) after implementing the acquisition and release phase. [](https://cs186.gitbook.io/project/assignments/proj4/part-2-lockcontext-and-lockutil#putting-it-all-together) Putting it all together ------------------------------------------------------------------------------------------------------------------------------------------- After implementing project 4, our database now supports locking, a fundamentally important functionality for database concurrency and isolation! Navigate to `CommandLineInterface.java` and uncomment [line 41](https://github.com/berkeley-cs186/sp25%C3%9F-rookiedb/blob/main/src/main/java/edu/berkeley/cs186/database/cli/CommandLineInterface.java#L41) and comment out line 38. Run the code to start our CLI. This should open a new panel in IntelliJ at the bottom. Click on this panel. We've provided 3 demo tables (Students, Courses, Enrollments). Recall from project 0 that we can run queries on this CLI. Let's try starting a transaction and querying a table by running: Copy BEGIN TRANSACTION; and then Copy SELECT * FROM Students AS s INNER JOIN Enrollments AS e ON s.sid = e.sid; We can display all the locks held by this transaction by running `\locks`. Now let's run: Copy INSERT INTO Students VALUES (3000, 'Name', 'Major', 5.0); and display the locks held using `\locks`. Notice how we've upgraded some locks and now hold an X lock on a page of the Students table. Let's commit and end our transaction by running `COMMIT;`. Locking is important when we have multiple clients modifying and querying the database. The demo below shows how this works. We run RookieDB as a server and open connections to this server to run transactions and interact with the database. You can try it yourself by running Server.java. You can open multiple connections via client.py. Check out these files for more information! [](https://cs186.gitbook.io/project/assignments/proj4/part-2-lockcontext-and-lockutil#additional-notes) **Additional Notes** --------------------------------------------------------------------------------------------------------------------------------- After this, you should pass all the tests we have provided to you under `database.concurrency.*`, as well as the tests in `TestDatabaseDeadlockPrecheck` and `TestDatabase2PL`. Note that you may **not** modify the signature of any methods or classes that we provide to you, but you're free to add helper methods. Also, you should only modify code in the `concurrency` directory for this section. [PreviousPart 1: Queuing](https://cs186.gitbook.io/project/assignments/proj4/part-1-lockmanager) [NextTesting](https://cs186.gitbook.io/project/assignments/proj4/testing) Last updated 8 months ago --- # Testing | CS186 Projects We strongly encourage testing your code yourself, especially after each part (rather than all at the end). The given tests for this project (even more so than previous projects) are **not** comprehensive tests: it **is** possible to write incorrect code that passes them all. Things that you might consider testing for include: anything that we specify in the comments or in this document that a method should do that you don't see a test already testing for, and any edge cases that you can think of. Think of what valid inputs might break your code and cause it not to perform as intended, and add a test to make sure things are working. [](https://cs186.gitbook.io/project/assignments/proj5/testing#running-tests-with-coverage) Running tests with coverage --------------------------------------------------------------------------------------------------------------------------- To find cases that you've accounted for in your implementation but are not being covered in your tests, you can run all of the Project 5 tests [with coverage](https://www.jetbrains.com/help/idea/code-coverage.html) . Afterwards, you can navigate to your ARIESRecoveryManager file to see what parts of your code are not yet tested for. [](https://cs186.gitbook.io/project/assignments/proj5/testing#cases-not-covered-in-the-public-tests) Cases not covered in the public tests ----------------------------------------------------------------------------------------------------------------------------------------------- Here are a few cases mentioned in the spec but not tested for in the public test set: * The checkpoint test provided checkpoints with a small number of transaction table and dirty page table entries -- enough to fit within 1 to 2 pages. Make sure your code still works even when there's a large amount of entries. If the entries aren't split up properly and too many entries are inserted into a single EndCheckpointLogRecord, your code will fail to flush the entry for exceeding the log tail size. * For appropriate transactions after analysis/undo, make sure that transactions [have been cleaned up](https://github.com/berkeley-cs186/sp25-rookiedb/blob/master/src/test/java/edu/berkeley/cs186/database/recovery/DummyTransaction.java#L29) (calling cleanup() on a transaction should set that flag). And here are two common cases that your code should be prepared to handle: * Make sure your redo logic still works without error even if there are no entries in the reconstructed dirty page table after analysis. * Make sure your undo logic still works without error even if there are no transactions that need to be undone after analysis. [](https://cs186.gitbook.io/project/assignments/proj5/testing#writing-your-own-tests) Writing your own tests ----------------------------------------------------------------------------------------------------------------- You can use or modify any of the functions we provided in the public test set to write your own tests. ### [](https://cs186.gitbook.io/project/assignments/proj5/testing#setup) Setup Copy @Before public void setup() throws IOException { testDir = tempFolder.newFolder("test-dir").getAbsolutePath(); recoveryManager = loadRecoveryManager(testDir); DummyTransaction.cleanupTransactions(); LogRecord.onRedoHandler(t -> { }); } The function above is run before every single test, and sets the value of the `recoveryManager` private variable to a new RecoveryManager object that operates on files in the `"test-dir"` directory (locally this directory will be generated and likely cleaned up every time you run the test wherever JUnit is configured to create temporary directories). The recovery manager object created will use a dummy locking system to prevent any dependencies with project 4, and 32 pages of memory in its buffer manager. ### [](https://cs186.gitbook.io/project/assignments/proj5/testing#getting-useful-objects) Getting useful objects The following variables of the RecoveryManager can be used for testing purposes: * `bufferManager` - Useful if you want to manually run updates using records (argument to LogRecord.redo) * `diskSpaceManager` - Useful if you want to manually run updates using records (argument to LogRecord.redo) * `logManager` - Useful to directly append and flush logs to see how the recovery manager deals with them when rolling back. See `testAbortingEnd` for an example. * `dirtyPageTable` - Useful to make sure that pages are getting flushed properly and that recLSN's are set correctly or check that its reconstructed properly during analysis. * `transactionTable` - Useful to make sure that entries are created/removed properly or check that its reconstructed properly during analysis. ### [](https://cs186.gitbook.io/project/assignments/proj5/testing#redo-checks) Redo checks You may have noticed calls to `setupRedoChecks` and `finishRedoChecks`. To help with testing, every time redo is called on a LogRecord we make a [call to a provided method](https://github.com/berkeley-cs186/sp25-rookiedb/blob/master/src/main/java/edu/berkeley/cs186/database/recovery/LogRecord.java#L156) . During regular operation this will just be a no-op function, but during testing we can set this to be whatever we want using [onRedoHandler](https://github.com/berkeley-cs186/sp25-rookiedb/blob/master/src/main/java/edu/berkeley/cs186/database/recovery/LogRecord.java#L225-L232) . To make it more straight forward to do a series of checks, setupRedoChecks accepts a list of functional objects that take a LogRecord as an argument. Every time redo is called, the first LogRecord in the list is removed and is called using the LogRecord that was redone. For example, in [testAbortingEnd](https://github.com/berkeley-cs186/sp25-rookiedb/blob/master/src/test/java/edu/berkeley/cs186/database/recovery/TestRecoveryManager.java#L196-L199) we use this to check that the expected CLR's are emitted and redone in the order that we anticipated. This is useful when: * when ending an aborted transaction, rolling back changes should involve calling redo on CLRs as they are generated * during the undo phase, rolling back changes should involve calling redo on CLRs as they are generated [PreviousYour Tasks](https://cs186.gitbook.io/project/assignments/proj5/your-tasks) [NextSubmitting the Assignment](https://cs186.gitbook.io/project/assignments/proj5/submitting-the-assignment) Last updated 7 months ago --- # Submitting the Assignment | CS186 Projects [](https://cs186.gitbook.io/project/assignments/proj5/submitting-the-assignment#files) Files ------------------------------------------------------------------------------------------------- You may **not** modify the signature of any methods or classes that we provide to you, but you're free to add helper methods. You should make sure that all code you modify belongs to files with `TODO(proj5)` comments in them (e.g. don't add helper methods to DataBox). A full list of files that you may modify follows: * `src/main/java/edu/berkeley/cs186/database/recovery/ARIESRecoveryManager.java` Make sure that your code does _not_ use any static (non-final) variables - this may cause odd behavior when running with maven vs. in your IDE (tests run through the IDE often run with a new instance of Java for each test, so the static variables get reset, but multiple tests per Java instance may be run when using maven, where static variables _do not_ get reset). [](https://cs186.gitbook.io/project/assignments/proj5/submitting-the-assignment#gradescope) Gradescope ----------------------------------------------------------------------------------------------------------- Once all of your files are prepared in your repo you can submit to Gradescope through GitHub the same way you did for [Project 0](https://cs186.gitbook.io/project/assignments/proj0/submitting#pushing-changes-to-github-classroom) . [](https://cs186.gitbook.io/project/assignments/proj5/submitting-the-assignment#submitting-via-upload) Submitting via upload --------------------------------------------------------------------------------------------------------------------------------- If your GitHub account has access to many repos, the Gradescope UI might time out while trying to load which repos you have available. If this is the case for you, you can submit your code directly using via upload. You can zip up your source code with `python3 zip.py --assignment proj5` and submit that directly to the autograder. [](https://cs186.gitbook.io/project/assignments/proj5/submitting-the-assignment#partners) Partners ------------------------------------------------------------------------------------------------------- Only one partner has to submit, but please make sure to add the other partner to the Gradescope submission. Slip minutes will be calculated individually. For example, if partner A has 10 slip minutes remaining and partner B has 20 slip minutes remaining and they submit 20 minutes late, partner A will be subject to the late penalty (1/3 off partner A's score) while partner B will have 0 remaining slip minutes and no late penalty applied to partner B's score. [](https://cs186.gitbook.io/project/assignments/proj5/submitting-the-assignment#grading) Grading ----------------------------------------------------------------------------------------------------- * 60% of your grade will be made up of tests released to you (the tests that we provided in `database.recovery.TestRecoveryManager`). * 40% of your grade will be made up of hidden, unreleased tests that we will run on your submission after the deadline. [PreviousTesting](https://cs186.gitbook.io/project/assignments/proj5/testing) [NextProject 6: NoSQL](https://cs186.gitbook.io/project/assignments/proj6) Last updated 7 months ago --- # Project 6: NoSQL | CS186 Projects [Getting Started](https://cs186.gitbook.io/project/assignments/proj6/getting-started) [Your Tasks](https://cs186.gitbook.io/project/assignments/proj6/your-tasks) [Submitting the Assignment](https://cs186.gitbook.io/project/assignments/proj6/submitting-the-assignment) [PreviousSubmitting the Assignment](https://cs186.gitbook.io/project/assignments/proj5/submitting-the-assignment) [NextGetting Started](https://cs186.gitbook.io/project/assignments/proj6/getting-started) Last updated 7 months ago --- # Project 0: Setup | CS186 Projects Project 0: Setup | CS186 Projects --- # Submitting the Assignment | CS186 Projects [](https://cs186.gitbook.io/project/assignments/proj6/submitting-the-assignment#files) Files ------------------------------------------------------------------------------------------------- You should make sure that all code you modify belongs to the .js files inside the `query/` directory. [](https://cs186.gitbook.io/project/assignments/proj6/submitting-the-assignment#gradescope) Gradescope ----------------------------------------------------------------------------------------------------------- Once all of your files are prepared in your repo you can submit to Gradescope through GitHub the same way you did for [Project 0](https://cs186.gitbook.io/project/assignments/proj0/submitting#pushing-changes-to-github-classroom) . [](https://cs186.gitbook.io/project/assignments/proj6/submitting-the-assignment#submitting-via-upload) Submitting via upload --------------------------------------------------------------------------------------------------------------------------------- If your GitHub account has access to many repos, the Gradescope UI might time out while trying to load which repos you have available. If you want to submit via upload, you can zip up your `query/` directory and upload that to Gradescope instead. [](https://cs186.gitbook.io/project/assignments/proj6/submitting-the-assignment#grading) Grading ----------------------------------------------------------------------------------------------------- * This project will be worth 5% of your overall grade in the class. 100% of your grade will come from the public tests provided to you. [PreviousYour Tasks](https://cs186.gitbook.io/project/assignments/proj6/your-tasks) [NextAdding a partner on GitHub](https://cs186.gitbook.io/project/common/adding-a-partner-on-github) Last updated 7 months ago --- # Getting Started | CS186 Projects [](https://cs186.gitbook.io/project/assignments/proj6/getting-started#logistics) Logistics ----------------------------------------------------------------------------------------------- This project is due **Thursday, 5/8/2025 at 11:59PM PDT (GMT-7)**. It is worth 5% of your overall grade in the class. 100% of your grade will come from the public tests released with the data set. Like Project 1, this project **must be completed individually.** **A gentle reminder that though our projects have tight release schedules, projects don't tend to take the entire time given to complete them :)** [](https://cs186.gitbook.io/project/assignments/proj6/getting-started#prerequisites) Prerequisites ------------------------------------------------------------------------------------------------------- There are no hard prerequisites for this project. The spec will walk you through writing a query in Mongo's syntax. However, you may find watching the NoSQL lectures (after they're released) helpful to help contextualize how Mongo differs from the traditional SQL databases we've been working with for the majority of this semester. [](https://cs186.gitbook.io/project/assignments/proj6/getting-started#academic-integrity-policy) Academic Integrity Policy ------------------------------------------------------------------------------------------------------------------------------- “_As a member of the UC Berkeley community, I act with honesty, integrity, and respect for others._” — UC Berkeley Honor Code **Read through the academic integrity guidelines** [**here**](https://cs186berkeley.net/integrityguidelines/) **.** We will be running plagiarism detection software on every submission against our own database of this semester's submissions, past submissions, and publicly hosted implementations on platforms such as GitHub and GitLab, followed by a thorough manual review process. Plagiarism on any assignment will result in a [non-reportable warning](https://conduct.berkeley.edu/wp-content/uploads/2024/01/Academic-Misconduct-Resource-Sheet-for-Students-UPDATED.pdf) and a grade penalty based on the severity of the infraction. Note that Project 6 is an individual project; while this means we expect you to write all your queries on your own, all of the following are **permitted** under our academic integrity guidelines: * Discussion of approaches for solving a problem. * Giving away or receiving conceptual ideas towards a problem solution. * Discussion of specific syntax issues and bugs in your code. * Looking at another student's code for the sole purpose of helping that student debug. * Using small snippets of code that you find online for solving tiny problems (e.g. Googling “number to string mongo” may lead you to some sample code that you copy and paste into your solution). Such code should always be cited with relevant code comments. As long as you follow the guidelines, there isn't anything to worry about here. While we do rely on software to find possible cases of academic dishonesty, every case is reviewed by multiple TAs who can filter out false positives. [](https://cs186.gitbook.io/project/assignments/proj6/getting-started#fetching-the-released-code) Fetching the released code --------------------------------------------------------------------------------------------------------------------------------- The GitHub Classroom link for this project is in the Project 6 release post on [Edstem](https://edstem.org/us/courses/70276/discussion/) . Once your private repo is set up, clone the Project 6 skeleton code onto your local machine. [](https://cs186.gitbook.io/project/assignments/proj6/getting-started#required-software) Required Software --------------------------------------------------------------------------------------------------------------- ### [](https://cs186.gitbook.io/project/assignments/proj6/getting-started#mongodb-v4.4) MongoDB v4.4 We'll be exploring the document-oriented database [MongoDB](https://en.wikipedia.org/wiki/MongoDB) in this project. Check if you already have a copy installed by running `mongo --version` in a terminal. If you already have it installed you should see output similar to the following: Copy > mongo --version MongoDB shell version v4.4.1 Build Info: ... If you don't already have MongoDB on your machine, follow the instructions for your platform: #### [](https://cs186.gitbook.io/project/assignments/proj6/getting-started#windows) Windows Follow these instructions to install MongoDB and the MongoDB Database Tools on Windows: 1. MongoDB [Tutorial](https://www.mongodb.com/docs/v4.4/tutorial/install-mongodb-on-windows/#install-mongodb-community-edition) * You won't see an option for MongoDB 4.4; feel free to install any higher version other than 6.0. Please post on Ed if you have any issues running commands with your MongoDB version; we're looking to weed out versions that don't work! 2. MongoDB Command Line Database Tools [Tutorial](https://www.mongodb.com/docs/database-tools/installation/installation-windows/) * Please use the `msi` download [here](https://fastdl.mongodb.org/tools/db/mongodb-database-tools-windows-x86_64-100.10.0.msi) instead of the download link provided in the above tutorial. Specifically, you should go to the [MongoDB Download Center -> MongoDB Command Line Database Tools Download](https://www.mongodb.com/try/download/database-tools) , select `Windows x86_64` as the _Platform_, and select `msi` as the _Package_. Once you have everything installed you'll want to locate the location of the mongo shell and mongoimport binaries. Confirm the location of the binaries at the following spots: * The mongo shell binary (mongo.exe) should be located at `C:\Program Files\MongoDB\Server\4.4\bin\`. * The mongoimport binary (mongoimport.exe) should be located at `C:\Program Files\MongoDB\Tools\100\bin\`. If you can't find it at that exact location, check other directories under `C:\Program Files\MongoDB\Tools\`. If your file has a long name like `windows-x86-64-bit-mongoimport.exe` then rename it to just `mongoimport.exe` Add the two directories to your `PATH`. To edit your environment variables on Windows 10, use the following steps: 1. Open up search and type in "Edit the system environment variables" 2. Open that up and click "Environment Variables..." near the bottom 3. Click "Path" under user variables (top half of the screen) and click edit 4. Click "New" on the top right and add C:\\Program Files\\MongoDB\\Server\\4.4\\bin\\ 5. Repeat the same process for database tools with the appropriate PATH If everything went successfully you should be able to run `mongo --version` and `mongoimport --version` successfully in Git Bash, or `mongo.exe --version` and `mongoimport.exe --version` in other shells. #### [](https://cs186.gitbook.io/project/assignments/proj6/getting-started#macos) MacOS If you don't already have it, install [Homebrew](https://brew.sh/) . Then, in a terminal, run the following: Copy brew tap mongodb/brew brew install mongodb-community@4.4 brew services start mongodb-community@4.4 If you run into a CompilerSelectionError, run `xcode-select --install` and repeat the commands above. Check that everything is installed by running `mongo --version` and `mongoimport --version`. If both of these commands work then you should be good to go. * If your Mac is M1-based or later, and you install mongodb through homebrew, it's likely that you will get an error saying `mongo: command not found`. In the output of `brew install mongodb-community@4.4`, you should have gotten a message giving a command on how to do this. It should look similar (not necessarily the same) to Copy echo 'export PATH="/opt/homebrew/opt/mongodb-community@4.4/bin:$PATH"' >> ~/.zshrc Run that command, open a new terminal session, (this is important!) and your error should be gone. If your version of Mac can't support Mongo 4.4 then we recommend you use the Docker approach to complete this assignment. Otherwise, if it doesn't support Docker either then you can use Mongo 4.2 instead. This will work the same as 4.4 except the following functions recommended in the spec will not be available, so you'll have to modify the advice slightly: * `{$first: }` will have to be replaced with `{ $arrayElemAt: [ , 0 ]}` * `$isNumber` will have to be rewritten as an or statement based on the the fields [type](https://docs.mongodb.com/manual/reference/operator/aggregation/type/) #### [](https://cs186.gitbook.io/project/assignments/proj6/getting-started#linux) Linux Follow the instructions [here](https://docs.mongodb.com/manual/administration/install-on-linux/) for your appropriate platform. If something breaks during the installation process and you can't run `mongo` and `mongoimport --version`, follow the instructions in the next section (Docker) to get a docker container with mongo and python pre-installed. #### [](https://cs186.gitbook.io/project/assignments/proj6/getting-started#docker) Docker If you're on MacOS/Linux and ran into issues with installing mongo directly on your host machine, we recommend using a [docker container](https://www.docker.com/resources/what-container) with mongo and python pre-installed instead. To use our Docker image you'll need to install Docker Community Edition ("CE") on your machine. * To install Docker CE on Mac open the [Docker getting started page](https://www.docker.com/get-started) , stay on the "Developer" tab, and click the button on the right to download the installer for your OS. Follow all the instructions included. * To install Docker CE on Linux, open the [Docker docs](https://docs.docker.com/install/#server) , and click the appropriate link to find instructions for your Linux distro. Confirm that Docker is installed by running `docker --version` on the command line. If it works, you should be good to go. From the root of your project directory, run `pwd` to get the path to your present working directory. Then carefully run the following command (be sure to replace `/path/to/project/directory` with the path from the previous step): `docker run --name mongo186 -v "/path/to/project/directory:/proj6" -it chriskw/mongo186` This will download an image of a container with mongo and python preinstalled. You should see output like the following: Copy $ docker run --name mongo186 -v "/replace/this/accordingly:/proj6" -it chriskw/mongo186 Unable to find image 'chriskw/mongo186:latest' locally latest: Pulling from chriskw/mongo186 (a bunch of downloads should happen here) about to fork child process, waiting until server is ready for connections. forked process: 10 child process started successfully, parent exiting student@a2ba045477a4:/$ This should bring you into a container with the necessary requirements. Run `cd /proj6` to enter the proj6 directory. All of the files on your host machine should be present. Changes on your host machine (for example, using a text editor like VSCode/Sublime) should be visible from within this container as you work through the project. If everything went smoothly, you should be able to go to the next section [Extract the data set](https://cs186.gitbook.io/project/assignments/proj6/getting-started#extract-the-data-set) . If you exit the container and wish to access it again, you can run the command `docker start -ai mongo186` to re-enter the container. If your proj6 directory is empty, you most likely provided an invalid path when you ran `docker run`. In this case, run the following two commands: `docker kill mongo186` followed by `docker rm mongo186`. Afterwards, rerun the `docker run` command from above, making sure to replace the string after the `-v` accordingly. Followup on Edstem if you run into trouble with this step. ### [](https://cs186.gitbook.io/project/assignments/proj6/getting-started#python) Python You'll need a copy of Python 3.5 or higher to run the tests for this project locally (the same as used in Project 1). You can check if you already have an existing copy by running `python3 --version` in a terminal. If you don't already have a working copy download and install one for your appropriate platform from [here](https://www.python.org/downloads/) . [](https://cs186.gitbook.io/project/assignments/proj6/getting-started#extract-the-data-set) Extract the data set --------------------------------------------------------------------------------------------------------------------- Download the data set from the class drive [here](https://drive.google.com/file/d/1mwPqVvkTYEwrBU7q6RDfb5usFdKo0jpc/view?usp=drive_link) . Unzip the `data.zip` file inside your `sp25-proj6-yourname` directory. You should now have a `data/` directory in your `sp25-proj6-yourname` directory. Afterwards, try running `python3 load.py`. You should see output like the following: Copy > python3 load.py 2021-04-11T08:30:08.567-0700 connected to: mongodb://localhost:27017/ 2021-04-11T08:30:08.567-0700 dropping: movies.credits 2021-04-11T08:30:14.590-0700 45475 document(s) imported successfully. 0 document(s) failed to import. 2021-04-11T08:30:14.609-0700 connected to: mongodb://localhost:27017/ 2021-04-11T08:30:14.610-0700 dropping: movies.movies_metadata 2021-04-11T08:30:15.551-0700 45406 document(s) imported successfully. 0 document(s) failed to import. 2021-04-11T08:30:15.562-0700 connected to: mongodb://localhost:27017/ 2021-04-11T08:30:15.562-0700 dropping: movies.keywords 2021-04-11T08:30:16.569-0700 43986 document(s) imported successfully. 0 document(s) failed to import. 2021-04-11T08:30:16.580-0700 connected to: mongodb://localhost:27017/ 2021-04-11T08:30:16.581-0700 dropping: movies.ratings 2021-04-11T08:30:17.968-0700 99958 document(s) imported successfully. 0 document(s) failed to import ### [](https://cs186.gitbook.io/project/assignments/proj6/getting-started#unfiltered-dataset) Unfiltered Dataset The dataset used for this project is a subset of the original dataset -- we've filtered out overtly offensive and inappropriate keywords and movie descriptions, as well as any keywords that appear less than 15 times. If you want to access the original dataset without these filters applied, the unfiltered version is [here](https://drive.google.com/file/d/1ZiYYcW_vqeyL239AcAbsd2nybXZLdt9e/view) . Note that the expected output of the project is based on the filtered version, so you'll need to use the filtered version to complete the project. [](https://cs186.gitbook.io/project/assignments/proj6/getting-started#running-the-tests) Running the tests --------------------------------------------------------------------------------------------------------------- If you followed the instructions above you should now be able to test your code. Navigate to your project directory and try using `python3 test.py`. You should get output similar to the following: Copy > python3 test.py q0 FAIL: Empty output q1i FAIL: Empty output q1ii FAIL: Empty output q1iii FAIL: Empty output q1iv FAIL: Empty output q2i FAIL: Empty output q2ii FAIL: Empty output q2iii FAIL: Empty output q3i FAIL: Empty output q3ii FAIL: Empty output If so, move on to the next section to start the project. If you see `ERROR`instead of `FAIL` create a followup on Edstem with details from your `your_output/` folder. [](https://cs186.gitbook.io/project/assignments/proj6/getting-started#debugging-issues-with-github-classroom) Debugging Issues with GitHub Classroom --------------------------------------------------------------------------------------------------------------------------------------------------------- Feel free to skip this section if you don't have any issues with GitHub Classroom. If you are having issues (i.e. the page froze or some error message appeared), first check if you have access to your repo at `https://github.com/cs186-student/sp25-proj6-username`, replacing `username` with your GitHub username. If you have access to your repo and the starter code is there, then you can proceed as usual. ### [](https://cs186.gitbook.io/project/assignments/proj6/getting-started#id-404-not-found) 404 Not Found If you're getting a 404 not found page when trying to access your repo, make sure you've set up your repo using the GitHub Classroom link in the Project 6 release post on [Edstem](https://edstem.org/us/courses/70276/discussion/) . If you don't have access to your repo at all after following these steps, feel free to contact the course staff on Edstem. [PreviousProject 6: NoSQL](https://cs186.gitbook.io/project/assignments/proj6) [NextYour Tasks](https://cs186.gitbook.io/project/assignments/proj6/your-tasks) Last updated 7 months ago --- # Adding a partner on GitHub | CS186 Projects If you want to share your code over GitHub with your project partner you'll need to pick between the two of you whose copy of the starter code you want to work off of. For example, if users `OskiBear` and `JoeBruin` want to collaborate then they might both choose to work off of `sp25-proj2-OskiBear`. In that case `OskiBear` would navigate to "Settings", "Manage access", then "Invite teams or people" and add `JoeBruin`(see images below). `JoeBruin` should receive an email afterwards containing an invitation to the repo. Alternatively `OskiBear` can share the link to the repo after sending the invitation. Once you both have access to the repo you your partner can clone the repo to get a local copy to work off of. From there you can share files over git, pushing and pulling updates as you collaborate. **Do not add anyone other than your project partner to your repository.** You aren't allowed to share code with any students other than your project partner for this project. ![](https://cs186.gitbook.io/project/~gitbook/image?url=https%3A%2F%2F678656433-files.gitbook.io%2F%7E%2Ffiles%2Fv0%2Fb%2Fgitbook-legacy-files%2Fo%2Fassets%252F-MFVQnrLlCBowpNWJo1E%252Fsync%252F90a0829c6f56c5592579fee8b4063c14d2db6337.png%3Fgeneration%3D1599798456341006%26alt%3Dmedia&width=768&dpr=4&quality=100&sign=80802878&sv=2) Navigate to your sp25-proj2-yourname repo's Settings ![](https://cs186.gitbook.io/project/~gitbook/image?url=https%3A%2F%2F678656433-files.gitbook.io%2F%7E%2Ffiles%2Fv0%2Fb%2Fgitbook-legacy-files%2Fo%2Fassets%252F-MFVQnrLlCBowpNWJo1E%252Fsync%252Ff49406365c81af88df42b4b459b8cd499346cd46.png%3Fgeneration%3D1599798455242759%26alt%3Dmedia&width=768&dpr=4&quality=100&sign=f7a3c389&sv=2) Go to Manage Access ![](https://cs186.gitbook.io/project/~gitbook/image?url=https%3A%2F%2F678656433-files.gitbook.io%2F%7E%2Ffiles%2Fv0%2Fb%2Fgitbook-legacy-files%2Fo%2Fassets%252F-MFVQnrLlCBowpNWJo1E%252Fsync%252Fd68ce49b36795993677b8be6a3570f455a8d3bfc.png%3Fgeneration%3D1599798457430817%26alt%3Dmedia&width=768&dpr=4&quality=100&sign=4536f86&sv=2) ![](https://cs186.gitbook.io/project/~gitbook/image?url=https%3A%2F%2F678656433-files.gitbook.io%2F%7E%2Ffiles%2Fv0%2Fb%2Fgitbook-legacy-files%2Fo%2Fassets%252F-MFVQnrLlCBowpNWJo1E%252Fsync%252Fc2184addfe151556bc93d7d71d4aa407610aef70.png%3Fgeneration%3D1599798454394042%26alt%3Dmedia&width=768&dpr=4&quality=100&sign=22549726&sv=2) Invite your partner (replace JoeBruin with your partner's GitHub username) After following these steps your partner should receive an email containing an invitation link. Alternatively, you can share the link to the repo with your partner. [PreviousSubmitting the Assignment](https://cs186.gitbook.io/project/assignments/proj6/submitting-the-assignment) [NextDevelopment Container Setup](https://cs186.gitbook.io/project/common/devcontainer-setup) Last updated 10 months ago --- # Miscellaneous | CS186 Projects [Nested Loop Join Animations](https://cs186.gitbook.io/project/common/misc/nested-loop-join-animations) [PreviousDevelopment Container Setup](https://cs186.gitbook.io/project/common/devcontainer-setup) [NextNested Loop Join Animations](https://cs186.gitbook.io/project/common/misc/nested-loop-join-animations) Last updated 4 years ago --- # Nested Loop Join Animations | CS186 Projects **Key** * Records highlighted in blue belong to a page in the left relation that is loaded into memory. * Records highlighted in orange belong to a page in the right relation that is loaded into memory. * The dark blue and dark orange records are the two records currently being compared to see if they fit the join criteria. * The purple squares represent which pairs of records have already been considered. Notice that regardless of the nested loop join implementation, by the time we finish we've considered every pair of records! [](https://cs186.gitbook.io/project/common/misc/nested-loop-join-animations#normal-speed) Normal Speed ----------------------------------------------------------------------------------------------------------- ### [](https://cs186.gitbook.io/project/common/misc/nested-loop-join-animations#simple-nested-loop-join) Simple Nested Loop Join ![](https://cs186.gitbook.io/project/~gitbook/image?url=https%3A%2F%2F678656433-files.gitbook.io%2F%7E%2Ffiles%2Fv0%2Fb%2Fgitbook-legacy-files%2Fo%2Fassets%252F-MFVQnrLlCBowpNWJo1E%252Fsync%252Fa73c972f30b1f1f9a4d3338fa7994c85c980d74a.gif%3Fgeneration%3D1601331281677102%26alt%3Dmedia&width=768&dpr=4&quality=100&sign=816d4367&sv=2) ### [](https://cs186.gitbook.io/project/common/misc/nested-loop-join-animations#page-nested-loop-join) Page Nested Loop Join ![](https://cs186.gitbook.io/project/~gitbook/image?url=https%3A%2F%2F678656433-files.gitbook.io%2F%7E%2Ffiles%2Fv0%2Fb%2Fgitbook-legacy-files%2Fo%2Fassets%252F-MFVQnrLlCBowpNWJo1E%252Fsync%252F6adf3cb0f45370a03122af29a549010ff73d14eb.gif%3Fgeneration%3D1601331281376980%26alt%3Dmedia&width=768&dpr=4&quality=100&sign=14026108&sv=2) ### [](https://cs186.gitbook.io/project/common/misc/nested-loop-join-animations#block-nested-loop-join-b-4) Block Nested Loop Join (B=4) ![](https://cs186.gitbook.io/project/~gitbook/image?url=https%3A%2F%2F678656433-files.gitbook.io%2F%7E%2Ffiles%2Fv0%2Fb%2Fgitbook-legacy-files%2Fo%2Fassets%252F-MFVQnrLlCBowpNWJo1E%252Fsync%252Feec406d2f15d541041f6cb5a3578064547de1227.gif%3Fgeneration%3D1601083826234812%26alt%3Dmedia&width=768&dpr=4&quality=100&sign=b0903340&sv=2) [](https://cs186.gitbook.io/project/common/misc/nested-loop-join-animations#x2-speed) x2 Speed --------------------------------------------------------------------------------------------------- ### [](https://cs186.gitbook.io/project/common/misc/nested-loop-join-animations#simple-nested-loop-join-1) Simple Nested Loop Join ![](https://cs186.gitbook.io/project/~gitbook/image?url=https%3A%2F%2F678656433-files.gitbook.io%2F%7E%2Ffiles%2Fv0%2Fb%2Fgitbook-legacy-files%2Fo%2Fassets%252F-MFVQnrLlCBowpNWJo1E%252Fsync%252F7d98e512c06ac453b6d348f26f034152a05f9ed7.gif%3Fgeneration%3D1601331287864478%26alt%3Dmedia&width=768&dpr=4&quality=100&sign=efe6ba40&sv=2) ### [](https://cs186.gitbook.io/project/common/misc/nested-loop-join-animations#page-nested-loop-join-1) Page Nested Loop Join ![](https://cs186.gitbook.io/project/~gitbook/image?url=https%3A%2F%2F678656433-files.gitbook.io%2F%7E%2Ffiles%2Fv0%2Fb%2Fgitbook-legacy-files%2Fo%2Fassets%252F-MFVQnrLlCBowpNWJo1E%252Fsync%252F34b7dfb801054415308bebbdb903a79ca66b425e.gif%3Fgeneration%3D1601331282193511%26alt%3Dmedia&width=768&dpr=4&quality=100&sign=3e26b034&sv=2) ### [](https://cs186.gitbook.io/project/common/misc/nested-loop-join-animations#block-nested-loop-join-b-4-1) Block Nested Loop Join (B=4) ![](https://cs186.gitbook.io/project/~gitbook/image?url=https%3A%2F%2F678656433-files.gitbook.io%2F%7E%2Ffiles%2Fv0%2Fb%2Fgitbook-legacy-files%2Fo%2Fassets%252F-MFVQnrLlCBowpNWJo1E%252Fsync%252F6417e98132194a70acfd2b305f32d6ed096028bc.gif%3Fgeneration%3D1601331282191017%26alt%3Dmedia&width=768&dpr=4&quality=100&sign=88d9729a&sv=2) [PreviousMiscellaneous](https://cs186.gitbook.io/project/common/misc) Last updated 5 years ago --- # Your Tasks | CS186 Projects ![](https://cs186.gitbook.io/project/~gitbook/image?url=https%3A%2F%2F678656433-files.gitbook.io%2F%7E%2Ffiles%2Fv0%2Fb%2Fgitbook-x-prod.appspot.com%2Fo%2Fspaces%252F-MFVQnrLlCBowpNWJo1E%252Fuploads%252Fgit-blob-1a5651bccd266676a5e24fcb41ca3add8521a877%252Fdatatake%2520%282%29%2520%283%29%2520%283%29%2520%283%29%2520%282%29.png%3Falt%3Dmedia&width=768&dpr=4&quality=100&sign=fd694d36&sv=2) Datatake In this project you'll be working with a subset of the [MovieLens Dataset](https://www.kaggle.com/rounakbanik/the-movies-dataset) . Unlike the data set you worked on long ago in Project 1, the table here won't be organized in tables of records but rather as collections of documents! Documents are similar to records in the sense that they are used to group together pieces of data, but unlike the records we covered for SQL databases, documents can have fields that _are not_ primitive data types. For example, the following document has three fields, two of which aren't primitive data types: Copy { "dataA": 1, // a regular primitive data type "anArray": [1,2,3], // an array! "nestedDocument": {"dataB": 2, "dataC": 3} // a doc inside a doc! } The following section will introduce you to the dataset. [](https://cs186.gitbook.io/project/assignments/proj6/your-tasks#understanding-the-dataset) Understanding the Dataset -------------------------------------------------------------------------------------------------------------------------- This section will be helpful to reference as you're completing the tasks. A nice way to get an example of a record for any of the four collections (for example, `ratings`) is to call `db.ratings.findOne()` in the mongo shell. Copy $ mongo movies MongoDB shell version v4.4.1 connecting to: mongodb://127.0.0.1:27017/movies?compressors=disabled&gssapiServiceName=mongodb Implicit session: session { "id" : UUID("cd49cd34-6c93-4548-aa20-b57e9f45d975") } MongoDB server version: 4.4.1 > db.ratings.findOne() { "_id" : ObjectId("5fb32f37766efe011e6af587"), "userId" : 1, "movieId" : 783, "rating" : 2, "timestamp" : 1260759148 } ### [](https://cs186.gitbook.io/project/assignments/proj6/your-tasks#movies-metadata) Movies Metadata The `movies_metadata` collection contains documents with metadata for every movie in the MovieLens Dataset. There are many possible fields in each document, but some you may find useful for completing this project are: * `movieId (int)`: A unique identifier for the movie. Corresponds to the field of the same name in `keywords`, `ratings`, and `credits`. * `title (string)`: The title of the movie. * `tagline (string)`: A short phrase usually used to advertise the movie. * `release_date (int)`: The date of the film's release, as a UNIX Timestamp. * `budget (inconsistent)`: The movie's production budget in USD. See question 2iii for more details on this field's type. * `vote_average (number)`: The average rating given by viewers on a scale from 0 to 10. * `vote_count (int)`: The total number of ratings given. * `revenue (int)`: The movie's revenue in USD * `runtime (int)`: The length of the movie in minutes * `genres (array)`: 0 or more documents each containing the following: * `name (string)`: the name of one of the movie's genres * `id (int)`: a unique identifier for the genre Example document: Copy // Extra fields omitted for brevity { "budget" : 30000000, "genres" : [\ { "id" : 16, "name" : "Animation" },\ { "id" : 35, "name" : "Comedy" },\ { "id" : 10751, "name" : "Family" }\ ], "release_date" : 815040000, "revenue" : 373554033, "runtime" : 81, "status" : "Released", "title" : "Toy Story", "vote_average" : 7.7, "vote_count" : 5415, "movieId" : 862, "tagline" : "" } ### [](https://cs186.gitbook.io/project/assignments/proj6/your-tasks#keywords) Keywords The `keywords` collection contains documents with keywords related to certain movies. Each document in the collection has the following attributes: * `movieId (int)`: A unique identifier for the movie. Corresponds to the field of the same name in `movies_metadata`, `ratings`, and `credits` * `keywords (array)`: 0 or more documents each containing the following: * `id (int)`: A unique identifier for a keyword * `name (string)`: A keyword associated with the movie, for example "based on novel", "pirate", and "murder". Example document: Copy { "keywords" : [\ { "id" : 3633, "name" : "dracula" },\ { "id" : 11931, "name" : "spoof" }\ ], "movieId" : 12110 } ### [](https://cs186.gitbook.io/project/assignments/proj6/your-tasks#ratings) Ratings The `ratings` collection contains roughly 10,000 ratings submitted by specific viewers. Each document consists of the following format: * `userId (int)`: A unique identifier for the user who gave the rating * `movieId (int)`: A unique identifier for the movie. Corresponds to the field of the same name in `movies_metadata`, `keywords`, and `credits` * `rating (number)`: The rating the user gave the movie, from 0 to 5. * `timestamp (int)`: UNIX timestamp of when this rating was given Copy { "userId" : 1, "movieId" : 9909, "rating" : 2.5, "timestamp" : 1260759144 } ### [](https://cs186.gitbook.io/project/assignments/proj6/your-tasks#credits) Credits The `credits` collection contains details on writers, actors, directors, and technicians who worked on the production of the movies in the data set. Each document consists of the following:\` * `movieId (int)`: A unique identifier for the movie. Corresponds to the field of the same name in `movies_metadata`, `keywords`, and `ratings` * `cast (array)`: 0 or more documents of the each containing the following fields: * `id (int)`: A unique identifier for the actor who played the character * `character (string)`: The name of the character in the movie * `name (string)`: The name of the actor as listed in the movie's credits * `crew (array)`: 0 or more documents each containing the following fields: * `id (int)`: A unique identifier for the crew member * `department (string)`: The department the crew member worked in * `job (string)`: The job title of the crew member (e.g. "Audio Technician", "Director") * `name (string)`: The name of the crew member as listed in the movie's credits Example document: Copy // Extra fields for cast and crew omitted for brevity { "cast" : [\ {\ "character" : "Max Goldman",\ "id" : 6837,\ "name" : "Walter Matthau"\ },\ ... // Other cast members\ ], "crew" : [\ {\ "department" : "Directing",\ "id" : 26502,\ "job" : "Director",\ "name" : "Howard Deutch",\ },\ ... // Other crew members\ ], "movieId" : 15602 } [](https://cs186.gitbook.io/project/assignments/proj6/your-tasks#building-your-first-query) Building your first query -------------------------------------------------------------------------------------------------------------------------- This task will walk you through step by step how to construct a query in MongoDB, and introduce you to some helpful operations for use in the rest of the tasks. If you're already comfortable doing queries in MongoDB feel free to skip to the end of this section to complete the corresponding question in `query/q0.js`. #### [](https://cs186.gitbook.io/project/assignments/proj6/your-tasks#querying-from-the-ratings-collection) Querying from the ratings collection Inside the file `query/q0.js` you should see the following: Copy // Task 0 (Building your first query) db.todo.aggregate([\ // TODO: Write your query here\ ]); Try replacing the `todo` on line 3 so that the line becomes `db.ratings.aggregate([` instead. This tells mongo that we want to pull in documents from the `ratings` collection. Now try running the the following in a terminal: `python3 test.py q0 --view`. This should run the query and give something similar to the following output (note that the \_id field will likely differ, which is fine):\ \ Copy\ \ Showing up to the first 10 results of the query\ { "_id" : ObjectId("5fb11b4a82f9cebdc2acaea0"), "userId" : 1, "movieId" : 9909, "rating" : 2.5, "timestamp" : 1260759144 }\ { "_id" : ObjectId("5fb11b4a82f9cebdc2acaea1"), "userId" : 1, "movieId" : 783, "rating" : 2, "timestamp" : 1260759148 }\ ....\ \ This query attempts to read every single document in the `ratings` collection, and would be analogous to something like the following:\ \ Copy\ \ SELECT * FROM ratings;\ \ #### \ \ [](https://cs186.gitbook.io/project/assignments/proj6/your-tasks#match)\ \ Match\ \ The query from the earlier section attempts to read every document in the `ratings` collections. This next query will selectively match only specific documents matching a specific property.\ \ Copy\ \ db.ratings.aggregate([\ // Match documents with certain timestamps\ {\ $match: {\ timestamp: {\ $gte: 838857600, // >= 838857600\ $lt: 849398400 // < 849398400\ }\ }\ }\ ]);\ \ It may be useful to see how this would look as a SQL query:\ \ Copy\ \ SELECT * FROM ratings WHERE timestamp >= 838857600 AND timestamp < 849398400;\ \ After pasting in the new query into `query/q0.js` and running `test.py q0 --view` you should see output resembling the following:\ \ Copy\ \ Showing up to the first 10 results of the query\ { "_id" : ObjectId("5fb11b4a82f9cebdc2acc11b"), "userId" : 24, "movieId" : 400, "rating" : 4, "timestamp" : 849321769 }\ { "_id" : ObjectId("5fb11b4a82f9cebdc2acc11c"), "userId" : 24, "movieId" : 949, "rating" : 5, "timestamp" : 849321588 }\ ...\ \ Lets break down the query.\ \ * `db.ratings.aggregate([ ... ])` : This tells mongo that we'll be running an "aggregate" operation. We can pass in a list `[ ... ]` known as the "pipeline", which will execute a series of operations. Each operation in the pipeline is known as a "stage", and each stage operates on the output of the previous stage.\ \ * `{$match: ...}` : This is the only element of the pipeline so far. This tells mongo that we want documents from the collection that match certain properties, much like a `WHERE` clause.\ \ * `{timestamp: { $gte: ..., $lt: ...}}` : This tells mongo that we only want documents where the timestamp field has a value greater than or equal to `838857600` and less than `849398400`.\ \ * `838857600` and `849398400`: The value in the `timestamp` field is the number of seconds that have elapsed since January 1, 1970. This is more commonly known as "Unix time", "POSIX time", "Epoch time" or "UNIX Timestamp" and is a common way to represent times in computer systems. The two timestamps we use in the query correspond to October 1st, 1996 and December 1st, 1996 respectively.\ \ * There's no shortage of online tools like [this one](https://www.epochconverter.com/)\ to convert between human readable times and UNIX time.\ \ * If you've ever heard of rumors about the world ending in January, 2038, that has to do with the way these timestamps are stored!\ \ \ \ #### \ \ [](https://cs186.gitbook.io/project/assignments/proj6/your-tasks#group)\ \ Group\ \ Next we'll extend our pipeline to perform an aggregate similar to what we might attempt in SQL.\ \ Copy\ \ db.ratings.aggregate([\ // Match documents with certain timestamps\ {$match: {timestamp: { $gte: 838857600, $lt: 849398400}}},\ // Perform an aggregation\ {\ $group: {\ _id: "$movieId", // Group by the field movieId\ min_rating: {$min: "$rating"}, // Get the min rating for each group\ max_rating: {$max: "$rating"}, // Get the max rating for each group\ count: {$sum: 1} // Get the count for each group\ }\ }\ ]);\ \ The equivalent SQL expression would look like the following:\ \ Copy\ \ SELECT\ movieId as _id,\ MAX(rating) as max_rating,\ MIN(rating) as min_rating,\ COUNT(*) as count\ FROM ratings\ WHERE timestamp >= 838857600 AND timestamp < 849398400\ GROUP BY movieId;\ \ After pasting in the new query into `query/q0.js` and running `test.py q0 --view` :\ \ Copy\ \ { "_id" : 1094, "min_rating" : 3, "max_rating" : 3, "count" : 1 }\ { "_id" : 830, "min_rating" : 2, "max_rating" : 5, "count" : 2 }\ { "_id" : 474, "min_rating" : 2, "max_rating" : 5, "count" : 16 }\ { "_id" : 62, "min_rating" : 3, "max_rating" : 5, "count" : 12 }\ { "_id" : 64, "min_rating" : 3, "max_rating" : 3, "count" : 1 }\ { "_id" : 231, "min_rating" : 1, "max_rating" : 5, "count" : 32 }\ ...\ \ A group "stage" in the pipeline always takes the following form:\ \ Copy\ \ {\ $group:\ {\ _id: , // Group by the field or value in \ : { : },\ ... // as many copies of the above as you want\ }\ }\ \ In our above example, we grouped by the `movieId` field. To indicate that we were referring to a field and not the string literal `"movieId"` we prefixed it `$`. After that we had three expressions representing values we wanted to compute in the aggregate. The first two expressions computed the `min` and `max` values of the `rating` field.\ \ The last column looks a bit peculiar: `count: {$sum: 1}`. This assigns the count field to the accumulated sum of the value `1`. This means we add together `n` copies of the value `1` where `n` is the number of documents in each group, giving the total count of documents in each group.\ \ #### \ \ [](https://cs186.gitbook.io/project/assignments/proj6/your-tasks#sort-and-limit)\ \ Sort and Limit\ \ Next lets try to see the top 10 movies with the most ratings. Continuing to build off our previous query:\ \ Copy\ \ db.ratings.aggregate([\ // Match documents with certain timestamps\ {$match: {timestamp: { $gte: 838857600, $lt: 849398400}}},\ // Perform an aggregation\ {\ $group: {\ _id: "$movieId", // Group by the field movieId\ min_rating: {$min: "$rating"}, // Get the min rating for each group\ max_rating: {$max: "$rating"}, // Get the max rating for each group\ count: {$sum: 1} // Get the count for each group\ }\ },\ // Sort in descending order of count, break ties by ascending order of _id\ {$sort: {count: -1, _id: 1}},\ // Limit to only the first 10 documents\ {$limit: 10}\ ]);\ \ Our equivalent query in SQL now looks like:\ \ Copy\ \ SELECT\ movieId as _id,\ MAX(rating) as max_rating,\ MIN(rating) as min_rating,\ COUNT(*) as count\ FROM ratings\ WHERE timestamp >= 838857600 AND timestamp < 849398400\ GROUP BY movieId\ ORDER BY count DESC, _id ASC\ LIMIT 10;\ \ After pasting in the new query into `query/q0.js` and running `test.py q0 --view` :\ \ Copy\ \ { "_id" : 480, "min_rating" : 2, "max_rating" : 5, "count" : 48 }\ { "_id" : 356, "min_rating" : 1, "max_rating" : 5, "count" : 47 }\ { "_id" : 590, "min_rating" : 3, "max_rating" : 5, "count" : 45 }\ { "_id" : 457, "min_rating" : 3, "max_rating" : 5, "count" : 44 }\ { "_id" : 296, "min_rating" : 1, "max_rating" : 5, "count" : 42 }\ { "_id" : 592, "min_rating" : 2, "max_rating" : 5, "count" : 42 }\ { "_id" : 150, "min_rating" : 2, "max_rating" : 5, "count" : 41 }\ { "_id" : 380, "min_rating" : 2, "max_rating" : 5, "count" : 39 }\ { "_id" : 589, "min_rating" : 1, "max_rating" : 5, "count" : 37 }\ { "_id" : 165, "min_rating" : 2, "max_rating" : 5, "count" : 35 }\ \ The sort stage always takes the following form:\ \ `{ $sort: { : , : ... } }`\ \ The fields refer to which field of the output to sort on. The sort order is always either `1` to indicate ascending order or `-1` for descending order.\ \ The limit stage just needs to specify a number to limit the number of possible documents.\ \ #### \ \ [](https://cs186.gitbook.io/project/assignments/proj6/your-tasks#lookup)\ \ Lookup\ \ Next, we'll do the equivalent of a join in a SQL database to figure out what movies we're the IDs correspond to. Building again off the previous query:\ \ Copy\ \ db.ratings.aggregate([\ // Match documents with certain timestamps\ {$match: {timestamp: { $gte: 838857600, $lt: 849398400}}},\ // Perform an aggregation\ {\ $group: {\ _id: "$movieId", // Group by the field movieId\ min_rating: {$min: "$rating"}, // Get the min rating for each group\ max_rating: {$max: "$rating"}, // Get the max rating for each group\ count: {$sum: 1} // Get the count for each group\ }\ },\ // Sort in descending order of count, break ties by ascending order of _id\ {$sort: {count: -1, _id: 1}},\ // Limit to only the first 10 documents\ {$limit: 10},\ // Perform a "lookup" on a different collection\ {\ $lookup: {\ from: "movies_metadata", // Search inside movies_metadata\ localField: "_id", // match our _id\ foreignField: "movieId", // with the "movieId" in movies_metadata\ as: "movies" // Put matching rows into the field "movies"\ }\ }\ ]);\ \ Normally this is where we would put the expected output, but if you tried it out yourself you should know it looks like a complete mess! It may help to look at a single formatted document here. Try running `python3 test.py q0 --format`, which should give a cleaned up version of the first document returned by the query:\ \ Copy\ \ {\ "_id" : 480,\ "min_rating" : 2,\ "max_rating" : 5,\ "count" : 48,\ "movies": [ // Notice that "movies" is an array!\ {\ "title": "Some Movie",\ "budget": 123456789,\ // Full contents of a document from\ // movies_metadata\ }\ ]\ \ There are two things to note here:\ \ * The "movies" field corresponds to an _array_ of matching documents, not a single document. If there were multiple documents in `movies_metadata` with a matching id, they would all appear in that list. If there were no matching documents, `movie` would map to an empty list.\ \ * The contents of `movie` are _entire documents._ In SQL this would be like having an entire record stored in a single column! As the name NoSQL implies though, we're not bound to the rule of SQL that all values must be atomic, and so we're allowed to have this nested structure.\ \ \ #### \ \ [](https://cs186.gitbook.io/project/assignments/proj6/your-tasks#project)\ \ Project\ \ The result of the last query was a bit messy, so lets do some cleaning up. We'll create a new field, `name` , to store the name of the movie, rename `count` and get rid of the column field `_id`.\ \ Copy\ \ db.ratings.aggregate([\ // Match documents with certain timestamps\ {$match: {timestamp: { $gte: 838857600, $lt: 849398400}}},\ // Perform an aggregation\ {\ $group: {\ _id: "$movieId", // Group by the field movieId\ min_rating: {$min: "$rating"}, // Get the min rating for each group\ max_rating: {$max: "$rating"}, // Get the max rating for each group\ count: {$sum: 1} // Get the count for each group\ }\ },\ // Sort in descending order of count, break ties by ascending order of _id\ {$sort: {count: -1, _id: 1}},\ // Limit to only the first 10 documents\ {$limit: 10},\ // Perform a "lookup" on a different collection\ {\ $lookup: {\ from: "movies_metadata", // Search inside movies_metadata\ localField: "_id", // match our _id\ foreignField: "movieId", // with the "movieId" in movies_metadata\ as: "movies" // Put matching rows into the field "movies"\ }\ },\ {\ $project: {\ _id: 0, // explicitly project out this field\ title: {$first: "$movies.title"}, // grab the title of first movie\ num_ratings: "$count", // rename count to num_ratings\ max_rating: 1,\ min_rating: 1\ }\ }\ ]);\ \ After pasting in the new query into `query/q0.js` and running `test.py q0 --view` :\ \ Copy\ \ -- Note that the closest equivalent to $lookup is a LEFT OUTER JOIN, not an\ -- INNER JOIN!\ SELECT\ MAX(rating) as max_rating,\ MIN(rating) as min_rating,\ m.title as title,\ COUNT(*) as num_ratings\ FROM ratings as r LEFT OUTER JOIN movies_metadata as m ON r.movieId = m.id\ WHERE timestamp >= 838857600 AND timestamp < 849398400\ GROUP BY r.movieId\ ORDER BY num_ratings DESC, r._id ASC\ LIMIT 10;\ \ A few things to note here:\ \ * The 0's and 1's stand for "drop" and "keep" respectively, i.e. "\_id" gets dropped because its corresponding value in the project was 0.\ \ * To get the title of the first movie in the "movies" array we used `{$first: "$movies.title"}`. We used `.title` to access the `title` attribute of each document in `movies`. Try running the query without the `$first` operator (`"title": "$movies.title"`) and see what happens.\ \ * You can rename columns using a project.\ \ \ You should now see some output that looks like this:\ \ Copy\ \ { "min_rating" : 2, "max_rating" : 5, "title" : "Jurassic Park", "num_ratings" : 48 }\ { "min_rating" : 1, "max_rating" : 5, "title" : "Forrest Gump", "num_ratings" : 47 }\ { "min_rating" : 3, "max_rating" : 5, "title" : "Dances with Wolves", "num_ratings" : 45 }\ { "min_rating" : 3, "max_rating" : 5, "title" : "The Fugitive", "num_ratings" : 44 }\ { "min_rating" : 2, "max_rating" : 5, "title" : "Batman", "num_ratings" : 42 }\ { "min_rating" : 1, "max_rating" : 5, "title" : "Pulp Fiction", "num_ratings" : 42 }\ { "min_rating" : 2, "max_rating" : 5, "title" : "Apollo 13", "num_ratings" : 41 }\ { "min_rating" : 2, "max_rating" : 5, "title" : "True Lies", "num_ratings" : 39 }\ { "min_rating" : 1, "max_rating" : 5, "title" : "Terminator 2: Judgment Day", "num_ratings" : 37 }\ { "min_rating" : 2, "max_rating" : 5, "title" : "Pretty Woman", "num_ratings" : 35 }\ \ Congrats, you've built your first query! You can run `python3 test.py q0` to test that the provided solution works. This section may seem a bit intimidating, but its mostly there for you to reference back to as you work through the remaining tasks.\ \ [](https://cs186.gitbook.io/project/assignments/proj6/your-tasks#your-tasks)\ \ Your Tasks\ \ \ --------------------------------------------------------------------------------------------\ \ Note on grading: question 0 and the questions in Task 1 are worth 1 point each, while the questions in Tasks 2 and 3 are worth 2 points each.\ \ Based on student feedback from previous semesters, we estimate that this project will take approximately 10-15 hours to complete. We have also included a star-based difficulty ranking per task, relative to the rest of the project, as a guide for pacing your work.\ \ _Please note that every student works at a different pace, and it's absolutely ok to spend more or less time on the project than the provided estimates!_\ \ ### \ \ [](https://cs186.gitbook.io/project/assignments/proj6/your-tasks#task-1-basics)\ \ Task 1: Basics\ \ _Difficulty: ★★☆☆☆_\ \ **i.** After spending over a year social distancing, you find yourself reading a lot of marvel comics and watching a lot of Disney movies. Find the IDs of all movies labeled with the keyword "mickey mouse" **or** "marvel comic" by writing a query on the `keywords` collection. Order your output in ascending order of `movieId`. The output documents should have the following fields:\ \ Copy\ \ {"movieId": }\ \ * Hint: start by trying to find movieIds labeled with just "mickey mouse", then use the [$or](https://docs.mongodb.com/manual/reference/operator/aggregation/or/)\ operator to match documents with either of the labels.\ \ * Hint: you may find the [$elemMatch](https://docs.mongodb.com/manual/reference/operator/query/elemMatch/)\ operator useful here to select the appropriate documents. For example, the following query would match any movie with English listed as one of its spoken languages:\ \ \ Copy\ \ db.movies_metadata.aggregate([\ // Use elemMatch in the $match stage to find movies with English\ // as a spoken language\ {$match: {spoken_languages: {$elemMatch: {name: "English"}}}},\ {$project: {title: 1, _id: 0}} // clean up output\ ])\ \ **ii.** We're interested in the best comedy films to watch. Return the id, title, average vote, and vote count of the top 50 comedy movies ordered from highest to lowest by average vote, breaking ties by descending order of vote count, and any further ties in ascending order of `movieId`. Only include movies with 50 or more votes. The output documents should have the following fields:\ \ Copy\ \ {\ "title" : ,\ "vote_average" : ,\ "vote_count" : ,\ "movieId" : \ }\ \ * Useful operators: [$elemMatch](https://docs.mongodb.com/manual/reference/operator/query/elemMatch/)\ , [$gte](https://docs.mongodb.com/manual/reference/operator/aggregation/gte/)\ for matching\ \ * Hint: genre names are case sensitive!\ \ \ **iii.** Do movies get more good reviews than bad reviews? Is it the other way around? We want to know! For each possible rating find how many times that rating was given. Include the rating and the number of the times the rating was given and output in descending order of the rating. The output documents should have the following fields:\ \ Copy\ \ {\ "count": ,\ "rating": \ }\ \ * Hint: the building your first query section gives an example of how to get a count\ \ \ **iv.** You've discovered a critic who always seems to know exactly which movies you would love and which ones you would hate. Their true name is a mystery, but you know their user id: `186`. Find critic 186's five most recent movie reviews, and create create a document with the following fields:\ \ Copy\ \ {\ "movieIds": [most recent movieId, 2nd most recent, ... , 5th most recent],\ "ratings": [most recent rating, 2nd most recent, ..., 5th most recent],\ "timestamps": [most recent timestamp, 2nd most recent, ... , 5th most recent]\ }\ \ * Useful operators: Look into the [$push](https://docs.mongodb.com/manual/reference/operator/aggregation/push/)\ operator\ \ * Hint: You may find it helpful to see what happens when you [group by null](https://docs.mongodb.com/manual/reference/operator/aggregation/group/#group-by-null)\ .\ \ \ ### \ \ [](https://cs186.gitbook.io/project/assignments/proj6/your-tasks#task-2-movie-night)\ \ Task 2: Movie Night\ \ _Difficulty: ★★★★☆_\ \ **i.** The TAs are having a movie night but they're having trouble choosing a movie! Luckily, Joe has read about IMDb's Weighted Rating which assigns movies a score based on demographic filtering. The weighted ranking (WR\\textrm{WR}WR) is calculated as follows:\ \ WR\=(vv+m)R+(mv+m)C\\textrm{WR} = (\\frac{v}{v+m})R + (\\frac{m}{v+m})CWR\=(v+mv​)R+(v+mm​)C\ \ * vvv is the number of votes for the movie\ \ * mmm is the minimum votes required to be listed in the chart\ \ * RRR is the average rating of the movie (this is stored in the field `vote_average`)\ \ * CCC is the mean vote across the whole report. For the purposes of this question this value is approximately 7, which you can hardcode into your query.\ \ \ We would like to set a minimum number of votes to make sure the score is accurate. For this question we will assume the minimum votes required to be listed is 1838. Return the 20 highest rated movies according to this formula. The output should contain three fields: `title` with the title of the movie, `vote_count` with the number of votes the movie received, and `score` which contains the WR for the associated movie rounded to two decimal places. How many movies can you recognize on this list? Sort in descending order of `score`, and break ties in descending order of `vote_count` and ascending order of `title`. Your output documents should have the following fields:\ \ Copy\ \ {\ "title": ,\ "vote_count": ,\ "score": \ }\ \ * Useful operators: Look up what the [`$add`](https://docs.mongodb.com/manual/reference/operator/aggregation/add/)\ , [`$multiply`](https://docs.mongodb.com/manual/reference/operator/aggregation/multiply/)\ , [`$divide`](https://docs.mongodb.com/manual/reference/operator/aggregation/divide/)\ , and [`$round`](https://docs.mongodb.com/manual/reference/operator/aggregation/round/)\ operators do (you may find this question reminiscent of Scheme from 61a!)\ \ \ **ii.** The TAs consider the prospect of making their own feature film on the beauty and joy of databases, and want to think of a catchy tagline. Run the following to see some examples taglines:\ \ `db.movies_metadata.aggregate({$project: {"_id": 0, "tagline": 1}})`\ \ Notice how the second one is "Roll the dice and unleash the excitement!" We want to see the 20 most common words (length > 3) across all taglines in descending order. In order to do this, we would need to split our sample tagline into its constituent words ("Roll", "the", "dice", "and", "unleash", "the", "excitement!").\ \ To make things interesting, we will limit the words to length >3 to remove filler words, prepositions, and some pronouns (in the previous example, remove "the" and "and"). We also want to trim off any surrounding punctuation (periods, commas, question marks, or exclamation points) in a word and set all words to lowercase (our final set of words that will be included in our table for our example tagline is "roll, "dice", "unleash", "excitement", without the exclamation mark). Order your output by descending order of `count`. Your output documents should have the following fields:\ \ Copy\ \ {\ "_id": ,\ "count": \ }\ \ Can you guess what the most popular words might be?\ \ * Hint: Look up the [`$unwind`](https://docs.mongodb.com/manual/reference/operator/aggregation/unwind/)\ stage to see what it does.\ \ * Useful operators:\ \ * [$split](https://docs.mongodb.com/manual/reference/operator/aggregation/split/)\ can be used to convert a string to an array. For example splitting the string "a proper copper coffee pot" by " " (a space) will create the array \["a", "proper", "copper", "coffee", "pot"\]\ \ * [$toLower](https://docs.mongodb.com/manual/reference/operator/aggregation/toLower/)\ converts a string to lowercase\ \ * [$trim](https://docs.mongodb.com/manual/reference/operator/aggregation/trim/)\ can be used to trim off surrounding punctuation marks\ \ * [$strLenCP](https://docs.mongodb.com/manual/reference/operator/aggregation/strLenCP/)\ can be used to get the length of a string. Make sure to check for length _after_ removing punctuation marks!\ \ \ \ **iii.** How much does it cost to make a movie? The TAs were hoping to write a query for this but realized something that will haunt them for the rest of their lives... Mongo's lack of schema requirements means that the budget field of documents metadata isn't always an integer! Even worse, sometimes the field doesn't even exist! It looks like whoever prepared the data set always did one of the following:\ \ * If they didn't know the budget of a given movie they did one of the following:\ \ * Set the `budget` field to `false`\ \ * Set the `budget` field to `null`\ \ * Set the `budget` field to an empty string: `""`\ \ * Excluded the `budget` field from the document\ \ \ * If they did know the budget of a given movie they did the following:\ \ * Set the `budget` field to a number value, for example `186`\ \ * Set the `budget` field to a string with prefix `$`, for example `"$186"`\ \ * Set the `budget` field to a string with the the postfix "[USD](https://en.wikipedia.org/wiki/USD)\ ", for example `"186 USD"`\ \ \ \ Group the budgets by their value rounded to the nearest multiple of ten million, and return the count for each rounded value. Additionally include an extra group `"unknown"` for the count of movies where the budget was not known. Order by ascending order of rounded budget. Your output documents should have the following fields:\ \ Copy\ \ {\ "budget": ,\ "count": \ }\ \ * Useful operators: You may find the following useful: [$ne](https://docs.mongodb.com/manual/reference/operator/aggregation/ne/)\ , [$and](https://docs.mongodb.com/manual/reference/operator/aggregation/and/)\ , [$cond](https://docs.mongodb.com/manual/reference/operator/aggregation/cond/)\ , [$isNumber](https://docs.mongodb.com/manual/reference/operator/aggregation/isNumber/)\ , [$toInt](https://docs.mongodb.com/manual/reference/operator/aggregation/toInt/)\ and [$round](https://docs.mongodb.com/manual/reference/operator/aggregation/round/)\ . Trim will also be useful here for removing prefixes and postfixes.\ \ * Hint: You can check if a field is present in a document by checking whether the field is equal to `undefined`\ \ \ ### \ \ [](https://cs186.gitbook.io/project/assignments/proj6/your-tasks#task-3-paparazzi)\ \ Task 3: Paparazzi\ \ _Difficulty: ★★★☆☆_\ \ **i.** Comic book writer [Stan Lee](https://en.wikipedia.org/wiki/Stan_Lee)\ was known to make cameos in film adaptations of his works. Find the release date, title, and the name of the character Lee played for every movie Lee has appeared in. Order the results in descending order of release date. Your output documents should have the following fields:\ \ Copy\ \ {\ "title": ,\ "release_date": ,\ "character": \ }\ \ * Useful operators: you may find [$unwind](https://docs.mongodb.com/manual/reference/operator/aggregation/unwind/)\ (used in 2ii) handy here\ \ * Hint: Stan Lee's id in the credits collection is `7624`.\ \ \ **ii.** Director [Wes Anderson](https://en.wikipedia.org/wiki/Wes_Anderson)\ is known for his unique visual and narrative style, and frequently collaborates with certain actors. Find the 5 actors who have appeared the most often in movies where Anderson is listed on the crew with the title "Director". Your output should include the actor's name, id, and the number of times the actor has collaborated with Anderson. Order in descending order of the number of collaborations. Break ties in ascending order of the actor's id. Your output documents should have the following fields:\ \ Copy\ \ {\ "count": , // number of times collaborated\ "id": ,\ "name": \ }\ \ * Hint: Wes Anderson's id in the credits collection is `5655`. To get started, try to match all documents in `credits` where he is listed as the director.\ \ * Hint: Like the above question, [$unwind](https://docs.mongodb.com/manual/reference/operator/aggregation/unwind/)\ can be useful here.\ \ * Hint: You may need to group by multiple fields for this question. For example, `{$group: _id: {val1: "$field.val1", val2: "$field.val2"}}` will group documents by both val1 and val2, similar to how the expression `GROUP BY val1, val2` would in SQL.\ \ \ [](https://cs186.gitbook.io/project/assignments/proj6/your-tasks#youre-done)\ \ You're done!\ \ \ ----------------------------------------------------------------------------------------------\ \ Congrats, you're finished with the last project! There are **no hidden tests** for this assignment, so whatever score you see on the autograder after this will be your score on this assignment. Follow the instructions in the [next section](https://cs186.gitbook.io/project/assignments/proj6/submitting-the-assignment)\ to submit your work.\ \ [](https://cs186.gitbook.io/project/assignments/proj6/your-tasks#testing-tips)\ \ Testing Tips\ \ \ ------------------------------------------------------------------------------------------------\ \ ### \ \ [](https://cs186.gitbook.io/project/assignments/proj6/your-tasks#running-queries)\ \ Running Queries\ \ You can run your answers through mongo directly by running `mongo movies` to open the database and then entering your query directly:\ \ Copy\ \ $ mongo movies\ db.replace_with_a_collection.aggregate([ ... your query ... ])\ \ This can help you catch any syntax errors in your queries. Alternatively you can run a query directly through the testing script by pasting in your query into the appropriate file (we'll use `query/q0.js` as an example) and running `python3 test.py q0 --view`. This will print up to ten of the query's results.\ \ You can request more results with the `--batch_size` flag (i.e. `python3 test.py q0 --view --batch_size 20` will give the first twenty results).\ \ ### \ \ [](https://cs186.gitbook.io/project/assignments/proj6/your-tasks#formatting-output)\ \ Formatting output\ \ If you find yourself dealing with large, hard to read documents, you can view a formatted version of the first document by using `--format` instead of `--view`. For example, using the provided query from the [Building your first query](https://cs186.gitbook.io/project/assignments/proj6/your-tasks#building-your-first-query)\ section of the spec:\ \ Copy\ \ $ python3 test.py q0 --format\ Showing formatted first document of the query\ {\ "min_rating": 2,\ "max_rating": 5,\ "title": "Jurassic Park",\ "num_ratings": 48\ }\ \ To run a test, from within the `sp25-proj6-yourname` directory:\ \ Copy\ \ $ python3 test.py # This runs all of the tests\ $ python3 test.py 3ii # This would run tests for only q3ii\ \ ### \ \ [](https://cs186.gitbook.io/project/assignments/proj6/your-tasks#format-matching)\ \ Format Matching\ \ Before we run a full test on your output, we check that the format of your output matches what we're expecting. Format in this context means that all the field names we expect are there, there are no extra field names, and that the types corresponding to the field names match. Here's an example of some mismatched format for `diffs/q2i.diff`\ \ Copy\ \ EXTRA FIELDS\ - foo\ \ MISMATCHED TYPES\ - mismatch on field `movieId`:\ - expected type: `number` (example: `63`)\ - actual type: `null`, (example: `null`)\ \ FORMAT MISMATCH\ - Example of expected document:\ {\ "movieId": 63\ }\ \ - Your document:\ {\ "foo": "bar",\ "movieId": null\ }\ \ The above output tells you two things:\ \ * One of your documents had an extra field. In this case, looking at the "Your document" section, your output had an extra field called "foo"\ \ * One of your documents has a mismatched type for one of its fields. In this case, look at the "Your document" section, your output had a value of type null for the field "movieId", when it should have been a number.\ \ \ ### \ \ [](https://cs186.gitbook.io/project/assignments/proj6/your-tasks#diffs)\ \ Diffs\ \ If you pass the format check, we'll run a diff against your query and the expected output. Become familiar with the UNIX [diff](http://en.wikipedia.org/wiki/Diff)\ format, if you're not already, because our tests saves a simplified diff for any query executions that don't match in `diffs/`. As an example, the following output for `diffs/q2ii.diff:`:\ \ Copy\ \ + {"_id": "only", "count": 521}\ {"_id": "just", "count": 481}\ - {"_id": "about", "count": 535}\ \ This indicates that:\ \ * your output has an extra document `{"_id": "about", "count": 535}` (the `-` at the beginning means the expected output _doesn't_ include this line but your output has it)\ \ * your output is missing the document `{"_id": "only", "count": 521}` (the plus at the beginning means the expected output _does_ include those lines but your output is missing it).\ \ * If there is neither a `+` nor `-` at the beginning then it means that the line is in both your output and the expected output (your output is correct for that line).\ \ \ If you care to look at the query outputs directly, ours are located in the `expected_output` directory. Your output should be located in your solution's `your_output` directory once you run the tests.\ \ ### \ \ [](https://cs186.gitbook.io/project/assignments/proj6/your-tasks#reformatting)\ \ Reformatting\ \ When we generate the diffs we'll be doing some basic reformatting to reorder things that don't have an inherent order to make sure that the results are consistent with each other. These include:\ \ * field names will be rearranged to be in alphabetical order\ \ * arrays when we don't ask for an explicit order to them\ \ \ [PreviousGetting Started](https://cs186.gitbook.io/project/assignments/proj6/getting-started)\ [NextSubmitting the Assignment](https://cs186.gitbook.io/project/assignments/proj6/submitting-the-assignment)\ \ Last updated 7 months ago --- # Adding a partner on GitHub | CS186 Projects If you want to share your code over GitHub with your project partner you'll need to pick between the two of you whose copy of the starter code you want to work off of. For example, if users `OskiBear` and `JoeBruin` want to collaborate then they might both choose to work off of `sp25-proj2-OskiBear`. In that case `OskiBear` would navigate to "Settings", "Manage access", then "Invite teams or people" and add `JoeBruin`(see images below). `JoeBruin` should receive an email afterwards containing an invitation to the repo. Alternatively `OskiBear` can share the link to the repo after sending the invitation. Once you both have access to the repo you your partner can clone the repo to get a local copy to work off of. From there you can share files over git, pushing and pulling updates as you collaborate. **Do not add anyone other than your project partner to your repository.** You aren't allowed to share code with any students other than your project partner for this project. ![](https://cs186.gitbook.io/project/~gitbook/image?url=https%3A%2F%2F678656433-files.gitbook.io%2F%7E%2Ffiles%2Fv0%2Fb%2Fgitbook-legacy-files%2Fo%2Fassets%252F-MFVQnrLlCBowpNWJo1E%252Fsync%252F90a0829c6f56c5592579fee8b4063c14d2db6337.png%3Fgeneration%3D1599798456341006%26alt%3Dmedia&width=768&dpr=4&quality=100&sign=80802878&sv=2) Navigate to your sp25-proj2-yourname repo's Settings ![](https://cs186.gitbook.io/project/~gitbook/image?url=https%3A%2F%2F678656433-files.gitbook.io%2F%7E%2Ffiles%2Fv0%2Fb%2Fgitbook-legacy-files%2Fo%2Fassets%252F-MFVQnrLlCBowpNWJo1E%252Fsync%252Ff49406365c81af88df42b4b459b8cd499346cd46.png%3Fgeneration%3D1599798455242759%26alt%3Dmedia&width=768&dpr=4&quality=100&sign=f7a3c389&sv=2) Go to Manage Access ![](https://cs186.gitbook.io/project/~gitbook/image?url=https%3A%2F%2F678656433-files.gitbook.io%2F%7E%2Ffiles%2Fv0%2Fb%2Fgitbook-legacy-files%2Fo%2Fassets%252F-MFVQnrLlCBowpNWJo1E%252Fsync%252Fd68ce49b36795993677b8be6a3570f455a8d3bfc.png%3Fgeneration%3D1599798457430817%26alt%3Dmedia&width=768&dpr=4&quality=100&sign=4536f86&sv=2) ![](https://cs186.gitbook.io/project/~gitbook/image?url=https%3A%2F%2F678656433-files.gitbook.io%2F%7E%2Ffiles%2Fv0%2Fb%2Fgitbook-legacy-files%2Fo%2Fassets%252F-MFVQnrLlCBowpNWJo1E%252Fsync%252Fc2184addfe151556bc93d7d71d4aa407610aef70.png%3Fgeneration%3D1599798454394042%26alt%3Dmedia&width=768&dpr=4&quality=100&sign=22549726&sv=2) Invite your partner (replace JoeBruin with your partner's GitHub username) After following these steps your partner should receive an email containing an invitation link. Alternatively, you can share the link to the repo with your partner. [PreviousSubmitting the Assignment](https://cs186.gitbook.io/project/assignments/proj6/submitting-the-assignment) [NextDevelopment Container Setup](https://cs186.gitbook.io/project/common/devcontainer-setup) Last updated 10 months ago ---