An information-lossless decomposition theory of relational information systems
文献类型：期刊论文
| 作者 | Lee, TT; Lo, TY; Wang, JF |
| 刊名 | IEEE TRANSACTIONS ON INFORMATION THEORY
 |
| 出版日期 | 2006-05-01 |
| 卷号 | 52期号:5页码:1890-1903 |
| 关键词 | bipartite graph commutative partitions entropy running intersection property |
| ISSN号 | 0018-9448 |
| DOI | 10.1109/TIT.2006.872860 |
| 英文摘要 | Relational information systems, systems that can be represented by tables of finite states, are commonly used in many areas such as logic circuits, finite-state machines, and relational databases. Decomposition is a natural method of handling complex systems and removing redundancies. It splits a table into a network of smaller, simpler, and interrelated new tables. In order. to preserve the original features of the system, any valid decomposition must be lossless. Commutative partitions play an important role in the decomposition. The commutative property is essentially a general algebraic formulation of independency of two partitions. We express the interdependency of two commutative partitions by a bipartite graph, and classify the hierarchical independency structures by the topological property of bipartite graphs. In particular, we show that two partitions are decomposable, the strongest version of dependency, if and only if the associate bipartite graph is uniform. We also adopt Shannon's entropy to quantify the amount of information contained in each partition, and formulate the information-lossless decomposition by the entropy conservation identity. Under the assumption of running intersection property, we show that the general formulation of information-lossless decomposition of relational systems is given by the entropy inclusion-exclusion equality. Applications of these formulations to Boolean logic circuits and relational databases are presented to manifest the information-lossless decomposition processes. |
| WOS研究方向 | Computer Science ; Engineering |
| 语种 | 英语 |
| WOS记录号 | WOS:000237147400006 |
| 出版者 | IEEE-INST ELECTRICAL ELECTRONICS ENGINEERS INC |
| 源URL | [http://ir.amss.ac.cn/handle/2S8OKBNM/2755]  |
| 专题 | 中国科学院数学与系统科学研究院 |
| 通讯作者 | Lee, TT |
| 作者单位 | 1.Chinese Univ Hong Kong, Dept Informat Engn, Shatin, Hong Kong, Peoples R China 2.Chinese Acad Sci, Acad Math & Syst Sci, Beijing 100080, Peoples R China |
| 推荐引用方式 GB/T 7714 | Lee, TT,Lo, TY,Wang, JF. An information-lossless decomposition theory of relational information systems[J]. IEEE TRANSACTIONS ON INFORMATION THEORY,2006,52(5):1890-1903. |
| APA | Lee, TT,Lo, TY,&Wang, JF.(2006).An information-lossless decomposition theory of relational information systems.IEEE TRANSACTIONS ON INFORMATION THEORY,52(5),1890-1903. |
| MLA | Lee, TT,et al."An information-lossless decomposition theory of relational information systems".IEEE TRANSACTIONS ON INFORMATION THEORY 52.5(2006):1890-1903. |
入库方式： OAI收割
来源：数学与系统科学研究院
浏览0
下载0
收藏0
其他版本
除非特别说明，本系统中所有内容都受版权保护，并保留所有权利。