XML数据管理技术6课件

XML数据管理技术周军锋12/17/20221共2页XML数据管理技术周军锋12/16/20221共2页大纲简介流程内容总结12/17/20222大纲简介12/16/20222大纲简介流程内容总结12/17/20223大纲简介12/16/20223综述简介——必要性XML数据大量涌现Gartner[1]预测，XML文件的使用率在2007年达到40%，2008年将占据支配地位IDC（国际数据公司）报告显示，在500家受访企业的IT部门中，有29％正在大量使用XML数据库XML研究如火如荼每年各种学术会议期刊发表XML相关论文多达300篇没有系统的总结和比较发表时间早：大部分出现在06年左右内容局限性：主要涉及查询，索引[1].in/summit/eform/technical-papers/gartneruseofxml.pdf/view12/17/20224综述简介——必要性XML数据大量涌现12/16/20224综述简介——信息源要求全面性06-08年各种会议期刊国际会议国际期刊国内会议国内期刊12/17/20225综述简介——信息源要求12/16/20225综述简介——信息源国际会议(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:应用相关的会议关注的会议较好的workshop12/17/20226综述简介——信息源国际会议关注的会议较好的workshop1综述简介——信息源国际期刊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

12/17/20227综述简介——信息源国际期刊12/16/20227综述简介——信息源国内会议NDBC国内期刊计算机学报软件学报计算机研究与发展计算机科学与探索12/17/20228综述简介——信息源国内会议12/16/20228综述简介——内容提炼12/17/20229综述简介——内容提炼12/16/20229综述简介——内容提炼如何压缩内容？06-08：200/812，2005年以前的？已有综述中阐述的内容，直接引用并总结对所有新内容分类整理，得到需要的类别对每一类中的文章，去除重复文章尽量引用大会文章12/17/202210综述简介——内容提炼如何压缩内容？12/16/202210综述简介——内容提炼分类整理，去除重复：150/360/700/80012/17/202211综述简介——内容提炼分类整理，去除重复：150/360/70大纲简介流程内容总结12/17/202212大纲简介12/16/202212综述流程DataStorageManagerDataManagerSchemaManagerIndexManagerXMLDataXMLQueryQueryResultExecuteEngineDataDefinitionXQueryXPath…Keyword建立数据库导入/出文档执行查询12/17/202213综述流程DataStorageManagerDat综述流程DataStorageManagerDataManagerSchemaManagerIndexManagerXMLDataXMLQueryQueryResultExecuteEngineDataDefinitionXQueryXPath…Keyword建立数据库12/17/202214综述流程DataStorageManagerDat综述流程DataStorageManagerDataManagerSchemaManagerIndexManagerXMLDataXMLQueryQueryResultExecuteEngineDataDefinitionXQueryXPath…Keyword建立数据库导入/出文档12/17/202215综述流程DataStorageManagerDat综述流程DataStorageManagerDataManagerSchemaManagerIndexManagerXMLDataXMLQueryQueryResultExecuteEngineDataDefinitionXQueryXPath…Keyword建立数据库导入/出文档执行查询QueryParserQueryOptimizerQueryEvaluatorExecuteEnginePeople/person/profile/gender12/17/202216综述流程DataStorageManagerDat综述流程DataStorageManagerDataManagerSchemaManagerIndexManagerXMLDataXMLQueryQueryResultExecuteEngineDataDefinitionXQueryXPath…Keyword研究点存储存储策略编码方案索引查询查询改写查询优化查询算法12/17/202217综述流程DataStorageManagerDat大纲简介流程内容总结12/17/202218大纲简介12/16/202218内容介绍存储存储策略编码方案索引查询查询改写查询优化查询算法12/17/202219内容介绍存储12/16/202219存储策略关系表查询导出文档Native方式混合方式问题Benchmark文档类型文本数据。。。attributesvaluenameid12/17/202220存储策略关系表。。。attributesvaluenamei内容介绍存储存储策略编码方案索引查询查询改写查询优化查询算法12/17/202221内容介绍存储12/16/202221编码方案为什么使用编码导航不可行a1b1b2b3c1d1d2e1f1adQueryDocument如何判断元素之间的关系？aa1dd1d2仅处理tag名为a和d的元素，可以减少处理的元素数量12/17/202222编码方案为什么使用编码a1b1b2b3c1d1d2e1f1a编码方案为什么使用编码已有的解决方案区间编码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)12/17/202223编码方案为什么使用编码a1b1b2b3c1d1d2e1f1a编码方案为什么使用编码已有的解决方案区间编码路径编码a1b1b2b3c1d1d2e1f1adQueryDocumentad..1.4.212/17/202224编码方案为什么使用编码a1b1b2b3c1d1d2e1f1a编码方案为什么使用编码已有的解决方案实际问题文档更新插入叶子节点插入非叶子节点节点编码需要更新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)1618ga1b1b2b3c1d1d2e1f.1.4.2gggg12/17/202225编码方案为什么使用编码adQueryDocumenta1b1编码方案为什么使用编码已有的解决方案已有更新方法空间预留无法避免重新编码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)16018012/17/202226编码方案为什么使用编码adQueryDocumenta1b1编码方案为什么使用编码已有的解决方案已有更新方法空间预留浮点数编码无法避免重新编码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)12/17/202227编码方案为什么使用编码adQueryDocumenta1b1编码方案为什么使用编码已有的解决方案已有更新方法空间预留浮点数编码路径编码ORDPATH代价高a1b1b2b4c1d1d2e1f1a1b1b4c1e1f.3b21.2.1d1d2b21.2.3b312/17/202228编码方案为什么使用编码a1b1b2b4c1d1d2e1f1a编码方案为什么使用编码已有的解决方案已有更新方法空间预留浮点数编码路径编码素数编码可避免更新编码N值计算代价高a1b2c1d1d2e1f112357111312=2*16=3*210=5*27=7*177=11*791=13*7d117170=17*10N1=1523N2=6N1=1139N2=7272NNNNN345NNNNN12/17/202229编码方案为什么使用编码a1b2c1d1d2e1f112357编码方案为什么使用编码已有的解决方案已有更新方法空间预留浮点数编码路径编码素数编码二进制位串将整数用二进制字符串表示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)12/17/202230编码方案为什么使用编码将整数用二进制字符串表示a1b1b2b编码方案为什么使用编码已有的解决方案已有更新方法空间预留浮点数编码路径编码素数编码位串编码向量编码将整数用向量表示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将插入整数变为插入向量12/17/202231编码方案为什么使用编码将整数用向量表示a1b1b2b3c1d编码方案为什么使用编码已有的解决方案已有更新方法空间预留浮点数编码路径编码素数编码位串编码向量编码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)161812/17/202232编码方案为什么使用编码a1b1b2b3c1d1d2e1f1(编码方案为什么使用编码已有的解决方案已有更新方法空间预留浮点数编码路径编码素数编码位串编码向量编码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)12/17/202233编码方案为什么使用编码a1b1b2b3c1d1d2e1f1(编码方案为什么使用编码已有的解决方案已有更新方法基于图的编码不支持更新12/17/202234编码方案为什么使用编码12/16/202234编码方案为什么使用编码已有的解决方案已有更新方法基于图的编码不支持更新支持更新12/17/202235编码方案为什么使用编码12/16/202235编码方案为什么使用编码已有的解决方案实际问题可能的研究点树上编码的更新什么情况下可在两个值之间插入无穷多个值图上编码的更新如何将不同区间用一个值表示a1d2d112/17/202236编码方案为什么使用编码a1d2d112/16/202236内容介绍存储存储策略编码方案索引查询查询改写查询优化查询算法12/17/202237内容介绍存储12/16/202237索引为什么使用索引a1b1b2b3c1d1d2e1f1adQueryDocumentaa1dd1d212/17/202238索引为什么使用索引a1b1b2b3c1d1d2e1f1adQ索引为什么使用索引索引的类型结构索引Tag索引Structuralsummary值索引倒排表a1b1b2d3c1d1d2e1f1bdQueryDocumentbb1dd1d2b2bb1dd1d2b2d3abcdefd12/17/202239索引为什么使用索引a1b1b2d3c1d1d2e1f1bdQ索引为什么使用索引索引的类型结构索引F&Bindex1-index12/17/202240索引为什么使用索引12/16/202240索引为什么使用索引索引的类型结构索引F&Bindex1-indexBDCBD12/17/202241索引为什么使用索引BDCBD12/16/202241内容介绍存储存储策略编码方案索引查询查询改写查询优化查询算法12/17/202242内容介绍存储12/16/202242查询改写什么是查询改写用户提交查询Q系统处理Q’12/17/202243查询改写什么是查询改写12/16/202243查询改写什么是查询改写为什么要查询改写用户提交的查询表达能力有限：关键字查询用户提交的查询有误a1b1b2d3c1d1d2e1f112/17/202244查询改写什么是查询改写a1b1b2d3c1d1d2e1f11查询改写什么是查询改写为什么要查询改写查询改写的方式基于用户反馈结果反馈查询反馈隐式反馈：无用户参与12/17/202245查询改写什么是查询改写12/16/2022451234…XMLXMLIRIRindexindexFaginIRindex用户反馈2.Usermarksrelevantand

nonrelevantdocs3.Systemfindsbesttermstodistinguishbetweenrelevantandnonrelevantdocs4.Systemsubmitsexpanded

query1.UsersubmitsqueryqueryevaluationXML

not(Fagin)FeedbackforXMLIR:StartwithkeywordqueryFindstructuralexpansionsCreatestructuralquery12/17/2022461234…XMLXMLIRIRindexindexFaginTag+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“12/17/202247Tag+Contentofother

elements用户反馈XMLSearch

EnginefeedbackScoring+RerankingexpandedqueryqueryresultsrerankedresultsContentModulePathModuleDocModule…FeedbackDimensionsquery+results12/17/202248用户反馈XMLSearch

EnginefeedbackS查询改写什么是查询改写为什么要查询改写查询改写的方式基于用户反馈伪反馈又称局部反馈、盲反馈,它假设初始检索结果的前面若干篇文档是相关的,然后利用标准的相关反馈过程进行查询扩展隐式反馈用户不主动参与反馈,但是系统仍需要从用户的浏览行为中分析得到一些有用的信息用来确定用户兴趣模式,从而推理出描述用户查询需求的表达式,并据此进行检索.查询扩展黄静的工作12/17/202249查询改写什么是查询改写12/16/202249内容介绍存储存储策略编码方案索引查询查询改写查询优化查询算法12/17/202250内容介绍存储12/16/202250查询优化种类逻辑优化物理优化12/17/202251查询优化种类12/16/202251查询优化逻辑优化语法优化语义优化12/17/202252查询优化逻辑优化语法优化语义优化12/16/202252查询优化物理优化代价估计单步代价估计执行顺序整体代价估计查询：abcdefd√12/17/202253查询优化物理优化查询：abcdefd√12/16/20225内容介绍存储存储策略编码方案索引查询查询改写查询优化查询算法12/17/202254内容介绍存储12/16/202254查询算法-Twig查询处理导航式a1b1b2b3c1d1d2e1f1adQueryDocument12/17/202255查询算法-Twig查询处理导航式a1b1b2b3c1d1d2查询算法-Twig查询处理导航式结构连接二元Path连接整体匹配abdcabbdaca1b1b2b3c1d1d2e1f13212abdac21大量中间结果12/17/202256查询算法-Twig查询处理导航式abdcabbdaca1b1查询算法-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后代指针回指为什么？12/17/202257查询算法-Twig查询处理导航式adrd1a1a3a5a2a查询算法-Twig查询处理导航式结构连接二元Path连接整体匹配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)a3d2a3d3a4d2a4d3a6d4a6d5a1(7,20)a2(14,19)a3(21,28)a4(22,27)a5(29,31)a6(32,40)12/17/202258查询算法-Twig查询处理导航式adrd1a1a3a5a2a查询算法-Twig查询处理导航式结构连接二元Path连接整体匹配A1B1A2B2C1ABCXMLDocQueryA1A2B1B2C1Result:A1B1C1A1B2C1A2B2C1SCSBSA12/17/202259查询算法-Twig查询处理导航式A1B1A2B2C1ABCX查询算法-Twig查询处理导航式结构连接二元Path连接整体匹配12/17/202260查询算法-Twig查询处理导航式12/16/202260查询算法-Twig查询处理导航式结构连接二元Path连接整体匹配a7c12c8b4a7c8a7b4c9a7c9c10a7c10c11a7c11b5a7b5a7c12StackaStackbStackcResultofA//CResultofA//B12/17/202261查询算法-Twig查询处理导航式a7c12c8b4a7c8大纲简介流程内容展望总结12/17/202262大纲简介12/16/202262研究展望编码：图上可更新的编码方案查询静态文档：关键字查询，近似查询数据流：关键字查询，近似查询数据集成概率XML时态XML数据仓库数据挖掘数据压缩分布式XML√√与OrientX不冲突12/17/202263研究展望编码：图上可更新的编码方案√√与OrientX不冲突总结动机及准备工作系统架构存储存储策略编码方案索引查询查询改写查询优化查询算法研究展望DataStorageManagerDataManagerSchemaManagerIndexManagerXMLDataXMLQueryQueryResultExecuteEngineDataDefinitionXQueryXPath…Keyword12/17/202264总结动机及准备工作DataStorageManagThankyou!12/17/202265Thankyou!12/16/202265XML数据管理技术周军锋12/17/202266共2页XML数据管理技术周军锋12/16/20221共2页大纲简介流程内容总结12/17/202267大纲简介12/16/20222大纲简介流程内容总结12/17/202268大纲简介12/16/20223综述简介——必要性XML数据大量涌现Gartner[1]预测，XML文件的使用率在2007年达到40%，2008年将占据支配地位IDC（国际数据公司）报告显示，在500家受访企业的IT部门中，有29％正在大量使用XML数据库XML研究如火如荼每年各种学术会议期刊发表XML相关论文多达300篇没有系统的总结和比较发表时间早：大部分出现在06年左右内容局限性：主要涉及查询，索引[1].in/summit/eform/technical-papers/gartneruseofxml.pdf/view12/17/202269综述简介——必要性XML数据大量涌现12/16/20224综述简介——信息源要求全面性06-08年各种会议期刊国际会议国际期刊国内会议国内期刊12/17/202270综述简介——信息源要求12/16/20225综述简介——信息源国际会议(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:应用相关的会议关注的会议较好的workshop12/17/202271综述简介——信息源国际会议关注的会议较好的workshop1综述简介——信息源国际期刊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

