SQL与TSQL的图灵完备性

SQL及其变体TSQL是否图灵完备一直备受争议。虽然SQL主要被认为是一种数据查询语言，但一些人认为其表达能力超越了这个有限的范围。

SQL的图灵完备性

Andrew Gierth在一组幻灯片中，令人信服地证明了SQL即使没有像PL/SQL或PSM这样的脚本扩展，也能实现图灵完备性。他通过使用公共表表达式（CTE）和窗口函数在SQL中构建循环标记系统来证明这一点。

CTE允许用户创建可以自我引用的命名子表达式，从而实现递归问题求解。此功能为通常与SQL无关的计算复杂性打开了可能性。

意义和影响

必须注意的是，SQL的图灵完备性并非有意设计的。引入CTE是为了增强语言的声明性能力，而不是将其转变为类似于C 的通用编程语言。

这一认识突出了看似简单的结构中可能产生的深远计算能力。SQL通过CTE实现的递归能力，释放了类似于图灵完备系统的表达能力。

实际应用

虽然用SQL编写编译器可能不切实际，但其图灵完备性的理论意义值得关注。这表明SQL可能比以前认为的能够解决更广泛的计算问题。从曼德布罗特集可视化到复杂的数学模拟，基于SQL的解决方案的可能性超越了传统的数据查询和操作。