概率数据库中图类型的不等式查询语句的置信度计

摘要 在元组独立的概率数据库中根据不等式的结构特性,不等式查询语句被分为三类：路径类型、树类型和图类型,针对现有secondary-storage算法不能很好地处理图类型的查询语句,本文提出了一种Split算法来计算不等式查询语句的置信度,其将图类型的查询语句分解为多个路径类型的查询语句,并分别把这些路径类型查询语句的溯源表达式编译为有序二叉决策图(OBDD),最后将这些OBDD合并起来计算原溯源表达式最终的置信度.Split算法不仅可以处理图类型的查询语句,而且在处理树类型的查询语句时,也能够大大降低溯源表达式的大小,从而提高置信度计算的效率