《數(shù)據(jù)庫系統(tǒng)》PPT課件

OrientX: Native XML數(shù)據(jù)庫系統(tǒng),孟小峰 王宇 羅道峰 陸世潮 安靖 陳妍 蔣瑜 歐建波 中國人民大學(xué)信息學(xué)院 （100872） ,Outline,體系結(jié)構(gòu)和特征 存儲 索引 SUPEX結(jié)構(gòu)索引 結(jié)構(gòu)索引使用的編碼方法 查詢處理 導(dǎo)航式查詢處理 集合式查詢處理 基于代價(jià)的查詢優(yōu)化 更新 基于角色的訪問控制,OrientX特征,基于模式 采用多種粒度的樹形結(jié)構(gòu)存儲數(shù)據(jù) 支持描述化查詢語言XQuery 基于代價(jià)估計(jì)的查詢優(yōu)化方法 基于模式的路徑索引 基于角色的訪問控制 ,體系結(jié)構(gòu),圖1 OrientX體系結(jié)構(gòu)圖,數(shù)據(jù)存儲管理 索引模塊 查詢處理 數(shù)據(jù)更新 用戶訪問控制 模式管理 接口,查詢更新處理流 數(shù)據(jù)導(dǎo)入導(dǎo)出流,Outline,體系結(jié)構(gòu)和特征 存儲 索引 查詢處理 導(dǎo)航式查詢處理 集合式查詢處理 基于代價(jià)的查詢優(yōu)化 更新 基于角色的訪問控制,OrientX 存儲策略,存儲管理以記錄為單位,邏輯含義是一棵子樹，是讀寫的最小單位 一個XML文檔包含若干個記錄，多個滿足同一個模式定義（DTD或者XML Schema）的XML文檔放在一個數(shù)據(jù)集里。 EID（AID）唯一地標(biāo)志結(jié)點(diǎn)的類型 數(shù)據(jù)集用SetID來標(biāo)志；在文件上劃分邏輯物理塊物理塊用LpNo來標(biāo)志；給定一對，能馬上找到對應(yīng)文件的相應(yīng)的偏移量。,多粒度存儲策略,四種存儲方法 Element-based Depth-first 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,存儲策略的選擇,不同的文檔適合用不同的方法來存儲 當(dāng)文檔比較小的時(shí)候，采用深度優(yōu)先方法 當(dāng)文檔比較大的時(shí)候，使用聚簇方法 文檔性質(zhì)比較強(qiáng)的文檔，采用深度優(yōu)先方法 數(shù)據(jù)性質(zhì)比較強(qiáng)的文檔，采用聚簇方法 為了處理上的方便，無論底層采取什么存儲方法，對上層查詢的接口都是一樣的，這樣，提供了一定的獨(dú)立性。,Outline,體系結(jié)構(gòu)和特征 存儲 索引 查詢處理 導(dǎo)航式查詢處理 集合式查詢處理 基于代價(jià)的查詢優(yōu)化 更新 基于角色的訪問控制,SUPEX索引策略,父子關(guān)系 祖先-后代關(guān)系 絕對路徑查詢 相對路徑查詢,元素映射表,編碼方法概述,三類編碼方法： Region-based: , Prefix-based: Dewey-code K-ary-tree-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方法相比，變長、更新代價(jià)小。 與其它prefix-based方法相比，不需要分隔符，減少存儲空間，提高查詢效率。,Outline,體系結(jié)構(gòu)和特征 存儲 索引 查詢處理 導(dǎo)航式查詢處理 集合式查詢處理 基于代價(jià)的查詢優(yōu)化 更新 基于角色的訪問控制,處理XQuery的核心問題,Path路徑的求值問題 結(jié)構(gòu)連接 基于樹的導(dǎo)航式處理 嵌套查詢的解決方案 相關(guān)嵌套 非相關(guān)嵌套 XML數(shù)據(jù)的有序性問題,XQuery查詢導(dǎo)航式實(shí)現(xiàn)方法的主要模塊,語法分析 語義檢查 生成執(zhí)行計(jì)劃 優(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í)行計(jì)劃的算法,構(gòu)建執(zhí)行計(jì)劃 并不是先生成語法樹再構(gòu)建執(zhí)行計(jì)劃。 而是，語法分析的同時(shí)構(gòu)建執(zhí)行計(jì)劃。 當(dāng)規(guī)約成一個語法單元時(shí)，即構(gòu)建一個相應(yīng)的操作符 把構(gòu)成該語法單元的子單元的對應(yīng)操作符，置為新構(gòu)建操作符的子操作；形成一棵執(zhí)行計(jì)劃樹,例子,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í)行計(jì)劃,FLWR,ForVarBind,LetVarBind,ConditionTree,EleConstructor,EleConstructor,Path,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)航式處理,FLWR,ForVarBind,LetVarBind,ConditionTree,EleConstructor,EleConstructor,Path,Path,Evaluated false,Outline,體系結(jié)構(gòu)和特征 存儲 索引 查詢處理 導(dǎo)航式查詢處理 集合式查詢處理 基于代價(jià)的查詢優(yōu)化 更新 基于角色的訪問控制,集合式查詢處理,借鑒關(guān)系代數(shù)方法，引入XML 代數(shù)，使操作變成一次一集合的操作。,XML Algebra 設(shè)計(jì),設(shè)計(jì)思想 主要問題 難點(diǎn),設(shè)計(jì)思想,引入關(guān)系中關(guān)于記錄的概念，操作符的操作對象是記錄的集合，若干操作符組成一棵操作符樹，來表達(dá)一個查詢。 記錄是一棵XML樹 操作符的分類 Extraction操作 Processing操作 Construction操作,主要問題1：綁定到結(jié)點(diǎn)還是結(jié)點(diǎn)序列？（引入+修飾符）,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é)點(diǎn)和非謂詞結(jié)點(diǎn), 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/book $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/title=“C+” return $v/name $b ,問題5：值綁定和引用綁定,有了中間結(jié)果，要不要與源數(shù)據(jù)發(fā)生聯(lián)系？,難點(diǎn),Pattern Tree Matching的策略選擇 導(dǎo)航式 結(jié)構(gòu)連接 混合,Outline,體系結(jié)構(gòu)和特征 存儲 索引 SUPEX結(jié)構(gòu)索引 結(jié)構(gòu)索引使用的編碼方法 查詢處理 導(dǎo)航式查詢處理 集合式查詢處理 基于代價(jià)的查詢優(yōu)化 更新 基于角色的訪問控制,基于代價(jià)的查詢優(yōu)化方法,采用直方圖方法統(tǒng)計(jì)XML數(shù)據(jù)的分布情況 與模式統(tǒng)計(jì)信息相結(jié)合形成統(tǒng)計(jì)信息模型 通過六種不同的直方圖運(yùn)算, 計(jì)算任意路徑中任意子路徑的選擇性,代價(jià)計(jì)算實(shí)例,n1/n2/n3/n4av,Outline,體系結(jié)構(gòu)和特征 存儲 索引 SUPEX結(jié)構(gòu)索引 結(jié)構(gòu)索引使用的編碼方法 查詢處理 導(dǎo)航式查詢處理 集合式查詢處理 基于代價(jià)的查詢優(yōu)化 更新 基于角色的訪問控制,XML更新涉及問題,更新有效性檢查 結(jié)構(gòu)有效性 屬性有效性 結(jié)點(diǎn)定位 存儲空間的分配 其它輔助數(shù)據(jù)的更新，比如索引、編碼等。,更新方法,根據(jù)模式信息判斷更新的有效性 根據(jù)不同的存儲方法設(shè)計(jì)不同的更新方法 根據(jù)模式信息設(shè)計(jì)不同的預(yù)留空間 在非聚簇存儲和CEB時(shí)預(yù)留空間相同 在CSB方法時(shí)預(yù)留空間不同,Outline,體系結(jié)構(gòu)和特征 存儲 索引 SUPEX結(jié)構(gòu)索引 結(jié)構(gòu)索引使用的編碼方法 查詢處理 導(dǎo)航式查詢處理 集合式查詢處理 基于代價(jià)的查詢優(yōu)化 更新 基于角色的訪問控制,基于角色的用戶訪問控制,角色之間有繼承關(guān)系，構(gòu)成一棵角色樹。 用戶訪問控制的最小粒度是結(jié)點(diǎn)級。 采用類XPath語句對每個角色授權(quán) 為了使用方便和強(qiáng)化授權(quán)能力引入否定授權(quán)，制定權(quán)限沖突規(guī)則，和沖突檢測機(jī)制。 授權(quán)檢測時(shí)，只需對查詢語句構(gòu)成的查詢樹和授權(quán)語句構(gòu)成的權(quán)限樹匹配，如果查詢樹滿足權(quán)限樹，則允許查詢執(zhí)行，否則拒絕，無需訪問數(shù)據(jù)信息。,下一步工作,完善XML代數(shù)，實(shí)現(xiàn)集合式的XQuery查詢處理 進(jìn)一步研究XML查詢優(yōu)化問題 完善更新和訪問控制方法,