Pascal's type system contains a wide range of datastructure notions, including variant records.

Remember that variant records have a component that is common by all records of the type and a variable component that is unique to a subset of records (discriminated through an optional tag field).

Consider the following variant-record type UBtree of unary/binary branching trees:

a

UBtree = record value: integer ; case k: type of unary: UBtree ; binary: record left: UBtree ; right: UBtree end end ;

Explain how problems in the Pascal type system were created by variant records.

Provide an encoding of the UBtree type as a datatype to explain why the aforementioned defects do not exist in SML.

[7 notations]

(c) Explain how function types are expressed in the computer language Scala using an example.

[6 notations]

CST.2008.6.8s8 (TURN OVER)

Databases

(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]

[2 pts] A, C (R S)

iii) B(R) (B(R) B(S)) [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 value.