[發明專利]數據庫一致性錯誤的重要度判定方法

有效

• 申請號: 201710981214.5
• 申請日: 2017-10-20
• 公開（公告）號: CN107633099B
• 公開（公告）日: 2021-02-02
• 發明（設計）人: 劉海龍;成阿茹;李戰懷;張國榮;張陶然;劉文潔
• 申請（專利權）人: 西北工業大學
• 主分類號: G06F16/23
• 分類號: G06F16/23;G06F16/28
• 代理公司: 西北工業大學專利中心 61204
• 代理人: 王鮮凱

1.一種數據庫一致性錯誤的重要度判定方法，其特征在于包括以下步驟：

步驟一、對數據庫中的關系表構建C-Graph和D-Graph超圖；C-Graph給出數據庫D上的函數依賴集合Σ，C-Graph G_Σ＝(V,E)：Σ_i：X_i→Y_i，U＝X∪Y；對于Σ中的每一個Σ_i:X_i→Y_i，有一個超邊e_i∈E，T(e_i)＝X_i且H(e_i)＝Y_i；D-Graph：根據C-Graph G_Σ和關系表R，G_R＝(V,E)：t∈R，每一個節點V_i∈V被定義為V_i＝(A_i,F_i)，對于每一個屬性A_i∈U的不同的值，都有一個在V中標為(A_i,F_i)的節點；給出C-Graph邊E_Σ＝{T_Σ(E),H_Σ(E)},會產生許多條D-Graph邊，每一個D-Graph邊E_i∈E被定義為E_i＝{T(E_i),H(E_i),Ω(E_i)}，其中T(E_i).A_i＝T_Σ(E)；H(E_i).A_i＝H_Σ(E)，每一個包含所有和相關的元組的IDs,被定義為函數依賴X→Y意味著X的值相同則Y值也必須相同，根據X的值將關系表中的數據分為不同的等價類，每一個等價類中，所有成員有相同的X值，其Y值相同或者不同；在D-Graph中有兩種超邊，一種是只有一個頭結點及|H(E)|＝1，另一種則是有多個頭結點及|H(E)|1，分別為B-arc邊和邊；在D-Graph中，如果包含一個或者多個邊，意味著至少一個函數依賴等價類的左屬性映射到多個等價類的右屬性；若圖中只包含B-arc邊，意味著每一個等價類的左屬性僅映射一個等價類的右屬性，因此沒有函數依賴違規；所以函數依賴違規檢查轉變為在D-Graph中查找函數依賴違規修復問題轉化為轉換所有的邊為B-arc邊，其目標是對所有違反函數依賴的元組集合排序即對函數依賴違規進行排序，因此問題轉換為對D-Graph中所有邊進行排序；

X、Y：為關系表中的屬性，U＝X∪Y；

Σ：函數依賴集合；

V：為超圖中節點的集合；

E：為超圖中超邊的集合；

H(e)：表示超邊的頭結點；

T(e)：表示超邊的尾節點；

t：為表R中的元組；

A_i：是屬性名且A_i∈U；

F_i：是t[A_i]的一個值；

步驟二、對不同函數依賴之間的關系進行分類；假設Σ集合為最小覆蓋，Σ_i:X→Y和Σ_j:X'→Y'，根據函數依賴最小覆蓋的定義：若或者Σ_i和Σ_j之間關系分為四類：

和Σ_j中的屬性表示如下:

如果Σ_i和Σ_j共享約束左邊的一些屬性，表示如下：

為

如果約束的右邊屬性值相同，表示如下：

為

如果約束左邊和右邊都有共享屬性，表示如下：

為

如果Σ_i和Σ_j中的屬性滿足以下：

為

為

為

如果Σ_i和Σ_j中的屬性滿足以下：

為

為

為

Σ：函數依賴集合名稱；

步驟三、找出關系表中的函數依賴違規并對不同函數依賴違規間的關系進行分類；假設當解決函數依賴違規問題時，僅修正函數依賴約束的右邊屬性的值；Σ_i和Σ_j之間的違規模式分為以下四類：

在和中解決其中一個約束的違規將不會影響另一個約束的違規，定義為模式；

在和中當修正約束的右邊屬性的值時，將影響所有共享屬性所在函數依賴約束的右屬性的值，定義為模式；

在和中修改約束右屬性的值將影響另一個約束中違規的左屬性的值，定義為模式；

在模式中分為以下幾種情況：

假設是邊且邊轉變為B-arc影響

