论文部分内容阅读
随着XML的广泛应用，XML数据呈现爆炸性增长，如何有效的管理XML数据成为一个挑战性问题。查询处理和查询改写技术是数据管理研究中的一个核心问题，通过一些方法将已初始的查询改写为一个效率和资源利用率更优的查询。XML查询改写与传统改写问题不太一样，它提出了新的研究问题和挑战。 现有的XML查询处理技术代表了两个领域的研究，数据库领域和信息检索领域。数据库领域注重开发一些结构化查询的语言和提高结构化查询的效率等。信息检索领域关注对非结构化数据的检索，主要集中对关键词检索的研究，提出了许多技术来改进搜索结果的质量，如查询改写和结果排序等。目前两者有融合的趋势，它们相互借鉴已有的研究成果来改进XML查询的质量。本文的围绕XML数据的查询处理问题展开，分别对结构化查询改写和关键字查询改写进行了深入研究。 “Transform”查询为XQuery/Update中的一种特殊查询，在XML安全视图和访问控制等方面有着重要的应用。“Transform”查询需要先拷贝XML结点，并对拷贝的结点执行更新操作，通常会拷贝和更新大量与查询结果无关的结点。因此如何减少这些无用的拷贝与更新操作是“Transform”查询优化的关键。针对上述分析，本文基于XML代数提出了三种方法对查询进行优化，它们分别是:等价转换，“Lazy”处理策略，以及“Hybrid”策略。 XML关键字查询为用户提供了灵活、友好的查询方式，但是查询结果比较差。本文对已有的XML查询改写进行了分类和分析，提出了一种全新的方法自动地将关键词改写为结构化查询。基本方法是将查询关键词拆分为指向结构的词和指向内容的词，从数据中抽取出指向结构的词的关系图，并将查询改写问题转化为关系图的生成根树为问题。研究了有向图存在生成根树的必要条件、生成根树计数、有向图的改造、带权有向图的最优生成根树和前k个权值最大的生成根树的求解等问题。