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

1、XML數(shù)據(jù)管理技術(shù),周軍鋒,2024/3/25,2/65,大綱,簡介流程內(nèi)容總結(jié),2024/3/25,3/65,大綱,簡介流程內(nèi)容總結(jié),2024/3/25,4/65,綜述簡介——必要性,XML數(shù)據(jù)大量涌現(xiàn)Gartner[1]預(yù)測，XML文件的使用率在2007年達(dá)到40%，2008年將占據(jù)支配地位IDC（國際數(shù)據(jù)公司）報(bào)告顯示，在500家受訪企業(yè)的IT部門中，有29％正在大量使用XML數(shù)據(jù)庫 XML研究如火如荼每年

2、各種學(xué)術(shù)會(huì)議期刊發(fā)表XML相關(guān)論文多達(dá)300篇沒有系統(tǒng)的總結(jié)和比較發(fā)表時(shí)間早：大部分出現(xiàn)在06年左右內(nèi)容局限性：主要涉及查詢，索引[1]http://egovstandards.gov.in/summit/eform/technical-papers/gartneruseofxml.pdf/view,2024/3/25,5/65,綜述簡介——信息源,要求全面性06-08年各種會(huì)議期刊國際會(huì)議國際期刊國內(nèi)會(huì)議國內(nèi)期刊

3、,2024/3/25,6/65,綜述簡介——信息源,國際會(huì)議(ACM) SIGMOD ： (Association for Computing Machinery) Special Interest Group on Management of DataVLDB : International Conference on Very Large Data BasesICDE : International Confe

4、rence on Data Engineering EDBT : International Conference on Extending Database Technology WWW : International Conference on World Wide WebCIKM : International Conference on Information and Knowledge Management

5、 DASFAA : Database Systems for Advanced Applications ER : International Conference on the Entity Relationship Approach PODS : Symposium on Principles of Database Systems SIGIR : International Conference

6、 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

7、 WISE : Web Information Systems Engineering WAIM : International Conference on Web-Age Information Management APWeb : Asia-Pacific Web Conference WebDB : International Workshop on the Web and Databases INEX

8、 : INitiative for the Evaluation of XML Retrieval XIME-P : Workshop on XQuery IMplementation, Experience and Perspectives XSym : International XML Database Symposium （08年不存在了）XML Conference : 應(yīng)用相關(guān)的會(huì)議,2024/3/

9、25,7/65,綜述簡介——信息源,國際期刊VLDBJ ：The VLDB Journal TODS ： ACM Transactions on Database Systems TKDE ： IEEE Transactions on Knowledge and Data EngineeringTOIS ： ACM Transactions on Information Systems JACM ： Journal

10、 of the ACM CACM ： Communications of the ACM IS ： Information SystemIR ： Information RetrievalKIS： Knowledge and Information SystemSIGMOD-Record DKE ： Data & Knowledge Engineering J

11、DM ： Journal of Database Management WWWJ ：World Wide Web JCST ： Journal of Computer Science and Technology,2024/3/25,8/65,綜述簡介——信息源,國內(nèi)會(huì)議NDBC國內(nèi)期刊計(jì)算機(jī)學(xué)報(bào)軟件學(xué)報(bào)計(jì)算機(jī)研究與發(fā)展計(jì)算機(jī)科學(xué)與探索,2024/3/25,9/65,綜述簡介——內(nèi)容提煉,2024/3/25

12、,10/65,綜述簡介——內(nèi)容提煉,如何壓縮內(nèi)容？06-08：200/812，2005年以前的？已有綜述中闡述的內(nèi)容，直接引用并總結(jié)對(duì)所有新內(nèi)容分類整理，得到需要的類別對(duì)每一類中的文章，去除重復(fù)文章盡量引用大會(huì)文章,2024/3/25,11/65,,綜述簡介——內(nèi)容提煉,分類整理，去除重復(fù)：150/360/700/800,,2024/3/25,12/65,大綱,簡介流程內(nèi)容總結(jié),2024/3/25,13/65,綜述流程

13、,建立數(shù)據(jù)庫導(dǎo)入/出文檔執(zhí)行查詢,2024/3/25,14/65,綜述流程,建立數(shù)據(jù)庫,,,,,,2024/3/25,15/65,綜述流程,建立數(shù)據(jù)庫導(dǎo)入/出文檔,,,,,,2024/3/25,16/65,綜述流程,建立數(shù)據(jù)庫導(dǎo)入/出文檔執(zhí)行查詢,,People/person/profile/gender,,,,,2024/3/25,17/65,綜述流程,研究點(diǎn)存儲(chǔ)存儲(chǔ)策略編碼方案索引查詢查詢改寫查詢優(yōu)化查詢算

