XML数据管理技术6课件.ppt

1、XML数据管理技术数据管理技术周军锋周军锋2022-8-92/65大纲大纲l简介简介l流程流程l内容内容l总结总结2022-8-93/65大纲大纲l简介简介l流程流程l内容内容l总结总结2022-8-94/65综述简介综述简介必要性必要性lXML数据大量涌现数据大量涌现lGartner1预测，XML文件的使用率在l2007年达到40%，l2008年将占据支配地位lIDC（国际数据公司）报告显示，在500家受访企业的IT部门中，有29正在大量使用XML数据库 lXML研究如火如荼研究如火如荼l每年各种学术会议期刊发表XML相关论文多达300篇l没有系统的总结和比较没有系统的总结和比较l发表时间早

2、：大部分出现在06年左右l内容局限性：主要涉及查询，索引1http:/egovstandards.gov.in/summit/eform/technical-papers/gartneruseofxml.pdf/view2022-8-95/65综述简介综述简介信息源信息源l要求要求l全面性l06-08年各种会议期刊年各种会议期刊l国际会议l国际期刊l国内会议l国内期刊2022-8-96/65综述简介综述简介信息源信息源l国际会议国际会议l(ACM)SIGMOD ：(Association for Computing Machinery)Special Interest Group on Man

3、agement of DatalVLDB :International Conference on Very Large Data BaseslICDE :International Conference on Data Engineering lEDBT:International Conference on Extending Database Technology lWWW:International Conference on World Wide WeblCIKM :International Conference on Information and Knowledge Manag

4、ement lDASFAA:Database Systems for Advanced Applications lER :International Conference on the Entity Relationship Approach lPODS :Symposium on Principles of Database Systems lSIGIR :International Conference on Research and Development in Information Retrieval lICDT :International Conference on Datab

5、ase Theory lDEXA :Database and Expert Systems Applications lCIDR :Conference on Innovative Data Systems Research lWISE :Web Information Systems Engineering lWAIM:International Conference on Web-Age Information Management lAPWeb:Asia-Pacific Web Conference lWebDB :International Workshop on the Web an

6、d Databases lINEX :INitiative for the Evaluation of XML Retrieval lXIME-P:Workshop on XQuery IMplementation,Experience and Perspectives lXSym :International XML Database Symposium （08年不存在了）lXML Conference:应用相关的会议应用相关的会议关注的会议关注的会议较好的较好的workshop2022-8-97/65综述简介综述简介信息源信息源l国际期刊国际期刊lVLDBJ：The VLDB Journa

7、l lTODS：ACM Transactions on Database Systems lTKDE：IEEE Transactions on Knowledge and Data EngineeringlTOIS：ACM Transactions on Information Systems lJACM：Journal of the ACM lCACM：Communications of the ACM lIS：Information SystemlIR：Information RetrievallKIS：Knowledge and Information SystemlSIGMOD-Rec

8、ord lDKE：Data&Knowledge Engineering lJDM：Journal of Database Management lWWWJ：World Wide Web lJCST：Journal of Computer Science and Technology 2022-8-98/65综述简介综述简介信息源信息源l国内会议国内会议lNDBCl国内期刊国内期刊l计算机学报l软件学报l计算机研究与发展l计算机科学与探索2022-8-99/65综述简介综述简介内容提炼内容提炼2022-8-910/65综述简介综述简介内容提炼内容提炼l如何压缩内容？如何压缩内容？l06-08：2

9、00/812，2005年以前的？l已有综述中阐述的内容，已有综述中阐述的内容，直接引用并总结直接引用并总结l对所有新内容对所有新内容分类整理分类整理，得到需要的类别，得到需要的类别l对每一类中的文章，对每一类中的文章，去除重复去除重复文章文章l尽量引用大会文章2022-8-911/65综述简介综述简介内容提炼内容提炼l分类整理，去除重复：分类整理，去除重复：150/360/700/8002022-8-912/65大纲大纲l简介简介l流程流程l内容内容l总结总结2022-8-913/65综述流程综述流程Data Storage ManagerData ManagerSchema ManagerI

10、ndex ManagerXML DataXML QueryQuery ResultExecute EngineData DefinitionXQueryXPathKeywordl建立数据库建立数据库l导入导入/出文档出文档l执行查询执行查询2022-8-914/65综述流程综述流程Data Storage ManagerData ManagerSchema ManagerIndex ManagerXML DataXML QueryQuery ResultExecute EngineData DefinitionXQueryXPathKeywordl建立数据库建立数据库2022-8-915/65

