Abstract:

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.

Key words: query trimming, semantics, restricted predication, range predication, semantic cache