第 1 章　初識圖

本章內(nèi)容

● 圖以及相關(guān)術(shù)語介紹

● 圖數(shù)據(jù)庫如何有助于解決高度關(guān)聯(lián)數(shù)據(jù)問題

● 圖數(shù)據(jù)庫相對于關(guān)系數(shù)據(jù)庫的優(yōu)勢

● 識別適合使用圖數(shù)據(jù)庫的問題

現(xiàn)代應(yīng)用程序是基于數(shù)據(jù)構(gòu)建的，而數(shù)據(jù)的規(guī)模在不斷擴大，復(fù)雜性也在不斷提高。隨著數(shù)據(jù)的復(fù)雜性越來越高，我們對應(yīng)用程序從這些數(shù)據(jù)中有所收獲的期望也越來越高。如果你接觸計算機有一定年頭了，那么可能還記得那些加載數(shù)據(jù)需要很長時間并且功能有限的應(yīng)用程序。時代不同了，現(xiàn)在的應(yīng)用程序需要提供強大、靈活、即時的數(shù)據(jù)洞察力。但是，現(xiàn)代應(yīng)用程序每解答100個疑問，最常見的數(shù)據(jù)工具（關(guān)系數(shù)據(jù)庫）只能很好地處理其中的88個，還剩下12個難以解答。這些疑問涉及數(shù)據(jù)中的鏈接和連接，而這些方面恰恰能讓我們對數(shù)據(jù)產(chǎn)生強大而獨特的理解。這就使我們處在了一個岔路口：要么選擇使用關(guān)系數(shù)據(jù)庫這個“錘子”1強行解答這些疑問，勉強應(yīng)付；要么后退一步，看看還有哪些工具可以更好、更快、更省力地做出解答。

1這里的“錘子”來自于查理·芒格的一句話：“拿著錘子的人，看什么都像釘子。”——譯者注

既然選擇閱讀本書，就說明你已經(jīng)決定從關(guān)系數(shù)據(jù)庫這個“錘子”后退一步，研究一條鮮為人知的道路：圖數(shù)據(jù)庫。本書面向想探索其他方法來解決高度關(guān)聯(lián)數(shù)據(jù)相關(guān)問題的開發(fā)人員、工程師和架構(gòu)師。我們假定你熟悉關(guān)系數(shù)據(jù)庫，并且對了解圖數(shù)據(jù)庫何時、何地以及如何能成為更好的工具感興趣。

本書的目標是幫你掌握所需的技術(shù)，將圖數(shù)據(jù)庫添加進你的工具袋里。我們多么希望當(dāng)初在開始構(gòu)建以圖為基礎(chǔ)的應(yīng)用程序時能有這樣一本書作為指導(dǎo)。本書將展示常見的圖模式，這些模式突出了圖數(shù)據(jù)庫是如何以傳統(tǒng)關(guān)系數(shù)據(jù)庫難以實現(xiàn)的方式來導(dǎo)航和探索數(shù)據(jù)的。

我們的主要方法是構(gòu)建一個虛構(gòu)的餐廳評價和推薦應(yīng)用程序示例，名為“友聚”（DiningByFriends）。通過這個示例來走一遍從規(guī)劃、分析、設(shè)計到實現(xiàn)的軟件開發(fā)生命周期，我們將演示如何設(shè)計和使用圖數(shù)據(jù)。每一章都建立在前一章的基礎(chǔ)之上，到本書結(jié)束時，我們將在一個圖數(shù)據(jù)庫上創(chuàng)建了一個能夠正常運行的應(yīng)用程序。我們認為，通過解決一系列現(xiàn)實問題（即使這些問題被簡單化了），立即將概念付諸實踐，是掌握新技術(shù)的最佳途徑。讓我們從介紹什么是圖和圖數(shù)據(jù)庫，以及它們與關(guān)系數(shù)據(jù)庫等傳統(tǒng)工具的區(qū)別開始吧。

1.1　什么是圖

當(dāng)你查看路線圖，研究組織結(jié)構(gòu)圖，或者使用Facebook、LinkedIn、Twitter等社交網(wǎng)絡(luò)的時候，就是在使用圖。圖，是一種幾乎無處不在、用來思考現(xiàn)實世界場景的方法，因為圖能夠抽象出這些場景要表現(xiàn)的項（item）和關(guān)系，從而能夠快速、高效地處理數(shù)據(jù)中的連接。

讓我們用一個常見的任務(wù)來演示這一點吧：從家去超市。拿出一張紙，畫出從你家到超市的路線，很可能如圖1-1所示。

圖1-1　表示從家到超市的導(dǎo)航圖

圖1-1展示了一張用抽象方法來表示關(guān)鍵項及其關(guān)系的圖。我們首先抽象出關(guān)鍵位置，如路口，并將其表示為圓；然后將這些關(guān)鍵交叉點之間的連接表示為線，以體現(xiàn)其間的關(guān)聯(lián)。這只是如何自然地將現(xiàn)實世界問題表現(xiàn)為圖的一個例子。

對現(xiàn)實世界中的實體及其關(guān)系進行抽象是人類的天性，這種抽象結(jié)構(gòu)的數(shù)學(xué)名稱就是圖。當(dāng)要思考的數(shù)據(jù)集含有大量高度相互關(guān)聯(lián)的項時，也可以將該數(shù)據(jù)集描述為一個由相關(guān)事物組成的網(wǎng)絡(luò)，這也是圖的另一種說法。

在地圖上，城市通常用圓來表示，連接這些城市的路則用線來表示。在組織結(jié)構(gòu)圖中，一個圓通常代表一個人，并通常帶有相關(guān)的頭銜，將這些人連接在一起的線則表示雇傭關(guān)系。在社交網(wǎng)絡(luò)中，人們通過加好友或關(guān)注的方式來相互連接。這種對實體及其之間的關(guān)聯(lián)進行概括的過程就是圖和圖論的基礎(chǔ)。數(shù)學(xué)家?guī)讉€世紀以來對圖進行的定義和研究，讓我們得以直接將圖論中的這些定義作為術(shù)語。