14、法,2024/3/25,18/65,大綱,簡介流程內(nèi)容總結(jié),2024/3/25,19/65,內(nèi)容介紹,存儲(chǔ)存儲(chǔ)策略編碼方案索引查詢查詢改寫查詢優(yōu)化查詢算法,,2024/3/25,20/65,存儲(chǔ)策略,關(guān)系表查詢導(dǎo)出文檔Native 方式混合方式問題Benchmark文檔類型文本數(shù)據(jù),,,2024/3/25,21/65,內(nèi)容介紹,存儲(chǔ)存儲(chǔ)策略編碼方案索引查詢查詢改寫查詢優(yōu)化查詢算法,,2

15、024/3/25,22/65,編碼方案,為什么使用編碼導(dǎo)航不可行,a1,b1,b2,b3,c1,d1,d2,e1,f1,a,d,,Query,Document,,如何判斷元素之間的關(guān)系？,2024/3/25,23/65,編碼方案,為什么使用編碼已有的解決方案區(qū)間編碼,a1,b1,b2,b3,c1,d1,d2,e1,f1,a,d,,Query,Document,(1,,,1),(start, end, level),(2,,,2),

16、3,(4,,,2),(5,,,3),6,(7,,,3),8,9,(10,,,2),11,(12,,,2),17,(13,,,3),14,(15,,,3),16,18,2024/3/25,24/65,編碼方案,為什么使用編碼已有的解決方案區(qū)間編碼路徑編碼,a1,b1,b2,b3,c1,d1,d2,e1,f1,a,d,,Query,Document,1,1.1,1.2,1.2.1,1.2.2,1.3,1.4,1.4.1,1.4.2,2

17、024/3/25,25/65,編碼方案,為什么使用編碼已有的解決方案實(shí)際問題文檔更新插入葉子節(jié)點(diǎn)插入非葉子節(jié)點(diǎn)節(jié)點(diǎn)編碼需要更新,a,d,,Query,Document,a1,b1,b2,b3,c1,d1,d2,e1,f1,(1,,,1),(2,,,2),3,(4,,,2),(5,,,3),6,(7,,,3),8,9,(10,,,2),11,(12,,,2),17,(13,,,3),14,(15,,,3),16,18,g,a1

18、,b1,b2,b3,c1,d1,d2,e1,f1,1,1.1,1.2,1.2.1,1.2.2,1.3,1.4,1.4.1,1.4.2,g,g,g,g,2024/3/25,26/65,編碼方案,為什么使用編碼已有的解決方案已有更新方法空間預(yù)留無法避免重新編碼,a,d,,Query,Document,a1,b1,b2,b3,c1,d1,d2,e1,f1,(10,,,1),(20,,,2),30,(40,,,2),(50,,,3),

19、60,(70,,,3),80,90,(100,,,2),110,(120,,,2),170,(130,,,3),140,(150,,,3),160,180,2024/3/25,27/65,編碼方案,為什么使用編碼已有的解決方案已有更新方法空間預(yù)留浮點(diǎn)數(shù)編碼無法避免重新編碼,a,d,,Query,Document,a1,b1,b2,b3,c1,d1,d2,e1,f1,(1,,,1),(2,,,2),3,(4,,,2),(5,,

20、,3),6,(7,,,3),8,9,(10,,,2),11,(12,,,2),17,(13,,,3),14,(15,,,3),16,18,g1,g2,(110.01, 110.11, 3),(101, 110, 3),(111, 1000, 3),(110.1101, 110.1111, 3),2024/3/25,28/65,編碼方案,為什么使用編碼已有的解決方案已有更新方法空間預(yù)留浮點(diǎn)數(shù)編碼路徑編碼ORDPATH代價(jià)高,

21、,a1,b1,b2,b4,c1,d1,d2,e1,f1,a1,b1,b4,c1,e1,f1,1,1.1,1.3,1.5,1.5.1,1.5.3,b2,1.2.1,b3,2024/3/25,29/65,編碼方案,為什么使用編碼已有的解決方案已有更新方法空間預(yù)留浮點(diǎn)數(shù)編碼路徑編碼素?cái)?shù)編碼可避免更新編碼N值計(jì)算代價(jià)高,,a1,b2,c1,d1,d2,e1,f1,1,2,3,5,7,11,13,1,2=2*1,6=3*2,10=

