不确定性数据管理综述.pdf

《不确定性数据管理综述.pdf》由会员分享，可在线阅读，更多相关《不确定性数据管理综述.pdf（16页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第 32 卷第 1 期2009 年 1 月计 算机 学报CHINESE JOURNA L OF COM PU TERSVol. 32No. 1Jan. 2009不确定性数据管理技术研究综述周傲英金澈清 王国仁 李建中1)2)3)(1)1)2)3)( 华东师范大学软件学院 上海市高可信计算重点实验室 上海200062)( 东北大学信息科学与工程学院 沈阳 110004)哈尔滨工业大学计算机科学与技术学院 哈尔滨 150001)摘要随着数据采集和处理技术的进步 , 人们对数据的不确定性的认识也逐步深 入. 在诸如经济、 军事、 物流、 金融、 电信等领域的具体应用中 , 数据的不确定性普遍存在 .

2、 不确定性 数据的表 现形式 多种多 样, 它们可以 以关系 型数据、 半结构化数据、 流数据或移动对象数据等形式出现 . 目前, 根据应用特点与数 据形式差异, 研究者已经提出 了多种针对不确定数据的数据模型 . 这些不确定性 数据模型的 核心思 想都源自 于可能 世界模 型. 可能世界 模型从 一个或多个不确定的数据源演化出诸多确定的数据库实例 , 称为可能 世界实例, 而且所 有实例的 概率之和 等于 1. 尽管可以首先分别为各个实例计算查询结果 , 然后合并中间结 果以生 成最终查 询结果, 但由于可能 世界实 例的数 量远大于不确定性数据库的规模 , 这种方法并不可 行. 因此, 必

3、须运用排序、 剪枝等启 发式技术设 计新型算 法, 以提高效率. 文中介绍了不确定性数据管理技术的概念 、 特点与挑战, 综述了数据 模型、 数据预处理与 集成、 存储与索引、查询处理等方面的工作 .关键词 不确定性数据; 可能世界模型; 数据集成; 世系; 不确定数据流中图法分类号TP393号: 10. 3724/ SP. J. 1016. 2009. 00001ZHOU AoYingJIN CheQingWANG GuoRenLI JianZhong1)(Shangh ai2)3)1)1)2)3)Key Laboratory of T rustw orthy Computing , Sof

4、 twar e Engineering Institute , East China N ormal Univ ersity , Shang hai(School of Inf ormation Science and Engineer ing , N ortheastern University , Shenyang 110004)(S chool of Comp uter Science and Te chnolog y , H ar bin Institu te of Te chnolog y , H ar bin 150001)200062)T he importance of the

5、 data uncertainty was studied deeply with the rapid developm entin data gathering and processing in various fields,inclusive of economy,military,logistic, finance and telecom munication,etc. Uncertain data has many different styles,such as relationaldata, semistructured data, stream ing data, and mo

6、v ing objects.Accor ding to scenarios and datacharacter istics, tens of data models have been developed,stemming from the core possible worldmodel that contains a huge number of the possible world instances with the sum of probabilitiesequal to 1. However, the number of the possible world instances

7、is far greater than the volume ofthe uncertain database, making it infeasible to combine medial results generated from all of possible world instances for the final query results.T hus, some heuristic techniques,such as ordering, pruning,must be used to reduce the com putation cost for the high effi

8、ciency. T his paper intro duces the concepts, characteristics and challenges in uncertain data manag ement, proposes theadvance of the research on uncertain data management,including data model, preprocessing,integr ating, storag e, indexing, and query processing.uncertain data; possible world model

9、; data integration;lineage; uncertain stream收稿日期: 200809 05. 本课题得到国家自然科学基金 ( 60803020) 、 上海市重点 学科建设 项目( B412) 资助. 周傲英, 男, 1965 年生, 教授,博士生导师, 主要研究兴趣为数据管理与信息系统 , 包括: Web 数据管理、 中文 Web 基础设施、 Web 搜索与挖掘、 数据流与 数据挖掘、 复杂事件处理与实时商务智能、不确定数据管理及其应用、 数据密集的 计算、 分布存储与 计算、 对等计 算及其数 据管理、 Web 服务计算 等.金澈清( 通信作者) , 男, 197

