Problem Set 2

Part I due by 11:59 p.m. on Tuesday, February 25, 2025.
Part II due by 11:59 p.m. on Thursday, March 20, 2025.

Preliminaries

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.

Part I

40 points total

Creating the necessary folder

Create a subfolder called ps2 within your cs460 folder, and put all of the files for this assignment in that folder.

Creating the necessary file

This part of the assignment will all be completed in a single PDF file. To create it, you should do the following:

1. Access the template that we have created by clicking on this link and signing into your Google account as needed.

2. When asked, click on the Make a copy button, which will save a copy of the template file to your Google Drive.

3. Select File->Rename, and change the name of the file to ps2_partI.

4. Add your work for the problems from Part I to this file.

5. Once you have completed all of these problems, choose File->Download->PDF document, and save the PDF file in your ps2 folder. The resulting PDF file (ps2_partI.pdf) is the one that you will submit. See the submission guidelines at the end of Part I.

Problem 1: Fixed-length and variable-length records

19 points total

Recall the Oscar table from our movie database, which has the following schema:

Oscar(movie_id CHAR(7), person_id CHAR(7), type VARCHAR(23), year INTEGER)

Consider the following tuple from that table:

('1539877', '0614165', 'BEST-ACTOR', 2024)

which captures the fact that Cillian Murphy (whose id is '0614165') won the 2024 Oscar for Best Actor for his performance in Oppenheimer (which has an id of .'1539877').

1. (3 points) What would this tuple look like if we stored it in a fixed-length record? In the 1.1 and 1.2 section of ps2_partI (see above), put your answer in the table labeled record contents.

   You should observe the following conventions:

   • Give each data value its own cell of the table. Adjust the widths of the cells as needed to better fit the sizes of the values, and delete any cells that are not needed.

   • Use a number sign ('#') as a delimiter when it is necessary to record the end of a variable-length field’s value.

   • Use hyphens ('-') for any “wasted” bytes (i.e, bytes that are part of the record’s representation but are not actually storing useful data or metadata).

   To illustrate these conventions, imagine that we were working with the Enrolled table in our university database, which has the following schema:

   Enrolled(student_id CHAR(9), course_name VARCHAR(10), credit_status VARCHAR(10));
   

   If we wanted to show what the tuple

   ('U00000006', 'CS 460', 'ugrad')
   

   would look like using a fixed-length record, we would fill in the table as follows:

   

2. (2 points) What is the length in bytes of the record from part 1? Assume that we are using:

   • four-byte integer field values

   • one-byte characters – including any digit characters that are part of a CHAR or VARCHAR.

   Put your final answer in the box labeled length in bytes, and show your work in the box below the answer.

3. (3 points) What would this tuple look like if we stored it in a variable-length record in which each field is preceded by its length?

   In the 1.3 and 1.4 section of ps2_partI, put your answer in the table labeled record contents.

   In addition to the conventions that we specified for part 1, you should also give each metadata value its own cell of the table. Change the background color of cells containing metadata to distinguish them from cells containing actual data values. You can do so by using the icon that looks like a paint can in the menu bar at the top of Google Docs.

   In addition to the assumptions about the sizes of characters and integers that we gave you in part 2, you should assume that integers used for metadata are two bytes long (not four bytes).

4. (2 points) What is the length in bytes of the record from part 3? Make the same assumptions stated in parts 2 and 3. Put your final answer in the box labeled length in bytes, and show your work in the box below the answer.

5. (4 points) What would this tuple look like if we stored it in a variable-length record that begins with a header of offsets?

   In the 1.5 and 1.6 section of ps2_partI, put your answer in the table labeled record contents. Use the same conventions that we specified for parts 1 and 3, and use the same assumptions about the sizes of characters, integer field values, and integer metadata that we gave you in parts 2 and 3.

6. (2 points) What is the length in bytes of the record from part 5? Put your final answer in the box labeled length in bytes, and show your work in the box below the answer.

