工学硕士学位论文-基于DRA的不确定数据的查询研究

分类号： 密级： U D C ： 编号： 工学硕士学位论文基于DRA的不确定数据的查询研究硕士研究生指导教师学科、专业：计算机软件与理论论文主审人：哈尔滨工程大学2011年12月分类号： 密级： U D C ： 编号： 工学硕士学位论文基于DRA的不确定数据的查询研究硕士研究生：魏小艳 指导教师：张志强 教授学位级别：工学硕士学科、专业：计算机软件与理论所在单位：计算机科学与技术学院论文提交日期：2011年12月论文答辩日期：2012年3月学位授予单位：哈尔滨工程大学 Classified Index: U.D.C:A Dissertation for the Degree of M. EngResearch on Query Processing AlgorithmsIn Uncertain Data Based DRACandidate:Wei XiaoyanSupervisor:Prof. Zhang ZhiqiangAcademic Degree Applied for:Master of EngineeringSpecialty:Computer Softwar and TheoryDate of Submission:Dec., 2011Date of Oral Examination:Mar, 2012University:Harbin Engineering University 哈尔滨工程大学学位论文原创性声明本人郑重声明：本论文的所有工作，是在导师的指导下，由作者本人独立完成的。有关观点、方法、数据和文献的引用已在文中指出，并与参考文献相对应。除文中已注明引用的内容外，本论文不包含任何其他个人或集体已经公开发表的作品成果。对本文的研究做出重要贡献的个人和集体，均已在文中以明确方式标明。本人完全意识到本声明的法律结果由本人承担。 作者（签字）： 日期： 年 月 日哈尔滨工程大学学位论文授权使用声明本人完全了解学校保护知识产权的有关规定，即研究生在校攻读学位期间论文工作的知识产权属于哈尔滨工程大学。哈尔滨工程大学有权保留并向国家有关部门或机构送交论文的复印件。本人允许哈尔滨工程大学将论文的部分或全部内容编入有关数据库进行检索，可采用影印、缩印或扫描等复制手段保存和汇编本学位论文，可以公布论文的全部内容。同时本人保证毕业后结合学位论文研究课题再撰写的论文一律注明作者第一署名单位为哈尔滨工程大学。涉密学位论文待解密后适用本声明。本论文（在授予学位后即可 在授予学位12个月后 解密后）由哈尔滨工程大学送交有关部门进行保存、汇编等。作者（签字）： 导师（签字）：日期： 年 月 日 年 月 日 哈尔滨工程大学硕士学位论文摘 要随着不确定数据的大量产生，如何从不确定数据库中进行Top-k查询成为一个急需解决的问题。由于不确定数据概率维的存在，使得它和传统的确定性数据在处理方法上有很大的不同，准确并高效解决不确定数据的查询问题具有重要意义。本文首先详细介绍一下不确定数据的产生的原因，及其特点，比较一下它和确定性数据的不同之处。之后总结了现有针对不确定数据的查询处理模型和处理方法，并指出这些模型存在的问题，以及现有方法的优缺点。本文不仅对现有的处理不确定数据的Top-k方法进行系统的研究，而且还比较了Skyline查询和不确定数据Top-k查询之间的关系，并采用已有的Skyline的方法来解决不确定数据的Top-k查询。最后，提出使用元组之间的DRA关系来改进现有的方法，该思想是通过元组的分值和概率值之间的大小关系来确定元组之间的控制关系，从而使得一些被控制的元组可以直接排除，不参与Top-k查询的计算，使得现有的查询方法可以更加高效的得到准确的结果。本文提出的使用元组之间的DRA的关系来提前删掉一些不可能成为结果的元组，使得查询过程更加简单。另一方面，对于某些数据经常更新变化的数据库，这种方法表现出更加优秀的效果，可以直接判断发生变化的元组能不能对查询结果产生影响，这样就节约了重新查询所需要的时间和空间。实验结果表明本文所提出方法能够更好的满足用户对于搜索结果的快速和准确的要求，搜索效率提高了。关键词：DRA；Top-k；不确定数据AbstractWith the large number of uncertain data produced, how to get the result of the Top-k query in uncertain database is becoming an urgent problem. Because the special dimension of probability exists in uncertain data, making it is very different with the certainty traditional data in processing methods. It has a great significance to solve the query problem in uncertain data accurately and efficiently.First, the causes of how to generate uncertainty data, and the characteristics of uncertain data, compare it with deterministic data and find the differences of them. Then summarize the existing query processing models and methods for the uncertain data, and point out the problems in these models explain the corresponding methods are how to solve these problems, as well as advantages and disadvantages of existing methods. This paper not only study the existing Top-k methods of processing uncertain data, but also study the relationship between Skyline queries and queries and Top-k queries. use the existing methods of processing Skyline queries to solve the Top-k queries. Finally, we proposed use the DRA (dominate relationship analysis) of the tuples to improve existing methods, the idea determine the control relationships of the tuples by compare the score and probability, making some of the controlled tuples excluded directly before query processing, do not appear in Top-k query calculation. Witch can make the existing query methods more efficiently and accurately.This paper presents the idea of using the DRA (dominate relationship analysis) of the tuples to delete those tuples can not be the result, making the query processing be more simple.On the other hand, for the frequently updated database, this method showed more excellent effect. It could determine whether the change tuple will make an impact on the query results, thus saving the time and space for re-query. Experimental results show that the method we proposed can be better meet the users requirements for fast and accurate get the query result, and the search efficiency is also getting improved.Key words: DRA; Top-k; Uncertain Data目 录第1章 绪 论11.1引言11.2 研究背景及意义21.3 论文工作31.4 论文的组织及内容安排4第2章 不确定数据的介绍62.1 不确定数据产生的原因62.2 不确定数据的概念和特点72.3 不确定数据的不确定性82.3.1 属性值的不确定性82.3.2 存在性的不确定性92.4 不确定数据元组之间的关系102.4.1 元组之间相互独立102.4.2 元组之间存在一定关系112.5 本章小结12第3章 不确定数据的处理模型及存在的问题143.1 可能世界模型143.1.1关系型数据模型153.1.2 流数据模型173.1.3 多维数据模型183.2可能世界模型存在的问题203.2.1排序的方法203.2.2 剪枝的方法233.3 本章小结24第4章 基于DRA的不确定数据查询264.1 现有的不确定数据查询264.1.1 U-Topk264.1.2 Uk-Ranks284.1.3 PT-k294.1.4 Pk-Topk304.2 DRA思想的来源和Skyline查询314.3 基于DRA的不确定数据查询424.3.1 基于DRA的U-Topk查询424.3.2 基于DRA的PT-k查询454.3.3 基于DRA的Pk-Topk查询474.3.4 基于DRA的不确定数据查询474.4 本章小结48第5章 实验与结果分析495.1 实验环境495.2 实验数据495.3 实验结果495.4本章小结57参考文献58结 论61攻读硕士学位期间发表的论文和取得的科研成果62致 谢63第1章 绪论第1章 绪 论1.1引言由于RFID，GPS和无线传感器等技术的快速发展和大量应用，不确定数据已经对人们的生活产生了重大影响，由于不确定数据元组存在一个0到1之间的数字来表示其不确定性，使很多有关传统的确定性数据的处理方法不能够用于处理不确定数据，急切需要提出新的方法来处理大量的不确定数据。自上个世纪八十年代末，Cavallo1和Abiteboul2提出有关不确定数据和可能世界的理论后，就有不少学者开始关注这种含有不确定概率值的新型数据。2000年以后，随着不确定数据出现的越来越多，数据库领域的研究人员对此也产生了极大的兴趣，并推动了社会各界对不确定数据的关注和研究。目前，已经有很多文献对不确定数据的处理模型和查询算法进行了研究。可能世界模型1,2是最早被提出来的，之后的很多处理模型和查询算法都是在可能世界模型的基础上提出的。一些研究人员根据不同的数据特点，提出了相应的处理模型，用于处理拥有某些数据结构特性的不确定数据，比如滑动窗口模型3是针对随时间快速流动的数据(流数据)所提出的处理模型，当数据随着时间的变化，以流数据的形式快速产生时，可能世界模型产生的可能世界实例的数目将会非常大，而滑动窗口模型只处理窗口内的元组，这些元组由窗口的大小和窗口滑动的位置决定，这样就大大减少了要处理的不确定数据元组的数量。在众多的处理模型被提出的同时，也有不少查询方法根据不同的语义和应用背景被明确定义下来。比如Top-k查询4和Skyline查询5,6，Top-k查询就是要查询不确定数据中分值最高的k个元组，由于在不确定数据中每个元组都存在不确定性，因此对于不确定数据的Top-k查询处理不能像在传统的确定性数据库中那么简单，不仅要考虑分值的大小，还要考虑到元组的不确定性；Skyline查询原本是用于研究多目标优化的问题，是属于确定性数据库的研究范畴，但近年来由于可能世界模型的影响力越来越大，文献6也把Skyline查询引入到不确定数据的研究中来。本文所研究的问题就是如何基于可能世界模型更加高效的处理存在性不确定数据的Top-k查询问题，由于存在性不确定数据产生的可能世界实例的数目会随着数据量的增长呈现出指数级的增长，这样当数据量比较大时，就无法得到所有的可能世界实例，也无法得到正确的查询结果。目前已经有不少文章3,4,7针对这个问题和不同的Top-k查询方法给出了比较好的解决办法，本文工作就是在这些方法的基础上提出了改进，进一步降低了时间复杂度和空间复杂度，提高了搜索的效率。1.2 研究背景及意义最近几年，针对不确定数据各方面的研究都取得了很大的进展，在众多数据模型和查询方法被提出后，又出现了不少具体的处理方法，得到了不错的处理效果。由于不确定数据产生于多种应用背景中，所以产生不确定数据的原因也是大不相同的，总的来说，一方面是由于客观因素产生的，如数据测量的不准确，传输过程中受到干扰等，另一方面是主观因素造成的，即人们在处理数据时给数据造成的不准确性，如处理脏数据，数据集成等8-11，由于不确定数据来源的多样性和应用的广泛性，学术界已经在多方面展开了对不确定数据的研究。按照不确定数据的不确定性，不确定数据主要两种，属性值不确定的数据和存在性不确定的数据。属性值不确定的数据是指在数据元组的一个或多个属性上有多个属性值，每个值都是其对应属性上的可能出现的值，并且都有一个0到1之间的概率值来表示该属性值出现的可能性；存在性不确定的数据是指数据元组不是一定存在于客观世界中的，每个存在性不确定的元组都有唯一的概率值表示该元组存在的可能性。本文主要研究存在性不确定数据的Top-k查询问题，在传统的数据库中，我们常常会按照一定的标准，找到在某个属性值最高的k个元组，然而在不确定数据库中，由于元组的存在性不能够确定，所以对于此类数据的Top-k的查询问题不再只是简单的考虑某些属性值的问题了，还需要考虑其存在性的问题，而可能世界模型合理的解决了这个问题。可能世界模型能够把所有不确定数据元组在客观世界存在的不确定性转变为可能世界实例出现的不确定性，可能世界实例是不确定数据元组的任意一种组合，一个可能世界实例就表示不确定数据元组出现的一个可能世界，在这个可能世界实例中出现的元组就一定是存在于这个可能世界里，其他的元组也一定不存在于这个可能世界里8。由于可能世界模型合理的把元组的不确定性转化为可能世界实例的不确定性，使得很多关于不确定数据的研究都是基于不确定数据模型的，然而可能世界模型在计算过程中是要生成不确定元组数目指数级别的可能世界实例，在不确定数据元组的数目很大时，基本上不可能得到有效的查询结果，所以快速地得到不确定数据Top-k查询的正确结果就变得至关重要。目前，研究者们已经提出了以下四种不确定数据的Top-k查询语义：U-Topk4、U-kRanks4、 PT-k7、 Pk-topk3 ；U-Topk查询返回k个按照分值排序的元组，这k个有序元组排在前面的可能世界实例概率值之和一定是最大的；U-kRanks查询是要查找可能世界实例中前k个位置上，每个位置上出现的元组中相应的可能世界实例概率值之和最大的元组；PT-k查询是要找到排在可能世界实例前k个位置的元组中相应的可能世界实例之和大于等于阈值P的那些元组；Pk-Topk查询是要查找排在可能世界实例前k个位置的元组中相应的可能世界实例之和最大的k个元组。针对每一种查询语义，都有相应的解决算法被提出，这些算法都在一定程度上解决了指数级可能世界实例的问题，而本文通过应用DRA思想对这些算法提出了进一步的改进，不仅减少了很多参与查询计算的元组的数量，也降低了形成可能世界实例的复杂度。1.3 论文工作本文是在现有多种不确定数据查询处理方法的基础上，为了进一步提高算法的计算效率，降低算法的时间复杂度和空间复杂度，本文提出了通过DRA（分析元组之间的控制关系）思想来简化查询处理过程，并得到了不错的效果。什么是控制关系呢？其实这个概念最早来源于微观经济学，当用户去买某种商品时，都倾向于买质量好且价格低的商品，这里我们可以说是质量好价格低的商品是控制价格高质量低的商品的，以为质量好价格低的商品更符合人们的意愿，在Skyline查询中，也用到了这种思想来处理多目标优化的问题，而本文把这种思想引入不确定数据的多种Top-k查询中，实现了对原有方法的改进，得到了更优的查询效果。那如何引入这种思想的呢？我们定义不确定数据元组之间的控制关系如下：如果不确定数据元组t1在分值上大于另外一个元组t2，并且t1存在的概率值大于等于t2，我们就说元组t1能够控制元组t2。在不确定数据的Top-k查询中，目的是要找到分值又大，存在的可能性也大的k个元组。按照不确定数据元组之间的控制关系和几种不确定数据Top-k查询方法的定义，我们很容易证明，对于元组t2，如果还有另外k-1个或更多的元组控制元组t2时，那么元组t2就不可能成为不确定数据的Top-k查询结果。本文就是通过分析不确定数据元组之间的控制关系，把一些不可能出现在查询结果中的元组去掉，大大减少了要参与查询计算的元组数量，尤其是在一些k值不是经常变化的应用中，当数据变动时，(比如插入和删除操作)，只需要考虑插入的元组和要被删除的元组有没有对相应的控制集合产生影响，从而确定数据的变动有没有可能影响到查询结果，如果能够判断出产生变化的元组不可能成为不确定数据的Top-k查询结果，就不需要再次对数据进行查询，不仅能够减少很多不必要的花销，而且能够快速准确的返回查询结果。1.4 论文的组织及内容安排本文提出了不确定数据元组之间的控制关系，并用于改进现有不确定数据的处理方法，使大量不能成为查询结果的元组在查询处理之前就排除掉,增加了查询的效率。本文具体的内容安排如下：第一章，对不确定数据的发展过程做了简单的介绍，同时也介绍了现有的研究取得的成果和存在的问题，指出了解决不确定数据的Top-k查询问题是一件非常重要，非常有价值的一件事，也提出本文的研究工作是通过分析不确定数据元组之间的控制关系，去掉那些不可能成为查询结果的元组，减少了查询过程中的计算和比较，使现有的查询方法能够更加快速准确的得到查询结果，同时介绍了本文的工作概况。第二章，介绍了不确定数据产生的原因，主要有客观原因和主观原因两个方面；之后介绍了不确定数据的概念和特点，指出每一个不确定数据元组都有一个相应的概率值来表示其不确定性，并按照不确定性把不确定数据分为属性值不确定的不确定数据和存在性不确定的不确定数据，给出了每种不确定数据详细的描述和说明；最后，介绍了不确定数据元组之间可能存在的关系，有可能是相互独立的，有可能存在异或关系，也有可能存在包含和被包含的关系，对这几种情况也都进行了一一解释。第三章，首先给出了可能世界模型的定义，指出可能世界模型是不确定数据研究领域最基本的模型，该模型通过把不确定数据元组的不确定性转变为可能世界实例出现的概率，能够合理的解决不确定概率值给不确定数据带来的影响，并且本文用实例说明了可能世界模型的思想和特点；之后本文介绍了几种用于处理不同数据结构的不确定数据处理模型，这些模型都是在可能世界模型的基础上，根据相应的数据结构的特点提出的，对于每一种特殊的数据结构，本文都给出了相应的分析过程；最后，指出了可能世界模型存在的问题，即可能世界实例的数目会随着不确定数据元组数目的增长呈现指数级的增长，并介绍使用分值排序和剪枝的方法来解决这个问题。第四章，本文的核心内容，先是介绍了几种主要的不确定数据的查询方法，由于每一种查询方法的查询语义和应用背景的不同，所以还没有一种方法能够同时解决这几种不同的查询，本文介绍了每一种查询独有的解决办法；然后介绍了DRA思想的来源和应用，提出了不确定数据元组之间的控制关系，即一个元组t1在分值上大于另外一个元组t2，并且存在性概率值也大于等于元组t2，就说元组t1能够控制t2，并给出了不确定数据的Top-k查询和Skyline查询的关系；最后，详细阐述了本文是如何使用元组之间的控制关系来改进现有的处理方法，对于每一种查询方法，都举例说明DRA思想的在查询中的具体作用。第五章，主要介绍了实验的运行环境，使用到的工具，以及实验的数据、实验的结果。并对实验数据和实验结果进行了描述和分析评价，为了更好的证明本文方法的效果，试验中使用多组数据，并使用多个k值对每组数据都进行了查询。最后，对本文要解决的问题和所提到的方法进行了简要的概括，并指出了文章的不足之处，以及不确定数据研究领域还存在的问题和未来的研究方向。5第2章 不确定数据的介绍第2章 不确定数据的介绍由于不确定数据存在于人们生活的各个角落，而且这种带有0到1之间的概率值来表示其不确定性的数据，使得它和传统的确定性数据在处理方法和管理方式上都大为不同，以往的已经成熟的技术不能够直接用于处理不确定数据12。那么什么是不确定数据，它是如何产生的，又有什么样的特点呢？2.1 不确定数据产生的原因不确定数据产生的原因多种多样，换句话说，很多应用和不同领域都能产生大量的不确定数据，如GPS、RFID，无线传感器网络等应用和金融、军事、物流、商业、电信等领域8,13-18。有一些研究者把不确定数据按照其产生的过程中是否受到人为因素的影响分为主观不确定数据和客观不确定数据，主观不确定数据是指由于数据的处理过程中受到人为因素的改变而产生的不确定性，如数据清洗、数据集成等；客观不确定性是指原始数据由于电子元件不够精密在产生、传输和存储等过程中造成的不确定性19。这一节，我们按照具体的应用背景说明一下不确定数据产生的原因，大致有以下几个方面:(1)数据自身存在不确定性，这是由于测量设备的局限性和不精确造成的不可改变的误差，以及数据在传输过程中受到温度，风力，压强等众多环境因素的干扰而造成的数据不准确，这是产生不确定数据的客观因素，也是根本因素。例如无线传感器网络、全球定位系统、无线射频识别等技术，都会因为设备采集数据的精确度不够高和数据传输过程中受到噪声的干扰等影响数据的准确性。(2)网络数据的不确定性，一方面是因为网络信息传播快，信息很容易被复制，在复制的过程中产生了不准确的数据；另一方面是信息资源十分丰富，而各个网站的信息管理是按照自己的标准进行的，出现了众口不一的情况，对相同的信息和记录，也会出现不同的数据，造成了数据的不确定性。例如对酒店价格和地理位置的查询问题，也许同时有多家网站或信息查询系统提供这样的信息，但对同一家酒店，他们在价格或者位置上提供的信息不尽相同，甚至相差甚远，这也许是数据库管理员的操作失误，也许是信息来源本身就存在错误，也许是没有及时更新正确的信息，导致了信息不一致，数据不准确。(3)数据库管理员对数据的预处理，如处理缺失值和数据集成等造成的数据不准确，什么是缺失值呢？为什么要处理缺失值呢？其实缺失值就是指由于操作失误或者缺数据等原因造成的数据不完整，以至于数据库管理员在数据库中挖掘一些信息时，无法按照正常的步骤处理数据，这时如果缺失的数据占很少一部分时，可以根据一些处理缺失值的方法人为的添加数据或删除数据，使缺失值对数据挖掘造成的影响降到最低，但这些操作都导致了数据的不准确。同样在数据集成的过程中，也会存在多个不同来源的数据在格式、属性个数和属性范畴等不一致的现象，需要调整其中的一个或者多个数据源，使各种需要集成的数据在逻辑上和物理上达到统一，这就会导致原始数据发生改变而出现不确定性。比如某个学生信息数据库关于学生的表现这一列写的是优秀、良好、一般、较差等，而另外一个是打的分数，按照分数的大小来刻画表现的好坏，那么在集成的时候，就得把打分的那个数据库转化成另外一种评价标准，或者把写优良中差的数据转化为分值形式的数据，这都引入了数据的不确定性。(4)为了满足某种目的特意造成数据的不确定性，比如客户信息隐私保护，把客户的年龄从一个准确的数值改为一个年龄段数据；或者移动位置服务中的隐私保护，随着移动技术的发展，随时都能获得某个人在什么地方的信息。文献20叙述了某人利用GPS技术随时监控别人位置的事情，还一些某公司利用带有GPS的手机追踪监视本公司雇员行踪等等的案例，这在军事上也有着广发的应用。越来越多的事实说明先进技术给人们的生活带来方便时，也在一定程度上侵犯了人们的权利，带来了很多不利因素，保护隐私变得日益重要，目前也出现了很多隐私保护的算法，如K-匿名算法21,22，专门用来把数据变得不准确以达到保护隐私的目的。2.2 不确定数据的概念和特点不确定数据简而言之就是说数据不准确、不确定。不确定数据的每条记录都会有一个0到1之间的一个数值来表示这条记录某些属性值的不确定性和这条记录存在的不确定性，对于属性值的不确定性，0表示该值一定不是这一记录在相应属性上的取值，1表示数据记录在相应属性上有且只能有这一个取值；对于存在性的不确定性，0表示这条记录一定不存在于客观世界中，1表示一定存在于客观世界中，值越大就表示存在的可能性越大，这个值就表示了数据确定存在的概率。这一特殊的存在性概率值，使得不确定数据与传统的数据库是有很大区别的，在传统的数据库中，只要是在数据库中出现的信息就都是一定存在的，是可信的和确定的。不确定数据的主要特点就是数据的不确定概率值，也正是这一概率值描述了数据的不确定性并给数据处理和管理带来了一系列的新情况、新问题。不确定概率值出现在数据处理中的各个环节，数据库管理人员输入数据时可能因为操作失误产生不准确性，数据存储和计算时也可能由于数据精度产生错误，数据在输出时也可能受到某种条件的约束产生不准确的数据，造成不确定性8，由此看来，在数据处理的整个过程中都有可能产生不确定数据。表面上，不确定数据和传统的确定性数据在存储和表示的形式上没有太大的差距，在传统的确定性数据库中，每条记录都是唯一确定的，并存在一个或者多个属性，而每个属性只有一个取值，在不确定数据库中，每条记录并不是一定存在的，或者每条记录的每个属性上的取值不是唯一的，那么我们能不能把不确定数据库中表示数据存在性的概率值和属性取值的概率值看作是一个独立的普通属性值，然后把不确定数据库看做是确定性的数据库，使用已经成熟的确定的数据库的处理方法进行处理，事实证明这种方法并不可行，这种转变本身就不正确，不确定概率值对于不确定数据的意义深远，影响也特别大，并不是一个简单的转变就能够遮盖的23。2.3 不确定数据的不确定性文献8指出按照不确定性的不同把不确定数据分为了两大类，一类是数据元组存在于客观世界的不确定性，一类是数据元组属性取值不唯一的不确定性，存在级不确定性指的是数据元组不一定存在于客观世界中，这种不确定性比较普遍，也很常见，属性级不确定性和存在级不确定性有着本质的区别，和元组的存在无关，而是指数据元组的一个或多个属性上的取值无法确定，可以有多种取值的可能性，并且每一个取值都有相应的概率值或者函数来描述特定属性值的不确定性。2.3.1 属性值的不确定性属性级的不确定数据是比较容易处理的。表2.1是一个客户信息调查表，这是数据挖掘中经常能够看到的，用来研究什么样的人群更有可能购买电脑，这个信息对于电脑销售公司来说是非常重要的，这样就能够针对专门的人群进行宣传，不仅可以节约广告的成本而且得到的收益也会比较大。但是客户可能为了保护自己的隐私不愿意透漏真实的数据，所以调查得到的数据也不是十分确定的，表2.1中显示的年龄和收入这两个属性中都包含有不确定的属性值，如ID为1的记录在年龄属性上是20-24，这不是独立确定的年龄值，而是一个区间值，这也就表示该客户的年龄不能够从这张表中确定下来，这个区间的任意一个值都有可能是该客户的真实年龄。表2.1客户信息不确定数据ID性别年龄收入购买与否1女20-243000买2男232500-5000买3男50-552000不买4女522500不买5男30-324200-4500不买现在已经存在不少方法能够解决类似的问题，最简单的就是取这一区间的每个值的可能性是一样的，比如第一条记录中的年龄20-24，就可以看做真实年龄为20的概率是1/(24-20+1)=0.2，同样取其他几个年龄值21,22,23,24的概率也都是0.2。也有考虑到按照某一年龄出现的频率来划分的，比如第二条记录年龄为23，那么在对第一条记录划分的时候就会把真实值为23岁的概率赋值更大一些，因为该值比其他几个值更有可能成为该客户的真实年龄。文献24,25专门对这个问题做出了详细分析和深入研究，而文献26也是针对类似的数据进行研究的，只是目的和处理方式不同而已，前者是为了从数据中挖掘出有用的信息，后27,28者则是从这种具有范围区间数据的偏序关系入手，用来解决数据的查询问题。2.3.2 存在性的不确定性存在级的不确定性显而易见就是指数据的不确定性是关于该数据是否存在的问题，一个数据元组在一个客观世界中，只有两种可能，要么存在，要么不存在，但是如何衡量这个存在不存在的问题呢，那就是这个存在的概率值了。现有比较合理的方法都是把这种不确定性转化为确定的，然后再对数据进行处理。如表2.2就是一个在存在级上不确定的数据表，一共有6条记录，这里也可以说是6个元组，每条记录的信息都是由雷达采集到的。比如t1这条记录是指在10:02的时候，位于南通大街这车牌号为黑AQ1060的这辆车的速度是100公里每个小时，后面的概率值0.6是说这条记录的可信程度，即存在的可能性。这是因为雷达得到的信息本身就可能由于电子元件的不够精密而不够准确，另外这个信息由雷达传送到服务器的过程中可能会受到高压、高温等环境因素的影响而变得不准确。表2.2 雷达探测不确定数据Id 时间地点车牌号速度概率值t110:02南通大街黑AQ10601000.6t210:30先锋路黑AQ1005800.7t311:25和平路黑AQ1203900.3t411:33南通大街黑AQ11801200.5目前，已经有很多文章是针对存在性不确定数据展开研究的，有的是在处理模型20-22上做研究，这方面的工作我们将在下一章详细说明。还有的是考虑存储索引的问题23-25，比如概率阈值索引、U-tree29-32索引、APLA-tree33,34索引等都能够很好的处理不确定数据，大大提高了查询的效率。也有考虑数据挖掘相关问题的35-42，把现有的针对确定性数据的经典挖掘算法进行了改进，使其适用于不确定数据上，也得到了不错的效果。2.4 不确定数据元组之间的关系 传统的确定性数据库中，各个元组之间都是相互独立的，没有任何关系，并且是确定存在着的。然而不确定数据由于其不确定的特性，也使得数据元组之间可能存在着这样或那样的关系，并且同一个数据元组既可以拥有属性级的不确定性又可以具备存在级的不确定性，使数据处理起来变得非常复杂。按照这一特点，可以将不确定数据又分为以下两类。2.4.1 元组之间相互独立不确定数据元组之间相互独立的情况是指各数据元组之间没有任何关系，取值和存在都是独立的，不受别的元组影响。这种情况是不确定数据库中最简单的一种，也是最容易处理的一种情况，在产生可能世界实例时，不确定数据元组可以独立的出现在可能世界实例中，不会受到其他元组的影响。2.4.2 元组之间存在一定关系元组之间存在一定关系是指不确定数据元组的属性取值和存在性不是独立的，有可能受到其他元组的属性值或者存在性的约束，使数据元组在处理过程中也要考虑到其他元组的影响，处理起来比较困难。这里引用文献43中的例子说明一下元组之间存在异或关系的情况，如表2.3所示，如果北京和广州两个城市相距很远，那么很容易想到T1和T3这两条记录是不可能同时出现的，其中至少有一条是不准确的，这是由于T1和T3中的车牌号是一模一样的，而时间上只差5分钟，同一辆车不可能在5分钟之内能够从北京跑到广州。也正是由于这一点，说明要么T1是正确的，要么T3是正确的，或者两个都是错误的，所以在处理类似的数据时，这两条记录不可能出现在同一个可能世界实例中。注意表中T1的Pro是0.5，而T3的Pro是0.3，Pr(T1)+Pr(T2)=0.81，这里要说明一下，无论有多少个元组之间存在这样的异或关系，这些元组存在的概率值之和都必须小于等于1。若总和等于1，那么在所有的可能世界实例中必须出现这一组元组中的一个，说明把这一组元组看作一个元组，总的概率值1就是这一个元组的概率值，代表这个元组是确定性存在的。文献44-47把这样相互之间存在异或关系的元组叫做x-tuple，如果一个x-tuple中只有一个元组就叫做Single-Alternative，有多个元组时叫做Multialternative，当然，如果所有的x-tuple中都是只有一个元组，那就变为元组之间相互独立的情况了。而文献43是把这样存在异或关系的一组不确定数据元组看作一个单独的元组，即把一个x-tuple看作一个不可分割的整体，在此基础上定义了U-x-kRanks查询，U-x-kRanks查询是把x-tuple中每一个元组成为Top-k的概率合并起来，得到每个x-tuple成为Top-k查询的概率值，并提出了一种合理高效的算法能在最小的搜索空间内完成查询。表2.3 存在异或关系的数据TupleTimePlateNoLocationSpeedProb.T111:35X-123北京2500.5T211:38Y-245上海2100.9T311:40X-123广州2000.3T411:55W-567重庆1400.7元组之间除了上面说的异或关系外，还有一种包含关系。文献24,25中要处理的数据就具有这样的特点，如图2.1所示：2.1(a)是一张事实表，这张表存储了汽车维修的事件，2.1(b)说明了在图(a)中的位置之间存在的关系，以及不同汽车类型之间的关系。如Truck这一型号的车既包含F150又包含S10，WI这个地方包括了Madison和Dells。之后我们再来看图(a)中的P1和P6这两条记录，除了汽车类型不一样外，别的属性值都是一样的。P1的汽车类型是F150，而P6的汽车型号是Truck，而Truck又包含F150。如果有一个查询是要查找所有在Madison这个地方维修过Truck型号车的总费用，那么必须要把P1这条记录算上才行，同理也得加上P2。这种关系情况也已经有不少人在研究，最终的目的就是要把级别不一致的属性统一起来，使得查询的结果更加准确。图2.1 (a)汽车维修记录表 (b)多维数据表2.5 本章小结本章主要介绍了不确定数据产生的多种原因、概念和特点，然后举例说明了不确定数据的分类情况以及各种情况的研究状况。首先，不确定数据产生的原因主要有客观因素和主观因素两个方面，客观因素是指数据在产生，传输，处理的过程中受到无法改变的原因而变得不准确，而主观因素却恰恰相反，完全是由于人类行为的影响而造成的不准确。然后本章介绍了不确定数据的特点，那就是不确定数据中的任何一个元组在属性的取值上不能够唯一，在客观世界的存在也是不能够确定的，只有在概率为1或为0的时候才能够确定，概率在0到1之间的时候属性取值可以有多个，在客观世界既可能存在也可能不存在，这就是不确定数据的特点，正是因为这一点，在数据的处理和管理中都必须要考虑到这一点，这也是它与传统的确定性数据在处理和管理上的最大区别。最后本章介绍了不确定数据按照其不确定性的不同分为了属性值不确定的数据和存在性不确定性的数据，属性值不确定的数据是指数据元组的一个或者多个属性上的取值不唯一，每一个取值都有一定的概率与之相对应，存在性不确定的数据正是本文要研究的数据，是指数据不一定存在于客观世界中，也有相应的概率来表示其出现的可能性。本章还按照数据元组之间的关系把不确定数据分为两种，一种是元组之间是相互独立，任何一个元组的属性取值和存在性都不受别的元组的约束；另一种是元组之间是有依赖关系的，是相互制约的。但是这几种分类情况是可以同时存在的，在同一个不确定数据库中，既可以有属性级不确定的数据，也可以有存在级不确定的数据，部分元组之间可以是相互独立的，部分元组之间可以是存在各种各样的关系的。57第3章 不确定数据的处理模型及存在的问题第3章 不确定数据的处理模型及存在的问题由于不确定数据对人们的生活和工作产生的影响越来越广泛，人们不得不寻找合适的办法来解决有关不确定数据的一系列这个问题。传统的确定性数据处理技术不能够很好的处理这种含有不确定概率值的数据，所以有不少研究者已经提出了几种针对不同数据结构的不确定数据的处理模型，但应用最广泛的是可能世界模型，其他模型都是在可能世界模型的语义基础上针对不同的数据结构而提出的。由于可能世界模型本身就有一定的问题存在，所以想要很好的解决不确定数据的问题，首先得解决可能世界模型产生大量的可能世界实例的问题。3.1 可能世界模型可能世界模型是目前学术界和工业界最为认可的一种模型，也是最合理的一种模型，其思想就是把不确定数据尤其是存在性不确定数据转化为确定性的数据。这也就导致了可能世界实例的数目随着元组的增加呈现出指数级别的上升，成为一个不容易解决的问题。直观上看，一个可能世界实例就是指在现实世界中可能出现的一种实际情况，由于每个存在性不确定的数据元组都有一个存在性概率值来表示其出现在客观世界的可能性，那么最终产生的每一个可能世界实例也对应一个存在概率值，这个值就是出现在该可能世界实例中的所有元组的概率值的乘积再乘以那些没有出现在该可能世界实例中的元组不出现的概率。考虑下面的例子，如表3.1所示，是一个具有存在级不确定的数据表，并且元组之间是相互独立的关系。这里一共有四条关于汽车的行驶信息记录，比如第三条记录是指在上午10:37，一辆车牌号为Z-341的马自达汽车行驶的速度是80公里每小时，并且这条记录的可信度是0.4。表3.1 汽车行驶信息表IDReading InfoSpeed（10）Prob.110:30, Honda, X-12350.8210:35, Toyota, Y-24560.5310:37, Mazda, Z-34180.4 410:38, Honda, W-54120.4对于表3.1中的这四条记录，一共有四个速度值，分别是8，6，5和2，所以一共会有16种可能世界实例产生，如图3.1所示在每一个可能世界实例中，元组之间是按照速度值从大到小排列的，这样做是为了满足“找到速度最大那条记录”的查询要求。这16个可能世界实例其实就是表3.1中的四条记录的任意一种组合，这任意的一种组合就代表了可能出现的一种实际情况。每个可能世界实例出现的可能性等于存在于该实例中的元组存在的概率值和没出现在该实例中元组不存在的概率值之积，如第一个可能世界实例8，6，5，2的概率值等于0.80.50.40.4=0.064。这是由于表3.1中的所有元组都出现在这个可能实例中了，那这个可能实例的概率值就是所有元组的概率之积。第二个可能世界实例中只有速度为8,6,5的三个元组，也就是ID号为1,2,3的三个，这个可能世界实例的概率值为0.80.50.4(1-0.4)=0.096图3.1 可能世界实例上面的情况只考虑了元组存在性不确定和元组之间是相互独立的情况，是最简单的情况，在之后的关系数据模型中会举例说明元组之间存在一定复杂关系的复杂情况。综上所述，可能世界模型是把所有元组存在不确定性