An information-lossless decomposition theory of relational information systems

doi:10.1109/TIT.2006.872860

	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.