22、5*2,7=7*1,77=11*7,91=13*7,d1,17,170=17*10,N1=1523,N2=6,72,,2024/3/25,30/65,編碼方案,為什么使用編碼已有的解決方案已有更新方法空間預(yù)留浮點(diǎn)數(shù)編碼路徑編碼素?cái)?shù)編碼二進(jìn)制位串,將整數(shù)用二進(jìn)制字符串表示,,a1,b1,b2,b3,c1,d1,d2,e1,f1,(1,,,1),(2,,,2),3,(4,,,2),(5,,,3),6,(7,,,3),8,9,(

23、10,,,2),11,(12,,,2),17,(13,,,3),14,(15,,,3),16,18,0 size=0,19 size=0,,,,(01, 01001, 001),(0101, 011, 001),g,(010011, 0100111, 001),2024/3/25,31/65,編碼方案,為什么使用編碼已有的解決方案已有更新方法空間預(yù)留浮點(diǎn)數(shù)編碼路徑編碼素?cái)?shù)編碼位串編碼向量編碼,將整數(shù)用向

24、量表示,,a1,b1,b2,b3,c1,d1,d2,e1,f1,(1,,,1),(2,,,2),3,(4,,,2),(5,,,3),6,(7,,,3),8,9,(10,,,2),11,(12,,,2),17,(13,,,3),14,(15,,,3),16,18,2024/3/25,32/65,編碼方案,為什么使用編碼已有的解決方案已有更新方法空間預(yù)留浮點(diǎn)數(shù)編碼路徑編碼素?cái)?shù)編碼位串編碼向量編碼,,a1,b1,b2,b3,c

25、1,d1,d2,e1,f1,(1,,,1),(2,,,2),3,(4,,,2),(5,,,3),6,(7,,,3),8,9,(10,,,2),11,(12,,,2),17,(13,,,3),14,(15,,,3),16,18,2024/3/25,33/65,編碼方案,為什么使用編碼已有的解決方案已有更新方法空間預(yù)留浮點(diǎn)數(shù)編碼路徑編碼素?cái)?shù)編碼位串編碼向量編碼,,a1,b1,b2,b3,c1,d1,d2,e1,f1,(1,,

26、,1),(2,,,2),3,(4,,,2),(5,,,3),6,(7,,,3),8,9,(10,,,2),11,(12,,,2),17,(13,,,3),14,(15,,,3),16,18,2024/3/25,34/65,編碼方案,為什么使用編碼已有的解決方案已有更新方法基于圖的編碼不支持更新,,2024/3/25,35/65,編碼方案,為什么使用編碼已有的解決方案已有更新方法基于圖的編碼不支持更新支持更新,,,,,2

27、024/3/25,36/65,編碼方案,為什么使用編碼已有的解決方案實(shí)際問題可能的研究點(diǎn)樹上編碼的更新什么情況下可在兩個(gè)值之間插入無窮多個(gè)值圖上編碼的更新如何將不同區(qū)間用一個(gè)值表示,2024/3/25,37/65,內(nèi)容介紹,存儲(chǔ)存儲(chǔ)策略編碼方案索引查詢查詢改寫查詢優(yōu)化查詢算法,,2024/3/25,38/65,索引,為什么使用索引,a1,b1,b2,b3,c1,d1,d2,e1,f1,a,d,,Query,D

28、ocument,,a,a1,d,d1,d2,,,,2024/3/25,39/65,索引,為什么使用索引索引的類型結(jié)構(gòu)索引Tag 索引Structural summary值索引倒排表,a1,b1,b2,d3,c1,d1,d2,e1,f1,b,d,,Query,Document,,,2024/3/25,40/65,索引,為什么使用索引索引的類型結(jié)構(gòu)索引F&B index1-index,,2024/3/25,41/

29、65,索引,為什么使用索引索引的類型結(jié)構(gòu)索引F&B index1-index,,,,B,D,C,,,,,B,D,,2024/3/25,42/65,內(nèi)容介紹,存儲(chǔ)存儲(chǔ)策略編碼方案索引查詢查詢改寫查詢優(yōu)化查詢算法,,2024/3/25,43/65,查詢改寫,什么是查詢改寫用戶提交查詢Q系統(tǒng)處理Q’,2024/3/25,44/65,查詢改寫,什么是查詢改寫為什么要查詢改寫用戶提交的查詢表達(dá)能力有限：關(guān)鍵字

30、查詢用戶提交的查詢有誤,a1,b1,b2,d3,c1,d1,d2,e1,f1,2024/3/25,45/65,查詢改寫,什么是查詢改寫為什么要查詢改寫查詢改寫的方式基于用戶反饋結(jié)果反饋查詢反饋隱式反饋：無用戶參與,2024/3/25,46/65,用戶反饋,2. User marks relevant and nonrelevant docs,3. System finds best terms to disting

