NAME
    Que.pm -- query tree manipulation and type-checking.

DESCRIPTION
    This package includes the data structures and procedures for the
    representation and manipulation of query trees. Qios uses a single
    representation of queries for parsing, type-checking, optimization and
    query evaluation. The main skeleton of the query tree is fixed after the
    parsing is completed. The skeleton, ie. operations; symbols and links
    among them, is then used during the subsequent phases of the query
    execution for attaching the information relevant for the particular
    phase.

    The main procedure implemented in this module is type-checking which is
    performed on query trees. The query trees are constructed by module
    *Parse.pm* which also retrieves class objects linked to the access
    methods. The module *Que.pm* checks the type of query trees in a
    bottom-up manner starting with access methods progressing toward the
    root node of query tree.

    The type-checking procedure is used also for rule matching procedure
    described with *Rule.pm*. In this case, the successful computation of
    type of query tree denotes formalization of the successful rule
    matching. For this purpose, the type-checking procedure is defined also
    for spans.

Query trees
    A query tree is a graph (dag) which vertices are query nodes. The
    vertices are linked with respect to the parse tree formed during parsing
    of query.

    Query nodes represent the operations, operation parameters, spans
    linking rules, and access methods. The query nodes store the data for
    the different phases of query processing: parsing, type checking,
    optimization, and query evaluation. The data elements of query nodes
    used in *Que.pm* are as follows.

    The basic links among query nodes are generated during parsing. They are
    implemented by using the following data members of query nodes.

        nodOprt    -- type of operator 
        nodOuter   -- outer operand 
        nodInner   -- inner operand (in the case it exists) 
        nodParam   -- predicate of algebraic operation 
        nodName    -- name of node (meaning depends on node type) 

    The parameters of the set operations *select*, *project* and *join* are
    abstracted away by using the separate type of query node. The parameter
    node stores information about the query sub-tree corresponding to the
    parameter expression; it includes references to the root of query
    sub-tree, variables and the references to the data sources of variables.

    The parameter nodes play vital role for the representation of rules as
    well as for the rule matching procedure. The following are the data
    members of parameter nodes used for the representation of the interface
    of parameter expression.

        nodKind    -- kind of param (normal,rule) 
        nodBinded  -- parameter binded to param expression 
        nodVrmap   -- mapping var names to data sources 
        nodPnam    -- list of variable names (ordered by data sources)
        nodPvars   -- list of variable nodes (ordered by parse) 

    Here are some of the remaining important data members of the query nodes
    used for type-checking, query optimization and query evaluation.

        nodType    -- type associated to node 
        nodExpr    -- expr of query rooted in this node 
        nodCval    -- current value for iterator 
        nodSite    -- site of operation 
        nodEquc    -- reference to equiv class of query 

Type-checking
    Type-checking is implemented by procedure computing the types of query
    nodes bottom-up, that is, from access methods toward the root of query
    tree. The class objects related to the access methods are retrieved
    during the parsing process. The computation of the types of the
    particular query nodes is simple since the tuple-structured types are
    flat, that is, they do not include nested structured elements except the
    arrays of scalars. The type of a query node is stored by constructing a
    new class object.

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