專場5.6-分布式知識圖譜管理技術介紹-彭鵬.pptx

1、分布式知識圖譜管理技術介紹,彭鵬湖南大學 信息科學與工程學院 副教授,背景介紹集群式系統聯邦型系統總結,目錄,3,背景介紹,Part 1,4,RDF 簡介,5,資源描述框架（Resource Description Framework）,它是一種被廣泛用于知識庫的數據模型所有東西都是唯一命名的資源可以定義資源的屬性可以定義與其他資源的關系,dbpedia:Zayed_Khan,dbpedia:name Zayed Khanendbpedia:dateOfBirth 1980-07-05,dbpedia:birthPlace,dbpedia:Maharashtra,RDF 知識圖譜,6,RDF數

2、據集可以表示為圖，進而構成知識圖譜,RDF知識圖譜上的查詢模型,7,查詢模型SPARQL查詢語言SPARQL查詢是一組帶有變量的三元模式,Select?x where?yresidence?z.?ybirthPlace?x.?xfoundingDate1947-08-15.,RDF知識圖譜上的查詢模型,8,回答SPARQL查詢=使用同態的子圖匹配,*,RDF知識圖譜規模,9,現在，基于RDF的知識圖譜數據集變得越來越大,Leipzig UniversityUniversity of MannheimOpenLink Software,Max-Planck-Institute,Metaweb C

3、ompanyacquired by Google in 2010,95億三元組,2.84億個三元組,24億三元組,設計一個分布式RDF系統來管理大型RDF數據集非常重要,集群式系統,Part 2,10,分布式RDF知識圖譜管理系統體系結構,11,基于劃分的分布式架構,通過對RDF知識圖譜的劃分將其分不到不同的站點目標：并行化查詢處理，盡可能少的站點間通信,分布式查詢執行模型,12,對數據和查詢進行劃分，以盡量減少分區間連接,相關工作,13,RDF知識圖譜劃分方法可以分為三種類型:,頂點不相交：將每個頂點放在一個分區中現有方法的目標是最小化切邊，而不是最小化分區間連接邊不相交：將每條邊放在一個分

4、區中現有基于大數據計算平臺的系統廣泛使用，以刪除不相關的分區，并避免在大數據計算平臺中進行過多的掃描，但沒有關注避免分區間連接其他：考慮額外的信息，比如查詢日志,H-RDF-3X Huang et al.,VLDB 2011,14,使用METIS對數據進行分區使用n-hop保證復制頂點如果Q的半徑不大于n，則每個站點都可以對Q進行本地執行如果Q的半徑大于n，則將Q分解為幾個可獨立求值的子查詢Qi；然后將它們的結果連接起來,SHAPE Lee et al.,VLDB 2013,15,按照點生成邊組 語義哈希邊組：URI引用通常具有層次結構，具有共同祖先的URI引用通常連接在一起，因此SHAPE將

5、此類URI引用(頂點)放在同一個分區中 允許在不同分區之間復制一些數據,示例三元組,16,黑色子圖是一個基于subject的三元組 紅色子圖是一個基于object的三元組 整個圖是一個基于subject-object的三元組,最小屬性切 Peng et al.,ICDE 2022,17,我們提出了一種新的點劃分方案，最小屬性切（Minimum Property-Cut，MPC），用于分布式SPARQL查詢處理,內部和跨界屬性,當且僅當一個屬性與該屬性至少有一條跨界邊時，該屬性被稱為跨界屬性；否則，它被稱為內部屬性,18,設計目標,19,分布式SPARQL執行中的主要性能瓶頸是分區間連接如果查詢

6、中的所有屬性都是內部的，則在每個分區上獨立執行，不需要分區間連接設計目標：內部屬性的數量最大化可能增加切邊，但減少唯一屬性切邊的數量,不同分區的比較示例,20,最小屬性切,示例RDF知識圖譜劃分,問題定義,21,給定RDF知識圖譜G和正整數k,G的最小屬性切割(MPC)分區是一個分區F=F1,F2,.,Fk 跨界屬性|Lcross|的數量最小化(即內部屬性|Lin|的數量最大化);對于每個Fi,Fi(即|Vi|)的大小不大于(1+)|V|/k，其中是用戶定義的分區的最大不平衡比率(即分區的相對大小可以有多大差異)。,MPC復雜度,22,定理:MPC劃分問題是NP完全的。證明:我們將NP完全最小

