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

Wai Yin Mok; Joseph Fong; David W. Embley

首页> 外文期刊>Information Systems >Generating the fewest redundancy-free scheme trees from acyclic conceptual-model hypergraphs in polynomial time

【24h】

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

机译：在多项式时间内从非循环概念模型超图生成最少的无冗余方案树

获取原文

获取原文并翻译 | 示例

掌桥外文数据库（机构版） >>

开具论文收录证明 >>

文献代查 >>

页面导航

摘要
著录项
相似文献
相关主题

摘要

Generating the fewest redundancy-free scheme trees from conceptual-model hypergraphs is NP-hard. 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.

机译：从概念模型超图生成最少的无冗余方案树是NP-hard。但是，我们表明，如果概念模型超图是非循环的，则该问题具有多项式时间解。我们定义了概念模型超图，周期和方案树，然后提出了多项式时间算法，并证明了该算法生成最少的无冗余方案树。作为该算法的实际应用，我们评论它在设计用于数据存储的“良好” XML模式时的用途。

著录项

来源
《Information Systems》 |2014年第5期|20-44|共25页
作者
Wai Yin Mok; Joseph Fong; David W. Embley;
展开▼
作者单位

Department of Economics and Information Systems, University of Alabama in Huntsville, Huntsville, Alabama 35899, USA;

Department of Computer Science, City University of Hong Kong, Hong Kong, China;

Department of Computer Science, Brigham Young University, Provo, Utah 84602, USA;

展开▼
收录信息美国《科学引文索引》(SCI);美国《工程索引》(EI);
原文格式 PDF
正文语种 eng
中图分类
关键词
Conceptual-model-based scheme-tree; generation; Data redundancy in scheme trees; Minimal scheme-tree forests; Acyclic conceptual-model hypergraphs;

机译：基于概念模型的方案树;代;方案树中的数据冗余;最少的方案树森林;非循环概念模型超图;

相似文献

外文文献
中文文献
专利

1. Generating compact redundancy-free XML documents from conceptual-model hypergraphs [J] . Mok W.Y., Embley D.W. IEEE Transactions on Knowledge and Data Engineering . 2006,第8期

机译：从概念模型超图生成紧凑的无冗余XML文档
2. Extracting a largest redundancy-free XML storage structure from an acyclic hypergraph in polynomial time [J] . Wai Yin Mok, Joseph Fong, David W. Embley Information Systems . 2010,第7期

机译：在多项式时间内从非循环超图提取最大的无冗余XML存储结构
3. A polynomial time approximation scheme for embedding a directed hypergraph on a weighted ring [J] . Li J., Li W., Wang L. Journal of combinatorial optimization . 2012,第3期

机译：用于将有向超图嵌入加权环的多项式时间逼近方案
4. Polynomial Delay and Space Discovery of Connected and Acyclic Sub-hypergraphs in a Hypergraph [C] . Kunihiro Wasa, Takeaki Uno, Kouichi Hirata, International conference on discovery science . 2013

机译：超图中连通和无环子超图的多项式延迟和空间发现
5. A polynomial time algorithm for calculating the probability of a ranked gene tree given a species tree [O] . Tanja Stadler, James H Degnan 2019

机译：用于在给定种类树的情况下计算排名基因树的概率的多项式时间算法
6. Generating the Fewest Redundancy-Free Scheme Trees from Acyclic Conceptual-Model Hypergraphs in Polynomial Time [O] . Wai Yin Mok, Joseph Fong, David W. Embley 2014

机译：在多项式时间内从非循环概念模型超图生成最小的无冗余方案树

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

摘要

著录项

相似文献

相关主题

期刊订阅