[發明專利]基于聚類的非一致性數據庫查詢方法

在審

• 申請號: 201310668188.2
• 申請日: 2013-12-11
• 公開（公告）號: CN103605812A
• 公開（公告）日: 2014-02-26
• 發明（設計）人: 不公告發明人
• 申請（專利權）人: 湖南人文科技學院
• 主分類號: G06F17/30
• 分類號: G06F17/30
• 代理公司: 暫無信息
• 代理人: 暫無信息

技術領域

本發明涉及一種基于聚類的非一致性數據庫查詢方法，屬于數據庫查詢技術領域。

背景技術

聚類方法把數據集合分成若干類，使得每個類內部的數據盡量相似，而屬于不同類的數據盡量不同。現實世界中，有一種不確定信息，信息不精確。在處理不確定性信息方面，經典關系數據庫處理不了具有不精確的數據，因而概率數據模型擴展了關系數據模型，對數據的不確定性進行了度量，在數據庫的關系中引入概率屬性來表示該元組的不確定性。對于實體對應的多個元組而言，每個元組的屬性值是不確定的，表示實體的概率大小。基于聚類的概念，聚類內多個潛在的非一致性元組可以給定概率，假定一個聚類代表一個現實實體，聚類內的每個元組表示實體的概率和為1，認為是元組在聚類內概率是條件獨立的，在不同聚類之間概率是獨立的；并提出了一種候選數據庫概念，對聚類概率進行計算和評價，但考慮的候選數據庫對于實際的海量數據庫來說是不可行的，且沒有考慮查詢重寫。

發明內容

本發明的目的在于提供一種基于聚類的非一致性數據庫查詢方法，以便縮小結果集中的可信聚類數量，有效地提高查詢性能。

為了實現上述目的，本發明的技術方案如下。?

一種基于聚類的非一致性數據庫查詢方法，具體包括：?

（1）多個關系的可信聚類概率的查詢重寫算法，詳細的步驟如下：

（1a）在給定的一個SPJ查詢中，首先得到查詢中的關系個數t和選擇條件個數k，初始化重寫查詢RJ。外循環次數為關系個數，內循環為選擇條件個數。在外循環中，取得臨時變量存儲產生結果集的別名filter，初始化非連接合取謂詞集SCW和連接合取謂詞屬性集AJ；

（1b）在第1個內循環中，如果合取選擇謂詞中的屬性是關系中的屬性，則判斷是否為連接的。如果為非連接合取謂詞，則把合取選擇謂詞中的屬性加入到非連接合取謂詞屬性集SCW中，否則加入到連接合取謂詞屬性集AJ中；

（1c）在第2個內循環中，如果合取選擇謂詞中的屬性是查詢中投影屬性，把合取選擇謂詞中的屬性加入到連接合取謂詞屬性集AJ中；

（1d）在外循環的最后取得該次循環產生的過濾查詢RJ。連接合取謂詞屬性集SCJ等于合取謂詞屬性集減去非連接合取謂詞屬性集SCW；

（1e）通過已經取得的產生過濾查詢RJ、連接合取謂詞屬性集SCJ和結果集別名filter，最終輸出查詢重寫語句。注意到沒有加入非連接合取謂詞屬性集SCW，這是因為在產生過濾查詢RJ時，就已經對本次循環的關系進行了非連接合取謂詞過濾元組，這樣壓縮了需要連接結果集的元組，在最后的結果集進行連接時，有助于提高查詢性能。

（2）無連接聚集查詢重寫算法，具體算法的基本步驟如下：

（2a）首先對初始分組屬性G和聚類屬性cluster進行分組求聚集屬性的最大值、最小值以及期望值和，得到結果集cand；

（2b）如果同一聚類內分組屬性值不相同，則最小值為0，因此需要去掉這種情況的元組，在產生的結果集cand上對初始分組屬性G進行分組求最小值和，得到包含最小值的結果集min_cand；

（2c）在結果集cand上對初始分組屬性G進行分組求最大值和期望值和，得到包含最大值和期望值的結果集max_cand；

（2d）在外查詢中，對已經產生的包含最大值和期望值的結果集max_cand左連接到包含最小值的的結果集min_cand。如果連接得到最小值為空，則最小值為0。最終產生初始分組屬性G的最值和期望值。

?（3）基于聚類的有連接聚集查詢重寫算法，基本步驟如下：

（3a）首先初始化重寫查詢，取得SPJ聚集查詢的關系集合R的元素個數、分組屬性集合G的元素個數、選擇謂詞集合SC的元素個數和聚集屬性集合E的元素個數；