![[BACK]](/cvsweb/icons/back.gif){kind=icon}
Return to decision.c CVS log ![[TXT]](/cvsweb/icons/text.gif){kind=icon}
![[DIR]](/cvsweb/icons/dir.gif){kind=icon}
Up to [CSRG BSD Unix] / 42BSD / ingres / source / decomp|
Return to decision.c CVS log | Up to [CSRG BSD Unix] / 42BSD / ingres / source / decomp |
1.1 root 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(@(#)decision.c 7.1 2/5/81)
9:
10: /*
11: ** DECISION -- This file contains code related to deciding how to
12: ** process the remaining query. The main routine is decision()
13: ** and the other routines are called only by decision. The routine
14: ** in this file include:
15: **
16: ** Decision -- Decides how to process a query.
17: **
18: ** Fixtl -- Determines the target list for each component.
19: **
20: ** Fixresult -- Determines the result relation for the next query
21: **
22: ** Fixrange -- Adjust the range table after a query
23: **
24: ** Fixovlap -- Fixes trees in cases where reduction is used
25: **
26: ** Rmovlap -- Restores trees in cases where reduction was used.
27: **
28: ** Listcomp -- Debugging routine.
29: */
30: /*
31: ** Decision is given a subquery and decides how to process it.
32: ** The choices are:
33: ** Disjoint pieces -- The original query had disjoint components.
34: ** Do each component separately.
35: ** Reduction -- The query is joined by a single variable.
36: ** Reduce the query on that joining variable
37: ** and do each component separately.
38: ** Substitution -- The query is neither disjoint nor reducible.
39: ** Process by tuple substitution.
40: **
41: ** Notice that decision() is recursive and will call itself on each
42: ** subcomponent it decides to do. Decision calls various support
43: ** routines in the file "reduction.c".
44: */
45:
46: decision(root, qmode, result_num, buf)
47: QTREE *root;
48: int qmode;
49: int result_num;
50: char *buf;
51: {
52: register QTREE **qp;
53: register struct complist *clist;
54: register int ovlapvar;
55: struct complist *cp;
56: int i, onepiece, qtrue, map;
57: int mark, mark1, cand_map;
58: QTREE *tree, *newtree;
59: QTREE *qlist[MAXRANGE];
60: int newqmode;
61: int ovlaprelnum, newr;
62: int locrange[MAXRANGE];
63: extern QTREE *copy_ands();
64: extern struct complist *buildlist(), *order();
65: extern QTREE *construct();
66:
67: # ifdef xDTR1
68: if (tTf(37, -1))
69: {
70: printf("DECISION root=%x,vc=%d,res=%d\n", root, root->sym.value.sym_root.tvarc, result_num);
71: }
72: # endif
73: mark = markbuf(buf);
74: if (root->sym.value.sym_root.tvarc < 3)
75: {
76: /* setup to do as one single piece */
77: onepiece = TRUE;
78: }
79: else
80: {
81: /* break the query apart if possible */
82:
83: /* build component list */
84: clist = buildlist(root, buf);
85: # ifdef xDTR1
86: if (tTf(37, 2))
87: listcomp(clist, "Original Comp");
88: # endif
89:
90: /* is query completely connected or disjoint */
91: map = root->sym.value.sym_root.lvarm | root->sym.value.sym_root.rvarm;
92: onepiece = algorithm(clist, map);
93: # ifdef xDTR1
94: if (tTf(37, 1))
95: printf("Orig query %s\n", onepiece ? "connected" : "disjoint");
96: # endif
97: /* assume there is no joining variable */
98: ovlapvar = -1;
99:
100: if (onepiece)
101: {
102: /*
103: ** Try to reduce a single connected piece.
104: ** In turn each variable will be logically
105: ** removed from the query and a test will
106: ** be made to see if the query is still
107: ** connected.
108: */
109:
110: cand_map = map;
111: for (i = 1; cand_map; i <<= 1)
112: {
113: if ((cand_map & i) == 0)
114: continue;
115: cand_map &= ~i;
116: freebuf(buf, mark);
117: clist = buildlist(root, buf);
118: if (algorithm(clist, map & ~i) == 0)
119: {
120: ovlapvar = bitpos(i);
121: ovlaprelnum = De.de_rangev[ovlapvar].relnum;
122: onepiece = FALSE;
123: break;
124: }
125: }
126: # ifdef xDTR1
127: if (tTf(37, 1))
128: {
129: if (ovlapvar < 0)
130: printf("Query not reducible\n");
131: else
132: {
133: printf("Query Reducible on %d\n", ovlapvar);
134: if (tTf(37, 3))
135: listcomp(clist, "After reduct");
136: }
137: }
138: # endif
139: }
140:
141: /*
142: ** If query is more than one piece, build trees
143: ** for each piece.
144: */
145:
146: if (!onepiece)
147: {
148: /* order pieces */
149: clist = order(clist, ovlapvar);
150: # ifdef xDTR1
151: if (tTf(37, 4))
152: listcomp(clist, "After ordering");
153: # endif
154: cp = clist;
155: qp = qlist;
156: do
157: {
158: *qp++ = construct(root, cp, buf);
159: } while (cp = cp->nextcomp);
160: *qp++ = 0;
161: }
162: }
163:
164: /*
165: ** The query is now either the one original piece or
166: ** is in multiple pieces. The information in clist
167: ** has been thrown away and now the ordered pieces
168: ** will be processed.
169: */
170:
171: if (onepiece)
172: {
173: freebuf(buf, mark);
174: qtrue = decompy(root, qmode, result_num, buf);
175: }
176: else
177: {
178: /* the query is in pieces. prepare to process */
179:
180: newquery(locrange); /* save state of range table */
181:
182: /* determine the target list for each piece of the query */
183: for (qp = qlist; tree = *qp++; )
184: fixtl(tree, qp, ovlapvar, buf);
185:
186: /* adjust refs to ovlapvar since domain #'s could have changed */
187: fixovlap(qlist, ovlapvar, buf);
188:
189:
190: /* now process each component */
191: mark1 = markbuf(buf);
192: for (qp = qlist; tree = *qp++; )
193: {
194:
195: # ifdef xDTR1
196: if (tTf(37, 6))
197: {
198: printf("next piece\n");
199: treepr(tree);
200: }
201: # endif
202:
203: /* determine result relation name */
204: newr = fixresult(root, tree, &newqmode, qmode, result_num);
205:
206: /*
207: ** Run the query. If reduction is being
208: ** performed, the actual tree given to
209: ** the decision routine must be a copy
210: ** to protect from the recursive call changing
211: ** the tree. Any work done at this level,
212: ** must be to the original tree
213: */
214: newtree = tree;
215: if (ovlapvar != -1)
216: {
217: freebuf(buf, mark1);
218: newtree = copy_ands(tree, buf);
219: }
220: qtrue = decision(newtree, newqmode, newr, buf);
221:
222: /* fix up the range table */
223: fixrange(root, tree, ovlapvar, ovlaprelnum, newr);
224:
225: /* if last piece was false then done */
226: if (!qtrue)
227: break;
228:
229: }
230:
231: /* restore the trees */
232: rmovlap(qlist, ovlapvar);
233:
234: /* restore range table back to original */
235: endquery(locrange, TRUE); /* reopen previous range */
236:
237: /* return any buffer space used */
238: freebuf(buf, mark);
239: }
240:
241: /* all done with query */
242: return (qtrue);
243: }
244: /*
245: ** Fixresult -- Determine result relation for "tree" query.
246: ** If "tree" is the original target list piece then use the
247: ** original relation and mode.
248: ** If "tree" is a reduction piece then create a temporary relation
249: ** for it.
250: ** If "tree" is a disjoint piece then there is no target list nor
251: ** result relation.
252: **
253: ** Return:
254: ** result relation number
255: ** Side Effects:
256: ** *newmode is set to the query mode of the next piece
257: */
258:
259: fixresult(root, tree1, newmode, origmode, resnum)
260: QTREE *root;
261: QTREE *tree1;
262: int *newmode;
263: int origmode;
264: int resnum;
265: {
266: register QTREE *tree;
267: register int newresult;
268:
269: tree = tree1;
270: *newmode = mdRETR;
271: if (tree->left->sym.type != TREE)
272: {
273: if (tree != root)
274: {
275: /* make new result for reduction step */
276: newresult = mak_t_rel(tree, "r", -1);
277: }
278: else
279: {
280: /* final piece with original result and mode */
281: newresult = resnum;
282: *newmode = origmode;
283: }
284: }
285: else
286: newresult = NORESULT;
287: return (newresult);
288: }
289: /*
290: ** Update range table after a reduction has been processed.
291: ** Only the intermediate reductions will affect the range
292: ** table. The last piece does not.
293: */
294:
295: fixrange(root, tree, ovlapvar, reductnum, newrelnum)
296: QTREE *root;
297: QTREE *tree;
298: int ovlapvar;
299: int reductnum;
300: int newrelnum;
301: {
302: register int old;
303: register int i;
304: extern DESC *openr1();
305:
306: if (root != tree)
307: {
308: /* this is an intermediate piece */
309: i = ovlapvar;
310:
311: if (newrelnum >= 0)
312: {
313: old = new_range(i, newrelnum);
314: if (old != reductnum)
315: dstr_rel(old);
316: openr1(i);
317: }
318: }
319: }
320: /*
321: ** Fixovlap -- Adjust subsequent trees which reference the reduction var
322: **
323: ** If the first query in list redefines the reduction variable
324: ** (if any) then each subsequent query which references the
325: ** reduction variable is adjusted.
326: ** Since there may be multiple pieces,
327: ** subsequence redefinitions are done without
328: ** reallocating buffer space.
329: **
330: */
331:
332: fixovlap(qlist, ovlapvar, buf)
333: QTREE *qlist[];
334: int ovlapvar;
335: char *buf;
336: {
337: register QTREE **qp, *piece, **qp1;
338: QTREE *next;
339: int ovmap;
340: extern QTREE **mksqlist();
341:
342: ovmap = 1 << ovlapvar;
343:
344: /* for each piece, if it redefines ovlapvar, then fix up rest */
345: for (qp = qlist; piece = *qp++; )
346: {
347: if (piece->sym.value.sym_root.lvarm & ovmap)
348: {
349: for (qp1 = qp; next = *qp1++; )
350: {
351: if ((next->sym.value.sym_root.lvarm | next->sym.value.sym_root.rvarm) & ovmap)
352: {
353: tempvar(next, mksqlist(piece, ovlapvar), buf);
354: buf = NULL; /* do not allocate on subsequent refs */
355: }
356: }
357: }
358: }
359: }
360: /*
361: ** Rmovlap -- Restore query trees back to their original state.
362: **
363: ** Rmovlap undoes the effect of fixovlap(). Any references
364: ** to the reduction variable which were adjusted are now
365: ** reverted back to the original reference. Note that the
366: ** first piece is not effected by fixovlap.
367: */
368:
369: rmovlap(qlist, ovlapvar)
370: QTREE *qlist[];
371: int ovlapvar;
372: {
373: register QTREE **qp, *tree;
374: int ovmap;
375:
376: if (ovmap = (1 << ovlapvar))
377: {
378: /* for each piece, remove any tempvars */
379: for (qp = &qlist[1]; tree = *qp++; )
380: {
381: origvar(tree, mksqlist(tree, ovlapvar));
382: }
383: }
384: }
385: /*
386: ** Fixtl -- Determine what the target list of each tree should be.
387: **
388: ** Fixtl takes each query which references the reduction variable
389: ** and looks for references to that variable in subsequent queries.
390: ** Dfind will build a target list which includes every domain
391: ** which will later be referenced.
392: */
393:
394: fixtl(tree1, qp1, ovlapvar, buf)
395: QTREE *tree1;
396: QTREE *qp1[];
397: int ovlapvar;
398: char *buf;
399: {
400: register QTREE *tree, **qp, *next;
401: int var, map;
402: extern QTREE **mksqlist();
403:
404: tree = tree1;
405: var = ovlapvar;
406: map = 1 << var;
407:
408: /*
409: ** if the last tree referenced the overlap variable then
410: ** try to fix next tree
411: */
412: if (tree->sym.value.sym_root.rvarm & map)
413: {
414: qp = qp1;
415: while (next = *qp++)
416: {
417: if ((next->sym.value.sym_root.lvarm | next->sym.value.sym_root.rvarm) & map)
418: dfind(next, buf, mksqlist(tree, var));
419: }
420: }
421: }
422:
423:
424:
425: # ifdef xDTR1
426:
427: /*
428: ** This is strictly a debuggin routine used for
429: ** printing component lists.
430: */
431:
432: listcomp(list, mesg)
433: struct complist *list;
434: char *mesg;
435: {
436: register struct complist *c, *cl;
437: register int i;
438:
439: if (tTf(37, 14))
440: {
441: printf("%s\n", mesg);
442: i = -1;
443:
444: for (cl = list; cl; cl = cl->nextcomp)
445: {
446: i++;
447: printf("Component %d:map=%o\n", i, cl->bitmap);
448: for (c = cl; c; c = c->linkcomp)
449: {
450: printf("%x, ", c->clause);
451: if (tTf(37, 15))
452: {
453: treepr(c->clause->left);
454: nodepr(c->clause);
455: }
456: }
457: printf("\n");
458: }
459: }
460: }
461: # endif
This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.