● 圖：頂點和邊的集合。

● 頂點：圖中零條、一條或多條邊經(jīng)過的點，也稱為節(jié)點或?qū)嶓w。

● 邊：圖中兩個頂點之間的關(guān)系，有時也稱為關(guān)系、鏈接或連接。

歐拉與圖論的起源

人們一般認為，圖論起源于萊昂哈德·歐拉在1736年發(fā)表的一篇關(guān)于“哥尼斯堡七橋問題”的論文。哥尼斯堡（現(xiàn)為俄羅斯加里寧格勒）當(dāng)時是普魯士的一座城市，位于普雷格爾河畔。這條河中有兩座島，通過七座橋相互連接以及和主城連接。論文中的實驗要設(shè)計出一條路線，讓鎮(zhèn)上的居民可以不重復(fù)、不遺漏地一次走完七座橋，最后回到出發(fā)點。歐拉通過創(chuàng)建島（頂點）和它們之間的橋梁（連接或邊）的抽象表示來解決這個問題。基于這種抽象，歐拉指出，重要的不是具體的項，而是表現(xiàn)這些項之間如何連接的拓撲結(jié)構(gòu)。

歐拉在論文中指出，要解決這個問題，該圖需要零個或兩個具有奇數(shù)連接的節(jié)點。如今，任何滿足這一條件的圖都被稱為歐拉圖。如果路徑只訪問每條邊一次，則該圖具有歐拉路徑。如果路徑起點和終點相同，則該圖具有歐拉回路，或稱為歐拉環(huán)。我們講這個故事是為了分享一個很有趣的歷史背景，但是在實踐經(jīng)驗中，我們從未在任何現(xiàn)實世界的問題中用過這些學(xué)術(shù)事實或歐拉定義。

雖然定義很正式，但是圖的優(yōu)點是簡單、易于說明。在實際使用中，圖通常由表示頂點的圓和表示邊的線組成，如圖1-2所示。

圖1-2　很容易通過用圓來表示頂點、用線來表示邊來表示圖

注意　本書使用頂點和邊這兩個術(shù)語。有一些圖數(shù)據(jù)庫使用節(jié)點而非頂點，使用關(guān)系而非邊，但是它們在概念上是相同的。

對于軟件開發(fā)人員來說，圖并不是什么新概念。它是我們在軟件開發(fā)中使用的許多常見數(shù)據(jù)結(jié)構(gòu)的基礎(chǔ)，甚至可能根本令人意識不到。常見的數(shù)據(jù)結(jié)構(gòu)，如鏈表和樹，都是應(yīng)用了特定規(guī)則的圖。雖然這些數(shù)據(jù)結(jié)構(gòu)為開發(fā)人員所熟知，但是它們特定于圖的實現(xiàn)細節(jié)通常被抽象掉了。

1.1.1　什么是圖數(shù)據(jù)庫

圖數(shù)據(jù)庫是一種數(shù)據(jù)存儲引擎，將包含頂點和邊的基本圖結(jié)構(gòu)與持久化技術(shù)和遍歷（查詢）語言相結(jié)合，以創(chuàng)建針對高度關(guān)聯(lián)數(shù)據(jù)的存儲和快速檢索進行優(yōu)化的數(shù)據(jù)庫。與其他數(shù)據(jù)庫技術(shù)不同，圖數(shù)據(jù)庫建立在這樣的概念上：實體之間的關(guān)系與數(shù)據(jù)中的實體同等重要，甚至比后者更加重要。由于實體和關(guān)系得到了同等對待，因此圖數(shù)據(jù)庫可以用于更準確、更容易地表示和推理現(xiàn)實世界中的關(guān)系，特別是與其他數(shù)據(jù)庫技術(shù)相比。正如本書將展示的，如果既要表示事物之間豐富多樣的關(guān)系，又要識別基于這些關(guān)系的模式，那么圖數(shù)據(jù)庫是更好的工具。

下面簡要介紹用關(guān)系數(shù)據(jù)庫表示多種關(guān)系面臨的一些挑戰(zhàn)。關(guān)系數(shù)據(jù)庫（這個命名有點諷刺）在表示豐富的關(guān)系方面表現(xiàn)得相當(dāng)差。它使用外鍵來表示關(guān)系，而外鍵就是指向其他表中主鍵的指針。這些指針不容易觀察和操作。與圖數(shù)據(jù)庫不同，在查詢關(guān)系時，外鍵是從一行跟隨到另一行的。（因此，關(guān)系數(shù)據(jù)庫盡管能夠表示關(guān)系，但往往代價高昂。）關(guān)系數(shù)據(jù)庫中的查找表或鏈接表使用的不是查詢時的指針結(jié)構(gòu)，而是存儲了有關(guān)關(guān)系屬性的結(jié)構(gòu)，類似于圖數(shù)據(jù)庫中的邊結(jié)構(gòu)。

圖數(shù)據(jù)庫為在數(shù)據(jù)中遍歷關(guān)系提供了極好的工具。通過將連接（邊）和數(shù)據(jù)項（頂點）放在同等重要的地位，圖數(shù)據(jù)庫可以將這些關(guān)聯(lián)表示為數(shù)據(jù)庫里的完整結(jié)構(gòu)，從而輕松地觀察和操作。這種存儲豐富關(guān)系的能力是圖數(shù)據(jù)庫更適合處理復(fù)雜鏈接數(shù)據(jù)用例的主要原因之一。用開發(fā)人員的話來說，邊和頂點一樣，都是“一等公民”。也就是說，關(guān)系在數(shù)據(jù)模型中與事物或?qū)嶓w一樣重要、一樣有用。

最后要說的是，圖數(shù)據(jù)庫可以通過其他技術(shù)無法實現(xiàn)的方式來提高開發(fā)人員解決某些問題的效率。圖數(shù)據(jù)庫存儲數(shù)據(jù)的方式能更好地代表現(xiàn)實世界，從而令開發(fā)人員能夠更容易地思考和理解他們所處的業(yè)務(wù)領(lǐng)域。這能令新的團隊成員更快地熟悉業(yè)務(wù)，并同時學(xué)到業(yè)務(wù)領(lǐng)域知識及其數(shù)據(jù)庫表示。

