Skip to content

Latest commit

 

History

History
341 lines (218 loc) · 22.4 KB

图数据库记录.md

File metadata and controls

341 lines (218 loc) · 22.4 KB
Raw

图数据记录

什么是ThinkerPop Apache

TinkerPop是一个面向实时事务处理（OLTP:online transaction processing）以及批量、分析型（OLAP: oneline analytical processing）的开源的图计算框架。TinkerPop是一个可以应用于不同图形数据库的抽象层，避免应用程序与特定数据库高度依赖。

提供通用的API和工具，使开发人员可以基于不同图数据库轻松创建图形应用程序，使图形数据库与图计算解耦，方便切换不同图形数据库，简化其工作。

gremlin

gremlin是TinkerPop图形遍历语言，使用户能够以简但的代码进行复杂的图形遍历，Gremlin具有“写一次，随处运行” 的特点。意味着，所有支持TinkerPop的图形系统都可以使用Gremlin语言进行图形遍历。

image

如何使用gremlin？

如何连接到一个图是一个多方面的主题，本质上是沿着，Gremlin遍历机器（Gremlin Traversal Machine）在哪？这个问题的答案来简单划分。这个问题之所以如此重要，是因为GTM负责处理遍历。可以用任何语言编写Gremlin遍历，但是如果没有GTM，就无法对启用TinkerPop的图形执行遍历。GTM通常位于下列地方之一：

嵌入到java应用中。

托管在gremlin服务器中。

由远程gremlin提供程序（RGP：Remote Gremlin Provider）托管

  1. 嵌入java中

TinkerPop维护GTM的参考实现，GTM是用Java编写的，因此可用于Java虚拟机(JVM)。这是一个经典的实现方式，但并不是一定需要java，任何其他JVM语言都可以。在某些情况下，有一些特定于语言的包装器可以帮助Gremlin更方便地在该语言的风格和功能中使用。这些包装器的示例包括gremlin-Scala和Ogre(适用于Clojure)。

在这种模式下，用户将首先创建一个图形实例，然后创建一个GraphTraversalSource，它是生成Gremlin遍历的类。允许这种直接实例化的图形显然是基于JVM(或具有基于JVM的连接器)并直接实现TinkerPop接口的图形。

Graph grpah = TinkerGraph.open();

然后，“图”生成一个GraphTraversalSource，如下所示，通常按照惯例，这个变量名为“g”：

GraphTraversalSource g = graph.traversal();
List<Vertex> vertices = g.V().toList();

尽管TinkerPop社区致力于确保所有使用模式之间的行为一致，但嵌入式模式确实提供了最大程度的灵活性和控制。而且有许多特性只在使用JVM语言时才能工作。下面列出了这些特性：

Lambdas可以用本机语言编写，这是很方便的，但是，如果需要从嵌入式模式转换，就会降低Gremlin的可移植性。请参阅关于lambdas部分的说明中的更多内容。

任何涉及扩展TinkerPop Java接口的特性-例如VertexProgram、TraversalStrategy等-都绑定到JVM。在某些情况下，这些特性可以为非JVM语言所访问，但显然它们必须首先为JVM开发。

某些依赖lambda或其他JVM配置的内置TraversalStrategy实现可能无法以任何其他方式使用。

序列化(例如GraphSON)没有边界，因为嵌入的图形只处理Java对象。

更好地控制图形事务。

直接访问较低级别的API-例如“structure”API方法，如Vertex和Edge接口方法。正如本文档的其他部分所提到的，TinkerPop不建议最终用户直接使用这些方法。

  1. Gremlin Server

基于JVM的图形可能托管在TinkerPop的Gremlin服务中。Gremlin Server将图抽象为不同客户端都可以连接的端点，实质上提供了一个远程GTM。Gremlin Server为客户端提供了多种方法的接口来连接他：

  • Websockets with a custom sub-protocol
    • 基于字符串的Gremlin脚本
    • 基于字节码的Gremlin遍历
  • HTTP for string-based scripts