12/17/202272综述简介——信息源国际期刊12/16/20227综述简介——信息源国内会议NDBC国内期刊计算机学报软件学报计算机研究与发展计算机科学与探索12/17/202273综述简介——信息源国内会议12/16/20228综述简介——内容提炼12/17/202274综述简介——内容提炼12/16/20229综述简介——内容提炼如何压缩内容？06-08：200/812，2005年以前的？已有综述中阐述的内容，直接引用并总结对所有新内容分类整理，得到需要的类别对每一类中的文章，去除重复文章尽量引用大会文章12/17/202275综述简介——内容提炼如何压缩内容？12/16/202210综述简介——内容提炼分类整理，去除重复：150/360/700/80012/17/202276综述简介——内容提炼分类整理，去除重复：150/360/70大纲简介流程内容总结12/17/202277大纲简介12/16/202212综述流程DataStorageManagerDataManagerSchemaManagerIndexManagerXMLDataXMLQueryQueryResultExecuteEngineDataDefinitionXQueryXPath…Keyword建立数据库导入/出文档执行查询12/17/202278综述流程DataStorageManagerDat综述流程DataStorageManagerDataManagerSchemaManagerIndexManagerXMLDataXMLQueryQueryResultExecuteEngineDataDefinitionXQueryXPath…Keyword建立数据库12/17/202279综述流程DataStorageManagerDat综述流程DataStorageManagerDataManagerSchemaManagerIndexManagerXMLDataXMLQueryQueryResultExecuteEngineDataDefinitionXQueryXPath…Keyword建立数据库导入/出文档12/17/202280综述流程DataStorageManagerDat综述流程DataStorageManagerDataManagerSchemaManagerIndexManagerXMLDataXMLQueryQueryResultExecuteEngineDataDefinitionXQueryXPath…Keyword建立数据库导入/出文档执行查询QueryParserQueryOptimizerQueryEvaluatorExecuteEnginePeople/person/profile/gender12/17/202281综述流程DataStorageManagerDat综述流程DataStorageManagerDataManagerSchemaManagerIndexManagerXMLDataXMLQueryQueryResultExecuteEngineDataDefinitionXQueryXPath…Keyword研究点存储存储策略编码方案索引查询查询改写查询优化查询算法12/17/202282综述流程DataStorageManagerDat大纲简介流程内容总结12/17/202283大纲简介12/16/202218内容介绍存储存储策略编码方案索引查询查询改写查询优化查询算法12/17/202284内容介绍存储12/16/202219存储策略关系表查询导出文档Native方式混合方式问题Benchmark文档类型文本数据。。。attributesvaluenameid12/17/202285存储策略关系表。。。attributesvaluenamei内容介绍存储存储策略编码方案索引查询查询改写查询优化查询算法12/17/202286内容介绍存储12/16/202221编码方案为什么使用编码导航不可行a1b1b2b3c1d1d2e1f1adQueryDocument如何判断元素之间的关系？aa1dd1d2仅处理tag名为a和d的元素，可以减少处理的元素数量12/17/202287编码方案为什么使用编码a1b1b2b3c1d1d2e1f1a编码方案为什么使用编码已有的解决方案区间编码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)12/17/202288编码方案为什么使用编码a1b1b2b3c1d1d2e1f1a编码方案为什么使用编码已有的解决方案区间编码路径编码a1b1b2b3c1d1d2e1f1adQueryDocumentad..1.4.212/17/202289编码方案为什么使用编码a1b1b2b3c1d1d2e1f1a编码方案为什么使用编码已有的解决方案实际问题文档更新插入叶子节点插入非叶子节点节点编码需要更新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)1618ga1b1b2b3c1d1d2e1f.1.4.2gggg12/17/202290编码方案为什么使用编码adQueryDocumenta1b1编码方案为什么使用编码已有的解决方案已有更新方法空间预留无法避免重新编码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)16018012/17/202291编码方案为什么使用编码adQueryDocumenta1b1编码方案为什么使用编码已有的解决方案已有更新方法空间预留浮点数编码无法避免重新编码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)12/17/202292编码方案为什么使用编码adQueryDocumenta1b1编码方案为什么使用编码已有的解决方案已有更新方法空间预留浮点数编码路径编码ORDPATH代价高a1b1b2b4c1d1d2e1f1a1b1b4c1e1f.3b21.2.1d1d2b21.2.3b312/17/202293编码方案为什么使用编码a1b1b2b4c1d1d2e1f1a编码方案为什么使用编码已有的解决方案已有更新方法空间预留浮点数编码路径编码素数编码可避免更新编码N值计算代价高a1b2c1d1d2e1f112357111312=2*16=3*210=5*27=7*177=11*791=13*7d117170=17*10N1=1523N2=6N1=1139N2=7272NNNNN345NNNNN12/17/202294编码方案为什么使用编码a1b2c1d1d2e1f112357编码方案为什么使用编码已有的解决方案已有更新方法空间预留浮点数编码路径编码素数编码二进制位串将整数用二进制字符串表示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)12/17/202295编码方案为什么使用编码将整数用二进制字符串表示a1b1b2b编码方案为什么使用编码已有的解决方案已有更新方法空间预留浮点数编码路径编码素数编码位串编码向量编码将整数用向量表示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将插入整数变为插入向量12/17/202296编码方案为什么使用编码将整数用向量表示a1b1b2b3c1d编码方案为什么使用编码已有的解决方案已有更新方法空间预留浮点数编码路径编码素数编码位串编码向量编码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)161812/17/202297编码方案为什么使用编码a1b1b2b3c1d1d2e1f1(编码方案为什么使用编码已有的解决方案已有更新方法空间预留浮点数编码路径编码素数编码位串编码向量编码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)12/17/202298编码方案为什么使用编码a1b1b2b3c1d1d2e1f1(编码方案为什么使用编码已有的解决方案已有更新方法基于图的编码不支持更新12/17/202299编码方案为什么使用编码12/16/202234编码方案为什么使用编码已有的解决方案已有更新方法基于图的编码不支持更新支持更新12/17/2022100编码方案为什么使用编码12/16/202235编码方案为什么使用编码已有的解决方案实际问题可能的研究点树上编码的更新什么情况下可在两个值之间插入无穷多个值图上编码的更新如何将不同区间用一个值表示a1d2d112/17/2022101编码方案为什么使用编码a1d2d112/16/202236内容介绍存储存储策略编码方案索引查询查询改写查询优化查询算法12/17/2022102内容介绍存储12/16/202237索引为什么使用索引a1b1b2b3c1d1d2e1f1adQueryDocumentaa1dd1d212/17/2022103索引为什么使用索引a1b1b2b3c1d1d2e1f1adQ索引为什么使用索引索引的类型结构索引Tag索引Structuralsummary值索引倒排表a1b1b2d3c1d1d2e1f1bdQueryDocumentbb1dd1d2b2bb1dd1d2b2d3abcdefd12/17/2022104索引为什么使用索引a1b1b2d3c1d1d2e1f1bdQ索引为什么使用索引索引的类型结构索引F&Bindex1-index12/17/2022105索引为什么使用索引12/16/202240索引为什么使用索引索引的类型结构索引F&Bindex1-indexBDCBD12/17/2022106索引为什么使用索引BDCBD12/16/202241内容介绍存储存储策略编码方案索引查询查询改写查询优化查询算法12/17/2022107内容介绍存储12/16/202242查询改写什么是查询改写用户提交查询Q系统处理Q’12/17/2022108查询改写什么是查询改写12/16/202243查询改写什么是查询改写为什么要查询改写用户提交的查询表达能力有限：关键字查询用户提交的查询有误a1b1b2d3c1d1d2e1f112/17/2022109查询改写什么是查询改写a1b1b2d3c1d1d2e1f11查询改写什么是查询改写为什么要查询改写查询改写的方式基于用户反馈结果反馈查询反馈隐式反馈：无用户参与12/17/2022110查询改写什么是查询改写12/16/2022451234…XMLXMLIRIRindexindexFaginIRindex用户反馈2.Usermarksrelevantand

nonrelevantdocs3.Systemfindsbesttermstodistinguishbetweenrelevantandnonrelevantdocs4.Systemsubmitsexpanded

query1.UsersubmitsqueryqueryevaluationXML

not(Fagin)FeedbackforXMLIR:StartwithkeywordqueryFindstructuralexpansionsCreatestructuralquery12/17/20221111234…XMLXMLIRIRindexindexFaginTag+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“12/17/2022112Tag+Contentofother

elements用户反馈XMLSearch

EnginefeedbackScoring+RerankingexpandedqueryqueryresultsrerankedresultsContentModulePathModuleDocModule…FeedbackDimensionsquery+results12/17/2022113用户反馈XMLSearch

EnginefeedbackS查询改写什么是查询改写为什么要查询改写查询改写的方式基于用户反馈伪