張引紅

(咸陽職業(yè)技術(shù)學(xué)院，咸陽 712000)

0 引言

分布式數(shù)據(jù)庫系統(tǒng)是基于集中式數(shù)據(jù)庫技術(shù)的計(jì)算機(jī)網(wǎng)絡(luò)技術(shù)，其和集中式數(shù)據(jù)庫的主要區(qū)別就是：分布式數(shù)據(jù)庫數(shù)據(jù)為分散性存儲(chǔ)到網(wǎng)絡(luò)不同場所中，而且不同場地?cái)?shù)據(jù)庫的處理能力各有不同。還能夠在局部完成功能應(yīng)用，另外每個(gè)場地都要參與到全局應(yīng)用程序執(zhí)行過程中，全局應(yīng)用程序是利用已有網(wǎng)絡(luò)拓?fù)鋵?shí)現(xiàn)通信，從而對各場地?cái)?shù)據(jù)進(jìn)行訪問。在實(shí)際應(yīng)用及操作過程中是無法感受到分布式網(wǎng)絡(luò)存在，操作也屬于整體數(shù)據(jù)庫。以此表示分布式數(shù)據(jù)庫物理方面是在各網(wǎng)絡(luò)節(jié)點(diǎn)中分散，但是在邏輯方面還是相同數(shù)據(jù)庫系統(tǒng)數(shù)據(jù)集。以此就使其在優(yōu)化過程中和集中數(shù)據(jù)庫系統(tǒng)不同。因?yàn)榉植际綌?shù)據(jù)庫系統(tǒng)數(shù)據(jù)冗余性和分散性，從而就導(dǎo)致查詢處理優(yōu)化存在復(fù)雜性。在實(shí)際使用過程中，分布式查詢處理與優(yōu)化在項(xiàng)目周期中具有重要的作用。

1 分布式數(shù)據(jù)庫查詢優(yōu)化代價(jià)

分布式數(shù)據(jù)庫技術(shù)具有集中性和分布性的特點(diǎn)，其分布性主要指的是在數(shù)據(jù)在網(wǎng)絡(luò)中屬于跨結(jié)點(diǎn)物理存儲(chǔ)，集中性指的是用戶邏輯中屬于簡單且同構(gòu)數(shù)據(jù)庫。和分布式進(jìn)行對比，集中式數(shù)據(jù)庫管理系統(tǒng)要求邏輯和物理兩方面都相互集中。所以，分布式數(shù)據(jù)庫還能夠定義成為物理中分布，邏輯中集中的共享數(shù)據(jù)集合。分布式數(shù)據(jù)庫管理系統(tǒng)屬于數(shù)據(jù)管理軟件，利用分布式數(shù)據(jù)庫管理系統(tǒng)能夠提高分布式數(shù)據(jù)庫分布特點(diǎn)的透明度。

在集中式數(shù)據(jù)庫中，因?yàn)橄到y(tǒng)大部分都是在單個(gè)處理器計(jì)算機(jī)中運(yùn)行，一個(gè)查詢執(zhí)行預(yù)期代價(jià)屬于I/O代價(jià)與CPU代價(jià)結(jié)合。在分布式數(shù)據(jù)庫系統(tǒng)中，一個(gè)查詢包括多電站，查詢處理還要對站點(diǎn)之間數(shù)據(jù)傳輸?shù)耐ㄐ刨M(fèi)用進(jìn)行全面的考慮，對于不同通信類型具有不同的查詢處理算法。在遠(yuǎn)程通信網(wǎng)絡(luò)中，查詢局部處理時(shí)間和通信時(shí)間進(jìn)行對比，可以不對其進(jìn)行計(jì)算。所以，一般都是將降低傳輸次數(shù)及數(shù)據(jù)量作為優(yōu)化的主要目標(biāo)。在高速局域網(wǎng)中，傳輸時(shí)間要比處理時(shí)間短，所以一般都要將響應(yīng)時(shí)間作為主要的優(yōu)化目標(biāo)。響應(yīng)時(shí)間不僅和通信時(shí)間具有密切的聯(lián)系，并且還和局部的處理時(shí)間具有密切的聯(lián)系。但是局部處理時(shí)間屬于關(guān)鍵內(nèi)容，所以此問題的主要內(nèi)容就是要降低局部的處理時(shí)間。

通過以上描述就可以了解到，分布式查詢總代價(jià)包括通信代價(jià)、CPU代價(jià)和I/O代價(jià)，那么通信代價(jià)就能夠通過CO+C1*X進(jìn)行計(jì)算。其中CO指的是兩個(gè)站點(diǎn)之間通信初始化的一次花費(fèi)時(shí)間；X指的是數(shù)據(jù)傳輸?shù)牧?，C1指的是傳輸速率[1]。

2 分布式數(shù)據(jù)查詢的處理模式