7. (3 points) Now consider the following Person tuple for the actor Jack Quaid:

    ('4425051', 'Jack Quaid', '1992-04-24', NULL)
   

   This tuple reflects the fact that our database is missing his pob value, which is stored as NULL.

   What would this tuple look like if we stored it in a variable-length record that begins with a header of offsets?

   In the 1.7 section of ps2_partI, put your answer in the table labeled record contents.

   For the purposes of this problem, you should assume that the schema of the Person table is:

   Person(id CHAR(7), name VARCHAR(128), dob CHAR(10), pob VARCHAR(128))
   

   In addition, you should use:

   • the approach to NULL values that we took in lecture

   • the same conventions that we specified for parts 1 and 3

   • the same assumptions about the sizes of characters, integer field values, and integer metadata that we gave you in parts 2 and 3.

   There is no separate length-computation question for this record.

Problem 2: Index structures

21 points total; 7 points each part

Let’s say that you want to insert items with the following sequence of keys into a collection of records that uses some form of indexing:

31, 19, 21, 29, 30, 11, 10, 13, 18, 16, 35, 23, 32

1. Insert this key sequence into an initially empty B-tree of order 2. In section 2.1 of ps2_partI, show the tree after each insertion that causes a split of one or more nodes, and the final tree.

   We have given you a sample diagram that includes nodes of different sizes. Make copies of the diagram so that you can use separate diagrams for the results of each insertion that causes a split, and for the final tree. Note that you do not need to keep the shape of the tree that we have given you. Rather, you should edit it as needed: deleting or adding nodes and edges, replacing the Xs with keys, adding or removing keys, and making whatever other changes are needed.

2. Insert this same key sequence into an initially empty B+tree (note the +) of order 2. In section 2.2 of ps2_partI, show the tree after each insertion that causes a split of one or more nodes, and the final tree. Here again, you should make copies of the diagram that we have given you and edit them as needed.

3. Insert this same key sequence into a hash table that uses linear hashing. In section 2.3 of ps2_partI, use the tables that we have provided to show the state of the table before and after each increase in the number of buckets, as well as the final state of the table.

   Important details:

   • The table should use the hash function h(x) = x, and it should start out with two empty buckets.

   • Within a given bucket, please list the keys in the order in which they were inserted.

   • Assume that a bucket is added whenever the number of items in the table exceeds three times the number of buckets.

   • An item that causes the table to grow should appear in both the before and after tables for that increase. See the PS 2 FAQ for more details.

Submitting your work for Part I

Login to Gradescope by clicking the link in the left-hand navigation bar. Once you are in logged in, click on the box for CS 460.

Submit your ps2_partI.pdf file using these steps:

1. 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 ps2 folder.

2. Click on PS 2: Part I 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.)

3. Choose the Submit PDF option, and then click the Select PDF button and find the ps1_partI.pdf that you created in step 1. Then click the Upload PDF button.

4. You should see an outline of the problems along with thumbnails of the pages from your uploaded PDF. For each problem in the outline:

   • Click the title of the problem.
   • Click the page(s) on which your work for that problem can be found.

   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.

5. 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.

6. You should see a box saying that your submission was successful. Click the (x) button to close that box.

7. 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.

Part II

60 points total

Problem 3: Converting the Movie table to XML

25 points; pair-optional

This is the only problem of the assignment 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 this problem, you will write a series of methods that can be used to create an XML version of the Movie table from Problem Set 1. Your methods will be part of a larger program that uses the JDBC framework to connect to the SQLite database that you used in PS 1 and to execute the SQL queries needed to extract the necessary data.

Obtaining the necessary files

You should begin by downloading the following zip file:
problem3.zip

Unzip/extract the contents of the file.

Depending on your system, after extracting the contents you will either have:

• a folder named problem3 that contains all of the files that you need for this problem

• an outer folder called problem3 that contains an inner folder named problem3 that contains all of the Java files that you need for this problem.

