云环境下的物化视图机制和高效查询应答的方法与关键技术研究

Implementing indexes and views in massive scale distributed database to support efficient query answering is one of the open research issues in the area of cloud data management. XML is by now the standard for exporting and exchanging data on the web and it is used to address data integration and source heterogeneity issues. In this proposal, we will study methods and key techniques for supporting storage of views and efficient XML query answering in the cloud. Specifically, we will identify answerability conditions for complex XML queries using views and design efficient techniques for maintaining views and for answering and optimizing queries using views in centralized and distributed environments and the cloud. We will design elaborate algorithms that select bitmap views for materialization under different constraints, in the presence and in the absence of query workloads, statically and incrementally, and in query streaming environments. We will implement and experimentally test our new techniques and make analytical and empirical comparison of the developed optimization techniques with existing techniques (mainly index-based ones) in terms of space consumption, query performance and scalability and study of their integration into a query engine. We will develop a system that can efficiently answer XML queries in the cloud. Expected research results include novel techniques, patents and software, etc.

为基于云计算模型的数据管理系统创建视图和索引机制从而实现高效的查询应答是云数据管理的一个开放性研究问题，也是当今学术界研究热点之一。本课题研究云环境下XML数据库的物化视图存储和高效查询应答的方法和关键技术。本课题的研究基于一种新颖的基于位图的视图机制，研究的内容包括物化视图的物理存储机制，视图的可用性/查询可求解性判断标准和算法，视图维护策略和算法，利用物化视图计算和优化XML查询方法，和不同情形下(所有可能的查询工作负载，给定查询工作负载，静态或增量，和动态查询流)物化视图选择方法。验证上述方法和技术的合理性和有效性。与现有的查询优化技术(主要是基于索引的技术)在空间消耗，查询性能，和扩展性等方面展开分析和比较。研究这些新技术与XML查询引擎的集成。开发基于上述新技术的高效处理和优化XML查询的原型系统。在技术创新、专利申请和软件注册等方面取得成果。

创建大数据管理系统的视图和索引机制从而实现高效的查询应答是大数据管理的一个开放性研究问题，也是当今学术界研究热点之一。本课题研究面向大型半结构数据的物化视图存储和查询优化方法和关键技术。我们提出了一种用压缩的位图形式存储物化视图的方法。这种方法不仅能大幅度的降低空间消耗，而且通过将对视图的处理转换为对位图的按位操作，从而大大节省CPU和I/O代价。区别于传统的物化视图方法，我们的方法避免了枚举和计算补充查询。我们设计了一个高效的基于栈结构的算法来寻找查询节点在视图中的覆盖节点，通过计算从视图到查询的同态来确定一个给定的查询节点的覆盖节点集。这种方法避免了枚举所有的从视图到查询的具有视图节点指数数量的同态。基于从视图到查询的同态，我们建立了单个或多个视图来部分或全部解答给定查询的充分必要条件来有效地确定视图可用性，并提高了查询在视图池中的命中率。我们研究了如何利用一种基于堆栈的整体查询处理算法利用物化视图来部分或全部解答给定查询。我们实现了基于压缩位图的物化视图机制并设计了大量实验来验证上述查询优化技术的有效性。 同时， 我们在真实、基准及合成数据集上与现有的查询优化技术在空间消耗，查询性能，和扩展性等方面展开了分析、比较及实验验证。..为了实现基于压缩位图的物化视图在优化查询方面的优势，我们定义和解决了一个新颖的物化视图的配置问题，并给出了物化视图配置的两种解决方案，即二元路径模型与二元树模型配置。我们实现了这两种配置方案。我们在不同数据集上运行了大量的实验验证该方法的有效性。实验结果显示出该方法是支持基于倒排列表框架的查询优化方法的最佳候选者。..对大规模数据库实现视图及索引的自动选择是数据库研究的核心问题。我们提出了用树型结构模板来定义视图类的思想, 定义并解决了一种新颖的物化视图选择问题。区别于传统的针对确定查询负载的视图选择方法，我们的目标是选择一组视图类来回答所有可能的查询。我们证明了该问题是NP-难问题，并且设计了两个启发式贪心算法。我们进行了广泛的实验来验证算法的有效性及性能。实验结果表明我们提出的方法能在合理的时间里给出高质量的视图推荐。.. 本课题在其它与视图相关的查询优化技术，包括共享感知的查询调度方法、重叠数据源的选择方法、数据源查询结果的更新方法、数据流查询优化、XML关键字查询结果聚类等方面也展开了研究并取得了相应的研究成果。