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

(3)体问题,[42].在高效计算复HAVING谓词的).灵活的约束条件能够,是不确定性数据管理的重要工具,但是当前仍不具备普遍接受的约束条件定义方式.

可能世界实例,并回答查询;在时间点3时,则基于

(22,018〉)和〈(21,012〉)构造可能元组〈,〈23,017〉

世界实例,并回答查询;依此类推.

另外,在多数据流应用中,不同数据流上到达的元组之间可能存在相关性,必须整体考虑[37].2.5　针对多维数据的模型

OLAP提供了一种多维数据分析手段,能够快

速得到复杂的查询统计结果.OLAP(DataCube)的基本元素是cuboid.据模型中,各个事实(fact)中.例如,考虑一个有关汽车销售的多维数据模型,它包括两个维度:city与automobile,分别表示购车城市与车体型号.city维

3　数据预处理和数据集成

数据预处理与集成是很多数据管理应用不可或缺的组成部分.在传统数据管理领域,数据预处理是针对不准确、不精确的数据进行数据清理、数据转换等处理,从而提升数据质量,最终能够被确定性管理技术所处理.例如,由于多种原因,RFID读卡器的能够正确读取RFID标签的概率约为60～70%左右,即超过30%的数据被误读了[43].数据误读的原因很多,包括漏读、多读、脏数据等.因此,RFID应用的一大关键模块就是数据清洗模块,它将这些不准确的数据转化为准确的数据,再进行后续处理.这种方法被广泛应用于面向不精确数据的数据管理领域.该方法的不足之处主要有两点,首先,从不精确数据到精确数据的转换过程会损失原始数据的部分特征,无法准确反映原始数据的全貌;其次,一种数据清洗技术往往针对特定的原始数据(例如,漏读产生的数据集合),而非对所有数据集合均有效,这使得直接将数据清洗技术从一个应用搬到其他应用的难度加大[3].

数据预处理也包括将准确数据(或者高精度数据)转化为不精确的数据,从而达到隐私保护等特殊目的,典型的例子是基于位置的服务LBS.作为移动计算领域的核心问题,LBS在军事、通信、交通、服务业中均获得广泛应用.服务器利用GPS等技术获取移动对象的实时位置信息,并提供相应的服务.GPS技术能够获取精度较高的位置信息,恶意用户

度是一个三级层次结构,国家→省→市.若仅仅知道某辆“奔驰车”是从“浙江北部城市”购买的话,由于“浙江北部城市”包含多个城市,该条记录是不确定性数据,无法存放到事实表中去.文献[38239]提出了基于可能世界的多维数据模型,以处理这类不确定数据.在这种模型中,上述记录能够被存储于不确定性数据库中,可以基于可能世界语义执行OLAP

操作(例如切块、上卷等).他们的后续工作也考虑到了元组之间存在相关性的情况[40].2.6　要求与挑战

不确定数据管理技术采用与确定性数据管理技术截然不同的数据模型,这使得不确定性数据管理技术面临以下挑战:

(1)庞大的可能世界实例集合

毫无疑问,不确定性数据管理所面临的最直接的挑战就是其相对于数据库规模呈指数倍的可能世界实例的数量.假设某不确定性数据库含N条元组,各元组独立.当该数据库仅有存在级不确定性,可能世界的数目将达到2N个;而若各个元组还拥有属性级不确定性时,可能世界的数目将远大于2N.如果查询要求访问所有的可能世界时,则这个查询开销将会是一个#P问题[41].因此,需要在查询的准确度与查询开销之间进行权衡,目标是以较小的计算开销获得高质量的近似结果.

完全能够根据某移动对象的运动轨迹推测出一些有

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

用的信息.例如,若某个对象每天早上沿相同路径移动,则一般来说起点就是家庭地址,而终点则是工作单位地址.

k2匿名模型(k2anonymitymodel)能够解决这

(1)不确定性数据源.不确定性数据源是该数

