different databases

CST.2008.6.8

(a) Define the idea of a safe query in relational calculus.

[2 notations]

(b) Assume we have schemas R(A, B) and S(B, C), where r represents the number of tuples in R and s represents the number of tuples in S.

Assume that neither R nor S are empty and contain no duplicates.

In terms of r and s, state the minimum and maximum number of tuples in the result for each of the following relational algebra queries.

I p(R S)

[2 notations]

(ii) A, C (R S)

[2 notations]

B(R) (B(R) B(S)) (iii)

[2 notations]

(iv) R \s./L S (left outerjoin)

[2 notations]

(v) R \s./ S (full outerjoin)

[2 notations]

(c)

Assume we have the R(A, B) and S schemas (B, C).

No assumptions should be made about functional dependencies.

Let b represent a domain B value.

Consider the following relational algebra problems.

1. A,C (R ./ B=b(S))

A (B=b(R)) B (B=b(S))

3. A and C (A(R) B=b(S)

Two of these queries always get the same result, whereas the third may or may not.

Which one is distinct?

Give a simple database instance where this query produces a different result.

[8 notations]

SECTION C 9 Functional Programming Foundations 8 CST.2008.6.9

(a) Define I -equivalence, (ii) -reduction, (iii) -reduction, and (iv) -term equality.

Syntactic definitions such as F V (free variables), variable swapping, and capture-avoiding replacement may be used.

[8 notations]

(c) Prove or disprove the following equality:

I

z = (x. (y. x y)) (x. y).

[3 scribbles]

(ii) (x. M) ((y. N) P) = (y.(x. M)N)P (M).

[Hint: L. M[L/y] M if y/F V (M).

[4 scribbles]

(b) Demonstrate how the following reduction rule equalizes all -terms:

M N s N M

[Hint: If x / F V (M), you may find it useful to recall (x. M)L = M.]

[5 marks]

9 (FORWARD) 10 Computation Theory

CST.2008.6.10

(a) Describe each of the following phrases:

"c" represents the whole recursive function f: N N.

[2 notations]

"F is a recursively enumerable set whose members are total recursive functions f: N N."

[3 scribbles]

(b) Describe why the set is recursively enumerable in each of the following situations:

I the set A of all total recursive functions a: N N such that a(n + 1) > a for each n N (n).