《XML数据管理技术.ppt》由会员分享，可在线阅读，更多相关《XML数据管理技术.ppt（65页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、XML数据管理技术数据管理技术周军锋周军锋1/27/20231大纲大纲l简介简介l流程流程l内容内容l总结总结1/27/20232大纲大纲l简介简介l流程流程l内容内容l总结总结1/27/20233综述简介综述简介必要性必要性lXML数据大量涌现数据大量涌现lGartner1预测，XML文件的使用率在l2007年达到40%，l2008年将占据支配地位lIDC（国际数据公司）报告显示，在500家受访企业的IT部门中，有29正在大量使用XML数据库 lXML研究如火如荼研究如火如荼l每年各种学术会议期刊发表XML相关论文多达300篇l没有系统的总结和比较没有系统的总结和比较l发表时间早：大部分出现
2、在06年左右l内容局限性：主要涉及查询，索引1/27/20234综述简介综述简介信息源信息源l要求要求l全面性l06-08年各种会议期刊年各种会议期刊l国际会议l国际期刊l国内会议l国内期刊1/27/20235综述简介综述简介信息源信息源l国际会议国际会议l(ACM)SIGMOD ：(Association for Computing Machinery)Special Interest Group on Management of DatalVLDB :International Conference on Very Large Data BaseslICDE :International
3、Conference on Data Engineering lEDBT:International Conference on Extending Database Technology lWWW:International Conference on World Wide WeblCIKM :International Conference on Information and Knowledge Management lDASFAA:Database Systems for Advanced Applications lER :International Conference on th
4、e Entity Relationship Approach lPODS :Symposium on Principles of Database Systems lSIGIR :International Conference on Research and Development in Information Retrieval lICDT :International Conference on Database Theory lDEXA :Database and Expert Systems Applications lCIDR :Conference on Innovative D
5、ata 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 and Databases lINEX :INitiative for the Evaluation of XML Retrieval lXIME-P:Workshop on XQuery
6、 IMplementation,Experience and Perspectives lXSym :International XML Database Symposium （08年不存在了）lXML Conference:应用相关的会议应用相关的会议关注的会议关注的会议较好的较好的workshop1/27/20236综述简介综述简介信息源信息源l国际期刊国际期刊lVLDBJ：The VLDB Journal lTODS：ACM Transactions on Database Systems lTKDE：IEEE Transactions on Knowledge and Data Eng
7、ineeringlTOIS：ACM Transactions on Information Systems lJACM：Journal of the ACM lCACM：Communications of the ACM lIS：Information SystemlIR：Information RetrievallKIS：Knowledge and Information SystemlSIGMOD-Record lDKE：Data&Knowledge Engineering lJDM：Journal of Database Management lWWWJ：World Wide Web l
8、JCST：Journal of Computer Science and Technology 1/27/20237综述简介综述简介信息源信息源l国内会议国内会议lNDBCl国内期刊国内期刊l计算机学报l软件学报l计算机研究与发展l计算机科学与探索1/27/20238综述简介综述简介内容提炼内容提炼1/27/20239综述简介综述简介内容提炼内容提炼l如何压缩内容？如何压缩内容？l06-08：200/812，2005年以前的？l已有综述中阐述的内容，已有综述中阐述的内容，直接引用并总结直接引用并总结l对所有新内容对所有新内容分类整理分类整理，得到需要的类别，得到需要的类别l对每一类中的文章，对
9、每一类中的文章，去除重复去除重复文章文章l尽量引用大会文章1/27/202310综述简介综述简介内容提炼内容提炼l分类整理，去除重复：分类整理，去除重复：150/360/700/8001/27/202311大纲大纲l简介简介l流程流程l内容内容l总结总结1/27/202312综述流程综述流程Data Storage ManagerData ManagerSchema ManagerIndex ManagerXML DataXML QueryQuery ResultExecute EngineData DefinitionXQueryXPathKeywordl建立数据库建立数据库l导入导入/出文
10、档出文档l执行查询执行查询1/27/202313综述流程综述流程Data Storage ManagerData ManagerSchema ManagerIndex ManagerXML DataXML QueryQuery ResultExecute EngineData DefinitionXQueryXPathKeywordl建立数据库建立数据库1/27/202314综述流程综述流程Data Storage ManagerData ManagerSchema ManagerIndex ManagerXML DataXML QueryQuery ResultExecute EngineD
11、ata DefinitionXQueryXPathKeywordl建立数据库建立数据库l导入导入/出文档出文档1/27/202315综述流程综述流程Data Storage ManagerData ManagerSchema ManagerIndex ManagerXML DataXML QueryQuery ResultExecute EngineData DefinitionXQueryXPathKeywordl建立数据库建立数据库l导入导入/出文档出文档l执行查询执行查询Query ParserQuery OptimizerQuery EvaluatorExecute EnginePeo
12、ple/person/profile/gender1/27/202316综述流程综述流程Data Storage ManagerData ManagerSchema ManagerIndex ManagerXML DataXML QueryQuery ResultExecute EngineData DefinitionXQueryXPathKeywordl研究点研究点l存储l存储策略l编码方案l索引l查询l查询改写l查询优化l查询算法1/27/202317大纲大纲l简介简介l流程流程l内容内容l总结总结1/27/202318内容介绍内容介绍l存储存储l存储策略存储策略l编码方案l索引索引l查
13、询查询l查询改写l查询优化l查询算法1/27/202319存储策略存储策略l关系表关系表l查询l导出文档lNative 方式方式l混合方式混合方式l问题问题lBenchmarkl文档类型l文本l数据。attributesvaluenameid1/27/202320内容介绍内容介绍l存储存储l存储策略l编码方案编码方案l索引索引l查询查询l查询改写l查询优化l查询算法1/27/202321编码方案编码方案l为什么使用编码为什么使用编码l导航不可行导航不可行a1b1b2b3c1d1d2e1f1adQueryDocument如何判断元素之间的关系？aa1dd1d2仅处理tag名为a和d的元素，可以减
14、少处理的元素数量1/27/202322编码方案编码方案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,3)16 18 1 18 5 6 7 8ad(1,18,1)(5,6,3)(7,8,3)1/27/202323编码方案编码方案l为什么使用编码为什么使用编码l已有的解决方案已有的解决方案l区间编码l路径编码路径编码a1b1b2b3c1d1d2e1f1ad
15、QueryDocumentad11.2.11.2.211.11.21.31.41/27/202324编码方案编码方案l为什么使用编码为什么使用编码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 18ga1b1b2b3c1d1d2e1f111.11.21.31.4gggg1/27/202325编码方案编码方案l为什么使用编码为什么使用编码l已有的解决方
16、案已有的解决方案l已有更新方法已有更新方法l空间预留l无法避免重新编码adQueryDocumenta1b1b2b3c1d1d2e1f1(10,1)(20,2)30(40,2)(50,3)60(70,3)8090(100,2)110(120,2)170(130,3)140(150,3)160 1801/27/202326编码方案编码方案l为什么使用编码为什么使用编码l已有的解决方案已有的解决方案l已有更新方法已有更新方法l空间预留l浮点数编码l无法避免重新编码adQueryDocumenta1b1b2b3c1d1d2e1f1(1,1)(2,2)3(4,2)(5,3)6(7,3)89(10,2)
17、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)1/27/202327编码方案编码方案l为什么使用编码为什么使用编码l已有的解决方案已有的解决方案l已有更新方法已有更新方法l空间预留l浮点数编码l路径编码ORDPATHl代价高a1b1b2b4c1d1d2e1f1a1b1b4c1e1f111.11.31.5b2d11.2.1.1d21.2.1.3b21.2.3b31/27/202328编码方案编码方案l为什么使用编码为什么使用编码l已有的解决方案已有的解决方
18、案l已有更新方法已有更新方法l空间预留l浮点数编码l路径编码l素数编码l可避免更新编码lN值计算代价高a1b2c1d1d2e1f112357111312=2*16=3*210=5*27=7*177=11*791=13*7d117170=17*10N1=1523N2=6N1=1139N2=7272NNNNN345NNNNN1/27/202329编码方案编码方案l为什么使用编码为什么使用编码l已有的解决方案已有的解决方案l已有更新方法已有更新方法l空间预留l浮点数编码l路径编码l素数编码l二进制位串将整数用二进制字符串表示a1b1b2b3c1d1d2e1f1(1,1)(2,2)3(4,2)(5,3
19、)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)1/27/202330编码方案编码方案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)
20、16 18将插入整数变为插入向量1/27/202331编码方案编码方案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 181/27/202332编码方案编码方案l为什么使用编码为什么使用编码l已有的解决方案已有的解决方案l已有更新方法已有更新方法l空间预留l浮点数编码l路径编码l素数编码l位串编码l向量编码a1b1b2b3c1d1d2e1
21、f1(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)1/27/202333编码方案编码方案l为什么使用编码为什么使用编码l已有的解决方案已有的解决方案l已有更新方法已有更新方法l基于图的编码基于图的编码l不支持更新1/27/202334编码方案编码方案l为什么使用编码为什么使用编码l已有的解决方案已有的解决方案l已有更新方法已有更新方法l基于图的编码基于图的编码l不支持更新l支持更新1
22、/27/202335编码方案编码方案l为什么使用编码为什么使用编码l已有的解决方案已有的解决方案l实际问题实际问题l可能的研究点可能的研究点l树上编码的更新l什么情况下可在两个值之间插入无穷多个值l图上编码的更新l如何将不同区间用一个值表示a1d2d11/27/202336内容介绍内容介绍l存储存储l存储策略l编码方案l索引索引l查询查询l查询改写l查询优化l查询算法1/27/202337索引索引l为什么使用索引为什么使用索引a1b1b2b3c1d1d2e1f1adQueryDocumentaa1dd1d21/27/202338索引索引l为什么使用索引为什么使用索引l索引的类型索引的类型l结构
23、索引lTag 索引lStructural summaryl值索引l倒排表a1b1b2d3c1d1d2e1f1bdQueryDocumentbb1dd1d2b2bb1dd1d2b2d3abcdefd1/27/202339索引索引l为什么使用索引为什么使用索引l索引的类型索引的类型l结构索引lF&B indexl1-index1/27/202340索引索引l为什么使用索引为什么使用索引l索引的类型索引的类型l结构索引lF&B indexl1-indexBDCBD1/27/202341内容介绍内容介绍l存储存储l存储策略l编码方案l索引索引l查询查询l查询改写查询改写l查询优化l查询算法1/27/2
24、02342查询改写查询改写l什么是查询改写什么是查询改写l用户提交查询Ql系统处理Q1/27/202343查询改写查询改写l什么是查询改写什么是查询改写l为什么要查询改写为什么要查询改写l用户提交的查询表达能力有限：关键字查询l用户提交的查询有误a1b1b2d3c1d1d2e1f11/27/202344查询改写查询改写l什么是查询改写什么是查询改写l为什么要查询改写为什么要查询改写l查询改写的方式查询改写的方式l基于用户反馈l结果反馈l查询反馈l隐式反馈：无用户参与1/27/2023451234XMLXMLIRIRindexindexFaginIRindex用户反馈用户反馈2.User mar
25、ks relevant and nonrelevant docs3.System 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 query1/27/202346Tag
26、+Content of other elements in the documentD:/authorBaeza /citationAbiteboulUser marksrelevant resultPath tothe resultP:article/body/sec/subsec用户反馈用户反馈secSemistructured data“articlebodysecsubsecXML has evolved“frontmatterbackmattersecsubsecpppWith the advent of XSLT“authorBaeza-Yates“Content ofresult
27、Possible dimensions:C:XMLcitationSerge Abiteboul“1/27/202347用户反馈用户反馈XML SearchEnginefeedbackScoring+Rerankingexpanded queryqueryresultsreranked resultsContentModulePathModuleDocModuleFeedback Dimensionsquery+results1/27/202348查询改写查询改写l什么是查询改写什么是查询改写l为什么要查询改写为什么要查询改写l查询改写的方式查询改写的方式l基于用户反馈l伪反馈l又称局部反馈、
28、盲反馈,它假设初始检索结果的前面若干篇文档是相关的,然后利用标准的相关反馈过程进行查询扩展l隐式反馈l用户不主动参与反馈,但是系统仍需要从用户的浏览行为中分析得到一些有用的信息用来确定用户兴趣模式,从而推理出描述用户查询需求的表达式,并据此进行检索.l查询扩展l黄静的工作1/27/202349内容介绍内容介绍l存储存储l存储策略l编码方案l索引索引l查询查询l查询改写l查询优化查询优化l查询算法1/27/202350查询优化查询优化l种类种类l逻辑优化l物理优化1/27/202351查询优化查询优化l逻辑优化逻辑优化语法优化语义优化1/27/202352查询优化查询优化l物理优化物理优化l代价
29、估计l单步代价估计l执行顺序l整体代价估计查询：abcdefd1/27/202353内容介绍内容介绍l存储存储l存储策略l编码方案l索引索引l查询查询l查询改写l查询优化l查询算法查询算法1/27/202354查询算法查询算法-Twig查询处理查询处理l导航式导航式a1b1b2b3c1d1d2e1f1adQueryDocument1/27/202355查询算法查询算法-Twig查询处理查询处理l导航式导航式l结构连接结构连接l二元lPath连接l整体匹配abdcabbdaca1b1b2b3c1d1d2e1f13212abdac21大量中间结果1/27/202356查询算法查询算法-Twig查询
30、处理查询处理l导航式导航式l结构连接结构连接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后代指针回指后代指针回指为什么？为什么？1/27/202357查询算法查询算法-Twig查询处理查询处理l导航式导航式l结构连接结构连接l二元二元lP
31、ath连接l整体匹配adrd1a1a3a5a2a4f1d2d3a6d4d5d6a3a4d2d3a6d4d5ada1(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)1/27/202358查询算法查询算法-Twig查询处理查询处理l导航式导航式l结构连接结构连接l二元二元lPath连接连
32、接l整体匹配A1B1A2B2C1ABCXML DocQueryA1A2B1B2C1Result:A1 B1 C1A1 B2 C1A2 B2 C1SCSBSA1/27/202359查询算法查询算法-Twig查询处理查询处理l导航式导航式l结构连接结构连接l二元二元lPath连接连接l整体匹配整体匹配1/27/202360查询算法查询算法-Twig查询处理查询处理l导航式导航式l结构连接结构连接l二元二元lPath连接连接l整体匹配整体匹配a7c12c8b4a7 c8a7 b4c9a7 c9c10a7 c10c11a7 c11b5a7 b5a7 c12Stack aStack bStack cRe
33、sult of A/CResult of A/B1/27/202361大纲大纲l简介简介l流程流程l内容内容l展望展望l总结总结1/27/202362研究展望研究展望l编码：图上可更新的编码方案l查询l静态文档：关键字查询，近似查询l数据流：关键字查询，近似查询l数据集成l概率XMLl时态XMLl数据仓库l数据挖掘l数据压缩l分布式XML与与OrientX不冲突不冲突1/27/202363总结总结l动机及准备工作动机及准备工作l系统架构系统架构l存储存储l存储策略l编码方案l索引索引l查询查询l查询改写l查询优化l查询算法l研究展望研究展望Data Storage ManagerData ManagerSchema ManagerIndex ManagerXML DataXML QueryQuery ResultExecute EngineData DefinitionXQueryXPathKeyword1/27/202364Thank you!1/27/202365