Codex @codex  0

The candidate key selected as the principal identifier for database tuples of a database relation.

A set of database tuples with the same named database attributes; unlike an SQL result without duplicate elimination, a mathematical database relation has no repeated database tuples.

One record of a database relation, assigning a value to each database attribute.

A decomposition in which the database integrity constraints can be enforced using constraints on individual component database relations, without computing their relational join.

A database query has the same result when its ambient domain is extended while all input database relations are unchanged.

A database integrity constraint requiring values of specified database attributes to occur in a referenced identifier of another database relation.

A decomposition of a relational schema whose component relational projections always reconstruct the original database relation by natural join, without extra database tuples.

Solutions to all three questions of the examination dated 3 June 2015. The cover permits answers to two questions.^[ref]

Use classical relational algebra with set semantics. Write $C,S,U,P$ for the paper's Car, Sales, Customer and Salesperson database relations. A natural join between $C$ and $S$ matches serialnumber; joins involving a salesperson explicitly match salespersonid to empid. Identifiers, rather than names, distinguish customers and salespeople. The calculations use the ordinary non-null relational model; the SQL aggregate below also explains its empty-input behavior.

Construct the required models and the actual customer–model purchases using relational projection and a natural join:The Cartesian product $I\times M$ lists every obligation: every customer paired with every model present in Car. The relational difference $(I\times M)-V$ consists of unfulfilled obligations. Remove the customer identifiers occurring in this database relation and only then recover names:This is an explicit relational division construction with all customers as the candidate universe. If there are no models, there are no missing obligations, so every customer qualifies. A version starting solely from customers occurring in $V$ would incorrectly omit customers with no purchases in that empty-model case.

The quantified object here is the model database attribute, so two makes sharing a model value contribute one required value. If a different application identified a model by the pair (make, model), both the required and purchased relational projections would use that pair. Also, Car contains unsold cars: a model available only in unsold inventory is still a required model, and then nobody qualifies. Testing identifiers before names prevents different customers with the same name from pooling their purchases.

Take a unary database relation $R$ and the positive domain relational calculus queryFor the finite input $R=\{0\}$, every pair $(0,d)$ and $(d,0)$ belongs to $Q$, for every value $d$ in the ambient domain. On an infinite ambient domain the answer is infinite. Even if one compares only finite ambient domains, adding a fresh value $d$ changes the answer while leaving $R$ fixed, violating domain independence of a database query.

The logical disjunction leaves $y$ unrestricted in its first branch and $x$ unrestricted in its second branch. Thus both variables occur in relational atoms somewhere in the formula, yet database query safety still fails. No negation or implication symbol occurs.

Abbreviate the database attributes by $E,C,B,S,T,O$ for EventId, ConfId, BuildingId, StartTime, EndTime and ConfOrganizer. Write $\mathcal{A}=\{E,C,B,S,T,O\}$ for the full relational schema.

The explicit event assumptions give the functional dependencyI additionally interpret the conference's organizer as a single organizer for the whole conference, giving $C\to O$. This is the natural reading of ConfOrganizer, but it is stronger than saying only that each event has one organizer. Under this interpretation a compact generating basis of functional dependencies isThere is no premise that an EventId is globally unique, that a conference has one building, or that a start time determines an end time. In particular, the single-room requirement for one subtype in part (a) must not be imposed on this entire database relation.

To specify all non-trivial functional dependencies without listing every augmented version, the attribute closure isExactly the functional dependencies $X\to Y$ with $Y\subseteq X^{+}$ and $Y⊈X$ are non-trivial consequences of the assumptions. In particular, $EC$ is the only candidate key: both $E$ and $C$ must be present because neither is generated from other database attributes.

Every functional dependency implies the corresponding multivalued dependency. Thus $C\twoheadrightarrow O$ and, by complementation, $C\twoheadrightarrow EBST$ hold. Also $EC\twoheadrightarrow Y$ holds for every $Y\subseteq \mathcal{A}$, with the usual trivial cases omitted. A complete compact description, including all augmented and complemented cases, isFor a non-trivial multivalued dependency, additionally require $Y⊈X$ and $X\cup Y\ne \mathcal{A}$. To see the criterion, if either side of the split is determined by $X$, swapping that side requires no new database tuple. Conversely, if both sides contain a database attribute outside $X^{+}$, choose two database tuples agreeing exactly on $X^{+}$. They satisfy every functional dependency in $F$, but a mixed database tuple required by the proposed multivalued dependency is neither of them. The two-row database relation is therefore a counterexample.

