Introduction to Databases

Assignment #4Due Monday October 28 -- NO LATE WORK ACCEPTED |

This assignment consists of writing XPath, XQuery, and XSLT queries over two different databases, along with a few challenge problems in relational design.

- Warning #1: No late work of any type is accepted for this assignment. Because of the midterm exam on October 30, we will be posting sample solutions to the challenge problems shortly after the 11:59:00 PM due date on October 28.
- Warning #2: Most students find it takes them considerably longer to become facile with XPath, XQuery, and XSLT than it took them for SQL. This week's challenge problems are no piece of cake either. We strongly suggest starting early!

Automated XML Query Exercises |

- XML Course-Catalog XPath & XQuery Exercises (assigned) - 9 problems
- XML Course-Catalog XSLT Exercises (assigned) - 2 problems
- XML World-Countries XPath & XQuery Exercises (assigned) - 6 problems
- XML World-Countries XSLT Exercises (assigned) - 3 problems

As with all of the automated exercises, 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, you can install Kernow (an interface with Saxon embedded) on your computer, download the data files, and work offline:

- Here is a quick
guide for installing and using Kernow

- Here is the course-catalog XML data file
- Here is the world-countries XML data file

Challenge Problems |

Your task is to write SQL queries to check satisfaction of certain functional and multivalued dependencies on table instances. Suppose you have a table

`T(A,B,C,D)`

. You may assume there are
no `NULL`

values in `T`

, but otherwise make
no assumptions about the data. For each of the following three
dependencies -- two functional dependencies and one multivalued
dependency -- write a query that returns an empty result if and only
if the current contents of table `T`

satisfy the
dependency. That is, if the dependency is satisfied then the
result of the query is empty, while if the dependency is not
satisfied then the query
result is nonempty (the specific contents of the result
don't matter).(c)

Notes:

- We're looking for solutions that use the standard declarative
constructs of SQL, not esoteric constructs supported by specific
systems.

- You won't be a candidate for a "Gold" score on this set of
challenge problems unless you include a transcript of running
your SQL queries over sample tables on SQLite, MySQL, or some
other SQL DBMS. You sample tables should demonstrate a variety
of instances of table
`T`

, including some instances satisfying the dependencies and some not. Please include your data as well as your query results.

Consider a relation `R(A1,A2,...,An)` with `n > 0` attributes. Your goal
is to construct an instance (set of tuples) for this relation that
satisfies the functional dependencies `Ai `→` A(i+1)` for all `i=1..(n-1)`.
That is, in your instance:

A1 → A2 A2 → A3 A3 → A4 ... A(n-1) → AnFurthermore, the

Your solution writeup should consist of a clear description or
depiction of how to generate your relation instance for any `n > 0`.
As examples, show the actual instances for `n=2`, `n=4`, and `n=6` (i.e., relations
with 2, 4, and 6 attributes).

Prove the *intersection rule* for multivalued
dependencies. Specifically, consider a relation `R`, and
let `A`,
`B`, and `C` be three
sets of attributes in `R.` Prove that if `A `→>`
B `and
`A` →>`
C `hold
for `R`, then `A `→>` (B `∩` C)` also holds,
where ∩ is the standard intersection of attribute sets. For
simplicity you may assume that `A` does not
intersect `B`
or `C`,
and there are no attributes in `R` besides those in sets
`A`, `B`, and `C`.

Submission Instructions: Challenge Problems |

Solutions
should be submitted in pdf
format. 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 *Challenge
Problems #4* (for Assignment #4 challenge problems -- don't
worry, there was no Challenge
Problems #3). 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.

`challenge4.pdf`

(or `challenge4.jpg`

). Login to Coursework. Under Assignments you will see

Reminders: Late Policy and Honor Code |

- Your score for each automated exercise set is the highest score achieved as of 11:59:00 PM on the due date. No credit is given for automated exercises submitted after the due date.
- The Challenge Problems are due at 11:59:00 PM on the due date.
For this assignment, no
late submissions of challenge problems are accepted.
Because of the midterm exam on October 31, we will be posting
sample solutions to the challenge problems shortly after the
due date.

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