李 川

(西安航空學(xué)院計(jì)算機(jī)工程系，西安 710077)

隨著信息技術(shù)的高速發(fā)展，數(shù)據(jù)庫技術(shù)已經(jīng)廣泛應(yīng)用于當(dāng)今社會的各行各業(yè)。特別是在生物學(xué)、農(nóng)林業(yè)等領(lǐng)域，需要調(diào)查研究的數(shù)據(jù)量大，而且每個數(shù)據(jù)元組又包含了大量的屬性。對于這些數(shù)據(jù)，各研究機(jī)構(gòu)研究的內(nèi)容和方向不盡相同。如何將這些數(shù)據(jù)做到既邏輯統(tǒng)一又合理分布是一個非常重要的問題。分布式數(shù)據(jù)庫是物理上分布而邏輯上統(tǒng)一的系統(tǒng)。

將大規(guī)模數(shù)據(jù)(包括大規(guī)模關(guān)系或大規(guī)模元組)的數(shù)據(jù)庫建立成分布式數(shù)據(jù)庫系統(tǒng)，由于分布式數(shù)據(jù)庫的分布性和冗余性使得數(shù)據(jù)查詢操作變得復(fù)雜，因此如何提高查詢效率成為分布式數(shù)據(jù)庫研究的重要問題。本文針對大規(guī)模數(shù)據(jù)元組或較多記錄的數(shù)據(jù)，建立分布式數(shù)據(jù)庫模型，詳細(xì)分析了分布式查詢處理的目標(biāo)、數(shù)據(jù)分片體系結(jié)構(gòu)、查詢優(yōu)化方法及改進(jìn)策略。

1 分布式數(shù)據(jù)庫查詢優(yōu)化目標(biāo)

分布式數(shù)據(jù)庫不同于集中式數(shù)據(jù)庫，查詢處理除了考慮CPU代價和I/O代價之外，還應(yīng)包括數(shù)據(jù)在網(wǎng)絡(luò)上的傳輸代價

通信代價估算公式為

其中:C初為初始化的時間，單位為s;R為傳輸率，單位為 bit/s;X為需要傳輸?shù)臄?shù)據(jù)量，單位為 bit［1］。

分布式數(shù)據(jù)庫系統(tǒng)的查詢優(yōu)化有2個準(zhǔn)則［2］:一種準(zhǔn)則以總代價最小為標(biāo)準(zhǔn)，例如在廣域網(wǎng)分布式數(shù)據(jù)庫系統(tǒng)中，忽略CCPU+CI/O，只考慮C通信;另一種準(zhǔn)則以每次查詢的響應(yīng)時間最短為標(biāo)準(zhǔn)，一般應(yīng)用在高速局域網(wǎng)分布式數(shù)據(jù)庫中。

總之，分布式查詢優(yōu)化的準(zhǔn)則是使通信費(fèi)用最低和響應(yīng)時間最短，即以最小的代價在最短的響應(yīng)時間內(nèi)獲得需要的數(shù)據(jù)［3－4］。具體采用哪種準(zhǔn)則需要根據(jù)具體的分布式數(shù)據(jù)系統(tǒng)網(wǎng)絡(luò)結(jié)構(gòu)而定。

2 分布式數(shù)據(jù)庫數(shù)據(jù)分片

2.1 分布式數(shù)據(jù)庫數(shù)據(jù)分片機(jī)制

數(shù)據(jù)分片是分布式數(shù)據(jù)庫的重要特性。數(shù)據(jù)分片把關(guān)系按照用戶需求有效劃分成若干個片段，這些片段可以分布在不同站點(diǎn)上，但在邏輯上是一個整體。常見的分片方式為水平分片和垂直分片。水平分片是將關(guān)系按行橫向以某種條件分為若干個子集;垂直分片是將關(guān)系按列豎向分為若干個子集。實(shí)際劃分時采用水平分片或是垂直分片根據(jù)用戶需求及網(wǎng)絡(luò)的情況具體而定。在本文的應(yīng)用中，一種植物的數(shù)據(jù)記錄規(guī)模較大(超過104條)，且數(shù)據(jù)元組規(guī)模也較大(超過200個屬性列)，由于各個研究機(jī)構(gòu)研究的內(nèi)容及側(cè)重點(diǎn)均不同，因此不能單純地采用水平分片或垂直分片，而應(yīng)采用一種混合型的改進(jìn)算法。

