Attribute Level Lineage and Probabilistic Computation of Uncertain Data
Author:
Affiliation:

Clc Number:

Fund Project:

  • Article
  • |
  • Figures
  • |
  • Metrics
  • |
  • Reference
  • |
  • Related
  • |
  • Cited by
  • |
  • Materials
  • |
  • Comments
    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.

    Reference
    Related
    Cited by
Get Citation

王梁,周光焱,王黎维,彭智勇.不确定关系数据属性级溯源表示与概率计算.软件学报,2014,25(4):863-879

Copy
Share
Article Metrics
  • Abstract:
  • PDF:
  • HTML:
  • Cited by:
History
  • Received:September 26,2012
  • Revised:May 03,2013
  • Adopted:
  • Online: March 28,2014
  • Published:
You are the firstVisitors
Copyright: Institute of Software, Chinese Academy of Sciences Beijing ICP No. 05046678-4
Address:4# South Fourth Street, Zhong Guan Cun, Beijing 100190,Postal Code:100190
Phone:010-62562563 Fax:010-62562533 Email:jos@iscas.ac.cn
Technical Support:Beijing Qinyun Technology Development Co., Ltd.

Beijing Public Network Security No. 11040202500063