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: www.cs.albany.edu/~nvm/ritries/ Erik Rosenthal's Web Page: www.newhaven.edu/show.asp?durki=1623 Neil Murray's Web Page: www.cs.albany.edu/~nvm/