10、7 年生, 博士, 副教授, 主要研究方向为数据流管理、 不确定性数据管理技术等 . Email: cqjin sei. ecnu. edu. cn.王国仁, 男, 1966 年生, 教授, 博士生导师, 主要研究领域为 XM L 数据管理、 生物信息学、 分布与并 行数据库、 多媒体 索引技术、 并行计 算等. 李建中, 男, 1950 年生, 教授, 博士生导师, 主要研究领域为数据库、 并行计算等.2计算机学报2009 年目的, 某些应用无法获取原始的精确数据, 而仅能够1 引 言近四十年来, 传统的确定性数据 ( deterministicdata) 管理技术得到了极大的发展, 造就了

11、一个数百亿的数据库产业. 数据库技术和系统已经成为信息化社会基础设施建设的重要支撑 . 在传统数据库的应用中, 数据的存在性 和精确性均确 定无疑. 近年来, 随着技术的进步和人们对数据采集和处理技术理解的不断深入, 不确定性数据 ( uncertain data) 得到了广泛的重视. 在许多现实的应用中 , 例如经济、军事、 物流、 金融、 电信等领域, 数据的不确定性普遍存在, 不确定性数据扮演着关键角色. 传统的数据管理技术却无法有效管理不确定性数据 , 这就引发了学术界和工业界对研发新型的不确定性数据管理技术的兴趣.不确定性数据的产生原因比较复杂 . 可能是原始数据本身不准确或是采用了

12、粗粒度的数据集合 ,也可能是为了满足特殊应用目 的或是在处理 缺失值、 数据集成过程中而产生的.( 1) 原始数据不准确. 这是产生不确定 性数据最直接的因素. 首先, 物理仪器所采集的数据的准确度受仪器的精度制约. 其次, 在网络传输 ( 特别是无线网络传输) 过程中, 数据的准确性受到带宽、传输延时、 能量等因素影响. 还有, 在传感器网络应用与 RFID 应用 3等场合, 周围环境也会影响原始数据的准确度.( 2) 使用粗粒度数据集合. 很明显, 从粗粒度数据集合转换到细粒度数据集合的过程会引入不确定性. 例如, 假设某人口分布数据库以乡为基础单位记录全国的人口数量, 而某应用却要求查询

13、以村为基础单位的人口数量, 查询结果就存在不确定性.( 3) 满足特殊应用目的. 出于隐私保护 等特殊 12得到变换之后的不精确数据.( 4) 处理缺失值. 缺失值产生的原因很多 , 装备故障、 无法获取信息、 与其他字段不一致、历史原因等都可能产生缺失值. 一种典型的处理方法是插值,插值之后的数据可看作服从特定概率分布. 另外, 也可以删除所有含缺失值的记录, 但这个操作也在一定程度上变动了原始数据的分布特征.( 5) 数据集成 . 不同数据源的数据信息可能是不一致的, 在数据集成过程中就会引入不确定性. 例如, Web 中含很多信息, 但是由于页面更新等因素 ,许多页面的内容并不保持一致

14、4.对某些应用而言, 还可能同时存在多种不确定性. 例如, 基于位置的服务( LocationBased Service,LBS)是移动计算领域的核心问题, 在军事、 通信、交通、 服务业等方面有着广泛 的应用. LBS 应用获取各移动对象的位置, 为用户提供定制服务, 该过程存在若干不确定性. 首先, 受技术手段( 例如 GPS 技术) 限制, 移动对象的位置信息存在一定误差. 其次,移动对象可能暂时不在服务区, 导致 LBS 应用采集的数据存在缺失值情况. 最后, 某些查询要求保护用户的隐私 信息, 必须采用 位置隐私等方式 处理查询 6.实际上, 针对不确定性数据的研究工作已经有几十年历

