⑴ 比Redis好用的Nosql
实际上为了更好的描述实体之间的关系,我们要是再继续使用Redis的话,是不是感觉实体之间的关系不够那么的明显,虽然也是属于NoSQL的一种,但是相对来说,Redis,表现实体之间的关系就没有那么清晰了,为了更好的描述实体之间的关系,就会使用图形数据库来进行了,那么今天阿粉介绍的,就是一个图形化的数据可,Neo4J。
Neo4j是一个世界领先的开源的基于图的数据库。 它是使用Java语言完全开发的。那么什么是图数据库呢?图数据库是以图结构的形式存储数据的数据库。 它以节点,关系和属性的形式存储应用程序的数据。正如RDBMS以表的“行,列”的形式存储数据,GDBMS以图的形式存储数据。
RDBMS与图数据库的区别
1.Tables 表Graphs 图表
2.Rows 行Nodes 节点
3.Columns and Data 列和数据 Properties and its values属性及其值
4.Constraints 约束Relationships 关系
5.Joins 加入Traversal 遍历
说完了图形数据库,我们就来看看这个 Neo4J 数据库吧
neo4j是用Java语言编写的图形数据库,运行时需要启动JVM进程,因此,需安装JAVA SE的JDK。关于 Java 怎么安装,我就不用再多废话了吧,到时候别忘了检测一下 Java 的版本就好了, java -version
接下来我们就是要进行一个安装了,我们先去官网,下载社区版,企业版要收费的,注意哈。
官网地址
下载完成,直接开始安装,傻瓜式操作即可。
Neo4j应用程序有如下主要的目录结构:
注意,如果你使用的是Zip的压缩包来进行的使用的话,那么你就需要注意一些地方,比如你如果是用 Zip 的包解压之后,并且想要通过 bat 的命令启动,直接在目录下进行 cmd ,然后 neo4j.bat ,这时候可能会出现一个问题,就是版本可能会出现问题,你如果下载使用的是最新版的 Neo4J ,那么就可能会让你使用 JDK 11 ,而阿粉就是踩过了这个大坑之后,才发现,bat 闪退的原因。
这样就是说明我们的 JDk 的版本对应的和 Neo4J 需要的 JDK 是不匹配的,我们就需要换一下我们的 JDK 了。把他换成 JDK 11 就好了,再次启动。
这时候,我们就直接访问 localhost:7474 的端口,直接就能看到如下的画面, 1.jpg
刚进入的时候可能需要大家输入帐号密码,默认的帐号密码就是,neo4j 修改成你想要的就行了。
这样登录进去我们就能开始正式学习 Neo4J 的所有内容了。
Neo4j - CQL语法
我们在讲语法之前首先我们先得看看 Neo4J 的构建模块,不然之后的查询都是无意义的。
Neo4j图数据库主要有以下构建块 -
节点是图表的基本单位。 它包含具有键值对的属性,如下所示
属性是用于描述图节点和关系的键值对
关系是图形数据库的另一个主要构建块。 它连接两个节点,如下所示。
Label将一个公共名称与一组节点或关系相关联。 节点或关系可以包含一个或多个标签。 我们可以为现有节点或关系创建新标签。 我们可以从现有节点或关系中删除现有标签。
Neo4j数据浏览器 一旦我们安装Neo4j,我们可以访问Neo4j数据浏览器使用以下URL
http:// localhost:7474 / browser /
CREATE 语法
CREATE ( : )
它是我们要创建的节点名称。
它是一个节点标签名称
我们可以创建一个节点,然后给他安排上一个标签
CREATE (emp:Employee)
当我们看到
Added 1 label, created 1 node, completed after 74 ms.
这就创建成功了,
那么怎么查看呢?
MATCH语法
MATCH ( : ) return xxx
是这个样子的
但是看到里面竟然没有东西,就相当于是一个空的对象,那是不是就应该给里面放入属性的操作呢?没错,肯定有
CREATE (emp:Employee{ id : 1001 ,name :"lucy", age : 10})
Added 1 label, created 1 node, set 3 properties, completed after 163 ms. 创建成功。
我们再次查看就能看到
如果我们想只要其中的一些对象的属性,而不是全部属性,那应该怎么操作呢?
RETURN语法
RETURN 可以返回的是一个对象,也可以是对象中的属性,比如:
结果就是下面这个样子的,大家看一下,是不是感觉还是挺好用的。
** WHERE语法**
WHERE
为什么在前面的位置阿粉说,CQL 是和 SQL 类型的,这完全是因为很多东西和 SQL 是类似的。
结果如下:
相同的还有
布尔运算符 描述 AND 和 OR 或者 NOT 非 XOR 异或
比较运算符 描述 = “等于”运算符 > “不等于”运算符 < “小于”运算符 > “大于”运算符 <= “小于或等于”运算符。 >= “大于或等于”运算符。
DELETE语法
删除语法必然是有的,因为有创建,肯定有删除。
DELETE
但是这个命令也不是单独使用的哈,
MATCH (e: Employee) DELETE e
直接删除成功。
基础的东西讲完了,阿粉就得说说这个比较重要的内容了,关系,
我们之前创建节点的时候,那叫一个简单舒适加愉快,但是创建关系就比较复杂了,因为需要考虑如何匹配到有关系的两个节点,以及关系本身的属性如何设置。这里我们就简单学一下如何建立节点之间的关系。
由于Neo4j CQL语法是以人类可读的格式。 Neo4j CQL也使用类似的箭头标记来创建两个节点之间的关系。
每个关系( )包含两个节点
在Neo4j中,两个节点之间的关系是有方向性的。 它们是单向或双向的。
如果我们尝试创建一个没有任何方向的关系,那么就会报错。
关系创建语法
CREATE ( )-[ ]->( )
我们这里直接使用创建新的节点来创建关系。
提示创建成功
这里关系名称是“CONTAINS”
关系标签是“contains”。
这么看是看不出有啥关系的,但是,我们可以从另外的一个位置
这样看下来,这个 Neo4J 简单操作是不是就学会了,阿粉接下来的文章中讲怎么使用 Java 来操作 Neo4J 数据库。欢迎大家来观看。
⑵ 为什么选择图形数据库,为什么选择Neo4j
图形数据库每个对象是一个节点,之间的关系是一条边。相对于关系数据库来说,图形数据库善于处理大量复杂、互连接、低结构化的数据,这些数据变化迅速,需要频繁的查询——在关系数据库中,由于这些查询会导致大量的表连接,从而导致性能问题,而且在设计使用上也不方便。
图形数据库适合用于社交网络,推荐系统等专注于构建关系图谱的系统。
图数据库的代表有Neo4J、FlockDB、InfoGrid、AllegroGraph、GraphDB等。
⑶ 什么是图数据库
图数据库(Graph database) 并非指存储图片的数据库,而是以“图”这种数据结构存储和查询数据。目前比较典型的代表产品是Neo4j。
⑷ Neo4j类似的软件有哪些
GraphScope、NetworkX、JanusGraph、TigerGraph、Dgraph这些都是,比如GraphScope的代码可以在GitHub上面查看,它是阿里达摩院研发的一站式图计算系统,应该还是比较权威。
⑸ 漫谈工业大数据9:开源工业大数据软件简介(上)
今天真是一个美好的时代,有无数的开源系统可以为我们提供服务,现在有许多开发软件可以用到工业大数据中,当然很多系统还不成熟,应用到工业中还需要小心,并且需要开发人员对其进行一定的优化和调整。下面就简单介绍一些开源的大数据工具软件,看看有哪些能够应用到工业大数据领域。
下面这张图是我根据网上流传的一张开源大数据软件分类图整理的:
我们可以把开源大数据软件分成几类,有一些可以逐步应用到工业大数据领域,下面就一一介绍一下这些软件。(以下系统介绍大都来源于网络)
1、数据存储类
(1)关系数据库MySQL
这个就不用太多介绍了吧,关系型数据库领域应用最广泛的开源软件,目前属于 Oracle 旗下产品。
(2)文件数据库Hadoop
Hadoop是大数据时代的明星产品,它最大的成就在于实现了一个分布式文件系统(Hadoop Distributed FileSystem),简称HDFS。HDFS有高容错性的特点,并且设计用来部署在低廉的硬件上,而且它提供高吞吐量来访问应用程序的数据,适合那些有着超大数据集的应用程序。
Hadoop可以在工业大数据应用中用来作为底层的基础数据库,由于它采用了分布式部署的方式,如果是私有云部署,适用于大型企业集团。如果是公有云的话,可以用来存储文档、视频、图像等资料。
(3)列数据库Hbase
HBase是一个分布式的、面向列的开源数据库,HBase是Apache的Hadoop项目的子项目。HBase不同于一般的关系数据库,它是一个适合于非结构化数据存储的数据库。另一个不同的是HBase基于列的而不是基于行的模式。
基于Hbase开发的OpenTSDB,可以存储所有的时序(无须采样)来构建一个分布式、可伸缩的时间序列数据库。它支持秒级数据采集所有metrics,支持永久存储,可以做容量规划,并很容易的接入到现有的报警系统里。
这样的话,它就可以替代在工业领域用得最多的实时数据库。
(4)文档数据库MongoDB
MongoDB是一个介于关系数据库和非关系数据库之间的产品,是非关系数据库当中功能最丰富,最像关系数据库的。他支持的数据结构非常松散,是类似json的bson格式,因此可以存储比较复杂的数据类型。Mongo最大的特点是他支持的查询语言非常强大,其语法有点类似于面向对象的查询语言,几乎可以实现类似关系数据库单表查询的绝大部分功能,而且还支持对数据建立索引。
MongoDB适合于存储工业大数据中的各类文档,包括各类图纸、文档等。
(5)图数据库Neo4j/OrientDB
图数据库不是存放图片的,是基于图的形式构建的数据系统。
Neo4j是一个高性能的,NOSQL图形数据库,它将结构化数据存储在网络上而不是表中。它是一个嵌入式的、基于磁盘的、具备完全的事务特性的Java持久化引擎,但是它将结构化数据存储在网络(从数学角度叫做图)上而不是表中。Neo4j也可以被看作是一个高性能的图引擎,该引擎具有成熟数据库的所有特性。程序员工作在一个面向对象的、灵活的网络结构下而不是严格、静态的表中——但是他们可以享受到具备完全的事务特性、 企业级 的数据库的所有好处。
OrientDB是兼具文档数据库的灵活性和图形数据库管理 链接 能力的可深层次扩展的文档-图形数据库管理系统。可选无模式、全模式或混合模式下。支持许多高级特性,诸如ACID事务、快速索引,原生和SQL查询功能。可以JSON格式导入、导出文档。若不执行昂贵的JOIN操作的话,如同关系数据库可在几毫秒内可检索数以百记的链接文档图。
这些数据库都可以用来存储非结构化数据。
2、数据分析类
(1)批处理MapRece/Spark
MapRece是一种编程模型,用于大规模数据集(大于1TB)的并行运算。概念"Map(映射)"和"Rece(归约)",是它们的主要思想,都是从函数式编程语言里借来的,还有从矢量编程语言里借来的特性。它极大地方便了编程人员在不会分布式并行编程的情况下,将自己的程序运行在分布式系统上。 当前的软件实现是指定一个Map(映射)函数,用来把一组键值对映射成一组新的键值对,指定并发的Rece(归约)函数,用来保证所有映射的键值对中的每一个共享相同的键组。
Apache Spark 是专为大规模数据处理而设计的快速通用的计算引擎。Spark 是一种与 Hadoop 相似的开源集群计算环境,但是两者之间还存在一些不同之处,这些有用的不同之处使 Spark 在某些工作负载方面表现得更加优越,换句话说,Spark 启用了内存分布数据集,除了能够提供交互式查询外,它还可以优化迭代工作负载。尽管创建 Spark 是为了支持分布式数据集上的迭代作业,但是实际上它是对 Hadoop 的补充,可以在 Hadoop 文件系统中并行运行。
这些大数据的明星产品可以用来做工业大数据的处理。
(2)流处理Storm
Storm是一个开源的分布式实时计算系统,可以简单、可靠的处理大量的数据流。Storm有很多使用场景:如实时分析,在线机器学习,持续计算,分布式RPC,ETL等等。Storm支持水平扩展,具有高容错性,保证每个消息都会得到处理,而且处理速度很快(在一个小集群中,每个结点每秒可以处理数以百万计的消息)。Storm的部署和运维都很便捷,而且更为重要的是可以使用任意编程语言来开发应用。
(3)图处理Giraph
Giraph是什么?Giraph是Apache基金会开源项目之一,被定义为迭代式图处理系统。他架构在Hadoop之上,提供了图处理接口,专门处理大数据的图问题。
Giraph的存在很有必要,现在的大数据的图问题又很多,例如表达人与人之间的关系的有社交网络,搜索引擎需要经常计算网页与网页之间的关系,而map-rece接口不太适合实现图算法。
Giraph主要用于分析用户或者内容之间的联系或重要性。
(4)并行计算MPI/OpenCL
OpenCL(全称Open Computing Language,开放运算语言)是第一个面向 异构系统 通用目的并行编程的开放式、免费标准,也是一个统一的编程环境,便于软件开发人员为高性能计算 服务器 、桌面计算系统、手持设备编写高效轻便的代码,而且广泛适用于多核心处理器(CPU)、图形处理器(GPU)、Cell类型架构以及数字信号处理器(DSP)等其他并行处理器,在 游戏 、 娱乐 、科研、医疗等各种领域都有广阔的发展前景。
(5)分析框架Hive
Hive是基于Hadoop的一个数据仓库工具,可以将结构化的数据文件映射为一张数据库表,并提供简单的sql查询功能,可以将sql语句转换为MapRece任务进行运行。 其优点是学习成本低,可以通过类SQL语句快速实现简单的MapRece统计,不必开发专门的MapRece应用,十分适合数据仓库的统计分析。
(6)分析框架Pig
Apache Pig 是apache平台下的一个免费开源项目,Pig为大型数据集的处理提供了更高层次的抽象,很多时候数据的处理需要多个MapRece过程才能实现,使得数据处理过程与该模式匹配可能很困难。有了Pig就能够使用更丰富的数据结构。[2]
Pig LatinPig Latin 是一个相对简单的语言,一条语句 就是一个操作,与数据库的表类似,可以在关系数据库中找到它(其中,元组代表行,并且每个元组都由字段组成)。
Pig 拥有大量的数据类型,不仅支持包、元组和映射等高级概念,还支持简单的数据类型,如 int、long、float、double、chararray 和 bytearray。并且,还有一套完整的比较运算符,包括使用正则表达式的丰富匹配模式。
⑹ 图计算引擎Neo4j和Graphscope有什么区别
Neo4j是单机系统,主要做图数据库。GraphScope是由阿里巴巴达摩院智能计算实验室研发的图计算平台,是全球首个一站式超大规模分布式图计算平台,并且还入选了中 国科学技术协会“科创中 国”平台。Graphscope的代码在github.com/alibaba/graphscope上开源。SSSP算法上,GraphScope单机模式下平均要比Neo4j快176.38倍,最快在datagen-9.2_zf数据集上快了292.2倍。
⑺ 有哪些轻型的非关系型数据库
常见的非关系型数据库有:1、mongodb;2、cassandra;3、redis;4、hbase;5、neo4j。其中mongodb是非常着名的NoSQL数据库,它是一个面向文档的开源数据库。
常见的几种非关系型数据库:
1、MongoDB
MongoDB是最着名的NoSQL数据库。它是一个面向文档的开源数据库。MongoDB是一个可伸缩和可访问的数据库。它在c++中。MongoDB同样可以用作文件系统。在MongoDB中,JavaScript可以作为查询语言使用。通过使用sharding MongoDB水平伸缩。它在流行的JavaScript框架中非常有用。
人们真的很享受分片、高级文本搜索、gridFS和map-rece功能。惊人的性能和新特性使这个NoSQL数据库在我们的列表中名列第一。
特点:提供高性能;自动分片;运行在多个服务器上;支持主从复制;数据以JSON样式文档的形式存储;索引文档中的任何字段;由于数据被放置在碎片中,所以它具有自动负载平衡配置;支持正则表达式搜索;在失败的情况下易于管理。
优点:易于安装MongoDB;MongoDB Inc.为客户提供专业支持;支持临时查询;高速数据库;无模式数据库;横向扩展数据库;性能非常高。
缺点:不支持连接;数据量大;嵌套文档是有限的;增加不必要的内存使用。
2、Cassandra
Cassandra是Facebook为收件箱搜索开发的。Cassandra是一个用于处理大量结构化数据的分布式数据存储系统。通常,这些数据分布在许多普通服务器上。您还可以添加数据存储容量,使您的服务保持在线,您可以轻松地完成这项任务。由于集群中的所有节点都是相同的,因此不需要处理复杂的配置。
Cassandra是用Java编写的。Cassandra查询语言(CQL)是查询Cassandra数据库的一种类似sql的语言。因此,Cassandra在最佳开源数据库中排名第二。Facebook、Twitter、思科(Cisco)、Rackspace、eBay、Twitter、Netflix等一些最大的公司都在使用Cassandra。
特点:线性可伸缩;;保持快速响应时间;支持原子性、一致性、隔离性和耐久性(ACID)等属性;使用Apache Hadoop支持MapRece;分配数据的最大灵活性;高度可伸缩;点对点架构。
优点:高度可伸缩;无单点故障;Multi-DC复制;与其他基于JVM的应用程序紧密集成;更适合多数据中心部署、冗余、故障转移和灾难恢复。
缺点:对聚合的有限支持;不可预知的性能;不支持特别查询。
3、Redis
Redis是一个键值存储。此外,它是最着名的键值存储。Redis支持一些c++、PHP、Ruby、Python、Perl、Scala等等。Redis是用C语言编写的。此外,它是根据BSD授权的。
特点:自动故障转移;将其数据库完全保存在内存中;事务;Lua脚本;将数据复制到任意数量的从属服务器;钥匙的寿命有限;LRU驱逐钥匙;支持发布/订阅。
优点:支持多种数据类型;很容易安装;非常快(每秒执行约11万组,每秒执行约81000次);操作都是原子的;多用途工具(在许多用例中使用)。
缺点:不支持连接;存储过程所需的Lua知识;数据集必须很好地适应内存。
4、HBase
HBase是一个分布式的、面向列的开源数据库,该技术来源于 Fay Chang 所撰写的Google论文“Bigtable:一个结构化数据的分布式存储系统”。就像Bigtable利用了Google文件系统(File System)所提供的分布式数据存储一样,HBase在Hadoop之上提供了类似于Bigtable的能力。
HBase是Apache的Hadoop项目的子项目。HBase不同于一般的关系数据库,它是一个适合于非结构化数据存储的数据库。另一个不同的是HBase基于列的而不是基于行的模式。
5、neo4j
Neo4j被称为原生图数据库,因为它有效地实现了属性图模型,一直到存储层。这意味着数据完全按照白板的方式存储,数据库使用指针导航和遍历图。Neo4j有数据库的社区版和企业版。企业版包括Community Edition必须提供的所有功能,以及额外的企业需求,如备份、集群和故障转移功能。
特点:它支持唯一的约束;Neo4j支持完整的ACID(原子性、一致性、隔离性和持久性)规则;Java API: Cypher API和本机Java API;使用Apache Lucence索引;简单查询语言Neo4j CQL;包含用于执行CQL命令的UI: Neo4j Data Browser。
优点:容易检索其相邻节点或关系细节,无需连接或索引;易于学习Neo4j CQL查询语言命令;不需要复杂的连接来检索数据;非常容易地表示半结构化数据;大型企业实时应用程序的高可用性;简化的调优。
缺点:不支持分片
⑻ neo4j是什么怎么配置能单独使用吗
Neo4j是一个嵌入式,基于磁盘的,支持完整事务的Java持久化引擎,它在图像中而不是表中存储数据。Neo4j提供了大规模可扩展性,在一台机器上可以处理数十亿节点/关系/属性的图像,可以扩展到多台机器并行运行。相对于关系数据库来说,图形数据库善于处理大量复杂、互连接、低结构化的数据,这些数据变化迅速,需要频繁的查询——在关系数据库中,这些查询会导致大量的表连接,因此会产生性能上的问题。Neo4j重点解决了拥有大量连接的传统RDBMS在查询时出现的性能衰退问题。通过围绕图形进行数据建模,Neo4j会以相同的速度遍历节点与边,其遍历速度与构成图形的数据量没有任何关系。此外,Neo4j还提供了非常快的图形算法、推荐系统和OLAP风格的分析,而这一切在目前的RDBMS系统中都是无法实现的。
⑼ 如何用 Python 实现一个图数据库(Graph Database)
本文章是 重写 500 Lines or Less 系列的其中一篇,目标是重写 500 Lines or Less 系列的原有项目:Dagoba: an in-memory graph database。
Dagoba 是作者设计用来展示如何从零开始自己实现一个图数据库( Graph Database )。该名字似乎来源于作者喜欢的一个乐队,另一个原因是它的前缀 DAG 也正好是有向无环图 ( Directed Acyclic Graph ) 的缩写。本文也沿用了该名称。
图是一种常见的数据结构,它将信息描述为若干独立的节点( vertex ,为了和下文的边更加对称,本文中称为 node ),以及把节点关联起来的边( edge )。我们熟悉的链表以及多种树结构可以看作是符合特定规则的图。图在路径选择、推荐算法以及神经网络等方面都是重要的核心数据结构。
既然图的用途如此广泛,一个重要的问题就是如何存储它。如果在传统的关系数据库中存储图,很自然的做法就是为节点和边各自创建一张表,并用外键把它们关联起来。这样的话,要查找某人所有的子女,就可以写下类似下面的查询:
还好,不算太复杂。但是如果要查找孙辈呢?那恐怕就要使用子查询或者 CTE(Common Table Expression) 等特殊构造了。再往下想,曾孙辈又该怎么查询?孙媳妇呢?
这样我们会意识到,SQL 作为查询语言,它只是对二维数据表这种结构而设计的,用它去查询图的话非常笨拙,很快会变得极其复杂,也难以扩展。针对图而言,我们希望有一种更为自然和直观的查询语法,类似这样:
为了高效地存储和查询图这种数据结构,图数据库( Graph Database )应运而生。因为和传统的关系型数据库存在极大的差异,所以它属于新型数据库也就是 NoSql 的一个分支(其他分支包括文档数据库、列数据库等)。图数据库的主要代表包括 Neo4J 等。本文介绍的 Dagoba 则是具备图数据库核心功能、主要用于教学和演示的一个简单的图数据库。
原文代码是使用 JavaScript 编写的,在定义调用接口时大量使用了原型( prototype )这种特有的语言构造。对于其他主流语言的用户来说,原型的用法多少显得有些别扭和不自然。
考虑到本系列其他数据库示例大多是用 Python 实现的,本文也按照传统,用 Python 重写了原文的代码。同样延续之前的惯例,为了让读者更好地理解程序是如何逐步完善的,我们用迭代式的方法完成程序的各个组成部分。
原文在 500lines 系列的 Github 仓库中只包含了实现代码,并未包含测试。按照代码注释说明,测试程序位于作者的另一个代码库中,不过和 500lines 版本的实现似乎略有不同。
本文实现的代码参考了原作者的测试内容,但跳过了北欧神话这个例子——我承认确实不熟悉这些神祇之间的亲缘关系,相信中文背景的读者们多数也未必了解,虽然作者很喜欢这个例子,想了想还是不要徒增困惑吧。因此本文在编写测试用例时只参考了原文关于家族亲属的例子,放弃了神话相关的部分,尽管会减少一些趣味性,相信对于入门级的代码来说这样也够用了。
本文实现程序位于代码库的 dagoba 目录下。按照本系列程序的同意规则,要想直接执行各个已完成的步骤,读者可以在根目录下的 main.py 找到相应的代码位置,取消注释并运行即可。
本程序的所有步骤只需要 Python3 ,测试则使用内置的 unittest , 不需要额外的第三方库。原则上 Python3.6 以上版本应该都可运行,但我只在 Python3.8.3 环境下完整测试过。
本文实现的程序从最简单的案例开始,通过每个步骤逐步扩展,最终形成一个完整的程序。这些步骤包括:
接下来依次介绍各个步骤。
回想一下,图数据库就是一些点( node )和边( edge )的集合。现在我们要做出的一个重大决策是如何对节点/边进行建模。对于边来说,必须指定它的关联关系,也就是从哪个节点指向哪个节点。大多数情况下边是有方向的——父子关系不指明方向可是要乱套的!
考虑到扩展性及通用性问题,我们可以把数据保存为字典( dict ),这样可以方便地添加用户需要的任何数据。某些数据是为数据库内部管理而保留的,为了明确区分,可以这样约定:以下划线开头的特殊字段由数据库内部维护,类似于私有成员,用户不应该自己去修改它们。这也是 Python 社区普遍遵循的约定。
此外,节点和边存在互相引用的关系。目前我们知道边会引用到两端的节点,后面还会看到,为了提高效率,节点也会引用到边。如果仅仅在内存中维护它们的关系,那么使用指针访问是很直观的,但数据库必须考虑到序列化到磁盘的问题,这时指针就不再好用了。
为此,最好按照数据库的一般要求,为每个节点维护一个主键( _id ),用主键来描述它们之间的关联关系。
我们第一步要把数据库的模型建立起来。为了测试目的,我们使用一个最简单的数据库模型,它只包含两个节点和一条边,如下所示:
按照 TDD 的原则,首先编写测试:
与原文一样,我们把数据库管理接口命名为 Dagoba 。目前,能够想到的最简单的测试是确认节点和边是否已经添加到数据库中:
assert_item 是一个辅助方法,用于检查字典是否包含预期的字段。相信大家都能想到该如何实现,这里就不再列出了,读者可参考 Github 上的完整源码。
现在,测试是失败的。用最简单的办法实现数据库:
需要注意的是,不管添加节点还是查询,程序都使用了拷贝后的数据副本,而不是直接使用原始数据。为什么要这样做?因为字典是可变的,用户可以在任何时候修改其中的内容,如果数据库不知道数据已经变化,就很容易发生难以追踪的一致性问题,最糟糕的情况下会使得数据内容彻底混乱。
拷贝数据可以避免上述问题,代价则是需要占用更多内存和处理时间。对于数据库来说,通常查询次数要远远多于修改,所以这个代价是可以接受的。
现在测试应该正常通过了。为了让它更加完善,我们可以再测试一些边缘情况,看看数据库能否正确处理异常数据,比如:
例如,如果用户尝试添加重复主键,我们预期应抛出 ValueError 异常。因此编写测试如下:
为了满足以上测试,代码需要稍作修改。特别是按照 id 查找主键是个常用操作,通过遍历的方法效率太低了,最好是能够通过主键直接访问。因此在数据库中再增加一个字典:
完整代码请参考 Github 仓库。
在上个步骤,我们在初始化数据库时为节点明确指定了主键。按照数据库设计的一般原则,主键最好是不具有业务含义的代理主键( Surrogate key ),用户不应该关心它具体的值是什么,因此让数据库去管理主键通常是更为合理的。当然,在部分场景下——比如导入外部数据——明确指定主键仍然是有用的。
为了同时支持这些要求,我们这样约定:字段 _id 表示节点的主键,如果用户指定了该字段,则使用用户设置的值(当然,用户有责任保证它们不会重复);否则,由数据库自动为它分配一个主键。
如果主键是数据库生成的,事先无法预知它的值是什么,而边( edge )必须指定它所指向的节点,因此必须在主键生成后才能添加。由于这个原因,在动态生成主键的情况下,数据库的初始化会略微复杂一些。还是先写一个测试:
为支持此功能,我们在数据库中添加一个内部字段 _next_id 用于生成主键,并让 add_node 方法返回新生成的主键:
接下来,再确认一下边是否可以正常访问:
运行测试,一切正常。这个步骤很轻松地完成了,不过两个测试( DbModelTest 和 PrimaryKeyTest )出现了一些重复代码,比如 get_item 。我们可以把这些公用代码提取出来。由于 get_item 内部调用了 TestCase.assertXXX 等方法,看起来应该使用继承,但从 TestCase 派生基类容易引起一些潜在的问题,所以我转而使用另一个技巧 Mixin :
实现数据库模型之后,接下来就要考虑如何查询它了。
在设计查询时要考虑几个问题。对于图的访问来说,几乎总是由某个节点(或符合条件的某一类节点)开始,从与它相邻的边跳转到其他节点,依次类推。所以链式调用对查询来说是一种很自然的风格。举例来说,要知道 Tom 的孙子养了几只猫,可以使用类似这样的查询:
可以想象,以上每个方法都应该返回符合条件的节点集合。这种实现是很直观的,不过存在一个潜在的问题:很多时候用户只需要一小部分结果,如果它总是不计代价地给我们一个巨大的集合,会造成极大的浪费。比如以下查询:
为了避免不必要的浪费,我们需要另外一种机制,也就是通常所称的“懒式查询”或“延迟查询”。它的基本思想是,当我们调用查询方法时,它只是把查询条件记录下来,而并不立即返回结果,直到明确调用某些方法时才真正去查询数据库。
如果读者比较熟悉流行的 Python ORM,比如 SqlAlchemy 或者 Django ORM 的话,会知道它们几乎都是懒式查询的,要调用 list(result) 或者 result[0:10] 这样的方法才能得到具体的查询结果。
在 Dagoba 中把触发查询的方法定义为 run 。也就是说,以下查询执行到 run 时才真正去查找数据:
和懒式查询( Lazy Query )相对应的,直接返回结果的方法一般称作主动查询( Eager Query )。主动查询和懒式查询的内在查找逻辑基本上是相同的,区别只在于触发机制不同。由于主动查询实现起来更加简单,出错也更容易排查,因此我们先从主动查询开始实现。
还是从测试开始。前面测试所用的简单数据库数据太少,难以满足查询要求,所以这一步先来创建一个更复杂的数据模型:
此关系的复杂之处之一在于反向关联:如果 A 是 B 的哥哥,那么 B 就是 A 的弟弟/妹妹,为了查询到他们彼此之间的关系,正向关联和反向关联都需要存在,因此在初始化数据库时需要定义的边数量会很多。
当然,父子之间也存在反向关联的问题,为了让问题稍微简化一些,我们目前只需要向下(子孙辈)查找,可以稍微减少一些关联数量。
因此,我们定义数据模型如下。为了减少重复工作,我们通过 _backward 字段定义反向关联,而数据库内部为了查询方便,需要把它维护成两条边:
然后,测试一个最简单的查询,比如查找某人的所有孙辈:
这里 outcome/income 分别表示从某个节点出发、或到达它的节点集合。在原作者的代码中把上述方法称为 out/in 。当然这样看起来更加简洁,可惜的是 in 在 Python 中是个关键字,无法作为函数名。我也考虑过加个下划线比如 out_.in_ 这种形式,但看起来也有点怪异,权衡之后还是使用了稍微啰嗦一点的名称。
现在我们可以开始定义查询接口了。在前面已经说过,我们计划分别实现两种查询,包括主动查询( Eager Query )以及延迟查询( Lazy Query )。
它们的内在查询逻辑是相通的,看起来似乎可以使用继承。不过遵循 YAGNI 原则,目前先不这样做,而是只定义两个新类,在满足测试的基础上不断扩展。以后我们会看到,与继承相比,把共同的逻辑放到数据库本身其实是更为合理的。
接下来实现访问节点的方法。由于 EagerQuery 调用查询方法会立即返回结果,我们把结果记录在 _result 内部字段中。虽然 node 方法只返回单个结果,但考虑到其他查询方法几乎都是返回集合,为统一起见,让它也返回集合,这样可以避免同时支持集合与单结果的分支处理,让代码更加简洁、不容易出错。此外,如果查询对象不存在的话,我们只返回空集合,并不视为一个错误。
查询输入/输出节点的方法实现类似这样:
查找节点的核心逻辑在数据库本身定义:
以上使用了内部定义的一些辅助查询方法。用类似的逻辑再定义 income ,它们的实现都很简单,读者可以直接参考源码,此处不再赘述。
在此步骤的最后,我们再实现一个优化。当多次调用查询方法后,结果可能会返回重复的数据,很多时候这是不必要的。就像关系数据库通常支持 unique/distinct 一样,我们也希望 Dagoba 能够过滤重复的数据。
假设我们要查询某人所有孩子的祖父,显然不管有多少孩子,他们的祖父应该是同一个人。因此编写测试如下:
现在来实现 unique 。我们只要按照主键把重复数据去掉即可:
在上个步骤,初始化数据库指定了双向关联,但并未测试它们。因为我们还没有编写代码去支持它们,现在增加一个测试,它应该是失败的:
运行测试,的确失败了。我们看看要如何支持它。回想一下,当从边查找节点时,使用的是以下方法:
这里也有一个潜在的问题:调用 self.edges 意味着遍历所有边,当数据库内容较多时,这是巨大的浪费。为了提高性能,我们可以把与节点相关的边记录在节点本身,这样要查找边只要看节点本身即可。在初始化时定义出入边的集合:
在添加边时,我们要同时把它们对应的关系同时更新到节点,此外还要维护反向关联。这涉及对字典内容的部分复制,先编写一个辅助方法:
然后,将添加边的实现修改如下:
这里的代码同时添加正向关联和反向关联。有的朋友可能会注意到代码略有重复,是的,但是重复仅出现在该函数内部,本着“三则重构”的原则,暂时不去提取代码。
实现之后,前面的测试就可以正常通过了。
在这个步骤中,我们来实现延迟查询( Lazy Query )。
延迟查询的要求是,当调用查询方法时并不立即执行,而是推迟到调用特定方法,比如 run 时才执行整个查询,返回结果。
延迟查询的实现要比主动查询复杂一些。为了实现延迟查询,查询方法的实现不能直接返回结果,而是记录要执行的动作以及传入的参数,到调用 run 时再依次执行前面记录下来的内容。
如果你去看作者的实现,会发现他是用一个数据结构记录执行操作和参数,此外还有一部分逻辑用来分派对每种结构要执行的动作。这样当然是可行的,但数据处理和分派部分的实现会比较复杂,也容易出错。
本文的实现则选择了另外一种不同的方法:使用 Python 的内部函数机制,把一连串查询变换成一组函数,每个函数取上个函数的执行结果作为输入,最后一个函数的输出就是整个查询的结果。由于内部函数同时也是闭包,尽管每个查询的参数形式各不相同,但是它们都可以被闭包“捕获”而成为内部变量,所以这些内部函数可以采用统一的形式,无需再针对每种查询设计额外的数据结构,因而执行过程得到了很大程度的简化。
首先还是来编写测试。 LazyQueryTest 和 EagerQueryTest 测试用例几乎是完全相同的(是的,两种查询只在于内部实现机制不同,它们的调用接口几乎是完全一致的)。
因此我们可以把 EagerQueryTest 的测试原样不变拷贝到 LazyQueryTest 中。当然拷贝粘贴不是个好注意,对于比较冗长而固定的初始化部分,我们可以把它提取出来作为两个测试共享的公共函数。读者可参考代码中的 step04_lazy_query/tests/test_lazy_query.py 部分。
程序把查询函数的串行执行称为管道( pipeline ),用一个变量来记录它:
然后依次实现各个调用接口。每种接口的实现都是类似的:用内部函数执行真正的查询逻辑,再把这个函数添加到 pipeline 调用链中。比如 node 的实现类似下面:
其他接口的实现也与此类似。最后, run 函数负责执行所有查询,返回最终结果;
完成上述实现后执行测试,确保我们的实现是正确的。
在前面我们说过,延迟查询与主动查询相比,最大的优势是对于许多查询可以按需要访问,不需要每个步骤都返回完整结果,从而提高性能,节约查询时间。比如说,对于下面的查询:
以上查询的意思是从孙辈中找到一个符合条件的节点即可。对该查询而言,主动查询会在调用 outcome('son') 时就遍历所有节点,哪怕最后一步只需要第一个结果。而延迟查询为了提高效率,应在找到符合条件的结果后立即停止。
目前我们尚未实现 take 方法。老规矩,先添加测试:
主动查询的 take 实现比较简单,我们只要从结果中返回前 n 条记录:
延迟查询的实现要复杂一些。为了避免不必要的查找,返回结果不应该是完整的列表( list ),而应该是个按需返回的可迭代对象,我们用内置函数 next 来依次返回前 n 个结果:
写完后运行测试,确保它们是正确的。
从外部接口看,主动查询和延迟查询几乎是完全相同的,所以用单纯的数据测试很难确认后者的效率一定比前者高,用访问时间来测试也并不可靠。为了测试效率,我们引入一个节点访问次数的概念,如果延迟查询效率更高的话,那么它应该比主动查询访问节点的次数更少。
为此,编写如下测试:
我们为 Dagoba 类添加一个成员来记录总的节点访问次数,以及两个辅助方法,分别用于获取和重置访问次数:
然后浏览代码,查找修改点。增加计数主要在从边查找节点的时候,因此修改部分如下:
此外还有 income/outcome 方法,修改都很简单,这里就不再列出。
实现后再次运行测试。测试通过,表明延迟查询确实在效率上优于主动查询。
不像关系数据库的结构那样固定,图的形式可以千变万化,查询机制也必须足够灵活。从原理上讲,所有查询无非是从某个节点出发按照特定方向搜索,因此用 node/income/outcome 这三个方法几乎可以组合出任意所需的查询。
但对于复杂查询,写出的代码有时会显得较为琐碎和冗长,对于特定领域来说,往往存在更为简洁的名称,例如:母亲的兄弟可简称为舅舅。对于这些场景,如果能够类似 DSL (领域特定语言)那样允许用户根据专业要求自行扩展,从而简化查询,方便阅读,无疑会更为友好。
如果读者去看原作者的实现,会发现他是用一种特殊语法 addAlias 来定义自己想要的查询,调用方法时再进行查询以确定要执行的内容,其接口和内部实现都是相当复杂的。
而我希望有更简单的方法来实现这一点。所幸 Python 是一种高度动态的语言,允许在运行时向类中增加新的成员,因此做到这一点可能比预想的还要简单。
为了验证这一点,编写测试如下:
无需 Dagoba 的实现做任何改动,测试就可以通过了!其实我们要做的就是动态添加一个自定义的成员函数,按照 Python 对象机制的要求,成员函数的第一个成员应该是名为 self 的参数,但这里已经是在 UnitTest 的内部,为了和测试类本身的 self 相区分,新函数的参数增加了一个下划线。
此外,函数应返回其所属的对象,这是为了链式调用所要求的。我们看到,动态语言的灵活性使得添加新语法变得非常简单。
到此,一个初具规模的图数据库就形成了。
和原文相比,本文还缺少一些内容,比如如何将数据库序列化到磁盘。不过相信读者都看到了,我们的数据库内部结构基本上是简单的原生数据结构(列表+字典),因此序列化无论用 pickle 或是 JSON 之类方法都应该是相当简单的。有兴趣的读者可以自行完成它们。
我们的图数据库实现为了提高查询性能,在节点内部存储了边的指针(或者说引用)。这样做的好处是,无论数据库有多大,从一个节点到相邻节点的访问是常数时间,因此数据访问的效率非常高。
但一个潜在的问题是,如果数据库规模非常大,已经无法整个放在内存中,或者出于安全性等原因要实现分布式访问的话,那么指针就无法使用了,必须要考虑其他机制来解决这个问题。分布式数据库无论采用何种数据模型都是一个棘手的问题,在本文中我们没有涉及。有兴趣的读者也可以考虑 500lines 系列中关于分布式和集群算法的其他一些文章。
本文的实现和系列中其他数据库类似,采用 Python 作为实现语言,而原作者使用的是 JavaScript ,这应该和作者的背景有关。我相信对于大多数开发者来说, Python 的对象机制比 JavaScript 基于原型的语法应该是更容易阅读和理解的。
当然,原作者的版本比本文版本在实现上其实是更为完善的,灵活性也更好。如果想要更为优雅的实现,我们可以考虑使用 Python 元编程,那样会更接近于作者的实现,但也会让程序的复杂性大为增加。如果读者有兴趣,不妨对照着去读读原作者的版本。