3

我有几个要转换为关系代数的 SQL 查询。但是，一些查询使用聚合运算符，我不知道如何转换它们。值得注意的是，他们使用 COUNT 和 GROUP BY.. HAVING 运算符。

这是架构：

水手（sid，sname，rating） Reserves（sid，bid，price） Boats（bid，bname）

这是我正在做的一个示例：查找恰好由 2 名水手保留的所有船只的出价和名称。

SELECT B.bid, B.bname
FROM Boats B, Reserves R
WHERE B.bid = R.bid
GROUP BY R.bid
HAVING 2 = (SELECT COUNT(*)
FROM Reserves R2
WHERE R2.bid = B.bid);

允许的关系代数运算：选择、投影、连接、条件连接、重命名、联合、交集、叉积、除法

4

3 回答 3

5

这只是一半的答案...

可以使用条件连接和投影找到关系“由两个或多个水手保留的船”，它们都在您的允许操作集中：

SELECT DISTINCT R1.bid
  FROM Reserves AS R1 
       JOIN Reserves AS R2
          ON R1.bid = R2.bid
             AND R1.sid < R2.sid;

可以使用条件连接（两次）和投影找到关系“由三个或更多水手保留的船”，它们都在您的允许操作集中：

SELECT DISTINCT R1.bid
  FROM Reserves AS R1
       JOIN Reserves AS R2
          ON R1.bid = R2.bid
             AND R1.sid < R2.sid
       JOIN Reserves AS R3
          ON R1.bid = R3.bid
          AND R2.sid < R3.sid;

如果我们有一个减号运算符，例如EXCEPT在标准 SQL 中：

SELECT DISTINCT R1.bid
  FROM Reserves AS R1 
       JOIN Reserves AS R2
          ON R1.bid = R2.bid
             AND R1.sid < R2.sid
EXCEPT
SELECT DISTINCT R1.bid
  FROM Reserves AS R1
       JOIN Reserves AS R2
          ON R1.bid = R2.bid
             AND R1.sid < R2.sid
       JOIN Reserves AS R3
          ON R1.bid = R3.bid
          AND R2.sid < R3.sid;

如果我们有限制（WHERE在 SQL 中）和半差分（aka antijoin）运算符（例如NOT IN在 SQL 中）：

SELECT DISTINCT R1.bid
  FROM Reserves AS R1 
       JOIN Reserves AS R2
          ON R1.bid = R2.bid
             AND R1.sid < R2.sid
 WHERE R1.bid NOT IN (
                      SELECT DISTINCT R1.bid
                        FROM Reserves AS R1
                             JOIN Reserves AS R2
                                ON R1.bid = R2.bid
                                   AND R1.sid < R2.sid
                             JOIN Reserves AS R3
                                ON R1.bid = R3.bid
                                AND R2.sid < R3.sid
                     );

