GremlinApache軟件基金會下的Apache TinkerPop開發的圖遍歷語言和虛擬機。Gremlin適用於基於OLTP的圖數據庫以及基於OLAP的圖處理器。Gremlin的函數式語言自動機基礎使Gremlin能夠自然地支持指令式聲明式查詢、主機語言不可知性、用戶定義的領域特定語言、可擴展的編譯器/優化器、單機和多機運行模型、混合深度和廣度優先評估以及圖靈完備性[2]

Gremlin
設計者Marko A. Rodriguez
實作者Apache軟件基金會下的Apache TinkerPop
面市時間2009年,​15年前​(2009
當前版本
  • 2.6.0 (2014年9月17日)[1]
編輯維基數據鏈接
操作系統跨平台
許可證Apache許可證
網站tinkerpop.apache.org/gremlin.html
衍生副語言
Gremlin-Java8, Gremlin-Groovy, Gremlin-Python, Gremlin-Scala, Gremlin-Clojure, Gremlin-PHP, Gremlin-JavaScript, Gremlin-Typeset
啟發語言
正則表達式, XPath, Ripple, SPARQL, SQL, Java/JVM

作為一個解釋性的類比,Apache TinkerPop和Gremlin之於圖數據庫,就如同JDBCSQL之於關係型數據庫。 同樣,Gremlin遍歷機與圖計算的關係也類似於為Java虛擬機與通用計算之間的關係。[3]

歷史

編輯
  • 2009-10-30 項目誕生,並被命名為「TinkerPop」
  • 2009-12-25 v0.1是第一個版本
  • 2011-05-21 v1.0發布
  • 2012-05-24 v2.0發布
  • 2015-01-16 TinkerPop成為Apache孵化器項目
  • 2015-07-09 v3.0.0 孵化版發布
  • 2016-05-23 Apache TinkerPop成為一個Apache頂級項目
  • 2016-07-18 v3.1.3和v3.2.1是第一次作為Apache TinkerPop發布的版本
  • 2017-12-17 v3.3.1發布
  • 2018-05-08 v3.3.3發布

供應商的一體化

編輯

Gremlin是Apache2許可的圖遍歷語言,可供圖系統供應商使用。通常有兩種類型的圖系統供應商:OLTP圖數據庫和OLAP圖處理器。下表概述了支持Gremlin的圖系統供應商。

供應商 圖系統
Neo4j 圖數據庫
OrientDB 圖數據庫
DataStax Enterprise(5.0+) 圖數據庫
Hadoop (Giraph) 圖處理器
Hadoop (Spark) 圖處理器
InfiniteGraph 圖數據庫
JanusGraph 圖數據庫
Cosmos DB 圖數據庫
Amazon Neptune 圖數據庫
Ontotext GraphDB Triplestore

圖遍歷示例

編輯

以下Gremlin-Groovy環境中的Gremlin查詢和響應示例與MovieLens數據集的圖表示有關。[4] 該數據集包括為電影評分的用戶,每個用戶都有各自的職業,每部電影都有一個或多個與之相關的類別,MovieLens圖表架構詳述如下。

user--rated[stars:0-5]-->movie
user--occupation-->occupation
movie--category-->category

簡單遍歷

編輯
gremlin> g.V().label().groupCount()
==>[occupation:21, movie:3883, category:18, user:6040]
gremlin> g.V().hasLabel('movie').values('year').min()
==>1919
gremlin> g.V().has('movie','name','Die Hard').inE('rated').values('stars').mean()
==>4.121848739495798

投影遍歷

編輯
gremlin> g.V().hasLabel('category').as('a','b').
           select('a','b').
             by('name').
             by(inE('category').count())
==>[a:Animation, b:105]
==>[a:Children's, b:251]
==>[a:Comedy, b:1200]
==>[a:Adventure, b:283]
==>[a:Fantasy, b:68]
==>[a:Romance, b:471]
==>[a:Drama, b:1603]
==>[a:Action, b:503]
==>[a:Crime, b:211]
==>[a:Thriller, b:492]
==>[a:Horror, b:343]
==>[a:Sci-Fi, b:276]
==>[a:Documentary, b:127]
==>[a:War, b:143]
==>[a:Musical, b:114]
==>[a:Mystery, b:106]
==>[a:Film-Noir, b:44]
==>[a:Western, b:68]
gremlin> g.V().hasLabel('movie').as('a','b').
           where(inE('rated').count().is(gt(10))).
           select('a','b').
             by('name').
             by(inE('rated').values('stars').mean()).
           order().by(select('b'),decr).
           limit(10)
==>[a:Sanjuro, b:4.608695652173913]
==>[a:Seven Samurai (The Magnificent Seven), b:4.560509554140127]
==>[a:Shawshank Redemption, The, b:4.554557700942973]
==>[a:Godfather, The, b:4.524966261808367]
==>[a:Close Shave, A, b:4.52054794520548]
==>[a:Usual Suspects, The, b:4.517106001121705]
==>[a:Schindler's List, b:4.510416666666667]
==>[a:Wrong Trousers, The, b:4.507936507936508]
==>[a:Sunset Blvd. (a.k.a. Sunset Boulevard), b:4.491489361702127]
==>[a:Raiders of the Lost Ark, b:4.47772]

聲明式模式匹配遍歷

編輯

Gremlin支持類似於SPARQL的聲明式圖模式匹配。例如,下面的查詢使用了Gremlin的match() 步驟。

gremlin> g.V().
           match(
             __.as('a').hasLabel('movie'),
             __.as('a').out('category').has('name','Action'),
             __.as('a').has('year',between(1980,1990)),
             __.as('a').inE('rated').as('b'),
             __.as('b').has('stars',5),
             __.as('b').outV().as('c'),
             __.as('c').out('occupation').has('name','programmer'),
             __.as('c').has('age',between(30,40))).
           select('a').groupCount().by('name').
           order(local).by(valueDecr).
           limit(local,10)
==>Raiders of the Lost Ark=26
==>Star Wars Episode V - The Empire Strikes Back=26
==>Terminator, The=23
==>Star Wars Episode VI - Return of the Jedi=22
==>Princess Bride, The=19
==>Aliens=18
==>Boat, The (Das Boot)=11
==>Indiana Jones and the Last Crusade=11
==>Star Trek The Wrath of Khan=10
==>Abyss, The=9

OLAP遍歷

編輯
gremlin> g = graph.traversal(computer(SparkGraphComputer))
==>graphtraversalsource[hadoopgraph[gryoinputformat->gryooutputformat], sparkgraphcomputer]
gremlin> g.V().repeat(outE('rated').has('stars', 5).inV().
                 groupCount('m').by('name').
                 inE('rated').has('stars', 5).outV()).
               times(4).cap('m')
==>Star Wars Episode IV - A New Hope	  35405394353105332
==>American Beauty	  31943228282020585
==>Raiders of the Lost Ark	31224779793238499
==>Star Wars Episode V - The Empire Strikes Back  30434677119726223
==>Godfather, The	30258518523013057
==>Shawshank Redemption, The	28297717387901031
==>Schindler's List	27539336654199309
==>Silence of the Lambs, The	26736276376806173
==>Fargo	 26531050311325270
==>Matrix, The	 26395118239203191

Gremlin圖遍歷機

編輯

Gremlin是一個由指令集和執行引擎組成的虛擬機。下表在Gremlin和Java之間進行了類比。

Java生態系統 Gremlin生態系統
Apache Groovy編程語言 Gremlin-Groovy
Scala編程語言 Gremlin-Scala
Clojure編程語言 Gremlin-Clojure
Java編程語言 Gremlin-Java8
Java指令集 Gremlin步驟庫
Java虛擬機 Gremlin遍歷機

Gremlin步驟(指令集)

編輯

以下歷是一個Gremlin遍歷在Gremlin-Java8的方言。

g.V().as("a").out("knows").as("b").
  select("a","b").
    by("name").
    by("age")

Gremlin語言(即表達圖遍歷的流式接口)可以用任何支持函數組合和函數嵌套的宿主語言表示。由於這個簡單的要求,存在各種Gremlin方言,包括Gremlin-Groovy、Gremlin-Scala和Gremlin-Clojure等。上面的Gremlin-Java8遍歷最終被編譯成稱為遍歷(traversal)的步驟序列。下面提供了遍歷的字符串表示。

[GraphStep([],vertex)@[a], VertexStep(OUT,[knows],vertex)@[b], SelectStep([a, b],[value(name), value(age)])]

這些步驟(steps)是Gremlin圖遍歷機的原語。它們是機器最終執行的參數化指令。Gremlin指令集大約有30個步驟。這些步驟足以提供通用計算以及表達任何圖遍歷查詢的共同主題通常所需的內容。 鑑於Gremlin是一種語言、一個指令集和一個虛擬機,可以設計另一種編譯為Gremlin遍歷機器的遍歷語言(類似於Scala如何編譯到JVM)。例如,可以編譯流行的SPARQL圖模式匹配語言以在Gremlin機器上執行。以下SPARQL查詢

SELECT ?a ?b ?c
WHERE {
  ?a a Person .
  ?a ex:knows ?b .
  ?a ex:created ?c .
  ?b ex:created ?c .
  ?b ex:age ? d .
    FILTER(?d < 30)
}

將被編譯到

[GraphStep([],vertex), MatchStep(AND,[[MatchStartStep(a), LabelStep, IsStep(eq(Person)), MatchEndStep], [MatchStartStep(a), VertexStep(OUT,[knows],vertex), MatchEndStep(b)], [MatchStartStep(a), VertexStep(OUT,[created],vertex), MatchEndStep(c)], [MatchStartStep(b), VertexStep(OUT,[created],vertex), MatchEndStep(c)], [MatchStartStep(b), PropertiesStep([age],value), MatchEndStep(d)], [MatchStartStep(d), IsStep(gt(30)), MatchEndStep]]), SelectStep([a, b, c])].

在Gremlin-Java8中,上面的SPARQL查詢將被編譯為相同的Gremlin步驟序列(即遍歷),其表示如下。

g.V().match(
  as("a").label().is("person"),
  as("a").out("knows").as("b"),
  as("a").out("created").as("c"),
  as("b").out("created").as("c"),
  as("b").values("age").as("d"),
  as("d").is(gt(30))).
    select("a","b","c")

Gremlin機(虛擬機)

編輯

Gremlin圖遍歷機可以在單台機器上執行,也可以在多機計算集群上執行。執行不可知論允許Gremlin在圖數據庫(OLTP)和圖處理器(OLAP)上運行。

參考文獻

編輯
  1. ^ Release 2.6.0. 2014年9月17日 [2020年5月29日]. 
  2. ^ Rodriguez, Marko A. The Gremlin graph traversal machine and language (invited talk). 2015: 1–10. ISBN 9781450339025. arXiv:1508.03843 . doi:10.1145/2815072.2815073. 
  3. ^ The Benefits of the Gremlin Graph Traversal Machine. 2015-09-14 [2015-09-17]. (原始內容存檔於2018-10-30). 
  4. ^ The Gremlin Graph Traversal Language. 2015-08-19 [2015-08-22]. (原始內容存檔於2020-11-08). 

外部連結

編輯
  1. Apache TinkerPop主頁頁面存檔備份,存於網際網路檔案館
  2. GremlinDocs.com (TinkerPop2)
  3. sql2gremlin.com (TinkerPop2)
  4. Rodriguez, M.A., "The Gremlin Graph Traversal Machine and Language," Proceedings of the ACM Database Programming Languages Conference, October, 2015.