Part I due by 11:59 p.m. on Tuesday, October 21, 2025.
Part II due by 11:59 p.m. on Tuesday, October 28, 2025.
In your work on this assignment, make sure to abide by the collaboration policies of the course.
If you have questions, please come to office hours, post them on
Piazza, or email cs460-staff@cs.bu.edu.
Make sure to submit your work on Gradescope, following the procedures found at the end of Part I and Part II.
50 points total
Create a subfolder called ps3 within your
cs460 folder, and put all of the files for this assignment in that
folder.
0 points
In the next problem and in Problem 3 from Part II, you will implement portions of a simple relational database management system that supports a subset of the SQL language. We have provided you with two of the three components of the system:
Your job is to implement parts of the “middle layer” of the system, which takes the parsed version of a SQL command and performs the necessary lower-level actions to execute the command. To help you, we have given you a code framework for the middle layer that already provides some of the necessary functionality.
You should begin by downloading the necessary files and configuring your work environment. The steps for doing so can be found here.
Please do this ASAP, so that you can be sure that you don’t run into any problems later on.
After configuring everything, you should spend some time
familiarizing yourself with the files that we have given you in the
dbms folder, and with Berkeley DB. In particular, you should
review/read the following resources:
The following additional resources may also be helpful:
highly recommended
Before you begin coding, we strongly encourage you to answer the questions found here:
code-reading and design questions
In the code that you write, you must limit yourself to the packages that we’ve imported at the top of the starter files. You must not use classes from any other Java package. In addition, you must not use any Java features that were not present in Java 8.
As discussed on the separate configuration page, you will need to compile and run the code from the command line in the Terminal window of VS Code.
to compile:
javac -cp 'lib/*' -d classes *.java
(see below for the expected warning messages)
to run on Windows:
java -cp 'lib/*;classes' DBMS
to run on macOS:
java -cp 'lib/*:classes' DBMS
Note: The two commands for running the program are almost
identical, but in the Windows version there is a semi-colon (;)
before the word classes, whereas the macOS version uses a
colon (:).
You will see one or more warnings when compiling your code (e.g., “Note: Parser.java uses unchecked or unsafe operations.”). These warnings are to be expected and should be ignored. Messages labeled as errors (not warnings) will keep your code from compiling and will need to be addressed. You shouldn’t see any errors when you compile the starter code that we’ve given you. If you do, let us know.
After making changes to the code, you will need to recompile it before you can try to re-run it. When you are at the command line of the Terminal, using the up arrow will allow you to access and reenter previously entered commands without needing to re-type them!
The code that we’ve given you can be run before you make any changes. It will begin by printing the following prompt:
Enter command (q to quit):
If you enter a valid SQL command, the program will parse the command
and display a summary of some of the command’s components (see the
notes on the DEBUG constant below for how to disable this summary).
Entering a lower-case q will allow you to quit the program.
When you run the program for the first time, it will create a
directory called db within your code directory. This is the home
directory for the Berkeley DB environment, and it will be used to
store the files that BDB creates for your database. If your program
crashes for any reason, these files may be corrupted. As a result,
we recommend that you remove all files from this directory after
a crash.
There is a constant named DEBUG that is defined in DBMS.java. When
it is set to true (as it is in the file that we have given you),
the values of many of the tokens generated by the parser are printed
after each SQL command is entered by the user. You may find this
information helpful as you implement the various types of commands.
You may also wish to add additional debugging code that is only
executed when this constant is set to true. To eliminate the
debugging messages, set DEBUG to false.
20 points; pair-optional
This is the only problem in Part I that you may complete with a partner. See the rules for working with a partner on pair-optional problems for details about how this type of collaboration must be structured.
Important
Before you begin coding, make sure that you have completed Problem 0, including performing the tasks listed under the Getting Started section and answering the code-reading questions.
In order to insert rows into a table, your DBMS needs to be able to
marshall a collection of column values into a single Berkeley DB
key/value pair. In this problem, you will add support for marshalling
by implementing the key method of the InsertRow class.
As you saw when completing the code-reading
questions, an InsertRow object is used by
the execute() method for INSERT commands (the one in the
InsertStatement class). That execute() method creates an
InsertRow object to represent the row to be inserted, and it calls
that object’s marshall() method to prepare the marshalled
key/value pair for the row.
We have already implemented some of the other methods of this class for you:
InsertRow constructor that initializes the state of object.
It takes two parameters: an already opened Table object for
the table to which the row will be added, and an array of type
Object containing the values in the row to be inserted. We
assume that the values are in the appropriate order – i.e.,
that element 0 of the array contains a value for the first
column in the table, element 1 contains a value for for the
second column in the table, etc. We also assume that the values
are valid and that they have been adjusted as needed to
correspond to the types of the columns.getKeyBuffer() method that returns a RowOutput object for
the key portion of the marshalled key/value pair.getValueBuffer() method that returns a RowOutput object for
the value portion of the marshalled key/value pair.toString() method that returns a String representation
that includes:offsets field, which is an
array in which your code will store the field offsets that
you compute at the beginning of marshalling (see below)RowOutput for the key)RowOutput for the value).
This toString() method should help you when debugging your
marshalling code.You will implement the marshall() method, which should take the
column values of the InsertRow object and marshall them into byte arrays
for the key/value pair that will eventually be inserted into the
B+tree for the table.
Important: marshall() should not interact with Berkeley DB at
all. In particular, it should not create any DatabaseEntry
objects or attempt to add them to the BDB database.
Rather, marshall() should only do the following:
Determine the correct offset values and store them in the
array to which the offsets field in the InsertRow object refers.
Write the appropriate values into the buffers represented by
the keyBuffer and valueBuffer fields, each of which refers to
a RowOutput object.
See below for more detail about each of these tasks.
Notes:
Each key/value pair should have the format that we discussed in the lecture notes on the logical-to-physical mapping. The key portion of the key/value pair should be based on the value of the primary-key column. The value portion should consist of a header of offsets followed by the values of the non-primary-key, non-null columns.
The key portion of the key/value pair will be stored in the
RowOutput object assigned to the keyBuffer field of the
InsertRow object. The value portion will be stored in the
RowOutput object assigned to the valueBuffer field.
Because RowOutput objects fill their associated byte
arrays from left to right, you will need to determine all of
the offsets that belong in the header before you begin marshalling the
column values themselves. Store these offsets in the array to
which the InsertRow object’s offsets field refers.
Once all of the offsets have been computed and stored in
the offsets array, you can begin the process of writing into the
RowOutput objects using the appropriate methods.
The InsertRow constructor takes a reference to the
corresponding Table object as a parameter, and it stores that
reference in a field called table. Your code can obtain any
column information that it needs from the Table object and its
associated Column objects.
The getLength() method in a Column object gives the actual
length in bytes of all columns except VARCHARs. In the case of
VARCHARs, you should determine the length by invoking the
String.length() method on the actual value.
Because the column values are stored in an array of type Object,
you will need to use type casts in order to treat them as objects
of their actual types. For example, to treat values[i] as a
String, you would need to do something like (String)values[i].
Consult the Column class for the method you should use to determine
the type of a given column.
Integer values are stored in the values array as objects of
Java’s Integer class, and real values are stored as objects of
Java’s Double class. When marshalling these values, you will
need to convert them to primitive values of type int and
double, and you should use the Integer.intValue() and
Double.doubleValue() methods to do so. For example, if you have
an Integer object named val, you can convert it to an int by
making the method call val.intValue().
The RowOutput methods that you will use for writing the offsets
and column values are inherited from the DataOutputStream class,
so you should make sure to review the
API
of that class.
When marshalling a String value, you should use
the writeBytes() method, not the writeUTF() method.
You should assume that all offset values are small enough to be
represented by a two-byte integer, and thus you should use the
writeShort() method for them.
To keep the marshall() method from getting too large, you may
want to add one or more private helper methods that can be called
to do part of the overall task.
Important: If you write a helper method that uses one or
more of the RowOutput methods, you must include a throws
clause in the header of the method like the one we’ve given you
for the marshall method:
public void marshall() throws IOException {
Review the Table, Column, RowOutput, and
DataOutputStream classes as needed.
marshall() methodYou should test your marshall() method thoroughly.
We’ve given you the following tools for doing so:
The RowOutput class includes a toString() method that
shows the current contents of the underlying byte array.
The InsertRow class includes its own toString() method that shows
the current values in the InsertRow object’s offsets array and
the contents of the byte arrays underlying the RowOutput objects
assigned to its keyBuffer and valueBuffer fields.
The code that we’ve given you in the execute() method of
InsertStatement will create the necessary InsertRow object,
call your marshall() method, and – if the DEBUG constant in
the DBMS class is true – print the InsertRow object so that
you can examine the values of its fields.
Given these tools, you can:
Compile and run the DBMS program as described above.
Create a table using a CREATE TABLE command. The starter code
already includes everything needed to carry out this type of command.
Enter one or more INSERT commands for the newly created table, and
see if the output from printing the InsertRow object looks correct.
For example, let’s say that you enter these two SQL commands:
CREATE TABLE Movie(id CHAR(7) PRIMARY KEY, name VARCHAR(64), runtime INT);
INSERT INTO Movie VALUES ('2294629', 'Frozen', 102);
If your marshall() command is working correctly, you should see the
following as part of the output of the debugging print statement:
for the offsets field:
[-2, 8, 14, 18]
Because there are three columns, there are four offsets. The -2
indicates that the first column (id) is the primary key.
The next two offsets (8 and 14) are the offets of the name
and runtime column values, and the 18 is the offset
of the end of the record.
for the key buffer (i.e., the keyBuffer field):
[50, 50, 57, 52, 54, 50, 57]
The numbers in this byte array represent the ASCII codes for
the characters in the id value '2294629': 50 for the
character '2', 57 for the character '9', etc.
for the value buffer (i.e., the valueBuffer field):
[-1, -2, 0, 8, 0, 14, 0, 18, 70, 114, 111, 122, 101, 110, 0, 0, 0, 102]
This byte array begins with 8 bytes for the offset table:
The first two bytes ([-1, -2]) represent the special -2
offset for the primary-key column. When -2 is represented
using a two-byte integer, the individual bytes
end up being the 8-bit representations of -1 and -2.
In general, when you use multiple bytes to store a
negative number whose absolute value is relatively small,
the rightmost byte will show the negative number itself,
and all of the remaining bytes will show -1. For example,
if we stored -3 using two bytes, we would see [-1, -3] as
its two bytes. If we stored -10 using four bytes, we
would see [-1, -1, -1, -10].
The next two bytes ([0, 8]) represent the offset of the
name column, which has an offset of 8 bytes because it
comes immediately after the offset table, which has a
length of 4*2 = 8 bytes.
The next two bytes ([0, 14]) represent the offset of the
runtime column, which has an offset of 8 + 6 = 14 bytes
in this particular row.
The next two bytes ([0, 18]) represent the offset of the
end of the record, which is 14 + 4 = 18 in this particular
row.
The next 6 bytes represent the ASCII codes for 'Frozen':
70 for 'F', 114 for 'r', etc.
The final 4 bytes ([0, 0, 0, 102]) represent the 4-byte
integer stored for the runtime value of 102.
Note: When you store larger integers, the resulting bytes can be harder to interpret. Here are some examples:
If you stored a runtime of 150 in the Movie table that we
created above, you would see the bytes [0, 0, 0, -106] for
the runtime. This stems from the fact that when only one byte
is used to store a signed integer (one that could be
negative), it can store any value between -128 and 127. When
we store 150 using two or more bytes, the 8 bits in the
rightmost byte look like they represent a negative number,
because 150 can’t actually be represented using an 8-bit signed
integer.
If you stored a runtime of 300, you would see the bytes
[0, 0, 1, 44] for the runtime. That’s because we need more
than 8 bits to store 300 as a binary number. In fact, when
we convert 300 to binary, we get a 9-bit number: 100101100.
When these 9 bits are stored as part of a 32-bit integer, we
get:
00000000 00000000 00000001 00101100
The bits in the rightmost byte represent the integer 44, and the bits in the byte to its left represent the integer 1.
Try inserting other rows as well, and convince yourself that your
marshall() method is working in all cases. For example, does it
work correctly when one of the column values is NULL?
30 points total
This problem asks you to construct XPath and XQuery queries for an XML version of our entire movie database. The schema of this XML database is described here.
To allow you to check your work, we’ll make use of a freely available XML DBMS called BaseX. You should begin by following the instructions for installing and using it that are available here.
As outlined in our instructions, you can perform queries by taking the following steps:
Start up the BaseX GUI by double-clicking on the JAR file that you downloaded.
Select the Database->New menu option, click the Browse button,
and use the resulting dialog box to find the imdb.xml
file that you downloaded above.
Click Open to select the file, and click OK to create the database.
To execute a query, enter it in the Editor pane in BaseX, and click the green play button to execute it. (You can also use Ctrl+Enter or Ctrl+Return for this purpose.)
The results (if any) will be displayed in the Result pane.
If you have trouble getting BaseX to work on your machine, see the troubleshooting tips on our BaseX page.
If you’re using a Mac, you should disable smart quotes, because they may lead to errors in BaseX and in our testing. There are instructions for doing so here.
ps3_queries.py is a Python file, so you could use a Python IDE
to edit it, but a regular text editor like TextEdit or Notepad++
would also be fine. However, if you use a text editor, you must
ensure that you save it as a plain-text
file.
Construct the XQuery commands needed to solve the problems given below. Test each command in BaseX to make sure that it works.
Once you have finalized the XQuery command for a given problem, copy
the command into your ps3_queries.py file, putting it between
the triple quotes provided for that query’s variable. We have
included a sample query to show you what the format of your
answers should look like.
Each of the problems must be solved by means of a single query. Unless the problem specifies otherwise, you may use either a standalone XPath expression or an XQuery FLWOR expression.
Unless the problem specifies otherwise, you must limit yourself to features of XQuery that we have discussed in lecture. See our general query-writing guidelines for more details.
The only place that you may use a subquery (i.e., a nested FLWOR
expression) is in the results clause of an outer FLWOR
expression. You should NOT have a nested FLWOR expression in a
for clause or a let clause.
The order of the clauses in each query/subquery must follow the
FLWOR acronym: a for clause (F), followed optionally by a let
clause (L), followed optionally by a where clause (W), followed
optionally by an order by clause (O), followed by a return clause
(R). You should not put the clauses in a different order –
e.g., for, followed by let, followed by another for, etc. BaseX
may allow you to do this, but it is never necessary to do so, and
such a query will often fail to run to completion in the Autograder.
Your queries should only use information provided in the problem itself. In addition, they should work for any XML database that follows the schema that we have specified.
You do not need to worry about indenting and line breaks in the results of your queries.
Make sure to read and follow the guidelines given above.
In Problem Set 1,
you wrote a SQL query to find information about the animated
version of Lilo and Stitch. Write a standalone XPath
expression (not a FLWOR expression) to find only the year
of that version of the movie. Your query should make use of only
two facts: (1) that the movie’s name is Lilo and Stitch, and (2)
that there is an 'N' somewhere in the value of its genre
attribute. The result of the query should be a single year
element. (Note: In our XML version of the database, we’ve
replaced the “&” character in the movie’s name with the word
“and”.)
Hint: You should use the contains function to perform
substring matching, as discussed in lecture.
In Problem Set
1,
you wrote a SQL query to find information about the 2025 Oscar
winners who were born in New York. Write a FLWOR expression to
solve a similar problem. The results of the query should be new
elements of type winner that each include two nested child
elements:
the name child element of a person born in New York
who won an Oscar in 2025
the type child element of the Oscar that the person won.
For example:
<winner> <name>Adrien Brody</name> <type>BEST-ACTOR</type> </winner>
Notes:
Remember that you do not need to worry about indenting or line breaks in the results of your queries.
In 2025, no person who won an Oscar won more than one
award. However, it would theoretically be possible for someone
to win multiple Oscars in the same year. If a person from New
York had won multiple Oscars in 2025, your query should
produce multiple winner elements for them, one for each
award that they won in that year.
Hints:
Here again, you will need to use the contains function to
perform substring matching. You should assume that you are
interested in people with the string “New York” anywhere
in their pob value, even though that is less specific than
the criteria that we used in PS 1.
You will need to use curly braces and commas as part of
your return clause. In lecture, we’ve seen examples of
queries that use these delimiters to transform the elements
selected by a query into new types of elements.
In Problem Set 1,
you wrote a SQL query to find information about each place of
birth (pob) associated with 10 or more people in the database.
Write a FLWOR expression to solve a similar problem. The result
of the query should be new elements of type common_pob that
each have two nested child elements:
pob for the name of the place of birth; see below
for more details about this elementnum_born_there that has as its value
the number of people born in that place of birth.For example:
<common_pob> <pob>Houston, Texas, USA</pob> <num_born_there>14</num_born_there> </common_pob>
Hints:
To ensure that you only consider a given pob once, your query
should use the distinct-values function. For example, to
iterate over distinct Oscar types, you could do the following:
for $t in distinct-values(//oscar/type)
distinct-values gives you the text values of the
corresponding elements, not the elements themselves. As a
result, your return clause will need to construct new pob
elements by adding back in the begin and end tags that were
removed by distinct-values.
You will need to use one of the following built-in aggregate
functions: count(), sum(), avg(), min() and
max(). In lecture, we’ve seen examples of queries that
illustrate how to use this type of function.
Some of the hints for the previous problems also apply here.
In Problem Set
1, you wrote
a SQL query to find information about movies that have more than
one director. Write a FLWOR expression to solve a similar
problem. The result of the query should be new elements of type
multi_director_movie that each include the following nested
child elements:
name child element of the moviedirector,
each of which has as its value the name of one of that movie’s
directors.For example:
<multi_director_movie> <name>No Country for Old Men</name> <director>Ethan Coen</director> <director>Joel Coen</director> </common_pob>
You must sort the results in the following ways:
Sort the multi_director_movie elements in descending order
by the number of directors. If multiple movies have the same
number of directors, sort them in ascending order by the name
of the movie. See the hints below for more about sorting.
Within a given multi_director_movie element, sort the
director child elements in increasing order by name.
Hints:
In XQuery, when you ask it to sort the results, it puts them
in ascending/increasing order by default. To obtain
descending/decreasing order, put the word descending after
the thing that you are sorting on. You can also break ties in
the same way that we did in SQL.
For example, let’s say that our query was assigning person
elements to a variable $p and we wanted to sort the results
in descending order by the person’s dob and break ties by
the person’s name in ascending order. To do so, we would use
the following clause:
order by $p/dob descending, $p/name
You will need to use a subquery (i.e., a nested FLWOR
expression). Remember that these are only allowed in the
return clause of the outer query.
When reformatting the results, you will need to use the
string() function to obtain the values of some elements,
without their begin and end tags.
Some of the hints for the previous problems also apply here.
In Problem Set 2,
you wrote a SQL query to find all movie ratings that are
associated with none of the top-grossing movies. Write a FLWOR
expression to solve a similar problem. The result of the query
should be new elements of type rating_no_top_grossers whose
value is one of the relevant ratings, followed
by a space, followed by the number of top-grossing movies for that
rating – so you can ensure that it does indeed have 0
top-grossing movies! For example:
<rating_no_top_grossers>NC-17 0</rating_no_top_grossers>
Hints:
To ensure that you only consider a given rating once, you
should use the distinct-values function as you did in one
of the earlier problems.
You should take advantage of the fact that our database only
includes an earnings_rank element for a movie if the movie
is a top grosser. Recall that you can check for the presence
of an element or attribute by just including its name in your
predicate as if the name were a boolean expression. For
example, the following XPath expression obtains all person
elements that have “Alice” somewhere in the value of the
name child element and that have a child element of type
dob:
//person[contains(name, "Alice") and dob]
Some of the hints for the previous problems also apply here.
In Problem Set
1, you wrote
a SQL query to find, for each person in the database born in 1960,
the number of Oscars won by that person. Write a FLWOR expression
to solve a similar problem. The results of the query should be new
elements of type born_1960 that include the following nested
child elements:
the name child element of a person born in 1960
a new element of type num_oscars that has as its
value the number of Oscars won by the person; if the person
did not win any Oscars, the value of this element should be 0
for each Oscar won by the person (if any), a new element
of type award that has as its value the year and type of the
Oscar, separated by a space.
For example:
<born_1960> <name>Sean Penn</rating> <num_oscars>2</num_oscars> <award>2004 BEST-ACTOR</award> <award>2009 BEST-ACTOR</award> </born_1960>
Sort the results by the name of the person.
Within a given born_1960 element, sort the
award child elements in increasing order by the year.
Hints:
There are different approaches to obtaining the necessary
people. However, you will need to ensure that a given person
appears at most once in the results. Among other things, this
means that your outer query’s for clause should have only
one XPath expression. In other words, you should not
attempt to use the outer for clause to join person
elements with oscar elements.
Some of the hints for the previous problems also apply here.
Login to Gradescope by clicking the link in the left-hand navigation bar, and click on the box for CS 460.
You should submit only the following two files:
InsertRow.javaps3_queries.pyIMPORTANT: If you worked with a partner on Problem 1, you should each make your own separate submission of your joint work on that problem, along with your individual work on Problem 2.
Here are the steps:
Click on PS 3: Part I in the list of assignments. You should see a pop-up window with a box labeled DRAG & DROP. (If you don’t see it, click the Submit or Resubmit button at the bottom of the page.)
Add your files to the box labeled DRAG & DROP. You can either drag and drop the files from their folder into the box, or you can click on the box itself and browse for the files.
Click the Upload button.
You should see a box saying that your submission was successful.
Click the (x) button to close that box.
The Autograder will perform some tests on your files. Once it is done, check the results to ensure that the tests were passed. If one or more of the tests did not pass, the name of that test will be in red, and there should be a message describing the failure. Based on those messages, make any necessary changes. Feel free to ask a staff member for help.
Notes:
You will not see a complete Autograder score when you submit. That is because additional tests for at least some of the problems will be run later, after the final deadline for the submission has passed. For such problems, it is important to realize that passing all of the initial tests does not necessarily mean that you will ultimately get full credit on the problem. You should always run your own tests to convince yourself that the logic of your solutions is correct.
For Problem 1, you should see some preliminary results. If you’re not seeing any results at all for that problem, it may mean that you’re using features of Java that are not supported by the version of Java that we’re using in the Autograder. In particular, you should NOT:
add any new import statements to the top of your file
use a method from a built-in class if the method was added in a version of Java after version 8. You can determine whether a method is supported by Java 8 by checking if is found in the API docs.
For Problem 2:
You should see test results for each query. If you don’t see any results for a given query, it probably means that one or more of the following is true:
You have a syntax or logic error in your query.
You have a nested FLWOR expression in a for clause
or a let clause. As stated in the guidelines, you are
not allowed to do that on this assignment.
The order of the clauses in your query/subquery do not follow the order specified by the FLWOR acronym. BaseX may allow you to do this, but it is never necessary to do so, and such a query will often fail to run to completion in the Autograder. See the guidelines for more details.
You should keep making changes as needed until you get full credit for a given query. There will be no partial credit awarded for an incorrect query.
Make sure that each query is logically correct, and that it will work for any instance of the movie database that follows the same schema. We reserve the right to ultimately run your queries on a slightly different version of the database to ensure that your queries are logically correct.
If needed, use the Resubmit button at the bottom of the page to resubmit your work. Important: Every time that you make a submission, you should submit all of the files for that Gradescope assignment, even if some of them have not changed since your last submission.
Near the top of the page, click on the box labeled Code. Then click on the name of each file to view its contents. Check to make sure that the files contain the code that you want us to grade.
Important
It is your responsibility to ensure that the correct version of a file is on Gradescope before the final deadline. We will not accept any file after the submission window for a given assignment has closed, so please check your submission carefully using the steps outlined above.
If you are unable to access Gradescope and there is enough
time to do so, wait an hour or two and then try again. If you
are unable to submit and it is close to the deadline, email
your homework before the deadline to
cs460-staff@cs.bu.edu
50 points total
20 points; pair-optional
This is the only problem in Part II that you may complete with a partner. See the rules for working with a partner on pair-optional problems for details about how this type of collaboration must be structured.
In order to execute a SELECT command, your DBMS needs to be able to
iterate over the rows in one or more tables, and to access the values
of the columns in those rows. In this problem, you will complete the
implementation of a table iterator that will be able to iterate over
all or some of the rows in a single table and access the values of the
columns. We can associate a WHERE clause with such an iterator, in
which case it will only visit rows that satisfy the WHERE clause.
Each table iterator will be an instance of the provided TableIterator
class. We have already implemented most of the methods of this class
for you, including:
a TableIterator constructor that takes an already opened table
object and initializes the state needed by the table iterator,
including:
DatabaseEntry objects called key
and value. These DatabaseEntry objects will be used
by the cursor methods to retrieve the current key/value pair.The constructor also examines the columns mentioned in the SQL
statement for which this iterator is needed, and it associates
this iterator with those columns; doing so allows the code that
evaluated the WHERE clause to use the iterator to obtain the
column values that it needs.
a first() method that positions the iterator on the first
tuple of the table.
a next() method that advances the iterator to the next tuple
specified by the SELECT command.
a getColumn() method that takes an index nand returns a
Column object for the nth column in the table associated
with the iterator. The leftmost column has an index of 0.
a close() method that closes the cursor associated with
the iterator.
a printAll() method that will be called to iterate over all rows
in the associated table and print them out.
For this assignment, you should implement the method called
getColumnVal() that takes an index colIndex and returns the value
of the column with that index in the tuple on which the iterator is
currently positioned. To do so, it will need to unmarshall the
appropriate value from the BDB key/value pair associated with that
tuple, and it should use the metadata that you included when you
marshalled the tuple to efficiently access the value of the specified
column. See the notes below for more detail.
Notes:
We have already given you the code needed to handle the two types of exceptions that are mentioned in the comments before the method.
You code that you write should assume that the underlying cursor
has already been positioned on an appropriate key/value pair. The
key can be accessed using the DatabaseEntry object to which the
TableIterator‘s key field refers, and the value can be
accessed using the DatabaseEntry object to which the
TableIterator‘s value field refers.
Your code will need to use one or two RowInput objects to
unmarshall the value of the specified column.
For example, to create a RowInput object that is based on the
value portion of the current key/value pair, you would do something
like the following:
RowInput valIn = new RowInput(this.value.getData());
Your getColumnVal() method should not perform unnecessary
reads. Rather, it should only read (1) the offset or offsets
needed to determine where the column value is located and (when
necessary) the length of the column value, and (2) the column
value itself.
The RowInput class includes two methods for each type of value:
readIntAtOffset() and
readDoubleAtOffset()). These methods jump to the specified
position in the underlying byte array before performing the read.readNextInt() and readNextDouble()).
When the RowInput object is created, the
current offset is set to 0. After each read, the current
offset is updated to be the offset of the byte that comes
immediately after the value that was just read.The RowInput class also includes a toString() method that you
may find useful when debugging. It returns a string that includes
the contents of the underlying byte array and the current offset
within that array.
When unmarshalling the key portion of the key-value pair, you
can use the getSize() method in its DatabaseEntry object
to determine the key’s length in bytes.
Review the Table, Column, and RowInput classes as needed, as
well as the Berkeley DB DatabaseEntry class.
Once you complete Problem 3, you can create a database, add rows to
it, and then perform SELECT * commands involving that table.
The following is a sample interaction with the DBMS. Note: We set
the DEBUG constant to false in DBMS.java before we ran these
commands.
Enter command (q to quit): CREATE TABLE Course(name VARCHAR(20), enrollment INT);
Created table Course.
Enter command (q to quit): SELECT * FROM Course;
| name | enrollment |
---------------------------------------
Selected 0 tuples.
Enter command (q to quit): DROP TABLE Course;
Dropped table Course.
Enter command (q to quit): SELECT * FROM Course;
Course: no such table
Enter command (q to quit): CREATE TABLE Course(id CHAR(5) PRIMARY KEY, name VARCHAR(20));
Created table Course.
Enter command (q to quit): INSERT INTO Course VALUES ('01000', 'CS 460');
Added 1 row to Course.
Enter command (q to quit): INSERT INTO Course VALUES ('00050', 'Math 123');
Added 1 row to Course.
Enter command (q to quit): INSERT INTO Course VALUES ('02050', NULL);
Added 1 row to Course.
Enter command (q to quit): INSERT INTO Course VALUES ('00050', 'Physics 211');
There is an existing row with the specified primary key.
Could not insert row.
Enter command (q to quit): SELECT * FROM Course;
| id | name |
----------------------------------
| 00050 | Math 123 |
| 01000 | CS 460 |
| 02050 | null |
Selected 3 tuples.
Enter command (q to quit): SELECT name FROM Course;
Specifying column names in the SELECT clause is not supported.
Enter command (q to quit): CREATE TABLE Foo(id CHAR(5) PRIMARY KEY, year INT);
Created table Foo.
Enter command (q to quit): SELECT * FROM Course, Foo;
Specifying multiple table names in the FROM clause is not supported.
Enter command (q to quit): q
Make sure to try to lots of different examples so that you can ensure that your unmarshalling code is working correctly!
The remaining problems will all be completed in a single PDF file. To create it, you should do the following:
Access the template that we have created by clicking on this link and signing into your Google account as needed.
When asked, click on the Make a copy button, which will save a copy of the template file to your Google Drive.
Select File->Rename, and change the name of the file to
ps3_pr456.
Add your work for the remaining problems to this file.
Once you have completed all of these problems, choose
File->Download->PDF document, and save the PDF file in your ps3
folder. The resulting PDF file (ps3_pr456.pdf) is the one that
you will submit. See the submission guidelines at the end of Part I.
16 points total
Below are two schedules in which actions by three transactions (T1, T2, and T3) are interleaved.
schedule 1:
r1(C); w2(B); w1(A); w2(C); c2; r3(B); w3(B); c3; w1(C); c1
schedule 2:
w1(A); r3(A); w2(C); r2(B); c2; r1(C); c1; w3(B); c3
For each of the above schedules, you should take the following steps:
In your copy of the ps3_pr456 template (see above), edit the
diagram that we have provided for the schedule, making whatever
changes are needed to construct the schedule’s precedence graph.
State whether the schedule is conflict serializable. Explain briefly why or why not. In addition, if the schedule is conflict serializable, state one possible equivalent serial schedule.
State whether the schedule is recoverable. Explain briefly why or why not. As needed, your explanation should refer to specific actions by the two transactions.
State whether the schedule is cascadeless. Explain briefly why or why not. As needed, your explanation should refer to specific actions by the two transactions.
8 points total
Consider these two transactions:
T1: r(A); r(B); r(C); w(C); commit T2: r(B); r(A); r(C); w(A); commit
The following is the beginning of one possible schedule of these transactions, with appropriate lock instructions added:
|
T1 |
T2 |
|---|---|
|
sl(A); r(A) |
|
Given the remaining operations that the two transactions need to perform, if the system is using regular two-phase locking (not strict or rigorous), could T2’s next action be to unlock B? Explain briefly why or why not.
Regardless of your answer to part 1, imagine that T1 actually goes next and completes two more actions:
|
T1 |
T2 |
|---|---|
|
sl(A); r(A) |
|
Fill in the table that we have provided in ps3_pr456 to show one
way in which this partial schedule could be successfully completed
under strict two-phase locking. There is more than one possible
answer to this question.
Important guidelines:
The actions that you add should go below the dotted lines in the table. Make sure to position them so that there is no confusion about the order in which they occur.
Make sure to include appropriate lock, unlock and commit actions. You should assume that the DBMS is not using update locks, and that it allows shared locks to be upgraded to exclusive locks.
To show that you understand the difference between strict and rigorous locking, it should not be the case that both transactions delay all of their unlock actions until after their commit actions. At least one unlock action by one of the transactions should come before a read or write by that transaction.
6 points total; 1 point each part
Consider the following partial schedule of the transactions T3, T4, and T5:
ul3(A); r3(A); sl4(B); r4(B); xl5(C); ...
Given this partial schedule, which of the following lock requests would be granted if it were the next operation in the schedule, and which would be denied?
sl4(A)sl3(B)ul5(A)xl3(A)ul5(B)ul4(C)Fill in the provided table with the system’s response to each request,
along with a brief explanation of your answer. (Remember: uli(X)
indicates Ti’s request of the update lock for X.)
You will make submissions to two separate assignments on Gradescope. The steps needed for the two submissions are different, so please make sure to follow carefully the procedures outlined below.
PS 3: Problem 3
IMPORTANT: If you worked with a partner on Problem 3, you should make a single joint submission. One person should submit the file, and they should add the other person as a group member following the instructions in step 6 below.
You should submit only your TableIterator.java file.
When testing, we will use our version of the InsertRow.java file
from Problem 1.
Here are the steps:
Click on PS 3: Problem 3 in the list of assignments. You should see a pop-up window with a box labeled DRAG & DROP. (If you don’t see it, click the Submit or Resubmit button at the bottom of the page.)
Add your file to the box labeled DRAG & DROP. You can either drag and drop the file from its folder into the box, or you can click on the box itself and browse for the file.
Click the Upload button.
You should see a box saying that your submission was successful.
Click the (x) button to close that box.
The Autograder will perform some tests on your file. Once it is done, check the results to ensure that the tests were passed. If one or more of the tests did not pass, the name of that test will be in red, and there should be a message describing the failure. Based on those messages, make any necessary changes. Feel free to ask a staff member for help.
Note: You will not see a complete Autograder score when you submit. That is because additional tests will be run later, after the final deadline for the submission has passed. Passing all of the initial tests for a given problem does not necessarily mean that you will ultimately get full credit on the problem. You should always run your own tests to convince yourself that the logic of your solutions is correct.
If you worked with a partner and you are the one who is submitting the files:
Click on the Add Group Member link that appears below your name above the results of the Autograder.
In the pop-up box that appears, click on the Add Member link.
Type your partner’s name or choose it from the drop-down menu.
Click the Save button.
Check to ensure that your partner’s name now appears below your name above the results of the Autograder.
If needed, use the Resubmit button at the bottom of the page to resubmit your work. Important: Every time that you make a submission, you should submit all of the files for that Gradescope assignment, even if some of them have not changed since your last submission.
Near the top of the page, click on the box labeled Code. Then click on the name of each file to view its contents. Check to make sure that the files contain the code that you want us to grade.
PS 3: Problems 4-6
Submit your ps3pr456.pdf file using these steps:
If you still need to create a PDF file, open your file
on Google Drive, choose File->Download->PDF document, and
save the PDF file in your ps3 folder.
Click on the name of the assignment in the list of assignments on Gradescope. You should see a pop-up window labeled Submit Assignment. (If you don’t see it, click the Submit or Resubmit button at the bottom of the page.)
Click the Select PDF button and find the PDF file that you created. Then click the Upload PDF button.
You should see an outline of the problems along with thumbnails of the pages from your uploaded PDF. For each problem in the outline:
As you do so, click on the magnifying glass icon for each page and doublecheck that the pages that you see contain the work that you want us to grade.
Once you have assigned pages to all of the problems in the question outline, click the Submit button in the lower-right corner of the window.
You should see a box saying that your submission was successful.
Click the (x) button to close that box.
You can use the Resubmit button at the bottom of the page to resubmit your work as many times as needed before the final deadline.
Important
It is your responsibility to ensure that the correct version of a file is on Gradescope before the final deadline. We will not accept any file after the submission window for a given assignment has closed, so please check your submission carefully using the steps outlined above.
If you are unable to access Gradescope and there is enough
time to do so, wait an hour or two and then try again. If you
are unable to submit and it is close to the deadline, email
your homework before the deadline to
cs460-staff@cs.bu.edu
Last updated on October 22, 2025.