众包环境下多谓词查询优化

作者：冯剑红; 胡卉芪; 翁学平; 冯建华

来源：计算机工程与应用, 2016, 52(02): 7-13.

• 众包选择查询
• 采样
• 选择性

近年来,众包查询优化得到了数据库领域的广泛关注。主要研究了众包多谓词选择查询问题——借助于人力找到满足多谓词查询条件的对象。一种简单的方法是枚举数据集中的对象,对于每个对象判断是否满足每条谓词。它产生的代价是|R|·n,其中|R|为数据集中对象的数量,n为谓词的数量。很显然,当处理大数据集或者查询包含较多谓词的时候,简单方法的代价是非常昂贵的。由于不同的谓词具有不同的选择性,如果首先验证高选择性的谓词,那么在验证剩余谓词的时候,就可以避免验证不满足高选择性谓词的对象。因此,采用一个好的谓词顺序实现众包选择查询可以显著减少人工代价。然而,实际中很难获得最佳的谓词序列。针对该问题,提出了一种基于采样的框架来获得高质量的查询序列。为了控制查询序列生成的成本,设计了基于随机序列的最优选择方法,该方法通过随机选择序列获得最终的谓词顺序。由于基于随机序列的选择方法可能产生较大的代价,为了减少开销,提出了一种基于过滤的序列选择方法。通过在众包平台上使用真实数据集评测了提出的方法,实验结果表明,该方法能够显著减少查询序列生成的代价,同时获得高质量的查询序列。

• 单位
  清华大学