FLEXIBLE ADJUSTMENT OF DATA: AN EXERCISE IN RELATIONAL ALGEBRA

Abstract

Databases may exhibit many forms of incompleteness. This paper explores methods for overcoming incompleteness in the form of missing tuples. Specifically, algorithms are investigated for replacing a relation that is known to be incomplete with a superset. Of particular interest are algorithms that make available at any time a current approximation and with the property that the approximate solution improves monotonically with computing time. Although this paper concentrates on rule matching in rule-based systems, application of these and similar methods to problems of knowledge discovery in incomplete databases is also discussed.

INDEX TERMS:

• Relational algebra
• flexible algorithm
• anytime algorithm
• rule-based systems

Notes

Michael Pittarelli attended the University of Chicago from 1973 to 1976. He received a B.A. in Philosophy from Binghamton University in 1978 and M.A. in Philosophy from the University of Chicago in 1979. He received an M.S. and Ph.D. in Advanced Technology from Binghamton University in 1983 and 1988, respectively. In 1992, he received the William Goodell Research Creativity Award from the State University of New York Institute of Technology, where he is an Associate Professor and Chairperson of the Computer Science Department. He was a Visiting Associate Professor in the Department of Computer Science at the University of Rochester during the 1990-1991 academic year. He is a contributing editor of ACM SIGART Bulletin. His current research interests are in resource-bounded inference and decision making.