Abstract: Lineage analysis over uncertain data will trace the origin of uncertainty of data production and evolution with time passing. In order to reflect the inherent time-series property and the process of data evolution, and support probability inferences and uncertainty tracing in lineage analysis, this paper considers the lineages representation of query processing over uncertain data and adopts Bayesian network (BN), an important probabilistic graphical model (PGM), as the framework for uncertainty representation. Specifically, it extends BN by incorporating the time-series and multi-level properties. To provide the basis of lineage analysis models, this paper starts from the Boolean formulas for describing query processing, and proposes the concept of time-series multi-level probabilistic graphical model, then gives the corresponding method for constructing BN structures in separate time slices and those between adjacent time slices, as well as the method for computing probability parameters of nodes. Experimental results show that the proposed method for lineage representation is effective and applicable.

Key words: uncertain data, lineage representation, probabilistic graphical model (PGM), Bayesian network (BN), time-series multi-level probabilistic graphical model

摘要： 不确定性数据世系分析需要追踪随时间推移数据产生和演化过程中不确定性的起源，为了有效地反映世系本身的时序特征和数据演化过程，并支持世系分析中的概率推理和不确定性追踪，针对不确定性数据查询处理的世系表示，以贝叶斯网这一重要的概率图模型作为不确定性知识表示的框架，并基于世系的时序性和层次性对其进行了扩展。以世系的布尔公式表达式为出发点，提出了涉及连续时间片的时序多层概率图模型的概念，给出了时间片内和连续时间片间贝叶斯网结构的构建方法，以及网络中各结点概率参数的计算方法，旨在为世系分析奠定模型基础。实验结果表明，该世系表示方法是有效、实用的。

关键词: 不确定性数据, 世系表示, 概率图模型, 贝叶斯网, 时序多层概率图模型