11、综述流程综述流程Data Storage ManagerData ManagerSchema ManagerIndex ManagerXML DataXML QueryQuery ResultExecute EngineData DefinitionXQueryXPathKeywordl建立数据库建立数据库l导入导入/出文档出文档2022-8-916/65综述流程综述流程Data Storage ManagerData ManagerSchema ManagerIndex ManagerXML DataXML QueryQuery ResultExecute EngineData Defini

12、tionXQueryXPathKeywordl建立数据库建立数据库l导入导入/出文档出文档l执行查询执行查询Query ParserQuery OptimizerQuery EvaluatorExecute EnginePeople/person/profile/gender2022-8-917/65综述流程综述流程Data Storage ManagerData ManagerSchema ManagerIndex ManagerXML DataXML QueryQuery ResultExecute EngineData DefinitionXQueryXPathKeywordl研究点研究

13、点l存储l存储策略l编码方案l索引l查询l查询改写l查询优化l查询算法2022-8-918/65大纲大纲l简介简介l流程流程l内容内容l总结总结2022-8-919/65内容介绍内容介绍l存储存储l存储策略存储策略l编码方案l索引索引l查询查询l查询改写l查询优化l查询算法2022-8-920/65存储策略存储策略l关系表关系表l查询l导出文档lNative 方式方式l混合方式混合方式l问题问题lBenchmarkl文档类型l文本l数据。attributesvaluenameid2022-8-921/65内容介绍内容介绍l存储存储l存储策略l编码方案编码方案l索引索引l查询查询l查询改写l查询

14、优化l查询算法2022-8-922/65编码方案编码方案l为什么使用编码为什么使用编码l导航不可行导航不可行a1b1b2b3c1d1d2e1f1adQueryDocument如何判断元素之间的关系？aa1dd1d2仅处理tag名为a和d的元素，可以减少处理的元素数量2022-8-923/65编码方案编码方案l为什么使用编码为什么使用编码l已有的解决方案已有的解决方案l区间编码区间编码a1b1b2b3c1d1d2e1f1adQueryDocument(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,

15、3)16 18 1 18 5 6 7 8ad(1,18,1)(5,6,3)(7,8,3)2022-8-924/65编码方案编码方案l为什么使用编码为什么使用编码l已有的解决方案已有的解决方案l区间编码l路径编码路径编码a1b1b2b3c1d1d2e1f1adQueryDocumentad11.2.11.2.211.11.21.2.11.2.21.31.41.4.11.4.22022-8-925/65编码方案编码方案l为什么使用编码为什么使用编码l已有的解决方案已有的解决方案l实际问题实际问题l文档更新l插入叶子节点l插入非叶子节点l节点编码需要更新adQueryDocumenta1b1b2b3

16、c1d1d2e1f1(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 18ga1b1b2b3c1d1d2e1f111.11.21.2.11.2.21.31.41.4.11.4.2gggg2022-8-926/65编码方案编码方案l为什么使用编码为什么使用编码l已有的解决方案已有的解决方案l已有更新方法已有更新方法l空间预留l无法避免重新编码adQueryDocumenta1b1b2b3c1d1d2e1f1(10,1)(20,2)30(40,2)(50,3)60(70,3)8090(100,2)110(120,2)170(

17、130,3)140(150,3)160 1802022-8-927/65编码方案编码方案l为什么使用编码为什么使用编码l已有的解决方案已有的解决方案l已有更新方法已有更新方法l空间预留l浮点数编码l无法避免重新编码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)(111,1000,3)(110.1101,110.1111,3)2022-8-928/65编码方案编码方案l为什么使用编码为什

