ylfink@water.UUCP (ylfink) (12/15/86)
Subject: CS, U of W, Dr. J. Han on "Handling Redundancy in the Processing of Recursive Database Queries", Wed., Dec. 17/86, 3:30.
Newsgroups: uw.talks,ont.events
Distribution: uw
Keywords: Knowledge Base Seminar
DEPARTMENT OF COMPUTER SCIENCE
UNIVERSITY OF WATERLOO
SEMINAR ACTIVITIES
KNOWLEDGE BASE SEMINAR
- Wednesday, December 17, 1986.
Dr. Jiawei Han of Northwestern University will speak on
``Handling Redundancy in the Processing of Recursive
Database Queries''.
TIME: 3:30 PM
ROOM: MC 5158
ABSTRACT
The elimination of redundant or duplicated database
accessing is a challenging task in recursive query
optimization. Redundancy may exist in the processing
of recursive database queries at four different levels:
precompilation level, iteration level, tuple processing
level and file accessing level. Techniques for reduc-
ing redundant work at each level are studied. In the
precompilation level, the techniques discussed include
the removal of redundant parts in a rule cluster, the
simplification of complexity of rule clusters, and the
sharing of common subexpressions among rules. At the
iteration level, the techniques discussed are the use
of frontier relations and the counting method. At the
tuple processing level, we develop the techniques of
merging and filtering to exclude processed drivers from
database reaccessing. Finally, at the file accessing
level, I/O cost can be further reduced by level relaxa-
tion. We conclude that even for complex recursion,
redundant database processing can be considerably
reduced or eliminated by developing appropriate algo-
rithms.