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