CS186: Introduction to Database Systems

Homework 6: Functional Dependencies and Schema Refinement

Spring 2003

Redundancy is at the root of several problems associated with relational schemata (schemata is the plural of schema). The problems include redundant storage and insert/delete/update anomalies. This exercise introduces you to a normalization tool called designview, which is distributed with the minibase educational system that accompanies our textbook. Designview allows you to design schemata, identify functional dependencies, isolate sources of potential redundancy, and decide how you want to deal with the redundancy. As you work through this assignment, you will be asked questions; your answers to these questions will form your solution set for this assignment.

Important Notes on the Assignment


Creation of a Relation

Creation of Functional Dependencies

Creation of a Schema

Now that we have defined what attributes and FD's the database contains, we must decide on a schema. To start, we will be simple-minded and simply take all of the attributes in the DB as the only relation. To do this:

Potential problems

With the schema that you have just created there are several problems caused by the functional dependencies. The first set of questions is designed to illustrate these problems.

Consider this possible instance of the above schema:

Lab_Section  TA  Location  Date  SID  Computer_Num 
LAB01 Alex  Soda 271 Wed 7PM  12342154  47A 
LAB01 Alex  Soda 271  Wed 7PM  34561129  47B 
LAB01  Alex  Soda 271  Wed 7PM  84354510  12A 
LAB01  Alex  Soda 271  Wed 7PM   42790843  11C
LAB02  David  Soda 211  Wed 4PM   98234141  13F
LAB02  David  Soda 211  Wed 4PM   42540829  1A
LAB02  David  Soda 211  Wed 4PM   45203758  11B
LAB03 Joe  Cory 251  Tue 8PM  76493235  1A 
LAB03 Joe  Cory 251  Tue 8PM  85105742  1B 
LAB03 Joe  Cory 251  Tue 8PM  24479439  1C 
LAB04 Ana  Soda 211  Mon 7PM  43789821  1A
LAB04 Ana  Soda 211  Mon 7PM  85154940  1B
LAB04 Ana  Soda 211  Mon 7PM  21545428  1C 

Questions on the Original Schema:

  1. Give an example of an anomaly resulting from an update in the TA field.
  2. Give an example of an insertion anomaly that could occur.
  3. What would happen if all the students were to drop the lab section given by David?
Decomposition of the schema can eliminate the above problems!

BCNF Testing & Decomposition in Designview

We learned in class that if all of the relations in a schema are in BCNF, then no redundancies should arise. To test if the Base relation is in BCNF, do the following: (Note that the tool has automatically carried out the decomposition technique we learned in class!)

Testing Properties of the Decomposition

Our next task is to ensure that the decomposition we just performed is lossless-join; if it is not, we will be unable to reconstruct the original relation! Now we must check that the decomposition is dependency-preserving.  If it is not dependency-preserving, it will be expensive to maintain the dependencies.

Completion of the BCNF Decomposition

Continue using the tool in this fashion -- one FD at a time -- to decompose the relation into BCNF. (Note: you only decompose the "leaves" of the decomposition tree.  "Internal nodes" represent relations that have already been decomposed.) As you decompose, the tool is actually checking automatically whether or not your decompositions are lossless-join and dependency-preserving. When you arrive at a schema that is in BCNF, choose Save As from the Session menu, and when prompted for a name for the session, type 'MyBCNF'. Then close the session window by choosing Exit from the Session menu.

Conversion to SQL

In the main designview window, the Base relation should still be visible in an unchanged form. However, designview has remembered your "MyBCNF" decomposition session. To see the SQL commands that create your decomposed tables, select the Base relation and press the Show SQL button. Write down the resulting SQL DDL commands on scratch paper (or cut-and-paste into your favorite editor.)

Unfortunately, designview does not provide all the SQL constraints required to guarantee that dependencies are maintained by the system.

    1. Modify the SQL DDL from designview to guarantee the dependencies.

Automatic Decomposition in Designview

In our previous session, we decomposed Base one FD at a time, to get a BCNF decomposition. Designview can automate these individual steps.  We will try this now:

A 3NF Decomposition

Since the previous decomposition was not dependency-preserving, we will delete it and consider a 3NF decomposition instead.

SQL for the 3NF Decomposition: Using Multiple Saved Sessions

You now have two sessions saved: MyBCNF and My3NF. To choose the default session, press the View Details button in the main designview window. Three extra frames pop up: one for attributes of Base, one for the FDs, and one with a list of Decomposition Sessions. We want to make the My3NF decomposition be the default: Now you can see the SQL for the 3NF decomposition by clicking the Show SQL button.

A Dependency-Preserving, BCNF Decomposition

In general, there is no dependency-preserving BCNF decomposition of every schema. However, it happens that there is a dependency-preserving BCNF decomposition of our schema, even though designview doesn't find it automatically. The final part of this assignment is to find a dependency preserving BCNF decomposition for Base.  You may want to use designview to help you, but you shouldn't rely on it to find the decomposition for you; it probably won't!