當(dāng)前互聯(lián)網(wǎng)系統(tǒng)時(shí)刻都在產(chǎn)生海量非結(jié)構(gòu)化、相互關(guān)聯(lián)的數(shù)據(jù),這些數(shù)據(jù)往往由于系統(tǒng)不斷演進(jìn)不具備統(tǒng)一的格式,并且對(duì)象類型千變?nèi)f化,對(duì)象之間關(guān)系復(fù)雜多變。圖數(shù)據(jù)庫(kù)作為一種新型的專門為存儲(chǔ)圖數(shù)據(jù)而設(shè)計(jì)的數(shù)據(jù)庫(kù),能夠很好適應(yīng)這種數(shù)據(jù)應(yīng)用場(chǎng)景,它是當(dāng)前一個(gè)研究熱點(diǎn)。目前圖數(shù)據(jù)庫(kù)的發(fā)展中的困難和瓶頸主要集中在兩個(gè)方面。其一,如何設(shè)計(jì)一個(gè)基于原生圖存儲(chǔ)的數(shù)據(jù)庫(kù),而不是簡(jiǎn)單的在其它類型數(shù)據(jù)庫(kù)存儲(chǔ)引擎的基礎(chǔ)上進(jìn)行語(yǔ)義封裝。如果不能在存儲(chǔ)層就考慮到圖數(shù)據(jù)的鄰近性和關(guān)系查詢,其性能必然得不到本質(zhì)的提升。其二,如何提供一個(gè)具有豐富圖查詢能力的計(jì)算層,它可以為用戶提供一種基于圖的思想來(lái)查詢數(shù)據(jù)庫(kù)的能力。其它類型的查詢語(yǔ)言在對(duì)圖數(shù)據(jù)查詢的表達(dá)上有著先天不足,不足以勝任圖數(shù)據(jù)庫(kù)的查詢工作。本文提出了一個(gè)高性能分布式圖數(shù)據(jù)庫(kù)架構(gòu)以解決以下技術(shù)難點(diǎn):1.本文中采用基于Hash的數(shù)據(jù)分布算法來(lái)在分布式場(chǎng)景下基于圖數(shù)據(jù)的臨近性高效地索引點(diǎn)和邊。通過(guò)將圖劃分為多個(gè)分片,并使用專門設(shè)計(jì)的數(shù)據(jù)存儲(chǔ)格式和在物理上選擇相近的位置存儲(chǔ)等方法來(lái)加速點(diǎn)和邊的索引。2.本文采用額外的抽象層和基于表格的數(shù)據(jù)抽象保證所有的算子具有一個(gè)通用的基于事件... 

【文章來(lái)源】：電子科技大學(xué)四川省 211工程院校 985工程院校 教育部直屬院校

【文章頁(yè)數(shù)】：86 頁(yè)

【學(xué)位級(jí)別】：碩士

【部分圖文】：

簡(jiǎn)單查詢的AST語(yǔ)法樹

第五章性能測(cè)試65圖5-4則展示了其生成的邏輯執(zhí)行計(jì)劃。可以看到，其產(chǎn)生的邏輯執(zhí)行是符合預(yù)期的。圖框中圈出的第二行的ProduceResult算子后描述表示會(huì)返回其中的id屬性。圖5-4邏輯執(zhí)行計(jì)劃生成的物理執(zhí)行計(jì)劃如圖5-5。從圖中可以看到，AllNodeScan算子和ProduceResult算子均被劃分為了兩個(gè)分片，其中AllNodeScan算子的分片1被劃分到了192.168.1.72:7777上運(yùn)行的圖查詢節(jié)點(diǎn)中，分片2被劃分到了192.168.1.73:7777上運(yùn)行的圖查詢節(jié)點(diǎn)中，由于當(dāng)前集群中一共只有2個(gè)圖查詢節(jié)點(diǎn)，因此這種劃分是正確且有效的。圖5-5物理執(zhí)行計(jì)劃接下來(lái)以更加復(fù)雜的一條語(yǔ)句為輸入，檢查整個(gè)系統(tǒng)是否能夠正常工作：“match(n)-[]->(p)wheren.id=p.idreturnn.id”。該條語(yǔ)句中包含了一個(gè)一級(jí)關(guān)系查詢和一次Join操作，其期望邏輯執(zhí)行計(jì)劃應(yīng)形如圖5-6。ProduceResultJoinAllNodeScanExpand圖5-6復(fù)雜語(yǔ)句的期望執(zhí)行計(jì)劃其在系統(tǒng)執(zhí)行后輸出的AST語(yǔ)法樹，邏輯執(zhí)行計(jì)劃和物理執(zhí)行計(jì)劃分別如圖5-7，圖5-8和圖5-9。從圖5-7中可以看出，AST的生成結(jié)果與第四章邏輯執(zhí)行計(jì)劃生成算法中提到的情況類似，AST中主要包含了MATCH和RETURN兩個(gè)大的

電子科技大學(xué)碩士畢業(yè)論文66子句，其中Match子句中又包含了一個(gè)Path和一個(gè)BinaryOperator（二元運(yùn)算符）。其中Path代表的是語(yǔ)句中“(n)-[]->(p)”這一部分，指代關(guān)系查詢。BinaryOperator代表的是語(yǔ)句中“wheren.id=p.id”這一部分。這里的BinaryOperator的運(yùn)算符（即圖中的value）是“=”符號(hào)，因此可以生成Join算子。但如果遇到的是“>”之類的大小比較符，圖中后續(xù)就會(huì)生成Apply算子。圖5-7復(fù)雜語(yǔ)句的抽象語(yǔ)法樹從圖5-8中可以看出，在邏輯計(jì)劃中一共生成了4個(gè)邏輯算子。位于對(duì)底層的算子是AllNodeScan算子，該算子將會(huì)做全圖掃描，對(duì)應(yīng)查詢語(yǔ)句中“(n)”所代表的操作。Expand算子用于在前一個(gè)AllNodeScan算子的基礎(chǔ)上對(duì)其按任意邊進(jìn)行一次擴(kuò)展，對(duì)應(yīng)查詢語(yǔ)句中“(n)-[]->(p)的部分”。Join算子用于將結(jié)果集n和結(jié)果集p進(jìn)行比較，取出n中與p中id相等的行，對(duì)應(yīng)查詢語(yǔ)句中“wheren.id=p.id”。最后符合條件行通過(guò)ProduceResult算子進(jìn)行輸出，對(duì)應(yīng)查詢語(yǔ)句中“returnn.id”。圖5-8復(fù)雜語(yǔ)句的邏輯執(zhí)行計(jì)劃從圖5-9中可以看出，在物理計(jì)劃中一共有6個(gè)物理算子算子生成。其中邏輯執(zhí)行計(jì)劃中AllNodeScan算子和Expand算子被拆分成了兩個(gè)物理算子，并且分別


本文編號(hào)：2988100