论文部分内容阅读
随着XML(eXtendedMarkupLanguage,扩展标记语言)技术的飞速发展,越来越多的数据使用XML进行表示,XML已经逐渐成为Web上数据表示和交换的标准。XML数据是一种特殊的半结构化数据,且其查询也不同于传统关系数据库的SQL语句,这为XML数据管理带来新的研究问题。本文以XML数据管理技术为研究对象,研究XML数据管理中的关键技术,在XML数据的数据模型、XML数据的查询语言、XML数据的存储结构、XML数据查询处理及优化技术方面取得了一系列研究成果。在XML数据的数据模型方面,提出了一种基于映射的XML数据库的数据模型。该模型能够充分表达XML数据库的复杂数据结构和语义,并支持以路径表达式为核心的查询代数操作。优于其他数据模型,该模型给出了XML数据模型的精确定义,同时定义了模式维护和数据维护操作。在XML数据的查询语言方面,提出了一种XML数据库的查询语言X-SQL。X-SQL具有类似于SQL(StructureQueryLanguage,结构化查询语言)语言的Select-From-Path-Where结构,使用方便,具有路径表达式查询能力和同时从多个数据源选取数据的能力,支持数据更新操作和查询结果的语义捕述。
在XML数据存储结构方面,设计并实现了基于模式划分的ASRX存储结构、以及适应于TwigJoin方法的ERCX存储结构。理论分析和实验结果表明,这些存储结构能够有效地支持各种XML数据维护操作。在XML数据的查询处理及优化方面,提出了三种XML数据查询处理方法:基于ASRX存储结构的路径表达式查询处理方法、基于过滤的XML数据查询处理算法和基于ERCX存储结构的查询处理算法。(1).基于ASRX存储结构的查询处理方法利用自动机匹配求解查询计划,并根据数据的划分信息扫描少量的数据块,从而降低了算法的I/O代价。本文将异步迭代查询处理技术应用于基于ASRX的查询处理,在查询计划的执行过程中不同层次的结点以流水线方式运行,并行完成查询的处理,提高了查询处理的效率。(2).本文还提出了三种基于过滤的查询处理方法BFX-Filter、CX-Filter和SX-Filter。这三种基于过滤的算法可以大大降低元素扫描数日,使得参加查询处理的元素结点数日大大降低。但由于采用了适合顺序扫描的索引结构,使得这三种方法运行时间开销比较大。为此,我们研究了基于ERCX存储结构的查询处理方法。(3).利用结点的ERC编码,数据在存储时被进行划分。查询处理时,只扫描对查询处理结果可能有贡献的结点。实验结果表明,基于ERCX存储结构的HTwigJoin查询处理算法无论在扫描的结点数日、磁盘I/O数日还是运行时间上都优于目前的其它XML查询处理方法。本文还给出HTwigJoin算法的优化策略:基于ERC编码的查询最小化方法。理论分析表明,该方法可以有效提高HTwigJoin算法的效率。
基于以上研究的结果,我们实现了一个XML数据库原型系统,用于验证所提出的理论和方法的正确性,同时为进一步深入研究打下一个基础。该系统已经用于分布式信息集成与共享系统。