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

Relational Algebra, SQL Query Sublanguage, Normal Forms

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.