查询语言中的求值顺序与非终止性

- **Datalog** 是一种声明式逻辑编程语言，常用于数据库查询和知识推理。与 SQL 不同，Datalog 基于逻辑规则（类似“如果 A 且 B，则 C”），理论上保证查询总会终止。 - **非终止（nontermination）** 指程序运行陷入无限循环、永远不返回结果。在 Datalog 中，递归规则（规则引用自身）若写法不当，可能导致查询无限执行。 - **求值顺序（evaluation order）** 是编程语言执行表达式的次序。在 Datalog 中，不同的求值策略（如“先广度优先”还是“先深度优先”）会影响同一段代码能否正常终止。 - 本文讨论的是：Datalog 虽然以“保证终止”著称，但在实际实现中，求值顺序的选择会让某些合法查询无法终止。这揭示了声明式语言在理论和工程之间的差距，对数据库系统和逻辑编程的设计者有意义。