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

第6頁/共65頁2023/3/137/65綜述簡介——信息源國內會議NDBC國內期刊計算機學報軟件學報計算機研究與發(fā)展計算機科學與探索第7頁/共65頁2023/3/138/65綜述簡介——內容提煉第8頁/共65頁2023/3/139/65綜述簡介——內容提煉如何壓縮內容？06-08：200/812，2005年以前的？已有綜述中闡述的內容，直接引用并總結對所有新內容分類整理，得到需要的類別對每一類中的文章，去除重復文章盡量引用大會文章第9頁/共65頁2023/3/1310/65綜述簡介——內容提煉分類整理，去除重復：150/360/700/800第10頁/共65頁2023/3/1311/65大綱簡介流程內容總結第11頁/共65頁2023/3/1312/65綜述流程DataStorageManagerDataManagerSchemaManagerIndexManagerXMLDataXMLQueryQueryResultExecuteEngineDataDefinitionXQueryXPath…Keyword建立數據庫導入/出文檔執(zhí)行查詢第12頁/共65頁2023/3/1313/65綜述流程DataStorageManagerDataManagerSchemaManagerIndexManagerXMLDataXMLQueryQueryResultExecuteEngineDataDefinitionXQueryXPath…Keyword建立數據庫第13頁/共65頁2023/3/1314/65綜述流程DataStorageManagerDataManagerSchemaManagerIndexManagerXMLDataXMLQueryQueryResultExecuteEngineDataDefinitionXQueryXPath…Keyword建立數據庫導入/出文檔第14頁/共65頁2023/3/1315/65綜述流程DataStorageManagerDataManagerSchemaManagerIndexManagerXMLDataXMLQueryQueryResultExecuteEngineDataDefinitionXQueryXPath…Keyword建立數據庫導入/出文檔執(zhí)行查詢QueryParserQueryOptimizerQueryEvaluatorExecuteEnginePeople/person/profile/gender第15頁/共65頁2023/3/1316/65綜述流程DataStorageManagerDataManagerSchemaManagerIndexManagerXMLDataXMLQueryQueryResultExecuteEngineDataDefinitionXQueryXPath…Keyword研究點存儲存儲策略編碼方案索引查詢查詢改寫查詢優(yōu)化查詢算法第16頁/共65頁2023/3/1317/65大綱簡介流程內容總結第17頁/共65頁2023/3/1318/65內容介紹存儲存儲策略編碼方案索引查詢查詢改寫查詢優(yōu)化查詢算法第18頁/共65頁2023/3/1319/65存儲策略關系表查詢導出文檔Native方式混合方式問題Benchmark文檔類型文本數據。。。attributesvaluenameid第19頁/共65頁2023/3/1320/65內容介紹存儲存儲策略編碼方案索引查詢查詢改寫查詢優(yōu)化查詢算法第20頁/共65頁2023/3/1321/65編碼方案為什么使用編碼導航不可行a1b1b2b3c1d1d2e1f1adQueryDocument如何判斷元素之間的關系？aa1dd1d2僅處理tag名為a和d的元素，可以減少處理的元素數量第21頁/共65頁2023/3/1322/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)第22頁/共65頁2023/3/1323/65編碼方案為什么使用編碼已有的解決方案區(qū)間編碼路徑編碼a1b1b2b3c1d1d2e1f1adQueryDocumentad..1.4.2第23頁/共65頁2023/3/1324/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)1618ga1b1b2b3c1d1d2e1f.1.4.2gggg第24頁/共65頁2023/3/1325/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)160180第25頁/共65頁2023/3/1326/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)第26頁/共65頁2023/3/1327/65編碼方案為什么使用編碼已有的解決方案已有更新方法空間預留浮點數編碼路徑編碼ORDPATH代價高a1b1b2b4c1d1d2e1f1a1b1b4c1e1f.3b21.2.1d1d2b21.2.3b3第27頁/共65頁2023/3/1328/65編碼方案為什么使用編碼已有的解決方案已有更新方法空間預留浮點數編碼路徑編碼素數編碼可避免更新編碼N值計算代價高a1b2c1d1d2e1f112357111312=2*16=3*210=5*27=7*177=11*791=13*7d117170=17*10N1=1523N2=6N1=1139N2=7272NNNNN345NNNNN第28頁/共65頁2023/3/1329/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將插入整數變?yōu)椴迦胱址?size=019size=0(01,01001,001)(0101,011,001)g(010011,0100111,001)第29頁/共65頁2023/3/1330/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將插入整數變?yōu)椴迦胂蛄康?0頁/共65頁2023/3/1331/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第31頁/共65頁2023/3/1332/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)第32頁/共65頁2023/3/1333/65編碼方案為什么使用編碼已有的解決方案已有更新方法基于圖的編碼不支持更新第33頁/共65頁2023/3/1334/65編碼方案為什么使用編碼已有的解決方案已有更新方法基于圖的編碼不支持更新支持更新第34頁/共65頁2023/3/1335/65編碼方案為什么使用編碼已有的解決方案實際問題可能的研究點樹上編碼的更新什么情況下可在兩個值之間插入無窮多個值圖上編碼的更新如何將不同區(qū)間用一個值表示a1d2d1第35頁/共65頁2023/3/1336/65內容介紹存儲存儲策略編碼方案索引查詢查詢改寫查詢優(yōu)化查詢算法第36頁/共65頁2023/3/1337/65索引為什么使用索引a1b1b2b3c1d1d2e1f1adQueryDocumentaa1dd1d2第37頁/共65頁2023/3/1338/65索引為什么使用索引索引的類型結構索引Tag索引Structuralsummary值索引倒排表a1b1b2d3c1d1d2e1f1bdQueryDocumentbb1dd1d2b2bb1dd1d2b2d3abcdefd第38頁/共65頁2023/3/1339/65索引為什么使用索引索引的類型結構索引F&Bindex1-index第39頁/共65頁2023/3/1340/65索引為什么使用索引索引的類型結構索引F&Bindex1-indexBDCBD第40頁/共65頁2023/3/1341/65內容介紹存儲存儲策略編碼方案索引查詢查詢改寫查詢優(yōu)化查詢算法第41頁/共65頁2023/3/1342/65查詢改寫什么是查詢改寫用戶提交查詢Q系統處理Q’第42頁/共65頁2023/3/1343/65查詢改寫什么是查詢改寫為什么要查詢改寫用戶提交的查詢表達能力有限：關鍵字查詢用戶提交的查詢有誤a1b1b2d3c1d1d2e1f1第43頁/共65頁2023/3/1344/65查詢改寫什么是查詢改寫為什么要查詢改寫查詢改寫的方式基于用戶反饋結果反饋查詢反饋隱式反饋：無用戶參與第44頁/共65頁2023/3/1345/651234…XMLXMLIRIRindexindexFaginIRindex用戶反饋2.Usermarksrelevantand

