学术论文：概率数据库及有效查询技术的研究(可编辑文本).pdf

摘要 在信息检索、传感器数据和图像识别等领域中，存在着大量不确 定性的数据。当把这些数据存储到数据库时，要求数据库有对其进行 处理的能力，而传统的数据库都是确定性的，不能对不确定性信息进 行处理。因此，概率数据库逐渐成为研究的热点之一。 本文首先描述了概率数据库的研究背景、现状和广泛应用，介绍 了两种广泛应用的概率数据库模型，分析了目前概率关系模型的缺 点，并针对缺点对概率关系模型进行了改进，把其中的元组重新分类， 并采用不同的概率计算公式，有效的解决了投影不合理的问题。 其次对概率数据库中数字属性的模糊查询技术进行了研究，通过 建立模糊集、选择隶属函数、调整模糊范围等一系列操作，逐步完成 了模糊到精确的查询过程。提出了可信度的基本概念，通过设置可信 度能有效地减少低概率元组的数量，所以查询得到的数据能更好的满 足用户的要求，同时也能降低查询的时间。 目前，聚集函数是直接应用于每一个可能世界的，且在线性时间 内不可计算。本文把聚集函数直接应用于原概率关系，通过转换和存 储过程等方法对每一个元组进行计算，使得能够在线性时间内计算其 结果，理论分析和实验证明了该方法的正确性。同时把每一个聚集函 数分为三个聚集分量，得到的聚集结果能更好的满足用户的多方面需 要。针对a v g 提出近似计算( a c ) 算法，实验结果表明该算法在很大 程度上缩短了计算时间，且具有较低的错误率，所以a c 算法的结果 可以作为概率数据库中a v g 的精确值。 关键词概率数据库，隶属函数，模糊查询，聚集函数 a bs t r a c t t h e r ea r el o t so fu n c e r t a i nd a t ai nt h ei n f o r l n a t i o nr e t r i e v a l ，s e n s o r d a t aa n di m a g ep r o c e s s i n g d a t a b a s en e e dt op r o c e s st h i su n c e r t a i n i n f o r m a t i o nw h e ni ti ss t o r e di nd a t a b a s e t h et r a d i t i o n a ld a t a b a s ec a nn o t d oi tv e r yw e l l ，s or e s e a r c ho np r o b a b i l i s t i cd a t a b a s eb e c o m e sm o r ea n d m o r ei m p o r t a n t t h ep a p e rf i r s t l yd e s c r i b e st h er e s e a r c hb a c k g r o u n d ，s t a t u s ，t h ew i d e r u s eo ft h ep r o b a b i l i s t i cd a t a b a s ea n di n t r o d u c e st w oe x t e n s i v ea p p l i e d p r o b a b i l i s t i cd a t a b a s em o d e l s w ea n a l y z e c u r r e n ts h o r t c o m i n g sa b o u t p r o b a b i l i s t i cd a t a b a s ea n dm a k es o m ei m p r o v e m e n ta b o u ti t i t st u p l e si s r e - c l a s s i f i e db ys o m es t a n d a r da n dt a k e nd i f f e r e n tf o r m u l at oc a l c u l a t et h e p r o b a b i l i t y t h ep r o b l e ma b o u tu n r e a s o n a b l ep r o j e c t i o n i se f f e c t i v e l y r e s o l v e di nt h i sm e t h o d f u z z yq u e r yt e c h n o l o g yo nf i g u r ea t t r i b u t ei np r o b a b i l i s t i cd a t a b a s e i so u ro n em a i nr e s e a r c h i n g w ei m p l e m e n tq u e r yp r o c e s sf r o mf u z z i n e s s t oe x a c t n e s st h r o u g hc r e a t i n gf u z z ys e t s ，c h o o s i n gm e m b e r s h i pf u n c t i o n a n da d j u s t i n gt h ef u z z ys c a l ea b o u tf u z z yo b j e c t b a s i cc o n c e p ta b o u t c o n f i d e n c ei sp r o p o s e di nt h i sp a p e r b ys e t t i n ge f f i c i e n tc o n f i d e n c e ，t h e n u m b e ro ft u p l e si nl o wp r o b a b i l i t yc a nb ee f f e c t i v e l yr e d u c e d 。i tw i l ln o t o n l yi nab e t t e rw a yt om e e tu s e r sr e q u i r e m e n t s ，b u ta l s oc a nr e d u c et h e q u e r yt i m e a tp r e s e n t ，a g g r e g a t i o nf u n c t i o ni s d i r e c t l ya p p l i e d i n t oe a c h p o s s i b l ew o r l d ，b u ti t c a nn o tb ec a l c u l a t e di nl i n e a rt i m e t h ep a p e r d i r e c t l ya p p l i e st h ea g g r e g a t i o nf u n c t i o n t ot h e o r i g i n a lp r o b a b i l i s t i c r e l a t i o na n dc o m p u t a t i o ni sm a d ea g a i n s te a c ht u p l eb yt r a n s f o r m a t i o n a n ds t o r ep r o c e d u r em e t h o d s t h e o r ya n a l y s i sa n de x p e r i m e n tr e s u l t p r o v e si t s c o r r e c t n e s s e a c ha g g r e g a t i o nf u n c t i o ni sd i v i d e di n t ot h r e e c o m p o n e n t sa n di t c a nm e e tu s e r sv a r i o u sn e e d si nab e t t e rw a y w e p r o p o s ea p p r o x i m a t ec o m p u t a t i o n m e t h o dt oc a l c u l a t ea v g t h e e x p e r i m e n tp r o v e st h a ti tc a ns h o r t e nr u n n i n gt i m ea n de r r o rr a t ei nt h i s w a yi sv e r yl o w , s ow ec a nt a k ei ta so u re x a c t a v g k e yw o r d s p r o b a b i l i s t i cd a t a b a s e ，m e m b e r s h i p f u n c t i o n ，f u z z y q u e r y , a g g r e g a t i o nf u n c t i o n 原创性声明 本人声明，所呈交的学位论文是本人在导师指导下进行的研究 工作及取得的研究成果。尽我所知，除了论文中特别加以标注和致谢 的地方外，论文中不包含其他人已经发表或撰写过的研究成果，也不 包含为获得中南大学或其他单位的学位或证书而使用过的材料。与我 共同工作的同志对本研究所作的贡献均已在论文中作了明确的说明。 名：锱扛吼午年且幺日 学位论文版权使用授权书 本人了解中南大学有关保留、使用学位论文的规定，即：学校 有权保留学位论文并根据国家或湖南省有关部门规定送交学位论文， 允许学位论文被查阅和借阅；学校可以公布学位论文的全部或部分内 容，可以采用复印、缩印或其它手段保存学位论文。同时授权中国科 学技术信息研究所将本学位论文收录到中国学位论文全文数据库， 并通过网络向社会公众提供信息服务。 作者答名：燃导师签名型嗍号年月日 硕 ：学位论文 第一章绪论 1 1 课题研究的背景 第一章绪论 数据库是对客观世界一部分( 可能是一个企业，一个单位等等) 的抽象描述。 各种数据是对客观事物的属性、数量、位置或是它们的相互关系的形式表示，是 各种信息的载体。目前己经有许多形式的代数或者逻辑等方法对客观事物的描述 提供了可用的工具，也为数据库各种模型的建立提供了一些理论基础的。 随着信息化进程的推进，数据库正在同常生活和经济发展中发挥着越来越重 要的作用i lj ，而这些数据库查询处理的方法和工具都是以数据的确定性为前提 的。当前，在很多领域发现了大量的不确定性数据：比如，在面部轮廓识别系统 中，即使是同一个人，不同照片的面部轮廓也不可能完全相同，如果使用关系模 型进行严格的匹配，将很难得到准确的结果；还有大量的不确定数据的例子，请 见文献【2 、3 、4 、5 】，下面就不确定性数据的主要应用的三个方面介绍如下： ( 1 ) 信息检索 数据库系统支持简单的布尔查询检索模型，即系统返回满足查询条件的所有 元组。这将导致多结果问题的产生当查询语句的选择性不强时，结果集中就会包 含过多的元组。比如由一个表组成的数据库中，表的结构如下： p e o p l e ( n a m e ，s e x ，l o c a t i o n ，t e l ，) ，表中的每一个元组表示一个人的信息，现 假设有查询语句： s e l e c t 幸 f r o mp e o p l ep w h e r e p 1 0 c a t i o n = b e i ji n ga n dp s e x = m a l e 结果将会查询到大量的符合条件的元组，因为在可以看到居住在北京的女性 太多了。 多结果问题在信息检索中得到了广泛的研究。克服这个问题的办法有查询重 构技术【6 1 和查询结果自动分级【7 1 等。查询重构技术对查询语句进行重新调整，增 强语句的选择性。查询结果自动分级则根据结果集中每个元组和查询的相关度的 大小。例如，根据以前该类客户的其他潜在查询要求等，对结果集中的所有元组 进行排序，只将相关度较高的一个或多个元组作为最终结果返回。 显然，自动分级技术在数据库环境中的应用更能引起人们的兴趣，这种相关 性的取得是对用户潜在需要的一种推测，可能符合用户的需要，也可能根本不符 合要求，所以用概率数据进行表示。它根据用户以自 对某个属性的查询习惯对新 硕i j 学位论文第一章绪论 的查询条件进行补充，经过相应计算后对每个符合查询条件的元组赋予一个概率 值，根据概率值由大到小进行排序，返回概率值较大的那些元组，同时也是相关 度最大的元组。 文献 8 【9 1 中对该种情况给出了详细的处理方法，主要是利用用户在进行类 似查询时在数据库中保留的历史记录，根据用户以往的查询习惯，对潜在条件进 行挖掘，得到最终的结果集。 ( 2 ) 传感器数据 传感器通常用来对环境状态进行连续不断的检测。传感器的数据又被传送到 应用程序来进行决策或回答用户的查询。比如，建筑内的火警系统会使用温度传 感器来检测任何温度上的异常，有时天气的好坏也能使温度传感器发生变化，这 就要求温度传感器有能够处理这些不确定因素引起的问题；军事系统中会在飞机 上装备传感器来追踪风速，用雷达监控和报告飞机的位置，这个位置并不是十分 的准确的，和实际总是存在着一些的差距；有时采用视频传输系统来检测室内老 年人的异常状况( 例如老人突然的摔倒) ，视频检测系统检测到的每一天的老人 的活动不可能都是一样的，这时就需要数据库来存储这些不确定性的数据，以及 对老年人活动的不确定性判断。这类应用中通常包括一个数据库或服务器来存储 或接收传感器发送的数据。但是有限的网络带宽和电池电量使服务器不能记录被 监控实体在每时每刻的确切状态。特别地，如果被监控实体的状态值( 如温度， 位置等) 不停地发生变化，数据库中存储的数值就有可能与实际的数值不符。这 时，对数据库进行查询就会得到错误的结果，此时就需要建立概率数据模型来对 数据进行存储，并要求数据库能对这些概率数据进行处理。 文献 1 0 对该类数掘进行了有效处理，提出了概率查询区域等与位置查询相 关的一些概念，并给出了两类英武概率位置查询的计算方法；文献【1 1 】中对传感 器网络进行概率查询的选择模式进行了研究；文献 1 2 】对概率查询进行了分类， 并针对不同的分类给出了相应的概率计算方法。 ( 3 ) 图像识别 在大多数图像数据库中，图像处理算法对图像进行处理，并将结果存入关系 数据库中。比如，一个面部图像数据库，对一张图片，图像处理算法做两件事它 首先将面部信息记录在这张图片上，然后将记录在图片上的面部图像同存储在面 部轮廓数据库中的面部轮廓图片进行匹配。结果存储的关系表如下所示，对应的 表关系如表1 1 关系i m a g e 所示。 i m a g e ( n a m e ，x l ，x 2 ，x 3 ，x 4 ，p e o p l e ，p s i ，p s 2 ) 表1 1 关系i m a g e 中的每个元组中的最后一个参数有三个参数，t l ，t 2 和t 3 分别表示个元组。元组t l 表示在图片上的左下角的坐标为( 5 ，1 0 ) ，右上角坐标 硕i ：学位论文第一章绪论 为( 3 5 ，4 0 ) 1 约矩形区域内有一个人的脸部图像，该脸部图像是j o h n 的概率是 2 0 - 2 5 ，j i m 为3 5 一4 0 ，t o r n 为4 0 一4 5 。 表1 1 关系i m a g e 图像处理算法为图像计算出了一个概率值p ，但是考虑到算法本身也会产生 误差e ，所以概率并没有表示为一个数值，而是表示成了一个概率区间，实际的 概率值在 m a x ( 0 ，p e ) ，m i n ( 1 ，p + e ) 】之间。上面的例子中，对于每一个元组： i p e = 0 2。i p = 0 2 2 5 ：， lp + e = 0 2 5le = 0 0 2 5 也就是说，图像处理算法计算的的j o h n 概率值为2 2 5 ，误差为2 5 。 1 2 课题研究的现状 使用传统的关系模型对非精确数据进行描述和处理已经不能满足实际要求， 甚至可能会出现错误的结果，这就需要采用其他的数据模型对非精确数据进行描 述。确定性的关系数据库虽能够存储不确定性数据，但不能对不确定性数据进行 有效的处理，因此需要定义概率关系模型，研究在概率关系模型下的不确定数据 的处理方法。 目前，国内对这方面的研究基本上研究甚少，主要的研究成果就是对概率关 系数据库模型的基本定义，详细内容可参考文献【1 3 】【1 4 】【1 5 1 6 1 7 】。国外许多 著名人士以及刊物对概率数据库研究与处理有着浓厚的兴趣，因为它有着巨大的 应用价值。比如自动控制装置对有关活动事件的概率估计离不丌概率数据库理 论。 1 9 8 8 年k l i r 和f o l g e r | 8 l 将不确定性数据分为模糊型和概率型后，对这两方 面的研究就逐步深入扩展，用概率型处理可能性演算，扩展关系模型来描述概率 方面的不确定性。 1 9 9 2 年，b a r b a r a ，g a r c i a m o l i n a 和p o r t e r 1 9 j 用概率理论提出了关系模式的 硕f j 学位论文 第一章绪论 扩展，采用概率关系的n 1 n f 观，用概率理论重新定义投影、选择、并等操作。 基于b a r b a r a 等的模型，于1 9 9 3 年开发了扩展的关系模型来描述数据不统一的 不确定性。他们对元组象对属性一样运用概率定义了常规的关系操作，也引进了 一种称为i n t e g r a t i o n 的新操作。 1 9 9 6 年，d e v 和s a r k a l a r t 2 0 】提出一种概率关系数据模型及代数，他在研究中 用系统的观点阐述了概率数据库的有关理论，定义了超键、主键、候选键、概率 模式、概率关系、概率关系数据库等系统概念，定义了投影、选择、连结、并、 差、重命名等操作，也讨论了概率数据库的实现问题及n u l l 问题。将部分概率 分布解析为区间估计及点估计两种，在概率关系代数中作了些基本的定义，如属 性名、关系模式、关系域、元组、值等元组以及值等元组的两种合并方法等。阐 述了有关的信息及概率标准化，同时也说明了关系代数的操作及特性，叙及了象 s q l 一样的概率关系查询语言，可以说它是目前概率数据库研究方面较完善的 最新成果。 1 9 9 7 年，l a k s h m a r u l a n i2 l j 基于元组的概率取值区间提出了一种灵活的广泛适 用的概率关系代数，但其引入的路径属性使得该代数变得相当复杂。 2 0 0 2 年，v e r o n i c ab i a z z o ，a l f r e d of e r r o 等【2 2 j 在l a k s h m a n n a n 的基础上，采 用条件概率区间值以及d ef i n e t t i 一致性原理提出了一种新的概率关系代数，每 个元组给定属性在区间内的取值。 2 0 0 4 年，n i l e s hd a l v i 和d a ns u c i u 2 3 】提出了判别概率数据库的有效查询的 方法，用具体的算法可以判断某个查询是否可以查询到正确的结果，同时，当查 询不到正确的结果的时候，又给了优化的方案，使得能够查询到f 确的结果，但 也有一些查询是线性时间内不可计算的，也就是说不可能查询到完全正确的结 果，这样的情况下，作者给出了两种近似计算的方法：一种是最少不安全方案； 另一种是m o n t e c a r l o 近似计算的方法1 2 4 1 。 2 0 0 5 年r o b e r t 2 5 j 利用b g p 框架，提出了聚集查询的方法，有效的解决了聚 集查询的一些问题。2 0 0 6 年，n i l e s hd a l v i 和d a ns u c i u l 2 6 1 再次总结了以前的概 率数据库的基础工作和未来的挑战，列举了未来的几个重要的研究工作：( 1 ) 查 询的优化问题【2 7 】；( 2 ) 概率推理算法；( 3 ) 概率查询的复杂度计算问题【2 8 】；( 4 ) 条件概率及软约束。 2 0 0 7 年，c h r i s t o p h e rr e 【2 9 】等提出了一个非常新颖的方法来计算概率数据库 i 拘t o p k 查询，指出了对t o p k 查询条件进行限制是提高查询效率的最好方法，因 为在概率数据库经常会得到一些概率非常低的元组，而用户可能只对概率比较高 的元组感兴趣，在进行条件设定时，低概率元组就不会出现在查询结果中。计算 t o p k 时，他主要使用的方法是同时并列使用多个m o n t e c a r l o 模拟算法，这个算 4 硕i ：学位论文第一章绪论 法对于大型的数据库，可能效果会更好一些，同时，还提到了一些查询优化技术。 2 0 0 8 年，k ey i 3 0 1 等提出了一种新的方法解决概率数据库的t o p k 查询，他的计算 方法降低了存储空间的使用，同时也降低的执行的时间。若元组间全部相互独立， 则算法的效率会达到最佳。 1 3 研究的意义 现在许多大型公司对于不确定性的数据采取的方法都是用数据清理【3 i 】或者 e t l 工具p 2 j 把这些不确定性的数据丢掉。事实上，一些个人或者团体需要直接 应对这些不确定性的数据，但是把这些数据清理掉将会付出很大代价( 例如在科 学数据整合、w e b 数据整合等) ，或者不可能把这些数据清理掉( 例如传感器数 据、r f i d 数据等) 。很明显，需要能够处理这些不确定性的数据，这种不确定性 会用一个概率来表示，因此，要寻求管理概率数据的方法和技术。 概率数据库中一个标准的s q l 查询语句返回的结果是一组概率元组的集 合，每一个元组都会返回一个查询结果的概率。这就要求系统能够计算出这个概 率，而事实上是非常因难的，因为这是一个概率推理的问题，在人工智能中有广 泛的应用【3 3 j ，并且相当的复杂【3 4 l 。目自 ，不确定数据在同常生活中的频繁出现， 使得对不确定信息的处理也显得尤为重要，本文的研究工作可以带来以下三个方 面的好处： ( 1 ) 基于目前概率关系模型的缺点，对d s 概率关系模型进行改进，使得 元组的投影操作更加的合理，进一步完善了概率关系模型的结构。 ( 2 ) 由于数据的不确定性，概率关系数据库中的元组数目可能比确定性的 关系数据库中元组数目要多很多，这样，对于模糊查询来说，只要与查询条件相 关的元组都会返回给用户，其中包含很多用户不需要的数据( 例如可信度很低的 元组) 。通过本文引入的可信度的设定，可以有效的解决复杂查询结果的问题。 ( 3 ) 聚集查询是目自订概率关系数据库的研究的难题，而聚集函数同常生活 中有着非常广泛的应用，例如天气预测系统需要判断一个区域降雨的期望值，或 者最小值、最大值等，本文定义的聚集函数可以有效的解决生活中的某些应用问 题。由于a v g 目前没有找有一种有效的计算的方式，采用的是近似计算a c 的 方法，通过错误率可以判断出，近似计算的方法的有效性。 1 4 本文的主要工作 本文的主要研究内容是概率数据库有效查询技术，主要是通过对概率关系模 型的介绍，能够实现概率关系中更有效的查询，包括模糊查询和聚集查询。其主 要创新点体现在以后几个方面： 硕一i j 学位论文 第一章绪论 ( 1 ) 目前主要使用的两种概率关系模型中，由于第一种b g p 模型不满足1 n f 要求，许多概率关系模型的操作无法描述，计算其操作时很复杂，并且每一个元 组的概率都是一个区间，因而把b g p 模型作为研究对象的比较少；第二种关系 模型能够解决第一种模型的缺点，但是由于在定义合并操作时，没有能把数据库 中的元组进行有效的区分，因而投影的结果出现了不合理之处。本文针对第二种 关系模型的缺点，对其进行了改进，把概率关系数据库中的元组进行有效的区分， 分为相互不相容元组和相互独立元组，并且定义了不同类型的元组的合并操作， 有效地解决了合并不合理的缺点。 ( 2 ) 模糊查询主要通过建立模糊集、选择隶属函数、调整模糊范围等一系 列操作，逐步完成从精确到模糊的查询过程，能够更有效的满足用户的要求。由 于在没有设定可信度的情况下，某些对象属于用户查询的要求的可信度很小，但 是还是会出现在查询结果中，这就不利于用户查看有用信息，本文通过设定可信 度，可以把可信度较低的元组丢掉，这样查询到的数据就会比较接近用户的要求， 同进可以有效的降低查询的时间。 ( 3 ) 聚集查询主要是针对概率关系聚集查询的特点，把聚集函数应用于每 一个可能世界，这样对于一个元组有2 n 个可能世界的概率关系1 3 引，聚集查询 是在线性时间内不可计算的。本文通过证明，使某些聚集函数直接应用于原概率 关系，也可以计算出相应的结果。为了能满足不能聚集的需要，本文重新定义了 聚集函数，既能得到某些特殊的聚集查询结果，又解决了聚集查询多结果的问题。 本文对于a v g 的期望值不能实现其精确值，主要采用近似计算的方法，并给出 了近似计算的评判标准，通过实验证明，近似计算的错误率是很低的，因此可以 作为a v g 的精确值。 1 5 论文的结构安排 第一章绪论。论述了选题的背景和目前研究的现状，分析了现实中大量存 在的不确定性数据和广泛的应用前景，并给出了研究的意义和本文的主要工作。 第二章概率关系模型及其改进。首先详细的介绍了两种概率关系数据模式， 分析了两种概率关系模型的缺点，并在d s 模型的基础上进行改进，使概率关系 模型的投影操作更加的合理。 第三章研究了概率关系数据库数字属性的模糊查询。在传统关系数据模式的 基础上，把隶属函数引入到概率数据库的模糊查询中来，用户针对不同的模糊对 象可以建立不同的模糊集，使用不同的隶属函数。通过设置隶属度，用户可以把 所需要的元组设置在某个程度上符合用户的要求，这样就会更加丰富用户查询的 结果，不但能查询到完全符合用户要求的元组，而且还会把那么比较接近用户要 6 硕j ：学位论文第一章绪论 求的元组也返回给用户。最后，通过d a t a f a c t o r y 生成大量的数据，对本文的概 率数据库数字属性模糊进行验证。实验表明，通过设置不同的参数及可信度，可 以查询到不同需求的结果，在不同程度上降低查询时间。 第四章研究了概率关系数据库的聚集查询。研究了概率数据库聚集查询的特 点，说明了当前概率数据库聚集查询的难点问题，介绍了再有的聚集查询方法。 为了提高这些聚集函数的查询效率，本文给原有的概率关系进行了编码，主要的 解决聚集查询的方法分为三类：转换、存储过程和近似计算。前两种方法都能够 计算出其精确值，但由于a v g 的计算必须针对每一个可能世界进行操作，目前 不能通过公式有效地证明使用某种方法实现其精确聚集查询，所以本文采用了近 似计算的方法实现其近似值。在实验中，通过有限个元组的实验结果表明，其错 误率是比较低的，而且随着空可能世界的概率的降低，其错误率总体来说也是不 断降低的，因此，可以把它当作精确值。 第五章是总结和展望部分。对本文的研究工作进行了总结，指出了本论文的 不足之处，以及进一步的研究方向。 硕i ：学位论文 第一二章概率关系数据模型 第二章概率关系数据模型 概率是解决不确定信息的比较适用的方法。经典关系数据库处理不了具有概 率的数据，所以要对此种数据库在这方面加以推广，也就是非经典关系模型。从 1 9 8 8 年k i i r 和f o l g e r 【加j 将不确定性数据分为模糊型和概率型后，对概率关系的研 究不断深入，许多科研工作者都提出了自己对概率关系模型的描述，使得概率关 系模型越来越趋于完善。目前，普遍被认可的概率关系模型有两种，下面分别介 绍一下这两种概率关系模型。 2 1 两种常见的概率关系数据模型 根据a m o ld e s h p a n d e 的理论，把不确定性分成两类基于元组层次的不确定 性和基于属性层次的不确定性。 定义2 1 基于元组层次的不确定性：元组中的属性是精确的，而元组是不确 定的。例如给定n a m el i k e w u 的查询，查询的结果可能为元组( w ug a n g ) 。 定义2 2 基于属性层次的不确定性：元组( 由主关键字唯一标识) 是确定性 的，而属性值是不确定性的。例如：明天的温度在多少度之i 、日j ，它们一个区i b j 内 的取值，但是具体多少度就无法得知了。 最常见的基于属性层次的不确定性的应用就是传感器网络的应用。接下来， 介绍两种常见的概率数据模型，并给出它们的各自特征。 2 1 1b a r b a r a ，g a r c i a m o l i n a ，p o r t e r 框架( b g p 框架) b a r b a r a ，g a r c i a m o l i n a ，p o r t e r 在中提出了如下的数据模型： 定义2 3 ：k 为一组关键字属性 k 1 ，砭，凰) 的集合，a 是一组随机属 性a l ，a 2 ，a m 的集合，属性k i 和a i 的值域分别为d o m ( k i ) 和d o m ( a j ) 。用 木) 表示空，用d o m ( a i ) u 木) 表示d o m ( a j ) 木，用p f 表示形式如同d o m ( a i ) 幸x x d o m ( a 脚) + 一【o ，l 】概率分御函数的集合。那么，定义在属性对( k ，彳) 上的概率 关系r - d o m ( k i ) x d o m ( k n ) 一p f 。 一般的，任何一个概率关系由两种属性组成： ( 1 ) 确定性属性：这类属性都是可知的，是定义2 3 的概率关系的关键字 属性。 ( 2 ) 不确定性属性：这类属性的值都是不可知的，但是通过一些概率信息 可以预测它的大概值。 根据定义2 3 ，概率信息可以通过对随机属性进行联合概率分御取得。 硕r i 二学位论文第二章概率关系数据模型 b g p 框架有两种方式存储元组，如表2 1 和表2 2 所示： 表2 1 关系t a b l e l查! ：! 墨墨些丝 a b c a l 0 4 b l 】o 4 c l 】 a 1 o 6 b 2 】0 5 c 2 】 a 2 1 0 b 3 】0 6 c 3 】 a 2 1 0 b 3 】0 4 c 4 】 abc 如表2 1 所示，关系t a b l e l 中a 属性为确定性属性，b 、c 属性为不确定性 的属性，其第一个元组的意义是：a 属性取值为a 1 ，在b 属性上取值为b 1 的概 率是0 4 ，在c 属性上取值为c 1 的概率是0 4 。 如表2 2 所示，关系t a b l e 2 中的第一个元组的意义是：a 属性取值为a l ，在 ( b 、c ) 属性上取值为( b l ，c 1 ) 的概率是o 1 6 。显而易见，b g p 框架有以下特 点： ( 1 ) b g p 框架不满足1 n f ，每个元组由一个随机值表示( 如表2 1 的关系t a b l e l ) 或者由多个随机值的联合概率分布( 如表2 2 的关系t a b l e 2 ) 。 ( 2 ) 如果随机属性不同，那么可以认为该属性是不相容的。例如，在表2 2 中，对于同一个元组“a 1 ，在属性b ，c 上取值有很多不确定性因素，取值为【b l c 1 】的概率是o 1 6 ，而【b 1c 2 】出现的概率是0 2 0 ，它们之间是不相容的，也就是 说，它们不可能是同时出现的。 ( 3 ) 如果确定性属性取值不同，则可以认为它们是互斥的。例如：对于元组 【a 1 ，b l ，e 1 0 1 6 和元组 a 2 ，b 3 ，c 3 0 6 0 就是相互互斥的两个元组，因为它们的确定性 属性取值是不同的。 ( 4 ) b g p 框架可以表示还没有出现的不确定信息。例如：在表2 1 关系t a b l e l 中，对于a 属性取值为a 1 的元组，c 属性取值的概率相加0 4 + 0 5 z ( p s ) ) 八( x ( p s ) = y ( p s ) 一z ( p ) ) ) ) 投影运算 设r 是关系模式r 上的关系，scr ，则r 在s 上的投影，记作兀。( ，) ，定 义如下： 兀( ，) = x ( s ) l x = oj ，( s ) ) ytr j ，( n ) = j 注意到，如果q c s ，则与经典关系类似，有： 硕i ：学位论文第二章概率关系数据模型 兀。，( f i ，( r ) ) = 兀d ( ，) ( 3 ) 选择运算 设r 是关系模式r 上的关系，矽是r 中属性域上的比较运算符的集合，p 是 一个谓词( 称为选择谓词) ，p 是由r 中的属性、8 中的比较运算符、r 中各属 性的域中的常数、逻辑联词组成的有意义的式子。于是，的p 选择，记作仃，( ，) ， 是集合 x ，i 尸( x ) ) 。对于两个连接的选择，也像经典关系那样与次序无关，即 有： l ( c r p 2 ( ，) ) = 盯，2 ( 仃尸l ( 厂) ) = 盯川，j 2 ( ，| ) ( 4 ) 自然连接运算 设r 及s 分别是关系模式r 及s 上的关系，令r = r 一 p s ) ，s = s 一 p s ) 则 ，与s 的自然连接，记作? o o s ，定义如下： r o o s = x ( 尺u s ) l ( 3 y r ) ( 3 z s ) ( ( x ( 尺。) = y ( r ) ) ( x ( s ) = z ( s ) ) a ( x ( p s ) = y ( p s ) z ( p s ) ) ) ) 为了自然连接运算能得出有意义的结果，r 与s 中的属性应该是独立的。容 易看出，自然连接运算是满足交换律与结合律的。 2 1 4d s 框架的特点 1 d s 框架的概率关系可以存储不同随机值的信息。不同的主关键字决定了 不同的随机值，其中主关键字是非概率属性集合的子集。表2 3 所示的概率关系 t a b l e 3 中，其主关键字就是a 属性。自仃三个元组a 属性的取值为a 1 ，后两个 元组a 属性的耿值为a 2 。 2 关系中主关键字的值代表一次事件或一个对象。其他的属性描述该对象或 事件在关系中发生的情况及其概率。 3 一个关键字的值对应一次事件或一个对象，并称关系中关键字取这个值的 所有元组为这个对象的实体。如果这个对象实体中所有元组的概率总和为l 整 数，那么这个对象的实体是完全可以确定的。如果这个对象实体中的所有元组的 概率和小于1 ，那么称这个对象的实体是不完全可以确定的。 表2 3 所示的概率关系t a b l e 3 关键字为a 性。对于a l 对象，实体中的所有 元组的概率和为l ，它就是个完全确定的对象。a 2 的那个对象，实体中的所有元 组的概率和仅为0 9 ，它就是个不完全确定的对象。 2 2 改进的d s 框架 在对d s 框架进行深入的研究分析后，发现在d s 框架下，由于元组之间的性 质并不是完全相同的，有些是相互独立的，有些是不相容的，因此，需要对元组 进行有效的区分。由于元组没有有效的区分，在一些概率关系的运算过程中，会 1 2 硕十学位论文第一二章概率关系数据模型 出现一些不符合实际的结果，因此要求对d s 框架下的有些关系运算针对不元组 的元组进行重新定义。 2 2 1d s 框架存在的问题 ( 1 ) d s 框架中，没有对一个关系中的属性进行很细致的划分，把所有的属 性都认为是不确定的，而事实上，在概率关系中，有的属性的取值是不确定性的， 可变的，但对于另一部分属性来说，它们是确定性的，因此不能够把一个关系中 的所有属性都认为是不确定性的。例如，以表2 - 3 中，若a 代表一个实体，b ，c 只是代表其两个属性，则可以把a 当作关系中的确定性的属性，把b ，c 当作不确 定属性。 ( 2 ) d s 框架虽然在b g p 框架的基础之上作出了改进，基本符合了现实中的 概率数据的要求，能够解决一定的概率关系上的问题，但是在对概率关系中元组 的划分不是很明确。在同一个关系中，有的元组是相元独立的，有的则是不相容 的，对于它们之间关系代数运算，是需要有区分的，不能够用统一的关系代数运 算解决投影之类的问题。如果对于不同类型的元组运用相同的代数运算，则会引 起错误。例如对表2 5 中b 属性投影，得到结果如表2 - 6 所示。 表2 - 5 关系t a b l e 5表2 - 6 关系t a b l e 6 垒旦竺卫! a lb lc l0 7 堡巳兰 b l1 a 1b 2c 20 2b 2o 5 a 1b 1c 30 1 a 2b lc l0 6 a 2b 2c 20 3 在表2 5 关系t a l b e 5 中，a 为确定属性，b 、c 为不确定属性，如果在b 属 性上进行投影操作，投影后在b 属性上的结果为 b 1 ，b 2 ，其概率分别如下计算： p s ( b 1 ) = m i n ( 1 ，0 7 + 0 1 + 0 6 ) = 1 p s ( b 2 ) = m i n ( 1 ，0 2 + 0 3 ) = 0 5 而事实上，a 1 所在的两个元组中，在b 属性上取值时，可能不会出现b 1 ， 其不出现的概率为1 - 0 7 - 0 1 = 0 2 ；同样，a 2 所在的元组中，在b 属性上取值也 有可能不会出现b 1 ，其概率为1 - 0 6 = 0 4 。因此，在2 - 5 所在的关系t a b l e 5 中， 不可能一定出现b 1 ，也就是说，在b 属性上投影计算的结果( 如表2 6 关系t a b l e 6 所示) 是不正确的。因此，在概率关系数据库中，不能像传统的确定性的数据库 那样，运用统一的投影操作。 2 2 2 改进的d s 概率数据库模型 d s 概率数据库模型是传统的关系数据模型的自然扩展，它的理论体系以关 硕t ：学位论文 第一二章概率关系数据模型 系数据模型为基础，但又有别于传统的关系数据模型。下面给出d s 概率数据模 型的有关概念。 定义2 1l 标志一个事物或一个对象的特有属性或属性集，它的任何子集都 缺乏这种性质，称这种属性或属性集为对象属性。 定义2 1 2 伴随一个事物或一个对象的存在而存在的特性，这种特性相对稳 定，不因对象或事物的动态变化而变化，称为静态属性。 定义2 1 3 在对象确定存在的情况下，它的某些特性的存在又具有多种可能 性，这种描述事物在存在及存在的前提下，某些方面存在的动态特性称为动态属 性。 一个事物或一个对象，它具有对象属性与静态属性，在动态世界中同时也表 现出动念属性。如表2 5 关系t a b l e 5 有一个对象属性：a ；静态属性：a ；动态 属性：b ，c ；其中这三种属性的某一组合，就称为对象的一个事件。这种 对象属 性 u 静态属性 u 动态属性 构成对象的事件。同样，如果对象或事物本身的 存在具有可能性，也即有动态性，这时将对象或事物看成一个事件。 定义2 1 4 由于世界是动态的，对象或事件存在与否本身具有一定可能性。 在存在的前提下，对象表现某种动念属性具有一定可能性，也即对象的某个事件 的发生具有一定可能性。这两种可能性，均称为事件的概率属性。 综上所述，在概率数据模型中，从属性来看，对象属性、动态属性必须存在， 但可以合二为一。当合二为一时，描述的是动念的对象，否则描述的只是确定对 象的动态方面。无论哪种动态性都产生随机事件，这些随机事件都伴有随机的可 能性概率。概率属性正是为描述这种随机事件而引进产生的。 定义2 1 5 形如 a i ，a 2 ，a 。) 的属性集合称为一个概率关系模式，其中 a l ，a 2 ，a 。) = k j ，恐，) u s i ，s ) u 乃，乃，瓦) u p s ) ， k i ，& ，) 为对象属性集， s i ， 为静念属性集， n ， 乃，瓦) 为动态属性集， p s ) 为概率属性。 定义2 1 6 概率关系模式 彳i ，彳2 ，a 。 上每一属性的取值范围称为属性 域，记为d i = d o m ( a i ) ，模式上属性域中值的直积称为关系模式r 上的关系域，记 为d o m ( r ) = d o m ( a 1 ) d o m ( a 2 ) x d o m ( a n ) ，或胪d lx d 2 x d n 。 关系模式尺上的一个元组就是从模式尺到域上的一个映射：r - - - d o m ( r ) ， 使得： ( v x 尺) ( ( 戈) d o m ( x ) ) 概率关系模式上的一个元组由对象属性、静态属性、动态属性、概率属性等 组成，它描述的不是传统关系数据模型中的简单对象，而是动态对象( 包括动念 的对象本身和对象的动态属性) 的一个事件连同该事件发生的概率。形式上它类 1 4 硕 ：学位论文第二章概率关系数据模型 似传统关系模式，是二维表中的一行，本质上它描述某事件发生的概率。所以不 同的行描述的是不同的事件及其概率，同一事件不允许出现在同一关系之中。 定义2 1 7 为了能够更好的描述概率数据库中的对象或事物，把一个对象或 事物具有的所有可能称为一个元组，而这个对象或事物的每一个可能称为一个可 选元组。表2 5 关系t a b l e 5 中，有两个对象a 1 ，a 2 ，也就是说有两个元组，但对 于第一个元组，它有三个可选元组，分别为 ( a l ，b l ，c 1 ) ，( a l ，b 2 ，c 2 ) ，( a l ，b l ，c 3 ) ) 。 定义2 1 8 对于对象属性与动态属性合一的情况，由于元组本身描述的是动 态的对象事件及其概率，因此一个元组描述一个对象，一个对象代表一个事件， 事件的集合称为对象的基本空间，简称对象空间。如：关系2 5 由两个元组构成， 即两个对象，该对象空间有两个元素。对于对象属性与动态属性不合