18、么使用编码l已有的解决方案已有的解决方案l已有更新方法已有更新方法l空间预留l浮点数编码l路径编码ORDPATHl代价高a1b1b2b4c1d1d2e1f1a1b1b4c1e1f111.11.31.51.5.11.5.3b21.2.1d11.2.1.1d21.2.1.3b21.2.3b32022-8-929/65编码方案编码方案l为什么使用编码为什么使用编码l已有的解决方案已有的解决方案l已有更新方法已有更新方法l空间预留l浮点数编码l路径编码l素数编码l可避免更新编码lN值计算代价高xilabelNilabelNni)(mod)(,01a1b2c1d1d2e1f112357111312=2*

19、16=3*210=5*27=7*177=11*791=13*7d117170=17*101153210NN1=1523N2=6N1=1139N2=7272NNNNN345NNNNN2022-8-930/65编码方案编码方案l为什么使用编码为什么使用编码l已有的解决方案已有的解决方案l已有更新方法已有更新方法l空间预留l浮点数编码l路径编码l素数编码l二进制位串将整数用二进制字符串表示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 si

20、ze=0(01,01001,001)(0101,011,001)g(010011,0100111,001)2022-8-931/65编码方案编码方案l为什么使用编码为什么使用编码l已有的解决方案已有的解决方案l已有更新方法已有更新方法l空间预留l浮点数编码l路径编码l素数编码l位串编码l向量编码将整数用向量表示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将插入整数变为插入向量2022-8-932/65编码方案编码方案l为什么使用编码为什么使用编码l已有的解决方案已有的解决方案

21、l已有更新方法已有更新方法l空间预留l浮点数编码l路径编码l素数编码l位串编码l向量编码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 182022-8-933/65编码方案编码方案l为什么使用编码为什么使用编码l已有的解决方案已有的解决方案l已有更新方法已有更新方法l空间预留l浮点数编码l路径编码l素数编码l位串编码l向量编码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

22、 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)2022-8-934/65编码方案编码方案l为什么使用编码为什么使用编码l已有的解决方案已有的解决方案l已有更新方法已有更新方法l基于图的编码基于图的编码l不支持更新2022-8-935/65编码方案编码方案l为什么使用编码为什么使用编码l已有的解决方案已有的解决方案l已有更新方法已有更新方法l基于图的编码基于图的编码l不支持更新l支持更新2022-8-936/65编码方案编码方案l为什么使用编码为什么使用编码l已有的解决方案已有的解决方案l实际问题实际问题

23、l可能的研究点可能的研究点l树上编码的更新l什么情况下可在两个值之间插入无穷多个值l图上编码的更新l如何将不同区间用一个值表示a1d2d12022-8-937/65内容介绍内容介绍l存储存储l存储策略l编码方案l索引索引l查询查询l查询改写l查询优化l查询算法2022-8-938/65索引索引l为什么使用索引为什么使用索引a1b1b2b3c1d1d2e1f1adQueryDocumentaa1dd1d22022-8-939/65索引索引l为什么使用索引为什么使用索引l索引的类型索引的类型l结构索引lTag 索引lStructural summaryl值索引l倒排表a1b1b2d3c1d1d2e

24、1f1bdQueryDocumentbb1dd1d2b2bb1dd1d2b2d3abcdefd2022-8-940/65索引索引l为什么使用索引为什么使用索引l索引的类型索引的类型l结构索引lF&B indexl1-index2022-8-941/65索引索引l为什么使用索引为什么使用索引l索引的类型索引的类型l结构索引lF&B indexl1-indexBDCBD2022-8-942/65内容介绍内容介绍l存储存储l存储策略l编码方案l索引索引l查询查询l查询改写查询改写l查询优化l查询算法2022-8-943/65查询改写查询改写l什么是查询改写什么是查询改写l用户提交查询Ql系统处理Q2

25、022-8-944/65查询改写查询改写l什么是查询改写什么是查询改写l为什么要查询改写为什么要查询改写l用户提交的查询表达能力有限：关键字查询l用户提交的查询有误a1b1b2d3c1d1d2e1f12022-8-945/65查询改写查询改写l什么是查询改写什么是查询改写l为什么要查询改写为什么要查询改写l查询改写的方式查询改写的方式l基于用户反馈l结果反馈l查询反馈l隐式反馈：无用户参与2022-8-946/651234XMLXMLIRIRindexindexFaginIRindex用户反馈用户反馈2.User marks relevant and nonrelevant docs3.Sys

26、tem finds best terms to distinguish between relevant and nonrelevant docs4.System submits expanded query1.User submits queryquery evaluationXML not(Fagin)Feedback for XML IR:Start with keyword query Find structural expansions Create structural query2022-8-947/65Tag+Content of other elements in the d

27、ocumentD:/authorBaeza /citationAbiteboulUser marksrelevant resultPath tothe resultP:article/body/sec/subsec用户反馈用户反馈secSemistructured data“articlebodysecsubsecXML has evolved“frontmatterbackmattersecsubsecpppWith the advent of XSLT“authorBaeza-Yates“Content ofresultPossible dimensions:C:XMLcitationSe