Take the problem3 folder that actually contains the necessary files and drag it into your ps2 folder so that you can easily find and open it from within VS Code.

Getting started

1. Read through our overview of the JDBC framework.

2. Launch VS Code on your laptop.

3. In VS Code, select the File->Open Folder or File->Open menu option, and use the resulting dialog box to find and open the problem3 folder that you created above – the one that contains the provided files. (Note: You must open the folder; it is not sufficient to simply open one of the Java files in the folder.)

   The name of the folder should appear in the Explorer pane on the left-hand side of the VS Code window, along with a list of all of its contents.

4. Click on the name XMLforOscars.java in the Explorer pane, which will open the file that you need to modify.

5. Review all of the code that we’ve provided before you start writing any new code. See below for some additional information on what we’ve given you.

The provided code

The class that you will be completing is called MovieToXML. In this class we’ve given you:

• the constructor for the class, which takes the name of a SQLite file that should contain a relational database with the schema outlined in Problem Set 1; the constructor establishes a connection to the SQLite database, and it stores the resulting Connection object in a field called db.

• a helper method called simpleElem(), which takes as inputs the name and value of a simple element and returns a string of the form "<name>value</name>". This method should only be used to form simple elements – ones that do not have any attributes or child elements.

• a helper method called resultsFor(), which takes as input a string presenting a SQL query for the movie database and returns a ResultSet object that can be used to process the results of that query. You are welcome to use this method in the code that you write, although doing so is not required.

• a method called idFor(), which takes as input the name of a movie and performs a query to find and return the movie’s id; this method will be useful when testing the methods that you write. (Note: Although movie names are not unique, we can safely ignore that fact for the purposes of this method.)

• a method called createFile(), which performs a query to obtain the id numbers of all of the movies in the Movie table, and which processes them one at a time

• the main method, which runs the full program.

Note that many of these methods – and all of the methods that you will implement – include a throws clause in their method header. This clause is needed because the code included in these methods may throw the exception(s) mentioned in the throws clause, and instead of catching them, we are simply declaring that they may be thrown.

The methods you will write

You will implement a number of non-static methods of the MovieToXML class.

Here are your tasks:

1. Implement the method called fieldsFor() whose header we have provided. It takes a string representing the id number of a movie, and it should return a string containing a sequence of XML elements – one for each non-null field (i.e., column value) in that movie’s tuple. If a field has a null value, that field should not be included in the returned string. If there is no movie with the specified id, the method should simply return the empty string.

   For example, if you run the following test code (adding it to the main method in TestDriver.java):

   MovieToXML xml = new MovieToXML("movie.sqlite");
   System.out.println(xml.fieldsFor(xml.idFor("Black Panther")));
   System.out.println(xml.fieldsFor("1234567"));   // no movie with that id
   System.out.println(xml.fieldsFor(xml.idFor("Cool Hand Luke")));
   

   you should see:

       <name>Black Panther</name>
       <year>2018</year>
       <rating>PG-13</rating>
       <runtime>134</runtime>
       <genre>AVS</genre>
       <earnings_rank>6</earnings_rank>
        
        
       <name>Cool Hand Luke</name>
       <year>1967</year>
       <runtime>126</runtime>
       <genre>D</genre>
        
   

   Notes:

   • In our database, Cool Hand Luke has null values for rating and earnings_rank, and thus those elements are not included in the results for that movie.

   • You should see an extra blank line when you print the results of any call that produces one or more fields (including the blank line after the results for Cool Hand Luke shown above), because the string returned by the method ends with a newline, and the println method adds its own newline.

   • The second println statement prints only a blank line because there is no movie whose id is 1234567, and thus the call xml.fieldsFor("1234567") returns an empty string. As a result, there are two blank lines after the results for Black Panther: one after its fields, and one from the printing of the empty string.

   Important guidelines:

   • You must begin by performing the appropriate SQL query. Use the idFor() method as a model for what you should do.

   • When processing the results, make sure to follow the approach given in our JDBC overview.

   • The elements for the non-null fields should appear in the same order as the corresponding columns in the Movie table:

     • name
     • year
     • rating
     • runtime
     • genre
     • earnings_rank

   • You must use the provided simpleElem() method to form the XML element for a given field.

   • Each element should be on its own line, which you can accomplish by including a newline character ("\n") after each element.

   • Each element should be preceded by exactly four spaces, and there should be no extra spaces at the end of a given line.

