XML数据管理

可扩展标记语言(XML)是一种简单、灵活的文本格式,它来源于为大规模电子出版物而设计的SGML(ISO 8879)。随着XML逐渐成为表示和传输网络数据的标准,也出现了许多XML应用。例如:股票交易、新闻订阅、传感器网络等等。XML已经对网络信息的管理和集成产生了非常大的影响。管理半结构化的XML数据也带来了许多挑战。

  • 研究动机
  • XML文档是一种带标签的树型结构,这和关系数据模型是不同的,因此,如何以一种自然的方式管理XML数据是个新的挑战。现有的管理XML数据的方法可以分为两种:一种是利用关系数据库系统储存XML数据;另一种是利用Native XML数据库系统来管理XML数据。Native XML数据库系统能够保持XML数据的树型结构,可以将节点或者子树作为存储单元,因此,Native XML数据库系统受到了研究者广泛的关注。其中具有挑战性的问题有:如何存储XML数据来支持有效的查询、如何更新XML数据、如何构造索引以及对于给定的查询如何找到所有匹配的结果等等。
  • XML数据存储策略
  • 存储是一个数据库系统的基础,也是影响系统效率的最主要因素之一。在传统数据库理论中,使用基于代价的查询优化技术,代价的最主要指标就是IO次数。一个良好和健壮的存储系统,通过有效的聚簇和划分,能够减少大多数查询需要的IO次数,从而提高查询的效率。XML数据是半结构化的,不像关系数据那样是严格的结构化数据,这样就给Native XML数据库中的存储系统带来更大的灵活性,同时,也带来的更大的挑战。恰当的记录划分和聚簇,能够减少IO次数,提高查询效率。
    我们在现有的native XML数据库存储技术的基础上,总结归纳了现有的存储策略,并且在此基础上提出基于文档模式信息的聚簇子树存储策略,并实现了四种存储方法,使得能够根据文档的特征将查询感兴趣的相关数据自动的存储到同一物理存储单元中,同时根据查询需求有选择的将同一类型的XML文档中的结点或者子树存储到一起或者按照文档自身的顺序组织存储,这样的选择机制能够极大的方便上层查询的执行。
    所开发的原型系统OrientStore发表在国际数据库顶级会议VLDB2003。该研究成果被国际和国内会议期刊等引用2次,其中Athena Vakal等人在IEEE Computer Society上的文章“Athena Vakali, Barbara Catania, Anna Maddalena: XML Data Stores: Emerging Practices. IEEE Internet Computing 9(2): 62-69 (2005)”指出我们的方法在一些新的应用中的具有明显的优势The advantages of this approach are evident in several new applications)。

    基于上述研究成果申请一项国家专利(申请号:200410073869.5)。
  • 数据编码方法
  • 大部分XML查询技术都是基于某种对XML树的编码方法。对XML树的编码,是指按照某种规则对XML树的每一个结点分配唯一的编码,目的是通过任意两个结点的编码,能够直接判断两个结点之间是否具有祖先后代关系。最常用的编码方法是区域编码方法(region based numbering scheme)。基于XML编码的结构连接带来查询效率提高的同时,也带来了编码更新的代价问题。降低编码更新代价的一般方法是在编码的时候预留编码空间。问题是如何预留,以及插入新结点的时候,如何分配预留的空间。XML数据可能有模式约束(schema-dependent),也可能没有模式约束(schema-independent)。如果数据没有模式约束,则可以在任意位置插入任意类型的结点;如果模式有模式约束,则要求插入新的子树之后的XML文档仍然满足模式定义。因此,有没有模式约束将会对数据插入产生重大影响,所以,编码空间的预留也应该有所不同。
    我们主要研究区域编码和前缀PBi Tree的更新问题,采用预留编码空间的方法,针对不同特征的XML数据和应用环境提出了一整套预留算法和编码更新算法,用实验研究了编码方法的编码长度,更新特征,预留算法和更新算法的有效性问题。大量的实验表明,这套算法是很有效的,能够大大降低编码的更新代价。使用这些预留算法和编码更新算法,85%以上的数据插入不会引起编码更新。

    该研究成果先后发表在WWWJ2005和软件学报上。先后被国际会议期刊论文引用5次,被认为是研究XML编码更新问题的重要工作。
  • XMl数据索引方法
  • Twig查询是XML查询处理的核心组件。对于给定的一个twig查询,大多数XML索引方法在求解时会将该查询分解为几个子查询分别求解,然后再将每个子查询的结果根据连接条件执行连接操作以得到最终的解。其中连接操作已经被大家公认为最耗费时间的操作,Twig查询的主要缺点是需要执行多次连接操作,这样做需要重复处理大量数据元素和缓存大量无用的中间结果,这将严重影响系统的处理效率。
    为了解决上述传统问题,我们提出了一种基于序列的XML数据索引方法,对于用户提交的查询,系统根据特定的算法将该查询转化为序列,这个序列保持了原查询的结构特性,具有和原树形查询等价的结构特性,根据特定的序列匹配算法,从原文档对应的序列中找与用户查询等价的序列匹配的文档片断。同时进一步研究和论证了树状数据和查询向序列的转化技术以及序列匹配方法的正确性和完整性,提出了基于序列的XML数据索引方法,能够保证查询结果的正确性,同时避免了耗时的结构连接操作,大大提高了查询执行的性能。
    该工作发表在国际数据库顶级会议ICDE2005,其演示系统XSeq发表在国际数据库顶级会议SIGMOD2004。该工作随即被国际数据库顶级会议VLDB2005两篇论文引用,IEEE Internet Computing9(2)对有关XML索引技术作了全面的分析,认为该工作是序列索引的代表性工作,该工作目前被引用16次。Bartley等在其文章[R2-7]中指出我们的方法在索引XML文档的时候采用了完全不同的方法(an entirely different approach to encoding (building) the index from an XML or OEM source document),另外,K.Hima Prasad等在其文章“K.Hima Prasad Ch.Rajesh P.Sreenivasa Kumar: Handling Updates in Sequence Based XML Query Processing. In the Proceeding of International Conference on Management of Data (COMAD 2005), Hyderabad, India, December 20-22, 2005.”中指出我们的工作由于具有整体查询处理的特性而变得越来越重要(Recently sequence based query processing is gaining importance because of its holistic query processing feature)。

    基于上述研究成果申请两项国家专利(分别为200810056098.7 和 200810056100.0 )。
  • 查询代数
  • 作为W3C的推荐标准,XQuery的表达能力比XPath强大很多,同时,XQuery也比XPath复杂很多。XQuery兼有结构化查询语言和过程化编程语言的特点。一方面,XQuery的FLWR子句一定程度上类似于SQL的Select-From-Where子句,是XQuery的最重要的表达式;另一方面,XQuery支持表达式的任意嵌套,支持诸如条件表达式(IF-THEN-ELSE),循环表达式(FOR)和返回值(RETURN)等,还有变量和谓词的作用域问题,这些,都是一门编程语言的重要特征。因为XQuery兼有这两种特点,因此,XQuery的处理方法分为两大类:基于核心语法的处理和基于XML代数的处理。单独使用任一种方法都不能很好地处理XQuery查询。一方面,一次一结点的操作,效率很低,而且很难优化,在关系数据库中,一次一集合的操作被证明效率远高于一次一结点的操作;另一方面,一次一集合的方法又和XQuery过程化编程语言的特点不相符,XQuery是任意嵌套的语言,特别是在结果构造符中,一次一集合的操作有时不可能表达复杂的结果嵌套情况,而必须借用编程语言的线性执行的特点。目前,人们提出了很多XML代数,包括:TAX,Xtasy,TTX,SAL,XAL等。由于XQuery是可以任意嵌套的查询语言。这给代数式处理带来了额外的困难。XQuery更像一个第三代编程语言的代码,而不像SQL那样的结构化查询语言。有时候,由于表达式的任意嵌套,一些操作符必须序列化执行。序列化操作实际上引入了一次一结点的处理思想。现有的XML代数和传统的关系代数都没有这样的操作符,因此不能很好地处理任意嵌套化的XML查询。
    我们提出了结合这两种处理策略的方法,既能有效地表达XQuery查询,又能获得很高的处理效率。同时提出了OrientXA XQuery查询代数。OrientXA代数系统使用一次一集合的方法表达查询,同时,在它的结果构造符中,体现了XQuery查询语言的过程化特点,具有很强的表达能力,能够表达W3C Use Case和XMark数据集的所有查询。同时,我们提出了一种模式信息指导的Pattern树语义优化方法,给出了三个冗余结点判定规则并提出了一种基于直方图计算的多谓词复杂路径选择性代价的计算方法,所设计的二维直方图可正确反映值与位置的关系,把结构的相关性隐含在直方图的位置关系中。为提高选择性计算的效率,提出了一种模式指导的多谓词复杂路径代价估计方法。最后,我们提出了基于结构索引进行过滤以提高查询速度的优化方法,该方法针对某些XML文档索引结构过大所带来的查询效率下降的问题,提出了将结构索引打平并进行有效的组织存储,从而可以快速进行过滤,很好的解决了索引结构过大带来的性能下降问题,有效的提高了查询处理的综合性能。

    该方面的工作发表于国际重要会议WAIM2004、国内主要期刊软件学报和计算机研究与发展。
  • 原型系统OrientX
  • 在深入研究native XML数据库系统各方面技术问题的基础上,设计并实现了自己的Native XML数据库系统OrientX(http://idke.ruc.edu.cn/OrientX/),它包括完整的存储、索引、查询、优化以及访问控制等模块,此外还有一个与XML数据管理密切相关的模式信息管理模块,模式信息的辅助能够极大提高OrientX系统中各个模块的工作效率。OrientX是世界上领先的几个native XML数据库系统之一。目前,该系统已被国际知名的万维网标准组织W3C网站(http://www.w3.org/XML/Query)收录在XQuery Implementation List中,并得到了世界各地五十多个国家和地区的研究者的关注。

    2006年11月19日至22日,申请人应邀参加了在德国举办的“Dagstuhl Seminar on XQuery Implementation Paradigms”。此次研讨会是关于W3C XQuery 查询语言实现技术。所有参加者都是受邀参加,且在本领域研究活跃。过去五年申请人领导的研究小组自主开发了Native XML数据库系统OrientX,在本领域内得到广泛关注。会议主席德国慕尼黑理工大学的Torsten Grust教授在发来的邀请中特别指出“Your native XML database system OrientX is clearly recognized as a highly significant contribution in this research area and the seminar organizers are looking forward to your attendance(你们的Native XML数据库系统OrientX对于本领域的研究工作来说是一个重要贡献,会议组织方希望你的参加)”。
    [Top]        
    Ontology数据管理

    Ontology是对一个特定领域中重要概念的共享的形式化的描述,由于具有明确性和共享性,它可以作为领域内不同主体之间进行交流的语义基础;更进一步的,Ontology可以帮助机器理解文档表达的语义信息。语义网络是Ontology的一个重要应用场景。互联网堪称人类最丰富的信息源,但是持续且快速的信息增长使得维护和访问用户所需的网络信息变得越发困难。语义网络是近年来提出的新型网络的概念,旨在使机器自动完成基于语义的网络信息搜索,为用户提供最大的便利。在语义网络的框架中,Ontology用来描述网络资源的语义,从而使机器具有自动管理网络信息的能力。
    巨大的数据规模是语义网络环境下Ontology数据管理面临的一个突出问题。另外,网络资源的持续增长也导致了语义数据的持续更新。如何有效支持更新是语义网络环境下Ontology数据管理面临的另一个重要问题。

    大部分已有的工作是想通过关系数据库中的方法来解决这些问题。但是,关系数据库并不是根据Ontology数据的特点而设计的。Ontology复杂的图型模型和关系数据简单的扁平结构有很大的区别。基于Ontology数据管理的关系数据库需要将Ontology图划分为简单的关系,并且将基于图的查询转换成关系表上的一些连接操作。两种模型之间的错配限制了基于关系数据库的方法在管理大规模Ontology数据上的应用。另外,基于关系数据库的方法总是预算隐含的推理数据并且在存储使物化它们。尽管这种方法能够保证执行效率,但是增加了大量的更新代价。更新外在数据时,物化数据的维护代价非常大。事实上,大部分已有的Ontology管理系统不能有效地支持更新。

    为了有效地管理大量的Ontology数据,文献[6]提出了一个新的存储方法,它是根据Ontology数据的特性,设计了native的存储结构,突破了关系数据模型的限制。最显著的特点是它使用XML数据模型,采用树型结构来存储Ontology中的类和属性。树型结构能够保留Ontology数据中原有的层次,所以,不需要物化隐含的推理数据,这样可以减少更新的代价。这样的存储结构具有很好的更新能力,在Ontology数据变化时能够很方便的保证数据的一致性,同时保持很小的更新代价。基于这种新的存储方法,文献[6]也提出了相应的查询处理方法来支持SPARQL查询。除了查询处理,推论能力Ontology数据管理中很重要的一方面。文献[1]研究了这方面的问题并提出了初始的推理算法和增量的推理算法来确保推理处理的完整性和效率。

    OrientX是一个Native的XML数据管理系统,OrientX/Ontology是基于OrientX的一个扩展的版本,它可以看成是专门为处理Ontology数据的特别版本。它实现了新的存储方法并且有查询和推理的能力,这对于研究人员和开发人员都有很重要的意义。现在,系统能够加载超过200M的文档,未来的工作是改进查询引擎和支持更大量的数据。
    [Top]        
    XML关键字查询
    查询处理时使用特殊的查询语言对于想从XML文档中获得一些数据的用户来说有很强的限制性,因此,XML关键字查询是一个重要的问题。未来我们将试图在OrientX中支持有效的关键字查询。
    [Top]        
    获资助课题
    • 2006-2007 中国-希腊政府间科技合作项目"基于context的XML数据管理研究"
      中方项目负责人
    • 2005 IBM中国研究中心大学联合研究项目"Ontology based Data Management"
    • 2004-2007 教育部新世纪优秀人才支持计划"XML数据管理关键技术研究"
    [Top]        
    论文著作
    • 1. 周军锋,孟小峰,Ling Tok Wang: 一种高效处理不完全结构约束的Twig查询方法,已录用,中国科学E辑:信息科学
    • 2. J. Zhu, W. Wang, X. Meng: Efficient Processing of Complex XML Twig Query. In Proceedings of 9th International? Conference on Web-Age Information Management (WAIM 2008), Zhangjajie, China
    • 3. 黄静,徐俊劲, 周军锋, 孟小峰. MLCEA: 一种基于实体的XML关键字查询语义,计算机研究与发展增刊,2008.10(第二十五届中国数据库学术会议, 桂林)
    • 4. 朱金清,王伟,周军锋,孟小峰:基于相关性语义的高效XML Twig查询处理方法.计算机研究与发展增刊,2008.10(第二十五届中国数据库学术会议, 桂林)
    • 5. 张新, 孟小峰, 朱金清, 王伟, 黄静: OrientStore+: 一种支持高效更新的Native XML存储方法. 计算机研究与发展, 卷44(增刊): 368-373, 2007.10(第二十四届中国数据库学术会议, 海口, 优秀论文)
    • 6. 周军锋, 孟小峰, 张新, 黄静: XML数据流上基于关键字的多查询处理. 计算机研究与发展, 卷44(增刊): 392-397, 2007.10(第二十四届中国数据库学术会议, 海口)
    • 7. J. Zhou, M. Xie, X. Meng: TwigStack+: Holistic Twig Join Pruning Using Extended Solution Extension. Wuhan University Journal of Natural Sciences, Vol. 12, No. 5: 855-860, 2007.9 (4th Web Information System and Application(WISA2007), Beijing, Best Paper Award)
    • 8. 周军锋, 孟小峰, 蒋瑜,谢敏:F-Index:一种加速Twig查询处理的扁平结构索引,软件学报,卷18(6):1429-1442,2007,6.
    • 9. Xiaofeng Meng, Xiaofeng Wang, Min Xie and et al: OrientX: An Integrated, Schema-Based Native XML Database System. Wuhan University Journal of Natural Sciences,11(5):1192-1196, Nov., 2006.(The Third Web Information System and Application(WISA2006), Nanjing, Nov 3-5, 2006.)
    • 10. 王小锋,张新,谢敏,孟小峰,周军锋,XML数据流上的关键字查询. 计算机研究与发展,卷43(增刊):484-489,2006. (第23届中国数据库学术会议,广州.)
    • 11. 谢敏,王小锋,张新,孟小峰,周军锋,XML数据流上的有序XPath查询处理,计算机研究与发展,卷43(增刊):464-470,2006,11. (第23届中国数据库学术会议,广州.)
    • 12. X. Wang, J. Ou, X. Meng, and Y. Chen: Abox Inference for Large Scale OWL-Lite Data. To appear in Proceedings of The 2th International Conference on Semantics, Knowledge, and Grids(SKG2006), Guilin, China, Oct. 31 - Nov. 3, 2006. (Regular paper 18%)
    • 13. 谢敏,王小锋,张新,孟小峰,周军锋,XML数据流上的有序XPath查询处理,计算机研究与发展,卷43(增刊):464-470,2006,11. (第23届中国数据库学术会议,广州.)
    • 14. 王小锋,张新,谢敏,孟小峰,周军锋,XML数据流上的关键字查询. 计算机研究与发展,卷43(增刊):484-489,2006. (第23届中国数据库学术会议,广州.)
    • 15. X. Meng, X.Wang , M. Xie and et al: OrientX: An Integrated, Schema-Based Native XML Database System. Wuhan University Journal of Natural Sciences,11(5):1192-1196, Nov., 2006.(The Third Web Information System and Application(WISA2006), Nanjing, Nov 3-5, 2006.)
    • 16. 孟小峰, 王 宇, 王小锋, XML查询优化研究, 软件学报, 卷17(10):2069-2086, Oct. 2006
    • 17. Y. Chen, J. Ou, Y. Jiang, X. Meng: HStar-a Semantic Repository for Large Scale OWL Documents. In Proceedings of the First Asian Semantic Web Conference (ASWC2006), page 415-428, Beijing, China, September 3-7, 2006. Lecture Notes in Computer Science 4185, Springer. (Full Paper 36/208=18%)
    • 18. 王宇,孟小峰,王珊,基于直方图的XPath含值谓词路径选择性代价估计,计算机研究与发展,卷43(2):288-294, 2006,2
    • 19. 王 静, 孟小峰, 王 宇, 王 珊, 以目标节点为导向的XML路径查询处理,软件学报,卷16(5):827-837,2005.5
    • 20. 罗道锋, 孟小峰, 蒋瑜,XML数据扩展前序编码的更新方法, 软件学报,卷16(5):810-818,2005
    • 21. H.Wang, X. Meng: On the Sequencing of Tree Structures for XML Indexing. In Processdings of the 21st International Conference on Data Engineering (ICDE 2005), pages 372-373, Tokyo, Japan, April 2005.
    • 22. J. X. Yu, D. Luo, X. Meng, H. Lu: Dynamically Updating XML Data: Numbering Scheme Revisited, World Wide Web, Vol 8( 1):5-26, March, 2005.
    • 23. 孟小峰,罗道锋,蒋瑜,王宇,OreintXA:一种有效的XQuery查询代数,软件学报,卷15(11),1648-1660,2004,11
    • 24. X. Meng, D. Luo, J. Ou: Extended Role Based Access Control Method for XML Documents. Wuhan University Journal of Natural Science, Vol.9(5):740-744, Sept., 2004.
    • 25. 陆世潮,孟小峰,林灿,王宇,OrientX中XQuery的导航式实现, 计算机研究与发展, 卷41(10):1815-1822, 2004,10
    • 26. 王宇,孟小峰,王珊,基于模式的Pattern Tree语义优化, 计算机研究与发展, 卷41(增刊):355-362, 2004,10
    • 27. 欧建波,孟小峰,RSBAC:一种基于角色-模式关联的XML数据访问控制方法, 计算机研究与发展, 卷41(增刊):363-369, 2004,10
    • 28. Y. Wang, H. Wang, X. Meng, S. Wang: Estimating the Selectivity of XML Path Expression with predicates by Histograms. In proceedings of the 5th International Conference Web-Age Information Management(WAIM 2004), pages 409-418, Dalian, China, July 15-17, 2004. Lecture Notes in Computer Science 3129 Springer 2004.
    • 29. 王静,孟小峰,王珊,基于区域划分的XML结构连接,软件学报,卷15(5):720-729 ,2004,5.
    • 30. X. Meng, Y. Jiang, Y. Chen, H. Wang: XSeq: An Index Infrastructure for Tree Pattern (Demo). In Proceedings of the ACM SIGMOD International Conference on Management of Data (SIGMOD 2004), pages941-942, Paris, France, June 13-18, 2004.
    • 31. D. Luo, T. Chen, T. W. Ling, X. Meng: On View Transformation Support for a Native XML Database. In Proceedings of the 9th International Conference on Database Systems for Advances Applications(DASFAA 2004), pages 226-231, Jeju Island, Korea, March 17-19, 2004. Lecture Notes in Computer Science 2973, Springer.
    • 32. 孟小峰等,OrientX: 一个Native XML数据库系统的实现策略,第20届全国数据库学术会议,计算机科学,卷30(10),2003,10.
    • 33. 罗道峰,孟小峰,蒋喻,XML数据扩展前序编码的更新方法,第20届全国数据库学术会议,计算机科学,卷30(10),2003,10。NDBC2003优秀论文
    • 34. 王静,孟小峰,王珊,以目标节点为导向的XML路径查询处理,第20届全国数据库学术会议,计算机科学,卷30(10),2003,10。NDBC2003优秀论文
    • 35. 王宇, 孟小峰, 王珊, OrientX中的统计信息收集方法研究,第20届全国数据库学术会议,计算机科学,卷30(10),2003,10.
    • 36. X. Meng, D. Luo, M.L. Lee, J. An: OrientStore: A Schema Based Native XML Storage System. (Demo).In Proceedings of 29th International Conference on Very Large Data Bases(VLDB2003), pages 1057~1060, Berlin, Germany, September 9-12, 2003.
    • 37. J. Wang, X. Meng, S. Wang: Integrating Path Index with Value Index for XML Data. In Proceedings of the Fifth Asia Pacific Web Conference(APWeb2003), pages 95-100, Xi'an China, 27-29 September 2003. LNCS 2642.
    • 38. 王静,孟小峰,王珊,SUPEX:一种基于模式的XML路径索引,NDBC2002,计算机科学,卷29(8):35-38,2002,8.
    • 39. 王宇,孟小峰,王珊, OrientX中的复杂路径表达式求解,NDBC2002,计算机科学,卷29(8):39-42,2002,8.
    [Top]        
    Maintained by Zhongyuan Wang() Copyright © 2007-2009 WAMDM, All rights reserved