1.1.2　與其他類型數(shù)據(jù)庫的比較

雖然本書主要討論圖數(shù)據(jù)庫，并主要使用關(guān)系數(shù)據(jù)庫作為襯托，但我們應(yīng)該注意，數(shù)據(jù)庫世界并非只有這兩種類型的數(shù)據(jù)存儲。從最廣泛的角度來說，數(shù)據(jù)庫可以分為以下五種引擎類型。圖1-3總結(jié)了這些數(shù)據(jù)庫引擎類型之間的關(guān)系。

● 鍵值數(shù)據(jù)庫：所有數(shù)據(jù)都由唯一標識符（鍵）和關(guān)聯(lián)的數(shù)據(jù)對象（值）表示。例子包括Berkeley DB、RocksDB、Redis和Memcached。

● 列存儲數(shù)據(jù)庫（又名面向列、寬列式數(shù)據(jù)庫）：數(shù)據(jù)按列來存儲，可能每行有大量的列，也可能每行的列數(shù)不一樣。例子包括Apache HBase、Azure Table Storage、Apache Cassandra和Google Cloud Bigtable。

● 文檔數(shù)據(jù)庫（又名面向文檔數(shù)據(jù)庫）：將數(shù)據(jù)存儲到帶有唯一鍵的文檔中，該文檔可以具有不同的模式，也可以包含嵌套數(shù)據(jù)。例子包括MongoDB和Apache CouchDB。

● 關(guān)系數(shù)據(jù)庫：將數(shù)據(jù)存儲在包含具有嚴格模式行結(jié)構(gòu)的表中，允許在表之間連接行來建立關(guān)系。例子包括PostgreSQL、Oracle Database和Microsoft SQL Server。

● 圖數(shù)據(jù)庫：將數(shù)據(jù)存儲為頂點（節(jié)點、組件）和邊（關(guān)系）。例子包括Neo4j、Apache TinkerPop的Gremlin Server、JanusGraph和TigerGraph。

圖1-3　按數(shù)據(jù)復(fù)雜性排序的數(shù)據(jù)庫引擎類型

從這些例子可以看出，默認情況下，只有關(guān)系數(shù)據(jù)庫和圖數(shù)據(jù)庫才具有將數(shù)據(jù)中的實體關(guān)聯(lián)起來的功能。雖然使用鍵值數(shù)據(jù)庫、列存儲數(shù)據(jù)庫或文檔數(shù)據(jù)庫的特定產(chǎn)品也可能具有這個功能，但通常是由具體數(shù)據(jù)庫產(chǎn)品廠商特意添加的增強功能。因為我們的重點是圖數(shù)據(jù)庫，而只有關(guān)系數(shù)據(jù)庫具有類似、可比較的功能，所以接下來的討論僅限于這兩種引擎類型。

1.1.3　為什么不能使用SQL

作為開發(fā)人員，我們經(jīng)常選擇熟悉的工具，而不是最佳的工具，尤其是在處理數(shù)據(jù)庫時。大多數(shù)開發(fā)團隊對關(guān)系數(shù)據(jù)庫的各種細節(jié)有深入的了解，但是很少有人精通其他類型的數(shù)據(jù)庫。因此，即使某些問題可以用更好的工具解決，我們也經(jīng)常出于方便或者無知而默認使用關(guān)系數(shù)據(jù)庫。

這并不是說關(guān)系數(shù)據(jù)庫是糟糕的工具。實際上，它通常是我們在開發(fā)應(yīng)用程序時的首選工具。但是，關(guān)系數(shù)據(jù)庫有其局限性。雖然關(guān)系數(shù)據(jù)庫也可以用于存儲高度關(guān)聯(lián)數(shù)據(jù)，但在許多情況下，可以使用專門為這類用例設(shè)計的工具來簡化工作。在以下三個方面，圖數(shù)據(jù)庫提供了比關(guān)系數(shù)據(jù)庫更簡單、更優(yōu)雅的解決方案，本節(jié)將一一介紹：

● 遞歸查詢（例如，組織中員工的匯報層次結(jié)構(gòu)或者組織結(jié)構(gòu)圖）

● 復(fù)合結(jié)果類型（例如，訂單和產(chǎn)品報告示例）

● 路徑（例如，過河問題）

本章將用三個示例來分別展示圖數(shù)據(jù)庫的這三個獨特功能。從第2章開始，我們將介紹“友聚”的問題領(lǐng)域，并開始正式的數(shù)據(jù)建模過程。屆時，大多數(shù)示例將隨對應(yīng)示例領(lǐng)域的發(fā)展而變化。但在此之前，我們將使用多種方法介紹圖和圖數(shù)據(jù)庫的基本概念。

遞歸查詢

遞歸查詢會連續(xù)執(zhí)行多次，反復(fù)調(diào)用自己，直到滿足某種終止條件。關(guān)系數(shù)據(jù)庫不能很好地處理遞歸操作（尤其是無邊界的遞歸操作），不論在語法還是性能方面都很吃力。這通常會導(dǎo)致需要編寫和維護復(fù)雜的查詢語句，或者/以及對數(shù)據(jù)進行過度的反規(guī)范化，而這只是為了及時返回結(jié)果而已。

圖數(shù)據(jù)庫能夠利用其表示豐富關(guān)系的能力，干凈、高效地處理無邊界遞歸查詢。為了更好地理解，讓我們看看遞歸查詢在SQL和圖數(shù)據(jù)庫中分別是什么樣子的。假設(shè)有如圖1-4所示的公司員工和經(jīng)理列表，我們來研究如何找出具體某個人的匯報層次結(jié)構(gòu)。

圖1-4　演示遞歸查詢用的管理層次結(jié)構(gòu)

為了在關(guān)系數(shù)據(jù)庫中對該層次結(jié)構(gòu)進行建模，以下SQL語句定義了表結(jié)構(gòu)。然后，按照這個表結(jié)構(gòu)來布局數(shù)據(jù)，如表1-1所示。

