[發(fā)明專利]用于優(yōu)化針對(duì)垂直存儲(chǔ)式數(shù)據(jù)庫(kù)的查詢的方法和設(shè)備

無(wú)效

• 申請(qǐng)?zhí)枺?/td>: 200710192738.2
• 申請(qǐng)日: 2007-11-16
• 公開(kāi)（公告）號(hào): CN101436192A
• 公開(kāi)（公告）日: 2009-05-20
• 發(fā)明（設(shè)計(jì)）人: 王晨;閆鶯;馬力;潘越
• 申請(qǐng)（專利權(quán)）人: 國(guó)際商業(yè)機(jī)器公司
• 主分類號(hào): G06F17/30
• 分類號(hào): G06F17/30
• 代理公司: 北京市金杜律師事務(wù)所
• 代理人: 朱海波

1.一種用于優(yōu)化針對(duì)垂直存儲(chǔ)式數(shù)據(jù)庫(kù)的查詢的方法，其中所述數(shù)據(jù)庫(kù)中的條目被分成若干分區(qū)，每個(gè)分區(qū)具有表示所述分區(qū)中的條目的分區(qū)簽名，該方法包括：

將從用戶接收的第一查詢分解為多個(gè)第一子查詢；

按照與產(chǎn)生所述分區(qū)簽名的方式相對(duì)應(yīng)的方式，為每個(gè)第一子查詢產(chǎn)生簽名；

通過(guò)將每個(gè)第一子查詢的簽名分別與所有分區(qū)的分區(qū)簽名進(jìn)行比較，獲得與該第一子查詢匹配的所有分區(qū)；

基于所述匹配的分區(qū)，重寫(xiě)由第一子查詢轉(zhuǎn)換而來(lái)的第二子查詢，以得到重寫(xiě)的第二子查詢；以及

組合針對(duì)所有第一子查詢的重寫(xiě)的第二子查詢來(lái)形成第二查詢，以便利用該第二查詢執(zhí)行對(duì)所述數(shù)據(jù)庫(kù)的查詢。

2.根據(jù)權(quán)利要求1所述的方法，其中所述第一查詢和第一子查詢是SPARQL查詢，以及第二子查詢和第二查詢是SQL查詢。

3.根據(jù)權(quán)利要求1所述的方法，其中所述數(shù)據(jù)庫(kù)是RDF存儲(chǔ)庫(kù)，所述RDF存儲(chǔ)庫(kù)中的每個(gè)條目包含RDF三元組，該RDF存儲(chǔ)庫(kù)包含其值表示RDF三元組主語(yǔ)的主語(yǔ)列、其值表示RDF三元組謂詞的謂詞列以及其值表示RDF三元組賓語(yǔ)的賓語(yǔ)列，以及其中該RDF存儲(chǔ)庫(kù)還包含其值表示對(duì)應(yīng)的RDF三元組所在分區(qū)的唯一標(biāo)識(shí)符列。

4.根據(jù)權(quán)利要求3所述的方法，其中所述RDF存儲(chǔ)庫(kù)中的所有條目被映射為一張表示所有RDF三元組的圖，RDF三元組主語(yǔ)被表示為圖中的源節(jié)點(diǎn)，RDF三元組賓語(yǔ)被表示為圖中的宿節(jié)點(diǎn)，RDF三元組謂詞被表示為從源節(jié)點(diǎn)到宿節(jié)點(diǎn)的有向連接，以及其中該圖被分成若干子圖，每個(gè)子圖對(duì)應(yīng)于一個(gè)分區(qū)。

5.根據(jù)權(quán)利要求4所述的方法，其中子圖內(nèi)的連接是較密的，跨越子圖之間的連接是較稀疏的，以及其中對(duì)于跨越子圖之間的連接，在相關(guān)子圖的每一個(gè)子圖內(nèi)制作該連接的副本，以使得分割后的子圖能夠反映所述RDF存儲(chǔ)庫(kù)中的所有數(shù)據(jù)關(guān)系。

6.根據(jù)權(quán)利要求1所述的方法，其中所述分區(qū)的簽名是通過(guò)利用哈希函數(shù)為分區(qū)中的每個(gè)條目生成簽名并且對(duì)每個(gè)條目的簽名進(jìn)行“或”操作得到的。

