2.11BSD#431 - /usr/ingres/source/parser/norml.c

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

Defined functions