2.2 改進(jìn)的分片機(jī)制

數(shù)據(jù)冗余可提高數(shù)據(jù)的可靠性和查詢效率。首先，為保證數(shù)據(jù)可靠性，將所有數(shù)據(jù)存放在一個數(shù)據(jù)庫，形成一個統(tǒng)一全面的數(shù)據(jù)庫，該數(shù)據(jù)庫為備用數(shù)據(jù)庫。因?yàn)槠鋽?shù)據(jù)規(guī)模較大，查詢效率低，故一般不直接在該庫中進(jìn)行查找，將存放該數(shù)據(jù)的站點(diǎn)稱為備用數(shù)據(jù)庫站點(diǎn);然后，根據(jù)植物的數(shù)據(jù)結(jié)構(gòu)特征和研究機(jī)構(gòu)的需求進(jìn)行水平分片;最后，將水平分片得到的片段分別進(jìn)行垂直分片。分片結(jié)構(gòu)如圖1所示。

圖1 帶有冗余的大規(guī)模數(shù)據(jù)分布式數(shù)據(jù)庫分片結(jié)構(gòu)

3 基于半連接的查詢優(yōu)化算法研究

3.1 分布式數(shù)據(jù)庫數(shù)據(jù)查詢方法

分布式數(shù)據(jù)庫查詢過程一般分為4個步驟:查詢分解、數(shù)據(jù)本地化、全局優(yōu)化和局部優(yōu)化。其中全局優(yōu)化和局部優(yōu)化是2個可以明顯提高查詢效率的過程。局部優(yōu)化是在各站點(diǎn)的數(shù)據(jù)查詢，該過程和普通集中式數(shù)據(jù)庫的查詢優(yōu)化方法相同，故在此不再討論。

在全局優(yōu)化階段，各個站點(diǎn)間的連接運(yùn)算是產(chǎn)生代價的主要操作。而關(guān)于如何處理連接操作，以往的研究提出很多種算法，主要分為基于半連接的查詢優(yōu)化算法和基于直接連接的查詢優(yōu)化算法兩大類。

基于直接連接的查詢一般多用于高速局域網(wǎng)中。由于局域網(wǎng)的網(wǎng)絡(luò)傳輸速度很快，因此可忽略數(shù)據(jù)傳輸?shù)拇鷥r。所采用的方式為一次將所有數(shù)據(jù)傳輸，然后再進(jìn)行查詢。

基于半連接的查詢常用于廣域網(wǎng)環(huán)境下。廣域網(wǎng)一般傳輸速度有限，所以減少2個站點(diǎn)進(jìn)行連接時的傳輸代價是半連接查詢優(yōu)化的關(guān)鍵。通常2個站點(diǎn)間需要2次以上的數(shù)據(jù)傳輸，但總的數(shù)據(jù)傳輸量遠(yuǎn)小于傳輸整個關(guān)系的數(shù)據(jù)量。其基本原理是:在進(jìn)行連接之前，先根據(jù)需求消除與連接無關(guān)的數(shù)據(jù)，減少作為連接的數(shù)據(jù)量，從而減小通信代價。雖然在連接之前所做的消除與連接無關(guān)數(shù)據(jù)的操作也會增加額外的代價，但與減小通信代價相比，還是很小的。

本文主要針對大規(guī)模數(shù)據(jù)廣域網(wǎng)分布式數(shù)據(jù)進(jìn)行庫查詢優(yōu)化，所以重點(diǎn)研究基于半連接的查詢優(yōu)化。

