面向DATALOG查询的半环溯源计算方法

摘要 数据溯源描述了数据产生和随着时间推移而演变的整个过程，它的应用领域很广，包括增量视图维护、信任评估、概率数据库的查询评估等.本文主要研究面向Datalog查询的半环溯源计算问题.根据半环溯源模型的特点提出一种基于magic的溯源计算方法.之后，针对数据更新的频繁导致半环溯源计算问题，提出一种基于派生树结构的半环溯源计算方法.最后，为了解决半环溯源表示的冗余性尤其是递归导致的形式幂级数溯源形式，提出本质溯源表示形式，该溯源方法表示构成结果元组必不可少的派生路径.最后通过大量实验来验证了本文提出方法的可行性和有效性