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

Research output: Journal Publications and Reviews (RGC: 21, 22, 62)21_Publication in refereed journalpeer-review

3 Scopus Citations
View graph of relations


  • Wai Yin Mok
  • Joseph Fong
  • David W. Embley

Related Research Unit(s)


Original languageEnglish
Pages (from-to)20-44
Journal / PublicationInformation Systems
Issue number1
Publication statusPublished - May 2014


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. © 2013 Elsevier Ltd.

Research Area(s)

  • Acyclic conceptual-model hypergraphs, Conceptual-model-based scheme-tree generation, Data redundancy in scheme trees, Minimal scheme-tree forests