如何在域关系演算中表示“至多”？附示例查询解析

针对给出的关系模型：

• Dish(dish_id, name)：菜品表，包含菜品ID和名称
• Have(dish_id, ing_id)：关联表，记录菜品与对应食材ID的关联关系
• Ingredient(ing_id, name)：食材表，包含食材ID和名称

以下是两个查询需求的域关系演算表达式：

1. 找出被至多两道菜品包含的食材名称 #

“至多两道”的核心逻辑是：不存在三个不同的菜品同时包含该食材。对应的域关系演算表达式为：

{ i_name | ∃ i_id ( Ingredient(i_id, i_name) ∧ ¬(∃ d1, d2, d3 ( Have(d1, i_id) ∧ Have(d2, i_id) ∧ Have(d3, i_id) ∧ d1≠d2 ∧ d1≠d3 ∧ d2≠d3 )) ) }

也可以用全称量词等价表示（所有包含该食材的菜品中，任意三个里至少有两个是相同的）：

{ i_name | ∃ i_id ( Ingredient(i_id, i_name) ∧ (∀ d1, d2, d3 ( Have(d1, i_id) ∧ Have(d2, i_id) ∧ Have(d3, i_id) → d1=d2 ∨ d1=d3 ∨ d2=d3 )) ) }

2. 找出被至多一道菜品包含的食材名称 #

“至多一道”的核心逻辑是：不存在两个不同的菜品同时包含该食材。对应的域关系演算表达式为：

{ i_name | ∃ i_id ( Ingredient(i_id, i_name) ∧ ¬(∃ d1, d2 ( Have(d1, i_id) ∧ Have(d2, i_id) ∧ d1≠d2 )) ) }

等价的全称量词写法：

{ i_name | ∃ i_id ( Ingredient(i_id, i_name) ∧ (∀ d1, d2 ( Have(d1, i_id) ∧ Have(d2, i_id) → d1=d2 )) ) }

逻辑说明 #

• 用存在量词∃定位目标食材的ID和名称
• 通过否定“存在n个不同菜品关联该食材”的逻辑，直接表达“至多n-1个”的约束
• 全称量词的写法是从反向约束：所有关联的菜品中，任意n个里必有重复，从而限制总数不超过n-1

内容的提问来源于stack exchange，提问作者user5653890