CS3811 - 2003

Dr. R. Rosebrugh

Current Assignment

General Information

The course meeting time is 9:30MWF in Chem 311. For official detail see the Department Handbook.

The textbook is Introduction to Database Systems by Date. We will cover all of chapters 1--13, and parts of chapters 13-25.

The page for the Ullman-Widom book (including lecture notes) is at http://www-db.stanford.edu/~ullman/dscb.html ; Ullman's slides on optimization in pdf form are here and here.

Check this URL regularly for information about the course.

There will be written assignments, two mid-term tests and a major group project. The first test will be held in class on 2003 February 14; the second test will be held on 2003 March 31.

The Project assignment is at 381103pr.html .

Grades will be assigned using approximately the following weights:


Assignment 1

From the text: 1.5,1.10,2.4,2.5,2.8,3.2. Due January 17.

Please attempt the other text problems before consulting the solutions provided.

Assignment 2

Due January 31 in class.

1. Design a database (give an E/R diagram) for a bank with information about at least 3 entities: customers, accounts and loans. Customers have name, address, phone... Accounts have numbers, types(saving, chequing...), balances... Loans have numbers, types, rates,...
Be sure to define (no more than 4) appropriate relationships also, and include arrows to indicate multiplicity.
Required points: an account can have only one customer; a customer can have a set of addresses.

2. Design a database (give an E/R diagram) for an airport with information about at least 4 entities: hangers, aircraft, runways (including taxiways), gates. As in 1., consider appropriate properties. Be sure to define (no more than 5) appropriate relationships also, and include arrows to indicate multiplicity; indicate at least three constraints.

3. and 4.: For the E/R diagrams you just constructed, give the database schemata (use Tutorial D syntax).

Assignment 3

Due February 14 in class.

1. For the relation scheme R(ABC) let S = { A --> B, B --> C}. Find S+ (you may ignore trivial dependencies).
2. If S = {A --> B, B --> C, C --> A} and T = {A --> BC, B --> A, C --> A} show that S and T are equivalent. Find an irreducible cover for T.
3. For R(ABCD) with dependencies S = {AB --> C, A --> D, BD --> C}
a) find an irreducible cover for S
b) give a 3NF dependency-preserving decomposition of R with only 2 schemes
c) does your answer to a) have a lossless join? (if not, modify your answer to assure this)
d) give 3 examples of update anomalies that can arise if R is not decomposed.
4. For the relation scheme R(SDIM) with dependencies {SI --> D, SD --> M}
a) find all candidate keys of R
b) show that R is 2NF, but not 3NF
c) give an example of an update anomaly that can arise for R

For 4. it might be handy to interpret the attributes as Store, Department, Item, Manager.

Assignment 4

Due March 12 in class.

Consider the following `relation schemes' or relvars (typing ignored)
ENROLL ( S#, C#, Section ) : S# is a student, C# a course
TEACH ( Prof, C#, Section )
ADVISE ( Prof, S# ) : faculty adviser
PRE_REQ ( C#, Pre_C# )
GRADES ( S#, C# , Grade, Year )
STUDENT ( S#, Sname )

1. Draw an ER diagram that might have led to the relations defined.

2. Draw appropriate referential diagrams. (You will need to list appropriate primary and foreign keys). Compare your answer to 1.

3. Write relational algebra queries with the following results:
- all students taking courses with Smith or Jones
- all students taking a course their adviser teaches
- professors who teach more than 1 section of a course
- courses that student `Jon Doe' can enroll in i.e. he has passed prereqs!

4. Write relational algebra expressions with the following results:
- courses and their enrollments by section
- profs, their courses and enrollment totals by section
- student numbers and their GPA

5. Write relational algebra expressions with the following results:
- students in section A of CS1711 all get a B
- pre-1990 grades are eliminated

Assignment 5

Due April 2 in class (but be sure to attempt these problems before the second mid-term test!)

1. Does the relational operator product commute with intersection? With difference? (In each case your answer must be either a proof of equality or a proof that equality fails, i.e. a counterexample.)

2. Show that duplicate elimination commutes with natural join.

3. Does duplicate elimination commute with union? With difference? (Same comment as with 1.)

4. For the relation scheme R(BOSQID)let the dependencies F = { S --> D, I --> B, IS --> Q, B --> O} hold. (It might help to think of an investment firm with Brokers, Offices, Stocks, Quantities(of stock), Investors and Dividends(paid).
a) Find a key for R.
b) How many keys does R have? (prove your answer!)
c) Find a lossles join BCNF decomposition.
d) Find a dependency-preserving, lossless join 3NF