TY - JOUR
T1 - Generating the fewest redundancy-free scheme trees from acyclic conceptual-model hypergraphs in polynomial time
AU - Mok, Wai Yin
AU - Fong, Joseph
AU - Embley, David W.
PY - 2014/5
Y1 - 2014/5
N2 - 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.
AB - 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.
KW - Acyclic conceptual-model hypergraphs
KW - Conceptual-model-based scheme-tree generation
KW - Data redundancy in scheme trees
KW - Minimal scheme-tree forests
UR - http://www.scopus.com/inward/record.url?scp=84890454449&partnerID=8YFLogxK
UR - https://www.scopus.com/record/pubmetrics.uri?eid=2-s2.0-84890454449&origin=recordpage
U2 - 10.1016/j.is.2013.10.009
DO - 10.1016/j.is.2013.10.009
M3 - RGC 21 - Publication in refereed journal
SN - 0306-4379
VL - 41
SP - 20
EP - 44
JO - Information Systems
JF - Information Systems
IS - 1
ER -