google Cayley图谱数据库初试

一.安装

mkdir cayley

cd cayley

mkdir src

export GOPATH=$(pwd)

go get github.com/google/cayley

go build src/github.com/google/cayley/cayley.go

其中缺什么包下什么包，没有hg工具安装hg

修改下源码cayley.go

    switch cmd {
    case "init":
        db.Init(cfg, *tripleFile)
    case "load":
        ts, _ = db.Open(cfg)
        db.Load(ts, cfg, *tripleFile)
        ts.Close()
    case "repl":
        ts, _ = db.Open(cfg)　　　　　　　　　　
        db.Repl(ts, *queryLanguage, cfg)
        ts.Close()
    case "http":
        ts, _ := db.Open(cfg)
        http.Serve(ts, cfg)
        ts.Close()
    default:
        fmt.Println("No command", cmd)
        flag.Usage()
    }

运行

go build $GOPATH/src/github.com/google/cayley/cayley.go && ./cayley http --port=8080 --assets=$GOPATH/src/github.com/google/cayley --dbpath=src/testdata.nt

assets 参数代表启动http server以后存放html静态资源的目录，源码里是自带的

dbpath 是数据库的一些初始化数据，必须指定，不然启动了，也没法添加数据，默认是指定为/tmp/testdb文件

在浏览器输入http://127.0.0.1:8080/如果有页面输出说明成功了

二.基本概念

testdata.nt内容如下

alice follows bob .
bob follows alice .
charlie follows bob .
dani follows charlie .
dani follows alice .
alice is cool .
bob is "not cool" .
charlie is cool .
dani is "not cool" .

内容的每行都是以空格分隔的四元组，每一行叫做一个Triple，存储多个Triple组成了TripleStore，每个Triple由四部分组成，依次对应数据每行用空格分隔的每项，分别叫Subject，Predicate，Object，Provenance。对应中文里的，Subject是中文里的主语，Predicate是中文里的谓语，Object是宾语，Provenance是来源。也就是说，每行描述了，谁怎么样了XX，或者谁是XX样的。Subject转换成有向图中的顶点，Object是出度的顶点，Predicate是路径。

cayley搭了一套图数据库的框架，官方提供了三种存储memory,leveldb,mongodb 可以切换存储引擎，只需要实现接口，就可以扩展存储方式，和mysql与innodb的关系差不多。

三.使用API

1. g.V()

取一个图中的顶点，也就是Triple中的Subject，返回一个点的对象

2. path.Out(`[predicatePath], [tags]`)

Out是取一个顶点的出度。不过，这个出度是按照谓词区分的，当Out()不传递参数的时候，是取出某个顶点不按路径区分的所有出度；当Out传递了predicatePath参数的时候，是取出某个顶点，在某个路径上的所有出度。tags 是用来存储路径的名称。例如：

我们入库的数据中以alice顶点为例，

alice follows bob
alice is cool

可以看出alice这个顶点有两个路径，分别是follows和is

(1) 查询allice的所有出度

g.V("alice").All()

(2) 查询alice的关注：

g.V("alice").Out("follows").All()

(3) 查询allice是否很cool

g.V("alice").Out("is").All()

(4) 查询alice的关注和是否很cool

g.V("alice").Out(["follows", "is"]).All()

"result": [
  {
   "id": "bob"
  },
  {
   "id": "cool"
  }
 ]

(5) 虽然你可以直观的看到，alice的关注是bob，并且alice是个很酷的人，那是因为是通过字面意思，比如有些人follows为空，有些人is为空，那就没法判断返回的出度在哪个路径上，这个时候应该使用tag参数

g.V("alice").Out(["follows", "is"], "path").All()

3. path.In(`[predicatePath], [tags]`)

和Out正好相反，是求的入度。

(1) 求所有cool的人

g.V("cool").In("is").All()

(2) alice的粉丝

g.V("alice").In("follows").All()

4. path.Both(`[predicatePath], [tags]`)

In和Out的的结果并集，没有去重

5. path.Has(`predicate, object`)

反向查找，paredicate是路径，object是三元组中的宾语

(1) 查找alice的粉丝

g.V().Has("follows", "alice").All()

6.path.Follow(morphism)

通过管道加速

g.V().Has("name","Casablanca") .Out("/film/film/starring").Out("/film/performance/actor") .Out("name").All()

等价于

var filmToActor = g.Morphism().Out("/film/film/starring").Out("/film/performance/actor")

g.V().Has("name", "Casablanca").Follow(filmToActor).Out("name").All()

总体的查询模式就是，选顶点，选路径，ALL输出

四. Triple,基于内存的TripleStore数据结构

1.数据结构

type Triple struct {
　　Subject string
　　Predicate string
　　Object string 
　　Provenance string
}

三元组，Provenance好像是类似于数据库里的分库的概念（不大确定），Triple中不同的字段，在后面叫Direction

type TripleStore struct {
　　idCounter int64　　　　　　　　　　　//idMap的长度　　　　　
　　tripleIdCounter int64　　　　　　　 //tripleId的序列
　　idMap map[string]int64　　　　　　　//存储三元组的 内容->tripleId 的对应关系
　　revIdMap map[int64]string　　　　　//存储三元组的 tripleId->内容 的对应关系 idMap的反向映射关系
　　triples []graph.Triple　　　　　　 //存储每条记录的关系三元组
　　size int64　　　　　　　　　　　　　 //triples的数量
　　index TripleDirectionIndex　　　　//triples的索引 每个idMap中的一个key有一个平衡二叉树，里面放了tripleId
}

TripleDirectionIndex是一个通过Direction作为分组的一级索引

type TripleDirectionIndex struct {
    subject    map[int64]*llrb.LLRB　　
    predicate  map[int64]*llrb.LLRB
    object     map[int64]*llrb.LLRB
    provenance map[int64]*llrb.LLRB
}

2.实例演示

数据

alice follows bob .

bob follows alice .

charlie follows bob .

建立以后的结果如下

　　　　　　　　　　idMap revIdMap

　　　　　　　　　　1 <=============> alice

　　　　　　　　　　2 <=============> follows

　　　　　　　　　　3 <=============> bob

　　　　　　　　　　4 <=============> charlie

　　　　　　　　　　　　　　　　　　triples

　　　　　　Direction　　DirectionSubject　　DirectionPredicate 　　DirectionObject

tripleId　　1　　　　　　 alice　　　　　　　　follows　　　　　　　　bob

　　　　　 2　　　　　　 bob　　　　　　　　 follows　　　　　　　　alice

　　　　　 3　　　　　　 charlie　　　　　　 follows　　　　　　　　bob　　

　　　　　　　　　　　　　　　　　　DirectionIndex

　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　 1　　=========>　　(1)

　　　　　　　　DirectionSubject=============>　　　 3　　=========>　　(2)

　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　4　　=========>　　(3)　　　　　　

　　　　　　　　DirectionPredicate============>　　　 2　　=========> 插入第一行时(1) ---> 插入第二行 (2) 　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　 /　　

　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　(1)

　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　-----> 插入第三行 (2)

　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　(1) (3)

　　　　　　　　DirectionObject==============>　　　3 ============> 插入第一行 (1) ---> 插入第三行 (3)

　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　(1)

　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　 1 =============> (2)

DirectionIndex中的1 是IdMap中的编号，（1）是triples中的tripleId

3.查询方法

看源码里把查询逻辑都写在了itorator里，各种hasA,and,or,link!@#!4。

如果查一个值的入度就是先查DirectionObject索引，查出度就查DirectionSubject索引，有路径条件就再在DirectionPredicate里做二分排除掉。