7.根據(jù)權(quán)利要求1所述的方法，所述分解步驟進(jìn)一步包括：

將所述第一查詢映射為一個(gè)查詢圖，以及

枚舉所述查詢圖中的2可達(dá)子圖，所述2可達(dá)子圖是這樣的圖，其中任何頂點(diǎn)是由至多2個(gè)連接或者邊可達(dá)的；

其中每個(gè)2可達(dá)子圖對(duì)應(yīng)于一個(gè)第一子查詢。

8.根據(jù)權(quán)利要求6所述的方法，通過(guò)與產(chǎn)生分區(qū)的簽名相同的哈希函數(shù)來(lái)產(chǎn)生針對(duì)每個(gè)第一子查詢的簽名。

9.根據(jù)權(quán)利要求6或8所述的方法，其中所述哈希函數(shù)為MD5哈希函數(shù)。

10.根據(jù)權(quán)利要求9所述的方法，其中當(dāng)在針對(duì)第一子查詢產(chǎn)生的簽名中為1的位置在分區(qū)的簽名中也都被置1時(shí)，則該第一子查詢與該分區(qū)相匹配。

11.根據(jù)權(quán)利要求1所述的方法，其中如果在所述獲得步驟沒(méi)有得到與該第一子查詢匹配的分區(qū)，則提前結(jié)束查詢處理。

12.根據(jù)權(quán)利要求1所述的方法，其中所述分區(qū)具有唯一標(biāo)識(shí)符，以及所述重寫(xiě)步驟進(jìn)一步包括：

創(chuàng)建一個(gè)臨時(shí)表，用于存儲(chǔ)與該第一子查詢相匹配的所有分區(qū)的唯一標(biāo)識(shí)符，以及

利用與存儲(chǔ)有唯一標(biāo)識(shí)符的該臨時(shí)表相關(guān)的附加連接條件，來(lái)重寫(xiě)該第二子查詢。

13.根據(jù)權(quán)利要求1所述的方法，其中所述分區(qū)具有唯一標(biāo)識(shí)符，以及其中，

當(dāng)與該第一子查詢相匹配的分區(qū)的數(shù)量大于預(yù)定數(shù)值時(shí)，所述重寫(xiě)步驟包括：

創(chuàng)建一個(gè)臨時(shí)表，用于存儲(chǔ)與該第一子查詢相匹配的所有分區(qū)的唯一標(biāo)識(shí)符，以及

利用與存儲(chǔ)有唯一標(biāo)識(shí)符的該臨時(shí)表相關(guān)的附加連接條件，來(lái)重寫(xiě)該第二子查詢，

當(dāng)與該第一子查詢相匹配的分區(qū)的數(shù)量小于預(yù)定數(shù)值時(shí)，所述重寫(xiě)步驟包括：

利用關(guān)于與該第一子查詢匹配的分區(qū)的附加限制，來(lái)重寫(xiě)該第二子查詢。

14.一種用于優(yōu)化針對(duì)垂直存儲(chǔ)式數(shù)據(jù)庫(kù)的查詢的設(shè)備，其中所述數(shù)據(jù)庫(kù)中的條目被分成若干分區(qū)，每個(gè)分區(qū)具有表示所述分區(qū)中的條目的分區(qū)簽名，該設(shè)備包括：

分解裝置，用于將從用戶接收的第一查詢分解為多個(gè)第一子查詢；

查詢簽名產(chǎn)生裝置，用于按照與產(chǎn)生所述分區(qū)簽名的方式相對(duì)應(yīng)的方式，為每個(gè)第一子查詢產(chǎn)生簽名；

分區(qū)獲得裝置，用于通過(guò)將每個(gè)第一子查詢的簽名分別與所有分區(qū)的分區(qū)簽名進(jìn)行比較，獲得與該第一子查詢匹配的所有分區(qū)；

查詢重寫(xiě)裝置，用于基于所述匹配的分區(qū)，重寫(xiě)由第一子查詢轉(zhuǎn)換而來(lái)的第二子查詢，以得到重寫(xiě)的第二子查詢；以及

查詢組合裝置，用于組合針對(duì)所有第一子查詢的重寫(xiě)的第二子查詢來(lái)形成第二查詢，以便利用該第二查詢執(zhí)行對(duì)所述數(shù)據(jù)庫(kù)的查詢。