转换关系表达式

引言

众所周知，在现代的数据库世界中，关系表达式通常用于描述如何从不同的表集合中有效收集、过滤或组合数据。这些表达式最终是通过一组称为“关系代数”的规则来构建的。虽然对于数据库系统来说，关系表达式精确且有用，但对于普通用户或初学者来说，它们通常显得过于技术化或复杂。

尽管如此，在数据库管理系统中转换关系表达式意味着在不改变其含义的情况下，改变所有这些表达式的结构和顺序。这样做有很多原因，有时是为了让查询运行得更快，有时是为了让查询更容易阅读或理解，并且通常是为了准备由数据库引擎有效执行。例如，如果一个查询的写法很复杂，它仍然可以得到正确的结果，但可能会花费更多的时间或使用更多的系统资源。因此，通过重新排序或简化表达式的某些部分，可以更有效地获得相同的结果。这类似于用不同的方法解决一个数学问题，但得到相同的答案。

此外，所有这些转换对于数据库的有效优化尤其重要。当系统必须处理大量数据时，编写节省时间和资源的查询就变得必不可少。尽管转换后的表达式可能看起来不同，但它仍然会产生与原始表达式相同的输出。

在数据库管理系统（DBMS）中，关系代数是什么意思？

在数据库管理系统中，关系代数就像一种专门用于与数据库通信的特殊语言。它为我们提供了一种结构化的方法来提问并从海量数据集合中获取特定信息。就像我们使用数学来解决问题一样，关系代数使用一系列操作，包括选择特定行、提取特定列、合并不同表或过滤结果，来分解和解决与数据相关的问题。这些操作包括选择、投影、并集、交集、差集和连接，每种操作都有助于检索所需的数据。

此外，关系代数构成了当今广泛用于与数据库交互的SQL（结构化查询语言）的骨干。当我们编写 SQL 查询时，数据库系统通常会在处理之前将其内部转换为关系代数。这就是为什么理解关系代数如此有用的原因。它帮助我们了解 SQL 在后台是如何工作的，以及如何有效地编写更好、更快的查询。

实施

优化器的第一步是实现与给定表达式逻辑等价的表达式。为了实现这一步，我们使用等价规则，该规则描述了将生成的表达式转换为逻辑等价表达式的方法。

尽管可以通过多种方式表达查询，并且成本不同。但为了高效地表达查询，我们将学习创建给定表达式的替代等价表达式，而不是直接处理给定表达式。如果两个关系代数表达式在每个合法的数据库实例上产生相同的元组集，则它们是等价的。**合法数据库实例**指的是满足数据库模式中指定的所有完整性约束的数据库系统。然而，两个表达式生成的元组的顺序可能不同，但只要它们产生相同的元组集，就被认为是等价的。

等价规则

等价规则指出，两种形式的表达式是相同或等价的，因为这两种表达式在任何合法的数据库实例上都会产生相同的输出。这意味着我们可以用第二种形式的表达式替换第一种形式的表达式，或者用第一种形式的表达式替换第二种形式的表达式。因此，查询执行计划的优化器使用这种等价规则或方法将表达式转换为逻辑等价的表达式。

优化器使用各种关系代数表达式的等价规则来转换关系表达式。为了描述每个规则，我们将使用以下符号：

θ, θ₁, θ₂ …：用于表示谓词。

L₁, L₂, L₃ …：用于表示属性列表。

E, E₁, E₂ ….：表示关系代数表达式。

让我们讨论一些等价规则

规则 1：σ 的级联

此规则指出，将合取选择操作分解为一系列单独的选择操作。这种转换称为 **σ 的级联**。

σ_{θ1 ᴧ θ 2} (E) = σ_θ1 (σ_θ2 (E))

规则 2：交换律

a) 此规则指出选择操作是可交换的。

σ_θ1 (σ_θ2 (E)) = σ _θ2 (σ_θ1 (E))

b) Theta Join (θ) 是可交换的。

E₁ ⋈ _θ E ₂ = E ₂ ⋈ _θ E ₁ (θ 在连接符号的下标处)

然而，在 theta join 的情况下，如果考虑属性的顺序，则等价规则不适用。自然连接是 Theta join 的特例，自然连接也是可交换的。

然而，在 theta join 的情况下，如果考虑属性的顺序，则等价规则不适用。自然连接是 Theta join 的特例，自然连接也是可交换的。

规则 3：∏ 的级联

此规则指出，我们只需要投影操作序列中的最终操作，而其他操作将被省略。这种转换称为 **∏ 的级联**。

∏L1 (∏L2 (. . . (∏Ln (E)) . . . )) = ∏L1 (E)

规则 4：我们可以将选择与笛卡尔积以及 theta join 结合起来

1. σ_θ (E₁ x E₂) = E_1θ ⋈ E₂
2. σ_θ1 (E₁ ⋈ _θ2 E₂) = E₁ ⋈ _θ1ᴧθ2 E₂

规则 5：结合律

a) 此规则指出自然连接操作是可结合的。

(E1 ⋈ E2) ⋈ E3 = E1 ⋈ (E2 ⋈ E3)

b) Theta join 对于以下表达式是可结合的

