保罗·拉姆齐：凯文·贝肯的六度分离——Postgres风格
内容提要
在1990年代初期，两名大学生发明了一款名为“六度分离”的游戏。该游戏的概念是演员凯文·贝肯可以通过不超过六个步骤与任何其他演员建立联系。为什么是凯文·贝肯？这纯属偶然，但这两名学生注意到贝肯在一次采访中说“他与好莱坞的每个人或者与他们合作过的人合作过”，并将这句话视为挑战。从某个演员到凯文·贝肯的步骤数被称为“贝肯数”。原始的“六度分离”游戏的挑战是仅凭头脑中的知识将两名演员联系起来。现代我们不需要聪明，可以通过结合数据和算法来解决贝肯数问题。数据部分相对简单，互联网电影数据库（IMDB）允许直接下载所需信息。具体来说，我们需要的是演员名称和职位的name.basics.tsv.gz文件，电影名称和日期的title.basics.tsv.gz文件，以及演员和电影之间关系的title.principals.tsv.gz文件。为了使表格更小且函数更快，ETL过程中对原始文件进行了简化，结果是三个较小的表。演员表有371,557行，电影表有678,204行，电影演员表有1,866,533行。计算任何给定演员的贝肯数所需的算法是什么？演员通过电影连接在一起。演员和电影共同形成一个图！演员是图的节点，电影是图的边。幸运的是，PostgreSQL已经有
延伸解读
从游戏到图论：贝肯数问题的本质
文章将贝肯数问题转化为图论中的最短路径问题：演员是节点，电影是边。这种建模方式使得原本依赖记忆的游戏可以通过算法自动求解。读者可以理解，许多看似复杂的关联问题，一旦抽象为图结构，就能利用现有算法高效解决。
pgRouting与递归CTE：两种求解路径的权衡
文章对比了pgRouting和递归CTE两种方法。pgRouting适合动态图，但每次查询需重新构建图，耗时约5秒；递归CTE虽编写复杂，但针对静态图和小步数场景，运行仅需几百毫秒。这提示读者，技术选型需结合数据特性和性能需求，而非盲目选择通用工具。
数据预处理与规模：ETL如何影响查询效率
文章通过ETL将原始IMDB数据精简为三个表：演员表37万行、电影表67万行、关系表186万行。自连接后生成的actor_graph包含约1100万条边。这种预处理显著减小了数据规模，为后续快速查询奠定了基础。读者可借鉴这种“先精简再计算”的思路。
实际应用与局限：贝肯数查询的现状
文章提供了PL/PgSQL函数封装递归CTE查询，并发现目前最高贝肯数为3（演员Gates McFadden）。这暗示在IMDB数据中，大多数演员与凯文·贝肯的连接非常紧密。但文章也指出，递归CTE的SQL编写复杂，且仅适用于静态图和小步数场景，动态更新数据时可能需另寻方案。
Q&A
六度分离游戏的起源是什么？
六度分离游戏在1990年代初期由两名大学生发明，基于演员凯文·贝肯可以通过不超过六个步骤与任何其他演员建立联系的概念。
贝肯数是什么？
贝肯数是指从某个演员到凯文·贝肯所需的步骤数。
如何计算贝肯数？
计算贝肯数的算法是通过将演员和电影视为图的节点和边，利用PostgreSQL的图形求解器pgRouting或递归CTE来实现。
IMDB提供了哪些数据来支持六度分离游戏？
IMDB允许下载演员名称、电影名称及演员与电影之间关系的数据文件，包括name.basics.tsv.gz、title.basics.tsv.gz和title.principals.tsv.gz。
pgRouting和递归CTE在计算贝肯数时有什么区别？
pgRouting适合动态图的求解，而递归CTE适合静态图，且递归CTE在处理小规模图时运行速度更快。
目前找到的最高贝肯数是多少？
目前找到的最高贝肯数是3，针对演员Gates McFadden。
