XML數(shù)據(jù)管理技術

XML數(shù)據(jù)管理技術周軍鋒2024/5/102/65大綱簡介流程內(nèi)容總結2024/5/103/65大綱簡介流程內(nèi)容總結2024/5/104/65綜述簡介——必要性XML數(shù)據(jù)大量涌現(xiàn)Gartner[1]預測，XML文件的使用率在2007年達到40%，2008年將占據(jù)支配地位IDC（國際數(shù)據(jù)公司）報告顯示，在500家受訪企業(yè)的IT部門中，有29％正在大量使用XML數(shù)據(jù)庫XML研究如火如荼每年各種學術會議期刊發(fā)表XML相關論文多達300篇沒有系統(tǒng)的總結和比較發(fā)表時間早：大部分出現(xiàn)在06年左右內(nèi)容局限性：主要涉及查詢，索引[1].in/summit/eform/technical-papers/gartneruseofxml.pdf/view2024/5/105/65綜述簡介——信息源要求全面性06-08年各種會議期刊國際會議國際期刊國內(nèi)會議國內(nèi)期刊2024/5/106/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:應用相關的會議關注的會議較好的workshop2024/5/107/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

2024/5/108/65綜述簡介——信息源國內(nèi)會議NDBC國內(nèi)期刊計算機學報軟件學報計算機研究與發(fā)展計算機科學與探索2024/5/109/65綜述簡介——內(nèi)容提煉2024/5/1010/65綜述簡介——內(nèi)容提煉如何壓縮內(nèi)容？06-08：200/812，2005年以前的？已有綜述中闡述的內(nèi)容，直接引用并總結對所有新內(nèi)容分類整理，得到需要的類別對每一類中的文章，去除重復文章盡量引用大會文章2024/5/1011/65綜述簡介——內(nèi)容提煉分類整理，去除重復：150/360/700/8002024/5/1012/65大綱簡介流程內(nèi)容總結2024/5/1013/65綜述流程DataStorageManagerDataManagerSchemaManagerIndexManagerXMLDataXMLQueryQueryResultExecuteEngineDataDefinitionXQueryXPath…Keyword建立數(shù)據(jù)庫導入/出文檔執(zhí)行查詢2024/5/1014/65綜述流程DataStorageManagerDataManagerSchemaManagerIndexManagerXMLDataXMLQueryQueryResultExecuteEngineDataDefinitionXQueryXPath…Keyword建立數(shù)據(jù)庫2024/5/1015/65綜述流程DataStorageManagerDataManagerSchemaManagerIndexManagerXMLDataXMLQueryQueryResultExecuteEngineDataDefinitionXQueryXPath…Keyword建立數(shù)據(jù)庫導入/出文檔2024/5/1016/65綜述流程DataStorageManagerDataManagerSchemaManagerIndexManagerXMLDataXMLQueryQueryResultExecuteEngineDataDefinitionXQueryXPath…Keyword建立數(shù)據(jù)庫導入/出文檔執(zhí)行查詢QueryParserQueryOptimizerQueryEvaluatorExecuteEnginePeople/person/profile/gender2024/5/1017/65綜述流程DataStorageManagerDataManagerSchemaManagerIndexManagerXMLDataXMLQueryQueryResultExecuteEngineDataDefinitionXQueryXPath…Keyword研究點存儲存儲策略編碼方案索引查詢查詢改寫查詢優(yōu)化查詢算法2024/5/1018/65大綱簡介流程內(nèi)容總結2024/5/1019/65內(nèi)容介紹存儲存儲策略編碼方案索引查詢查詢改寫查詢優(yōu)化查詢算法2024/5/1020/65存儲策略關系表查詢導出文檔Native方式混合方式問題Benchmark文檔類型文本數(shù)據(jù)。。。attributesvaluenameid2024/5/1021/65內(nèi)容介紹存儲存儲策略編碼方案索引查詢查詢改寫查詢優(yōu)化查詢算法2024/5/1022/65編碼方案為什么使用編碼導航不可行a1b1b2b3c1d1d2e1f1adQueryDocument如何判斷元素之間的關系？aa1dd1d2僅處理tag名為a和d的元素，可以減少處理的元素數(shù)量2024/5/1023/65編碼方案為什么使用編碼已有的解決方案區(qū)間編碼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)2024/5/1024/65編碼方案為什么使用編碼已有的解決方案區(qū)間編碼路徑編碼a1b1b2b3c1d1d2e1f1adQueryDocumentad11.2.11.2.211.11.21.2.11.2.21.31.41.4.11.4.22024/5/1025/65編碼方案為什么使用編碼已有的解決方案實際問題文檔更新插入葉子節(jié)點插入非葉子節(jié)點節(jié)點編碼需要更新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)1618ga1b1b2b3c1d1d2e1f111.11.21.2.11.2.21.31.41.4.11.4.2gggg2024/5/1026/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)1601802024/5/1027/65編碼方案為什么使用編碼已有的解決方案已有更新方法空間預留浮點數(shù)編碼無法避免重新編碼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)2024/5/1028/65編碼方案為什么使用編碼已有的解決方案已有更新方法空間預留浮點數(shù)編碼路徑編碼ORDPATH代價高a1b1b2b4c1d1d2e1f1a1b1b4c1e1f111.11.31.51.5.11.5.3b21.2.1d1d2b21.2.3b32024/5/1029/65編碼方案為什么使用編碼已有的解決方案已有更新方法空間預留浮點數(shù)編碼路徑編碼素數(shù)編碼可避免更新編碼N值計算代價高a1b2c1d1d2e1f112357111312=2*16=3*210=5*27=7*177=11*791=13*7d117170=17*10N1=1523N2=6N1=1139N2=7272NNNNN345NNNNN2024/5/1030/65編碼方案為什么使用編碼已有的解決方案已有更新方法空間預留浮點數(shù)編碼路徑編碼素數(shù)編碼二進制位串將整數(shù)用二進制字符串表示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將插入整數(shù)變?yōu)椴迦胱址?size=019size=0(01,01001,001)(0101,011,001)g(010011,0100111,001)2024/5/1031/65編碼方案為什么使用編碼已有的解決方案已有更新方法空間預留浮點數(shù)編碼路徑編碼素數(shù)編碼位串編碼向量編碼將整數(shù)用向量表示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將插入整數(shù)變?yōu)椴迦胂蛄?024/5/1032/65編碼方案為什么使用編碼已有的解決方案已有更新方法空間預留浮點數(shù)編碼路徑編碼素數(shù)編碼位串編碼向量編碼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)16182024/5/1033/65編碼方案為什么使用編碼已有的解決方案已有更新方法空間預留浮點數(shù)編碼路徑編碼素數(shù)編碼位串編碼向量編碼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)2024/5/1034/65編碼方案為什么使用編碼已有的解決方案已有更新方法基于圖的編碼不支持更新2024/5/1035/65編碼方案為什么使用編碼已有的解決方案已有更新方法基于圖的編碼不支持更新支持更新2024/5/1036/65編碼方案為什么使用編碼已有的解決方案實際問題可能的研究點樹上編碼的更新什么情況下可在兩個值之間插入無窮多個值圖上編碼的更新如何將不同區(qū)間用一個值表示a1d2d12024/5/1037/65內(nèi)容介紹存儲存儲策略編碼方案索引查詢查詢改寫查詢優(yōu)化查詢算法2024/5/1038/65索引為什么使用索引a1b1b2b3c1d1d2e1f1adQueryDocumentaa1dd1d22024/5/1039/65索引為什么使用索引索引的類型結構索引Tag索引Structuralsummary值索引倒排表a1b1b2d3c1d1d2e1f1bdQueryDocumentbb1dd1d2b2bb1dd1d2b2d3abcdefd2024/5/1040/65索引為什么使用索引索引的類型結構索引F&Bindex1-index2024/5/1041/65索引為什么使用索引索引的類型結構索引F&Bindex1-indexBDCBD2024/5/1042/65內(nèi)容介紹存儲存儲策略編碼方案索引查詢查詢改寫查詢優(yōu)化查詢算法2024/5/1043/65查詢改寫什么是查詢改寫用戶提交查詢Q系統(tǒng)處理Q’2024/5/1044/65查詢改寫什么是查詢改寫為什么要查詢改寫用戶提交的查詢表達能力有限：關鍵字查詢用戶提交的查詢有誤a1b1b2d3c1d1d2e1f12024/5/1045/65查詢改寫什么是查詢改寫為什么要查詢改寫查詢改寫的方式基于用戶反饋結果反饋查詢反饋隱式反饋：無用戶參與2024/5/1046/651234…XMLXMLIRIRindexindexFaginIRindex用戶反饋2.Usermarksrelevantand

