CS145 - Introduction to Databases
Spring 2000, Prof. Widom

Written Assignment #5
Due Wednesday May 17

Problem 1 (recursion)

Recall from Problem 9 in Written Assignment #3 and Problem 1 in Written Assignment #4 the relation Flight(from,to,cost,airline), containing nonstop flights from one city to another. In those problems we were interested in finding the cheapest cost of flying between each pair of cities, regardless of the number of stops. In Assignment #3 we learned that it is not possible to write this query using a single statement of SQL2, and in Assignment #4 we learned that we can compute the answer using SQL2 embedded in a programming language.

(a) Write the query in one statement of SQL3, using the recursive WITH construct.

(b) Can your query for part (a) return tuples where from and to are the same city? If so, what is the cheapest cost of traveling from a city to itself? Modify your solution to part (a) so that no such tuples appear in the query result.

Problem 2 (more recursion)

Consider the relation ParentOf(parent,child) discussed in class, and consider the following WITH statement to compute the Ancestor relation recursively (also discussed in class):

WITH RECURSIVE Ancestor(anc,desc) AS
((SELECT parent as anc, child as desc FROM ParentOf)
UNION
(SELECT Ancestor.anc, ParentOf.child as desc
FROM Ancestor, ParentOf
WHERE Ancestor.desc = ParentOf.parent))
...

(a) Suppose that when we view the tuples in relation ParentOf(parent,child) as a graph (as shown in class), the longest path in that graph has 8 edges. How many times does the query processor need to evaluate a SELECT statement within the UNION before a fixed-point is reached, i.e., before neither of the SELECT statements adds any new tuples to Ancestor?

(b) Now consider the following slightly altered WITH statement that also computes the Ancestor relation recursively:

WITH RECURSIVE Ancestor(anc,desc) AS
((SELECT parent as anc, child as desc FROM ParentOf)
UNION
(SELECT A1.anc, A2.desc
FROM Ancestor A1, Ancestor A2
WHERE A1.desc = A2.anc))
...

Again suppose that when we view the tuples in relation ParentOf(parent,child) as a graph, the longest path in that graph has 8 edges. Now how many times does the query processor need to evaluate a SELECT statement within the UNION before a fixed-point is reached?

Problem 3 (referential integrity)

Give an example of two simple relation schemas R1 and R2 where the PRIMARY KEY of R1 is also a FOREIGN KEY referencing the PRIMARY KEY of R2, and the PRIMARY KEY of R2 is also a FOREIGN KEY referencing the PRIMARY KEY of R1. You may choose any application domain you like, but the relations you choose and the pair of referential integrity constraints should make sense as representations of the real world. Write your table declarations using SQL2 syntax, and include any informal comments needed for us to understand your example.

Problem 4 (constraints)

In class we discussed six types of integrity constraints:

  1. Non-null constraints
  2. Key constraints
  3. Referential integrity constraints
  4. Attribute-based constraints
  5. Tuple-based constraints
  6. General assertions

Consider the following very simple SQL relation declarations:

create table R (A integer, B integer)
create table S (C integer)

Consider each of the following problem parts separately; that is, start "fresh" with the above relation definitions for each one. Use the SQL2 syntax for constraints described in class and in the textbook. You must ensure in each case that the constraint will hold regardless of what modifications are made to the database.

(a) Specify that attribute R.A may not take on the value NULL, in each of the following ways:

(b) Specify that attribute A is a key for relation R, in each of the following ways:

(c) Specify that there is a referential integrity constraint from attribute S.C (the foreign key) to attribute R.A (the primary key), in each of the following ways:

(d) Specify that the value of attribute R.A must be at least 10 and no greater than 20, in each of the following ways:

(e) Specify that for each tuple in R the value of attribute R.A must be at least twice the value of attribute R.B, in each of the following ways:

(f) Specify that for each tuple in R the value of attribute R.A must be smaller than the average of all of the S.C values, in each of the following ways:

Problem 5 (more constraints)

(a) Consider the relation R(A,B) and the functional dependency A -> B. Encode the functional dependency as a constraint expressed in SQL2. You may use any type of constraint that you like (attribute-based, tuple-based, etc.).

(b) Consider the relation R(A,B,C) and the multivalued dependency A ->> B. Encode the multivalued dependency as a constraint expressed in SQL2. You may use any type of constraint that you like (attribute-based, tuple-based, etc.).

Problem 6 (triggers)

Consider a relation Student(ID,major,GPA) and assume that ID is a key.

(a) Consider the following trigger, specified using the FOR EACH ROW option:

CREATE TRIGGER Secret
AFTER UPDATE OF Student ON major
REFERENCING OLD AS O, NEW AS N
WHEN (N.major = 'CS' AND O.major <> 'CS')
UPDATE Student
SET GPA = 1.1 * GPA
WHERE ID = N.ID
FOR EACH ROW

First describe in English what this trigger does. Then write an equivalent trigger that does not use the FOR EACH ROW option.

(b) (Warning - this one does take some thought) Specify another trigger on the Student relation that does not use the FOR EACH ROW option such that an equivalent trigger cannot be written using the FOR EACH ROW option. (Assume that the equivalent trigger is not allowed to introduce temporary variables or tables.) In addition to specifying the trigger in SQL, describe in English what your trigger does.

Problem 7 (views and triggers)

Views in SQL are virtual, meaning that they are not stored in the database but rather their definitions are used to translate queries referencing views into queries over base relations. One disadvantage of this approach is that views may effectively be computed over and over again if many queries reference the same view. An alternative approach is to materialize views: the contents of a view are computed and the result is stored in a database table, so that a reference to the view in a query can simply access the stored table. However, when contents of a base relation referenced in the view change, then the contents of the materialized view must be modified accordingly. For example, consider a base relation R(A,B), where A and B are of type integer and A is a key for R. A materialized view V that contains those tuples of R satisfying R.A > 5 can be created as follows:

CREATE TABLE V (A int, B int)

Initially, V is populated using the following SQL statement:

INSERT INTO V
SELECT * FROM R WHERE A > 5

Now when we refer to view/table V in queries we obtain the desired result.

If an INSERT statement is executed on R, then V must be modified accordingly. This behavior can be implemented using a trigger:

CREATE TRIGGER VinsR
AFTER INSERT ON R
REFERENCING NEW_TABLE AS NT
INSERT INTO V
SELECT * FROM NT WHERE A > 5

(a) Write another trigger VdelR to modify V after tuples are deleted from R.

(b) Write another trigger VupdR to modify V after tuples in R are updated.

(c) Write SQL statements and triggers to create, populate, and maintain a materialized view V that projects columns A and B from a base relation R(A,B,C). You may assume that all three attributes are of type integer and that A is a key for R.

(d) (Optional - answer is long) Write SQL statements and triggers to create, populate, and maintain a materialized view V that is the natural join of base relations R(A,B) and S(B,C). You may assume that all four attributes are of type integer and that R.A and S.C are keys for R and S respectively.