种隐私保护问题[6].该模型最早应用于关系模型,关系中的属性被划分为准标识符(quasi2identifier)和敏感属性(sensitiveattribute),使得任一准标识符至少包括k个不同元组.位置k2匿名(locationk2anonymity)则是k2匿名模型在移动对象数据库上

据集成系统最直接的动力.很多情况都可能产生不确定性数据.例如,当数据从非结构化数据源或者半结构化数据源中自动抽取出来时,会引入不确定性;当数据从某些不可靠的或者过时的站点获取时,也会引入不确定性.

(2)不确定性模式映射.数据集成系统利用模式映射技术从多个原始数据源的模式构造中介模式(mediatedschema),.事实上,.原因很多,①,比如在个人;,因此无,;③超大数据规模阻止,例如Web数据集成.实际应用中,中介模式往往通过半自动化工具生成,而非由领域专家特别指定.

(3)不确定性查询.查询也可能具备不确定性.特别是在Web应用中,查询往往以“关键词”形式被提交,而并非一个定义规范的结构化查询.系统需要将这些查询转化成某些结构化形式,使得它们能够在这些数据源上重新定义.在这个步骤,系统可能会产生多个候选的结构化查询,并且拥有一些不确定性.

的扩展,当某消息被发送时,变换消息的空间信息,使其无法与其他k-1条不同消息区分开来[44].

)2匿名问题((k2δ)2ano2Abul等人[45]定义了(k,δ

nymityproblem),在任一时刻,总能够找到k象,聚集在半径为δ的圆内,N方法进行求解.

造一个新数据集合.这,但是能够提高查询处理的效率[46].

数据集成是管理多自治与异构数据源的应用所需面对的普遍挑战[47].当前的数据集成系统仅是传统数据库的扩展,查询以结构化格式定义,数据以传统模型建模,例如关系模型和XML模型等.此外,系统也知道原始数据映射到中间模式的确切规则.然而,这些系统无法管理不确定性数据.Philippi和Kohler[48]认为,针对生命科学数据库的数据集成系

4　存储和索引

目前,传统的关系型数据存储技术仍然是实

现不确定性数据库的存储任务的主流技术.例如,Orion项目[50]由C语言和PL/pgSQL实现,运行于PostgreSQL之上;MystiQ项目[51]具有较好的层次结构,支持PostgreSQL、SqlServer、DB2等关系型数据库;MayBMS[52]运行于PostgreSQL之上;Trio项目的初版原型系统Trio2One基于标准的关系数据库(postgreSQL)[53]等.图6描述了Trio2One系统的架构.该架构共有3层,用户界面层、Trio接口与转换层、关系数据库管理系统.用户界面层包括命令行界面与图形用户界面,并将指令以TriQL语言(Trio项目的查询语言)的形式传递给下一层.中间层是通过Python实现的Trio接口和转换器,它将来自用户界面层的TriQL指令翻译成标准的SQL语句,发送底层的关系数据库管理系统.关系数据库管理系统存储了一些必要的元数据、存储过程、编码数据表和世系表等,它处理来自中间层的SQL语句,将查询结果经由中间层送到用户界面层,并呈现给终端用户.

统的最大挑战在于数据的不精确性:数据没有统一的概念模式,数据不完整,缺乏部分信息,且有不确定性.事实上,这种情况也在其他许多领域广泛存在.

Xin等人最早研究了针对不确定性数据库的数

据集成系统,他们认为一个数据集成系统需要在三个层次上处理不确定性[49]:不确定性数据源、不确定性模式映射、不确定性查询.系统的基本框架结构如图5所示

.

图5　面向不确定数据的数据集成系统架构

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

以设置多个x2bound.各个x2bound由两根线组成,

在线的左边或右边,其总概率均不超过x.令Mi表示第i个元组的MBR,Mi.lb(x)和Mi.rb(x)分别表示x2bound的左边和右边值,Li和Ri分别表示最左边和最右边的值,fi表示该元组的概率密度函数,则我们有

∫

Li

Mi.lb(x) …… 此处隐藏：3527字，全部文档内容请下载后查看。喜欢就下载吧 ……