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.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.