2. Implement the method called actorsFor() whose header we have provided. It takes a string representing the id number of a movie, and it should return a string containing the XML for a single complex element named actors that includes nested child elements of type actor for each of the actors associated with the movie, ordered by the full name of the actor. If there is no movie with the specified id, the method should simply return the empty string.

   For example, if you run the following test code:

   MovieToXML xml = new MovieToXML("movie.sqlite");
   System.out.println(xml.actorsFor(xml.idFor("Black Panther")));
   System.out.println(xml.actorsFor("1234567"));
   System.out.println(xml.actorsFor(xml.idFor("Wonder Woman")));
   

   you should see:

       <actors>
         <actor>Chadwick Boseman</actor>
         <actor>Danai Gurira</actor>
         <actor>Lupita Nyong’o</actor>
         <actor>Martin Freeman</actor>
         <actor>Michael B. Jordan</actor>
       </actors>
    
    
       <actors>
         <actor>Chris Pine</actor>
         <actor>Connie Nielsen</actor>
         <actor>Danny Huston</actor>
         <actor>Gal Gadot</actor>
         <actor>Robin Wright</actor>
       </actors>
    
   

   Here again, you should see an extra blank line when you print the results of any call that produces one or more elements (including the blank lines shown above), because the string returned by the method ends with a newline, and the println method adds its own newline.

   Note that the second println statement prints only a blank line because there is no movie whose id is 1234567, and thus the call xml.actorsFor("1234567") returns an empty string.

   Important guidelines:

   • You shouldn’t make any assumptions about the number of actors associated with a given movie. In many cases it will be five, but your code should be able to handle an arbitrary number.

   • You should begin by performing the appropriate SQL query to get the necessary ResultSet. Make sure to use an ORDER BY clause in your query to get the necessary ordering. You may find it helpful to use the resultsFor method that we have provided, but doing so is not required.

   • Given the results of the query, you should take the necessary steps to return either:

     • a string containing the XML for the appropriate actorsFor element

       OR

     • an empty string, if there is no movie with the specified id.

   • The returned string should be formatted as shown above. The outer start tag, outer end tag, and each child element should be on its own line, with a newline character ("\n") at the end of each line.

   • You must use your simpleElem() method to form the XML child element for each actor. However, you should not use it to form the outer actors element.

   • The outer start tag and outer end tag should each be preceded by exactly four spaces, but the child elements should each be preceded by exactly six spaces. There should be no extra spaces at the end of a given line.

