marina@ai.toronto.edu (Marina Haloulos) (01/13/90)
Department of Computer Science, University of Toronto
(SF = Sandford Fleming Building, 10 King's College Road)
-------------------------------------------------------------
COLLOQUIUM
SF1105, at 11:00 a.m., Tuesday 23 January 1990
Professor Ashok Chandra
Thomas J. Watson Research Center
"Theory of Database Queries"
The theory of database queries was begun by Codd when he showed that
queries expressible by first order predicate calculus were the same as
those expressible using relational algebra. This set a target for query
language designers who aspired to "enough" expressiveness in their
languages. However, some simple queries (such as transitive closure) were
shown not to be expressible in first order logic. There remained the
question of formulating the set of all reasonable (i.e., computable)
queries. It turned out that there is a robust definition of computable
queries, and these can be represented by generalizing the relational
algebra into a programming language.
The talk will address the above, and subsequent development of the theory
of database queries as motivated by logic, complexity theory, AI, and
programming primitives. Examples include the Horn-clause queries
(Datalog), stratified queries, queries defined by fixpoint constructs,
polynomial-time and nondeterministic polynomial-time queries, second-order
queries, queries obtained by iterating on tuples of relations, etc. The
interconnections between these concepts appear to be technically rich and
deep.
Note: This colloquium is supported by the IBM Thomas J. Watson Research
Center, through their "Lecture in Computer Science Program".