[發(fā)明專(zhuān)利]基于Datalog的分布式環(huán)境下大圖數(shù)據(jù)查詢(xún)方法

有效

• 申請(qǐng)?zhí)枺?/td>: 201210210245.8
• 申請(qǐng)日: 2012-06-19
• 公開(kāi)（公告）號(hào): CN102799624A
• 公開(kāi)（公告）日: 2012-11-28
• 發(fā)明（設(shè)計(jì)）人: 高軍;周家?guī)?/a>;王騰蛟;楊冬青;唐世渭
• 申請(qǐng)（專(zhuān)利權(quán)）人: 北京大學(xué)
• 主分類(lèi)號(hào): G06F17/30
• 分類(lèi)號(hào): G06F17/30
• 代理公司: 北京君尚知識(shí)產(chǎn)權(quán)代理事務(wù)所(普通合伙) 11200
• 代理人: 余長(zhǎng)江

技術(shù)領(lǐng)域

本發(fā)明具體涉及分布式環(huán)境下進(jìn)行大圖數(shù)據(jù)的查詢(xún)，具體涉及了一種基于Datalog的分布式環(huán)境下大圖數(shù)據(jù)查詢(xún)方法，屬于信息技術(shù)領(lǐng)域。

背景技術(shù)

現(xiàn)代社會(huì)中，圖的應(yīng)用越來(lái)越廣泛。社交網(wǎng)絡(luò)、生物信息、交通導(dǎo)航等領(lǐng)域技術(shù)的迅猛發(fā)展產(chǎn)生了規(guī)模龐大的圖數(shù)據(jù)。如何有效的管理這些大圖數(shù)據(jù)面臨著許多挑戰(zhàn)：首先是傳統(tǒng)的單機(jī)計(jì)算模式很難支持大圖數(shù)據(jù)的管理，單機(jī)的存儲(chǔ)能力有限，很難將整個(gè)大圖數(shù)據(jù)都加載到內(nèi)存中，同時(shí)單機(jī)的處理能力也不足，很難有效支持大圖數(shù)據(jù)上各種復(fù)雜的操作；其次是大圖數(shù)據(jù)上的應(yīng)用需求日益復(fù)雜，大圖上的操作不僅僅局限于檢索結(jié)點(diǎn)和邊這樣簡(jiǎn)單的操作，同時(shí)還包括各種復(fù)雜的查詢(xún)，比如最短路徑查詢(xún)、子圖模式匹配等。這些操作往往需要循環(huán)迭代，涉及很大的搜索空間和執(zhí)行代價(jià)。因此，利用分布式環(huán)境來(lái)對(duì)大圖數(shù)據(jù)進(jìn)行管理成為發(fā)展的必然趨勢(shì)。

目前出現(xiàn)了一些基于分布式環(huán)境的大圖數(shù)據(jù)管理系統(tǒng)，其中具有代表性的系統(tǒng)包括Google的Pregel系統(tǒng)，可具體參考【1】（Grzegorz?Malewicz,Matthew?H.Austern,Aart?J.C.Bik,James?C.Dehnert,Ilan?Horn,Naty?Leiser,Grzegorz?Czajkowski:Pregel:a?system?for?large-scale?graph?processing.SIGMOD?2010:135-146）以及Microsoft的Trinity系統(tǒng)，這兩個(gè)系統(tǒng)都不是開(kāi)源的，主要是針對(duì)圖數(shù)據(jù)管理的特點(diǎn)，專(zhuān)門(mén)開(kāi)發(fā)的大圖數(shù)據(jù)分布式管理框架，需要用戶(hù)自己使用高級(jí)編程語(yǔ)言來(lái)實(shí)現(xiàn)查詢(xún)，對(duì)用戶(hù)的專(zhuān)業(yè)知識(shí)要求較高。

