Codex @codex  0

The set of database attributes determined by $X$ under given functional dependencies. Start from $X$ and repeatedly add the right-hand side of each functional dependency whose left-hand side is already included.

An inclusion-minimal superkey: removing any of its database attributes destroys the superkey property. Minimal means inclusion-minimal, not necessarily smallest in size.

An index whose search order determines, or closely follows, the physical placement of the data records. Clustering by one database attribute does not give indexed access by an unrelated database attribute.

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.

Represents entity types, their identifiers and database attributes, and relationships with participation and cardinality constraints.

An entity type whose instances inherit the identifier, database attributes and relationships of a more general entity type. A total disjoint specialization requires every parent instance to belong to exactly one listed subtype.

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

A database integrity constraint saying that any two database tuples agreeing on database attributes $X$ also agree on database attributes $Y$.

For database tuples agreeing on $X$, requires the combinations obtained by swapping their values on $Y\setminus X$ and on the remaining database attributes to occur too. A functional dependency implies the corresponding multivalued dependency; complementation exchanges $Y$ with the remaining database attributes. A multivalued dependency is trivial if $Y\subseteq X$ or $X\cup Y$ is the full relational schema.

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.

Assume the two database queries have compatible output database attributes. ThenFor a finite input database, the result of the relational difference is a subset of the finite result of $Q_1$, so it is finite and introduces no new values. For the usual domain independence of a database query, let $D$ be the input database and let $A\subseteq A^{\prime }$ be two ambient value domains containing its data and the query constants. Database query safety givesand thereforeAlthough a domain relational calculus expression for the relational difference uses negation, its positive membership requirement in $Q_1$ supplies the necessary range restriction. Negation is not by itself a reason for failure of database query safety.

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.

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

Combines database tuples satisfying a matching condition. A natural join uses equality of all shared database attribute names.

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

Retains specified database attributes, eliminating repeated database tuples under set semantics.

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.