计算机应用 ›› 2015, Vol. 35 ›› Issue (7): 1915-1920.DOI: 10.11772/j.issn.1001-9081.2015.07.1915

• 数据技术 • 上一篇    下一篇

基于增量计算的信息系统属性粒结构计算方法

郝彦彬1, 郭晓2, 杨乃定1   

  1. 1. 西北工业大学 管理学院, 西安710072;
    2. 西安电子科技大学 经济与管理学院, 西安 710071
  • 收稿日期:2015-02-03 修回日期:2015-03-23 出版日期:2015-07-10 发布日期:2015-07-17
  • 通讯作者: 郝彦彬(1976-),男,黑龙江伊春人,讲师,博士研究生,CCF会员,主要研究方向:信息系统、数据挖掘、粒计算,nwpuhyb@163.com
  • 作者简介:郭晓(1981-),女,山东泰安人,讲师,博士,主要研究方向:管理系统工程、风险管理、项目管理; 杨乃定(1964-),男,陕西户县人,教授,博士生导师,博士,主要研究方向:管理系统工程、风险管理、项目管理。
  • 基金资助:

    国家自然科学基金资助项目(71471146)。

Computing method of attribute granule structure of information system based on incremental computation

HAO Yanbin1, GUO Xiao2, YANG Naiding1   

  1. 1. College of Management, Northwestern Polytechnical University, Xi'an Shaanxi 710072, China;
    2. School of Economics and Management, Xidian University, Xi'an Shaanxi 710071, China
  • Received:2015-02-03 Revised:2015-03-23 Online:2015-07-10 Published:2015-07-17

摘要:

针对不可分离信息系统的属性粒结构计算问题,提出一种利用分治和增量计算相结合的计算方法。首先,研究了在信息系统函数依赖集上增加新的函数依赖(FD)后,信息系统属性粒结构的变化规律,证明了信息系统结构增量定理;其次,通过移除部分函数依赖,使不可分离信息系统成为可分离信息系统,利用分解定理计算出可分离信息系统结构;然后,将移除的函数依赖加入可分离信息系统,利用增量定理计算出原信息系统结构;最后,给出了计算不可分离信息系统属性粒结构的算法,分析了算法复杂度。与直接计算不可分离信息系统的粒结构相比,该计算方法可将计算复杂度从O(n×m×2n)降低到小于O(n×k×2n)(k<m),并且当k=1,2时,可进一步降低为O(n1×m1×2n1)+O(n2×m2×2n2)(n=n1+n2,m=m1+m2)。理论分析和实例计算表明,所提方法能有效降低不可分离信息系统属性粒结构的计算复杂度。

关键词: 函数依赖, 属性粒, 信息系统结构, 增量计算, 复杂度

Abstract:

A computational method utilizing divide-and-conquer and incremental computation was proposed to calculate the structure of attribute granule of an inseparable information system. Firstly, the rule that how the structure of attribute granule of an information system changed when new Functional Dependency (FD) was added to the functional dependency set of an information system was studied and the increment theorem of information system structure was proved. Secondly, by removing a part of the functional dependency, an inseparable information system could become a separable information system and the structure of the separable information system was calculated by using decomposition theorem. Thirdly, the removed functional dependency was added to the separable information system and the structure of the original information system was calculated by using increment theorem. Lastly, the algorithm to calculate the structure of attribute granule of inseparable information system was given and its complexity was analyzed. The complexity of the direct calculation of the structure of attribute granule of information system was O(n×m×2n), and the proposed method could reduce the complexity to below O(n×k×2n)(k<m), and when k=1,2, the complexity could be reduced to O(n1×m1×2n1)+O(n2×m2×2n2)(n=n1+n2,m=m1+m2). The theoretical analysis and practical calculation demonstrate that the proposed method can effectively reduce the computational complexity of the structure of attribute granule of an inseparable information system.

Key words: functional dependency, attribute granule, information system structure, incremental computation, complexity

中图分类号: