2.1 图的结构

在第1章中，我们介绍了图的基本思想。在本节中，我们将进行更深入的探讨。首先，我们将确定本书后面要用到的术语。然后，我们将更多地讨论图模式的概念，这是你制定计划和了解数据结构的关键。

2.1.1 图的术语

假设你正在组织关于电影、演员和导演的数据。也许你在Netflix或其他流媒体服务公司工作，或者你只是一个影迷。

让我们以电影《星球大战4：新希望》（Star Wars：A New Hope）及其三位主演和导演为例。如果在关系数据库中构建此数据，你可以将此信息记录在一个表中，但该表将很快变得庞大并难以处理。如何将一部电影的细节、50位演员和每位演员职业生涯的详细信息都记录到一个表中呢？

关系数据库的最佳实践是将演员、电影和导演分别放入单独的表中，但这也意味着需要添加交叉引用表来处理演员和电影之间、电影和导演之间的多对多关系。

在关系数据库中，你需要5个表来表示这个例子，如图2-1所示。

尽管将不同类型的事物分成不同的表是组织数据的正确方法，但要了解一条记录与另一条记录之间的关系，我们必须重新连接数据。查询哪位演员与哪位导演一起工作时，需要在内存中创建一个临时表，该表被称为连接表（join table），表中包括满足查询条件的所有可能的行组合。就内存和处理器时间而言，连接表是昂贵的。

从图2-2中可以看出，这个表连接中存在很多冗余数据。对于非常大或复杂的数据库来说，你需要考虑如何组织数据和查询，以优化连接表。

如果我们将其与图2-3所示的图方法进行比较，就会立即注意到一个事实：表和图之间的区别在于，图可以直接显示一个数据元素与其他数据元素之间的关系。也就是说，数据点之间的关系是在数据库中直接构建的，而不必在运行时构建。因此，图数据库和关系数据库之间的一个关键区别在于，在图数据库中，数据点之间的关系是显式的。

每个演员、电影和导演都被称为节点或顶点。顶点代表事物，可以是实体或抽象概念。在我们的例子中，图2-3有5个顶点。顶点之间的连接被称为边，描述顶点之间的关系。边也被视为数据元素。图2-3有4条边：3条表示演员与电影之间的关系（acted_in），1条表示导演与电影之间的关系（directed_by）。在最简单的形式中，图就是顶点和边的集合。我们将使用通用术语对象来表示顶点或边。

有了这个图，我们可以回答一个基本问题：哪些演员与导演George Lucas合作过？从George Lucas开始，我们查看他执导的电影，包括《星球大战》，然后我们查找在该电影中出演的演员，包括Mark Hamill、Carrie Fisher和Harrison Ford。

区分边的方向是有用的，甚至是必要的。在图数据库中，边可以是有向的或无向的。有向边具有特定的方向，它从一个源顶点指向目标顶点。我们使用箭头来绘制有向边。

通过添加有向边，我们还可以看出层次关系，即《帝国反击战》（The Empire Strikes Back）是《星球大战》的续集（见图2-4）。

为了提高图的实用性，我们需要为每个顶点或边添加更多细节，例如演员的出生日期或电影的类型。

下面我们介绍属性图。属性图是一种每个顶点和每条边都可以具有属性的图，这些属性提供了有关单个元素的详细信息。回顾一下关系数据库，属性就像表中的列一样。属性使图变得真正有用，它们为数据增添了丰富性和上下文，使我们能够开发更精细的查询来提取所需的数据。图2-5展示了带有一些附加属性的《星球大战》图。

图为我们提供了另一种给属性建模的选择。我们可以将每个电影类型作为一个单独的顶点，而不是将类型作为电影的属性。为什么要这样做呢？当某个属性是一种类别属性时，我们会期望有很多其他顶点具有相同的属性值（例如，有很多科幻电影）。将所有的科幻电影都链接到科幻顶点，能使搜索它们或收集关于它们的统计数据变得非常容易，例如，搜索“票房最高的科幻电影是什么”，所有非科幻电影都已经被过滤掉了。图结构不仅可以为核心数据建模，还可以充当搜索索引。

