查询语言中的求值顺序与非终止性
本文探讨了Datalog等查询语言中因求值顺序导致的非终止性问题。作者分析了不同求值策略（如自底向上与自顶向下求值）对查询终止性的影响，并讨论了如何通过优化求值顺序来避免无限循环。文章还对比了Datalog与SQL等语言在非终止性处理上的异同，为查询语言的实现和优化提供了理论指导。
背景速读
- 本文讨论的是**查询语言（query languages）**中的求值顺序与非终止（nontermination）问题，核心对比对象是 **Datalog** 和 **SQL**（及递归 CTE，即公用表表达式）。Datalog 是一种声明式逻辑编程语言，常用于数据库和知识图谱的推理查询；SQL 的递归 CTE 是 SQL 标准中支持递归查询的机制。
- 关键人物：作者 **Michael Arntzenius**（网名 rntz），是知名 Datalog 方言 **Datafun** 的设计者之一，长期研究声明式语言、逻辑编程与数据库理论。他的观点在学术圈有相当分量。
- 为什么重要：Datalog 传统上保证终止（termination），但作者发现了一个反例，说明其保证比人们通常认为的更脆弱；SQL 的递归 CTE 则因实现差异存在行为不一致问题。这对数据库系统设计者、编程语言实现者以及依赖递归查询的数据工程师都有直接影响。
- 背景：Datalog 社区长期以来将“保证终止”作为其相对于 SQL 递归 CTE 的一项关键优势；本文以具体案例挑战了这一共识。