![[BACK]](/cvsweb/icons/back.gif){kind=icon}
Return to norml.c CVS log ![[TXT]](/cvsweb/icons/text.gif){kind=icon}
![[DIR]](/cvsweb/icons/dir.gif){kind=icon}
Up to [CSRG BSD Unix] / 43BSD / ingres / source / qrymod|
Return to norml.c CVS log | Up to [CSRG BSD Unix] / 43BSD / ingres / source / qrymod |
1.1 root 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: }
This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.