維基百科

Gremlin

Gremlin是Apache軟體基金會下的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之於圖資料庫，就如同JDBC和SQL之於關係型資料庫。 同樣，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.
取自「https://zh.wikipedia.org/w/index.php?title=Gremlin&oldid=78629627」