• Submission Instructions: All challenge problems should be submitted by email to cs145-submit@cs.stanford.edu. Solutions should be typed and can be submitted in a variety of formats: Word, pdf, or postscript. Well formatted text solutions will also be accepted if they are named with the *.txt extension. For students who absolutely prefer handwriting the solutions, solutions may be scanned in using the scanner in Meyer library or a personal scanner, and then submitted as jpeg or another universally readable reasonable format. If you are unsure, please contact the TA question list at cs145@cs. The on-time deadline is 11:59 PM on the due date. Submissions after the deadline but less than 24 hours late will be accepted but penalized 10%, and submissions more than 24 hours but less than 48 hours late will be penalized 30%. No submissions will be accepted more than 48 hours late since solutions may be made available at that time. Since emergencies do arise, each student is allocated four "chits" for turning in work with no penalty. Please see the Assigned Work page for a detailed description of chits. Please remember that challenge problems must be submitted electronically, and plan accordingly.

• Guidelines for Typing Assignments:
  • Please put your name,preferred email address, and student id number at the beginning of the assignment.
  • Use common sense. Something that looks unreadable to you is probably unreadable to us. Clearly number each problem, put enough space between problems, avoid lots of typos, and try to be clear and succinct. If you have a series of equations, put space between the text and the equations, and indent. However, we're not expecting that you spend a lot of time on making the assignments "look pretty".
  • For relational algebra, instead of using symbols, you may use "SELECT", "PROJECT", "RENAME", and "JOIN". A simple example of the desired format for relational algebra is the following:

    RENAME[NewName(ID)]((SELECT[ID>12](PROJECT[ID](Students))) JOIN[Students.ID = Classes.ID] Classes)
    

    Subscripting may be used, and is encouraged, to make the expressions clearer.
  • If a figure is required (unlikely, but a possibility) there are two options: Using the word-processing application you are using, you may create such figures, or you may handwrite the figures and scan them in. If you do scan in the figures, mention in your type up of the particular problem requiring the figure the name of the file that corresponds to the figure.

• Honor Code reminder: For more detailed discussion of the Stanford Honor Code as it pertains to CS145, please see the Assigned Work page under Honor Code. In summary: You must indicate on your written and programming assignments any assistance (human or otherwise) that you received. Any assistance received that is not given proper citation will be considered a violation of the Honor Code. In any event, you are responsible for understanding and being able to explain on your own all material that you submit.

• Partners are not permitted. Problems must be completed individually.

Challenge Problems

1. This problem explores how to systematically store relational data in XML. We will use as examples two relations:

     Student(ID, name, phone)  // ID is key
     Plays(ID, sport, season)  // (ID, sport) is key
   

   We will use the following sample data for these relations:

   In Student:

     (123, Susan, 123-4567)
     (456, Sam, 456-7890)
     (789, Samantha, 789-0123)
   

   In Plays:

     (123, soccer, fall)
     (123, basketball, winter)
     (789, soccer, fall)
   

   (a) Specify a single DTD that allows data from any relational schema (one or more relations) to be stored as an XML document valid with respect to that DTD. (That is, the element structure of the XML will not be derived from the relational schema, since it needs to work for every schema.) Show how the sample data above would be encoded in XML corresponding to your DTD.

   (b) Specify an algorithm for translating a relational schema (one or more relations) into a single XML DTD, where in this case the element structure (i.e., the tags) in the XML can reflect the relational schema. Show how the sample data above would be encoded in XML corresponding to your DTD. You may specify your algorithm using any kind of code or high-level pseudocode that you like.

   (c) Suppose you have the additional information that every value for attribute Plays.ID appears exactly once in Student.ID (but not necessarily vice-versa). You don't have to give a translation algorithm, but illustrate what might be considered a "better" XML structure for the sample data than the structure produced by your algorithm in (2).

2. Consider the same schema used for the XML problem, with one additional attribute in relation Plays:

     Student(ID, name, phone)        // ID is key
     Plays(ID, sport, season, rank)  // (ID, sport) is key
   

   Write a relational algebra expression that returns the names of all students who play at least two sports in the same season and who have the highest rank in at least one of those sports. Do not assume there is a specific highest rank, such as 1. However, if it helps you may assume there are not ties in rank for a given sport. To keep your expression from getting too unwieldy you may use "S" for Student and "P" for Plays.