一种基于XPath的高效语义缓存机制
An Effective Semantic Cache for Exploiting XPath Query/View Answerability
-
摘要: 1.本文的创新点
本文主要创新点包括:(1)一种基于“分而治之”思想的XPath分解技术,通过对XPath分解不仅能够开发缓存的利用率而且能够提高缓存查找(视图选择)的性能; (2)一种基于数字整除的方法来提高缓存查找的效率,通过素数乘积的整除关系来验证视图是否能回答新查询,从而可以进一步加速缓存查找的性能;(3)一种高效的缓存替换策略,它可以大大提高缓存的命中率;(4)一系列实验表明本文提出的方法比现有算法具有更高的语义缓存的查询能力,更高的命中率,以及高效的缓存查找效率。
2.实现方法
本文实验方式是:1)XPath分解技术:首先找到XPath的主路径,然后基于主路径对XPath进行分解。只有当查询的主路径被视图的主路径包含,该查询才能使用视图进行查询处理。该方法不仅可以提高缓存查找性能而且可以提高缓存的回答能力;2)素数乘积整除技术:首先为XPath每个的节点赋予一个素数,只有查询的所有节点的素数的乘积能够整除视图中所有节点的素数的乘积,该查询才能使用该视图进行查询处理,此方法可以大大提高缓存查找的效率;3)缓存替换策略:为了提高缓存的命中率,本文通过综合考虑视图的访问频率和访问时间来设计缓存的替换方法。该方法总是替换那些最近最少访问的以及历史上访问较少的视图。
3.结论及未来待解决的问题
本文提出的基于XPath路径分解的方法不仅能够提高缓存查找速度,而且能够提高缓存的回答能力。基于数字整除关系的缓存查找方法能够进一步提高视图的查找速度,从而提高缓存的性能。本文提出的缓存替换策略可以改善、提高缓存的命中率,从而可以大大提高语义缓存的性能。下一步工作,我们将研究如何更大力度的开发缓存的利用率,提高缓存的命中率,并且最大程度的发挥缓存的作用。此外,我们可以通过挖掘频繁的XML请求,通过缓存那些频繁的XML查询请求来提高语义缓存的性能。我们还将研究如何设计基于XQuery查询语言(另外一种XML查询处理的语言)的语义缓存机制,从而可以利用缓存来回答新的XQuery查询。
4.实用价值或应用前景
随着网络的发展,XML已经成为了网上数据表示和交换的标准,越来越多的应用已经离不开XML。而如何查询处理XML数据则成为了目前国内外研究的重点。而基于XPath的缓存正好可以提高和改善XML查询处理的性能,因此备受国内外学术界和工业界广泛关注。语义缓存对客户端-服务器端这种架构下有着广泛的应用,他可以通过在客户端进行缓存,从而当用户输入查询时,不用到服务器重新查找,而是通过客户端的缓存结果来回答查询,从而降低了网络的开销以及服务器端得负载。Abstract: Maintaining a semantic cache of materialized XPath views inside or outside the database is a novel, feasible and efficient approach to facilitating XML query processing. However, most of the existing approaches incur the following disadvantages: 1) they cannot discover enough potential cached views sufficiently to effectively answer subsequent queries; or 2) they are inefficient for view selection due to the complexity of XPath expressions. In this paper, we propose SCEND, an effective Semantic Cache based on dEcompositioN and Divisibility, to exploit the XPath query/view answerability. The contributions of this paper include: 1) a novel technique of decomposing complex XPath queries into some much simpler ones, which can facilitate discovering more potential views to answer a new query than the existing methods and thus can adequately exploit the query/view answerability; 2) an efficient view-section method by checking the divisibility between two positive numbers assigned to queries and views; 3) a cache-replacement approach to further enhancing the query/view answerability; 4) an extensive experimental study which demonstrates that our approach achieves higher performance and outperforms the existing state-of-the-art alternative methods significantly.
下载: