2.11BSD#431 - /usr/ingres/source/decomp/reduction.c

   1: # include   "../ingres.h"
   2: # include   "../symbol.h"
   3: # include   "../tree.h"
   4: # include   "decomp.h"
   5: 
   6: /*
   7: **	Reduction -- This file contains routines related to the
   8: **	reduction algorithm. The routines are all called by
   9: **	decision().
  10: **
  11: **	Included are:
  12: **
  13: **		algorithm -- groups clauses according to common variables
  14: **
  15: **		buildlist -- build linked list of clauses from a query tree
  16: **
  17: **		construct -- build query trees from link lists of clauses
  18: **
  19: **		order     -- order a linked list of clauses into the prefered
  20: **				execution sequence
  21: */
  22: 
  23: 
  24: algorithm(clist, varmap)
  25: struct complist *clist;
  26: int     varmap;
  27: 
  28: /*
  29: **	Algorithm - determine whether query is connected or not
  30: **
  31: **	Algorithm takes a linked list of query components
  32: **	and groups them according to the variables involved
  33: **	in each component. If the query is fully interconnected
  34: **	then algorithm returns TRUE else it returns FALSE.
  35: **
  36: **	By definition a constant clause (one involving zero variables)
  37: **	is considered to use all variables. Without this rule,
  38: **	a query with a null target list would always break into
  39: **	two pieces.
  40: **
  41: **	Whether a query is fully connected is independent
  42: **	of whether there are any one variable components
  43: **	or not. This includes the target list. After applying
  44: **	the algorithm, a scan is made to see how many multi-var
  45: **	components are present. If there are two or more multi-var
  46: **	components then the query is disconnected.
  47: */
  48: 
  49: {
  50:     register struct complist    *chead, *cnext;
  51:     register int            var;
  52:     int             vmap;
  53:     struct complist         *cprev, *cl;
  54: 
  55:     vmap = varmap;
  56:     for (var = 1; vmap; var <<= 1)
  57:     {
  58:         if ((vmap & var) == 0)
  59:             continue;
  60:         vmap &= ~var;   /* remove var */
  61: 
  62:         /* done if query is already a single piece */
  63:         if (clist->nextcomp == 0)
  64:             break;
  65: 
  66:         /* find first component using variable var */
  67:         for (chead = clist; chead; chead = chead->nextcomp)
  68:         {
  69:             if (chead->bitmap == 0 || (chead->bitmap & var))
  70:             {
  71:                 /* this component uses variable var */
  72: 
  73:                 cprev = chead;
  74: 
  75:                 /* look for other components using variable var */
  76:                 for (cnext = chead->nextcomp; cnext; cnext = cnext->nextcomp)
  77:                 {
  78:                     if (cnext->bitmap == 0 || (cnext->bitmap & var))
  79:                     {
  80: 
  81:                         /*
  82: 						** Found a component. Remove it from "next"
  83: 						** link and put it with head piece
  84: 						*/
  85: 
  86:                         /* remove piece */
  87:                         cprev->nextcomp = cnext->nextcomp;
  88: 
  89:                         /* fix up bit map */
  90:                         chead->bitmap |= cnext->bitmap;
  91: 
  92:                         /* find end of head component */
  93:                         for (cl = chead; cl->linkcomp; cl = cl->linkcomp);
  94: 
  95:                         /* connect with head piece */
  96:                         cl->linkcomp = cnext;
  97:                     }
  98:                     else
  99:                         cprev = cnext;
 100:                 }
 101:             }
 102:         }
 103:     }
 104: 
 105:     /* return whether connected or not connected */
 106:     for (var =0, chead = clist; chead; chead = chead->nextcomp)
 107:         if (bitcnt(chead->bitmap) > 1)
 108:             var++; /* this component involves 2 or more vars */
 109: 
 110:     return (var < 2); /* return TRUE if zero or one component multi-var */
 111: }
 112: 
 113: 
 114: struct complist *buildlist(root1, buf)
 115: struct querytree    *root1;
 116: char            *buf;
 117: 
 118: /*
 119: **	Buildlist -- Build a component list from a query tree.
 120: **
 121: **	Each ROOT and AND node is treated as a separate component
 122: **	and a linked list is built connecting them. The ROOT node
 123: **	MUST be the first element. This list will later be manipulated
 124: **	by algorithm() to determine the structure of the query.
 125: **
 126: **	Returns:
 127: **		Head of the list
 128: */
 129: 
 130: {
 131:     register struct complist    *head, *next;
 132:     register struct querytree   *root;
 133:     struct complist         *ret;
 134:     extern struct querytree     *need();
 135: 
 136:     ret = (struct complist *) need(buf, 0);
 137:     head = 0;
 138: 
 139:     for (root = root1; root->sym.type != QLEND; root = root->right)
 140:     {
 141:         next = (struct complist *) need(buf, sizeof (struct complist));
 142:         next->clause = root;
 143:         next->nextcomp = next->linkcomp = 0;
 144:         next->bitmap = ((struct qt_root *)root)->lvarm;
 145: 
 146:         if (head)
 147:             head->nextcomp = next;
 148:         head = next;
 149:     }
 150:     return (ret);
 151: }
 152: 
 153: 
 154: struct querytree *construct(root, listhead, buf)
 155: struct querytree    *root;
 156: struct complist     *listhead;
 157: char            *buf;
 158: 
 159: /*
 160: **  Construct -- construct a tree from a list component
 161: **
 162: **	Construct takes a list head and builds a querytree
 163: **	from the components in the list. If the head component
 164: **	is the ROOT of the original query, then
 165: **	the original ROOT node is reused.
 166: **
 167: */
 168: 
 169: {
 170:     register struct querytree   *ret, *q;
 171:     register struct complist    *clist;
 172:     extern struct querytree     *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 = Qle;
 194: 
 195:     mapvar(ret, 1);
 196: #	ifdef xDTR1
 197:     if (tTf(16, 0))
 198:         printree(ret, "Construct");
 199: #	endif
 200:     return (ret);
 201: }
 202: 
 203: 
 204: 
 205: struct complist *order(clist, ovlapvar)
 206: struct complist *clist;
 207: int     ovlapvar;
 208: 
 209: /*
 210: **  Order -- order a link list set of query components.
 211: **
 212: **	Takes a list of components and orders them:
 213: **		first - disjoint components
 214: **		second - reduction pieces
 215: **		last - the original target list piece
 216: **
 217: **	Return:
 218: **		new head of list
 219: */
 220: 
 221: {
 222:     register struct complist    *cl, *joint, *disjoint;
 223:     struct complist         *xd, *xj, *tlpiece, *ret;
 224:     struct querytree        *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