動(dòng)態(tài)規(guī)劃的關(guān)鍵算法.docx

動(dòng)態(tài)規(guī)劃的關(guān)鍵算法Mf1432075許耀峰組號(hào)：201. 背景介紹1.1 PostgresSQL中的動(dòng)態(tài)規(guī)劃算法所謂基于代價(jià)的動(dòng)態(tài)規(guī)劃算法，就是窮舉所有可能的查詢的可執(zhí)行的方法，估算它們的代價(jià)，找出一個(gè)代價(jià)嘴角的來(lái)執(zhí)行，這是物理層次的優(yōu)化。在PostgresSQL中，基于代價(jià)的動(dòng)態(tài)規(guī)劃算法應(yīng)用在物理查詢優(yōu)化階段求解最優(yōu)的多表連接路徑。1.2 物理查詢優(yōu)化在查詢優(yōu)化器實(shí)現(xiàn)的早期，使用的是邏輯優(yōu)化技術(shù)，即使用關(guān)系代數(shù)規(guī)則和啟發(fā)式規(guī)則對(duì)查詢進(jìn)行優(yōu)化后，認(rèn)為生成的執(zhí)行計(jì)劃就是最優(yōu)的。在引入了基于代價(jià)的查詢優(yōu)化方式后，對(duì)查詢執(zhí)行計(jì)劃做了定量的分析，對(duì)每一個(gè)可能的執(zhí)行方式進(jìn)行評(píng)估，挑出代價(jià)最小的作為最優(yōu)的計(jì)劃。目前，數(shù)據(jù)庫(kù)的查詢優(yōu)化器通常融合了這兩種方式。2. 多表連接查詢多表連接算法實(shí)現(xiàn)的是在查詢路徑生成的過(guò)程中，根據(jù)代價(jià)估算，從各種可能的候選路徑中找出最優(yōu)的路徑（最優(yōu)路徑是代價(jià)最小的路徑）。多表連接算法需要解決兩個(gè)問(wèn)題：（1） 多表連接的順序：表的不同的連接順序，會(huì)產(chǎn)生許多不同的連接路徑；不同的連接路徑有不同的效率。（2） 多表連接的搜索空間：因?yàn)槎啾磉B接的順序不同，產(chǎn)生的連接組合會(huì)有多種，如果這個(gè)組合的數(shù)目巨大，連接次數(shù)會(huì)達(dá)到一個(gè)很高的數(shù)量級(jí)，最大可能的連接次數(shù)是N ?。∟ 的階乘）2.1多表連接順序多表間的連接順序表示了查詢計(jì)劃樹(shù)的基本形態(tài)。一棵樹(shù)就是一種查詢路徑，SQL 的語(yǔ)義可以由多棵這樣的樹(shù)表達(dá)，從中選擇花費(fèi)最少的樹(shù)，就是最優(yōu)查詢計(jì)劃形成的過(guò)程。而一棵樹(shù)包括左深連接樹(shù)、右深連接樹(shù)、緊密樹(shù)3 種形態(tài)。另外，即使是同一種樹(shù)的生成方式，也有細(xì)節(jié)需要考慮。在圖3-1a 中，A，B 和B，A 兩種連接方式花費(fèi)可能不同。比如最終連接結(jié)果是A，B，C，但是需要驗(yàn)證是A，B，C、A，C，B、B，C，A、B，A，C、C，A，B、C，B，A 中哪一個(gè)連接方式得到的結(jié)果，這就要求無(wú)論是哪種結(jié)果，都需要計(jì)算這6 種連接方式中每一種的花費(fèi)，找出最優(yōu)的一種作為下次和其他表連接的依據(jù)。人們針對(duì)以上樹(shù)的形成、形成的樹(shù)的花費(fèi)代價(jià)最少的，提出了諸多算法。樹(shù)的形成過(guò)程，主要有以下兩種策略：（1）至頂向下。從 SQL 表達(dá)式樹(shù)的樹(shù)根開(kāi)始，向下進(jìn)行，估計(jì)每個(gè)結(jié)點(diǎn)可能的執(zhí)行方法，計(jì)算每種組合的代價(jià)，從中挑選最優(yōu)的。（2）自底向上。從 SQL 表達(dá)式樹(shù)的樹(shù)葉開(kāi)始，向上進(jìn)行，計(jì)算每個(gè)子表達(dá)式的所有實(shí)現(xiàn)方法的代價(jià)，從中挑選最優(yōu)的，再和上層（靠近樹(shù)根）的進(jìn)行連接，周而復(fù) 始直至樹(shù)根。2.2 常用的多表連接算法表與表進(jìn)行連接，對(duì)多表連接進(jìn)行搜索查找最優(yōu)查詢樹(shù)，通常有多種算法，比如啟發(fā)式、分枝界定計(jì)劃枚舉、爬山法、動(dòng)態(tài)規(guī)劃、System R 優(yōu)化方法等。3. 動(dòng)態(tài)規(guī)劃算法3.1 簡(jiǎn)介20 世紀(jì)40 年代，Richard Bellman 最早使用了動(dòng)態(tài)規(guī)劃這一概念，用以表述通過(guò)遍歷尋找最優(yōu)決策解問(wèn)題。“動(dòng)態(tài)規(guī)劃”（dynamic programming）中的programming 來(lái)自“數(shù)學(xué)規(guī)劃”（mathematical programming，又稱規(guī)劃），與“計(jì)算機(jī)編程”（computer programming）中的programming 沒(méi)有關(guān)系。規(guī)劃的含義是指生成活動(dòng)的優(yōu)化策略，規(guī)劃意味著找到一個(gè)可行的活動(dòng)計(jì)劃。動(dòng)態(tài)規(guī)劃，是指決策依賴于當(dāng)前狀態(tài)，又隨即引起狀態(tài)的轉(zhuǎn)移，一個(gè)決策序列就是在變化的狀態(tài)中產(chǎn)生出來(lái)的，這就是“動(dòng)態(tài)”的含義?！皠?dòng)態(tài)規(guī)劃”將待求解的問(wèn)題分解為若干個(gè)子問(wèn)題（子階段），按順序求解子問(wèn)題，前一子問(wèn)題的解為后一子問(wèn)題的求解提供了有用的信息。在求解任一子問(wèn)題時(shí)，列出各種可能的局部解，通過(guò)決策保留那些有可能達(dá)到最優(yōu)的局部解，丟棄其他局部解。依次解決各子問(wèn)題，最后一個(gè)子問(wèn)題就是初始問(wèn)題的解。3.2 動(dòng)態(tài)規(guī)劃的概念i. 階段。把求解問(wèn)題的過(guò)程分成若干個(gè)相互聯(lián)系的階段，以便于求解。在多數(shù)情況下，階段變量是離散的。ii. 狀態(tài)。表示每個(gè)階段開(kāi)始面臨的自然狀況或客觀條件，它不以人們的主觀意志為轉(zhuǎn)移，也稱為不可控因素。iii. 無(wú)后效性。狀態(tài)應(yīng)該具有的性質(zhì)，如果給定某一階段的狀態(tài)，則在這一階段以后過(guò)程的發(fā)展不受這階段以前各段狀態(tài)的影響。iv. 決策。一個(gè)階段的狀態(tài)確定后，從該狀態(tài)演變到下一階段某個(gè)狀態(tài)的選擇（行動(dòng)）稱為決策。v. 策略。由每個(gè)階段的決策組成的序列稱為策略。對(duì)于每一個(gè)實(shí)際的多階段決策過(guò)程，可供選取的策略有一定的范圍限制，這個(gè)范圍稱為允許策略集合。允許策略集合中達(dá)到最優(yōu)效果的策略稱為最優(yōu)策略。vi. 最優(yōu)化原理。如果問(wèn)題的最優(yōu)解所包含的子問(wèn)題的解也是最優(yōu)的，就稱該問(wèn)題具有最優(yōu)子結(jié)構(gòu)，即滿足最優(yōu)化原理。最優(yōu)化原理實(shí)際上是要求問(wèn)題的最優(yōu)策略的子策略也是最優(yōu)的。3.3 動(dòng)態(tài)規(guī)劃的具體實(shí)現(xiàn)在數(shù)據(jù)庫(kù)領(lǐng)域，動(dòng)態(tài)規(guī)劃算法主要解決的是多表連接的問(wèn)題。動(dòng)態(tài)規(guī)劃算法是從底向上進(jìn)行的，即從葉子（單個(gè)表）開(kāi)始算作一層，然后由底層開(kāi)始對(duì)每層的關(guān)系做兩兩連接（如果滿足內(nèi)連接則兩兩連接，不滿足內(nèi)連接則不可對(duì)全部表進(jìn)行兩兩連接操作），構(gòu)造出上層，逐次遞推到樹(shù)根。下面介紹具體步驟。步驟1初始狀態(tài)。構(gòu)造第一層關(guān)系，即葉子結(jié)點(diǎn)，每個(gè)葉子對(duì)應(yīng)一個(gè)單表，為每一個(gè)待連接的關(guān)系計(jì)算最優(yōu)路徑（單表的最優(yōu)路徑就是單表的最佳訪問(wèn)方式，通過(guò)評(píng)估不同的單表的數(shù)據(jù)掃描方式花費(fèi)，找出代價(jià)最小的作為每個(gè)單表的局部最優(yōu)路徑）。步驟2歸納。當(dāng)層數(shù)從第1 到n-1，假設(shè)已經(jīng)生成，則如何求解第n 層的關(guān)系方法有：（1）左深樹(shù)連接方式：將第n-1層的關(guān)系（有多個(gè)關(guān)系）與第一層中的每個(gè)關(guān)系連接，生成新的關(guān)系（對(duì)新關(guān)系的大小進(jìn)行估算），放于第n 層，且每一個(gè)新關(guān)系，均求解其最優(yōu)路徑。（2）緊密樹(shù)連接方式：將第k層的關(guān)系每個(gè)關(guān)系，與第other_level層中的每個(gè)關(guān)系連接，生成新的關(guān)系（新的關(guān)系就存儲(chǔ)著形成這個(gè)關(guān)系的多種局部路徑，從中選出最優(yōu)的一個(gè)局部路徑）放于第n層，且每一個(gè)新的關(guān)系，均求解其最優(yōu)路徑。其中other_level = level k，level為要連接的基表個(gè)數(shù)。以上雖然分為兩步，但實(shí)際上步驟2 多次執(zhí)行，每一次執(zhí)行后生成的結(jié)果被下一次使用，即每層（k層）路徑的生成都是基于下層（k-1層）生成的最優(yōu)路徑的，這滿足最優(yōu)化原理的要求。動(dòng)態(tài)規(guī)劃算法與System R 算法相比，增加了中間關(guān)系的大小估算。還有的改進(jìn)算法，在生成第n 層的時(shí)候，除了通過(guò)第n-1 層和第一層連接外，還可以通過(guò)第n-2 層和第2 層連接，通過(guò)第n-3 層和第3 層連接3.4 緊密樹(shù)處理流程4. 遺傳算法4.1 概念遺傳算法（Genetic Algorithm，GA）是美國(guó)學(xué)者Holland 于1975 年首先提出來(lái)的。它是一種啟發(fā)式的優(yōu)化算法，是基于自然群體遺傳演化機(jī)制的高效探索算法。遺傳算法拋棄了傳統(tǒng)的搜索方式，模擬自然界生物進(jìn)化過(guò)程，采用人工進(jìn)化的方式對(duì)目標(biāo)空間進(jìn)行隨機(jī)化搜索。它將問(wèn)題域中的可能解看作是群體的一個(gè)個(gè)體（染色體），并將每一個(gè)個(gè)體編碼成符號(hào)串形式，模擬達(dá)爾文的遺傳選擇和自然淘汰的生物進(jìn)化過(guò)程，對(duì)群體反復(fù)進(jìn)行基于遺傳學(xué)的操作（選擇、交叉、變異），根據(jù)預(yù)定的目標(biāo)適應(yīng)度函數(shù)對(duì)每個(gè)個(gè)體進(jìn)行評(píng)價(jià)，依據(jù)“適者生存，優(yōu)勝劣汰”的進(jìn)化規(guī)則，不斷得到更優(yōu)的群體，同時(shí)以全局并行搜索方式來(lái)搜索優(yōu)化群體中的最優(yōu)個(gè)體，求得滿足要求的最優(yōu)解。遺傳算法可以有效地利用已經(jīng)有的信息處理來(lái)搜索那些有希望改善解質(zhì)量的串，類似于自然進(jìn)化，遺傳算法通過(guò)作用于“染色體”上的“基因”，尋找好的“染色體”來(lái)求解問(wèn)題（對(duì)算法所產(chǎn)生的每個(gè)“染色體”進(jìn)行評(píng)價(jià)，并基于適應(yīng)度值來(lái)改造“染色體”，使適用性好的“染色體”比適應(yīng)性差的“染色體”有更多的“繁殖機(jī)會(huì)”）。4.2 遺傳算法的具體實(shí)現(xiàn)遺傳算法主要步驟如下：1）隨機(jī)初始化種群；2）評(píng)估初始的種群，即為種群計(jì)算每個(gè)個(gè)體的適應(yīng)值且對(duì)所有個(gè)體排序；3）如果沒(méi)有達(dá)到預(yù)定演化數(shù)（可以是一個(gè)確定的、與連接的表的個(gè)數(shù)無(wú)關(guān)的值，這樣保證搜索空間一定