```   1: # include   "../ingres.h"
2: # include   "../aux.h"
3: # include   "../pipes.h"
4: # include   "../tree.h"
5: # include   "../symbol.h"
6:
7: /*
8: ** NORML
9: **	this routine passes the qualification clause portion of the query
10: **	tree to the routines for depressing nots and for conjunctive
11: **	normalization.  It also calls a routine to place an and with one
12: **	null branch at the rightmost end of the tree.
13: */
14: struct querytree *
15: norml(ptr)
16: struct querytree    *ptr;
17: {
18:     extern struct querytree *nnorm();
19:     extern struct querytree *travers();
20:     extern struct querytree *tree();
21:
22:     if (ptr == NULL)
23:         return (tree(NULL, NULL, QLEND, 0, 0));
24:
25:     /* push through the 'nots' as far a possible */
26:     ptr = nnorm(ptr);
27:
28:     /* make tree into conjunctive normal form */
29:     ptr = travers(ptr);
30:
31:     /* terminate the list on the rightmost branch */
33:
34:     /* make 'ands' into a linear list */
35:     mvands(ptr);
36:     return (ptr);
37: }
38:
39:
40: /*
41: ** NORM
42: **	this routine takes a tree which has nots only at the lower ends, and
43: **	places it into conjunctive normal form by repeatedly applying the
44: **	replacement rule: A or (B and C) ==> (A or B) and (A or C)
45: */
46: struct querytree *
47: norm(p1)
48: struct querytree    *p1;
49: {
50:     extern struct querytree     *tree();
51:     register struct querytree   *p;
52:     register struct querytree   *lptr;
53:     register struct querytree   *rptr;
54:
55:     p = p1;
56:     switch (p->sym.type)
57:     {
58:       case AND:
59:         p->left = norm(p->left);
60:         p->right = norm(p->right);
61:         break;
62:
63:       case OR:
64:         if (p->right->sym.type == AND)
65:         {
66:         andright:
67:             /*
68: 			** combine left subtree with each subtree of the
69: 			** right subtree
70: 			*/
71:             /*
72: 			** use copy first so that the copy is guaranteed to be
73: 			** the same as the original
74: 			*/
75:             lptr = tree(treedup(p->left), p->right->left, OR, 0, 0);
76:             rptr = tree(p->left, p->right->right, OR, 0, 0);
77:             lptr = norm(lptr);
78:             rptr = norm(rptr);
79:             /* change node type to AND from OR */
80:             p->left = lptr;
81:             p->right = rptr;
82:             p->sym.type = AND;  /* length is same */
83:             break;
84:         }
85:         if (p->left->sym.type == AND)
86:         {
87:         andleft:
88:             /*
89: 			** combine right subtree with each subtree of the
90: 			** left subtree
91: 			*/
92:             /*
93: 			** again, the copy should be used first
94: 			*/
95:             lptr = tree(p->left->left, treedup(p->right), OR, 0, 0);
96:             rptr = tree(p->left->right, p->right, OR, 0, 0);
97:             lptr = norm(lptr);
98:             rptr = norm(rptr);
99:             /* change node type to AND from OR */
100:             p->left = lptr;
101:             p->right = rptr;
102:             p->sym.type = AND;
103:             break;
104:         }
105:         /*
106: 		** when TRAVERS is being used to optomize the normalization
107: 		** order there should never be (I think) an OR as a child
108: 		** of the OR in the parent.  Since TRAVERS works bottom up
109: 		** in the tree the second OR level should be gone.
110: 		*/
111:         if (p->right->sym.type == OR)
112:         {
113:             /* skip this (p->sym.type) "or" and normalize the right subtree */
114:             p->right = norm(p->right);
115:
116:             /* now re-try the current node */
117:             if (p->right->sym.type == AND)
118:                 goto andright;
119:             break;
120:         }
121:         if (p->left->sym.type == OR)
122:         {
123:             /* skip this "or" and normalize the left subtree */
124:             p->left = norm(p->left);
125:
126:             /* now re-try the current node */
127:             if (p->left->sym.type == AND)
128:                 goto andleft;
129:             break;
130:         }
131:         break;
132:     }
133:     return (p);
134: }
135:
136: /*
137: ** TRAVERS
138: **	traverse the tree so that conversion of ORs of ANDs can
139: **	take place at the innermost clauses first.  IE, normalize
140: **	before replication rather than after replication.
141: **
142: **	This routine need not be used.  The NORM routine will completely
143: **	traverse the tree and normalize it but...    TRAVERS finds
144: **	the lowest subtree to normalize first so that sub-trees can
145: **	be normalized before replication, hence reducing the time required
146: **	to normalize large trees.  It will also make OR-less trees faster
147: **	to normalize (since nothing need be done to it).
148: */
149: struct querytree *
150: travers(p1)
151: struct querytree    *p1;
152: {
153:     register struct querytree   *p;
154:     extern struct querytree     *norm();
155:
156:     p = p1;
157:     if (p->right != NULL)
158:         p->right = travers(p->right);
159:     if (p->left != NULL)
160:         p->left = travers(p->left);
161:     if (p->sym.type == OR)
162:         p = norm(p);
163:     return (p);
164: }
165: /*
166: ** NNORM
167: **	this routine depresses nots in the query tree to the lowest possible
168: **	nodes.  It may also affect arithmetic operators in this procedure
169: */
170: struct querytree *
171: nnorm(p1)
172: struct querytree    *p1;
173: {
174:     extern struct querytree     *notpush();
175:     register struct querytree   *p;
176:
177:     p = p1;
179:     {
180:         /*
181: 		** don't need to continue past an AGHEAD
182: 		** actually, it causes problems if you do
183: 		** because the qualification on the agg
184: 		** has already been normalized and the
185: 		** QLEND needs to stay put
186: 		*/
187:         return (p);
188:     }
189:     if ((p->sym.type == UOP) && (((struct qt_op *)p)->opno == opNOT))
190:     {
191:         /* skip not node */
192:         p = p->right;
193:         p = notpush(p);
194:     }
195:     else
196:     {
197:         if (p->left != NULL)
198:             p->left = nnorm(p->left);
199:         if (p->right != NULL)
200:             p->right = nnorm(p->right);
201:     }
202:     return (p);
203: }
204:
205: /*
206: ** NOTPUSH
207: **	this routine decides what to do once a not has been found in the
208: **	query tree
209: */
210: struct querytree *
211: notpush(p1)
212: struct querytree    *p1;
213: {
214:     extern struct querytree     *nnorm();
215:     register struct querytree   *p;
216:
217:     p = p1;
218:     switch (p->sym.type)
219:     {
220:       case AND:
221:         p->sym.type = OR;
222:         p->left = notpush(p->left);
223:         p->right = notpush(p->right);
224:         break;
225:
226:       case OR:
227:         p->sym.type = AND;
228:         p->left = notpush(p->left);
229:         p->right = notpush(p->right);
230:         break;
231:
232:       case BOP:
233:         switch (((struct qt_op *)p)->opno)
234:         {
235:           case opEQ:
236:             ((struct qt_op *)p)->opno = opNE;
237:             break;
238:
239:           case opNE:
240:             ((struct qt_op *)p)->opno = opEQ;
241:             break;
242:
243:           case opLT:
244:             ((struct qt_op *)p)->opno = opGE;
245:             break;
246:
247:           case opGE:
248:             ((struct qt_op *)p)->opno = opLT;
249:             break;
250:
251:           case opLE:
252:             ((struct qt_op *)p)->opno = opGT;
253:             break;
254:
255:           case opGT:
256:             ((struct qt_op *)p)->opno = opLE;
257:             break;
258:
259:           default:
260:             syserr("strange BOP in notpush '%d'", ((struct qt_op *)p)->opno);
261:         }
262:         break;
263:
264:       case UOP:
265:         if (((struct qt_op *)p)->opno == opNOT)
266:         {
267:             /* skip not node */
268:             p = p->right;
269:             p = nnorm(p);
270:         }
271:         else
272:             syserr("strange UOP in notpush '%d'", ((struct qt_op *)p)->opno);
273:         break;
274:
275:       default:
276:         syserr("unrecognizable node type in notpush '%d'", p->sym.type);
277:     }
278:     return (p);
279: }
280:
281: /*
283: **	terminate qual with an AND and a QLEND at the rightmost branch
284: */
286: struct querytree    **pp;
287: {
288:     extern struct querytree     *tree();
289:     register struct querytree   *p;
290:
291:     p = *pp;
292:     switch (p->sym.type)
293:     {
294:       case AND:
296:         break;
297:
298:       case OR:
299:       default:
300:         *pp = tree(p, tree(NULL, NULL, QLEND, 0, NULL), AND, 0, 0);
301:         break;
302:     }
303: }
304:
305: struct querytree *treedup(p1)
306: struct querytree    *p1;
307: {
308:     register struct querytree   *np;
309:     register struct querytree   *p;
310:     extern char         *Qbuf;
311:
312:     if ((p = p1) == NULL)
313:         return (p);
314:     np = (struct querytree *) need(Qbuf, (p->sym.len & I1MASK) + 6);
315:     bmove(p, np, (p->sym.len & I1MASK) + 6);
316:     np->left = treedup(p->left);
317:     np->right = treedup(p->right);
318:     return (np);
319: }
320:
321: /*
322: **	MVANDS -- pushes all AND's in Qual into linear list
323: */
324: mvands(andp)
325: struct querytree    *andp;
326: {
327:     register struct querytree   *ap, *lp, *rp;
328:
329:     ap = andp;
330:     if (ap->sym.type == QLEND)
331:         return;
332:     rp = ap->right;
333:     lp = ap->left;
334:     if (lp->sym.type == AND)
335:     {
336:         ap->left = lp->right;
337:         ap->right = lp;
338:         lp->right = rp;
339:         mvands(ap);
340:     }
341:     else
342:         mvands(rp);
343: }
```

#### Defined functions

adjust defined in line 285; used 2 times
mvands defined in line 324; used 3 times
nnorm defined in line 170; used 6 times
norm defined in line 46; used 11 times
norml defined in line 14; used 4 times
notpush defined in line 210; used 6 times
travers defined in line 149; used 4 times
treedup defined in line 305; used 4 times
 Last modified: 1995-02-19 Generated: 2016-12-26 Generated by src2html V0.67 page hit count: 3031