我们鼓励用户在WebSocket中使用基于字节码的方法，因为它允许用户用自己选择的语言编写Gremlin。连接看起来有点类似于嵌入式方法，因为需要创建一个GraphTraversalSource。在嵌入式方法中，该对象的创建方法是从生成该对象的GraphObject派生出来的。但是在这种情况下，图形实例只存在于服务器上，这意味着没有图形实例在本地创建。方法是使用AnonyousTraversalSource匿名创建GraphTraversalSource，然后应用一些“远程”选项来描述要连接到的Gremlin服务器的位置：

python:

from gremlin_python.process.anonymous_traversal_source import traversal

g = traversal().withRemote(
    DriverRemoteConnection('ws://localhost:8182/gremlin','g'))

java:

import static org.apache.tinkerpop.gremlin.process.traversal.AnonymousTraversalSource.traversal;

GraphTraversalSource g = traversal().withRemote('conf/remote-graph.properties');

正如上一节中的嵌入式方法所示，一旦定义了“g”，编写Gremlin在结构和概念上都是相同的，而不管编程语言如何。

模式限制

上一节概述了关于嵌入式模型的它所具有的一些优点，这是因为完整的GTM是以它的起源语言(即Java)向用户提供的。这些项目中有一些重点关注的重要概念需要在这里提及。

  • 其中第一个点是序列化。当Gremlin Server收到请求时，必须将结果序列化为客户端请求的表单，然后客户端将这些结果反序列化为语言本身的对象。TinkerPop有两种与Gryo和GraphSON一起使用的格式。Gryo是只使用JVM的格式，因此它的优点是序列化和反序列化发生在客户机和服务器端JVM的原生类上。由于客户端可以完全访问与服务器相同的类，因此它本身基本上有一个完整的GTM，因此能够执行一些稍微高级一些的事情。
  • 一个很好的例子是subgraph()-步骤，它返回图形实例作为其结果。从服务器返回的子图可以反序列化为客户机上的实际图形实例，这意味着可以从它生成一个GraphTraversalSource，以便在客户端执行本地Gremlin遍历。对于非JVM 的Gremlin语言变体，无法反序列化查询结果为本地图，也没有GTM处理Gremlin，因此这样的结果无法完成太多工作。
  • 第二点是。因为没有GTM，所以没有“structure”API，因此像Vertex和Edge这样的图形元素只是“引用”。“引用”意味着它们只包含元素的id和标签，而不包含属性。为了保持一致性，即使是基于JVM的语言在与远程Gremlin服务器对话时也有这一限制。
  • 第三个也是最后一点涉及事务。在此模式下，一个遍历等价于单个事务，并且TinkerPop无法将多个遍历串到同一个事务中。
  1. Remote Gremlin Provider（RGPs）

远程Gremlin提供者(RGPs)越来越多地出现在图形数据库空间中。在TinkerPop术语中，这类图形提供程序是由那些只支持Gremlin语言的人定义的。通常，这些是基于服务器的图形，通常是基于云的，它们接受Gremlin脚本或字节码作为请求并返回结果。它们通常实现GremlinServer协议，这使得TinkerPop驱动程序能够像与GremlinServer一样连接到它们。因此，典型的连接方法与前一节中提出的连接方法是相同的，并在最后指出了相同的注意事项。

尽管利用TinkerPop协议和驱动程序是一种经典的方式，但RGPs并不需要这样做才能被视为启用了TinkerPop。RGPs很可能有自己的驱动程序和协议，这些驱动程序和协议可以插入到<gremlin驱动程序变体、Gremlin语言变体>，并可能允许更高级的选项，如更好的安全性、集群感知、批处理请求或其他功能。这些不同系统的详细信息超出了本文档的范围，因此一定要查阅它们的文档以获得更多信息。

这种方式在python中对应的使用方式是

from gremlin_python.driver import client
from gremlin_python.driver.serializer import GraphSONSerializersV3d0

graph_client = client.Client('ws://localhost:8182/gremlin', 'g', 
                             message_serializer=GraphSONSerializersV3d0())

使用这种方式可以使用，python中的函数方式调用gremlin语法，但是貌似这样还是有些限制的，有待后续发掘。

ThinkerPop与图交互的两种方式

TinkerPop提供了两种与图形交互的主要方法：联机事务处理(OLTP)和联机分析处理(OLAP)。这在最开始就有提及。

