不确定关系数据属性级溯源表示与概率计算

被引：6

作者：

王梁 ^{[1
]}

周光焱 ^{[1
]}

王黎维 ^{[2
]}

彭智勇 ^{[1
]}

机构：

[1] 武汉大学计算机学院

[2] 不详

来源：

软件学报 | 2014年 / 25卷 / 04期

关键词：

不确定性; 属性表达式; 溯源表达式; 概率计算; 共享路径;

D O I：

10.13328/j.cnki.jos.004426

中图分类号：

TP311.13 [];

学科分类号：

1201 ;

摘要：

传统的数据库应用中,数据往往被假定是精确可用的,而实际中数据普遍存在不确定性.以往许多利用溯源信息追踪数据不确定性的方法往往关注元组或单一属性存在不确定性的情况,通过对元组添加唯一变量标识,用变量标识所表示的溯源信息构造布尔表达式计算结果元组概率.当元组中多个属性存在不确定性时,对元组进行标识不能帮助用户快速而准确地找到造成不确定性的源属性值.定义属性表达式,并通过属性表达式构造溯源表达式.利用该溯源表达式不仅可以准确地追溯不确定性产生的具体位置,同时还可以实现结果元组的概率计算.为保证概率计算结果的正确性,提出溯源表达式的转换算法.通过分析影响结果元组概率计算效率的因素,还提出构建共享路径表的方法,在构建过程中对原子析取式进行预计算,以提高概率计算的效率.实验部分将该方法与现有的元组级溯源信息表示方法在时间代价和空间代价方面进行比较,验证其可行性和有效性.此外,实验部分还对利用共享路径加快结果元组概率计算的有效性进行了评估.

引用

页码：863 / 879

页数：17

共 21 条

[1] Databases with uncertainty and lineage
Benjelloun, Omar
Sarma, Anish Das
Hallevy, Alon
Theobald, Martin
Widom, Jennifer
[J]. VLDB JOURNAL, 2008, 17 (02) : 243 - 264
[2] Supporting fine-grained data lineage in a database visualization environment. Woodruff A,Stonebraker M. Proc.of the Int’’l Conf.on Data Engineering . 1997
[3] A survey of data provenance in e-science
Simmhan, YL
Plale, B
Gannon, D
[J]. SIGMOD RECORD, 2005, 34 (03) : 31 - 36
[4] ProbView[J] . Laks V. S. Lakshmanan,Nicola Leone,Robert Ross,V. S. Subrahmanian. &nbspACM Transactions on Database Systems (TODS) . 1997 (3)
[5] A probabilistic relational algebra for the integration of information retrieval and database systems
Fuhr, N
Rolleke, T
[J]. ACM TRANSACTIONS ON INFORMATION SYSTEMS, 1997, 15 (01) : 32 - 66
[6] A LOCALLY ADAPTIVE DATA-COMPRESSION SCHEME
BENTLEY, JL
SLEATOR, DD
TARJAN, RE
WEI, VK
[J]. COMMUNICATIONS OF THE ACM, 1986, 29 (04) : 320 - 330
[7] Transaction Processing Performance Council (TPC) Benchmarks[S/OL]. http://tpc.org . 2001
[8] 一种基于概率图模型的不确定性数据世系表示方法
岳昆
刘惟一
朱运磊
张伟
[J]. 计算机学报, 2011, 34 (10) : 1897 - 1906
[9] Efficient query evaluation on probabilistic database. Dalvi N,Suciu D. Proc.of the Very Large Data Bases . 2004
[10] Data provenance:A categorization of existing approaches. Glavic B,Dittrich K. Proc.of the 12th Symp.of the German Informatics Society Section"Databases and Information Systems" (DBIS)on Database Systems in Business,Technology and Web . 2007

← 1 2 3 →