CS145 - Fall 2013
Introduction to Databases
Assignment #1
Due Monday October 7

This assignment consists of three automated quizzes, a set of automated XML DTD validation exercises, a set of automated relational algebra exercises, and two challenge problems. It's a fair amount of work so we recommend you get started early. Please leave time to carefully follow the Submission Instructions below.

Automated Quizzes for Basic Material

Log into the CS145 Class2Go Site. Make sure you're using the CS145 portal and not the public one. Your SUNet ID should be required to access the site; logging in with SUNet also ensures that we properly record your scores.

Click on the Quizzes tab. You are to complete three quizzes: XML Quiz (6 problems), JSON Quiz (4 problems), and Relational Algebra Quiz (10 problems). There are several versions of each quiz, and you are permitted to take each version up to three times. Note: Throughout the course, all of our quiz questions are designed to have multiple correct and incorrect answers.  For each quiz, all of the versions contain the same set of questions, however the correct and incorrect multiple-choice options are different in each version.

Although all quiz attempts and scores are recorded, the only score we will use is the highest score achieved on any version of each quiz as of the due date. We strongly suggest that you start early and continue quizzing until you've achieved a perfect score on at least one version, and you feel you understand the material thoroughly. Also please note: Automated quizzes receive no credit if submitted late.

Automated Database Exercises

Log into the CS145 Class2Go Site. Make sure you're using the CS145 portal and not the public one. Your SUNet ID should be required to access the site; logging in with SUNet also ensures that we properly record your scores.

Click on the Interactive Exercises tab. Complete the DTD Exercises (3 problems) and the Relational Algebra Exercises (9 problems). The website is designed so you can interactively develop your solutions in place: each problem allows you to run your proposed solution and see a comparison between your result and the expected one. Once you're happy with your solutions, you must press Submit Answers for your score to be recorded. If you prefer to develop your solutions offline, all data files are provided. For XML DTD validation, it's a simple matter to use the xmlint tool, with instructions provided on the Software Quick Guides page. For the relational algebra exercises, downloading the RA system and setting it up to work on the exercises database takes a bit more effort. In general, students find the website to be the most convenient platform on which to develop their solutions. Either way, don't forget to submit your final solutions to obtain your score. You may do the exercises as many times as you like, and we strongly encourage you to keep working on them until you've received a perfect score. Although all scores are recorded, we will only use the highest score you've achieved on each exercises set as of the due date.

We strongly suggest that you start early -- DTD validation can sometimes take a while to get right, and some of the relational algebra problems are fairly challenging. Also please note: Automated exercises receive no credit if submitted late.

Challenge Problems

Problem 1

Consider a relation Flight(city1,city2) containing one tuple for each pair of cities with a nonstop flight from city1 to city2. Your goal is to write a relational algebra expression that returns a single tuple (Bangkok, Prague) if it is possible to fly from Bangkok to Prague by taking any number of flights. (If not, the expression should return no tuples.) The first flight must originate in Bangkok, the last must terminate in Prague, and all connections require city2 in one flight to be the same as city1 in the next flight.

It turns out that if you don't know in advance how many different cities can appear in relation Flight, it's not possible to write an expression to achieve our goal, using only standard relational operators. However, if we know there can be no more than N different cities in Flight (for some nonnegative integer N), then it is possible. Show such an expression. Note your expression will need to have a "..." of some form in it, but from the way you write it, we should be able to understand immediately how to instantiate the expression for a given N.

Problem 2

Now suppose we don't know in advance how many different cities can appear in relation Flight. To help achieve our goal, let us extend basic relational algebra with a few additional constructs:

  • Statements of the form "R := relational algebra expression", where R can be an existing relation that gets replaced, or a new one that gets created. If it's helpful, R can be referenced in the right-hand side expression.
  • Loops of the form "While NotEmpty(R) Do { sequence of statements }".
  • Sequences of Statements and/or While loops.
Using these constructs, write a relational algebra expression that returns a single tuple (Bangkok, Prague) if it is possible to fly from Bangkok to Prague by taking any number of flights. If it is not possible to reach Prague from Bangkok then no tuples should be returned, but the expression should still terminate. You may assume that the relation Flight has a finite number of tuples, and therefore the number of cities is finite, but do not assume any specific upper limit on the number of cities. Since your solution may not be obvious to understand, please add an English comment to each statement or expression that explains what it does. Without comments, your solution will not be graded.

Submission Instructions for Challenge Problems

Challenge problem solutions should be submitted in pdf format. (If you prepare your solutions in Word before converting to pdf, we've created a handy Word document with relational algebra symbols.) For students who prefer hand-writing their solutions or using some other format, solutions may be scanned and submitted as jpg. Solutions must be submitted through CourseWork, and must be in a single file named challenge1.pdf (or challenge1.jpg). Login to CourseWork and click on the CS145 tab at the top. In the left side-bar, click on Assignments; you will see Challenge Problems #1. Upload your solution file and submit for grading. You may resubmit as many times as you like, however only the latest file and the latest timestamp are saved, and those are what we will use for grading your work and determining late penalties. Submissions via email will not be accepted.

Late Policy and Honor Code