[00145135]关系数据库与信息超图的结构理论

1970年，IBM公司研究员E.F.Codd首次提出关系数据模型，这一理论很快就受到了产业界和学术界的高度重视和广泛响应，并获得1981年图灵奖。20世纪80年代以来，主流的数据库管理系统，例如IBM DB2，Oracle，Microsoft SQL Server等，都基于关系数据库模型。　　在关系数据库中，数据的逻辑结构体现为关系数据库表（relational table）。设计关系数据库模式（schema）的核心问题是数据库的规范化（database normalization），以减少冗余信息，也避免了在插入、删除和更新时的异常操作。本项目围绕数据库规范化中涉及到的结构性问题，取得一系列開创性的成果。主要的研究课题在以下两个方面。　　1.关系数据库的划分格理论　　本项目首次将划分格（Partition Lattice）引入关系数据模型，并以此建立划分格的偏序(partial ordering)与数据依赖性（data dependency）的对应关系，证明了划分格论在关系数据库规范理论中的完备性与科学性。这项工作为日后的粒计算（Granular Computing）奠定了重要的理论基础。自1996年由加州大学伯克利分校的Zadeh教授和圣何塞州立大学T.Y.Lin（林早阳）教授共同提出以来，粒计算己成为近十几年来计算机科学中一个新兴的研究领域。自2005年起，IEEE每年定期举办粒计算的国际会议（IEEE International Conference on Granular Computing）。粒计算的一个基本思想是将信息分类为信息粒，根据其大小与包含关系，信息粒之间将会形成多层次结构，而这种信息分类和层次结构关系可以用本项目所提出的划分格来表达。因此，BISC（The Berkeley InitiatIVe in Soft Computing）粒计算组的T. Y.Lin(林早阳)教授，将本项目所提出的Partition Lattice以及由波兰科学院Pawlak教授所提出的Rough Set并列为信息划分的原创工作，并将之与加州大学伯克利分校Zadeh教授的Fuzzy Set共列为粒计算领域的奠基理论。　　此外，在扩展关系数据模型的应用方面，本项目首先提出通信协议验证与逻辑电路分解的关系代数通解。项目首次将关系代数引入通信协议验证这一课题。随后，前贝尔通讯实验室(Bellcore)的研究员、现任美国Georgetown UnIVersity计算机系主任及讲席教授Ofier Frieder用并行数据库系统实现了此一理论。近期，项目还成功地将关系数据模型应用到逻辑电路功能分解中，并指出关系代数和逻辑代数一样，都是基础的计算模型。这一结果在数字系统设计上有良好的应用价值。　　2.无损分解的熵守恒原理　　针对关系数据模型中的数据依赖，项目创新性地得到信息无损分解的熵守恒条件。项目首先指出：数据库模式的交集关系是一个交闭半格（semilattice），可用代数中的Hasse图表示。基于信息无损分解的无圈模式在Hasse图中拓扑结构，建立其与熵守恒的对应关系。本项目并在2006年于IEEE Trans.Information Theory发表的论文中将划分格和信息熵守恒统一成完整的关系系统的无损分解理论。同时，在无圈模式的熵守恒条件中发现超图的“欧拉不变量”，其后并证明这不变量实际为超图的“欧拉公式”。这项结果得到哈佛大学丘成桐教授(1982年菲尔兹奖，2010年沃尔夫奖获得者)的极度重视，并在其2001年与陈北方教授(香港科技大学)、叶永南教授(台北中央研究院)合撰的论文中，用代数拓朴的同伦论(Homotopy)重新解释了这个重要的结果。本项目在国际期刊上发表文章近二十多篇，为此一研究领域提出许多开创性的基本概念，并结集出版专著“信息超图论”一书。