学习笔记DB3：图数据库

分类：IT>数据库

1、图数据库的基本概念是什么？图的应用场景是什么？

图是一种灵活的数据结构，现实生活中的各类应用都可以用图来进行建模。

图可以对广泛的、各种各样的实际应用进行建模，例如：

（1）1736年哥尼斯堡七桥问题如何不重复的一次性走完七座桥？

（2）旅行商问题

（3）图着色问题

2、图的表示方法是什么？

（1）图一般用四元组（V,E,L,F）V表示顶点的集合，E表示边的集合，L表示标签的集合，F是标签生成函数，用来为图中顶点和边生成标签。例如：化学结构的表示、社交网络的表示

（2）另一种采用属性图表示，属性图由顶点、边、标签和属性组成。顶点可以包含一组属性，每个属性由键值对组成，即属性名和属性值。顶点可以被赋予一个或多个标签，每个标签代表该顶点的类别。边是有方向的，边表示源点到终点的联系。类似于顶点，边也可以包含属性和标签。

3、什么是图数据模型？

（1）数据模型的三要素为：数据结构、数据操作、数据的完整性约束条件

（2）从关系数据模型→图数据模型也有类似的要素：

属性图

可达性查询；最短路径查询；图匹配；节点排序；聚类；频繁模式挖掘

完整性约束：

4、图数据管理技术的产生和发展是怎样的？

（1）1970s层次模型、网状模型、关系模型。网状模型的表达能力最强；网状数据库之父、图灵奖获得者—Charles Bachman；但是结构复杂、查询语言不易掌握和使用、数据操作也较为复杂。

（2）随着生物信息学和社交网络的发展，2010s提出面向事务型的图数据库和面向分析型的分布式图处理系统。

5、图数据管理的应用及面临的挑战是怎样的？

数据的规模、图数据的复杂结构、多样的查询类型、计算的复杂度

6、图数据库的分类

根据应用需求不同，图数据管理系统分类：

（1）面向某一特定应用的专用图数据管理系统Oracle RDF、HP Jena、RDF 3X等

（2）通用图数据管理系统面向事务型（对应于关系型RDBMS）面向分析型（对应于数据仓库）

根据存储模型的不同，图数据库又可分为四类：

（1）基于关系存储模型开发的图数据库典型的代表是基于MySQL开发的Twitter公司的FlockDB

（2）基于图存储模型的专用图数据库。典型的代表包括Neo4J、Titan

（3）基于文档存储模型开发的图数据库。典型代表是OrientDB

（4）基于键值对存储模型开发的图数据库。典型代表是Apache Accumulo

7、为什么要有图数据管理系统？

相对于传统的关系数据库管理系统，图数据库管理系统在处理图数据时具有以下两个优点性能和灵活性

（1）性能：人，以及人与人之间的关系，构成了社交网络应用（例如微信、微博）的基本架构。社交网络的结构可以用如下的关系模式来描述。社交网络中的查询

图数据库性能优势的原因：

为每类对象单独存成文件，每个对象的大小固定。方便查询

顶点文件、联系文件、标签文件、属性文件等

（2）灵活性：

关系数据库：事先建立完整关系模式、模式修改代价太大、互联网应用需要频繁修改模式

图数据库：无需事先建立模式、图的结构变化不影响已有的查询和应用程序

8、图数据库的主要功能是什么？

面向事务的图数据库能够支持：

（1）数据对象（顶点与边）及其属性的增删改操作

（2）支持ACID事务处理

（3）提供定制的查询语言来支持、分析和检索操作

（4）数据的备份与恢复

9、如何利用图数据管理系统来存储和查询图数据？

利用Neo4J进行存储和查询

（1）查询处理引擎基于十字链表的遍历

（2）存储系统图模型

（3）查询语言类似于SQL，Neo4J的查询语言是语法接近于SQL的Cypher

Cypher：Neo4J的查询语言

简单的说，Cypher的工作原理就是通过图的模式匹配的方式找到满足条件的子图。

Cypher的基本语法结构

Create：创建数据对象

Start：通过顶点的ID或者属性的值，找到图中的起始点

Match：图的模式匹配

Where：过滤条件

Return：返回所需要的信息

