OrientX3.0及其改进之处

1、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 XQuer

2、y/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 ConstructorPath ExpressionF

3、LWR ExpressionConditional ExpressionBuilt-in-FunctionAttribute Constructor1.Step2.CondTreeNode3.Path4.ForVarBind5.LetVarBind6.FLWR7. EleConstructor8. AttrConstructor9. BuiltInFun10. IfThenElse11. Quanlify12. SetOpt13. SortBy目前有目前有13中操作符中操作符: 导航处理的操作符处理处理XQuery的流程的流程Parser and TranslatoroptimizerEval

4、uator EngineXQuery QueryInitial Query planoptimized Query plan查询计划示例查询计划示例bibbooktitlepublisherpriceyeartitlebookbookpublisherpriceyear。查询计划查询计划$doc查询计划的执行示例查询计划的执行示例文档文档bibbooktitlepublisherpriceyeartitlebookbookpublisherpriceyear。$doc$t查询计划的执行示例查询计划的执行示例文档文档查询计划查询计划bibbooktitlepublisherpriceyearti

5、tlebookbookpublisherpriceyear。$doc$t$p查询计划的执行示例查询计划的执行示例文档文档查询计划查询计划bibbooktitlepublisherpriceyeartitlebookbookpublisherpriceyear。$doc$t$pprice65.95TCP/IPIllustrated minprice查询计划的执行示例查询计划的执行示例文档文档查询计划查询计划bibbooktitlepublisherpriceyeartitlebookbookpublisherpriceyear。$doc$t$prepeatprice65.95TCP/IPIllu

6、strated minprice查询计划的执行示例查询计划的执行示例文档文档查询计划查询计划bibbooktitlepublisherpriceyeartitlebookbookpublisherpriceyear。$docpriceminpricepriceminprice results65.9570.05查询计划的执行示例查询计划的执行示例文档文档查询计划查询计划导航查询引擎小结 优点优点 简单，直接，而且对简单查询非常有效简单，直接，而且对简单查询非常有效 符合符合XQuery的特点：的特点： 过程化查询语言过程化查询语言 任意的嵌套任意的嵌套 缺点缺点 对复杂的查询需要遍历文档多遍对

7、复杂的查询需要遍历文档多遍 访问了非常多的无用结点访问了非常多的无用结点 不利于查询优化不利于查询优化代数查询引擎-OrientXA 一次一集合的查询处理策略 XQuery处理的问题 数据抽取操作 选择 投影 结果构造操作 结构构造 数据处理操作 连接 消除重复 分组Q1：一个XQuery例子 for $b in doc(bib.xml)/bib/book let $a := $b/author where $b/publisher/text() = Addison-Wesley and $b/year 1991 return $b/author 导航处理construct a for $bi

8、b in doc (“bib.xml”)/bib dofor $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 under construct a attribute year for with value $year append $authors content under end-if end-for

9、 /$year end-if end-for /$publisherend-for /$bend-for /$bib for $b in doc(bib.xml)/bib/book let $a := $b/author where $b/publisher/text() = Addison-Wesley and $b/year 1991 return $b/author OrientXA关于Pattern Tree 观察： XQuery一个变量绑定对应一个XPath Pattern Tree标识和抽取查询感兴趣的结点() Pattern Tree实际上是XPath的树状表示() 类比关系(?

10、)： Pattern Tree vs. 表定义 Instance Tree vs. 元组 Instance Tree集合 vs. 表Q1对应的Pattern Tree和Algebra Tree for $b in doc(bib.xml)/bib/book let $a := $b/author where $b/publisher/text() = Addison-Wesley and $b/year 1991 return $b/author 强结点绑定弱结点绑定序列绑定或序列构造 父子边祖先后代边元素属性边图例：p: 绑定所有后代结点n: 新建结点c: 拷贝结点SPTCPT Source

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

12、采用策略采用策略问题1 V3.0测试报告查询效率低查询效率低问题1分析数据抽取：数据抽取：访问磁盘的操作访问磁盘的操作结果构造：结果构造：内存中的中间结果内存中的中间结果结果构造：结果构造：内存中的中间结果内存中的中间结果 for $b in doc(bib.xml)/bib/book let $a := $b/author where $b/publisher/text() = Addison-Wesley and $b/year 1991 return $b/author 数据抽取的效率很大数据抽取的效率很大程度上决定了代数系程度上决定了代数系统的效率统的效率问题1分析 (2) Navig

13、ation处理尚未利用任何索引 for $b in doc(bib.xml)/bib/book let $a := $b/author where $b/publisher/text() = Addison-Wesley and $b/year 1991 return $b/author 问题1的解决办法 物理实现采用Twig查询处理方法 建立索引 Tag Index Path Index Sequence Index 利用TwigStack查询处理方法 Tag Index问题1的解决办法(2) 索引建立 在DEB存储的文档导入时创建索引 代码修改集中在DEB方式的四个SAX接口中 start

14、Document, 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

15、XQuery 1.0XQuery/Update (2) Insert, Delete, Replace, Rename, Transform表达式1.Insert 语句 2.Delete语句Insert 50 after /book/author Delete /bookyear = 1994/author XQuery/Update (3)3.Rename(修改结点名字), Replace(替换结点或值)4.Transform查询copy $a := /bookmodify delete $a/authorreturn $a 执行前执行后查询结果Transform查询的应用1. 修改查询结果

16、修改查询结果 查询: book的信息，但不返回 price信息2. 安全视图安全视图3. 更新虚拟视图更新虚拟视图copy $a := /book modify delete $a/price return $a 访问控制访问控制： 用户A不能访问author 为”Rose” 的book结点的price用户A提交查询: /book合成Transform查询: copy $a := /book modify delete $aauthor = “Rose”/price return $aXQuery代数处理 类似关系代数一样,提出了一系列的操作符.FOR $b in /book/priceFOR

17、 $y in /book/yearWHERE $b/price 1990RETURN $bSelectFilter $2 1990 Construct $2XQuery/Update代数处理copy $cb := /bookmodify delete $cb/pricereturn let $nb := $cb where $nb/title = “C+” return $nbConstruct $nbFilter $nb/title = “C+” 现有的XML代数能否表达XQuery/Update?扩展扩展现有XML代数(基于OrientXA):提出新操作符:1. Copy (拷贝)2. I

18、nsert (插入)3. Delete (删除)4. Replace (替换)5. Rename (重命名)Select book $1Copy $1Delete($2)Filter $nb/title = “C+” Construct $nb问题2 如何实现Transform查询？ 查询编译 Lex、Yacc 查询处理 修改XML代数规则 添加Transform操作符问题2分析 Transform查询语句分析 Copy Modify Insert Replace Delete FLWR语句copy $cb := /bookmodify delete $cb/pricereturn let $nb := $cb where $nb/title = “C+” return $nb问题2分析 (2) 代数操