3.2 改進(jìn)的半連接查詢優(yōu)化算法

3.2.1 一般的半連接查詢方法

半連接是投影和連接組成的一種關(guān)系代數(shù)運(yùn)算。假設(shè)R1、R2是2個關(guān)系，分別位于站點(diǎn)S1、S2，而屬性A1、A2分別在R1和R2上，半連接操作可表示為

連接操作可表示為:

其中:∞表示連接操作，∝表示半連接操作，∏表示投影操作。

直接連接是將站點(diǎn)S2中的所有關(guān)系R2一次傳輸給站點(diǎn)S1，而半連接的執(zhí)行過程如表1所示。

表1 半連接執(zhí)行過程

在廣域網(wǎng)分布式數(shù)據(jù)庫系統(tǒng)中，只考慮通信代價，再次忽略網(wǎng)絡(luò)的差異性，即式(2)中的C初和R都一樣。下面根據(jù)式(2)計(jì)算比較使用直接連接和使用半連接方法實(shí)現(xiàn)的代價。

使用直接連接方法:

其中:size(R2)為R2元組的長度;record(R2)為R2的總記錄數(shù)。

根據(jù)表1，使用半連接需要傳輸2次數(shù)據(jù)，分別為:

其中:size(A2)為關(guān)系R2中A2屬性的長度;record(∏A2R2)為關(guān)系R2中屬性A2上投影運(yùn)算后的記錄數(shù);size(R1’)為關(guān)系R1’元組的長度，即R1的長度;record(R’)為關(guān)系R1’的記錄數(shù)。

半連接的總代價為

在大規(guī)模數(shù)據(jù)記錄多字段的數(shù)據(jù)庫結(jié)構(gòu)下，容易得出

因此，在廣域網(wǎng)中通過半連接的查詢方式可大大減小通信代價。

3.2.2 改進(jìn)的半連接查詢優(yōu)化

在一般的半連接查詢中，連接代價主要是2次傳輸?shù)拇鷥r。其中的第一次傳輸，即由站點(diǎn)S2將∏A2R2從S2傳輸?shù)秸军c(diǎn)S1，因?yàn)橹挥幸粋€屬性，所以相對于大規(guī)模數(shù)據(jù)而言其傳輸?shù)臄?shù)據(jù)量較少;第二次傳輸，即由站點(diǎn)S1將R1’傳輸?shù)秸军c(diǎn)S2，需要傳輸?shù)臄?shù)據(jù)元組長度為R1的長度，記錄個數(shù)為R1’的記錄數(shù)。這樣，當(dāng)R1長度很長，R1’記錄很多時，該次傳輸?shù)臄?shù)據(jù)量仍然相當(dāng)大，即帶來了較大通信代價。由此提出一種改進(jìn)的半連接查詢方法。

首先，介紹改進(jìn)半連接查詢中涉及到的幾個概念和理論。

定理1 連接運(yùn)算的交換律。

假設(shè)有關(guān)系 R1和關(guān)系 R2，那么 R1∞R2=R2∞R1，即連接運(yùn)算滿足交換律。

定義1 關(guān)系元組比Rsize。

假設(shè)有關(guān)系 R1和關(guān)系 R2，那么 Rsize=size(R1)/size(R2)，稱為關(guān)系R1和R2的關(guān)系元組比。

定義2 關(guān)系記錄比Rrecord。

假設(shè)有關(guān)系 R1和關(guān)系 R2，那么 Rrecord=record(R1)/record(R2)，稱為關(guān)系R1和 R2的關(guān)系記錄比。

定義3 關(guān)系數(shù)據(jù)比Rdata。

假設(shè)有關(guān)系R1和關(guān)系R2，那么Rdata=Rsize*Rrecord，稱為關(guān)系R1和R2的關(guān)系數(shù)據(jù)比。