15、史了. 从 20 世纪 80 年代末开始, 针对概率数据库( probabilistic database) 的研究 工作就从未间断过 711. 这类研究工作将不确定性引入到关系数据模型中去, 取得了较大进展 . 近年来, 针对不确定性数据的研究工作则在更广的范围内取得了更大的进展, 即在更丰富的数据类型上处理更多种类的查询任务. 图 1 描述了不确定性数据管理技术的典型框架, 它包含 4 大部分: 模型定义、 预处理与集成、存储与索引和查询分析处理. 5图 1不确定性数据管理的框架模型定义. 定义与应用场景相匹配的数据模型是不确定性数据管理的首要任务 . 在不确定性数据管理领域, 最常用的模

16、型是可能世界模型 ( possibleworld model) 1213. 该模型从一个不确定性 数据库演化出很多 确定的 数据库 实例( 称为可能 世界实例) , 而且所有实例的概率之和为1. 不确定性数据的种类较多, 例如关系型数据、 半结构化数据、 流数据、 移动对象数据等, 尽管存在许多与数据类型紧密相关的数据模型, 但是这些模型最终都可以转化为可能世界模型.1 期周傲英等: 不确定性数据管理技术研究综 述3预处理与集成. 某些应用需要为数据执行预处理操作, 主动引入不确定性, 从而达到信息隐藏和隐私保护的目的. 这种不确定性会降低查询结果质量,必须在查询质量与信息隐藏程度之间进行权衡

17、 . 当应用需要使用多个数据源时, 数据不一致性问题就凸显出来. 这个问题在 WEB 上尤为突出. 数据集成所要应对的不确定性问题不仅 包括原始数据 不一致, 还包括模式匹配不确定、 待处理的查询语义不确定等多种因素.存储与索引. 有效的存储和索引技术能够大幅提高数据管理效率. 尽管可以基于传统的关系型数据存储技术实现不确定性数据库的存储任务 , 但仍有必要开发新型存储技术, 以提高特定查询任务( 例如数据世系, data lineage) 的执行效率. 概要数据结构( synopsis data structure ) 是存储流数据( datastream) 1415的典型技术. 不确定性数

18、据与确定性数据的最大区别在于不确定性数据含有概率维度 . 一部分查询任务仅使用基于非概率维度的索引. 例如,在处理不确定 T opk 查询的过程中 , 往往只需对值维度以 ranking 函数创建索引 . 另一类查询 则需针对概率维度开发新的索引技术, 例如, 范围查询( Rang e query ) 、 最近 邻查 询 ( NearestNeighbo rquery) 等. 当概率维度以概率密度函数 ( probabilistic density function, 简称 pdf) 描述而非概率值时 ,创建索引的难度更大.查询分析处理. 查询分析处理是不确定性数据管理的最终目标. 查询类型非

19、常丰富, 例如关系查询操作、 数据世系、 XML 处理、 流数据查 询、 Ranking查询、 Skyline 查询、 OLAP 分析、 数据挖掘等. 尽管可以分别针对各个可能世界实例计算查询结果 , 再合并中间结果以生成最终查询结果 , 但由于可能世界实例的数量远大于不确定数据库的规模 , 该方法并不可行. 因此, 必须采用排序、 剪枝等启发式技术优化处理, 以提高效率. 另外, 由于输入数据具有不确定性, 查询结果也往往是近似结果.目前在研的主要项目不确定数据管理正成为一个研究热点 . 表 1 列举了一些知名大学以及公司的研究机构正在进行的相关科研项目的基本情况.表 1不确定性数据管理的相

20、关研究项目科研机构University of Puget SoundUn iversity of T oron to项目名称proTDBConquer链接地址http: / / ww w. math. ups. edu/ anierman/ umich/ protdb/http: / / queens. db. toronto.edu/project/ conquer/http: / / orion. cs. purdue. edu/描述主要研究概率半结构化数据的查询处理技术 .主要研究针对不一致数据库( inconsistent database) 的高效管理技术. 主要应用查询重写技术、

