支持多種Now語義的SMNE4R樹.pdf

1、隨著計(jì)算機(jī)系統(tǒng)在日常生活及工作中的普及，時(shí)態(tài)信息越來越多的出現(xiàn)在應(yīng)用系統(tǒng)中，且很大一部分是Now相關(guān)的，也即當(dāng)前的。為了存儲(chǔ)和處理大規(guī)模的時(shí)態(tài)數(shù)據(jù)，人們引入時(shí)態(tài)數(shù)據(jù)庫。其中，時(shí)間維可以有兩個(gè)：事務(wù)時(shí)間和有效時(shí)間，其二者是正交的。為了有效地存儲(chǔ)和查詢“當(dāng)前”的時(shí)態(tài)數(shù)據(jù)，需要引入有效時(shí)間變量Now和事務(wù)時(shí)間變量UC。在實(shí)際應(yīng)用中，二者的正交性導(dǎo)致它們在不同的情況下有不同的語義(即取值)。 適合時(shí)態(tài)數(shù)據(jù)的高效的索引技術(shù)對(duì)加快數(shù)據(jù)的查詢

2、和更新速度起著重要的作用。通過分析我們發(fā)現(xiàn)，當(dāng)前流行的時(shí)態(tài)數(shù)據(jù)索引技術(shù)均假設(shè)了事務(wù)時(shí)間與有效時(shí)間的“同步”，這與兩者的正交性相悖，不利于實(shí)際應(yīng)用。本文全面分析由于有效時(shí)間和事務(wù)時(shí)間的正交性所造成的Now的多種語義情形，并提出了事務(wù)時(shí)間提前、滯后、預(yù)測等情況下的Now語義的處理技術(shù)。針對(duì)當(dāng)前較優(yōu)的4R樹作擴(kuò)展和完善，提出“支持多種Now語義的4R樹模型”(SMNE4R)。當(dāng)中重新定義了四種雙時(shí)態(tài)數(shù)據(jù)類型的數(shù)據(jù)變換、查詢變換，使其支持當(dāng)前版

3、本和過去版本數(shù)據(jù)庫中，Now的過去、將來等多種語義，且可作一定程度的預(yù)測查詢。 最后利用通用搜索樹GiST工具包實(shí)現(xiàn)了SMNE4R樹。并用大量由程序隨機(jī)生成的實(shí)驗(yàn)數(shù)據(jù)進(jìn)行實(shí)驗(yàn)，通過比較SMNE4R索引樹與其他幾種索引技術(shù)的磁盤I/O次數(shù)來評(píng)價(jià)它們的查詢和更新性能。實(shí)驗(yàn)表明，SMNE4R樹完善了4R樹的主要缺陷，支持更多的Now語義，同時(shí)在性能上遠(yuǎn)優(yōu)于MTR樹和2R樹，且基本與4R樹相當(dāng)。這表明了擴(kuò)展后的SMNE4R模型是有效的。