OrientX Native XML数据库系统课件

OrientX:NativeXML数据库系统Outline体系结构和特征存储索引SUPEX结构索引结构索引使用的编码方法查询处理导航式查询处理集合式查询处理基于代价的查询优化更新基于角色的访问控制OrientX特征基于模式采用多种粒度的树形结构存储数据支持描述化查询语言XQuery基于代价估计的查询优化方法基于模式的路径索引基于角色的访问控制…

体系结构图1OrientX体系结构图数据存储管理索引模块查询处理数据更新用户访问控制模式管理接口查询更新处理流数据导入导出流

查询处理XML文档用户访问控制DTD文档XSD文档数据库建立维护管理API数据更新模式管理数据存取管理查询处理语句数据存储管理数据、模式信息、用户信息、统计信息、索引信息DEBCEBDSBCSB查询分解查询执行查询优化数据缓冲管理索引管理Outline体系结构和特征存储索引查询处理导航式查询处理集合式查询处理基于代价的查询优化更新基于角色的访问控制OrientX存储策略

存储管理以记录为单位,逻辑含义是一棵子树，是读写的最小单位

一个XML文档包含若干个记录，多个满足同一个模式定义（DTD或者XMLSchema）的XML文档放在一个数据集里。

EID（AID）唯一地标志结点的类型数据集用SetID来标志；在文件上划分逻辑物理块物理块用LpNo来标志；给定一对<SetID，LpNo>，能马上找到对应文件的相应的偏移量。多粒度存储策略四种存储方法Element-basedDepth-firstElementBased(DEB)ClusteredElementBased（CEB）

Subtree-basedDepth-firstSubtreeBased(DSB)

ClusteredSubtreeBased(CSB)

多粒度存储策略l1

l2

f2

f1

a1

b

t

a2

l1

l2

f2

f1

a1

b

t

a2

DEB存储顺序:tf1l1a1f2l2a2b每个记录包含EID，TextValue和它的父记录的地址PAddress。CEB存储顺序:a1,a2聚簇存储在一个物理块；f1,f2在一个物理块；l1,l2在一个物理块；b,t各在一个物理块。DSB CSB存储策略的选择不同的文档适合用不同的方法来存储当文档比较小的时候，采用深度优先方法当文档比较大的时候，使用聚簇方法文档性质比较强的文档，采用深度优先方法数据性质比较强的文档，采用聚簇方法为了处理上的方便，无论底层采取什么存储方法，对上层查询的接口都是一样的，这样，提供了一定的独立性。Outline体系结构和特征存储索引查询处理导航式查询处理集合式查询处理基于代价的查询优化更新基于角色的访问控制SUPEX索引策略父子关系祖先-后代关系绝对路径查询相对路径查询结构图

索引记录

