《《數(shù)據(jù)庫(kù)系統(tǒng)》PPT課件》由會(huì)員分享，可在線閱讀，更多相關(guān)《《數(shù)據(jù)庫(kù)系統(tǒng)》PPT課件（42頁(yè)珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。
1、OrientX: Native XML數(shù)據(jù)庫(kù)系統(tǒng),孟小峰 王宇 羅道峰 陸世潮 安靖 陳妍 蔣瑜 歐建波 中國(guó)人民大學(xué)信息學(xué)院 （100872） ,Outline,體系結(jié)構(gòu)和特征 存儲(chǔ) 索引 SUPEX結(jié)構(gòu)索引 結(jié)構(gòu)索引使用的編碼方法 查詢(xún)處理 導(dǎo)航式查詢(xún)處理 集合式查詢(xún)處理 基于代價(jià)的查詢(xún)優(yōu)化 更新 基于角色的訪問(wèn)控制,OrientX特征,基于模式 采用多種粒度的樹(shù)形結(jié)構(gòu)存儲(chǔ)數(shù)據(jù) 支持描述化查詢(xún)語(yǔ)言XQuery 基于代價(jià)估計(jì)的查詢(xún)優(yōu)化方法 基于模式的路徑索引 基于角色的訪問(wèn)控制 ,體系結(jié)構(gòu),圖1 OrientX體系結(jié)構(gòu)圖,數(shù)據(jù)存儲(chǔ)管理 索引模塊 查詢(xún)處理 數(shù)據(jù)更新 用戶(hù)訪問(wèn)控制 模式管理 接
2、口,,,查詢(xún)更新處理流 數(shù)據(jù)導(dǎo)入導(dǎo)出流,Outline,體系結(jié)構(gòu)和特征 存儲(chǔ) 索引 查詢(xún)處理 導(dǎo)航式查詢(xún)處理 集合式查詢(xún)處理 基于代價(jià)的查詢(xún)優(yōu)化 更新 基于角色的訪問(wèn)控制,OrientX 存儲(chǔ)策略,存儲(chǔ)管理以記錄為單位,邏輯含義是一棵子樹(shù)，是讀寫(xiě)的最小單位 一個(gè)XML文檔包含若干個(gè)記錄，多個(gè)滿足同一個(gè)模式定義（DTD或者XML Schema）的XML文檔放在一個(gè)數(shù)據(jù)集里。 EID（AID）唯一地標(biāo)志結(jié)點(diǎn)的類(lèi)型 數(shù)據(jù)集用SetID來(lái)標(biāo)志；在文件上劃分邏輯物理塊物理塊用LpNo來(lái)標(biāo)志；給定一對(duì)，能馬上找到對(duì)應(yīng)文件的相應(yīng)的偏移量。,多粒度存儲(chǔ)策略,四種存儲(chǔ)方法 Element-based Depth
3、-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ǔ)策略的選擇,不同的文檔適合用不同的方
4、法來(lái)存儲(chǔ) 當(dāng)文檔比較小的時(shí)候，采用深度優(yōu)先方法 當(dāng)文檔比較大的時(shí)候，使用聚簇方法 文檔性質(zhì)比較強(qiáng)的文檔，采用深度優(yōu)先方法 數(shù)據(jù)性質(zhì)比較強(qiáng)的文檔，采用聚簇方法 為了處理上的方便，無(wú)論底層采取什么存儲(chǔ)方法，對(duì)上層查詢(xún)的接口都是一樣的，這樣，提供了一定的獨(dú)立性。,Outline,體系結(jié)構(gòu)和特征 存儲(chǔ) 索引 查詢(xún)處理 導(dǎo)航式查詢(xún)處理 集合式查詢(xún)處理 基于代價(jià)的查詢(xún)優(yōu)化 更新 基于角色的訪問(wèn)控制,SUPEX索引策略,父子關(guān)系 祖先-后代關(guān)系 絕對(duì)路徑查詢(xún) 相對(duì)路徑查詢(xún),元素映射表,編碼方法概述,三類(lèi)編碼方法： Region-based: , Prefix-based: Dewey-code K-ary-
5、tree-based: PBiTree 基于編碼方法的索引和查詢(xún)技術(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ǔ)空間，提高查詢(xún)效率。,Outline,體系結(jié)構(gòu)和特征 存儲(chǔ) 索引 查詢(xún)處理 導(dǎo)航式查詢(xún)處理 集合式查詢(xún)處理 基于代價(jià)的查詢(xún)優(yōu)化 更新 基于角色的訪問(wèn)控制,處理XQuery的核心問(wèn)題,Path路徑的求
6、值問(wèn)題 結(jié)構(gòu)連接 基于樹(shù)的導(dǎo)航式處理 嵌套查詢(xún)的解決方案 相關(guān)嵌套 非相關(guān)嵌套 XML數(shù)據(jù)的有序性問(wèn)題,XQuery查詢(xún)導(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ǔ)法樹(shù)再構(gòu)建執(zhí)行計(jì)劃。 而是，語(yǔ)法分析的同時(shí)構(gòu)建執(zhí)
7、行計(jì)劃。 當(dāng)規(guī)約成一個(gè)語(yǔ)法單元時(shí)，即構(gòu)建一個(gè)相應(yīng)的操作符 把構(gòu)成該語(yǔ)法單元的子單元的對(duì)應(yīng)操作符，置為新構(gòu)建操作符的子操作；形成一棵執(zhí)行計(jì)劃樹(shù),例子,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,EleConstruct
8、or,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,,,
9、,,,,,Evaluated true,導(dǎo)航式處理,FLWR,ForVarBind,LetVarBind,ConditionTree,EleConstructor,EleConstructor,Path,Path,,,Evaluated false,Outline,體系結(jié)構(gòu)和特征 存儲(chǔ) 索引 查詢(xún)處理 導(dǎo)航式查詢(xún)處理 集合式查詢(xún)處理 基于代價(jià)的查詢(xún)優(yōu)化 更新 基于角色的訪問(wèn)控制,集合式查詢(xún)處理,借鑒關(guān)系代數(shù)方法，引入XML 代數(shù)，使操作變成一次一集合的操作。,XML Algebra 設(shè)計(jì),設(shè)計(jì)思想 主要問(wèn)題 難點(diǎn),設(shè)計(jì)思想,引入關(guān)系中關(guān)于記錄的概念，操作符的操作對(duì)象是記錄的集合，若干操作符組成
10、一棵操作符樹(shù)，來(lái)表達(dá)一個(gè)查詢(xún)。 記錄是一棵XML樹(shù) 操作符的分類(lèi) Extraction操作 Processing操作 Construction操作,主要問(wèn)題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
11、$b/year $b/author ,問(wèn)題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 ,問(wèn)題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/titl
12、e 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 ,問(wèn)題4：謂詞的作用域,for $v in document(“book.xml”)//vendor where $v/address=”beijing” return $v/name $v/booktitle=
13、“C++” ,for $v in document(“book.xml”)//vendor $b in $v/book where $v/address=”beijing” and $b/title=“C++” return $v/name $b ,問(wèn)題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)索引使用的編碼方法 查詢(xún)處理 導(dǎo)航式查詢(xún)處理 集合式查詢(xún)處理 基于代價(jià)的查詢(xún)優(yōu)化 更新 基于角色的訪問(wèn)控制,
14、基于代價(jià)的查詢(xún)優(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)索引使用的編碼方法 查詢(xún)處理 導(dǎo)航式查詢(xún)處理 集合式查詢(xún)處理 基于代價(jià)的查詢(xún)優(yōu)化 更新 基于角色的訪問(wèn)控制,XML更新涉及問(wèn)題,更新有效性檢查 結(jié)構(gòu)有效性 屬性有效性 結(jié)點(diǎn)定位 存儲(chǔ)空間的分配 其它輔助數(shù)據(jù)的更新，比如索引、編碼等。,更新方法,,,根據(jù)模式信息判斷更新的有效性 根據(jù)不同的存儲(chǔ)方法設(shè)計(jì)不同的更新方法 根
15、據(jù)模式信息設(shè)計(jì)不同的預(yù)留空間 在非聚簇存儲(chǔ)和CEB時(shí)預(yù)留空間相同 在CSB方法時(shí)預(yù)留空間不同,Outline,體系結(jié)構(gòu)和特征 存儲(chǔ) 索引 SUPEX結(jié)構(gòu)索引 結(jié)構(gòu)索引使用的編碼方法 查詢(xún)處理 導(dǎo)航式查詢(xún)處理 集合式查詢(xún)處理 基于代價(jià)的查詢(xún)優(yōu)化 更新 基于角色的訪問(wèn)控制,基于角色的用戶(hù)訪問(wèn)控制,角色之間有繼承關(guān)系，構(gòu)成一棵角色樹(shù)。 用戶(hù)訪問(wèn)控制的最小粒度是結(jié)點(diǎn)級(jí)。 采用類(lèi)XPath語(yǔ)句對(duì)每個(gè)角色授權(quán) 為了使用方便和強(qiáng)化授權(quán)能力引入否定授權(quán)，制定權(quán)限沖突規(guī)則，和沖突檢測(cè)機(jī)制。 授權(quán)檢測(cè)時(shí)，只需對(duì)查詢(xún)語(yǔ)句構(gòu)成的查詢(xún)樹(shù)和授權(quán)語(yǔ)句構(gòu)成的權(quán)限樹(shù)匹配，如果查詢(xún)樹(shù)滿足權(quán)限樹(shù)，則允許查詢(xún)執(zhí)行，否則拒絕，無(wú)需訪問(wèn)數(shù)據(jù)信息。,下一步工作,完善XML代數(shù)，實(shí)現(xiàn)集合式的XQuery查詢(xún)處理 進(jìn)一步研究XML查詢(xún)優(yōu)化問(wèn)題 完善更新和訪問(wèn)控制方法,
《數(shù)據(jù)庫(kù)系統(tǒng)》PPT課件
