Introduction to Databases

Assignment #1Due 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

Automated Quizzes for Basic Material |

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 Database Exercises |

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*Prague* from *Bangkok* then no tuples should be
returned, but the expression should still terminate. You may
assume that the relation

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 :=`

", where*relational algebra expression*`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.

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

`challenge1.pdf`

(or `challenge1.jpg`

).
Login to CourseWork and click
on the CS145 tab at the top. In the left side-bar, click on

Late Policy and Honor Code |

- Your score for each automated quiz and exercise set is the highest score achieved as of 11:59:00 PM on the due date. No credit is given for automated quizzes or exercises submitted after the due date.
- The Challenge Problems are submitted separately as specified above. They are due at 11:59:00 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 emergencies do arise, each student is allowed a total of four unpenalized late days (four periods up to 24 hours each) for non-automated work, but no single assignment may be more than two days late.
- For 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 all submitted work*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.