计 算 机 学 报
C HIN ESE J OU RNAL OF COM PU TERS
Vol.32No.1
Jan.2009
收稿日期:2008209205.本课题得到国家自然科学基金(60803020)、上海市重点学科建设项目(B412)资助.周傲英,男,1965年生,教授,博士生导师,主要研究兴趣为数据管理与信息系统,包括:Web 数据管理、中文Web 基础设施、Web 搜索与挖掘、数据流与数据挖掘、复杂事件处理与实时商务智能、不确定数据管理及其应用、数据密集的计算、分布存储与计算、对等计算及其数据管理、Web 服务计算等.金澈清(通信作者),男,1977年生,博士,副教授,主要研究方向为数据流管理、不确定性数据管理技术等.E 2mail :cqjin @sei.ecnu.edu.cn.王国仁,男,1966年生,教授,博士生导师,主要研究领域为XML 数据管理、生物信息学、分布与并行数据库、多媒体索引技术、并行计算等.李建中,男,1950年生,教授,博士生导师,主要研究领域为数据库、并行计算等.
不确定性数据管理技术研究综述
周傲英1) 金澈清1) 王国仁2) 李建中
3)
1)
(华东师范大学软件学院上海市高可信计算重点实验室 上海 200062)
2)(东北大学信息科学与工程学院 沈阳 110004)
3)
(哈尔滨工业大学计算机科学与技术学院 哈尔滨 150001)
摘 要 随着数据采集和处理技术的进步,人们对数据的不确定性的认识也逐步深入.在诸如经济、军事、物流、金
融、电信等领域的具体应用中,数据的不确定性普遍存在.不确定性数据的表现形式多种多样,它们可以以关系型数据、半结构化数据、流数据或移动对象数据等形式出现.目前,根据应用特点与数据形式差异,研究者已经提出了多种针对不确定数据的数据模型.这些不确定性数据模型的核心思想都源自于可能世界模型.可能世界模型从一个或多个不确定的数据源演化出诸多确定的数据库实例,称为可能世界实例,而且所有实例的概率之和等于1.尽管可以首先分别为各个实例计算查询结果,然后合并中间结果以生成最终查询结果,但由于可能世界实例的数量远大于不确定性数据库的规模,这种方法并不可行.因此,必须运用排序、剪枝等启发式技术设计新型算法,以提高效率.文中介绍了不确定性数据管理技术的概念、特点与挑战,综述了数据模型、数据预处理与集成、存储与索引、查询处理等方面的工作.
关键词 不确定性数据;可能世界模型;数据集成;世系;不确定数据流中图法分类号TP393 DOI 号:10.3724/SP.J.1016.2009.00001
A Survey on the Management of U ncertain Data
ZHOU Ao 2Ying 1) J IN Che 2Qing 1) WAN G Guo 2Ren 2) L I Jian 2Zhong 3
)
1)
(S hanghai Key L aboratory of T rustworthy Com puting ,S of tw are Engineering Institute ,East China N ormal University ,S hanghai
200062)
2)(School of I nf ormation S cience and Engineering ,N ort heastern Universit y ,S heny ang 110004)3)
(School of Com p uter S cience and Technolog y ,Harbin I nstit ute of Technology ,Harbi n 150001)
Abstract The importance of t he data uncertainty was st udied deeply wit h t he rapid develop ment in data gat hering and processing in various fields ,inclusive of economy ,military ,logistic ,fi 2nance and telecommunication ,etc.Uncertain data has many different styles ,such as relational data ,semist ruct ured data ,st reaming data ,and moving object s.According to scenarios and data characteristics ,tens of data models have been developed ,stemming from t he core possible world model t hat co ntains a huge number of t he possible world instances wit h t he sum of probabilities equal to 1.However ,t he number of t he possible world instances is far greater t han t he volume of t he uncertain database ,making it infeasible to co mbine medial result s generated from all of possi 2ble world instances for t he final query result s.Thus ,some heuristic techniques ,such as orde 2ring ,p runing ,must be used to reduce t he comp utatio n co st for t he high efficiency.This paper in 2t roduces t he concept s ,characteristics and challenges in uncertain data management ,proposes t he advance of t he research on uncertain data management ,including data model ,preprocessing ,in 2tegrating ,storage ,indexing ,and query p rocessing.
K eyw ords uncertain data ;possible world model ;data integration ;lineage ;uncertain stream
1 引 言
近四十年来,传统的确定性数据(deterministic
data )管理技术得到了极大的发展,造就了一个数百亿的数据库产业.数据库技术和系统已经成为信息化社会基础设施建设的重要支撑.在传统数据库的应用中,数据的存在性和精确性均确定无疑.近年来,随着技术的进步和人们对数据采集和处理技术理解的不断深入,不确定性数据(uncertain data )得到了广泛的重视.在许多现实的应用中,例如经济、军事、物流、金融、电信等领域,数据的不确定性普遍存在,不确定性数据扮演着关键角色.传统的数据管理技术却无法有效管理不确定性数据,这就引发了学术界和工业界对研发新型的不确定性数据管理技术的兴趣.
不确定性数据的产生原因比较复杂.可能是原始数据本身不准确或是采用了粗粒度的数据集合,也可能是为了满足特殊应用目的或是在处理缺失值、数据集成过程中而产生的.
(1)原始数据不准确.这是产生不确定性数据最直接的因素.首先,物理仪器所采集的数据的准确度受仪器的精度制约.其次,在网络传输(特别是无线网络传输)过程中,数据的准确性受到带宽、传输延时、能量等因素影响.还有,在传感器网络应用[122]与RFID 应用[3]等场合,周围环境也会影响原始数据的准确度.
(2)使用粗粒度数据集合.很明显,从粗粒度数据集合转换到细粒度数据集合的过程会引入不确定性.例如,假设某人口分布数据库以乡为基础单位记录全国的人口数量,而某应用却要求查询以村为基础单位的人口数量,查询结果就存在不确定性.
(3)满足特殊应用目的.出于隐私保护等特殊
目的,某些应用无法获取原始的精确数据,而仅能够得到变换之后的不精确数据.
(4)处理缺失值.缺失值产生的原因很多,装备故障、无法获取信息、与其他字段不一致、历史原因等都可能产生缺失值.一种典型的处理方法是插值,插值之后的数据可看作服从特定概率分布.另外,也可以删除所有含缺失值的记录,但这个操作也在一定程度上变动了原始数据的分布特征.
(5)数据集成.不同数据源的数据信息可能是不一致的,在数据集成过程中就会引入不确定性.例如,Web 中含很多信息,但是由于页面更新等因素,许多页面的内容并不保持一致[4].
对某些应用而言,还可能同时存在多种不确定性.例如,基于位置的服务(Location 2Based Service ,LBS )[5]是移动计算领域的核心问题,在军事、通信、交通、服务业等方面有着广泛的应用.LBS 应用获取各移动对象的位置,为用户提供定制服务,该过程存在若干不确定性.首先,受技术手段(例如GPS 技术),移动对象的位置信息存在一定误差.其次,移动对象可能暂时不在服务区,导致LBS 应用采集的数据存在缺失值情况.最后,某些查询要求保护用户的隐私信息,必须采用“位置隐私”等方式处理查询[6].
实际上,针对不确定性数据的研究工作已经有几十年历史了.从20世纪80年代末开始,针对概率数据库(probabilistic database )的研究工作就从未间断过[7211].这类研究工作将不确定性引入到关系数据模型中去,取得了较大进展.近年来,针对不确定性数据的研究工作则在更广的范围内取得了更大的进展,即在更丰富的数据类型上处理更多种类的查询任务.图1描述了不确定性数据管理技术的典型框架,它包含4大部分:模型定义、预处理与集成、存储与索引和查询分析处理
.
图1 不确定性数据管理的框架
模型定义.定义与应用场景相匹配的数据模型
是不确定性数据管理的首要任务.在不确定性数据管理领域,最常用的模型是可能世界模型(possible world model )[12213].该模型从一个不确定性数据库演化出很多确定的数据库实例(称为可能世界实例),而且所有实例的概率之和为1.不确定性数据的种类较多,例如关系型数据、半结构化数据、流数据、移动对象数据等,尽管存在许多与数据类型紧密相关的数据模型,但是这些模型最终都可以转化为可能世界模型.
2计 算 机 学 报2009年
存储与索引.有效的存储和索引技术能够大幅提高数据管理效率.尽管可以基于传统的关系型数据存储技术实现不确定性数据库的存储任务,但仍有必要开发新型存储技术,以提高特定查询任务(例如数据世系,data lineage)的执行效率.概要数据结构(synop sis data struct ure)是存储流数据(data st ream)[14215]的典型技术.不确定性数据与确定性数据的最大区别在于不确定性数据含有概率维度.一部分查询任务仅使用基于非概率维度的索引.例如,在处理不确定Top2k查询的过程中,往往只需对值维度以ranking函数创建索引.另一类查询则需针对概率维度开发新的索引技术,例如,范围查询(Range query)、最近邻查询(Nearest Neighbor query)等.当概率维度以概率密度函数(p robabilis2 tic density f unction,简称p df)描述而非概率值时,创建索引的难度更大.
查询分析处理.查询分析处理是不确定性数据管理的最终目标.查询类型非常丰富,例如关系查询操作、数据世系、XML处理、流数据查询、Ranking 查询、Skyline查询、OL A P分析、数据挖掘等.尽管可以分别针对各个可能世界实例计算查询结果,再合并中间结果以生成最终查询结果,但由于可能世界实例的数量远大于不确定数据库的规模,该方法并不可行.因此,必须采用排序、剪枝等启发式技术优化处理,以提高效率.另外,由于输入数据具有不确定性,查询结果也往往是近似结果.
目前在研的主要项目
不确定数据管理正成为一个研究热点.表1列举了一些知名大学以及公司的研究机构正在进行的相关科研项目的基本情况.
表1 不确定性数据管理的相关研究项目
科研机构项目名称链接地址描述
University of Puget Sound pro TDB http://www.mat h.ups.edu/～
anierman/umich/protdb/
主要研究概率半结构化数据的查询处理技术.
University of Toronto Conquer http://queens.db.toronto.edu/
project/conquer/
主要研究针对不一致数据库(inconsistent database)的高效管
理技术.主要应用查询重写技术、实时和动态数据清洗技术.
Purdue University Orion http://orion.cs.purdue.edu/曾用名:U2DBMS,是一个通用目的的不确定性数据库系统.它支持离散或连续的概率密度函数;高效的访问不确定性数据的方法;优化连接、选择等操作;图形可视化界面.
Stanford University Trio http://infolab.stanford.edu/trio/主要研究不确定数据管理技术,特别是针对不确定数据的世系分析技术.它基于ULDB模型,使用TriQL语言.
Cornell University MayBMS http://www.cs.cornell.edu/da2
tabase/maybms/
研究内容包括:查询语言、表示与存储技术、支持数据清洗、
高效的查询处理、更新等.
University of Washington MystiQ http://www.cs.washington.edu/
homes/suciu/project2mystiq.html
研究内容包括:数据模型、查询处理技术、关系代数计算等.
Intel/Berkeley HeisenData http://www.eecs.berkeley.edu/
Research/Project s/Data/102060.
ht ml
该项目试图将现有的确定性数据管理框架与不确定性查询
处理技术相结合,从而使得新增的功能模块能够嵌入到现
有框架中,增强其性能.
University of Maryland Prob DBs http://www.cs.umd.edu/～vs/
research.ht m#pdb
研究概率聚集查询的计算方法,开发空间2时间概率数据库.
IBM Almaden Avatar http://www.almaden.ibm.com/
cs/project s/avatar/
该项目有两大目标:(1)从非结构化数据中抽取结构化的信
息;(2)基于这类信息构建下一代搜索和商业智能应用.
Ré与Suciu[16]观察到不确定性数据广泛出现在诸多应用之中,并总结了不确定性数据管理所面临的巨大挑战.Dalvi和Suciu[17]进一步从理论角度阐述不确定性数据管理的基础与挑战.Aggarwal 与Yu[18]从算法与应用角度综述了不确定数据管理技术.Pei等人[19]回顾了近期不确定性查询处理方面的进展,特别是他们自己的工作,包括范围查询、skyline查询与Ranking查询等.本文则以不确定性数据管理的框架为主线,综述了不确定性数据管理技术在数据模型、预处理与集成、存储与索引、查询分析处理等方面所取得的重要进展.本文第2～5节分别介绍上述4个方面的内容;第6节总结全文.
3
1期周傲英等:不确定性数据管理技术研究综述2 数据模型与挑战
2.1 可能世界模型
不确定数据库建模的研究工作很多,可能世界模型则是应用最广泛的数据模型[12213].在该模型中,各元组的任一合法组合均构成一个可能世界实例(instance),实例的概率值可以通过相关元组的概率计算得到.可能世界实例的数量远远高于不确定性数据库的规模,甚至是后者的指数倍,这也是不确定性数据管理技术所面临的最大难点.考虑如图2所示的一个例子.图2(a)是一个不确定性数据库,包含3个元组,概率字段表示该元组的发生概率.元组之间可能也可能存在依赖关系.首先假设各个元组之间,则共有23=8个可能世界实例,各实例的概率等于实例内元组的概率乘积与实例外元组的不发生概率的乘积,如图2(b)所示.例如,可能世界实例{1,2}的发生概率为013×017×(1-016)= 01084.某些场景下,元组之间并非,而是存在依赖关系,这种依赖关系可以用规则描述.假设规则为1 3,即元组1与元组3不能够同时发生,但可以同时不发生[20].总共有6个可能世界实例,如图2 (b)所示.可能世界实例{1}的发生概率为013×(1-017)=0109,可能世界实例{2}的发生概率为(1-013-016)×017=0107.
ID信息概率1A013 2B017 3C016元组:
PW={{},{1},{2},{3},{1,2},{1,3},{2,3},{1,2,3}} P(PW)={.084,.036,.196,.126,.084,.054,.294,.126}依赖规则:1 3
PW={{},{1},{3},{2},{1,2},{2,3}}
P(PW)={.03,.09,.18,.07,.21,.42}
(a)一个不确定数据库样例(b)可能世界
图2 可能世界样例
在大多数应用中,不确定性可细分为存在级不确定性(Existential Uncertainty)和属性级不确定性(Attribute Level Uncertainty).存在级不确定性描述元组的存在与否,较为普遍.在图2中,各元组均具备存在级不确定性.属性级不确定性并不涉及整个元组的不确定性,而是以概率密度函数或统计参数(例如方差等)来描述特定属性的不确定性.例如,假设某传感器无法准确探测周围环境温度,典型的记录方式为:70%的概率为26℃,30%的概率为25℃.类似的记录均具有属性级不确定性.属性级不确定性往往比存在级不确定性更容易处理.有些时候,也可以将多个相关的元组视为单个含属性级不确定性的元组.例如,图2(b)定义了依赖规则1 3,则元组1和3无法同时发生.可以将这两个元组视为单个元组,该元组有存在级不确定性,发生概率为019;该元组的信息字段有属性级不确定性,由离散概率密度函数描述(信息=A的概率为1/3,信息=C的概率为2/3).
作为不确定性数据库建模的最核心思想,可能世界模型被广泛采纳于各种应用之中,并衍生出多种应用相关的模型,特别是针对关系型数据、半结构化数据、流数据和数据的模型.
2.2 针对关系型数据的模型
针对关系模型的扩展最为常见,包括Probabi2listic?2table[9,11]、Probabilistic or2set table[11]、Proba2 bilistic or2set2?table[11]、Probabilistic c2table[13]等.
Probabilistic?2table以一个的概率字段表示元组的概率,且各元组之间.一个特定的数据库实例(也即可能世界实例)的概率等于其所包含的元组的概率乘积和其所不包含的元组的不发生概率的乘积.图3(a)所示的Probabilistic?2table含3个字段c1、c2与概率字段,其中概率字段描述元组的发生概率.该表中有2个元组,可构成4个可能世界实例.Probabilistic?2table能够描述存在级不确定性,而Probabilistic or2set table则倾向于描述属性级不确定性.在Probabilistic or2set table中,元组的属性值被描述为多个候选值之间的“或”关系,可视为离散概率密度函数.以图3(b)为例,元组1的c2字段既可取2,也可取3,其概率分别为014和016;元组2的c2字段既可取4也可取5,其概率分别是012与018.Probabilistic or2set2?table[13,21]则是上述两种模型的综合体.例如,在图3(c)中,元组2本身具有概率值,而且其c2字段既可取4,也可取5,概率分别是012和018.Probabilistic c2table的定义与Probabilistic or2set table比较类似,不同之处在于它是从c table衍生而出[22].部分学者也将p robabilistic or2set2?table命名为x2relation,它包含若干x2t uple(无存在级不确定性)或者maybe x2t uple(有存在级不确定性)[8,23].
4计 算 机 学 报2009年c1c2概率12.5 23.6c1c2
1(〈2,.4〉,〈3,.6〉)
2(〈4,.2〉,〈5,.8〉)
c1c2概率
1(〈2,.4〉,〈3,.6〉)
2(〈4,.2〉,〈5,.8〉).8
(a)Probabilistic?2table(b)Probabilistic or2set table(c)Probabilistic or2set2?table
图3 基于关系数据的扩展模型
2.3 针对半结构化数据的模型
半结构化数据模型(semist ruct ured data mod2 el)能有效描述缺乏严格模式结构的数据[24].半结构化数据通常可以用文档树来描述.Dekhtyar等人[25]提出了一种管理概率半结构化数据(p robabilistic semist ruct ured data)的方法,该方法以关系数据库技术为基础,支持丰富的代数查询.更多的工作则是直接以文档树形式描述不确定性半结构化数据,例如p2文档模型(p2document model)[26]、概率树模型(Probabilistic t ree model)[27228]、PXDB模型[29]等.
p2文档模型[26]将概率值附加于文档树的边上,各节点的概率依赖于其祖先的概率,节点之间可以是互斥关系(mux)或相互(ind).在图4(a)所示的例子中,共有5个节点,4条边.边A2B与A2C,概率值分别为017和018;边C2D与C2E互斥,概率值分别为014与015.此时,包含且仅包含节点A、C、D的子图的概率为(1-017)×018×014= 01096;任意子图均不能同时包含D、E两个节点
.
图4 常用的不确定性XML模型
概率树模型是一个事件驱动的模型[27228].它并
不在各节点/边上附加概率值来描述不确定性,而是
在各节点附加一系列事件变量,由外部事件的发生
与否决定节点的存在性.图4(b)描述了一个概率树
的例子,共有2个外部事件w1和w2,其发生概率分
别为017和018.节点B出现的前提条件是事件w1
发生且事件w2不发生;节点E存在的前提条件是事
件w2发生.由于节点B与E的存在条件互斥,不存
在同时包含节点B、E的子图.包含且仅包含A、C、
D3个节点的子图的概率为(1-018)×(1-017)=
0106,前提是w1、w2均不发生.可以看出,概率树模
型的表达能力强于p2文档模型.
PXDB模型[29]扩展了p2文档模型,增加外部约
束条件.在图4(c)所示的例子中,左下角是一个完
整的p2文档;右下角定义了两个子图S A与S A B,S A
含节点A,S A B含节点A与B.条件为:对于任
意一个S A子图,它所包含的S A B子图的数量不能够
超过1个.因此,尽管A2B边在p2文档中出现了2
次,但它们无法同时出现在任意一个子图之中.
其他模型还包括PXML模型[30231]、Keulen等
人的概率树模型[32]、PrXML模型[33]等.
2.4 针对数据流的模型
在数据流模型中,数据到达的速度极快、数据规
模极大,仅能够开发一次扫描算法,使用有限内存在
线计算查询结果.在不确定性数据流(Uncertain
Data Stream,或Probabilistic Data St ream)中,各
元组具有不确定性.文献[34]假设各元组可以在一
个离散域B中取多值,流上各元组的值是基于这些
离散域的一个概率密度函数,例如某元组t被描述
为(〈i1,p1〉,…,〈i m,p m〉),则Π1ΦsΦm,有i s∈B,
Pr[i s]=p s,且∑
m
1
p sΦ1.例如,考虑一个温度传感
器产生的数据流,环境温度范围(离散域B)是
[-30,50],则可能的数据流为{(〈20,014〉,〈22,
016〉),(〈22,018〉),(〈21,012〉,〈23,017〉),…}.部分
学者将研究重点放在一个基本特例,即m=1[35].
根据窗口定义不同,数据流模型可细分为界标
模型、滑动窗口模型.界标模型的范围从某固定时间
5 1期周傲英等:不确定性数据管理技术研究综述点至当前时间为止,滑动窗口模型仅考虑最新的W 个元组[36].在各模型中,新元组的到达与旧元组的消逝均引发可能世界实例的大变迁.以上面的环境温度数据流为例,假设窗口大小W=2,在时间点2时,需基于元组(〈20,014〉,〈22,016〉)和(〈22,018〉)构造可能世界实例,并回答查询;在时间点3时,则基于元组(〈22,018〉)和(〈21,012〉,〈23,017〉)构造可能世界实例,并回答查询;依此类推.
另外,在多数据流应用中,不同数据流上到达的元组之间可能存在相关性,必须整体考虑[37].
2.5 针对数据的模型
OL A P提供了一种数据分析手段,能够快速得到复杂的查询统计结果.OLA P中数据立方(Data Cube)的基本元素是cuboid.在确定性数据模型中,各个事实(fact)必定属于某一个立方体中.但对于处理不精确数据的应用而言,各事实可能无法被准确地定位到立方体中.例如,考虑一个有关汽车销售的数据模型,它包括两个维度:city与automobile,分别表示购车城市与车体型号.city维度是一个三级层次结构,国家→省→市.若仅仅知道某辆“奔驰车”是从“浙江北部城市”购买的话,由于“浙江北部城市”包含多个城市,该条记录是不确定性数据,无法存放到事实表中去.文献[38239]提出了基于可能世界的数据模型,以处理这类不确定数据.在这种模型中,上述记录能够被存储于不确定性数据库中,可以基于可能世界语义执行OL A P 操作(例如切块、上卷等).他们的后续工作也考虑到了元组之间存在相关性的情况[40].
2.6 要求与挑战
不确定数据管理技术采用与确定性数据管理技术截然不同的数据模型,这使得不确定性数据管理技术面临以下挑战:
(1)庞大的可能世界实例集合
毫无疑问,不确定性数据管理所面临的最直接的挑战就是其相对于数据库规模呈指数倍的可能世界实例的数量.假设某不确定性数据库含N条元组,各元组.当该数据库仅有存在级不确定性,可能世界的数目将达到2N个;而若各个元组还拥有属性级不确定性时,可能世界的数目将远大于2N.如果查询要求访问所有的可能世界时,则这个查询开销将会是一个#P问题[41].因此,需要在查询的准确度与查询开销之间进行权衡,目标是以较小的计算开销获得高质量的近似结果.
(2)新出现的维度———概率维
概率在不确定性数据管理中扮演多重角色.输入数据可能有概率,表示元组自身或者某字段具有不确定性;输出结果可能有概率,表明该项结果的发生概率;查询定义可以有概率,用于约束查询结果;处理过程也与概率紧密相关.因此,概率维的出现极大地改变了传统的数据处理模式,迫切需要开发新技术进行处理.
(3)不确定性数据管理的理论问题
在不确定数据库管理技术方面仍然存在大量具体问题,特别是理论相关的问题[42].在高效计算复杂条件下的聚集查询(例如含有HAV IN G谓词的聚集查询)处理起来困难较大.灵活的约束条件能够提高数据质量,是不确定性数据管理的重要工具,但是当前仍不具备普遍接受的约束条件定义方式.
3 数据预处理和数据集成
数据预处理与集成是很多数据管理应用不可或缺的组成部分.在传统数据管理领域,数据预处理是针对不准确、不精确的数据进行数据清理、数据转换等处理,从而提升数据质量,最终能够被确定性管理技术所处理.例如,由于多种原因,RFID读卡器的能够正确读取RFID标签的概率约为60～70%左右,即超过30%的数据被误读了[43].数据误读的原因很多,包括漏读、多读、脏数据等.因此,RFID应用的一大关键模块就是数据清洗模块,它将这些不准确的数据转化为准确的数据,再进行后续处理.这种方法被广泛应用于面向不精确数据的数据管理领域.该方法的不足之处主要有两点,首先,从不精确数据到精确数据的转换过程会损失原始数据的部分特征,无法准确反映原始数据的全貌;其次,一种数据清洗技术往往针对特定的原始数据(例如,漏读产生的数据集合),而非对所有数据集合均有效,这使得直接将数据清洗技术从一个应用搬到其他应用的难度加大[3].
数据预处理也包括将准确数据(或者高精度数据)转化为不精确的数据,从而达到隐私保护等特殊目的,典型的例子是基于位置的服务LBS.作为移动计算领域的核心问题,LBS在军事、通信、交通、服务业中均获得广泛应用.服务器利用GPS等技术获取移动对象的实时位置信息,并提供相应的服务. GPS技术能够获取精度较高的位置信息,恶意用户完全能够根据某移动对象的运动轨迹推测出一些有
6计 算 机 学 报2009年
用的信息.例如,若某个对象每天早上沿相同路径移动,则一般来说起点就是家庭地址,而终点则是工作单位地址.
k 2匿名模型(k 2anonymity model )能够解决这
种隐私保护问题[6].该模型最早应用于关系模型,关系中的属性被划分为准标识符(quasi 2identifier )和敏感属性(sensitive att ribute ),使得任一准标识符至少包括k 个不同元组.位置k 2匿名(location k 2anonymity )则是k 2匿名模型在移动对象数据库上
的扩展,当某消息被发送时,变换消息的空间信息,使其无法与其他k -1条不同消息区分开来[44].
Abul 等人[45]定义了(k ,δ
)2匿名问题((k 2δ)2ano 2nymity p roblem ),在任一时刻,总能够找到k 个对
象,聚集在半径为δ的圆内,作者同时提出了N WA 方法进行求解.
数据预处理还包括从原始的不确定数据库中构造一个新数据集合,并在此集合上计算查询结果.这个做法会降低查询结果的准确度,但是能够提高查询处理的效率[46].
数据集成是管理多自治与异构数据源的应用所需面对的普遍挑战[47].当前的数据集成系统仅是传统数据库的扩展,查询以结构化格式定义,数据以传统模型建模,例如关系模型和XML 模型等.此外,系统也知道原始数据映射到中间模式的确切规则.然而,这些系统无法管理不确定性数据.Philippi 和K ohler [48]认为,针对生命科学数据库的数据集成系
统的最大挑战在于数据的不精确性:数据没有统一的概念模式,数据不完整,缺乏部分信息,且有不确定性.事实上,这种情况也在其他许多领域广泛存在.
Xin 等人最早研究了针对不确定性数据库的数
据集成系统,他们认为一个数据集成系统需要在三个层次上处理不确定性[49]:不确定性数据源、不确定性模式映射、不确定性查询.系统的基本框架结构如图5所示
.
图5 面向不确定数据的数据集成系统架构
(1)不确定性数据源.不确定性数据源是该数
据集成系统最直接的动力.很多情况都可能产生不确定性数据.例如,当数据从非结构化数据源或者半结构化数据源中自动抽取出来时,会引入不确定性;当数据从某些不可靠的或者过时的站点获取时,也会引入不确定性.
(2)不确定性模式映射.数据集成系统利用模式映射技术从多个原始数据源的模式构造中介模式(mediated schema ),再利用中介模式回答查询.事实上,中介模式也可能存在不准确性.原因很多,①用户并非熟练地进行精确映射管理,比如在个人信息管理中;②对某些字段的理解不充分,因此无法正确映射,例如生物信息;③超大数据规模阻止了产生和维护精确映射的可能,例如Web 数据集成.实际应用中,中介模式往往通过半自动化工具生成,而非由领域专家特别指定.
(3)不确定性查询.查询也可能具备不确定性.特别是在Web 应用中,查询往往以“关键词”形式被提交,而并非一个定义规范的结构化查询.系统需要将这些查询转化成某些结构化形式,使得它们能够在这些数据源上重新定义.在这个步骤,系统可能会产生多个候选的结构化查询,并且拥有一些不确定性.
4 存储和索引
目前,传统的关系型数据存储技术仍然是实
现不确定性数据库的存储任务的主流技术.例如,Orion 项目[50]由C 语言和PL/p gSQL 实现,运行于Po st greSQL 之上;MystiQ 项目[51]具有较好的层次结构,支持Post greSQL 、Sql Server 、DB2等关系型数据库;MayBMS [52]运行于Post greSQL 之上;Trio 项目的初版原型系统Trio 2One 基于标准的关系数据库(postgreSQL )[53]等.图6描述了Trio 2One 系统的架构.该架构共有3层,用户界面层、Trio 接口与转换层、关系数据库管理系统.用户界面层包括命令行界面与图形用户界面,并将指令以TriQL 语言(Trio 项目的查询语言)的形式传递给下一层.中间层是通过Pyt hon 实现的Trio 接口和转换器,它将来自用户界面层的TriQL 指令翻译成标准的SQL 语句,发送底层的关系数据库管理系统.关系数据库管理系统存储了一些必要的元数据、存储过程、编码数据表和世系表等,它处理来自中间层的SQL 语句,将查询结果经由中间层送到用户界面层,并呈现给终端用户.
关系型的存储技术比较直接,但是无法有效处理部分特殊查询,例如数据世系等.一些研究小组逐渐认识到应该开发新的存储技术.例如,Trio项目组认为一些数据库物理设计问题非常重要,包括数据呈现(Data layout)、索引(indexing)、划分(parti2 tioning)、物化视图(materialized view)等.因此,他们期望新版的Trio系统不再是简单地基于现有RDBMS之上,而是能够将一些针对性的设计理念融入到数据库物理设计中去,以提高查询处理性能[23].
另外,对于不确定性数据流而言,其存储任务仍旧是构建基于内存的各种概要数据结构,而非基于磁盘的数据结构,以便实时计算查询结果.半结构化数据的通用存储形式是文档树.
有效的索引能够大幅提高查询效率.不确定性数据含有概率维度,有些查询仅使用非概率维度的索引,而有些查询却需要对概率维度进行索引.例如,处理不确定Top2k查询过程就仅需以ranking 函数对特定值维度进行索引[20,54],而处理范围查询[55258]、最近邻查询(Nearest Neighbor query,NN query)[57,59]等则迫切需要对概率维度进行索引[56].
在移动对象数据库等应用中,物体在某时刻的位置可能并非确定,仅知道在一个较大的区域之内,一般用概率密度函数(p df)描述.R树[60]以及其变种是为高维数据创建索引的重要手段,一种方法是以p df的覆盖范围作为该物体的实际空间尺寸,并建立索引.但是这个方法的可行性不高,原因在于p df所覆盖的范围可能很大,而物体最可能出现的地方却是其中的一小块地方.构建索引必须考虑p df的分布特征.
概率阈值索引(Probability Threshold Inde2 xing,P TI)[55]能够实现对一维数据的索引.假设数据库中各元组的属性值对应一个一维区间[a,b],可以设置多个x2bo und.各个x2bound由两根线组成,在线的左边或右边,其总概率均不超过x.令M i表示第i个元组的MBR,M i.lb(x)和M i.rb(x)分别表示x2bound的左边和右边值,L i和R i分别表示最左边和最右边的值,f i表示该元组的概率密度函数,则
我们有∫M i.lb(x)
L i
f i(y)d yΦx和∫R i M i.rb(x)f i(y)d yΦx.该做法能够避免一些额外的计算.
U2t ree可被视为是P TI的扩展版本[56,61].令o表示任一对象,o.ur表示该对象的范围, o.p d f(・)表示该对象的概率密度函数.当位置x在o.ur之内时,o.p d f(x)>0;否则,o.p d f(x)=0.该方法基于概率约束区域(Probabilistically Con2 strained Region,PCR)技术,首先将区域划分成若干个规则的矩形,各个矩形分别和一个概率相关,然后利用U2t ree(类似于R树)对这些PCR进行索引.这些PCR有助于在查询过程中进行剪枝、验证等操作.图7描述了一个不确定对象o的示意图.整个凸多边形就是o.ur,它被4条线(l1-,l1+,l2-, l2+)切出中间一块空白的矩形,即PCR,满足条件:在l1-左边、l1+右边、l2+上面、l2-下边的区域的发生概率各为012.例如,针对l1-可以有
∫l1--∞∫∞-∞p d f(x,y)d y d x=012
.
图7 PCR例子
Ljosa等人[57]提出了A PLA2t ree技术,创建索引,他们同时也针对kNN查询进行了优化.
5 查询与分析
5.1 关系代数处理
关系型不确定性数据管理技术的研究工作起源较早,从20世纪80年代后期到现在一直在延续.根据存在级不确定性与属性级不确定性,细分的数据模型就有Probabilistic?2table[9,11]、Probabilistic or2 set table[11]、Probabilistic c2table等.一般可以向数据库提交类似于SQL的查询语句,从而返回查询结果.这其中如何计算查询结果的概率值是一个大的研究问题.
Andrit so s等人提出了查询重写技术来处理查询[62].给定一个SPJ查询:“select A1,…,A n f rom R1,…,R m where W”,可以将其转化为“select A1,…,A n,s um(R1.p rob.3…3R m.p rob) f rom R1,…,R m where W group by A1,…,A n”.新的查询语句中包含了结果查询的产生概率值.
Sen和Deshpande等人则利用构建图模型的方法来处理SQL语句[63].数据库上的查询评价问题看作是基于概率图模型上的推断问题.文中应用概率图模型来刻画元组间的相关关系,并应用概率图模型来分解联合概率分布,通过分解后因子表达式中的条件概率分布计算并返回查询概率.
要完整地计算出查询结果有时是非常困难的.研究结果表明,一个含连接操作的查询要么相对于概率数据库在多项式复杂度的时间内被计算出来,要么相对于概率数据库是#P2完全问题[41,].
文献[65]研究了近似查询及其复杂性.
5.2 世系分析
数据的世系(lineage或者provenance)是指数据产生并随着时间推移而演变的整个过程[66].现有工作大多针对确定性数据库,但很多应用(特别是超大规模应用)往往需面对不精确数据集合,而非精确的数据集合,包括科学数据管理、传感器数据管理、近似查询处理、隐私保护等[67].例如,一些大型科研项目必须由多个科研小组分工合作完成,一部分小组的任务是制造并记录大量原始实验数据,另一部分学者基于原始数据、外部数据与中间数据进行分析,生成新数据集合,乃至最终获取查询结果.在整个数据演化过程中,各环节所产生的不确定性不断传递、放大,从而能够极大地影响最终查询结果的质量.
Trio项目最早研究如何整合不确定性与数据的世系[67].该项目定义了ULDB(U ncertainty2Line2 age Database),面向世系分析的不确定性数据库,并证明它是完全的(complete);提出了执行关系操作的算法[23,68].
图8是一个关于犯罪现场数据的世系的例子.图8(a)是目击调查表,张三与李四是两个目击证人,张三看到的可能是宝马或者奔驰,李四看到的是奔驰.图8(b)是驾驶记录表,记录在某个时段内通过某区域的所有宝马与奔驰车辆以及车主.图8(c)是通过上述两个表生成的3项指控记录.例如,指控记录42的世系为(42,1)={(21,2),(32,1)},表示张三指控赵六,证据是目击调查表的记录21的第2项与驾驶记录表的记录32.但由于目击调查表存在不确定性,这项指控本身也存在不确定性.
ID
目击调查(目击者,车型)
21(张三,宝马)‖(张三,奔驰)? 22(李四,奔驰)?ID
驾驶记录
(驾驶员,车型)
31(王五,宝马)
32(赵六,奔驰)
ID
指控
(目击者,驾驶员)
41(张三,王五)?(41,1)={(21,1),(31,1)}
42(张三,赵六)?(42,1)={(21,2),(32,1)}
43(李四,赵六)?(43,1)={(22,1),(32,1)}
(a)目击调查表(b)驾驶记录表(c)指控表
图8 一个数据世系的例子
当数据的世系比较复杂时,如何计算查询结果的概率就成为一件困难的事情.当不考虑概率因素时,可以为某一个数据世系设计多种查询计划,并且得到相同结果.但是当存在概率因素时,不同查询计划返回的查询结果的概率值却可能不同.其原因是在设计查询计划的过程中未考虑到数据的相关性特征,导致重复计算[23].文献[69]提出了一种数据计算与概率计算解偶的技术,使两者可以分开计算,这样一方面概率值可以采用传统的关系型数据库方法进行计算,另一方面,如果用户并不关注查询结果的概率,则可以节约计算概率值的开销.
在一些大型应用(特别是生物数据库)中,元组的世系可能非常庞大,甚至高达10MB,而其中大部分数据仅对结果产生较小的影响.文献[70]就考虑以高效的方法近似描述一个元组的数据世系.
5.3 Top2k查询
面向确定性数据库的top2k查询的定义非常清晰:返回ranking函数值最大的k个元组.但是在不确定性数据库上却存在多种定义方法,例如U2Top k[54]、U2k Ranks[54]、P T2k[20]和P k2top k[36]查询等.U2Top k查询返回一个长度为k的元组矢量,它在所有可能世界中的发生概率最大;U2k Ranks 查询返回在各个级别中出现的总概率最大的元组; P T2k首先定义一个阈值p,返回所有在可能世界实例中成为top2k的总概率超过阈值的元组;P k2top k 则返回在所有可能世界实例中成为top2k的总概率最大的k个元组.假设一个不确定数据库含有4个元组,即{t1=(5,018),t2=(6,015),t3=(8,014), t4=(2,014)}.当k=2时,U2top k返回(t2,t1), U2k Ranks返回(t3,t1),P T2k返回(t1,t2,t3);当p= 013时,P k2top k返回(t1,t2).
Soliman等人提出了基于搜索空间的方法来处理U2Top k查询与U2k Ranks查询[54].各元组首先按照ranking函数从大到小进行排序,然后不断地构造搜索空间,缩小空间的范围,最终获得查询结果.Cheng等人针对U2Top k查询提出了一种动态维护的结构,支持元组的插入与删除[71].Hua等人针对P T2k查询提出了构造dominant集合的方法[20].在其后续工作中,也提出了近似解决方案[72].上述算法均需要预先对数据进行排序.Jin等人[36]提出了面向数据流应用的Top2k查询处理算法,不仅能够解决上述4种查询,而且是一次遍历算法,能够处理数据流应用.
上述4种查询均可视为是从单个数据库表中获取的数据.Ré等人[73]则研究了在多表之间做连接操作的情况.各个表的数据并不精确,存在不一致性.他们的基本想法是并行地运行多个Monte2 Carlo模拟器,每一个对应于一个候选的答案,再计算各个候选答案的近似概率.
514 Skyline查询
Skyline查询[74]能用于解决多准则决策(Muli2 Criteria Decisio n2Making,MCDM)问题.给定一个确定性的n2维数据集合D,任一点d可被表示为(d.D1,…,d.D n).Skyline查询返回数据集合S, SΑD,则Πu∈S,不存在其它点v,满足(1)对于任一维度i(1ΦiΦn),u.D iΦv.D i;(2)存在一个维度j(1ΦjΦn)使得u.D j Lian与Chen等人则考虑了如何在不确定数据集合上处理reverse skyline查询[76]的问题[77].确定性reverse skyline查询返回在数据库中所有的动态skyline包含给定查询点的数据点.相应的,概率reverse skyline查询(Probabilistic Reverse Skyline, PRS)被定义为:给定一个概率阈值p(0ΦpΦ1)和一个查询对象q,返回所有对象v,使得对象q为v 的动态skyline点的概率不低于阈值p.文献[77]将每一个数据对象看作是一个不确定区域,应用确定情形下的BBS算法[78]进行空间剪枝,应用用户定义的概率阈值p进行概率剪枝,得到候选的PRS点进行精化,最后输出查询结果. 5.5 数据流 在不确定性数据流中,各元组以概率形式表达不确定性,可以是单一的概率值,也可以是复杂的概率密度函数.数据流模型中,数据到达速率极快,数据量极大,要求设计单遍扫描算法,以低空间复杂度实时处理查询. 传统的面向确定性数据流的方法经过改装之后能够应用于不确定性数据流应用之中.例如,AMS sketch[79]能用于处理聚集查询,特别是F2问题;FM sketch[80]能用于求解数据流上的相异元素个数; Cluster Feat ure被广泛用于设计各种在线聚类算法[81282].Cormode等人发展了AMS sketch和FM sketch方法,引入了概率参数,构造了pAMS结构和p FM结构,能够处理不确定性数据流上的相应查询[35].Aggarwal和Yu改进了CF方法,提出了ECF(Error2based CF)方法,处理数据流上的聚类问题[83]. 文献[34]最早在数据流上计算简单的聚集函数,特别是AV G函数.他们的方法比较复杂,主要采用生成函数技术(generating f unctions),难以进行扩展以解决其它问题.他们的后续工作[84]能够解决更多的聚集查询问题,包括F0和F2,并且提高了AV G函数的查询效率.Zhang等人定义了在不确定性数据流上查询频繁元素的问题,并设计解决方法[85]. Jin等人最早提出了面向滑动窗口模型的查询处理方法[36].如前所述,存在各种top2k查询.他们提出了一种针对top2k查询的框架.首先,可以针对各种top2k查询设计compact set,各个compact set 含有一部分数据.这个compact set具有两个特性: (1)能够计算top2k查询结果;(2)能够增量维护.但是compact set仍然不足以回答滑动窗口模型,因此,可以将多个compact set s进行压缩,降低空间复杂度与时间复杂度.他们提出的SCSQ2buffer策略在时间复杂度与空间复杂度上均是优秀的. 事件数据流是一种重要的数据流.传统方法大多仅能够处理准确的数据流,例如Cayuga[86]、SASE[87]、Snoop IB[88]等.文献[]能够处理概率数据流上的查询分析,但是他们的工作主要集中于少数几种查询,例如选择、映射和聚集查询等.Lahar 系统则能够处理不精确的数据流,特别适用于RFID等环境中,能够处理误读数据、冲突数据、粒度不匹配等不精确信息[37]. 5.6 OLAP OL A P技术使用模型.事实表(fact table)中的各个事实(fact)可被视为空间的一个点.然而,当存在不确定因素时,各事实记录并不表现为一个点,而是跨越多个维度值,成为空间里的一个“区域”.例如,可以以“籍贯”为维度对在校学生进行OLA P分析.籍贯是层次型的,包括省级与区县级.若学生均已准确登记其区县级的籍贯信息,则各事实都是空间的一个点;若某学生仅登记其籍贯为“浙江省”,则该事实表现为空间里的“区域”. Burdick等人[38240,90]基于可能世界模型来处理上述不精确的OLA P查询.根据可能世界模型的语义,一个含不精确事实的数据库可被描述为多个可能世界,各可能世界仅含有精确事实,最终的查询结果能够从这些可能世界实例中获取.例如,首先在一个不精确的数据库D上生成所有可能世界实例w1,…,w n,各可能世界实例w i的发生概率为p(w i);在各可能世界实例上分别执行查询Q,得到Q(w i);最后,对这些查询结果进行聚集,得到∑p(w i)×Q(w i). 当数据集合较大时,通过枚举所有可能世界实例的方法并不可行.Burdick等人首先研究了在数据情况下的优化方法.该方法首先构造EDB (Extended DataBase),然后再单遍扫描EDB,快速计算查询结果[39].文献[90]则改进了计算EDB的方法,进一步提高查询效率. 数据的情况较易处理,而若数据之间存在约束条件时则更为复杂.典型的约束条件如:“张三和李四的籍贯都是浙江省,但是他俩来自不同地级市”,则不可能存在如下可能世界实例:{(张三,文成县),(李四,平阳县),…}①.首先在一个不精确的数据库D上生成所有可能世界实例w1,…,w n,然后运用规则,仅剩下m个有效的实例,各可能世界实例w i的发生概率为p(w i);对各有效可能世界实例上生成的查询结果进行聚集,得到∑p(w i)×Q(w i).Burdick等人[40]提出了优化方法,基于原始数据库D构造MDB(Marginal DataBase),然后能够利用MDB以单遍扫描的方式迅速获得查询结果.在MDB中,各个事实均被首先计算了边缘概率值,以加速查询处理. 517 数据挖掘 面向不确定性数据的挖掘算法越来越引起人们的关注,主要研究内容包括聚类技术和分类技术.数据的不确定性能够显著影响数据挖掘应用的结果. 聚类技术得到了广泛的研究.Kriegel等人意识到不确定因素会影响两个元组之间的距离,因此重新定义了距离公式.令p( X, Y)表示元组 X和 Y之间的距离的概率密度函数,则 X与 Y间的距离在 (a,b)之间的概率为p(aΦd( X, Y)Φb)=∫b a p( X, Y)(z)d z.基于上述距离公式,他们改进了DB2 SCAN[91]算法,提出了FDBSCAN算法[92];改进了OP TICS[93]算法,提出了FO P TICS算法,解决层次聚类问题[94].Ngai等人提出了U K2means算法[95],基本思想与k2means类似:各数据点将被距离最近的簇吸收.为了提高计算效率,U K2means算法将数据点可能出现的区域用最小边界矩形(MBR)描述,设计剪枝策略减少运算量.文献[96]提出了针对移动对象的聚类方法,主要思路也是计算从各个对象到簇中心点的期望距离.文献[97]提出的方法采用一个函数来计算不确定的点到任意一个中心的距离的期望值,然后再运用传统的聚类方法进行计算. 上述工作均面向传统的静态数据库,无法适应高速的数据流模型.Aggarwal与Yu将CF结构扩展为ECF结构,增加了描述不确定性的组成部分,以解决数据流上的聚类问题[83].算法主要改进了新到点与簇中心点的距离与每个簇的接收半径的计算过程. Bi等人[98]提出了一种面向不确定性数据库的分类算法,它基于支持向量机(Support Vector Ma2 chine,SVM)技术. 6 总 结 近年来,不确定性数据广泛出现在诸多应用领 ①文成县与平阳县均属于浙江省温州市.域之中,例如传感器网络、RFID应用、数据集成、LBS、Web应用等,为数据管理技术提出了如下要求.(1)丰富的数据类型,包括结构化的关系数据、半结构化数据、流数据、移动对象数据以及其他领域相关数据等.(2)广泛性,数据处理的各个环节均可能存在不确定性,包括原始数据采集、预处理与集成、存储与索引、查询分析处理等.(3)繁多的查询类别,例如关系操作、数据世系、数据挖掘、模式匹配等.(4)概率维的冲击,概率维与普通数据维不同,会极大地影响查询定义、查询处理、结果定义等关键环节. 可能世界模型是不确定性数据管理领域中最通用的数据模型.尽管存在针对不同应用的具体模型,但这些模型通常均可转化为可能世界模型,如第2节所示.可能世界模型将问题域划分成若干可能世界实例,所有可能世界实例的发生概率之和为1,但各可能世界实例内部不存在不确定性.因此,可以在各可能世界实例上分别处理查询,然后再合并生成最终的查询结果.而事实上,由于可能世界实例的数量过于庞大,无法利用上述方法进行计算.目前,典型的不确定性解决方案大量采用排序、剪枝等启发式技术,从而大大减少计算量,快速获取查询结果. 在不确定性数据管理领域仍然存在很多工作有待完成: (1)许多在确定性数据管理领域所遇到的问题在不确定数据管理领域也非常重要,可以将这些查询问题搬到不确定数据管理领域上,以寻求解决方案. (2)由于概率维的存在,不确定数据管理领域存在一些特有的查询问题,需要找出这些查询并设计处理算法.例如,现有4种不确定top2k查询,包括U2Top k、U2k Ranks、P T2k、P k2Top k. (3)寻求在新模型定义下的查询处理方法.尽管大家都使用可能世界模型,但是不同应用场景下的模型仍然有所区别.事实上,不确定性XML处理技术的提升总是伴随着不确定性XML模型定义的更新. (4)需要针对不确定性查询设计更优秀的算法. 参考文献 [1]Deshpande A,Guestrin C,Madden S,Hellerstein J M, Hong W.Model2driven data acquisition in sensor networks// Proceedings of t he30t h International Conference on Very Large Data Bases.Toronto,2004:5882599 [2]Li Jian2Zhong,Li Jin2Bao,Shi Sheng2Fei.Concept s,issues and advance of sensor networks and data management of sen2 sor networks.Journal of Software,2003,14(10):17172 1727(in Chinese) (李建中,李金宝,石胜飞.传感器网络及其数据管理的概 念、问题与进展.软件学报,2003,14(10):171721727) [3]Gu Yu,Yu Ge,Zhang Tian2Cheng.RFID complex event processing techniques.Journal of Frontiers of Computer Sci2 ence and Technology,2007,1(3):2552267(in Chinese) (谷峪,于戈,张天成.RFID复杂事件处理技术.计算机科 学与探索,2007,1(3):2552267) [4]Madhavan J,Cohen S,Xin D,Halevy A,J effery S,K o D, Yu C.Web2scale data integration:Y ou can afford to pay as you go//Proceedings of t he33rd Biennial Conference on In2 novative Data Systems Research.Asilomar,2007:3422350 [5]Liu Ling.From data privacy to location privacy:Models and algorit hms(tutorial)//Proceedings of t he33rd International Conference on Very Large Data bases.Vienna,2007:14292 1430 [6]Samarati P,Sweeney L.Generalizing data to provide ano2 nymity when disclosing information(abst ract)//Proceedings of t he17t h ACM SIGACT2SIGMOD2SIGAR T Symposium on Principles of Database Systems.Seattle,1998:188 [7]Cavallo R,Pittarelli M.The t heory of probabilistic databas2 es//Proceedings of t he13t h International Conference on Very Large Data Bases.Brighton,1987:71281 [8]Barbara D,Garcia2Molina H,Porter D.The management of probabilistic data.IEEE Transactions on Knowledge and Da2 ta Engineering,1992,4(5):4872502 [9]Fuhr N,Rolleke T.A probabilistic relational algebra for t he integration of information retrieval and database systems. ACM Transactions on Information Systems,1997,15(1): 32266 [10]Z imanyi E.Query evaluation in probabilistic databases.The2 oretical Computer Science,1997,171(122):1792219 [11]Lakshmanan L V S,Leone N,Ross R,Subrahmanian V S. ProbView:A flexible database system.ACM Transactions on Database Systems,1997,22(3):4192469 [12]Abiteboul S,Kanellakis P,Grahne G.On t he representation and querying of set s of possible worlds.ACM SIGMOD Re2 cord,1987,16(3):34248 [13]Green T J,Tannen V.Models for incomplete and probabilis2 tic information.IEEE Date Engineering Bulletin,2006,29 (1):17224 [14]Babcock B,Babu S,Datar M,Motwani R,Widom J.Mod2 els and issues in data stream systems//Proceedings of t he 21st ACM SIGMOD2SIGACT2SIGAR T Symposium on Prin2 ciples of Database Systems.Madison,2002:1216 [15]Jin Che2Qing,Qian Wei2Ning,Zhou Ao2Y ing.Analysis and management of streaming data:A survey.Journal of Soft2 ware,2004,15(8):117221181(in Chinese) (金澈清,钱卫宁,周傲英.流数据分析与管理综述.软件学 报,2004,15(8):117221181) [16]RéC,Suciu D.Management of data wit h uncertainties// Proceedings of t he16t h ACM Conference on Information and Knowledge Management.Lisbon,2007:328 [17]Dalvi N,Suciu D.Management of probabilistic data founda2 tions and challenges//Proceedings of t he26t h ACM SIG2 MOD2SIGACT2SIGAR T Symposium on Principles of Data2 base Systems.Beijing,2007:1212 [18]Aggarwal C C,Yu P S.A survey of uncertain data algo2 rit hms and applications.IBM Research Report,October31, 2007 [19]Pei J,Hua M,Tao Y F,Lin X M.Query answering tech2 niques on uncertain and probabilistic data:Tutorial summa2 ry//Proceedings of t he2008ACM SIGMOD International Conference on Management of Data.Vancouver,2008: 1357213 [20]Hua M,Pei J,Zhang W J,Lin X M.Efficiently answering probabilistic t hreshold top2k queries on uncertain data//Pro2 ceedings of t he24t h IEEE International Conference on Data Engineering.2008:140321405 [21]Sarma A D,Benjelloun O,Halevy A,Widom J.Working models for uncertain data//Proceedings of the22nd IEEE In2 ternational Conference on Data Engineering.Atlanta,2006:7 [22]Imieli ski O,J r W L.Incomplete information in relational databases.Journal of ACM,1984,31(4):7612791 [23]Benjelloun O,Sarma A D,Halevy A,Widom J.ULDBs: Databases wit h uncertainty and lineage//Proceedings of t he 32nd International Conference on Very Large Data Bases.Se2 oul,2006:95329 [24]Abiteboul S,Buneman P,Suciu D.Data on t he Web:From Relations to Semist ructured Data and XML.San Francisco, CA:Morgan Kauf mann,1999 [25]Dekhtyar A,G oldsmit h J,Hawkes S R.Semistructured probabilistic databases//Proceedings of t he13t h International Conference on Statistical and Scientific Database Manage2 ment.Tokyo,2001:36245 [26]Nierman A,J agadish H V.Pro TDB:Probabilistic data in XML//Proceedings of t he28t h International Conference on Very Large Data Bases.Hong K ong,China,2002:62657 [27]Abiteboul S,Senellart P.Querying and updating probabilis2 tic information in XML//Proceedings of t he9t h International Conference on Extending Database Technology:Advances in Database Technology.Munich,2006:105921068 [28]Senellart P,Abiteboul S.On t he complexity of managing probabilistic XML data//Proceedings of t he26t h ACM SIG2 MOD2SIGACT2SIGAR T Symposium on Principles of Data2 base Systems.Beijing,2007:2832292 [29]Cohen S,K imelfeld B,Sagiv Y.Incorporating constraint s in probabilistic XML//Proceedings of t he27t h ACM SIGMOD2 SIGACT2SIGAR T Symposium on Principles of Database Sys2 tems.Vancouver,2008:1092118[30]Hung E,Getoor L,Subrahmanian V S.PXML:A probabi2 listic semistruct ured data model and algebra//Proceedings of t he19t h IEEE International Conference on Data Engineering. Bangalore,2003:4672478 [31]Hung E,Getoor L,Subrahmanian V S.Probabilistic interval XML.ACM Transactions on Computational Logic,2007,8 (4):24 [32]van Keulen M,de Keijzer A,Alink W.A probabilistic XML approach to data integration//Proceedings of t he21st IEEE International Conference on Data Engineering.Tokyo,2005: 4592470 [33]K imelfeld B,K osharovsky Y,Sagiv Y.Query efficiency in probabilistic XML models//Proceedings of t he2008ACM SIGMOD International Conference on Management of Data. Vancouver,2008:7012714 [34]J ayram T S,Kale S,Vee E.Efficient aggregation algorit hms for probabilistic data//Proceedings of t he18t h Annual ACM2 SIAM Symposium on Discrete Algorit hms.New Orleans, 2007:3462355 [35]Cormode G,Garofalakis M.Sketching probabilistic data streams//Proceedings of t he2007ACM SIGMOD Interna2 tional Conference on Management of Data.Beijing,2007: 2812292 [36]Jin Che2Qing,Y i Ke,Chen Lei,Yu Xu,Lin Xue2Min.Slid2 ing2window top2k queries on uncertain Streams.Proceedings of t he VLDB Endowment,2008,1(1):3012312 [37]RéC,Letchner J,Balazinska M,Suciu D.Event queries on correlated probabilistic streams//Proceedings of t he27t h ACM SIGMOD International Conference on Management of Data.Vancouver,2008:7152728 [38]Burdick D,Deshpande P M,J ayram T S,Ramakrishnan R, Vait hyanat han S.OLAP over uncertain and imprecise data// Proceedings of t he31st International Conference on Very Large Data Bases.Trondheim,2005:9702981 [39]Burdick D,Deshpande P M,J ayram T S,Ramakrishnan R, Vait hyanat han S.OLAP over uncertain and imprecise data. The VLDB Journal,2007,16(1):1232144 [40]Burdick D,Doan A,Ramakrishnan R,Vait hyanat han S. Olap over imprecise data wit h domain constraint s//Proceed2 ings of t he33rd International Conference on Very Large Data Bases.Vienna,2007:39250 [41]Dalvi N,Suciu D.The dichotomy of conjunctive queries on probabilistic st ructures//Proceedings of t he26t h ACM SIG2 MOD2SIGACT2SIGAR T Symposium on Principles of Data2 base Systems.Beijing,2007:2932302 [42]Dalvi N,Suciu D.Efficient query evaluation on probabilistic databases//Proceedings of t he30t h International Conference on Very Large Data Bases.Toronto,2004:82875 [43]J effery S R,Garofalakis M,Franklin M J.Adaptive cleaning for RFID data st reams//Proceedings of t he32nd Internation2 al Conference on Very Large Data Bases.Seoul,2006:1632 174[44]Gruteser M,Grunwald D.Anonymous usage of location2 based services t hrough spatial and temporal cloaking//Pro2 ceedings of t he1st International Conference on Mobile Sys2 tems,Applications and Services.San Francisco,2003:31242 [45]Abul O,Bonchi F,Nanni M.Never walk alone:Uncertainty for anonymity in moving object s databases//Proceedings of t he24t h IEEE International Conference on Data Engineering. Cancun,2008:3762385 [46]Cheng R,Chen Jinchuan,Xie Xike.Cleaning uncertain data wit h quality guarantees.Proceedings of t he VLDB Endow2 ment,2008,1(1):7222735 [47]Halevy A,Rajaraman A,Ordille J.Data integration:The teenage years//Proceedings of t he32nd International Confer2 ence on Very Large Data Bases.Seoul,2006:9216 [48]Philippi S,K ohler J.Addressing t he problems wit h life2sci2 ence databases for traditional uses and systems biology. Nature Reviews Genetics,2006,(7):4812488 [49]Xin D,Halevy A,Yu C.Data integration wit h uncertainty// Proceedings of t he33rd International Conference on Very Large Data Bases.Vienna,2007:6872698 [50]Singh S,Cheng R,S.U2DBMS:A database sys2 tem for managing constantly2evolving data//Proceedings of t he31st International Conference on Very Large Data Bases. Trondheim,2005:127121274 [51]Boulos J,Dalvi N,Mandhani B,Mat hur S,RéC,Suciu D. Mystiq:A system for finding more answers by using proba2 bilities//Proceedings of t he2005ACM SIGMOD Internation2 al Conference on Management of Data.Baltimore,2005: 123 [52]Antova L,K och C,Olteanu D.MayBMS:Managing incom2 plete information wit h probabilistic world2set decomposi2 tions//Proceedings of t he23rd International Conference on Data Engineering.Istanbul,2007:147921480 [53]Mut suzaki M,Theobald M,de Keijzer A,Widom J,Agraw2 al P,Benjelloun O,Sarma A D,Murt hy R,Sugihara T. TrioOne:Layering uncertainty and lineage on a conventional DBMS//Proceedings of t he3rd Biennial Conference on Inno2 vative Data Systems Research.Asilomar,2007:2692274 [54]Soliman M A,Ilyas I F,Chang K C.Top2k query processing in uncertain databases//Proceedings of t he23rd IEEE Inter2 national Conference on Data Engineering.Istanbul,2007: 62905 [55]Cheng R,Xia Y,Prabhakar S,Shah R,Vitter J S.Efficient indexing met hods for probabilistic t hreshold queries over un2 certain data//Proceedings of t he30t h International Confer2 ence on Very Large Data Bases.Toronto,2004:8762887 [56]Tao Y,Cheng R,Xiao X,Ngai W K,Kao B,Prabhakar S. Indexing multi2dimensional uncertain data wit h arbitrary probability density functions//Proceedings of t he31st Inter2 national Conference on Very Large Data Bases.Trondheim, 2005:9222933[57]Ljosa V,Singh A K.APLA:Indexing Arbitrary Probability Dist ributions//Proceedings of t he23rd IEEE International Conference on Data Engineering.Istanbul,2007:9462955 [58]Chen J,Cheng R.Efficient evaluation of imprecise location2 dependent queries//Proceedings of t he23rd IEEE Interna2 tional Conference on Data Engineering.Istanbul,2007:5862 595 [59]Cheng R,Chen J,Mokbel M,Chow C.Probabilistic verifi2 ers:Evaluating constrained nearest2neighbor queries over un2 certain data//Proceedings of t he24t h IEEE International Conference on Data Engineering.Cancun,2008:9732982 [60]Gutt man A.R2t rees:A dynamic index structure for spatial searching//Proceedings of t he1984ACM SIGMOD Interna2 tional Conference on Management of Data.Boston,1984: 47257 [61]Tao Y,Xiao X,Cheng R.Range search on multidimensional uncertain data.ACM Transactions on Database Systems, 2007,32(3):15 [62]Andrit sos P,Fuxman A,Miller R J.Clean answers over dirty databases:A probabilistic approach//Proceedings of t he 22nd IEEE International Conference on Data Engineering. Atlanta,2006:30 [63]Sen P,Deshpande A.Representing and querying correlated tuples in probabilistic databases//Proceedings of t he23rd IEEE International Conference on Data Engineering.Istan2 bul,2007:5962605 []Gradel E,Gurevich Y,Hirsch C.The complexity of query reliability//Proceedings of t he17t h ACM SIGACT2SIG2 MOD2SIGAR T Symposium on Principles of Database Sys2 tems.Seattle,1998:2272234 [65]K och C.Approximating predicates and expressive queries on probabilistic databases//Proceedings of t he27t h ACM SIG2 MOD2SIGACT2SIGAR T Symposium on Principles of Data2 base Systems.Vancouver,2008:992108 [66]Woodruff A,Stonebraker M.Supporting fine2grained data lineage in a database visualization environment//Proceedings of t he13t h IEEE International Conference on Data Engineer2 ing.Birmingham,1997:912102 [67]Widom J.Trio:A system for integrated management of da2 ta,accuracy,and lineage//Proceedings of t he2nd Biennial Conference on Innovative Data Systems Research.Asilomar, 2005:2622276 [68]Benjelloun O,Sarma A D,Halevy A,Theobald M,Widom J.Databases wit h uncertainty and lineage.The VLDB Jour2 nal,2008,17(2):24322 [69]Sarma A D,Theobald M,Widom J.Exploiting lineage for confidence computation in uncertain and probabilistic data2 bases//Proceedings of t he24t h IEEE International Confer2 ence on Data Engineering.Cancun,2008:102321032 [70]RéC,Suciu D.Approximate lineage for probabilistic data2 bases.Proceedings of t he VLDB Endowment,2008,1(1): 7972808[71]Chen J,Y i K.Dynamic struct ures for top2k queries on uncer2 tain data//Proceedings of t he18t h International Symposium on Algorit hms and Computation.Sendai,2007:4272438 [72]Hua Ming,Pei Jian,Zhang Wenjie,Lin Xuemin.Ranking queries on uncertain data:A probabilistic t hreshold ap2 proach//Proceedings of t he2008ACM SIGMOD Internation2 al Conference on Management of Data.Vancouver,2008: 6732686 [73]RéC,Dalvi N,Suciu D.Efficient top2k query evaluation on probabilistic data//Proceedings of t he23rd IEEE Internation2 al Conference on Data Engineering.Istanbul,2007:88625 [74]Borzsonyi S,K ossmann D,Stocker K.The skyline opera2 tor//Proceedings of t he17t h IEEE International Conference on Data Engineering.Heidelberg,2001:4212430 [75]Pei J,Jiang B,Lin X,Yuan Y.Probabilistic skylines on un2 certain data//Proceedings of t he33rd International Confer2 ence on Very Large Data Bases.Vienna,2007:15226 [76]Dellis E,Seeger B.Efficient computation of reverse skyline queries//Proceedings of t he33rd International Conference on Very Large Data Bases.Vienna,2007:2912302 [77]Lian X,Chen L.Monochromatic and bichromatic reverse skyline search over uncertain databases//Proceedings of t he 2008ACM SIGMOD International Conference on Manage2 ment of Data.Vancouver,2008:2132226 [78]Deng K,Zhou X,Shen H T.Multi2source skyline query processing in road networks//Proceedings of t he23rd Inter2 national Conference on Data Engineering.Istanbul,2007: 7962805 [79]Alon N,Matias Y,Szegedy M.The space complexity of ap2 proximating t he frequency moment s//Proceedings of t he28t h Annual ACM Symposium on Theory of Computing.Philadel2 phia,1996:20229 [80]Flajolet P,Martin G N.Probabilistic counting algorit hms for database applications.Journal of Computer and System Sci2 ences,1985,31(2):1822209 [81]Zhang T,Ramakrishnan R,Livny M,BIRCH:An efficient data clustering met hod for very large databases//Proceedings of t he15t h ACM SIGMOD International Conference on Man2 agement of Data.Montreal,1996:1032114 [82]Aggarwal C C,Han J,Wang J,Yu P S.A framework for clustering evolving data streams//Proceedings of t he2003 ACM SIGMOD International Conference on Management of Data.Berlin,2003:81292 [83]Aggarwal C C,Yu P S.A framework for clustering uncer2 tain data streams//Proceedings of t he24t h IEEE Internation2 al Conference on Data Engineering.Cancun,2008:1502159 [84]J ayram T S,Mc Gregor A,Mut hukrishnan S,Vee E.Esti2 mating statistical aggregates on probabilistic data streams// Proceedings of t he26t h ACM SIGMOD2SIGACT2SIGAR T Symposium on Principles of Database Systems.Beijing, 2008:2432252 [85]Zhang Qin,Li Fei2Fei,Y i Ke.Finding frequent items in probabilistic data//Proceedings of t he27t h ACM SIGMOD International Conference on Management of Data.Vancou2 ver,2008:8192832 [86]Demers A J,Gehrke J,Hong M,Riedewald M,White W M.Towards expressive publish/subscribe systems//Pro2 ceedings of t he9t h International Conference on Extending Database Technology:Advances in Database Technology. Munich,2006:62724 [87]Wu E,Diao Y,Rizvi S.High2performance complex event processing over streams//Proceedings of t he ACM SIGMOD International Conference on Management of Data.Chicago, 2006:4072418 [88]Adaikkalavan R,Chakravart hy S.Snoopib:Interval2based event specification and detection for active databases.Data Knowledge Engineering,2006,59(1):1392165 []Kanagal B,Deshpande A.Online filtering,smoot hing and probabilistic modeling of streaming data//Proceedings of t he 24t h IEEE International Conference on Data Engineering. Cancun,2008:116021169 [90]Burdick D,Deshpande P M,J ayram T S,Ramakrishnan R, Vait hyanat han S.Efficient allocation algorit hms for OLAP over imprecise data//Proceedings of t he32nd International Conference on Very Large Data Bases.Seoul,2006:3912402 [91]Ester M,Kriegel H P,Sander J,Xu X.A density based al2 gorit hm for discovering clusters in large spatial databases wit h noise//Proceedings of t he2nd International Conference on Knowledge Discovery and Data Mining.Portland,1996: 2262231 [92]Kriegel H P,Pfeifle M.Density2based clustering of uncertain data//Proceedings of t he11t h ACM SIGKDD International Conference on Knowledge Discovery in Data Mining.Chica2 go,2005:6722677 [93]Ankerst M,Breunig M M,Kriegel H P,Sander J.OP TICS: Ordering point s to identify t he clustering st ructure//Proceed2 ings of t he1999ACM SIGMOD International Conference on Management of Data.Philadelphia,1999:49260 [94]Kriegel H P,Pfeifle M.Hierarchical density2based clustering of uncertain data//Proceedings of t he5t h International Con2 ference on Data Mining.Houston,2005:62692 [95]Ngai W K,Kao B,Chui C K,Cheng R,Chau M,Y ip K Y. Efficient clustering of uncertain data//Proceedings of t he6t h International Conference on Data Mining.Hong K ong,Chi2 na,2006:4362445 [96]Chau M,Cheng R,Kao B,Ngai J.Uncertain data mining: An example in clustering location data//Proceedings of t he 10t h Pacific2Asia Conference on Knowledge Discovery and Data Mining.Singapore,2006:1992204 [97]Cormode G,Mc Gregor A.Approximation algorit hms for clustering uncertain data//Proceedings of t he27t h ACM SIGMOD2SIGACT2SIGAR T Symposium on Principles of Da2 tabase Systems.Vancouver,2008:1912200 [98]Bi Jinbo,Zhang Tong.Support vector classification wit h in2 put data uncertainty//Advances in Neural Information Pro2 cessing Systems.Vancouver,2005,17:1612168 ZH OU Ao 2Ying ,born in 1965, professor ,Ph.D.supervisor.His re 2search interests focus on data manage 2ment and information system ,inclusive of Web data management ,Chinese Web infrastructure ,Web searching and min 2ing ,data streaming and mining ,com 2 plex event processing and real 2time business intelligence ,un 2certain data management and applications ,data 2intensive computing ,distributed storage and computing ,peer to peer computing and management ,Web service. JIN Che 2Q ing ,born in 1977,Ph.D.,associate profes 2sor.His research interests include data stream management ,uncertain data management. WANG G uo 2R en ,born in 1966,professor ,Ph.D.su 2pervisor.His research interests include XML management ,bioinformatics ,distributed database ,and parallel compu 2ting. L I Jian 2Zhong ,born in 1950,professor ,Ph.D.super 2visor.His research interests include database ,parallel com 2puting. B ackground This paper surveys the recent research work on uncer 2tain data management that belongs to the database category.Data uncertainty widely appears in various applications ,in 2clusive of economy ,military ,logistic ,finance and telecom 2munication etc.The reasons for uncertain data include ,but are not limited to the following :Imprecise data caused by the physical devise ,network or environment ;Using a coarse 2grained dataset ;To meet the special application requirement ;Incomplete dataset ;Data integration.Thus ,it is critical to develop new techniques to manage such uncertain database. The research of management on uncertain database starts from the late 80’s last century ,and becomes a very hot field today.The work in the early stage focused on ex 2tending the relational model with an additional probability field to process SQL like queries ,but now it has been devel 2oped to a quite boarder range.Besides the relational data ,new data types such as semistructured data ,streaming data ,and moving objects are also studied intensively ,which leads to numerous novel sophistical query processing issues.How 2ever ,neither the traditional techniques for deterministic da 2 ta ,nor the techniques for probabilistic relational database are capable of handling such query tasks efficiently. There are already a few survey papers on management of uncertain database with different emphasis recently.R éand Suciu summarized some big challenges in this field in 2007.Dalvi and Suciu pointed out the foundation and challenges with the analysis in theory in 2007.Aggarwal and Yu fo 2cused on algorithms and applications.The literature by Pei et al.mainly aimed at their own work. Contrarily ,this paper surveys present work according to a general way of processing uncertain database ,including modeling ,preprocessing and cleaning ,storage and indexing ,and query processing.At first ,several uncertain models for different data types are proposed ,stemming f rom the core possible w orl d semantics ,following which the concepts for the data preprocessing and cleaning are also introduced.Af 2ter outlining the storage and indexing techniques ,the work for concrete query tasks are listed ,inclusive of relational op 2erator ,data lineage ,skyline query ,ranking query ,stream query ,OL A P ,and data mining.
Copyright © 2019-2025 51dongshi.net 版权所有
违法及侵权请联系：TEL:177 7030 7066 E-MAIL:11247931@qq.com 本站由北京市万商天勤律师事务所王兴未律师提供法律服务