CREATE TABLE org_chart (
  employee_id           SMALLINT NOT NULL,
  manager_employee_id   SMALLINT NULL,
  employee_name         VARCHAR(20) NOT NULL
);

表1-1　使用關(guān)系數(shù)據(jù)庫的組織管理層次結(jié)構(gòu)示例

然后使用遞歸函數(shù)來查詢這些數(shù)據(jù)，以找出用戶的管理層次結(jié)構(gòu)。以下是查詢語句的代碼片段。

WITH RECURSIVE org AS (
     SELECT employee_id,
            manager_employee_id,
            employee_name,
            1 AS level
     FROM org_chart
  UNION
     SELECT e.employee_id,
            e.manager_employee_id,
            e.employee_name,
            m.level + 1 AS level
     FROM org_chart AS e
       INNER JOIN org AS m ON e.manager_employee_id = m.employee_id
  )
SELECT employee_id, manager_employee_id, employee_name
FROM org
ORDER BY level ASC;

如果用SQL的通用表表達式（common table expression，CTE）編寫過像上面管理層次結(jié)構(gòu)查詢一樣的SQL語句，那么你就會知道，這些表達式可能編寫和調(diào)試起來很復(fù)雜，并且因性能不佳而臭名昭著。嵌套查詢和遞歸查詢（如前面的層次結(jié)構(gòu)示例所示）是圖數(shù)據(jù)庫擅長解答的疑問類型。例如，圖1-5展示了相同數(shù)據(jù)的圖結(jié)構(gòu)。

圖1-5　以圓為頂點、箭頭為邊的組織層次結(jié)構(gòu)圖表示

要在圖中找到用戶的管理鏈，需要編寫一個類似于SQL查詢的查詢語句，這種查詢在圖中稱為遍歷。對于我們的層次結(jié)構(gòu)示例，遍歷語句如下所示。

g.V().
  repeat(
    out('works_for')
  ).path().next()

注意　這個遍歷使用的是一種稱為Gremlin的圖查詢語言，整本書中都將使用該語言。此時還不需要確切地了解它是如何工作的，我們將從第3章開始詳細研究它。現(xiàn)在，只需要注意該查詢語句與前面的SQL查詢語句相比更為簡單。

這個示例展示了通過圖來解決遞歸問題有多么簡單、直接。如果將其與圖1-5進行比較，就可以看到，這種遍歷能夠自然地契合我們對數(shù)據(jù)層次結(jié)構(gòu)的直觀理解。
 

復(fù)合結(jié)果類型

你是否曾經(jīng)需要從數(shù)據(jù)庫中返回一個包含好幾種數(shù)據(jù)類型的結(jié)果集？雖然可以通過聯(lián)合各個表的列來實現(xiàn)這一點，但結(jié)果往往不太理想。圖數(shù)據(jù)庫的優(yōu)點之一就是能夠返回包含不同數(shù)據(jù)類型的結(jié)果集。讓我們比較一下在返回不同數(shù)據(jù)類型結(jié)果集時，關(guān)系數(shù)據(jù)庫和圖數(shù)據(jù)庫分別是如何處理的。

例如，假設(shè)我們有一個訂單處理系統(tǒng)，并且希望在結(jié)果集中既返回訂單信息，又同時返回產(chǎn)品信息。圖1-6展示了通過表來做到這一點的關(guān)系數(shù)據(jù)庫傳統(tǒng)實現(xiàn)。

圖1-6　關(guān)系數(shù)據(jù)庫中的訂單和產(chǎn)品表。注意列名之間的差異

以下代碼片段展示了檢索帶有相關(guān)產(chǎn)品信息的訂單查詢語句2。表1-2展示了該查詢語句的結(jié)果集。

SELECT id,
       name,
       address,
       null AS product_name,
       null AS cost,
       'Order' AS object_type
FROM Orders
UNION
SELECT id,
       null AS name,
       null AS address,
       product_name,
       cost,
       'Product' AS object_type
FROM Products;

表1-2　檢索訂單并從中檢索產(chǎn)品的關(guān)聯(lián)查詢結(jié)果

可以看到，聯(lián)合兩種不同數(shù)據(jù)類型的結(jié)果表明，這個方案會包含大量空值（這種情況通常稱為稀疏數(shù)據(jù)或稀疏矩陣）。如此多的空數(shù)據(jù)是兩個表之間的列不一致造成的。關(guān)系數(shù)據(jù)庫指定聯(lián)合返回的結(jié)果集必須包含一致的列。在稀疏數(shù)據(jù)的情況下，這不僅增加了返回的數(shù)據(jù)量，還降低了數(shù)據(jù)結(jié)構(gòu)的描述性。下面來看看相同數(shù)據(jù)在圖數(shù)據(jù)庫中的顯示方式（見圖1-7）。

圖1-7　訂單產(chǎn)品信息示例展示為圖中的頂點（未對邊建模）

使用這個圖，可以編寫一個圖遍歷來返回產(chǎn)品和訂單數(shù)據(jù)。在此示例中，圖數(shù)據(jù)庫返回以下結(jié)果。

gremlin> g.V().valueMap(true)

==>[label:order, address:[123 Main St], name:[John Smith], id:1]
==>[label:order, address:[234 Park St], name:[Jane Right], id:2]
==>[label:product, cost:[10.76], id:234, product_name:[widget 2]]
==>[label:product, cost:[5.95], id:123, product_name:[widget 1]]

與前面的SQL結(jié)果相比，從圖返回的數(shù)據(jù)保留了對象的含義及其表示的語義，并且沒有多余的空數(shù)據(jù)。因為圖數(shù)據(jù)庫提供了返回不同類型數(shù)據(jù)的靈活性，所以當(dāng)要處理不同的數(shù)據(jù)類型時，我們可以寫出更簡潔的代碼。
 

路徑

路徑是一組頂點和邊的序列，描述遍歷如何在圖中移動。例如，在Google地圖或Apple地圖中，兩個地點之間的一組方向就是路徑。從數(shù)據(jù)庫中返回兩個對象的關(guān)聯(lián)關(guān)系是圖數(shù)據(jù)庫獨有的功能。

