[发明专利]一种最小函数依赖的增量计算方法

摘要

本发明公开了一种最小函数依赖的增量计算方法，该方法根据关系表变化前的最小非平凡函数依赖集、增量数据集、变化前的关系表的划分信息集，增量检测原有的最小函数依赖是否成立，最后确定关系表变化后的最小非平凡函数依赖集。该方法按照元组的操作类型(增加、删除或修改)，进行相应的最小函数依赖的增量计算。由于在实际应用中，数据库变化后，原数据集中的大多数最小函数依赖都是有效的，本发明提出的方法不需要重新计算新数据集的所有最小函数依赖，仅需要计算原最小函数依赖集的新增及删除的最小函数依赖，因此效率较高，且灵活性强，计算结果准确。

主权项

一种最小函数依赖的增量计算方法，其特征在于，包括步骤：(1)选择关系模式为R的初始关系表r进行操作，将增量元组记录到△r中，得到变化后的新关系表rnew；(2)根据增量元组集△r中所有元组操作类型及属性值，修改变化前的关系表的划分信息集Partitions中的划分信息；(3)初始时，令关系表变化后的最小非平凡函数依赖集FDs_new(rnew)等于关系表变化前的最小非平凡函数依赖集FDs_old(r)；(4)从△r中读取一条元组tp；(5)根据元组tp的操作类型，进行最小函数依赖的增量计算，方法如下：(5‑1)如果tp是增加的元组，修改FDs_new(rnew)的步骤如下：(5‑1‑1)读取FDs_new(rnew)中的一条最小函数依赖f，设f：X→Y；(5‑1‑2)判定函数依赖f在rnew中是否成立，若成立，f仍是最小函数依赖，保留在FDs_new(rnew)中，且转步骤(5‑1‑4)；若不成立，在FDs_new(rnew)中删除f，转步骤(5‑1‑3)；(5‑1‑3)对于(5‑1‑2)判定为不再成立的函数依赖：X→Y，判定不在FDs_new(rnew)中的X∪Z→Y在rnew中是否为最小函数依赖，若是，则X∪Z→Y为新增的最小函数依赖，加入FDs_new(rnew)中，其中：“‑”是集合的差运算符，且Z非空；(5‑1‑4)判断FDs_new(rnew)中是否还有未读取的最小函数依赖，若是，则重复步骤(5‑1‑1)～(5‑1‑3)；若否，则进入步骤(6)；(5‑2)如果tp是删除的元组，修改FDs_new(rnew)的步骤如下：(5‑2‑1)读取FDs_new(rnew)中的一条最小函数依赖f，设f：X→Y，(5‑2‑2)若|X|＝1，则f在rnew中仍为最小函数依赖；若|X|＞1，针对所有且Z非空，判断Z→Y在rnew中是否为最小函数依赖，若是，则将其增加到FDs_new(rnew)中，且在FDs_new(rnew)中删除f；若在rnew中不存在Z→Y是最小函数依赖，则判定f在rnew中是否仍为函数依赖，若是，则f在rnew中仍为最小函数依赖；若不是，则在FDs_new(rnew)中删除f；(5‑2‑3)从R中读取一个属性A，采用以下步骤计算其他新增的最小函数依赖：(5‑2‑3‑1)设且X非空}，X为不包含A的非空属性集，L＝1；(5‑2‑3‑2)若C非空，则否则，转(5‑2‑4)；(5‑2‑3‑3)若C′非空，对于C′中的每一元素X，针对不在FDs_new(rnew)中的X→A，判定其是否是最小函数依赖，若是，则将X→A增加到FDs_new(rnew)中，并在C中删除所有X∪Y元素，其中且(5‑2‑3‑4)令L加1；(5‑2‑3‑5)如果C非空，且L<|R|‑1，则重复步骤(5‑2‑3‑2)～(5‑2‑3‑4)；否则，进入步骤(5‑2‑4)；(5‑2‑4)判定R中是否还有没读取过的属性，若是，重复步骤(5‑2‑3)；若否，进入步骤(5‑2‑5)；(5‑2‑5)判断FDs_new(rnew)中是否还有未读取的最小函数依赖，若是，则重复步骤(5‑2‑1)～(5‑2‑4)；若否，则进入步骤(6)；(5‑3)如果tp是修改的元组，对于tp中每一被修改的属性A，设tp表示为：(v1,…,(vA‑old,vA‑new),…,vn)，计算FDs_new(rnew)的步骤如下：(5‑3‑1)如果将(v1,…,vA‑old,…,vn)作为删除元组，按照步骤(5‑2)修改FDs_new(rnew)；(5‑3‑2)如果A∈{Z|X→Y∈FDs_new(rnew)，Z＝X∪Y}，则先将(v1,…,vA‑old,…,vn)作为删除元组处理，按照步骤(5‑2)修改FDs_new(rnew)；再将(v1,…,vA‑new,…,vn)作为增加元组处理，按照步骤(5‑1)修改FDs_new(rnew)；(6)判断△r中是否还存在未读取的元组，若是，重复步骤(4)～(5)；若否，进入步骤(7)；(7)保存FDs_new(rnew)以及rnew的划分信息集Partitions_new；(8)输出FDs_new(rnew)。