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

Confidence Computation for Queries with Inequality Graph in Probabilistic Databases

作　　者：余萝 覃飙[1] 刘勇[1] 

机构地区：[1]中国人民大学信息学院,北京100872

出　　处：《小型微型计算机系统》2015年第5期996-1001,共6页Journal of Chinese Computer Systems

基　　金：国家自然科学基金项目(61170012)资助;中国人民大学明德青年学者培育项目(10XNJ048)资助;江苏省未来网络创新研究院未来网络前瞻性研究项目资助

摘　　要：在元组独立的概率数据库中根据不等式的结构特性,不等式查询语句被分为三类:路径类型、树类型和图类型,针对现有secondary-storage算法不能很好地处理图类型的查询语句,本文提出了一种Split算法来计算不等式查询语句的置信度,其将图类型的查询语句分解为多个路径类型的查询语句,并分别把这些路径类型查询语句的溯源表达式编译为有序二叉决策图(OBDD),最后将这些OBDD合并起来计算原溯源表达式最终的置信度.Split算法不仅可以处理图类型的查询语句,而且在处理树类型的查询语句时,也能够大大降低溯源表达式的大小,从而提高置信度计算的效率.This paper investigates the problem of confidence computation of conjunctive queries with inequalities over tuple independent probabilistic database. Conjunctive queries with inequalities are categorized into path, tree and graph according to the structure property of inequalities. The existing secondary-storage algorithm falls to compute the confidence of queries with inequality graph. We propose a split algorithm, which splits queries with inequality graph into several queries with inequality paths. Then we compile the lineages of queries with inequality paths into Ordered Binary Decision Diagrams （ OBDDs ） and merge these OBDDs to compute the final confidence. Our algorithm could not only process queries with inequality graphs but also decrease the size of lineages and accelerate the confidence computation of queries with inequality trees or paths.

关 键 词：概率数据库 置信度分析 OBDD 不等式查询语句 

分 类 号：TP311[自动化与计算机技术—计算机软件与理论]