21、实时和动态数据清洗技术.曾用名: UDBMS, 是一个 通用 目的 的不确 定性 数据 库系统.它支持离散或连续的概率密度函数 ; 高效的访 问不确定性数据的方法; 优化连接、 选择等操作; 图形可视化界面 .主要研究不确定数据 管理技术, 特别是 针对不 确定数 据的世系分析技术. 它基于 UL DB 模型, 使用 TriQL 语言.研究内容包括: 查询语言、 表示与存储技术、 支持 数据清洗、高效的查询处理、 更新等.研究内容包括: 数据模型、 查询处理技术、 关系代数计算等 .该项目试图将现有的确定性数据管理框架与不确 定性查询处理技术相结合, 从而 使得新增 的功能 模块能 够嵌入 到

22、现有框架中, 增强其性能.研究概率聚集查询的计算方法,开发空间时间概率数据库.该项目有两大目标: ( 1) 从非结构化数据中抽取结 构化的信息; ( 2)基于这类信息构建下一代搜索和商业智能应用 .Purdue U nivers ityOrionStanford Un iversityCornell UniversityUniversity of WashingtonIntel/ BerkeleyUn iversity of MarylandIBM AlmadenTrioMayBMSMystiQHeisenDataProb DBsAvatarhttp: / / infolab. stanfor

23、d. edu/ trio/http: / / ww w. cs. cornell. edu/ database/ maybm s/http: / / www. cs. washington. edu/homes/ suciu/projectmystiq. htmlhttp: / / ww w. eecs. berkeley. edu/Research/ Projects/ Data/ 102060.htmlhttp: / / ww w. cs. um d. edu/ vs/research. htm# pdbhttp: / / ww w. almaden. ibm. com/cs/pr oje

24、cts/ avatar/R 与 Suciu 16观察到不确 定性数据广泛 出现在诸多应用之中, 并总结了不确定性数据管理所面临的巨大挑战 . Dalvi 和 Suciu 17进一步从理 论角度阐述不确定性数据管理的基础与挑战 . Agg arwal与 Yu 18面的进展, 特别是他们自己的工作 , 包括范围查询、skyline 查询与 Ranking 查询等. 本文则以不确定性数据管理的框架为主线, 综述了不确定性数据管理技术在数据模型、 预处理与集成、 存储与索引、 查询分析处理等方面所取得的重要进展. 本文第 2 5 节分别介绍上述 4个方面的内容; 第 6 节总结全文.从算法与应用角度综

25、述了不确定数据管理 19技术. Pei 等人回顾了近期不确定性查询处理方4计算机学报2009 年之间可能独立也可能存在依赖关系 . 首先假设各个2 数据模型与挑战2. 1可能世界模型不确定数据库建模的研究工作很多 , 可能世界模型则是应用最广泛的数据模型 1213. 在该模型中,各元组的任一合法组合均构成 一个可能世界 实例( instance) , 实例的概率值可以通过相关元组的概率计算得到. 可能世界实例的数量远远高于不确定性数据库的规模, 甚至是后者的指数倍, 这也是不确定性数据管理技术所面临的最大难点 . 考虑如图 2 所示的一个例子. 图 2( a) 是一个不确定性数据库 , 包含

26、3 个元组, 概率字段表示该元组的发生概率. 元组ID123信息概率0 30 70 6元组之间独立, 则共有 23= 8 个可能世界实例, 各实例的概率等于实例内元组的概率乘积与实例外元组的不发生概率的乘积, 如图 2(b) 所示. 例如, 可能世界实例1, 2 的发生概率为 0 3 ! 07! ( 1- 0 6) =0 084. 某些场景下, 元组之间并非独立, 而是存在依赖关系, 这种依赖关系可以用规则描述. 假设规则为13, 即元组 1 与元组 3 不能够同时发生 , 但可以同时不发生 20. 总共有 6 个可能世界 实例, 如图 2( b) 所示. 可能世界实例 1 的发生 概率为 0

