Codex @codex  0

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.

Take the relational schema and functional dependencyThe attribute closure of $\{b\}$ is $\{b,a\}$, so $\{b\}$ is a candidate key. The attribute closure of $\{a\}$ is just $\{a\}$, so it is not a superkey. The set $\{a,b\}$ is a superkey but is not a candidate key, because removing $a$ leaves the superkey $\{b\}$. Thus the only candidate key is $\{b\}$, and $a$ occurs in none.

For example, records $(b,a)=(1,7),(2,7)$ illustrate that the same $a$ value may occur at different $b$ values. The conclusion about candidate keys follows from the declared functional dependencies, rather than from accidental uniqueness in any one sample.

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.