mwang (03/29/83)
DEPARTMENT OF COMPUTER SCIENCE UNIVERSITY OF WATERLOO SEMINAR ACTIVITIES COMPUTER SCIENCE COLLOQUIUM - Wednesday, April 6, 1983. Dr. J. Minker of the University of Maryland will speak on ``On Theories of Definite and Indefinite Data Bases''. TIME: 3.30 PM ROOM: MC 5158 ABSTRACT A database is said to be indefinite if there is an answer to a query of the form P(a) v P(b) where nei- ther P(a) nor P(b) can be derived from the database. Indefinite data bases arise where, in general, the data consists of non-Horn clauses. A clause is non-Horn if it is a disjunction of literals in which more than one literal in the clause is positive. Horn databases, which comprise most databases in ex- istence, do not admit answers of the form P(a) v P(b) where neither P(a) nor P(b) are derivable from the database. It has been shown by Reiter that in such databases one can make an assumption, termed the Closed World Assumption (CWA), such that one can assume P(a) provided there is no proof of P(a). When a database consists of Horn and non-Horn clauses, Reiter has shown that it is sometimes not possible to make the CWA. In this paper we propose a theory of indefinite databases that encompasses conventional relational databases and provides a correct interpretation for negation, indefinite data,and one aspect of the null value problem. The theory extends the definition of the CWA to ap- ply to databases defined by Horn and non-Horn clauses. The assumption needed for such databases is termed the Generalized Closed World Assumption (GCWA). Syntactic and semantic definitions of gen- eralized closed worlds are given. It is shown that the two definitions are equivalent. March 29, 1983