4.3BSD - /usr/ingres/source/qrymod/norml.c

   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: }

Defined functions