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

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