Abstract:In the traditional database applications, data is generally considered to be accurate and available. However, data uncertainty often occurs in the real world. Most of current methods usually use provenance information to track data uncertainty while placing focus on the uncertainty with tuple level rather than attribute level. Their main idea is to identify a tuple with a variable, and then construct Boolean expression based on provenance information to compute the probability of a tuple. For the tuple with lots of uncertain attributes, these methods can not help users rapidly and correctly identify the source of uncertainty. In this paper, attribute expressions are defined and used to construct the lineage expression for each result tuple. With the lineage expression, the new method can not only accurately traces the location where the uncertainty takes place, but also computes the probability of the result tuple. Meanwhile, the exchange algorithm of the lineage expression is proposed to guarantee the correctness of the probability computation. In order to improve the efficiency of the probability computation, a method is also provided to construct share paths, and compute the probability of atomic disjunctions during the period of constructing share paths. Experiments are performed to compare tuple level lineage expressions with the existing methods on both time and cost. The results show the feasibility and validity of the proposed method, and further verify the validity of utilizing share paths to speed up the probability computation.