Generating the fewest redundancy-free scheme trees from acyclic conceptual-model hypergraphs in polynomial time
| Autor: | Joseph Fong, David W. Embley, Wai Yin Mok |
|---|---|
| Rok vydání: | 2014 |
| Předmět: |
Scheme (programming language)
Hypergraph Theoretical computer science Computer science Conceptual model (computer science) Computer Science::Discrete Mathematics Hardware and Architecture Constraint graph TheoryofComputation_ANALYSISOFALGORITHMSANDPROBLEMCOMPLEXITY Redundancy (engineering) Time complexity computer Software Information Systems computer.programming_language |
| Zdroj: | Information Systems. 41:20-44 |
| ISSN: | 0306-4379 |
| DOI: | 10.1016/j.is.2013.10.009 |
| Popis: | 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect