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

1、XML數(shù)據(jù)管理技術(shù)周軍鋒7/19/20221精選ppt大綱簡(jiǎn)介流程內(nèi)容總結(jié)7/19/20222大綱簡(jiǎn)介流程內(nèi)容總結(jié)7/19/20223綜述簡(jiǎn)介必要性XML數(shù)據(jù)大量涌現(xiàn)Gartner1預(yù)測(cè)，XML文件的使用率在2007年達(dá)到40%，2008年將占據(jù)支配地位IDC（國(guó)際數(shù)據(jù)公司）報(bào)告顯示，在500家受訪企業(yè)的IT部門中，有29正在大量使用XML數(shù)據(jù)庫(kù) XML研究如火如荼每年各種學(xué)術(shù)會(huì)議期刊發(fā)表XML相關(guān)論文多達(dá)300篇沒(méi)有系統(tǒng)的總結(jié)和比較發(fā)表時(shí)間早：大部分出現(xiàn)在06年左右內(nèi)容局限性：主要涉及查詢，索引1.in/summit/eform/technical-papers/gartneruseofxm

2、l.pdf/view7/19/20224綜述簡(jiǎn)介信息源要求全面性06-08年各種會(huì)議期刊國(guó)際會(huì)議國(guó)際期刊國(guó)內(nèi)會(huì)議國(guó)內(nèi)期刊7/19/20225綜述簡(jiǎn)介信息源國(guó)際會(huì)議(ACM) SIGMOD ： (Association for Computing Machinery) Special Interest Group on Management of DataVLDB : International Conference on Very Large Data BasesICDE : International Conference on Data Engineering EDBT : Interna

3、tional Conference on Extending Database Technology WWW : International Conference on World Wide WebCIKM : International Conference on Information and Knowledge Management DASFAA : Database Systems for Advanced Applications ER : International Conference on the Entity Relationship Approach PODS : Symp

4、osium on Principles of Database Systems SIGIR : International Conference on Research and Development in Information Retrieval ICDT : International Conference on Database Theory DEXA : Database and Expert Systems Applications CIDR : Conference on Innovative Data Systems Research WISE : Web Informatio

5、n Systems Engineering WAIM : International Conference on Web-Age Information Management APWeb : Asia-Pacific Web Conference WebDB : International Workshop on the Web and Databases INEX : INitiative for the Evaluation of XML Retrieval XIME-P : Workshop on XQuery IMplementation, Experience and Perspec

6、tives XSym : International XML Database Symposium （08年不存在了）XML Conference : 應(yīng)用相關(guān)的會(huì)議關(guān)注的會(huì)議較好的workshop7/19/20226綜述簡(jiǎn)介信息源國(guó)際期刊VLDBJ ：The VLDB Journal TODS ： ACM Transactions on Database Systems TKDE ： IEEE Transactions on Knowledge and Data EngineeringTOIS ： ACM Transactions on Information Systems JACM ：

7、Journal of the ACM CACM ： Communications of the ACM IS ： Information SystemIR ： Information RetrievalKIS： Knowledge and Information SystemSIGMOD-Record DKE ： Data & Knowledge Engineering JDM ： Journal of Database Management WWWJ ：World Wide Web JCST ： Journal of Computer Science and Technology 7/19/

8、20227綜述簡(jiǎn)介信息源國(guó)內(nèi)會(huì)議NDBC國(guó)內(nèi)期刊計(jì)算機(jī)學(xué)報(bào)軟件學(xué)報(bào)計(jì)算機(jī)研究與發(fā)展計(jì)算機(jī)科學(xué)與探索7/19/20228綜述簡(jiǎn)介內(nèi)容提煉7/19/20229綜述簡(jiǎn)介內(nèi)容提煉如何壓縮內(nèi)容？06-08：200/812，2005年以前的？已有綜述中闡述的內(nèi)容，直接引用并總結(jié)對(duì)所有新內(nèi)容分類整理，得到需要的類別對(duì)每一類中的文章，去除重復(fù)文章盡量引用大會(huì)文章7/19/202210綜述簡(jiǎn)介內(nèi)容提煉分類整理，去除重復(fù)：150/360/700/8007/19/202211大綱簡(jiǎn)介流程內(nèi)容總結(jié)7/19/202212綜述流程Data Storage ManagerData ManagerSchema Manager

9、Index ManagerXML DataXML QueryQuery ResultExecute EngineData DefinitionXQueryXPathKeyword建立數(shù)據(jù)庫(kù)導(dǎo)入/出文檔執(zhí)行查詢7/19/202213綜述流程Data Storage ManagerData ManagerSchema ManagerIndex ManagerXML DataXML QueryQuery ResultExecute EngineData DefinitionXQueryXPathKeyword建立數(shù)據(jù)庫(kù)7/19/202214綜述流程Data Storage ManagerData M

10、anagerSchema ManagerIndex ManagerXML DataXML QueryQuery ResultExecute EngineData DefinitionXQueryXPathKeyword建立數(shù)據(jù)庫(kù)導(dǎo)入/出文檔7/19/202215綜述流程Data Storage ManagerData ManagerSchema ManagerIndex ManagerXML DataXML QueryQuery ResultExecute EngineData DefinitionXQueryXPathKeyword建立數(shù)據(jù)庫(kù)導(dǎo)入/出文檔執(zhí)行查詢Query ParserQue

11、ry OptimizerQuery EvaluatorExecute EnginePeople/person/profile/gender7/19/202216綜述流程Data Storage ManagerData ManagerSchema ManagerIndex ManagerXML DataXML QueryQuery ResultExecute EngineData DefinitionXQueryXPathKeyword研究點(diǎn)存儲(chǔ)存儲(chǔ)策略編碼方案索引查詢查詢改寫查詢優(yōu)化查詢算法7/19/202217大綱簡(jiǎn)介流程內(nèi)容總結(jié)7/19/202218內(nèi)容介紹存儲(chǔ)存儲(chǔ)策略編碼方案索引查詢查詢

12、改寫查詢優(yōu)化查詢算法7/19/202219存儲(chǔ)策略關(guān)系表查詢導(dǎo)出文檔Native 方式混合方式問(wèn)題Benchmark文檔類型文本數(shù)據(jù)。attributesvaluenameid7/19/202220內(nèi)容介紹存儲(chǔ)存儲(chǔ)策略編碼方案索引查詢查詢改寫查詢優(yōu)化查詢算法7/19/202221編碼方案為什么使用編碼導(dǎo)航不可行a1b1b2b3c1d1d2e1f1adQueryDocument如何判斷元素之間的關(guān)系？aa1dd1d2僅處理tag名為a和d的元素，可以減少處理的元素?cái)?shù)量7/19/202222編碼方案為什么使用編碼已有的解決方案區(qū)間編碼a1b1b2b3c1d1d2e1f1adQueryDocumen

13、t(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)7/19/202223編碼方案為什么使用編碼已有的解決方案區(qū)間編碼路徑編碼a1b1b2b3c1d1d2e1f1adQueryDocumentad..1.4.27/19/202224編碼方案為什么使用編碼已有的解決方案實(shí)際問(wèn)題

14、文檔更新插入葉子節(jié)點(diǎn)插入非葉子節(jié)點(diǎn)節(jié)點(diǎn)編碼需要更新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 18ga1b1b2b3c1d1d2e1f.1.4.2gggg7/19/202225編碼方案為什么使用編碼已有的解決方案已有更新方法空間預(yù)留無(wú)法避免重新編碼adQueryDocumenta1b1b2b3c1d1d2e1f1(10, ,1)(20, ,2) 3

15、0(40, ,2)(50, ,3) 60(70, ,3) 8090(100, ,2)110(120, ,2) 170(130, ,3) 140(150, ,3) 160 1807/19/202226編碼方案為什么使用編碼已有的解決方案已有更新方法空間預(yù)留浮點(diǎn)數(shù)編碼無(wú)法避免重新編碼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 18g1g2(110.01, 110.11, 3)(101, 110, 3)(11

16、1, 1000, 3)(110.1101, 110.1111, 3)7/19/202227編碼方案為什么使用編碼已有的解決方案已有更新方法空間預(yù)留浮點(diǎn)數(shù)編碼路徑編碼ORDPATH代價(jià)高a1b1b2b4c1d1d2e1f1a1b1b4c1e1f.3b21.2.1d1d2b21.2.3b37/19/202228編碼方案為什么使用編碼已有的解決方案已有更新方法空間預(yù)留浮點(diǎn)數(shù)編碼路徑編碼素?cái)?shù)編碼可避免更新編碼N值計(jì)算代價(jià)高a1b2c1d1d2e1f112357111312=2*16=3*210=5*27=7*177=11*791=13*7d117170=17*10

17、N1=1523N2=6N1=1139N2=7272NNNNN345NNNNN7/19/202229編碼方案為什么使用編碼已有的解決方案已有更新方法空間預(yù)留浮點(diǎn)數(shù)編碼路徑編碼素?cái)?shù)編碼二進(jìn)制位串將整數(shù)用二進(jìn)制字符串表示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 18將插入整數(shù)變?yōu)椴迦胱址? size=019 size=0(01, 01001, 001)(0101, 011, 001)g(010011, 0100111, 001)7/1

18、9/202230編碼方案為什么使用編碼已有的解決方案已有更新方法空間預(yù)留浮點(diǎn)數(shù)編碼路徑編碼素?cái)?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) 16 18將插入整數(shù)變?yōu)椴迦胂蛄?/19/202231編碼方案為什么使用編碼已有的解決方案已有更新方法空間預(yù)留浮點(diǎn)數(shù)編碼路徑編碼素?cái)?shù)編碼位串編碼向量編碼a1b1b2b3c1d1d2e1f1(1, ,1)(2, ,2) 3(4, ,2)(5, ,3) 6(7, ,3)

19、89(10, ,2)11(12, ,2) 17(13, ,3) 14(15, ,3) 16 187/19/202232編碼方案為什么使用編碼已有的解決方案已有更新方法空間預(yù)留浮點(diǎn)數(shù)編碼路徑編碼素?cái)?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) 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)7/19/202233編碼方案為

