遞歸查詢(數(shù)據(jù)庫)

時(shí)間：2022-12-17 02:30:02 | 來源：信息時(shí)代

時(shí)間：2022-12-17 02:30:02 來源：信息時(shí)代

    遞歸查詢 : 一種用遞歸的邏輯程序定義的查詢或涉及遞歸規(guī)則求值的查詢。演繹數(shù)據(jù)庫不僅需要處理非遞歸查詢,而且必須處理由邏輯規(guī)則表示的遞歸查詢。因此,遞歸查詢和查詢優(yōu)化處理一直是演繹數(shù)據(jù)庫的重要特性和主要研究課題。傳統(tǒng)數(shù)據(jù)庫及關(guān)系查詢語言通常并不支持遞歸查詢,而且在問題求解系統(tǒng)中會生成無限的一階語言,使執(zhí)行效率降低。由于低效一直是制約遞歸查詢得以廣泛應(yīng)用的關(guān)鍵因素,也是影響數(shù)據(jù)庫效率的重要原因,因此近年來人們對遞歸查詢算法的研究十分關(guān)注,其研究集中在遞歸查詢的表達(dá)方式和尋求復(fù)雜度較低的查詢優(yōu)化算法方面。
1.遞歸查詢算法
遞歸(recursion)是將一個(gè)較大的問題歸約到一個(gè)或多個(gè)子問題的求解過程,這些子問題在結(jié)構(gòu)上與原問題相同,但子問題的求解比原問題簡單。遞歸算法用于演繹數(shù)據(jù)庫的查詢優(yōu)化被稱為遞歸查詢。常用的遞歸查詢算法有:
(1)線性遞歸查詢(linear recursive query): 遞歸查詢中的一個(gè)子類,它通過線性遞歸規(guī)則來實(shí)現(xiàn)查詢。該規(guī)則是指規(guī)則遞歸謂詞在規(guī)則體中出現(xiàn)且僅出現(xiàn)一次的規(guī)則。線性遞歸系統(tǒng)都是由所謂的獨(dú)立規(guī)則組成的。
(2)傳遞閉包查詢(transitive closure query): 一種基于傳遞閉包算法的遞歸查詢方法。傳遞閉包查詢可定義為: 在一組規(guī)則中,若謂詞p出現(xiàn)在規(guī)則頭為謂詞q的規(guī)則的規(guī)則體中,則稱p導(dǎo)出q,記作p→q。這里,“→”是一種傳遞關(guān)系,則記→*為→的傳遞閉包。傳遞閉包查詢被認(rèn)為是新一代數(shù)據(jù)庫系統(tǒng)應(yīng)具備的重要操作,可應(yīng)用于求解“最短路徑”等數(shù)學(xué)難題。常用的傳遞閉包算法有: ①迭代算法(iterative algorithm): 包括半純真、對數(shù)等傳遞閉包算法,其特點(diǎn)是重復(fù)地計(jì)算某一關(guān)系代數(shù)表達(dá)式,直至沒有新的結(jié)果產(chǎn)生為止; ②直接算法(direct algorithm): 包括基于矩陣和基于圖的算法。前者將傳遞閉包的計(jì)算轉(zhuǎn)化為矩陣的表示與操作;后者則將閉包的計(jì)算變?yōu)閳D的遍歷求解問題。直接算法的特點(diǎn)是對每一個(gè)元素(例如一個(gè)結(jié)點(diǎn)或一條邊)只計(jì)算一次;③混合型算法:綜合各種傳遞閉包算法而形成的一種傳遞閉包算法,用于遞歸查詢,如可以將基于矩陣和基于圖的算法綜合成一種混合型的傳遞閉包算法。
(3) Datalog遞歸查詢: 采用純Horn子句的Datalog語言實(shí)現(xiàn)的遞歸查詢方法,包括: 可分離(separable)、右線性(right linear)、可變換(commutable)、可分解(factorable)等各種遞歸查詢的優(yōu)化算法。
(4) 自底向上的遞歸優(yōu)化(bottom-up recursive optimization):一種遞歸查詢算法,又稱為前向鏈接(forward chaining)或不動點(diǎn)(fixpoint)算法。其作法是: 從已知事實(shí)出發(fā),不斷地應(yīng)用規(guī)則進(jìn)行搜索,直至獲得查詢結(jié)果。該算法一般都采用“一次一個(gè)集合”的方法,它與Prolog所采用的“一次一個(gè)記錄”的方式正好對應(yīng)。多數(shù)自底向上的遞歸算法是魔集、半純真算法的擴(kuò)展。后來,J.F.Naughton等人相繼提出了“滑動式窗口制表”和“利用規(guī)則順序”等優(yōu)化算法,前者用于克服存儲空間開銷大和效率低的問題;而后者用來優(yōu)化邏輯程序的不動點(diǎn)求值問題。
2.遞歸查詢的實(shí)現(xiàn)
遞歸查詢的實(shí)現(xiàn)是通過構(gòu)造遞歸謂詞、遞歸規(guī)則和遞歸邏輯程序來實(shí)現(xiàn)的。
(1)遞歸謂詞: 指直接或間接地由自身定義的謂詞。如果存在一個(gè)規(guī)則r,其頭部謂詞為q,并且謂詞p出現(xiàn)在r的規(guī)則體中,則稱謂詞p導(dǎo)出謂詞q,記作p→q。令→+表示→的非自反的傳遞閉包,即如果p→q,則p→+q; 如果存在謂詞s使得p→s且s→+q,則p→+q。如果p→+p,則稱謂詞p為遞歸謂詞; 否則,稱p為非遞歸謂詞。如果p→+q,并且q→+p,則稱p和q是相互遞歸的。
(2)遞歸規(guī)則: 指規(guī)則體中包含遞歸子目標(biāo)的規(guī)則。設(shè)規(guī)則r的頭部謂詞為q。如果與q相互遞歸的謂詞p出現(xiàn)在r的規(guī)則體中,則稱規(guī)則r為遞歸規(guī)則; 否則,稱r為基本規(guī)則。如果r的規(guī)則體中僅出現(xiàn)一個(gè)與q相互遞歸的謂詞p,并且p僅在r的規(guī)則體中出現(xiàn)一次,則稱r為線性遞歸規(guī)則; 其他遞歸規(guī)則稱為非線性遞歸規(guī)則。
(3)遞歸邏輯程序: 簡稱遞歸(recursion)。如果邏輯程序P包含遞歸規(guī)則,則稱P是遞歸的邏輯程序,簡稱遞歸。如果邏輯程序P包含遞歸規(guī)則,并且所有遞歸規(guī)則都是線性的,則稱P為線性遞歸程序,簡稱線性遞歸。如果邏輯程序P包含非線性的遞歸規(guī)則,則稱P為非線性遞歸。
設(shè)邏輯程序P₁包含如下規(guī)則:
r₁:path(X,Y):-arc(X,Y)。
r₂:path(X,Y):-arc(X,Z),path(Z,Y)。
謂詞path是遞歸謂詞,而謂詞arc是非遞歸謂詞。規(guī)則r₁是非遞歸規(guī)則,而規(guī)則r₂是遞歸規(guī)則,并且是線性的。這樣,邏輯程序P₁是一個(gè)遞歸,并且線性遞歸。
如果又設(shè)邏輯程序P₂包含如下規(guī)則:
r₁:path(X,Y):-arc(X,Y)。
r₃: path(X,Y):-path(X,Z),path(Z,Y)。
這里,規(guī)則r₃是一個(gè)非線性遞歸規(guī)則,而邏輯程序P₂是一個(gè)非線性遞歸。
3.線性遞歸中的特殊子類
線性遞歸中有一些比較實(shí)用的特殊子類——右線性遞歸、左線性遞歸和混合線性遞歸。這些遞歸的定義都只涉及一個(gè)遞歸謂詞,且該遞歸謂詞與特定的約束模式相關(guān)聯(lián)。
如果一個(gè)遞歸邏輯程序只包含單個(gè)IDB謂詞p,并且它的所有規(guī)則或者是基本規(guī)則,或者是關(guān)于約束模式α左線性的,則稱該邏輯程序是關(guān)于約束模式α左線性的,簡稱左線性遞歸。類似地,如果一個(gè)遞歸邏輯程序只包含單個(gè)IDB謂詞p,并且它的所有規(guī)則或者是基本規(guī)則,或者是關(guān)于約束模式α右線性的,則稱該邏輯程序是關(guān)于約束模式α右線性的,簡稱右線性遞歸?；旌暇€性遞歸是既包含左線性規(guī)則,又包含右線性規(guī)則的遞歸。
對于一個(gè)線性遞歸規(guī)則,不能簡單地根據(jù)遞歸子目標(biāo)出現(xiàn)在規(guī)則體的左部還是右部來判斷它是左線性的還是右線性的,還必須考慮約束模式。
對前述遞歸規(guī)則r₂,如果給定的約束模式為bf,即規(guī)則r₂頭部的第一個(gè)變元是被約束的,而第二個(gè)變元是自由的。這時(shí),確實(shí)r₂是右線性的,從而,邏輯程序P₁關(guān)于約束模式bf是右線性遞歸。但是,如果給定的約束模式為fb,則在給定的子目標(biāo)次序下,r₂的遞歸子目標(biāo)path(Z,Y)約束模式為bb。因此,關(guān)于約束模式fb,r₂不是右線性的。然而,如果將r₂的遞歸子目標(biāo)移到規(guī)則體的左部,得到:r′₂:path(X,Y):-path(Z,Y),arc(X,Z),則r′₂關(guān)于約束模式fb是左線性的。而邏輯程序P₁關(guān)于約束模式fb則是右線性遞歸。