基于相关性语义的高效XML Twig查询处理方法 朱金清, 王伟, 周军锋, 孟小峰 中国人民大学WAMDM实验室 http://idke.ruc.edu.cn

大纲 背景 动机 基于相关性语义的Twig查询处理方法rTwigStack 实验分析 总结

背景 XML XML的应用 互联网数据的表示和交换的标准 可以表示结构化和半结构化的数据 政府数据数据交换 各业务部门易于理解 跨平台、多种数据源 国税 工商 国土 公安

背景(2) XML的应用 电子病例数据(EMR) … 性别 民族 籍贯 诱因 症状 部位 形状 定义 大小 时间 机能 婚姻状况 职业技能 XML pieces 检查 活动 损伤 处置 性质 方式 程度 修饰 家庭成员 一般表述 生理指标 生理指征 … XML structure <性别> <value>男</value> <value>女</value> </性别> <籍贯> <value>北京</value> <value>上海</value> <value> … </value> </籍贯> <诱因> <value>活动后</value> <value>体检时</value> <value> … </value> </诱因> <症状 t=“Dict”> <value>气促</value> <value>疼痛</value> <value> … </value> </症状> <部位 t=“Dict”> <value>头部</value> <value>胸部</value> <value> … </value> </部位> <检查 t=“Dict”> <value id=“n”>常规</value> <value id=“m”>生化</value> <value> … </value> </检查> <民族> <value>汉</value> <value>蒙</value> <value>…</value> </民族> <婚姻> <value>已婚</value> <value>未婚</value> <value> … </value> </婚姻> <时间> <format>yyyy-mm-dd</format> <format>yyyy年mm月dd日</format> <format unit=“天” max=“7” min=“1”> </format> <format unit=“小时” max=“24” min=“1”> </format> </时间> <指标 t=“Dict”> <value id=“n” n=“RBC” cn=“红血球” unit=“/L”></value> <value id=“m” n=“RBC” cn=“红血球” unit=“/L”></value> <value> … </value> </指标>

背景(3) 越来越多的数据采用XML来表示和传输 随之而来的问题： 如何高效查询XML数据？？

2) 必须学会复杂的查询语言，如XQuery等 背景(4) 结构化查询方法 XPath XQuery … 1) 必须掌握文档的结构 2) 必须学会复杂的查询语言，如XQuery等

大纲 背景 动机 基于相关性语义的Twig查询处理方法rTwigStack 实验分析 总结

XML查询存在的挑战性 XML文档结构的复杂性 信息的对称性和文档组织结构的不对称性 XML文档结构的不断演变性

返回不相关的元素(Intel生的产Chip) 动机 Pansisa公司 的购买记录： 在这种情况下，如何获取想要的数据？ 必须了解详细的Schema 查询Dell公司卖的计算机部件: Q1： S[N=‘dell’]/IS/I Q2： S[N=‘dell’]//I 返回不相关的元素(Intel生的产Chip)

一点观察 XML文档中关系组织的复杂性 实际上，复杂性只是对应了语义的简单性 元素S在I的祖先结点，也可以在I的后代结点 实际上，复杂性只是对应了语义的简单性 总之，S和I是相关的（卖、卖家等） 所以，通过定义简单的语义来避免数据的复杂性，即相关性(related)语义

动机 扩展XPath的语法使之支持Related轴(“~>”) 扩展的好处 用户了解文档结构，用精确XPath定位 [26] RelativePathExpr ::= StepExpr ( ("/" | "//" | "~>" ) StepExpr)* [27] StepExpr ::= FilterExpr | AxisStep [28] AxisStep ::= (ReverseStep | ForwardStep | RelatedStep) PredicateList [n1] RelatedStep ::= RelatedAxis NodeTest [n2] RelatedAxis ::= "Related" "::"

大纲 背景 动机 基于相关性语义的Twig查询处理方法rTwigStack 实验分析 总结

相关性(related)语义 related轴(“~>”) 返回一系列数据元素,这些数据元素是当前context节点的最邻近的后代或者祖先. S~>I:返回红色的元素I 对两个文档（内容相同但组织形式不同）的返回结果一样

相关性语义(2) 同样，查找Dell公司卖的计算机部件： 查询Q：Intel生产的Chip不作为结果返回。

含related轴的整体匹配方法难点 related轴的对称性 related轴与A-D或P-C轴的不可相互表示 u~v可能对应文档中的u//v, u/v , v//u , v/u中的一种或几种，如： related轴与A-D或P-C轴的不可相互表示

rTwigStack 优点： 一次扫描即可得到所有的结果 支持related轴的扩展XPath查询 可以移植到XQuery中以增强XQuery的功能 同时兼容包含PC、AD边的Twig查询处理

大纲 背景 动机 基于相关性语义的Twig查询处理方法rTwigStack 实验分析 总结

实验分析 实验设置： 度量指标： 三种方法：TwigStack(TS), rTwigStack和rTwigStack+ 1~200M的不同大小XMark文档 6个查询 3个含related查询 3个不含related查询数据集： 度量指标： (1) 运行时间 (2) 扫描的元素数量

与TS相比,rTS在处理不包含related轴时仍具有很高的效率 运行时间对比 rTS 和rTS+所用时间少于TS 与TS相比,rTS在处理不包含related轴时仍具有很高的效率

扫描元素数量、扩展性 rTS 和rTS+扫描的元素数量少于TS 算法具有很好的可扩展性

大纲 背景 动机 基于相关性语义的Twig查询处理方法rTwigStack 实验分析 总结

总结和下一步工作 提出了一种新的related查询语义 提出了一种高效查询处理算法rTwigStack和基于DTD提出一种优化算法rTwigStack+ 实验表明,本文提出的算法不但可以高效处理包含related轴的查询,而且可以高效处理不包含related轴的查询. 下一步将考虑在XML图上的related语义和求解

谢谢~ Q&A