由于關(guān)系R1的記錄數(shù)和R1’的記錄數(shù)一般情況下是成正比的，所以可認(rèn)為:

當(dāng)Rdata＞1時，即站點(diǎn)S1上的數(shù)據(jù)量大于站點(diǎn)S2上的數(shù)據(jù)量;

當(dāng)Rdata＜1時，即站點(diǎn)S1上的數(shù)據(jù)量小于站點(diǎn)S2上的數(shù)據(jù)量;

當(dāng)滿足第2種情況時，采用一般的半連接方法是比較合適的，但當(dāng)滿足第1種情況的時候，顯然采用一般半連接的傳輸代價較大。由于連接運(yùn)算滿足交換律，所以可將傳輸?shù)膬?nèi)容改為將R2’從站點(diǎn)S2傳輸?shù)秸军c(diǎn)S1，由此降低了傳輸代價。改進(jìn)的半連接查詢算法過程描述見表2。

表2 改進(jìn)半連接查詢算法過程

3.2.3 算法性能比較

假設(shè)關(guān)系R1和R2的關(guān)系結(jié)構(gòu)如表3所示。

表3 關(guān)系結(jié)構(gòu)

根據(jù)表3得關(guān)系數(shù)據(jù)比為2，按照改進(jìn)的半連接查詢，計(jì)算所需數(shù)據(jù)如表4所示。

表4 改進(jìn)半連接查詢計(jì)算數(shù)據(jù)

由此可以得出2種算法的代價。

一般半連接查詢代價:

改進(jìn)半連接查詢代價:

改進(jìn)半連接查詢算法在數(shù)據(jù)傳輸之前，先進(jìn)行數(shù)據(jù)關(guān)系大小比較(比較所產(chǎn)生的代價可忽略)，保證了實(shí)際傳輸數(shù)據(jù)比較小，從而降低了傳輸代價。

4 結(jié)束語

本文主要分析和研究了分布式數(shù)據(jù)庫的特點(diǎn)、查詢優(yōu)化目標(biāo)、數(shù)據(jù)分片機(jī)制、查詢優(yōu)化的算法等。提出了在廣域網(wǎng)中大規(guī)模數(shù)據(jù)的分布式數(shù)據(jù)庫改進(jìn)的數(shù)據(jù)分片模型及改進(jìn)半連接查詢算法。通過實(shí)例分析表明:改進(jìn)半連接查詢算法極大地降低了傳輸代價，提高了查詢效率。

由于本文提出的改進(jìn)半連接查詢優(yōu)化算法是基于廣域網(wǎng)的大規(guī)模數(shù)據(jù)，因此在高速局域網(wǎng)或者數(shù)據(jù)規(guī)模不大的情況下該算法并不適用。在進(jìn)行連接操作時，當(dāng)要連接的2個數(shù)據(jù)關(guān)系大小差異較大時，采用該算法較適合，反之使用該算法意義不大。另外，本文認(rèn)為在某一關(guān)系上投影操作之后，關(guān)系記錄數(shù)與原關(guān)系記錄數(shù)成正比，這在有些情況下是無法滿足的，因此也會對改進(jìn)算法帶來負(fù)面影響。

［1］石小艷.分布式數(shù)據(jù)庫中的查詢策略與查詢優(yōu)化［J］.計(jì)算機(jī)與網(wǎng)絡(luò)，2010(30):244－245.

［2］姜愛福，李長云.分布式查詢優(yōu)化的技術(shù)實(shí)現(xiàn)［J］.計(jì)算技術(shù)與自動化，2005(1):72－74.

［3］陳鐘.一種改進(jìn)的分布式數(shù)據(jù)庫查詢優(yōu)化算法［J］.計(jì)算機(jī)應(yīng)用，2008(28):233 －235.

［4］陳世保.基于直接連接的分布式數(shù)據(jù)庫查詢優(yōu)化實(shí)現(xiàn)方法研究［J］.計(jì)算機(jī)時代，2011(7):17－20.