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 |
语种 | 英语 |
出版者 | IEEE-INST ELECTRICAL ELECTRONICS ENGINEERS INC |
WOS记录号 | WOS:000237147400006 |
内容类型 | 期刊论文 |
源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. |
个性服务 |
查看访问统计 |
相关权益政策 |
暂无数据 |
收藏/分享 |
除非特别说明,本系统中所有内容都受版权保护,并保留所有权利。
修改评论