讓我們看看一個被稱為“過河問題”的經(jīng)典問題，以此說明路徑是如何以一種新穎的方式來解決問題的。在問題中，有一只狐貍、一只鵝和一袋大麥必須由農(nóng)夫用船運過河。但是，移動過程有如下限制條件。

● 每次移動過程中，除了農(nóng)夫以外，船上只能攜帶一件物品。

● 農(nóng)夫必須參與每次移動過程。

● 狐貍不能單獨和鵝待在一起，否則狐貍會吃掉鵝。

● 鵝不能單獨和大麥待在一起，否則鵝會吃掉大麥。

使用關(guān)系數(shù)據(jù)庫，如果不采用暴力破解的方法來計算出所有可能的組合，我們將找不到解決該問題的方法。但是，如果使用圖，通過巧妙的數(shù)據(jù)建模和強大的尋路算法（又名路徑算法），就能很簡單地解決這個問題。

首先，將系統(tǒng)的初始狀態(tài)建模為圖的頂點。我們將頂點命名為TGFB_，其中每個字符代表問題的一部分：

● T（船和農(nóng)夫）

● G（鵝）

● F（狐貍）

● B（大麥）

● _（河）

頂點TGFB_編碼了問題的狀態(tài)，告訴我們船和農(nóng)夫、鵝、狐貍和大麥都在河的一側(cè)。我們期望達到的狀態(tài)是，所有這些字符都在河的另一側(cè)。

當(dāng)用頂點來表示可能的狀態(tài)時，就能使用邊來展示如何從一個狀態(tài)轉(zhuǎn)換到下一個狀態(tài)了。例如，圖1-8展示了如何表示農(nóng)夫把鵝運到河的另一側(cè)，把狐貍和大麥留在河最初一側(cè)的狀態(tài)變化。圖1-9展示了將所有的潛在選項建模為這些狀態(tài)（頂點）和狀態(tài)變化（邊）的表示結(jié)果。

圖1-8　農(nóng)夫用船（T）運鵝（G）過河（_），留下狐貍（F）和大麥（B）的圖示

圖1-9　使用尋路算法求解過河問題的完整圖。注意，這清楚地描述了可能的解決方案，任何違反限制條件的狀態(tài)都被突出顯示了

圖1-10說明了如果通過刪除違反限制條件的狀態(tài)（頂點）和相鄰關(guān)系（邊）來簡化圖，會發(fā)生什么情況。可以通過刪除任何連接回先前狀態(tài)的邊來進一步簡化圖，因為它們會將我們引向先前的狀態(tài)（這種情況在圖論中稱為環(huán)）。

圖1-10　用只顯示有效狀態(tài)的尋路算法求解過河問題

通過分析圖1-10，可以看到有兩條不同的路徑能夠達到我們想要的狀態(tài)。要查詢圖以返回這些路徑，只需利用圖數(shù)據(jù)庫的尋路功能通過如下所示的遍歷語句來返回這兩條正確的路徑。

g.V('TFGB_').
  repeat(
    out()
  ).until(hasId('_TGFB')).
  path().next()

當(dāng)我們運行這個遍歷語句時，它不僅返回訪問過的第一個和最后一個頂點，而且返回一路上訪問過的所有頂點和邊。這兩個列表代表了解決方案的兩條不同路徑。

TFGB_ -運鵝過河-> FB_TG -空船返回-> TFB_G -運大麥過河-> F_TGB -運鵝返回->
     TFG_B -運狐貍過河-> G_TBF -空船返回-> TG_FB -運鵝過河-> _TGFB

TFGB_ -運鵝過河-> FB_TG -空船返回-> TFB_G -運狐貍過河-> B_TFG -運鵝返回->
     TGB_F -運大麥過河-> G_TBF -空船返回-> TG_FB -運狐貍過河-> _TGFB

這個例子雖然只是一個數(shù)學(xué)問題，但是代表了現(xiàn)實世界應(yīng)用中的許多同類問題，例如在地圖上尋找路線，在物流系統(tǒng)中尋找最優(yōu)資源使用解，或者在社交網(wǎng)絡(luò)中定位人與人之間的聯(lián)系。這些情況從根本上都是求解從一個實體到另一個實體的最佳操作集。圖數(shù)據(jù)結(jié)構(gòu)能夠讓我們充分利用它的尋路功能，而其他數(shù)據(jù)庫類型并不原生支持這些功能。

2雖然實際工作中沒有人會用這么笨的SQL和方法來解決問題，但是這個例子能明顯體現(xiàn)關(guān)系數(shù)據(jù)庫與圖數(shù)據(jù)庫的差異。請把注意力集中在圖數(shù)據(jù)庫如何優(yōu)雅地處理關(guān)系數(shù)據(jù)庫里的UNION操作上。——譯者注

1.2　我的問題適合用圖數(shù)據(jù)庫嗎

從社交網(wǎng)絡(luò)分析、推薦引擎、依賴性分析、欺詐檢測和主數(shù)據(jù)管理，到搜索問題和互聯(lián)網(wǎng)上的研究，你很快就能列出一個適合使用圖數(shù)據(jù)庫的用例列表。使用該列表的困難在于，除非你的問題恰好在列表中，否則很難知道如何使用圖數(shù)據(jù)庫來解決你的問題，或者你的問題是否適合用圖數(shù)據(jù)庫來解決。

本節(jié)不再關(guān)注特定的用例，而是以更通用的方式來研究問題。這有些偏概念性，但是我們發(fā)現(xiàn)很難通過一個例子概括特定的問題領(lǐng)域。我們將從定義一個通用問題開始，然后提供一些示例來進行說明，并用一個評估問題的通用框架和一個用于決定是否使用圖數(shù)據(jù)庫的決策樹（這也是圖的一種形式！）來結(jié)束本節(jié)。

1.2.1　探究疑問

