魔集(數(shù)據(jù)庫(kù))

時(shí)間：2022-11-03 14:30:01 | 來(lái)源：信息時(shí)代

時(shí)間：2022-11-03 14:30:01 來(lái)源：信息時(shí)代

    魔集 : 一種通用的遞歸查詢優(yōu)化技術(shù),也稱作魔集技術(shù)。該技術(shù)將遞歸查詢處理分成規(guī)則改寫(xiě)和規(guī)則求值兩個(gè)階段。在規(guī)則改寫(xiě)階段,將通過(guò)魔集變換構(gòu)造一組新規(guī)則(稱作魔集規(guī)則),新規(guī)則并不一般地等價(jià)于原規(guī)則,但卻能正確回答查詢。規(guī)則改寫(xiě)是在編譯時(shí)完成的。查詢求值階段采用自底向上算法,如半樸質(zhì)計(jì)算,對(duì)新規(guī)則求值,得到查詢的回答。
從狹義上講,魔集是指變換后的規(guī)則自底向上處理時(shí)產(chǎn)生的魔謂詞對(duì)應(yīng)關(guān)系的元組集。這種元組集恰是查詢的規(guī)則/目標(biāo)樹(shù)擴(kuò)展時(shí)傳遞到IDB目標(biāo)結(jié)點(diǎn)的約束集。由于它們限制了IDB謂詞的求值范圍,壓縮了導(dǎo)出元組的數(shù)量,從而使變換后的規(guī)則自底向上求值產(chǎn)生“魔術(shù)”般的效果。
1986年,F. Bancilhon等針對(duì)線性規(guī)則給出了魔集變換算法。1987年,C.Beeri和R.Ramakrishnan給出了基本魔集算法的一般形式。1988年,R.Ramakrishnan進(jìn)一步拓廣了魔集變換,給出了廣義魔集變換,用來(lái)處理帶函數(shù)詞的規(guī)則。這些變換算法通稱魔集算法。
1. 魔集變換
魔集技術(shù)的核心是魔集變換。魔集變換引進(jìn)了兩類IDB謂詞: 魔謂詞和輔助謂詞。
(1)魔謂詞對(duì)應(yīng)的關(guān)系是魔集,模擬約束沿規(guī)則/目標(biāo)樹(shù)自頂向下傳遞。對(duì)于每個(gè)IDB謂詞p都有一個(gè)魔謂詞,記作m_p。①對(duì)于基本魔集變換,m_p的變?cè)獙?duì)應(yīng)于p的唯一約束模式中被約束的變?cè)?②對(duì)于廣義魔集變換,m_p與p的變?cè)嗤?br>(2)輔助謂詞對(duì)應(yīng)于輔助關(guān)系,模擬約束沿規(guī)則子目標(biāo)自左向右傳遞。如果規(guī)則r_i有k個(gè)子目標(biāo),則引入k個(gè)輔助謂詞sup_i,j(0≤j≤k-1)。對(duì)于基本魔集變換,輔助謂詞sup_i.j的變?cè)莚_i這樣的一些變量,它們?cè)谝?guī)則r_i的頭部被約束(根據(jù)頭部的唯一約束模式),或者出現(xiàn)在r_i的前j個(gè)子目標(biāo)中,并且還出現(xiàn)在次后的子目標(biāo)或規(guī)則頭部中。對(duì)于廣義魔集變換,輔助謂詞帶有更多的約束信息。輔助謂詞sup_i.j的變?cè)獙?duì)應(yīng)于出現(xiàn)在r_i頭部的所有變量和r_i的前j-1個(gè)子目標(biāo)中,并且還出現(xiàn)在r_i的第j個(gè)子目標(biāo)或次后子目標(biāo)的所有變量中。
2.魔集規(guī)則
通過(guò)魔集變換可為新的IDB謂詞創(chuàng)建規(guī)則,并對(duì)原來(lái)的IDB謂詞創(chuàng)建新的規(guī)則。魔集變換所產(chǎn)生的規(guī)則稱作魔集規(guī)則。有以下幾種情況: ①對(duì)于每個(gè)魔謂詞m_p,如果謂詞p出現(xiàn)在規(guī)則r_i的第j個(gè)子目標(biāo)中,則為m_p創(chuàng)建一個(gè)用輔助謂詞sup_i.j-1定義的規(guī)則。②對(duì)于每個(gè)規(guī)則r_i,如果規(guī)則r_i定義謂詞p,則規(guī)則r_i的第零個(gè)輔助謂詞sup_0.j用魔謂詞m_p定義,而r_i的第j(>0)個(gè)輔助謂詞sup_i.j用sup_i.j-1和r_i的第j個(gè)子目標(biāo)定義。③對(duì)于每個(gè)謂詞p,如果規(guī)則r_i定義謂詞p的規(guī)則,包含k個(gè)子目標(biāo),則用r_i的第k-1個(gè)輔助謂詞sup_i.k-1和r_i的最后一個(gè)子目標(biāo)取代r_i的規(guī)則體,創(chuàng)建一個(gè)新規(guī)則。④為查詢謂詞q的魔謂詞m_q創(chuàng)建一個(gè)初始化規(guī)則。這是一個(gè)形如m_q(t₁,…,t_m)事實(shí),其中t₁,…,t_m是查詢中的常量。
如果我們定義“同代人”的規(guī)則:
r₁:sg(X,X):-person(X);
r₂:sg(X,Y):-parent(X,X_p),sg(X_p,Y_p),parent(Y,Y_p)。
其中,sg為IDB謂詞,person和parent為EDB謂詞。規(guī)則r₁表示每個(gè)人都與自己是同代人,而規(guī)則r₂表示如果X_p是X的父母,Y_p是Y的父母,并且X_p和Y_p是同代人,則X和Y是同代人。查詢“sg(‘李明’ ,Y)?”求李明的同代人。對(duì)于給定的查詢和規(guī)則r₁、r₂,則通過(guò)基本魔集變換將產(chǎn)生如下魔集規(guī)則:
m_sg(X_p):-sup_2.1(X,X_p);
sup_1.0(X):-m_sg(X);
sup_2.0(X):-m_sg(X);
sup_2.1(X,X_p):-sup_2.0(X),parent(X,X_p);
sup_2.2(X,Y_p):-sup_2.1(X,X_p),sg(X_p,Y_p);
sg(X,X):-sup_1.0(X),person(X);
sg(X,Y):-sup_2.2(X,Y_p),parent(Y,Y_p);
m_sg(‘李明’)。
經(jīng)魔集變換會(huì)產(chǎn)生許多規(guī)則,變換后的規(guī)則用來(lái)回答查詢要比采用原來(lái)的魔集規(guī)則更為有效。此外,還可通過(guò)對(duì)魔集規(guī)則化簡(jiǎn)來(lái)減少輔助謂詞的個(gè)數(shù)和中間關(guān)系的計(jì)算與存放來(lái)提高規(guī)則的處理效率和查詢處理速度。魔集變換的思想廣泛用于左線性、右線性、混合線性和計(jì)數(shù)線性遞歸等各種線性遞歸查詢處理。