目前還出現(xiàn)了基于MapReduce框架支持SQL查詢(xún)的工作，如在SIGMOD2007上出現(xiàn)的Map-Reduce-Merge的工作，如參考文件【2】（Hung-chih?Yang,Ali?Dasdan,Ruey-Lung?Hsiao,Douglas?Stott?Parker?Jr.:Map-reduce-merge:simplified?relational?data?processing?on?large?clusters.SIGMOD?2007:1029-1040）,以及在hadoop環(huán)境中采用類(lèi)SQL語(yǔ)言進(jìn)行分析的Hive系統(tǒng)，可參考文件【3】（Ashish?Thusoo,Joydeep?Sen?Sarma,Namit?Jain,Zheng?Shao,Prasad?Chakka,Ning?Zhang,Suresh?Anthony，Hao?Liu,Raghotham?Murthy:Hive-a?petabyte?scale?data?warehouse?using?Hadoop.ICDE?2010:996-1005）。但是，此類(lèi)工作只是考慮單個(gè)關(guān)系數(shù)據(jù)的操作符號(hào)，并沒(méi)有考慮圖遞歸Datalog查詢(xún)對(duì)MapReduce函數(shù)生成和優(yōu)化的影響。

針對(duì)Datalog查詢(xún)的研究曾經(jīng)是數(shù)據(jù)管理領(lǐng)域重點(diǎn)，如參考文件【4】（Serge?Abiteboul,Richard?Hull,and?Victor?Vianu.Foundations?of?Databases.http://webdam.inria.fr/Alice/.）Datalog查詢(xún)表達(dá)能力強(qiáng)，用戶(hù)能夠以簡(jiǎn)潔的方式表達(dá)其查詢(xún)要求。本發(fā)明主要是利用Datalog對(duì)圖數(shù)據(jù)進(jìn)行查詢(xún)，圖數(shù)據(jù)需要較為復(fù)雜的遞歸循環(huán)處理。本發(fā)明擴(kuò)展了Datalog查詢(xún)語(yǔ)言，所設(shè)計(jì)的Datalog查詢(xún)顯式地給出循環(huán)的終止條件，支持更多的系統(tǒng)函數(shù)，在不增加用戶(hù)太多負(fù)擔(dān)的情況下，擴(kuò)展了圖查詢(xún)的表達(dá)能力。

大圖數(shù)據(jù)管理系統(tǒng)建設(shè)的一種方案是充分考慮圖數(shù)據(jù)管理的特點(diǎn)和需求，完全從底層開(kāi)始的實(shí)現(xiàn)。這種方式的優(yōu)點(diǎn)是能夠針對(duì)大圖數(shù)據(jù)作出特定的優(yōu)化，系統(tǒng)管理大圖數(shù)據(jù)比較自然。缺點(diǎn)是需要自己專(zhuān)門(mén)實(shí)現(xiàn)數(shù)據(jù)分布、任務(wù)調(diào)度、數(shù)據(jù)副本、結(jié)點(diǎn)失敗等通用分布式計(jì)算框架的功能，這會(huì)帶來(lái)龐大的工程實(shí)現(xiàn)代價(jià)，同時(shí)也沒(méi)有辦法利用已有系統(tǒng)積累的優(yōu)勢(shì)。

發(fā)明內(nèi)容

本發(fā)明針對(duì)利用現(xiàn)有相對(duì)成熟的MapReduce分布式計(jì)算框架來(lái)對(duì)大圖數(shù)據(jù)進(jìn)行查詢(xún)，針對(duì)現(xiàn)有框架下大圖數(shù)據(jù)查詢(xún)性能難以滿(mǎn)足應(yīng)用需求、用戶(hù)編寫(xiě)圖數(shù)據(jù)處理腳本繁瑣低效等問(wèn)題，設(shè)計(jì)了一種基于Datalog的MapReduce分布式環(huán)境下大圖數(shù)據(jù)查詢(xún)方法。該方法的設(shè)計(jì)主要包括如下三方面的內(nèi)容：描述性圖查詢(xún)語(yǔ)言的設(shè)計(jì)、描述性查詢(xún)語(yǔ)言執(zhí)行計(jì)劃的產(chǎn)生和描述性查詢(xún)語(yǔ)言執(zhí)行計(jì)劃的優(yōu)化。