魔集(数据库)

时间：2022-11-03 14:30:01 | 来源：信息时代

时间：2022-11-03 14:30:01 来源：信息时代

    魔集 : 一种通用的递归查询优化技术,也称作魔集技术。该技术将递归查询处理分成规则改写和规则求值两个阶段。在规则改写阶段,将通过魔集变换构造一组新规则(称作魔集规则),新规则并不一般地等价于原规则,但却能正确回答查询。规则改写是在编译时完成的。查询求值阶段采用自底向上算法,如半朴质计算,对新规则求值,得到查询的回答。
从狭义上讲,魔集是指变换后的规则自底向上处理时产生的魔谓词对应关系的元组集。这种元组集恰是查询的规则/目标树扩展时传递到IDB目标结点的约束集。由于它们限制了IDB谓词的求值范围,压缩了导出元组的数量,从而使变换后的规则自底向上求值产生“魔术”般的效果。
1986年,F. Bancilhon等针对线性规则给出了魔集变换算法。1987年,C.Beeri和R.Ramakrishnan给出了基本魔集算法的一般形式。1988年,R.Ramakrishnan进一步拓广了魔集变换,给出了广义魔集变换,用来处理带函数词的规则。这些变换算法通称魔集算法。
1. 魔集变换
魔集技术的核心是魔集变换。魔集变换引进了两类IDB谓词: 魔谓词和辅助谓词。
(1)魔谓词对应的关系是魔集,模拟约束沿规则/目标树自顶向下传递。对于每个IDB谓词p都有一个魔谓词,记作m_p。①对于基本魔集变换,m_p的变元对应于p的唯一约束模式中被约束的变元;②对于广义魔集变换,m_p与p的变元相同。
(2)辅助谓词对应于辅助关系,模拟约束沿规则子目标自左向右传递。如果规则r_i有k个子目标,则引入k个辅助谓词sup_i,j(0≤j≤k-1)。对于基本魔集变换,辅助谓词sup_i.j的变元是r_i这样的一些变量,它们在规则r_i的头部被约束(根据头部的唯一约束模式),或者出现在r_i的前j个子目标中,并且还出现在次后的子目标或规则头部中。对于广义魔集变换,辅助谓词带有更多的约束信息。辅助谓词sup_i.j的变元对应于出现在r_i头部的所有变量和r_i的前j-1个子目标中,并且还出现在r_i的第j个子目标或次后子目标的所有变量中。
2.魔集规则
通过魔集变换可为新的IDB谓词创建规则,并对原来的IDB谓词创建新的规则。魔集变换所产生的规则称作魔集规则。有以下几种情况: ①对于每个魔谓词m_p,如果谓词p出现在规则r_i的第j个子目标中,则为m_p创建一个用辅助谓词sup_i.j-1定义的规则。②对于每个规则r_i,如果规则r_i定义谓词p,则规则r_i的第零个辅助谓词sup_0.j用魔谓词m_p定义,而r_i的第j(>0)个辅助谓词sup_i.j用sup_i.j-1和r_i的第j个子目标定义。③对于每个谓词p,如果规则r_i定义谓词p的规则,包含k个子目标,则用r_i的第k-1个辅助谓词sup_i.k-1和r_i的最后一个子目标取代r_i的规则体,创建一个新规则。④为查询谓词q的魔谓词m_q创建一个初始化规则。这是一个形如m_q(t₁,…,t_m)事实,其中t₁,…,t_m是查询中的常量。
如果我们定义“同代人”的规则:
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谓词。规则r₁表示每个人都与自己是同代人,而规则r₂表示如果X_p是X的父母,Y_p是Y的父母,并且X_p和Y_p是同代人,则X和Y是同代人。查询“sg(‘李明’ ,Y)?”求李明的同代人。对于给定的查询和规则r₁、r₂,则通过基本魔集变换将产生如下魔集规则:
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(‘李明’)。
经魔集变换会产生许多规则,变换后的规则用来回答查询要比采用原来的魔集规则更为有效。此外,还可通过对魔集规则化简来减少辅助谓词的个数和中间关系的计算与存放来提高规则的处理效率和查询处理速度。魔集变换的思想广泛用于左线性、右线性、混合线性和计数线性递归等各种线性递归查询处理。