Werden wir Helden für einen Tag

Home | About | Archive

Relational division

Posted on Oct 20, 2011 by Chung-hong Chan

想一個問題想到頭爆,可是最後解決了。假設有兩個 table ,第一個 table 叫候選人 (candidates) ,是一些辭了職才親民落區的前高官,現職是無業遊民。

人物 優點
唐唐 乞人憎
唐唐 有外遇
振英 乞人憎
振英 黨員
犯婦 乞人憎
犯婦 長舌
犯婦 黨員

另一個 table 叫原則 (criteria)

優點
乞人憎
有外遇

哪個 candidate 有齊所有 criteria 的是廢柴一條。請問如何用 relational algebra 把這個 candidate 選出來。
原來這個算法叫做 relational division (÷) ,大部份的 DBMS 都無此功能。
從 eyeball 可知,如

candidates ÷ criteria ,答案應該是

人物
唐唐

但是怎樣用 relational algebra 算出來,卻並不簡單。網上找出的算法如下:

1. 從 candidates 取出 (project) 出「人物」的 column (π人物 candidates ),稱為 T1 。 T1 就是

人物
唐唐
振英
犯婦

2. 算出 T1 及 criteria 的 Cartesian product (T1 X criteria) ,稱為 T2 。 T2 就是

人物 優點
唐唐 乞人憎
唐唐 有外遇
振英 乞人憎
振英 有外遇
犯婦 乞人憎
犯婦 有外遇

3. 將 T2 與 Candidates 相減 ( T2 - Candidates ) ,得出 T3 。 T3 是

人物 優點
振英 有外遇
犯婦 有外遇

4. 從 T3 取出人物 column ,成 T4 (π人物 T3) 。 T4 是

人物
振英
犯婦

5. 將 T1 和 T4 相減 (T1 - T4) 得出答案

人物
唐唐

Powered by Jekyll and profdr theme