斯坦福数据库试卷database

CS145 Final Exam 8:30-11:30AM Friday Dec. 14, 2007

This exam is open book and notes. You may use a laptop, but please keep your sound on

mute so you do not disturb others. You may access class notes or other written materials

on your computer, even using the Internet if you have wireless access. However, you must

not use your computer to run a DBMS, either over the Internet, or locally, should you have

a DBMS that runs on your own computer.

Print your name: ___________________________________________________

The Honor Code is an undertaking of the students, individually and collectively:

1. That they will not give or receive aid in examinations; that they will not give or receive unpermitted

aid in class work, in the preparation of reports, or in any other work that is to be used by the instructor

as the basis of grading;

temptations to violate the Honor Code. While the faculty alone has the right and obligation to set

academic requirements, the students and faculty will work together to establish optimal conditions for

honorable academic work.

I acknowledge and accept the Honor Code (signed): ____________________________________

1. The same [choice (a)], meaning that for every database the answers to the two queries are the same.

That is, the same tuples are produced by each query, and a tuple is produced the same number of

times by each query. The order in which tuples are produced is not to be considered.

2. Completely different [choice (d)], meaning that there are databases where Q1 produces more of

some particular tuple, and other databases where Q2 produces more of some particular tuple. Note that

the query producing the smaller number of copies of a tuple may produce zero copies of that tuple.

3. One is contained in the other but they are not the same [choice (b) or (c)]. For instance, Q1 is

contained in Q2 if on every database, Q2 produces at least as many copies of each tuple as Q1 does.

SQL relations may have NULL's, although in relational algebra, you should assume no NULL's unless

stated otherwise.

In SQL it is possible that there may be duplicate tuples, but in relational algebra and Datalog assume

the relations are sets unless stated otherwise.

For XPath and XQuery, think of the result as a bag of items, rather than a sequence (list) of items, so

order does not matter.

SELECT * FROM R;

Q2:

(SELECT * FROM R)

INTERSECT

(SELECT * FROM R);

a) Q1 and Q2 produce the same answer.

b) The answer to Q1 is always contained in the answer to Q2.

c) The answer to Q2 is always contained in the answer to Q1.

Question 2. Consider XML documents containing information about students in classes and conforming

<!DOCTYPE Classes [

Consider this query pair:

Q1: XPath:

/Classes/Class

[Students/Student/@Name != Students/Student/@Name]/Topic

Q2: XQuery:

for $c in /Classes/Class

for $s1 in $c/Students/Student

a) Q1 and Q2 produce the same answer.

b) The answer to Q1 is always contained in the answer to Q2.

c) The answer to Q2 is always contained in the answer to Q1.

d) Q1 and Q2 produce different answers.

Question 3. Assume the XML document in file xxxxxx conforms to the following DTD:

<!DOCTYPE X [

Bidding_closure(x, y) <- Bid_on(x, y)

Bidding_closure(x, y) <- Bid_on(x, z) AND Bidding_closure(z, y)

Q2: SQL:

WITH RECURSIVE Bidding_closure(x, y) AS

(SELECT sellerID, bidderID FROM Items, Bids WHERE items.itemID = bids.itemID AND

sellerID <> bidderID)

UNION

(SELECT bc1.sellerID, bc2.bidderID FROM Bidding_closure bc1, Bidding_closure bc2 WHERE

bc1.y = bc2.x)

Question 5. Suppose T is a UDT, R is a relation with a reference to T as one of its attributes, and S is a

relation using T as a rowtype, all defined by:

CREATE TYPE T AS (a INT, B INT);

CREATE TABLE R(c INT, d REF T);

CREATE TABLE S OF T;

Q1:

c) The answer to Q2 is always contained in the answer to Q1.