保留函数的分解

Click to edit Master title style,Click to edit Master text styles,Second level,Third level,Fourth level,Fifth level,*,*,*,Enforcing Functional Dependencies,This presentation was prepared by Yufei Tao,http:/www.cse.cuhk.edu.hk/taoyf,Outline,Dependency preserving decomposition,保留函數的分解,Canonical functional dependencies,最簡約的函數依賴,2,FD as a constraint,We already know that a functional dependency may reflect a constraint in the 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 the same,cust,-id,but different,acc-id,.,就是要查是否有兩個元組有相同的,cust,-id,但不同的,acc-id,。,3,FD as a constraint (cont.),DEPOSIT(,transaction,-id,cust,-id,acc-id,amount,),cust,-id,acc-id,SELECT,cust,-id,FROM DEPOSITGROUP BY,cust,-id,HAVING COUNT(DISTINCT,acc-id,) 1,The functional dependency holds if and only if the query result is empty.,如果此檢索返回空，則上面的函數依賴得以滿足。否則，則不滿足。,Corollary: you should be able to write a trigger to reject any update that violates the functional dependency.,對了，你應該可以寫一個,激發程式來拒絕所有違反此,函數依賴的更新吧。,4,Poor decomposition,A careless decomposition can make it very costly to check a functional dependency.,一個粗心的分解可能導致高昂的檢查函數依賴的代價,Say, we decompose,例如，考慮將,DEPOSIT(,transaction,-id,cust,-id,acc-id,amount,) into,分解為,：,T,1,(,transaction-id,cust,-id,) and,T,2,(,transaction-id,acc-id,amount,).,It is easy to see that verifying,cust,-id,acc-id,requires a join between,T,1,and,T,2,.,那么，檢查此函數依賴需要一個連接操作。,In this case, we say that this dependency is,not preserved,.,這樣的話，我們說此函數依賴,未被保留,。,5,Outline,Dependency preserving decomposition,保留函數的分解,Canonical functional dependencies,最簡約的函數依賴,6,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,B,B,C,.,Importance: instead of enforcing 4 dependencies, it suffices to enforce 2.,重要性：無需去驗證四個函數依賴，兩個即可。,7,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,.,8,Example 1,Simplify ,A,B, B,C, A,CD, to its canonical form.,將這組函數依賴化為規范形式。,9,Example 2,Simplify ,A,BC, B,C,A,B, AB,C, to its canonical form.,10,