《XML数据管理技术》

1、XML数据管理技术周军锋7/19/20221精选ppt大纲简介流程内容总结7/19/20222大纲简介流程内容总结7/19/20223综述简介必要性XML数据大量涌现Gartner1预测，XML文件的使用率在2007年达到40%，2008年将占据支配地位IDC（国际数据公司）报告显示，在500家受访企业的IT部门中，有29正在大量使用XML数据库 XML研究如火如荼每年各种学术会议期刊发表XML相关论文多达300篇没有系统的总结和比较发表时间早：大部分出现在06年左右内容局限性：主要涉及查询，索引1.in/summit/eform/technical-papers/gartneruseofxm

2、l.pdf/view7/19/20224综述简介信息源要求全面性06-08年各种会议期刊国际会议国际期刊国内会议国内期刊7/19/20225综述简介信息源国际会议(ACM) SIGMOD ： (Association for Computing Machinery) Special Interest Group on Management of DataVLDB : International Conference on Very Large Data BasesICDE : International Conference on Data Engineering EDBT : Interna

3、tional Conference on Extending Database Technology WWW : International Conference on World Wide WebCIKM : International Conference on Information and Knowledge Management DASFAA : Database Systems for Advanced Applications ER : International Conference on the Entity Relationship Approach PODS : Symp

4、osium 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 Informatio

5、n 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 Perspec

6、tives XSym : International XML Database Symposium （08年不存在了）XML Conference : 应用相关的会议关注的会议较好的workshop7/19/20226综述简介信息源国际期刊VLDBJ ：The VLDB Journal TODS ： ACM Transactions on Database Systems TKDE ： IEEE Transactions on Knowledge and Data EngineeringTOIS ： ACM Transactions on Information Systems JACM ：

7、Journal of the ACM CACM ： Communications of the ACM IS ： Information SystemIR ： Information RetrievalKIS： Knowledge and Information SystemSIGMOD-Record DKE ： Data & Knowledge Engineering JDM ： Journal of Database Management WWWJ ：World Wide Web JCST ： Journal of Computer Science and Technology 7/19/

8、20227综述简介信息源国内会议NDBC国内期刊计算机学报软件学报计算机研究与发展计算机科学与探索7/19/20228综述简介内容提炼7/19/20229综述简介内容提炼如何压缩内容？06-08：200/812，2005年以前的？已有综述中阐述的内容，直接引用并总结对所有新内容分类整理，得到需要的类别对每一类中的文章，去除重复文章尽量引用大会文章7/19/202210综述简介内容提炼分类整理，去除重复：150/360/700/8007/19/202211大纲简介流程内容总结7/19/202212综述流程Data Storage ManagerData ManagerSchema Manager

9、Index ManagerXML DataXML QueryQuery ResultExecute EngineData DefinitionXQueryXPathKeyword建立数据库导入/出文档执行查询7/19/202213综述流程Data Storage ManagerData ManagerSchema ManagerIndex ManagerXML DataXML QueryQuery ResultExecute EngineData DefinitionXQueryXPathKeyword建立数据库7/19/202214综述流程Data Storage ManagerData M

10、anagerSchema ManagerIndex ManagerXML DataXML QueryQuery ResultExecute EngineData DefinitionXQueryXPathKeyword建立数据库导入/出文档7/19/202215综述流程Data Storage ManagerData ManagerSchema ManagerIndex ManagerXML DataXML QueryQuery ResultExecute EngineData DefinitionXQueryXPathKeyword建立数据库导入/出文档执行查询Query ParserQue

11、ry OptimizerQuery EvaluatorExecute EnginePeople/person/profile/gender7/19/202216综述流程Data Storage ManagerData ManagerSchema ManagerIndex ManagerXML DataXML QueryQuery ResultExecute EngineData DefinitionXQueryXPathKeyword研究点存储存储策略编码方案索引查询查询改写查询优化查询算法7/19/202217大纲简介流程内容总结7/19/202218内容介绍存储存储策略编码方案索引查询查询

12、改写查询优化查询算法7/19/202219存储策略关系表查询导出文档Native 方式混合方式问题Benchmark文档类型文本数据。attributesvaluenameid7/19/202220内容介绍存储存储策略编码方案索引查询查询改写查询优化查询算法7/19/202221编码方案为什么使用编码导航不可行a1b1b2b3c1d1d2e1f1adQueryDocument如何判断元素之间的关系？aa1dd1d2仅处理tag名为a和d的元素，可以减少处理的元素数量7/19/202222编码方案为什么使用编码已有的解决方案区间编码a1b1b2b3c1d1d2e1f1adQueryDocumen

