SQL 查询优化-自然连接与差异的分配律

Question

我对以下等价是否成立感兴趣：

NaturalJoin (R,S-T) equivalence Difference(NaturalJoin(R,S),NaturalJoin(R,T))

如果是这样，你能给出等价的理由吗？如果您知道从运行时的角度来看哪种查询可能更优化，那将非常有帮助。

P.S。我想使用 LATEX，但对 Whosebug 还很陌生，我似乎无法理解如何在这里使用它——math.stackexchange 中的标记只是 \[...\].

Answer 1

NaturalJoin (R,S-T) equivalence Difference(NaturalJoin(R,S),NaturalJoin(R,T))

处理此问题的一般方法是用它们的定义替换运算符调用。

这是一个大纲，假设关系表达式和它们所包含的元组之间存在某些等价性。人们实际上需要使用等价来证明一个人的查询 return 一个人被要求获得的元组，但这通常不会被解释。（相反，人们通过大量示例和挥手学习。）

S & T 具有相同的属性集。
X 包含 (...) 行，其中 X(...)，即 (...) IN X.
NATURALJOIN(X,Y) 包含 X(...) AND Y(...).
的行 DIFFERENCE(X,Y) 包含 X(...) AND NOT Y(...) 所在的行。

左侧包含行，其中：

R(...) AND (S(...) AND NOT T(...))
R(...) AND S(...) AND NOT T(...)

右侧包含行，其中：

(R(...) AND S(...)) AND NOT (R(...) AND T(...))
(R(...) AND S(...)) AND (NOT R(...) OR NOT T(...))
((R(...) AND S(...)) AND NOT R(...)) OR ((R(...) AND S(...)) AND NOT T(...))
(R(...) AND S(...) AND NOT R(...)) OR (R(...) AND S(...) AND NOT T(...))
R(...) AND S(...) AND NOT T(...)

所以它们是等价的。

您可以通过将 X(...) 替换为 x IN X 并使用适当的量化（FORALL & FORSOME/EXISTS）将其转换为证明并设置理解 ({variable|wff}).

在推理中重新使用自然连接 & SQL 参见及其链接。

And if you know what query could be more optimal in a sense of runtime, that would be really helpful.

这取决于您的 DMBS 及其查询 implementation/optimization。没有执行模型、cost/benefit 函数和该函数的输入参数就没有 "optimal"。此外 "optimal" 是混乱的——关系和物理 DDL、数据库内容和统计信息、查询 DML、查询和更新模式以及 DBMS 实现中的微小变化可以给出完全不同的权衡。

SQL 查询优化-自然连接与差异的分配律

SQL Query optimization - distributive law of natural join and difference

sql

relational-algebra

query-optimization