DATALOG程序的组及其应用  

THE GROUP OF DATALOG PROGRAMS AND ITS APPLICATIONS

作　　者：王云明[1] 施伯乐[1] 

机构地区：[1]复旦大学计算机科学系,上海200433

出　　处：《软件学报》1997年第9期641-646,共6页Journal of Software

基　　金：国家自然科学基金;国家863高科技项目

摘　　要：为了提高DATALOG程序自底向上计值的效率，本文提出了把DATALOG规则分成若干个组，对这些组可以给出一个拓扑序列，而对同一个组内的各个规则可以给出一个激发序列，以此来有效地控制DATALOG程序自底向上计值时对规则的调度，从而提高计算效率．这一技术可以应用于传统的各种自底向上计算方法，本文绘出了半朴质（Semi-Naove）算法和良基模型（Well-Founded）的交替不动点算法（AlternatingFixPoint）的改进．改进后的算法比原算法在时间和空间效率上都有较大的提高．In order to gain more efficiency when calculating a Datalog program bottomup, a suggestion is proposed to divide the set of Datalog rules into the several groups. Areasonable sequence is provided for those groups, and so for rules in the same group aswell. Consequently, according to those sequences scheduling rules will result in more effi-ciency when calculating a Datalog prograrn bottorn-up. This ordering technique can be ap-plied to any traditional bottom-up algorithms, hence the wide application of group. Theauthors put forward some improved versions of certain traditional algorithrns, and they aremore efficient than the previous versions in space and time. It is also pointed out that theconception of group has more applications other than improving bottom-up calculations.

关 键 词：DATALOG程序 组 拓扑序列 激发序列 

分 类 号：TP31[自动化与计算机技术—计算机软件与理论]