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

第 32卷 第 1期 2009年 1月 计 算 机 学 报 CHINESE joURNAL OF COMPUTERS Vo1．32 No．1 Jan．2009 不确定性数据管理技术研究综述 周傲英” 金澈清” 王国仁 李建中 ”(华东师范大学软件学院 上海市高可信计算重点实验室 上海 200062) (东北大学信息科学与工程学院 沈阳 110004) ”(哈尔滨工业大学计算机科学与技术学院 哈尔滨 150001) 摘 要 随着数据采集和处理技术的进步，人们对数据的不确定性的认识也逐步深入．在诸如经济、军事、物流、金 融、电信等领域的具体应用中，数据的不确定性普遍存在．不确定性数据的表现形式多种多样，它们可以以关系型 数据、半结构化数据、流数据或移动对象数据等形式出现．目前，根据应用特点与数据形式差异，研究者已经提出了 多种针对不确定数据的数据模型．这些不确定性数据模型的核心思想都源 自于可能世界模型．可能世界模型从一 个或多个不确定的数据源演化出诸多确定的数据库实例，称为可能世界实例，而且所有实例的概率之和等于 1．尽 管可以首先分别为各个实例计算查询结果 ，然后合并中间结果以生成最终查询结果，但由于可能世界实例的数量 远大于不确定性数据库的规模，这种方法并不可行．因此 ，必须运用排序、剪枝等启发式技术设计新型算法 ，以提高 效率．文中介绍了不确定性数据管理技术的概念、特点与挑战，综述 了数据模型、数据预处理与集成、存储与索引、 查询处理等方面 的工作． 关键词 不确定性数据；可能世界模型；数据集成；世系；不确定数据流 中图法分类号 TP393 DOI号 ：10．3724／SP．J．1016．2009．00001 A Survey on the Management of Uncertain Data ZHOU Ao—Ying” JIN Che—Qing WANG Guo—Ren∞ LI Jian—Zhong。 ”(Shanghai Key Laboratory of Trustworthy Computing，So ware Engineering Institute，East China Normal University，Shanghai 200062) (School of Information Science and Engineering，Northeastern University。Shenyang 110004) ”(School of Computer Science and Technology，Harbin Institute of Technology，Harbin 150001) Abstract The importance of the data uncertainty was studied deeply with the rapid development in data gathering and processing in various fields，inclusive of economy，military，logistic，fi— nance and telecommunication，etc． Uncertain data has many different styles，such as relational data，semistructured data，streaming data，and moving objects．According to scenarios and data characteristics，tens of data models have been developed，stemming from the core possible world model that contains a huge number of the possible world instances with the sum of probabilities equal to 1．However，the number of the possible world instances is far greater than the volume of the uncertain database，making it infeasible to combine medial results generated from all of possi— ble world instances for the final query results．Thus，some heuristic techniques，such as orde— ring，pruning，must be used to reduce the computation cost for the high efficiency．This paper in— troduces the concepts，characteristics and challenges in uncertain data management，proposes the advance of the research on uncertain data management，including data model，preprocessing，in— tegrating，storage，indexing，and query processing． Keywords uncertain data；possible world model；data integration；lineage；uncertain stream 收稿 日期：2008—09—05．本课 题 快递公司问题件快递公司问题件货款处理关于圆的周长面积重点题型关于解方程组的题及答案关于南海问题 得到国家自然科学基金(60803020)、上海市重点学科建设项目(B412)资助．周傲英，男，1965年生，教授， 博士生导师，主要研究兴趣为数据管理与信息系统，包括：Web数据管理、中文Web基础设施、Web搜索与挖掘、数据流与数据挖掘、复 杂事件处理与实时商务智能、不确定数据管理及其应用、数据密集的计算、分布存储与计算、对等计算及其数据管理、Web服务计算等． 金澈清(通信作者)，男，1977年生，博士，副教授，主要研究方向为数据流管理、不确定性数据管理技术等．E-mail：cqjin@sei．ecnu．edu．ca． 王国仁，男，1966年生，教授，博士生导师，主要研究领域为 XML数据管理、生物信息学、分布与并行数据库、多媒体索引技术、并行计算 等．李建中，男，1950年生，教授，博士生导师，主要研究领域为数据库、并行计算等． 计 算 机 学 报 1 引 言 近四十年来，传统的确定性数据(deterministic data)管理技术得到了极大的发展，造就了一个数百 亿的数据库产业．数据库技术和系统已经成为信息 化社会基础设施建设的重要支撑．在传统数据库的 应用中，数据的存在性和精确性均确定无疑．近年 来，随着技术的进步和人们对数据采集和处理技术 理解的不断深入，不确定性数据(uncertain data)得 到了广泛的重视．在许多现实的应用中，例如经济、 军事、物流、金融、电信等领域，数据的不确定性普遍 存在，不确定性数据扮演着关键角色．传统的数据管 理技术却无法有效管理不确定性数据，这就引发了 学术界和工业界对研发新型的不确定性数据管理技 术的兴趣． 不确定性数据的产生原因比较复杂．可能是原 始数据本身不准确或是采用了粗粒度的数据集合， 也可能是为了满足特殊应用 目的或是在处理缺失 值、数据集成过程中而产生的． (1)原始数据不准确．这是产生不确定性数据 最直接的因素．首先，物理仪器所采集的数据的准确 度受仪器的精度制约．其次，在网络传输(特别是无 线网络传输)过程中，数据的准确性受到带宽、传输 延时、能量等因素影响．还有，在传感器网络应用[】 ] 与 RFID应用口 等场合，周围环境也会影响原始数 据的准确度． (2)使用粗粒度数据集合．很明显，从粗粒度数 据集合转换到细粒度数据集合的过程会引入不确定 性．例如，假设某人 口分布数据库 以乡为基础单位记 录全国的人口数量，而某应用却要求查询以村为基 础单位的人口数量，查询结果就存在不确定性． (3)满足特殊应用目的．出于隐私保护等特殊 不确定 厂 性数据 L 目的，某些应用无法获取原始的精确数据，而仅能够 得到变换之后的不精确数据． (4)处理缺失值．缺失值产生的原因很多，装备 故障、无法获取信息、与其他字段不一致、历史原因 等都可能产生缺失值．一种典型的处理方法是插值， 插值之后的数据可看作服从特定概率分布．另外，也 可以删除所有含缺失值的记录，但这个操作也在一 定程度上变动了原始数据的分布特征． (5)数据集成。不同数据源的数据信息可能是 不一致的，在数据集成过程中就会引入不确定性．例 如，Web中含很多信息，但是由于页面更新等因素， 许多页面的内容并不保持一致_4]． 对某些应用而言，还可能同时存在多种不确定 性．例如，基于位置的服务(Location-Based Service， LBS)[5 是移动计算领域的核心问题，在军事、通信、 交通、服务业等方面有着广泛的应用．LBS应用获 取各移动对象的位置，为用户提供定制服务，该过程 存在若干不确定性．首先，受技术手段(例如 GPS技 术)限制，移动对象的位置信息存在一定误差．其次， 移动对象可能暂时不在服务区，导致 LBS应用采集 的数据存在缺失值情况．最后，某些查询要求保护用 户的隐私信息，必须采用“位置隐私”等方式处理 查询 ． 实际上，针对不确定性数据 的研究工作 已经有 几十年历史了．从 20世纪 8O年代末开始，针对概率 数据库(probabilistic database)的研究工作就从未 间断过 ．这类研究工作将不确定性引入到关系 数据模型中去，取得了较大进展．近年来，针对不确 定性数据的研究工作则在更广的范围内取得了更大 的进展，即在更丰富的数据类型上处理更多种类的 查询任务．图 1描述了不确定性数据管理技术的典 型框架，它包含 4大部分：模型定义、预处理与集成、 存储与索引和查询分析处理． 晶日圄 蝣 模型定义 预处理与集成 存储与索引 查询分析处理 图 1 不确定性数据管理的框架 模型定义．定义与应用场景相匹配的数据模型 是不确定性数据管理的首要任务．在不确定性数据 管理领域，最常用的模型是可能世界模型(possible world．mode1) ．该模型从一个不确定性数据库 演化出很多确定的数据库实例(称为可能世界实 广 查询 结果 例)，而且所有实例的概率之和为 1．不确定性数据 的种类较多，例如关系型数据、半结构化数据、流数 据、移动对象数据等，尽管存在许多与数据类型紧密 相关的数据模型，但是这些模型最终都可以转化为 可能世界模型． 1期 周傲英等：不确定性数据管理技术研究综述 3 预处理与集成．某些应用需要为数据执行预处 理操作，主动引入不确定性，从而达到信息隐藏和隐 私保护的目的．这种不确定性会降低查询结果质量， 必须在查询质量与信息隐藏程度之间进行权衡．当 应用需要使用多个数据源时，数据不一致性问题就 凸显出来．这个问题在 WEB上尤为突出．数据集成 所要应对的不确定性问题不仅包括原始数据不一 致，还包括模式匹配不确定、待处理的查询语义不确 定等多种因素． 存储与索引．有效的存储和索引技术能够大幅 提高数据管理效率．尽管可以基于传统的关系型数 据存储技术实现不确定性数据库的存储任务，但仍 有必要开发新型存储技术，以提高特定查询任务(例 如数据世系，data lineage)的执行效率。概要数据结 构(synopsis data structure)是存储流数据 (data stream)[¨。 ]的典型技术．不确定性数据与确定性数 据的最大区别在于不确定性数据含有概率维度．一 部分查询任务仅使用基于非概率维度的索引．例如， 在处理不确定 Top一是查询的过程中，往往只需对值 维度以 ranking 函数 excel方差函数excelsd函数已知函数     2 f x m x mx m      2 1 4 2拉格朗日函数pdf函数公式下载 创建索引．另一类查询则需针 对概率维度开发新的索引技术，例如，范围查询 (Range query)、最 近邻查 询 (Nearest Neighbor query)等．当概率维度以概率密度函数(probabilis— tic density function，简称 pdf)描述而非概率值时， 创建索引的难度更大． 查询分析处理．查询分析处理是不确定性数据 管理的最终目标．查询类型非常丰富，例如关系查询 操作、数据世系、XML处理、流数据查询、Ranking 查询、Skyline查询、OLAP分析、数据挖掘等．尽管 可以分别针对各个可能世界实例计算查询结果，再 合并中间结果以生成最终查询结果，但由于可能世 界实例的数量远大于不确定数据库的规模，该方法 并不可行．因此，必须采用排序、剪枝等启发式技术 优化处理，以提高效率．另外，由于输人数据具有不 确定性，查询结果也往往是近似结果． 目前在研的主要项 目 不确定数据管理正成为一个研究热点．表 1列 举了一些知名大学以及公司的研究机构正在进行的 相关科研项目的基本情况． 表 1 不确定性数据管理的相关研究项目 R邑与 Suciu[1 观察到不确定性数据广泛出现 在诸多应用之中，并总结了不确定性数据管理所面 临的巨大挑战．Dalvi和 Suciu 进一 步从 理论角 度阐述不确定性数据管理的基础与挑战．Aggarwal 与 Yu_1。 从算法与应用角度综述了不确定数据管理 技术．Pei等人[1 回顾了近期不确定 性查询处理方 面的进展，特别是他们自己的工作，包括范围查询、 skyline查询与 Ranking查询等．本文则以不确定性 数据管理的框架为主线，综述了不确定性数据管理 技术在数据模型、预处理与集成、存储与索引、查询 分析处理等方面所取得的重要进展．本文第 2～5节 分别介绍上述 4个方面的内容；第 6节总结全文． 计 算 机 学 报 2 数据模型与挑战 2．1 可能世界模型 不确定数据库建模的研究工作很多，可能世界 模型则是应用最广泛的数据模型[1 ¨ ]．在该模型中， 各元组的任一合法组合均构成一个可能世界实例 (instance)，实例的概率值可以通过相关元组的概率 计算得到．可能世界实例的数量远远高于不确定性 数据库的规模，甚至是后者的指数倍，这也是不确定 性数据管理技术所面临的最大难点．考虑如图 2所 示的一个例子．图 2(a)是一个不确定性数据库，包 含 3个元组，概率字段表示该元组的发生概率．元组 (a)一个不确定数据库样例 之间可能独立也可能存在依赖关系．首先假设各个 元组之间独立，则共有 2。一8个可能世界实例，各实 例的概率等于实例内元组的概率乘积与实例外元组 的不发生概率的乘积，如图 2(b)所示．例如，可能世 界实例{1，2}的发生概率为 0．3×0．7×(1—0．6)一 0．084．某些场景下，元组之间并非独立，而是存在依 赖关系，这种依赖关系可以用规则描述．假设规则为 1o 3，即元组 1与元组 3不能够同时发生，但可以 同时不发生_2 ．总共有 6个可能世界实例，如图 2 (b)所示．可能世界实例 {1}的发生概率为 0．3× (1—0．7)一0．09，可能世界实例{2)的发生概率为 (1— 0．3—0．6)×O．7—0．07． 元组独立 ： 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(P∽ ={．03，．09。．18，．O7，．21，．42} (b)可能世界 图 2 可能世界样例 在大多数应用中，不确定性可细分为存在级不 确定性(Existential Uncertainty)和属性级不确定性 (Attribute Level Uncertainty)．存在级不确定性描 述元组的存在与否，较为普遍．在图 2中，各元组均 具备存在级不确定性．属性级不确定性并不涉及整 个元组的不确定性，而是以概率密度函数或统计参 数(例如方差等)来描述特定属性的不确定性．例如， 假设某传感器无法准确探测周围环境温度，典型的 记录方式为：70 的概率为 26℃，3O 的概率为 25℃．类似的记录均具有属性级不确定性．属性级不 确定性往往比存在级不确定性更容易处理．有些时 候，也可以将多个相关的元组视为单个含属性级不 确定性的元组．例如，图 2(b)定义了依赖规则 1 0 3，则元组 1和 3无法同时发生．可以将这两个元组 视为单个元组，该元组有存在级不确定性，发生概率 为 0．9；该元组的信息字段有属性级不确定性，由 离散概率密度函数描述(信息一A的概率为 1／3， 信息一C的概率为2／3)． 作为不确定性数据库建模的最核心思想，可能 世界模型被广泛采纳于各种应用之中，并衍生出多 种应用相关的模型，特别是针对关系型数据、半结构 化数据、流数据和多维数据的模型． 2．2 针对关系型数据的模型 针对关系模型的扩展最为常见，包括 Probabi— listic?一table／。’ 、Probabilistic or-set table[ 、Proba— bilistic or-set-?table[¨]、Probabilistic C—table／¨]等． Probabilistic?-table以一个独立的概率字段表 示元组的概率，且各元组之间独立．一个特定的数据 库实例(也即可能世界实例)的概率等于其所包含的 元组的概率乘积和其所不包含的元组的不发生概率 的乘积．图3(a)所示的Probabilistic?一table含 3个 字段 c1、c2与概率字段，其中概率字段描述元组的 发生概率．该表中有 2个元组，可构成4个可能世界 实例．Probabilistic?一table能够描述存在级不确定 性，而 Probabilistic or—set table则倾 向于描述属性 级不确定性．在 Probabilistic or—set table中，元组的 属性值被描述为多个候选值之间的“或”关系，可视 为离散概率密度函数．以图 3(b)为例，元组 1的 c2 字段既可取 2，也可取 3，其概率分别为 0．4和 0．6； 元组 2的 c2字段既可取 4也可取 5，其概率分别是 0．2与 0．8．Probabilistic or—set一?table_】。 则是上 述两种模型的综合体．例如，在图 3(c)中，元组 2本 身具有概率值，而且其 c2字段既可取 4，也可取 5， 概率分别是 0．2和 0．8．Probabilistic c—table的定 义与 Probabilistic or—set table比较类似，不同之处 在于它是从 C table衍生而出r2 ．部分学者也将 probabilistic or—set一?table命名为 x-relation，它包 含若干 x-tuple(无存在级不确定性)或者 maybe x-tuple(有存在级不确定性)[8 引． 1期 周傲英等：不确定性数据管理技术研究综述 c1 c2 概率 l 2 ．5 2 3 ．6 (a)Probabilistic?-table c2 概率 (b)Probabilistie or-set table 图 3 基于关系数据的扩展模型 2．3 针对半结构化数据的模型 半结构化数据模型(semistructured data rood- e1)能有效描述缺乏严格模式结构的数据 ．半结构 化数据通常可以用文档树来描述．Dekhtyar等人[ ] 提出了一种管理概率半结构化数据(probabilistic semistructured data)的方法，该方法以关系数据库 技术为基础，支持丰富的代数查询．更多的工作则是 直接以文档树形式描述不确定性半结构化数据，例 如 P一文档模型( —document mode1)[2 、概率树模型 (Probabilistie tree mode1)[27_ ]、PXDB模型 等． P一文档模型 将概率值附加于文档树的边上， 各节点的概率依赖于其祖先的概率，节点之间可以 是互斥关系(mux)或相互独立(ind)．在图4(a)所示 的例子中，共有 5个节点，4条边．边 A—B与A-C独 立，概率值分别为 0．7和 0．8；边 C—D与C-E互斥， 概率值分别为 0．4与 0．5．此时，包含且仅包含节点 A、C、D 的子图的概率为(1—0．7)X 0．8×0．4— 0．096；任意子图均不能同时包含 D、E两个节点． 限制条件：VS^，[CNT(十一s ) 1] (a)P—documentmodel (b)Probabilistictreemodel (c)PXDBmodel 图 4 常用的不确定性 XML模型 概率树模型是一个事件驱动的模型[2 引．它并 不在各节点／边上附加概率值来描述不确定性，而是 在各节点附加一系列事件变量，由外部事件的发生 与否决定节点的存在性．图 4(b)描述了一个概率树 的例子，共有 2个外部事件 W 和 W ，其发生概率分 别为 0．7和0．8．节点B出现的前提条件是事件W。 发生且事件W 不发生；节点E存在的前提条件是事 件 Wz发生．由于节点 B与 E的存在条件互斥 ，不存 在同时包含节点B、E的子图．包含且仅包含 A、C、 D 3个节点的子图的概率为(1—0．8)×(1—0．7)一 0．06，前提是 W 、W。均不发生．可以看出，概率树模 型的表达能力强于 声一文档模型． PXDB模型L2 扩展了P一文档模型，增加外部约 束条件．在图 4(c)所示的例子中，左下角是一个完 整的P一文档；右下角定义了两个子图 sA与S们，S^ 含节点A，S e含节点 A与 B．限制条件为：对于任 意一个 S 子图，它所包含的 S一。子图的数量不能够 超过 1个．因此，尽管A—B边在P一文档中出现了2 次，但它们无法同时出现在任意一个子图之中． S 团 SAB 冒 其他模型还包括 PXML模型[3。。。 、Keulen等 人的概率树模型 ]、PrXML模型 。。 等． 2．4 针对数据流的模型 在数据流模型中，数据到达的速度极快、数据规 模极大，仅能够开发一次扫描算法，使用有限内存在 线计算查询结果．在不确定性数据流 (Uncertain Data Stream，或 Probabilistic Data Stream)中，各 元组具有不确定性．文献[34]假设各元组可以在一 个离散域 B中取多值，流上各元组的值是基于这些 离散域的一个概率密度函数，例如某元组 t被描述 为()，则 V1 sGm，有 i ∈B， 卅 Pr ]=P ，且 P 1．例如，考虑一个温度传感 。 1 器产生 的数据流，环境温度范 围(离散域 B)是 [一30，5O]，则可能的数据流为(((20，0．4>，<22， 0．6>)，(<22，0．8>)，((21，0．2>，<23，0．7>)，⋯)．部分 学者将研究重点放在一个基本特例，即 =1[3引． 根据窗口定义不同，数据流模型可细分为界标 模型、滑动窗口模型．界标模型的范围从某固定时间 计 算 机 学 报 点至当前时间为止，滑动窗口模型仅考虑最新的 个元组 ．在各模型中，新元组的到达与旧元组的消 逝均引发可能世界实例的大变迁．以上面的环境温度 数据流为例，假设窗口大小w一2，在时间点 2时，需 基于元组(<20，0．4)，(22，0．6))和((22，0．8>)构造 可能世界实例，并回答查询；在时间点 3时，则基于 元组((22，0．8>)和(<21，0．2)，(23，0．7))构造可能 世界实例，并回答查询；依此类推． 另外，在多数据流应用中，不同数据流上到达的 元组之间可能存在相关性，必须整体考虑[3 ． 2．5 针对多维数据的模型 OLAP提供了一种多维数据分析手段，能够快 速得到复杂的查询统计结果．OLAP中数据立方 (Data Cube)的基本元素是 cuboid．在确定性 多维数 据模型中，各个事实(fact)必定属于某一个立方体 中．但对于处理不精确数据的应用而言，各事实可能 无法被准确地定位到立方体中．例如，考虑一个有关 汽车销售的多维数据模型，它包括两个维度：city与 automobile，分别表示购车城市与车体型号．city维 度是一个三级层次结构，国家一省一市．若仅仅知道 某辆“奔驰车”是从“浙江北部城市”购买的话，由于 “浙江北部城市”包含多个城市，该条记录是不确定 性数据，无法存放到事实表中去．文献E38—39]提出 了基于可能世界的多维数据模型，以处理这类不确 定数据．在这种模型中，上述记录能够被存储于不确 定性数据库中，可以基于可能世界语义执行 OLAP 操作(例如切块、上卷等)．他们的后续工作也考虑到 了元组之间存在相关性的情况_4 ． 2．6 要求与挑战 不确定数据管理技术采用与确定性数据管理技 术截然不同的数据模型，这使得不确定性数据管理 技术面临以下挑战： (1)庞大的可能世界实例集合 毫无疑问，不确定性数据管理所面临的最直接 的挑战就是其相对于数据库规模呈指数倍的可能世 界实例的数量．假设某不确定性数据库含 N条元 组，各元组独立．当该数据库仅有存在级不确定性， 可能世界的数目将达到 2 个；而若各个元组还拥有 属性级不确定性时，可能世界的数 目将远大于 2 ． 如果查询要求访问所有的可能世界时，则这个查询 开销将会是一个 #P问题 ．因此，需要在查询的准 确度与查询开销之间进行权衡，目标是以较小的计 算开销获得高质量的近似结果． (2)新出现的维度——概率维 概率在不确定性数据管理中扮演多重角色．输 入数据可能有概率，表示元组 自身或者某字段具有 不确定性；输出结果可能有概率，表明该项结果的发 生概率；查询定义可以有概率，用于约束查询结果； 处理过程也与概率紧密相关．因此，概率维的出现极 大地改变 了传统的数据处理模式 ，迫切需要开发新 技术进行处理． (3)不确定性数据管理的理论问题 在不确定数据库管理技术方面仍然存在大量具 体问题，特别是理论相关的问题r4引．在高效计算复 杂条件下的聚集查询(例如含有 HAVING谓词的 聚集查询)处理起来困难较大．灵活的约束条件能够 提高数据质量，是不确定性数据管理的重要工具，但 是当前仍不具备普遍接受的约束条件定义方式． 3 数据预处理和数据集成 数据预处理与集成是很多数据管理应用不可或 缺的组成部分．在传统数据管理领域，数据预处理是 针对不准确、不精确的数据进行数据清理、数据转换 等处理，从而提升数据质量，最终能够被确定性管理 技术所处理．例如，由于多种原因，RFID读卡器的能 够正确读取 RFID标签的概率约为 60~70 左右，即 超过 30 的数据被误读了_4 ．数据误读的原因很多， 包括漏读、多读、脏数据等．因此，RFID应用的一大 关键模块就是数据清洗模块，它将这些不准确的数 据转化为准确的数据，再进行后续处理．这种方法被 广泛应用于面向不精确数据的数据管理领域．该方 法的不足之处主要有两点，首先，从不精确数据到精 确数据的转换过程会损失原始数据的部分特征，无 法准确反映原始数据的全貌；其次，一种数据清洗技 术往往针对特定的原始数据(例如，漏读产生的数据 集合)，而非对所有数据集合均有效，这使得直接将数 据清洗技术从一个应用搬到其他应用的难度加大[3]． 数据预处理也包括将准确数据(或者高精度数 据)转化为不精确的数据，从而达到隐私保护等特殊 目的，典型的例子是基于位置的服务 LBS．作为移 动计算领域的核心问题，LBS在军事、通信、交通、 服务业中均获得广泛应用．服务器利用 GPS等技术 获取移动对象的实时位置信息，并提供相应的服务． GPS技术能够获取精度较高的位置信息，恶意用户 完全能够根据某移动对象的运动轨迹推测出一些有 1期 周傲英等：不确定性数据管理技术研究综述 7 用的信息．例如，若某个对象每天早上沿相同路径移 动，则一般来说起点就是家庭地址，而终点则是工作 单位地址． k一匿名模型(愚一anonymity mode1)能够解决这 种隐私保护问题[6]．该模型最早应用于关系模型，关 系中的属性被划分为准标识符(quasi—identifier)和 敏感属性(sensitive attribute)，使得任一准标识符 至少包括 k个不 同元组．位置 忌一匿名 (1ocation k— anonymity)则是 是一匿名模型在移动对象数据库上 的扩展，当某消息被发送时，变换消息的空间信息， 使其无法与其他 k一1条不同消息区分开来l_4 ． Abul等人l4朝定义了(忌， )一匿名问题 ((足一 )一ano— nymity problem)，在任一时刻，总能够找到 k个对 象，聚集在半径为 的圆内，作者同时提出了 NWA 方法进行求解． 数据预处理还包括从原始的不确定数据库中构 造一个新数据集合，并在此集合上计算查询结果．这 个做法会降低查询结果的准确度，但是能够提高查 询处理的效率[4 ． 数据集成是管理多自治与异构数据源的应用所 需面对的普遍挑战_4 ．当前的数据集成系统仅是传 统数据库的扩展，查询以结构化格式定义，数据以传 统模型建模，例如关系模型和 XML模型等．此外， 系统也知道原始数据映射到中间模式的确切规则． 然而 ，这些系统无 法管理不确定性数据．Philippi和 Kohler[48]认为，针对生命科学数据库的数据集成系 统的最大挑战在于数据的不精确性：数据没有统一 的概念模式，数据不完整，缺乏部分信息，且有不确定 性．事实上，这种情况也在其他许多领域广泛存在． Xin等人最早研究了针对不确定性数据库的数 据集成系统，他们认为一个数据集成系统需要在三 个层次上处理不确定性 ：不确定性数据源、不确 定性模式映射、不确定性查询．系统的基本框架结构 如图 5所示． 图 5 面向不确定数据的数据集成系统架构 (1)不确定性数据源．不确定性数据源是该数 据集成系统最直接的动力．很多情况都可能产生不 确定性数据．例如，当数据从非结构化数据源或者半 结构化数据源中自动抽取出来时，会引入不确定性； 当数据从某些不可靠的或者过时的站点获取时，也 会引入不确定性． (2)不确定性模式映射．数据集成系统利用模 式映射技术从多个原始数据源的模式构造中介模式 (mediated schema)，再利用中介模式回答查询．事 实上，中介模式也可能存在不准确性．原因很多， ①用户并非熟练地进行精确映射管理，比如在个人 信息管理中；②对某些字段的理解不充分，因此无 法正确映射 ，例如生物信息；③超大数据规模阻止 了产生和维护精确映射的可能，例如 Web数据集 成．实际应用中，中介模式往往通过半自动化工具生 成，而非由领域专家特别指定． (3)不确定性查询．查询也可能具备不确定性． 特别是在 Web应用中，查询往往以“关键词”形式被 提交 ，而并非一个定义规范的结构化查询．系统需要 将这些查询转化成某些结构化形式，使得它们能够 在这些数据源上重新定义．在这个步骤，系统可能 会产生多个候选的结构化查询，并且拥有一些不 确定性． 4 存储和索引 目前 ，传统的关系型数据存储技术仍然是实 现不确定性数据库的存储任务的主流技术．例如， Orion项 目Eso]由 C语言和 PL／pgSQL实现，运行 于 PostgreSQL之上 ；MystiQ项 目[51]具有较好的层次 结构，支持 PostgreSQL、Sql Server、DB2等关系型 数据库；MayBMS_5 ]运行于 PostgreSQL之上；Trio 项 目的初版原型系统 Trio—One基于 标准 excel标准偏差excel标准偏差函数exl标准差函数国标检验抽样标准表免费下载红头文件格式标准下载 的关系数据 库(postgreSQL)l_5 等．图 6描述了 Trio-One系统的 架构．该架构共有 3层，用户界面层、Trio接口与转换 层、关系数据库管理系统．用户界面层包括命令行界 面与图形用户界面，并将指令以TriQL语言(Trio项 目的查询语言)的形式传递给下一层．中间层是通过 Python实现的 Trio接口和转换器，它将来自用户界 面层的TriQL指令翻译成标准的SQL语句，发送底 层的关系数据库管理系统．关系数据库管理系统存 储了一些必要的元数据、存储过程、编码数据表和世 系表等，它处理来自中间层的 SQL语句，将查询结 果经由中间层送到用户界面层，并呈现给终端用户． 计 算 机 学 报 ， ——————，_，。_、 ，—— _，————— ___、 图 6 Trio—One的系统架构L53d 关系型的存储技术比较直接，但是无法有效处 理部分特殊查询，例如数据世系等．一些研究小组逐 渐认识到应该开发新的存储技术．例如，Trio项目 组认为一些数据库物理设计问题非常重要，包括数 据呈现(Data layout)、索引(indexing)、划分(parti— tioning)、物化视图(materialized view)等．因此，他 们期望新版的 Trio系统不再是简单地基于现有 RDBMS之上，而是能够将一些针对性的设计理念 融入到数据库物理设计 中去，以提高查询处理 性能 ． 另外，对于不确定性数据流而言，其存储任务仍 旧是构建基于内存的各种概要数据结构，而非基于 磁盘的数据结构，以便实时计算查询结果．半结构化 数据的通用存储形式是文档树． 有效的索引能够大幅提高查询效率．不确定性 数据含有概率维度，有些查询仅使用非概率维度的 索引，而有些查询却需要对概率维度进行索引．例 如，处理不确定 Top—k查询过程就仅需以 ranking 函数对特定值维度进行索引[20,s4]，而处理范围查 询[5 引、最近邻查询(Nearest Neighbor query，NN query)r5 等则迫切需要对概率维度进行索引Is6]． 在移动对象数据库等应用中，物体在某时刻的 位置可能并非确定，仅知道在一个较大的区域之内， 一 般用概率密度函数(pdf)描述．R树 。 以及其变 种是为高维数据创建索引的重要手段，一种方法是 以pdf的覆盖范围作为该物体的实际空间尺寸，并 建立索引．但是这个方法的可行性不高，原因在于 pdf所覆盖的范围可能很大，而物体最可能出现的 地方却是其中的一小块地方．构建索引必须考虑 pdf的分布特征． 概率阈值索引 (Probability Threshold Inde— xing，PTI)[5 能够实现对一维数据 的索引．假设数 据库中各元组的属性值对应一个一维区间[n，6]，可 以设置多个 z—bound．各个x-bound由两根线组成， 在线的左边或右边，其总概率均不超过 z．令 表 示第i个元组的 MBR，Mi．1b(x)和M ．rb(x)分别表 示 X—bound的左边和右边值，L 和R 分别表示最左 边和最右边的值，厂f表示该元组的概率密度函数，则 rM ．1b( ) rR 我们有I‘ 厂 ( )d Gx和I ( )d z．该 d L l dMi·rb(x) 做法能够避免一些额外的计算． U—tree可被视为是 PTI的多维扩展版本 ． 令 0表示 任一对 象，o．ur表 示该对 象 的范围， o．pdf(·)表示该对象的概率密度函数．当位置z在 0．ur之内时，0．pdf(x)>0；否则，0．pdf(x)一0．该 方法 基于概 率约 束 区域 (Probabilistically Con— strained Region，PCR)技术，首先将区域划分成若 干个规则的矩形，各个矩形分别和一个概率相关，然 后利用 U—tree(类似于 R树)对这些 PCR进行索 引．这些 PCR有助于在查询过程中进行剪枝、验证 等操作．图 7描述了一个不确定对象 0的示意图．整 个凸多边形 就是 0．ur，它被 4条线 (1。一，l +，z。一， z +)切出中间一块空白的矩形，即 PCR，满足条件： 在 Z 一左边、Z 右边 、Z +上面 、Z 一下边的区域的发生 概率各为 0．2．例如，针对 z卜可以有 LL2-~(z， )d d 一。．2． — — — l l。+ 钐 f2_ z 一 ￡ + 图 7 PCR例子 Ljosa等人田 提出了 APLA—tree技术，创建多 维索引，他们同时也针对 kNN查询进行了优化． 5 查询与分析 5．1 关系代数处理 关系型不确定性数据管理技术的研究工作起源 较早，从 20世纪 8O年代后期到现在一直在延续．根 据存在级不确定性与属性级不确定性，细分的数据 模型就有 Probabilistie?一table_g 、Probabilistic or- set table_】 、Probabilistie e—table等．一般可以向数 1期 周傲英等：不确定性数据管理技术研究综述 9 据库提交类似于 sQL的查询语句，从而返回查询结 果．这其中如何计算查询结果的概率值是一个大的 研究问题． Andritsos等人提 出了查询重写技术来处理 查询[6引．给定一个 SPJ查询：“select Al，⋯，A from R1，⋯，R where W”，可 以将 其 转 化 为 “ select A1，⋯ ，A ， sum(R卜prob．*⋯ *R ．prob) from R1，⋯，R where W group by A1，⋯ ，A ”．新 的查询语句中包含了结果查询的产生概率值． Sen和 Deshpande等人则利用构建图模型的方 法来处理 SQL语句[6 ．数据库上的查询 评价 LEC评价法下载LEC评价法下载评价量规免费下载学院评价表文档下载学院评价表文档下载 问题 看作是基于概率图模 型上的推断问题．文 中应用概 率图模型来刻画元组间的相关关系，并应用概率图 模型来分解联合概率分布，通过分解后因子表达式 中的条件概率分布计算并返回查询概率． 要完整地计算出查询结果有时是非常困难的． 研究结果表明，一个含连接操作的查询要么相对于 概率数据库在多项式复杂度的时间内被计算出来， 要么相对于概率数据库是#P一完全问题[4 ． 文献[653研究了近似查询及其复杂性． 5．2 世系分析 数据的世系(1ineage或者 provenance)是指数 据产生并随着时间推移而演变的整个过程 ．现有 工作大多针对确定性数据库，但很多应用(特别是超 T、 目击调查 ⋯ (目击者 ， 车型) 21 (张三，宝马)}1(张三，奔驰) 22 (李四，奔驰) ID 驾驶记录 (驾驶员，车型) ? 31 (王五 ，宝马) ? 32 (赵六 ，奔驰) (a)目击调查表 大规模应用)往往需面对不精确数据集合，而非精确 的数据集合，包括科学数据管理、传感器数据管理、 近似查询处理、隐私保护等[6 ．例如，一些大型科研 项目必须由多个科研小组分工合作完成，一部分小组 的任务是制造并记录大量原始实验数据，另一部分学 者基于原始数据、外部数据与中间数据进行分析，生 成新数据集合，乃至最终获取查询结果．在整个数据 演化过程中，各环节所产生的不确定性不断传递、放 大，从而能够极大地影响最终查询结果的质量． Trio项 目最早研究如何整合不确定性与数据 的世系_6 ．该项 目定义了 ULDB(Uncertainty—Line— age Database)，面向世系分析的不确定性数据库，并 证明它是完全的(complete)；提出了执行关系操作 的算法 。 ． 图 8是一个关于犯罪现场数据的世系的例子． 图 8(a)是 目击调查表，张三与李 四是两个 目击证 人，张三看到的可能是宝马或者奔驰，李四看到的是 奔驰．图 8(b)是驾驶 记录表 ，记录在某个时段 内通 过某区域的所有宝马与奔驰车辆以及车主．图8(c) 是通过上述两个表生成的 3项指控记录．例如，指控 记录 42的世系为(42，1)==={(21，2)，(32，1)}，表示 张三指控赵六，证据是目击调查表的记录 21的第 2 项与驾驶记录表的记录 32．但由于目击调查表存在 不确定性，这项指控本身也存在不确定性． (b)驾驶记录表 (c)指控表 图 8 一个数据世系的例子 当数据的世系比较复杂时，如何计算查询结果 的概率就成为一件困难的事情．当不考虑概率因素 时，可以为某一个数据世系设计多种查询 计划 项目进度计划表范例计划下载计划下载计划下载课程教学计划下载 ，并且 得到相同结果．但是当存在概率因素时，不同查询计 划返回的查询结果的概率值却可能不同．其原因是 在设计查询计划的过程中未考虑到数据的相关性特 征，导致重复计算口 ．文献[693提出了一种数据计 算与概率计算解偶的技术，使两者可以分开计算，这 样一方面概率值可以采用传统的关系型数据库方法 进行计算，另一方面，如果用户并不关注查询结果的 概率，则可以节约计算概率值的开销． 在一些大型应用(特别是生物数据库)中，元组 的世系可能非常庞大，甚至高达 10MB，而其中大部 分数据仅对结果产生较小的影响．文献[7O]就考虑 以高效的方法近似描述一个元组的数据世系． 5．3 Top-k查询 面向确定性数据库 的 top@ 查询 的定义非常清 晰：返回 ranking函数值最大的 k个元组．但是在不 确定性 数 据库 上 却存 在多 种定 义 方法，例 如 U—Topk[ 、U一是RanksE。 、PT一是[ 。 和 pk'-topkE。 查 询等．U—Topk查询返回一个长度为是的元组矢量， 它在所有可能世界中的发生概率最大；U—kRanks 查询返回在各个级别中出现的总概率最大的元组； PT—k首先定义一个阈值P，返回所有在可能世界实 1O 计 算 机 学 报 例中成为 top—k的总概率超过阈值的元组；Pk-topk 则返回在所有可能世界实例 中成为 top—k的总概率 最大的k个元组．假设一个不确定数据库含有 4个 元组 ，即{t1一(5，0．8)，t2一(6，0．5)，t。一(8，0．4)， t4一(2，0．4)}．当 k：2时，U—topk返 回 (t2，t1)， U—kRanks返 回( 3，t1)，PT—k返回( 1，t2，t3)；当 P一 0．3时，Pk—topk返回(t1，t2)． Soliman等人提出了基于搜索空间的方法来处 理 U—Topk查询与 U—kRanks查询 ．各元组首先 按照 ranking函数从大到小进行排序 ，然后不断地 构造搜索空间，缩小空间的范围，最终获得查询结 果．Cheng等人针对 U—Topk查询提出了一种动态 维护的结构，支持元组的插入与删除_7 ．Hua等人 针对 PT—k查询提 出了构造 dominant集合 的方 法l2 ．在其后续工作中，也提出了近似解决方案 ． 上述算法均需要预先对数据进行排序．Jin等人[3 ] 提出了面向数据流应用的 Top—k查询处理算法，不 仅能够解决上述 4种查询，而且是一次遍历算法，能 够处理数据流应用． 上述 4种查询均可视为是从单个数据库表中获 取的数据．R6等人_7 3_则研究了在多表之间做连接 操作的情况．各个表的数据并不精确，存在不一致 性．他们的基本想法是并行地运行多个 Monte— Carlo模拟器，每一个对应于一个候选的答案，再计 算各个候选答案的近似概率． 5．4 Skyline查询 Skyline查询[7 ]能用于解决 多准则决策(Muli— Criteria Decision—Making，MCDM)问题．给定一个 确定性的 一维数据集合 D，任一点 d可被表示为 ( ．D ，⋯，d．D )．Skyline查询返回数据集合 S， S D，则 Vu∈S，不存在其它点 ，满足(1)对 于任 一 维度 (1--< )，U．D ．D ；(2)存在一个维度 J(1Gj )使得 “．D，< ．D，． 近来 ，面向不确定性数据的 skyline查询处理问 题也得到了关注．各个元组的值并不确定 ，以概率密 度函数描述．Pei等人根据可能世界模型定义了概 率 skyline查询口引．不确定性数据库会衍生出很多 可能世界实例，各元组在各可能世界实例中可能是 skyline点地 可能不是 skyline点．由此，p—skyline 查询(0 P 1)被定义为返回所有成为 skyline点 的概率超过 P的数据点．文献[753同时提出了两种 解决方法：自下而上方法(bottom—up method)和自 上而下方法(top—down method)，分别采用不同的定 界、剪枝、精化等启发式规则进行迭代处理． Lian与 Chen等人则考虑了如何在不确定数据 集合上处理 reverse skyline查询 的问题[77]．确定 性 reverse skyline查询返回在数据库中所有的动态 skyline包含给定查询点的数据点．相应 的，概率 reverse skyline查询(Probabilistic Reverse Skyline， PRS)被定义为：给定一个概率阈值 P(0 P-<1)和 一 个查询对象 q，返回所有对象 ，使得对象 q为 的动态 skyline点的概率不低于阈值 P．文献[77]将 每一个数据对象看作是一个不确定区域，应用确定 情形下的 BBS算法 。 进行空间剪枝，应用用户定义 的概率阈值 P进行概率剪枝，得到候选的 PRS点进 行精化，最后输出查询结果． 5．5 数据流 在不确定性数据流中，各元组以概率形式表达 不确定性，可以是单一的概率值，也可以是复杂的概 率密度函数．数据流模型中，数据到达速率极快，数 据量极大，要求设计单遍扫描算法，以低空间复杂度 实时处理查询． 传统的面向确定性数据流的方法经过改装之后 能够应用于不确定性数据流应用之中．例如，AMS sketch_7 能用于处理聚集查询 ，特别是 F2问题 ；FM sketch_8们能用于求解数据流