第三講知識圖譜的存儲與查詢第1節(jié)基于關系型數(shù)據(jù)庫的知識圖譜存儲第2節(jié)基于原生圖數(shù)據(jù)庫的知識圖譜存儲第3節(jié)原生圖數(shù)據(jù)庫實現(xiàn)原理淺析浙江大學計算機科學與技術(shù)學院陳華鈞教授/博導1第三講知識圖譜的存儲與查詢浙江大學計算機科學與技術(shù)學院陳華鈞教授/博導3知識圖譜的存儲需要綜合考慮知識結(jié)構(gòu)、圖的特點、索引和查詢優(yōu)化等問題。典型的知識圖譜存儲引擎分為基于關系數(shù)據(jù)庫的存儲和基于原生圖的存儲。圖數(shù)據(jù)庫存儲并非必須，例如Wikidata項目后端是MySQL實現(xiàn)的。知識圖譜存儲：從圖結(jié)構(gòu)模型說起屬性圖和RDF圖模型都是有向標記圖:DirectedLabeledGraph詳細語法細節(jié)參考：/TR/sparql11-query/manyself-joins!屬性表存儲也稱為垂直仍然基于傳統(tǒng)關系數(shù)據(jù)庫實現(xiàn)，典型的如Jena[Wilkinsonetal基本思想是以實體類型為中心，把屬于同一個實體類型的屬性組織為一個表，即屬性表進優(yōu)點：Join減少了，本質(zhì)上接近于關系數(shù)據(jù)庫，可重用RDBMS功能缺點：很多空值，對Subject聚類比較復雜、不易處理多值屬性。二元表也稱為垂直劃分表，也是基于關系數(shù)據(jù)庫實現(xiàn)的三元組存儲方式。基本思想是對三元組按屬性分組，為每個屬性在關系數(shù)據(jù)庫中建立一個包含（subject、Object）兩列的表。由于一個知識圖譜中屬性數(shù)量是有限的，表的總體數(shù)量是可控的。優(yōu)點是沒有空值、也不需要聚類、對于Subject-Subject-Join操作性能好。缺點是Insert性能損耗高、并且Subject-ObjectJoin性能差。性能最好的存儲方式是基于全索引結(jié)構(gòu)的存儲，典型的實現(xiàn)包括RDF-3X,Hexastore等。這種方法也僅維護一張包含(Subject,Predicate,Object）的三列表，但增加了多個方面的優(yōu)化手段。第一個優(yōu)化手段是建立MappingTable，即將所有的字符串首先映射到唯一的數(shù)字ID，這一將大大壓縮存儲空間。進一步建立六種索引：SPO,SOP,PSO,POS,OPS,OSP，即分別建立Subject-Predicate-Object;Subject-Object-Predicate；Predicate-Subject-Object等六個方面的全索引，顯然多種形式的索引覆蓋了多個維度的圖查詢需求。同時三元組基于字符串排序，并利用clusteredB+tree樹來組織索引以進一步優(yōu)化索引檢索的效率。from《知識圖譜數(shù)據(jù)管理研究綜述》王鑫等謝謝大家！第三講知識圖譜的存儲與查詢第2節(jié)基于原生圖數(shù)據(jù)庫的知識圖譜存儲浙江大學計算機科學與技術(shù)學院陳華鈞教授/博導關系型數(shù)據(jù)庫的局限性：關系模型不善處理“關系”數(shù)據(jù)來源多樣性帶來大量離群數(shù)據(jù)（OutlierData），導致互聯(lián)網(wǎng)的開放世界假設要求數(shù)據(jù)模型滿足高動態(tài)和去中心化關系模型背離了用接近自然語言的方式來描述客觀世界的原則，這使得概念化、高度關關系模型背離了用接近自然語言的方式來描述客觀世界的原則，這使得概念化、高度關聯(lián)的世界模型與數(shù)據(jù)的物理存儲之間出現(xiàn)了失配。1.Asking“whoareBob’sfriends?”iseasy2.處理Reflexiverelationship的自反查詢帶來底層數(shù)據(jù)庫的更多計算，從圖的角度，只需聲明friend關系是自反關系即可支持反向查詢。3.處理Chainrelationship的多跳查詢帶來更加復雜的Join計算。有些數(shù)據(jù)庫如Oracle提供了SyntaxSuger如“ConnectBy”，但沒有降低底層的計算復雜度。eeABC客戶信息表交易信息表eeABC3…1,000,000people,eachwithapproximately50friends,querytoamaximumdepthoffive.20.0160.01~2500330.2670.168~110,00041543.5051.359~600,0005Unfinished2.132~800,000在需要更加深入的研究數(shù)據(jù)之間的關系時，需要更加豐富的關系語義的表達能力，除了前述Reflesive和多跳關系、還包括傳遞關系Transitive、對稱關系（非對稱關系）Symmetric、反關系（Inverse）、函數(shù)關系（Functional）。除了關聯(lián)查詢能力，深層次的關系建模還將提供關聯(lián)推理的能力，屬性圖數(shù)據(jù)庫如Neo4J提供了由于關系模型的關聯(lián)查詢能力，AllegroGraph等RDF圖數(shù)據(jù)庫提供了更多的關聯(lián)推理能力。SymmetricPropertyTransitiveP關系在NoSQL數(shù)據(jù)庫中也不是First-ClassCitizen，在處理數(shù)據(jù)關聯(lián)也需要使用類似于外鍵的ForeignAggregates。ForeignAggregates不能處理自反關系，例如，查詢“whoisfriendswithBob?”時，需要暴力計算，即掃描所有實體數(shù)據(jù)集。ForeignAggregates也不負責維護Link的有效性，在處理多跳關系時效率也很低下。關系模型中關系被隱藏定義圖數(shù)據(jù)模型中關系被顯示描述CompanyTableIDCTencentdocuments,SQLcodeandcollectivememories-notavailabletoavailabletoapplicationsCityTableCityShengzhenRelationshipRelationshipModelChinaCompany_CityTableDataDefinitionStatements?ApplicationsdonotCompany_CityTableDataDefinitionStatements?Applicationsdonotusethem,theyarenotdescriptiveQuestionandID=CO_IDandCityandtheirscopeisasingledatabaseCity_IDCity_IDCO_IDShengzhenIDCWherearetherelationships?DataDictionary?DataRegistry?Theyareforhuman,notcomputeruse原生圖數(shù)據(jù)庫：利用圖的結(jié)構(gòu)特征建索引自然表達：圖是十分自然的描述事物關系的方式，更加接近于人腦對客觀事物的記憶方式。易于擴展：圖模型更加易于適應變化，例如在圖中，臨時希望獲取歷史訂單，只需新增邊即可。復雜關聯(lián)表達：圖模型易于表達復雜關聯(lián)邏輯的查詢，例如在推薦系統(tǒng)中，希望表達復雜的推薦邏輯，例如：“alltheflavorsoficecreamlikedbypeoplewhoenjoyespressobutdislikeBrusselssprouts,andwholiveinaparticularneighborhood.”多跳優(yōu)化：在處理多跳查詢上，圖模型有性能優(yōu)勢。屬性圖是圖數(shù)據(jù)庫Neo4J實現(xiàn)的圖結(jié)構(gòu)表示模型，在工業(yè)界有廣泛應用。在屬性圖的術(shù)語中，屬性圖是由頂點（Vertex），邊（Edge），標簽（Label），關系類型還有屬性（Property）組成的有向圖。在屬性圖中，節(jié)點和關系是最重要的實體。節(jié)點上包含屬性，屬性可以以任何鍵值形式存在。CypherofNeo4JSPARQLofW3CRETURNb,cSelect?a,?b,?cwhere{}g.V().has(“name","Jim").out(“:KNOWS").out(“:KNOWS”).舉例：跨領域圖建模與查詢theatricaldomaineospatialdomain利用圖譜將不同領域的數(shù)據(jù)進行關聯(lián)要求模型能按需擴展查詢語句能表示跨多個領域的關聯(lián)邏輯CREATE(shakespeare:Author{firstname:'William',lastname:'Shakespeare'}),(juliusCaesar:Play{title:'JuliusC(theTempest:Play{title:'Th(production1:Production{name:'JuliusCaesa(performance1:Performance{date:2(production2:Production{name:'TheTemp(performance2:Performance{date:2(performance3:Performance{date:2(review:Review{rating:(theatreRoyal:Venue{name:'Theatre(greyStreet:Street{name:'Gre(tyneAndWear:County{name:'Tyneand(stratford:City{name:'StratforduponAQueryacrossdomainsFindsalltheShakespeareperformancesatNewcastle’sTheatreRoyalMATCH(theater:Venue{name:'TheatreRoyal'}),(bard:Author{lastname:RETURNDISTINCTplay.titleASplayIdentifypotentiallysuspectbehavior:retrievealltheemailsthatBobhassentwherehe’sCC’doneofhisownaliasesRETURNemail.id名稱LicenseLanguage簡介AllegroGraphProprietary,clients:EclipsePublicLicensev1C#,C,CommonLisp,Java,PythonRDF原生圖存儲，支持SPARQL，支持部分OWL推理，支持Prolog規(guī)則推理，有可視化工具AmazonNeptuneProprietaryNotdisclosed亞馬遜的圖數(shù)據(jù)庫云服務，支持屬性圖和RDF，屬性圖存儲支持ApacheThinkerPopGremlin，RDF存儲支持SPARQLAnzoGraphProprietaryC,C++CambridgeSemantics提供的原生圖數(shù)據(jù)庫引擎，支持交互式的RDF數(shù)據(jù)分析，底層支持與HDFS等大數(shù)據(jù)引擎對接，支持W3CSPARQL語言ArangoDBFreeApache2,Proprietary,部分開源JavaScriC++,JavaScri基于NoSQL實現(xiàn)的圖數(shù)據(jù)庫，支持ArangoDB自己的圖查詢語言AQL，適合那些綜合需要NoSQL存儲和圖存儲的場景 pt pJava,Python,Node.js,a,Go,Ruby。PHP,ScalDataStaxEnterpriseGraphProprietaryJava分布式實時可擴展圖數(shù)據(jù)庫，底層與Cassandra集成，支持ThinkerPopGremlin查詢語言。JanusGraphMarkLogicApache2開源JavaLinuxFoundation下的開源分布式圖數(shù)據(jù)庫，支持與各種大數(shù)據(jù)存儲后端集成，如Cassandra，HBase等，支持與Giraph等圖計算引擎集成，支持ThinkerPopGremlin查詢語言。Proprietary,freewaredeveloperversionJava基于NoSQL實現(xiàn)的圖數(shù)據(jù)庫，支持RDF和SPARQL查詢。Neo4jOpenLinkVirtuosoOrientDBGiraphBlazeGraphGPLv3CommunityJava,.NET,JavaScript,Python,R原生圖數(shù)據(jù)庫，支持屬性圖和自定義的Cypher查詢語言。Edition,commercial&AGPLv3optionsforubyenterpriseOpenSourceEditionisGPLv2,EnterpriseC,C++老牌的RDF圖數(shù)據(jù)庫，支持RDF，SPARQL。底層基于關系數(shù)據(jù)庫實現(xiàn)。EditionisproprietaryCommunityEditionisApache2,Java基于NoSQL實現(xiàn)的圖數(shù)據(jù)庫，支持屬性圖EnterpriseEditioniscommercial支持RDF圖存儲，支持并行圖計算GPLv2orcommercialJavaWikidata的后端，支持RDF推理，支持SPARQL，支持基于RDF的圖挖掘與分析謝謝大家！第三講知識圖譜的存儲與查詢第3節(jié)原生圖數(shù)據(jù)庫實現(xiàn)原理淺析浙江大學計算機科學與技術(shù)學院陳華鈞教授/博導原生圖是指采用免索引鄰接（Index-freeadjacency）構(gòu)建的圖數(shù)據(jù)庫引擎，如：采用免索引鄰接的數(shù)據(jù)庫為每一個節(jié)點維護了一組指向其相鄰節(jié)點的引用，這組引用本質(zhì)上可而對于Index-freeadjacency，關系是直接基于某個節(jié)點的相鄰節(jié)點獲取的(tailtohead,orheadtotail)；例如，為了查詢“whoisfriendswithAlice”,我們只需要檢索Alice的所有incomingFRIEND關系即可；這個復雜度僅與節(jié)點的鄰居個數(shù)有關，而與整個數(shù)據(jù)集的大小是無關的。重點針對圖查詢進行優(yōu)化節(jié)點存關系邊存儲文件儲文件標簽存儲文件屬性存標簽存儲文件屬性存儲文件儲文件屬性索動態(tài)存屬性索節(jié)點存儲于獨立的“節(jié)點存儲文件節(jié)點存儲于獨立的“節(jié)點存儲文件”，每個節(jié)點的存儲空間固定，如14字節(jié)，便于直接通過ID編號計算獲得訪問地址，基于這種格式，節(jié)點查詢成本為O(1)，而非O(N)每個節(jié)點首字節(jié)標明是否inUse，接下來四個字節(jié)存儲該節(jié)點的第一個關系邊的ID，再接下來四個字節(jié)存儲該節(jié)點的第一個屬性ID，再接下來4個字節(jié)存儲該節(jié)點的第一個LabelID。節(jié)點的屬性數(shù)據(jù)（如姓名、年齡等）是分開存儲的，節(jié)點只存儲其第一個屬性的ID，這樣的設計是為了保證節(jié)點遍歷的高效性。關系邊存儲于獨立的“關系存儲文件”，每個關系邊的存儲空間固定，如34字節(jié)，和節(jié)點一樣，這種設計便于直接通過ID編號計算獲得關系邊的訪問地址。每個節(jié)點首字節(jié)標明是否inUse，接下來四個字節(jié)存儲該關系邊的頭節(jié)點ID，再接下來四個字節(jié)存儲該關系邊的尾節(jié)點