保留函数的分解.ppt

1、Enforcing Functional Dependencies,This presentation was prepared by Yufei Tao .hk/taoyf,2,Outline,Dependency preserving decomposition保留函數的分解 Canonical functional dependencies最簡約的函數依賴,3,FD as a constraint,We already know that a functional dependency may reflect a constraint in t

2、he underlying application.函數依賴通常是實際應用中的一條要求。 If every customer can have a single account如果每個客戶只能擁有一個賬戶： cust-id acc-id Assume that we want to check whether the FD holds in:假設我們想檢查在下表中上面的函數依賴是否存在： DEPOSIT(transaction-id, cust-id, acc-id, amount). In other words, check if there are two tuples having t

3、he same cust-id but different acc-id.就是要查是否有兩個元組有相同的cust-id但不同的acc-id。,4,FD as a constraint (cont.),DEPOSIT(transaction-id, cust-id, acc-id, amount) cust-id acc-id SELECT cust-idFROM DEPOSITGROUP BY cust-idHAVING COUNT(DISTINCT acc-id) 1 The functional dependency holds if and only if the query resul

4、t is empty.如果此檢索返回空，則上面的函數依賴得以滿足。否則，則不滿足。 Corollary: you should be able to write a trigger to reject any update that violates the functional dependency. 對了，你應該可以寫一個激發程式來拒絕所有違反此函數依賴的更新吧。,5,Poor decomposition,A careless decomposition can make it very costly to check a functional dependency.一個粗心的分解可能導致

5、高昂的檢查函數依賴的代價 Say, we decompose 例如，考慮將DEPOSIT(transaction-id, cust-id, acc-id, amount) into 分解為：T1(transaction-id, cust-id) and T2(transaction-id, acc-id, amount). It is easy to see that verifying cust-id acc-id requires a join between T1 and T2.那么，檢查此函數依賴需要一個連接操作。 In this case, we say that this depe

6、ndency is not preserved.這樣的話，我們說此函數依賴未被保留。,6,Outline,Dependency preserving decomposition保留函數的分解 Canonical functional dependencies最簡約的函數依賴,7,Equivalence of FD sets,Two sets of functional dependencies are equivalent if either set can be derived from another. 兩組可互相導出的函數依賴是等同的。 A BC, B C, A B, AB C = A

7、B, B C. Importance: instead of enforcing 4 dependencies, it suffices to enforce 2.重要性：無需去驗證四個函數依賴，兩個即可。,8,Canonical set,Find the simplest equivalent of A B, B C, A C. 將這組函數依賴化至最簡。 Answer: A B, B C. If a set of FDs cannot be simplified further, we say it is canonical. 如果一組函數依賴不能再繼續化簡，我們說它是規范的。 A B, B C is canonical. A B, B C is the canonical form of A B, B C, A C.前者為后者的規范形式 Also called canonical cover.,9,Example 1,Simplify A