DocId,RID,Level,Info……元素映射表编码方法概述三类编码方法：Region-based:<start,end>,<order,size>Prefix-based:Dewey-codeK-ary-tree-based:PBiTree基于编码方法的索引和查询技术：EE-Join，EA-Join和KC-JoinMPMCJNSHCJ,MHCJ,VPJstack-merge结构索引使用的编码BitPath思想：prefix-based方法好处：与region或者k-arytree方法相比，变长、更新代价小。与其它prefix-based方法相比，不需要分隔符，减少存储空间，提高查询效率。Outline体系结构和特征存储索引查询处理导航式查询处理集合式查询处理基于代价的查询优化更新基于角色的访问控制处理XQuery的核心问题Path路径的求值问题结构连接基于树的导航式处理嵌套查询的解决方案相关嵌套非相关嵌套XML数据的有序性问题XQuery查询导航式实现方法的主要模块语法分析语义检查生成执行计划优化器逻辑的物理的执行引擎XQueryExecuteEngine导航式处理XQuery的结构图QueryInterfaceXPathExecutePlanXQueryExecutePlanXPathExecuteEngineDataManagerTypecheckSemanticCheckXQueryParserOptimizeinline产生执行计划的算法构建执行计划并不是先生成语法树再构建执行计划。而是，语法分析的同时构建执行计划。当规约成一个语法单元时，即构建一个相应的操作符把构成该语法单元的子单元的对应操作符，置为新构建操作符的子操作；形成一棵执行计划树例子importdefaultschema="xmark"for$pindocument('xsmall.xml')//people/personLet$i:=$p//interestwhere$p/profile/@income>10000return<person><profile>{$p/profile}</profile>{$i}</person>执行计划FLWRForVarBindLetVarBindConditionTreeEleConstructorEleConstructorPathPath$pindocument('xsmall.xml')//people/person$i:=$p//interest$p/profile/@income>10000<person><profile>{$p/profile}</profile>$i导航式处理FLWRForVarBindLetVarBindConditionTreeEleConstructorEleConstructorPathPath导航式处理FLWRForVarBindLetVarBindConditionTreeEleConstructorEleConstructorPathPathEvaluatedtrue导航式处理FLWRForVarBindLetVarBindConditionTreeEleConstructorEleConstructorPathPathEvaluatedfalseOutline体系结构和特征存储索引查询处理导航式查询处理集合式查询处理基于代价的查询优化更新基于角色的访问控制集合式查询处理借鉴关系代数方法，引入XML代数，使操作变成一次一集合的操作。XMLAlgebra设计设计思想主要问题难点设计思想引入关系中关于记录的概念，操作符的操作对象是记录的集合，若干操作符组成一棵操作符树，来表达一个查询。记录是一棵XML树操作符的分类Extraction操作Processing操作Construction操作主要问题1：绑定到结点还是结点序列？（引入+修饰符）FOR$bindocument(“books.xml”)//bookLET$a:=$b/authorWHERE$b/year<1990RETURN<books_before_1990> <book> {$a}</book><books_before_1990>FOR$bindocument(“books.xml”)//book$ain$b/authorWHERE$b/year<1990RETURN<books_before_1990> <book> {$a}</book><books_before_1990>FOR$bindocument(“books.xml”)//bookWHERE$b/year<1990RETURN<books_before_1990> <book> {$b/author}</book><books_before_1990>问题2：结构谓词结点和非谓词结点

<bib>{for$bindoc("/bib.xml")/bib/bookwhere$b/publisher="Addison-Wesley"and$b/@year>1991return<bookyear="{$b/@year}">{$b/title}</book>}</bib>问题3：表达式的嵌套（结果构造符多次使用）

<result>FOR$bindocument(“books.xml”)/bib/bookRETURN<books_price_and_review>{$b/title}{$b/price}{FOR$rindocument(“reviews.xml”)//reviewWHERE$b/title=$r/titleRETURN$r/content}</books_price_and_review></result><result>FOR$bindocument(“books.xml”)/bib/book$rindocument(“reviews.xml”)//reviewWHERE$b/title=$r/title RETURN<books_price_and_review>{$b/title}{$b/price}{$r/content}</books_price_and_review></result>问题4：谓词的作用域

for$vindocument(“book.xml”)//vendorwhere$v/address=”beijing”return<vendor_books>{$v/name} {$v/book[title=“C++”]}</vendor_books>for$vindocument(“book.xml”)//vendor$bin$v/bookwhere$v/address=”beijing”and$b/title=“C++”return<vendor_books>{$v/name} {$b}</vendor_books>问题5：值绑定和引用绑定

有了中间结果，要不要与源数据发生联系？难点PatternTreeMatching的策略选择导航式结构连接混合Outline体系结构和特征存储索引SUPEX结构索引结构索引使用的编码方法查询处理导航式查询处理集合式查询处理基于代价的查询优化更新基于角色的访问控制基于代价的查询优化方法采用直方图方法统计XML数据的分布情况与模式统计信息相结合形成统计信息模型通过六种不同的直方图运算,计算任意路径中任意子路径的选择性代价计算实例n1/n2//n3/n4[a>v]

Outline体系结构和特征存储索引SUPEX结构索引结构索引使用的编码方法查询处理导航式查询处理集合式查询处理基于代价的查询优化更新基于角色的访问控制XML更新涉及问题更新有效性检查结构有效性属性有效性结点定位存储空间的分配其它辅助数据的更新，比如索引、编码等。更新方法

根据模式信息判断更新的有效性根据不同的存储方法设计不同的更新方法根据模式信息设计不同的预留空间在非聚簇存储和CEB时预留空间相同在CSB方法时预留空间不同Outline体系结构和特征存储索引SUPEX结构索