4.3BSD - /usr/ingres/source/decomp/reduction.c

   1: # include   <ingres.h>
   2: # include   <symbol.h>
   3: # include   <aux.h>
   4: # include   <tree.h>
   5: # include   "globs.h"
   6: # include   <sccs.h>
   7: 
   8: SCCSID(@(#)reduction.c	8.1	12/31/84)
   9: 
  10: /*
  11: **	Reduction -- This file contains routines related to the
  12: **	reduction algorithm. The routines are all called by
  13: **	decision().
  14: **
  15: **	Included are:
  16: **
  17: **		algorithm -- groups clauses according to common variables
  18: **
  19: **		buildlist -- build linked list of clauses from a query tree
  20: **
  21: **		construct -- build query trees from link lists of clauses
  22: **
  23: **		order     -- order a linked list of clauses into the prefered
  24: **				execution sequence
  25: */
  26: /*
  27: **	Algorithm - determine whether query is connected or not
  28: **
  29: **	Algorithm takes a linked list of query components
  30: **	and groups them according to the variables involved
  31: **	in each component. If the query is fully interconnected
  32: **	then algorithm returns TRUE else it returns FALSE.
  33: **
  34: **	By definition a constant clause (one involving zero variables)
  35: **	is considered to use all variables. Without this rule,
  36: **	a query with a null target list would always break into
  37: **	two pieces.
  38: **
  39: **	Whether a query is fully connected is independent
  40: **	of whether there are any one variable components
  41: **	or not. This includes the target list. After applying
  42: **	the algorithm, a scan is made to see how many multi-var
  43: **	components are present. If there are two or more multi-var
  44: **	components then the query is disconnected.
  45: **
  46: **	Trace Flags:
  47: **		38
  48: */
  49: 
  50: algorithm(clist, varmap)
  51: struct complist *clist;
  52: int     varmap;
  53: {
  54:     register struct complist    *chead, *cnext;
  55:     register int            var;
  56:     int             vmap;
  57:     struct complist         *cprev, *cl;
  58: 
  59:     vmap = varmap;
  60:     for (var = 1; vmap; var <<= 1)
  61:     {
  62:         if ((vmap & var) == 0)
  63:             continue;
  64:         vmap &= ~var;   /* remove var */
  65: 
  66:         /* done if query is already a single piece */
  67:         if (clist->nextcomp == 0)
  68:             break;
  69: 
  70:         /* find first component using variable var */
  71:         for (chead = clist; chead; chead = chead->nextcomp)
  72:         {
  73:             if (chead->bitmap == 0 || (chead->bitmap & var))
  74:             {
  75:                 /* this component uses variable var */
  76: 
  77:                 cprev = chead;
  78: 
  79:                 /* look for other components using variable var */
  80:                 for (cnext = chead->nextcomp; cnext; cnext = cnext->nextcomp)
  81:                 {
  82:                     if (cnext->bitmap == 0 || (cnext->bitmap & var))
  83:                     {
  84: 
  85:                         /*
  86: 						** Found a component. Remove it from "next"
  87: 						** link and put it with head piece
  88: 						*/
  89: 
  90:                         /* remove piece */
  91:                         cprev->nextcomp = cnext->nextcomp;
  92: 
  93:                         /* fix up bit map */
  94:                         chead->bitmap |= cnext->bitmap;
  95: 
  96:                         /* find end of head component */
  97:                         for (cl = chead; cl->linkcomp; cl = cl->linkcomp);
  98: 
  99:                         /* connect with head piece */
 100:                         cl->linkcomp = cnext;
 101:                     }
 102:                     else
 103:                         cprev = cnext;
 104:                 }
 105:             }
 106:         }
 107:     }
 108: 
 109:     /* return whether connected or not connected */
 110:     for (var =0, chead = clist; chead; chead = chead->nextcomp)
 111:         if (bitcnt(chead->bitmap) > 1)
 112:             var++; /* this component involves 2 or more vars */
 113: 
 114:     return (var < 2); /* return TRUE if zero or one component multi-var */
 115: }
 116: /*
 117: **	Buildlist -- Build a component list from a query tree.
 118: **
 119: **	Each ROOT and AND node is treated as a separate component
 120: **	and a linked list is built connecting them. The ROOT node
 121: **	MUST be the first element. This list will later be manipulated
 122: **	by algorithm() to determine the structure of the query.
 123: **
 124: **	Returns:
 125: **		Head of the list
 126: */
 127: 
 128: struct complist *
 129: buildlist(root1, buf)
 130: QTREE   *root1;
 131: char    *buf;
 132: {
 133:     register struct complist    *head, *next;
 134:     register QTREE          *root;
 135:     struct complist         *ret;
 136:     extern char         *need();
 137: 
 138:     ret = (struct complist *) need(buf, 0);
 139:     head = 0;
 140: 
 141:     for (root = root1; root->sym.type != QLEND; root = root->right)
 142:     {
 143:         next = (struct complist *) need(buf, sizeof (*next));
 144:         next->clause = root;
 145:         next->nextcomp = next->linkcomp = 0;
 146:         next->bitmap = root->sym.value.sym_root.lvarm;
 147: 
 148:         if (head)
 149:             head->nextcomp = next;
 150:         head = next;
 151:     }
 152:     return (ret);
 153: }
 154: /*
 155: **  Construct -- construct a tree from a list component
 156: **
 157: **	Construct takes a list head and builds a querytree
 158: **	from the components in the list. If the head component
 159: **	is the ROOT of the original query, then
 160: **	the original ROOT node is reused.
 161: **
 162: */
 163: 
 164: QTREE *
 165: construct(root, listhead, buf)
 166: QTREE       *root;
 167: struct complist *listhead;
 168: char        *buf;
 169: {
 170:     register QTREE          *ret, *q;
 171:     register struct complist    *clist;
 172:     extern QTREE            *makroot();
 173: 
 174:     clist = listhead;
 175: 
 176:     /* determine ROOT of tree */
 177:     if (root == clist->clause)
 178:     {
 179:         q = root;
 180:         clist = clist->linkcomp;
 181:     }
 182:     else
 183:     {
 184:         q = makroot(buf);
 185:     }
 186:     ret = q;
 187:     for (; clist; clist = clist->linkcomp)
 188:     {
 189:         q->right = clist->clause;
 190:         q = q->right;
 191:     }
 192: 
 193:     q->right = De.de_qle;
 194: 
 195:     mapvar(ret, 1);
 196: #	ifdef xDTR1
 197:     if (tTf(38, 0))
 198:     {
 199:         printf("Construct\n");
 200:         treepr(ret);
 201:     }
 202: #	endif
 203:     return (ret);
 204: }
 205: /*
 206: **  Order -- order a link list set of query components.
 207: **
 208: **	Takes a list of components and orders them:
 209: **		first - disjoint components
 210: **		second - reduction pieces
 211: **		last - the original target list piece
 212: **
 213: **	Return:
 214: **		new head of list
 215: */
 216: 
 217: struct complist *
 218: order(clist, ovlapvar)
 219: struct complist *clist;
 220: int     ovlapvar;
 221: {
 222:     register struct complist    *cl, *joint, *disjoint;
 223:     struct complist         *xd, *xj, *tlpiece, *ret;
 224:     QTREE               *tmp;
 225:     int             map;
 226: 
 227:     tlpiece = clist;    /* target list piece always first */
 228:     disjoint = joint = 0;
 229:     map = ovlapvar >= 0 ? 1 << ovlapvar : 0;
 230: 
 231:     /* examine each irreducible component for disjointness */
 232:     for (cl = tlpiece->nextcomp; cl; cl = cl->nextcomp)
 233:     {
 234:         if (cl->bitmap & map)
 235:         {
 236:             /* joint piece */
 237:             if (joint == 0)
 238:             {
 239:                 joint = cl;
 240:                 xj = cl;
 241:             }
 242:             else
 243:             {
 244:                 joint->nextcomp = cl;
 245:                 joint = cl;
 246:             }
 247:         }
 248:         else
 249:         {
 250:             /* disjoint piece */
 251:             if (disjoint == 0)
 252:             {
 253:                 disjoint = cl;
 254:                 xd = cl;
 255:             }
 256:             else
 257:             {
 258:                 disjoint->nextcomp = cl;
 259:                 disjoint = cl;
 260:             }
 261:         }
 262: 
 263:     }
 264:     /* we now have all disjoint, joint and tl pieces */
 265:     /* order them in order (1) xd, (2) xj, (3) tlpiece */
 266: 
 267:     ret = tlpiece;
 268:     tlpiece->nextcomp = 0;
 269: 
 270:     if (joint)
 271:     {
 272:         ret = xj;
 273:         joint->nextcomp = tlpiece;
 274:         if ((tlpiece->bitmap & (~map)) == 0)
 275:         {
 276:             /*
 277: 			** This is the special case of the target list
 278: 			** being one (or zero) variable and that variable
 279: 			** is the overlap variable. If left as is, the
 280: 			** reduction will take one step more than is
 281: 			** necessary. The target list piece is combined
 282: 			** with the last joint piece and processed together.
 283: 			**
 284: 			** An example of when this will happen is:
 285: 			** ret(p.a) : p.b = s.b ^ p.c = y.c
 286: 			**
 287: 			** Reduction would split this up into
 288: 			** (1) ret (p.a,p.b) : p.c = y.c
 289: 			** (2) ret (p.a) : p.b = s.b
 290: 			** (3) ret (p.a)
 291: 			**
 292: 			** Here we are allowing pieces (2) & (3) to be done together
 293: 			*/
 294: 
 295:             for (cl = joint; cl->linkcomp; cl = cl->linkcomp);
 296: 
 297:             cl->linkcomp = tlpiece;
 298:             joint->nextcomp = 0;
 299: 
 300:             /* switch tl clause to top of complist */
 301:             tmp = joint->clause;
 302:             joint->clause = tlpiece->clause;
 303:             tlpiece->clause = tmp;
 304:         }
 305:     }
 306: 
 307:     if (disjoint)
 308:     {
 309:         ret = xd;
 310:         disjoint->nextcomp = joint ? xj : tlpiece;
 311:     }
 312: 
 313:     return (ret);
 314: }

Defined functions