ling@ria.ccs.uwo.ca (Charles X. Ling) (02/08/90)
Friday, February 23, 1990. 2:00 pm. Middlesex College, Room 316
Dr. V.S. Lakshmanan
Department of Computer Science
Concordia University
Montreal, Quebec
will speak on:
QUERY EVALUATION WITH NULL VALUES:
HOW COMPLEX IS COMPLETENESS?
A B S T R A C T
The problem of evaluating queries on a relational database which is allowed
to contain null values has been extensively studied. In general, most of the
schemes to query evaluation in the literature fall into two categories.
Those in the first guarantee that answers to queries can be efficiently
computed ({\it i.e.} in time that is a polynomial in the database size),
while being {\it incomplete} in the sense that they do not compute
all {\it valid} answers to certain queries.
The second kind guarantee {\it completeness} but unfortunately suffer from
{\it intractability}. In this talk, we reexamine the proof-theoretic approach
proposed by Reiter [Reiter 86] (which, as proposed, is incomplete) and present
a ``natural'' interpretation of null values using the notion of {\it null
assignment functions}. We show that while this approach leads to
a complete evaluation scheme, there are ``simple'' queries whose evaluation
under this scheme is co-NP-complete, and thus intractable.
We next propose the notion of {\it feasible completeness} and ask
``is it possible to develop a notion of completeness that is feasible?"
We then propose an approach based on intuitionistic logic,
for query evaluation with nulls. We adapt the intuitionistic notion of
completeness in a way that is relevant to the database context.
We show that this approach is at once feasible ({\it i.e.} all queries
are polynomial time doable under this approach) and complete (in the
sense above). We provide a nonprocedural query language based on the
logic and its procedural counterpart -- an algebra -- and show their
equivalence. The advantages are: our inference system
is extremely simple compared to the inference systems in related
works; the algebra reduces to the traditional relational
algebra when there are no nulls in the database. Thus our system
can be directly implemented on top of existing data management systems
with little fuss.
Coffee and cookies will be served after the colloquium in room 300