在閱讀互聯(lián)網(wǎng)上關(guān)于圖數(shù)據(jù)庫的大量信息時，你可能會遇到這么一種說法：“一切問題都是圖問題。”我們同意，現(xiàn)實世界很容易用圖術(shù)語來描述，但是說用一種類型的數(shù)據(jù)庫就可以解決所有問題則過于簡單化了。一個問題可以用圖來表示，并不一定意味著圖數(shù)據(jù)庫是解決這個問題的最佳技術(shù)。

我們的流程將從一個簡單的疑問開始：我們要解決什么技術(shù)問題3？回答這個疑問可以提供相關(guān)業(yè)務(wù)問題的關(guān)鍵細節(jié)，這些細節(jié)將決定我們需要存儲的數(shù)據(jù)類型以及如何檢索數(shù)據(jù)。技術(shù)問題可以歸為以下幾類：

3本書中的問題分為兩類：一類是業(yè)務(wù)問題，比如地圖求解；另一類是具體實施中的技術(shù)問題，如搜索、聚合、模式匹配，等等。——譯者注

● 選擇/搜索

● 獲取數(shù)據(jù)相關(guān)性或遞歸數(shù)據(jù)

● 聚合

● 模式匹配

● 中心性、聚集性和影響力

讓我們依次研究每一類，并討論哪些適合使用圖數(shù)據(jù)庫，哪些不適合。

選擇/搜索

以下類型的疑問可歸類為搜索或選擇問題。這些疑問側(cè)重于尋找一組具有共同屬性（如姓名、位置或雇主）的實體。

● 給我X公司所有員工的名單。

● 系統(tǒng)中有哪些人叫John？

● 找到N千米范圍內(nèi)的所有商店。

解答這類疑問不需要數(shù)據(jù)中豐富的關(guān)系。在大多數(shù)數(shù)據(jù)庫中，只需要使用單個篩選條件或者索引就能解答這類疑問。雖然可以使用圖數(shù)據(jù)庫來解答，但這類疑問并不需要圖數(shù)據(jù)庫特有的功能。相反，建議使用諸如PostgreSQL之類的本地數(shù)據(jù)庫或諸如Apache Solr和Elasticsearch之類的搜索技術(shù)。要解答上述疑問，這些數(shù)據(jù)庫或工具要么更成熟（例如RDBMS），要么經(jīng)過更好的優(yōu)化（例如搜索工具）。因為這類問題并沒有利用數(shù)據(jù)中的關(guān)系，所以根據(jù)我們的經(jīng)驗，承擔(dān)圖數(shù)據(jù)庫的額外復(fù)雜性是不值得的。

結(jié)論　對于這類疑問，使用RDBMS或搜索技術(shù)。

 

獲取數(shù)據(jù)相關(guān)性或遞歸數(shù)據(jù)

探究實體之間關(guān)系的疑問增加了數(shù)據(jù)的意義并提供了拓撲價值，為圖數(shù)據(jù)庫提供了一個強大的用例。下面是這類疑問的幾個例子。

● 認識X公司高管最簡單的方法是什么？

● John和Paula是如何認識的？

● X公司與Y公司有什么關(guān)系？

圖數(shù)據(jù)庫比任何其他類型數(shù)據(jù)引擎都能更好地利用這些信息，而且圖數(shù)據(jù)庫查詢語言更適用于推斷數(shù)據(jù)內(nèi)部的關(guān)系。雖然關(guān)系數(shù)據(jù)庫也能解決這類問題，但是這類“朋友的朋友”查詢需要復(fù)雜的SQL并且難以維護，或者需要對多個表之間的遞歸CTE代碼或復(fù)雜連接進行推斷。

結(jié)論　對于這類疑問，使用圖數(shù)據(jù)庫。

 

聚合

數(shù)據(jù)聚合查詢是關(guān)系數(shù)據(jù)庫的一個優(yōu)秀用例。關(guān)系數(shù)據(jù)庫經(jīng)過優(yōu)化，能以最小的開銷快速執(zhí)行復(fù)雜的聚合查詢。下面是這類疑問的幾個例子。

● 系統(tǒng)中有多少家公司？

● 過去一個月里，我的平均日銷售額是多少？

● 系統(tǒng)每天處理多少筆交易？

這些類型的查詢可以在圖數(shù)據(jù)庫中執(zhí)行，但是圖遍歷的本質(zhì)要求接觸更多的數(shù)據(jù)。這會導(dǎo)致更高的查詢延遲和更多的資源消耗。

結(jié)論　對于這類疑問，使用RDBMS。

 

模式匹配

基于實體關(guān)聯(lián)方式的模式匹配是充分利用圖數(shù)據(jù)庫功能的一個主要例子。這類查詢的典型用例包括推薦引擎、欺詐檢測和入侵檢測。下面是這類疑問的幾個例子。

● 系統(tǒng)中誰的資料和我相似？

● 這筆交易是否與其他已知的欺詐交易相似？

● J. Smith和Johan S.是同一個用戶嗎？

模式匹配用例在圖數(shù)據(jù)庫中非常常見，以至于圖查詢語言具有特定的內(nèi)置功能來精確地處理這類查詢。

結(jié)論　對于這類疑問，使用圖數(shù)據(jù)庫。

 

中心性、聚集性和影響力

一個實體相對于另一個實體的影響力或重要性是圖數(shù)據(jù)庫的典型用例。下面是這類疑問的幾個例子。

● 在LinkedIn上與我有聯(lián)系并且最有影響力的人是誰？

● 在我的網(wǎng)絡(luò)中，哪個設(shè)備發(fā)生故障時影響最大？

● 哪些部件可能會同時出現(xiàn)故障？

這類疑問的例子還包括在Twitter網(wǎng)絡(luò)中找到最有影響力的人，識別基礎(chǔ)設(shè)施的關(guān)鍵部分，或者定位數(shù)據(jù)中的實體組。求解這類問題需要考慮實體、實體之間的關(guān)系、事件關(guān)系和鄰近關(guān)系。與模式匹配用例一樣，通常有特定的內(nèi)置圖查詢語言功能來處理這類問題。

結(jié)論　對于這類疑問，使用圖數(shù)據(jù)庫。

1.2.2　如果仍無法確定