...但是您允许的操作集不包括限制、半差或减号:(

于 2011-09-30T10:11:44.067 回答
4

“我正在读一本书，其中有一章是关于关系代数的，它根本没有提到它们的聚合函数”。

关于关系代数的文献通常将自己限制在代数中使关系封闭的部分。如果代数的任何运算符都没有返回不是该集合成员的类型的值，则代数在一组类型上是封闭的（我可能表达自己有点草率，但主要思想是正确的）代数封闭的类型。

如果您拥有（或想在书中考虑）是所有关系类型的集合，并且您想编写代数的处理方法，那么您不能定义返回整数 (COUNT) 或浮点数 ( HARMONICMEAN)，或日期 (MIN(<date column>))，或任何类似的东西，而不会破坏代数的“封闭”属性。

这并不是说这样的聚合操作没有用（当然不是）。在主要目的是解释 JOIN、PROJECT、RESTRICT 等的上下文中，它们通常并不完全相关。

编辑

关于 GROUP BY ... HAVING 的补充答案。您正确地注意到，当涉及到代数等价物时，这个 SQL 构造是不平凡的东西。它的要点是您提到的代数运算符集缺少实现这些东西所需的运算符，而该运算符是 GROUP。GROUP 接受一个输入关系，并产生一个输出关系，其中一个属性是关系值。

例如，GROUP (RESERVES, SAILORS_AND_THEIR_BID (SID, PRICE)) 将产生 2 阶关系，具有 BID 和 SAILORS_AND_THEIR_BID 属性。后一个属性是关系值的，因此表达式 COUNT(SAILORS_AND_THEIR_BID) 在应用于此关系的 RESTRICT 条件的上下文中变得有效，因此您可以编写 (GROUP (RESERVES, SAILORS_AND_THEIR_BID (SID, PRICE))) WHERE COUNT (SAILORS_AND_THEIR_BID) = 2。

于 2011-10-01T19:46:00.637 回答
1

基于 onedaywhen 的回答：

是的，缺少集合差异运算符确实会受到伤害。应该完全允许。但是，我们可以用集合补集和交集来表示集合差：

B - A = B ∩ A'

即B和A的不同实际上是B与A的补码的交集。我们将交集作为允许的运算符，虽然关系的适当补码是一件丑陋的事情，但 R1 ⊆ R 相对于 R 的补码（即 R 中不存在于 R1 中的内容）可以通过连接轻松找到：

SELECT DISTINCT R0.x
FROM R as R1
JOIN R as R0 ON R1.x<>R0.x
WHERE R1.x=val

是相对于 R 的补码

SELECT DISTINCT R.x FROM R WHERE R.x=val

所以，这里有一个谜题的解决方案，我认为：很容易得到两个或更多人保留的所有船：选择保留表中的所有船，将结果与它本身相乘，然后选择每一行都有不同的水手 1 和水手 2。在笨拙的关系代数符号中，他们教给我：

π( R.bid ) (
   σ( R.bid=R2.bid and R.sid<R2.sid )( R x ρ(R, R2) ) 
)

（其中 π 是投影算子，σ 是选择算子，ρ 是重命名算子）

这可以获取两个或更多人预订的所有船只的 ID。现在我要去取所有由两个或更少的人预订的船。为此，我将选择三个或更多人保留的所有船，并通过从原始表中选择该集合中不存在的所有行来获取集合的补充。它不会很漂亮，但它是这样的：

 π(R.bid)(σ(R.bid<>R1.bid)(
    π(R.bid)(R)
      x
    π(R1.bid) (
        σ( R1.bid=R2.bid and R2.bid=R3.bid and R1.sid<R2.sid and R2.sid<R3.sid )( ρ(R, R1) x ρ(R, R2) x ρ(R, R3) )
     )
  ))

你看，我选择了所有具有属性的行，然后从原始表中选择了所有不属于这些的行，将所有没有属性的行都排除在外，这意味着所有没有被三个人保留的船或更多人，由两个或更少人预订的船。

要获得恰好有两个人预订的船，只需将其与不止一个人预订的船相交即可。

π( R.bid ) (
   σ( R.bid=R2.bid and R.sid<R2.sid )( R x ρ(R, R2) ) 
) ∩ π( R.bid ) (
    σ(R.bid<>R1.bid)(
       π(R.bid)(R)
         x
       π(R1.bid) (
           σ( R1.bid=R2.bid and R2.bid=R3.bid and R1.sid<R2.sid and R2.sid<R3.sid )( ρ(R, R1) x ρ(R, R2) x ρ(R, R3) )
        )
     )
 )

啊。太丑了，让人心疼。我希望我知道一个更好的符号。

SQLishly，它可能看起来像这样，我认为：

(SELECT DISTINCT R1.bid
  FROM Reserves AS R1 
    JOIN Reserves AS R2 ON R1.bid = R2.bid AND R1.sid < R2.sid
) INTERSECT (
SELECT DISTINCT R.bid
  FROM Reserves AS R1
    JOIN Reserves AS R2 ON R1.bid = R2.bid AND R1.sid < R2.sid
    JOIN Reserves AS R3 ON R1.bid = R3.bid AND R2.sid < R3.sid
    JOIN Reserves AS R ON R.bid<>R1.bid
)

请注意，这正是 onedaywhen 的解决方案，除了我将集差表示为取与补码的交集。

于 2011-10-13T00:07:07.887 回答