OrientX3.0及其改进之处 XML小组

大纲 OrientX3.0的体系结构 OrientX3.0的主要特征 OrientX3.0的查询处理问题【系统的效率】 基于代数引擎的XQuery/Update实现问题 OrientX3.0需要改进地方的总结

体系结构 OrientX3.0的体系结构图

大纲 OrientX3.0的体系结构 OrientX3.0的主要特征 OrientX3.0的查询处理问题【系统的效率】 基于代数引擎的XQuery/Update实现问题 OrientX3.0需要改进地方的总结

OrientX V3.0的新特征 √ √ New architecture Support W3C XQuery/Update A set of programming API Usable index management Visual tools Application √ √ √

大纲 OrientX3.0的体系结构 OrientX3.0的主要特征 OrientX3.0的查询处理问题【系统的效率】 基于代数引擎的XQuery/Update实现问题 OrientX3.0需要改进地方的总结

查询处理策略 导航查询处理 (OrientX2.0) 代数查询处理 (OrientX2.5, OrientX3.0)

基于导航的查询处理 例子 找到价格最低的书 Element Constructor Path Expression Attribute Constructor FLWR Expression Conditional Expression Built-in-Function

导航处理的操作符 目前有13中操作符: Step EleConstructor CondTreeNode AttrConstructor Path ForVarBind LetVarBind FLWR EleConstructor AttrConstructor BuiltInFun IfThenElse Quanlify SetOpt SortBy

处理XQuery的流程 Parser and Translator optimizer Evaluator Engine XQuery Query Parser and Translator Initial Query plan optimizer optimized Query plan Evaluator Engine

查询计划示例

查询计划的执行示例 文档 查询计划 $doc bib book book book title year 。。。 year title publisher price publisher price 查询计划

查询计划的执行示例 文档 查询计划 $doc $t bib book book book title year 。。。 year title publisher price publisher price 查询计划

查询计划的执行示例 文档 查询计划 $doc $t $p bib book book book title year 。。。 year publisher price $t publisher price 查询计划

查询计划的执行示例 文档 查询计划 $doc $t $p minprice price TCP/IP Illustrated 65.95 bib $doc book 文档 book book title year 。。。 year title publisher price $t $p publisher price minprice 查询计划 price TCP/IP Illustrated 65.95

查询计划的执行示例 文档 查询计划 $doc $t $p minprice repeat price TCP/IP Illustrated bib $doc book 文档 book book title year 。。。 year title publisher price $t $p publisher price minprice 查询计划 repeat price TCP/IP Illustrated 65.95

查询计划的执行示例 文档 查询计划 $doc results minprice minprice … … price price 65.95 bib $doc book 文档 book book title year 。。。 year title publisher price publisher price results 查询计划 minprice minprice … … price price 65.95 70.05

导航查询引擎小结 优点 缺点 简单，直接，而且对简单查询非常有效 符合XQuery的特点： 对复杂的查询需要遍历文档多遍 过程化查询语言 任意的嵌套 缺点 对复杂的查询需要遍历文档多遍 访问了非常多的无用结点 不利于查询优化

代数查询引擎-OrientXA 一次一集合的查询处理策略 XQuery处理的问题 数据抽取操作 结果构造操作 数据处理操作 选择 投影 结构构造 数据处理操作 连接 消除重复 分组

