计算机应用
計算機應用
계산궤응용
Journal of Computer Applications
2015年
7期
1915-1920
,共6页
函数依赖%属性粒%信息系统结构%增量计算%复杂度
函數依賴%屬性粒%信息繫統結構%增量計算%複雜度
함수의뢰%속성립%신식계통결구%증량계산%복잡도
functional dependency%attribute granule%information system structure%incremental computation%complexity
针对不可分离信息系统的属性粒结构计算问题,提出一种利用分治和增量计算相结合的计算方法.首先,研究了在信息系统函数依赖集上增加新的函数依赖(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).理论分析和实例计算表明,所提方法能有效降低不可分离信息系统属性粒结构的计算复杂度.
針對不可分離信息繫統的屬性粒結構計算問題,提齣一種利用分治和增量計算相結閤的計算方法.首先,研究瞭在信息繫統函數依賴集上增加新的函數依賴(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).理論分析和實例計算錶明,所提方法能有效降低不可分離信息繫統屬性粒結構的計算複雜度.
침대불가분리신식계통적속성립결구계산문제,제출일충이용분치화증량계산상결합적계산방법.수선,연구료재신식계통함수의뢰집상증가신적함수의뢰(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).이론분석화실례계산표명,소제방법능유효강저불가분리신식계통속성립결구적계산복잡도.
