Path: utzoo!utgpu!news-server.csri.toronto.edu!bonnie.concordia.ca!clyde.concordia.ca!nstn.ns.ca!news.cs.indiana.edu!samsung!dali.cs.montana.edu!uakari.primate.wisc.edu!zaphod.mps.ohio-state.edu!swrinde!elroy.jpl.nasa.gov!decwrl!pa.dec.com!shodha.enet.dec.com!wahl
From: wahl@shodha.enet.dec.com (David Wahl)
Newsgroups: comp.databases
Subject: Re: Query Optimization (Magic Sets)
Message-ID: <2563@shodha.enet.dec.com>
Date: 19 Feb 91 17:07:39 GMT
Organization: Digital Equipment Corp. - Colorado Springs, CO.
Lines: 41

Most commercially available database managers have some form of query
optimizer, although it may not be a cost-based rewriter.  Magic sets
is a general technique for handling queries which are recursively 
defined.  SQL doesn't allow the specification of recursion, so you
won't find a declarative (i.e., without specifying an execution plan)
way of doing recursion in any commercial relational system.

There are a lot of different wrinkles to the query optimization
problem.  If you are looking for a general introduction to the field,
almost any modern text on relational databases has a chapter on the
subject.  A lot of work on recursive query processing has come from
the field of logic and databases.  If you are interested in magic sets
and related subjects, you might find the chapter on deductive
databases in Valduriez & Gardarin's book on Relational Databases and
Knowledge Bases helpful; it's particularly accessible to the general
reader.

As far as commercialization is concerned, more work is needed to
determine the application needs for recursion in relational queries
and methods for specifying and implementing them which suit
applications programmers and end users.  We have been studying the
problem here; there are several other industrial labs looking at the
problem as well.

Regards,
Dave Wahl
===================================================================
Digital Equipment Corporation
Database Systems Research (CXN1/2)
1175 Chapel Hills Drive
Colorado Springs, CO 80920-2080

Tel 719-260-2758
Email: wahl@cookie.enet.dec.com
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% The opinions expressed are my own, not Digital's.               %
% "I suppose you would have to be very well educated to get that  %
%  kind of job."                                                  %
% "Extremely well educated.  Typing, everything."                 %
% -- Donald Barthelme, "The Emerald"                              %
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%