20、什么使用編碼已有的解決方案已有更新方法基于圖的編碼不支持更新7/19/202234編碼方案為什么使用編碼已有的解決方案已有更新方法基于圖的編碼不支持更新支持更新7/19/202235編碼方案為什么使用編碼已有的解決方案實(shí)際問(wèn)題可能的研究點(diǎn)樹(shù)上編碼的更新什么情況下可在兩個(gè)值之間插入無(wú)窮多個(gè)值圖上編碼的更新如何將不同區(qū)間用一個(gè)值表示a1d2d17/19/202236內(nèi)容介紹存儲(chǔ)存儲(chǔ)策略編碼方案索引查詢查詢改寫查詢優(yōu)化查詢算法7/19/202237索引為什么使用索引a1b1b2b3c1d1d2e1f1adQueryDocumentaa1dd1d27/19/202238索引為什么使用索引索引的類型結(jié)構(gòu)

21、索引Tag 索引Structural summary值索引倒排表a1b1b2d3c1d1d2e1f1bdQueryDocumentbb1dd1d2b2bb1dd1d2b2d3abcdefd7/19/202239索引為什么使用索引索引的類型結(jié)構(gòu)索引F&B index1-index7/19/202240索引為什么使用索引索引的類型結(jié)構(gòu)索引F&B index1-indexBDCBD7/19/202241內(nèi)容介紹存儲(chǔ)存儲(chǔ)策略編碼方案索引查詢查詢改寫查詢優(yōu)化查詢算法7/19/202242查詢改寫什么是查詢改寫用戶提交查詢Q系統(tǒng)處理Q7/19/202243查詢改寫什么是查詢改寫為什么要查詢改寫用戶提交的查

22、詢表達(dá)能力有限：關(guān)鍵字查詢用戶提交的查詢有誤a1b1b2d3c1d1d2e1f17/19/202244查詢改寫什么是查詢改寫為什么要查詢改寫查詢改寫的方式基于用戶反饋結(jié)果反饋查詢反饋隱式反饋：無(wú)用戶參與7/19/2022451234XMLXMLIRIRindexindexFaginIRindex用戶反饋2. User marks relevant and nonrelevant docs3. System finds best terms to distinguish between relevant and nonrelevant docs4. System submits expanded

23、 query1. User submits queryquery evaluationXML not(Fagin)Feedback for XML IR: Start with keyword query Find structural expansions Create structural query7/19/202246Tag+Content of other elements in the documentD: /authorBaeza /citationAbiteboulUser marksrelevant resultPath tothe resultP: article/body

24、/sec/subsec用戶反饋secSemistructured data“articlebodysecsubsecXML has evolved“frontmatterbackmattersecsubsecpppWith the advent of XSLT“authorBaeza-Yates“Content ofresultPossible dimensions:C: XMLcitationSerge Abiteboul“7/19/202247用戶反饋XML SearchEnginefeedbackScoring + Rerankingexpanded queryqueryresultsr

25、eranked resultsContentModulePathModuleDocModuleFeedback Dimensionsquery +results7/19/202248查詢改寫什么是查詢改寫為什么要查詢改寫查詢改寫的方式基于用戶反饋偽反饋又稱局部反饋、盲反饋,它假設(shè)初始檢索結(jié)果的前面若干篇文檔是相關(guān)的,然后利用標(biāo)準(zhǔn)的相關(guān)反饋過(guò)程進(jìn)行查詢擴(kuò)展隱式反饋用戶不主動(dòng)參與反饋,但是系統(tǒng)仍需要從用戶的瀏覽行為中分析得到一些有用的信息用來(lái)確定用戶興趣模式,從而推理出描述用戶查詢需求的表達(dá)式,并據(jù)此進(jìn)行檢索.查詢擴(kuò)展黃靜的工作7/19/202249內(nèi)容介紹存儲(chǔ)存儲(chǔ)策略編碼方案索引查詢查詢改寫查詢

26、優(yōu)化查詢算法7/19/202250查詢優(yōu)化種類邏輯優(yōu)化物理優(yōu)化7/19/202251查詢優(yōu)化邏輯優(yōu)化語(yǔ)法優(yōu)化語(yǔ)義優(yōu)化7/19/202252查詢優(yōu)化物理優(yōu)化代價(jià)估計(jì)單步代價(jià)估計(jì)執(zhí)行順序整體代價(jià)估計(jì)查詢：abcdefd7/19/202253內(nèi)容介紹存儲(chǔ)存儲(chǔ)策略編碼方案索引查詢查詢改寫查詢優(yōu)化查詢算法7/19/202254查詢算法-Twig查詢處理導(dǎo)航式a1b1b2b3c1d1d2e1f1adQueryDocument7/19/202255查詢算法-Twig查詢處理導(dǎo)航式結(jié)構(gòu)連接二元Path連接整體匹配abdcabbdaca1b1b2b3c1d1d2e1f13212abdac21大量中間結(jié)果7/19/202256查詢算法-Twig查詢處理導(dǎo)航式結(jié)構(gòu)連接二元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后代指針回指為什么？7/19/202257查詢算法-Twig查詢處理導(dǎo)航式