(E₁ ⋈ _θ1 E₂) ⋈ _θ2ᴧθ3 E₃ = E₁ ⋈ _θ1ᴧθ3 (E₂ ⋈ _θ2 E₃)

在 theta 结合律中，θ2 只涉及 E2 和 E3 的属性。可能存在空条件的情况，因此可以得出笛卡尔积也是可结合的。

注意：join 操作的结合律和交换律对于查询优化中的 join 重新排序至关重要。

规则 6：选择操作分布到 Theta Join 上。

在以下两种条件下，选择操作会分布到 theta-join 操作上：

a) 当选择条件 θ₀ 中的所有属性仅包含正在连接的一个表达式的属性时。

σ_θ0 (E₁ ⋈ _θ E₂) = (σ_θ0 (E₁)) ⋈ _θ E₂

b) 当选择条件 θ₁ 只包含 E₁ 的属性，而 θ₂ 只包含 E₂ 的属性时。

σ_{θ1ꓥ θ2} (E₁ ⋈ _θ E₂) = (σ_θ1 (E₁)) ⋈ _θ ((σ_θ2 (E₂))

规则 7：投影操作分布到 theta join 上。

在以下两种条件下，选择操作会分布到 theta-join 操作上：

a) 假设连接条件 θ 只包含 E₁ 和 E₂ 的 L₁ υ L₂ 属性。那么，我们得到以下表达式：

∏_L1υL2 (E₁ ⋈ _θ E₂) = (∏_L1 (E₁)) ⋈ _θ (∏_L2 (E₂))

b) 假设一个连接为 E₁ ⋈ E₂。表达式 E₁ 和 E₂ 分别具有属性集 L₁ 和 L₂。假设有两个属性 L₃ 和 L₄，其中 L₃ 是 E₁ 表达式的属性，参与 θ 连接条件但不在 L₁ υ L₂ 中。类似地，L₄ 是 E₂ 表达式的属性，仅参与 θ 连接条件但不在 L₁ υ L₂ 属性中。因此，我们得到以下表达式：

∏_L1υL2 (E₁ ⋈ _θ E₂) = ∏_L1υL2 ((∏_L1υL3 (E₁)) ⋈ _θ ((∏_L2υL4 (E₂)))

规则 8：并集和交集集合运算是可交换的。

E₁ υ E₂ = E₂ υ E₁

E₁ ꓵ E₂ = E₂ ꓵ E₁

然而，集合差集运算不是可交换的。

规则 9：并集和交集集合运算是可结合的。

(E₁ υ E₂) υ E₃ = E₁ υ (E₂ υ E₃)

(E₁ ꓵ E₂) ꓵ E₃ = E₁ ꓵ (E₂ ꓵ E₃)

规则 10：选择操作分布到交集、并集和差集运算上。

以下表达式显示了分布在差集运算上的操作。

σ_p (E₁ − E₂) = σ_p(E₁) − σ_p(E₂)

我们可以类似地将选择操作分布到 υ 和 ꓵ 上，用 - 替换。此外，我们得到

σ_p (E₁ − E₂) = σ_p(E₁) −E₂

规则 11：投影操作分布到并集操作上。

此规则指出，我们可以将投影操作分布到给定表达式的并集操作上。

∏_L (E₁ υ E₂) = (∏_L (E₁)) υ (∏_L (E₂))

除了这些讨论过的等价规则外，还有许多其他等价规则。

常见问题解答/FAQ

在处理关系表达式转换时，需要记住的几个常见问题如下：

问题 1：转换后出现不同结果的风险吗？

答案：不，如果转换正确的话。转换关系表达式的主要原则是必须保留查询的原始含义。这意味着即使在更改操作的顺序或结构后，最终结果也应与原始查询相同。这就是为什么 DBMS 依赖于既定的关系代数规则来确保任何转换都是逻辑上可靠且有效的。

问题 2：列出在关系表达式转换中常用的各种技术？

答案：常用的几种技术如下：

• 下推选择：尽早应用条件来减小中间结果集的大小。
• 合并投影：将多个 投影操作合并为一个。
• 重新排序连接：更改连接的顺序，以使其在结果不变的情况下计算速度更快。
• 使用等价规则：应用诸如结合律或交换律之类的数学规则来重构表达式。这些技术有助于简化表达式并提高执行时间。

问题 3：转换在优化中起什么作用？

答案：转换在查询优化中起着重要作用。它还可以提高性能，并确保即使是复杂的查询也不会减慢系统的速度。因此，学习所有这些转换技术和规则不仅仅是有用的，对于任何处理数据并致力于构建高效、高性能应用程序的人来说，都是必不可少的。

结论

关系表达式的转换被认为是现代数据库系统管理和优化查询处理方式的基本组成部分。因此，通过在不改变最终结果的情况下改变所有选定表达式的结构，数据库系统可以更容易、更高效地执行操作。这些转换通常使系统更容易最小化资源使用，如内存和磁盘访问，尤其是在处理大量数据时。主要目标不是改变返回的数据，而是有效地检索数据的方式。

理解和应用等价规则，例如选择各种可用的下推、连接重新排序或合并投影，可以确保数据库始终找到获取所需结果的最短且成本效益最高路径。这些技术还可以帮助开发人员和数据库管理员编写更好的查询，并了解系统在内部如何解释它们。