7、邊切問題簡化為MPC問題，方法是在具有不同屬性的最小邊切圖劃分實例中分配每條邊。,最小化屬性切框架,23,內部屬性約束,24,如果屬性p是一個內部屬性，則p的誘導子圖的弱連通分量中的任意兩個頂點都應該在一個分區中。,如果我們想要出生地是一個內部屬性，所有六個頂點應該在一個分區中,內部屬性選擇代價,25,給定一組屬性L，將其選擇為內部屬性的代價定義為屬性誘導子圖GL中最大弱連通分量的大小。其中c是WCC(GL)中的弱連通分量，|c|表示c中的頂點數。,內部屬性選擇算法,26,首先，我們為內部屬性初始化一個空集Lin，并為每個屬性計算屬性誘導子圖的弱連通分量我們迭代地選擇一個最小化Cost(Lin

8、p)的屬性p，并將其插入Lin。重復這些步驟，直到不能選擇更多的屬性為了計算和合并弱連通分量，我們使用并查集數據結構,可獨立執行查詢,27,可獨立執行查詢(IEQs)是那些“本地”分區的查詢，無需與另一個分區連接即可執行,內部可獨立執行查詢：不包含任何跨界屬性的查詢擴展可獨立執行查詢：刪除跨界屬性邊后仍然連通的查詢,查詢分解,28,不可獨立執行查詢：我們分解成一組可獨立執行查詢并加入結果,刪除跨界屬性邊和變量邊形成子查詢為子查詢添加跨界屬性邊和變量邊,查詢執行,29,當收到一個不可獨立執行查詢的Q時，它被分解成一組子查詢q1,q2，qy，它們被發送到每個分區進行獨立執行然后，將子查詢的匹配連接

9、起來以獲得最終結果,實驗設置,30,數據集:競爭對手:Subject_Hash,METIS 和 VP環境:阿里云有8臺運行Linux的機器,劃分質量,31,|Lcross|&|Ec|:可獨立執行查詢百分比:,查詢處理性能比較,32,基準查詢:真實查詢日志:,聯邦型系統,Part 3,33,聯邦型分布式RDF知識圖譜管理系統由多個“自治”站點組成，這些站點存儲自己的RDF數據并提供SPARQL查詢接口。在這里，具有SPARQL接口的自治站點稱為RDF數據源,34,聯邦型分布式RDF知識圖譜管理系統,35,聯邦SPARQL查詢處理,它們大多集中于查詢分解和數據源選擇,36,現有方法,基于元數據的方

10、法使用元數據來確定哪些數據源是相關的DARQ Quilitz Prasser et al.,EDBT 2012.基于查詢的方法查詢一個三元模式在數據源上是否有答案FedX Schwarte et al.,ISWC 2011,37,聯邦 RDF 系統,多查詢優化Peng et al.,DASFAA 2018,TKDE 2021,38,方法概覽,39,一種基于查詢重寫的方法，用于在RDF數據源上進行查詢評估，同時考慮查詢處理和數據傳輸的代價一種使用RDF數據源之間的互連拓撲過濾掉不相關數據源的有效方法一種共享中間結果連接公共計算的有效方法。,方法框架,40,查詢分解和源選擇,本地查詢評估,加入部分

11、匹配,Control Site,RDF Sources,SPARQL Query,Matches,基本查詢分解和數據源選擇,41,大多數現有的解決方案基于三元組模式分解輸入查詢,基于數據源拓撲的查詢分解和數據源選擇,42,方法框架,43,查詢分解和數據源選擇,本地查詢評估,加入部分匹配,Control Site,RDF Sources,SPARQL Query,Matches,本地查詢執行,44,當同時提出多個SPARQL查詢時，在執行這些查詢時就有了共享計算的空間我們提出了一種成本驅動的查詢重寫方案，將它們在控制站點重寫為更少的SPARQL查詢，這可以減少遠程請求的數量并提高性能,基于OPT

12、IONAL的查詢重寫,45,基于OPTIONAL和UNION的查詢重寫,46,基于Filter的查詢重寫,47,基于VALUES的查詢重寫,48,基本圖模式的成本模型,49,求基本圖模式Q的基數如下。其中sel(e)是Q中三元模式e的選擇性。,查詢重寫的成本模型,50,因此，給定SPARQL Q，其用于局部評估的成本成本(Q)定義如下 其中TCPU是計算結果的CPU單位時間，3和4是經驗上的小值,數據傳輸的成本模型,51,基于以上，給定查詢的數據傳輸成本如下所示 其中 TMSG是傳輸單位數據的單位時間。,查詢重寫的成本模型,52,給定RDF數據源上的一組子查詢，如果p是這些查詢中的公共子圖，則

