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

PurdueUniversityOrion

StanfordUniversityCornellUniversityUniversityofWashingtonIntel/BerkeleyUniversityofMarylandIBMAlmaden

TrioMayBMSMystiQHeisenDataProbDBsAvatar

http://infolab.stanford.edu/trio/

http://www.cs.cornell.edu/da2研究内容包括:查询语言、表示与存储技术、支持数据清洗、tabase/maybms/高效的查询处理、更新等.http://www.cs.washington.edu/homes/suciu/project2mystiqhttp://www.eecs.berkeley.edu/Research/Projects/Data/102060

http://www.cs.umd.edu/～vs/research.htm#pdb

/cs/projects/avatar/

研究内容包括:数据模型、查询处理技术、关系代数计算等.该项目试图将现有的确定性数据管理框架与不确定性查询处理技术相结合,从而使得新增的功能模块能够嵌入到现有框架中,增强其性能.

研究概率聚集查询的计算方法,开发空间2时间概率数据库.该项目有两大目标:(1)从非结构化数据中抽取结构化的信息;(2)基于这类信息构建下一代搜索和商业智能应用.

Ré与Suciu[16]观察到不确定性数据广泛出现

在诸多应用之中,并总结了不确定性数据管理所面临的巨大挑战.Dalvi和Suciu[17]进一步从理论角度阐述不确定性数据管理的基础与挑战.Aggarwal与Yu[18]从算法与应用角度综述了不确定数据管理技术.Pei等人[19]回顾了近期不确定性查询处理方

面的进展,特别是他们自己的工作,包括范围查询、skyline查询与Ranking查询等.本文则以不确定性数据管理的框架为主线,综述了不确定性数据管理技术在数据模型、预处理与集成、存储与索引、查询分析处理等方面所取得的重要进展.本文第2～5节分别介绍上述4个方面的内容;第6节总结全文.

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

4计　　算　　机　　学　　报2009年

2　数据模型与挑战

2.1　可能世界模型

不确定数据库建模的研究工作很多,可能世界模型则是应用最广泛的数据模型[12213].在该模型中,

各元组的任一合法组合均构成一个可能世界实例(instance),实例的概率值可以通过相关元组的概率计算得到.可能世界实例的数量远远高于不确定性数据库的规模,甚至是后者的指数倍,这也是不确定性数据管理技术所面临的最大难点.考虑如图2所示的一个例子.图2(a)是一个不确定性数据库,包含3个元组,概率字段表示该元组的发生概率.ID13

之间可能独立也可能存在依赖关系.首先假设各个元组之间独立,则共有23=8个可能世界实例,各实例的概率等于实例内元组的概率乘积与实例外元组的不发生概率的乘积,如图2(b)所示.例如,可能世界实例{1,2}的发生概率为013×017×(1-016)=01084.某些场景下,元组之间并非独立,而是存在依

赖关系,这种依赖关系可以用规则描述.假设规则为1 3,即元组1与元组3不能够同时发生,但可以同时不发生[20].总共有6个可能世界实例,如图2(b)所示.的发生概率为013×(1-017=01{2}的发生概率为(03016)00信息

AB概率

137016

:

{{},{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}

(b)可能世界

(a)一个不确定数据库样例

图2　可能世界样例

在大多数应用中,不确定性可细分为存在级不

确定性(ExistentialUncertainty)和属性级不确定性(AttributeLevelUncertainty).存在级不确定性描述元组的存在与否,较为普遍.在图2中,各元组均具备存在级不确定性.属性级不确定性并不涉及整个元组的不确定性,而是以概率密度函数或统计参数(例如方差等)来描述特定属性的不确定性.例如,假设某传感器无法准确探测周围环境温度,典型的记录方式为:70%的概率为26℃,30%的概率为25℃.类似的记录均具有属性级不确定性.属性级不确定性往往比存在级不确定性更容易处理.有些时候,也可以将多个相关的元组视为单个含属性级不确定性的元组.例如,图2(b)定义了依赖规则1 3,则元组1和3无法同时发生.可以将这两个元组视为单个元组,该元组有存在级不确定性,发生概率为019;该元组的信息字段有属性级不确定性,由离散概率密度函数描述(信息=A的概率为1/3,信息=C的概率为2/3).

作为不确定性数据库建模的最核心思想,可能世界模型被广泛采纳于各种应用之中,并衍生出多种应用相关的模型,特别是针对关系型数据、半结构化数据、流数据和多维数据的模型.2.2　针对关系型数据的模型

针对关系模型的扩展最为常见,包括Probabi2

listic?2table[9,11]、Probabilisticor2settable[11]、Proba2bilisticor2set2?table[11]、Probabilisticc2table[13]等.

Probabilistic?2table以一个独立的概率字段表示元组的概率,且各元组之间独立.一个特定的数据库实例(也即可能世界实例)的概率等于其所包含的

元组的概率乘积和其所不包含的元组的不发生概率的乘积.图3(a)所示的Probabilistic?2table含3个字段c1、c2与概率字段,其中概率字段描述元组的发生概率.该表中有2个元组,可构成4个可能世界实例.Probabilistic?2table能够描述存在级不确定性,而Probabilisticor2settable则倾向于描述属性级不确定性.在Probabilisticor2settable中,元组的属性值被描述为多个候选值之间的“或”关系,可视为离散概率密度函数.以图3(b)为例,元组1的c2字段既可取2,也可取3,其概率分别为014和016;元组2的c2字段既可取4也可取5,其概率分别是012与018.Probabilisticor2set2?table[13,21]则是上述两种模型的综合体.例如,在图3(c)中,元组2本身具有概率值,而且其c2字段既可取4,也可取5,概率分别是012和018.Probabilisticc2table的定义与Probabilisticor2settable比较类似,不同之处在于它是从ctable衍生而出[22].部分学者也将probabilisticor2set2?table命名为x2relation,它包含若干x2tuple(无存在级不确定性)或者maybex2tuple(

有存在级不确定性)[8,23].

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

1期

c112

c223

周傲英等:

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

概率

.5.6

c112

c2

(2,.4〉)〈,〈3,.6〉(4,.2〉)〈,〈5,.8〉

c112

c2

(2,.4〉)〈,〈3,.6〉(4,.2〉)〈,〈5,.8〉

.8

5

概率

(a)Probabilistic?2table(b)Probabilisticor2settable(c)Probabilisticor2set2?table

图3　基于关系数据的扩展模型

2.3　针对半结构化数据的模型

半结构化数据模型(semistructureddatamod2el)能有效描述缺乏严格模式结构的数据[24].半结构

(Probabilistictreemodel)[27228]、PXDB模型[29]等.

化数据通常可以用文档树来描述.Dekhtyar等人[25]

提出了一种管理概率半结构化数据(probabilisticsemistructureddata)的方法,该方法以关系数据库技术为基础,支持丰富的代数查询.更多的工作则是直接以文档树形式描述不确定性半结构化数据如p2文档模型(p2documentmodel)[26]将概率值附加于文档树的边上,

各节点的概率依赖于其祖先的概率,节点之间可以是互斥关系(mux)(ind).在图4(a)所示

p2文档模型

[26]

的例子中,共有5.边A2B与A2C独立01C2D与C2E互斥,4015.此时,包含且仅包含节点A(1-017)×018×014=096;任意子图均不能同时包含D、E两个节点

.

图4　常用 …… 此处隐藏：3732字，全部文档内容请下载后查看。喜欢就下载吧 ……