Identification of vacuous predicates in computer programs

Details Identification of vacuous predicates in computer programs Identification of vacuous predicates in computer programs

1999-09-24

2004-04-27

Dam, Tuan Q. (Department: 2122)

Data processing: software development, installation, and managem

Software program development tool

Translation of code

C717S136000, C717S142000, C717S143000, C717S144000, C717S146000

Reexamination Certificate

active

06728952

ABSTRACT:

FIELD OF THE INVENTION
The present invention is directed to an improvement in computing systems and in particular to the identification of vacuous predicates in computer programs.
BACKGROUND OF THE INVENTION
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 “tautologies”, and the problem of identifying such predicates, which is known as “tautology checking”, 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
(p
1
OR q
1
) AND (p
2
OR q
2
) AND (p
3
OR q
3
) AND . . . AND (p
40
OR q
40
).
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.
SUMMARY OF THE INVENTION
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, =, <, >, <=, >=, 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 <> with logically equivalent expressions containing only one or more of AND, OR, =, <, >, <=, and >=.
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

Affiliated with

Also associated with

Rating

Identification of vacuous predicates in computer programs does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Identification of vacuous predicates in computer programs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Identification of vacuous predicates in computer programs will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3241517