Representing and processing lineages over uncertain data based on the Bayesian network

- We propose a method to transform the lineage expression into directed acyclic graphs (DAGs) equivalently starting from the lineage expressed as Boolean formulas for SPJ queries over uncertain data. Specifically, we discuss the corresponding probabilistic semantics and properties to guarantee that the graphical model can support effective probabilistic inferences in lineage processing theoretically.
- We propose the function-based method to compute the conditional probability table (CPT) for each node in the DAG. Therefore, the BN for representing the lineage expression over uncertain data, called LBN, can be constructed while generally suitable for both safe and unsafe query plans.
- 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.