3. Implement the method called directorsFor() whose header we have provided. It takes a string representing the id number of a movie, and it should return a string containing the XML for a single complex element named directors that includes nested child elements of type director for all of the directors associated with the movie, ordered by the full name of the director. If there is no movie with the specified id, the method should simply return the empty string.

   For example, if you run the following test code:

   MovieToXML xml = new MovieToXML("movie.sqlite");
   System.out.println(xml.directorsFor(xml.idFor("Black Panther")));
   System.out.println(xml.directorsFor("1234567"));
   System.out.println(xml.directorsFor(xml.idFor("Frozen")));
   

   you should see:

       <directors>
         <director>Ryan Coogler</director>
       </directors>
    
    
       <directors>
         <director>Chris Buck</director>
         <director>Jennifer Lee</director>
       </directors>
    
   

   Here again, you should see an extra blank line when you print the results of any call that produces one or more elements (including the blank lines shown above), because the string returned by the method ends with a newline, and the println method adds its own newline.

   Note that the second println statement prints only a blank line because there is no movie whose id is 1234567, and thus the call xml.directorsFor("1234567") returns an empty string.

   Important guidelines:

   • You shouldn’t make any assumptions about the number of directors associated with a given movie. In many cases it will be one, but your code should be able to handle an arbitrary number.

   • You should begin by performing the appropriate SQL query to get the necessary ResultSet. Make sure to use an ORDER BY clause in your query to get the necessary ordering.

   • Given the results of the query, you should take the necessary steps to return either:

     • a string containing the XML for the appropriate directorsFor element

       OR

     • an empty string, if there is no movie with the specified id.

   • The returned string should be formatted as shown above. The outer start tag, outer end tag, and each child element should be on its own line, with a newline character ("\n") at the end of each line.

   • You must use your simpleElem() method to form the XML child element for each director. However, you should not use it to form the outer directors element.

   • The outer start tag and outer end tag should each be preceded by exactly four spaces, but the child elements should each be preceded by exactly six spaces. There should be no extra spaces at the end of a given line.

4. Implement the method called elementFor() whose header we have provided. It takes a string representing the id number of a movie, and it should return a string containing the XML for a single complex element named movie that includes nested child elements for:

   • the non-null fields in the movie’s tuple (use fieldsFor() to get these)

   • the actors in the movie (use actorsFor() to get these)

   • the directors of the movie (use directorsFor() to get these)

   In addition, each movie element must have an attribute named id for the movie’s id number.

   For example, if you run the following test code:

   MovieToXML xml = new MovieToXML("movie.sqlite");
   System.out.println(xml.elementFor(xml.idFor("Black Panther")));
   System.out.println(xml.elementFor("1234567"));
   System.out.println(xml.elementFor(xml.idFor("Wonder Woman")));
   

   you should see:

     <movie id="1825683">
       <name>Black Panther</name>
       <year>2018</year>
       <rating>PG-13</rating>
       <runtime>134</runtime>
       <genre>AVS</genre>
       <earnings_rank>6</earnings_rank>
       <actors>
         <actor>Chadwick Boseman</actor>
         <actor>Danai Gurira</actor>
         <actor>Lupita Nyong’o</actor>
         <actor>Martin Freeman</actor>
         <actor>Michael B. Jordan</actor>
       </actors>
       <directors>
         <director>Ryan Coogler</director>
       </directors>
     </movie>
    
    
     <movie id="0451279">
       <name>Wonder Woman</name>
       <year>2017</year>
       <rating>PG-13</rating>
       <runtime>141</runtime>
       <genre>A</genre>
       <earnings_rank>37</earnings_rank>
       <actors>
         <actor>Chris Pine</actor>
         <actor>Connie Nielsen</actor>
         <actor>Danny Huston</actor>
         <actor>Gal Gadot</actor>
         <actor>Robin Wright</actor>
       </actors>
       <directors>
         <director>Patty Jenkins</director>
       </directors>
     </movie>
    
   

   Here again, you should see an extra blank line when you print the results of any call that produces one or more elements (including the blank lines shown above), because the string returned by the method ends with a newline, and the println method adds its own newline.

   Note that the second println statement prints only a blank line because there is no movie whose id is 1234567, and thus the call xml.elementFor("1234567") should return an empty string.

   Important guidelines:

   • This method should not perform any queries of its own. Rather, you must use your previous methods to obtain the necessary child elements.

   • Because the movie element that you are forming has an attribute, you should not use the simpleElem() method to create it. Rather, you should construct it yourself using string concatenation.

   • Don’t forget to include the movie’s id as an attribute within the start tag for movie, as shown above. In order to include the quotes around the id, you will need to use the escape sequence "\"" for each double-quote character.

   • The outer start tag and outer end tag should each be on their own line preceded by exactly two spaces and followed by a newline character.

   • The child elements should have the same spacing and formatting described in the earlier method specifications, so you won’t need to add any new spaces to them.

   • Once again, there should be no extra spaces at the end of a given line.