27、3 !( 1- 0 7)= 0 09, 可能世界 实例 2 的发生 概率为( 1- 0 3- 06) ! 0 7= 0 07.元组独立: = , 1 , 2 , 3 , 1, 2 , 1, 3 , 2, 3 , 1, 2, 3 ()= .084, .036, .196, .126, .084, .054, .294, .126依赖规则: 13 = , 1 , 3 , 2 , 1, 2 , 2, 3 ()= .03, .09, .18, .07, .21, .42( b) 可能世界( a) 一个不确定数据库样例图 2可能世界样例在大多数应用中, 不确定性可细分为存在级不确定性( Existent

28、ial Uncertainty) 和属性级不确定性( AttributeLevel Uncertainty) . 存在级不确定性描述元组的存在与否, 较为普遍. 在图 2 中, 各元组均具备存在级不确定性. 属性级不确定性并不涉及整个元组的不确定性, 而是以概率密度函数或统计参数( 例如方差等) 来描述特定属性的不确定性. 例如,假设某传感器无法准确探测周围环境温度 , 典型的记录方式为: 70% 的概率为 26 , 30% 的概率为25 . 类似的记录均具有属性级不确定性. 属性级不确定性往往比存在级不确定性更容易处理 . 有些时候, 也可以将多个相关的元组视为单个含属性级不确定性的元组.

29、例如, 图 2( b) 定义了 依赖规则 13, 则元组 1 和 3 无法同时发生 . 可以将这两个元组视为单个元组, 该元组有存在级不确定性, 发生概率为 0 9; 该元组的信息字 段有属 性级不 确定性, 由离散概率 密度函 数描述( 信息=的概率为 1/ 3,信息=的概率为 2/3).作为不确定性数据库建模的最核心思想 , 可能世界模型被广泛采纳于各种应用之中 , 并衍生出多种应用相关的模型, 特别是针对关系型数据、 半结构化数据、 流数据和多维数据的模型.2. 2针对关系型数据的模型针对关系模型的扩展最为常见 , 包括 Probabilistic ?table 9, 11、 Proba

30、bilistic orset table 11、 Proba 11 13bilistic orset? table、 Probabilistic ctable等.Probabilistic ?table 以一个独立的概率字段表示元组的概率, 且各元组之间独立. 一个特定的数据库实例( 也即可能世界实例) 的概率等于其所包含的元组的概率乘积和其所不包含的元组的不发生概率的乘积. 图 3(a) 所示的 Probabilistic ?table 含 3 个字段 c1、 c2 与概率字段, 其中概率字段描述元组的发生概率. 该表中有 2 个元组, 可构成 4 个可能世界实例. Probabilisti

31、c ?table 能够描述存在级不确定性, 而 Probabilistic orset table 则倾向于描述属性级不确定性. 在 Probabilistic orset table 中, 元组的属性值被描述为多个候选值之间的 或 关系, 可视为离散概率密度函数. 以图 3( b) 为例, 元组 1 的 c2字段既可取 2, 也可取 3, 其概率分别为 0 4 和 0 6;元组 2 的 c2 字段既可取 4 也可取 5, 其概率分别是0 2 与 08. Probabilistic orset? table 13, 21则是上述两种模型的综合体. 例如, 在图 3( c) 中, 元组 2 本身

