In this paper, the author studies the close relationship that exists between a database schema and a hypergraph. Many of the results in this paper are closely related to the results in [1] and [2]. The main results of the paper concern various types of closures of database hypergraphs. Without getting into too much technical detail of the definitions needed here, we say that the reduction of a hypergraph H is obtained by removing each undirected hyperedge that is a proper subset of another undirected hyperedge. If H equals its reduction, then we say that H is reduced. The closure of H is a reduced hypergraph H⁺ that is equivalent to H such that if H′ is equivalent to H then H′ ≤ H⁺.

In general, the closure may not exist for every database hypergraph. In such cases, the author uses an L-closure H⁻ which is a lower bound of the closure and a U-closure H* which is an upper bound of the closure. H⁻ and H* exist for all hypergraphs and the set of undirected hyperedges of these can be computed in polynomial time. An e-independent hypergraph is equivalent to some independent (i.e., cover embedding) database schema. An e-acyclic hypergraph is equivalent to some acyclic database schema. These two concepts are generalizations of independent and acyclic database schema, respectively.

The notations get very complex quite early. Several examples are provided to illustrate various points. Pertinent results are included in the paper for following the proofs. The major results can be summarized as follows:

( 1 ) If the closure of a hypergraph H exists, then H⁻ ≤ H⁺ ≤ H*.

( 2 ) If H* ≡ H, then H⁺ exists and H⁺ ≃ H*.

( 3 ) If H is independent, then H⁻ = H*.

( 4 ) H is e-independent if and only if H⁺ exists and is independent.

( 5 ) If H is acyclic then H⁻ = H*.

( 6 ) H is e-acyclic if and only if H⁺ exists and is acyclic.

( 7 ) There is a nondeterministic polynomial time algorithm for recognizing whether a hypergraph H is e-acyclic.