Once you have completed and tested all of your methods, running the MovieToXML program should create a file named movies.xml that represents the entire Movie table in XML!

Problem 4: Querying an XML database

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.

Installing the software

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.

Performing queries in BaseX

As outlined in our instructions, you can perform queries by taking the following steps:

1. Start up the BaseX GUI by double-clicking on the JAR file that you downloaded.

2. 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.

3. Click Open to select the file, and click OK to create the database.

4. 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.)

5. 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.

Important guidelines

1. 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.

2. ps2_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.

3. Construct the XQuery commands needed to solve the problems given below. Test each command in BaseX to make sure that it works.

4. Once you have finalized the XQuery command for a given problem, copy the command into your ps2_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.

5. 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.

6. 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.

7. 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.

8. 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.

9. 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.

10. You do not need to worry about indenting and line breaks in the results of your queries.

The query problems

Make sure to read and follow the guidelines given above.

It is worth noting that our movie database was last updated in September of last year, so it doesn’t include information about the most recent movies.

1. In Problem Set 1, you wrote a SQL query to find information about two Oscar nominees born overseas: Sebastian Stan and Felicity Jones. Write a standalone XPath expression (not a FLWOR expression) to find the places of birth of these two actors. The result of the query should be two pob elements.

2. In our XML movie database, both movie and person elements include an attribute called oscars if the corresponding movie or person has received one or more Oscars. These oscar attributes are of type IDREFS, and they’re used to capture the relationships between a person or movie and the corresponding Oscar or Oscars.

   For example, here is the beginning of the movie element for the movie Titanic:

   <movie id="M0120338" directors="P0000116"
          actors="P0000138 P0000701 P0000708 P0000870 P0000200"
          oscars="O19980000000 O19980000116">
      <name>Titanic</name>
      <year>1997</year>
      ...
   

   Because that movie won two of the Oscars in our database, it has an attribute of called oscars whose value is a list containing two id values for the corresponding oscar elements from elsewhere in the database.

   It’s also worth noting that the id values shown in the oscars attribute for Titanic each begin with the string "O1998". The upper-case O indicates that it is an Oscar id, and the 1998 indicates that the Oscars were awarded in 1998. This same format is used for all Oscar id values in the database: they each begin with an upper-case O, followed by the year in which the Oscar was awarded, followed by some additional numeric digits.

   Based on the above information, write a standalone XPath expression (not a FLWOR expression) to find the names of all people and all movies that won an Oscar in 2015. You should assume that the id values of all of the Oscars won by those movies include the string "O2015" (an upper-case O, followed by the digits 2015). The result of the query should be a collection of name elements with the names of the winning movies and people.

   Hints:

   • The attributes of a given element are considered children of that element in the XML document tree, at the same level as its nested child elements.

   • You should use the contains function to perform substring matching, as discussed in lecture.

   • Some of the name elements that we’re looking for have a parent of type movie and others have a parent of type person. Ask yourself: How can I construct an XPath expression that does not depend on which type of parent an element has?

3. In Problem Set 1, you wrote a SQL query to find information about all Best Picture winners directed by a foreign-born director. Write a FLWOR expression to solve a similar problem. The results of the query should be new elements of type foreign_best_pic that each include three nested child elements:

   • the name element of a movie that won Best Picture and was directed by a foreign-born director
   • a new element of type director whose value is the name of the director of the movie
   • a new element of type oscar_year whose value is the year in which the movie won Best Picture.

   For example:

   <foreign_best_pic>
     <name>Titanic</name>
     <director>James Cameron</director>
     <oscar_year>1998</oscar_year>
   </foreign_best_pic>
   

   Note: Remember that you do not need to worry about indenting or line breaks in the results of your queries.

   Hints:

   • Here again, you will need to use the contains function to perform substring matching.

   • Because we want pob values that do not contain the string "USA", you will also need to use the not function (which XQuery provides instead of a logical operator not):

     not(contains(...))
     

     where you replace the ... with the correct inputs to contains.

   • When a person’s pob is unknown, our database doesn’t include a pob element for them. To ensure that you only include directors that have a pob element, your predicate will need to check for the presence of that element. 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 movie elements that have an earnings_rank child element and a runtime greater than 100:

     //movie[earnings_rank and runtime > 100]
     

   • 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.

   • 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.

