The reduced implicate trie (ri-trie), developed by the PI's in [12,13], is a data structure that enables fast response to queries of all propositional databases: Once a database is 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 is different from earlier approaches to knowledge compilation, where the goal was a small end product that enabled fast responses. Knowledge compilation was originally proposed by Kautz and Selman~[9]. Their idea was that while compiling a knowledge base D is intractable (unless NP = P), the compilation need be done only once, in an off-line phase. They specified that the compiled database K should be polynomial in the size of D, and query response time should be polynomial in the size of K.

Several authors [1,2,3,4,5,7,8,10,14,15] have developed target languages for compilation that satisfy the second condition but not the first. These efforts typically have linear response times. But linear response time on an exponential compilation is less than satisfactory. While ri-tries also do not meet the first condition, they do guarantee fast query response time, regardless of the size of the trie.

The ri-trie merits further exploration and will be the primary focus of this project.

Implementation.

An algorithm that builds ri-tries from logical formulas was introduced in [12,13]. It will be refined, and a prototype system that compiles logical formulas into ri-tries will be developed. Much of the programming will be done by undergraduate students at the University of New Haven. One value of the prototype will be finding classes of databases with which ri-tries are effective.

Maintenance.

Unless a database is static, updates are necessary. Developing techniques that efficiently update ri-tries when new data is introduced will be a central focus of this project. Maintenance does not appear to have been a part of the original knowledge compilation paradigm.

Other Data Structures.

Are there other data structures that share the search characteristics of the ri-trie? Such data structures may work well with different classes of databases.

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 be doing much of the programming of the prototype system. The goal is to inspire the students by engaging them in real research that contributes to real publications.

The University recognizes the importance of undergraduate participation in research, and the PI is committed to attracting talented young men and women into mathematics and computer science and to preparing them for graduate school. A number of students who might not otherwise have done so have already gone on to graduate school, in large part because of their exposure to the PI's research.

The University at Albany has a strong graduate program in computer science. The PI at Albany is committed to preparing students for a career in research. Two who were mentored by the PI have received distinguished doctoral dissertation awards.

In view of the guaranteed response time of ri-tries, the potential impact on real-world databases is significant.

Keywords: Knowledge compilation; query processing; reduced implicate trie.

References

1. Bryant, R. E., Symbolic Boolean manipulation with ordered binary decision diagrams, ACM Comput. Surv. 24, 3 (1992), 293--318.
   
   
2. Cadoli, M., and Donini, F. M., A survey on knowledge compilation, AI Communications 10 (1997), 137--150.
   
   
3. Darwiche, A., Compiling devices: A structure-based approach, Proc. Int'l Conf. on Principles of Knowledge Representation and Reasoning (KR98), Morgan-Kaufmann, San Francisco (1998), 156--166.
   
   
4. Darwiche, A., Decomposable negation normal form, J.ACM 48,4 (2001), 608--647.
   
   
5. Forbus, K.D. and de Kleer, J., Building Problem Solvers, MIT Press, Cambridge, Mass. (1993).
   
   
6. Hai, L. and Jigui, S., Knowledge compilation using the extension rule, J. Automated Reasoning, 32(2), 93-102, 2004.
   
   
7. Haehnle, R., Murray N.V., and Rosenthal, E. Normal Forms for Knowledge Compilation. Proceedings of the International Symposium on Methodologies for Intelligent Systems, (ISMIS `05, Z. Ras ed.), Lecture Notes in Computer Science, Springer, Vol. 3488, 304-313.
   
   
8. Kautz, H. and Selman, B., A general framework for knowledge compilation, in Proceedings of the International Workshop on Processing Declarative Knowledge (PDK), Kaiserslautern, Germany (July, 1991).
   
   
9. Marquis, P., Knowledge compilation using theory prime implicates, Proc. Int'l Joint Conf. on Artificial Intelligence (IJCAI) (1995), Morgan-Kaufmann, San Mateo, Calif, 837-843.
   
   
10. Duality in Knowledge Compilation Techniques. Proceedings of the International Symposium on Methodologies for Intelligent Systems, (ISMIS `05, Z. Ras ed.), Lecture Notes in Computer Science, Springer, Vol. 3488, 182-190.
    
    
11. Efficient query processing with compiled knowledge bases. Proceedings of the International Conference TABLEAUX 2005 -- Analytic Tableaux and Related Methods, Koblenz, Germany, September 2005. In Lecture Notes in Artificial Intelligence, Springer-Verlag, Vol. 3702, 231-244.
    
    
12. N.V. Murray and E. Rosenthal. Efficient query processing with reduced implicate tries, (to appear), Journal of Automated Reasoning.
    
    
13. Ramesh, A. and Murray, N.V. An application of non-clausal deduction in diagnosis. Expert Systems with Applications 12,1 (1997), 119-126.
    
    
14. Selman, B., and Kautz, H., Knowledge compilation and theory approximation, J.ACM 43,2 (1996), 193-224.