要確定圖數(shù)據(jù)庫是否是解決你手頭問題的理想選擇，到目前為止所討論的問題類型提供了重要的第一步。但如果你的問題與這些預(yù)定義類型都不一樣，那又該怎么辦呢？本節(jié)將使用帶有決策框架的“朋友的朋友”問題來幫助你決定一個問題是否適合用圖數(shù)據(jù)庫解決。

下面使用如圖1-11所示的一個小型社交圖來演示，其中Alice、Bob、Ted和Josh是頂點，并由邊進行連接。要解答的疑問是：給定圖中的一個人，這個人關(guān)注的人又關(guān)注了其他人，那么在這些“其他人”中，有誰是第一個人可能也想關(guān)注的？這個疑問和LinkedIn、Twitter或Facebook等網(wǎng)站每天向用戶推薦連接時解答的一樣。首先把它分成四個基本部分。

● 給定圖中的一個人。

● 找出這個人所關(guān)注的人。

● 再找出這些人又關(guān)注了其他哪些人。

● 在這些“其他人”中，誰是第一個人可能也想關(guān)注的？

圖1-11　展示了常見“朋友的朋友”模式的簡單社交圖

以Bob為起點（第一個點）。Bob關(guān)注了Alice（第二個點）。Alice關(guān)注了Ted和Josh（第三個點）。因此，Bob可能想關(guān)注Ted和Josh（終點）。

請看圖1-12中的決策樹，該樹旨在回答“是否應(yīng)該使用圖數(shù)據(jù)庫”的疑問。然后按照該決策樹逐步檢查并分析為什么這些疑問會導(dǎo)致你在工作中使用或不使用圖數(shù)據(jù)庫。從一開始就應(yīng)該注意到，這里關(guān)注的是事務(wù)性用例（如在線事務(wù)處理，簡稱OLTP）。對于分析性用例（例如在線分析處理，簡稱OLAP），決策矩陣可能會有所不同。本書前10章幾乎只關(guān)注事務(wù)處理案例，但最后一章會給出關(guān)于圖處理（或圖分析）的一些指導(dǎo)。

圖1-12　“我應(yīng)該使用圖數(shù)據(jù)庫嗎”決策樹。從最高層開始，最終會回答“是”“否”或者“也許”

我是否像關(guān)心實體本身一樣關(guān)心實體之間的關(guān)系，甚至更關(guān)心后者

這個問題也許是最關(guān)鍵的線索，因此我們把它放在第一位。它揭示了圖數(shù)據(jù)庫一大功能的核心：關(guān)系和實體一樣有意義。如果我們對這個問題的回答是肯定的，那么可能需要一個允許使用復(fù)雜關(guān)系表示形式的數(shù)據(jù)模型，因此使用圖數(shù)據(jù)庫是這個業(yè)務(wù)問題的絕佳選擇。但如果答案是否定的，那么另一個類別的數(shù)據(jù)引擎也許會是更好的選擇。

就“朋友的朋友”問題而言，答案是肯定的。在第一個基本部分（給定圖中的一個人）之后，每部分都需要使用人與人之間的關(guān)系來求解。
 

我的SQL查詢是否需要在同一個表上執(zhí)行多個join，或者需要遞歸的CTE

雖然SQL查詢中包含大量join可能表明圖數(shù)據(jù)庫是一個很好的選擇，但并不能確定。SQL查詢中的大量join通常是數(shù)據(jù)模型規(guī)范化的良好標志。但是，當(dāng)這些join并非用于檢索引用數(shù)據(jù)（如關(guān)系數(shù)據(jù)庫中的第三個范式所做的那樣），而是用于將記錄項鏈接在一起（就像父子關(guān)系那樣）時，就可能需要考慮使用圖數(shù)據(jù)庫了。此外，當(dāng)我們不知道要執(zhí)行的join數(shù)量時，使用圖數(shù)據(jù)庫的遞歸查詢模式更好。

以“朋友的朋友”為例，假設(shè)我們要解答“從Bob到Ted有哪些連接”的疑問。在關(guān)系數(shù)據(jù)庫中執(zhí)行該查詢需要未知數(shù)量的join，并且可能無法完成（即表明兩者之間不存在路徑）。但是，圖數(shù)據(jù)庫可以高效地對諸如此類的無邊界分層數(shù)據(jù)進行遞歸。如果遞歸方法有助于解決問題，則通常最好使用圖數(shù)據(jù)庫。
 

我的數(shù)據(jù)結(jié)構(gòu)是否會不斷變化

我們不會把圖數(shù)據(jù)庫稱為與數(shù)據(jù)模式無關(guān)的（schemaless），該術(shù)語表示數(shù)據(jù)庫引擎不會對寫操作強制執(zhí)行數(shù)據(jù)結(jié)構(gòu)檢查。我們知道有幾個圖數(shù)據(jù)庫產(chǎn)品確實會強制執(zhí)行數(shù)據(jù)結(jié)構(gòu)檢查，但是你可以把圖數(shù)據(jù)庫設(shè)計得能夠容忍不斷發(fā)展變化的數(shù)據(jù)。另外，關(guān)系數(shù)據(jù)庫因其對數(shù)據(jù)結(jié)構(gòu)的嚴格性和更改數(shù)據(jù)結(jié)構(gòu)時的復(fù)雜性而聞名。

如果你的問題需要接收具有不同數(shù)據(jù)結(jié)構(gòu)的數(shù)據(jù)（例如依賴關(guān)系管理），那么可能值得研究使用圖數(shù)據(jù)庫來解決問題。數(shù)據(jù)結(jié)構(gòu)的靈活性不能作為選擇圖數(shù)據(jù)庫的充分理由，但與其他功能相結(jié)合，很可能足以使你轉(zhuǎn)而使用圖數(shù)據(jù)庫。
 

我的業(yè)務(wù)領(lǐng)域是否天生適合使用圖數(shù)據(jù)庫

