《《數(shù)據(jù)庫系統(tǒng)》PPT課件》由會員分享，可在線閱讀，更多相關(guān)《《數(shù)據(jù)庫系統(tǒng)》PPT課件（42頁珍藏版）》請在裝配圖網(wǎng)上搜索。
1、OrientX: Native XML數(shù)據(jù)庫系統(tǒng),孟小峰 王宇 羅道峰 陸世潮 安靖 陳妍 蔣瑜 歐建波 中國人民大學(xué)信息學(xué)院 （100872） ,Outline,體系結(jié)構(gòu)和特征 存儲 索引 SUPEX結(jié)構(gòu)索引 結(jié)構(gòu)索引使用的編碼方法 查詢處理 導(dǎo)航式查詢處理 集合式查詢處理 基于代價的查詢優(yōu)化 更新 基于角色的訪問控制,OrientX特征,基于模式 采用多種粒度的樹形結(jié)構(gòu)存儲數(shù)據(jù) 支持描述化查詢語言XQuery 基于代價估計的查詢優(yōu)化方法 基于模式的路徑索引 基于角色的訪問控制 ,體系結(jié)構(gòu),圖1 OrientX體系結(jié)構(gòu)圖,數(shù)據(jù)存儲管理 索引模塊 查詢處理 數(shù)據(jù)更新 用戶訪問控制 模式管理 接
2、口,查詢更新處理流 數(shù)據(jù)導(dǎo)入導(dǎo)出流,Outline,體系結(jié)構(gòu)和特征 存儲 索引 查詢處理 導(dǎo)航式查詢處理 集合式查詢處理 基于代價的查詢優(yōu)化 更新 基于角色的訪問控制,OrientX 存儲策略,存儲管理以記錄為單位,邏輯含義是一棵子樹，是讀寫的最小單位 一個XML文檔包含若干個記錄，多個滿足同一個模式定義（DTD或者XML Schema）的XML文檔放在一個數(shù)據(jù)集里。 EID（AID）唯一地標(biāo)志結(jié)點的類型 數(shù)據(jù)集用SetID來標(biāo)志；在文件上劃分邏輯物理塊物理塊用LpNo來標(biāo)志；給定一對，能馬上找到對應(yīng)文件的相應(yīng)的偏移量。,多粒度存儲策略,四種存儲方法 Element-based Depth-f
3、irst Element Based(DEB) Clustered Element Based（CEB） Subtree-based Depth-first Subtree Based (DSB) Clustered Subtree Based (CSB),多粒度存儲策略,DEB 存儲順序:t f1 l1 a1 f2 l2 a2 b 每個記錄包含EID，Text Value和它的父記錄的地址PAddress。 CEB 存儲順序:a1,a2聚簇存儲在一個物理塊；f1,f2在一個物理塊；l1,l2在一個物理塊；b, t各在一個物理塊。 DSB CSB,存儲策略的選擇,不同的文檔適合用不同的方法來存
4、儲 當(dāng)文檔比較小的時候，采用深度優(yōu)先方法 當(dāng)文檔比較大的時候，使用聚簇方法 文檔性質(zhì)比較強的文檔，采用深度優(yōu)先方法 數(shù)據(jù)性質(zhì)比較強的文檔，采用聚簇方法 為了處理上的方便，無論底層采取什么存儲方法，對上層查詢的接口都是一樣的，這樣，提供了一定的獨立性。,Outline,體系結(jié)構(gòu)和特征 存儲 索引 查詢處理 導(dǎo)航式查詢處理 集合式查詢處理 基于代價的查詢優(yōu)化 更新 基于角色的訪問控制,SUPEX索引策略,父子關(guān)系 祖先-后代關(guān)系 絕對路徑查詢 相對路徑查詢,元素映射表,編碼方法概述,三類編碼方法： Region-based: , Prefix-based: Dewey-code K-ary-tre
5、e-based: PBiTree 基于編碼方法的索引和查詢技術(shù)： EE-Join，EA-Join 和 KC-Join MPMCJN SHCJ, MHCJ,VPJ stack-merge,結(jié)構(gòu)索引使用的編碼,BitPath 思想：prefix-based方法 好處： 與region或者k-ary tree方法相比，變長、更新代價小。 與其它prefix-based方法相比，不需要分隔符，減少存儲空間，提高查詢效率。,Outline,體系結(jié)構(gòu)和特征 存儲 索引 查詢處理 導(dǎo)航式查詢處理 集合式查詢處理 基于代價的查詢優(yōu)化 更新 基于角色的訪問控制,處理XQuery的核心問題,Path路徑的求值問題
6、 結(jié)構(gòu)連接 基于樹的導(dǎo)航式處理 嵌套查詢的解決方案 相關(guān)嵌套 非相關(guān)嵌套 XML數(shù)據(jù)的有序性問題,XQuery查詢導(dǎo)航式實現(xiàn)方法的主要模塊,語法分析 語義檢查 生成執(zhí)行計劃 優(yōu)化器 邏輯的 物理的 執(zhí)行引擎,XQuery Execute Engine,導(dǎo)航式處理XQuery的結(jié)構(gòu)圖,Query Interface,XPath Execute Plan,XQuery Execute Plan,XPath Execute Engine,Data Manager,Optimize inline,產(chǎn)生執(zhí)行計劃的算法,構(gòu)建執(zhí)行計劃 并不是先生成語法樹再構(gòu)建執(zhí)行計劃。 而是，語法分析的同時構(gòu)建執(zhí)行計劃。
7、當(dāng)規(guī)約成一個語法單元時，即構(gòu)建一個相應(yīng)的操作符 把構(gòu)成該語法單元的子單元的對應(yīng)操作符，置為新構(gòu)建操作符的子操作；形成一棵執(zhí)行計劃樹,例子,import default schema = xmark for $p in document(xsmall.xml) /people /person Let $i := $p/interest where $p/profile/income 10000 return $p/profile $i ,執(zhí)行計劃,FLWR,ForVarBind,LetVarBind,ConditionTree,EleConstructor,EleConstructor,Path
8、,Path,$p in document(xsmall.xml) /people /person,$i := $p/interest,$p/profile/income 10000,$p/profile ,$i,導(dǎo)航式處理,FLWR,ForVarBind,LetVarBind,ConditionTree,EleConstructor,EleConstructor,Path,Path,導(dǎo)航式處理,FLWR,ForVarBind,LetVarBind,ConditionTree,EleConstructor,EleConstructor,Path,Path,Evaluated true,導(dǎo)航式處理
9、,FLWR,ForVarBind,LetVarBind,ConditionTree,EleConstructor,EleConstructor,Path,Path,Evaluated false,Outline,體系結(jié)構(gòu)和特征 存儲 索引 查詢處理 導(dǎo)航式查詢處理 集合式查詢處理 基于代價的查詢優(yōu)化 更新 基于角色的訪問控制,集合式查詢處理,借鑒關(guān)系代數(shù)方法，引入XML 代數(shù)，使操作變成一次一集合的操作。,XML Algebra 設(shè)計,設(shè)計思想 主要問題 難點,設(shè)計思想,引入關(guān)系中關(guān)于記錄的概念，操作符的操作對象是記錄的集合，若干操作符組成一棵操作符樹，來表達(dá)一個查詢。 記錄是一棵XML樹 操
10、作符的分類 Extraction操作 Processing操作 Construction操作,主要問題1：綁定到結(jié)點還是結(jié)點序列？（引入+修飾符）,FOR $b in document(“books.xml”)/book LET $a := $b/author WHERE $b/year $a ,FOR $b in document(“books.xml”)/book $a in $b/author WHERE $b/year $a ,FOR $b in document(“books.xml”)/book WHERE $b/year $b/author ,問題2：結(jié)構(gòu)謂詞結(jié)點和非謂詞結(jié)點,
11、for $b in doc( where $b/publisher = Addison-Wesley and $b/year 1991 return $b/title ,問題3：表達(dá)式的嵌套（結(jié)果構(gòu)造符多次使用）, FOR $b in document(“books.xml”)/bib/book RETURN $b/title $b/price FOR $r in document(“reviews.xml”)/review WHERE $b/title = $r/title RETURN $r/content , FOR $b in document(“books.xml”)/bib/boo
12、k $r in document(“reviews.xml”)/review WHERE $b/title = $r/title RETURN $b/title $b/price $r/content ,問題4：謂詞的作用域,for $v in document(“book.xml”)/vendor where $v/address=”beijing” return $v/name $v/booktitle=“C+” ,for $v in document(“book.xml”)/vendor $b in $v/book where $v/address=”beijing” and $b/ti
13、tle=“C+” return $v/name $b ,問題5：值綁定和引用綁定,有了中間結(jié)果，要不要與源數(shù)據(jù)發(fā)生聯(lián)系？,難點,Pattern Tree Matching的策略選擇 導(dǎo)航式 結(jié)構(gòu)連接 混合,Outline,體系結(jié)構(gòu)和特征 存儲 索引 SUPEX結(jié)構(gòu)索引 結(jié)構(gòu)索引使用的編碼方法 查詢處理 導(dǎo)航式查詢處理 集合式查詢處理 基于代價的查詢優(yōu)化 更新 基于角色的訪問控制,基于代價的查詢優(yōu)化方法,采用直方圖方法統(tǒng)計XML數(shù)據(jù)的分布情況 與模式統(tǒng)計信息相結(jié)合形成統(tǒng)計信息模型 通過六種不同的直方圖運算, 計算任意路徑中任意子路徑的選擇性,代價計算實例,n1/n2/n3/n4av,Outlin
14、e,體系結(jié)構(gòu)和特征 存儲 索引 SUPEX結(jié)構(gòu)索引 結(jié)構(gòu)索引使用的編碼方法 查詢處理 導(dǎo)航式查詢處理 集合式查詢處理 基于代價的查詢優(yōu)化 更新 基于角色的訪問控制,XML更新涉及問題,更新有效性檢查 結(jié)構(gòu)有效性 屬性有效性 結(jié)點定位 存儲空間的分配 其它輔助數(shù)據(jù)的更新，比如索引、編碼等。,更新方法,根據(jù)模式信息判斷更新的有效性 根據(jù)不同的存儲方法設(shè)計不同的更新方法 根據(jù)模式信息設(shè)計不同的預(yù)留空間 在非聚簇存儲和CEB時預(yù)留空間相同 在CSB方法時預(yù)留空間不同,Outline,體系結(jié)構(gòu)和特征 存儲 索引 SUPEX結(jié)構(gòu)索引 結(jié)構(gòu)索引使用的編碼方法 查詢處理 導(dǎo)航式查詢處理 集合式查詢處理 基于代價的查詢優(yōu)化 更新 基于角色的訪問控制,基于角色的用戶訪問控制,角色之間有繼承關(guān)系，構(gòu)成一棵角色樹。 用戶訪問控制的最小粒度是結(jié)點級。 采用類XPath語句對每個角色授權(quán) 為了使用方便和強化授權(quán)能力引入否定授權(quán)，制定權(quán)限沖突規(guī)則，和沖突檢測機制。 授權(quán)檢測時，只需對查詢語句構(gòu)成的查詢樹和授權(quán)語句構(gòu)成的權(quán)限樹匹配，如果查詢樹滿足權(quán)限樹，則允許查詢執(zhí)行，否則拒絕，無需訪問數(shù)據(jù)信息。,下一步工作,完善XML代數(shù)，實現(xiàn)集合式的XQuery查詢處理 進(jìn)一步研究XML查詢優(yōu)化問題 完善更新和訪問控制方法,
《數(shù)據(jù)庫系統(tǒng)》PPT課件