假設是邊且邊轉變為B-arc將自動使轉變為B-arc邊；

假設是邊且邊轉變為B-arc將自動使轉變為B-arc邊；

假設是B-arc邊且是邊且轉變邊為B-arc將產生新的邊

假設是邊且無論轉變邊為B-arc還是邊轉變為B-arc都會將新的邊

在模式中分為以下幾種情況：

表示邊從v開始，表示邊從v'開始，U＝e.T(e)-{v}，U'＝e'.T(e')-{v'}；

對于每一對e和e'，假設轉變為會帶來新的邊；

對于每一對e和e'，假設轉變為會移動中的元組從B-arc邊e'到另一條B-arc邊e；

對于每一對e和e'，假設轉變為會移動中的元組從邊e'到另一條B-arc邊e；

對于每一對e和e'，假設|H(e)|1∧|H(e')|1∧U＝U',若轉變為會移動中的元組從邊e'到一條新邊e；若轉變為會移動中的元組從邊e'到邊e；

對于每一對e和e'，U≠U'，轉變為不影響另一條新邊的形成；

步驟四、函數依賴違規重要度評估，忽視所有的代價模型，修正函數依賴違規可能給數據庫帶來一些消極和積極的影響；一個函數依賴違規修正可以給關系表R質量的提高帶來一些效益，所以根據每一個違規帶來的潛在效益來評估其重要性；用函數依賴違規修正操作前和操作后臟元組的改變數量來評估函數依賴違規的重要性；vio(Σ,R)Θvio(Σ_i,R,v)表示修正函數依賴違規vio(Σ_i,R,v)之后的函數依賴違規集合；|vio(Σ,R)|表示包括vio(Σ,R)的元組數量；因為vio(Σ_i,R,v)的消除可能削減臟元組的數量或者可能帶來新的的臟元組，所以|vio(Σ,R)Θvio(Σ_i,R,v)|≥|vio(Σ_i,R,v)|或者|vio(Σ,R)Θvio(Σ_i,R,v)|≤|vio(Σ_i,R,v)|；|vio(Σ_i,R,v)|-|vio(Σ,R)Θvio(Σ_i,R,v)|評估關系表R中違規數量的改變和修正后的實例R'，定義其改變量為Δ(vio(Σ_i,R,v))，違規的效益值計算公式如下：

違規不是孤立的，數據庫中的一個函數依賴違規會影響另一個違規；當評估一個函數依賴違規修正所帶來的效益時，不僅考慮函數依賴違規本身還要考慮函數依賴違規的演變因素；在公式(1)中評估一個函數依賴違規消除的潛在好處為函數依賴違規所在的關系表中元組消除或增加的比率；給出由約束集合Σ和關系表R創建的相關的D-Graph，假設是相關的違規vio(Σ_i,R,v)；表示將轉變為B-arc后其他邊的改變，下面討論如何通過超圖的屬性計算公式(1)中的|Δ(vio(Σ_i,R,v))|；

假設約束Σ_i和其他約束的模式是或者清除這些函數依賴違規不會影響其他約束中的違規；所以當計算函數依賴違規vio(Σ_i,R,v)的|Δ(vio(Σ_i,R,v))|時，僅僅計算和其相關聯的元組的數量，即但是邊和其他的超邊同時是和模式時，是在這兩個模式中超邊影響的和，如公式(3)；

表示在模式中對超邊的影響，表示在模式中對超邊的影響；

公式(4)中為在模式中函數依賴違規滿足時，轉變為B-arc邊的改變量；

為在模式中函數依賴違規滿足時，轉變為B-arc邊的改變量；

為在模式中函數依賴違規滿足時，轉變為B-arc邊的改變量；

在公式(4)中當違規滿足時，改變量為0；

公式(5)中為在模式中函數依賴違規滿足時，轉變為B-arc邊的改變量；

為在模式中函數依賴違規滿足轉變為B-arc邊的改變量；

在公式(5)中當違規滿足時改變量為0；

步驟五、對數據庫中函數依賴違規重要度進行排序，根據步驟一得到關系表的C-Graph和D-Graph超圖；通過步驟二得到函數依賴間的關系并對函數依賴間的關系進行分類；在步驟三找出關系表的所有函數依賴違規，并對函數依賴違規關系進行分類；在步驟四中根據步驟三的分類計算每一個函數依賴違規的效益值；當對函數依賴違規排序時，首先創建一個列表，當通過步驟四得到函數依賴違規的效益值，根據比較函數依賴違規效益值將違規插入到列表中。