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

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