62

使用数据库,如何使用关系代数找到 MAX?

4

8 回答 8

83

假设你有一个关系,A,有一个属性,'a'(减少一个更复杂的关系是关系代数中的一个简单任务,我相信你已经做到了这一点),所以现在你想找到最大值A中的值。

一种方法是找到 A 与自身的叉积,一定要重命名“a”,这样你的新关系就具有不同名称的属性。例如:

(将“a”重命名为“a1”) X(将“a”重命名为“a2”)

现在选择'a1' <'a2',结果关系将具有除最大值之外的所有值。要获得最大值,只需找到原始关系之间的差异:

(A x A) - (select 'a1' < 'a2') ((rename 'a' as 'a1')(A) x (rename 'a' as 'a2')(A))

然后project按照 Tobi Lehman 在下面的评论中建议的那样,使用运算符减少到单个列。

用关系代数表示法写这个是(如果我没记错的话)。请注意,最终重命名(即 ρ)只是为了得到一个与原始关系具有相同名称的属性:

ρ a/a1a1 ((A x A) - σ a1 < a2a1/a (A) x ρ a2/a (A))))

于 2011-10-24T21:37:14.533 回答
44

只是我的两分钱,因为我今天自己试图解决这个问题。

假设我们有 A = 1,2,3

如果你使用

A x A - (select 'a1' < 'a2') ((rename 'a' as 'a1')(A) x (rename 'a' as 'a2')(A))

你不会得到单个最大值,而是像 1|1, 2|1,3|2,3|1,3|2,3|3 这样的两列

获得 3 的方法是

project(a)A - project(a1)((select 'a1' < 'a2') ((rename 'a' as 'a1')(A) x (rename 'a' as 'a2')(A)))

至少这是我在类似情况下必须做的。

希望它可以帮助某人

于 2013-01-27T14:07:19.290 回答
29

假设我们与属性 A 和值 1,2,3 有关系

A

1
2
3

所以现在..

项目 A 值并用 A1 重命名

A1
1
2
3

再次项目 A 值并用 A2 重命名

A2
1
2
3

将其与A2<A1 ie连接起来\join_{A2<A1}
- 输出模式:(A2 整数,A1 整数)

A2<A1

1|2
1|3
2|3

