XML数据管理技术

2022/12/211/65大纲简介流程内容总结2022/12/212/65大纲简介流程内容总结2022/12/213/65综述简介——必要性XML数据大量涌现Gartner[1]预测，XML文件的使用率在2007年达到40%，2008年将占据支配地位IDC（国际数据公司）报告显示，在500家受访企业的IT部门中，有29％正在大量使用XML数据库XML研究如火如荼每年各种学术会议期刊发表XML相关论文多达300篇没有系统的总结和比较发表时间早：大部分出现在06年左右内容局限性：主要涉及查询，索引2022/12/214/65综述简介——信息源要求全面性06-08年各种会议期刊国际会议国际期刊国内会议国内期刊2022/12/215/65综述简介——信息源国际会议(ACM)SIGMOD

：(AssociationforComputingMachinery)SpecialInterestGrouponManagementofDataVLDB:InternationalConferenceonVeryLargeDataBasesICDE:InternationalConferenceonDataEngineeringEDBT:InternationalConferenceonExtendingDatabaseTechnologyWWW:InternationalConferenceonWorldWideWebCIKM:InternationalConferenceonInformationandKnowledgeManagementDASFAA:DatabaseSystemsforAdvancedApplicationsER:InternationalConferenceontheEntityRelationshipApproachPODS:SymposiumonPrinciplesofDatabaseSystemsSIGIR:InternationalConferenceonResearchandDevelopmentinInformationRetrievalICDT:InternationalConferenceonDatabaseTheoryDEXA:DatabaseandExpertSystemsApplicationsCIDR:ConferenceonInnovativeDataSystemsResearchWISE:WebInformationSystemsEngineeringWAIM:InternationalConferenceonWeb-AgeInformationManagementAPWeb:Asia-PacificWebConferenceWebDB:InternationalWorkshopontheWebandDatabasesINEX:INitiativefortheEvaluationofXMLRetrievalXIME-P:WorkshoponXQueryIMplementation,ExperienceandPerspectivesXSym:InternationalXMLDatabaseSymposium（08年不存在了）XMLConference:应用相关的会议关注的会议较好的workshop2022/12/216/65综述简介——信息源国际期刊VLDBJ：TheVLDBJournal

TODS：ACMTransactionsonDatabaseSystems

TKDE

：IEEETransactionsonKnowledgeandDataEngineeringTOIS：ACMTransactionsonInformationSystems

JACM

：JournaloftheACM

CACM

：CommunicationsoftheACM

IS：InformationSystemIR：InformationRetrievalKIS：KnowledgeandInformationSystemSIGMOD-Record

DKE：Data&KnowledgeEngineering

JDM：JournalofDatabaseManagement

WWWJ：WorldWideWeb

JCST：JournalofComputerScienceandTechnology