注意：有些关键字，例如start where不是必选的

创建顶点刘晨

Create(:person)

一次创建多个顶点

Create(:person),(:person)

创建顶点刘晨、边friend、顶点王欣

方法1：create (:person)-[:friend]-> (:person)

方法2：

create (l:person)

create (r:person)

create l-[:friend]->r

方法3（假设顶点刘晨和王欣已经创建）：

找到刘晨顶点：match(l:User(ID:1))

找到王欣顶点：match(r:User(ID:2))

创建边friend：create l-[:friend]->r

创建面向类别属性的索引

Create index on :user(Name)

创建面向类别属性的复合索引

Create index on :user(Name,Affiliation)

创建完整性约束

Create constraint on (C:User) assert C.ID isunique

顶点查询

方法1：通过编号查找顶点

START L=NODE(0)

RETURN L

方法2：通过属性：ID查找顶点

MATCH(L:User(ID:1))

RETURN L

方法3：通过where条件

Match(L:User)

Where ID=1

RETURN L

边查询

方法1：

START L=NODE(0)

START R=NODE(1)

MATCH(L-[e:friend]->R)

方法2：

MATCH(L:User(Name:’刘晨’)-[e:friend]->R:User(Name:’王欣’))

Return e

路径查询：

查找对刘晨发的帖子点赞过的用户的信息

MATCH(:User(Name:’刘晨’))-[:Post]->(:Message)

Return L

10、分布式处理系统的必要性是什么？

（1）图的数据规模庞大

社交网络：

facebook用户：22亿用户，千亿规模的联系

新浪微博：4亿多个用户，百亿规模的联系

互联网：截止2016年12月，中国网页数量达到2360亿个。

（2）集中式下图数据库存在问题：

存不了：单机的存储能力有限

算不出：即使是相对简单的最短路径发现操作，其计算时间复杂度是O(n^2)或O(m+nlogn)，其中n是图中顶点的个数，m是边的数目，图数据规模增长导致算法代价迅速增加。更糟糕的是很多图算法的时间复杂度与顶点或边的个数呈超线性关系。

（3）分布式图处理系统的提出，新的硬件和计算环境提供了可能性。

CPU、GPU、大内存技术的发展

云计算、大数据技术的出现

11、分布式图处理系统如何兴起的？

（1）2004 MapReduce迭代的图算法&一次迭代一个MapReduce Job

主要问题：数据重复载入、木桶效应

（2）2010 Pregel采用整体同步并行计算（BSP）模型，以图顶点为中心的分布式计算框架。

优点：消除了数据的重复加载；构建以图顶点为计算中心，以消息为驱动的编程模型，易于实现各类图算法

主要问题：木桶效应、过多迭代次数和通信量

（3）2010~现在Giraph、Trinity、GPS、GraphX、Mizan、Pregel+、GraphLab、PowerGraph

出发点：消除木桶效应、减少迭代次数、减少通信量、快速故障恢复

解决方案：合理图数据划分、动态数据迁移机制、扩展以图顶点为计算中心的编程模型、异步迭代计算。

谷歌的分布式图处理系统Pregel

12、Pregel计算模型是什么？

Pregel是基于BSP(Bulk Synchronous Parallel,整体同步并行计算)模型实现的分布式图处理系统。

BSP模型的主要思想：一次BSP计算过程包含一个局部超步（Superstep），每一个超步主要包括三个步骤：局部计算、通信和屏障同步。

13、Pregel系统结构是什么？

Pregel采用主从式结构（Master、Worker）

Master任务分配、协调从节点（worker）的计算和同步、从节点的故障恢复

Worker：任务计算、节点间通信

数据存储在分布式文件系统中（例如HDFS）

临时数据存放在每个从节点的本地磁盘

14、Pregel执行过程是怎样的？

Master进行图数据的划分，每个worker读取相应的分片。

Master协调worker的计算

每个worker遍历其分片中包含的顶点，执行compute函数

各work之间的消息通信；当前superstep的同步

重复执行以上superstep，直到图中所有顶点都被标志为“非活跃（inactive）”状态，且没消息在传递

参考资料：

MOOC中国人民大学《数据库系统概论（新技术篇）》

第16讲图数据库卢卫