不确定性数据管理技术研究综述(4)

关于不确定数据管理的分析与研究

据库提交类似于SQL的查询语句,从而返回查询结果.这其中如何计算查询结果的概率值是一个大的研究问题.

Andritsos等人提出了查询重写技术来处理查询[62].给定一个SPJ查询:“selectA1,…,AnfromR1,…,RmwhereW”,可以将其转化为

大规模应用)往往需面对不精确数据集合,而非精确

的数据集合,包括科学数据管理、传感器数据管理、近似查询处理、隐私保护等[67].例如,一些大型科研项目必须由多个科研小组分工合作完成,一部分小组的任务是制造并记录大量原始实验数据,另一部分学者基于原始数据、外部数据与中间数据进行分析,生成新数据集合,乃至最终获取查询结果.在整个数据演化过程中,各环节所产生的不确定性不断传递、放大,从而能够极大地影响最终查询结果的质量.

Trio的世系[67.(Uncertainty2Line2),,并(complete);提出了执行关系操作[,68].

图8是一个关于犯罪现场数据的世系的例子.图8(a)是目击调查表,张三与李四是两个目击证人,张三看到的可能是宝马或者奔驰,李四看到的是奔驰.图8(b)是驾驶记录表,记录在某个时段内通过某区域的所有宝马与奔驰车辆以及车主.图8(c)是通过上述两个表生成的3项指控记录.例如,指控记录42的世系为(42,1)={(21,2),(32,1)},表示张三指控赵六,证据是目击调查表的记录21的第2项与驾驶记录表的记录32.但由于目击调查表存在不确定性,这项指控本身也存在不确定性.

ID414243

“selectA1,…,An,sum(R1.prob.3…3Rm.prob)fromR1,…,RmwhereWgroupbyA1,…,An”.新的查询语句中包含了结果查询的产生概率值.

Sen和Deshpande等人则利用构建图模型的方法来处理SQL语句[63].数据库上的查询评价问题看作是基于概率图模型上的推断问题.文中应用概率图模型来刻画元组间的相关关系,模型来分解联合概率分布,.研究结果表明,,要么相对于概率数据库是#P2完全问题[41,64].

文献[65]研究了近似查询及其复杂性.5.2　世系分析

数据的世系(lineage或者provenance)是指数据产生并随着时间推移而演变的整个过程[66].现有工作大多针对确定性数据库,但很多应用(特别是超

ID2122

目击调查

(目击者,车型)(张三,宝马)‖(张三,奔驰)

(李四,奔驰)

??

ID3132

驾驶记录

(驾驶员,车型)(王五,宝马)(赵六,奔驰)

指控

(目击者,驾驶员)(张三,王五)(张三,赵六)(李四,赵六)

???

(41,1)={(21,1),(31,1)}(42,1)={(21,2),(32,1)}(43,1)={(22,1),(32,1)}

(a)目击调查表(b)驾驶记录表(c)指控表

图8　一个数据世系的例子

当数据的世系比较复杂时,如何计算查询结果

的概率就成为一件困难的事情.当不考虑概率因素时,可以为某一个数据世系设计多种查询计划,并且得到相同结果.但是当存在概率因素时,不同查询计划返回的查询结果的概率值却可能不同.其原因是在设计查询计划的过程中未考虑到数据的相关性特征,导致重复计算[23].文献[69]提出了一种数据计算与概率计算解偶的技术,使两者可以分开计算,这样一方面概率值可以采用传统的关系型数据库方法进行计算,另一方面,如果用户并不关注查询结果的概率,则可以节约计算概率值的开销.

在一些大型应用(特别是生物数据库)中,元组

的世系可能非常庞大,甚至高达10MB,而其中大部分数据仅对结果产生较小的影响.文献[70]就考虑以高效的方法近似描述一个元组的数据世系.5.3　Top2k查询

面向确定性数据库的top2k查询的定义非常清晰:返回ranking函数值最大的k个元组.但是在不确定性数据库上却存在多种定义方法,例如U2Topk[54]、U2kRanks[54]、PT2k[20]和Pk2topk[36]查

询等.U2Topk查询返回一个长度为k的元组矢量,它在所有可能世界中的发生概率最大;U2kRanks查询返回在各个级别中出现的总概率最大的元组;PT2k首先定义一个阈值p,返回所有在可能世界实

关于不确定数据管理的分析与研究

例中成为top2k的总概率超过阈值的元组;Pk2topk

则返回在所有可能世界实例中成为top2k的总概率最大的k个元组.假设一个不确定数据库含有4个元组,即{t1=(5,018),t2=(6,015),t3=(8,014),t4=(2,014)}.当k=2时,U2topk返回(t2,t1),U2kRanks返回(t3,t1),PT2k返回(t1,t2,t3);当p=013时,Pk2topk返回(t1,t2).

Soliman等人提出了基于搜索空间的方法来处

Lian与Chen等人则考虑了如何在不确定数据

集合上处理reverseskyline查询[76]的问题[77].确定性reverseskyline查询返回在数据库中所有的动态skyline包含给定查询点的数据点.相应的,概率reverseskyline查询(ProbabilisticReverseSkyline,PRS)被定义为:给定一个概率阈值p(0ΦpΦ1)和一个查询对象q,返回所有对象v,使得对象q为v的动态skyline点的概率不低于阈值p.文献[77]将每一个数据对象看作是一个不确定区域,应用确定情形下的BBS算法[78],应用用户定义pPRS点进.55,各元组以概率形式表达不确定性,可以是单一的概率值,也可以是复杂的概率密度函数.数据流模型中,数据到达速率极快,数据量极大,要求设计单遍扫描算法,以低空间复杂度实时处理查询.

传统的面向确定性数据流的方法经过改装之后能够应用于不确定性数据流应用之中.例如,AMSsketch[79]能用于处理聚集查询,特别是F2问题;FMsketch[80]能用于求解数据流上的相异元素个数;ClusterFeature被广泛用于设计各种在线聚类算

理U2Topk查询与U2kRanks查询[54].各元组首先按照ranking函数从大到小进行排序,然后不断地构造搜索空间,缩小空间的范围,最终获得查询结果.Cheng等人针对U2Topk查询提出了一种动态维护的结构,支持元组的插入与删除[71].Hua针对PT2k查询提出了构造dominant集合法[20].在其后续工作中,[.等人[36]k查询处理算法,不仅能够解决上述4,而且是一次遍历算法,能够处理数据流应用.

上述4种查询均可视为是从单个数据库表中获取的数据.Ré等人[73]则研究了在多表之间做连接操作的情况.各个表的数据并不精确,存在不一致性.他们的基本想法是并行地运行多个Monte2Carlo模拟器,每一个对应于一个候选的答案,再计算各个候选答案的近似概率.514　Skyline查询

Skyline查询[74]能用于解决多准则决策(Muli2CriteriaDecision2Making,MCDM)问题.给定一个

法[81282].Cormode等人发展了AMSsketch和FMsketch方法,引入了概率参数,构造了pAMS结构和pFM结构,能够处理不确定性数据流上的相应查询[35].Aggarwal和Yu改进了CF方法,提出了ECF(Error2basedCF)方法,处理数据流上的聚类问题[83].

文献[34]最早在数据流上计算简单的聚集函数,特别是AVG函数.他们的方法比较复杂,主要采用生成函数技术(generatingfunctions),难以进行扩展以解决其它问题.他们的后续工作[84]能够解决更多的聚集查询问题,包括F0和F2,并且提高了AVG函数的查询效率.Zhang等人定义了在不确定性数据流上查询频繁元素的问题,并设计解决方法[85].

Jin等人最早提出了面向滑动窗口模型的查询处理方法[36].如前所述,存在各种top2k查询.他们提出了一种针对top2k查询的框架.首先,可以针对各种top2k查询设计compactset,各个compactset含有一部分数据.这个compactset具有两个特性:(1)能够计算top2k查询结果;(2)能够增量维护.但是compactset仍然不足以回答滑动窗口模型,因此,

确定性的n2维数据集合D,任一点d可被表示为(d.D1,…,d.Dn).Skyline查询返回数据集合S,

SΑD,则Πu∈S,不存在其它 …… 此处隐藏：3682字，全部文档内容请下载后查看。喜欢就下载吧 ……