NAME
    Rule.pm -- logical optimization rules.

DESCRIPTION
    The *query transformation rules* are used for the transformation of
    query trees into logically equivalent query trees having different
    syntactical structure and therefore, potentially, a faster method for
    the evaluation of queries. Module *Rule.pm* deals with the rules for
    logical level of the query optimization.

    The logical optimization rules are in Qios specified in a language that
    follows strictly the syntax and the semantics of the Qios query
    expressions. The new constructs are added to the language to be able to
    express transformation rules.

Rules
    A rule is composed of the input pattern and the output pattern. The
    input and output patterns are connected by means of common variables and
    common data sources. The links among the variables define the meaning of
    the rule. The input and output patterns, ie. query expressions, are
    "terminated" using special operators called *spans*. A span is a virtual
    operation which can match any operation defined on sets of objects. The
    rule (i/o) patterns can then be seen, from the perspective of parse
    trees, as the upper parts of query trees with the abstract leaves.

    The examples of the logical transformation rules are presented by the
    currently used rules in Qios which are given at the beginning of the
    module *Rule.pm*.

    The query transformation rules are from the external form (augumented
    query expressions) transformed into the representation which is based on
    the query tree representation of query expressions. The input and output
    patterns of the rule are represented by the input and output query
    trees. These are connected by the links relating variables, data sources
    and parameters of the input and output patterns of rule.

Matching
    Given a query tree and a rule, the matching procedure can be viewed as
    an attempt to cover the root of query tree with the input rule pattern
    ie. query tree. It is realized by a procedure that descends in paralel
    on both query trees and matches the corresponding query nodes. The first
    part of matching completes successfully if all nodes from the input rule
    pattern match the input query tree.

    The second phase of matching is type-checking of the transformed input
    query expression. The construction of transformed query, ie. the target
    rule pattern on top of the matched input query tree, is realized
    together with the successful first phase of matching since the nodes of
    the input and output patterns (query trees) are linked in spans as well
    as thru some operations. The output pattern of the rule can serve as the
    "test" construction on which the type-checking procedure can be
    executed. The rule matches completely if the type-checking routine
    completes successfully.

    The final transformation phase is now easy since the output pattern can
    be simply duplicated and linked to the input query tree at spans.

COMMENTS
    This module is part of the *qios* programming environment.