（计算机软件与理论专业论文）概率数据库中移动对象查询方法的研究.pdf

山东大学硕士学位论文 摘要 对数据库的查询可以分为精确查询和概率查询两种。当进行精确查询时，查 询结果完全符合查询条件，而且结果是确定准确的。但对于某些情况，无法采用 精确查询得到正确的结果。比如，当对移动物体的位置信息进行查询时，由于物 体在不停地运动中，实际的位置信息的变化往往快于存储在数据库中的位置信 息。这样，查询语句从数据库中取得数据时，数据库中的数据往往已经过时了， 从而造成查询结果与实际情况的不一致。对于这种情况，由于无法获得查询时刻 的精确值，所以通常采用概率查询的办法，即对查询得到的结果赋予一个概率值， 用来表示该结果正确的概率。这个概率通过使用相关的概率计算方法计算得到。 目前采用的计算模型中，当新的位置更新信息到达时，将立即覆盖上一次保存的 位置信息，数据库只能保留最后一次更新的位置信息。这样一来，当使用概率计 算方法计算结果的概率值时，由于数据库中没有位置信息的历史记录，自然无法 获得位置信息的统计结果，而只能使用通用的概率分布( 如均匀分布等) ，从而 降低了对具体查询对象的针对性和查询结果的准确度。另外，使得某些特定的精 确查询( 如查询过去某个时间点的位置信息) 也变得完全不可能，从而减少了可 处理的查询的类型。 针对这个问题，本文提出一种新的数据的存储方法。该方法改变了目前采用 的对位置更新数据的存储方式，当新的位置更新数据到达时，不是用新的数据覆 盖旧的数据，而是将新的信息作为一条新的记录插入到相应的信息表中，这样就 可以在数据库中保留大量的历史信息记录。对于概率查询，由于保留了历史更新 记录，使得到的新的概率分布比使用通用的概率分布具有更强针对性，从而提高 了概率查询结果的真实性和可靠性。同时，新模型的实现还同时得到了一个附加 的好处使某些特定的精确查询得到实现，比如，可以得到过去某个时间点的 移动物体的位置信息。 本文首先对概率数据库进行了简要的介绍，包括概率数据库的研究背景、基 本概念、相关模型和研究热点。接下来对移动物体位置查询系统进行概述，给出 了系统的模型，并介绍了模型各部分的功能。然后，对系统中最主要的部分 山东大学硕士学位论文 位置信息系统进行了详细介绍，主要包括对移动物体位置信息更新频率的控制策 略和对概率查询结果的概率的计算方法。接着，对比已有的数据处理方式，提出 一种新的数据处理方式。然后，利用新建立的模型，不但对概率查询进行了改进， 而且对某些特定查询的处理进行了描述，同时给出了算法实现。最后，对整篇文 章进行总结。 关键宇：精确查询；概率查询；预测时间间隔；概率函数：概率密度函数： n 山东大学硕士学位论文 a b s t r a c t a q u e 猡o nd a _ 纽b a 辩c a l lb ed 鏊s i f i e di l l l op 把c i s e ( 如e l y 翩d1 1 1 译r i 辩u e 黟 w h 肌q u 唧i n gt 量i el o c a l i o ni n f o m a d o no fr n 晰n go b j e c 协f 如m 也i 讪a s e ，1 l l e 觚= t i l a l i o c 砸衄枷白n l 】厕彻。船i lc h 锄g 嚣f 函e rt l 船t l l ed a 组s 幻_ r e di nt f i e 出纽b 豁eb e c a u 辩 t 1 1 eo b j e c 信n 1 0 v ec o r n i n u o i l s l ys ow h g e t t m g 阳s l l l td a 土af b md a t a b a ，1 l l e 妇a b 嬲eu s u a l l yh 勰o m d a r t e d t h i sw i i l 陀s i | l ti i in o n - c o n s i s 衄l tb e t w e l 量i er 鹊u ng o t 白d m 出l t a ：b a s e 趴dm e t i l a lo n e f o r “ss i | 嘶o n ，w ec 雏n o tg e tt l l ep f e c i s ev a l u eo f 血er e s u l ts ow e 哪u a l l y 懈ep r o b 出i l i 妇cq l l e f y ，w h i c h 谢l la d da p t o b a b i l 时v a l mt o m er e s l d t ，t op r e s e m 增f i d e l 崎o f 吐增r 豁珂t ，w bc 趾g e tt h i sp r o b a b i n 锣v a l u eb y u s i n gr e l e v 锄tp r o b a b i l i t yc a l 砌以o nm e n l o d h 1t h ec a l c i l l a 五0 i ln d d e l s 砒p r 鼯饥t ， w h e nn e w 印d a t ei n f o n 】d 撕o na r r i v 铝，t h eo l do n es t o r e di i l l l e 幽b 豁ew i l lb e r 印1 e d 血ed a t a b 鹤eo i l l ys t o f 嚣t l l ed a l au p d a t e df o rt l el a c e s t 石m e w h 锄w e c a l c 试a t e 也ep r o 蛐l i l yv a l u eu 或f 喀p 阳b a b i l i 锣c a l c l l l a 五o nm e t i b d ，w ec a n n o tg e tm e s 嘶s t i c sr e s l l l to f m el o c 撕o ni n f 0 肌a t i 0 i l ，b e c a u m e r ei sn oh i s 幻f y 蚴r ds t o r e di n t l l ed a 协b a s e ，no r d e rt og e tt l l ep r o b 曲i l i t yv a l u eo f l 量i er 鼯t i l 乞t 量i ep 陀s e r l tm e l 量l o di s 惜如gg e i l e r i cd i s 仃i b u t i o l l ，s u c h 鹤g a u s s i a nd i s 仃i b u d o n b i i tm i sw i l lr e d l i c em e a c c i l r a c yf o ras p e c i a io b j e c t a d d i d o n a l l y ，f o rs o m es p e c i a lp r e c i s eq u e 吼s u c h 舾 q u e r y i n gm el o c 撕o ni i l i o 姗觚o no fn m ep o mi nt l l ep a s t ，谢i lb e c o m ei r i l p o 哪i b l e 1 1 l i s 、i l lr e s 缸n l l l e 枷g e o f t h e q u e 辑 f o r 曲j ss i t u a 石o n ，a 办e wd a ap r o c 郎s i l 】gm 劬o di sp r o p o s e dt 1 1 i sm e t l 】o d c h 锄g 韩t l ed a t as 的r e dm 黝e rc u m 喜n n yl l s e d w h 既t h eu p d a 血gi n f o m l 撕o na 玎i v 鼯， i tw i l lb ei n s e r t e d 岫协m ei n 内仉嘶o nt a b l e 笛an e wr e c o r d i l l s t e a do f r 印1 a c i n gt l l e 0 1 do n e q 咖埘豁o f h i 哟r yr e c o r d sc 觚b er e s e r v e db y 血i s 、v 移t h i s 砌l i v em e p 量o b l e mo f m e8 p e c i a l 胁c i c m e 彤删c h 嬲q u e r ) rt 1 1 el o c a l i o ni n f o 咖觚“ o b j e c t sa tm e 劬ep o i n ti nt h ep a s t b e s i d e st l l 鸸f o rp r o b a b i l i s t i cq u e 吼u s i n g1 h e d a t a 豫c o r d 蕾og e t 出el o c a t i o nd i s 订i b t i t i o ni sm o r er e 】i a b l ea n da c c u 阳把t l l 锄u s i n gt h e g e n e r i co n 豁 h lt 量l i sp 印e r ，w e 、i l if i r s ti 1 1 仃0 d u c em e m o v i n g0 b j e c t sq i l e r y 吨s y s t 锄h lt l l i s i 山东大学硕士学位论文 p a r t ，w e 谢l l 百v eo u tt 1 1 e 夥s t e mm o d e l 锄dt l l ef 血c 6 0 no f t h ec o m p o n t so f t l l e m o d e l a 鼯t h a l ，w e 稍nd e s c 曲em em o s ti m p o f t 觚tp a n - t h el 0 c a t i o nh l f b 姗新o n s y s t e mi nd 酏a i l ht l l i sp a w em a i l l l yi n 打o d u c et l l el o c a l i 衄i i l f b 咖a t i o n 印捌n g c o n t r 0 1 1 i n gs 仃a r t e | 搿f o rm 响go b j e c 住舭dt 1 1 ec a l c i l l 撕o no fm ep r o b a b i l n yo fl l l e r 船u ho fp r o b 如i l i s t i cq u e 够t h e l l ，c o m p 盯e dc t l y 吣e dm o d e i ，p r o p o s ean e w w 科o f p r o c 嚣s i n gd a t a 锄ds u p e r v i s et h ec a l c l 】1 a l i o no f 啪k i i l d so f t y p i c a lq u e r y ，i n m e 髓d w e 翻| i n m a r i 乃e 也ew h o l e 腻 _ 沁yw o r d p 仲c i 鼯q u e r y ；p 加b a b i i i s t i cq u e r y ；p m d i c t i o n 砸i 吣h 衄r v m ； p m b a b i l i t yf u n c t i o n ；p r o b a b i i 蚵d e n s 畸f u n c 6 0 n 原创性声明和关于论文使用授权的说明 原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独 立进行研究所取得的成果。除文中已经注明引用的内容外，本论文不 包含任何其他个人或集体已经发表或撰写过的科研成果。对本文的研 究做出重要贡献的个人和集体，均已在文中以明确方式标明。本声明 的法律责任由本人承担。 论文作者签笔：聋宣望日期：望? ：竺! 关于学位论文使用授权的声明 本人完全了解山东大学有关保留、使用学位论文的规定，同意学 校保留或向国家有关部门或机构送交论文的复印件和电子版，允许论 文被查阅和借阅；本人授权山东大学可以将本学位论文的全部或部分 内容编入有关数据库进行检索，可以采用影印、缩印或其他复制手段 保存论文和汇编本学位论文。 ( 保密论文在解密后应遵守此规定) 论文作者签名：越导师签名： 期：1 2 ：兰 山东大学硕士学位论文 1 1 课题提出的背景 第1 章绪论 随着信息化进程的推进，数据库正在日常生活和经济发展中发挥着越来越重 要的作用。目前已广泛应用的成熟的数据库系统中，大多数属于传统的关系型数 据库。关系型数据库中的数据是确定的，即数据库中的每个元组要么符合查询条 件，要么不符合，结果是确定的。 但在现代企业应用中，需要处理大量非精确的数据。比如，在进行信息检索 时，当关键字过于简单，选择条件不充分。导致产生的符合条件的结果过多。这 时就要对结果进行筛选，根据结果中元组与查询的关联程度，将关联程度较高的 元组选择出来，并附以相应的概率，作为最后的结果返回。在移动对象位置信息 监控系统中，由于移动对象的位置处于不断变化中，使得查询语句执行过程中从 数据库中得到的数据与移动对象的实际位置数据可能产生较大的差异，导致产生 错误的结果。在温度监控系统中，当对空气温度不断变化的房间的温度进行监控 时，由于温度不停发生变化，使得温度计的读数也不断变化，但存储温度信息的 数据库中的数据却不能变化地如此频繁，势必使数据库中的数据与实际数据产生 差异。如果仍采用传统的关系数据库进行查询，也将导致产生错误的查询结果。 在面部轮廓识别系统中，即使是同一个人，不同照片的面部轮廓也不可能完全相 同。如果使用关系模型进行严格的匹配，将很难得到想要的结果，等等。 从上述情况可以看出。对于许多场合，使用传统的关系模型来对非精确数据 进行描述和处理已经不能满足实际要求，甚至可能会出现错误的结果。这就需要 采用其他的数据模型对非精确数据进行描述。 非精确数据通常采用概率数据模型的方式进行描述，这种模型对每个元组附 加一个概率值来表示该元组的可靠程度。概率数据模型不仅可以对关系数据模型 无法描述的非精确数据进行描述，而且可以描述关系数据模型所能描述的精确数 据。对概率数据库进行的查询称为概率查询。概率查询采用统计学的方法，得到 符合某个查询条件的结果的概率。概率查询无法得到某个具体时间点的精确结 果，却可以根据一个时间段内某个事件发生的统计规律，得到事件的概率结果。 山东大学硕士学位论文 在概率统计中，获取某个概率值的通常做法是利用概率密度函数进行积分。由于 数据库中只保存有最后一次更新的信息，没有更新信息的历史记录，所以只能采 用通用的一些分布规律，如均匀分布、正态分布、高斯分布等。这类通用的分布 规律显然降低了对具体问题的针对性，因为实际的分布不一定严格符合这类分 布，所以精确性不能得到保证。另外，对某些特定的查询，如查询过去某个时间 点的物体的位置信息，若采用精确查询，因为过去某个时间点的数据以被新数据 覆盖，而无法得到结果；若采用概率查询，虽然可以得到结果，但因为是统计意 义上的结果，和实际上的情况可能会有较大的差别。 造成上述情况的原因，在于数据库中只保留了最后一次更新的信息。本文改 变原来的存储方式，提出一种新的数据存储方式，不仅可以提高概率查询时获取 概率密度函数的准确性，从而得到更加符合实际情况的查询结果，而且使某些特 定查询的实现成为可能。 1 2 本文的主要工作和创新点 1 本文的主要工作 针对上述的概率查询存在的问题，本文对概率查询的一种典型应用移 动对象的位置查询方法进行改进，提出一种新的位置信息存储方式，当某个对象 的位置更新信息到达时，不再用新数据覆盖原来的数据，而是将新数据连同时间 等信息作为一条新记录插入到相应对象的信息表中。这样，就可以对过去某个时 间点的位置信息进行较为精确的查询。而且对于概率查询，由于保存了移动对象 的历史更新记录，使得概率密度函数的获取有了更可靠的来源，提高了概率查询 的精确程度。 2 本文的创新点 ( 1 ) 提出一种新的存储数据的方法，由于保存了历史更新记录，为后面 的算法改进提供了依据。 ( 2 ) 改进了概率查询中的概率计算的精度，通过保存的历史记录，可以得 到更具有针对性的概率密度函数，并对相关的定义和算法进行了该迸。 ( 3 ) 对某些特定的精确查询给出解决办法，如对过去某个时间点的位置信 息的查询给出了具体的处理方法和算法实现。 2 山东大学硕士学位论文 1 3 本文的组织结构 本文首先在第2 章给出概率数据库的相关概念、模型和研究热点，然后在第 3 章对移动对象的位置查询进行深入的描述，第4 章对目前采用的查询方法进行 改进。最后，总结全文。 山东大学硕士学位论文 第2 章概率数据库 2 1 概率数据库的概念 目前广泛应用的数据库绝大多数是关系型数据库，它们均是以efc o d d 的 关系代数为数据库理论的基础，由此导致了它只能存储、管理完全确定性信息。 而现实世界中存在大量不确定信息，如市场预测、专家系统、模糊分析等等，这 就需要建立一种具有不确定性量度的数据库模式。针对这种情况，d e b a b r a t a d e y 和s 啪i t s a r k a r 于1 9 9 6 年提出了p r m 模型( p r o b a b i l i s i i cr e l a t i a l m d d e i ) ，该 模型所描述的数据库结构模式称为概率关系数据库模式，简称为概率关系模式。 该模式是在数据库的每个元组中引入概率标记s p ( p o b a b i l i s t i cs i 驴) 属性来表 示该元组的不确定性。概率关系模式r 为属性名的集合 a l ， 2 ，a 3 ，a n l ， 其中属性之一为概率属性，用符号s p 表示。对应于每个属性a i ( i - 1 ，2 ， n ) ，有一个值域d i 。若a i 为s p ，则d i _ ( o ，l 】。积集d 一 d l ，d 2 一，d n 称为 r 的值域。r 是r 上的一个关系，r 的每个元组x 是r 到d 的一个函数，即x ：r d ，x ( a i ) d i ，i = l ，2 ，n ，表示某一对象的各属性的综合可信度或者说是某 一事件发生的可能程度。如图2 1 所示的概率关系。 工号电话号码 姓名工种工资，元部门 s p 3 0 2 57 1 8 4 8 l o 张三管理员 1 0 0 0 开发部0 2 3 0 2 57 1 8 4 8 1 0张三程序员5 0 0 开发部 0 2 3 0 2 57 1 8 4 8 l o 张三管理员 1 0 0 0 人事部0 6 7 0 2 3 8 5 4 2 3 8 7 李四 分析员 5 0 0 市场部 o 2 7 0 2 38 5 4 2 3 8 7 李四程序员 5 0 0 开发部 o j 3 7 0 2 38 5 4 2 3 8 7 李四管理员 1 0 0 0 人事部 0 1 图2 1 职工基本情况 工号是原始关键字，s p 属性值表示每个元组所有属性的不确定性。而部分 属性组合的不确定性则要通过投影操作完成。这种模式可以方便地表示确定性信 息，如果该元组表示完全确定的对象，则其s p = l ：这个模式中的所有关系均符 4 山东大学硕士学位论文 合l n f ，且关系是唯一合法的对象，并有一种通用的关系定义和关系操作。 另外需要说明的重要一点是，概率数据库分为两种：1 数据库中的数据是 确定的，查询结果是概率的；2 数据库中的数据是概率的，查询结果也是概率 的。所以包含元组概率的数据库一定是概率数据库，不包含元组概率的数据库也 可能是概率数据库，因为概率可能会从查询结果中反映出来。 概率关系数据库模式是数据库研究领域的一个新概念，对其理论体系的研究 尚处于开始阶段。由于它可以适应大量不确定信息的处理要求，有较大的应用前 景，因此，引起了人们极大的研究兴趣。 2 2 概率数据库的模型 【1 9 】给出了一种概率数据库的基本模型，包括概率关系和概率数据库的定义 以及概率关系的基本操作等，下面给出简单的描述。 2 2 1 概率关系 定义概率关系模式设s = a 1 ，a 2 ，a n ) 是一个传统关系模式，则一个概 率关系模式r i a 1 ，a 2 ，a n ，l a ，u a ) ，l a 和u a 分别称为概率下界属性和 概率上界属性，r上的元组0 1 ，口2 ，册，细，搬) 是 面m ( 彳1 ) 面m 似2 ) 砌聊( 彳n ) 矿矿 的一个元素，d o m ( a 1 ) ， d 0 1 1 1 ( a 2 ) 一，d o m ( a n ) 分别表示属性a l ，a 2 ，a n 的域，l a 和u a 的域为v ， v = 【o ，1 1 ，且u l a ，概率关系模式r 上的概率关系f 是其元组的有限集合，即 r c d a 坍( 4 1 ) 面所似2 ) x 面小似力) 矿矿，一个概率关系数据库是概率关系的 有限集合，一个元组x 在属性集a 上的取值记为x ( a ) 。 r 上的元组( a l ，a 2 ，a i l ，l a u a ) 的意思是：属性a 1 ，a 2 ，a n 分别取值 a l ，a 2 ，锄的联合概率取值区间为 i a ，u a 】，即p a 1 - a l ，a 2 = a 2 a i l = 狮 【1 a ，岫】。 若l a 和i l a 恒等于1 ，则r 上的每一个元组的概率值为l ，则概率关系模式 r 是一个传统确定性关系模式，这时可去掉l a 和u a 属性。 元组相等：两个元组相等，记为x = y ，当且仅当对所有的a i r ，y ( 加户x ( ) ， i = 】。2 ，n 。 山东大学硕士学位论文 主键和外键：在以上概率关系模式中，每一元组用有概率下界属性l a 和概 率上界属性u a 表示元组取r 上所有其他属性值的联台概率区闻，因此，每一元 组不能代表唯一的一个对象，一个对象可能有几个元组代表它的属性值得联合概 率区间，因此，主键是对象的代表，而不是元组的唯一标识。 2 。2 2 概率关系基本操作 为定义关系操作。先定义两个元组操作0 和固以及概率连接o 。 设x = y ，x = ( a l ，a 2 ，粕，l a ，u a ) ，y = ( a l ，a 2 ，锄，l b ，u b ) 定义z 0 y a 1 ，a 2 ，舳，l c ，u c ) 其中【l c ，u c 】= 【l a ，u 司u 1 b ，u b z = x 圆y = ( a l ，a 2 一，锄，l c ，岫其中【l c ，u c 】；【i a ，尬 n 1 b ，u b 概率连接o ：设事件e l ，e 2 的概率取值区间分别为【a l ，b l 】和【a 2 ，b 2 】，则 e 1 八e 2 概率取值区间依赖于事件e 1 ，e 2 之间的关系，例如：若e l ，e 2 相互独立， 则e l 八e 2 的概率等于事件e 1 和e 2 的概率之积，e 1 八e 2 的概率取值区间为【a 1 a 2 ， b l b 2 】，若不知e 1 ，e 2 之间的精确依赖关系，则e 1 八e 2 的概率取值区间为 i i l i n ( 0 ， a l + a 2 一1 ) ，m i n ( b 1 ，b 2 ) 】，若e 1 ，e 2 之间的依赖关系为一个事件蕴含着另一个 事件，则e 1 八e 2 的概率取值区间为 i l l i n ( a l ，a 2 ) ，m i n ( b l ，b 2 ) 】，以往概率关系 模型在定义关系的笛卡儿积或连接运算时都假定元组所代表的事件之间的依赖 关系为某一特定的依赖关系，例如相互独立，这就使得概率关系模型缺乏广泛性、 灵活性和实用性。为此，定义一个算子来表示事件之积的概率取值区间的计算。 定义概率连接满足以下条件的算子。称为概率连接： ( 1 ) 【a 1 ，b l 】0 心，b 2 】【l i l i n ( a 1 ，a 2 ) ，m i n ( b 1 ，b 2 ) 】， 这里【a ，b 】【a ， b l 当且仅当a a 且b b ( 2 ) 【a ，b 】0 【l ，l 】= 【a ，b 】 ( 3 ) 【a ，b 】o 【o ，o 】= 【o ，o 】 ( 4 ) 【a 1 ，b l 】0 a 2 ，b 2 】- 【a 2 ，b 2 】o 【a l ，b 1 】 ( 5 ) ( 【a l ，b l 】o 【a 2 ，b 2 】) 0 【a 3 ，b 3 】= i a l ，b l 】o ( 【a 2 ，b 2 】o 【a 3 ，b 3 1 ) ( 6 ) 若【a 1 ，b l 】f a 2 ，b 2 】，则【a 1 ，b 1 】o 【a ，b 】【a 2 ，b 2 】0 【a ，b 】 以下定义关系的基本操作： ( 1 ) 并：设r 和s 是同一关系模式r 上的关系，r 和s 的并操作定义为： 山东大学硕士学位论文 r us ：仅( r ) i ( ( x r ) ( v y s ( y x ) ) ) v ( ( x s ) ( v y r ( y x ) ) ) v ( 3 y r j z s ( ( x = y = z ) ( x = y o z ) ) ) ( 2 ) 交：设r 和s 是同一关系模式r 上的关系，r 和s 的交操作定义为： r n s = x ( r ) l3 y r j z s ( ( x = y = z ) ( 研o z ) ) ) ( 3 ) 非；设x = ( a l ，a 2 ，a n ，la j u a ) 则、f ( a 1 ，a 2 ，a n ，l 一1 a ，1 一u a ) 关系r 的非操作定义为：1 r = _ 1 x k r ( 4 ) 投影：设r 是关系模式r 上的关系，s c r ，r 在s 上的投影操作定义 为： 若为i a s ，u a 仨s ，则投影操作与传统关系模式下的定义相同，即 兀，( ，) = s ) l x r 若l a s ，u a s ，则先进行传统关系模式下的投影操作 s ) 怔r ) ，再对 x ( s ) l x r ) 中相等的元组进行合一，合一是指若 x ( s ) j x r ，中含有相等的元 组y 1 ，y 2 ，y k ，则令y = y 10 y 2 0 y k ， s ) f x r 经合一后的结果集即为 n 。( n a ( 5 ) 选择：设r 是关系模式r 上的关系，p 是由r 的属性形成的选择谓词， 关系r 的选择操作定义为： n ，( ，) = x | p ( x ) ，x r ) ( 6 ) 笛卡尔积：设r 、s 分别是关系模式r 和s 上的关系，t r 和t s 分别是 r 和s 上的元组，设t r = ( a l ，a 2 ，a n ，l a ，u a ) ，t s = ( b 1 ，b 2 ，b ，l b ，u b ) ， 元组t r 和t s 的连接定义为；t r o t s = ( a 1 ，a l 2 ，a n ，b 1 ，b 2 ，b m ，口，卢) ， 这里，( 口，声) = ( 1 a ，u a ) o ( 1 b ，u b ) 此处概率连接。算子可以由用户动态地、灵活地指定，r 和s 的笛卡尔积定 义为：r s = t r ( d t s lt r r ，馏s ) 以上介绍了6 种基本运算，其他的运算如差、占连接可由这6 种基本运算来 表达。设r 和s 是同一关系模式r 上的关系，r 和s 的差操作定义为：r s = r n l so 设r 、s 分别是关系模式r 和s 上的关系，p 为由( r u s ) 中的属性形成的谓 山东大学硕士学位论文 词，护连接操作定义为： f p s = 巧p ( r s ) 以上对概率关系和概率数据库进行了定义，并给出了概率关系的基本操作， 很多研究在上述模型的基础上进行了改进和补充，提出了各种不同的概率数据库 模型，【6 】中的p r o b e w 模型就是一个很典型的例子。这些不同的概率模型实际 上都是针对不同的应用背景和研究方向提出的，下面，就对目前概率数据库的研 究热点进行一个简单的描述。 2 3 概率数据库的主要研究热点 概率数据库正在得到越来越广泛的应用，研究熟点也层出不穷，下面对几个 主要的研究方向进行一个简要的介绍。 2 3 1 信息检索( i r ) 数据库系统支持简单的布尔查询检索模型，即系统返回满足查询条件的所有 元组。这将导致多结果问题的产生：当查询语句的选择性不强时，结果集中就会 包含过多的元组。比如：有一个由一个表组成的数据库，表的结构如下： f ) ，蹦c e ，c 时，b e d f 1 1 1 s ，b 灿r 0 0 傩，l i 、，i n g a r e a ，s d l 嘲d i 面c t ，e w ， p o h d l ，g a r a g e ，b o a t d o c k ) 。表中的每个元组表示一所代售房产。 假设有一条对该数据库的查询，如“c i 坤= s e 枷e 锄d e 、 一 强t e r 行o n t ”。结 果将会得到大量符合条件的元组。因为在s e a t d e 可以看到w 舭航l t 的房子太多 了。 多结果问题在信息检索中得到了广泛的研究。克服这个问题的办法有查询重 构技术和查询结果自动分级等。查询重构技术对查询语句进行重新调整，增强语 句的选择性。查询结果自动分级则根据结果集中每个元组和查询的相关度的大小 ( 比如，根据以前该类客户的其他潜在查询要求等) ，对结果集中的所有元组进 行排序，只将相关度较高的一个或多个元组作为最终结果返回。 显然，自动分级技术在数据库环境中的应用更能引起人们的兴趣。例如，在 前面的例子中的查询者可能更倾向于结果集中的房屋能够包含其它的属性，比如 山东大学硕士学位论文 好的s c h o o l d i s 研c t ，b o a t l ) o c k 等。一般来说，浏览产品目录的人会觉得这样的 功能更吸引人。 可以看出，这种相关性的取得是对用户潜在需要的一种推测，可能符合用户 的需要，也可能根本不符合要求，所以用概率数据进行表示。它根据用户以前对 某个属性的查询习惯对新的查询条件进行补充，经过相应计算后对每个符合查询 条件的元组赋予一个概率值，根据概率值由大到小进行排序，返回概率值较大的 k 个元组，同时也是相关度最大的k 个元组。 川【1 7 】中对该种情况给出了详细的处理方法。主要是利用用户在进行类似查 询时在数据库中保留的历史记录，根据用户以往的查询习惯，对潜在条件进行挖 掘，得到最终的结果集。 2 3 2 传感器数据 传感器通常用来对环境状态进行连续不断的检测。传感器的数据又被传送到 应用程序来进行决策或回答用户的查询。比如，建筑内的火警系统会使用温度传 感器来检测任何温度上的异常；军事系统中会在飞机上装备传感器来追踪风速， 用雷达监控和报告飞机的位置。这类应用中通常包括一个数据库或服务器来存储 或接收传感器发送的数据。但是有限的网络带宽和电池电量使服务器不能记录被 监控实体在每时每刻的确切状态。特别地，如果被监控实体的状态值( 如温度， 位置等) 不停地发生变化，数据库中存储的数值就有可能与实际的数值不符。这 时，对数据库进行查询就会得到错误的结果。 9 山东大学硕士学位论文 卜毒l_ | 卜* _ t ， * ， 倒k 乓一 鲫叠毒三其善i 图2 2 ：数据不确定性和最近邻居 如2 2 图0 ) 所示，用传感器监控两个移动物体口和6 。如果使用存储在数据 库中的数值( 0 0 和6 0 ) ，口就会成为q 的最近邻居。但事实上，口和6 已经分别移 动到了位置口1 和6 l ，这种情况下，6 才是g 的最近邻居。在对精度有苛刻要求的 情形下，产生错误的结果是不能接受的。 显然，在一个监控器的数值不停变换的系统里，从数据库中得到有意义的查 询结果是不可能的。但是，这些被监控实体的状态参数值在一个短的时间段内是 不会发生显著的变化的，参数值改变的程度或比率是会受到限制的。在上面的例 子中( 6 ) 的情况，如果假设在查询执行期间，口和6 的实际位置分别限制在从口。和 6 0 开始的一个特定区域内，这时就可以肯定口是4 的最近邻居。 通常情况下，物体的不确定性使我们无法确定单个物体是否是最近邻居。如 ( c ) 种情况所示，口和6 都有可能是g 的最近邻居，因为a 可能比6 距离g 更远， 反之亦然。所以如果一个实体的状态值表示成一个区间而不是确定的数值，则查 询结果可以是确定的，也可以是不确定的。 【3 】对该类数据进行了处理处理，提出了概率查询区域等与位置查询相关的 一些概念，并给出了两类典型概率位置查询的计算方法，具体细节将在后面进行 山东大学硕士学位论文 详细的讨论。【9 1 中对传感器网络进行概率查询的选择模式进行了研究。【1 0 】对概 率查询进行了分类，并针对不同的分类给出了相应的概率计算方法。 2 3 3 图像识别 在大多数图像数据库中，图像处理算法对图像进行处理，并将结果存入关系 数据库中。比如，一个面部图像数据库。对一张图片，图像处理算法做两件事： 它首先将面部信息记录在这张图片上，然后将记录在图片上的面部图像同存储在 面部轮廓数据库中的面部轮廓图片进行匹配。结果存储在这样的关系表中： 鲫i l 肌蜘e ，k r c o m e r j 【，l e r c o m e r 二y r t c o n 豇j ( ，r t c o m e r 二y ? e r s 伽p r o b ) 这个关系中的每个元组中的最后一个参数有三个概率，f ；，f ；和f ；表示3 个元 组。 图2 3 ；关系表f 如e 元组，表示，在图片i m l 萄f 上的左下角的坐标为( 5 ，l o ) ，右上角坐标为 ( 3 5 ，4 0 ) 的矩形区域内有一个人的脸部图像，该脸部图像是j o l l i l 的概率是 2 0 一2 5 ，j i m 为3 5 4 0 ，t 0 m 为4 0 一4 5 。 图像处理算法为图像计算出了一个概率值p ，但是考虑到算法本身也会产生 误差e ，所以概率并没有表示为一个数值，而是表示成了一个概率区间，实际的 概率值在【m a x ( 0 ，p 一8 ) ，m i i l ( 1 ，p + 8 ) 】之间。上面的例子中，设定p = o 0 2 5 ， 也就是说，图像处理算法计算的j o l l n 的概率值为2 2 5 。 上面简要介绍了概率数据库的几个研究热点。本文将对传感器数据中的一个 典型应用移动物体的位置查询，进行了进一步的研究，对目前采用的概率查 询方法进行了改进。在后面的部分中，首先对目前的移动物体位置查询系统进行 山东大学硕士学位论文 介绍，包括模型、功能以及相关的处理算法等，然后对已有的模型进行改进，并 利用改进后的模型给出新的处理算法。 山东大学硕士学位论文 第3 章移动对象的位置查询 3 1 移动对象位置查询概述 随着无线网络、传感器网络、移动定位等相关技术的发展，移动对象数据库 系统引起了人们的关注。移动对象数据库系统管理大量移动对象的位置信息，在 基于位置的信息服务、军事等领域有着广泛的应用。 移动对象数据库属于概率数据库研究中传感器数据的研究范畴，在传感器数 据的研究中具有很强的代表性。i y n o l d c h e n g ，k 锄一y i u l 锄等在【2 】中给出了对 移动对象进行查询的模型。如图3 一l 所示： j ，黑i 南 图3 1 ：移动对象位置查询模型 由上图可以看出该查询模型主要由移动对象查询处理程序和位置信息数据 库，移动对象和客户端查询三部分组成。移动对象以一定的频率产生位置和速度 等状态参数信息，并通过无线网络将参数传送到移动对象查询处理程序进行处 理；移动对象查询处理程序接收到移动对象的更新信息，进行相应处理后存入位 置信息数据库，该数据库为概率数据库。同时，移动对象查询处理程序还响应来 自客户端的查询请求，从概率数据库中得到相应的结果返回给客户端；客户端则 运过不断查询数据库获得最新的位置信息和状态参数。下面对这三部分进行较详 细的描述。 辫她 山东大学硕士学位论文 1 移动物体 移动物体通过如g p s 等移动传感器设备产生位置。速度和方向等即时状态 参数，并按一定的时间间隔，通过无线网络，向查询处理器发送最新的状态信息。 该时间间隔由查询处理器迸行控制。由于无线网络的带宽的限制，通过无线网络 传输的数据量应尽量小，从而减少因网络拥塞而产生的传输延迟或信息丢失。另 外，由于移动物体本身因素( 如电池等) 的影响，移动物体的位置信息产生装置 只具有产生简单的位置，速度和方向等信息的能力，而不具有复杂的处理和计算 功能，如距离目的地的路径和距离等，以避免复杂计算对资源的过度消耗。 2 移动对象查询处理程序 移动对象查询处理程序接收到来自移动对象的更新信息，进行进一步处理 后，存入位置信息数据库。除此之外，移动对象查询处理程序将通过无线网络向 发送更新信息的移动对象发送控制信息，该控制信息的内容是该移动对象下次发 送更新信息和本次更新的时间间隔，由于该时间间隔是对下次应该更新时间的预 测，故称为预测时间间隔( p ) 。阿由移动对象查询处理程序根据查询语句的 不同类型，采用特定的算法计算得到。移动对象接收到该控制信息后，下次将按 该控制信息包含的时间间隔发送位置更新信息。另外，移动对象查询处理程序还 响应来自客户端的查询，根据查询条件，从位置信息数据库中取得要查询对象的 状态参数，通过相关的概率算法计算查询结果的概率，并将最终的查询结果返回 到客户端。 3 客户端查询 客户端负责与用户进行交互，给用户一个友好的人机界面。它把用户输入的 查询关键字组合成完整的查询语句，并将查询语句传送到查询处理器。查询完成 后，将查询结果显示给用户或进行进一步处理。 在对移动对象位置查询模型的总体结构和功能有了初步的了解之后，下面对 该系统中最重要的部分移动对象查询处理程序的功能、结构和设计进行详细 的介绍。 1 4 山东大学硕士学位论文 3 2 移动对象查询处理程序 作为移动对象查询系统中最重要的部分，移动对象查询处理程序主要有三部 分功能：接受移动对象的位置更新信息向移动对象发送控制信息和处理来自客 户端的查询。接受更新信息主要是将使用标准的s q l 语句将移动对象的更新信 息保存到数据库中；向移动对象发送控制信息主要是采用特定算法，根据不同的 查询类型，锝到下次移动对象发送更新信息的时间间隔( p 1 1 ) ，并将此时间间隔 发送到相应的移动对象，以达到控制信息更新频率的目的；处理客户端查询主要 是对来自客户端的查询进行处理，根据查询语句的不同类型和条件，计算出概率 结果，返回给客户端。 由此可见，对于该系统中两个重要数值阿和查询结果的计算，都需要 知道查询的类型。所以下面首先对查询进行分类，然后根据分类来计算肌和查 询结果值。 3 2 i 查询的分类 根据不同的分类标准，可以将查询进行如下划分： 按查询是否返回确定的数值，可以将查询分为精确查询和概率查询。 1 精确查询；结果值是确定的，或完全符合查询条件的。 2 概率查询：结果值是不确定的，对结果集中的每一个元组，都有一个 概率值与之对应，以表示原则的可靠性。 特别的，对于概率查询，可以按结果集中的元组是否需要排序， 分为基于分级的查询和非基于分级的查询。 1 1 基于分级的查询：对数据项进行排序操作，典型应用是最近邻居 查询( n n q ) 。 非基于分级的查询：不对数据项进行排序，典型应用是范围计数 查询( r c q ) 。 按查询结果的属性，分为基于值的查询和基于实体的查询。 1 基于值的查询：结果返回一个简单的数值，比如查询某个物体和查询 点的距离。 2 基于实体的查询：返回满足查询条件的物体的集合。比如范围查询 山东大学硕士学位论文 ( r q ) 返回查询区域内的物体的集合。 另外，在【1 3 】中，根据查询语句的构成的复杂度，可以将查询分为容易查询 和困难查询。这里不作进一步的讨论。 3 2 2 信息更新频率的控制 对查询进行简单分类后，将利用该分类对个重要的数据位置信息更新 频率进行计算。 位置更新频率是指移动对象通过无线网络向位置信息系统发送位置更新信 息的频繁程度。 3 2 2 1 信息更新频率的控制方式 目前，控制移动对象位置更新频率主要有两种方式： 1 基于距离的控制方式 这种控制方式根据移动对象的移动距离进行更新。一旦移动对象移动超过 定的距离，就发送一次位置更新信息。 2 基于时间的控制方式 这种控制方式根据移动对象的移动时间进行更新，一旦移动对象移动超过一 个时间间隔，将马上发送一个位置更薪信息。在基于时闻的控锘g 方式中，还可以 分为基于固定时间段的控制和基于变化时间段的控制。基于固定时间段的控制是 指更新的时间间隔是固定的，无论移动对象有没有移动，只要经过这个固定的时 问段，就发送一次位置更新信息；基于变化时间段的控制是指移动对象发送位置 更新信息的时间间隔是动态变化的，每次的时间间隔可以相同，也可以不同。这 个变化的时间段的确定主要基于两个方面： ( 1 ) 该移动对象对查询结果的影响 当移动对象的更新信息对查询结果影响不大时，可以适当增大下次更新的时 间间隔：反之，当移动对象的更新信息对查询结果影响至关重要时，就应当缩短 下次更新的时间间隔。 ( 2 ) 对移动对象运动进行预测的准确程度 当对移动对象的运动的预测出现较大偏差时，应缩短下次进行更新的时间， 山东大学硕士学位论文 否则将得到错误的结果；当移动对象的实际运动和预测基本一致，或误差在个 可接受的范围内时，表明通过预测就可得到位置信息，可以增大下次更新的时间 间隔。 之所以采用变化时间段的控制方式，主要考虑的是在不影响查询精度和可靠 性的前提下，尽可能地减少移动对象进行位置更新的次数。因为无线网络的带宽 是有限的，当被监控移动对象的数量