Representing and processing lineages over uncertain data based on the Bayesian network
Representing and processing lineages over uncertain data based on the Bayesian network
复制标题
基于贝叶斯网络的不确定数据的谱系表示和处理
DOI：
10.1016/j.asoc.2015.07.047
复制
发表时间：
2015
影响因子：
8.7
通讯作者：
Zhu Yunlei
中科院分区：
文献类型：
--
作者：
Yue Kun;Wu Hao;Liu Weiyi;Zhu Yunlei
对不确定数据的处理谱系（也称为起源）在于根据数据产生和演化的过程来追踪不确定性的起源。在本文中，我们重点关注不确定性数据谱系的表示和处理，其中采用流行且重要的概率图模型（PGM）之一贝叶斯网络（BN）作为不确定性表示和推理的框架。从不确定数据上 SPJ（选择-投影-连接）查询的布尔公式表示的谱系出发，我们提出了一种将谱系表达式等效地转换为有向无环图（DAG）的方法。具体来说，我们讨论了相应的概率语义和属性，以保证图模型能够在理论上支持谱系处理中的有效概率推理。然后，我们提出基于函数的方法来计算 DAG 中每个节点的条件概率表（CPT）。用于表示不确定数据上的谱系表达式的 BN，称为谱系 BN，缩写为 LBN，可以构建，同时通常适用于安全和不安全的查询计划。因此，我们给出了基于变量消除的LBN精确推理算法来获得查询结果的概率，称为基于LBN的查询处理。然后，我们专注于获取以查询结果为条件的输入或中间元组的概率，称为基于LBN的推理查询处理，并给出了基于吉布斯采样的LBN近似推理算法。实验结果表明了我们方法的效率和有效性。
Processing lineages (also called provenances) over uncertain data consists in tracing the origin of uncertainty based on the process of data production and evolution. In this paper, we focus on the representation and processing of lineages over uncertain data, where we adopt Bayesian network (BN), one of the popular and important probabilistic graphical models (PGMs), as the framework of uncertainty representation and inferences. Starting from the lineage expressed as Boolean formulae for SPJ (Selection–Projection–Join) queries over uncertain data, we propose a method to transform the lineage expression into directed acyclic graphs (DAGs) equivalently. Specifically, we discuss the corresponding probabilistic semantics and properties to guarantee that the graphical model can support effective probabilistic inferences in lineage processing theoretically. Then, we propose the function-based method to compute the conditional probability table (CPT) for each node in the DAG. The BN for representing lineage expressions over uncertain data, called lineage BN and abbreviated as LBN, can be constructed while generally suitable for both safe and unsafe query plans. Therefore, we give the variable-elimination-based algorithm for LBN's exact inferences to obtain the probabilities of query results, called LBN-based query processing. Then, we focus on obtaining the probabilities of inputs or intermediate tuples conditioned on query results, called LBN-based inference query processing, and give the Gibbs-sampling-based algorithm for LBN's approximate inferences. Experimental results show the efficiency and effectiveness of our methods.