知识卡片

同一可变长度路径查询在图模型与关系模型下的复杂度悬殊

普通读书笔记卡

内容

[[属性图模型用顶点与边的两张表建模任意关联数据]]可以直接用两张关系表实现,理论上 也能用SQL来查询它,但这样做会暴露出一个关系模型天生不擅长处理的场景:查询前需要 遍历的连接数量事先不确定。以”查找所有从美国移民到欧洲的人”为例:一个人的居住地可能 直接是国家,也可能是一个隔了好几层行政区划(街道→城市→州→国家)的地方,需要沿着 “属于”关系走零次或多次才能到达”欧洲”或”美国”这个顶点——连接的次数本身是可变的。用 Cypher表达这个”沿边走零次或多次”的语义只需要一个简洁的记号(-[:WITHIN*0..]->, 很像正则表达式里的*),整条查询语句只需要4行;而在SQL里要表达同样的语义,需要用 WITH RECURSIVE递归公用表表达式手工构造”in_usa”“in_europe”等中间集合,逐层沿着 WITHIN边递归查找,最终写出的等价查询长达29行,语法笨拙得多。这个具体的行数对比 (4行 vs 29行)不是为了说明Cypher”更好”,而是在提醒一个更根本的道理:不同的数据 模型是为不同的应用场景而设计的,同一个查询在契合自己数据结构的模型下可以轻松表达, 硬塞进不契合的模型里则会异常笨重——选择适合应用数据关联特征的数据模型,比选择某个 “更流行”或”更熟悉”的模型重要得多。

参考来源

- 位置:《数据密集型应用系统设计》第二章《数据模型与查询语言》"SQL中的图查询" (源文件:_epub-src/ch2_split_003.html) - 结论依据:原文说明图查询中需要遍历的连接数量事先不确定,Cypher用`WITHIN*0..` 简洁表达可变长度路径遍历,同样的查询在SQL中需要用递归公用表表达式写成29行, 而Cypher只需4行,并总结"不同的数据模型是为不同的应用场景而设计的",直接支撑 本卡片结论。 - 原始内容:在关系数据库中,你通常会事先知道在查询中需要哪些连接。在图查询中, 你可能需要在找到待查找的顶点之前,遍历可变数量的边……同一个查询,用某一个查询 语言可以写成4行,而用另一个查询语言需要29行,这恰恰说明了不同的数据模型是为 不同的应用场景而设计的。选择适合应用程序的数据模型非常重要。