Autonomous sets for the hypergraph of all canonical covers

作者：Koehler Henning

来源：Annals of Mathematics and Artificial Intelligence, 2011, 63(3-4): 257-285.

DOI：10.1007/s10472-012-9276-z

• Hypergraph
• Transversal
• Database
• Functional dependency
• Cover

We present a method for decomposing a hypergraph with certain regularities into smaller hypergraphs, in a "direct product"-like fashion. By applying this to the set of all canonical covers of a given set of functional dependencies, we obtain more efficient methods for solving several optimization problems in database design. These include finding one or all "optimal" covers w.r.t. different criteria, which can help to synthesize better decompositions, and to reduce the cost of constraint checking. As a central step we investigate how the hypergraph of all canonical covers can be computed efficiently. Our results suggest that decomposed representations of this hypergraph are usually small and can be obtained rather quickly, even if the number of canonical covers is huge.

• 出版日期2011-12