将属性建模为顶点的另一个原因是提高规范化或数据丰富度。规范化是一种分解表的方法，用于消除冗余和减少更新复杂性。此外，分解出更多种顶点意味着我们可以有更多的属性。

在电影数据库示例中，我们可能希望创建一种称为 Character 的新顶点类型，以便显示谁扮演了哪个角色。图2-6为《星球大战》图添加了 Character 类型的顶点。关于Darth Vader这个角色最有趣之处在于，他由两个人扮演：David Prowse（演戏）和James Earl Jones（配音）。幸运的是，我们的图数据库只需进行少量的修改，就可以轻松表示这种情况。

图2-6还可以做什么呢？好吧，它足够灵活，可以让我们添加几乎所有参与这部电影制作的人——从导演、演员到化妆师、特效师、道具师，甚至最佳男主角。每个对电影有所贡献的人都可以使用边worked_on和边属性role连接起来，其中包括director、actor、voice actor、camera operator、key grip等。

如果我们将数据库构建为包含数千部电影和每个参与制作电影的人员，那么我们就可以使用图算法来回答诸如“某些导演最喜欢与哪些演员一起合作？”之类的问题。使用图数据库，你可以回答那些不太明显的问题，例如“谁是科幻特效方面的专家？”或“某些导演最喜欢和哪些灯光师一起工作？”对于销售图形软件或灯光设备的公司来说，这些问题是非常有趣的。

通过图数据库，你可以连接到多个数据源，提取所需的数据作为顶点，并在组合后的数据集上运行查询操作。如果你有权访问各种电影项目中使用的灯光设备数据库，则可以将其连接到你的电影数据库，并使用图查询来找出哪些灯光师使用过哪些设备。

表2-1总结了我们所介绍的图术语。

2.1.2 图的模式

在上一节中，我们选择从一个非常简单的图开始，然后通过添加更多的顶点、边和属性，以及新类型的顶点和边，来增加图的复杂性。要对图进行良好的建模和管理，规划好数据类型和属性至关重要，特别是在业务环境中。

我们将这种规划称为图模式或图数据模型，类似于关系数据库的模式或实体关系模型。它定义了图中将包含的顶点和边的类型，以及与这些对象相关的属性。

你可以通过添加任意顶点和边来创建没有模式的图，但你很快就会发现，这样的图难以使用和理解。此外，如果你想搜索所有电影的数据，知道它们确切的类型，例如，它们都被称为“movie”而不是“film”或“motion picture”，这一点将是非常有用的！

为每种对象类型确定一组标准属性也很有帮助。如果我们知道所有电影顶点都具有相同的核心属性集，例如标题、类型和上映日期，我们就可以轻松而自信地对这些属性进行分析。

图2-7显示了可能的电影数据库的图模式。它系统地处理了在我们向数据库中添加越来越多的电影时出现的一些数据复杂性。

该模式的特性如下：

· 一个 Person 类型的顶点代表现实世界中的一个人，比如George Lucas。

· Worked_on 类型的边将一个人连接到一部电影。它有一个属性来描述这个人的角色：导演、制片人、演员、灯光师等。通过将角色作为属性，我们只需要为人和电影定义一个顶点类型和一个边类型就可以支持任意多的角色。如果一个人有多种角色，那么图可以有多条边 。模式只显示每种类型的一个对象。

· Character 类型的顶点与 Person 类型的顶点是分开的。一个人可以扮演多个角色（泰勒·佩里在《玛迪亚》电影中的角色），或者多个人扮演同一个角色（《绝地归来》中饰演达斯·维德的大卫·普劳斯、詹姆斯·厄尔·琼斯和塞巴斯蒂安·肖）。

· Movie 类型的顶点很简单明了。

· Is_sequel_of 是一个有向边类型，告诉我们源电影是目标电影的续集。

· 如前文所述，我们选择将电影的类型（ Genre ）建模为顶点而不是属性，以便按类型过滤和分析电影。

理解模式的关键在于，要有一组一致的对象类型集合，使数据更易于解释。 8EVqCAtDDXcxYSPdQrdzPYTx1h0jUacLqKXoXdOBD/dqmvEP6C+CI0ey3KoIZV6k