sql - 如何证明某事增加了关系表达能力？

Question

我如何证明某事增加了关系表达能力？例如，我遇到了一个问题，我需要说明向 SQL 的 select-project-join 查询添加某些功能是否会增加表达能力。我是否举了一个例子并表明它是不可表达的？

Answer 1

首先，您必须确定两个符号表示的是什么。（即他们在表达什么，即表达，即表示。）否则，这个问题没有多大意义。

例如：只要两个符号的表达式集是可数无限的，它们就可以以 1:1 的对应关系设置。因此，一个集合的表达式可以表达另一个集合的相应表达式的任何东西都可以被分配来表达。因此，它们在这种微不足道的意义上同样具有表现力。（从本质上讲，哪种意义可以同等地表达彼此的表达。）

在被告知我们的两个符号所表达的内容时，我们通常会得到每个符号：

• 一些原始表达
• 生成表达式的一些规则
• 一些原始的东西
• 生成事物的一些规则
• 从表达式到事物的映射

有时映射是从终结表达式到原始事物，从非终结表达式到结构化事物，但不必如此。

表明一种符号更具表达性（无论它们表达什么）就是表明一种符号可以表达另一种可以表达的所有东西，加上一些它不能表达的东西。

“事物”实际上是其中一个符号的表达式是可以的，从它的每个表达式到它自己都有一个平凡的映射，而另一个（表达性较差的）符号只映射到它的适当子集（更多富有表现力）。（这里的可表达性能够与上面的例子不同的原因是，这里两个符号的每个表达式都被定义为表达与那个例子不同的东西。）

请参阅Alice 书或Maier 书中的讨论。这些处理数据库查询语言。例如，关系代数、关系元组演算和关系域演算的表达等价版本，以及其他语言，如谓词逻辑和 Datalog 版本。