32、具有概率值, 而且其 c2 字段既可取 4, 也可取 5,概率分别 是 0 2 和 0 8. Probabilisticctable 的定义与 Probabilistic orset table 比较类似, 不同之处在于它是 从 c table 衍生而出 22. 部分学者也将probabilistic orset? table 命名为 xrelation, 它包含若干 xtuple ( 无存在级不确定性) 或者 maybextuple( 有存在级不确定性) 8, 23.1 期112223概率.5.6周傲英等: 不确定性数据管理技术研究综 述1122(#2, .4, #3, .6)(#4, .2

33、, #5, .8)1122(#2, .4, #3, .6)(#4, .2, #5, .8).8概率5( a) Probabilisti?table( b) Probab ilistiorset table( )Probabilistiorset? table图 3基于关系数据的扩展模型2. 3针对半结构化数据的模型半结构化数据模型( semistrutureddata model) 能有效描述缺乏严格模式结构的数据. 半结构化数据通常可以用文档树来描述. Dekhtyar 等人 25提出了一 种管理 概率半 结构化 数据( probabilistisemistrutureddata) 的方法,

34、 该方法以关系数据库技术为基础, 支持丰富的代数查询. 更多的工作则是直接以文档树形式描述不确定性半结构化数据 , 例如 文档模型( doumentmodel) 26、 概率树模型 24( Probabilistitree model) 2728、 PXDB 模型 29等.文档模型 26将概率值附加于文档树的边上,各节点的概率依赖于其祖先的概率 , 节点之间可以是互斥关系( mux) 或相互独立( ind). 在图 4( a) 所示的例子中, 共有 5 个节点, 4 条边. 边 AB 与A C 独立, 概率值分别为 07 和 0 8; 边 CD 与 CE 互斥,概率值分别为 0 4 与 0 5

35、. 此时, 包含且仅包含节点A 、 C、 D 的子图的概 率为( 1- 0 7) ! 0 8 ! 04=0 096; 任意子图均不能同时包含D、 E 两个节点.图 4常用的不确定性 XML 模型概率树模型是一个事件驱动的模型 2728. 它并不在各节点/ 边上附加概率值来描述不确定性, 而是在各节点附加一系列事件变量, 由外部事件的发生与否决定节点的存在性. 图 4( b) 描述了一个概率树的例子, 共有 2 个外部事件 w1和 w2, 其发生概率分别为0 7和 0 8. 节点 B 出现的前提条件是事件 w1发生且事件w2不发生; 节点E 存在的前提条件是事件 w2发生. 由于节点 B 与 E

36、 的存在条件互斥, 不存在同时包含节点 B、 E 的子图. 包含且仅包含 A、 C、D 3 个节点的子图的概率为(1- 0 8) ! (1- 07) =0 06, 前提是 w1、 w2均不发生 . 可以看出, 概率树模型的表达能力强于 文档模型.PXDB 模型 29扩展了文档模型, 增加外部约束条件. 在图 4( ) 所示的例子中 , 左下角是 一个完整的 文档; 右下角定义了两个子图 SA与 SAB, SA含节点A , SAB含节点 A 与 B. 限制条件为 : 对于任意一个 SA子图, 它所包含的 SAB子图的数量不能够超过1 个. 因此, 尽管 A B 边在文档中出现了 2次, 但它们无

37、法同时出现在任意一个子图之中.其他模型还包括 PXM L 模型 3031、 Keulen 等人的概率树模型、 PrXM L 模型2. 4针对数据流的模型 32 33等.在数据流模型中, 数据到达的速度极快、 数据规模极大, 仅能够开发一次扫描算法, 使用有限内存在线计算查 询结果. 在不确定性数据流( UnertainData Str eam, 或 ProbabilistiData Stream ) 中, 各元组具有不确定性. 文献 34 假设各元组可以在一个离散域 B 中取多值, 流上各元组的值是基于这些离散域的一个概率密度函数 , 例如某元组 t 被描述为(#i1,1, %,#im,m),

38、 则 !1 s m, 有 is& B,Pr is =s, 且s1. 例如, 考虑一 个温度传感1m器产生 的数据流, 环境温度范围( 离散 域 B) 是 - 30, 50 , 则可能的数据流为(#20, 0 4, #22,0 6), (#22, 0 8), (#21, 0 2, # 23, 0 7), %. 部分学者将研究重点放在一个基本特例, 即 m= 1.根据窗口定义不同 , 数据流模型可细分为界标模型、 滑动窗口模型. 界标模型的范围从某固定时间 356计算机学报2009 年点至当前时间为止, 滑动窗口模型仅考虑最新的 W个元组 36( 2) 新出现的维度 ) 概率维概率在不确定性数据管

39、理中扮演多重角色 . 输入数据可能有概率, 表示元组自身或者某字段具有不确定性; 输出结果可能有概率, 表明该项结果的发生概率; 查询定义可以有概率, 用于约束查询结果 ;处理过程也与概率紧密相关. 因此, 概率维的出现极大地改变了传统的数据处理模式 , 迫切需要开发新技术进行处理.( 3) 不确定性数据管理的理论问题在不确定数据库管理技术方面仍然存在大量具体问题, 特别是理论相关的问题 42. 在高效计算复杂条件下的聚集查询 ( 例如含有 HAVING 谓词的聚集查询) 处理起来困难较大. 灵活的约束条件能够提高数据质量, 是不确定性数据管理的重要工具, 但是当前仍不具备普遍接受的约束条件定

40、义方式. 在各模型中, 新元组的到达与旧元组的消逝均引发可能世界实例的大变迁 . 以上面的环境温度数据流为例,假设窗口大小 W= 2, 在时间点 2 时, 需基于元组(#20, 0 4, #22, 0 6)和(#22, 0 8)构造可能世界实例, 并回答查询; 在时间点 3 时, 则基于元组(#22, 0 8)和(#21, 02, #23, 07)构造可能世界实例, 并回答查询; 依此类推.另外, 在多数据流应用中, 不同数据流上到达的元组之间可能存在相关性, 必须整体考虑 37.2. 5针对多维数据的模型OLAP 提供了一种多维数据分析手段 , 能够快速得到复杂 的查询统计结果. OLAP

41、中数据立方( Data Cube) 的基本元素是 cuboid. 在确定性多维数据模型中, 各个事实 ( fact) 必定属于某一个 立方体中. 但对于处理不精确数据的应用而言, 各事实可能无法被准确地定位到立方体中. 例如, 考虑一个有关汽车销售的多维数据模型, 它包括两个维度: city 与automo bile, 分别表示购车城市与车体型号 . city 维度是一个三级层次结构, 国家(省 (市. 若仅仅知道某辆 奔驰车 是从 浙江北部城市 购买的话, 由于 浙江北部城市 包含多个城市 , 该条记录是不确定性数据, 无法存放到事实表中去 . 文献 3839 提出了基于可能世界的多维数据模

42、型 , 以处理这类不确定数据. 在这种模型中, 上述记录能够被存储于不确定性数据库中, 可以基于可能世界语义执行 OLAP操作( 例如切块、 上卷等) . 他们的后续工作也考虑到了元组之间存在相关性的情况 40.2. 6要求与挑战不确定数据管理技术采用与确定性数据管理技术截然不同的数据模型, 这使得不确定性数据管理技术面临以下挑战:( 1) 庞大的可能世界实例集合毫无疑问, 不确定性数据管理所面临的最直接的挑战就是其相对于数据库规模呈指数倍的可能世界实例的数量. 假设某不确 定性数据 库含 N 条元组, 各元组独立. 当该数据库仅有存在级不确定性 ,可能世界的数目将达到 2N个; 而若各个元组

43、还拥有属性级不确定性时, 可能世界的数目将远大于2N.如果查询要求访问所有的可能世界时 , 则这个查询开销将会是一个# P 问题 41. 因此, 需要在查询的准确度与查询开销之间进行权衡, 目标是以较小的计算开销获得高质量的近似结果.3 数据预处理和数据集成数据预处理与集成是很多数据管理应用不可或缺的组成部分. 在传统数据管理领域, 数据预处理是针对不准确、 不精确的数据进行数据清理、 数据转换等处理, 从而提升数据质量, 最终能够被确定性管理技术所处理. 例如, 由于多种原因, RFID 读卡器的能够正确读取RFID标签的概率约为60 70%左右, 即超过30%的数据被误读了 43. 数据误

44、读的原因很多,包括漏读、 多读、 脏数据等. 因此, RFID 应用的一大关键模块就是数据清洗模块 , 它将这些不准确的数据转化为准确的数据, 再进行后续处理. 这种方法被广泛应用于面向不精确数据的数据管理领域 . 该方法的不足之处主要有两点, 首先, 从不精确数据到精确数据的转换过程会损失原始数据的部分特征 , 无法准确反映原始数据的全貌; 其次, 一种数据清洗技术往往针对特定的原始数据( 例如, 漏读产生的数据集合) , 而非对所有数据集合均有效 , 这使得直接将数据清洗技术从一个应用搬到其他应用的难度加大 .数据预处理也包括将准确数据 ( 或者高精度数据) 转化为不精确的数据, 从而达到

45、隐私保护等特殊目的, 典型的例子是基于位置 的服务 LBS. 作为移动计算领域的核 心问题, LBS 在军事、 通信、 交通、服务业中均获得广泛应用. 服务器利用 GPS 等技术获取移动对象的实时位置信息, 并提供相应的服务.GPS 技术能够获取精度较高的位置信息 , 恶意用户完全能够根据某移动对象的运动轨迹推测出一些有 31 期周傲英等: 不确定性数据管理技术研究综 述7用的信息. 例如, 若某个对象每天早上沿相同路径移动, 则一般来说起点就是家庭地址, 而终点则是工作单位地址.匿名模型 ( anonymity model) 能够解决 这种隐私保护问题 6( 1) 不确定性数据源 . 不确定

46、性数据源是该数据集成系统最直接的动力. 很多情况都可能产生不确定性数据. 例如, 当数据从非结构化数据源或者半结构化数据源中自动抽取出来时, 会引入不确定性;当数据从某些不可靠的或者过时的站点获取时 , 也会引入不确定性.( 2) 不确定性模式映射 . 数据集成系统利用模式映射技术从多个原始数据源的模式构造中介模式( mediated schema) , 再利用中 介模式回答查 询. 事实上, 中介模 式也可能存 在不准 确性. 原因很多, 用户并非熟练地进行精确映射管理 , 比如在个人信息管理中; + 对某些字段的理解不充分 , 因此无法正确映射, 例如生物信息 ; , 超大数据规模阻止了产

47、生和维护精确映 射的可能, 例如 Web 数据集成. 实际应用中, 中介模式往往通过半自动化工具生成, 而非由领域专家特别指定.( 3) 不确定性查询. 查询也可能具备不确定性 .特别是在 Web 应用中, 查询往往以 关键词 形式被提交, 而并非一个定义规范的结构化查询. 系统需要将这些查询转化成某些结构化形式, 使得它 们能够在这些数据源上重新定义 . 在这个步骤, 系统可能会产生多 个候选 的结构 化查询, 并且拥有一些 不确定性. 该模型最早应用于关系模型, 关系中的属性被划分为准标识符 ( quasiidentifier ) 和敏感属性( sensitive attribute) ,

48、 使得任一准标 识符至少包括个不同元组. 位置匿名( locationanonym ity) 则是 匿名模型在 移动对象数据 库上的扩展, 当某消息被发送时 , 变换消息的空间信息 ,使其无法与其他- 1 条不同消息区分开来 44.Abul 等人 45定义了( , )匿名问题 ( ( )anonym ity problem ) , 在任一时刻, 总能够找到个对象, 聚集在半径为 的圆内, 作者同时提出了 NWA方法进行求解.数据预处理还包括从原始的不确定数据库中构造一个新数据集合, 并在此集合上计算查询结果. 这个做法会降低查询结果的准确度 , 但是能够提高查询处理的效率 46.数据集成是管理

49、多自治与异构数据源的应用所需面对的普遍挑战 47. 当前的数据集成系统仅是传统数据库的扩展, 查询以结构化格式定义, 数据以传统模型建模, 例如关系模型和 XML 模型等. 此外,系统也知道原始数据映射到中间模式的确切规则 .然而, 这些系统无法管理不确定性数据 . Philippi 和Kohler 48认为, 针对生命科学数据库的数据集成系统的最大挑战在于数据的不精确性 : 数据没有统一的概念模式,数据不完整, 缺乏部分信息, 且有不确定性. 事实上, 这种情况也在其他许多领域广泛存在 .Xin 等人最早研究了针对不确定性数据库的数据集成系统, 他们认为一个数据集成系统需要在三个层次上处理不

50、确定性 494 存储和索引目前, 传统的关系型数据存 储技术仍然是实现不确定性数据库的存储任务的主流技术. 例如,Orion 项目由 C 语言和 PL/ pgSQL 实现, 运行于Postg reSQL 之上; My stiQ 项目 51具有较好的层次结构, 支持 Postg reSQ L、 Sql Server 、 DB2 等关系型数据库; MayBM S运行于 Postg reSQL 之上; T rio项目的初版原型系统TrioOne 基于标准的关系数据库( postgreSQL) 53等. 图 6 描述了T rioOne 系统的架构. 该架构共有3 层, 用户界面层、 Trio 接口与转