13、t(1, ,1)(start, end, level)(2, ,2) 3(4, ,2)(5, ,3) 6(7, ,3) 89(10, ,2)11(12, ,2) 17(13, ,3) 14(15, ,3) 16 18 1 18 5 6 7 8ad(1, 18, 1)(5, 6, 3)(7, 8, 3)7/19/202223编码方案为什么使用编码已有的解决方案区间编码路径编码a1b1b2b3c1d1d2e1f1adQueryDocumentad..1.4.27/19/202224编码方案为什么使用编码已有的解决方案实际问题

14、文档更新插入叶子节点插入非叶子节点节点编码需要更新adQueryDocumenta1b1b2b3c1d1d2e1f1(1, ,1)(2, ,2) 3(4, ,2)(5, ,3) 6(7, ,3) 89(10, ,2)11(12, ,2) 17(13, ,3) 14(15, ,3) 16 18ga1b1b2b3c1d1d2e1f.1.4.2gggg7/19/202225编码方案为什么使用编码已有的解决方案已有更新方法空间预留无法避免重新编码adQueryDocumenta1b1b2b3c1d1d2e1f1(10, ,1)(20, ,2) 3

15、0(40, ,2)(50, ,3) 60(70, ,3) 8090(100, ,2)110(120, ,2) 170(130, ,3) 140(150, ,3) 160 1807/19/202226编码方案为什么使用编码已有的解决方案已有更新方法空间预留浮点数编码无法避免重新编码adQueryDocumenta1b1b2b3c1d1d2e1f1(1, ,1)(2, ,2) 3(4, ,2)(5, ,3) 6(7, ,3) 89(10, ,2)11(12, ,2) 17(13, ,3) 14(15, ,3) 16 18g1g2(110.01, 110.11, 3)(101, 110, 3)(11

16、1, 1000, 3)(110.1101, 110.1111, 3)7/19/202227编码方案为什么使用编码已有的解决方案已有更新方法空间预留浮点数编码路径编码ORDPATH代价高a1b1b2b4c1d1d2e1f1a1b1b4c1e1f.3b21.2.1d1d2b21.2.3b37/19/202228编码方案为什么使用编码已有的解决方案已有更新方法空间预留浮点数编码路径编码素数编码可避免更新编码N值计算代价高a1b2c1d1d2e1f112357111312=2*16=3*210=5*27=7*177=11*791=13*7d117170=17*10

17、N1=1523N2=6N1=1139N2=7272NNNNN345NNNNN7/19/202229编码方案为什么使用编码已有的解决方案已有更新方法空间预留浮点数编码路径编码素数编码二进制位串将整数用二进制字符串表示a1b1b2b3c1d1d2e1f1(1, ,1)(2, ,2) 3(4, ,2)(5, ,3) 6(7, ,3) 89(10, ,2)11(12, ,2) 17(13, ,3) 14(15, ,3) 16 18将插入整数变为插入字符串0 size=019 size=0(01, 01001, 001)(0101, 011, 001)g(010011, 0100111, 001)7/1

18、9/202230编码方案为什么使用编码已有的解决方案已有更新方法空间预留浮点数编码路径编码素数编码位串编码向量编码将整数用向量表示a1b1b2b3c1d1d2e1f1(1, ,1)(2, ,2) 3(4, ,2)(5, ,3) 6(7, ,3) 89(10, ,2)11(12, ,2) 17(13, ,3) 14(15, ,3) 16 18将插入整数变为插入向量7/19/202231编码方案为什么使用编码已有的解决方案已有更新方法空间预留浮点数编码路径编码素数编码位串编码向量编码a1b1b2b3c1d1d2e1f1(1, ,1)(2, ,2) 3(4, ,2)(5, ,3) 6(7, ,3)

19、89(10, ,2)11(12, ,2) 17(13, ,3) 14(15, ,3) 16 187/19/202232编码方案为什么使用编码已有的解决方案已有更新方法空间预留浮点数编码路径编码素数编码位串编码向量编码a1b1b2b3c1d1d2e1f1(1, ,1)(2, ,2) 3(4, ,2)(5, ,3) 6(7, ,3) 89(10, ,2)11(12, ,2) 17(13, ,3) 14(15, ,3) 16 1818=(0,1)1=(1,0)10=(1,1)6=(2,1)14=(1,2)(2,5), (2,1), 3)(5,3), (3,2), 3)7/19/202233编码方案为

