MARS

MARS Home

MARS Overview

People

MARS Live!

· MARS Demo

MARS Documentation

· MARS Manual
· Research Papers
· Related Research Papers
· Presentations

Tech. Center

· Download MARS
· MARS CVS server

The Chase

The chase is the fundamental method enabling fully query optimization and possibilities for rewriting.

Intuitively, a chase step consists in making a given constraint redundant by extending the query to satisfy it. Consider, for example, the query Q, asking for the price of beers offered in some pubs:

    SELECT  X = b.price
    FROM    Beers  b,  Pubs  p
    WHERE   b.beername = p.beername

and the constraint C that introduces an additional relation, View, containing redundant information about price and location:

All (a in Beers) All (c in Pubs) 
  if (a.name = c.beername) 
  then Some (v in View) (v.price = a.price) AND (v.Location = c.Location)

Then, by chasing Q with C, we obtain a new query:

    SELECT  X = b.price
    FROM    Beers  b,  Pubs  p, View w
    WHERE   b.beername = p.beername AND w.price = b.price AND
            w.Location = p.Location

Variables bound by the All quantifier were mapped using the homomorphism:

    a => b
    c => p

This function is extended to the variable bound by the Some quantifier, creating a new variable w which was added to the query:

    v => w

Since C does not fire again, if there are no other constraints, the chase would stop here or else, it continues with any other applicable constraint.

Attention! A chase sequence can be infinite if the constraints re-enable each other recursively.

The Translation

The result of the chase from the previous example led to a query plan which mentions three relations: Beers, Pubs, View. This is, of course, worse than the original query Q, but it presents the advantage that we can select subqueries out of it in order to do minization or rewriting-using-views (translation).

For instance, supposing that we want a query only about View, we would keep the parts of the query referring to this relation:

    SELECT  X = w.price
    FROM    View w

It is then again the job of the system to check that the resulting translation is equivalent to the original, which in this case would be ensured by the presence of a constraint such as:

All (b in Beers) All (p in Pubs) 
  if (b.beername = p.beername) 
  then Some (v in View) (v.price = b.price) AND (v.Location = p.Location)

which in a certain sense is the inverse of C.

The Backchase

Looking at the constraints and using the chase can also be used to minimize the queries.
For instance, if there is a constraint saying that any of the beers in the database can be found in a pub

All (b in Beers) Some (p in Pubs) (b.name = p.beername);

then the query Q could be reduced to

    SELECT  X = b.price
    FROM    Beers  b

This is equivalent to the original query because, if chased with the integrity constraint above, it would lead to Q. More generally, the backchase consists in selecting subqueries of a given query and verifying their equivalence to the initial one through the chase.

Putting everything together, a typical application for MARS would consist in chasing an input query with a set of constraints, possibly translate it to a schema which presents more interest and then minimize it by backchase.

Go back

MARS Home Page | MARS Demo