集中式數(shù)據(jù)庫系統(tǒng)主要包括內(nèi)模式、外模式和概念模式構(gòu)成，分布式數(shù)據(jù)庫系統(tǒng)的模式結(jié)構(gòu)主要包括局部數(shù)據(jù)模式和全局?jǐn)?shù)據(jù)模式，分布式數(shù)據(jù)庫的結(jié)構(gòu)，如圖1所示。

圖1 分布式數(shù)據(jù)庫的結(jié)構(gòu)

局部數(shù)據(jù)模式指的是各個(gè)站點(diǎn)中局部數(shù)據(jù)庫系統(tǒng)模式的結(jié)構(gòu)，其中具備集中式數(shù)據(jù)庫系統(tǒng)三級模式結(jié)構(gòu)。全局?jǐn)?shù)據(jù)模式的主要目的就是對局部數(shù)據(jù)模式進(jìn)行有效的協(xié)調(diào)，使其能夠成為整體模式結(jié)構(gòu)。

全局?jǐn)?shù)據(jù)模式包括全局外、全局概念和分片模式、分布模式構(gòu)成，其中全局外模式指的是全局使用的用戶視圖，屬于全局概念模式邏輯的子集；全局概念指的是分布式數(shù)據(jù)庫全局?jǐn)?shù)據(jù)邏輯的結(jié)構(gòu)；分片模式指的是使全局關(guān)系分解成為多個(gè)不相交部分，也就是數(shù)據(jù)分片。分片模式指的是片段和全局關(guān)系之間的映象，此種映象指的是一對多，也就是每個(gè)片段都是全局關(guān)系，但是全局關(guān)系能夠分解成為多個(gè)片段；其中分布模式指的是通過數(shù)據(jù)分片得出的片段還是分布式數(shù)據(jù)庫數(shù)據(jù)，其屬于全部關(guān)系邏輯的部分，每個(gè)分片物理中都能夠一個(gè)或者多個(gè)站點(diǎn)中進(jìn)行分配或者定位。分布模式能夠以選擇的數(shù)據(jù)實(shí)現(xiàn)策略有效分配，對片段物理存放站點(diǎn)進(jìn)行定義。分布模式中定義映象的類型能夠?qū)Ψ植际綌?shù)據(jù)庫數(shù)據(jù)分配的冗余進(jìn)行有效確定，如果映象屬于一對多，也就是片段到多站點(diǎn)充分存放進(jìn)行分配，那么此數(shù)據(jù)分配屬于冗余。相反，就是不冗余。

分布式環(huán)境查詢類型主要包括遠(yuǎn)程查詢、本地查詢及全局查詢，本地查詢也就是局部查詢，其和集中式數(shù)據(jù)庫優(yōu)化技術(shù)相同。其中遠(yuǎn)程查詢指的是單點(diǎn)數(shù)據(jù)遠(yuǎn)程通信，如果數(shù)據(jù)屬于冗余分配，要降低查詢處理通信代價(jià)，就要選擇距離查詢節(jié)點(diǎn)發(fā)出最近節(jié)點(diǎn)中的數(shù)據(jù)，或者還可以將數(shù)據(jù)片實(shí)現(xiàn)查詢。全局查詢指的是實(shí)現(xiàn)多點(diǎn)數(shù)據(jù)查詢，其主要流程為：對查詢對象進(jìn)行確定，之后以可用訪問路徑及算法對二元操作連接進(jìn)行有效確定，最后實(shí)現(xiàn)執(zhí)行節(jié)點(diǎn)的確定，要對通信代價(jià)、查詢速度及執(zhí)行效率進(jìn)行全面的考慮。

總而言之，要實(shí)現(xiàn)查詢處理策略的有效荀澤，對必要物理片段進(jìn)行確定從而有效實(shí)現(xiàn)查詢，并且還要對查詢過程中各個(gè)操作的執(zhí)行站點(diǎn)進(jìn)行確定。另外，實(shí)現(xiàn)分布式數(shù)據(jù)庫查詢的優(yōu)化還與算法操作具有密切的聯(lián)系[2]。

3 分布式數(shù)據(jù)庫查詢優(yōu)化算法

3.1 查詢樹和生成樹

對關(guān)系模式R進(jìn)行定義，使其為有限屬性集{A1，A2，…,An}，在關(guān)系模式中的實(shí)例R屬于從模式R到數(shù)據(jù)域的映射，此映射表示為{t1，t2，…，tn}。假如B屬于R的屬性，那么就表示為t.B。此表達(dá)式指的是等值相互連接的條件：R.B=S.C，為了能夠?qū)ふ易顑?yōu)連接策略，將查詢語句q進(jìn)行定義。雖然兩個(gè)數(shù)據(jù)之間可能會(huì)具有一個(gè)或者多個(gè)連接條件，但是并不對查詢圖是否為多邊圖進(jìn)行全面考慮。另外，將查詢語句中兩個(gè)關(guān)系R和S在連接的過程中所使用條件變動(dòng)為clauses(e，q)，查詢圖如圖2所示。

圖2 查詢圖