OLTP在TinkerPop中主要是用来进行图的查询和遍历，并且它只是进行少量数据的查询和使用（相对整个图的数据来说）。而OLAP是专门进行图计算的，但是OLAP的计算通常是耗时，离线的。这要求OLAP需要大量的计算资源，官方的教程里是结合Hadoop和Spark的（这可能我们想在的业务需求不符）。

  • OLTP: real-time, limited data accessed, random data access, sequential processing, querying
  • OLAP: long running, entire data set accessed, sequential data access, parallel processing, batch processing

图计算

VertexProgram

GraphComputer采用VertexProgram。顶点程序可以看作是在逻辑上并行地在每个顶点执行的一段代码，直到满足某种终止条件(例如，已经发生了多次迭代，图形中的数据没有变化等)。提交的VertexProgram会复制到所有的Worker。在API中，Worker不是一个明确的概念，而是假定为所有GraphComputer实施。至少每个顶点都是一个工作者(尽管由于每个顶点都会维护一个顶点程序，所以效率很低)。在实践中，Worker划分顶点集，并负责在其影响范围内的所有顶点上执行顶点程序。工作人员以批量同步并行(BSP)的方式在其所有顶点上编排VertexProgram.Execute()方法的执行。顶点可以通过消息相互通信。GremlinOLAP中有两种消息：MessageScope.Local和MessageScope.Global。本地消息是给相邻顶点的消息。全局消息是对图中任意顶点的消息。一旦VertexProgram完成了它的执行，就会评估任意数量的MapReduce作业。MapReduce作业由用户通过GraphComputer.mapReduce()提供，或者由VertexProgram通过VertexProgram.getMapReducers()提供

MapReduce

Pregel提出的BSP模型将计算结果以分布式方式存储为图中元素的属性。在许多情况下，必须将这些结果属性聚合到单个结果集(即统计数据)中。例如，假设一个顶点程序计算每个顶点的名义集群(即图聚类算法)。在计算结束时，每个顶点都有一个属性来表示分配给它的集群。TinkerPop提供了回答有关集群的全局问题的能力。例如，为了回答以下问题，需要MapReduce作业：

下面提供了TinkerPop中MapReductAPI的压缩表示形式。关键思想是，映射阶段处理所有顶点以发出键/值对。这些值在各自的键上进行聚合，以便使缩减阶段完成其处理，最终产生更多的键/值对。

mapreduce

在检查PeerPressureVertexProgram和相应的集群PopulationMapReduce时，MapReduce对GraphComputer的扩展是显式的。在下面的代码中，GraphComputer结果返回图上的计算结果以及计算的内存(ComputerResult)。内存维护任何MapReduce作业的结果。聚类总体映射推理结果表明，簇1中有5个顶点，簇6中有1个顶点。这可以通过查看结果图的PeerPressureVertexProgram.CLUSTER属性(以串行方式)来验证。注意，除非通过名称直接访问属性，否则该属性是“隐藏的”。

graph = TinkerFactory.createModern()
result = graph.compute().program(PeerPressureVertexProgram.build().create()).mapReduce(ClusterPopulationMapReduce.build().create()).submit().get()
result.memory().get('clusterPopulation')
g = result.graph().traversal()
g.V().values(PeerPressureVertexProgram.CLUSTER).groupCount().next()
g.V().elementMap()

如果需要大量的统计数据，那么可以根据需要注册尽可能多的MapReduce作业。例如，ClusterCountMapReduce确定由对等压力算法创建了多少唯一的集群。在ClusterCountMapReduce和ClusterPopulationMapReduce下面都是在结果图上计算的。

result = graph.compute().program(PeerPressureVertexProgram.build().create()).
           mapReduce(ClusterPopulationMapReduce.build().create()).
           mapReduce(ClusterCountMapReduce.build().create()).submit().get()
result.memory().clusterPopulation
result.memory().clusterCount

采用个新的实时计算架构

greenplum + MADlib

bbb333ac953995d4eaa10b326fa95223

a10e518bac603d62fe61ebf50f57af52

