一种溯源表达式的责任分析方法

摘要

本发明涉及一种溯源表达式的责任分析方法，其包括以下步骤：将溯源表达式分为路径溯源和复合溯源表达式；路径溯源表达式的责任分析方法包括：将复杂路径查询语句分解为简单路径查询语句；对非分解得到的简单路径查询语句，将各子表达式的变量按列排序，完成溯源表达式到溯源图的编译，对分解得到的简单路径查询语句，将其对应的简单路径表进行连接并直接编译成溯源图；将溯源图变换为路径矩阵PM；采用动态规划算法得到最短路径矩阵SPM；结合路径矩阵PM和最短路径矩阵SPM，计算路径溯源表达式中各源元组的责任；通过将复合溯源表达式分解并计算源元组的责任，完成对复合溯源表达式中各源元组的责任分析；采用排序算法对各个源元组的责任从大到小进行排序。

主权项

一种溯源表达式的责任分析方法，其包括以下步骤：1)在不等值查询分类的基础上，将溯源表达式分为路径溯源表达式和复合溯源表达式；2)对于路径溯源表达式，其责任分析方法具体包括以下步骤：Ⅰ)根据不等式的特点，将复杂路径查询语句分解为简单路径查询语句；Ⅱ)对于非分解得到的简单路径查询语句直接生成溯源表达式，溯源表达式表示为：$\Phi ={\Sigma }_{i=1}^m{x}_{i}f\left(x_i\right),$式中，x_i表示源元组，f(x_i)表示所有与源元组x_i有不等关系的源元组；对于由复杂路径查询语句分解得到的简单路径查询语句，将其在数据库中执行，得到查询结果并存储在数据库表中，存储的数据库表称为简单路径表；Ⅲ)对于非分解得到的简单路径查询语句，根据溯源表达式中的包含关系或从变量个数最少的子表达式x₁f(x₁)或x_mf(x_m)开始，将各子表达式的变量按列进行有序排列，直到排列完变量个数最多的子表达式x_mf(x_m)或x₁f(x₁)，完成溯源表达式到溯源图的编译；对于由复杂路径查询语句分解得到的简单路径查询语句，根据溯源表达式中的包含关系或将分解得到的简单路径查询语句对应的简单路径表进行连接并直接编译成溯源图；Ⅳ)将溯源图中每个变量的值设置为1，溯源图变换为m'(m'≤m)行n列的路径矩阵PM；Ⅴ)将路径矩阵PM中PM[0][0]处的结点作为根，采用动态规划算法分别计算根PM[0][0]到路径矩阵PM中其它结点PM[i][j]的最短距离，得到最短路径矩阵SPM，i＝1,2,…m'，j＝1,2,…n；VI)结合路径矩阵PM和最短路径矩阵SPM，计算路径溯源表达式中各源元组的责任；3)对于复合溯源表达式Φ'，其责任分析方法具体包括以下步骤：Ⅰ)将树查询语句和图查询语句均分解为路径查询语句，对每一条路径查询语句 用与步骤1)相同的方法进行责任分析；Ⅱ)假设复合溯源表达式Φ'分解成一组路径溯源表达式Φ'₁，Φ'₂，…，Φ'_k；预设路径溯源表达式Φ'₁，Φ'₂，…，Φ'_l的共同属性为X，且Vars(Φ'₁)∩…∩Vars(Φ'_l)＝{x₁,…,x_m}，其中，2≤l≤k；对于任意，将子溯源表达式x_jf(x_j)从路径溯源表达式Φ'_i中删除；Ⅲ)采用与步骤2)相同的方法递归地计算每一个路径溯源表达式Φ'_i中各源元组的责任，对于复合溯源表达式Φ'中源元组x_j∈X，其责任为：${\mathrm{resp}}_{{\Phi }^{\prime }}\left(x_j\right)=\max ({\mathrm{resp}}_{{{\Phi }^{\prime }}_1}\left(x_j\right),...,{\mathrm{resp}}_{{{\Phi }^{\prime }}_k}\left(x_j\right)).$4)按照从大到小的顺序，采用排序算法对由步骤2)和步骤3)计算得到的各源元组的责任进行排序。