从英文描述形成关系代数查询

Question

我正在为即将到来的学校考试做准备。

当我在做一些示例问题时，我被一个特定的问题卡住了。

Passenger {p_id, p_name, p_nation} with key {p_id}
Flight {f_no, f_date, f_orig, f_dest} with key {f_no, f_date}
Trip {p_id, f_no, f_date, class} with key {p_id, f_no,f date}  
    and foreign keys [p_id] ⊆ Passenger[p_id] and [f_no, f_date] ⊆ Flight[f_no, f_date]

问题问：

Consider classes that passengers have occupied on flights from Narita. Write in relational algebra: What are the ids of passengers who have flown from Narita in each of these classes at least once?

到目前为止我所做的是：

-- rename class to class' in Trip and join with Trip
Q1 = Trip JOIN RENAME class\class' (Trip)
-- select those Q1 tuples where class = class'
Q2 = RESTRICT class = class' (Q2)
-- Project for those who traveled in different classes more than once
Q3 = PROJECT p_id (Q1 - Q2)

Q3 将向我显示（如果我做对了）所有在不同类.

旅行超过一次的乘客的 ID

有人可以帮助我进一步了解这一点吗？

Answer 1

This is as far as I got.

你计算出的Q3实际上容纳了在同一天class同一航班乘坐多于一个class的乘客。而且，根据限制，没有这样的乘客。原因如下：

根据你的代码Q1是

/* (tuples where)
    p_id took f_no on f_date in class
AND p_id took f_no on f_date in class'
*/
Trip JOIN RENAME class\class' Trip

对于 Q1，乘客 p_id f_no d_no 在 class 和（对于该航班号和日期）在 class'。（注意，在常识下，一个人一次只能飞一趟class，如果class <> class' 则他们必须在同一日期以不同的 classes.)

乘坐相同航班号的多次旅行

Q1 - Q2 就是 SELECT class <> class' Q1。所以 Q3 保存了在同一日期乘坐相同航班号的不同 classes 旅行的乘客的 ID。但是这些人与对您的整体查询的合理解释无关 "passengers who have flown from Narita in each of these classes at least once".

但无论如何，由于{f_no，f_date}是Flight的CK（候选键），给定的航班号和日期只有一个航班，所以没有乘客可以乘坐相同的航班号和日期不止一次。所以Q3反正是空的。

Forming a relational algebra query from an English description

始终表征关系——给定关系的值或查询（子）表达式的值——通过语句模板——谓词——由属性参数化。该关系包含使其成为一个陈述的元组——命题——在这种情况下是正确的。

您必须已经为每个基本关系提供了谓词。例如：

-- (tuples where) p_id took f_no on f_date in class Trip

那么您需要根据基本谓词来表达您的查询（子）表达式谓词，以便可以根据基本关系计算（子）表达式关系：

Consider classes that passengers have occupied on flights from Narita.

/* (tuples where) FOR SOME p_id, f_no, f_date, f_orig & f_dest, p_id took f_no on f_date in class AND f_no flew on f_date from f_orig to f_dest AND f_orig = 'Narita' */ PROJECT class SELECT f_dest = 'Narita' (Trip JOIN Flight)

r JOIN s的谓词是predicate-of-r AND predicate-of-s。 SELECT c r 的谓词是 predicate-of-r AND c。每个关系运算符都有这样一个谓词变换。 PROJECT some-attributes-of-r r 的谓词是 FOR SOME other-attributes-of-r predicate-of-r。 RENAME a\a' r 的谓词是 predicate-of-r，其中（适当出现的）a 替换为 a'。

要查询，找到一些与你想要的谓词等价的谓词，然后用相应的关系表达式替换它的部分。参见 this。

约束和查询

我们必须知道谓词才能查询。约束（包括 FD、CK、PK 和 FK）是每个可能出现的 situation/state 中的真值，用谓词表示。如果查询的谓词只能用基本谓词来表达，我们只需要在查询时知道约束，因为这些约束成立。例如给定 Trip & Flight 但没有约束 我们不能为 "classes that passengers have occupied on flights from Narita" 查询 ，即元组中的 classes 其中：

p_id took f_no on f_date in class from f_orig to f_dest

我们能得到的最接近的是 (Trip JOIN Flight):

p_id took f_no on f_date in class AND f_no flew on f_date from f_orig to f_dest

但这并不一定能告诉我们在哪些航班上使用了哪些 class(es)。但是如果{f_no,f_date}在Flight中是唯一的，这意味着{f_no,f_date}是Flight的一个CK，那么这两个谓词的意思是一样的事情（即每个元组和情况都有相同的真值）。

另一方面，由于我们可以在给定 CK 约束的情况下表达该查询，因此我们也不需要被告知 {f_no, f_date} 是从旅行到飞行的 FK。 FK 说如果一些乘客在 f_date 上乘坐 f_no 在一些 class 然后 f_no 在 f_date 上从某个起点飞到某个目的地并且 {f_no, f_date}是飞行的CK。所以乘客 {f_no, f_date} 是航班 {f_no, f_date}。但是 无论 FK 的第一个合取是否也成立，或者任何其他约束是否也成立， 查询 returns 满足其谓词的元组。

从英文描述形成关系代数查询

Forming a relational algebra query from an English description

relational-algebra