nonrelevantdocs3.Systemfindsbesttermstodistinguishbetweenrelevantandnonrelevantdocs4.Systemsubmitsexpanded

query1.UsersubmitsqueryqueryevaluationXML

not(Fagin)FeedbackforXMLIR:StartwithkeywordqueryFindstructuralexpansionsCreatestructuralquery2024/5/1047/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“2024/5/1048/65用戶反饋XMLSearch

EnginefeedbackScoring+RerankingexpandedqueryqueryresultsrerankedresultsContentModulePathModuleDocModule…FeedbackDimensionsquery+results2024/5/1049/65查詢改寫什么是查詢改寫為什么要查詢改寫查詢改寫的方式基于用戶反饋偽反饋又稱局部反饋、盲反饋,它假設初始檢索結果的前面若干篇文檔是相關的,然后利用標準的相關反饋過程進行查詢擴展隱式反饋用戶不主動參與反饋,但是系統(tǒng)仍需要從用戶的瀏覽行為中分析得到一些有用的信息用來確定用戶興趣模式,從而推理出描述用戶查詢需求的表達式,并據(jù)此進行檢索.查詢擴展黃靜的工作2024/5/1050/65內(nèi)容介紹存儲存儲策略編碼方案索引查詢查詢改寫查詢優(yōu)化查詢算法2024/5/1051/65查詢優(yōu)化種類邏輯優(yōu)化物理優(yōu)化2024/5/1052/65查詢優(yōu)化邏輯優(yōu)化語法優(yōu)化語義優(yōu)化2024/5/1053/65查詢優(yōu)化物理優(yōu)化代價估計單步代價估計執(zhí)行順序整體代價估計查詢：abcdefd√2024/5/1054/65內(nèi)容介紹存儲存儲策略編碼方案索引查詢查詢改寫查詢優(yōu)化查詢算法2024/5/1055/65查詢算法-Twig查詢處理導航式a1b1b2b3c1d1d2e1f1adQueryDocument2024/5/1056/65查詢算法-Twig查詢處理導航式結構連接二元Path連接整體匹配abdcabbdaca1b1b2b3c1d1d2e1f13212abdac21大量中間結果2024/5/1057/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后代指針回指為什么？2024/5/1058/65查詢算法-Twig查詢處理導航式結構連接二元Path連接整體匹配adrd1a1a3a5a2