Generating the fewest redundancy-free scheme trees from acyclic conceptual-model hypergraphs in polynomial time

• Generating a minimal set of redundancy-free scheme trees for a conceptual-model hypergraph is NP-hard.
• An polynomial-time algorithmic solution exists, however, if the hypergraph is acyclic.
• The algorithm ensures that the generated forest of scheme trees is redundancy-free.
• It guarantees that the generated forest of scheme trees collectively covers the information in the given conceptual-model hypergraph.
• It is guaranteed to run in polynomial time.

Generating the fewest redundancy-free scheme trees from conceptual-model hypergraphs is NP-hard [17]. We show, however, that the problem has a polynomial-time solution if the conceptual-model hypergraph is acyclic. We define conceptual-model hypergraphs, cycles, and scheme trees, and then present a polynomial-time algorithm and show that it generates the fewest redundancy-free scheme trees. As a practical application for the algorithm, we comment on its use for the design of “good” XML schemas for data storage.