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

9901602 Ramakrishnan，C.R. Ramakrishnan，I. V. Kifer，MichaelWarren，大卫S.纽约州立大学石溪分校CISE实验计算机科学博士后研究员：表格逻辑编程系统中的需求传播表格查询评估-我们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.