III-COR: Collaborative Research: Knowledge Compilation with Fast Response

项目名称：基于快速响应pi的知识编译：该项目涉及索引结构的开发、维护和利用——减少隐含尝试（ri-tries）——用于回答大型数据库的逻辑查询。这个项目的主要目标是进一步发展ri- try，识别和分类这些尝试将有效的数据库，以及发展执行ri- try的计算机系统。简化隐含trie是一种用于在计算机上存储命题数据库的数据结构。通过轻松确定数据库的结果（具有yes答案的查询），可以实现对查询的快速响应。从技术上讲，一旦数据库被编译成一个ri-trie，任何查询的响应时间都保证与查询的大小成线性关系，而与编译的数据库的大小无关。这个响应时间代表了性能和空间之间的权衡，因为i- try可能很大。这个项目的中心焦点将是确定哪些类型的数据库适合ri- try。这将通过实验和理论发展来实现。将开发一个将逻辑公式编译成i- try的原型系统和一个查询处理模块。最初，该系统将设计为连接正常形式的数据库；从长远来看，命题逻辑中的任何公式都是可以接受的输入。查询处理器将被设计为接受子句作为输入，因为子句是查询的典型形式。纽黑文大学和纽约州立大学奥尔巴尼分校的学生将积极参与。本项目的RUI部分将由纽黑文大学的本科生广泛参与。向学生介绍自动推理和知识汇编的基本思想，并对原型系统进行操作。我们的目标是通过让学生参与真正的研究，为真正的出版物做出贡献，从而激励他们。PI致力于吸引有才华的青年男女进入数学和计算机科学领域，并为他们进入研究生院做准备。奥尔巴尼大学在计算机科学方面有很强的研究生课程，奥尔巴尼的PI致力于为学生的研究事业做好准备。项目网页：http://www.cs.albany.edu/~nvm/ritries/ Erik Rosenthal的网页：http://www.newhaven.edu/show.asp?durki=1623 Neil Murray的网页：http://www.cs.albany.edu/~nvm/

Abstract Project Title: Knowledge Compilation with Fast Response PIs: This project is concerned with the development, maintenance, and utilization of index structures -- reduced implicate tries (ri-tries) -- that answer logical queries of large databases. The primary goals of this project are further development of ri-tries, identification and classification of databases for which these tries will be effective, and development of computer systems that implement ri-tries. A reduced implicate trie is a data structure for storing a propositional database on a computer. Fast responses to queries are enabled by making it easy to determine consequences -- queries with yes answers -- of the database. Technically, once a database has been compiled into an ri-trie, the response time to any query is guaranteed to be linear in the size of the query, regardless of the size of the compiled database. This response time represents a trade-off between performance and space, since ri-tries may be large. A central focus of this project will be determining what types of databases lend themselves to ri-tries. This will be accomplished through experimentation and through theoretical developments. A prototype system that compiles logical formulas into ri-tries and a query processing module will be developed. Initially, the system will be designed for databases in conjunctive normal form; in the longer term, any formula from propositional logic will be acceptable input. The query processor will be designed to accept clauses as input, since a clause is the typical form for a query. Students at the University of New Haven and at SUNY at Albany will be active participants. Broader Impacts of the Proposed Activity The RUI component of this project will be extensive participation by undergraduates at the University of New Haven. Students will be introduced to the basic ideas of automated deduction and knowledge compilation and will work on the prototype system. The goal is to inspire students by engaging them in real research that contributes to real publications. The PI is committed to attracting talented young men and women into mathematics and computer science and to preparing them for graduate school. The University at Albany has a strong graduate program in computer science, and the PI at Albany is committed to preparing students for careers in research. Project Web Page: http://www.cs.albany.edu/~nvm/ritries/ Erik Rosenthal's Web Page: http://www.newhaven.edu/show.asp?durki=1623 Neil Murray's Web Page: http://www.cs.albany.edu/~nvm/