nonrelevantdocs3.Systemfindsbesttermstodistinguishbetweenrelevantandnonrelevantdocs4.Systemsubmitsexpanded

query1.UsersubmitsqueryqueryevaluationXML

not(Fagin)FeedbackforXMLIR:StartwithkeywordqueryFindstructuralexpansionsCreatestructuralquery第45頁/共65頁2023/3/1346/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“第46頁/共65頁2023/3/1347/65用戶反饋XMLSearch

EnginefeedbackScoring+RerankingexpandedqueryqueryresultsrerankedresultsContentModulePathModuleDocModule…FeedbackDimensionsquery+results第47頁/共65頁2023/3/1348/65查詢改寫什么是查詢改寫為什么要查詢改寫查詢改寫的方式基于用戶反饋偽反饋又稱局部反饋、盲反饋,它假設初始檢索結果的前面若干篇文檔是相關的,然后利用標準的相關反饋過程進行查詢擴展隱式反饋用戶不主動參與反饋,但是系統仍需要從用戶的瀏覽行為中分析得到一些有用的信息用來確定用戶興趣模式,從而推理出描述用戶查詢需求的表達式,并據此進行檢索.查詢擴展黃靜的工作第48頁/共65頁2023/3/1349/65內容介紹存儲存儲策略編碼方案索引查詢查詢改寫查詢優(yōu)化查詢算法第49頁/共65頁2023/3/1350/65查詢優(yōu)化種類邏輯優(yōu)化物理優(yōu)化第50頁/共65頁2023/3/1351/65查詢優(yōu)化邏輯優(yōu)化語法優(yōu)化語義優(yōu)化第51頁/共65頁2023/3/1352/65查詢優(yōu)化物理優(yōu)化代價估計單步代價估計執(zhí)行順序整體代價估計查詢：abcdefd√第52頁/共65頁2023/3/1353/65內容介紹存儲存儲策略編碼方案索引查詢查詢改寫查詢優(yōu)化查詢算法第53頁/共65頁2023/3/1354/65查詢算法-Twig查詢處理導航式a1b1b2b3c1d1d2e1f1adQueryDocument第54頁/共65頁2023/3/1355/65查詢算法-Twig查詢處理導航式結構連接二元Path連接整體匹配abdcabbdaca1b1b2b3c1d1d2e1f13212abdac21大量中間結果第55頁/共65頁2023/3/1356/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后代指針回指為什么？第56頁/共65頁2023/3/1357/65查詢算法-Twig查詢處理導航式結構連接二元Path連接整體匹配adrd1a1a3a5a2a4f1d2d3a6d4d5d6a3a4d2d3a6d4d5ada