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 journal › peer-review
Author(s)
Related Research Unit(s)
Detail(s)
| Original language | English |
|---|---|
| Pages (from-to) | 20-44 |
| Journal / Publication | Information Systems |
| Volume | 41 |
| Issue number | 1 |
| Publication status | Published - May 2014 |
Link(s)
Abstract
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
Citation Format(s)
Generating the fewest redundancy-free scheme trees from acyclic conceptual-model hypergraphs in polynomial time. / Mok, Wai Yin; Fong, Joseph; Embley, David W.
In: Information Systems, Vol. 41, No. 1, 05.2014, p. 20-44.Research output: Journal Publications and Reviews (RGC: 21, 22, 62) › 21_Publication in refereed journal › peer-review