20、什么使用编码已有的解决方案已有更新方法基于图的编码不支持更新7/19/202234编码方案为什么使用编码已有的解决方案已有更新方法基于图的编码不支持更新支持更新7/19/202235编码方案为什么使用编码已有的解决方案实际问题可能的研究点树上编码的更新什么情况下可在两个值之间插入无穷多个值图上编码的更新如何将不同区间用一个值表示a1d2d17/19/202236内容介绍存储存储策略编码方案索引查询查询改写查询优化查询算法7/19/202237索引为什么使用索引a1b1b2b3c1d1d2e1f1adQueryDocumentaa1dd1d27/19/202238索引为什么使用索引索引的类型结构

21、索引Tag 索引Structural summary值索引倒排表a1b1b2d3c1d1d2e1f1bdQueryDocumentbb1dd1d2b2bb1dd1d2b2d3abcdefd7/19/202239索引为什么使用索引索引的类型结构索引F&B index1-index7/19/202240索引为什么使用索引索引的类型结构索引F&B index1-indexBDCBD7/19/202241内容介绍存储存储策略编码方案索引查询查询改写查询优化查询算法7/19/202242查询改写什么是查询改写用户提交查询Q系统处理Q7/19/202243查询改写什么是查询改写为什么要查询改写用户提交的查

22、询表达能力有限：关键字查询用户提交的查询有误a1b1b2d3c1d1d2e1f17/19/202244查询改写什么是查询改写为什么要查询改写查询改写的方式基于用户反馈结果反馈查询反馈隐式反馈：无用户参与7/19/2022451234XMLXMLIRIRindexindexFaginIRindex用户反馈2. User marks relevant and nonrelevant docs3. System finds best terms to distinguish between relevant and nonrelevant docs4. System submits expanded

23、 query1. User submits queryquery evaluationXML not(Fagin)Feedback for XML IR: Start with keyword query Find structural expansions Create structural query7/19/202246Tag+Content of other elements in the documentD: /authorBaeza /citationAbiteboulUser marksrelevant resultPath tothe resultP: article/body

24、/sec/subsec用户反馈secSemistructured data“articlebodysecsubsecXML has evolved“frontmatterbackmattersecsubsecpppWith the advent of XSLT“authorBaeza-Yates“Content ofresultPossible dimensions:C: XMLcitationSerge Abiteboul“7/19/202247用户反馈XML SearchEnginefeedbackScoring + Rerankingexpanded queryqueryresultsr

25、eranked resultsContentModulePathModuleDocModuleFeedback Dimensionsquery +results7/19/202248查询改写什么是查询改写为什么要查询改写查询改写的方式基于用户反馈伪反馈又称局部反馈、盲反馈,它假设初始检索结果的前面若干篇文档是相关的,然后利用标准的相关反馈过程进行查询扩展隐式反馈用户不主动参与反馈,但是系统仍需要从用户的浏览行为中分析得到一些有用的信息用来确定用户兴趣模式,从而推理出描述用户查询需求的表达式,并据此进行检索.查询扩展黄静的工作7/19/202249内容介绍存储存储策略编码方案索引查询查询改写查询

26、优化查询算法7/19/202250查询优化种类逻辑优化物理优化7/19/202251查询优化逻辑优化语法优化语义优化7/19/202252查询优化物理优化代价估计单步代价估计执行顺序整体代价估计查询：abcdefd7/19/202253内容介绍存储存储策略编码方案索引查询查询改写查询优化查询算法7/19/202254查询算法-Twig查询处理导航式a1b1b2b3c1d1d2e1f1adQueryDocument7/19/202255查询算法-Twig查询处理导航式结构连接二元Path连接整体匹配abdcabbdaca1b1b2b3c1d1d2e1f13212abdac21大量中间结果7/19/202256查询算法-Twig查询处理导航式结构连接二元Path连接整体匹配adrd1a1a3a5a2a4f1d2d3a6d4d5d6a3a4d2d3a6d4d5cursorMarkada1(7,20)a2(14,19)a3(21,28)a4(22,27)a5(29,31)a6(32,40)d1(2,4)d2(23,24)d3(25,26)d4(33,34)d5(37,38)d6(43,44)a3d2a3d3a4d2a4d3a6d4a6d5后代指针回指为什么？7/19/202257查询算法-Twig查询处理导航式