Characterizations for functional dependency and Boyce-Codd normal form families (Q1069712): Difference between revisions

A functional-dependency family (fd-family) is the set of all instances of a relation that satisfy a given set of functional dependencies \(\Gamma\) and is denoted SAT(\(\Gamma)\). A Boyce-Codd-Normal-Form family (BCNF- family) is an fd-family for a set \(\Gamma\) of key functional dependencies. The paper explores characterizations and closure properties of fd- and BCNF-families. The two main tools for the exploration are closed sets of attributes and agreement sets for collection of instances. A set of attributes X is closed under dependencies \(\Gamma\) if X functionally determines no other attributes. \({\mathcal C}(\Gamma)\) is all the closed sets for dependencies \(\Gamma\). The agreement set Ag(\({\mathcal I})\) for a set of relation instances \({\mathcal I}\) contains all sets of attributes on which some pair of tuples in some relation instance in \({\mathcal I}\) agree. The first group of results relate closure sets and agreement sets. A key result is that the agreement sets for an fd-family are the closed sets of that family's dependencies: \(Ag(SAT(\Gamma))={\mathcal C}(\Gamma)\). The authors also study the smallest fd-family containing an arbitrary set of instances \({\mathcal I}\), denoted \({\mathcal F}({\mathcal I})\). That fd-family can be characterized in terms of Ag(\({\mathcal I})\) closed under intersection. A similar characterization is shown for BCNF-families, but there Ag(\({\mathcal I})\) is closed under subset. The authors next turn to generating \({\mathcal F}({\mathcal I})\) by closure of \({\mathcal I}\) under operations of instances. For fd-families, the necessary operations are subset of an instance, one-to-one renaming of values in an instance, a restricted type of union and partially disconnected augmentation, which adds a tuple of a restricted form to an instance. If \({\mathcal F}({\mathcal I})\) is constrained to be a BCNF-family, the restrictions on the tuple in the last operation are changed slightly. The remainder of the paper discusses when the image of fd-families under a relational algebra operator (or the inverse of an operator) is another fd-family. Closure properties under algebraic operators are useful knowledge for determining the dependencies the answer to a query must satisfy, given the dependencies on the relations being queried. Inverse projection prserves fd-families, but not BCNF-families, while the inverse of a restricted form of projection preserves both. The authors also show how to generate any fd-family or BCNF-family from a finite set of instances using inverse projections and intersection. The most significant results in the paper concern closure under projection. Here, the greatest difference between fd-families and BCNF- families comes out: BCNF-families are preserved under projection while arbitrary fd-families are not. The authors also characterize when the projection of an fd-family is another fd-family, and that characterization provides a decision procedure. Unfortunately, the proofs in this section of the paper depend on the recursively defined relation on tuples that has an almost impenetrable semantics. The authors acknowledge a connection of their relation with tableau operations, a more facile abstraction, and would have greatly aided readers by adopting the latter for their development. The final results of the paper give BCNF-versions of closure properties of fd-families under join and union.