Datalog 用 fact 與 rule 表達 derived relationship。它的 syntax 很小，因此能露出 SQL 常藏在 join、subquery 與 recursion 後面的邏輯。對 data cleaning 而言，這有助分清 source fact、derived evidence 與 violation rule。
Fact 與 rule
parent("Ada", "Ben").
parent("Ben", "Chen").
ancestor(X, Y) :- parent(X, Y).
ancestor(X, Z) :- parent(X, Y), ancestor(Y, Z).:- 可讀成「成立，如果」。第一條是 base case；第二條表示 ancestor 的 parent 也是 ancestor。
Evaluation 會反覆套 rule，直到推不出新 fact，這就是 least fixed point。
round 0: source parent facts
round 1: direct ancestors
round 2: length-two paths
...
result 不再成長就停止白話來說： Recursion 一直問「用目前知道的事，還能推出什麼新事？」答案是「沒有」時就結束。
Variable 必須 safe
Rule head 或 negative condition 裡的 variable，應由 positive body atom 綁定，否則它可能在未定義 universe 上任意取值。
has_author(P) :- paper_author(P, A).
missing_author(P) :- paper(P), not has_author(P).P 先被 paper(P) ground，再做 negative test。Negation 最安全的情況是 stratified program：predicate 不會透過 negative cycle 依賴自己。
Integrity constraint 作為 denial rule
Denial 表示某組合永遠不應成立：
:- paper_author(P, A), not paper(P).實作時把 body 當 query；每個 answer 都是 violation witness。它不只給一個「invalid relationship」flag，而是指出牽涉哪些 tuple。
Recursive SQL 對應寫法
WITH RECURSIVE ancestor(person, descendant) AS (
SELECT parent, child
FROM parent
UNION
SELECT a.person, p.child
FROM ancestor AS a
JOIN parent AS p ON p.parent = a.descendant
)
SELECT * FROM ancestor;UNION 去除 duplicate，讓有限 relation 到達 fixed point。UNION ALL 可能較快，但有 cycle 時可能重複 path 或無法停止，除非另外追蹤 visited state／depth。
Recursion 在 cleaning 的用途
- 沿 hierarchical taxonomy 展開；
- 找 transitive duplicate link；
- 追 provenance dependency；
- 在 graph 上傳播 classification；
- 找 parent-child cycle。
Recursion 不會判斷 edge 是否可信；它會放大收到的 base fact 與 mapping，所以 seed relation 仍要先驗證。
複習卡
- Fact 是 stored observation；rule 推導新 relation。
- Recursive evaluation 進行到 fixed point。
- Base case 為 recursion 定錨。
- Safe variable 由 positive atom 綁定。
- Denial rule 的 answer 就是 violation witness。
- Recursive SQL 使用相同 fixed-point 思想，但要明確處理 duplicate 與 cycle。