Q1：一个XQuery例子 <bib> { for $b in doc("bib.xml")/bib/book let $a := $b/author where $b//publisher/text() = "Addison-Wesley" and $b/@year > 1991 return <book year="{ $b/@year }"> { $b/author} </book> } </bib>

导航处理 <bib> {for $b in doc("bib.xml")/bib/book let $a := $b/author where $b//publisher/text() = "Addison-Wesley" and $b/@year > 1991 return <book year="{ $b/@year }"> { $b/author} </book>} </bib> construct a <bib> for $bib in doc (“bib.xml”)/bib do for $b in $bib/book do let $a := $b/author for $publisher in $b//publisher do if $publisher/text() = "Addison-Wesley" then for $year in $b/@year do if $year > 1991 then construct a <book> under <bib> construct a attribute year for <book> with value $year append $author’s content under <book> end-if end-for //$year end-for //$publisher end-for //$b end-for //$bib

OrientXA—关于Pattern Tree 观察： XQuery一个变量绑定对应一个XPath Pattern Tree标识和抽取查询感兴趣的结点(√) Pattern Tree实际上是XPath的树状表示(√) 类比关系(?)： Pattern Tree vs. 表定义 Instance Tree vs. 元组 Instance Tree集合 vs. 表

Q1对应的Pattern Tree和Algebra Tree Source pattern tree 数据抽取的结果 Construct pattern tree 结点绑定 拷贝绑定 Predicates 灵活的代数处理 <bib> { for $b in doc("bib.xml")/bib/book let $a := $b/author where $b//publisher/text() = "Addison-Wesley" and $b/@year > 1991 return <book year="{ $b/@year }"> { $b/author} </book> } </bib> SPT CPT 强结点绑定 弱结点绑定 序列绑定或序列构造 父子边 祖先后代边 元素属性边 图例： p: 绑定所有后代结点 n: 新建结点 c: 拷贝结点

问题1—数据抽取效率 数据抽取的方法[1]有： Navigation：对文档树进行遍历，找到满足pattern tree 的实例树；效率低下。 Structure Join：利用对XML 数据的编码和Tag Index，快速地找到满足祖先后代关系的结点。 Holistic Twig Join：整体求解 OrientX采用策略 [1] 孟小峰，罗道锋，蒋瑜，王宇，OreintXA:一种有效的XQuery查询代数，软件学报，卷15（11），1648-1660，2004，11

问题1 — V3.0测试报告 查询效率低

数据抽取的效率很大程度上决定了代数系统的效率 问题1分析 <bib> {for $b in doc("bib.xml")/bib/book let $a := $b/author where $b//publisher/text() = "Addison-Wesley" and $b/@year > 1991 return <book year="{ $b/@year }"> { $b/author} </book>} </bib> 结果构造： 内存中的中间结果 结果构造： 内存中的中间结果 数据抽取： 访问磁盘的操作 数据抽取的效率很大程度上决定了代数系统的效率

问题1分析 (2) Navigation处理尚未利用任何索引 <bib> {for $b in doc("bib.xml")/bib/book let $a := $b/author where $b//publisher/text() = "Addison-Wesley" and $b/@year > 1991 return <book year="{ $b/@year }"> { $b/author} </book>} </bib>

问题1的解决办法 物理实现采用Twig查询处理方法 建立索引 利用TwigStack查询处理方法 Tag Index Path Index Sequence Index … 利用TwigStack查询处理方法

问题1的解决办法(2) 索引建立 查询处理 在DEB存储的文档导入时创建索引 代码修改集中在DEB方式的四个SAX接口中 startDocument, endDocument startElement, endElement 查询处理 代数操作的流水线操作 TwigStack操作的输出为Sequence (满足一次一集合操作) 数据抽取操作 添加CTwigPatternMatching类

大纲 OrientX3.0的体系结构 OrientX3.0的主要特征 OrientX3.0的查询处理问题【系统的效率】 基于代数引擎的XQuery/Update实现问题 OrientX3.0需要改进地方的总结

XQuery/Update XQuery1.1包括 XQuery/Update XPath 2.0 Full-Text Search

XQuery/Update (2) Insert, Delete, Replace, Rename, Transform表达式 Insert <price>50</price> after /book/author Delete /book[year = 1994]/author

XQuery/Update (3) Rename(修改结点名字), Replace(替换结点或值) Transform查询 copy $a := //book modify delete $a/author return $a 执行前 执行后 查询结果

Transform查询的应用 修改查询结果 查询: book的信息，但不返回 price信息 安全视图 更新虚拟视图 copy $a := //book modify delete $a/price return $a 访问控制：　 用户A不能访问author 为”Rose” 的book结点的price 用户A提交查询: //book 合成Transform查询: copy $a := //book modify delete $a[author = “Rose”]/price return $a

XQuery代数处理 类似关系代数一样,提出了一系列的操作符. FOR $b in //book/price Construct $2 FOR $b in //book/price FOR $y in //book/year WHERE $b/price<50 and $y > 1990 RETURN $b Filter $2 < 50 & $3 > 1990 Select

XQuery/Update代数处理 ? 现有的XML代数能否表达XQuery/Update? where $nb/title = “C++” copy $cb := //book modify delete $cb/price return { let $nb := $cb where $nb/title = “C++” return $nb } Construct $nb Filter $nb/title = “C++” ? Construct $nb 扩展现有XML代数(基于OrientXA):提出新操作符: Copy (拷贝) Insert (插入) Delete (删除) Replace (替换) Rename (重命名) Filter $nb/title = “C++” Delete($2) Copy $1 Select book [$1]

问题2 如何实现Transform查询？ 查询编译 Lex、Yacc 查询处理 修改XML代数规则 添加Transform操作符

问题2分析 Transform查询语句分析 Copy Modify FLWR语句 Insert Replace Delete copy $cb := //book modify delete $cb/price return { let $nb := $cb where $nb/title = “C++” return $nb }

问题2分析 (2) 代数操作符的添加 Copy Modify？ 几个操作符的组合？

大纲 OrientX3.0的体系结构 OrientX3.0的主要特征 OrientX3.0的查询处理问题【系统的效率】 基于代数引擎的XQuery/Update实现问题 OrientX3.0需要改进地方的总结

需要改进的地方总结 尚未完全支持XQuery/Update 代数引擎中的数据抽取效率低 查询编译解析 基于代数的查询处理引擎 存储 查询 Lex/Yacc的修改 基于代数的查询处理引擎 代数操作符的添加 代数引擎中的数据抽取效率低 存储 在数据导入(DEB方式)时建立索引 查询 执行的物理操作采用Twig查询匹配方法 查询结构的重构问题

Thanks^_^ Q & A