[ont.events] UW CS Colloq., Dr. Minker on "On Theories of Definite and Indefinite Data Bases"

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