[發(fā)明專利]在多版本數(shù)據(jù)庫系統(tǒng)中的萬圣夜保護(hù)

有效

• 申請?zhí)枺?/td>: 201110358461.2
• 申請日: 2011-10-31
• 公開（公告）號: CN102567453A
• 公開（公告）日: 2012-07-11
• 發(fā)明（設(shè)計）人: C·S·弗里德曼;C·J·坎寧安
• 申請（專利權(quán)）人: 微軟公司
• 主分類號: G06F17/30
• 分類號: G06F17/30
• 代理公司: 上海專利商標(biāo)事務(wù)所有限公司 31100
• 代理人: 楊潔

技術(shù)領(lǐng)域

本發(fā)明涉及數(shù)據(jù)庫，尤其涉及在多版本數(shù)據(jù)庫系統(tǒng)中的萬圣夜保護(hù)(Halloween?protection)。

背景技術(shù)

背景和相關(guān)技術(shù)

計算機(jī)和計算系統(tǒng)已經(jīng)影響到了現(xiàn)代生活的幾乎每個方面。計算機(jī)通常在工作、消遣、保健、運(yùn)輸、娛樂、家政管理等中都有涉獵。

計算系統(tǒng)中的數(shù)據(jù)通常存儲在一個或多個數(shù)據(jù)庫中。數(shù)據(jù)庫是相關(guān)數(shù)據(jù)的集合。數(shù)據(jù)庫中的數(shù)據(jù)通常以二維的行和列的形式(稱為表格)來組織的。數(shù)據(jù)庫通常包括多個表格和多個關(guān)聯(lián)結(jié)構(gòu)。表格是數(shù)據(jù)庫中的對象，包括零個或更多記錄以及在每個記錄中的至少一個字段。記錄可被實現(xiàn)為表格中的行，所述記錄被稱為記錄標(biāo)識符的唯一數(shù)字所標(biāo)識。字段是記錄的細(xì)分，在這個意義上而言，表格中的一列數(shù)據(jù)代表表格中的每個記錄的相同字段。數(shù)據(jù)庫中的關(guān)聯(lián)結(jié)構(gòu)的示例是索引，通常，但不是必須的，B樹或散列索引的形式。關(guān)聯(lián)結(jié)構(gòu)對數(shù)據(jù)庫的用戶透明，但是對高效操作和控制數(shù)據(jù)庫管理系統(tǒng)是重要的。數(shù)據(jù)庫管理系統(tǒng)是支持?jǐn)?shù)據(jù)庫特征的控制系統(tǒng)，數(shù)據(jù)庫特征包括但不限于，將數(shù)據(jù)存儲在存儲介質(zhì)上，從存儲介質(zhì)檢索數(shù)據(jù)，以及更新存儲介質(zhì)上的數(shù)據(jù)。

查詢用于訪問或更新數(shù)據(jù)庫中的數(shù)據(jù)。查詢通常以結(jié)構(gòu)化查詢語言(SQL)的變體來構(gòu)造，該變體可以或可以不符合美國國家標(biāo)準(zhǔn)協(xié)會(ANSI)標(biāo)準(zhǔn)SQL定義。SQL查詢是非程序性的，因為它以對用戶有意義的語言來指定目標(biāo)或期望的查詢結(jié)果，但不定義查詢應(yīng)該被實現(xiàn)的步驟或過程。當(dāng)SQL查詢被用于數(shù)據(jù)庫時，數(shù)據(jù)庫管理系統(tǒng)的查詢優(yōu)化器處理該非程序性查詢以創(chuàng)建執(zhí)行計劃。執(zhí)行計劃是程序性的，因為它確定為實現(xiàn)SQL查詢的目標(biāo)所要執(zhí)行的運(yùn)算和算子的次序和類型。非程序性更新請求(SQL查詢)和程序性執(zhí)行計劃的組合創(chuàng)建了查詢優(yōu)化器對執(zhí)行計劃的自動計劃的機(jī)會和需求。查詢優(yōu)化器可為任何給定的SQL查詢生成多個不同的查詢計劃，并且通常配置為按照高效目標(biāo)生成查詢計劃。

更新是對數(shù)據(jù)庫中的數(shù)據(jù)執(zhí)行的通用類型的查詢。更新是修改數(shù)據(jù)庫中的現(xiàn)存記錄及插入和刪除數(shù)據(jù)庫中的記錄的任何操作。如此處所使用的，更新包括任何數(shù)據(jù)庫修改，包括值的修改(狹義更新)、插入、刪除、更新插入(upsert)(更新和插入的組合，如果數(shù)據(jù)庫中存在就更新或者如果不存在就插入)、合并等。執(zhí)行計劃的語義可用SLQ語言的ANSI/ISO標(biāo)準(zhǔn)來規(guī)定。根據(jù)該標(biāo)準(zhǔn)，任何更新語句的語義與執(zhí)行的三個獨立階段相同，各階段之間沒有重疊。首先，數(shù)據(jù)庫的只讀搜索確定要更新、插入，或刪除的記錄以及新列值。其次，更新記錄和列。第三，驗證為數(shù)據(jù)庫定義的一致性約束。

對表格中的記錄的更新還包括對索引中的索引條目及與所更新表格相關(guān)聯(lián)的其他關(guān)聯(lián)結(jié)構(gòu)的更新。對關(guān)聯(lián)結(jié)構(gòu)的改變，實際上關(guān)聯(lián)結(jié)構(gòu)它們本身，通常對用戶不可見，因為它們因執(zhí)行計劃的程序性執(zhí)行而引起。

每當(dāng)定位了滿足查詢表述的記錄時，使用每次一記錄(record-at-a-time)流水線操作(pipelining)的算子完全處理(即產(chǎn)生)輸出。使用每次一組(set-at-a-time)流水線操作的算子消耗它的全部輸入，并僅在那時從該算子中產(chǎn)生輸出。每次一記錄的處理在小的表間關(guān)系(cardinality)改變的傳統(tǒng)系統(tǒng)中可能更高效。大的表間關(guān)系的改變可能用每次一組的方法更高效，因為它可利用順序IO而非針對傳統(tǒng)盤驅(qū)動器的隨機(jī)IO來排序記錄并執(zhí)行改變。

在數(shù)據(jù)庫更新領(lǐng)域存在被稱為萬圣夜問題(Halloween?problem)的具體問題。自從IBM的San?Jose研究實驗室的研究人員在1975年的萬圣節(jié)前夜首次注意到它，萬圣夜問題已經(jīng)是公知的了。數(shù)據(jù)庫系統(tǒng)中的萬圣夜問題在產(chǎn)生了不正確結(jié)果的數(shù)據(jù)修改語句(插入、更新，和刪除)中可能是明顯的，因為修改數(shù)據(jù)庫狀態(tài)的過程改變了執(zhí)行語句的行為，并促使其修改了錯誤的一組記錄(歸因于跳過記錄或歸因于多次修改相同記錄)。

萬圣夜問題的典型示例是對“給薪水超過$30,000的所有員工5％的提高”的請求(SQL查詢)。如果(i)使用對薪水的索引來發(fā)現(xiàn)這些員工，以及(ii)以薪水遞增次序掃描索引條目，以及(iii)掃描不能區(qū)分該請求已經(jīng)更新的索引條目以及那些還未更新的條目，以及(iv)當(dāng)找到索引條目時立刻更新索引(每次一記錄流水線)，那么每個有資格的員工將獲得無限數(shù)量的提高。因此，處理該請求將不會終止。