The present invention is directed to an improvement in computing systems and in particular to the identification of vacuous predicates in computer programs.
In computer systems it is often advantageous to recognize predicates which are always true or always false (vacuous predicates). Predicates that are always TRUE are known as xe2x80x9ctautologiesxe2x80x9d, and the problem of identifying such predicates, which is known as xe2x80x9ctautology checkingxe2x80x9d, is a familiar problem in computer science. The problem of identifying predicates that are always FALSE is essentially the same problem, since such predicates become tautologies when negated. Examples of where identification of vacuous predicates is of value include computer program optimization and error-checking. An example of where the identification of vacuous predicates assists in optimization involves the compilation of an IF statement. If the expression on which the IF statement depends is identified as a vacuous predicate, the code for the IF statement may be optimized as the expression on which the IF statement depends will always be either TRUE or always FALSE.
Specialized computer systems exist which are able to determine whether a predicate is vacuous. For example, special programming languages such as Prolog are designed to permit theorem proving tools to be constructed which will identify vacuous predicates. Prior art approaches include the use of common techniques such as simplifying predicate manipulations by converting the predicates to conjunctive normal form (CNF) or to disjunctive normal form (DNF). Such prior art approaches to the problem, however, are potentially complex and slow and therefore have restricted applicability. For example, the problem of determining whether two predicates p and q are mutually exclusive (restated, whether the predicate p AND q is vacuously FALSE), can be solved using prior art techniques. However, the problem of identifying vacuous predicates is NP-hard and as a result, test cases can be constructed which will result in such powerful theorem-proving techniques running for an unacceptably long time, or requiring an unacceptable amount of computer memory.
A construct which is not atypical in the computer programming language SQL, such as
NOT (product_code IN (2, 3, 5, 7, 11, 13, . . . 149, 151))
can give rise to a predicate in the form
(p1 OR q1) AND (p2 OR q2) AND (p3 OR q3) AND . . . AND (p40 OR q40).
Such a predicate will give rise to an unacceptably large memory requirement, if converted to DNF. It is therefore desirable to have a system and method which will identify vacuous predicates in computer programs, in many practical cases, using less time and memory resources than the prior-art theorem-proving approaches. A system using such an approach will be advantageous in a practical sense even where it is not able to correctly identify all vacuous predicates, if it can quickly and simply identify many vacuous predicates.
According to one aspect of the present invention, there is provided an improved system and method for the identification of vacuous predicates in computer programs.
According to another aspect of the present invention, there is provided a computer system for identifying a predicate in a computer language as vacuous, the predicate containing one or more constant expressions, comprising means for identifying distinct variables contained in the predicate and for defining a predicate dimension number equal to the number of variables identified in the predicate, means for representing the predicate by a set of bounding rectangles, wherein a bounding rectangle is represented in a space having a number of dimensions equal to the predicate dimension number, wherein a finite limit on a dimension of a bounding rectangle represents the relationship between a one of the identified variables contained in the predicate and a one of the constant expressions in the predicate, and means for signalling that the predicate is vacuously FALSE where the set of bounding rectangles is empty.
According to another aspect of the present invention, there is provided, for the above computer system, a means for representing the predicate by a set of bounding rectangles which comprises means for deriving the set of bounding rectangles whereby a first selected one of the bounding rectangles is discarded from the set of bounding rectangles when the first selected one of the input rectangles is empty, discarded from the set of bounding rectangles when the selected one of the bounding rectangles is contained within any other rectangle in the set of bounding rectangles, merged with a second selected one of the bounding rectangles when the two rectangles exactly agree in all dimensions but one.
According to another aspect of the present invention, there is provided for the computer system above, a means for representing the predicate by a set of bounding rectangles which comprises a means for deriving the set of bounding rectangles by replacing a selected pair of rectangle sets in the set of bounding rectangles with a replacement rectangle set where the selected pair of rectangle sets correspond to expressions in the predicate subject to the operator AND, and where the replacement rectangle sets represent the intersection of the selected pair of rectangle sets.
According to another aspect of the present invention, there is provided for the computer system of above, a the means for representing the predicate by a set of bounding rectangles which comprises transforming means for transforming the predicate into an intermediate expression logically equivalent to the predicate, the intermediate expression containing only subexpressions which may be directly represented as rectangles, and means for representing the intermediate expression as a set of bounding rectangles.
According to another aspect of the present invention, there is provided the above computer system in which the intermediate expression consists of SQL expressions containing AND, OR, =,  less than ,  greater than ,  less than =,  greater than =, IS_NULL and IS_NOT_NULL.
According to another aspect of the present invention, there is provided the above computer system in which the transforming means comprises means for replacing expressions containing NOT and expressions containing  less than  greater than  with logically equivalent expressions containing only one or more of AND, OR, =,  less than ,  greater than ,  less than =, and  greater than =.
According to another aspect of the present invention, there is provided the above computer system in which the means for identifying variables uses syntactic matching to recognize distinct variables.
According to another aspect of the present invention, there is provided the above computer system in which the means for identifying variables uses semantic rules to recognize distinct variables.
According to another aspect of the present invention, there is provided a method for identifying a predicate in a computer language as vacuous, the predicate containing one or more constant expressions, comprising the steps of identifying distinct variables contained in the predicate, defining a predicate dimension number equal to the number of variables identified in the predicate, representing the predicate by a set of bounding rectangles, wherein a bounding rectangle is represented in a space having a number of dimensions equal to the predicate dimension number, wherein a finite limit on a dimension of a bounding rectangle represents the relationship between a one of the identified variables contained in the predicate and a one of the constant expressions in the predicate, and signalling that the predicate is vacuously FALSE where the set of bounding rectangles is empty.
According to another aspect of the present invention, there is provided a computer system for identifying a predicate in a computer language as vacuous, the predicate containing one or more constant expressions, comprising means for identifying distinct variables contained in the predicate and for defining a predicate dimension number equal to the number of variables identified in the predicate, means for reducing the predicate to a logically equivalent intermediate predicate which includes no operators other than those in the set of AND, OR, =,  less than ,  less than =,  greater than ,  greater than =, IS NULL and IS NOT NULL, means for representing the set of base predicates in the intermediate predicate by a set of rectangles wherein the set of rectangles are represented in a space having a number of dimensions equal to the predicate dimension number and each rectangle has limits on each of its dimensions, the limits being finite or infinite, a finite limit on a dimension of a rectangle representing the relationship between a one of the identified variables and a one of the constant expressions in the set of base predicates, an infinite limit on a dimension of a rectangle representing the absence of a relationship between a one of the identified variables and any of the constant expressions in the set of base predicates, means for manipulating the set of rectangles whereby an AND operator in the intermediate predicate is implemented by performing an intersection on the subsets of rectangles corresponding to the portions of the intermediate predicate to which the AND operator is applied, the OR operator is implemented by performing a union on the subsets of rectangles corresponding to the portions of the intermediate predicate to which the OR operator is applied, and whereby a first selected one of the set of rectangles is discarded from the set of rectangles when the first selected one of the rectangles is empty, discarded from the set of rectangles when the selected one of the rectangles is contained within any other rectangle in the set of rectangles, merged with a second selected one of the rectangles when the two rectangles exactly agree in all dimensions but one, and means for signalling that the predicate is vacuously FALSE where the set of rectangles is empty after manipulation by the means for manipulating the set of rectangles.
According to another aspect of the present invention, there is provided the above computer system in which the predicate represents two or more object view definitions in SQL and the identification of the predicate as vacuously FALSE represents an error check to determine that the two or more object view definitions are mutually exclusive.
According to another aspect of the present invention, there is provided a method for error checking the mutual exclusivity of SQL object view definitions, comprising the steps of constructing a predicate representing two or more object view definitions in SQL, identifying distinct variables contained in the predicate and defining a predicate dimension number equal to the number of variables identified in the predicate, reducing the predicate to a logically equivalent intermediate predicate which includes no operators other than those in the set of AND, OR, =,  less than ,  less than =,  greater than ,  greater than =, IS NULL and IS NOT NULL, representing the set of base predicates in the intermediate predicate by a set of rectangles wherein the set of rectangles are represented in a space having a number of dimensions equal to the predicate dimension number and each rectangle has limits on each of its dimensions, the limits being finite or infinite, a finite limit on a dimension of a rectangle representing the relationship between a one of the identified variables and a one of the constant expressions in the set of base predicates, an infinite limit on a dimension of a rectangle representing the absence of a relationship between a one of the identified variables and any of the constant expressions in the set of base predicates, manipulating the set of rectangles whereby an AND operator in the intermediate predicate is implemented by performing an intersection on the subsets of rectangles corresponding to the portions of the intermediate predicate to which the AND operator is applied, the OR operator is implemented by performing a union on the subsets of rectangles corresponding to the portions of the intermediate predicate to which the OR operator is applied, and whereby a first selected one of the set of rectangles is discarded from the set of rectangles when the first selected one of the rectangles is empty, discarded from the set of rectangles when the selected one of the rectangles is contained within any other rectangle in the set of rectangles, merged with a second selected one of the rectangles when the two rectangles exactly agree in all dimensions but one, and signalling that the object views definitions are mutually exclusive where the set of rectangles is empty after manipulation by the means for manipulating the set of rectangles.
Media encoded with program code to effect the above-described system or method is also provided in the invention.
Advantages of the present invention include a method which is able, in many practical cases, to efficiently identify vacuous predicates.
USPTO Backgrounds
USPTO Backgrounds