基于谓词分类的语义缓存查询裁剪

Query Trimming for Semantic Cache Based on Predicate Classification

为了解决传统查询裁剪在时间和空间上的高复杂性,提出了一种基于谓词分类的语义缓存查询裁剪算法.首先从语义上将谓词分成范围谓词和约束谓词两类,并分别对这两类谓词进行"满足"、"相交"和"包含"的定义;然后基于谓词分类提出了一种新的查询裁剪算法,并对算法的复杂度进行了分析.模拟实验结果表明,所提出的裁剪算法是有效的,特别是在处理查询和缓存相交的情况下,与基于谓词模型的传统串型裁剪算法和基于逻辑规则的裁剪算法相比,文中算法可明显改善查询裁剪效率.

In order to overcome the high complexity of the traditional query-trimming algorithm in time and space domains, a query-trimming algorithm for semantic cache is proposed based on predicate classification. In the proposed algorithm, all predicates are first divided into two different categories, namely restricted predicate and range predicate, which are then defined as semantic satisfaction, semantic intersection and semantic inclusion. Afterwards, a new query-trimming algorithm is presented, with its complexity being also analyzed. The proposed trimming algorithm is finally compared with the traditional serial trimming algorithm based on predicate model and with the trimming algorithm based on logic rules. Simulated results show that the proposed algorithm greatly improves the query-trimming efficiency, especially in the case of intersection between query and cache.