加冕合法继承人¶
这是一个 QL 侦探谜题，它向您展示了如何在 QL 中使用递归编写更复杂的查询。
巴兹尔国王的继承人¶
呼！村子里再也没有罪犯了 - 你终于可以离开村庄回家了。
但是… 在你在村庄的最后一个晚上，老国王 - 伟大的巴兹尔国王 - 在睡梦中去世了，到处都是混乱！
国王从未结婚，也没有孩子，所以没有人知道谁应该继承国王的城堡和财富。 很多村民立刻声称他们与国王家族有血缘关系，他们才是真正的继承人。 人们争吵和打架，情况似乎无望。
最终你决定留在村子里解决争端，找到王位的真正继承人。
你想知道村里是否有人真的与国王有血缘关系。 这乍一看似乎是一项艰巨的任务，但你充满信心地开始工作。 你现在对村民很了解，你有一份村里所有父母及其子女的名单。
为了更多地了解国王和他的家人，你获得了进入城堡的权限，并找到了一些古老的家谱。 你也把这些关系包含在你的数据库中，看看国王家族中是否还有人活着。
以下谓词可以帮助您访问数据
| 谓词 | 描述 |
|---|---|
parentOf(Person p) |
返回 p 的父母 |
例如，您可以列出所有孩子 p 以及他们的父母
from Person p
select parentOf(p) + " is a parent of " + p
信息太多，无法手动搜索，因此您编写了一个 QL 查询来帮助您找到国王的继承人。
我们知道国王本人没有孩子，但他可能有兄弟姐妹。 编写一个查询以找出
from Person p
where parentOf(p) = parentOf("King Basil") and
not p = "King Basil"
select p
他确实有兄弟姐妹！ 但是你需要检查他们中是否有还活着… 这里还有另一个你可能需要的谓词
| 谓词 | 描述 |
|---|---|
isDeceased() |
如果该人是已故的，则成立 |
使用此谓词查看国王的任何兄弟姐妹是否还活着。
from Person p
where parentOf(p) = parentOf("King Basil") and
not p = "King Basil"
and not p.isDeceased()
select p
不幸的是，巴兹尔国王的兄弟姐妹都不在了。 是时候进一步调查了。 定义一个谓词 childOf() 可能会有所帮助，它返回该人的孩子。 为此，可以在 childOf() 的定义中使用 parentOf() 谓词。 请记住，某人是 p 的孩子，当且仅当 p 是他们的父母时
Person childOf(Person p) {
p = parentOf(result)
}
注意
如上例所示，您不必在谓词定义中直接编写
result = <expression involving p>。 相反，您还可以通过写p在result的形式来表达p和result之间的关系。
尝试编写一个查询来找出国王的兄弟姐妹是否还有孩子
from Person p
where parentOf(p) = parentOf("King Basil") and
not p = "King Basil"
select childOf(p)
该查询没有返回结果，因此他们没有孩子。 但是也许巴兹尔国王有一个活着的堂兄或有孩子，或者一个表堂兄，或者…
这变得很复杂。 理想情况下，您希望定义一个谓词 relativeOf(Person p) 来列出所有 p 的亲属。
你怎么做呢？
考虑对“亲属”的精确定义会有所帮助。 一个可能的定义是，两个人如果有共同的祖先，他们就是有血缘关系的。
您可以引入一个谓词 ancestorOf(Person p) 来列出所有 p 的祖先。 p 的祖先是 p 的父母，或 p 的父母的父母，或 p 的父母的父母的父母，等等。 不幸的是，这会导致一个无限的父母列表。 你不能编写一个无限的 QL 查询，所以一定有更简单的方法。
啊哈，你有一个主意！ 你可以说祖先是父母，或者是你已经知道是祖先的人的父母。
您可以将其翻译成 QL，如下所示
Person ancestorOf(Person p) {
result = parentOf(p) or
result = parentOf(ancestorOf(p))
}
如您所见，您在它自己的定义中使用了 ancestorOf() 谓词。 这是一个关于 递归 的示例。
这种递归，其中相同的操作（在本例中为 parentOf()）被多次应用，在 QL 中非常常见，被称为该操作的传递闭包。 有两个特殊的符号 + 和 * 在处理传递闭包时非常有用
parentOf+(p)将parentOf()谓词应用到p一次或多次。 这等效于ancestorOf(p)。parentOf*(p)将parentOf()谓词应用到p零次或多次，因此它返回p的祖先或p本身。
尝试使用这种新表示法来定义一个谓词 relativeOf() 并用它来列出国王的所有活着的亲属。
提示
以下是一种定义 relativeOf() 的方法
Person relativeOf(Person p) {
parentOf*(result) = parentOf*(p)
}
不要忘记使用 isDeceased() 谓词来查找仍然活着的亲属。
➤ 检查你的答案
选择真正的继承人¶
在下一个村庄会议上，你宣布有两个活着的亲属。
为了决定谁应该继承国王的财产，村民们仔细阅读了村庄宪法
“王位的继承人是国王最亲近的活着的亲属。 任何有犯罪记录的人将不予考虑。 如果有多个候选人，年龄最大的人是继承人。”
作为你的最后一个挑战，定义一个谓词 hasCriminalRecord，以便 hasCriminalRecord(p) 成立，如果 p 是你之前揭露的任何罪犯（在“找到小偷” 和“抓住纵火犯” 教程中）。
➤ 检查你的答案
实验性探索¶
恭喜！ 你找到了王位的继承人，并恢复了村庄的和平。 但是，你还没有必要离开村民。 仍然有一些关于村庄宪法的问题，你可以通过编写 QL 查询来回答村民。
- 哪个村民是王位的下一继承人？ 你可以编写一个谓词来确定其余村民与新君主的亲密程度吗？
- 如果多个村民与君主的亲属关系相同，你将如何使用 QL 查询来选择最年长的候选人？
你也可以尝试编写更多你自己的 QL 查询来找出关于村民的有趣事实。 你可以自由地调查任何你喜欢的东西，但这里有一些建议
- 村里最常见的头发颜色是什么？ 每个地区呢？
- 哪个村民的孩子最多？ 谁的后代最多？
- 村庄的每个地区住着多少人？
- 所有村民都与他们的父母住在村庄的同一个地区吗？
- 找出村里是否有时间旅行者！（提示：寻找“不可能”的家庭关系。）
答案¶
在这些答案中，我们使用 /* 和 */ 来标记查询的不同部分。 任何被 /* 和 */ 包围的文本都不会作为 QL 代码的一部分进行评估，而是被视为注释。
练习 1¶
import tutorial
Person relativeOf(Person p) { parentOf*(result) = parentOf*(p) }
from Person p
where
not p.isDeceased() and
p = relativeOf("King Basil")
select p
练习 2¶
import tutorial
Person relativeOf(Person p) { parentOf*(result) = parentOf*(p) }
predicate hasCriminalRecord(Person p) {
p = "Hester" or
p = "Hugh" or
p = "Charlie"
}
from Person p
where
not p.isDeceased() and
p = relativeOf("King Basil") and
not hasCriminalRecord(p)
select p