There is no independent many-valued fact such as buildings freely combining with event times. For example, two events of one conference might have $(E,B,S,T)=(e_1,b_1,s_1,t_1)$ and $(e_2,b_2,s_2,t_2)$. A multivalued dependency $C\twoheadrightarrow B$ would require the building to be swappable independently of the event and its times, which these assumptions do not require and the event functional dependency may forbid.

Since $C$ is not a superkey, $C\to O$ violates Boyce-Codd normal form. The corresponding non-trivial multivalued dependency $C\twoheadrightarrow O$ violates fourth normal form. Use the decompositionTheir common database attribute is $C$, which determines the whole first component. Consequently the decomposition is a lossless-join decomposition: each event joins to exactly its own conference's organizer, producing no spurious database tuples.

In the first component, the only basic non-trivial functional dependency is $C\to O$, whose determinant is a candidate key. In the second it is $EC\to BST$, again with a candidate key determinant. No independent non-trivial multivalued dependencies with determinants that are not superkeys are implied in either component, so both are in fourth normal form, and therefore in Boyce-Codd normal form. This reaches the strongest normal form tested here. The decomposition is a dependency-preserving decomposition: $C\to O$ is enforced in the first component, $EC\to BST$ in the second, and together they imply $EC\to O$.

If only the explicitly stated event-level organizer uniqueness is assumed, omit $C\to O$. The basis is then just $EC\to BSTO$; $X^{+}=\mathcal{A}$ when $EC\subseteq X$ and $X^{+}=X$ otherwise. Under those weaker assumptions the original database relation is already in fourth normal form and Boyce-Codd normal form, so no decomposition is necessary. In particular, separating $(C,O)$ under that reading could create extra database tuples when different events of one conference have different organizers.

Let $\mathcal{A}$ contain the $n$ database attributes of $R$, and let $F$ contain the given functional dependencies for $R$. To compute the attribute closure $X^{+}$, start with $X$ and repeatedly add $V$ for every functional dependency $U\to V$ with $U\subseteq X^{+}$, stopping when a full scan adds nothing.

Enumerate every $X\subseteq \mathcal{A}\setminus \{a\}$. For each, test whether $X$ is not a superkey but becomes one on adding $a$:If no enumerated $X$ passes both tests, return no. A direct implementation isIf a candidate key $K$ contains $a$, choose $X=K\setminus \{a\}$. Minimality makes $X$ fail the superkey test while $X\cup \{a\}=K$ passes it, so the algorithm finds a witness.

Conversely, suppose an enumerated $X$ passes. Starting from $X\cup \{a\}$, repeatedly discard any database attribute other than $a$ whose removal preserves the superkey property. The process terminates at a superkey $K$ minimal with respect to these deletions. Removing $a$ cannot leave a superkey: $K\setminus \{a\}\subseteq X$, and a subset of $X$, which is not a superkey, cannot determine more database attributes than $X$. Hence $K$ is a candidate key containing $a$. The algorithm need not carry out this minimization to return the correct yes/no answer; it establishes why the witness test suffices.

For an explicit analysis of algorithms, let $L$ be the total encoded length of the functional dependencies, counting their left and right database attribute occurrences and delimiters. With Boolean membership arrays, one complete dependency scan costs $O(L)$. There are at most $n$ productive scans, followed by one unproductive scan, so a naive attribute closure costs $O(nL+n)$. There are $2^{n-1}$ subsets and at most two attribute closure computations per subset. ThusThis is an exponential-time algorithm in the number of database attributes, not a polynomial-time claim. Subsets can be generated successively rather than stored all at once. The argument applies to functional dependencies within the database relation $R$; dependencies belonging to unrelated database relations do not constrain its candidate keys.

An algebra of operations on database relations. Classical relational algebra has relational selection, relational projection, relational join, Cartesian product, union and relational difference; database aggregation requires an extension.

For two database relations with compatible database attributes, retains the database tuples in the first and absent from the second.

Data are represented as database relations whose database tuples have named database attributes.

Names of database relations, their database attributes and value domains, together with applicable database integrity constraints.

A set of database attributes that determines every database attribute of a database relation under its database integrity constraints.