数据库系统.ppt

《数据库系统.ppt》由会员分享，可在线阅读，更多相关《数据库系统.ppt（42页珍藏版）》请在三一办公上搜索。

1、OrientX:Native XML数据库系统,孟小峰 王宇 罗道峰 陆世潮 安靖 陈妍 蒋瑜 欧建波中国人民大学信息学院（100872）,Outline,体系结构和特征存储索引SUPEX结构索引结构索引使用的编码方法查询处理导航式查询处理集合式查询处理基于代价的查询优化更新基于角色的访问控制,OrientX特征,基于模式采用多种粒度的树形结构存储数据支持描述化查询语言XQuery基于代价估计的查询优化方法基于模式的路径索引基于角色的访问控制,体系结构,图1 OrientX体系结构图,数据存储管理索引模块查询处理数据更新用户访问控制模式管理接口,查询更新处理流数据导入导出流,Outline,体

2、系结构和特征存储索引查询处理导航式查询处理集合式查询处理基于代价的查询优化更新基于角色的访问控制,OrientX 存储策略,存储管理以记录为单位,逻辑含义是一棵子树，是读写的最小单位 一个XML文档包含若干个记录，多个满足同一个模式定义（DTD或者XML Schema）的XML文档放在一个数据集里。EID（AID）唯一地标志结点的类型数据集用SetID来标志；在文件上划分逻辑物理块物理块用LpNo来标志；给定一对，能马上找到对应文件的相应的偏移量。,多粒度存储策略,四种存储方法Element-basedDepth-first Element Based(DEB)Clustered Elemen

3、t Based（CEB）Subtree-basedDepth-first Subtree Based(DSB)Clustered Subtree Based(CSB),多粒度存储策略,DEB存储顺序:t f1 l1 a1 f2 l2 a2 b每个记录包含EID，Text Value和它的父记录的地址PAddress。CEB存储顺序:a1,a2聚簇存储在一个物理块；f1,f2在一个物理块；l1,l2在一个物理块；b,t各在一个物理块。DSB CSB,存储策略的选择,不同的文档适合用不同的方法来存储当文档比较小的时候，采用深度优先方法当文档比较大的时候，使用聚簇方法文档性质比较强的文档，采用深度优

4、先方法数据性质比较强的文档，采用聚簇方法为了处理上的方便，无论底层采取什么存储方法，对上层查询的接口都是一样的，这样，提供了一定的独立性。,Outline,体系结构和特征存储索引查询处理导航式查询处理集合式查询处理基于代价的查询优化更新基于角色的访问控制,SUPEX索引策略,父子关系祖先-后代关系绝对路径查询相对路径查询,元素映射表,编码方法概述,三类编码方法：Region-based:,Prefix-based:Dewey-codeK-ary-tree-based:PBiTree基于编码方法的索引和查询技术：EE-Join，EA-Join 和 KC-JoinMPMCJNSHCJ,MHCJ,V

5、PJstack-merge,结构索引使用的编码,BitPath思想：prefix-based方法好处：与region或者k-ary tree方法相比，变长、更新代价小。与其它prefix-based方法相比，不需要分隔符，减少存储空间，提高查询效率。,Outline,体系结构和特征存储索引查询处理导航式查询处理集合式查询处理基于代价的查询优化更新基于角色的访问控制,处理XQuery的核心问题,Path路径的求值问题结构连接基于树的导航式处理嵌套查询的解决方案相关嵌套非相关嵌套XML数据的有序性问题,XQuery查询导航式实现方法的主要模块,语法分析语义检查生成执行计划优化器逻辑的物理的执行引擎

6、,XQuery Execute Engine,导航式处理XQuery的结构图,Query Interface,XPath Execute Plan,XQuery Execute Plan,XPath Execute Engine,Data Manager,Optimize inline,产生执行计划的算法,构建执行计划并不是先生成语法树再构建执行计划。而是，语法分析的同时构建执行计划。当规约成一个语法单元时，即构建一个相应的操作符把构成该语法单元的子单元的对应操作符，置为新构建操作符的子操作；形成一棵执行计划树,例子,import default schema=xmarkfor$p in do