28、rge Abiteboul“2022-8-948/65用户反馈用户反馈XML SearchEnginefeedbackScoring+Rerankingexpanded queryqueryresultsreranked resultsContentModulePathModuleDocModuleFeedback Dimensionsquery+results2022-8-949/65查询改写查询改写l什么是查询改写什么是查询改写l为什么要查询改写为什么要查询改写l查询改写的方式查询改写的方式l基于用户反馈l伪反馈l又称局部反馈、盲反馈,它假设初始检索结果的前面若干篇文档是相关的,然后利用标

29、准的相关反馈过程进行查询扩展l隐式反馈l用户不主动参与反馈,但是系统仍需要从用户的浏览行为中分析得到一些有用的信息用来确定用户兴趣模式,从而推理出描述用户查询需求的表达式,并据此进行检索.l查询扩展l黄静的工作2022-8-950/65内容介绍内容介绍l存储存储l存储策略l编码方案l索引索引l查询查询l查询改写l查询优化查询优化l查询算法2022-8-951/65查询优化查询优化l种类种类l逻辑优化l物理优化2022-8-952/65查询优化查询优化l逻辑优化逻辑优化语法优化语义优化2022-8-953/65查询优化查询优化l物理优化物理优化l代价估计l单步代价估计l执行顺序l整体代价估计查询

30、：abcdefd2022-8-954/65内容介绍内容介绍l存储存储l存储策略l编码方案l索引索引l查询查询l查询改写l查询优化l查询算法查询算法2022-8-955/65查询算法查询算法-Twig查询处理查询处理l导航式导航式a1b1b2b3c1d1d2e1f1adQueryDocument2022-8-956/65查询算法查询算法-Twig查询处理查询处理l导航式导航式l结构连接结构连接l二元lPath连接l整体匹配abdcabbdaca1b1b2b3c1d1d2e1f13212abdac21大量中间结果2022-8-957/65查询算法查询算法-Twig查询处理查询处理l导航式导航式l结

31、构连接结构连接l二元二元lPath连接l整体匹配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)a3d2 a3d3a4d2 a4d3a6d4a6d5后代指针回指后代指针回指为什么？为什么？2022-8-958/65查询算法查询算法-Twig查询处理查询处理l导航式导航式l结构连接结构连接l二元二元lPath连接l整体匹配adr

32、d1a1a3a5a2a4f1d2d3a6d4d5d6a3a4d2d3a6d4d5ada1(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)a3d2 a3d3a4d2 a4d3a6d4a6d5a1(7,20)a2(14,19)a3(21,28)a4(22,27)a5(29,31)a6(32,40)2022-8-959/65查询算法查询算法-Twig查询处理查询处理l导航式导航式l结构连接结构连接l二元二元lPath连接连接l整体匹配A1B1A

33、2B2C1ABCXML DocQueryA1A2B1B2C1Result:A1 B1 C1A1 B2 C1A2 B2 C1SCSBSA2022-8-960/65查询算法查询算法-Twig查询处理查询处理l导航式导航式l结构连接结构连接l二元二元lPath连接连接l整体匹配整体匹配2022-8-961/65查询算法查询算法-Twig查询处理查询处理l导航式导航式l结构连接结构连接l二元二元lPath连接连接l整体匹配整体匹配a1a3a2b1b2b3c1c2c3c4c5c6a4b4c7c9c10c8c12b5c11a7a6a5abca7c12c8b4a7 c8a7 b4c9a7 c9c10a7 c

34、10c11a7 c11b5a7 b5a7 c12Stack aStack bStack cResult of A/CResult of A/B2022-8-962/65大纲大纲l简介简介l流程流程l内容内容l展望展望l总结总结2022-8-963/65研究展望研究展望l编码：图上可更新的编码方案l查询l静态文档：关键字查询，近似查询l数据流：关键字查询，近似查询l数据集成l概率XMLl时态XMLl数据仓库l数据挖掘l数据压缩l分布式XML与与OrientX不冲突不冲突2022-8-964/65总结总结l动机及准备工作动机及准备工作l系统架构系统架构l存储存储l存储策略l编码方案l索引索引l查询查询l查询改写l查询优化l查询算法l研究展望研究展望Data Storage ManagerData ManagerSchema ManagerIndex ManagerXML DataXML QueryQuery ResultExecute EngineData DefinitionXQueryXPathKeyword2022-8-965/65Thank you!