概率数据库查询处理关键技术研究

由于测量精度限制、网络延迟以及采样误差等因素导致不确定数据在现实生活中无处不在，我们用概率数据库来管理这些不确定数据。当概率数据库采用元组关联模型时，我们拟用图模型来表达它们，并用一阶概率图模型来描述其结果元组的推理过程；还要研究查询语句安全的充要条件，并提出生成安全外延执行计划的算法。当概率数据库采用元组独立模型时，本项目拟根据结果元组世系图的特点，从图论提出判断结果元组为只读一次范式的理论，并导出元组概率的推理算法。本项目拟研究查询语句与贝叶斯网络推理方法之间的映射关系，并在此基础上生成优化的安全计划或高效的内涵查询策略。本项目还将研究协同内涵和外延两种基本策略来高效地执行非安全查询语句的技术，并通过索引和物化视图来提高系统的性能。最后，研发一个概率数据库原型系统，对我们提出的理论和算法进行验证和分析。本项目的工作不仅对概率数据库查询处理有直接的意义，而且对其存储管理等方面有理论指导。

数据的不确定性在很多领域都有，比如传感器网络和RFID网络，我们用概率数据库来管理这些不确定数据。本项目研究块分离概论数据库上的安全执行计划，该问题是概论数据库的一个基本问题。我们提出了两种新的数据模型，关联表和扩展的关联表；接着我们提出了一种混合的投影，它的原子操作包括首先执行不相交投影然后执行独立投影在BID表上；此外，我们提出了一种高效的算法来在BID中找到安全的执行计划。本项目还研究了元组独立的概率数据库中不等式查询，这类查询分为路径类型、树类型和图类型，并提出了高效的查询处理策略来计算不等式查询的概率。.经典的数据挖掘算法需要修改和扩充来挖掘不确定数据对象，否则挖掘的精度将由于数据的不确定性而大大降低。我们为不确定的数值属性和字符属性定义了不确定数据模型，在此基础上提出新的EMU算法来聚类不确定数据对象。该算法经过精心设计基于不确定数据对象发现分布式参数以便最大化模型的质量，因此能够正确的区分不同的类。我们的聚类算法能够处理数值和字符数据，在实验中我们采用合成的和真实数据来评估我们算法的高效性和健壮性。.贝叶斯网络能够推导出事件的概率，是典型的不确定推理应用。微分和干预分别是贝叶斯网络和因果网的基本操作，我们揭示了这两种操作的联系，我们首先提出了一个新的表示模型部分干预表（PIT）来编码因果网中对一个结点的多干预。利用PIT，我们引入了联合树算法来求因果网中所有变量的全干预。我们接着发现经典算法只有当微分结点能够到达证据结点时才能够正确计算贝叶斯网络的微分。如果该条件不能满足，经典算法将不能正确计算微分。基于此，我们发现干预的微分语义。.连接查询语句的结果元组在世系的责任问题，我们把一类IQ查询的世系分为路径世系和复合世系。我们首先把路径世系编辑为世系图，然后把世系图转换为矩阵。接着我们把计算路径世系责任的问题归约为最小路径问题，该问题能够把动态规划算法在PTIME时间内求解。本项目进一步证明复合世系的责任能够分解为路径世系的责任求解。因此，本项目的第一个主要结论是IQ查询世系的责任能够在PTIME时间内求解。我们把先前的求解世系责任在等值连接查询推广到不等值连接查询。当把复合世系分解为路径世系后，进行责任计算的数据量降低了超过一个数量级。因此我们的算法能够高效地计算复合世系的责任。最后，本项目提出了一个贪婪算法，它把计算一般世系的责任归约为集合覆盖问题。