近几十年来,传统的确定性数据(deterministic data)管理技术得到了迅猛的发展,在国民经济建设中起到了突出作用。在传统数据库的应用中,数据的存在性和精确性均确凿无疑[1]。近年来,随着技术的进步和人们对数据采集和处理技术理解的不断深入,不确定性数据(uncertain data)[8][25][26]得到广泛的重视。数据整合、数据抽取、科学数据管理、多媒体应用以及知识学习等应用都有充斥着非确定性数据。传统的数据管理技术却无法有效管理不确定性数据,这就引发了学术界和工业界对研发新型的不确定性数据管理技术的兴趣。目前,已经国际上已经提出了几种非确定性数据库模型,其中最为典型的是斯坦福大学的ULDBs[6]模型。ULDBs基于可能世界模型,扩展了关系数据库模型,提出了相对统一的处理和描述非确定性数据的标准,其TRIO[7][28]系统也较为成熟。但由于庞大的可能世界实例集合和概率维的存在,目前基于ULDBs的数据查询还是个难点,尤其是结果数据置信度的计算。例如,如果某不确定性数据库含N条元组,各元组独立。当该数据库仅有存在级不确定性,可能世界的数目将达到2N个。如果查询要求访问所有的可能世界时,则这个查询开销将会是一个#P问题[19][24]。本文基于ULDBs模型,提出了一种置信度改进算法,能有效地减少不确定性数据查询的时间。本文首先概述了非确定性数据库的研究的背景和相关研究现状和研究意义,总结了扩展关系数据库系统处理非确定性数据的挑战。然后详细介绍了带世系分析的非确定性数据库模型ULDBs,描述了ULDBs如何表示不确定性数据,介绍了数据世系的概念及其与不确定性数据的结合,并介绍了如何把概率扩展到ULDBs。在分析ULDBs非确定性数据库模型后,本文重点研究了基于ULBDs的数据查询。研究了针对各种关系操作,如何计算其结果数据和数据世系。然后分析了Widom的置信度算法和独立模块求解算法,并分析了其优点和不足。在分析和借鉴的基础上,提出了一个基于深度优先最左遍历的独立模块求解算法,并就时间复杂度对本文算法和Widom的算法进行了比较。经比较发现,本文算法在数据世系中节点数目较多时,有更高的效率。本文的主要研究成果包括：提出了一种基于深度优先最左遍历的独立模块求解算法,将原算法的时间复杂度从O(N*E)降到了O(N*H)(其中M代表世系图中节点的个数,E代表边数,H代表节点的平均祖先节点数目)；针对较为复杂的独立模块,提出了一种基于最小割集的置信度算法,将原算法的复杂度从O(2k)降到了O(S)(其中k为独立模块中基础元组的个数,S为其最小割集的数目,S≤2k),减少了计算量；通过实验并和其他相关工作进行比较,说明本解决方案的实用性。