是否可以解除所有相关 SQL 子查询的关联？

Question

（注意：不是 this question 的重复，因为那个问题有一个特定的查询。这更多是从一般的理论角度来看。）

我在大学里学的是数据库，学过SQL数据库，为了执行一个查询，先把它翻译成relational algebra，以便形成一个如何查询的计划执行它。关系代数可以很容易地表示不相关的 SQL 子查询，然后我们可以根据需要将其组合成连接或集合操作。例如，我们可以很容易地表达

SELECT y FROM Table WHERE y NOT IN (SELECT x FROM AnotherTable);

作为两个查询之间的集合差异。

然而，据我所知，关系代数没有提供任何机制来表达 SQL 的相关子查询概念，或从父查询中捕获列的查询，因此必须多次执行，例如下面这个例子：

SELECT employee_number, name
  FROM employees AS emp
  WHERE salary > (
    SELECT AVG(salary)
      FROM employees
      WHERE department = emp.department);

(在这个例子中，外层WHERE子句中的子查询与员工的部门相关，这意味着子查询必须对每个员工运行一次，以便按部门过滤结果.)

与许多其他相关子查询一样，可以通过使用连接和单个聚合查询来解除此子查询的相关性，这将使查询可以在 RA 中完美表达，并使子查询成为运行只有一次：

SELECT emp.employee_number, emp.name
  FROM employees AS emp
  JOIN (
    SELECT department AS department, AVG(salary) AS avg_salary
    FROM employees
    GROUP BY department) AS salaries
    ON emp.department = salaries.department
  WHERE emp.salary > salaries.avg_salary;

但是，是否可以将所有相关子查询表示为去相关子查询，以便将它们表示为关系代数，或者是否有一些相关子查询必须表示为这样的？换句话说，SQL 相关只是一个方便的功能，不会增加任何 SQL 的表达能力，或者 RA 只是一个实施指南，SQL 更具表现力，因为这个功能？

如果是前者，这个proof/algorithm是什么？如果是后者，是否有一种普遍接受的RA形式直接表达相关性？

Answer 1

我想在这里指出，您可能误解了子查询的确切时间 "correlated"。

以我的理解，子查询是 "correlated" 当且仅当它引用包含（/外部）查询的列时。您的 SELECT AVG(...) 查询不符合该描述。这就是所谓的标量子查询。因为它除了根据 table 计算标量值外什么都不做。而且还可以"stand on its own".

至于实际问题，确定 THIS PARTICULAR 查询的 RA 表示法的任何困难是由于查询涉及聚合，并且 RA 表示法通常不支持表示此类操作。如果他们这样做了，将原始 table 与您的 SELECT AVG(...) 加上该 JOIN 上所需的 RESTRICT 的 JOIN 将解决您的问题。

Answer 2

首先，可以在关系代数和聚合中表达相关子查询（-> 依赖连接）。

您可能对此感兴趣：http://www.btw-2015.de/res/proceedings/Hauptband/Wiss/Neumann-Unnesting_Arbitrary_Querie.pdf

我还没有读完整篇论文，但我参加了 class Neumann 教授的讲座。他声称你可以解除任意查询的关联。但是我认为有一些限制。

select *
from T1
where T1.a = (select T2.a from T2 where T2.b = T1.b)

原则上，解除此查询的相关性很容易，在查看了查询计划后，我相信他们的数据库系统能够做到这一点 (https://hyper-db.de/interface.html). I think you could not express that in SQL though, since here you get a runtime error if the subquery does not return a scalar (https://blogs.msdn.microsoft.com/craigfr/2006/09/27/scalar-subqueries/)。

是否可以解除所有相关 SQL 子查询的关联？

Is it possible to decorrelate all correlated SQL subqueries?

sql

theory

relational-algebra