保罗·拉姆齐：凯文·贝肯的六度分离——Postgres风格
内容提要
在1990年代初期，两名大学生发明了一款名为“六度分离”的游戏。该游戏的概念是演员凯文·贝肯可以通过不超过六个步骤与任何其他演员建立联系。为什么是凯文·贝肯？这纯属偶然，但这两名学生注意到贝肯在一次采访中说“他与好莱坞的每个人或者与他们合作过的人合作过”，并将这句话视为挑战。从某个演员到凯文·贝肯的步骤数被称为“贝肯数”。原始的“六度分离”游戏的挑战是仅凭头脑中的知识将两名演员联系起来。现代我们不需要聪明，可以通过结合数据和算法来解决贝肯数问题。数据部分相对简单，互联网电影数据库（IMDB）允许直接下载所需信息。具体来说，我们需要的是演员名称和职位的name.basics.tsv.gz文件，电影名称和日期的title.basics.tsv.gz文件，以及演员和电影之间关系的title.principals.tsv.gz文件。为了使表格更小且函数更快，ETL过程中对原始文件进行了简化，结果是三个较小的表。演员表有371,557行，电影表有678,204行，电影演员表有1,866,533行。计算任何给定演员的贝肯数所需的算法是什么？演员通过电影连接在一起。演员和电影共同形成一个图！演员是图的节点，电影是图的边。幸运的是，PostgreSQL已经有
关键要点
- 在1990年代初期，两名大学生发明了名为“六度分离”的游戏。
- 游戏的概念是演员凯文·贝肯可以通过不超过六个步骤与任何其他演员建立联系。
- 贝肯数是指从某个演员到凯文·贝肯所需的步骤数。
- 原始游戏的挑战是仅凭头脑中的知识将两名演员联系起来。
- 现代可以通过结合数据和算法来解决贝肯数问题。
- IMDB允许直接下载所需的信息，包括演员名称、电影名称和演员与电影之间的关系。
- ETL过程中对原始文件进行了简化，结果是三个较小的表。
- 计算贝肯数的算法是通过电影将演员连接在一起，形成一个图。
- PostgreSQL提供了图形求解器pgRouting，可以用于计算贝肯数。
- 可以使用递归CTE在PostgreSQL中直接处理问题。
- 通过自连接movie_actors表，形成一个包含演员配对的actor_graph表。
- pgRouting适合动态图的求解，而递归CTE适合静态图，且运行速度更快。
- 提供了一个PL/PgSQL函数来简化贝肯数的查询过程。
- 目前找到的最高贝肯数是3，针对演员Gates McFadden。
延伸问答
六度分离游戏的起源是什么？
六度分离游戏在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。
