home *** CD-ROM | disk | FTP | other *** search
/ Complete Linux / Complete Linux.iso / docs / apps / database / ingres04.lzh / source / qrymod / norml.c < prev    next >
Encoding:
C/C++ Source or Header  |  1985-01-23  |  6.9 KB  |  367 lines
  1. # include    <ingres.h>
  2. # include    <aux.h>
  3. # include    <tree.h>
  4. # include    <symbol.h>
  5. # include    <sccs.h>
  6.  
  7. SCCSID(@(#)norml.c    8.1    12/31/84)
  8.  
  9. extern QTREE    *treedup();
  10. extern char    *need();
  11.  
  12.  
  13. /*
  14. ** NORML
  15. **    this routine passes the qualification clause portion of the query
  16. **    tree to the routines for depressing nots and for conjunctive 
  17. **    normalization.  It also calls a routine to place an and with one
  18. **    null branch at the rightmost end of the tree.
  19. */
  20.  
  21. QTREE *
  22. norml(ptr)
  23. QTREE    *ptr;
  24. {
  25.     extern QTREE    *nnorm();
  26.     extern QTREE    *travers();
  27.     extern QTREE    *tree();
  28.  
  29. #    ifdef xQTR2
  30.     if (tTf(73, 0))
  31.         treepr(ptr, "->NORML");
  32. #    endif
  33.  
  34.     if (ptr == NULL)
  35.         return (tree(NULL, NULL, QLEND, 0, 0));
  36.  
  37.     /* push through the 'nots' as far a possible */
  38.     ptr = nnorm(ptr);
  39.  
  40.     /* make tree into conjunctive normal form */
  41.     ptr = travers(ptr);
  42.  
  43.     /* terminate the list on the rightmost branch */
  44.     adjust(&ptr);
  45.  
  46. #    ifdef xQTR3
  47.     if (tTf(73, 2))
  48.         treepr(ptr, "before mvands");
  49. #    endif
  50.  
  51.     /* make 'ands' into a linear list */
  52.     mvands(ptr);
  53.  
  54. #    ifdef xQTR2
  55.     if (tTf(73, 1))
  56.         treepr(ptr, "<-NORML");
  57. #    endif
  58.  
  59.     return (ptr);
  60. }
  61.  
  62.  
  63. /*
  64. ** NORM
  65. **    this routine takes a tree which has nots only at the lower ends, and
  66. **    places it into conjunctive normal form by repeatedly applying the
  67. **    replacement rule: A or (B and C) ==> (A or B) and (A or C)
  68. */
  69. QTREE *
  70. norm(p1)
  71. QTREE    *p1;
  72. {
  73.     extern QTREE    *tree();
  74.     register QTREE    *p;
  75.     register QTREE    *lptr;
  76.     register QTREE    *rptr;
  77.  
  78.     p = p1;
  79.     switch (p->sym.type)
  80.     {
  81.       case AND:
  82.         p->left = norm(p->left);
  83.         p->right = norm(p->right);
  84.         break;
  85.  
  86.       case OR:
  87.         if (p->right->sym.type == AND)
  88.         {
  89.         andright:
  90.             /*
  91.             ** combine left subtree with each subtree of the
  92.             ** right subtree
  93.             */
  94.             /*
  95.             ** use copy first so that the copy is guaranteed to be
  96.             ** the same as the original
  97.             */
  98.             lptr = tree(treedup(p->left), p->right->left, OR, 0, 0);
  99.             rptr = tree(p->left, p->right->right, OR, 0, 0);
  100.             lptr = norm(lptr);
  101.             rptr = norm(rptr);
  102.             /* change node type to AND from OR */
  103.             p->left = lptr;
  104.             p->right = rptr;
  105.             p->sym.type = AND;    /* length is same */
  106.             break;
  107.         }
  108.         if (p->left->sym.type == AND)
  109.         {
  110.         andleft:
  111.             /*
  112.             ** combine right subtree with each subtree of the
  113.             ** left subtree
  114.             */
  115.             /*
  116.             ** again, the copy should be used first
  117.             */
  118.             lptr = tree(p->left->left, treedup(p->right), OR, 0, 0);
  119.             rptr = tree(p->left->right, p->right, OR, 0, 0);
  120.             lptr = norm(lptr);
  121.             rptr = norm(rptr);
  122.             /* change node type to AND from OR */
  123.             p->left = lptr;
  124.             p->right = rptr;
  125.             p->sym.type = AND;
  126.             break;
  127.         }
  128.         /*
  129.         ** when TRAVERS is being used to optomize the normalization
  130.         ** order there should never be (I think) an OR as a child
  131.         ** of the OR in the parent.  Since TRAVERS works bottom up
  132.         ** in the tree the second OR level should be gone.
  133.         */
  134.         if (p->right->sym.type == OR)
  135.         {
  136.             /* skip this (p->sym.type) "or" and normalize the right subtree */
  137.             p->right = norm(p->right);
  138.  
  139.             /* now re-try the current node */
  140.             if (p->right->sym.type == AND)
  141.                 goto andright;
  142.             break;
  143.         }
  144.         if (p->left->sym.type == OR)
  145.         {
  146.             /* skip this "or" and normalize the left subtree */
  147.             p->left = norm(p->left);
  148.  
  149.             /* now re-try the current node */
  150.             if (p->left->sym.type == AND)
  151.                 goto andleft;
  152.             break;
  153.         }
  154.         break;
  155.     }
  156.     return (p);
  157. }
  158.  
  159. /*
  160. ** TRAVERS
  161. **    traverse the tree so that conversion of ORs of ANDs can
  162. **    take place at the innermost clauses first.  IE, normalize
  163. **    before replication rather than after replication.
  164. **
  165. **    This routine need not be used.  The NORM routine will completely
  166. **    traverse the tree and normalize it but...    TRAVERS finds
  167. **    the lowest subtree to normalize first so that sub-trees can
  168. **    be normalized before replication, hence reducing the time required
  169. **    to normalize large trees.  It will also make OR-less trees faster
  170. **    to normalize (since nothing need be done to it).
  171. */
  172. QTREE *
  173. travers(p1)
  174. QTREE    *p1;
  175. {
  176.     register QTREE    *p;
  177.     extern QTREE    *norm();
  178.  
  179.     p = p1;
  180.     if (p->right != NULL)
  181.         p->right = travers(p->right);
  182.     if (p->left != NULL)
  183.         p->left = travers(p->left);
  184.     if (p->sym.type == OR)
  185.         p = norm(p);
  186.     return (p);
  187. }
  188. /*
  189. ** NNORM
  190. **    this routine depresses nots in the query tree to the lowest possible
  191. **    nodes.  It may also affect arithmetic operators in this procedure
  192. */
  193. QTREE *
  194. nnorm(p1)
  195. QTREE    *p1;
  196. {
  197.     extern QTREE    *notpush();
  198.     register QTREE    *p;
  199.  
  200.     p = p1;
  201.     if (p->sym.type == AGHEAD)
  202.     {
  203.         /*
  204.         ** don't need to continue past an AGHEAD
  205.         ** actually, it causes problems if you do
  206.         ** because the qualification on the agg
  207.         ** has already been normalized and the
  208.         ** QLEND needs to stay put
  209.         */
  210.         return (p);
  211.     }
  212.     if ((p->sym.type == UOP) && (p->sym.value.sym_op.opno == opNOT))
  213.     {
  214.         /* skip not node */
  215.         p = p->right;
  216.         p = notpush(p);
  217.     }
  218.     else
  219.     {
  220.         if (p->left != NULL)
  221.             p->left = nnorm(p->left);
  222.         if (p->right != NULL)
  223.             p->right = nnorm(p->right);
  224.     }
  225.     return (p);
  226. }
  227.  
  228. /*
  229. ** NOTPUSH
  230. **    this routine decides what to do once a not has been found in the
  231. **    query tree
  232. */
  233. QTREE *
  234. notpush(p1)
  235. QTREE    *p1;
  236. {
  237.     extern QTREE    *nnorm();
  238.     register QTREE    *p;
  239.  
  240.     p = p1;
  241.     switch (p->sym.type)
  242.     {
  243.       case AND:
  244.         p->sym.type = OR;
  245.         p->left = notpush(p->left);
  246.         p->right = notpush(p->right);
  247.         break;
  248.  
  249.       case OR:
  250.         p->sym.type = AND;
  251.         p->left = notpush(p->left);
  252.         p->right = notpush(p->right);
  253.         break;
  254.  
  255.       case BOP:
  256.         switch (p->sym.value.sym_op.opno)
  257.         {
  258.           case opEQ:
  259.             p->sym.value.sym_op.opno = opNE;
  260.             break;
  261.  
  262.           case opNE:
  263.             p->sym.value.sym_op.opno = opEQ;
  264.             break;
  265.  
  266.           case opLT:
  267.             p->sym.value.sym_op.opno = opGE;
  268.             break;
  269.  
  270.           case opGE:
  271.             p->sym.value.sym_op.opno = opLT;
  272.             break;
  273.  
  274.           case opLE:
  275.             p->sym.value.sym_op.opno = opGT;
  276.             break;
  277.  
  278.           case opGT:
  279.             p->sym.value.sym_op.opno = opLE;
  280.             break;
  281.  
  282.           default:
  283.             syserr("strange BOP in notpush '%d'", p->sym.value.sym_op.opno);
  284.         }
  285.         break;
  286.  
  287.       case UOP:
  288.         if (p->sym.value.sym_op.opno == opNOT)
  289.         {
  290.             /* skip not node */
  291.             p = p->right;
  292.             p = nnorm(p);
  293.         }
  294.         else
  295.             syserr("strange UOP in notpush '%d'", p->sym.value.sym_op.opno);
  296.         break;
  297.  
  298.       default:
  299.         syserr("unrecognizable node type in notpush '%d'", p->sym.type);
  300.     }
  301.     return (p);
  302. }
  303.  
  304. /*
  305. ** ADJUST
  306. **    terminate qual with an AND and a QLEND at the rightmost branch
  307. */
  308. adjust(pp)
  309. QTREE    **pp;
  310. {
  311.     extern QTREE    *tree();
  312.     register QTREE    *p;
  313.  
  314.     p = *pp;
  315.     switch (p->sym.type)
  316.     {
  317.       case AND: 
  318.         adjust(&(p->right));
  319.         break;
  320.  
  321.       case OR:
  322.       default:
  323.         *pp = tree(p, tree(NULL, NULL, QLEND, 0, NULL), AND, 0, 0);
  324.         break;
  325.     }
  326. }
  327.  
  328. QTREE *
  329. treedup(p)
  330. register QTREE    *p;
  331. {
  332.     register QTREE    *np;
  333.     extern char    Qbuf[];
  334.  
  335.     if (p == NULL)
  336.         return (p);
  337.     np = (QTREE *) need(Qbuf, (p->sym.len & I1MASK) + QT_HDR_SIZ);
  338.     bmove(p, np, (p->sym.len & I1MASK) + QT_HDR_SIZ);
  339.     np->left = treedup(p->left);
  340.     np->right = treedup(p->right);
  341.     return (np);
  342. }
  343.  
  344. /*
  345. **    MVANDS -- pushes all AND's in Qual into linear list
  346. */
  347. mvands(andp)
  348. QTREE    *andp;
  349. {
  350.     register QTREE    *ap, *lp, *rp;
  351.  
  352.     ap = andp;
  353.     if (ap->sym.type == QLEND)
  354.         return;
  355.     rp = ap->right;
  356.     lp = ap->left;
  357.     if (lp->sym.type == AND)
  358.     {
  359.         ap->left = lp->right;
  360.         ap->right = lp;
  361.         lp->right = rp;
  362.         mvands(ap);
  363.     }
  364.     else
  365.         mvands(rp);
  366. }
  367.