規(guī)則的計算含義(數(shù)據(jù)庫)

時間：2022-12-25 14:30:01 | 來源：信息時代

時間：2022-12-25 14:30:01 來源：信息時代

    規(guī)則的計算含義 : 提供一種“計算”規(guī)則的方法,以告之一個潛在的事實是真還是假。Prolog就是以這種方法定義規(guī)則的含義的。在演繹數(shù)據(jù)庫中,一個規(guī)則被轉(zhuǎn)換為一個左部為關系,右部為關系代數(shù)表達式的方程。對于非遞歸規(guī)則,其對應方程的關系代數(shù)表達式可以直接求值,求值結(jié)果就是該規(guī)則的計算含義。對于遞歸規(guī)則,則需要通過不動點計算,對這些方程求解來得到規(guī)則的計算含義。這里,規(guī)則的計算含義就稱為不動點計算規(guī)則含義。在演繹數(shù)據(jù)庫中,規(guī)則的計算含義遵循規(guī)則的模型論解釋,用規(guī)則的導出方程的不動點定義。
1. 規(guī)則的導出方程
給定一組Datalog規(guī)則(邏輯程序),每個規(guī)則轉(zhuǎn)換成一個Datalog方程,稱為該規(guī)則的導出方程。方程的左部是規(guī)則頭部謂詞對應的關系,方程的右部是由規(guī)則體導出的關系代數(shù)表達式。在Datalog方程中,EDB關系被看作關系常量,而IDB關系被看作關系變量。如,對于規(guī)則:p(X,Y):-q(X,Z),p(Z,Y)。其中p為IDB謂詞,q為EDB謂詞,其對應的關系分別為P和Q。由該規(guī)則導出的Datalog方程為: P(X,Y)=π_X,Y(Q(X,Z)⋈P(Z,Y))。
2.用不動點定義規(guī)則的計算含義
不動點的思想源于數(shù)學領域。1976年,M.H.Van Emden和R.A.Kowalski將不動點引入邏輯程序設計。1982年,A.K.Chandra和D.Harel將不動點的思想引入演繹數(shù)據(jù)庫。以下為引入不動點概念定義算邏輯程序中規(guī)則的計算含義。
給定一組Datalog方程和這組方程涉及的EDB關系R₁,…,R_k。設該方程組涉及的IDB關系為P₁,…,P_m。該Datalog方程組關于R₁,…,R_k的不動點就是使得這些方程都成立的IDB關系P₁,…,P_m的一個解。設S₁＝{P₁⁽¹⁾,…,P_m⁽¹⁾} 和S₂＝{P₁⁽²⁾,…,P_m⁽²⁾}是該方程組的兩個不動點。如果對于1≤i≤m,關系P_i⁽¹⁾都是關系P_i⁽²⁾的子集,則稱S₁小于S₂,記作S₁<S₂。如果S₀是Datalog方程組的一個不動點,并且不存在其他不動點使得SS₀,則稱是該Datalog方程組的一個極小不動點。Datalog方程組的最小不動點是滿足如下條件的不動點:如果S是Datalog方程組的不動點,則SS₀。
對于不含否定詞的Datalog規(guī)則,其導出方程的最小不動點是唯一存在的,它是可以使用規(guī)則由EDB關系導出(證明)的事實集。因此,不含否定詞的Datalog規(guī)則的計算含義用最小不動點定義。
極小不動點可以迭代地求解。設P_i＝1_i(R₁,…,R_k,P₁,…,P_m)(1≤i≤m)是由一組Datalog規(guī)則導出的Datalog方程組,其中P₁,…,P_m是IDB謂詞對應的關系,R₁,…,R_k是EDB謂詞對應的關系,_i(R₁,…,R_k,P₁,…,P_m)定義在EDB關系R₁,…,R_k和IDB關系P₁,…,P_m上的關系表達式。該Datalog方程組的極小不動點可以用如下迭代過程計算: ①令P_i⁰＝{}(1≤i≤m);②對于j=0,1,…,反復地計算P_i^j+1＝_i(R₁,…,R_k,P₁^j,…,P_m^j) (1≤i≤m),直到對于所有的1≤i≤m,P_i^j+1＝P_i^j。{P₁^j,…,P_m^j}即為該Datalog方程組的極小不動點。當Datalog規(guī)則中不含否定詞時,極小不動點是唯一的,{P₁^j,…,P_m^j}就是最小不動點。
用最小不動點定義Datalog規(guī)則的計算含義的方法可以推廣到包含否定詞的Datalog規(guī)則中。然而,如果不限制否定詞的使用,則包含否定詞的Datalog規(guī)則的不動點可能不存在。一種限制否定詞使用的方法是要求包含否定詞的Datalog規(guī)則必須是可分層的。一組規(guī)則是可分層的,如果規(guī)則中的謂詞可以分成若干層,其中層是滿足如下條件謂詞的最大集合: ①如果謂詞定義謂詞p的規(guī)則含有非否定的子目標q(…),則p所在的層不低于q所在的層: ②如果謂詞定義謂詞p的規(guī)則含有否定的子目標q(…), 則p所在的層高于q所在的層。 對于可分層的包含否定詞的Datalog規(guī)則,在求不動點時,可以由低層到高層,逐層對IDB謂詞進行處理。在處理第i層時,低于第i層的IDB謂詞被視為EDB謂詞。這將產(chǎn)生規(guī)則的一個極小不動點——完美不動點(perfect fixed point),并用它定義規(guī)則的計算含義。
另一種處理否定的方法是用膨脹不動點(inflationary fixed point)定義規(guī)則的計算含義。膨脹不動點也可以迭代地計算,但是與計算極小不動點不同,一個事實一經(jīng)導出就不再丟棄。即用P_i^j+1＝P_i^j∪_i(R₁,…,R_k,P₁^j,…,P_m^j) , 而 不 是 用P_i^j+1＝_i(R₁,…,R_k,P₁^j,…,P_m^j)迭代地計算P_i^j+1(1≤i≤m)。當規(guī)則中不含否定詞時,關系代數(shù)表達式_i(1≤i≤m)都是單調(diào)的,
_i(R₁,…,R_k,P₁^j,…,P_m^j)=P_i^j∪_i(R₁,…,R_k,P₁^j,…,P_m^j)膨脹不動點就是最小不動點。然而,在一般情況下,膨脹不動點不一定是最小不動點,但它是極小的。膨脹不動點比分層否定具有更強的表達能力,但是當規(guī)則是可分層的時,用完美不動點定義規(guī)則的計算含義是更好的選擇。
用不動點計算規(guī)則含義的方法還可以推廣到謂詞變元包含函數(shù)詞的規(guī)則。然而,允許函數(shù)作為謂詞的變元時,規(guī)則所定義的謂詞可能是一個無限關系。這時,不可能通過有限次迭代計算邏輯程序的不動點。盡管如此,不動點很好地定義了邏輯程序的語義,并且無限關系中的任何元組都可以在不動點計算的有限步迭代得到。