31、uish between relevant and nonrelevant docs,4. System submits expanded query,Feedback for XML IR: Start with keyword query Find structural expansions Create structural query,2024/3/25,47/65,用戶反饋,sec?Semistructure

32、d data…“,article,body,sec,subsec?XML has evolved…“,frontmatter,backmatter,sec,subsec,p,p,p?With the advent of XSLT…“,author?Baeza-Yates“,citation?Serge Abiteboul“,2024/3/25,48/65,用戶反饋,,XML SearchEngine,,feedback,Sco

33、ring + Reranking,expanded query,,,query,results,reranked results,ContentModule,PathModule,DocModule,…,Feedback Dimensions,,query +results,,,,,,,2024/3/25,49/65,查詢改寫,什么是查詢改寫為什么要查詢改寫查詢改寫的方式基于用戶反饋偽反饋又稱局部反饋、盲反饋,它假設(shè)初

34、始檢索結(jié)果的前面若干篇文檔是相關(guān)的,然后利用標(biāo)準(zhǔn)的相關(guān)反饋過程進(jìn)行查詢擴(kuò)展隱式反饋用戶不主動(dòng)參與反饋,但是系統(tǒng)仍需要從用戶的瀏覽行為中分析得到一些有用的信息用來確定用戶興趣模式,從而推理出描述用戶查詢需求的表達(dá)式,并據(jù)此進(jìn)行檢索.查詢擴(kuò)展黃靜的工作,2024/3/25,50/65,內(nèi)容介紹,存儲(chǔ)存儲(chǔ)策略編碼方案索引查詢查詢改寫查詢優(yōu)化查詢算法,,2024/3/25,51/65,查詢優(yōu)化,種類邏輯優(yōu)化物理優(yōu)化,2

35、024/3/25,52/65,,查詢優(yōu)化,邏輯優(yōu)化,2024/3/25,53/65,查詢優(yōu)化,物理優(yōu)化代價(jià)估計(jì)單步代價(jià)估計(jì)執(zhí)行順序整體代價(jià)估計(jì),√,2024/3/25,54/65,內(nèi)容介紹,存儲(chǔ)存儲(chǔ)策略編碼方案索引查詢查詢改寫查詢優(yōu)化查詢算法,,2024/3/25,55/65,查詢算法-Twig查詢處理,導(dǎo)航式,a1,b1,b2,b3,c1,d1,d2,e1,f1,a,d,,Query,Document,,2024

36、/3/25,56/65,查詢算法-Twig查詢處理,導(dǎo)航式結(jié)構(gòu)連接二元Path連接整體匹配,3,2,1,2,2,1,大量中間結(jié)果,2024/3/25,57/65,查詢算法-Twig查詢處理,導(dǎo)航式結(jié)構(gòu)連接二元Path連接整體匹配,,,,,,a3d2,a3d3,a4d2,a4d3,a6d4,a6d5,后代指針回指為什么？,2024/3/25,58/65,查詢算法-Twig查詢處理,導(dǎo)航式結(jié)構(gòu)連接二元Path連接整

37、體匹配,,,,a3d2,a3d3,a4d2,a4d3,a6d4,a6d5,,,,,a1(7,20),a2(14,19),a3(21,28),a4(22,27),a5(29,31),a6(32,40),2024/3/25,59/65,查詢算法-Twig查詢處理,導(dǎo)航式結(jié)構(gòu)連接二元Path連接整體匹配,A1,B1,A2,B2,C1,,,,,A,B,C,,,,,XML Doc,Query,A1,A2,B1,B2,C1,,,,Resul

38、t:A1 B1 C1A1 B2 C1A2 B2 C1,,,,,,,,,,SC,SB,SA,,2024/3/25,60/65,查詢算法-Twig查詢處理,導(dǎo)航式結(jié)構(gòu)連接二元Path連接整體匹配,2024/3/25,61/65,查詢算法-Twig查詢處理,導(dǎo)航式結(jié)構(gòu)連接二元Path連接整體匹配,,,,,,,,,,,,,,,,,,,,a7,,c12,c8,,b4,a7 c8,a7 b4,,c9,a7 c9,,c10,a7

39、 c10,,c11,a7 c11,,b5,a7 b5,,a7 c12,,,,,,,,,,,Stack a,Stack b,Stack c,Result of A//C,Result of A//B,2024/3/25,62/65,大綱,簡介流程內(nèi)容展望總結(jié),2024/3/25,63/65,研究展望,編碼：圖上可更新的編碼方案查詢靜態(tài)文檔：關(guān)鍵字查詢，近似查詢數(shù)據(jù)流：關(guān)鍵字查詢，近似查詢數(shù)據(jù)集成概率XML時(shí)態(tài)XML數(shù)