Return to norml.c CVS log

Up to [CSRG BSD Unix] / 42BSD / ingres / source / qrymod

Annotation of 42BSD/ingres/source/qrymod/norml.c, revision 1.1

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     7.1     2/5/81)
        !             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.