CSE/ISE 305
Spring 2002 Stony Brook |
Principles of Database Systems
Annie Liu Homework 4 |
Handout H4
Mar. 22, 2002 Due Apr. 4 |

You should understand all basic concepts, not just the ones mentioned below. You should know relational algebra and SQL for querying and manipulating data. You should also know normal forms and decompositions into normal forms for more advanced database design.

**Note:** You will need to understand these problems and
solutions to them, not just memorize the answers, because the data
manipulation part here is very different from the data definition part
earlier---very similar queries may need completely different SQL code
and can have completely difference answers.

More exercises for SQL queries are given in Project 3. Please make sure that you can do them yourself; do not just let your teammate do them. If you would like more problems to solve, do other exercises in the textbook.

**Problem 1. Relational algebra operations.**

Exercise 6.1 on page 172 of textbook. (You should understand the meaning of these operations, not just knowing answers to the questions; the meaning is what will be tested, the problems are just exercises).

**Problem 2. SQL queries.**

**a.** What is the simple strategy, i.e., what are the steps,
for evaluating an SQL statement of the following form?

SELECT thing1 FROM thing2 WHERE thing3 GROUP BY thing4 HAVING thing5 ORDER BY thing6

**b.** Exercise 6.10 (a).

**c.** Exercise 6.10 (c) (Hint: you may use views to hold
intermediate results).

**d.** Exercise 6.10 (d).

**e.** Exercise 6.15 (b) and (c).

**Problem 3. Normal forms and decomposition.**

**a.** What does the functional dependency X->Y mean?

**b.** How to use functional dependency to determine keys of a
given schema?

**c.** How to use Armstrong's Axioms to obtain that A->BC entails
A->AB?

**d.** Suppose F={A->D, BC->EJ, BD->AE, EJ->G, ADE->H, HD->J}.

1. If X={A,B}, what is the attribute closure X^+_F (read: X superscript +
subscript F)?

2. Is functional dependency AB->C entailed by F? Explain.

3. Is functional dependency AE->G entailed by F? Explain.

**e.** Consider the schema R=(ABCDEFGH, {BE->GH, G->FA, D->C, F->B}).

1. Can there be a key that does not contain D? Explain.

2. Is the schema in BCNF? Explain.

3. Use one cycle of the BCNF algorithm to decompose R into two
subrelations. Are the subrelations in BCNF? Are the subrelations in
3NF?

4. Show that your decomposition is lossless.

5. Is your decomposition dependency preserving? Explain.