7、cument(xsmall.xml)/people/personLet$i:=$p/interestwhere$p/profile/income 10000return$p/profile$i,执行计划,FLWR,ForVarBind,LetVarBind,ConditionTree,EleConstructor,EleConstructor,Path,Path,$p in document(xsmall.xml)/people/person,$i:=$p/interest,$p/profile/income 10000,$p/profile,$i,导航式处理,FLWR,ForVarBind,

8、LetVarBind,ConditionTree,EleConstructor,EleConstructor,Path,Path,导航式处理,FLWR,ForVarBind,LetVarBind,ConditionTree,EleConstructor,EleConstructor,Path,Path,Evaluated true,导航式处理,FLWR,ForVarBind,LetVarBind,ConditionTree,EleConstructor,EleConstructor,Path,Path,Evaluated false,Outline,体系结构和特征存储索引查询处理导航式查询处理

9、集合式查询处理基于代价的查询优化更新基于角色的访问控制,集合式查询处理,借鉴关系代数方法，引入XML 代数，使操作变成一次一集合的操作。,XML Algebra 设计,设计思想主要问题难点,设计思想,引入关系中关于记录的概念，操作符的操作对象是记录的集合，若干操作符组成一棵操作符树，来表达一个查询。记录是一棵XML树操作符的分类Extraction操作Processing操作Construction操作,主要问题1：绑定到结点还是结点序列？（引入+修饰符）,FOR$b in document(“books.xml”)/bookLET$a:=$b/authorWHERE$b/year$a,FOR

10、$b in document(“books.xml”)/book$a in$b/authorWHERE$b/year$a,FOR$b in document(“books.xml”)/bookWHERE$b/year$b/author,问题2：结构谓词结点和非谓词结点,for$b in doc(http:/where$b/publisher=Addison-Wesley and$b/year 1991 return$b/title,问题3：表达式的嵌套（结果构造符多次使用）,FOR$b in document(“books.xml”)/bib/bookRETURN$b/title$b/pric

11、e FOR$r in document(“reviews.xml”)/review WHERE$b/title=$r/title RETURN$r/content,FOR$b in document(“books.xml”)/bib/book$r in document(“reviews.xml”)/reviewWHERE$b/title=$r/titleRETURN$b/title$b/price$r/content,问题4：谓词的作用域,for$v in document(“book.xml”)/vendorwhere$v/address=”beijing”return$v/name$v/

12、booktitle=“C+”,for$v in document(“book.xml”)/vendor$b in$v/bookwhere$v/address=”beijing”and$b/title=“C+”return$v/name$b,问题5：值绑定和引用绑定,有了中间结果，要不要与源数据发生联系？,难点,Pattern Tree Matching的策略选择导航式结构连接混合,Outline,体系结构和特征存储索引SUPEX结构索引结构索引使用的编码方法查询处理导航式查询处理集合式查询处理基于代价的查询优化更新基于角色的访问控制,基于代价的查询优化方法,采用直方图方法统计XML数据的分布情

13、况与模式统计信息相结合形成统计信息模型通过六种不同的直方图运算,计算任意路径中任意子路径的选择性,代价计算实例,n1/n2/n3/n4av,Outline,体系结构和特征存储索引SUPEX结构索引结构索引使用的编码方法查询处理导航式查询处理集合式查询处理基于代价的查询优化更新基于角色的访问控制,XML更新涉及问题,更新有效性检查结构有效性属性有效性结点定位存储空间的分配其它辅助数据的更新，比如索引、编码等。,更新方法,根据模式信息判断更新的有效性根据不同的存储方法设计不同的更新方法根据模式信息设计不同的预留空间在非聚簇存储和CEB时预留空间相同在CSB方法时预留空间不同,Outline,体系结构和特征存储索引SUPEX结构索引结构索引使用的编码方法查询处理导航式查询处理集合式查询处理基于代价的查询优化更新基于角色的访问控制,基于角色的用户访问控制,角色之间有继承关系，构成一棵角色树。用户访问控制的最小粒度是结点级。采用类XPath语句对每个角色授权为了使用方便和强化授权能力引入否定授权，制定权限冲突规则，和冲突检测机制。授权检测时，只需对查询语句构成的查询树和授权语句构成的权限树匹配，如果查询树满足权限树，则允许查询执行，否则拒绝，无需访问数据信息。,下一步工作,完善XML代数，实现集合式的XQuery查询处理进一步研究XML查询优化问题完善更新和访问控制方法,