4. In Problem Set 1, you wrote a SQL query to find, for every movie released before 1940, the number of Oscars won by that movie. Write a FLWOR expression to solve a similar problem. The results of the query should be new elements of type old_movie that include the following nested child elements:

   • the name element of a movie released before 1940

   • a new element of type num_oscars that has as its value the number of Oscars won by the movie; if the movie did not win any Oscars, the value of this element should be 0

   • for each Oscar won by the movie (if any), the type element of the Oscar.

   For example:

   <old_movie>
     <name>Cavalcade</rating>
     <num_oscars>2</num_oscars>
     <type>BEST-DIRECTOR</type>
     <type>BEST-PICTURE</type>
   </old_movie>
   

   Sort the results by the name of the movie. Within a given old_movie element, sort the type child elements in increasing order by their value.

   Hints:

   • There are different approaches to obtaining the necessary movies. However, you will need to ensure that a given movie 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 movie elements with oscar elements.

   • 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.

   • You will also 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.

   • Some of the hints for the previous problem also apply here.

5. In Problem Set 1, you wrote a SQL query to find, for each non-NULL rating associated with 10 or more movies in our database, the shortest runtime, longest runtime, and average runtime of the movies with that rating. Write a FLWOR expression to solve the same problem. The results of the query should be new elements of type rating_runtimes that include the following nested child elements:

   • one for the rating; see below for more details about this element
   • a new element of type shortest that has as its value the shortest runtime of movies with that rating
   • a new element of type longest that has as its value the longest runtime of movies with that rating
   • a new element of type average that has as its value the average runtime of movies with that rating.

   For example:

   <rating_runtimes>
     <rating>G</rating>
     <shortest>78</shortest>
     <longest>238</longest>
     <average>116.41025641025641</average>
   </rating_runtimes>
   

   Sort the results by rating.

   Hints:

   • To ensure that you only consider a given rating once, you 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 rating elements by adding back in the begin and end tags that were removed by distinct-values.

   • Some of the hints for the previous problems also apply here.

6. Winning multiple Oscars is one sign of greatness, as is appearing in a large number of movies in our database. Doing both is truly impressive!

   Write a FLWOR expression to find all people who have both:

   • won two or more acting Oscars (BEST-ACTOR, BEST-ACTRESS, BEST-SUPPORTING-ACTOR, or BEST-SUPPORTING-ACTRESS)

   • appeared in six or more of the movies in the database.

   For each such person, construct a new element of type acting_legend that includes the following nested child elements:

   • the name element of the person

   • a new element of type movie_count that has as its value the number of movies in the database in which the person has acted

   • for each acting Oscar won by the person, a new element called oscar that has as its text value a string with the following format:

     year - type for movie
     

     See examples below.

     Sort these nested oscar elements by year.

   For example:

   <acting_legend>
     <name>Meryl Streep</name>
     <movie_count>7</movie_count>
     <oscar>1980 - BEST-SUPPORTING-ACTRESS for Kramer vs. Kramer</oscar>
     <oscar>1983 - BEST-ACTRESS for Sophie's Choice</oscar>
     <oscar>2012 - BEST-ACTRESS for The Iron Lady</oscar>
   </acting_legend>
   

   Hints:

   • Your return clause will need to include the string literals "-" and "for". Note that you should not need to include any spaces in these string literals, because XQuery will automatically add a space between string values that are separated by a comma in the return clause.

   • Some of the hints for the previous problems also apply here.

Submitting your work for Part II

Coming soon!

Last updated on February 27, 2025.