13、將它們重寫為SPARQL查詢。重寫的代價是重寫查詢的代價，如下所示。,查詢重寫,53,給定一組n個子查詢，目標是找到m個具有最小的重寫代價的集合(m)。我們證明了找到重寫查詢的最優集合是np完全的，并提出了一個貪婪的啟發式算法來尋找近似最優解,查詢改寫示例,54,后處理,55,框架,56,查詢分解和源選擇,本地查詢評估,加入部分匹配,Control Site,RDF Sources,SPARQL Query,Matches,部分匹配連接,57,在連接不同查詢的部分匹配時，可能存在一些共同的計算,部分匹配連接,58,在形式上,數據集：WatDiv,FedBench 和 LargeRDFBench

14、對比方法：FedX,SPLENDID 和 HiBISCuS環境：運行Linux的機器集群，每臺機器安裝Sesame 2.7以構建RDF數據源。,59,實驗,60,查詢分解和數據源選擇技術的效果,61,查詢重寫策略的效果,62,成本模型的評估,63,連接優化技術的效果,真實數據集上結果,64,FedBench(Cross Domain),真實數據集上結果,65,FedBench(Life Science),結論,Part 4,66,結論,67,我們介紹了集群式分布式RDF系統，并將它們分為兩類:基于劃分的方法和獨立于劃分的方法我們介紹了聯邦型RDF系統，并討論如何優化聯邦RDF系統中的多查詢處理

15、,未來工作,68,有許多分布式數據庫管理系統體系結構被進一步用于RDF知識圖譜并行計算邊緣計算.,70,參考文獻,Jiewen Huang,Daniel J.Abadi,Kun Ren.Scalable SPARQL Querying of Large RDF Graphs.Proc.VLDB Endow.4(11):1123-1134(2011)Kisung Lee,Ling Liu.Scaling Queries over Big RDF Graphs with Semantic Hash Partitioning.Proc.VLDB Endow.6(14):1894-1905(2013)

16、Yuanbo Guo,Zhengxiang Pan,Jeff Heflin.LUBM:A benchmark for OWL knowledge base systems.J.Web Semant.3(2-3):158-182(2005)Peng Peng,M.Tamer zsu,Lei Zou,Cen Yan,Chengjun Liu.Accelerating Partial Evaluation in Distributed SPARQL Query Evaluation.Accepted in ICDE 2022Katja Hose,Ralf Schenkel.WARP:Workload

17、-aware replication and partitioning for RDF.ICDE Workshops 2013:1-6Peng Peng,Lei Zou,Lei Chen,Dongyan Zhao.Adaptive Distributed RDF Graph Fragmentation and Allocation based on Query Workload.IEEE Trans.Knowl.Data Eng.31(4):670-685(2019)Peng Peng,Lei Zou,Lei Chen,Dongyan Zhao.Query Workload-based RDF

18、 Graph Fragmentation and Allocation.EDBT 2016:377-388,71,參考文獻,Peng Peng,Lei Zou,Runyu Guan.Accelerating Partial Evaluation in Distributed SPARQL Query Evaluation.ICDE 2019:112-123Peng Peng,Lei Zou,M.Tamer zsu,Lei Chen,Dongyan Zhao.Processing SPARQL queries over distributed RDF graphs.VLDB J.25(2):24

19、3-268(2016)Bastian Quilitz,Ulf Leser.Querying Distributed RDF Data Sources with SPARQL.ESWC 2008:524-538Andreas Harth,Katja Hose,Marcel Karnstedt,Axel Polleres,Kai-Uwe Sattler,Jrgen Umbrich.Data summaries for on-demand queries over linked data.WWW 2010:411-420Fabian Prasser,Alfons Kemper,Klaus A.Kuh

20、n.Efficient distributed query processing for autonomous RDF databases.EDBT 2012:372-383Andreas Schwarte,Peter Haase,Katja Hose,Ralf Schenkel,Michael Schmidt.FedX:Optimization Techniques for Federated Query Processing on Linked Data.ISWC(1)2011:601-616Peng Peng,Qi Ge,Lei Zou,M.Tamer zsu,Zhiwei Xu,Dongyan Zhao.Optimizing Multi-Query Evaluation in Federated RDF Systems.IEEE Trans.Knowl.Data Eng.33(4):1692-1707(2021)Peng Peng,Lei Zou,M.Tamer zsu,Dongyan Zhao.Multi-query Optimization in Federated RDF Systems.DASFAA(1)2018:745-765,