《XML数据管理技术》PPT课件.ppt

XML数据管理技术,周军锋,2019/5/22,2/65,大纲,简介 流程 内容 总结,2019/5/22,3/65,大纲,简介 流程 内容 总结,2019/5/22,4/65,综述简介必要性,XML数据大量涌现 Gartner1预测，XML文件的使用率在 2007年达到40%， 2008年将占据支配地位 IDC（国际数据公司）报告显示，在500家受访企业的IT部门中，有29正在大量使用XML数据库 XML研究如火如荼 每年各种学术会议期刊发表XML相关论文多达300篇 没有系统的总结和比较 发表时间早：大部分出现在06年左右 内容局限性：主要涉及查询，索引 1.in/summit/eform/technical-papers/gartneruseofxml.pdf/view,2019/5/22,5/65,综述简介信息源,要求 全面性 06-08年各种会议期刊 国际会议 国际期刊 国内会议 国内期刊,2019/5/22,6/65,综述简介信息源,国际会议 (ACM) SIGMOD ： (Association for Computing Machinery) Special Interest Group on Management of Data VLDB : International Conference on Very Large Data Bases ICDE : International Conference on Data Engineering EDBT : International Conference on Extending Database Technology WWW : International Conference on World Wide Web CIKM : International Conference on Information and Knowledge Management DASFAA : Database Systems for Advanced Applications ER : International Conference on the Entity Relationship Approach PODS : Symposium on Principles of Database Systems SIGIR : International Conference on Research and Development in Information Retrieval ICDT : International Conference on Database Theory DEXA : Database and Expert Systems Applications CIDR : Conference on Innovative Data Systems Research WISE : Web Information Systems Engineering WAIM : International Conference on Web-Age Information Management APWeb : Asia-Pacific Web Conference WebDB : International Workshop on the Web and Databases INEX : INitiative for the Evaluation of XML Retrieval XIME-P : Workshop on XQuery IMplementation, Experience and Perspectives XSym : International XML Database Symposium （08年不存在了） XML Conference : 应用相关的会议,2019/5/22,7/65,综述简介信息源,国际期刊 VLDBJ ：The VLDB Journal TODS ： ACM Transactions on Database Systems TKDE ： IEEE Transactions on Knowledge and Data Engineering TOIS ： ACM Transactions on Information Systems JACM ： Journal of the ACM CACM ： Communications of the ACM IS ： Information System IR ： Information Retrieval KIS： Knowledge and Information System SIGMOD-Record DKE ： Data & Knowledge Engineering JDM ： Journal of Database Management WWWJ ：World Wide Web JCST ： Journal of Computer Science and Technology,2019/5/22,8/65,综述简介信息源,国内会议 NDBC 国内期刊 计算机学报 软件学报 计算机研究与发展 计算机科学与探索,2019/5/22,9/65,综述简介内容提炼,2019/5/22,10/65,综述简介内容提炼,如何压缩内容？ 06-08：200/812，2005年以前的？ 已有综述中阐述的内容，直接引用并总结 对所有新内容分类整理，得到需要的类别 对每一类中的文章，去除重复文章 尽量引用大会文章,2019/5/22,11/65,综述简介内容提炼,分类整理，去除重复：150/360/700/800,2019/5/22,12/65,大纲,简介 流程 内容 总结,2019/5/22,13/65,综述流程,建立数据库 导入/出文档 执行查询,2019/5/22,14/65,综述流程,建立数据库,2019/5/22,15/65,综述流程,建立数据库 导入/出文档,2019/5/22,16/65,综述流程,建立数据库 导入/出文档 执行查询,People/person/profile/gender,2019/5/22,17/65,综述流程,研究点 存储 存储策略 编码方案 索引 查询 查询改写 查询优化 查询算法,2019/5/22,18/65,大纲,简介 流程 内容 总结,2019/5/22,19/65,内容介绍,存储 存储策略 编码方案 索引 查询 查询改写 查询优化 查询算法,2019/5/22,20/65,存储策略,关系表 查询 导出文档 Native 方式 混合方式 问题 Benchmark 文档类型 文本 数据,2019/5/22,21/65,内容介绍,存储 存储策略 编码方案 索引 查询 查询改写 查询优化 查询算法,2019/5/22,22/65,编码方案,为什么使用编码 导航不可行,a1,b1,b2,b3,c1,d1,d2,e1,f1,a,d,Query,Document,如何判断元素之间的关系？,2019/5/22,23/65,编码方案,为什么使用编码 已有的解决方案 区间编码,a1,b1,b2,b3,c1,d1,d2,e1,f1,a,d,Query,Document,(1,1),(start, end, level),(2,2),3,(4,2),(5,3),6,(7,3),8,9,(10,2),11,(12,2),17,(13,3),14,(15,3),16,18,2019/5/22,24/65,编码方案,为什么使用编码 已有的解决方案 区间编码 路径编码,a1,b1,b2,b3,c1,d1,d2,e1,f1,a,d,Query,Document,1,1.1,1.2,1.2.1,1.2.2,1.3,1.4,1.4.1,1.4.2,2019/5/22,25/65,编码方案,为什么使用编码 已有的解决方案 实际问题 文档更新 插入叶子节点 插入非叶子节点 节点编码需要更新,a,d,Query,Document,a1,b1,b2,b3,c1,d1,d2,e1,f1,(1,1),(2,2),3,(4,2),(5,3),6,(7,3),8,9,(10,2),11,(12,2),17,(13,3),14,(15,3),16,18,g,a1,b1,b2,b3,c1,d1,d2,e1,f1,1,1.1,1.2,1.2.1,1.2.2,1.3,1.4,1.4.1,1.4.2,g,g,g,g,2019/5/22,26/65,编码方案,为什么使用编码 已有的解决方案 已有更新方法 空间预留 无法避免重新编码,a,d,Query,Document,a1,b1,b2,b3,c1,d1,d2,e1,f1,(10,1),(20,2),30,(40,2),(50,3),60,(70,3),80,90,(100,2),110,(120,2),170,(130,3),140,(150,3),160,180,2019/5/22,27/65,编码方案,为什么使用编码 已有的解决方案 已有更新方法 空间预留 浮点数编码 无法避免重新编码,a,d,Query,Document,a1,b1,b2,b3,c1,d1,d2,e1,f1,(1,1),(2,2),3,(4,2),(5,3),6,(7,3),8,9,(10,2),11,(12,2),17,(13,3),14,(15,3),16,18,g1,(110.01, 110.11, 3),(101, 110, 3),(111, 1000, 3),(110.1101, 110.1111, 3),2019/5/22,28/65,编码方案,为什么使用编码 已有的解决方案 已有更新方法 空间预留 浮点数编码 路径编码ORDPATH 代价高,a1,b1,b2,b4,c1,d1,d2,e1,f1,a1,b1,b4,c1,e1,f1,1,1.1,1.3,1.5,1.5.1,1.5.3,b2,1.2.1,b3,2019/5/22,29/65,编码方案,为什么使用编码 已有的解决方案 已有更新方法 空间预留 浮点数编码 路径编码 素数编码 可避免更新编码 N值计算代价高,a1,b2,c1,d1,d2,e1,f1,1,2,3,5,7,11,13,1,2=2*1,6=3*2,10=5*2,7=7*1,77=11*7,91=13*7,d1,17,170=17*10,N1=1523,N2=6,72,2019/5/22,30/65,编码方案,为什么使用编码 已有的解决方案 已有更新方法 空间预留 浮点数编码 路径编码 素数编码 二进制位串,将整数用二进制字符串表示,a1,b1,b2,b3,c1,d1,d2,e1,f1,(1,1),(2,2),3,(4,2),(5,3),6,(7,3),8,9,(10,2),11,(12,2),17,(13,3),14,(15,3),16,18,0 size=0,19 size=0,(01, 01001, 001),(0101, 011, 001),g,(010011, 0100111, 001),2019/5/22,31/65,编码方案,为什么使用编码 已有的解决方案 已有更新方法 空间预留 浮点数编码 路径编码 素数编码 位串编码 向量编码,将整数用向量表示,a1,b1,b2,b3,c1,d1,d2,e1,f1,(1,1),(2,2),3,(4,2),(5,3),6,(7,3),8,9,(10,2),11,(12,2),17,(13,3),14,(15,3),16,18,2019/5/22,32/65,编码方案,为什么使用编码 已有的解决方案 已有更新方法 空间预留 浮点数编码 路径编码 素数编码 位串编码 向量编码,a1,b1,b2,b3,c1,d1,d2,e1,f1,(1,1),(2,2),3,(4,2),(5,3),6,(7,3),8,9,(10,2),11,(12,2),17,(13,3),14,(15,3),16,18,2019/5/22,33/65,编码方案,为什么使用编码 已有的解决方案 已有更新方法 空间预留 浮点数编码 路径编码 素数编码 位串编码 向量编码,a1,b1,b2,b3,c1,d1,d2,e1,f1,(1,1),(2,2),3,(4,2),(5,3),6,(7,3),8,9,(10,2),11,(12,2),17,(13,3),14,(15,3),16,18,2019/5/22,34/65,编码方案,为什么使用编码 已有的解决方案 已有更新方法 基于图的编码 不支持更新,2019/5/22,35/65,编码方案,为什么使用编码 已有的解决方案 已有更新方法 基于图的编码 不支持更新 支持更新,2019/5/22,36/65,编码方案,为什么使用编码 已有的解决方案 实际问题 可能的研究点 树上编码的更新 什么情况下可在两个值之间插入无穷多个值 图上编码的更新 如何将不同区间用一个值表示,2019/5/22,37/65,内容介绍,存储 存储策略 编码方案 索引 查询 查询改写 查询优化 查询算法,2019/5/22,38/65,索引,为什么使用索引,a1,b1,b2,b3,c1,d1,d2,e1,f1,a,d,Query,Document,a,a1,d,d1,d2,2019/5/22,39/65,索引,为什么使用索引 索引的类型 结构索引 Tag 索引 Structural summary 值索引 倒排表,a1,b1,b2,d3,c1,d1,d2,e1,f1,b,d,Query,Document,2019/5/22,40/65,索引,为什么使用索引 索引的类型 结构索引 F&B index 1-index,2019/5/22,41/65,索引,为什么使用索引 索引的类型 结构索引 F&B index 1-index,B,D,C,B,D,2019/5/22,42/65,内容介绍,存储 存储策略 编码方案 索引 查询 查询改写 查询优化 查询算法,2019/5/22,43/65,查询改写,什么是查询改写 用户提交查询Q 系统处理Q,2019/5/22,44/65,查询改写,什么是查询改写 为什么要查询改写 用户提交的查询表达能力有限：关键字查询 用户提交的查询有误,a1,b1,b2,d3,c1,d1,d2,e1,f1,2019/5/22,45/65,查询改写,什么是查询改写 为什么要查询改写 查询改写的方式 基于用户反馈 结果反馈 查询反馈 隐式反馈：无用户参与,2019/5/22,46/65,用户反馈,2. User marks relevant and nonrelevant docs,3. System finds best terms to distinguish between relevant and nonrelevant docs,4. System submits expanded query,Feedback for XML IR: Start with keyword query Find structural expansions Create structural query,2019/5/22,47/65,用户反馈,sec Semistructured data“,article,body,sec,subsec XML has evolved“,frontmatter,backmatter,sec,subsec,p,p,p With the advent of XSLT“,author Baeza-Yates“,citation Serge Abiteboul“,2019/5/22,48/65,用户反馈,XML Search Engine,feedback,Scoring + Reranking,expanded query,query,results,reranked results,Content Module,Path Module,Doc Module,Feedback Dimensions,query + results,2019/5/22,49/65,查询改写,什么是查询改写 为什么要查询改写 查询改写的方式 基于用户反馈 伪反馈 又称局部反馈、盲反馈,它假设初始检索结果的前面若干篇文档是相关的,然后利用标准的相关反馈过程进行查询扩展 隐式反馈 用户不主动参与反馈,但是系统仍需要从用户的浏览行为中分析得到一些有用的信息用来确定用户兴趣模式,从而推理出描述用户查询需求的表达式,并据此进行检索. 查询扩展 黄静的工作,2019/5/22,50/65,内容介绍,存储 存储策略 编码方案 索引 查询 查询改写 查询优化 查询算法,2019/5/22,51/65,查询优化,种类 逻辑优化 物理优化,2019/5/22,52/65,查询优化,逻辑优化,2019/5/22,53/65,查询优化,物理优化 代价估计 单步代价估计 执行顺序 整体代价估计,2019/5/22,54/65,内容介绍,存储 存储策略 编码方案 索引 查询 查询改写 查询优化 查询算法,2019/5/22,55/65,查询算法-Twig查询处理,导航式,a1,b1,b2,b3,c1,d1,d2,e1,f1,a,d,Query,Document,2019/5/22,56/65,查询算法-Twig查询处理,导航式 结构连接 二元 Path连接 整体匹配,3,2,1,2,2,1,大量中间结果,2019/5/22,57/65,查询算法-Twig查询处理,导航式 结构连接 二