基于函数依赖的导出关系候选码计算

Candidate Code Calculation of Derived Relation Based on Functional Dependencies

基于函数依赖的候选码计算在基于压缩策略的快照差分算法、数据一致性检测、数据不一致修复、数据完整性约束等方面有重要的作用。分析选择、并、差、笛卡尔积等基本运算的函数依赖保持性,得出导出关系候选码与原准基础关系候选码的关系,针对投影、广义投影、笛卡尔积和聚集运算候选码可能存在冗余属性的情况,给出相应的算法优化组成候选码的属性。提出一种递归算法对给定的导出关系求出其候选码,运用快照差分算法进行实验,结果表明,运用该算法可以提高增量计算的运行效率。

Candidate code calculation based on the functional dependencies has important uses in many aspects, such as in the snapshot differential algorithms based on the strategy of compression, in the data consistency inspection, in the data inconsistency repairmen and in the data integrity constraints. This paper discusses and analyzes the retaining ability of functional dependence for several basic operations such as selecting, excepting, unions and cartesian product. A conclusion on the relationship between the candidate code of derived relation and the candidate code of the original basic relations is presented. It proposes a corresponding algorithm to optimize the size of candidate attributes for projection,the generalized projection, cartesian product and aggregation operation that may have redundant attributes in their candidate code. An algorithm is proposed that can find out the candidate code for a given derived relation, and experiments are conducted applying into the snapshot differential algorithms. Results show that the algorithm can improve the efficiency of the incremental calculation.