CISE Postdoctoral Research Associates in Experimental Computer Science: Demand Propagation in Labeled Logic Programming Systems

9901602 Ramakrishnan，C.R.Ramakrishnan，I.V.Kifer，MichaelWarren，David S.纽约州立大学石溪分校实验计算机科学博士后研究助理：表逻辑编程系统中的需求传播表查询求值-我们的XSB逻辑编程系统的定义特征-消除了PROLOG式SLDNF解析的大部分缺陷。当XSB在表模式下运行时，系统自动维护一个包含谓词调用及其响应的表，该表用于在第一次调用之后对谓词进行的所有等价调用。当前表逻辑编程系统的实现计算表子目标的所有答案，而不考虑是否确实需要所有的答案来正确地回答最高目标。我们已经确定了一个我们称为需求传播的概念，该概念可以构成在表解决的上下文中的“无关”不确定性的理论和实现的基础。在这种方法中，程序员可以释放对目标的需求(例如，在返回的答案显示负的子目标为FALSE之后)，在这种情况下，只有当存在对这些答案的其他需求时，才会评估该目标及其子目标。这个概念可以很好地解决我们在XSB应用中出现的几个搜索问题。在该项目的支持下，博士后助理正在开发一个基于需求传播的表逻辑编程系统的理论基础和实现。生成的系统将用于在两个正在进行的研究项目中进行复杂的优化，即在我们基于XSB的模型检查器中使用偏序缩减进行搜索空间裁剪，以及在演绎数据库中减少查询评估时间。

9901602 Ramakrishnan, C.R. Ramakrishnan, I.V.Kifer, MichaelWarren, David S.State University of New York at Stony BrookCISE Postdoctoral Research Associates in Experimental Computer Science: Demand Propagation in Tabled Logic Programming Systems Tabled query evaluation - the defining feature of our XSB logic programming system - eliminates most of the drawbacks of Prolog-style SLDNF resolution. When XSB runs in the tabled mode, the system automatically maintains a table of predicate invocations and their answers, using the table for all equivalent calls to the predicate made after the first call. Current implementations of tabled logic programming systems compute all the answers to a tabled subgoal, regardless of whether all answers are actually needed to correctly answer the top goal.We have identified a concept we call demand propagation which can form the basis of a theory and implementation of "don't care" nondeterminism in the context of tabled resolution. In this approach a programmer can release demand on a goal (for example, after an answer has been returned which shows a negative subgoal in false), in which case that goal and its subgoals will only be evaluated if there are other demands for there answers. This concept can elegantly solve several search problems that have arisen in our application of XSB.The postdoctoral associate supported by the project is developing both the theoretical underpinnings as well as implementation of a tabled logic programming system based on demand propagation. The resulting system will be used for doing sophisticated optimizations in two on-going research projects, namely, search space pruning using partial-order reduction in our XSB-based model checker, and reducing query evaluation times in deductive databases.