总是听到 A2 值会小于 A1,因为我们join喜欢这样(a2<a1

现在项目 A2 输出如下

A2
1
2

现在与原始属性不同

A diff A2

A
1
2
3

 diff

A2
1
2

输出为3最大值

于 2014-01-20T12:53:09.920 回答
19

我现在已经忘记了大部分关系代数语法。仅使用SELECT,PROJECTMINUS的查询RENAME将是

SELECT v1.number
FROM values v1
MINUS
SELECT v1.number
FROM values v1 JOIN values v2 ON v2.number > v1.number

希望你能翻译!

于 2011-03-31T00:19:42.133 回答
5

我知道这很旧,但这里有一个手写的公式,可能很方便!

在此处输入图像描述

关系 A:1,2,3,4

1. First we want to PROJECT and RENAME relation A
2. We then to a THETA JOIN with the test a1<a2
3. We then PROJECT the result of the relation to give us a single set of values 
   a1: 1,2,3 (not max value since a1<a2)

4. We then apply the difference operator with the original relation so: 
   1,2,3,4 --- 1,2,3 returns 4

   4 is the Max value.
于 2014-11-01T10:23:46.443 回答
4

找到最大值:

  • 战略:

    1. 找出那些x不是MAX.

      • 重命名A关系,d以便我们可以将每个A x关系与所有其他关系进行比较。
    2. 用于查找在前面步骤中未找到的set difference那些。A x

  • 查询是: 在此处输入图像描述

于 2017-08-03T14:12:35.763 回答
1

 Project x(A) - Project A.x
(Select A.x < d.x (A x Rename d(A)))
于 2017-08-01T09:06:02.610 回答
0

关系代数(通过比较过滤)

最近这个问题在数据库模块中作为练习材料出现,当我四处寻找帮助时,我找不到任何好的答案。“Md. Rezwanul Haque”的答案是正确的,但它并没有得到真正的解释,因为它依赖于先验知识(如果你不理解笛卡尔积)。

所以,这是我的解释的答案,希望这能让一些人更容易:

    TABLE: PEOPLE
PEOPLE.name PEOPLE.age
'Jack'      16
'Megan'     15
'Harry'     14
'Lilly'     16
'Michael'   8

这个想法是"Collect what you don't want and remove it from what you have; leaving you with what you want."

第一步(建表查询)

使用过滤时,SELECTION我们只能比较我们拥有的元组中的内容。这意味着我们需要向这些元组添加我们想要比较的数据。

因此,我们需要将我们的PEOPLE表与我们想要比较的数据合并。这可以使用x (Cartesian Product) Operator

像这样:PEOPLE x PEOPLE但是我们不能这样做,因为结果表看起来像这样:

           TABLE: PEOPLE x PEOPLE
PEOPLE.name PEOPLE.age PEOPLE.name PEOPLE.age 
'Jack'      16         'Jack'      16

我们有duplicate Attribute names这意味着我们需要创建一个CopyPEOPLE,它具有我们可以引用的不同名称。否则我们不能使用它,x Cartesian Product Operator因为它要求所有属性在结果表中都是唯一的,你不能有两个PEOPLE.name属性。

这是我们将使用RENAME Operator看起来像这样的地方:

PEOPLE ⨯ (ρ ALT (PEOPLE))

在这里我所做的是使用Cartesian Product合并PEOPLE和在ALT哪里ALTPEOPLE renamedALT

这会给我们一个看起来有点像这样的表:

          TABLE: PEOPLE x ALT
PEOPLE.name  PEOPLE.age ALT.name  ALT.age
'jack'       16         'jack'    16
'jack'       16         'megan'   15
'jack'       16         'harry'   14
'jack'       16         'lilly'   16
'jack'       16         'michael' 8

(结果表是 (PEOPLE.size * PEOPLE.size) = 5*5,其中 size 是元组的数量)其中的每个值PEOPLE都与ALT

步骤 2(选择)

现在我们可以过滤所有值并获取我们不想要的值。所以假设我只希望PEOPLE这个问题中最年长的人可以改写为:Only people who are not younger than someone所以我们只抓住那些比某人年轻的人。我们这样做是因为it's easier to Query for what we don't want that what we do want.

因此,我们Predicate将是:PEOPLE.age < ALT.age我们只选择那些are younger than someone.

如果我们要反Predicate转到, PEOPLE.age > ALT.age我们会得到一些不是最年长的人,but who are older than at least one person. 这可以帮助我们获得the youngest

给我们一个SELECTION这样的:

(σ (PEOPLE.age < ALT.age) (PEOPLE x (ρ ALT (PEOPLE))))

这将产生一个像这样的表:

TABLE: (σ (PEOPLE.age < ALT.age) (PEOPLE x (ρ ALT (PEOPLE))))

PEOPLE.age  PEOPLE.name  ALT.name  ALT.age 
'megan'     15           'jack'    16
'megan'     15           'lilly'   16
'harry'     14           'jack'    16
'harry'     14           'megan'   15
'harry'     14           'lilly'   16
'michael'   8            'jack'    16
'michael'   8            'megan'   15
'michael'   8            'harry'   14
'michael'   8            'lilly'   16

结果是比某人年轻的人,以及他们比谁年轻。但是我们的查询是:Only people who are not younger than someone这与此完全相反。所以这不是我们的目标,我们需要做更多的事情。如果你要这样做:

π PEOPLE.name PEOPLE.age (σ (PEOPLE.age < ALT.age) (PEOPLE x (ρ ALT (PEOPLE))))

这将为我们提供一个包含megan, harry, and michael以下内容的表格:Only people who are younger than someone

第 3 步(获得我们的决赛桌)

现在我们有一个表,其中包含Only people who are younger than someone但我们想要的是Only people who are not younger than someone所以我们需要做的是remove all of the people who are younger than someone from the PEOPLE Table to give us only those who are not younger than someone

所以我们需要使用Subtraction Operation来从我们的PEOPLE table. 这给了我们最终的查询:

PEOPLE - (π PEOPLE.name PEOPLE.age (σ (PEOPLE.age < ALT.age) (PEOPLE x (ρ ALT (PEOPLE)))))

生成下表:

PEOPLE - (π PEOPLE.name PEOPLE.age (σ (PEOPLE.age < ALT.age) (PEOPLE x (ρ ALT (PEOPLE)))))

PEOPLE.name PEOPLE.age
'jack'      16
'lilly'     16

杰克和莉莉在哪里only people in PEOPLE who are NOT Younger than someone

于 2021-10-13T11:16:22.687 回答