MADlib是Pivotal公司与伯克利大学合作开发的一个开源机器学习库，提供了多种数据转换、数据探索、统计、数据挖掘和机器学习方法，使用它能够简易地对结构化数据进行分析和挖掘。MADlib不是面向程序员的，而是面向数据库开发或DBA的。如果用一句话说明什么是MADlib，那就是“SQL中的大数据机器学习库”。MADlib仅提供了可在SQL查询语句中调用的函数。其中不但包括基本的线性代数运算和统计函数，而且还提供了常用的、现成的机器学习或数据挖掘模型函数。用户不需要深入了解算法的程序实现细节，只要搞清楚各函数中相关参数的含义，从而提供正确的入参，并且能够理解和解释函数的输出结果即可。这种使用方式无疑会极大地提高开发效率，节约开发成本。在MADlib的世界里，一切皆函数，就是这么简单。

但是函数只能在SQL中调用，而SQL依赖于数据库系统，也就是说单独的MADlib函数库是无意义的，它必须与PostgreSQL、Greenplum和HAWQ等数据库系统结合使用。最后，既然MADlib是SQL中的机器学习库，注定它不关心数据可视化，本身不带数据的图形化表示功能。由此可见，MADlib作为工具，并不是传统意义上的数据挖掘系统软件，而只是一套可在SQL中调用的函数库，其出发点是让数据库技术人员用SQL快速完成简单的数据挖掘工作。

MADlib架构

20171219172340108

  • python 调用SQL模板实现的驱动函数
  • python实现的高级抽象层
  • C++实现的核心函数
  • C++实现的低级数据库抽象层

（1） python驱动函数

驱动函数是用户输入的主入口点，调用优化器执行迭代算法的外层循环

（2）Python实现的高级抽象层

​ 高级抽象层负责算法的流程控制。与驱动函数一起实现输入参数验证、SQL语句执行、结果评估，并可能在循环中自动执行更多的SQL语句直到达到某些收敛标准。

（3）C++实现的核心函数

​ 这部分函数是由C++编写的核心函数，在内层循环中实现特定机器学习或数据挖掘算法。出于性能考虑，这些函数使用C++而不是Python编写。

（4）C++实现的低级数据库抽象层

​ 这些函数提供一个编程接口，将所有的Postgres数据库内核实现细节进行抽象。它们提供了一种机制，使得MADlib能够支持不同的后端平台，从而将关注点集中在内部功能而不是平台集成上。

下面是一个简单的例子，主要是做了一个线性回归的模型，最终还计算了误差

CREATE TABLE regre_example
(
    id int,
    y  int,
    x1 int,
    x2 int
);

insert into regre_example
VALUES (1, 5, 2, 3),
       (2, 10, 7, 2),
       (3, 6, 4, 1),
       (4, 8, 3, 4);

select madlib.linregr_train(
    'regre_example',
    'regre_example_model',
    'y',
    'ARRAY [1, x1, x2]'
           );

SELECT * FROM regre_example_model;

SELECT regre_example.*, madlib.linregr_predict (ARRAY[1, x1, x2], m.coef) as predict,
       y - madlib.linregr_predict(ARRAY [1, x1, x2], m.coef) as residual from regre_example, regre_example_model m;

image-20201127142043997

这里就不讨论madlib的安装等问题了

madlib中的数据类型

madlib中的数据操作，是基于两种数据类型的，一种是array，一种是matrices。即向量和矩阵。但是矩阵有两种表示的方式，一种是稀疏矩阵，一种是非稀疏矩阵。在mablib中对于矩阵的操作是分割为多个向量操作完成的，比如说矩阵加的操作，就可以分为向量之间的操作进行完成。

但是需要注意的是，有些向量操作只能够用于非稀疏矩阵的运算。

image-20201127153405301image-20201127153415121

如上第一张图片所示是非稀疏矩阵的存储，第二张是稀疏矩阵。（如果矩阵的存储是一行一个栏目并且是纯数字，那我们数据库中的数据该如何转变为这种形式？数据预处理。转换后是否要单独重新存入一张表？）

madlib中的向量操作

先拿一个简单的例子来看：

create table array_tbl
( id integer, array1 integer[], array2 integer[] );  --注意类型

insert into array_tbl values
( 1, '{1,2,3,4,5,6,7,8,9}','{9,8,7,6,5,4,3,2,1}' ),
( 2, '{1,1,0,0,1,2,3,99,8}','{0,0,0,-5,4,1,1,7,6}');  -- 会自动转为一个向量