3.2 代價(jià)模型

在實(shí)現(xiàn)查詢連接操作的過程中，在關(guān)系R的某個(gè)屬性及屬性集中實(shí)現(xiàn)哈希劃分，那么此屬性就為part(R)，在對其進(jìn)行假設(shè)查詢執(zhí)行之前，此屬性只包括單個(gè)的元素幾何，也就是在一個(gè)屬性中實(shí)現(xiàn)哈希劃分。為了能夠?qū)Ψ植际讲樵儾呗杂行赃M(jìn)行分析，創(chuàng)建模型將查詢過程中的關(guān)系連接代價(jià)進(jìn)行全面反映。在分布式查詢過程中，為了能夠使響應(yīng)時(shí)間縮短，就可以尋找查詢圖小代價(jià)單條件生成樹QGTreeq，因?yàn)镼GTreeq代價(jià)不僅與連接操作關(guān)系大小和哈希劃分過程中參照屬性具有密切的聯(lián)系，其還與多個(gè)條件表達(dá)式中兩兩關(guān)系連接順序具有密切的聯(lián)系。那么要尋找最佳條件表達(dá)式序列。單條件生成樹QGTreeq最小的代價(jià)為：

QGTreeq=min{Cost(cs)} cs∈CS

假如查詢條件表達(dá)式通過查詢語句中其他的表達(dá)式進(jìn)行推導(dǎo)，那么此條件表達(dá)式就是冗余條件表達(dá)式。全面考慮QGTreeq冗余表達(dá)式，就能夠得到最佳的條件表達(dá)式序列，分別為{R.A,T.D},{T.E,S.C},{T.E,U.F}，其總代價(jià)為8k。以此表示，分布式查詢優(yōu)化過程中只考慮查詢圖QGTreeq并不夠，所以就要使用優(yōu)化算法實(shí)現(xiàn)。

3.3 優(yōu)化算法

定義查詢q屬于QGq中的一條鏈，其就是鏈查詢。本文使用動(dòng)態(tài)編程技術(shù)CHAIN算法有效解決鏈查詢中的MRP問題。通過此算法，能夠?qū)Σ樵兪褂玫年P(guān)系最佳連接徐磊進(jìn)行計(jì)算，以此降低連接代價(jià)，縮短查詢響應(yīng)時(shí)間。

比如，QGq最小的代價(jià)條件表達(dá)序列為c5、c3、c4，和其相互對應(yīng)的查詢圖優(yōu)化結(jié)果為R、T、S、U。簡單來說，最優(yōu)關(guān)系連接順序就是，R/T，其連接條件為c5，其次為RT/S，其連接條件為c3，最后為RS和U相互連接，其連接條件為c4。

在根據(jù)查詢語句條件表達(dá)式對兩條關(guān)系相互連接的過程中，要選擇最小代價(jià)表達(dá)式實(shí)現(xiàn)連接，并且代價(jià)和本地連接使用的代價(jià)與劃分代價(jià)相同。本地連接代價(jià)與兩個(gè)關(guān)系大小的和具有密切的關(guān)系，在確定連接關(guān)系之后，此部分代價(jià)就是固定的，并且條件表達(dá)式?jīng)]有關(guān)系。

3.4 算法實(shí)例

使用以下查詢，其包括的條件表達(dá)式為：

c1={R1.A,R2.B}

c2={R2.C,R3.D}

c3={R2.E,R3.F}

c4={R2.G,R4.H}

另外，CHAIN算法的實(shí)例數(shù)據(jù)，使用CHAIN算法尋找最小代價(jià)和相應(yīng)關(guān)系連接順序，如表1所示。

表1 CHAIN算法的實(shí)例數(shù)據(jù)

查詢優(yōu)化結(jié)果表示，如表2所示。

表2 實(shí)驗(yàn)結(jié)果

需要優(yōu)化的最小代價(jià)為1 470，其中的關(guān)系連接順序?yàn)椋簕R2.C,R3.D}、{R3.G,R4.H}、{R2.B,R1.A}[3]。

4 總結(jié)

查詢優(yōu)化算法指的是分布式數(shù)據(jù)庫研究過程中的主要問題，本文對分布式查詢優(yōu)化代價(jià)及處理過程進(jìn)行了全面的分析，掌握了對分布式查詢優(yōu)化影響的優(yōu)化因素，并且對分布式查詢優(yōu)化中的策略及算法進(jìn)行了有效的闡述。一般，查詢優(yōu)化算法并不是萬能且通用的，對于查詢算法選擇主要包括：是否滿足大數(shù)據(jù)量需求、是否能夠滿足異構(gòu)數(shù)據(jù)庫需求；是否能夠?yàn)槿只蛘呔植績?yōu)化；是否能夠滿足高復(fù)雜性需求。對于分布式數(shù)據(jù)查詢問題，相應(yīng)查詢優(yōu)化策略能夠使用到不同應(yīng)用中，從而選擇最省的代價(jià)方案。