如果要進行諸如路由、依賴關(guān)系管理、社交網(wǎng)絡(luò)分析或聚類分析等操作，那么你的問題就與高度互聯(lián)數(shù)據(jù)有關(guān)，你的業(yè)務(wù)領(lǐng)域也就可能非常適合使用圖數(shù)據(jù)庫。提醒一下：即使業(yè)務(wù)領(lǐng)域模型天生適合使用圖數(shù)據(jù)庫，但是如果你的具體技術(shù)問題并不依賴于圖中的關(guān)系來求解，那么也應(yīng)該考慮其他選擇。

實際上，早在2014年，我們對圖數(shù)據(jù)庫的最初研究就揭示了客戶數(shù)據(jù)為何非常自然地適合使用圖數(shù)據(jù)庫4。我們甚至嘗試了三個不同的圖數(shù)據(jù)庫產(chǎn)品。做出來的模型具有內(nèi)置的繼承功能、多跳遍歷和對依賴關(guān)系分析的自然要求。客戶應(yīng)用程序中的兩個主要數(shù)據(jù)結(jié)構(gòu)甚至被稱為組件（頂點的別名）和關(guān)系（邊的別名）。它應(yīng)該使用圖數(shù)據(jù)庫而不是關(guān)系數(shù)據(jù)庫構(gòu)建，這一點對于所有粗略瀏覽過數(shù)據(jù)和業(yè)務(wù)領(lǐng)域的人來說都是顯而易見的。

然而，該特定客戶的正確解決方案并不是使用我們評估過的三個圖數(shù)據(jù)庫引擎，而是使用它們的關(guān)系數(shù)據(jù)庫（或者說，以與其主要訪問模式一致的方式來使用它）。然后，我們將局部優(yōu)化過的關(guān)系投影（基本上是舊模型的完整副本）添加到為執(zhí)行查詢而設(shè)計的關(guān)系數(shù)據(jù)庫架構(gòu)中。這個模式有時被稱為命令查詢責(zé)任分離（CQRS）模式。通過這個新的“快速讀取”模型，一些最苛刻查詢的性能提高了100倍。

起初，我們都為圖數(shù)據(jù)庫并沒有提供必要的性能提升而感到震驚，因為按照業(yè)務(wù)領(lǐng)域數(shù)據(jù)建模自然而然地適合使用圖數(shù)據(jù)庫。然后，我們更加仔細地研究了用于評估數(shù)據(jù)庫性能的五個查詢。除了繼承建模之外，所有查詢都不需要圖式訪問模式。因為圖不是必需的，所以我們使用激進的反規(guī)范化來處理繼承用例。實際上，所需的訪問模式非常適合關(guān)系數(shù)據(jù)庫。因此，當(dāng)對數(shù)據(jù)進行建模并利用RDBMS查詢優(yōu)化器的優(yōu)勢時，性能得到了顯著提高。

回到前面的圖數(shù)據(jù)庫決策樹（見圖1-12），如果其中一個或多個問題的回答為“是”，則可能適合使用圖數(shù)據(jù)庫。如果你仍然不確定（仍然覺得使用圖數(shù)據(jù)庫有風(fēng)險），那么可以先花兩天到兩周時間做一個小項目試試，將圖數(shù)據(jù)庫作為解決方案的一部分進行評估。另外，并不一定全部使用圖數(shù)據(jù)庫，也并不一定全部不使用圖數(shù)據(jù)庫。不要害怕嘗試用圖數(shù)據(jù)庫來解決問題的一部分。使用圖數(shù)據(jù)庫的多模型方法（即混合使用關(guān)系數(shù)據(jù)庫和圖數(shù)據(jù)庫）很常見，并且根據(jù)我們的經(jīng)驗而言，往往非常成功。

正如本章開頭提到的那樣，關(guān)系數(shù)據(jù)庫能夠很好地解決100個應(yīng)用程序疑問中的88個，因此可以放心使用。剩下的12個疑問實際上是你可能想開始實驗圖數(shù)據(jù)庫的地方。本書的剩余部分（從第2章的數(shù)據(jù)建模開始）將介紹使用圖數(shù)據(jù)庫構(gòu)建軟件的方法和原因。

42016年7月，在西雅圖GraphDay舉辦的“Graph DB Shootout 2.0”研討會上，我們利用公共數(shù)據(jù)集重新進行了分析。

1.3　小結(jié)

● 圖數(shù)據(jù)庫的基礎(chǔ)是離散數(shù)學(xué)的圖論部分，后者已經(jīng)有數(shù)百年歷史了。這意味著數(shù)學(xué)家們花費了幾個世紀的時間來創(chuàng)建術(shù)語，但并非所有術(shù)語都有用，也并非所有術(shù)語都與使用圖數(shù)據(jù)庫構(gòu)建軟件有關(guān)。

● 圖由頂點（也稱為節(jié)點或?qū)嶓w）和邊（也稱為關(guān)系、鏈接或連接）組成。邊在頂點相交。

● 數(shù)據(jù)庫的五種常見類型是鍵值數(shù)據(jù)庫、列存儲數(shù)據(jù)庫、文檔數(shù)據(jù)庫、關(guān)系數(shù)據(jù)庫和圖數(shù)據(jù)庫。在這五種數(shù)據(jù)庫中，只有關(guān)系數(shù)據(jù)庫和圖數(shù)據(jù)庫能夠?qū)θ我鈴?fù)雜程度的關(guān)系進行建模。

● 圖數(shù)據(jù)庫將關(guān)系設(shè)計成“一等公民”，這使構(gòu)建依賴于這些關(guān)系的軟件變得更加容易。當(dāng)要解答嚴重依賴于數(shù)據(jù)之間關(guān)系的疑問時，圖數(shù)據(jù)庫往往比其他類型的數(shù)據(jù)庫表現(xiàn)得更好。

● 對于需要諸如遞歸查詢、返回不同結(jié)果類型或返回事物之間路徑等特性的用例，使用圖數(shù)據(jù)庫更容易編碼，并且性能更好。

● 由于圖數(shù)據(jù)庫的強大功能和靈活性，互聯(lián)網(wǎng)上有很多圖用例可參考，其中有好有壞。判斷一個用例是好還是壞的最重要因素是對要解答的疑問有深入的了解。