select id, madlib.array_max(array1) max from array_tbl;  -- array_max传入的一定是个向量，并计算这个向量中的最大值

>>>
2,99
1,9

加法运算

select id, madlib.array_add(array1, array2) add from array_tbl;
>>>
id,  add
1,  "{10,10,10,10,10,10,10,10,10}"  --注意这里将第一行的array1 和array2 相加，
2,  "{1,1,0,-5,5,3,4,106,14}"

这是不是就模拟了两个矩阵的相加。

下面就列举一下向量函数

函数 功能
array_add() 两个数组相加，需要所有值非空，返回与输入相同的数据类型。
sum() 数组元素求和，需要所有值非空，返回与输入相同的数据类型。
array_sub() 两个数组相减，需要所有值非空，返回与输入相同的数据类型。
array_mult() 两个数组相乘，需要所有值非空，返回与输入相同的数据类型。(数值乘法)
array_div() 两个数组相除，需要所有值非空，返回与输入相同的数据类型。
array_dot() 两个数组点积，需要所有值非空，返回与输入相同的数据类型。
array_contains() 检查一个数组是否包含另一个数组。如果右边数组中的每个非零元素都等于左边数组中相同下标的元素，函数返回TRUE。
array_max() 返回数组中的最大值，忽略空值，返回数组元素的相同类型。
array_max_index() 返回数组中的最大值及其对应的下标，忽略空值，返回类型的格式为[max, index]，其元素类型与输入类型相同。
array_min() 返回数组中的最小值，忽略空值，返回数组元素的相同类型。
array_min_index() 返回数组中的最小值及其对应的下标，忽略空值，返回类型的格式为[min, index]，其元素类型与输入类型相同。
array_sum() 返回数组中值的和，忽略空值，返回与输入相同的数据类型。
array_sum_big() 返回数组中值的和，忽略空值，返回FLOAT8类型。该函数的意思是当汇总值可能超出元素类型范围时，替换array_sum()。
array_abs_sum() 返回数组中绝对值的和，忽略空值，返回与输入相同的数据类型。
array_abs() 返回由数组元素的绝对值组成的新数组，需要所有值非空。
array_mean() 返回数组的均值，忽略空值。
array_stddev() 返回数组的标准差，忽略空值。
array_of_float() 创建元素个数为参数值的FLOAT8数组，初始值为0.0。
array_of_bigint() 创建元素个数为参数值的BIGINT数组，初始值为0。
array_fill() 将数组每个元素设置为参数值。
array_filter() 过滤掉数组中的指定元素，要求所有值非空。返回与输入相同的数据类型。不指定被过滤元素时，该函数移除数组中的所有0值。
array_scalar_mult() 数组与标量相乘，返回结果数组。需要所有值非空，返回与输入相同的数据类型。
array_scalar_add() 数组与标量相加，返回结果数组。需要所有值非空，返回与输入相同的数据类型。
array_sqrt() 返回由数组元素的平方根组成的数组，需要所有值非空。
array_pow() 以数组和一个float8为输入，返回每个元素的乘幂（由第二个参数指定）组成的数组, 需要所有值非空。
array_square() 返回由数组元素的平方组成的数组，需要所有值非空。
normalize() 该函数规范化一个数组，使它的元素平方和为1。要求所有值非空。

上述函数都是使用C语言实现的。他们支持下面的数据类型，也就是在声明数据类型时的选择

  • SMALLINT
  • INTEGER
  • BIGINT
  • REAL
  • DOUBLE PRECISION（FLOAT8）
  • NUMERIC（内部被转化为FLOAT8，可能丢失精度）
create table array_tbl
( id integer, array1 integer[], array2 integer[] );  --注意类型

目前madlib中的图算法有

查询所有顶点间的最短路径算法APSP（graph_apsp）

广度优先搜索Breadth-First

给每个顶点打分HITS

评价一个顶点的连通程度（节点的重要性）PageRank

单个节点的到其他节点的最短路径(SSSP)

求一个连通子图(weakly connected components)

统计函数：平均路径长度，最长的最短路径，出度和入度统计