2022/12/217/65综述简介——信息源国内会议NDBC国内期刊计算机学报软件学报计算机研究与发展计算机科学与探索2022/12/218/65综述简介——内容提炼2022/12/219/65综述简介——内容提炼如何压缩内容？06-08：200/812，2005年以前的？已有综述中阐述的内容，直接引用并总结对所有新内容分类整理，得到需要的类别对每一类中的文章，去除重复文章尽量引用大会文章2022/12/2110/65综述简介——内容提炼分类整理，去除重复：150/360/700/8002022/12/2111/65大纲简介流程内容总结2022/12/2112/65综述流程DataStorageManagerDataManagerSchemaManagerIndexManagerXMLDataXMLQueryQueryResultExecuteEngineDataDefinitionXQueryXPath…Keyword建立数据库导入/出文档执行查询2022/12/2113/65综述流程DataStorageManagerDataManagerSchemaManagerIndexManagerXMLDataXMLQueryQueryResultExecuteEngineDataDefinitionXQueryXPath…Keyword建立数据库2022/12/2114/65综述流程DataStorageManagerDataManagerSchemaManagerIndexManagerXMLDataXMLQueryQueryResultExecuteEngineDataDefinitionXQueryXPath…Keyword建立数据库导入/出文档2022/12/2115/65综述流程DataStorageManagerDataManagerSchemaManagerIndexManagerXMLDataXMLQueryQueryResultExecuteEngineDataDefinitionXQueryXPath…Keyword建立数据库导入/出文档执行查询QueryParserQueryOptimizerQueryEvaluatorExecuteEnginePeople/person/profile/gender2022/12/2116/65综述流程DataStorageManagerDataManagerSchemaManagerIndexManagerXMLDataXMLQueryQueryResultExecuteEngineDataDefinitionXQueryXPath…Keyword研究点存储存储策略编码方案索引查询查询改写查询优化查询算法2022/12/2117/65大纲简介流程内容总结2022/12/2118/65内容介绍存储存储策略编码方案索引查询查询改写查询优化查询算法2022/12/2119/65存储策略关系表查询导出文档Native方式混合方式问题Benchmark文档类型文本数据。。。attributesvaluenameid2022/12/2120/65内容介绍存储存储策略编码方案索引查询查询改写查询优化查询算法2022/12/2121/65编码方案为什么使用编码导航不可行a1b1b2b3c1d1d2e1f1adQueryDocument如何判断元素之间的关系？aa1dd1d2仅处理tag名为a和d的元素，可以减少处理的元素数量2022/12/2122/65编码方案为什么使用编码已有的解决方案区间编码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)16181185678ad(1,18,1)(5,6,3)(7,8,3)2022/12/2123/65编码方案为什么使用编码已有的解决方案区间编码路径编码a1b1b2b3c1d1d2e1f1adQueryDocumentad.1.42022/12/2124/65编码方案为什么使用编码已有的解决方案实际问题文档更新插入叶子节点插入非叶子节点节点编码需要更新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)1618ga1b1b2b3c1d1d2e1f1.4gggg2022/12/2125/65编码方案为什么使用编码已有的解决方案已有更新方法空间预留无法避免重新编码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)1601802022/12/2126/65编码方案为什么使用编码已有的解决方案已有更新方法空间预留浮点数编码无法避免重新编码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)1618g1g2(110.01,110.11,3)(101,110,3)(111,1000,3)(110.1101,110.1111,3)2022/12/2127/65编码方案为什么使用编码已有的解决方案已有更新方法空间预留浮点数编码路径编码ORDPATH代价高a1b1b2b4c1d1d2e1f1a1b1b4c1e1fb2d1d2b21.2.3b32022/12/2128/65编码方案为什么使用编码已有的解决方案已有更新方法空间预留浮点数编码路径编码素数编码可避免更新编码N值计算代价高a1b2c1d1d2e1f112357111312=2*16=3*210=5*27=7*177=11*791=13*7d117170=17*10N1=1523N2=6N1=1139N2=7272NNNNN345NNNNN2022/12/2129/65编码方案为什么使用编码已有的解决方案已有更新方法空间预留浮点数编码路径编码素数编码二进制位串将整数用二进制字符串表示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)1618将插入整数变为插入字符串0size=019size=0(01,01001,001)(0101,011,001)g(010011,0100111,001)2022/12/2130/65编码方案为什么使用编码已有的解决方案已有更新方法空间预留浮点数编码路径编码素数编码位串编码向量编码将整数用向量表示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)1618将插入整数变为插入向量2022/12/2131/65编码方案为什么使用编码已有的解决方案已有更新方法空间预留浮点数编码路径编码素数编码位串编码向量编码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)16182022/12/2132/65编码方案为什么使用编码已有的解决方案已有更新方法空间预留浮点数编码路径编码素数编码位串编码向量编码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)161818=(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/12/2133/65编码方案为什么使用编码已有的解决方案已有更新方法基于图的编码不支持更新2022/12/2134/65编码方案为什么使用编码已有的解决方案已有更新方法基于图的编码不支持更新支持更新2022/12/2135/65编码方案为什么使用编码已有的解决方案实际问题可能的研究点树上编码的更新什么情况下可在两个值之间插入无穷多个值图上编码的更新如何将不同区间用一个值表示a1d2d12022/12/2136/65内容介绍存储存储策略编码方案索引查询查询改写查询优化查询算法2022/12/2137/65索引为什么使用索引a1b1b2b3c1d1d2e1f1adQueryDocumentaa1dd1d22022/12/2138/65索引为什么使用索引索引的类型结构索引Tag索引Structuralsummary值索引倒排表a1b1b2d3c1d1d2e1f1bdQueryDocumentbb1dd1d2b2bb1dd1d2b2d3abcdefd2022/12/2139/65索引为什么使用索引索引的类型结构索引F&Bindex1-index2022/12/2140/65索引为什么使用索引索引的类型结构索引F&Bindex1-indexBDCBD2022/12/2141/65内容介绍存储存储策略编码方案索引查询查询改写查询优化查询算法2022/12/2142/65查询改写什么是查询改写用户提交查询Q系统处理Q’2022/12/2143/65查询改写什么是查询改写为什么要查询改写用户提交的查询表达能力有限：关键字查询用户提交的查询有误a1b1b2d3c1d1d2e1f12022/12/2144/65查询改写什么是查询改写为什么要查询改写查询改写的方式基于用户反馈结果反馈查询反馈隐式反馈：无用户参与2022/12/2145/651234…XMLXMLIRIRindexindexFaginIRindex用户反馈2.Usermarksrelevantand

nonrelevantdocs3.Systemfindsbesttermstodistinguishbetweenrelevantandnonrelevantdocs4.Systemsubmitsexpanded

query1.UsersubmitsqueryqueryevaluationXML

not(Fagin)FeedbackforXMLIR:StartwithkeywordqueryFindstructuralexpansionsCreatestructuralquery2022/12/2146/65Tag+Contentofother

elementsinthedocumentD://author[Baeza]

//citation[Abiteboul]Usermarks

relevantresultPathto

theresultP:article/body/sec/subsec用户反馈sec„Semistructureddata…“articlebodysecsubsec

„XMLhasevolved…“frontmatterbackmattersecsubsecppp

„WiththeadventofXSLT…“author

„Baeza-Yates“Contentof

resultPossibledimensions:C:XMLcitation

„SergeAbiteboul“2022/12/2147/65用户反馈XMLSearch

EnginefeedbackScoring+RerankingexpandedqueryqueryresultsrerankedresultsContentModulePathModuleDocModule…FeedbackDimensionsquery+results2022/12/2148/65查询改写什么是查询改写为什么要查询改写查询改写的方式基于用户反馈伪反馈又称局部反馈、盲反馈,它假设初始检索结果的前面若干篇文档是相关的,然后利用标准的相关反馈过程进行查询扩展隐式反馈用户不主动参与反馈,但是系统仍需要从用户的浏览行为中分析得到一些有用的信息用来确定用户兴趣模式,从而推理出描述用户查询需求的表达式,并据此进行检索.查询扩展黄静的工作2022/12/2149/65内容介绍存储存储策略编码方案索引查询查询改写查询优化查询算法2022/12/2150/65查询优化种类逻辑优化物理优化2022/12/2151/65查询优化逻辑优化语法优化语义优化2022/12/2152/65查询优化物理优化代价估计单步代价估计执行顺序整体代价估计查询：abcdefd√2022/12/2153/65内容介绍存储存储策略编码方案索引查询查询改写查询优化查询算法2022/12/2154/65查询算法-Twig查询处理导航式a1b1b2b3c1d1d2e1f1adQueryDocument2022/12/2155/65查询算法-Twig查询处理导航式结构连接二元Path连接整体匹配abdcabbdaca1b1b2b3c1d1d2e1f13212abdac21大量中间结果2022/12/2156/65查询算法-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后代指针回指为什么？2022/12/2157/65查询算法-Twig查询处理导航式结构连接二元Path连接整体匹配adrd1a1a3a5a2a4f1d2d3a6